In game theory, an aggregative game (AG), sometimes called a summarization game, is a game in which every player's payoff is a function of the player's own strategy and the aggregate of all players’ strategies. The concept was first proposed by Nobel laureate Reinhard Selten in 1970.
Definitions Consider a standard non-cooperative game with n players, where the set of strategies (actions) available to each player i is denoted by Si. The set of all possible strategy profiles is denoted by . Each player i has a payoff function and .
Simple aggregative game In the simplest setting studied in the context of aggregative games, Si is assumed to be one-dimensional, . That is, the game amounts to each player choosing a number simultaneously with the others. The game is called an aggregative game if for each player i there exists a function such that for all :
In words, payoff functions in aggregative games depend on players' own strategies and the aggregate .
Generalized aggregative game The definition can be generalized by replacing the sum with an arbitrary increasing function. Formally, in a generalized aggregative game (with one-dimensional strategy sets), there exists a function and a function such that for all :.Usually, it is assumed that the aggregator function is additively separable, that is, where and . So,Obviously, any aggregative game is generalized aggregative as seen by taking .
Quasi-aggregative games The definition above can be further generalized by allowing each player to have a different aggregation function. This is called a quasi-aggregative game.. See also Jensen's book chapter on Aggregative games.
Multi-dimensional aggregators The aggregator can be multi-dimensional: , for some positive integer d. Each coordinate of the aggregator is assumed to be additively-separable, that is: where where and . This class of games generalizes both anonymous games and weighted congestion games:
In anonymous games, each player selects an action from a finite set, and the utility of each player depends only on his own action and on the number of players who chose each action. Here, d is the number of actions, and for each action k, is 1 if and 0 otherwise, and is the identity function. Hence, is the number of players who chose action k in profile s. In weighted congestion games, each player selects a subset of resources from a finite family of allowed subsets, and the utility of each player depends only on his own subset and on the total weight of players who choose each resource. Here, d is the number of resources, and for each resource k, is the weight of player j if and 0 otherwise, and is the identity function.
Example Consider the Cournot competition, where firm i has payoff/profit function , where:
is the inverse demand function - it maps the total supplied amount to the price of the product; is the cost function of firm i.
This is an aggregative game since where .
Some other natural examples of aggregative games are:
Public goods game - the utility of each player depends only on his own contribution to the public good, and on the total amount contributed by all players. Pollution game - the utility of each player depends on its own pollution level and on the total pollution level. Congestion game - the utility of each player depends on his own choice, and the aggregate congestion caused by others. Bertrand competition. Games of Budget-proposal aggregation.
Properties Generalized AGs (hence AGs) admit backward reply correspondences and in fact, is the most general class to do so. Backward reply correspondences, as well as the closely related share correspondences, are powerful analytical tools in game theory. For example, backward reply correspondences were used to give the first general proof of the existence of a Nash equilibrium in the Cournot model without assuming quasiconcavity of firms' profit functions. Backward reply correspondences also play a crucial role for comparative statics analysis (see below). Quasi-AGs (hence generalized AGs, hence AGs) are best-response potential games if best-response correspondences are either increasing or decreasing. Precisely as games with strategic complementarities, such games therefore have a pure strategy Nash equilibrium regardless of whether payoff functions are quasiconcave and/or strategy sets are convex. The existence proof of Novshek for a Cournot equilibrium is a special case of such more general existence results. AGs have strong comparative statics properties. Under very general conditions one can predict how a change in exogenous parameters will affect the Nash equilibria..
History of terms and results
One-dimensional strategy sets, one-dimensional aggregators AGs were first studied under the assumption that the players' strategy sets are one-dimensional (each player chooses a number), and the aggregator function is also one-dimensional (returns a number).
Dubey, Mas-Collel and Shubik (1980) presented the "Aggregation Axiom": each player's utility depends on the player's action and the sum of all players' actions.
Corchon (1994) introduced the term "aggregative game" to mean a game that satisfies this aggregation axiom. He studied one-dimensional AGs in which the best-response function of each player is decreasing in the sum of actions --- a situation called strategic substitutes. Moreover, he required a stronger condition: the utility function of each player should be continuously differentiable, strictly decreasing in the sum of players' actions, and strictly concave in both variables. Under these assumptions, he proved some comparative statics results, such as, when new players enter, the strategy of each player decreases, the sum of strategies increases, and the payoff of each player decreases. He proved that strategic substitution alone, without the strong concavity assumption, is insufficient.
Kukushkin (1994), refining a previous result by Novshek (1985), studied one-dimensional AGs in which the best-response correspondence of each player has a selection that is a decreasing function (a condition called weak strategic substitute). He proved that such games always have a PNE. The proof proceeds in three propositions: (1) for a special case that the strategies of each player are integers in the interval [0,m]; (2) for a more general case that the strategies are arbitrary integers; (3) for the most general case that the strategies are real numbers. He claims that Proposition 1 can be easily adapted to multi-dimensional strategy sets.
Kukushkin (2004), studied one-dimensional AGs where the strategy sets are finite subsets of R. He proved that, if one of three single crossing conditions is satisfied, then every best response improvement path leads to a NE.
Dubey, Haimanko and Zapecheinyuk (2006) studied one-dimensional AGs with weak strategic substitutes or weak strategic complements. They proved that all these games are pseudo-potential games, and therefore have a PNE. When the strategy sets are finite, and the utilities are generic, the best response is unique. Hence, a pseudo-potential is a best-response potential; hence, every best-response sequence converges to a PNE in finite time. They show that their results can be extended to more general aggregation functions: not only sums, but also weighted sums of products. They also extend their results to some classes of discontinuous best-reply functions, which include some aggregative games with indivisibilities.
Dindos and Mezzetti (2006) studied one-dimensional AGs with quasiconcave utilities. They showed that the better-reply dynamics converges globally to a Nash equilibrium if actions are either strategic substitutes or strategic complements for all players around each asymptotically-stable equilibrium. In contrast, if the derivatives of the best-reply functions have different signs, then the better-reply dynamics might not converge even with two players. They assumed that the player who deviates, as well as the improving strategy he deviates too, are determined randomly.
Cornes and Hartley (2012) generalized one-dimensional AGs by allowing the utility of each player to depend on his own action and on an arbitrary aggregation function of the others' actions (same aggregation function to all players), instead of the sum. In addition, they assumed that the marginal utility of each player (that is, the derivative of ui w.r.t. the strategy of i) also depends on his own action and on the same aggregation function. They call such games fully aggregative games. They show that every such game with three or more players is equivalent to an aggregative game in which the aggregator is a simple sum.
Jensen (2018) studied a more general notion called quasi-aggregation, where each player may have a different aggregator function, but still with one-dimensional strategy sets. He proved that every quasi-aggregative game satisfying certain assumptions has a best-response potential function or a best-response pseudo-potential function, and therefore has a PNE. Moreover, every reasonable sequence of improvement paths converges to a PNE.
Kearns and Mansour (2002) assume that each player can choose one of two actions "0" or "1" (they say their results are easily generalizable to a finite set of actions). The utility of each player depends only on his own action and some global summarization function, which is allowed to be asymmetric and non-linear (they use the term summarization game instead of aggregative game). They also assume that (a) each player has a bounded influence on the summarization function; (b) the utility functions are continuous and have bounded derivatives; (c) the summarization function and payoff functions are computable in unit time. Under these assumptions, they present polytime algorithms for computing and learning approximate Nash equilibria. They also compute the rates of convergence as a function of the influence bound, the derivatives of utility functions, and the population size.
Babichenko (2013) assume that each player can choose any real number in [0,1]. The utility of each player depends only on his own action and some aggregator function (the same for all players). He assumes that the aggregator function is Lipschitz continuous w.r.t. the individual actions, and each utility function is Lipschitz continuous w.r.t. the aggregator, which means that each player has a bounded influence on the aggregation and on the utilities of others. He calls such game quasi-aggregative. He presents a best-reply dynamic that converges to approximate NE in O(n log n) steps.
Siddharth Barman and Katrina Ligett (2015) presented a polytime algorithm for computing an approximate correlated equilibrium with near-optimal welfare in aggregative games.
One-dimensional strategy sets, multi-dimensional aggregators Cummings, Kearns, Roth and Wu (2015) study AGs with finite strategy sets --- each player can choose an action from a set of m actions. They allow the aggregator to be multi-dimensional. This class of games generalizes both anonymous games and weighted congestion games. They present an algorithm, based on a weak mediator, that converges in polynomial time to an asymptotic Nash equilibrium, when the population is large. The algorithm for computing the weak mediator runs in time polynomial in the number of players and actions, but exponential in the number of dimensions of the aggregator. They use tools from differential privacy.
Multi-dimensional strategy sets In the most general setting, both the strategy sets and the aggregator output can be multi-dimensional.