Metric Distortion with Elicited Pairwise Comparisons

Metric Distortion with Elicited Pairwise Comparisons

Soroush Ebadian, Daniel Halpern, Evi Micha

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Main Track. Pages 2791-2798. https://doi.org/10.24963/ijcai.2024/309

In many social choice applications, information about individuals' preferences can only be elicited using a limited number of pairwise comparisons. In these cases, the task is twofold: we must first choose the queries, and then second, we must aggregate the responses to choose an outcome. We study the problem of designing algorithms for this setting. To compare the effectiveness of different outcomes, we use the metric distortion framework. In addition, we consider various constraints on the query algorithms, namely, placing restrictions on how the choice of the next query may depend on previous answers. Our main contributions are nearly optimal algorithms for all settings considered.
Keywords:
Game Theory and Economic Paradigms: GTEP: Computational social choice