<p>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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(k \ge 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>), 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.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the approximability of the yolk by the LP yolk in the spatial model of voting

  • Ran Hu,
  • James P. Bailey

摘要

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\) k 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.