Research Details

Abstract

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.]

Type

Article

Author(s)

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

Date Published

2011

Citations

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