Technion, IEM faculty - Information Systems seminar

Speaker: Ola Rozenfeld
Title: Near Strong Equilibrium
Date: 17/05/2011
Time: 13:00
Place: Bloomfield-527
Abstract:  <>
Or just read below:
Near Strong Equilibrium
Ola Rozenfeld
IE&M, Technion - Israel Institute of Technology
We introduce a new solution concept for games, near-strong equilibrium, a variation of Aumann's strong equilibrium. It
is a mathematically weaker yet conceptually similar concept, and our goal is to demonstrate the existence of this sort
of stability in settings where strong equilibrium is known to not exist. The model we focus on is the network creation
games. Previous work has shown the existence of 2-strong pure strategy equilibrium for network creation games with
edge cost between 1 and 2 and that k-strong equilibrium for k>2 does not exist. In this paper we show that
3-near-strong equilibrium exists, and provide tight bounds on existence of k-near-strong equilibria for k>3. Then we
repeat our analysis for correlated mixed strategies, where we show that, surprisingly, 3-correlated-strong equilibrium
exists, and also show bounds for existence of correlated k-strong equilibria. Moreover, the equilibrium profile can be
arbitrarily close to the social optimum. For both pure and correlated settings, we show examples where no equilibrium
exists. On the conceptual level, our work contributes to the recent literature of extensions of strong equilibrium,
while providing positive results for stability against group deviations in one of the basic settings discussed in the
algorithmic game theory literature.
Ph.D. seminar; advisor: Moshe Tennenholtz.
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from:  <>