caa a22 4500 445804432 CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110801xx s 000 0 eng 10.1007/s00453-009-9378-0 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9378-0 Permutation Betting Markets: Singleton Betting withExtra Information [Elektronische Daten] [Mohammad Ghodsi, Hamid Mahini, Vahab Mirrokni, Morteza Zadimoghaddam] We study permutation betting markets, introduced by Chen etal. (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 of positions. We consider the revenue maximization problem for the auctioneer in two main frameworks: the risk-free revenue maximization (studied in Chen et al., Proceedings of the ACM Conference on Electronic Commerce, 2007), 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 etal. (Proceedings of the ACM Conference on Electronic Commerce, 2007). 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. Springer Science+Business Media, LLC, 2009 Prediction markets nationallicence Revenue maximization nationallicence Betting markets nationallicence Linear programming nationallicence Combinatorial algorithms nationallicence Matching markets nationallicence Ghodsi Mohammad Department of Computer Engineering, Sharif University of Technology, Azadi St., Tehren, Iran aut Mahini Hamid Department of Computer Engineering, Sharif University of Technology, Azadi St., Tehren, Iran aut Mirrokni Vahab Microsoft Research, One Microsoft Way, 98052, Redmond, WA, USA aut Zadimoghaddam Morteza Department of Computer Engineering, Sharif University of Technology, Azadi St., Tehren, Iran aut Algorithmica Springer-Verlag 60/4(2011-08-01), 853-876 0178-4617 60:4<853 2011 60 453 https://doi.org/10.1007/s00453-009-9378-0 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9378-0 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Ghodsi Mohammad Department of Computer Engineering, Sharif University of Technology, Azadi St., Tehren, Iran aut NATIONALLICENCE 700 1- Mahini Hamid Department of Computer Engineering, Sharif University of Technology, Azadi St., Tehren, Iran aut NATIONALLICENCE 700 1- Mirrokni Vahab Microsoft Research, One Microsoft Way, 98052, Redmond, WA, USA aut NATIONALLICENCE 700 1- Zadimoghaddam Morteza Department of Computer Engineering, Sharif University of Technology, Azadi St., Tehren, Iran aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/4(2011-08-01), 853-876 0178-4617 60:4<853 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer