From Independence of Clones to Composition Consistency: A Hierarchy of Barriers to Strategic Nomination
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915169749172224 |
|---|---|
| author | Berker, Ratip Emin Casacuberta, Sílvia Robinson, Isaac Ong, Christopher Conitzer, Vincent Elkind, Edith |
| author_facet | Berker, Ratip Emin Casacuberta, Sílvia Robinson, Isaac Ong, Christopher Conitzer, Vincent Elkind, Edith |
| contents | We study two axioms for social choice functions that capture the impact of similar candidates: independence of clones (IoC) and composition consistency (CC). We clarify the relationship between these axioms by observing that CC is strictly more demanding than IoC, and investigate whether common voting rules that are known to be independent of clones (such as STV, Ranked Pairs, Schulze, and Split Cycle) are composition-consistent. While for most of these rules the answer is negative, we identify a variant of Ranked Pairs that satisfies CC. Further, we show how to efficiently modify any (neutral) social choice function so that it satisfies CC, while maintaining its other desirable properties. Our transformation relies on the hierarchical representation of clone structures via PQ-trees. We extend our analysis to social preference functions. Finally, we interpret IoC and CC as measures of robustness against strategic manipulation by candidates, with IoC corresponding to strategy-proofness and CC corresponding to obvious strategy-proofness. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_16973 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | From Independence of Clones to Composition Consistency: A Hierarchy of Barriers to Strategic Nomination Berker, Ratip Emin Casacuberta, Sílvia Robinson, Isaac Ong, Christopher Conitzer, Vincent Elkind, Edith Computer Science and Game Theory 91B12, 91B14, 68T01, 68Q25 F.2; I.2; J.4 We study two axioms for social choice functions that capture the impact of similar candidates: independence of clones (IoC) and composition consistency (CC). We clarify the relationship between these axioms by observing that CC is strictly more demanding than IoC, and investigate whether common voting rules that are known to be independent of clones (such as STV, Ranked Pairs, Schulze, and Split Cycle) are composition-consistent. While for most of these rules the answer is negative, we identify a variant of Ranked Pairs that satisfies CC. Further, we show how to efficiently modify any (neutral) social choice function so that it satisfies CC, while maintaining its other desirable properties. Our transformation relies on the hierarchical representation of clone structures via PQ-trees. We extend our analysis to social preference functions. Finally, we interpret IoC and CC as measures of robustness against strategic manipulation by candidates, with IoC corresponding to strategy-proofness and CC corresponding to obvious strategy-proofness. |
| title | From Independence of Clones to Composition Consistency: A Hierarchy of Barriers to Strategic Nomination |
| topic | Computer Science and Game Theory 91B12, 91B14, 68T01, 68Q25 F.2; I.2; J.4 |
| url | https://arxiv.org/abs/2502.16973 |