Logo Logo

An Ascending Vickrey Auction for Selling Bases of a Matroid, Operations Research


Consider selling bundles of indivisible goods to buyers with concave utilities that are additively separable in money and goods. We propose an ascending auction for the case when the seller is constrained to sell bundles whose elements form a basis of a matroid. It extends easily to polymatroids. Applications include scheduling (Demange, Gale, and Sotomayor, 1986), allocation of homogeneous goods (Ausubel, 2004), and spatially distributed markets (Babaioff, Nisan, and Pavlov, 2004).Our ascending auction induces buyers to bid truthfully, and returns the economically efficient basis. Unlike other ascending auctions for this environment, ours runs in pseudo-polynomial or polynomial time. Furthermore we prove the impossibility of an ascending auction for nonmatroidal independence set-systems. [Extended abstract published as Bikhchandani, Sushil, Sven de Vries, James Schummer, and Rakesh V. Vohra (2008). Ascending auctions for integral (poly)matroids with concave nondecreasing separable values. In SODA 08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, pages 864-873.]




Sushil Bikhchandani, Sven de Vries, James Schummer, Rakesh Vohra

Date Published



Bikhchandani, Sushil, Sven de Vries, James Schummer, and Rakesh Vohra. 2011. An Ascending Vickrey Auction for Selling Bases of a Matroid. Operations Research. 59(2): 400-413.


Explore leading research and ideas

Find articles, podcast episodes, and videos that spark ideas in lifelong learners, and inspire those looking to advance in their careers.
learn more


Review Courses & Schedules

Access information about specific courses and their schedules by viewing the interactive course scheduler tool.


Discover the path to your goals

Whether you choose our Full-Time, Part-Time or Executive MBA program, you’ll enjoy the same unparalleled education, exceptional faculty and distinctive culture.
learn more