Boolean Games: Inferring Agents' Goals Using Taxation Queries
Authors: Abhijin Adiga, Sarit Kraus, Oleg Maksimov, S. S. Ravi
IJCAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We present experimental results to demonstrate the efficacy our algorithms. We show experimentally that our coloring-based inference algorithm uses significantly fewer queries compared to inferring goals one at a time. Further, the coloring-based approach also uses significantly less time even for games with 36,000 agents. |
| Researcher Affiliation | Academia | 1Biocomplexity Institute and Initiative, University of Virginia, Charlottesville, VA, USA 2Department of Computer Science Bar Ilan University, Ramat Gan, Israel |
| Pseudocode | Yes | Algorithm 1: Inference algorithm for threshold functions. |
| Open Source Code | No | The paper does not provide any links or explicit statements about open-sourcing the code for the described methodology. |
| Open Datasets | No | The paper describes generating its own 'networks and agents goals' for experiments rather than using a pre-existing public dataset: 'We ran an extensive set of experiments creating a large number of networks and agents goals by varying the number of nodes, the minimum degree, the number of variables in an agent s goal controlled by the agent and by others and the threshold.' |
| Dataset Splits | No | The paper describes generating its own experimental data and does not mention specific training, validation, or test dataset splits in the conventional sense. |
| Hardware Specification | No | The paper mentions 'under the assumption that there are 20 processors that can be used for running the searches of the same color class, in parallel' but does not specify any particular hardware models (CPU, GPU, memory, etc.). |
| Software Dependencies | No | The paper does not list specific software dependencies with version numbers. |
| Experiment Setup | Yes | We ran an extensive set of experiments creating a large number of networks and agents goals by varying the number of nodes, the minimum degree, the number of variables in an agent s goal controlled by the agent and by others and the threshold. In each network, nodes represent agents and the network itself represents the goal overlap graph. We ensured this by creating for each edge {u, v}, a variable xu,v that appears only in the goals of u and v. To make the game general, we also created other variables and generated control sets for nodes so that for each node (agent) i, the sets Φi and Γi have a nonempty intersection. For each agent i, we generated a random threshold value in the range [1 .. |Γi|]. Let us first consider the SEQ approach which infers thresholds one node at a time. For each node i, our program finds its threshold by inhibiting all other nodes and constructing {0,1}-taxation queries to do binary search over the possible threshold values of i. Next, we generated a Brooks coloring of the graph using the simple greedy algorithm [West, 2003]. This method uses Δ + 1 colors, where Δ is the maximum node degree. |