Mechanisms for aggregating the preferences of agents in elections need to balance many different considerations, including efficiency, information elicited from agents, and ma-nipulability. We consider the utilitarian social welfare of mechanisms for preference aggregation, measured by the distortion. We show that for a particular input format called threshold approval voting, where each agent is presented with an independently chosen threshold, there is a mechanism with nearly optimal distortion when the number of voters is large. Threshold mechanisms are potentially manipulable, but place a low informational burden on voters. We then consider truthful mechanisms. For the widely-studied class of ordinal mechanisms which elicit the rankings of candidates from each agent, we show that truthfulness essentially imposes no additional loss of welfare. We give truthful mechanisms with distortion O(√(m log m)) for k-winner elections, and distortion O(√m log m) when candidates have arbitrary costs, in elections with m candidates. These nearly match known lower bounds for ordinal mechanisms that ignore the strategic behavior. We further tighten these lower bounds and show that for truthful mechanisms our first upper bound is tight. Lastly, when agents decide between two candidates, we give tight bounds on the distortion for truthful mechanisms.
展开▼
机译：聚集选举中代理偏好的机制需要平衡许多不同的考虑因素，包括效率，从代理商引发的信息以及MA-upulably。我们认为偏好聚集机制的功利主义社会福利，通过扭曲来衡量。 We show that for a particular input format called threshold approval voting, where each agent is presented with an independently chosen threshold, there is a mechanism with nearly optimal distortion when the number of voters is large.阈值机制可能是可操纵的，但在选民上占据了低的信息负担。然后我们考虑真实的机制。对于广泛研究的阶级机制，这些阶级机制引发了每个经理的候选人排名，我们表明真实性基本上造成了额外的福利损失。我们为K-Winner选举的失真O（√（m log m））提供真实的机制，当候选人有任意成本时，候选人的失真O（√mlog m）。这些几乎匹配了忽略战略行为的序数机制的已知下限。我们进一步收紧了这些下限，表明，对于真实的机制，我们的第一个上限是紧张的。最后，当代理人决定在两个候选人之间，我们在扭曲的情况下为真实的机制提供紧张的界限。
展开▼
