Combinatorial Betting

Опубликовано 6 сентября 2016, 18:12

Most betting markets -- from Las Vegas to Wall Street ΓÇô operate similarly: Each allowable bet is explicitly listed and tracked; each betΓÇÖs outcome space is low dimensional; and each bet type is managed independently. In this talk, I will survey our attempts to design combinatorial betting mechanisms that support doubly exponentially many allowable bets and propagate information appropriately across logically-related bets. Thus, our mechanisms have the potential to both collect more information and process that information more fully than standard mechanisms. The greater expressiveness comes at a computational cost for the auctioneer, who faces a difficult matching problem to connect up willing traders. In general, the auctioneer must consider complex multilateral matches and full expressiveness renders the matching problem intractable. However, in some cases we have discovered reasonable restrictions on expressiveness that admit polynomial-time matching algorithms.