2013 Jan 11 at 13:00
2310
Lachlan Dufton, PhD candidate, David R. Cheriton School of Comp. Sci., Univ. Waterloo
In this thesis, we examine stochastic techniques for overcoming game theoretic and computational issues in the collective decision making process of self-interested individuals. In particular, we examine truthful, stochastic mechanisms, for settings with a strong budget balance constraint (there is no net flow of money into or away from the agents). We characterize social choice functions that are implementable in truthful mechanisms for the setting of heterogeneous item allocation with unit demand agents, both with and without the strong budget balance constraint. These characterizations reveal impossibility results and poor worst-case performance that motivates us to examine stochastic solutions. To adequately compare stochastic mechanisms, we introduce and discuss measures that capture the behaviour of stochastic mechanisms, based on techniques used in stochastic algorithm design. We observe that mechanisms can (and typically must) achieve truthfulness and strong budget balance using one of two techniques: labelling a subset of agents as ``auctioneers'' who cannot affect the outcome, but collect any surplus; and partitioning agents into disjoint groups, such that each partition solves a subproblem of the overall decision making process. In addition to item allocation, we apply these techniques to the room assignment-rent division, and public good problems. Communication and computational complexity are two other important concerns of computational social choice. Both the random-auctioneer and random-partition approaches offer a flexible trade-off between low complexity of the mechanism, and high overall outcome quality measured, for example, by total agent utility. They enable truthful and feasible solutions to be incrementally improved on as the mechanism receives more information or is allowed more processing time. Our main results are based on optimizing worst-case performance, and we complement these results through empirical, average-case analyses on our mechanisms.