TSpace

Abstract (summary): Mechanism design deals with the design of protocols to elicit individual preferences while achieving some social objective (e.g., maximizing social welfare). An important property of mechanisms is strategy-proofness, which requires that no agent can gain (or induce a more preferred outcome) by misreporting her preferences to the mechanism. Previous results have shown that when monetary transfer (e.g., in the form of payments) is allowed between agents and the mechanism, the famous VCG mechanism is both strategy-proof and efficient (for social welfare maximization). Despite these positive results, there are still many settings where monetary transfer is difficult to implement, or even prohibited. For instance, political policies are generally determined without payment; monetary compensation between parties that are involved in organ donation is illegal in most countries, etc. It is natural to ask that whether it is possible to design strategy-proof mechanisms when monetary transfer is not allowed. This line of research, referred to as ``mechanism design without payment", has received much attention from people in economics, political science, and more recently, computer science. In this thesis, we study a classical embodiment of mechanism design without money called the facility location problem: suppose the municipal government plans to build several homogeneous facilities according to the reported preferred locations of the residents. Each resident would prefer one of the facilities built near his home/office (or ideal location), and the facilities should be built to minimize the social cost (i.e., sum of costs over all agents) or other social objectives. We study the facility location from three perspectives: mechanism design, single-peaked preferences and preference elicitation. We first propose a family of strategy-proof mechanisms for multi-dimensional, multi-facility location problem, called quantile mechanisms, by extending the classical generalized median mechanisms. We also show that the quantile mechanism are approximately group strategy-proof for constrained/unconstrained facility location problems, and study the computational complexity of finding an optimal group manipulation. Next, we study the common assumption of single-peakedness used in classical mechanism design for facility location problems, and show that agent preferences are far from being single-peaked in one-dimension, but approximately single-peaked in two-dimensions. Finally, we study preference elicitation in facility location problems (along with the second price auction), and propose a framework for analyzing the tradeoff between efficiency and privacy.