Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions

Abstract

We consider the following class of problems. The value of an outcome to a society is measured via a submodular utility function (submodularity has a natural economic interpretation: decreasing marginal utility). Decisions, however, are controlled by non-cooperative agents who seek to maximise their own private utility. We present, under basic assumptions, guarantees on the social performance of Nash equilibria. For submodular utility functions, any Nash equilibrium gives an expected social utility within a factor 2 of optimal, subject to a function-dependent additive term. For non-decreasing, submodular utility functions, any Nash equilibrium gives an expected social utility within a factor 1+/spl delta/ of optimal, where 0/spl les//spl delta//spl les/1 is a number based upon discrete curvature of the function. A condition under which all sets of social and private utility functions induce pure strategy Nash equilibria is presented. The case in which agents themselves make use of approximation algorithms in decision making is discussed and performance guarantees given. Finally we present specific problems that fall into our framework. These include competitive versions of the facility location problem and k-median problem, a maximisation version of the traffic routing problem studied by Roughgarden and Tardos (2000), and multiple-item auctions.