Complexity of combinatorial market makers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Complexity of combinatorial market makers

Full text

Pdf (239 KB)

Source

Electronic Commerce archive
Proceedings of the 9th ACM conference on Electronic commerce table of contents

Chicago, Il, USA

SESSION: Prediction markets table of contents

Pages 190-199

Year of Publication: 2008

ISBN:978-1-60558-169-9

Authors

Yiling Chen	Yahoo! Research, New York, NY, USA
Lance Fortnow	Northwestern University, Evanston, IL, USA
Nicolas Lambert	Stanford University, Stanford, CA, USA
David M. Pennock	Yahoo! Research, New York, NY, USA
Jennifer Wortman	University of Pennsylvania, Philadelphia, PA, USA

Sponsors

ACM: Association for Computing Machinery
SIGEcom: ACM Special Interest Group on Electronic Commerce

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 68, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1386790.1386822 What is a DOI?

ABSTRACT

We analyze the computational complexity of market maker pricing algorithms for combinatorial prediction markets. We focus on Hanson's popular logarithmic market scoring rule market maker (LMSR). Our goal is to implicitly maintain correct LMSR prices across an exponentially large outcome space. We examine both permutation combinatorics, where outcomes are permutations of objects, and Boolean combinatorics, where outcomes are combinations of binary events. We look at three restrictive languages that limit what traders can bet on. Even with severely limited languages, we find that LMSR pricing is #P-hard, even when the same language admits polynomial-time matching without the market maker. We then propose an approximation technique for pricing permutation markets based on an algorithm for online permutation learning. The connections we draw between LMSR pricing and the literature on online learning with expert advice may be of independent interest.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	H. Balakrishnan, I. Hwang, and C. Tomlin. Polynomial approximation algorithms for belief matrix maintenance in identity management. In 43rd Conference on Decision and Control, pages 4874--4879, 2004.
	2	Graham Brightwell , Peter Winkler, Counting linear extensions is #P-complete, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.175-181, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103441]
	3	Nicolo Cesa-Bianchi , Gabor Lugosi, Prediction, Learning, and Games, Cambridge University Press, New York, NY, 2006
	4	Yiling Chen , Lance Fortnow , Evdokia Nikolova , David M. Pennock, Betting on permutations, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250957]
	5	Yiling Chen , Lance Fortnow , Evdokia Nikolova , David M. Pennock, Combinatorial betting, ACM SIGecom Exchanges, v.7 n.1, p.61-64, December 2007 [doi>10.1145/1345037.1345053]
	6	Yiling Chen , Sharad Goel , David M. Pennock, Pricing combinatorial markets for tournaments, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374421]
	7	Y. Chen, D. M. Reeves, D. M. Pennock, R. D. Hanson, L. Fortnow, and R. Gonen. Bluffing and strategic reticence in prediction markets. In Workshop on Internet and Network Economics, 2007.
	8	Yiling Chen and David M. Pennock. A utility framework for bounded-loss market makers. In Proceedings of the 23rd Conference on Uncertainty in Artificial Intelligence, pages 49--56, 2007.
	9	R. Forsythe, F. Nelson, G. Neumann, and J. Wright. Anatomy of an experimental political stock market. The American Economic Review, 82(5):1142--1161, 1992.
	10	R. Forsythe, T. Rietz, and T. Ross. Wishes, expectations, and actions: A survey on price formation in election stock markets. Journal of Economic Behavior and Organization, 39:83--110, 1999.
	11	Lance Fortnow , Joe Kilian , David M. Pennock , Michael P. Wellman, Betting Boolean-style: a framework for trading in securities based on logical formulas, Decision Support Systems, v.39 n.1, p.87-104, March 2005 [doi>10.1016/j.dss.2004.08.010]
	12	Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, v.55 n.1, p.119-139, Aug. 1997 [doi>10.1006/jcss.1997.1504]
	13	Robin Hanson, Combinatorial Information Market Design, Information Systems Frontiers, v.5 n.1, p.107-119, January 2003 [doi>10.1023/A:1022058209073]
	14	R. D. Hanson. Logarithmic market scoring rules for modular combinatorial information aggregation. Journal of Prediction Markets, 2007.
	15	R. D. Hanson, J. Ledyard, and T. Ishikida. An experimental test of combinatorial information markets. Journal of Economic Behavior and Organization, 2008. To appear.
	16	D. Helmbold and M. Warmuth. Learning permutations with exponential weights. In 20th Annual Conference on Learning Theory, pages 469--483, 2007.
	17	Bahman Kalantari and Leonid Khachiyan. On the complexity of nonnegative-matrix scaling. Linear Algebra and its applications, (240):87--103, 1996.
	18	Nathan Linial, Alex Samorodnitsky, and Avi Wigderson. A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. Combinatorica, 20(4):545--568, 2000.
	19	Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
	20	R. Nelson and D. Bessler. Subjective probabilities and scoring rules: Experimental evidence. American Journal of Agricultural Economics, 71(2):363--369, 1989.
	21	Kenneth Oliven , Thomas A. Rietz, Suckers Are Born but Markets Are Made: Individual Rationality, Arbitrage, and Market Efficiency on an Electronic Futures Market, Management Science, v.50 n.3, p.336-351, March 2004 [doi>10.1287/mnsc.1040.0191]
	22	R. Sinkhorn. A relationship between arbitrary positive matrices and doubly stochastic matrices. The Annals of Mathematical Statistics, 35(2):876--879, 1964.
	23	R. Thaler and W. Ziemba. Anomalies: Parimutuel betting markets: Racetracks and lotteries. Journal of Economic Perspectives, 2(2):161--174, 1988.
	24	Seinosuke Toda, PP is as hard as the polynomial-time hierarchy, SIAM Journal on Computing, v.20 n.5, p.865-877, Oct. 1991 [doi>10.1137/0220053]
	25	L. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8:189--201, 1979.
	26	L. Valiant. The complexity of enumeration and reliability problems. SIAM Journal of Computing, 8(3):410--421, 1979.
	27	V. Vovk, A game of prediction with expert advice, Journal of Computer and System Sciences, v.56 n.2, p.153-173, April 1998 [doi>10.1006/jcss.1997.1556]

CITED BY 2

	Joan Feigenbaum , David C. Parkes , David M. Pennock, Computational challenges in e-commerce, Communications of the ACM, v.52 n.1, January 2009
	Mingyu Guo , David M. Pennock, Combinatorial prediction markets for event hierarchies, Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems, May 10-15, 2009, Budapest, Hungary