Auctions for structured procurement

Matthew C. Cary, Abraham D. Flaxman, Jason D Hartline, Anna R. Karlin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations


This paper considers a general setting for structured procurement and the problem a buyer faces in designing a procurement mechanism to maximize profit. This brings together two agendas in algorithmic mechanism design, frugality in procurement mechanisms (e.g., for paths and spanning trees) and profit maximization in auctions (e.g., for digital goods). In the standard approach to frugality in procurement, a buyer attempts to purchase a set of elements that satisfy a feasibility requirement as cheaply as possible. For profit maximization in auctions, a seller wishes to sell some number of goods for as much as possible. We unify these objectives by endowing the buyer with a decreasing marginal benefit per feasible set purchased and then considering the problem of designing a mechanism to buy a number of sets which maximize the buyer's profit, i.e., the difference between their benefit for the sets and the cost of procurement. For the case where the feasible sets are bases of a matroid, we follow the approach of reducing the mechanism design optimization problem to a mechanism design decision problem. We give a profit extraction mechanism that solves the decision problem for matroids and show that a reduction based on random sampling approximates the optimal profit. We also consider the problem of non-matroid procurement and show that in this setting the approach does not succeed.

Original languageEnglish (US)
Title of host publicationProceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
Number of pages10
StatePublished - 2008
Event19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States
Duration: Jan 20 2008Jan 22 2008

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Other19th Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CitySan Francisco, CA

ASJC Scopus subject areas

  • Software
  • Mathematics(all)


Dive into the research topics of 'Auctions for structured procurement'. Together they form a unique fingerprint.

Cite this