Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2603.04312 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908866189459456 |
|---|---|
| author | Song, Haoyu Nguyen, Thanh |
| author_facet | Song, Haoyu Nguyen, Thanh |
| contents | The core is a central concept in multi-winner social choice, ensuring that no coalition of voters can support an alternative outcome whose size or cost exceeds the group's share of the electorate. This idea originates from the Lindahl equilibrium in classical public goods theory. Yet Lindahl equilibria may fail to exist when voters have ordinal preferences over a finite set of outcomes and monetary transfers are not allowed. We introduce Lindahl Equilibrium with Ordinal Preferences (LEO), extending the equilibrium framework to discrete collective choice. Using LEO, we construct randomized outcomes that satisfy (approximate) core constraints for a probabilistic set of voters, while ensuring that each voter is represented with high probability. We also provide a deterministic approximate core guarantee with a factor of 6.24, improving on the previous bound of 32. In structured environments, these outcomes can be computed efficiently. Overall, our results extend classical equilibrium concepts, providing a normative foundation for proportional representation and practical algorithms for applications in voting and fair machine learning. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_04312 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Ordinal Lindahl Equilibrium for Voting Song, Haoyu Nguyen, Thanh Computer Science and Game Theory The core is a central concept in multi-winner social choice, ensuring that no coalition of voters can support an alternative outcome whose size or cost exceeds the group's share of the electorate. This idea originates from the Lindahl equilibrium in classical public goods theory. Yet Lindahl equilibria may fail to exist when voters have ordinal preferences over a finite set of outcomes and monetary transfers are not allowed. We introduce Lindahl Equilibrium with Ordinal Preferences (LEO), extending the equilibrium framework to discrete collective choice. Using LEO, we construct randomized outcomes that satisfy (approximate) core constraints for a probabilistic set of voters, while ensuring that each voter is represented with high probability. We also provide a deterministic approximate core guarantee with a factor of 6.24, improving on the previous bound of 32. In structured environments, these outcomes can be computed efficiently. Overall, our results extend classical equilibrium concepts, providing a normative foundation for proportional representation and practical algorithms for applications in voting and fair machine learning. |
| title | Ordinal Lindahl Equilibrium for Voting |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2603.04312 |