PaperlayerView exact revision on arXiv

Source-linked AI summary

Condorcet-Winning Sets and Peer Selection in Planar Metric Elections

Gabriel de Azevedo, Ulysse Hennebelle

arXiv:2608.27653v1cs.GTcs.CG

TL;DR

The paper asks how small stable committees can be in planar metric elections, especially when selected candidates must come from the voters. It unifies these settings with a Stackelberg-game and ε-net framework, proving three-member guarantees under ℓ1 and ℓ∞ and a four-member guarantee under ℓ2.

  • Problem

    The paper studies how to guarantee small Condorcet-winning sets in group and peer-selection settings where representativeness and stability matter.

  • Method

    It models metric elections, peer selection, strong peer selection, and the Voronoi game in a common two-player framework connected to weak and strong ε-nets.

  • Results

    Three voters suffice for strong peer selection under planar ℓ1 and ℓ∞, while four candidates suffice for planar metric elections under ℓ2.

  • Takeaways & Limitations

    The results provide a three-person committee guarantee for small planar peer-selection decisions and improve prior upper bounds.

  • Takeaways & Limitations

    Under ℓ2, strong peer selection has no nontrivial single-candidate guarantee, and the strong rectangular-net threshold may be tight.

Abstract

from arXiv · show

In ranked-choice voting, a Condorcet-winning set is a group of candidates for which no outside candidate is preferred to every member of the group by a majority of voters. We study Condorcet-winning sets in planar metric elections, where voters rank candidates according to their distance under a given norm. We formulate general metric elections, peer selection, and the one-round Voronoi game as instances of a two-player Stackelberg game and place these problems in a common hierarchy. We also introduce a new variant, which we call strong peer selection. Our main result concerns peer selection under the $\ell_1$ and $\ell_\infty$ norms. We prove that every planar instance admits a Condorcet-winning set of size at most three, even under strong peer selection. This follows from a new result for strong rectangular $\varepsilon$-nets. We show that, for every set of points in the plane, one can choose at most three input points that intersect every axis-parallel rectangle containing more than half of the points, improving the previous threshold of $9 / 16$ due to Ashok et al. Under the $\ell_2$ norm, we prove that every planar metric election admits a Condorcet-winning set of size at most four, improving on the general bound of five due to Song et al. Finally, we give new norm-independent bounds for the one-round Voronoi game.

1 Introduction

The paper studies stable group selection in planar spatial elections and connects several election models through a common Stackelberg-game and ε-net framework. It establishes improved bounds for peer selection, metric elections, and the Voronoi game under multiple norms.

  • Motivation: Group selection can improve representativeness and stability when no single Condorcet winner exists.A Condorcet-winning set prevents any outside candidate from being preferred to every elected member by a strict majority.
  • Motivation: Peer selection applies these stability questions when voters and eligible candidates are the same people, making small guaranteed coalitions especially relevant.The setting models recurring decisions such as neighborhood and departmental committees.
  • Spatial model: Planar spatial elections rank candidates by distance, while ℓ1, ℓ2, and ℓ∞ norms encode different ways of aggregating disagreement across two issue dimensions.The plane permits two independently varying policy dimensions, and the norm can change rankings for the same placements.
  • Framework: The paper unifies general metric elections, peer selection, strong peer selection, and the one-round Voronoi game as a two-player Stackelberg hierarchy linked to weak and strong ε-nets.Weak or strong nets apply depending on whether selected points may be placed freely or must come from candidates or voters.
  • Main results: 3 peers suffice for planar peer selection under ℓ1 and ℓ∞, including strong peer selection, via strong rectangular ε-nets improving the prior 9/16 threshold to 1/2.The result selects at most three input points intersecting every axis-parallel rectangle containing more than half the point set.
  • Main results: 4 candidates suffice for planar metric elections under ℓ2, improving the general bound of five, while four freely placed candidates suffice in the Voronoi game under any planar norm.The paper also gives exact single-candidate capture fractions and a two-candidate guarantee under an equidistance condition.

