Probabilistic Techniques in Algorithmic Game Theory (SAGA 2007 Invited Paper)

摘要

We consider applications of probabilistic techniques in the framework of algorithmic game theory. We focus on three distinct case studies: (ⅰ) The exploitation of the probabilistic method to demonstrate the existence of approximate Nash equilibria of logarithmic support sizes in bimatrix games; (ⅱ) the analysis of the statistical conflict that mixed strategies cause in network congestion games; (ⅲ) the effect of coalitions in the quality of congestion games on parallel links.