Computational Aspects of Equilibria in Discrete Preference Games
Authors: Phani Raj Lolakapuri, Umang Bhaskar, Ramasuri Narayanam, Gyana R Parija, Pankaj S Dayama
IJCAI 2019 | Conference PDF | Archive PDF | Plain Text | 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 finite, 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 {p.lolakapuri, umang}@tifr.res.in, {ramasurn, gyana.parija, pankajdayama}@in.ibm.com |
| 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. |