PaperlayerView exact revision on arXiv

Source-linked AI summary

Randomized Social Choice Functions Under Metric Preferences

Elliot Anshelevich, John Postl

arXiv:1512.07590v2cs.AIcs.GT

TL;DR

When metric costs are unknown or difficult to elicit, social choice mechanisms must rely on ordinal rankings rather than directly selecting the cost-optimal alternative. This paper analyzes randomized mechanisms using those rankings and bounds their distortion across general metric spaces and special settings. The results improve on deterministic mechanisms in several settings, including a median-objective mechanism with distortion 4.

  • Problem

    Metric costs can be difficult to know or elicit, so the optimal alternative cannot generally be selected directly from ordinal rankings.

    Source: §1 · p. 2, §2 · p. 7

  • Method

    The paper bounds worst-case distortion for randomized mechanisms that use ordinal preferences consistent with agents’ metric costs.

    Source: §1 · p. 2, §2 · p. 7

  • Results

    Uncovered Set Min-Cover achieves median distortion 4 in arbitrary metrics, while randomized mechanisms also improve on deterministic bounds in several settings.

    Source: §1 · p. 2, §1.1 · p. 4

  • Takeaways & Limitations

    Mechanisms such as randomized dictatorship and proportional to squares can achieve better-than-known-deterministic distortion using only agents’ first preferences.

    Source: §5 · p. 27

    For arbitrary numbers of alternatives under the sum objective, randomized dictatorship is the best known mechanism and its worst-case distortion can approach 3; a generalization reaching 2 may require the full preference profile.

    Source: §5 · p. 27

Abstract

from arXiv · show

We determine the quality of randomized social choice mechanisms in a setting in which the agents have metric preferences: every agent has a cost for each alternative, and these costs form a metric. We assume that these costs are unknown to the mechanisms (and possibly even to the agents themselves), which means we cannot simply select the optimal alternative, i.e. the alternative that minimizes the total agent cost (or median agent cost). However, we do assume that the agents know their ordinal preferences that are induced by the metric space. We examine randomized social choice functions that require only this ordinal information and select an alternative that is good in expectation with respect to the costs from the metric. To quantify how good a randomized social choice function is, we bound the distortion, which is the worst-case ratio between expected cost of the alternative selected and the cost of the optimal alternative. We provide new distortion bounds for a variety of randomized mechanisms, for both general metrics and for important special cases. Our results show a sizable improvement in distortion over deterministic mechanisms.

1 Introduction

The paper studies randomized social choice under metric preferences, where ordinal rankings are available but cardinal costs may be difficult to know or elicit. It gives distortion bounds for general metrics and special settings, improving on deterministic mechanisms in several cases.

1 Introduction

  • Randomized mechanisms improve on deterministic bounds for metric preferences, including settings where no deterministic mechanism can achieve the same worst-case performance.The paper studies both sum and median objectives and explores specialized metrics.Source: §1 · p. 2, §1.2 · p. 5

1.1 Our Contributions

  • Special cases include α-decisive preferences, 1-Euclidean preferences with optimal distortion 1 + α, and simplex alternatives, where proportional to squares is fairly close to the 1 + α bound.α-decisiveness constrains how indifferent an agent can be between her first and second choices.Source: §1 · p. 3, §1.1 · pp. 3–4
  • A general randomized mechanism has sum-distortion lower bound 1 + α (2 for general metrics); randomized dictatorship is strictly better than 3, and proportional to squares is optimal for two alternatives.The two-alternative optimum is 1 + α.Source: §1.1 · p. 3
  • For the median objective, Uncovered Set Min-Cover achieves distortion 4 in arbitrary metric spaces using a probability distribution over the uncovered set.Its construction uses LP duality and properties of the uncovered set.Source: §1.1 · p. 4

1.2 Related Work

  • Prior work established deterministic distortion bounds; related randomized work overlaps on general-metric and 1-Euclidean cases, while this paper also treats decisive voters and median distortion.The paper contrasts its 1-Euclidean mechanism with a truthful mechanism in.Source: §1.2 · pp. 4–6

2 Preliminaries

The preliminaries formalize ordinal social choice when preferences arise from metric costs, and define distortion as a worst-case comparison with the true optimum. Examples illustrate how ordinal information can leave randomized and deterministic rules with different costs, while decisiveness narrows the metric setting.

Social Choice with Ordinal Preferences

  • A Condorcet method selects a Condorcet winner when one exists, while a majority method selects a first-choice alternative supported by more than half the agents when one exists.A weak Condorcet winner may tie every alternative, and neither kind of winner is guaranteed to exist.Source: §2 · p. 6

Cardinal Metric Costs

  • A metric assigns agent-alternative costs satisfying the triangle inequality, and consistent rankings place lower-cost alternatives above higher-cost ones while allowing either order for ties.The costs may be pseudo-metric, allowing distinct agents or alternatives to have distance zero.Source: §2 · p. 7

Social Cost and Distortion

  • Distortion is the worst-case ratio of a rule’s social cost to the optimum, over metrics consistent with the observed ordinal profile.The paper considers sum and median social-cost objectives and takes expected cost for randomized rules.Source: §2 · p. 7

Examples

  • For the two-alternative sum-cost example, deterministic selection of Y has distortion approaching 3, while randomized dictatorship’s expected distortion approaches 2.The example has tied ordinal preferences, although the underlying metric costs make X optimal.Source: §2 · p. 8
  • For the median-cost example, X is optimal despite more agents preferring Y, and randomized dictatorship selects X only about half the time.The median agent cost is approximately 1 for X and 2 for Y.Source: §2 · p. 8

