Abstract
In spatial voting models, the "yolk" serves as a critical measure of stability and a generalized equilibrium point. Traditionally, computing the yolk required the exhaustive precomputation of all limiting median lines, leading to a computational bottleneck of $O(n^{4/3})$. This paper introduces a novel approach using Megiddo’s parametric search to compute the yolk in near-linear time ($O(n \log^7 n)$) without explicitly listing these lines. The algorithm provides exact solutions for $L_1$ and $L_\infty$ metrics and a $(1+\epsilon)$-approximation for the Euclidean ($L_2$) metric.
Introduction: The Stability of Policy Space
Spatial voting theory represents voters as points in a multi-dimensional policy space. In a two-dimensional plane, a single Condorcet winner—a point preferred by a majority over any other—rarely exists. To address this lack of a unique equilibrium, researchers use the yolk: the smallest disk that intersects every possible median line. A median line is any line that bisects the voter distribution such that no more than half the voters lie on either side.
The yolk's center acts as a generalized equilibrium, and its radius provides bounds for other social choice concepts, such as the "uncovered set." Historically, the $O(n^{4/3})$ complexity of finding all "limiting" median lines (those passing through at least two voters) hindered efficient computation.
Methodology: Optimization via Parametric Search
The authors transform the geometric construction of the yolk into an optimization problem solved through Megiddo’s parametric search. The core of their approach is a "decision algorithm" that determines if a disk of a given radius $r$ centered at $(x, y)$ intersects all median lines.
Rotating Sweep-Line and Polygon Generalization
To avoid precomputing lines, the decision algorithm employs a rotating sweep-line. By rotating a tangent line around a candidate shape and monitoring the voter count on one side, the algorithm can detect if any median line fails to intersect the shape.
The paper generalizes the yolk from a circle to a regular $k$-sided polygon ($P_k$). This allows for a unified treatment of different distance metrics:
- $L_1$ Metric: The yolk is a square rotated by 45°.
- $L_\infty$ Metric: The yolk is an axis-parallel square.
- $L_2$ Metric: The circular yolk is approximated by a polygon with $k \approx 1/\epsilon$ sides.
Key Results and Insights
The primary contribution is breaking the $O(n^{4/3})$ barrier. By shifting focus from explicit line computation to monitoring voter counts during rotation, the authors achieve:
- Exact $L_1$ and $L_\infty$ computation in $O(n \log^7 n)$ time.
- $(1+\epsilon)$-approximation for $L_2$ in $O(n \log^7 n \cdot \log^4 \frac{1}{\epsilon})$ time.
This represents the first algorithm to bypass the combinatorial complexity of limiting lines, demonstrating the practical power of parametric search in social choice theory.
Limitations and Future Work
While the algorithm is near-linear, the $O(\log^7 n)$ factor is theoretically high; future research might apply techniques like Cole’s optimization to reduce this. Additionally, while the $L_1$ and $L_\infty$ solutions are exact, the Euclidean $L_2$ metric currently relies on approximation. Extending this "no-precomputation" framework to higher-dimensional policy spaces remains a significant mathematical challenge.
Summary updated