The Problem

Consider a network in which each edge is owned by a self-interested agent with a privately known cost. A client wants to buy a path from source s to destination t. This problem is called the path auction problem; it arises in models of network transit, and also in problems of allocating a task to a team of agents. Currently, the most extensively studied solution is to use a strategyproof mechanism (the Vickrey-Clarke-Groves mechanism) to get agents to reveal their true costs.

Our Approach

We study non-strategyproof mechanisms, specifically, variants of first-price auctions, and try to bound the total price paid by the client. A first-price auction is any auction in which links on winning paths are paid their bid amount; the designer has flexibility in specifying remaining details.

Progress

In [1], we characterize all strong epsilon-Nash equilibria of a first-price auction, and show that the total payment is never significantly more than, and often less than, the well known dominant strategy Vickrey-Clark-Groves mechanism. We then present a randomized version of the first-price auction for which the equilibrium condition can be relaxed to \epsilon-Nash equilibrium. We next consider a model in which the amount of demand is uncertain, but its probability distribution is known. For this model, we show that a simple ex ante first-price auction may not have any epsilon-Nash equilibria. We then present a modified mechanism with 2-parameter bids which does have an epsilon-Nash equilibrium.

Future Work

Our results so far assume that agents will reach some Nash equilibrium in their bidding strategies. If agents know each others' costs, it is known how to design protocols to reach an equilibrium (a "bargaining solution"). However, when agents do not know each others' cost, there are no protocols known to enable them to reach a efficient solution in all cases. The future work is to find such protocols. They may even use external subsidies; as long as the subsidies required are lower than the surpluses paid by the Vickrey-Clarke-Groves mechanism, the resulting mechanism may still be superior.

References:

[1] Nicole Immorlica, David Karger, Evdokia Nikolova and Rahul Sami. First-Price Path Auctions. To appear in Proceedings of the ACM Conference on Electronic Commerce (EC '05), Vancouver, Canada, 2005.