|
Betting on Permutations
Yiling Chen, Lance Fortnow, Evdokia Nikolova & David
Pennock
We consider a permutation betting scenario, where people wager
on the final ordering of n candidates: for example, the outcome
of a horse race. We examine the auctioneer problem of risklessly
matching up wagers or, equivalently, finding 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 orderings
is 2^{n!}. We propose two expressive betting languages that seem
natural for bidders, and examine the computational 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 final ordering, for example, ``horse A will finish in positions 4,
9, or 13-21'', or that a position will be taken by some subset of candidates,
for example ``horse A, B, or D will finish in position 2''. For subset
betting, we show that the auctioneer 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 candidate,
for example ``horse A will beat horse B''. We prove that the auctioneer
problem becomes NP-hard for pair betting. We identify a sufficient condition
for the existence of a pair betting match that can be verified in polynomial
time. We also show that a natural greedy algorithm gives a poor approximation
for indivisible orders.
References:
[1] Yiling Chen, Lance Fortnow, Evdokia Nikolova, David Pennock. ``Betting
on Permutations." In Proceedings of 2007 ACM Conference on Electronic
Commerce (ACM EC 2007).
|
|
