Catcher-Evader Games
Authors: Yuqian Li, Vincent Conitzer, Dmytro Korzhyk
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We show that computing Stackelberg strategies is NP-hard, but give an algorithm for computing a Nash equilibrium that performs well in experiments. We also prove that the Nash equilibria of these games satisfy the interchangeability property, so that equilibrium selection is not an issue. (...) While we have been unable to show that our algorithm is guaranteed to require at most polynomially many iterations, it requires few iterations in experiments. |
| Researcher Affiliation | Academia | Yuqian Li, Vincent Conitzer, Dmytro Korzhyk Department of Computer Science, Duke University {yuqian, conitzer}@cs.duke.edu, dima.korzhyk@gmail.com. Dmytro contributed to this paper while he was a Ph.D. student at Duke University. |
| Pseudocode | Yes | We now present our algorithm. The algorithm is significantly more involved than earlier algorithms, notably requiring a min-cost-flow subroutine. (...) The main algorithm is Algorithm 1. After initializing, the algorithm repeatedly loops through Algorithms 2, 3, and 4, which together provably (eventually) increase the catcher s (allocated) resource amount while maintaining equilibrium. |
| Open Source Code | No | The paper states, 'Note that we implemented our algorithm completely in Python (including the min-cost network flow subroutine).', but does not provide any link or explicit statement about the availability of the source code. |
| Open Datasets | No | The paper mentions generating its own data for experiments: 'In our experiments, parameters r, b, and d are generated uniformly at random from {1, . . . , 10} (or { 10, . . . , 1}). Each instance of size n has n evaders and n sites; for each n we solved 20 instances.' It does not refer to any publicly available dataset. |
| Dataset Splits | No | The paper mentions generating its own random instances for experiments but does not provide specific details on train/validation/test splits, only that it 'solved 20 instances' for each size n. |
| Hardware Specification | No | The paper does not provide specific hardware details (e.g., GPU/CPU models, memory amounts) used for running its experiments. It only mentions 'we implemented our algorithm completely in Python'. |
| Software Dependencies | No | The paper mentions 'we implemented our algorithm completely in Python', but does not provide specific version numbers for Python or any other libraries or subroutines used. |
| Experiment Setup | No | The paper describes how the instances for experiments were generated ('parameters r, b, and d are generated uniformly at random from {1, . . . , 10} (or { 10, . . . , 1}). Each instance of size n has n evaders and n sites; for each n we solved 20 instances.') but does not provide specific experimental setup details such as hyperparameters, optimizer settings, or training configurations. |