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

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.