INTERDISCIPLINARY STOCHASTIC PROCESSES COLLOQUIUM

Tuesday September 16, room 60 Evans, 4.10 - 5.00pm

Speaker: Tim Roughgarden (Stanford)

Title: Probability in Algorithmic Game Theory: Two Unexpected Appearances 


Abstract:  We discuss two recent results in algorithmic game theory informed 
by a probabilistic perspective.  In the first (joint with Jason Hartline), 
we show that the popular benchmarks for the performance of prior-free auctions 
are most naturally motivated and justified via Bayesian analysis.  
In the second (building on joint work with Ho-Lin Chen and Greg Valiant), 
we interpret necessary and sufficient conditions for the existence of pure 
Nash equilibria in certain network games via order statistics of families of 
exponential random variables.