*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Title: The Price of Deception in Social Choice
Time: Friday, August 4th, 2017, 2pm
Location: Groseclose 402
Advisor: Dr. Craig Tovey, School of Industrial and Systems Engineering
Committee:
Dr. Paul Griffin, School of Industrial Engineering, Purdue University
Dr. Santosh Vempala, School of Computer Science, Georgia Institute
of Technology
Dr. Vijay Vazirani, School of Computer Science, Georgia Institute
of Technology
Dr. Prasad Tetali, School of Mathematics, Georgia Institute of Technology
Reader: Dr. Jörg Rothe, Institute for Computer Science, University of
Düsseldorf
The thesis is available for public inspection in the School of Mathematics
lounge (Skiles 236), the ARC lounge (Klaus 2222), the ISyE PhD student
lounge and at the URL
http://aco.gatech.edu/events/final-doctoral-examination-and-
defense-dissertation-james-bailey
Summary:
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 decision we are forced to either use a manipulable algorithm or an
algorithm with negative properties; for instance, a dictatorship is the
only reasonably strategy-proof way to decide an election. Thus, we view it
as unwise to take an all-or-nothing approach to manipulation since we 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. Our
model of human behavior is supported by an extensive amount of experimental
evidence and psychology and economics and allows us to better understand
the likely outcomes of strategic behavior. We introduce a measure of
manipulation – the Price of Deception – that quantifies the impact of
manipulation. With the Price of Deception we are able to identify
algorithms are negligibly impacted by manipulation, algorithms where
strategic behavior leads to arbitrarily poor outcomes, and anything
in-between. We prove the power of our model and the Price of Deception by
answering open problems in assignments, facility location, election and
stable marriage 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 manipulability than between
“yes” and “no”.
