Betting on permutations

Yiling Chen, Lance Fortnow, Evdokia Nikolova, David M. Pennock

Research output: Chapter in Book/Report/Conference proceedingConference contribution

23 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationEC'07 - Proceedings of the Eighth Annual Conference on Electronic Commerce
Pages326-335
Number of pages10
DOIs
StatePublished - 2007
Externally publishedYes
Event8th ACM Conference on Electronic Commerce, EC'07 - San Diego, CA, United States
Duration: Jun 11 2007Jun 15 2007

Publication series

NameEC'07 - Proceedings of the Eighth Annual Conference on Electronic Commerce

Other

Other8th ACM Conference on Electronic Commerce, EC'07
Country/TerritoryUnited States
CitySan Diego, CA
Period6/11/076/15/07

ASJC Scopus subject areas

  • Management of Technology and Innovation
  • Marketing
  • Computer Networks and Communications
  • Computer Science Applications

Keywords

  • Computational complexity
  • Expressive betting
  • Order matching
  • Prediction market

Fingerprint

Dive into the research topics of 'Betting on permutations'. Together they form a unique fingerprint.

Cite this