The Price of deception in social choice

Game theory;Price of deception;Minimal dishonesty;Social choice;Voting;Borda;Plurality;Copeland;Majority judgment;Veto;Facility location;Assignments;Stable marriage;Gale-Shapley;College admission;Student placement

Bailey, James P. ; Tovey, Craig A. Industrial and Systems Engineering Vempala, Santosh Tetali, Prasad Vazirani, Vijay Griffin, Paul ; Tovey, Craig A.

University:Georgia Institute of Technology

Department:Industrial and Systems Engineering

关键词: Game theory;    Price of deception;    Minimal dishonesty;    Social choice;    Voting;    Borda;    Plurality;    Copeland;    Majority judgment;    Veto;    Facility location;    Assignments;    Stable marriage;    Gale-Shapley;    College admission;    Student placement;   

Others  :  https://smartech.gatech.edu/bitstream/1853/59189/1/BAILEY-DISSERTATION-2017.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

Most social choice algorithms rely on private data from individuals to maximize a social utility. However, many algorithms are manipulable -- an individual can manipulate her reported data to obtain an outcome she prefers often at the cost of social good. Literature addresses this by declaring an algorithm as ``manipulable'' or ``strategy-proof''. However, for many decisions we are forced to either use a manipulable algorithm or an algorithm with negative properties; for instance, a dictatorship is the only strategy-proof way to decide an election. Thus, we view it as unwise to take an all-or-nothing approach to manipulation since we so often have to settle for nothing. In this dissertation, we focus on algorithmic design with strategic behavior in mind.Specifically, we develop the framework to examine the effect of manipulation on social choice using a game theoretic model. We show that the standard Nash equlibria solution concept is insufficient to capture human behavior as it relates to deception.The combinatorial nature of many problems results in Nash equilibria where individuals are lying to their own detriment. To remove these absurd equilibria and better capture human behavior, we introduce the Minimal Dishonesty refinement.In our model each individual tells the smallest possible lie to obtain the best possible result and therefore if the individual tries to be more honest then they will get a worse outcome.Our model for human behavior is supported by a vast amount of experimental evidence in psychology and economics and allows us to better understand the likely outcomes of strategic behavior. We also introduce a measure of manipulation -- the Price of Deception -- that \emph{quantifies} the impact of strategic behavior. Specifically, the Price of Deception is the worst-case ratio between the social utility when each individual is sincere, and the social utility at a Nash equilibrium. With Minimal Dishonesty and the Price of Deception we are able to identify algorithms that are negligibly impacted by manipulation, algorithms where strategic behavior leads to arbitrarily poor outcomes, and anything in-between.We demonstrate the power of Minimal Dishonesty and the Price of Deception by answering open problems in assignments, facility location, elections, and stable marriages including a 28-year open problem by Gusfield and Irving.Our results demonstrate that the Price of Deception, like computational complexity,provides finer distinctions of manipulabilitythan between ``yes" and ``no".