An Ascending Vickrey Auction for Selling Bases of a Matroid

An Ascending Vickrey Auction for Selling Bases of a Matroid

0.00 Avg rating0 Votes
Article ID: iaor20115737
Volume: 59
Issue: 2
Start Page Number: 400
End Page Number: 413
Publication Date: Mar 2011
Journal: Operations Research
Authors: , , ,
Keywords: investment
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, allocation of homogeneous goods, and spatially distributed markets, among others. Our ascending auction induces buyers to bid truthfully and returns the economically efficient basis. Unlike other ascending auctions for this environment, ours runs in pseudopolynomial or polynomial time. Furthermore, we prove the impossibility of an ascending auction for nonmatroidal independence set‐systems.

Reviews

Required fields are marked *. Your email address will not be published.