Incentive-compatible, budget-balanced, yet highly efficient auctions for supply chain formation

ABSTRACT

Engineering automated negotiation across the supply chain is a central research challenge for the important problem of supply chain formation. The difficult problem of designing negotiation strategies is greatly simplified if the negotiation mechanism is incentive compatible, in which case the agents' dominant strategy is to simply report their private information truthfully. Unfortunately, with two-sided negotiation it is impossible to simultaneously achieve perfect efficiency, budget balance, and individual rationality with incentive compatibility. This bears directly on the mechanism design problem for supply chain formation---the problem of designing auctions to coordinate the buying and selling of goods in multiple markets across a supply chain. We introduce incentive compatible, budget balanced, and individually rational auctions for supply chain formation inspired by previous work of Babaioff and Nisan, but extended to a broader class of supply chain topologies. The auctions explicitly discard profitable trades, thus giving up perfect efficiency to maintain budget balance and individual rationality. We use a novel payment rule analogous to Vickrey-Clarke-Groves payments, but adapted to our allocation rule. The first auction we present is incentive compatible when each agent desires only a single bundle of goods, the auction correctly knows all agents' bundles of interest, but the monetary valuations are private to the agents. We introduce extensions to maintain incentive compatibility when the auction does not know the agents' bundles of interest. We establish a good worst case bound on efficiency when the bundles of interest are known, which also applies in some cases when the bundles are not known. Our auctions produce higher efficiency for a broader class of supply chains than any other incentive compatible, individually rational , and budget-balanced auction we are aware of.

REFERENCES

• 1: Moshe Babaioff , Noam Nisan, Concurrent auctions across the supply chain, Proceedings of the 3rd ACM conference on Electronic Commerce, p.1-10, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501159]
• 2: E. H. Clarke. Multipart pricing of public goods. Public Choice, 11:17--33, Fall 1971.
• 3: Sven de Vries , Rakesh V. Vohra, Combinatorial Auctions: A Survey, INFORMS Journal on Computing, v.15 n.3, p.284-309, July 2003 [doi>10.1287/ijoc.15.3.284.16077]
• 4: T. Groves. Incentives in teams. Econometrica, pages 617--631, 1973.
• 5: Daniel Lehmann , Liadan Ita Oćallaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Journal of the ACM (JACM), v.49 n.5, p.577-602, September 2002 [doi>10.1145/585265.585266]
• 6: J. K. MacKie-Mason and H. R. Varian. Generalized Vickrey auctions. Technical report, Dept. of Economics, Univ. of Michigan, July 1994.
• 7: R. P. McAfee. A dominant strategy double auction. Journal of Economic Theory, 56:434--450, 1992.
• 8: R. B. Myerson and M. A. Satterthwaite. Efficient mechanisms for bilateral trading. Journal of Economic Theory, 29:265--281, 1983.
• 9: N. Nisan and A. Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35(1/2):166--196, April/May 2001.
• 10: D. C. Parkes, J. Kalagnanam, and M. Eso. Achieving budget-balance with Vickrey-based payment schemes in exchanges. In Seventeenth International Joint Conference on Artificial Intelligence, pages 1161--1168, 2001.
• 11: N. M. Sadeh, D. W. Hildum, D. Kjenstad, and A. Tseng. MASCOT: An agent-based architecture for dynamic supply chain creation and coordination in the internet economy. Production Planning and Control, 12(3), 2001.
• 12: W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 16:8--37, 1961.
• 13: William Edward Walsh , Michael P. Wellman, Market protocols for decentralized supply chain formation, 2001
• 14: William E. Walsh , Michael P. Wellman , Fredrik Ygge, Combinatorial auctions for supply chain formation, Proceedings of the 2nd ACM conference on Electronic commerce, p.260-269, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352900]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Payment schemes

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Coherence and coordination; Multiagent systems

General Terms:
Algorithms, Economics

Keywords:
auctions, mechanism design, supply chain formation