Logo image
Back
Learning-Augmented Metric Distortion via (p,q)-Veto Core
Conference proceeding   Open access

Learning-Augmented Metric Distortion via (p,q)-Veto Core

Ben Berger, Michal Feldman, Vasilis Gkatzelis and Xizhi Tan
Proceedings of the 25th ACM Conference on Economics and Computation, pp 984-984
08 Jul 2024
DOI: https://doi.org/10.1145/3670865.3673456
url
https://arxiv.org/abs/2307.07495View
SubmittedarXiv.org - Non-exclusive license to distribute,  Open

Abstract

Theory of computation -- Theory and algorithms for application domains -- Algorithmic game theory and mechanism design
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. A key concept here is the (p, q)-veto core, with p ∈ Δ(V) and q ∈ Δ(C) being normalized weight vectors representing voters' veto power and candidates' support, respectively. The (p, q)-veto core corresponds to a set of winners from a specific class of deterministic algorithms. Notably, the optimal distortion of 3 is obtained from this class, by selecting veto core candidates using uniform p and q proportional to candidates' plurality scores. Bounding the distortion of other algorithms from this class is an open problem. Our contribution is twofold. First, we establish upper bounds on the distortion of candidates from the (p, q)-veto core for arbitrary weight vectors p and q. Second, we revisit the metric distortion problem through the learning-augmented framework, which equips the algorithm with a (machine-learned) prediction regarding the optimal candidate. The quality of this prediction is unknown, and the goal is to optimize the algorithm's performance under accurate predictions (known as consistency), while simultaneously providing worst-case guarantees under arbitrarily inaccurate predictions (known as robustness). We propose an algorithm that chooses candidates from the (p, q)-veto core, using a prediction-guided q vector and, leveraging our distortion bounds, we prove that this algorithm achieves the optimal robustness-consistency trade-off. A full version of this paper can be found at https://arxiv.org/pdf/2307.07495.

Metrics

6 Record Views

Details

Logo image