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

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 numevents events, the matching problem is co-NP-complete in the divisible case and complete in the indivisible case. We show that the latter hardness result holds even under severe language restrictions on bids. With events, and numevents securities, the problem is polynomial in the divisible case and NP-complete in the indivisible case. We briefly discuss matching algorithms and tractable special cases.

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 , Bernardo A. Huberman, Forecasting uncertain events with small groups, Proceedings of the 3rd ACM conference on Electronic Commerce, p.58-64, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501165]
• 5: Bruno de Finetti. Theory of Probability: A Critical Introductory Treatment, volume 1. Wiley, New York, 1974.
• 6: Sven de Vries , Rakesh V. Vohra, Combinatorial Auctions: A Survey, INFORMS Journal on Computing, v.15 n.3, p.284-309, July 2003 [doi>10.1287/ijoc.15.3.284.16077]
• 7: Sandip Debnath , David M. Pennock , C. Lee Giles , Steve Lawrence, Information incorporation in online in-Game sports betting markets, Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779987]
• 8: Jacques H. Dreze. Market allocation under uncertainty. In Essays on Economic Decisions under Uncertainty, pages 119--143. Cambridge University Press, 1987.
• 9: R. Fagin , Joseph Y. Halpern , Nimrod Megiddo, A logic for reasoning about probabilities, Information and Computation, v.87 n.1-2, p.78-128, July/August 1990 [doi>10.1016/0890-5401(90)90060-U]
• 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, v.5 n.1, p.107-119, January 2003 [doi>10.1023/A:1022058209073]
• 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, Proceedings of the 2nd ACM conference on Electronic commerce, p.1-12, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352872]
• 22: Noam Nisan , Amir Ronen, Computationally feasible VCG mechanisms, Proceedings of the 2nd ACM conference on Electronic commerce, p.242-252, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352898]
• 23: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 24: David M. Pennock, Steve Lawrence, C. Lee Giles, and Finn \AArup Nielsen. The real power of artificial markets. Science, 291:987--988, February 9 2001.
• 25: David M. Pennock , Steve Lawrence , Finn Årup Nielsen , C. Lee Giles, Extracting collective probabilistic forecasts from web games, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.174-183, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502537]
• 26: David M. Pennock , Michael P. Wellman, Compact Securities Markets for Pareto Optimal Reallocation of Risk, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.481-488, June 30-July 03, 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.
• 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 , David Levine, Winner determination in combinatorial auction generalizations, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy [doi>10.1145/544741.544760]
• 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.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Economics, Theory

Keywords:
betting, combinatorial betting, compound securities markets, computational complexity of matching, gambling, hedging, information aggregation, risk allocation, speculating, trading in financial instruments based on logical formulas