Last update: August 19, 2009 |
4th Athens Colloquium on Algorithms and Complexity (ACAC 2009)August 20-21, 2009Athens University of Economics and BusinessInvited Talk
Marios Mavronicolas, University of Cyprus 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. |