Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Computational Aspects of Equilibria in Discrete Preference Games
Authors: Phani Raj Lolakapuri, Umang Bhaskar, Ramasuri Narayanam, Gyana R Parija, Pankaj S Dayama
IJCAI 2019 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the complexity of equilibrium computation in discrete preference games. These games were introduced by Chierichetti, Kleinberg, and Oren (EC 13, JCSS 18) to model decision-making by agents in a social network that choose a strategy from a ο¬nite, discrete set, balancing between their intrinsic preferences for the strategies and their desire to choose a strategy that is similar to their neighbours. We show that in general, equilibrium computation in discrete preference games is PLS-complete, even in the simple case where each agent has a constant number of neighbours. On the positive side, we show that if the metric space is a tree metric, or is the product of path metrics, then the equilibrium can be computed in polynomial time. |
| Researcher Affiliation | Collaboration | 1TIFR Mumbai, India 2IBM Research, India EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1 Tree Metric Algo |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | This is a theoretical paper and does not describe the use of any datasets. |
| Dataset Splits | No | This is a theoretical paper and does not describe the use of any datasets or dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not mention specific ancillary software details with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup or hyperparameters. |