Permutation betting markets: singleton betting with extra information

ABSTRACT

We study permutation betting markets, introduced by Chen, Fortnow, Nikolova, and Pennock [3]. For these markets, we consider subset bettings in which each trader can bet on a subset of candidates ending up in a subset of positions. We consider the revenue maximization problem for the auctioneer in two main frameworks: the risk-free revenue maximization (studied in [3]), and the probabilistic revenue maximization. We also explore the use of some certain knowledge or extra information about the possible outcomes of the market. We first show that finding the optimal revenue in the risk-free model for the subset betting problem is inapproximable. This resolves an open question posed by Chen et al. [3]. In order to identify solvable variants of the problem, we propose the singleton betting language which allows traders to bet an arbitrary value on one candidate for one position. For singleton bettings, we first provide a linear-time implementable necessary and sufficient condition for existence of a solution with positive revenue for any possible outcome. Furthermore, we develop an LP-based polynomial-time algorithm to find the optimum solution of this problem. In addition, we show how to extend this LP-based method to handle some extra information about the possible outcomes. Finally, we consider the revenue maximization problem in a probabilistic setting. For this variant, we observe that the problem of maximizing the expected revenue is polynomial-time solvable, but we show that maximizing the probability of achieving a pre-specified revenue is #P-Complete.

REFERENCES

• 1: J.E. Berg, R. Forsythe, F.D. Nelson, and T.A. Rietz. Results from a dozen years of election futures markets research. In C.A. Plottand V. Smith, editors, Handbook of Experimental Economic Results, 2001.
• 2: Peter Cramton , Yoav Shoham , Richard Steinberg, Combinatorial Auctions, The MIT Press, 2006
• 3: 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]
• 4: D. Pennock. Personal Communications.
• 5: Kedar Dhamdhere , Vineet Goyal , R. Ravi , Mohit Singh, How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.367-378, October 23-25, 2005 [doi>10.1109/SFCS.2005.42]
• 6: R. Forsythe, T.A. Rietz, and T.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.
• 7: Uriel Feige, On maximizing welfare when utility functions are subadditive, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132523]
• 8: U. Feige, K. Jain, M. Mahdian, and V.S. Mirrokni. Robust Combinatorial Optimization with Exponential Number of Scenarios. Integer Programming and Combinatorial Optimization, 2007.
• 9: 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]
• 10: Anupam Gupta , Martin Pál , R. Ravi , Amitabh Sinha, Boosted sampling: approximation algorithms for stochastic optimization, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007419]
• 11: Robin Hanson, Combinatorial Information Market Design, Information Systems Frontiers, v.5 n.1, p.107-119, January 2003 [doi>10.1023/A:1022058209073]
• 12: I. Heller, C.B. Tompkins. An extension of a theorem of Dantzig's, in: H.W. Kuhn, A.W. Tucker (Eds.), Linear Inequalities and Related Systems. Princeton University Press, Princeton, NJ, 1956, pp.247--254.
• 13: Nicole Immorlica , David Karger , Maria Minkoff , Vahab S. Mirrokni, On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 14: Benny Lehmann , Daniel Lehmann , Noam Nisan, Combinatorial auctions with decreasing marginal utilities, Proceedings of the 3rd ACM conference on Electronic Commerce, p.18-28, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501161]
• 15: Y. Nikulin. Robustness in combinatorial optimization and scheduling theory: An annotated bibliography. Technical Report SOR-91-13, Statistics and Operation Research, 2004.
• 16: Noam Nisan , Tim Roughgarden , Eva Tardos , Vijay V. Vazirani, Algorithmic Game Theory, Cambridge University Press, New York, NY, 2007
• 17: D.M. Pennock, S. Lawrence, C.L. Giles, and F.A. Nielsen. The real power of artifircial markets. Science, 291:987--988, February 2002.
• 18: C. Papadimitriou
• 19: C. Plott and S. Sunder. Efficiency of experimental security markets with insider information: An application of rational expectations models. Journal of Political Economy, 90:663--98, 1982
• 20: C. Plott and S. Sunder. Rational expectations and the aggregation of diverse information in laboratory security markets. Econometrica, 56:1085--1118, 1988.
• 21: Tuomas Sandholm, Algorithm for optimal winner determination in combinatorial auctions, Artificial Intelligence, v.135 n.1-2, p.1-54, 02/01/2002 [doi>10.1016/S0004-3702(01)00159-X]
• 22: A. Schrijver. Total Dual Integrality of Matching Forest Constraints. Combinatorica, 20:575--588, 2000.
• 23: David B. Shmoys , Chaitanya Swamy, Stochastic Optimization is (Almost) as easy as Deterministic Optimization, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.228-237, October 17-19, 2004 [doi>10.1109/FOCS.2004.62]
• 24: A. Schrijver, Combinatorial Optimization - Polyhedra and Efficiency, Springer-Verlag, Berlin, 2003.

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

General Terms:
Algorithms, Economics, Theory

Keywords:
linear programming, matching algorithms, permutation markets, prediction markets, revenue maximization