  This paper addresses the problem of fair equilibrium selection in graphical
games. Our approach is based on the data structure called the {\em best
response policy}, which was proposed by Kearns et al. \cite{kls} as a way to
represent all Nash equilibria of a graphical game. In \cite{egg}, it was shown
that the best response policy has polynomial size as long as the underlying
graph is a path. In this paper, we show that if the underlying graph is a
bounded-degree tree and the best response policy has polynomial size then there
is an efficient algorithm which constructs a Nash equilibrium that guarantees
certain payoffs to all participants. Another attractive solution concept is a
Nash equilibrium that maximizes the social welfare. We show that, while exactly
computing the latter is infeasible (we prove that solving this problem may
involve algebraic numbers of an arbitrarily high degree), there exists an FPTAS
for finding such an equilibrium as long as the best response policy has
polynomial size. These two algorithms can be combined to produce Nash
equilibria that satisfy various fairness criteria.
