Betting Boolean-Style: A Framework for Trading in  Securities Based on Logical Formulas  Lance Fortnow  Joe Kilian  NEC Laboratories America  4 Independence Way  Princeton, NJ 08540  David M. Pennock  ∗  Overture Services, Inc., 3rd floor  74 N. Pasadena Ave  Pasadena, CA 91103  Michael P. Wellman  University of Michigan  AI Laboratory  1101 Beal Avenue  Ann Arbor, MI 48109  ABSTRACT  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 co-NP-complete in the  divisible case and Σp  2-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 polynomial in the divisible case and NP-complete in  the indivisible case. We briefly discuss matching algorithms  and tractable special cases.  Categories and Subject Descriptors  F.2.2 [Theory of Computation]: Analysis of Algorithms  and Problem Complexity-Nonnumerical Algorithms and  Problems; J.4 [Computer Applications]: Social and   Behavioral Sciences-Economics    1. INTRODUCTION  Securities markets effectively allow traders to place bets  on the outcomes of uncertain future propositions. Examples  include stock markets like NASDAQ, options markets like  CBOE [17], futures markets like CME [30], other derivatives  markets, insurance markets, political stock markets [11, 12],  sports betting markets [7, 13, 32], horse racing markets [33],  idea futures markets [16], decision markets [14] and even  market games [4, 24, 25]. The economic value of securities  markets is two-fold. First, they allow traders to hedge risk,  or to insure against undesirable outcomes. For example, the  owner of a stock might buy a put option (the right to sell  the stock at a particular price) in order to insure against  a stock downturn. Or the owner of a house may purchase  an insurance contract to hedge against unforeseen damage  to the house. Second, securities markets allow traders to  speculate, or to obtain a subjective expected profit when  market prices do not reflect their assessment of the   likelihood of future outcomes. For example, a trader might buy  a call option if he believes that the likelihood is high that  the price of the underlying stock will go up, regardless of  risk exposure to changes in the stock price. Because traders  stand to earn a profit if they can make effective   probability assessments, often prices in financial markets yield very  accurate aggregate forecasts of future events [10, 29, 27, 28].  Real securities markets have complex payoff structures  with various triggers. However, these can all be modeled  as collections of more basic or atomic Arrow-Debreu   securities [1, 8, 20]. One unit of one Arrow-Debreu security pays  off one dollar if and only if (iff) a corresponding binary event  occurs; it pays nothing if the event does not occur. So, for  example, one unit of a security denoted Acme100 might  pay $1 iff Acme"s stock is above $100 on January 4, 2004.  An Acme stock option as it would be defined on a   finan144  cial exchange can be though of as a portfolio of such atomic  securities.1  In this paper, we develop and analyze a framework for  trading in compound securities markets with payoffs   contingent on arbitrary logical combinations of events, including  conditionals. For example, given binary events A, B, and  C, one trader might bid to buy three units of a security   denoted A ∧ ¯B ∨ C that pays off $1 iff the compound event  A ∧ ¯B ∨ C occurs for thirty cents each. Another trader may  bid to sell six units of a security A|C that pays off $1 iff  A occurs for fifty-five cents each, conditional on event C   occurring, meaning that the transaction is revoked if C does  not occur (i.e., no payoff is given and the price of the   security is refunded) [5]. Bids may also be divisible, meaning  that bidders are willing to accept less than the requested  quantity, or indivisible, meaning that bids must be fulfilled  either completely or not at all. Given a set of such bids,  the auctioneer faces a complex matching problem to decide  which bids are accepted for how many units at what price.  Typically, the auctioneer seeks to take on no risk of its own,  only matching up agreeable trades among the bidders, but  we also consider alternative formulations where the   auctioneer acts as a market maker willing to accept some risk.  We examine the computational complexity of the   auctioneer"s matching problem. Let the length of the description  of all the available securities be O(n). With n events, the  matching problem is co-NP-complete in the divisible case  and Σp  2-complete in the indivisible case. This Σp  2-complete  hardness holds even when the bidding language is   significantly restricted. With log n events, the problem is   polynomial in the divisible case and NP-complete in the indivisible  case.  Section 2 presents some necessary background   information, motivation, and related work. Section 3 formally   describes our framework for compound securities, and defines  the auctioneer"s matching problem. Section 4 briefly   discusses natural algorithms for solving the matching problem.  Section 5 proves our central computational complexity   results. Section 6 discusses the possibility of tractable special  cases. Section 7 concludes with a summary and some ideas  of future directions.  2. PRELIMINARIES  2.1 Background and notation  Imagine a world where there are only two future uncertain  events of any consequence: (1) the event that one"s house is  struck by lightning by December 31, 2003, denoted struck,  and (2) the event that Acme"s stock price goes above $100  by January 4, 2004, denoted acme100. In this simple world  there are four possible future states-all possible   combinations of the binary events" outcomes:  struck ∧ acme100,  struck ∧ acme100,  struck ∧ acme100,  struck ∧ acme100.  Hedging risk can be thought of as an action of moving money  between various possible future states. For example,   insur1  Technically, an option is a portfolio of infinitely many  atomic securities, though it can be approximately modeled  with a finite number.  ing one"s house transfers money from future states where  struck is not true to states where it is. Selling a security  denoted acme100 -that pays off $1 iff the event acme100  occurs-transfers money from future states where Acme"s  price is above $100 on January 4 to states where it"s not.  Speculating is also an act of transferring money between  future states, though usually associated with maximizing  expected return rather than reducing risk. For example,  betting on a football team moves money from the team  loses state to the team wins state. In practice, agents  engage in a mixture of hedging and speculating, and there  is no clear dividing line between the two [18].  All possible future outcomes form a state space Ω,   consisting of mutually exclusive and exhaustive states ω ∈ Ω.  Often a more natural way to think of possible future   outcomes is as an event space A of linearly independent events  A ∈ A that may overlap arbitrarily. So in our toy example  struck ∧ acme100 is one of the four disjoint states, while  struck is one of the two events. Note that a set of n   linearly independent events defines a state space Ω of size 2n  consisting of all possible combinations of event outcomes.  Conversely, any state space Ω can be factored into log |Ω|  events.  Suppose that A exhaustively covers all meaningful future  outcomes (i.e., covers all eventualities that agents may wish  to hedge against and/or speculate upon). Then the   existence of 2n  linearly independent securities-called a   complete market-allows agents to distribute their wealth   arbitrarily across future states.2  An agent may create any hedge  or speculation it desires. Under classical conditions, agents  trading in a complete market form an equilibrium where risk  is allocated Pareto optimally. If the market is incomplete,  meaning it consists of fewer than 2n  linearly independent  securities, then in general agents cannot construct arbitrary  hedges and equilibrium allocations may be nonoptimal [1,  8, 19, 20].  In real-world settings, the number of meaningful events n  is large and thus the number of securities required for   completeness is intractable. No truly complete market exists or  will ever exist. One motivation behind compound securities  markets is to provide a mechanism that supports the most  transfer of risk using the least number of transactions   possible. Compound securities allow a high degree of expressivity  in constructing bids. The tradeoff for increased expressivity  is increased computational complexity, from both the   bidder"s and auctioneer"s point of view.  2.2 Related work  The quest to reduce the number of financial instruments  required to support an optimal allocation of risk dates to  Arrow"s original work [1]. The requirement stated above of  only 2n  linearly-independent securities is itself a reduction  from the most straightforward formulation. In an economy  with k standard goods, the most straightforward complete  market contains k·2n  securities, each paying off in one good  under one state realization. Arrow [1] showed that a market  where securities and goods are essentially separated, with  2n  securities paying off in a single numeraire good plus k  spot markets in the standard goods, is also complete. For  our purposes, we need consider only the securities market.  2  By linearly independent securities, we mean that the   vectors of payoffs in all future states of these securities are   linearly independent.  145  Varian [34] shows that a complete market can be   constructed using fewer than 2n  securities, replacing the   missing securities with options. Still, the number of linearly   independent financial instruments-securities plus   optionsmust be 2n  to guarantee completeness.  Though the requirement of 2n  financial instruments   cannot be relaxed if one wants to guarantee completeness in  all circumstances, Pennock and Wellman [26] explore   conditions under which a smaller securities market may be   operationally complete, meaning that its equilibrium is Pareto   optimal with respect to the agents involved, even if the market  contains less than 2n  securities. The authors show that in  some cases the market can be structured and compacted  in analogy to Bayesian network representations of joint   probability distributions [23]. They show that, if all agents"  risk-neutral independencies agree with the independencies  encoded in the market structure, then the market is   operationally complete. For collections of agents all with constant  absolute risk aversion, agreement on Markov independencies  is sufficient.  Bossaerts, Fine, and Ledyard [2] develop a mechanism  they call combined-value trading (CVT) that allows traders  to order an arbitrary portfolio of securities in one bid, rather  than breaking up the order into a sequence of bids on   individual securities. If the portfolio order is accepted, all of  the implied trades on individual securities are executed   simultaneously, thus eliminating so-called execution risk that  prices will change in the middle of a planned sequence of   orders. The authors conduct laboratory experiments showing  that, even in thin markets where ordinary sequential   trading breaks down, CVT supports efficient pricing and   allocation. Note that CVT differs significantly from compound  securities trading. CVT allows instantaneous trading of any  linear combination of securities, while compound securities  allow more expressive securities that can encode nonlinear  boolean combinations of events. For example, CVT may   allow an agent to order securities A and B in a bundle that  pays off as a linear combination of A and B,3  but CVT won"t  allow the construction of a compound security A ∧ B that  pays off $1 iff both A and B occur, or a compound security  A|B .  Related to CVT are combinatorial auctions [6, 21] and   exchanges [31], mechanisms that have recently received quite  a bit of attention in the economics and computer science   literatures. Combinatorial auctions allow bidders to place   distinct values on all possible bundles of goods rather than just  on individual goods. In this way bidders can express   substitutability and complementarity relationships among goods  that cannot be expressed in standard parallel or sequential  auctions. Compound securities differ from combinatorial  auctions in concept and complexity. Compound securities  allow bidders to construct an arbitrary bet on any of the 22n  possible compound events expressible as logical functions of  the n base events, conditional on any other of the 22n    compound events. Agents optimize based on their own   subjective probabilities and risk attitude (and in general, their   beliefs about other agents" beliefs and utilities, ad infinitum).  The central auctioneer problem is identifying arbitrage   opportunities: that is, to match bets together without taking  on any risk. Combinatorial auctions, on the other hand,   allow bids on any of the 2n  bundles of n goods. Typically,  3  Specifically, one unit of each pays off $2 iff both A and B  occur, $1 iff A or B occurs (but not both), and $0 otherwise.  uncertainty-and thus risk-is not considered. The central  auctioneer problem is to maximize social welfare. Also note  that the problems lie in different complexity classes. While  clearing a combinatorial auction is polynomial in the   divisible case and NP-complete in the indivisible case, matching  in a compound securities market is NP-complete in the   divisible case and Σp  2-complete in the indivisible case. In fact,  even the problem of deciding whether two bids on compound  securities match, even in the divisible case, is NP-complete  (see Section 5.2).  There is a sense in which it is possible to translate our  matching problem for compound securities into an   analogous problem for clearing two-sided combinatorial exchanges  [31] of exponential size. Specifically, if we regard payoff in a  particular state as a good, then compound securities can be  viewed as bundles of (fractional quantities of) such goods.  The material balance constraint facing the combinatorial  auctioneer corresponds to a restriction that the   compoundsecurity auctioneer be disallowed from assuming any risk.  Note that this translation is not at all useful for addressing  the compound-security matching problem, as the resulting  combinatorial exchange has an exponential number of goods.  Hanson [15] develops a market mechanism called a market  scoring rule that is especially well suited for allowing bets  on a combinatorial number of outcomes. The mechanism  maintains a joint probability distribution over all 2n  states,  either explicitly or implicitly using a Bayesian network or  other compact representation. At any time any trader who  believes the probabilities are wrong can change any part  of the distribution by accepting a lottery ticket that pays  off according to a scoring rule (e.g., the logarithmic   scoring rule) [35], as long as that trader also agrees to pay off  the most recent person to change the distribution. In the  limit of a single trader, the mechanism behaves like a   scoring rule, suitable for polling a single agent for its   probability distribution. In the limit of many traders, it produces a  combined estimate. Since the market essentially always has  a complete set of posted prices for all possible outcomes,  the mechanism avoids the problem of thin markets, or   illiquidity, that necessarily plagues any market containing an  exponential number of alternative investments. The   mechanism requires a patron to pay off the final person to change  the distribution, though the patron"s payment is bounded.  Though Hanson offers some initial suggestions, several open  problems remain, including efficient methods for   representing and updating the joint distribution and recording traders  positions and portfolios, without resorting to exponential  time and space algorithms.  Fagin, Halpern, and Megiddo [9] give a sound and   complete axiomatization for deciding whether sets of   probabilistic inequalities are consistent. Bids for compound securities  can be thought of as expressions of probabilistic   inequalities: for example, a bid to buy A ∧ B at price 0.3 is a  statement that the probability of A ∧ B is greater than 0.3.  If a set of single-unit bids correspond to a set of inconsistent  probabilistic inequalities, then there is a match. However,  because they are interested in a much different framework,  Fagin et al. do not consider several complicating factors   specific to the securities market framework: namely, handling  multi-unit or fractional bid quantities, identifying matches,  choosing among multiple matches, and optimizing based on  probabilities and risk attitudes. We address these issues   below.  146  3. FRAMEWORK FOR TRADING IN   COMPOUND SECURITIES  3.1 High-level description  Common knowledge among agents is the set of events A.  There are no predefined securities. Instead, agents offer to  buy or sell securities of their own design that pay off   contingent on logical combinations of events and event negations.  Combination operators may include conjunctions,   disjunctions, and conditionals.  For all practical purposes, it is impossible for agents to  trade in enough securities (2n  ) to form a complete market,  so agents must devise their best tradeoff between the   number and complexity of their bids, and the extent to which  their risks are hedged and desirable bets are placed. In its  most general form, the problem is game-theoretic in nature,  since what an agent should offer depends on what it believes  other agents will accept. At the other end of the spectrum, a  simplified version of the problem is to optimize bids only on  currently available securities at current prices. In between  these two formulations are other possible interesting   optimization problems. Approximation algorithms might also  be pursued.  The auctioneer faces a nontrivial problem of matching buy  and sell orders to maximize surplus (the cash and securities  left over after accepted bids are fulfilled). For example, offers  to sell A1A2 at $0.2 and A1  ¯A2 at $0.1 can match with an  offer to buy A1 at $0.4, with surplus $0.1. Or an offer to  sell A1 at $0.3 can match with an offer to buy A1A2 at  $0.4, with surplus $0.1 in cash and A1  ¯A2 in securities. In  general, a single security might qualify for multiple matches,  but only one can be transacted. So the auctioneer must find  the optimal set of matches that maximizes surplus, which  could be measured in a number of ways. Again,   approximation algorithms might be considered. In another   formulation, the auctioneer functions as a market maker willing to  take on a certain amount of risk.  Informally, our motivation is to provide a mechanism that  allows a very high degree of expressivity in placing hedges  and bets, and is also capable of approximating the optimal  (complete-market) allocation of risk, trading off the number  and complexity of securities and transactions needed.  3.2 Formal description  3.2.1 Securities  We use φ and ψ to denote arbitrary boolean formulas, or  logical combinations of events in A. We denote securities  φ|ψ . Securities pay off $1 if and only if (iff) φ and ψ are  true, pay off $0 iff φ is false and ψ is true, and are canceled  (i.e., any price paid is refunded) iff ψ is false. We define  T ≡ Ω to be the event true and F ≡ ∅ to be the event  false. We abbreviate φ|T as φ .  3.2.2 Orders  Agents place orders, denoted o, of the form q units of  φ|ψ at price p per unit, where q > 0 implies a buy  order and q < 0 implies a sell order. We assume agents  submitting buy (sell) orders will accept any price p∗  ≤ p  (p∗  ≥ p). We distinguish between divisible and indivisible  orders. Agents submitting divisible orders will accept any  quantity αq where 0 < α ≤ 1. Agents submitting   indivisible orders will accept only exactly q units, or none at all.  We believe that, given the nature of what is being traded  (state-contingent dollars), most agents will be content to  trade using divisible orders.  Every order o can be translated into a payoff vector Υ  across all states ω ∈ Ω. The payoff Υ ω  in state ω is q ·  1ω∈ψ(1ω∈φ − p), where 1ω∈E equals 1 iff ω ∈ E and zero  otherwise. Recall that the 2n  states correspond to the 2n  possible combinations of event outcomes. We index multiple  orders with subscripts (e.g., oi and Υi). Let the set of all  orders be O and the set of all corresponding payoff vectors  be P.  Example 1. (Translating orders into payoff vectors)   Suppose that |A| = 3. Consider an order to buy two units of  A2 ∨ A3|A1 at price $0.8. The corresponding payoff vector  is:  Υ = Υ A1A2A3  , Υ A1A2  ¯A3  , Υ A1  ¯A2A3  , . . . , Υ  ¯A1  ¯A2  ¯A3  = 2 · 0.2, 0.2, 0.2, −0.8, 0, 0, 0, 0  2  3.2.3 The matching problem  The auctioneer"s task, called the matching problem, is to  determine which orders to accept among all orders o ∈ O.  Let αi be the fraction of order oi accepted by the auctioneer  (in the indivisible case, αi must be either 0 or 1; in the  divisible case, αi can range from 0 to 1). If αi = 0, then  order oi is considered rejected and no transactions take place  concerning this order. For accepted orders (αi > 0), the  auctioneer receives the money lost by bidders and pays out  the money won by bidders, so the auctioneer"s payoff vector  is:  Υauc =  X  Υi∈P  −αiΥi.  We also call the auctioneer"s payoff vector the surplus vector,  since it is the (possibly state-contingent) money left over  after all accepted orders are filled.  Assume that the auctioneer wants to choose a set of orders  so that it is guaranteed not to lose any money in any future  state, but that the auctioneer does not necessarily insist on  obtaining a positive benefit from the transaction (i.e., the  auctioneer is content to break even).  Definition 1. (Matching problem, indivisible case) Given  a set of orders O, does there exist αi ∈ {0, 1} with at least  one αi = 1 such that  ∀ω, Υ ω  auc ≥ 0?  In other words, does there exist a nonempty subset of orders  that the auctioneer can accept without risk? 2  If ∀ω, Υ  ω  auc = c where c is nonnegative, then the surplus  leftover after processing this match is c dollars. Let m =  minω[Υ  ω  auc]. In general, processing a match leaves m dollars  in cash and Υ  ω  auc − m in state-contingent dollars, which can  then be translated into securities.  Example 2. (Indivisible order matching) Suppose |A| =  2. Consider an order to buy one unit of A1A2 at price  0.4 and an order to sell one unit of A1 at price 0.3. The  147  corresponding payoff vectors are:  Υ1 = Υ  A1A2  1 ,Υ  A1  ¯A2  1 ,Υ  ¯A1A2  1 ,Υ  ¯A1  ¯A2  1  = 0.6, −0.4, −0.4, −0.4  Υ2 = −0.7, −0.7, 0.3, 0.3  The auctioneer"s payoff vector (the negative of the   componentwise sum of the above two vectors) is:  Υauc = −Υ1 − Υ2 = 0.1, 1.1, 0.1, 0.1 .  Since all components are nonnegative, the two orders match.  The auctioneer can process both orders, leaving a surplus of  $0.1 in cash and one unit of A1  ¯A2 in securities. 2  Now consider the divisible case, where order can be   partially filled.  Definition 2. (Matching problem, divisible case) Given  a set of orders O, does there exist αi ∈ [0, 1] with at least  one αi > 0 such that  ∀ω, Υ ω  auc ≥ 0,  2  Example 3. (Divisible order matching) Suppose |A| = 2.  Consider an order to sell one unit of A1 at price $0.5, an  order to buy one unit of A1A2|A1 ∨ A2 at price $0.5, and  an order to buy one unit of A1| ¯A2 at price $0.4. The  corresponding payoff vectors are:  Υ1 = Υ  A1A2  1 ,Υ  A1  ¯A2  1 ,Υ  ¯A1A2  1 ,Υ  ¯A1  ¯A2  1  = −0.5, −0.5, 0.5, 0.5  Υ2 = 0.5, −0.5, −0.5, 0  Υ3 = 0, 0.6, 0, −0.4  It is clear by inspection that no non-empty subset of whole  orders constitutes a match: in all cases where αi ∈ {0, 1}  (other than all αi = 0), at least one state sums to a positive  amount (negative for the auctioneer). However, if α1 =  α2 = 3/5 and α3 = 1, then the auctioneer"s payoff vector is:  Υauc = −  3  5  Υ1 −  3  5  Υ2 − Υ3 = 0, 0, 0, 0.1 ,  constituting a match. The auctioneer can process 3/5 of the  first and second orders, and all of the third order, leaving a  surplus of 0.1 units of ¯A1  ¯A2 . In this example, a divisible  match exists even though an indivisible match is not possible;  we examine the distinction in detail in Section 5, where we  separate the two matching problems into distinct complexity  classes. 2  The matching problems defined above are decision   problems: the task is only to show the existence or nonexistence  of a match. However, there may be multiple matches from  which the auctioneer can choose. Sometimes the choices are  equivalent from the auctioneer"s perspective; alternatively,  an objective function can be used to find an optimal match  according to that objective.  Example 4. (Auctioneer alternatives I) Suppose |A| =  2. Consider an order to sell one unit of A1 at price $0.7,  an order to sell one unit of A2 at price $0.7, an order to  buy one unit of A1A2 at price $0.4, an order to buy one  unit of A1  ¯A2 at price $0.4, and an order to buy one unit  of ¯A1A2 at price $0.4. The corresponding payoff vectors  are:  Υ1 = −0.3,−0.3, 0.7, 0.7  Υ2 = −0.3, 0.7,−0.3, 0.7  Υ3 = 0.6,−0.4,−0.4,−0.4  Υ4 = −0.4, 0.6,−0.4,−0.4  Υ5 = −0.4,−0.4, 0.6,−0.4  Consider the indivisible case. The auctioneer could choose  to accept bids 1, 3, and 4 together, or the auctioneer could  choose to accept bids 2, 3, and 5 together. Both constitute  matches, and in fact both yield identical payoffs (Υauc =  0.1, 0.1, 0.1, 0.1 , or $0.1 in cash) for the auctioneer. 2  Example 5. (Auctioneer alternatives II) Suppose |A| =  2. Consider an order to sell two units of A1 at price $0.6,  an order to buy one unit of A1A2 at price $0.3, and an  order to buy one unit of A1  ¯A2 at price $0.5. The   corresponding payoff vectors are:  Υ1 = −0.4,−0.4, 0.6, 0.6  Υ2 = 0.7,−0.3,−0.3,−0.3  Υ3 = −0.5, 0.5,−0.5,−0.5  Consider the divisible case. The auctioneer could choose to  accept one unit each of all three bids, yielding a payoff to  the auctioneer of $0.2 in cash (Υauc = 0.2, 0.2, 0.2, 0.2 ).  Alternatively, the auctioneer could choose to accept 4/3 units  of bid 1, and one unit each of bids 2 and 3, yielding a payoff  to the auctioneer of 1/3 units of security A1 . Both choices  constitute matches (in fact, accepting any number of units  of bid 1 between 1 and 4/3 can be part of a match), though  depending on the auctioneer"s objective, one choice might  be preferred over another. For example, if the auctioneer  believes that A1 is very likely to occur, it may prefer to accept  4/3 units of bid 1. 2  There are many possible criteria for the auctioneer to   decide among matches, all of which seem reasonable in some  circumstances. One natural quantity to maximize is the  volume of trade among bidders; another is the auctioneer"s  utility, either with or without the arbitrage constraint.  Definition 3. (Trade maximization problem) Given a set  of indivisible (divisible) orders O, choose αi ∈ {0, 1} (αi ∈  [0, 1]) to maximize  X  i  αiqi,  under the constraint that  ∀ω, Υ ω  auc ≥ 0.  2  Another reasonable variation is to maximize the total   percent of orders filled, or  P  i αi, under the same (risk-free)  constraint that ∀ω, Υ  ω  auc ≥ 0.  Definition 4. (Auctioneer risk-free utility-maximization  problem) Let the auctioneer"s subjective probability for each  state ω be Pr(ω), and let the auctioneer"s utility for y   dollars be u(y). Given a set of indivisible (divisible) orders O,  choose αi ∈ {0, 1} (αi ∈ [0, 1]) to maximize  X  ω∈Ω  Pr(ω)u(Υ ω  auc),  148  under the constraint that  ∀ω, Υ ω  auc ≥ 0.  2  Definition 5. (Auctioneer standard utility-maximization  problem) Let the auctioneer"s subjective probability for each  state ω be Pr(ω), and let the auctioneer"s utility for y   dollars be u(y). Given a set of indivisible (divisible) orders O,  choose αi ∈ {0, 1} (αi ∈ [0, 1]) to maximize  X  ω∈Ω  Pr(ω)u    Υ ω  auc    .  2  This last objective function drops the risk-free (arbitrage)  constraint. In this case, the auctioneer is a market maker  with beliefs about the likelihood of outcomes, and the   auctioneer may actually lose money is some outcomes.  Still other variations and other optimization criteria seem  reasonable, including social welfare, etc. It also seems   reasonable to suppose that the surplus be shared among bidders  and the auctioneer, rather than retained solely by the   auctioneer. This is analogous to choosing a common transaction  price in a double auction (e.g., the midpoint between the bid  and ask prices), rather than the buyer paying the bid price  and the seller receiving the ask price, with the difference  going to the auctioneer. The problem becomes more   complicated when dividing surplus securities, in part because  they are valued differently by different agents. Formulating  reasonable sharing rules and examining the resulting   incentive properties seems a rich and promising avenue for further  investigation.  4. MATCHING ALGORITHMS  The straightforward algorithm for solving the divisible  matching problem is linear programming; we set up an   appropriate linear program in Section 5.1. The straightforward  algorithm for solving the indivisible matching problem is   integer programming. With n events, to set up the   appropriate linear or integer programs, simply writing out the payoff  vectors in the straightforward way requires O(2n  ) space.  There is some hope that specialized algorithms that   exploit structure among bids can perform better in terms of  average-case time and space complexity. For example, in  some cases matches can be identified using logical reduction  techniques, without writing down the full payoff vectors. So  a match between the following bids:  • sell 1 of A1A2 at $0.2  • sell 1 of A1  ¯A2 at $0.1  • buy 1 of A1 at $0.4  can be identified by reducing the first two bids to an   equivalent offer to sell A1 at $0.3 that clearly matches with  the third bid. Formalizing a logical-reduction algorithm for  matching, or other algorithms that can exploit special   structure among the bids, is a promising avenue for future work.  5. THE COMPUTATIONAL COMPLEXITY  OF MATCHING  In this section we examine the computational complexity  of the auctioneer"s matching problem. Here n refers to the  problem"s input size that includes descriptions of all of the  buy and sell orders. We also assume that n bounds the  number of base securities.  We consider four cases based on two parameters:  1. Whether to allow divisible or indivisible orders.  2. The number of securities. We consider two   possibilities:  (a) O(log n) base securities yielding a polynomial   number of states.  (b) An unlimited number of base securities yielding  an exponential number of states.  We show the following results.  Theorem 1. The matching problem is  1. computable in polynomial-time for O(log n) base   securities with divisible orders.  2. co-NP-complete for unlimited securities with divisible  orders.  3. NP-complete for O(log n) base securities with   indivisible orders.  4. Σp  2-complete for unlimited securities with indivisible  orders.  5.1 Small number of securities with divisible  orders  We can build a linear program based on Definition 2. We  have variables αi. For each i, we have  0 ≤ αi ≤ 1  and for each state ω in Ω we have the constraint  Υ ω  auc =  X  i  −αiΥ  ω  i ≥ 0.  Given these constraints we maximize  X  i  αi.  A set of orders has a matching exactly when  P  i αi > 0.  With O(log n) base securities, we have |Ω| bounded by a  polynomial so we can solve this linear program in polynomial  time.  Note that one might argue that one should maximize some  linear combination of the −Υ  ω  i s to maximize the surplus.  However this approach will not find matchings that have  zero surplus.  5.2 Large number of securities with divisible  orders  With unlimited base securities, the linear program given  in Section 5.1 has an exponential number of constraint   equations. Each constraint is short to describe and easily   computable given ω.  149  Let m ≤ n be the total number of buy and sell orders.  By the theory of linear programming, an upper bound on  the objective function can be forced by a collection of m + 1  constraints. So if no matching exists there must exist m + 1  constraints that force all the αi to zero. In nondeterministic  polynomial-time we can guess these constraints and solve  the reduced linear program. This shows that matching is in  co-NP.  To show co-NP-completeness we reduce the NP-complete  problem of Boolean formula satisfiability to the nonexistence  of a matching. Fix a formula φ. Let the base securities be  the variables of φ and consider the single security φ with  a buy order of 0.5. If the formula φ is satisfiable then there  is some state with payoff 0.5 and no fractional unit of the  security φ is a matching. If the formula φ is not satisfiable  then every state has an auctioneer"s payoff of 0.5 and a single  unit of the security φ is a matching.  One could argue that if the formula φ is not satisfiable  then no fully rational buyer would want to buy φ for a cost  of 0.5. We can get around this problem by adding auxiliary  base securities, A and B, and defining two securities  τ = (φ ∧ A) ∨ (A ∧ B)  τ = (φ ∧ A) ∨ (A ∧ B)  with separate buy orders of 0.5 on each.  If φ were satisfiable then in the state corresponding to  the satisfying assignment and both A and B to be true, τ  and τ both have an auctioneer"s payoff of −0.5 so even no  divisible matching can exist.  If φ were not satisfiable then one unit of each would be a  matching since in every state at least one of τ or τ are  false.  5.3 Small number of securities with indivisible  orders  This case is easily seen to be in NP: Just   nondeterministically guess a nonempty subset S of orders and check for  each state ω in Ω that  Υ ω  auc =  X  i∈S  −Υ  ω  i ≥ 0.  Since |Ω| and |S| are bounded by a polynomial in n, the  verification can be done in polynomial time.  To show that matching is NP-complete we reduce the   NPcomplete problem EXACT COVER BY 3-SETS (X3C) to a  matching of securities.  The input to X3C consists of a set X and a collection C  of 3-element subsets of X. The input (X, C) is in X3C if C  contains an exact cover of X, i.e., there is a subcollection  C of C such that every element of X occurs in exactly one  member of C . Karp showed that X3C is NP-complete.  Suppose we have an instance (X, C) with the vector X =  {x1, . . . , x3q} and C = {c1, . . . , cm}.  We set Ω = {e1, . . . , e3q, r, s} and define securities labelled  φ1 , . . . , φm , ψ1 , . . . , ψq and τ , as follows:  • Security φi is true in state r, and is true in state ek  if k is not in ci.  • Security ψj is true only in state s.  • Security τ is true in each state ek but not r or s.  We have buy orders on each φi and ψj security for  0.5 − 1  8q  and a buy order on τ for 0.5.  We claim that a matching exists if and only if (X, C) is  in X3C.  If (X, C) is in X3C, let C be the subcollection that covers  each element of X exactly once. Note that |C | = q.  We claim the collection consisting of φi for each ci in  C , every ψj and τ has a matching.  In each state ek we have an auctioneer"s payoff of  (.5 −  1  8q  ) + (q − 1)(−.5 −  1  8q  ) + q(.5 −  1  8q  ) − .5  = .5 − 2q  1  8q  = .25 ≥ 0.  In states r and s the auctioneer"s payoffs are  −q(.5 +  1  8q  ) + −q(−.5 +  1  8q  ) + .5 = −5 − 2q  1  8q  = .25 ≥ 0.  Suppose now that (X, C) is not in X3C but there is a  matching. Consider the number q of the φi in that   matching and q the number of ψj in the matching. Since a  matching requires a nonempty subset of the orders and τ  by itself is not a matching we have q + q > 0.  We have three cases.  q > q: In state r, the auctioneer"s payoff is  −q (.5 +  1  8q  ) − q(−.5 +  1  8q  ) + .5 ≤ −(q + q)  1  8q  < 0.  q > q : In state s, the auctioneer"s payoff is  −q (.5 +  1  8q  ) − q (−.5 +  1  8q  ) + .5 ≤ −(q + q )  1  8q  < 0.  q ≤ q ≤ q: Consider the set C consisting of the ci  where φi is in the matching. There must be some state  ek not in any of the ci or C would be an exact cover. The  auctioneer"s payoff in ek is at most  −q (.5 +  1  8q  ) − q (−.5 +  1  8q  ) ≤ −(q + q )  1  8q  < 0.  5.4 Large Number of Securities with   Indivisible Orders  The class Σp  2 is the second level of the polynomial-time  hierarchy. A language L is in Σp  2 if there exists a polynomial  p and a set A in P such that x is in L if and only if there  is a y with |y| = p(|x|) such that for all z, with |z| = p(|x|),  (x, y, z) is in A. The class Σp  2 contains both NP and   coNP. Unless the polynomial-time hierarchy collapses (which  is considered unlikely), a problem that is complete for Σp  2 is  not contained in NP or co-NP.  We will show that computing a matching is Σp  2-complete,  and remains so even for quite restricted types of securities,  and hence is (likely) neither in NP or co-NP. While it may  seem that being NP-complete or co-NP-complete is hard  enough, there are further practical consequences of being  outside of NP and co-NP. If the matching problem were in  NP, one could use heuristics to search for and verify a match  if it exists; even if such heuristics fail in the worst case, they  may succeed for most examples in practice. Similarly, if  the matching problem were in co-NP, one might hope to at  least heuristically rule out the possibility of matching. But  for problems outside of NP or co-NP, there is no framework  for verifying that a heuristically derived answer is correct.  Less formally, for NP (or co-NP)-complete problems, you  have to be lucky; for Σp  2-complete problems, you can"t even  tell if you"ve been lucky.  150  We note that the existence of a matching is in Σp  2: We  use y to choose a subset of the orders and z to represent  a state ω with (x, y, z) in A if the set of orders has a total  nonpositive auctioneer"s payoff in state ω.  We prove a stronger theorem which implies that matching  is in Σp  2. Let S1, . . . , Sn be a set of securities, where each  security Si has cost ci and pays off pi whenever formula Ci  is satisfied. The 0 − 1-matching problem asks whether one  can, by accepting either 0 or 1 of each security, guarantee a  worst-case payoff strictly larger than the total cost.  Theorem 2. The 0−1-matching problem is Σp  2-complete.  Furthermore, the problem remains Σp  2-complete under the  following two special cases:  1. For all i, Ci is a conjunction of 3 base events (or their  negations), pi = 1, and ci = cj for all i and j.  2. For all i, Ci is a conjunction of at most 2 base   securities (or their negations).  These hardness results hold even if there is a promise that  no subset of the securities guarantees a worst-case payoff  identical to their cost.  To prove Theorem 2, we reduce from the standard Σp  2  problem that we call T∃∀BF. Given a boolean formula φ  with variables x1, . . . , xn and y1, . . . , yn is the following   fullyquantified formula true  ∃x1 . . . ∃xn∀y1 . . . ∀yn φ(x1, . . . , xn, y1, . . . , yn)?  The problem remains Σp  2-complete when  φ(x1, . . . , xn, y1, . . . , yn)  is restricted to being a disjunction of conjunctions of at most  3 variables (or their negations), e.g.,  φ(x1, . . . , xn, y1, . . . , yn) =  (x1 ∧ ¯x3 ∧ y2) ∨ (x2 ∧ y3 ∧ y7) ∨ · · · .  This form, without the bound on the conjunction size, is  known as disjunctive normal form (DNF); the restriction to  conjunctions of 3 variables is 3-DNF.  We reduce T∃∀BF to finding a matching. For the simplest  reduction, we consider the matching problem where one has  a set of Arrow-Debreu securities whose payoff events are  conjunctions of the base securities, or their negations. The  auctioneer has the option of accepting either 0 or 1 of each  of the given securities.  We first reduce to the case where the payoff events are  conjunctions of arbitrarily many base events (or their   negations). By a standard trick we can reduce the number of  base events in each conjunction to 3, and with a slight twist  we can even ensure that all securities have the same price as  well as the same payoff. Finally, we show that the problem  remains hard even if only conjunctions of 2 variables are  allowed, though with securities that deviate slightly from  Arrow-Debreu securities in that they may have varying, non  unit payoffs.  5.4.1 The basic reduction  Before describing the securities, we give some intuition.  The T∃∀BFproblem may be viewed as a game between a  selector and an adversary. The selector sets the xi variables,  and then the adversary sets the yi variables so as to falsify  the formula φ. We can view the 0 − 1-matching problem as  one in which the auctioneer is a buyer who buys securities  corresponding to disjunctions of the base events, and then  the adversary sets the values of the base events to minimize  the payoff from the securities.  We construct our securities so that the optimal buying  strategy is to buy n expensive securities along with a set  of cheap securities, of negligible cost (for some cases we  can modify the construction so that all securities have the  same cost). The total cost of the securities will be just  under 1, and each security pays off 1, so the adversary must  ensure that none of the securities pays off. Each expensive  security forces the adversary to set some variable, xi to a  particular value to prevent the security from paying off; this  corresponds to setting the xi variables in the original game.  The cheap securities are such that preventing every one of  of these securities from paying off is equivalent to falsifying  φ in the original game.  Among the technical difficulties we face is how to prevent  the buyer from buying conflicting securities, e.g., one that  forces xi = 0 and the other that forces xi = 1, allowing for  a trivial arbitrage. Secondly, for our analysis we need to  ensure that a trader cannot spend more to get more, say by  spending 1.5 for a set of securities with the property that at  least 2 securities pay off under all possible events.  For each of the variables {xi}, {yi} in φ, we add a   corresponding base security (with the same labels). For each  existential variable xi we add additional base securities, ni  and zi. We also include a base security Q.  In our basic construction, each expensive security costs C  and each cheap security costs ; all securities pay off 1. We  require that Cn+ (|cheap securities|) < 1 and C(n+1) > 1.  That is, one can buy n expensive securities and all of the  cheap securities for less than 1, but one cannot buy n + 1  expensive securities for less than 1. We at times refer to a  security by its payoff clause.  Remark: We may loosely think of as 0. However, this  would allow one to buy a security for nothing that pays (in  the worst case) nothing. By making > 0 , we can show  it hard to distinguish portfolios that guarantee a positive  profit from those that risk a positive loss. Setting > 0 will  also allow us to show hardness results for the case where all  securities have the same cost.  For 1 ≤ i ≤ n, we have two expensive securities with  payoff clauses (¯xi ∧Q) and (¯ni ∧Q) and two cheap securities  with payoff clauses (xi ∧ ¯zi) and (ni ∧ ¯zi).  For each clause C ∈ φ, we convert every negated variable  ¯xi into ni and add the conjunction z1 ∧ · · · ∧ zn. Thus, for a  clause C = (x2 ∧ ¯x7 ∧ ¯y5) we construct a cheap security SC,  with payoff clause  (z1 ∧ · · · ∧ zn ∧ x2 ∧ n7 ∧ ¯y5).  Finally, we have a cheap security with payoff clause ( ¯Q).  We now argue that a matching exists iff  ∃x1 . . . ∃xn∀y1 . . . ∀yn φ(x1, . . . , xn, y1, . . . , yn).  We do this by successively constraining the buyer and the  adversary, eliminating behaviors that would cause the other  player to win. The resulting reasonable strategies   correspond exactly to the game version of T∃∀BF.  First, observe that if the adversary sets all of the base  securities to false (0), then only the ( ¯Q) security will pay off.  151  Thus, no buyer can buy more than n expensive securities  and guarantee a profit. The problem is thus whether one  can buy n expensive securities and all the cheap securities,  so that at for any setting of the base events at least one  security will pay off.  Clearly, the adversary must make Q hold, or the ( ¯Q)   security will pay off. Next, we claim that for each i, 1 ≤ i ≤ i,  the auctioneer must buy at least one of the (¯xi ∧ Q) and  (¯ni ∧ Q) securities. This follow from the fact that if the   adversary sets xi, ni and zi to be false, and every other base  event to be true, then only the (¯xi ∧ Q) and (¯ni ∧ Q)   securities will pay off. As no auctioneer can buy more than  n expensive securities, it must therefore buy exactly one of  (¯xi ∧ Q) or (¯ni ∧ Q), for each i, 1 ≤ i ≤ n. For the rest  of the analysis, we assume that the auctioneer follows this  constraint.  Suppose that the buyer buys (¯xi ∧Q). Then the adversary  must set xi to be true (since it must set Q to be true), or the  security will pay off. It must then set zi to be true or (xi∧¯zi)  will pay off. Since the buyer doesn"t buy (¯ni ∧ Q) (by the  above constraint), and all the other securities pay the same  or less when ni is made false, we can assume without loss of  generality that the adversary sets ni to be false. Similarly,  if the buyer buys (¯ni ∧ Q), then the adversary must set  ni and zi to be true, and we can assume without loss of  generality that the adversary sets xi to be false. Note that  the adversary must in all cases set each zi event to be true.  Summarizing the preceding argument, there is an exact  correspondence between the rational strategies of the buyer  and settings for the xi variables forced on the adversary.  Furthermore, the adversary is also constrained to set the  variables Q, z1, . . . , zn to be true, and without loss of   generality may be assumed to set ni = ¯xi. Under these   constraints, those securities not corresponding to clauses in φ  are guaranteed to not pay off.  The adversary also decides the value of the y1, . . . , ym  base events. Recall that for each clause C ∈ φ there is a  corresponding security SC. Given that zi is true and ni = ¯xi  (without loss of generality), it follows from the construction  of SC that the setting of the yis causes SC to pay off iff it  satisfies C. This establishes the reduction from T∃∀BF to  the matching problem, when the securities are constrained  to be a conjunction of polynomially many base events or  their negations.  5.4.2 Reducing to 3-variable conjunctions  There are standard methods for reducing DNF formulae to  3-DNF formulae, which are trivially modifiable to our   securities framework; we include the reduction for completeness.  Given a security S whose payoff clause is  C = (v1 ∧ v2 ∧ · · · ∧ vk)  (variable negations are irrelevant to this discussion), cost  c and payoff p, introduce a new auxiliary variable, w, and  replace the security with two securities, S1 and S2, with  payoff clauses,  C1 = (v1 ∧ v2 ∧ w) and  C2 = ( ¯w ∧ v3 ∧ · · · ∧ vk).  The securities both have payoff p, and their costs can be  any positive values that sum to c. Note that at most one of  the securities can pay off at a time. If only one security is  bought, then the adversary can always set w so that it won"t  pay off; hence the auctioneer will buy either both or neither,  for a total cost of c (here we use the fact that one is only  allowed to buy either 0 or 1 shares of each security). Then,  it may be verified that, given the ability to set w arbitrarily,  the adversary can cause C to be unsatisfied iff it can cause  both C1 and C2 to be unsatisfied. Hence, owning one share  each of S1 and S2 is equivalent to owning one share of S.  Note that C1 has three variables and C2 has k−1 variables.  By applying the transformation successively, one obtains an  equivalent set of securities, of polynomial size, whose payoff  clauses have at most 3 variables.  We note that in the basic construction, all of the clauses  with more than 3 variables are associated with cheap   securities (cost ). Instead of subdividing costs, we can simply  make all of the resulting securities have cost ; the   constraints on C and must reflect the new, larger number of  cheap securities.  One can ensure that all of the payoff clauses have exactly  3 variables, with a similar construction. A security S with  cost c, payoff p and defining clause (x ∧ y) can be replaced  by securities S1 and S2 with cost c/2, payoff p and defining  clauses (x∧y∧w) and (x∧y∧ ¯w), where w is a new auxiliary  variable. Essentially the same analysis as given above   applies to this case. The case of single-variable payoff clauses  is handled by two applications of this technique.  5.4.3 Reducing to equi-cost securities  By setting C and appropriately, one can ensure that  in the basic reduction every security costs a polynomially  bounded integer multiple of ; call this ratio r. We now  show how to reduce this case to the case where every   security costs . Recall that the expensive securities have  payoff clauses (¯xi ∧ Q) or (¯ni ∧ Q). Assume that   security S has payoff clause (¯xi ∧ Q) (the other case is handled  identically). Replace S with security S , with payoff clause  (¯xi ∧ Q ∧ w1) (w1, . . . , wr−1 are auxiliary variables; fresh  variables are chosen for each clause), and also S1, . . . , Sr−1,  with payoff clauses  ( ¯w1 ∧ w2), ( ¯w2 ∧ w3), . . . , ( ¯wr−2 ∧ wr−1), and( ¯wr−1 ∧ ¯w1).  Clearly, buying none of the new securities is equivalent  to not buying the original security. We show that buying  all of the new securities is equivalent to buying the original  security, and that buying a proper, nonempty subset of the  securities is irrational.  We first note that if the buyer buys securities S1, . . . , Sr−1,  then the adversary must set w1 to be true, or one of the  securities will pay off. To see this, note that if wi is set to  false, then ( ¯wi ∧wi+1) will be true unless wi+1 is set to false;  thus, setting w1 to false forces the adversary to set wr−1 to  false, causing the final clause to be true. Having set w1  true, the adversary can set w2, . . . , wr−1 to false, ensuring  that none of the securities S1, . . . , Sr−1 pays out. If wi is  true, then (¯xi ∧ Q ∧ w1) is equivalent to (¯xi ∧ Q). So buying  all of the replacement securities for each is equivalent to  buying the original security for r.  It remains to show that buying a proper, nonempty   subset of the securities is irrational. If one doesn"t buy S ,  then the adversary can set the w variables so that none of  S1, . . . , Sr−1 will pay off; any money spent on these   securities is wasted. If one doesn"t buy Sr−1, the adversary can  set all w to false, in which case none of the new clauses will  pay off, regardless of the value of xi and Q. Similarly, if one  152  doesn"t buy Si, for 1 ≤ i ≤ r −2, the adversary can set wi+1  to be true, all the other w variables to be false, and again  there is no payoff, regardless of the value of xi and Q. Thus,  buying a proper subset of these securities will not increase  ones payoff.  We note that this reduction can be combined trivially with  the reduction that ensures that all of the defining clauses  have 3 or fewer variables. With a slightly messier argument,  all of the defining clauses can be set up to have exactly 3  variables.  5.4.4 Reducing to clauses of at most 2 variables  If we allow securities to have variable payoffs and prices,  we can reduce to the case where each security"s payoff clause  is a conjunction of at most 2 variables or their negations.  Given a security s with payoff clause (X ∧ Y ∧ Z), cost c  and payoff 1, we introduce fresh auxiliary variables, w1, w2  and w3 (new variables are used for each clause) and replace  S with the following securities:  • Securities S1, S2 and S3, each with cost c/3 and payoff  1, with respective payoff clauses (X ∧ w1), (Y ∧ w2)  and (Z ∧ w3).  • Securities S1, . . . , S6, each with cost 4 and payoff 24 −  2, with payoff clauses,  (w1 ∧ w2) (w1 ∧ w3) (w2 ∧ w3)  ( ¯w1 ∧ ¯w2) ( ¯w1 ∧ ¯w3) ( ¯w2 ∧ ¯w3)  Here, 2 is a tiny positive quantity, described later. By a  simple case analysis, we have the following.  Observations:  1. For any i, there exists a setting of w1, w2 an w3 such  that of the S securities only Si pays off.  2. For any setting of w1, w2 and w3, at least one of the  S securities will pay off.  3. If w1, w2 and w3 are all false, all of the S securities  will pay off.  4. Setting one of w1, w2 or w3 to be true, and the others  to be 0, will cause exactly one of the S securities to  pay off.  By Observation 1, there is no point in buying a nonempty  proper subset of the S securities: The adversary can ensure  that none of the bought securities will pay off, and even if  all the S securities pay off, it will not be sufficient to recoup  the cost of buying a single S security. By Observation 2, if  one buys all the S securities, one is guaranteed to almost  make back ones investment (except for 2), in which case by  Observations 3 and 4, the adversaries optimal strategy is to  make exactly one of w1, w2 or w3 true. We set C, and 2  so that  Cn + (|cheap securities|) + 2(|clauses|) < 1.  Thus, the accumulated losses of 2 can never spell the   difference between making a guaranteed profit and making no  profit at all. Note also that by making 2 positive we prevent  the existence of break-even buying strategies in which the  buyer only purchases S securities.  Summarizing the previous argument, we may assume   without loss of generality that the buyer buys all of the S   securities (for all clauses), and that for each clause the adversary  sets exactly one of that clause"s auxiliary variables w1, w2 or  w3 to be true. For the rest of the discussion, we assume that  the players follow these constraints.  We next claim that a rational buyer will either buy all  of S1, S2 or S3, or none of them. If the buyer doesn"t buy  S1, then if the adversary makes w1 true and w2 and w3  false, neither S2 nor S3 will pay off, regardless of how the  adversary sets X, Y and Z. Hence, there is no point in  buying either S2 or S3 if one doesn"t buy S1. Applying the  same argument to S2 and S3 establishes the claim.  Clearly, buying none of S1, S2 and S3 has, up to negligible  2 factors, the same price/payoff behavior as not buying S.  We next argue that, subject to the established constraints  put on the players" behaviors, buying all of S1, S2 and S3 has  the same price/payoff behavior (again ignoring 2 factors) as  buying S, regardless of how the adversary sets X, Y and Z.  First, in both cases, the cost is c. If the adversary makes  X, Y and Z true, then S pays off 1, and (assuming that  exactly one of w1, w2 and w3 is true), exactly one of S1, S2  or S3 will pay off 1. If X is false, then S doesn"t pay off,  and the adversary can set w1 true (and w2 and w3 false),  ensuring that none of S1, S2 and S3 pays off. The same  argument holds if Y or Z are false.  6. TRACTABLE CASES  The logical question to ask in light of these complexity   results is whether further, more severe restrictions on the space  of securities can enable tractable matching algorithms.   Although we have not systematically explored the possibilities,  the potential for useful tractable cases certainly exists.  Suppose, for example, that bids are limited to unit   quantities of securities of the following two forms:  1. Disjunctions of positive events: A1 ∨ · · · ∨ Ak .  2. Single negative events: ¯Ai .  Let p be the price offered for a disjunction A1 ∨ · · · ∨ Ak ,  and qi the maximal price offered for the respective negated  disjuncts. This disjunction bid is part of a match iff p +P  i qi ≥ k. Evaluating whether this condition is satisfied by  a subset of bids is quite straightforward.  Although this example is contrived, its application is not  entirely implausible. For example, the disjunctions may   correspond to insurance customers, who want an insurance   contract to cover all the potential causes of their asset loss. The  atomic securities are sold by insurers, each of whom   specialize in a different form of disaster cause.  7. CONCLUSIONS AND  FUTURE DIRECTIONS  We have analyzed the computational complexity of   matching for securities based on logical formulas. Many possible  avenues for future work exist, including  1. Analyzing the agents" optimization problem:  • How to choose quantities and bid/ask prices for  a collection of securities to maximizes one"s   expected utility, both for linear and nonlinear utility  functions.  153  • How to choose securities; that is, deciding on  what collection of boolean formulas to offer to  trade, subject to constraints or penalties on the  number or complexity of bids.  • How do make the above choices in a game   theoretically sound way, taking into account the choices  of other traders, their reasoning about other traders,  etc.  2. Although matching is likely intractable, are there good  heuristics that achieve matches in many cases or   approximate a matching?  3. Exploring sharing rules for dividing the surplus, and  incentive properties of the resulting mechanisms.  4. We may consider a market to be in computational   equilibrium if no computationally-bounded player can find  a strategy that increases utility. With few exceptions  [3, 22], little is known about computational   equilibriums. A natural question is to determine whether a  market can achieve a computational equilibrium that is  not a true equilibrium, and under what circumstances  this may occur.  Acknowledgments  We thank Rahul Sami for his help with Section 5.4.4. We  thank Rahul, Joan Feigenbaum and Robin Hanson for useful  discussions.  8. REFERENCES  [1] Kenneth J. Arrow. The role of securities in the  optimal allocation of risk-bearing. Review of Economic  Studies, 31(2):91-96, 1964.  [2] Peter Bossaerts, Leslie Fine, and John Ledyard.  Inducing liquidity in thin financial markets through  combined-value trading mechanisms. European  Economic Review, 46:1671-1695, 2002.  [3] Paul J. Brewer. Decentralized computation  procurement and computational robustness in a smart  market. Economic Theory, 13:41-92, 1999.  [4] Kay-Yut Chen, Leslie R. Fine, and Bernardo A.  Huberman. Forecasting uncertain events with small  groups. In Third ACM Conference on Electronic  Commerce (EC"01), pages 58-64, 2001.  [5] Bruno de Finetti. Theory of Probability: A Critical  Introductory Treatment, volume 1. Wiley, New York,  1974.  [6] Sven de Vries and Rakesh V. Vohra. Combinatorial  auctions: A survey. INFORMS J. of Computing, 2003.  [7] Sandip Debnath, David M. Pennock, C. Lee Giles, and  Steve Lawrence. Information incorporation in online  in-game sports betting markets. In Fourth ACM  Conference on Electronic Commerce (EC"03), 2003.  [8] Jacques H. Dreze. Market allocation under  uncertainty. In Essays on Economic Decisions under  Uncertainty, pages 119-143. Cambridge University  Press, 1987.  [9] Ronald Fagin, Joseph Y. Halpern, and Nimrod  Megiddo. A logic for reasoning about probabilities.  Information and Computation, 87(1/2):78-128, 1990.  [10] Robert Forsythe and Russell Lundholm. Information  aggregation in an experimental market. Econometrica,  58(2):309-347, 1990.  [11] Robert Forsythe, Forrest Nelson, George R. Neumann,  and Jack Wright. Anatomy of an experimental  political stock market. American Economic Review,  82(5):1142-1161, 1992.  [12] Robert Forsythe, Thomas A. Rietz, and Thomas 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.  [13] John M. Gandar, William H. Dare, Craig R. Brown,  and Richard A. Zuber. Informed traders and price  variations in the betting market for professional  basketball games. Journal of Finance,  LIII(1):385-401, 1998.  [14] Robin Hanson. Decision markets. IEEE Intelligent  Systems, 14(3):16-19, 1999.  [15] Robin Hanson. Combinatorial information market  design. Information Systems Frontiers, 5(1), 2002.  [16] Robin D. Hanson. Could gambling save science?  Encouraging an honest consensus. Social  Epistemology, 9(1):3-33, 1995.  [17] Jens Carsten Jackwerth and Mark Rubinstein.  Recovering probability distributions from options  prices. Journal of Finance, 51(5):1611-1631, 1996.  [18] Joseph B. Kadane and Robert L. Winkler. Separating  probability elicitation from utilities. Journal of the  American Statistical Association, 83(402):357-363,  1988.  [19] Michael Magill and Martine Quinzii. Theory of  Incomplete Markets, Vol. 1. MIT Press, 1996.  [20] Andreu Mas-Colell, Michael D. Whinston, and  Jerry R. Green. Microeconomic Theory. Oxford  University Press, New York, 1995.  [21] Noam Nisan. Bidding and allocation in combinatorial  auctions. In Second ACM Conference on Electronic  Commerce (EC"00), pages 1-12, 2000.  [22] Noam Nisan and Amir Ronen. Computationally  feasible VCG mechanisms. In Second ACM Conference  on Electronic Commerce (EC"00), pages 242-252,  2000.  [23] J. Pearl. Probabilistic Reasoning in Intelligent  Systems. Morgan Kaufmann, 1988.  [24] David M. Pennock, Steve Lawrence, C. Lee Giles, and  Finn ˚Arup Nielsen. The real power of artificial  markets. Science, 291:987-988, February 9 2001.  [25] David M. Pennock, Steve Lawrence, Finn ˚Arup  Nielsen, and C. Lee Giles. Extracting collective  probabilistic forecasts from web games. In Seventh  International Conference on Knowledge Discovery and  Data Mining, pages 174-183, 2001.  [26] David M. Pennock and Michael P. Wellman. Compact  securities markets for Pareto optimal reallocation of  risk. In Sixteenth Conference on Uncertainty in  Artificial Intelligence, pages 481-488, 2000.  [27] C. R. Plott, J. Wit, and W. C. Yang. Parimutuel  betting markets as information aggregation devices:  Experimental results. Social Science Working Paper  986, California Institute of Technology, April 1997.  154  [28] Charles R. Plott. Markets as information gathering  tools. Southern Economic Journal, 67(1):1-15, 2000.  [29] Charles R. Plott and Shyam Sunder. Rational  expectations and the aggregation of diverse  information in laboratory security markets.  Econometrica, 56(5):1085-1118, 1988.  [30] R. Roll. Orange juice and weather. American  Economic Review, 74(5):861-880, 1984.  [31] Tuomas Sandholm, Subhash Suri, Andrew Gilpin, and  David Levine. Winner determination in combinatorial  auction generalizations. In First International Joint  Conference on Autonomous Agents and Multiagent  Systems (AAMAS), July 2002.  [32] Carsten Schmidt and Axel Werwatz. How accurate do  markets predict the outcome of an event? the Euro  2000 soccer championships experiment. Technical  Report 09-2002, Max Planck Institute for Research  into Economic Systems, 2002.  [33] Richard H. Thaler and William T. Ziemba. Anomalies:  Parimutuel betting markets: Racetracks and lotteries.  Journal of Economic Perspectives, 2(2):161-174, 1988.  [34] Hal R. Varian. The arbitrage principle in financial  economics. J. Economic Perspectives, 1(2):55-72,  1987.  [35] Robert L. Winkler and Allan H. Murphy. Good  probability assessors. J. Applied Meteorology,  7:751-758, 1968.  155