Technion, IEM faculty - Information Systems seminar
Speaker: Ola Rozenfeld
Title: Near Strong Equilibrium
Date: 03/05/2011
Time: 13:00
Place: Bloomfield-527
Abstract:  <>
or see it here:
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
Ph.D. seminar; advisor: Moshe Tennenholtz.
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from:  <>