Convergence in competitive Games

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 eventhough 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.