research-article

A tractable combinatorial market maker using constraint generation

Authors:

Miroslav Dudik,

Sebastien Lahaie,

David M. PennockAuthors Info & Claims

EC '12: Proceedings of the 13th ACM Conference on Electronic Commerce

Pages 459 - 476

https://doi.org/10.1145/2229012.2229047

Published: 04 June 2012 Publication History

Abstract

We present a new automated market maker for providing liquidity across multiple logically interrelated securities. Our approach lies somewhere between the industry standard---treating related securities as independent and thus not transmitting any information from one security to another---and a full combinatorial market maker for which pricing is computationally intractable. Our market maker, based on convex optimization and constraint generation, is tractable like independent securities yet propagates some information among related securities like a combinatorial market maker, resulting in more complete information aggregation. We prove several favorable properties of our scheme and evaluate its information aggregation performance on survey data involving hundreds of thousands of complex predictions about the 2008 U.S. presidential election.

References

[1]

ABERNETHY, J., CHEN, Y., AND WORTMAN, J. 2011. An optimization-based framework for automated market-making. In ACM Conference on Electronic Commerce.

Digital Library

[2]

AGRAWAL, S., WANG, Z., AND YE, Y. 2008. Parimutuel betting on permutations. In International Workshop on Internet and Network Economics. 126--137.

Digital Library

[3]

CHEN, Y., FORTNOW, L., LAMBERT, N., PENNOCK, D. M., AND WORTMAN, J. 2008a. Complexity of combinatorial market makers. In ACM Conference on Electronic Commerce. ACM, New York, NY, USA, 190--199.

Digital Library

[4]

CHEN, Y., FORTNOW, L., NIKOLOVA, E., AND PENNOCK, D. M. 2007. Betting on permutations. In ACM Conference on Electronic Commerce. 326--335.

Digital Library

[5]

CHEN, Y., GOEL, S., AND PENNOCK, D. M. 2008b. Pricing combinatorial markets for tournaments. In ACM Symposium on Theory of Computing. ACM, New York, NY, USA, 305--314.

Digital Library

[6]

CHEN, Y. AND PENNOCK, D. M. 2007. A utility framework for bounded-loss market makers. In Conference on Uncertainty in Artificial Intelligence. 49--56.

[7]

DUDÍK, M., PHILLIPS, S. J., AND SCHAPIRE, R. E. 2007. Maximum entropy density estimation with generalized regularization and an application to species distribution modeling. Journal of Machine Learning Research 8, 1217--1260.

Digital Library

[8]

FEIGE, U., MIRROKNI, V. S., AND VONDRAK, J. 2007. Maximizing non-monotone submodular functions. In IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, Washington, DC, USA, 461--471.

Digital Library

[9]

FORTNOW, L., KILIAN, J., PENNOCK, D. M., AND WELLMAN, M. P. 2004. Betting Boolean-style: A framework for trading in securities based on logical formulas. Decision Support Systems 39, 1, 87--104.

Digital Library

[10]

GALAMBOS, J. AND SIMONELLI, I. 1996. Bonferroni-Type Inequalities with Applications. Springer, New York.

[11]

GUO, M. AND PENNOCK, D. M. 2009. Combinatorial prediction markets for event hierarchies. In International Conference on Autonomous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 201--208.

Digital Library

[12]

HANSON, R. D. 2003. Combinatorial information market design. Information Systems Frontiers 5, 1, 107--119.

Digital Library

[13]

HANSON, R. D. 2007. Logarithmic market scoring rules for modular combinatorial information aggregation. Journal of Prediction Markets 1, 1, 1--15.

[14]

HANSON, R. D., OPREA, R., AND PORTER, D. 2007. Information aggregation and manipulation in an experimental market. Journal of Economic Behavior and Organization 60, 4, 449--459.

[15]

NESTEROV, Y. 2007. Gradient methods for minimizing composite objective function. Tech. Rep. 76, Center for Operations Research and Econometrics (CORE), Catholic University of Louvain (UCL).

[16]

OTHMAN, A. AND SANDHOLM, T. 2011. Automated market makers that enable new settings: Extending constant-utility cost functions. In Conference on Auctions, Market Mechanisms and Their Applications.

[17]

PENNOCK, D. M. AND XIA, L. 2011. Price updating in combinatorial prediction markets with Bayesian networks. In Conference on Uncertainty in Artificial Intelligence. 581--588.

[18]

ROCKAFELLAR, R. T. 1970. Convex Analysis. Princeton University Press, Princeton, NJ.

[19]

SONTAG, D. AND JAAKKOLA, T. 2007. New outer bounds on the marginal polytope. In Neural Information Processing Systems.

[20]

WAINWRIGHT, M. J. AND JORDAN, M. I. 2008. Graphical models, exponential families, and variational inference. Found. Trends Mach. Learn. 1, 1--305.

Digital Library

[21]

WANG, G., KULKARNI, S. R., POOR, H. V., AND OSHERSON, D. N. 2011. Aggregating large sets of probabilistic forecasts by weighted coherent adjustment. Decision Analysis 8, 128--144.

Digital Library

[22]

XIA, L. AND PENNOCK, D. M. 2011. An efficient Monte-Carlo algorithm for pricing combinatorial prediction markets for tournaments. In International Joint Conference on Artificial Intelligence. 452--457.

Digital Library

[23]

em International Workshop on Internet and Network Economics}. 126--137.

Cited By

