More Web Proxy on the site http://driver.im/

research-article

Arbitrage-Free Combinatorial Market Making via Integer Programming

Authors:

Christian Kroer,

Miroslav Dudík,

Sébastien Lahaie,

Sivaraman BalakrishnanAuthors Info & Claims

EC '16: Proceedings of the 2016 ACM Conference on Economics and Computation

Pages 161 - 178

https://doi.org/10.1145/2940716.2940767

Published: 21 July 2016 Publication History

Abstract

We present a new combinatorial market maker that operates arbitrage-free combinatorial prediction markets specified by integer programs. Although the problem of arbitrage-free pricing, while maintaining a bound on the subsidy provided by the market maker, is #P-hard in the worst case, we posit that the typical case might be amenable to modern integer programming (IP) solvers. At the crux of our method is the Frank-Wolfe (conditional gradient) algorithm which is used to implement a Bregman projection aligned with the market maker's cost function, using an IP solver as an oracle. We demonstrate the tractability and improved accuracy of our approach on real-world prediction market data from combinatorial bets placed on the 2010 NCAA Men's Division I Basketball Tournament, where the outcome space is of size $2^{63}$. To our knowledge, this is the first implementation and empirical evaluation of an arbitrage-free combinatorial prediction market on this scale.

References

[1]

Jacob Abernethy, Yiling Chen, and Jennifer Wortman Vaughan. 2011. An optimization-based framework for automated market-making. In EC-11.

Digital Library

[2]

David Belanger, Dan Sheldon, and Andrew McCallum. 2013. Marginal Inference in MRFs using Frank-Wolfe. In NIPS 2013 workshop on Greedy Optimization, Frank-Wolfe and Friends.

[3]

Joyce Berg, Robert Forsythe, Forrest Nelson, and Thomas Rietz. 2008. Results from a Dozen Years of Election Futures Markets Research. In Handbook of Exp. Econ. Results.

[4]

Dimitri P. Bertsekas. 2015. Convex Optimization Algorithms.

[5]

Robert Charette. 2007. An Internal Futures Market. Information Management (March 2007).

[6]

Yiling Chen, Lance Fortnow, Nicolas Lambert, David M. Pennock, and Jennifer Wortman. 2008. Complexity of Combinatorial Market Makers. In EC-08.

Digital Library

[7]

Yiling Chen, Lance Fortnow, Evdokia Nikolova, and David M. Pennock. 2007. Betting on Permutations. In EC-07.

Digital Library

[8]

Yiling Chen, Sharad Goel, and David M. Pennock. 2008. Pricing Combinatorial Markets for Tournaments. In STOC-08.

Digital Library

[9]

Yiling Chen and David M. Pennock. 2007. A Utility Framework for Bounded-Loss Market Makers. In UAI-07.

[10]

Miroslav Dudík, Rafael Frongillo, and Jennifer Wortman Vaughan. 2014. Market Making with Decreasing Utility for Information. In UAI-14.

[11]

Miroslav Dudík, Sébastien Lahaie, and David M. Pennock. 2012. A Tractable Combinatorial Market Maker Using Constraint Generation. In EC-12.

[12]

Miroslav Dudík, Sébastien Lahaie, David M. Pennock, and David Rothschild. 2013. A Combinatorial Prediction Market for the U.S. Elections. In EC-13.

[13]

Marguerite Frank and Philip Wolfe. 1956. An algorithm for quadratic programming. Naval research logistics quarterly 3, 1--2 (1956).

[14]

Robin D. Hanson. 2003. Combinatorial information market design. Information Systems Frontiers 5, 1 (2003).

Digital Library

[15]

Robin D. Hanson. 2007. Logarithmic market scoring rules for modular combinatorial information aggregation. Journal of Prediction Markets 1, 1 (2007).

[16]

Martin Jaggi. 2013. Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In ICML-13.

[17]

Rahul G. Krishnan, Simon Lacoste-Julien, and David Sontag. 2015. Barrier Frank-Wolfe for marginal inference. In NIPS-15.

Digital Library

[18]

Yurii Nesterov. 2007. Gradient methods for minimizing composite objective function. Technical Report. UCL.

[19]

David M. Pennock, Steve Lawrence, C. Lee Giles, and Finn A. Nielsen. 2002. The real power of artificial markets. Science 291 (2002).

[20]

Martin Spann and Bernd Skiera. 2003. Internet-Based Virtual Stock Markets for Business Forecasting. Management Science 49, 10 (2003).

Digital Library

[21]

Pe11Lirong Xia and David M. Pennock. 2011. An Efficient Monte-Carlo Algorithm for Pricing Combinatorial Prediction Markets for Tournaments. In IJCAI-11.

Cited By

Wang XPennock DDevanur NRothschild DTao BWellman MBiró PChawla SEchenique F(2021)Designing a Combinatorial Financial Options MarketProceedings of the 22nd ACM Conference on Economics and Computation10.1145/3465456.3467634(864-883)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3465456.3467634

Index Terms

Arbitrage-Free Combinatorial Market Making via Integer Programming
1. Applied computing
  1. Law, social and behavioral sciences
    1. Economics
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design
      1. Computational pricing and auctions

Recommendations

Arbitrage Opportunities and Market-Making Traders in Prediction Markets
CECANDEEE '08: Proceedings of the 2008 10th IEEE Conference on E-Commerce Technology and the Fifth IEEE Conference on Enterprise Computing, E-Commerce and E-Services

Prediction markets are a promising approach for predicting uncertain future events and developments. These markets will work well if they are efficient and in efficient markets, one does not expect arbitrage opportunities to be persistent. This paper ...
Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem

In this paper, we consider problem (P) of minimizing a quadratic function q(x)=xtQx+ctx of binary variables. Our main idea is to use the recent Mixed Integer Quadratic Programming (MIQP) solvers. But, for this, we have to first convexify the objective ...
An efficient compact quadratic convex reformulation for general integer quadratic programs

We address the exact solution of general integer quadratic programs with linear constraints. These programs constitute a particular case of mixed-integer quadratic programs for which we introduce in Billionnet et al. (Math. Program., 2010) a general ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '16: Proceedings of the 2016 ACM Conference on Economics and Computation

July 2016

874 pages

ISBN:9781450339360

DOI:10.1145/2940716

General Chair:
Vincent Conitzer
Duke University, USA
,
Program Chairs:
Dirk Bergemann
Yale University, USA
,
Yiling Chen
Harvard University, USA

Copyright © 2016 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 the author(s) 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: 21 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EC '16

Sponsor:

SIGecom

EC '16: ACM Conference on Economics and Computation

July 24 - 28, 2016

Maastricht, The Netherlands

Acceptance Rates

EC '16 Paper Acceptance Rate 80 of 242 submissions, 33%;

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

1
Total Citations
View Citations
121
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)3

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang XPennock DDevanur NRothschild DTao BWellman MBiró PChawla SEchenique F(2021)Designing a Combinatorial Financial Options MarketProceedings of the 22nd ACM Conference on Economics and Computation10.1145/3465456.3467634(864-883)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3465456.3467634

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.

Media

Figures

Other

Tables

View Table of Contents