In social choice theory, researchers seek "well-behaved" preference structures to ensure stable collective decisions and prevent strategic manipulation. While single-peaked and single-crossing preferences are well-understood and characterized by small sets of "forbidden patterns," one-dimensional (1D) Euclidean preferences have remained more elusive. This paper by Chen, Pruhs, and Woeginger demonstrates that the 1D Euclidean domain is fundamentally more complex, proving it cannot be characterized by any finite set of obstructions.
The Euclidean Domain and Forbidden Patterns
A preference profile is 1D Euclidean if both voters and alternatives can be mapped to points on a real line such that each voter prefers alternatives closer to their own position. This geometric constraint is more restrictive than being single-peaked or single-crossing.
In many mathematical fields, structures are identified by what they exclude. For instance, a graph is planar if it lacks specific forbidden subgraphs (Kuratowski’s Theorem). Similarly, single-peaked and single-crossing profiles are defined by a small, finite list of forbidden sub-profiles. The central question of this research was whether a similar finite list exists for the 1D Euclidean domain.
The Construction of Minimal Obstructions
To prove that no finite list of obstructions suffices, the authors used a constructive proof by contradiction. They developed an infinite sequence of preference profiles, denoted as $P^*_k$, designed to be "minimally non-Euclidean":
- Non-Euclidean: The full profile $P^*_k$ cannot be embedded in a 1D Euclidean space.
- Minimally so: Removing any single voter results in a sub-profile that is 1D Euclidean.
The figure above illustrates the profile $P^*_4$, which consists of $2k$ voters and $4k$ alternatives (for $k=4$). By showing that such minimal obstructions exist for every integer $k \ge 2$, the authors demonstrate that the "reasons" a profile might fail to be Euclidean are infinite and grow in complexity. Any finite list of forbidden patterns would eventually fail to capture a larger, more intricate obstruction in this sequence.
Key Results and Implications
The main result, Theorem 3.2, formally establishes that 1D Euclidean preference profiles cannot be characterized by finitely many obstructions. This highlights a significant divide between purely combinatorial properties (like single-crossing) and geometric properties (like Euclidean distance). The distance requirement introduces global dependencies across the entire profile that cannot be reduced to local, small-scale patterns.
This finding has important algorithmic consequences. While single-peaked profiles can be recognized quickly by checking for a few small patterns, recognizing 1D Euclidean profiles requires more sophisticated tools, such as linear programming, to account for these complex geometric constraints.
Future Directions
The authors focus strictly on the one-dimensional case and voter deletion. They conjecture that higher-dimensional Euclidean spaces ($d \ge 2$) will also lack finite characterizations, though the proof techniques would need significant generalization. Additionally, the question of whether a finite characterization exists for the deletion of alternatives rather than voters remains an open problem in the field.
Summary updated