Betting on permutations

Publisher Website
Google Scholar
Abstract
We consider a permutation betting scenario, where people wager on the flnal ordering of n candidates: for example, the outcome of a horse race. We examine the auctioneer problem of risklessly matching up wagers or, equivalently, flnding arbitrage opportunities among the proposed wagers. Requiring bidders to explicitly list the orderings that they'd like to bet on is both unnatural and intractable, because the number of orderings is n! and the number of subsets of or- derings is 2n!. We propose two expressive betting languages that seem natural for bidders, and examine the computa- tional complexity of the auctioneer problem in each case. Subset betting allows traders to bet either that a candidate will end up ranked among some subset of positions in the flnal ordering, for example, \horse A will flnish in positions 4, 9, or 13-21", or that a position will be taken by some sub- set of candidates, for example \horse A, B, or D will flnish in position 2". For subset betting, we show that the auc- tioneer problem can be solved in polynomial time if orders are divisible. Pair betting allows traders to bet on whether one candidate will end up ranked higher than another can- didate, for example \horse A will beat horse B". We prove that the auctioneer problem becomes NP-hard for pair bet- ting. We identify a su-cient condition for the existence of a pair betting match that can be verifled in polynomial time. We also show that a natural greedy algorithm gives a poor approximation for indivisible orders.