Abstract
We consider the problem of selecting a committee of $k$ alternatives among
$m$ alternatives, based on the ordinal rank list of voters. Our focus is on the
case where both voters and alternatives lie on a metric space-specifically, on
the line-and the objective is to minimize the additive social cost. The
additive social cost is the sum of the costs for all voters, where the cost for
each voter is defined as the sum of their distances to each member of the
selected committee.
We propose a new voting rule, the Polar Comparison Rule, which achieves upper
bounds of $1 + \sqrt{2} \approx 2.41$ and $7/3 \approx 2.33$ distortions for $k
= 2$ and $k = 3$, respectively, and we show that these bounds are tight.
Furthermore, we generalize this rule, showing that it maintains a distortion of
roughly $7/3$ based on the remainder of the committee size when divided by
three. We also establish lower bounds on the achievable distortion based on the
parity of $k$ and for both small and large committee sizes.
BibTeX
@inproceedings{Afshinmehr_AAMAS25,
TITLE = {{EFX} Allocations and Orientations on Bipartite Multi-Graphs: {A} Complete Picture},
AUTHOR = {Afshinmehr, Mahyar and Danaei, Alireza and Kazemi, Mehrafarin and Mehlhorn, Kurt and Rathi, Nidhi},
LANGUAGE = {eng},
PUBLISHER = {ACM},
YEAR = {2025},
PUBLREMARK = {Accepted},
MARGINALMARK = {$\bullet$},
ABSTRACT = {We consider the problem of selecting a committee of $k$ alternatives among<br>$m$ alternatives, based on the ordinal rank list of voters. Our focus is on the<br>case where both voters and alternatives lie on a metric space-specifically, on<br>the line-and the objective is to minimize the additive social cost. The<br>additive social cost is the sum of the costs for all voters, where the cost for<br>each voter is defined as the sum of their distances to each member of the<br>selected committee.<br> We propose a new voting rule, the Polar Comparison Rule, which achieves upper<br>bounds of $1 + \sqrt{2} \approx 2.41$ and $7/3 \approx 2.33$ distortions for $k<br>= 2$ and $k = 3$, respectively, and we show that these bounds are tight.<br>Furthermore, we generalize this rule, showing that it maintains a distortion of<br>roughly $7/3$ based on the remainder of the committee size when divided by<br>three. We also establish lower bounds on the achievable distortion based on the<br>parity of $k$ and for both small and large committee sizes.<br>},
BOOKTITLE = {Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025)},
ADDRESS = {Detroit, MI, USA},
}Endnote
%0 Conference Proceedings
%A Afshinmehr, Mahyar
%A Danaei, Alireza
%A Kazemi, Mehrafarin
%A Mehlhorn, Kurt
%A Rathi, Nidhi
%+ External Organizations
External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T EFX Allocations and Orientations on Bipartite Multi-Graphs: A Complete
Picture :
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-6A9E-6
%D 2024
%B 24th International Conference on Autonomous Agents and Multiagent Systems
%Z date of event: 2025-05-19 - 2025-05-23
%C Detroit, MI, USA
%X We consider the problem of selecting a committee of $k$ alternatives among<br>$m$ alternatives, based on the ordinal rank list of voters. Our focus is on the<br>case where both voters and alternatives lie on a metric space-specifically, on<br>the line-and the objective is to minimize the additive social cost. The<br>additive social cost is the sum of the costs for all voters, where the cost for<br>each voter is defined as the sum of their distances to each member of the<br>selected committee.<br> We propose a new voting rule, the Polar Comparison Rule, which achieves upper<br>bounds of $1 + \sqrt{2} \approx 2.41$ and $7/3 \approx 2.33$ distortions for $k<br>= 2$ and $k = 3$, respectively, and we show that these bounds are tight.<br>Furthermore, we generalize this rule, showing that it maintains a distortion of<br>roughly $7/3$ based on the remainder of the committee size when divided by<br>three. We also establish lower bounds on the achievable distortion based on the<br>parity of $k$ and for both small and large committee sizes.<br>
%K Computer Science, Computer Science and Game Theory, cs.GT
%B Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems
%I ACM