Person:

Parkes, David

Since economic mechanisms are often applied to very different instances of the same problem, it is desirable to identify mechanisms that work well in a wide range of circumstances. We pursue this goal for a position auction setting and specifically seek mechanisms that guarantee good outcomes under both complete and incomplete information. A variant of the generalized first-price mechanism with multi-dimensional bids turns out to be the only standard mechanism able to achieve this goal, even when types are one-dimensional. The fact that expressiveness beyond the type space is both necessary and sufficient for this kind of robustness provides an interesting counterpoint to previous work on position auctions that has highlighted the benefits of simplicity. From a technical perspective our results are interesting because they establish equilibrium existence for a multi-dimensional bid space, where standard techniques break down. The structure of the equilibrium bids moreover provides an intuitive explanation for why first-price payments may be able to support equilibria in a wider range of circumstances than second-price payments.

We consider a setting in which a principal seeks to induce an adaptive agent to select a target action by providing incentives on one or more actions. The agent maintains a belief about the value for each action—which may update based on experience—and selects at each time step the action with the maximal sum of value and associated incentive. The principal observes the agent’s selection, but has no information about the agent’s current beliefs or belief update process. For inducing the target action as soon as possible, or as often as possible over a fixed time period, it is optimal for a principal with a per-period budget to assign the budget to the target action and wait for the agent to want to make that choice. But with an across-period budget, no algorithm can provide good performance on all instances without knowledge of the agent’s update process, except in the particular case in which the goal is to induce the agent to select the target action once. We demonstrate ways to overcome this strong negative result with knowledge about the agent’s beliefs, by providing a tractable algorithm for solving the offline problem when the principal has perfect knowledge, and an analytical solution for an instance of the problem in which partial knowledge is available.

A fundamental result in mechanism design theory, the so-called revelation principle, asserts that for many questions concerning the existence of mechanisms with a given outcome one can restrict attention to truthful direct-revelation mechanisms. In practice, however, many mechanisms use a restricted message space. This motivates the study of the tradeoffs involved in choosing simplified mechanisms, which can sometimes bring benefits in precluding bad or promoting good equilibria, and other times impose costs on welfare and revenue. We study the simplicity-expressiveness tradeoff in two representative settings, sponsored search auctions and combinatorial auctions, each being a canonical example for complete information and incomplete information analysis, respectively. We observe that the amount of information available to the agents plays an important role for the tradeoff between simplicity and expressiveness.

In kidney exchanges, hospitals share patient lists and receive transplantations. A kidney-paired donation (KPD) mechanism needs to promote full sharing of information about donor-patient pairs, and identify a Pareto efficient outcome that also satisfies participation constraints of hospitals. We introduce a random graph model of the KPD exchange and then fully characterize the structure of the efficient outcome and the expected number of transplantations that can be performed. Random graph theory allows early experimental results to be explained analytically, and enables the study of participation incentives in a methodological way. We derive a square-root law between the welfare gains from sharing patient-donor pairs in a central pool and the individual sizes of hospitals, illustrating the urgent need for the nationwide expansion of such programs. Finally, we establish through theoretical and computational analysis that enforcing simple individual rationality constraints on the outcome can mitigate the negative impact of strategic behavior by hospitals.