Combinatorial betting

ABSTRACT

We discuss the design of combinatorial betting mechanisms. We characterize the computational complexity of several variants of the problem and pose some open research questions.

REFERENCES

• 1: 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]
• 2: 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]
• 3: Robin Hanson, Combinatorial Information Market Design, Information Systems Frontiers, v.5 n.1, p.107-119, January 2003 [doi>10.1023/A:1022058209073]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems
          Subjects: Decision support (e.g., MIS)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms; Permutations and combinations

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.0 General
          Subjects: Economics

General Terms:
Algorithms, Design, Economics

Keywords:
computational complexity, expressive betting, mechanism design, order matching, prediction markets