Representative Proxy Voting

Elliot Anshelevich, Zack Fitzsimmons, Rohit Vaish, Lirong XiaAAAI 2021 · DOI

Introduction

In collective decision-making, voters often delegate their authority to proxies when they are unable or unwilling to participate directly. Traditional research in proxy voting typically assumes a fixed electorate, selecting proxies from a known set of individuals. However, real-world environments are dynamic; voters may join, leave, or shift their preferences over time. This paper introduces the concept of representative proxy voting, where a set of proxies is strategically positioned to capture the preferences of any potential voter within a spatial metric, regardless of their specific location.

The Spatial Model of Representation

The authors model the problem in a one-dimensional metric space, such as the real line $[0, 1]$, representing a political spectrum. Candidates and voters are points in this space. The objective is to pre-position a set of proxies such that for any voter appearing on the line, if they delegate their vote to the nearest proxy, that proxy’s preferred candidate is "close" to the voter’s own favorite.

Specifically, a set of proxies is defined as $\theta$-representative if, for every possible voter $v$, the distance between $v$'s favorite candidate and the favorite candidate of $v$'s assigned proxy is at most $ heta$.

Geometric Analysis and the Bisector Connection

A fundamental challenge in ensuring representation is managing the "bisectors"—the midpoints between candidates where voter preferences shift from one candidate to another.

Geometric condition for $\theta$-representativeness involving candidate bisectors.

The paper proves a critical "Bisector Connection": if two adjacent candidates are separated by a distance greater than $\theta$, a proxy bisector must coincide with the candidate bisector. If this alignment fails, there will inevitably be a region where a voter and their closest proxy disagree significantly on the top choice, violating the $\theta$-representativeness condition.

Algorithmic Approaches

The research explores two primary scenarios for proxy placement:

  1. Restricted Positioning: Proxies must be located at the positions of existing candidates.
  2. Unrestricted Positioning: Proxies can be placed at any point on the real line.

To find the minimum number of proxies required, the authors developed polynomial-time algorithms using dynamic programming. For the unrestricted case, they introduced an "Expand and Merge" algorithm. This approach first identifies necessary bisector locations and then strategically "pulls" proxies away from these bisectors until they can be merged, minimizing the total count.

An instance of the proxy voting problem showing candidate placement (top) and corresponding proxy assignments (bottom).

Key Results and Theoretical Bounds

The study establishes tight theoretical bounds on the number of proxies needed as a function of the representation threshold $\theta$. These results show that a relatively small number of proxies—proportional to $1/\theta$—is sufficient to represent an infinite number of potential voters.

Restriction Upper Bound Lower Bound Complexity
Restricted $2 \lceil 1/\theta \rceil$ $2 (\lceil 1/\theta \rceil - 1)$ Optimal (Poly Time)
Unrestricted $\frac{3}{2} \lceil 1/\theta \rceil$ $\lceil 1/\theta \rceil$ Optimal (Poly Time)

Furthermore, the authors show that $\theta$-representation preserves overall election outcomes for strict-Condorcet voting rules; the winner chosen via proxies will be within $\theta$ of the winner under direct voting.

Conclusion and Future Directions

This work provides a robust framework for voter-agnostic representation. By focusing on the geometry of candidate positions rather than current voter distributions, the resulting proxy systems are "future-proof" against demographic shifts.

Future research could extend these findings to higher-dimensional metric spaces, which would better represent multi-issue political landscapes. Additionally, exploring "top-$k$" representation—ensuring a proxy's broader ranking aligns with the voter's—and accounting for strategic voter behavior remain open challenges in the field of computational social choice.

Summary updated

BibTeX
@inproceedings{anshelevich2021representative,
  author = {Elliot Anshelevich and Zack Fitzsimmons and Rohit Vaish and Lirong Xia},
  title = {{Representative Proxy Voting}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16643},
}
Figure