Distortion in voting with top-t preferences

Allan Borodin; Daniel Halpern; Mohamad Latifian; Nisarg Shah

doi:10.24963/ijcai.2022/17

Distortion in voting with top-t preferences

Allan Borodin, Daniel Halpern, Mohamad Latifian^*, Nisarg Shah

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract / Description of output

A fundamental question in social choice and multi-agent systems is aggregating ordinal preferences expressed by agents into a measurably prudent collective choice. A promising line of recent work views ordinal preferences as a proxy for underlying cardinal preferences. It aims to optimize distortion, the worst-case approximation ratio of the (utilitarian) social welfare. When agents rank the set of alternatives, prior work identifies near-optimal voting rules for selecting one or more alternatives. However, ranking all the alternatives is prohibitive when there are many alternatives. In this work, we consider the setting where each agent ranks only her t favorite alternatives and identify almost tight bounds on the best possible distortion when selecting a single alternative or a committee of alternatives of a given size k. Our results also extend to approximating higher moments of social welfare. Along the way, we close a gap left open in prior work by identifying asymptotically tight distortion bounds for committee selection given full rankings.

Original language	English
Title of host publication	Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Editors	Luc De Raedt
Publisher	IJCAI Organization
Pages	116-122
Number of pages	7
ISBN (Electronic)	9781956792003
DOIs	https://doi.org/10.24963/ijcai.2022/17
Publication status	Published - 29 Jul 2022
Event	The 31st International Joint Conference on Artificial Intelligence and the 25th European Conference on Artificial Intelligence - Messe Wien, Vienna, Austria Duration: 23 Jul 2022 → 29 Jul 2022 https://ijcai-22.org/

Publication series

Name	Proceedings of the International Joint Conference on Artificial Intelligence
Publisher	IJCAI
ISSN (Print)	1045-0823

Conference

Conference	The 31st International Joint Conference on Artificial Intelligence and the 25th European Conference on Artificial Intelligence
Abbreviated title	IJCAI-ECAI 2022
Country/Territory	Austria
City	Vienna
Period	23/07/22 → 29/07/22
Internet address	https://ijcai-22.org/

Keywords / Materials (for Non-textual outputs)

agent-based and multi-agent systems
computational social choice

Access to Document

10.24963/ijcai.2022/17

Cite this

Borodin, A., Halpern, D., Latifian, M., & Shah, N. (2022). Distortion in voting with top-t preferences. In L. De Raedt (Ed.), Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (pp. 116-122). ( Proceedings of the International Joint Conference on Artificial Intelligence). IJCAI Organization. https://doi.org/10.24963/ijcai.2022/17

@inproceedings{bfa9b9d1ee7a4f51805317236d9722af,

title = "Distortion in voting with top-t preferences",

abstract = "A fundamental question in social choice and multi-agent systems is aggregating ordinal preferences expressed by agents into a measurably prudent collective choice. A promising line of recent work views ordinal preferences as a proxy for underlying cardinal preferences. It aims to optimize distortion, the worst-case approximation ratio of the (utilitarian) social welfare. When agents rank the set of alternatives, prior work identifies near-optimal voting rules for selecting one or more alternatives. However, ranking all the alternatives is prohibitive when there are many alternatives. In this work, we consider the setting where each agent ranks only her t favorite alternatives and identify almost tight bounds on the best possible distortion when selecting a single alternative or a committee of alternatives of a given size k. Our results also extend to approximating higher moments of social welfare. Along the way, we close a gap left open in prior work by identifying asymptotically tight distortion bounds for committee selection given full rankings.",

keywords = "agent-based and multi-agent systems, computational social choice",

author = "Allan Borodin and Daniel Halpern and Mohamad Latifian and Nisarg Shah",

year = "2022",

month = jul,

day = "29",

doi = "10.24963/ijcai.2022/17",

language = "English",

series = " Proceedings of the International Joint Conference on Artificial Intelligence",

publisher = "IJCAI Organization",

pages = "116--122",

editor = "{De Raedt}, Luc",

booktitle = "Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence",

note = "The 31st International Joint Conference on Artificial Intelligence and the 25th European Conference on Artificial Intelligence, IJCAI-ECAI 2022 ; Conference date: 23-07-2022 Through 29-07-2022",

url = "https://ijcai-22.org/",

}

Borodin, A, Halpern, D, Latifian, M & Shah, N 2022, Distortion in voting with top-t preferences. in L De Raedt (ed.), Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence. Proceedings of the International Joint Conference on Artificial Intelligence, IJCAI Organization, pp. 116-122, The 31st International Joint Conference on Artificial Intelligence and the 25th European Conference on Artificial Intelligence, Vienna, Austria, 23/07/22. https://doi.org/10.24963/ijcai.2022/17

Distortion in voting with top-t preferences. / Borodin, Allan; Halpern, Daniel; Latifian, Mohamad et al.
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence. ed. / Luc De Raedt. IJCAI Organization, 2022. p. 116-122 ( Proceedings of the International Joint Conference on Artificial Intelligence).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Distortion in voting with top-t preferences

AU - Borodin, Allan

AU - Halpern, Daniel

AU - Latifian, Mohamad

AU - Shah, Nisarg

PY - 2022/7/29

Y1 - 2022/7/29

N2 - A fundamental question in social choice and multi-agent systems is aggregating ordinal preferences expressed by agents into a measurably prudent collective choice. A promising line of recent work views ordinal preferences as a proxy for underlying cardinal preferences. It aims to optimize distortion, the worst-case approximation ratio of the (utilitarian) social welfare. When agents rank the set of alternatives, prior work identifies near-optimal voting rules for selecting one or more alternatives. However, ranking all the alternatives is prohibitive when there are many alternatives. In this work, we consider the setting where each agent ranks only her t favorite alternatives and identify almost tight bounds on the best possible distortion when selecting a single alternative or a committee of alternatives of a given size k. Our results also extend to approximating higher moments of social welfare. Along the way, we close a gap left open in prior work by identifying asymptotically tight distortion bounds for committee selection given full rankings.

AB - A fundamental question in social choice and multi-agent systems is aggregating ordinal preferences expressed by agents into a measurably prudent collective choice. A promising line of recent work views ordinal preferences as a proxy for underlying cardinal preferences. It aims to optimize distortion, the worst-case approximation ratio of the (utilitarian) social welfare. When agents rank the set of alternatives, prior work identifies near-optimal voting rules for selecting one or more alternatives. However, ranking all the alternatives is prohibitive when there are many alternatives. In this work, we consider the setting where each agent ranks only her t favorite alternatives and identify almost tight bounds on the best possible distortion when selecting a single alternative or a committee of alternatives of a given size k. Our results also extend to approximating higher moments of social welfare. Along the way, we close a gap left open in prior work by identifying asymptotically tight distortion bounds for committee selection given full rankings.

KW - agent-based and multi-agent systems

KW - computational social choice

U2 - 10.24963/ijcai.2022/17

DO - 10.24963/ijcai.2022/17

M3 - Conference contribution

T3 - Proceedings of the International Joint Conference on Artificial Intelligence

SP - 116

EP - 122

BT - Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence

A2 - De Raedt, Luc

PB - IJCAI Organization

T2 - The 31st International Joint Conference on Artificial Intelligence and the 25th European Conference on Artificial Intelligence

Y2 - 23 July 2022 through 29 July 2022

ER -

Distortion in voting with top-t preferences

Abstract / Description of output

Publication series

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Cite this