An Ascending Vickrey Auction for Selling Bases of a Matroid

Sven de Vries

Technische Universitat Munchen

Monday, November 28 at 2:30 in AKW 200

ABSTRACT
We consider an ascending auction to sell a spanning tree in a graph (that can be used also, more generally, to sell bases of a matroid). The value of each edge is private information to the bidders. Bidding sincerely is an equilibrium of the auction and the elements sold form a maximum weight spanning tree of the graph (or a maximum weight basis of the matroid). As a special case of our matroid-auction we obtain the ascending auction by Ausubel (2004) for selling homogeneous goods with decreasing marginal values. The paper is available at: http://www.kellogg.northwestern.edu/faculty/schummer/ftp/research/jvick/jvick.pdf Joint work with Sushil Bikhchandani (UCLA), James Schummer (NWU), Rakesh V. Vohra (NWU) Return to DMTCS home page.

ABSTRACT

We consider an ascending auction to sell a spanning tree in a graph (that can
be used also, more generally, to sell bases of a matroid). The value of each
edge is private information to the bidders. Bidding sincerely is an
equilibrium of the auction and the elements sold form a maximum weight
spanning tree of the graph (or a maximum weight basis of the matroid). As a
special case of our matroid-auction we obtain the ascending auction by Ausubel
(2004) for selling homogeneous goods with decreasing marginal
values.

The paper is available at:
http://www.kellogg.northwestern.edu/faculty/schummer/ftp/research/jvick/jvick.pdf

Joint work with Sushil Bikhchandani (UCLA), James Schummer (NWU),
Rakesh V. Vohra (NWU)

Return to DMTCS home page.