Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2505.06028 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918015058051072 |
|---|---|
| author | Caizergues, Emma Durand, François Noy, Marc de Panafieu, Élie Ravelomanana, Vlady |
| author_facet | Caizergues, Emma Durand, François Noy, Marc de Panafieu, Élie Ravelomanana, Vlady |
| contents | We study the probability that a given candidate is an alpha-winner, i.e. a candidate preferred to each other candidate j by a fraction alpha_j of the voters. This extends the classical notion of Condorcet winner, which corresponds to the case alpha = (1/2, ..., 1/2). Our analysis is conducted under the general assumption that voters have independent preferences, illustrated through applications to well-known models such as Impartial Culture and the Mallows model. While previous works use probabilistic arguments to derive the limiting probability as the number of voters tends to infinity, we employ techniques from the field of analytic combinatorics to compute convergence rates and provide a method for obtaining higher-order terms in the asymptotic expansion. In particular, we establish that the probability of a given candidate being the Condorcet winner in Impartial Culture is a_0 + a_{1, n} n^{-1/2} + O(n^{-1}), where we explicitly provide the values of the constant a_0 and the coefficient a_{1, n}, which depends solely on the parity of the number of voters n. Along the way, we derive technical results in multivariate analytic combinatorics that may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_06028 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Probability of a Condorcet Winner for Large Electorates: An Analytic Combinatorics Approach Caizergues, Emma Durand, François Noy, Marc de Panafieu, Élie Ravelomanana, Vlady Computer Science and Game Theory Combinatorics 91B12, 05A15, 05A16 We study the probability that a given candidate is an alpha-winner, i.e. a candidate preferred to each other candidate j by a fraction alpha_j of the voters. This extends the classical notion of Condorcet winner, which corresponds to the case alpha = (1/2, ..., 1/2). Our analysis is conducted under the general assumption that voters have independent preferences, illustrated through applications to well-known models such as Impartial Culture and the Mallows model. While previous works use probabilistic arguments to derive the limiting probability as the number of voters tends to infinity, we employ techniques from the field of analytic combinatorics to compute convergence rates and provide a method for obtaining higher-order terms in the asymptotic expansion. In particular, we establish that the probability of a given candidate being the Condorcet winner in Impartial Culture is a_0 + a_{1, n} n^{-1/2} + O(n^{-1}), where we explicitly provide the values of the constant a_0 and the coefficient a_{1, n}, which depends solely on the parity of the number of voters n. Along the way, we derive technical results in multivariate analytic combinatorics that may be of independent interest. |
| title | Probability of a Condorcet Winner for Large Electorates: An Analytic Combinatorics Approach |
| topic | Computer Science and Game Theory Combinatorics 91B12, 05A15, 05A16 |
| url | https://arxiv.org/abs/2505.06028 |