From: Kelli McGee \(Kelly Services Inc\) (a-kellim@microsoft.com)
Date: Thu Jul 08 2004 - 12:54:55 PDT
You are invited to attend...
************************************************************************
*****************************
WHO: Vahab S. Mirrokni
AFFILIATION: MIT
TITLE: Convergence in competitive Games
WHEN: Wed 7/14/2004
WHERE: 113/1159 Research Lecture Room, Microsoft Research
TIME: 3:30PM-5:00PM
HOST: Jennifer Chayes and Kamal Jain
************************************************************************
******************************
ABSTRACT:
In order to study the effects of the lack of coordination in games, we
can compute the ratio between the optimal social function and the social
function in a Nash equilibrium, i.e, we can find the price of anarchy of
the game. A large price of anarchy implies the need for the central
regulation, but a small price of anarchy does not necessarily imply a
good performance in lack of coordination for several reasons. One reason
is that we do not know if players will converge to a Nash equilibrium.
Moreover, if they converge to equilibria it may happen slowly. We study
the length of ``fair paths'' of best responses of players and prove
lower and upper bounds on the length of these paths to an approximate
solution. This concept is related to the local optimization algorithms
and the theory of PLS-completeness for local search. We study
basic-utility, valid-utility, and market sharing games. These are games
with submodular social functions. We also consider the following cut
game or the party affiliation game: each player corresponds to a node of
a graph and the strategy of a node is to choose one side of the cut.
Each node's payoff is its contribution in the cut.
The question is how fast players will converge to a large cut. We prove
the existence of short paths from any state and exponentially long paths
from some states in the state graph to approximate solutions. We prove
that random paths will converge to a good cut pretty fast. For games for
which the state graph may contain a cycle, we study the social function
in cyclic equilibria in these games. We show that even though for
valid-utility games the price of anarchy is at most 2, the social
function in a cyclic equilibria can be very bad.
I will survey results from joint works with M. Goemans, L. Li, M.
Thottan and with A. Vetta and with A. Sidiropoulos.
BIO:
Vahab S. Mirrokni received the Bachelor's degree in computer engineering
from Sharif University of Technology, Tehran, Iran in 2001. Since 2001,
he is a Ph.D. candidate in Applied Mathematics in Massachusetts
Institute of Technology. He is a member of the Theory of Computation
Group at Computer Science and Artificial Intelligence Laboratory at MIT.
During his Ph.D. studies, he also worked at the Bell-Laboratories
(Department of Fundamental Mathematics and Networking Center). His
research interests include approximation algorithms, combinatorial
optimization, computational game theory, and network management, and
graph theory.
This archive was generated by hypermail 2.1.6 : Thu Jul 08 2004 - 12:59:24 PDT