2 Preliminaries

The preliminaries define elections, Condorcet-winning sets, metric preferences, and weak versus strong ε-nets. They establish the geometric and preference notation used to relate voting guarantees to point-set intersection problems.

  • Elections: An election consists of finite voters and candidates, with each voter having a strict total preference relation over candidates.A voter prefers candidate c to set S when c is preferred to every member of S.
  • Elections: A Condorcet-winning set is a candidate set that no outside candidate defeats against every member by a strict majority.When the set has one candidate, it is a Condorcet winner.
  • Metric elections: In a metric election, voters and candidates are points, and voters prefer candidates at smaller distance; norm-induced metrics receive the corresponding norm label.The paper generally assumes distinct points and strict preferences.
  • ε-nets: A weak ε-net intersects every family member containing more than an ε fraction of the input points, whereas a strong ε-net additionally requires the net points to belong to the input set.Rectangular ε-nets specialize this definition to axis-parallel rectangles.

3 Strong Rectangular ε-nets

Strong rectangular ε-nets admit a three-point guarantee for axis-parallel rectangles containing more than half the input points. The proof uses a quartile-grid case analysis, while the exact threshold for four points remains unresolved.

  • Main result: Three input points intersect every axis-parallel rectangle containing more than half of the input points, improving the previous 9/16 threshold.This is the section’s main technical result for strong rectangular nets.
  • Proof overview: The proof partitions the plane into a 4 × 4 quartile grid whose rows and columns each have mass 1/4.The central 2 × 2 block is analyzed through six possible patterns of empty and nonempty cells.
  • Proof overview: For each central-cell case, the construction selects at most three input points that intersect every dangerous rectangle.A dangerous rectangle is one with mass greater than 1/2.
  • Geometric mechanism: A dangerous rectangle must contain the intersection of the quartile grid’s two middle lines, restricting where a rectangle avoiding a selected northwest point can lie.The relevant avoiding regions are south or east of that point; regions west and north have mass at most 1/2.
  • Open bounds: For k = 4, the known upper bound remains 1/2, while the authors conjecture the true factor is strictly smaller and that the three-point theorem may be tight.A matching lower bound is left as an open problem.
  • Connection to elections: The strong rectangular-net result is presented as the first application of rectangular nets beyond their study as geometric objects.The paper uses strong rectangular nets to bound Condorcet-winning sets in planar elections.

4 Metric Election Games

The paper places metric election problems in a two-player Stackelberg framework parameterized by defender and challenger restrictions. This hierarchy establishes equivalences and comparisons among Voronoi games, peer selection, strong peer selection, and general metric elections.

  • Common framework: Metric election problems are modeled as zero-sum Stackelberg games in which a defender chooses a coalition and a challenger responds to maximize captured voters.A challenger captures a voter when that voter prefers the challenger to every coalition member.
  • Player restrictions: Free, restricted, and peer-restricted players choose respectively from the whole space, the predefined candidate set, or the voter set.The first letter in a game label denotes the defender type, and the second denotes the challenger type.
  • Game hierarchy: Nine games arise from the three player types, with the framework recovering the one-round Voronoi game, general metric elections, and peer selection.The notation compares the largest voter fraction a challenger can capture against a coalition of size at most k.
  • Voronoi game: For every norm and positive integer k, FF(k) = FR(k) = FP(k), so restricting the challenger does not improve the worst-case value of the free-defender game.These three variants are collectively called the Voronoi game.
  • Strong peer selection: For every norm and positive integer k, PF(k) = PR(k), establishing an equivalence between free-challenger and predefined-candidate variants with peer-restricted defenders.These variants are collectively called strong peer selection.
  • Comparisons: General metric elections and strong peer selection are at least as hard as peer selection but are generally incomparable because the candidate and voter sets need not contain one another.The paper shows that some factors coincide under specific norms and coalition sizes.
  • Norm-specific equalities: The framework yields RRℓ2(1) = PPℓ2(1) = FFℓ2(1) and PFℓ1(1) = RRℓ1(1) = PPℓ1(1).These equalities identify settings where general elections, peer selection, and Voronoi-game factors coincide.

5 ε-nets and Metric Condorcet Problems

The section connects metric Condorcet problems to ε-net geometry and derives bounds for Voronoi games, metric elections, and peer selection. It establishes especially strong planar guarantees under ℓ2, ℓ1, and ℓ∞ norms.

  • Voronoi games: Weak ε-net bounds transfer to Voronoi games because captured voters lie in a convex set disjoint from the defending coalition.The reduction yields FF(k) = FR(k) = FP(k) ≤ ε_k on the plane for every norm.
  • Voronoi games: Four candidates suffice in the planar Voronoi game under any norm, ensuring that no challenger captures a majority of voters.This follows from the bound FF(4) ≤ 1/2.
  • Euclidean metric elections: Four candidates suffice for every planar ℓ2 metric election, improving the general bound of five candidates.Nearest-candidate rounding transfers weak convex-net bounds to candidate coalitions under ℓ2.
  • Strong rectangular nets and peer selection: Three voters suffice for strong peer selection on the plane under both ℓ1 and ℓ∞ norms.The result uses strong rectangular ε-nets and implies the corresponding peer-selection bound when candidates equal voters.
  • One-candidate case: The single-candidate capture factor is 2/3 under ℓ2 and 3/4 under both ℓ1 and ℓ∞ across the stated election and peer-selection problems.Under ℓ2, the equality covers Voronoi games, peer selection, and general metric elections; under ℓ1 and ℓ∞, it covers peer selection, strong peer selection, and general metric elections.
  • One-candidate case: Under ℓ2, strong peer selection with one candidate has no nontrivial guarantee.A convex-polygon construction lets a challenger capture all but one voter.

6 A Norm-Independent Two-Candidate Bound

The section proves a norm-independent two-candidate guarantee when an undecided voter is equidistant from every candidate. Every prescribed candidate can belong to such a Condorcet-winning pair, and the bound is tight for every ℓp norm.

  • Two-candidate bound: Two candidates suffice under every planar norm when an undecided voter is equidistant from all candidates.Moreover, every prescribed candidate can belong to a Condorcet-winning set of size at most two.
  • Proof structure: Candidates lie on a common unit-ball boundary, where each voter’s weakly preferred candidates form a consecutive arc.This circular ordering supports the construction of a pair blocking every challenger.
  • Proof structure: A plurality-majority candidate immediately forms a Condorcet-winning pair with the prescribed candidate.If no candidate has plurality at least half, candidates are traversed around the boundary until cumulative plurality exceeds half.
  • Tightness: The two-candidate guarantee is tight: for every ℓp norm, three equidistant candidates can induce a Condorcet cycle, so no single candidate wins.The example places the third candidate along the negative diagonal as p varies.

7 Conclusion

The paper uses planar geometry to sharpen guarantees for Condorcet-winning sets and related selection problems. It establishes three-candidate guarantees under ℓ1 and ℓ∞, a four-candidate guarantee under ℓ2, and identifies open questions about tightness and intermediate norms.

  • The paper places Condorcet-winning sets, peer selection, strong peer selection, and the Voronoi game in a common two-player framework.This framework separates restrictions on the defending coalition and the challenger.
  • Four candidates suffice for planar Condorcet-winning sets under the ℓ2 norm, improving the previous general guarantee of five.The proof rounds weak ε-nets to the candidate set.
  • Three voters suffice for strong peer selection under ℓ1 and ℓ∞, and therefore also for peer selection.The result follows from strong rectangular ε-nets and gives a natural guarantee for small collective decisions.
  • At most three input points intersect every axis-parallel rectangle containing more than half of a planar point set, improving the previous upper bound of 9/16.This strong rectangular-net result underpins the peer-selection guarantee.
  • Whether peer selection is easier than general Condorcet-winning sets remains open, including equality of RRℓp(1) and PPℓp(1) for 1 < p < ∞ and p ≠ 2.The paper also conjectures that its three-point rectangular-net bound is tight, although a matching lower-bound construction is unresolved.
  • Improving the weak-net bound to ε3 ≤ 1/2 would imply that three candidates suffice under the ℓ2 norm.Current weak-net bounds for three points are 5/11 ≤ ε3 ≤ 8/15.

