Person:

Lai, John Kwang

Cake cutting is a common metaphor for the division of a heterogeneous divisible good. There are numerous papers that study the problem of fairly dividing a cake; a small number of them also take into account self-interested agents and consequent strategic issues, but these papers focus on fairness and consider a strikingly weak notion of truthfulness. In this paper we investigate the problem of cutting a cake in a way that is truthful and fair, where for the first time our notion of dominant strategy truthfulness is the ubiquitous one in social choice and computer science. We design both deterministic and randomized cake cutting algorithms that are truthful and fair under different assumptions with respect to the valuation functions of the agents.

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.

Faced with an intractable optimization problem, a common approach to computational mechanism design seeks a polynomial time approximation algorithm with an approximation guarantee. Rather than adopt this worst-case viewpoint, we introduce a new paradigm that seeks to obtain good performance on typical instances through a modification to the branch-and-bound search paradigm. Incentive compatibility in single-dimensional domains requires that an outcome improves monotonically for an agent as the agent's reported value increases. We obtain a monotone search algorithm by coupling an explicit sensitivity analysis on the decisions made during search with a correction to the outcome to ensure monotonicity. Extensive computational experiments on single-minded combinatorial auctions show better welfare performance than that available from existing approximation algorithms.

In mechanism design it is typical to impose incentive compatibility and then derive an optimal mechanism subject to this constraint. By replacing the incentive compatibility requirement with the goal of minimizing expected ex post regret, we are able to adapt statistical machine learning techniques to the design of payment rules. This computational approach to mechanism design is applicable to domains with multi-dimensional types and situations where computational efficiency is a concern. Specifically, given an outcome rule and access to a type distribution, we train a support vector machine with a special discriminant function structure such that it implicitly establishes a payment rule with desirable incentive properties. We discuss applications to a multi-minded combinatorial auction with a greedy winner-determination algorithm and to an assignment problem with egalitarian outcome rule. Experimental results demonstrate both that the construction produces payment rules with low ex post regret, and that penalizing classification errors is effective in preventing failures of ex post individual rationality.

We consider the problem of fairly dividing a heterogeneous divisible good among agents with different preferences. Previous work has shown that envy-free allocations, i.e., where each agent prefers its own allocation to any other, may not be efficient, in the sense of maximizing the total value of the agents. Our goal is to pinpoint the most efficient allocations among all envy-free allocations. We provide tractable algorithms for doing so under different assumptions regarding the preferences of the agents.