  The design of distributed algorithms is central to the study of multiagent
systems control. In this paper, we consider a class of combinatorial
cost-minimization problems and propose a framework for designing distributed
algorithms with a priori performance guarantees that are near-optimal. We
approach this problem from a game-theoretic perspective, assigning agents cost
functions such that the equilibrium efficiency (price of anarchy) is optimized.
Once agents' cost functions have been specified, any algorithm capable of
computing a Nash equilibrium of the system inherits a performance guarantee
matching the price of anarchy. Towards this goal, we formulate the problem of
computing the price of anarchy as a tractable linear program. We then present a
framework for designing agents' local cost functions in order to optimize for
the worst-case equilibrium efficiency. Finally, we investigate the implications
of our findings when this framework is applied to systems with convex,
nondecreasing costs.
