Chapter 30: Further Reading

Foundational Papers

1. Hanson, R. (2003). "Combinatorial Information Market Design." Information Systems Frontiers, 5(1), 107--119.

Robin Hanson's seminal paper introducing the Logarithmic Market Scoring Rule (LMSR) and its extension to combinatorial markets. This is the intellectual origin of the LMSR-C framework discussed throughout this chapter. Hanson shows how a cost-function-based market maker provides bounded loss while allowing traders to express beliefs about arbitrary Boolean combinations of events.

2. Chen, Y. & Pennock, D.M. (2007). "A Utility Framework for Bounded-Loss Market Makers." Proceedings of the 23rd Conference on Uncertainty in Artificial Intelligence (UAI).

Extends the LMSR framework to combinatorial markets and proves key properties including bounded loss and no-arbitrage. The paper demonstrates that LMSR cost functions naturally handle exponential state spaces when trades are restricted to structured Boolean expressions. Directly relevant to the factored representation and lazy evaluation techniques in Section 30.6.

3. Chen, Y., Fortnow, L., Lambert, N., Pennock, D.M., & Wortman, J. (2008). "Complexity of Combinatorial Market Makers." Proceedings of the 9th ACM Conference on Electronic Commerce (EC).

Establishes the computational complexity of operating combinatorial market makers. Shows that computing the cost of a trade in a fully general combinatorial market is #P-hard, motivating the approximation approaches described in Section 30.5. Also identifies tractable subclasses where efficient computation is possible.

Approximation Methods

4. Dudik, M., Lahaie, S., & Pennock, D.M. (2012). "A Tractable Combinatorial Market Maker Using Constraint Generation." Proceedings of the 13th ACM Conference on Electronic Commerce (EC).

Proposes a constraint generation approach to combinatorial market making that avoids explicit state enumeration. The method iteratively adds constraints corresponding to the most relevant states, achieving near-exact pricing with much less computation than full enumeration. A practical middle ground between the exact and approximate methods discussed in this chapter.

5. Abernethy, J., Chen, Y., & Vaughan, J.W. (2013). "Efficient Market Making via Convex Optimization, and a Connection to Online Learning." ACM Transactions on Economics and Computation, 1(2), Article 12.

Connects cost-function market makers to convex optimization and online learning. Shows that the LMSR is a special case of a broader family of convex potential market makers, and that operating such a market is equivalent to running a no-regret online learning algorithm. This connection provides new approximation algorithms for combinatorial markets based on efficient online learning techniques.

6. Koller, D. & Friedman, N. (2009). Probabilistic Graphical Models: Principles and Techniques. MIT Press.

The definitive reference for Bayesian networks, Markov random fields, belief propagation, and mean-field approximation -- all of which are used as approximation methods for combinatorial markets in Section 30.5. Chapters on inference algorithms are particularly relevant for understanding how belief propagation can be applied to market price computation.

Conditional Markets and Tokens

7. Gnosis. "Conditional Tokens Framework Specification." Available at: github.com/gnosis/conditional-tokens-contracts.

The technical specification for Gnosis's Conditional Token Framework (CTF) on Ethereum, discussed in Section 30.8.2. The documentation includes the token splitting and merging mechanics, AMM integration patterns, and examples of nested conditional structures. Essential reading for anyone implementing conditional markets on a blockchain.

8. Othman, A. & Sandholm, T. (2013). "Decision Rules and Decision Markets." Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS).

Analyzes the game-theoretic properties of conditional prediction markets used for decision-making. Establishes conditions under which conditional market prices correctly reflect causal effects of decisions, directly connecting the conditional market framework of this chapter to the decision markets of Chapter 31.

Real-World Implementations

9. Cowgill, B. & Zitzewitz, E. (2015). "Corporate Prediction Markets: Evidence from Google, Ford, and Firm X." Review of Economic Studies, 82(4), 1309--1341.

Documents how large corporations have used prediction markets, including some combinatorial and conditional structures, for internal forecasting. Provides empirical evidence on how market design choices affect accuracy in corporate settings. The discussion of correlation discovery through trading patterns is directly relevant to the sports parlay case study.

10. Berg, J.E., Neumann, G.R., & Rietz, T.A. (2009). "Searching for Google's Value: Using Prediction Markets to Forecast Market Capitalization Prior to an Initial Public Offering." Management Science, 55(3), 348--361.

A real-world application of prediction markets that implicitly involves combinatorial reasoning: predicting a company's value requires combining beliefs about multiple uncertain factors. The paper illustrates how market participants aggregate diverse information even without an explicit combinatorial market structure.

Causal Inference

11. Pearl, J. (2009). Causality: Models, Reasoning, and Inference (2nd ed.). Cambridge University Press.

The foundational reference for causal inference, including the do-calculus used in Section 30.11. Pearl's framework for distinguishing observational (conditional) from interventional (causal) probabilities is essential for understanding the limitations and potential of combinatorial markets for causal reasoning.

12. Dimitrov, S. & Sami, R. (2008). "Non-myopic Strategies in Prediction Markets." Proceedings of the 9th ACM Conference on Electronic Commerce (EC).

Connects combinatorial market structures to Bayesian inference. Shows that certain market structures are equivalent to running belief propagation on graphical models, providing a deep theoretical connection between the approximation methods (Section 30.5) and the market mechanism itself.

Computational Aspects

13. Chen, Y., Goel, S., & Pennock, D.M. (2008). "Pricing Combinatorial Markets for Tournaments." Proceedings of the 40th ACM Symposium on Theory of Computing (STOC).

Addresses combinatorial markets for ranking outcomes (permutation markets), where the state space is $n!$ rather than $2^n$. Proposes efficient pricing algorithms for specific tournament structures. Relevant for sports and competition prediction markets where ordering matters.

14. Xia, L. & Pennock, D.M. (2011). "An Efficient Monte Carlo Method for Optimal Portfolio in a Combinatorial Prediction Market." Proceedings of the AAAI Conference on Artificial Intelligence.

Develops Monte Carlo methods specifically tailored for portfolio optimization in combinatorial markets. The sampling techniques described are more sophisticated than the basic importance sampling in Section 30.5.1 and provide better variance reduction for rare event pricing.

15. Kroer, C. & Sandholm, T. (2016). "Sequential Equilibrium Computation for Extensive-Form Games with Imperfect Information." Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI).

While focused on game theory, this paper's techniques for handling large state spaces in sequential games are directly applicable to combinatorial market computation. The iterative methods developed here can be adapted for efficient combinatorial market pricing when the state space has sequential structure.