Complexity of combinatorial market makers

Yiling Chen, Lance Fortnow, Nicolas Lambert, David M. Pennock, Jennifer Wortman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

36 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationEC'08 - Proceedings of the 2008 ACM Conference on Electronic Commerce
Pages190-199
Number of pages10
DOIs
StatePublished - 2008
Externally publishedYes
Event2008 ACM Conference on Electronic Commerce, EC'08 - Chicago, IL, United States
Duration: Jul 8 2008Jul 12 2008

Publication series

NameProceedings of the ACM Conference on Electronic Commerce

Conference

Conference2008 ACM Conference on Electronic Commerce, EC'08
Country/TerritoryUnited States
CityChicago, IL
Period7/8/087/12/08

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Computer Networks and Communications

Keywords

  • Logarithmic market scoring rule market makers
  • Online learning with expert advice
  • Prediction markets

Fingerprint

Dive into the research topics of 'Complexity of combinatorial market makers'. Together they form a unique fingerprint.

Cite this