Decisive Voters

  • An α-decisive agent’s top-choice cost is at most α times the cost of the second choice; a metric is α-decisive when every agent meets that condition.The 0-decisive setting includes cases where voters coincide with alternatives.Source: §2 · p. 9

3 Distortion of the Sum of Agent Costs

The section analyzes distortion for the sum of agent costs across general metric, 1-Euclidean, and simplex settings. It bounds or characterizes randomized mechanisms, including dictatorship, plurality, and proportional to squares, and identifies cases that reduce to two alternatives.

3.1 General Metric Spaces

  • For α-decisive metrics, no randomized mechanism can have distortion below 1 + α; this lower bound is tight for two alternatives.The α-generalized proportional-to-squares mechanism achieves distortion 1 + α when m = 2.Source: §3.1 · pp. 9, 14
  • For α-decisive metrics, the section refines distance bounds for top-choice voters, lower-bounds the optimal alternative’s social cost, and derives a distortion bound parameterized by selection probabilities.These lemmas support upper bounds for randomized mechanisms by substituting their alternative-selection probabilities.Source: §3.1 · pp. 10–11
  • Randomized dictatorship has tight distortion at most 2 + α − 2|W∗|/n, strictly below 3, while using only top choices and remaining strategy-proof.The section contrasts this with deterministic mechanisms, whose worst-case distortion is at least 3.Source: §3.1 · p. 12

3.2 1-Euclidean Preferences

  • In 1-Euclidean preferences, the optimal alternative must be the median agent’s top choice X or one of its neighbors Y and Z; comparing neighbor distances eliminates one candidate.The mechanism uses the ordinal profile to order agents and alternatives, reducing the possible optima from m to at most two before applying α-generalized proportional to squares.Source: §3.2 · pp. 15–16
  • In 1-Euclidean preferences, Algorithm 1 achieves distortion at most 1 + α, the best possible worst-case bound.When the two neighbors are equally distant from X, it selects X with probability 1.Source: §3.2 · p. 17
  • When |YX| is fixed, distortion decreases with |YX \ Y*| and is maximized at |YX| = |Y*|; the analysis reduces to two alternatives.The maximum also occurs when there are no agents left of Y and agents in |XY| have zero cost for X.Source: §3.2 · p. 18

3.3 Distortion in the (m −1)-Simplex

  • In the (m−1)-simplex setting, plurality has distortion at most 1 + 2α when preferences are α-decisive.The setting assumes alternatives are pairwise distance 1 and every agent's distance to every alternative is at most 1.Source: §3.3 · pp. 18–19
  • For high α, proportional to squares fares better; at α = 1 (general metrics), its distortion is at most 2, while plurality’s is at most 3.Source: §3.3 · p. 20
  • At α = 0, proportional to squares has distortion at most 1 + √2 ≈ 1.2071, and its bound increases more slowly than plurality's 1 + 2α.For 0.5 ≤ α ≤ 1, its bound is close to the lower bound 1 + α for all randomized mechanisms, so it is nearly optimal in that range.Source: §3.3 · p. 22

4 Median Agent Cost

For general metric spaces, randomized mechanisms face a median-distortion lower bound of 3, while Uncovered Set Min-Cover achieves an upper bound of 4. Special metric settings admit stronger guarantees, including a 1 + α bound for majority-criterion mechanisms in α-decisive simplex metrics.

4.1 General Metric Spaces

  • Randomized mechanisms have worst-case median distortion at least 3 for m ≥ 2.The section contrasts this with the deterministic lower bound of 5.Source: §4.1 · p. 22
  • Randomized dictatorship and proportional to squares have unbounded distortion for the median objective, even with m = 2.Source: §4.1 · p. 23
  • Mixing over the uncovered set can yield distortion at most 4 when every alternative covers at most half the distribution's probability mass.The mechanism uses an LP to construct a distribution satisfying this coverage condition.Source: §4.1 · p. 24
  • Uncovered Set Min-Cover has expected median distortion at most 4 in general metric spaces.It selects from the uncovered set using a distribution computed by a linear program.Source: §4.1 · pp. 23–25

4.2 Median Distortion for 1-Euclidean and Simplex Metrics

  • In 1-Euclidean settings, selecting the Condorcet winner gives median distortion at most 3.The passage states the winner is guaranteed to exist and be within a factor of 3 of the optimum.Source: §4.2 · p. 26
  • In α-decisive (m − 1)-simplex settings, any mechanism satisfying the majority criterion has median distortion at most 1 + α.This guarantee also makes plurality a good mechanism in this setting when a strict majority winner exists.Source: §4.2 · p. 26

5 Conclusion

The conclusion argues that randomized mechanisms can outperform known deterministic mechanisms with less preference information, including for the median objective. It identifies unresolved questions for arbitrary numbers of alternatives in the sum setting and broader directions for ordinal-information mechanisms.

  • Randomized mechanisms can achieve distortion better than known deterministic mechanisms using only agents' first preferences, even though the best deterministic mechanisms require the full preference profile.Source: §5 · p. 27
  • The paper reports improved distortion bounds for special metric settings, including decisive preferences, 1-Euclidean metrics, and completely dissimilar alternatives.Source: §5 · p. 27
  • For arbitrary m in the sum setting, randomized dictatorship is the best known mechanism and has worst-case distortion arbitrarily close to 3; a mechanism attaining 2 remains an open possibility.The suggested generalization of proportional to squares may be more complex and may require the full preference profile.Source: §5 · p. 27
  • The conclusion proposes studying other utility structures, limited numerical information, and normative properties of low-distortion mechanisms.Source: §5 · p. 28

Related papers

Loading 1512.07590v2…