Nearly Tight Bounds on Approximate Equilibria in Spatial Competition on the Line
Authors: Umang Bhaskar, Soumyajit Pyne
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our work studies approximate equilibria in this model, where a strategy profile is an (additive) ϵ-equilibria if no candidate can increase their votes by ϵ, and provides tight or nearly-tight bounds on the approximation ϵ achievable. We show that for 3 candidates, for any distribution of the voters, ϵ 1/12. Thus, somewhat surprisingly, for any distribution of the voters and any strategy profile of the candidates, at least 1/12th of the total votes is always left on the table. Extending this, we show that in the worst case, there exist voter distributions for which ϵ 1/6, and this is tight: one can always compute a 1/6-approximate equilibria in polynomial time. We then study the general case of m candidates, and show that as m grows large, we get closer to an exact equilibrium: one can always obtain a 1/(m + 1)-approximate equilibria in polynomial time. We show this bound is asymptotically tight, by giving voter distributions for which ϵ 1/(m + 3). |
| Researcher Affiliation | Academia | Umang Bhaskar and Soumyajit Pyne Tata Institute of Fundamental Research, Mumbai EMAIL, EMAIL |
| Pseudocode | No | The paper describes algorithms and proofs in narrative text, for example, 'Proof. Let x1 = Cut(0, 1/3) and x3 = Cut(0, 2/3). Then F(x1) = F(x3) F(x1) = 1 F(x3) = 1/3. Keeping x1 and x3 fixed as the equilibrium locations for candidates 1 and 3, we will try and find a location for candidate 2 to obtain an equilibrium.' However, it does not include any clearly labeled pseudocode blocks or algorithm listings. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code, nor does it provide links to any code repositories. It only mentions 'All proofs missing in the paper are given in the full version (Bhaskar and Pyne 2024)', referring to a more complete written work. |
| Open Datasets | No | The paper studies a theoretical model involving a 'unit mass of voters is distributed in the interval [0, 1] according to a density function f'. This refers to a mathematical distribution, not an actual dataset with concrete access information. |
| Dataset Splits | No | The paper focuses on theoretical analysis of voter distributions and approximate equilibria, not on empirical experiments using datasets. Therefore, there is no mention of training/test/validation dataset splits. |
| Hardware Specification | No | The paper presents theoretical bounds and algorithms and does not describe any computational experiments that would require specific hardware. No hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and focuses on mathematical proofs and algorithm descriptions without detailing any implementation. Therefore, it does not list any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical, providing bounds and algorithms for approximate equilibria. It does not describe any empirical experiments, and thus no experimental setup details, hyperparameters, or training configurations are provided. |