"Coordinate-wise Median: Not Bad, Not Bad, Pretty Good" (with Wade Hann-Caruthers) [arXiv]

We consider the facility location problem in two dimensions. In particular, we consider a setting where agents have Euclidean preferences, defined by their ideal points, for a facility to be located in a plane. For the utilitarian objective and an odd number of agents, we show that the coordinate-wise median mechanism (CM) has a worst-case approximation ratio (WAR) of $\sqrt{2}\frac{\sqrt{n^2+1}}{n+1}$. Further, we show that CM has the lowest WAR for this objective in the class of strategyproof, anonymous, continuous mechanism . For the p-norm social welfare objective, we find that the WAR for CM is bounded above by $2^{\frac{3}{2}-\frac{2}{p}}$ for p>=2. Since it follows from previous results in one-dimension that any deterministic strategyproof mechanism must have WAR at least $2^{1-\frac{1}{p}}$, our upper bound guarantees that the CM mechanism is very close to being the best deterministic strategyproof mechanism for p>=2.

"Project selection with partially verifiable information" (with Wade Hann-Caruthers) [arXiv]

We consider a problem where the principal chooses a project from a set of available projects for the agent to work on. Each project provides some profit to the principal and some payoff to the agent and these profits and payoffs are the agent's private information. The principal has a belief over these values and his problem is to find an incentive compatible mechanism without using transfers that maximizes expected profit. Importantly, we assume partial verifiability so that the agent cannot report a project to be more profitable to the principal than it actually is. In this setup, we find a neat characterization of the set of incentive compatible mechanisms. Using this characterization, we find the optimal mechanism for the principal when there are two projects. Within a subclass of incentive compatible mechanisms, we show that a single cutoff mechanism is optimal and conjecture that it is the optimal incentive compatible mechanism.

"Probably Approximately Strategyproof mechanisms"

We propose a notion of approximate incentive compatibility called probably approximately strategyproof (PAS) that relaxes the standard notion of strategyproofness (SP) by requiring that truth-telling be approximately optimal for most preference profiles. While SP precludes existence of mechanisms with other desirable properties in public good environments such as voting and facility location, we argue that the efficient mechanism in these environments is approximately SP by showing that it is PAS. In other environments, we show that revenue maximizing digital auction, uniform price auction, and double auction are PAS mechanisms. All these mechanisms exhibit a property of diminishing influence, a property often associated with good incentives in a large market. While diminishing influence is a sufficient condition for a mechanism to be PAS, we show that it is necessary as well in a simple binary voting environment. We also relate our notion to $\epsilon-SP$ and $SP−L$ which are two other notions of approximate SP in the literature and show that PAS mechanisms lie between them.