Optimal Metric Distortion with Predictions

Ben Berger, Michal Feldman, Vasilis Gkatzelis, Xizhi Tan

Introduction

The metric distortion problem is a cornerstone of social choice theory. Imagine selecting a location for a public park: while residents can easily rank potential sites (e.g., Site A > Site B > Site C), the underlying travel distances—the cardinal costs—are often unknown to the decision-maker. The goal is to select a candidate that minimizes the total social cost (sum of distances) using only these ordinal rankings. The "distortion" of a voting rule measures its worst-case performance relative to an omniscient algorithm that knows all distances.

Historically, deterministic algorithms have been limited by a lower bound of 3 for distortion. However, modern decision-making often incorporates external "predictions"—such as historical data or polling—about the optimal candidate. This research introduces the first learning-augmented algorithms for metric distortion, exploring how to leverage these predictions to surpass traditional theoretical limits without sacrificing safety.

Methodology: The $LA_\delta$ Algorithm

The authors utilize the $(p, q)$-veto core, a framework where voters have "veto power" ($p$) and candidates have "support" ($q$). By generalizing this framework, the researchers established new upper bounds on distortion for arbitrary weight distributions.

Central to this work is the $LA_\delta$ algorithm, which is parameterized by a confidence value $\delta \in [0, 1)$. This parameter allows a designer to tune the algorithm's reliance on a prediction $\hat{c}$:

  • Consistency: The performance guarantee when the prediction is correct.
  • Robustness: The performance guarantee when the prediction is incorrect.
Consistency and robustness as functions of the confidence parameter $\delta$. As confidence increases, consistency improves while robustness degrades.

As shown in the figure above, a higher $\delta$ indicates greater trust in the prediction, leading to a lower (better) consistency score but a higher (worse) robustness score.

Key Insights: The Pareto Frontier

A primary contribution of this paper is the identification of the fundamental trade-off between consistency and robustness. The authors prove that an algorithm cannot be perfectly consistent without becoming infinitely non-robust. They map out the exact Pareto frontier, representing the set of all mathematically optimal trade-offs.

The Pareto frontier of consistency versus robustness. The curve illustrates the optimal trade-off achievable by deterministic algorithms, starting from the traditional bound of (3,3).

Interestingly, the research demonstrates that even "weak" predictions (simply the name of a predicted winner) are as powerful as "strong" predictions (exact distance data) in terms of the achievable distortion bounds.

Key Results and Breaking the "3" Barrier

The $LA_\delta$ algorithm achieves a consistency of $\frac{3-\delta}{1+\delta}$ and a robustness of $\frac{3+\delta}{1-\delta}$. This result is significant because:

  1. Breaking the Limit: When $\delta > 0$ and the prediction is accurate, the algorithm achieves a distortion strictly less than 3, surpassing the long-standing hard limit for deterministic voting rules.
  2. Optimality: The authors prove that this trade-off is mathematically optimal; no deterministic algorithm can achieve a better combination of consistency and robustness.
  3. Refined Bounds: For "decisive" voters—those with a strong preference for their top choice—the distortion bounds improve further, potentially reaching a distortion of 2 in peer-selection settings.

Limitations and Future Directions

While this work sets a new standard for deterministic voting rules with predictions, several avenues for future research remain:

  • Randomized Algorithms: Randomized rules are known to achieve lower distortion (near 2). Extending this learning-augmented framework to the randomized setting could yield even tighter bounds.
  • Prediction Quality: The current model treats predictions as a "black box." Future work could investigate how structured prediction errors or biased data sources affect the algorithm's performance.
  • Multi-winner Elections: The current focus is on single-winner selection. Applying these principles to committee selection or multi-winner scenarios presents a natural next step for the field.

Summary updated

BibTeX
@inproceedings{berger2023optimal,
  author = {Ben Berger and Michal Feldman and Vasilis Gkatzelis and Xizhi Tan},
  title = {{Optimal Metric Distortion with Predictions}},
  booktitle = {EC},
  year = {2023},
}
Figure