Mechanisms for a spatially distributed market

ABSTRACT

We consider the problem of a spatially distributed market with strategic agents. In this problem a single good is traded in a set of independent markets, where shipment between markets is possible but incurs a cost. The problem has previously been studied in the non-strategic case, inwhich it can be analyzed and solved as a min-cost-flow problem. We considerthe case where buyers and sellers are strategic. Our first result gives adouble characterization of the VCG prices, first as distances in acertain residue graph and second as the minimal (for buyers) and maximal (forsellers) equilibrium prices. This provides a computationally efficient, individually rational and incentive compatible welfare maximizing mechanism. This mechanism is, necessarily, not budget balanced and we provide alsoa budget-balanced mechanism (which is also computationally efficient,incentive compatible, and individually rational) that achieves highwelfare. Some of our results extend to the cases where buyers andsellers have arbitrary convex demand and supply functions and to the case where transportation is controlled by strategic agents as well.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: Simon Anderson and Maxim Engers. Spatial competition with price-taking firms. Economica, 61:125--36, May 1994.
• 3: 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]
• 4: Moshe Babaioff , William E. Walsh, Incentive-compatible, budget-balanced, yet highly efficient auctions for supply chain formation, Proceedings of the 4th ACM conference on Electronic commerce, p.64-75, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779937]
• 5: Leon Y. Chu and Zuo-Jun Max Shen. Dominant strategy double auction with pair-related costs. University of Florida, Working Paper, 2003.
• 6: E. H. Clarke. Multipart pricing of public goods. Public Choice, 11:17--33, Fall 1971.
• 7: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 8: 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]
• 9: Theodore Groves. Incentives in teams. Econometrica, pages 617--631, 1973.
• 10: Frauk Gul and Ennio Stacchetti. Walrasian equilibrium with gross substitutes. Journal of Economic Theory, 87:95--124, 1999.
• 11: Peter H. Lindert and Jeffrey G. Williamson. Does globalization make the world more unequal. NBER 8228 Working Paper, 2001.
• 12: Andreu Mas-Colell, Michael D. Whinston, and Jerry R. Green. Microeconomic Theory. Oxford University Press, New York, 1995.
• 13: R. Preston McAfee. A dominant strategy double auction. Journal of Economic Theory, 56:434--450, 1992.
• 14: Paul Milgrom. Putting auction theory to work: The simultaneous ascending auction. The Journal of Political Economy, 108(2):245--272, April 2000.
• 15: Roger B. Myerson and Mark A. Satterthwaite. Efficient mechanisms for bilateral trading. Journal of Economic Theory, 29:265--281, 1983.
• 16: Noam Nisan and Amir Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35(1/2):166--196, April/May 2001.
• 17: Rabin Roundy, Rachel Chen, Ganesh Janakriraman, and Rachel Q. Zhang. Efficient auction mechanisms for supply chain procurement. Technical Report 1287, School of Operations Research and Industrial Engineering, Cornell University, 2001.
• 18: A. Schrijver. Combinatorial Optimization - Polyhedra and Efficiency. Springer, 2003.
• 19: William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 16:8--37, 1961.
• 20: 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: Multiagent systems; Coherence and coordination

General Terms:
Algorithms, Economics

Keywords:
algorithms, economics