Faculty Host: Michael Littman

Abstract:

In this work we consider online auction mechanisms for the allocation of M items that are identical to each other except for the fact that the items have different expiration times, and each item must be allocated before it expires. A computational application is the allocation of time slots in a scheduling problem, and an economic application is the allocation of transportation tickets.

If we ignore incentive issues, then 2-approximation online allocation algorithms are known. We, however, are interested in situations where players act "selfishly" and may misreport values, deadlines, or arrival times. We first design two auction-like mechanisms and prove that a 3-approximation allocation is obtained for a wide class of "semi-myopic" selfish behaviors of the players. The rest of the paper aims at providing a game-theoretic rational justification for acting in such a semi-myopic way.

We first show that the usual notions of incentive compatibility in dominant strategies cannot be used in this case, since such equilibria cannot obtain better than an M-approximation. Instead, we suggest a new notion of "Set-Nash" equilibria, where we cannot pinpoint a single best-response strategy, but rather only a set of possible best-response strategies. These strategies are all semi-myopic and, thus, our mechanisms will perform well on any of them. We believe that this notion is of independent interest.

Joint work with Noam Nisan.