Person:

Ma, Hongyao

In this extended abstract, we consider simple coordination problems, such as allocating the right to use a shared sports facility in a way that maximizes its usage, or picking the time of a meeting in a way that maximizes attendance. More generally, an alternative is selected by a mechanism in period zero based on reports from agents. This induces a decision problem facing agents in the next period (e.g., to use a resource, or to attend a meeting.) Outcomes are designated as either good or bad, and the design goal is to maximize the probability of good outcomes. For example, a good outcome may be the resource being used, or having enough people attend a meeting.

The existence of truthful social choice mechanisms strongly depends on whether monetary transfers are allowed. Without payments there are no truthful, non-dictatorial mechanisms under mild requirements, whereas the VCG mechanism guarantees truthfulness along with welfare maximization when there are payments and utility is quasi-linear in money. In this paper we study mechanisms in which we can use payments but where agents have non quasi-linear utility functions. Our main result extends the Gibbard-Satterthwaite impossibility result by showing that, for two agents, the only truthful mechanism for at least three alternatives under general decreasing utilities remains dictatorial. We then show how to extend the VCG mechanism to work under a more general utility space than quasi-linear (the "parallel domain) and show that the parallel domain is maximal—no mechanism with the VCG properties exists in any larger domain.