In game theory, an aggregative game (AG),[1] sometimes called a summarization game,[2] 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.[3]
Definitions
editConsider 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
editIn 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
editThe definition can be generalized by replacing the sum with an arbitrary increasing function.[4] 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
editThe definition above can be further generalized by allowing each player to have a different aggregation function. This is called a quasi-aggregative game.[5][6][7]
Multi-dimensional aggregators
editThe aggregator can be multi-dimensional: , for some positive integer d. Each coordinate of the aggregator is assumed to be additively-separable, that is:[8]
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
editConsider 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.[clarification needed]
- Pollution game[9] - the utility of each player depends on its own pollution level and on the total pollution level.[clarification needed]
- Congestion game - the utility of each player depends on his own choice, and the aggregate congestion caused by others.[clarification needed]
- Bertrand competition.[5] : 5.1
Properties
edit- Generalized AGs (hence AGs) admit backward reply correspondences and in fact, is the most general class to do so.[4] 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.[10] 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.[11][7] 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[10] 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.[1][12]
History of terms and results
editOne-dimensional strategy sets, one-dimensional aggregators
editAGs 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)[13] presented the "Aggregation Axiom": each player's utility depends on the player's action and the sum of all players' actions.
Corchon (1994)[1] 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),[14] refining a previous result by Novshek (1985),[15] 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),[16] 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)[11] 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.[11]: Sec.4 They show that their results can be extended to more general aggregation functions: not only sums, but also weighted sums of products.[11]: Sec.5 They also extend their results to some classes of discontinuous best-reply functions, which include some aggregative games with indivisibilities.[11]: Sec.6
Dindos and Mezzetti (2006)[17] 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)[4] 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)[5] 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)[2] 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)[18] 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)[19] presented a polytime algorithm for computing an approximate correlated equilibrium with near-optimal welfare in aggregative games.
One-dimensional strategy sets, multi-dimensional aggregators
editCummings, Kearns, Roth and Wu (2015)[8] 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
editIn the most general setting, both the strategy sets and the aggregator output can be multi-dimensional.
Jensen (2005)[20] studied AGs in which the strategy set of each agent i is a d-dimensional box in R^d, for some d ≥ 1. He required the aggregator to be "separable" in the sense that each coordinate of the aggregator depends on different coordinates of strategy profile; in particular, this implies that the aggregator has at most d coordinates. He proved that, if such a game has strategic substitutes and satisfies some other technical conditions, then it has a PNE. He also analyzes the structure of the set of PNE, their comparative statics, and sufficient conditions for uniqueness and stability.
Jensen (2010)[7] also studied AGs with multi-dimensional strategy sets. He extended the definition by allowing each player to have a different aggregator function. He named the extended notion "quasi-aggregative game". He proved that, under certain technical assumptions, such games have best-response potential functions, and thus the best-response dynamics converges to a PNE.
Parise, Grammatico, Gentile and Lygeros (2015[21]-2020[22]) study network AGs --- a variant in which the utility of each agent depends on his own strategy and on an aggregate function of his neighbors in the network (in the earlier version[21] they assume that the players' dis-utility functions are quadratic). The strategy sets are multi-dimensional. They present a class of distributed algorithms that are guaranteed to converge to a PNE, both for network aggregative games and for classic aggregative games (where the utility of each player depends on the sum of all other players' actions), under different sufficient conditions depending on the utillity functions and the communication network. Their algorithms in both cases require only local communication.
Xu, Chen, Qi and Hong (2023)[23] present a distributed algorithm for multi-dimensional AGs; they show that their algorithm has linear convergence. However, it converges to an approximate PNE, not to the exact PNE.
Deng and Nian (2018)[24] study AGs over weight-balanced digraphs. Players have constraint sets coupled by linear constraints. Players have first-order dynamics and are influenced by exogenous disturbances. For the case of smooth utility functions, they present a distributed continuous-time algorithm for finding the variational generalized NE.[clarification needed] Their algorithm uses gradient descent, internal model and dynamic average consensus. They prove that their algorithm converges exponentially[clarification needed] to the variational generalized NE. Later, Deng and Nian (2020)[25] they study non-smooth utility functions. They present another continuous-time algorithm that converges asymptotically, but without guarantees in its convergence rate. Deng (2022)[26] extends these results to players with second-order dynamics,[clarification needed] but no constraints on the strategy sets. He presents two continuous-time algorithms with exponential convergece rates.
Wang, Chen, Chen, Lian and Wang[27] extend the above works to weight-unbalanced digraphs; they, too, develop continuous-time algorithms with exponential convergence.
Li, Li, Rang, Zheng and Huang (2025)[28] survey distributed algorithms for aggregative games with multi-dimensional strategy sets. Importantly, they assume that there is a fixed undirected network that describes the possible connections between players, and each player can communicate only with its neighbors in the network.
Wang and Nedic (2024)[29] present a distributed and privacy-preserving algorithm for computing a NE in an aggregative game over a network. In their model, the strategy sets are multi-dimensional - compact and convex subsets of Rd. The aggregator function is the arithmetic mean (or the sum) of all strategy vectors. The utility functions are continuously differentiable, and they are concave functions of the player's action (equivalently, the cost is a convex function of the player's action). Their algorithm guarantees both a finite "privacy budget" and accurate convergence.
Mean field games
editMean field game can be seen as the limit of an aggregative game when the number of players goes to infinity. Thus, the effect of each player on the aggregate is negligible.
Acemoglu and Jensen (2010)[30] generalized aggregative games to allow for infinitely many players, in which case the aggregator will typically be an integral rather than a linear sum.
Grammatico, Parise, Colombino and Lygeros (2016)[31] present distributed algorithms for computing PNE in mean-field games. Their main contribution over previous work is that they allow agents to have different constraints (as long as the constraint set of each agent is convex). They present a decentralized algorithm for computing a mean field PNE.
See also
editNotes
edit- ^ a b c Corchón, Luis C. (1994-12-01). "Comparative statics for aggregative games the strong concavity case". Mathematical Social Sciences. 28 (3): 151–165. doi:10.1016/0165-4896(94)90001-9. ISSN 0165-4896.
- ^ a b Kearns, Michael; Mansour, Yishay (2012-12-12). "Efficient Nash Computation in Large Population Games with Bounded Influence". arXiv:1301.0577 [cs.GT].
- ^ Selten, Reinhard (1970). Preispolitik der Mehrproduktenunternehmung in der statischen Theorie. Ökonometrie und Unternehmensforschung / Econometrics and Operations Research. Vol. 16. doi:10.1007/978-3-642-48888-7. ISBN 978-3-642-48889-4. ISSN 0078-3390.
- ^ a b c Cornes, R.; Harley, R. (2012). "Fully Aggregative Games". Economics Letters. Vol. 116. pp. 631–633.
- ^ a b c Jensen, Martin (2018), "Aggregative games", Handbook of Game Theory and Industrial Organization, Volume I, Edward Elgar Publishing, pp. 66–92, retrieved 2025-08-16
- ^ http://www.socscistaff.bham.ac.uk/jensen/AggGames-RC3.pdf
- ^ a b c Jensen, M.K. (2010). "Aggregative Games and Best-Reply Potentials". Economic Theory. 43: 45–66. doi:10.1007/s00199-008-0419-8.. See also Jensen's book chapter on Aggregative games.
- ^ a b Cummings, Rachel; Kearns, Michael; Roth, Aaron; Wu, Zhiwei Steven (2015). "Privacy and Truthful Equilibrium Selection for Aggregative Games". In Markakis, Evangelos; Schäfer, Guido (eds.). Web and Internet Economics. Lecture Notes in Computer Science. Vol. 9470. Berlin, Heidelberg: Springer. pp. 286–299. doi:10.1007/978-3-662-48995-6_21. ISBN 978-3-662-48995-6.
- ^ Benchekroun, Hassan; Martín-Herrán, Guiomar (2016-05-16). "The impact of foresight in a transboundary pollution game". European Journal of Operational Research. 251 (1): 300–309. doi:10.1016/j.ejor.2015.11.014. ISSN 0377-2217.
- ^ a b Novshek, W. (1985). "On the Existence of Cournot Equilibrium". Review of Economic Studies. Vol. 52. pp. 86–98.
- ^ a b c d e Dubey, Pradeep; Haimanko, Ori; Zapechelnyuk, Andriy (2006-01-01). "Strategic complements and substitutes, and potential games". Games and Economic Behavior. 54 (1): 77–94. doi:10.1016/j.geb.2004.10.007. ISSN 0899-8256.
- ^ Acemoglu, D.; Jensen, M.K. (2013). "Aggregate Comparative Statics". Games and Economic Behavior. Vol. 81. pp. 27–49..
- ^ Dubey, Pradeep; Mas-Colell, Andreau; Shubik, Martin (1980-04-01). "Efficiency properties of strategies market games: An axiomatic approach". Journal of Economic Theory. 22 (2): 339–362. doi:10.1016/0022-0531(80)90047-2. ISSN 0022-0531.
- ^ Kukushkin, Nikolai S. (1994-09-01). "A fixed-point theorem for decreasing mappings". Economics Letters. 46 (1): 23–26. doi:10.1016/0165-1765(94)90072-8. ISSN 0165-1765.
- ^ Novshek, William (January 1985). "On the Existence of Cournot Equilibrium". The Review of Economic Studies. 52 (1): 85–98. doi:10.2307/2297471. ISSN 0034-6527. JSTOR 2297471. Archived from the original on 2024-04-06.
- ^ Kukushkin, Nikolai S. (2004-07-01). "Best response dynamics in finite games with additive aggregation". Games and Economic Behavior. 48 (1): 94–110. doi:10.1016/j.geb.2003.06.007. ISSN 0899-8256.
- ^ Dindoš, Martin; Mezzetti, Claudio (2006-02-01). "Better-reply dynamics and global convergence to Nash equilibrium in aggregative games". Games and Economic Behavior. 54 (2): 261–292. doi:10.1016/j.geb.2004.12.001. ISSN 0899-8256.
- ^ Yakov, Babichenko (28 January 2013). "Best-Reply Dynamic in Large Aggregative Games". SSRN 2210080.
- ^ Barman, Siddharth; Ligett, Katrina (2015-11-12). "Finding any nontrivial coarse correlated equilibrium is hard". SIGecom Exch. 14 (1): 76–79. doi:10.1145/2845926.2845929.
- ^ http://www.socscistaff.bham.ac.uk/jensen/AggGames-RC3.pdf
- ^ a b Parise, Francesca; Gentile, Basilio; Grammatico, Sergio; Lygeros, John (December 2015). "Network aggregative games: Distributed convergence to Nash equilibria". 2015 54th IEEE Conference on Decision and Control (CDC). pp. 2295–2300. doi:10.1109/CDC.2015.7402549. ISBN 978-1-4799-7886-1.
- ^ Parise, Francesca; Grammatico, Sergio; Gentile, Basilio; Lygeros, John (2020-07-01). "Distributed convergence to Nash equilibria in network and average aggregative games". Automatica. 117 108959. doi:10.1016/j.automatica.2020.108959. ISSN 0005-1098.
- ^ Parise, Francesca; Grammatico, Sergio; Gentile, Basilio; Lygeros, John (2020-07-01). "Distributed convergence to Nash equilibria in network and average aggregative games". Automatica. 117 108959. doi:10.1016/j.automatica.2020.108959. ISSN 0005-1098.
- ^ Deng, Zhenhua; Nian, Xiaohong (2018). "Distributed algorithm design for aggregative games of disturbed multiagent systems over weight-balanced digraphs". International Journal of Robust and Nonlinear Control. 28 (17): 5344–5357. doi:10.1002/rnc.4316. ISSN 1099-1239.
- ^ Deng, Zhenhua; Nian, Xiaohong (March 2019). "Distributed Generalized Nash Equilibrium Seeking Algorithm Design for Aggregative Games Over Weight-Balanced Digraphs". IEEE Transactions on Neural Networks and Learning Systems. 30 (3): 695–706. Bibcode:2019ITNNL..30..695D. doi:10.1109/TNNLS.2018.2850763. ISSN 2162-2388. PMID 30047905.
- ^ Deng, Zhenhua (2022-01-01). "Distributed Nash equilibrium seeking for aggregative games with second-order nonlinear players". Automatica. 135 109980. doi:10.1016/j.automatica.2021.109980. ISSN 0005-1098.
- ^ Wang, Dong; Chen, Pan; Chen, Mingfei; Lian, Jie; Wang, Wei (2022-01-01). "Distributed Nash Equilibrium Seeking for Aggregative Games over Weight-Unbalanced Digraphs". IFAC-PapersOnLine. 16th IFAC Symposium on Large Scale Complex Systems: Theory and Applications LSS 2022. 55 (3): 90–95. doi:10.1016/j.ifacol.2022.05.016. ISSN 2405-8963.
- ^ Li, Huaqing; Li, Jun; Ran, Liang; Zheng, Lifeng; Huang, Tingwen (May 2025). "A Survey of Distributed Algorithms for Aggregative Games". IEEE/CAA Journal of Automatica Sinica. 12 (5): 859–871. Bibcode:2025ICJAS..12..859L. doi:10.1109/JAS.2024.124998. ISSN 2329-9274.
- ^ Wang, Yongqiang; Nedić, Angelia (August 2024). "Differentially Private Distributed Algorithms for Aggregative Games With Guaranteed Convergence". IEEE Transactions on Automatic Control. 69 (8): 5168–5183. arXiv:2209.01486. Bibcode:2024ITAC...69.5168W. doi:10.1109/TAC.2024.3351068. ISSN 1558-2523.
- ^ Acemoglu, D.; Jensen, M.K. (2010). "Robust Comparative Statics in Large Static Games". IEEE Proceedings on Decision and Control. Vol. 49. pp. 3133–3139.
- ^ Grammatico, Sergio; Parise, Francesca; Colombino, Marcello; Lygeros, John (November 2016). "Decentralized Convergence to Nash Equilibria in Constrained Deterministic Mean Field Control". IEEE Transactions on Automatic Control. 61 (11): 3315–3329. arXiv:1410.4421. Bibcode:2016ITAC...61.3315G. doi:10.1109/TAC.2015.2513368. ISSN 1558-2523.
- ^ https://www.research-collection.ethz.ch/bitstreams/5d78a74c-8d00-41d0-a6e6-575fa239cb61/download
- ^ Xu, Gehui; Chen, Guanpu; Qi, Hongsheng; Hong, Yiguang (July 2023). "Efficient Algorithm for Approximating Nash Equilibrium of Distributed Aggregative Games". IEEE Transactions on Cybernetics. 53 (7): 4375–4387. arXiv:2108.12142. Bibcode:2023ITCyb..53.4375X. doi:10.1109/TCYB.2022.3175831. ISSN 2168-2275. PMID 35635831.
- ^ Fabiani, Filippo; Margellos, Kostas; Goulart, Paul J. (December 2020). "On the robustness of equilibria in generalized aggregative games". 2020 59th IEEE Conference on Decision and Control (CDC). pp. 3725–3730. arXiv:2005.09408. doi:10.1109/CDC42340.2020.9304348. ISBN 978-1-7281-7447-1.