AI Disclosure

The manuscript reports using ChatGPT for figures, writing revisions, proof verification, code generation, and computational testing.

  • ChatGPT assisted with figure generation, writing revision, proof verification, lower-bound searches, and mixed-integer programming tests.The tests examined point-configuration coverage and its symmetries in upper-bound proofs.

A Deferred details for Strong Rectangular ε-nets

The proof constructs strong rectangular 1/2-nets of size at most three by analyzing the six possible patterns of nonempty center cells in a quartile grid. Extreme and split points control the possible positions and masses of rectangles that avoid the selected points.

  • Quartile-grid setup: A quartile grid partitions the plane into four equal-mass rows and columns, forcing every dangerous rectangle to contain the grid’s central intersection.The proof then classifies configurations according to which of the four center cells are empty.
  • Selected-point construction: Extreme points and split points provide directional control over the mass remaining in rectangles east, west, north, or south of a selected point.A balanced split point simultaneously bounds mass in two directions.
  • Case analysis: Six center-cell patterns are handled: all, one, two adjacent, two opposite, three, or all four center cells nonempty or empty.Each case receives a strong rectangular 1/2-net of size at most three.
  • Safety verification: Every rectangle avoiding the selected points is shown to have mass at most 1/2, including the remaining exceptional positions in each center-cell case.The argument uses identities among cell masses and case-specific bounds for the potentially dangerous rectangles.

B Deferred details for Metric Election Games

The metric election problems are compared through a Stackelberg-game hierarchy using approximation by clustered voters and dense challenger locations. This establishes the relation between free and peer-restricted challenger settings.

  • Game hierarchy: Free-challenger, free-defender, and peer-restricted variants are related by restricting challenger and defender strategies, yielding FF(k) ≥ FR(k) ≥ FP(k).The remaining inequality is proved by approximating free-challenger instances with peer-restricted ones.
  • Approximation construction: A dense countable set of challenger locations is combined with large clusters around each original voter to approximate arbitrary free-challenger choices.Clusters contain q^2 nearby voters, while the first q dense challenger locations are added as individual voters.
  • Bounded coalition reduction: Optimal free-defender coalitions can be restricted to a bounded region by replacing distant coalition points with one reference voter without increasing clustered voters captured.Only the added dense-set voters can be affected by this replacement.
  • Limit argument: Compactness yields a convergent subsequence of bounded coalitions, while continuity transfers any challenger’s captured-voter guarantee to sufficiently fine approximating instances.The resulting inequality contradicts a hypothetical gap and establishes the required comparison.

C Deferred details for ε-nets and Metric Condorcet Problems

Norm geometry determines the shape of dominance regions and whether rounding or separation arguments apply. In the plane, supporting-line geometry proves a convex-separation lemma for arbitrary norms, while explicit examples mark its limits in other settings.

  • Dominance-region geometry: A supporting line of the norm unit ball parallel to b confines Dom(0, b) to the half-plane β < 1 in coordinates αu + βb.Convexity then implies b does not lie in conv(Dom(0, b)).
  • The ℓ1 specialization: For the ℓ1 norm, the supporting direction can be chosen along a coordinate axis, making the separating line axis-parallel.This supplies the geometric link from dominance regions to axis-parallel rectangles.
  • Higher-dimensional limitation: In three dimensions, the analogue of the convex-separation lemma fails for every ℓp norm with p ≠ 2.For sufficiently large t, three points lie in the dominance region while the opponent lies in its convex hull; the construction also covers p = ∞.
  • Rounding limitation: The planar nearest-candidate rounding argument fails for every ℓp norm with p ≠ 2.A midpoint weak 1/2-net can round to a candidate while the other candidate captures both voters.
Loading 2608.27653v1…