Last update:
August 19, 2009
 

4th Athens Colloquium on Algorithms and Complexity (ACAC 2009)

August 20-21, 2009

Athens University of Economics and Business




Invited Talk

Marios Mavronicolas, University of Cyprus
"Facets of the Fully Mixed Nash Equilibrium Conjecture"

Abstract. We look at a particular facet of the well-known Fully Mixed Nash Equilibrium Conjecture. The general conjecture applies to the original context of selfish routing proposed by Koutsoupias and Papadimitriou back in 1999. The particular facet deals with the case where there are only two identical machines and users are unweighted. We prove that if Social Cost if taken as the Quadratic Maximum Social Cost, then it is maximized by the fully mixed Nash equilibrium. An interesting facet of this work lies in the employed combinatorial techniques.