Auctions for structured procurement

ABSTRACT

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.

REFERENCES

• 1: Aaron Archer , Éva Tardos, Frugal path mechanisms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.991-999, January 06-08, 2002, San Francisco, California
• 2: Bikhchandani, S., de Vries, S., Schummer, J., and Vohra, R. Linear programming and Vickrey auctions. IMA Volume in Mathematics and its Applications, Mathematics of the Internet: E-auction and Markets 127 (2001), 75--116.
• 3: Clarke, E. H. Multipart Pricing of Public Goods. Public Choice 11 (1971), 17--33.
• 4: Artur Czumaj , Amir Ronen, On the expected payment of mechanisms for task allocation, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011782]
• 5: Kaustubh Deshmukh , Andrew V. Goldberg , Jason D. Hartline , Anna R. Karlin, Truthful and Competitive Double Auctions, Proceedings of the 10th Annual European Symposium on Algorithms, p.361-373, September 17-21, 2002
• 6: Edith Elkind , Amit Sahai , Ken Steiglitz, Frugality in path auctions, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 7: Amos Fiat , Andrew V. Goldberg , Jason D. Hartline , Anna R. Karlin, Competitive generalized auctions, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509921]
• 8: Goldberg, A., Hartline, J., Karlin, A., Saks, M., and Wright, A. Competitive auctions. Games and Economic Behavior 55 (2006), 242--269.
• 9: Andrew V. Goldberg , Jason D. Hartline , Andrew Wright, Competitive auctions and digital goods, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.735-744, January 07-09, 2001, Washington, D.C., United States
• 10: Groves, T. Incentives in Teams. Econometrica 41 (1973), 617--631.
• 11: Karger, D. R. Random sampling and greedy sparsification for matroid optimization problems. Math. Programming 82, 1--2, Ser. B (1998), 41--81. Networks and matroids; Sequencing and scheduling.
• 12: Anna R. Karlin , David Kempe , Tami Tamir, Beyond VCG: Frugality of Truthful Mechanisms, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.615-626, October 23-25, 2005 [doi>10.1109/SFCS.2005.25]
• 13: Moulin, H., and Shenker, S. Strategyproof Sharing of Submodular Costs: Budget Balance Versus Efficiency. Economic Theory 18 (2001), 511--533.
• 14: Myerson, R. Optimal Auction Design. Mathematics of Operations Research 6 (1981), 58--73.
• 15: Nash-Williams, C. S. J. A. An Application of Matroids to Graph Theory. In Theory of graphs: International Symposium, vol. 1966. Gordon & Breach, New York, 1967, pp. 264--265. Held at the International Computation Center in Rome, July.
• 16: Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
• 17: Oxley, J. G. Matroid Theory. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1992.
• 18: Amir Ronen , Rina Talisman, Towards Generic Low Payment Mechanisms for Decentralized Task Allocation: A Learning Based Approach, Proceedings of the Seventh IEEE International Conference on E-Commerce Technology, p.126-133, July 19-22, 2005 [doi>10.1109/ICECT.2005.96]
• 19: Kunal Talwar, The Price of Truth: Frugality in Truthful Mechanisms, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.608-619, February 27-March 01, 2003
• 20: Vickrey, W. Counterspeculation, Auctions, and Competitive Sealed Tenders. J. of Finance 16 (1961), 8--37.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.1 ADMINISTRATIVE DATA PROCESSING
      Subjects: Business

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.3 Applications

  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems
          Subjects: Decision support (e.g., MIS)

General Terms:
Algorithms, Design, Management, Theory