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.)
Copyright. All Rights Reserved.