  Game theoretic approaches have gained traction as robust methodologies for
designing distributed local algorithms that induce a desired overall system
configuration in multi-agent settings. However, much of the emphasis in these
approaches is on providing asymptotic guarantees on the performance of a
network of agents, and there is a gap in the study of efficiency guarantees
along transients of these distributed algorithms. Therefore, in this paper, we
study the transient efficiency guarantees of a natural game-theoretic algorithm
in the class of set covering games, which have been used to model a variety of
applications. Our main results characterize the optimal utility design that
maximizes the guaranteed efficiency along the transient of the natural
dynamics. Furthermore, we characterize the Pareto-optimal frontier with regards
to guaranteed efficiency in the transient and the asymptote under a class of
game-theoretic designs. Surprisingly, we show that there exists an extreme
trade-off between the long-term and short-term guarantees in that an
asymptotically optimal game-theoretic design can perform arbitrarily bad in the
transient.