Laskey KSun WHanson RTwardy CMatsumoto SGoldfedder B(2018)Graphical model market maker for combinatorial prediction marketsJournal of Artificial Intelligence Research10.1613/jair.1.1124963:1(421-460)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1613/jair.1.11249
Heidari HLahaie SPennock DVaughan J(2018)Integrating Market Makers, Limit Orders, and Continuous Trade in Prediction MarketsACM Transactions on Economics and Computation10.1145/32746436:3-4(1-26)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1145/3274643
Wah ELahaie SPennock D(2016)An empirical game-theoretic analysis of price discovery in prediction marketsProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3060621.3060693(510-516)Online publication date: 9-Jul-2016
https://dl.acm.org/doi/10.5555/3060621.3060693
Show More Cited By

Index Terms

A tractable combinatorial market maker using constraint generation
1. Applied computing
  1. Law, social and behavioral sciences
    1. Economics

Recommendations

A bayesian market maker
EC '12: Proceedings of the 13th ACM Conference on Electronic Commerce

Ensuring sufficient liquidity is one of the key challenges for designers of prediction markets. Variants of the logarithmic market scoring rule (LMSR) have emerged as the standard. LMSR market makers are loss-making in general and need to be subsidized. ...
A combinatorial prediction market for the U.S. elections
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerce

We report on a large-scale case study of a combinatorial prediction market. We implemented a back-end pricing engine based on Dudik et al.'s (2012) combinatorial market maker, together with a wizard-like front end to guide users to constructing any of ...
A combinatorial prediction market for the U.S. elections
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerce

We report on a large-scale case study of a combinatorial prediction market. We implemented a back-end pricing engine based on Dudik et al.'s (2012) combinatorial market maker, together with a wizard-like front end to guide users to constructing any of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '12: Proceedings of the 13th ACM Conference on Electronic Commerce

June 2012

1016 pages

ISBN:9781450314152

DOI:10.1145/2229012

General Chair:
Boi Faltings
École Polytechnique Fédérale de Lausanne (EPFL)
,
Program Chairs:
Kevin Leyton-Brown
University of British Columbia
,
Panos Ipeirotis
New York University

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGecom: Special Interest Group on Economics and Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 June 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EC '12

Sponsor:

SIGecom

EC '12: ACM Conference on Electronic Commerce

June 4 - 8, 2012

Valencia, Spain

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Upcoming Conference

EC '25

Sponsor:
sigecom

The 25th ACM Conference on Economics and Computation

July 7 - 11, 2025

Stanford , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
121
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Laskey KSun WHanson RTwardy CMatsumoto SGoldfedder B(2018)Graphical model market maker for combinatorial prediction marketsJournal of Artificial Intelligence Research10.1613/jair.1.1124963:1(421-460)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1613/jair.1.11249
Heidari HLahaie SPennock DVaughan J(2018)Integrating Market Makers, Limit Orders, and Continuous Trade in Prediction MarketsACM Transactions on Economics and Computation10.1145/32746436:3-4(1-26)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1145/3274643
Wah ELahaie SPennock D(2016)An empirical game-theoretic analysis of price discovery in prediction marketsProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3060621.3060693(510-516)Online publication date: 9-Jul-2016
https://dl.acm.org/doi/10.5555/3060621.3060693
Chen YGhosh AKearns MRoughgarden TVaughan J(2016)Mathematical foundations for social computingCommunications of the ACM10.1145/296040359:12(102-108)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1145/2960403
Kroer CDudík MLahaie SBalakrishnan SConitzer VBergemann DChen Y(2016)Arbitrage-Free Combinatorial Market Making via Integer ProgrammingProceedings of the 2016 ACM Conference on Economics and Computation10.1145/2940716.2940767(161-178)Online publication date: 21-Jul-2016
https://dl.acm.org/doi/10.1145/2940716.2940767
Devanur NDudík MHuang ZPennock D(2015)Budget constraints in prediction marketsProceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence10.5555/3020847.3020873(238-247)Online publication date: 12-Jul-2015
https://dl.acm.org/doi/10.5555/3020847.3020873
Heidari HLahaie SPennock DVaughan JRoughgarden TFeldman MSchwarz M(2015)Integrating Market Makers, Limit Orders, and Continuous Trade in Prediction MarketsProceedings of the Sixteenth ACM Conference on Economics and Computation10.1145/2764468.2764532(583-600)Online publication date: 15-Jun-2015
https://dl.acm.org/doi/10.1145/2764468.2764532
Dudík MFrongillo RVaughan J(2014)Market making with decreasing utility for informationProceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence10.5555/3020751.3020768(152-161)Online publication date: 23-Jul-2014
https://dl.acm.org/doi/10.5555/3020751.3020768
Dudik MLahaie SPennock DRothschild DKearns MMcAfee PTardos É(2013)A combinatorial prediction market for the U.S. electionsProceedings of the fourteenth ACM conference on Electronic commerce10.1145/2492002.2482601(341-358)Online publication date: 16-Jun-2013
https://dl.acm.org/doi/10.1145/2492002.2482601
Dudik MLahaie SPennock DRothschild DKearns MMcAfee PTardos É(2013)A combinatorial prediction market for the U.S. electionsProceedings of the fourteenth ACM conference on Electronic commerce10.1145/2482540.2482601(341-358)Online publication date: 16-Jun-2013
https://dl.acm.org/doi/10.1145/2482540.2482601

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten