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.