  Examining the behavior of multi-agent systems is vitally important to many
emerging distributed applications - game theory has emerged as a powerful tool
set in which to do so. The main approach of game-theoretic techniques is to
model agents as players in a game, and predict the emergent behavior through
the relevant Nash equilibrium. The virtue from this viewpoint is that by
assuming that self-interested decision-making processes lead to Nash
equilibrium, system behavior can then be captured by Nash equilibrium without
studying the decision-making processes explicitly. This approach has seen
success in a wide variety of domains, such as sensor coverage, traffic
networks, auctions, and network coordination. However, in many other problem
settings, Nash equilibrium are not necessarily guaranteed to exist or emerge
from self-interested processes. Thus the main focus of the paper is on the
study of sink equilibrium, which are defined as the attractors of these
decision-making processes. By classifying system outcomes through a global
objective function, we can analyze the resulting approximation guarantees that
sink equilibrium have for a given game. Our main result is an approximation
guarantee on the sink equilibrium through defining an introduced metric of
misalignment, which captures how uniform agents are in their self-interested
decision making. Overall, sink equilibrium are naturally occurring in many
multi-agent contexts, and we display our results on their quality with respect
to two practical problem settings.
