We consider the fundamental mechanism design problem of approximate social
welfare maximization under general cardinal preferences on a finite number of
alternatives and without money. The well-known range voting scheme can be
thought of as a non-truthful mechanism for exact social welfare maximization in
this setting. With m being the number of alternatives, we exhibit a randomized
truthful-in-expectation ordinal mechanism implementing an outcome whose
expected social welfare is at least an Omega(m^{-3/4}) fraction of the social
welfare of the socially optimal alternative. On the other hand, we show that
for sufficiently many agents and any truthful-in-expectation ordinal mechanism,
there is a valuation profile where the mechanism achieves at most an
O(m^{-{2/3}) fraction of the optimal social welfare in expectation. We get
tighter bounds for the natural special case of m = 3, and in that case
furthermore obtain separation results concerning the approximation ratios
achievable by natural restricted classes of truthful-in-expectation mechanisms.
In particular, we show that for m = 3 and a sufficiently large number of
agents, the best mechanism that is ordinal as well as mixed-unilateral has an
approximation ratio between 0.610 and 0.611, the best ordinal mechanism has an
approximation ratio between 0.616 and 0.641, while the best mixed-unilateral
mechanism has an approximation ratio bigger than 0.660. In particular, the best
mixed-unilateral non-ordinal (i.e., cardinal) mechanism strictly outperforms
all ordinal ones, even the non-mixed-unilateral ordinal ones.

研究机制设计的基本问题，即在无货币的情况下，考虑有限数量的备选方案和一般记数偏好下的近似社会福利最大化问题，并提出一种随机的期望真实序数机制来实现其预期社会福利至少是社会最优方案社会福利的 1/m^(3/4)。此外，对于足够多的代理和任何期望真实序数机制，存在一种评估配置文件，其中机制在预期上达到最优社会福利的 O (m^(-2/3)) 分数，对于 m=3 的自然特殊情况，可以获得更紧的界限，并获得有关实用期望真实机制可达到近似比率的自然受限类别的分离结果。

区间投票的真实近似

Truthful approximations to range voting

We study the behavior of Range Voting and Normalized Range Voting with
respect to electoral control. Electoral control encompasses attempts from an
election chair to alter the structure of an election in order to change the
outcome. We show that a voting system resists a case of control by proving that
performing that case of control is computationally infeasible. Range Voting is
a natural extension of approval voting, and Normalized Range Voting is a simple
variant which alters each vote to maximize the potential impact of each voter.
We show that Normalized Range Voting has among the largest number of control
resistances among natural voting systems.

研究显示，Normalized Range Voting 是自然投票系统中抵御选举控制的数量最多的，该系统可以通过改变每个选民的选票来最大化每个选民的潜在影响。