Probabilistic Approximation Theorems in Game Theory and Stochastic Optimization/The Theory of Crowdsourcing

Talk 1: 3:30 to 4:15

Title: Probabilistic Approximation Theorems in Game Theory and Stochastic Optimization
Speaker: Costis Daskalakis, MIT

Abstract: In Economics, reliability theory and other domains, uncertainty is often modeled assuming Bayesian knowledge about unknown parameters. This assumption enables important results, e.g. Nash’s theorem on the existence of equilibria in randomized strategies in games, and Myerson’s theorem on revenue-optimal auctions. On the other hand, stochastic uncertainty may introduce computational complexity, in the form of PPAD-completeness for computing Nash equilibria, and more generally non-linearity in the resulting optimization problems. In this talk, we explore probabilistic approximation theorems that alleviate the computational complexity, drawing examples from Game Theory and Stochastic optimization. In particular, we present finitary central limit theorems and extreme value theorems and apply those to obtain polynomial time approximation schemes for Nash equilibria in anonymous games, multi-dimensional pricing, and network reliability problems.

(based on joint work with Christos Papadimitriou, Yang Cai, and Ankur Moitra)

Talk 2: 4:25 PM to 4:55 PM Title: The Theory of Crowdsourcing
Speaker: Jason Hartline, Northwestern

Crowdsourcing contests have been popularized by the Netflix challenge and websites like TopCoder and Taskcn. What is crowdsourcing? Imagine you are designing a new web service, you have it all coded up, but the site looks bad because you haven’t got any graphic design skills. You could hire an artist to design your logo, or you could post the design task as a competition to crowdsourcing website Taskcn with a monetary reward of 100. Contestants on Taskcn would then compete to produce the best logo. You then select your favorite logo and award that contestant the 100 prize.

In this talk, I discuss the theory of crowdsourcing contests. First, I will show how to model crowdsourcing contests using auction theory. Second, I will discuss how to solve for contestant strategies. I.e., suppose you were entering such a programming contest on TopCoder, how much work should you do on your entry to optimize your gains from winning less the cost of doing the work? Finally, I will discuss inefficiency from the fact that the effort of losing contestants is wasted (e.g., every contestant has to do work to design a logo, but you only value your favorite logo). I will show that this wasted effort is at most half of the total amount of effort. A consequence is that crowdsourcing is approximately as efficient a means of procurement as conventional methods (e.g., auctions or negotiations).

Joint work with Shuchi Chawla and Balu Sivan