Computing the Yolk in Spatial Voting Games Without Computing Median Lines
Abstract
The yolk is an important concept in spatial voting games: the yolk center generalises the equilibrium and the yolk radius bounds the uncovered set. We present near-linear time algorithms for computing the yolk in the plane. To the best of our knowledge our algorithm is the first that does not precompute median lines, and hence is able to break the best known upper bound of O(n4/3) on the number of limiting median lines. We avoid this requirement by carefully applying Megiddo’s parametric search technique, which is a powerful framework that could lead to faster algorithms for other spatial voting problems.
Cite
Text
Gudmundsson and Wong. "Computing the Yolk in Spatial Voting Games Without Computing Median Lines." AAAI Conference on Artificial Intelligence, 2019. doi:10.1609/AAAI.V33I01.33012012Markdown
[Gudmundsson and Wong. "Computing the Yolk in Spatial Voting Games Without Computing Median Lines." AAAI Conference on Artificial Intelligence, 2019.](https://mlanthology.org/aaai/2019/gudmundsson2019aaai-computing/) doi:10.1609/AAAI.V33I01.33012012BibTeX
@inproceedings{gudmundsson2019aaai-computing,
title = {{Computing the Yolk in Spatial Voting Games Without Computing Median Lines}},
author = {Gudmundsson, Joachim and Wong, Sampson},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2019},
pages = {2012-2019},
doi = {10.1609/AAAI.V33I01.33012012},
url = {https://mlanthology.org/aaai/2019/gudmundsson2019aaai-computing/}
}