Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEfficient Estimation of Equilibria in Large Aggregative Games with Coupling Constraints
85
0
0.0
(
0
)
Added by
Paulin Jacquot Dr
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Authors
Paulin Jacquot
Ask ChatGPT about the research
No Arabic abstract
Aggregative games have many industrial applications, and computing an equilibrium in those games is challenging when the number of players is large. In the framework of atomic aggregative games with coupling constraints, we show that variational Nash equilibria of a large aggregative game can be approximated by a Wardrop equilibrium of an auxiliary population game of smaller dimension. Each population of this auxiliary game corresponds to a group of atomic players of the initial large game. This approach enables an efficient computation of an approximated equilibrium, as the variational inequality characterizing the Wardrop equilibrium is of smaller dimension than the initial one. This is illustrated on an example in the smart grid context.
rate research
Read More
This paper shows the existence of $mathcal{O}(frac{1}{n^gamma})$-Nash equilibria in $n$-player noncooperative aggregative games where the players cost functions depend only on their own action and the average of all the players actions, and is lower semicontinuous in the former while $gamma$-H{o}lder continuous in the latter. Neither the action sets nor the cost functions need to be convex. For an important class of aggregative games which includes congestion games with $gamma$ being 1, a proximal best-reply algorithm is used to construct an $mathcal{O}(frac{1}{n})$-Nash equilibria with at most $mathcal{O}(n^3)$ iterations. These results are applied in a numerical example of demand-side management of the electricity system. The asymptotic performance of the algorithm is illustrated when $n$ tends to infinity.
We consider polymatrix coordination games with individual preferences where every player corresponds to a node in a graph who plays with each neighbor a separate bimatrix game with non-negative symmetric payoffs. In this paper, we study $alpha$-approximate $k$-equilibria of these games, i.e., outcomes where no group of at most $k$ players can deviate such that each member increases his payoff by at least a factor $alpha$. We prove that for $alpha ge 2$ these games have the finite coalitional improvement property (and thus $alpha$-approximate $k$-equilibria exist), while for $alpha < 2$ this property does not hold. Further, we derive an almost tight bound of $2alpha(n-1)/(k-1)$ on the price of anarchy, where $n$ is the number of players; in particular, it scales from unbounded for pure Nash equilibria ($k = 1)$ to $2alpha$ for strong equilibria ($k = n$). We also settle the complexity of several problems related to the verification and existence of these equilibria. Finally, we investigate natural means to reduce the inefficiency of Nash equilibria. Most promisingly, we show that by fixing the strategies of $k$ players the price of anarchy can be reduced to $n/k$ (and this bound is tight).
We address the problem of assessing the robustness of the equilibria in uncertain, multi-agent games. Specifically, we focus on generalized Nash equilibrium problems in aggregative form subject to linear coupling constraints affected by uncertainty with a possibly unknown probability distribution. Within a data-driven context, we apply the scenario approach paradigm to provide a-posteriori feasibility certificates for the entire set of generalized Nash equilibria of the game. Then, we show that assessing the violation probability of such set merely requires to enumerate the constraints that ``shape it. For the class of aggregative games, this results in solving a feasibility problem on each active facet of the feasibility region, for which we propose a semi-decentralized algorithm. We demonstrate our theoretical results by means of an academic example.
In this paper we extend a popular non-cooperative network creation game (NCG) to allow for disconnected equilibrium networks. There are n players, each is a vertex in a graph, and a strategy is a subset of players to build edges to. For each edge a player must pay a cost alpha, and the individual cost for a player represents a trade-off between edge costs and shortest path lengths to all other players. We extend the model to a penalized game (PCG), for which we reduce the penalty counted towards the individual cost for a pair of disconnected players to a finite value beta. Our analysis concentrates on existence, structure, and cost of disconnected Nash and strong equilibria. Although the PCG is not a potential game, pure Nash equilibria always and pure strong equilibria very often exist. We provide tight conditions under which disconnected Nash (strong) equilibria can evolve. Components of these equilibria must be Nash (strong) equilibria of a smaller NCG. However, in contrast to the NCG, for almost all parameter values no tree is a stable component. Finally, we present a detailed characterization of the price of anarchy that reveals cases in which the price of anarchy is Theta(n) and thus several orders of magnitude larger than in the NCG. Perhaps surprisingly, the strong price of anarchy increases to at most 4. This indicates that global communication and coordination can be extremely valuable to overcome socially inferior topologies in distributed selfish network design.
We propose a simple uncertainty modification for the agent model in normal-form games; at any given strategy profile, the agent can access only a set of possible profiles that are within a certain distance from the actual action profile. We investigate the various instantiations in which the agent chooses her strategy using well-known rationales e.g., considering the worst case, or trying to minimize the regret, to cope with such uncertainty. Any such modification in the behavioral model naturally induces a corresponding notion of equilibrium; a distance-based equilibrium. We characterize the relationships between the various equilibria, and also their connections to well-known existing solution concepts such as Trembling-hand perfection. Furthermore, we deliver existence results, and show that for some class of games, such solution concepts can actually lead to better outcomes.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
