Frugal Auctions for Vertex Covers, Flows, and Cuts



David Kemp

Monday 19, 2011
4:00 PM,
5130 Upson Hall



In this talk, we investigate auction mechanisms for combinatorialreverse 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 kedge-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, which appeared in FOCS 2010; this talk will also discuss an independent FOCS 2010 paper by Ning Chen, Edith Elkind, Nick Gravin, and Fedor Petrov, including the similarities and differences between the ideas.)