Metric Distortion with Elicited Pairwise Comparisons

Soroush Ebadian; Daniel Halpern; Evi Micha

IJCAI 2024poster1 citations

Metric Distortion with Elicited Pairwise Comparisons

Soroush Ebadian, Daniel Halpern, Evi Micha

Abstract

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.

Game Theory and Economic Paradigms: GTEP: Computational social choice

BibTeX

@inproceedings{ijcai2024p309,
  title     = {Metric Distortion with Elicited Pairwise Comparisons},
  author    = {Ebadian, Soroush and Halpern, Daniel and Micha, Evi},
  booktitle = {Proceedings of the Thirty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-24}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Kate Larson},
  pages     = {2791--2798},
  year      = {2024},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2024/309},
  url       = {https://doi.org/10.24963/ijcai.2024/309},
}