Combinatorial Betting


January 8, 2009


David M. Pennock


Yahoo! Research


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.


David M. Pennock

David M. Pennock is a Senior Research Scientist at Yahoo! Research Labs based in Pasadena, California. Prior to joining Yahoo!, Dr. Pennock worked at NEC Laboratories America, served as an Adjunct Assistant Professor at Pennsylvania State University, and interned at Microsoft Research. He received a B.S. in Physics from Duke University (magna cum laude), an M.S. in Computer Science from Duke, and a Ph.D. in Computer Science from the University of Michigan. He has over thirty-five publications, over twenty talks, and three patents relating to computational issues in electronic commerce and the World Wide Web, including a finalist award for best student paper. His research interests include information markets, e-market analysis, auctions, Web analysis and modeling, recommender systems, machine learning, and artificial intelligence. His research has received significant attention among e-market companies and in the media, including reports in Discover Magazine, New Scientist Magazine, the New York Times, E!Online, and CNN/Money. For more information, please visit