Generalized value decomposition and structured multiattribute auctions

ABSTRACT

Multiattribute auction mechanisms generally either remain agnostic about traders' preferences, or presume highly restrictive forms, such as full additivity. Real preferences often exhibit dependencies among attributes, yet may possess some structure that can be usefully exploited to streamline communication and simplify operation of a multiattribute auction. We develop such a structure using the theory of measurable value functions, a cardinal utility representation based on an underlying order over preference differences. A set of local conditional independence relations over such differences supports a generalized additive preference representation, which decomposes utility across overlapping clusters of related attributes. We introduce an iterative auction mechanism that maintains prices on local clusters of attributes rather than the full space of joint configurations. When traders' preferencesare consistent with the auction's generalized additive structure, the mechanism produces approximately optimal allocations, atapproximate VCG prices.

REFERENCES

• 1: F. Bacchus and A. Grove. Graphical models for preference and utility. In Eleventh Conference on Uncertainty in Artificial Intelligence, pages 3--10, Montreal, 1995.
• 2: Damian R. Beil , Lawrence M. Wein, An Inverse-Optimization-Based Auction Mechanism to Support a Multiattribute RFQ Process, Management Science, v.49 n.11, p.1529-1545, November 2003 [doi>10.1287/mnsc.49.11.1529.20588]
• 3: Martin Bichler, The Future of Emarkets: Multi-Dimensional Market Mechanisms, Cambridge University Press, New York, NY, 2001
• 4: Craig Boutilier , Fahiem Bacchus , Ronen I. Brafman, UCP-Networks: A Directed Graphical Representation of Conditional Utilities, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.56-64, August 02-05, 2001
• 5: Ronen I. Brafman , Carmel Domshlak , Tanya Kogan, Compact value-function representations for qualitative preferences, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.51-58, July 07-11, 2004, Banff, Canada
• 6: D. Braziunas and C. Boutilier. Local utility elicitation in GAI models. In Twenty-first Conference on Uncertainty in Artificial Intelligence, pages 42--49, Edinburgh, 2005.
• 7: Y.-K. Che. Design competition through multidimensional auctions. RAND Journal of Economics, 24(4):668--680, 1993.
• 8: Esther David , Rina Azoulay-Schwartz , Sarit Kraus, An English Auction Protocol for Multi-attribute Items, Revised Papers from the Workshop on Agent Mediated Electronic Commerce on Agent-Mediated Electronic Commerce IV, Designing Mechanisms and Systems, p.52-68, July 16, 2002
• 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 Univ. Press, 1959.
• 10: J. S. Dyer and R. K. Sarin. An axiomatization of cardinal additive conjoint measurement theory. Working Paper 265, WMSI, UCLA, February 1977.
• 11: J. S. Dyer and R. K. Sarin. Measurable multiattribute value functions. Operations Research, 27:810--822, 1979.
• 12: Yagil Engel , Michael P. Wellman , Kevin M. Lochner, Bid expressiveness and clearing algorithms in multiattribute double auctions, Proceedings of the 7th ACM conference on Electronic commerce, p.110-119, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134720]
• 13: P. C. Fishburn. Interdependence and additivity in multivariate, unidimensional expected utility theory. Intl. Economic Review, 8:335--342, 1967.
• 14: C. Gonzales and P. Perny. GAI networks for utility elicitation. In Ninth Intl. Conf. on the Principles of Knowledge Representation and Reasoning, pages 224--234, Whistler, BC, 2004.
• 15: C. Gonzales and P. Perny. GAI networks for decision making under certainty. In IJCAI-05 Workshop on Advances in Preference Handling, Edinburgh, 2005.
• 16: N. Hyafil and C. Boutilier. Regret-based incremental partial revelation mechanisms. In Twenty-first National Conference on Artificial Intelligence, pages 672--678, Boston, MA, 2006.
• 17: R. L. Keeney and H. Raiffa. Decisions with Multiple Objectives: Preferences and Value Tradeoffs. Wiley, 1976.
• 18: D. Nilsson, An efficient algorithm for finding the M most probable configurationsin probabilistic expert systems, Statistics and Computing, v.8 n.2, p.159-173, June 1998 [doi>10.1023/A:1008990218483]
• 19: David C. Parkes , Jayant Kalagnanam, Models for Iterative Multiattribute Procurement Auctions, Management Science, v.51 n.3, p.435-451, March 2005 [doi>10.1287/mnsc.1040.0340]
• 20: J. Pearl and A. Paz. Graphoids: A graph based logic for reasoning about relevance relations. In B. Du Boulay, editor, Advances in Artificial Intelligence II. 1989.
• 21: J. Shachat and J. T. Swarthout. Procurement auctions for differentiated goods. IBM Research Report RC22587, IBM T.J. Watson Research Laboratory, 2002.
• 22: Nir Vulkan , Nicholas R. Jennings, Efficient mechanisms for the supply of services in multi-agent environments, Decision Support Systems, v.28 n.1-2, p.5-19, March 2000 [doi>10.1016/S0167-9236(99)00071-8]

INDEX TERMS

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

General Terms:
Algorithms, Economics

Keywords:
auctions, multiattribute auctions, preference handling