Correlated Voting
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 366-371.
Abstract
We study the social choice problem where a group of n voters report their preferences over alternatives and a voting rule is used to select an alternative. We show that when the preferences of voters are positively correlated according to the Kendall-Tau distance, the probability that any scoring rule is not ex post incentive compatible (EPIC) goes to zero exponentially fast with the number of voters, improving over the previously known rate of 1/√n for independent preferences. Motivated by rank-order models from machine learning, we introduce two examples of positively-correlated models, namely Conditional Mallows and Conditional Plackett-Luce. Conditional Mallows satisfies Kendall-Tau correlation and fits our positive result. We also prove that Conditional Plackett-Luce becomes EPIC exponentially quickly.
@inproceedings{ijcai2016p59,
title = {Correlated Voting},
author = {Mandal, Debmalya and Parkes, David C.},
booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-16}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Subbarao Kambhampati},
pages = {366--371},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/59},
}
TY - CPAPER TI - Correlated Voting AU - Mandal, Debmalya AU - Parkes, David C. T2 - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2016 SP - 366 EP - 371 UR - https://ijcai.org/proceedings/2016/59 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
