The Price of Deception

这一奖项的目标是发展决策机制，使系统利益最大化，并将拥有私人信息的代理人操纵的负面影响降至最低。总体利益的潜在减少是由个人效用函数的差异所推动的，并由个人对信息的控制所致。潜在的减少，即“欺骗的代价”，将被计算为博弈的混合或纯策略纳什均衡的预期系统效用与无所不知的公正决策者可实现的系统效用的最坏情况之比。初步研究表明，类似的机制可能会有非常不同的欺骗代价。将分析现有的程序，并开发新的变化，用于投票、排名、匹配或将一个组的成员分配给另一个组的成员，以及设施位置。如果成功，这项研究的结果将确定基础设施规划、匹配、投票和收集个人意见的机制，这些机制具有较低的欺骗代价，因此操纵私人信息将不会显著降低结果的整体质量。这项工作的主要目标是通过适当选择决策机制，更好地优化全系统或公共目标。更好的机制将有助于改善器官捐赠者与接受者的匹配，分配医学生到医院实习，在网络上产生评级，以及公共设施的安置等应用。这项工作也将对游戏和竞争的基本算法理论做出贡献。

The objective of this award is the development of decision-making mechanisms that maximize system benefit and minimize the negative impact of manipulation by agents that possess private information. Potential decreases in overall benefit are motivated by differences in individual utility functions and are enabled by individual control of information. The potential decrease, the "price of deception," will be calculated as the worst case ratio of the expected system utility of a mixed or pure strategy Nash equilibrium of the game in which players submit statements of private information, to the system utility achievable by an omniscient impartial decision-maker. Preliminary research has demonstrated that similar mechanisms can have greatly different prices of deception. Existing procedures will be analyzed and new variations will be developed for voting, ranking, matching or assigning members of one group to members of another group, and facility location.If successful, the results of this research will identify mechanisms for infrastructure planning, matching, voting, and aggregation of individual opinions that have a lesser price of deception, so that manipulation of private information will less significantly reduce the overall quality of the outcome. The primary goal of this work is to better optimize system-wide or public goals through appropriate choices of decision mechanisms. Better mechanisms will help improve the matching of organ donors to recipients, the assignment of medical students to hospital internships, generation of ratings over the web, and placement of public facilities, among other applications. This work will also contribute to the basic algorithmic theory of games and competition.