Learning-Augmented Metric Distortion via (p,q)-Veto Core
Ben Berger, Michal Feldman, Vasilis Gkatzelis, Xizhi Tan · 2024
In the metric distortion problem there is a set of candidates C and voters V within the same metric space. The goal is to select a candidate minimizing the social cost, defined as the sum of distances of the selected candidate from all the voters, and the challenge arises from the algorithm receiving only ordinal input --- each voter's list of candidates ranked by distance --- while the objective function is cardinal, determined by the underlying metric. The distortion of an algorithm is its worst-case approximation factor with respect to the optimal social cost.