How should we divide a good or set of goods among a set of agents? There are various constraints that we can consider. We consider two particular constraints. The first is fairness - how can we find fair allocations? The second is truthfulness - what if we do not know agents valuations for the goods being allocated? What if these valuations need to be elicited, and agents will misreport their valuations if it is beneficial? Can we design procedures that elicit agents' true valuations while preserving the quality of the allocation? We consider truthful and fair resource allocation procedures through a computational lens. We first study fair division of a heterogeneous, divisible good, colloquially known as the cake cutting problem. We depart from the existing literature and assume that agents have restricted valuations that can be succinctly communicated. We consider the problems of welfare-maximization, expressiveness, and truthfulness in cake cutting under this model. In the second part of this dissertation we consider truthfulness in settings where payments can be used to incentivize agents to truthfully reveal their private information. A mechanism asks agents to report their private preference information and computes an allocation and payments based on these reports. The mechanism design problem is to find incentive compatible mechanisms which incentivize agents to truthfully reveal their private information and simultaneously compute allocations with desirable properties. The traditional approach to mechanism design specifies mechanisms by hand and proves that certain desirable properties are satisfied. This limits the design space to mechanisms that can be written down and analyzed. We take a computational approach, giving computational procedures that produce mechanisms with desirable properties. Our first contribution designs a procedure that modifies heuristic branch and bound search and makes it usable as the allocation algorithm in an incentive compatible mechanism. Our second contribution draws a novel connection between incentive compatible mechanisms and machine learning. We use this connection to learn payment rules to pair with provided allocation rules. Our payment rules are not exactly incentive compatibility, but they minimize a measure of how much agents can gain by misreporting. / Engineering and Applied Sciences
| Identifer | oai:union.ndltd.org:harvard.edu/oai:dash.harvard.edu:1/11108713 |
| Date | 25 September 2013 |
| Creators | Lai, John Kwang |
| Contributors | Parkes, David C. |
| Publisher | Harvard University |
| Source Sets | Harvard University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis or Dissertation |
| Rights | open |
Page generated in 0.0022 seconds