Pricing combinatorial markets for tournaments

ABSTRACT

In a prediction market, agents trade assets whose value is tied to a future event, for example the outcome of the next presidential election. Asset prices determine a probability distribution over the set of possible outcomes. Typically, the outcome space is small, allowing agents to directly trade in each outcome, and allowing a market maker to explicitly update asset prices. Combinatorial markets, in contrast, work to estimate a full joint distribution of dependent observations, in which case the outcome space grows exponentially. In this paper, we consider the problem of pricing combinatorial markets for single-elimination tournaments. With $n$ competing teams, the outcome space is of size 2^n-1. We show that the general pricing problem for tournaments is P-hard. We derive a polynomial-time algorithm for a restricted betting language based on a Bayesian network representation of the probability distribution. The language is fairly natural in the context of tournaments, allowing for example bets of the form "team i wins game k". We believe that our betting language is the first for combinatorial market makers that is both useful and tractable. We briefly discuss a heuristic approximation technique for the general case.

REFERENCES

• 1: J. E. Berg, R. Forsythe, F. D. Nelson, and T. A. Rietz. Results from a dozen years of election futures markets research. In C. A. Plott and V. Smith, editors, Handbook of Experimental Economic Results (forthcoming). 2001.
• 2: Y. Chen, L. Fortnow, N. Lambert, D. M. Pennock, and J. Wortman. Complexity of combinatorial market makers. Unpublished manuscript, arXiv:0802.1362v1 {cs.GT}.
• 3: 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]
• 4: R. Forsythe, T. A. Rietz, and T. W. Ross. Wishes, expectations, and actions: A survey on price formation in election stock markets. Journal of Economic Behavior and Organization, 39:83--110, 1999.
• 5: 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]
• 6: C. Genest and C. G. Wagner. Further evidence against independence preservation in expert judgement synthesis. Aequationes Mathematicae, 32(1):74--86, 1987.
• 7: Robin Hanson, Combinatorial Information Market Design, Information Systems Frontiers, v.5 n.1, p.107-119, January 2003 [doi>10.1023/A:1022058209073]
• 8: R. D. Hanson. Logarithmic market scoring rules for modular combinatorial information aggregation. Journal of Prediction Markets, 1(1):1--15, 2007.
• 9: A. Marshall. The use of multi-stage sampling schemes in monte carlo computations. In M. Meyer, editor, Symposium on Monte Carlo Methods, pages 123--140. Wiley, New York, 1956.
• 10: P. Milgrom and N. L. Stokey. Information, trade and common knowledge. Journal of Economic Theory, 26(1):17--27, 1982.
• 11: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 12: D. M. Pennock, S. Lawrence, C. L. Giles, and F. A. Nielsen. The real power of artificial markets. Science, 291:987--988, February 2002.
• 13: David M. Pennock , Michael P. Wellman, Graphical Models for Groups: Belief Aggregation and Risk Sharing, Decision Analysis, v.2 n.3, p.148-164, September 2005 [doi>10.1287/deca.1050.0048]
• 14: C. R. Plott and S. Sunder. Efficiency of experimental security markets with insider information: An application of rational expectations models. Journal of Political Economy, 90:663--98, 1982.
• 15: C. R. Plott and S. Sunder. Rational expectations and the aggregation of diverse information in laboratory security markets. Econometrica, 56:1085--1118, 1988.
• 16: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 17: L. G. Valiant. The complexity of enumeration and reliability problems. SIAM J. Comput., 8(3):410--421, 1979.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Economics

Keywords:
bayesian networks, combinatorial markets, logarithmic market scoring rule, prediction markets, tournaments