Games with continuous strategy sets arise in several machine learning problems (e.g. adversarial learning). For such games, simple no-regret learning algorithms exist in several cases and ensure convergence to coarse correlated equilibria (CCE). The efficiency of such equilibria with respect to a social function, however, is not well understood. In this paper, we define the class of valid utility games with continuous strategies and provide efficiency bounds for their CCEs. Our bounds rely on the social function being a monotone DR-submodular function. We further refine our bounds based on the curvature of the social function. Furthermore, we extend our efficiency bounds to a class of non-submodular functions that satisfy approximate submodularity properties. Finally, we show that valid utility games with continuous strategies can be designed to maximize monotone DR-submodular functions subject to disjoint constraints with approximation guarantees. The approximation guarantees we derive are based on the efficiency of the equilibria of such games and can improve the existing ones in the literature. We illustrate and validate our results on a budget allocation game and a sensor coverage problem.
In the context of distributed optimization, where a game is designed to optimize a given objective @cite_12 , bounds on the robust price of anarchy find a similar importance. In this setting, a distributed scheme to optimize the social function is to let each player implement a no-regret learning algorithm based only on its payoff information. A bound on the robust PoA provides an approximation guarantee to such optimization scheme.
@cite_12
2133243407 2030208840 2131832787 2070394877
The price of anarchy (POA) is a worst-case measure of the inefficiency of selfish behavior, defined as the ratio of the objective function value of a worst Nash equilibrium of a game and that of an optimal outcome. This measure implicitly assumes that players successfully reach some Nash equilibrium. This drawback motivates the search for inefficiency bounds that apply more generally to weaker notions of equilibria, such as mixed Nash and correlated equilibria; or to sequences of outcomes generated by natural experimentation strategies, such as successive best responses or simultaneous regret-minimization. We prove a general and fundamental connection between the price of anarchy and its seemingly stronger relatives in classes of games with a sum objective. First, we identify a "canonical sufficient condition" for an upper bound of the POA for pure Nash equilibria, which we call a smoothness argument. Second, we show that every bound derived via a smoothness argument extends automatically, with no quantitative degradation in the bound, to mixed Nash equilibria, correlated equilibria, and the average objective function value of regret-minimizing players (or "price of total anarchy"). Smoothness arguments also have automatic implications for the inefficiency of approximate and Bayesian-Nash equilibria and, under mild additional assumptions, for bicriteria bounds and for polynomial-length best-response sequences. We also identify classes of games --- most notably, congestion games with cost functions restricted to an arbitrary fixed set --- that are tight, in the sense that smoothness arguments are guaranteed to produce an optimal worst-case upper bound on the POA, even for the smallest set of interest (pure Nash equilibria). Byproducts of our proof of this result include the first tight bounds on the POA in congestion games with non-polynomial cost functions, and the first structural characterization of atomic congestion games that are universal worst-case examples for the POA. This paper explains when and how communication and computational lower bounds for algorithms for an optimization problem translate to lower bounds on the worst-case quality of equilibria in games derived from the problem. We give three families of lower bounds on the quality of equilibria, each motivated by a different set of problems: congestion, scheduling, and distributed welfare games, welfare-maximization in combinatorial auctions with "black-box" bidder valuations, and welfare-maximization in combinatorial auctions with succinctly described valuations. The most straightforward use of our lower bound framework is to harness an existing computational or communication lower bound to derive a lower bound on the worst-case price of anarchy (POA) in a class of games. This is a new approach to POA lower bounds, which relies on reductions in lieu of explicit constructions. More generally, the POA lower bounds implied by our framework apply to all classes of games that share the same underlying optimization problem, independent of the details of players' utility functions. For this reason, our lower bounds are particularly significant for problems of game design--ranging from the design of simple combinatorial auctions to the computation of tolls for routing networks--where the goal is to design a game that has only near-optimal equilibria. For example, our results imply that the simultaneous first-price auction format is optimal among all "simple combinatorial auctions" in several settings. We study a network security game where strategic players choose their investments in security. Since a player's investment can reduce the propagation of computer viruses, a key feature of the game is the positive externality exerted by the investment. With selfish players, unfortunately, the overall network security can be far from optimum. The contributions of this paper are as follows. 1) We first characterize the price of anarchy (POA) in the strategic-form game under an “Effective-investment” model and a “Bad-traffic” model, and give insight on how the POA depends on individual players' cost functions and their mutual influence. We also introduce the concept of “weighted POA” to bound the region of payoff vectors. 2) In a repeated game, players have more incentive to cooperate for their long term interests. We consider the socially best outcome that can be supported by the repeated game, as compared to the social optimum. 3) Next, we compare the benefits of improving security technology and improving incentives, and show that improving technology alone may not offset the price of anarchy. 4) Finally, we characterize the performance of correlated equilibrium (CE). Although the paper focuses on network security, many results are generally applicable to games with positive externalities . We resolve the worst-case price of anarchy (POA) of atomic splittable congestion games. Prior to this work, no tight bounds on the POA in such games were known, even for the simplest non-trivial special case of affine cost functions. We make two distinct contributions. On the upper-bound side, we define the framework of "local smoothness", which refines the standard smoothness framework for games with convex strategy sets. While standard smoothness arguments cannot establish tight bounds on the POA in atomic splittable congestion games, we prove that local smoothness arguments can. Further, we prove that every POA bound derived via local smoothness applies automatically to every correlated equilibrium of the game. Unlike standard smoothness arguments, bounds proved using local smoothness do not always apply to the coarse correlated equilibria of the game. Our second contribution is a very general lower bound: for every set L that satisfies mild technical conditions, the worst-case POA of pure Nash equilibria in atomic splittable congestion games with cost functions in L is exactly the smallest upper bound provable using local smoothness arguments. In particular, the worst-case POA of pure Nash equilibria, mixed Nash equilibria, and correlated equilibria coincide in such games.