Frugal Auctions For Vertex Covers, Flows, and Cuts

David Kempe
University of Southern California (USC)

In this talk, we investigate auction mechanisms for combinatorial reverse auctions. The model is that selfish agents own elements, and the
auctioneer wants to purchase a feasible set for some problem from the agents. The specific problems that we study are:

1. Vertex Cover: The agents own the vertices of a graph, and the
auctioneer wants to purchase a vertex cover from them.
2. k-Flow: The agents own edges, and the auctioneer wants to buy k
edge-disjoint paths from a source to a sink.
3. Cut: The agents own edges, and the auctioneer wants to purchase an
s-t cut.

In such settings, it is commonly assumed that selfish agents will act in such a way as to maximize their own profit; in particular, this may
include misrepresenting their true cost for letting the auctioneer use their resources (edges or vertices). Thus, mechanisms should have
severable desirable properties.
1. Truthfulness: selfish agents want to reveal their true costs.
2. Frugality: the mechanism does not pay much more than "necessary" to achieve truthfulness.
3. Computability: the mechanism can be computed in polynomial time.

We begin this talk with a brief introduction to auctions, truthfulness, and the notion of frugality.
After presenting a novel and optimal mechanism for Vertex Cover,we show how to use the Vertex Cover mechanism as a useful design methodology for other problems, by deriving from it
competitive mechanisms for flows and cuts.
We end with a number of interesting open problems.

(Joint work with Mahyar Salek and Cristopher Moore; this talk will also discuss a recent independent paper by Ning Chen, Edith Elkind, Nick Gravin, and Fedor Petrov, including the similarities and differences between the ideas.)

Back to Algorithmic Game Theory