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.
- 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.Google Scholar
- P. Cramton,Y. Shoham and R. Steinberg. Combinatorial Auctions. MIT Press, Cambridge, MA, 2005. Google ScholarDigital Library
- Y. Chen, L. Fortnow, E. Nikolova, D. Pennock. Betting on Permutations, Proceedings of the ACM Conference on Electronic Commerce, 2007. Google ScholarDigital Library
- D. Pennock. Personal Communications.Google Scholar
- K. Dhamdhere, V. Goyal, R. Ravi, and M. Singh. How to pay, come what may: Approximation algorithms for demand-robust covering problems. FOCS, 2005. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- U. Feige. On maximizing welfare when utility functions are subadditive, STOC, 2006. Google ScholarDigital Library
- U. Feige, K. Jain, M. Mahdian, and V.S. Mirrokni. Robust Combinatorial Optimization with Exponential Number of Scenarios. Integer Programming and Combinatorial Optimization, 2007. Google ScholarDigital Library
- L. Fortnow, J. Kilian, D. Pennock, M.P. Wellman. Betting boolean-style: A framework for trading in securities based on logical formulas. Decision Support Systems, 39(1):87--104, 2004. Google ScholarDigital Library
- A. Gupta, M. Pal, R. Ravi, and A. Sinha. Boosted sampling:Approximation algorithms for stochastic optimization. In STOC, pages 170--178, 2004. Google ScholarDigital Library
- R.D. Hanson. Combinatorial information market design.Information Systems Frontiers,5(1):107-119, 2003. Google ScholarDigital Library
- 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.Google Scholar
- N. Immorlica, D. Karger, M. Minkoff, and V.S. Mirrokni. On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems. In SODA, 2004. Google ScholarDigital Library
- B. Lehmann, D. Lehmann, and N. Nisan. Combinatorial Auctions with Decreasing Marginal Utilities, ACM EC 2001. Google ScholarDigital Library
- Y. Nikulin. Robustness in combinatorial optimization and scheduling theory: An annotated bibliography. Technical Report SOR-91-13, Statistics and Operation Research, 2004.Google Scholar
- N. Nisan, T. Roughgarden, E. Tardos and V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007. Google ScholarDigital Library
- D.M. Pennock, S. Lawrence, C.L. Giles, and F.A. Nielsen. The real power of artifircial markets. Science, 291:987--988, February 2002.Google ScholarCross Ref
- C. PapadimitriouGoogle Scholar
- 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, 1982Google ScholarCross Ref
- C. Plott and S. Sunder. Rational expectations and the aggregation of diverse information in laboratory security markets. Econometrica, 56:1085--1118, 1988.Google ScholarCross Ref
- T. Sandholm. Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence, 135:1--54, 2002. Google ScholarDigital Library
- A. Schrijver. Total Dual Integrality of Matching Forest Constraints. Combinatorica, 20:575--588, 2000.Google ScholarCross Ref
- D. Shmoys and S. Swamy. Stochastic optimization is (almost) as easy as deterministic optimization. In FOCS, 2004. Google ScholarDigital Library
- A. Schrijver, Combinatorial Optimization - Polyhedra and Efficiency, Springer-Verlag, Berlin, 2003.Google Scholar
Index Terms
- Permutation betting markets: singleton betting with extra information
Recommendations
Permutation Betting Markets: Singleton Betting with Extra Information
We study permutation betting markets, introduced by Chen et al. (Proceedings of the ACM Conference on Electronic Commerce, 2007). For these markets, we consider subset bettings in which each trader can bet on a subset of candidates ending up in a subset ...
Permutation Betting Markets: Singleton Betting with Extra Information
We study permutation betting markets, introduced by Chen et al. (Proceedings of the ACM Conference on Electronic Commerce, 2007). For these markets, we consider subset bettings in which each trader can bet on a subset of candidates ending up in a subset ...
Gaming Prediction Markets: Equilibrium Strategies with a Market Maker
We study the equilibrium behavior of informed traders interacting with market scoring rule (MSR) market makers. One attractive feature of MSR is that it is myopically incentive compatible: it is optimal for traders to report their true beliefs about the ...
Comments