Econ Papers Daily / 期刊论文
空间投票模型中蛋黄由线性规划蛋黄逼近的可近似性
On the approximability of the yolk by the LP yolk in the spatial model of voting
摘要
In the spatial model of voting, the yolk and LP (linear programming) yolk are important solution concepts for predicting outcomes for a committee of voters. McKelvey and Tovey showed that the LP yolk provides a lower bound approximation for the size of the yolk and there has been considerable debate on whether the LP yolk is a good approximation of the yolk. The problem was partially resolved for arbitrarily large committees (as the number of voters goes to infinity) but remains open when there are few voters, which is standard for most committees. In this paper, we show that for an odd number of voters in a two-dimensional space, the yolk radius is at most twice the size of the LP yolk radius and we show that this bound is tight—there exists a family of instances where the LP yolk radius will differ from the yolk radius by a factor arbitrarily close to 2. We also show that (1) even in this setting, the LP yolk center can be arbitrarily far away from the yolk center (relative to the radius of the yolk) and (2) for all other settings (an even number of voters or in dimension k \ge 3), the LP yolk can be arbitrarily small relative to the yolk. Thus, in general, the LP yolk can be an arbitrarily poor approximation of the yolk.
中文摘要
在空间投票模型中，蛋黄（yolk）与线性规划蛋黄（LP yolk）是预测委员会投票结果的重要解概念。McKelvey与Tovey证明线性规划蛋黄为蛋黄规模提供了下界近似，但关于线性规划蛋黄能否有效近似蛋黄的问题一直存在激烈争论。该问题在委员会规模趋于无穷大时已得到部分解决，但在标准委员会常见的少量投票者情形下仍悬而未决。本文证明：在二维空间中奇数投票者情形下，蛋黄半径至多为线性规划蛋黄半径的两倍，且该上界是紧的——存在实例族使得线性规划蛋黄半径与蛋黄半径的比值可任意趋近于2。我们同时证明：（1）即便在此设定下，线性规划蛋黄中心与蛋黄中心的距离（相对于蛋黄半径）可任意大；（2）在其他所有设定中（偶数投票者或维度k≥3），线性规划蛋黄相对于蛋黄可任意小。因此，一般而言，线性规划蛋黄对蛋黄的近似效果可能极差。