Leadership in Congestion Games: Multiple User Classes and Non-Singleton Actions
Authors: Alberto Marchesi, Matteo Castiglioni, Nicola Gatti
IJCAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, for both settings, we provide mixed-integer linear programming formulations, and we experimentally evaluate their scalability on both random game instances and worst-case instances based on our hardness reductions. [...] 7 Experimental Results [...] We test the MILP formulations proposed in Section 6 on randomly generated games, which represent instances of average-case complexity, and games based on the reductions provided in the proofs of Theorems 1 and 6, which, instead, represent worst-case complexity instances. All the experiments are run on a UNIX machine with a total of 32 cores working at 2.3 GHz, equipped with 128 GB of RAM. Each instance is solved on a single core within a time limit of 3600 seconds. We use GUROBI 7.0 (with Python interface) as MILP solver. |
| Researcher Affiliation | Academia | Alberto Marchesi , Matteo Castiglioni and Nicola Gatti Politecnico di Milano, Piazza Leonardo da Vinci 32, Milano, Italy {alberto.marchesi, matteo.castiglioni, nicola.gatti}@polimi.it |
| Pseudocode | No | The paper describes a dynamic programming algorithm via a recursive equation (Lemma 4) but does not provide structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper mentions using 'GUROBI 7.0 (with Python interface) as MILP solver' but does not provide any specific access to source code for the methodology described in the paper. |
| Open Datasets | No | The paper describes generating 'random game instances' and 'worst-case instances' but does not provide concrete access information (link, DOI, repository, formal citation) for publicly available or open datasets. |
| Dataset Splits | No | The paper generates random game instances and worst-case instances but does not provide specific dataset split information (exact percentages, sample counts, or detailed splitting methodology) for training, validation, or testing. |
| Hardware Specification | Yes | All the experiments are run on a UNIX machine with a total of 32 cores working at 2.3 GHz, equipped with 128 GB of RAM. |
| Software Dependencies | Yes | We use GUROBI 7.0 (with Python interface) as MILP solver. |
| Experiment Setup | Yes | For T -class SSCGs, we generate random game instances with r {10, 20, 30, 40, 50, 60, 70, 80, 90, 100} resources and T {1, 2, 3, 4} classes, with nt {0.2 r, 0.5 r, r} followers per class t T and |At| = 0.5 r actions per class t T . Cost functions are randomly generated by sampling uniformly from {1, . . . , nr T}. For general SCGs, we generate instances with r {5, 10, 15, 20, 25} resources and n {r, 2 r, 3 r} followers, with |ap| {1, 2, 3, 4, 5} resources per action ap Ap and |Ap| = 0.5 r actions per player p N. Cost functions are randomly generated by sampling uniformly from {1, . . . , nr}. We build a testbed with 20 game instances per combination of the parameters. |