Bid expressiveness and clearing algorithms in multiattribute double auctions

ABSTRACT

We investigate the space of two-sided multiattribute auctions, focusing on the relationship between constraints on the offers traders can express through bids, and the resulting computational problem of determining an optimal set of trades. We develop a formal semantic framework for characterizing expressible offers, and show conditions under which the allocation problem can be separated into first identifying optimal pairwise trades and subsequently optimizing combinations of those trades. We analyze the bilateral matching problem while taking into consideration relevant results from multiattribute utility theory. Network flow models we develop for computing global allocations facilitate classification of the problem space by computational complexity, and provide guidance for developing solution algorithms. Experimental trials help distinguish tractable problem classes for proposed solution techniques.

REFERENCES

• 1: R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows. Prentice-Hall, 1993.
• 2: F. Bacchus and A. Grove. Graphical models for preference and utility. In Eleventh Conference on Uncertainty in Artificial Intelligence, pages 3--10, Montreal, 1995.
• 3: Martin Bichler, The Future of Emarkets: Multi-Dimensional Market Mechanisms, Cambridge University Press, New York, NY, 2001
• 4: M. Bichler and J. Kalagnanam. Configurable offers and winner determination in multi-attribute auctions. European Journal of Operational Research, 160:380--394, 2005.
• 5: M. Bichler, M. Kaukal, and A. Segev. Multi-attribute auctions for electronic procurement. In Proceedings of the 1st IBM IAC Workshop on Internet Based Negotiation Technologies, 1999.
• 6: C. Boutilier, T. Sandholm, and R. Shields. Eliciting bid taker non-price preferences in (combinatorial) auctions. In Nineteenth Natl. Conf. on Artificial Intelligence, pages 204--211, San Jose, 2004.
• 7: F. Branco. The design of multidimensional auctions. RAND Journal of Economics, 28(1):63--81, 1997.
• 8: Y.-K. Che. Design competition through multidimensional auctions. RAND Journal of Economics, 24(4):668--680, 1993.
• 9: G. Debreu. Topological methods in cardinal utility theory. In K. Arrow, S. Karlin, and P. Suppes, editors, Mathematical Methods in the Social Sciences. Stanford University Press, 1959.
• 10: N. Economides and R. A. Schwartz. Electronic call market trading. Journal of Portfolio Management, 21(3), 1995.
• 11: Y. Engel and M. P. Wellman. Multiattribute utility representation for willingness-to-pay functions. Tech. report, Univ. of Michigan, 2006.
• 12: Eugene Fink , Josh Johnson , Jenny Hu, Exchange Market for Complex Goods: Theory and Experiments, Netnomics, v.6 n.1, p.21-42, April 2004 [doi>10.1023/B:NETN.0000023379.66597.7c]
• 13: M L Fisher , R Jaikumar , L N Van Wassenhove, A multiplier adjustment method for the generalized assignment problem, Management Science, v.32 n.9, p.1095-1103, Sept. 1986 [doi>10.1287/mnsc.32.9.1095]
• 14: J. Gong. Exchanges for complex commodities: Search for optimal matches. Master's thesis, University of South Florida, 2002.
• 15: C. Gonzales and P. Perny. GAI networks for decision making under certainty. In IJCAI-05 workshop on preferences, Edinburgh, 2005.
• 16: Jayant R. Kalagnanam , Andrew J. Davenport , Ho S. Lee, Computational Aspects of Clearing Continuous Call Double Auctions with Assignment Constraints and Indivisible Demand, Electronic Commerce Research, v.1 n.3, p.221-238, July 2001 [doi>10.1023/A:1011589804040]
• 17: R. L. Keeney and H. Raiffa. Decisions with Multiple Objectives: Preferences and Value Tradeoffs. Wiley, 1976.
• 18: Noam Nisan, Bidding and allocation in combinatorial auctions, Proceedings of the 2nd ACM conference on Electronic commerce, p.1-12, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352872]
• 19: D. C. Parkes and J. Kalagnanam. Models for iterative multiattribute procurement auctions. Management Science, 51:435--451, 2005.
• 20: T. Sandholm and S. Suri. Side constraints and non-price attributes in markets. In IJCAI-01 Workshop on Distributed Constraint Reasoning, Seattle, 2001.
• 21: L. J. Schvartzman and M. P. Wellman. Market-based allocation with indivisible bids. In AAMAS-05 Workshop on Agent-Mediated Electronic Commerce, Utrecht, 2005.
• 22: J. Shachat and J. T. Swarthout. Procurement auctions for differentiated goods. Technical Report 0310004, Economics Working Paper Archive at WUSTL, Oct. 2003.
• 23: Aditya V. Sunderam , David C. Parkes, Preference elicitation in proxied multiattribute auctions, Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779965]
• 24: P. R. Wurman, M. P. Wellman, and W. E. Walsh. A parametrization of the auction design space. Games and Economic Behavior, 35: 304--338, 2001.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Economics

Keywords:
auctions, multiattribute auctions