Betting Boolean-style: A framework for trading in securities based on logical formulas

Lance Fortnow, Joe Kilian, David M. Pennock, Michael P. Wellman

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


We develop a framework for trading in compound securities: financial instruments that pay off contingent on the outcomes of arbitrary statements in propositional logic. Buying or selling securities - which can be thought of as betting on or against a particular future outcome - allows agents both to hedge risk and to profit (in expectation) on subjective predictions. A compound securities market allows agents to place bets on arbitrary Boolean combinations of events, enabling them to more closely achieve their optimal risk exposure, and enabling the market as a whole to more closely achieve the social optimum. The tradeoff for allowing such expressivity is in the complexity of the agents' and auctioneer's optimization problems. We develop and motivate the concept of a compound securities market, presenting the framework through a series of formal definitions and examples. We then analyze in detail the auctioneer's matching problem. We show that, with n events, the matching problem is worst-case intractable: specifically, the problem is co-NP-complete in the divisible case and ?2p -complete in the indivisible case. We show that the latter hardness result holds even under severe language restrictions on bids. With log n events, the problem is tractable (polynomial) in the divisible case and worst-case intractable (NP-complete) in the indivisible case. We briefly discuss matching algorithms and tractable special cases.

Original languageEnglish (US)
Pages (from-to)87-104
Number of pages18
JournalDecision Support Systems
Issue number1
StatePublished - Mar 2005
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Management Information Systems
  • Information Systems
  • Developmental and Educational Psychology
  • Arts and Humanities (miscellaneous)
  • Information Systems and Management


  • Betting
  • Combinatorial betting
  • Compound securities markets
  • Computational complexity of matching
  • Hedging
  • Information aggregation
  • Risk allocation
  • Speculating
  • Trading in financial instruments based on logical formulas


Dive into the research topics of 'Betting Boolean-style: A framework for trading in securities based on logical formulas'. Together they form a unique fingerprint.

Cite this