WorksComputer Science
Fair Selection of Generalized Nash Equilibria: A Comparability Perspective
Abstract
Generalized Nash equilibrium (GNE) problems model self-interested agents coupled through their costs and shared constraints, and arise throughout control applications that allocate a scarce common resource. Such problems typically admit a continuum of equilibria, so any implementation must select one. This selection is not neutral: it decides how the cost of the shared constraint is distributed among the agents, a decision often expected to be fair. The variational GNE (v-GNE), which charges all agents a uniform shadow price, is the conventional choice and is frequently advocated as fair. Through the lens of comparability from social choice theory, we show that the GNE set itself requires no inter-agent comparability of costs, whereas the v-GNE implicitly assumes cardinal unit comparability, one of the stronger notions. We then introduce the fair GNE (f-GNE), which selects an equilibrium by explicitly optimizing a fairness metric matched to the comparability at hand, and give constructive routes to compute it for single-constraint and linear-quadratic games. An electric-vehicle charging game serves as a running example throughout this self-contained tutorial.
Introduction
Game theory provides a natural language to describe the interaction of multiple self-interested decision makers, or agents, each of whom minimizes their own cost. In the classical Nash equilibrium problem, the agents are coupled only through their cost functions: what one agent pays depends on what the others decide, but each agent is free to choose any action from their own decision set. In a generalized Nash equilibrium (GNE) problem, the agents are additionally coupled through shared constraints [16]: the set of decisions available to one agent depends on the decisions of the others. This seemingly technical extension is what makes the model expressive enough to capture the allocation of a shared but finite resource, where the joint decision of all agents must respect a common capacity limit, and whatever one agent consumes is unavailable to the rest.
This modeling feature is the reason why GNE problems appear throughout control applications that involve resource allocation. Examples include energy management and peer-to-peer energy trading [4, 10], electric vehicle charging [33], demand-side flexibility and electricity markets [7], communication and network resource allocation [2, 34], environmental resources such as shared water basins [26, 44], and interactive motion planning for autonomous vehicles [30]. In all of these settings, access to resources is increasingly controlled automatically by algorithms, often distributed through large-scale systems, and the individuals seeking access can be thought of as self-interested agents, each wanting to fulfill their needs at minimal cost.
A structural feature of generalized games, and the starting point of this chapter, is that they typically admit not one but infinitely many equilibria: the GNE solution set is in general a continuum, even under strong convexity assumptions on the individual costs [16]. This multiplicity is first of all a computational nuisance: most algorithms compute some GNE, and which equilibrium they converge to depends on their initialization [25, 15], so the properties of the implemented solution are difficult to characterize ex ante. But multiplicity also poses a more fundamental question, which is the subject of this chapter: among the many equilibria, which one should be selected and implemented?
Equilibrium selection is not a neutral act. Different GNEs distribute the burden of the coupling constraint differently: moving from one equilibrium to another decreases the cost of some agents and increases the cost of others. Whoever selects the equilibrium (a system operator, a market platform, a control algorithm) is therefore deciding, implicitly or explicitly, how costs are shared among the participants. Moreover, when the resource at stake is a public infrastructure or a natural resource, there is often an implicit societal mandate attached to this decision: the selection is expected to be justifiable as fair.
What does it mean for an allocation to be fair? A principled answer comes from consequentialist ethics through the doctrine of welfarism: moral rightness is determined by the maximization of aggregate welfare. The framework demands that individual interests be aggregated impartially, without privileging oneself or particular groups, and that the best action is the one that maximizes total welfare [22, 43]. Operationally, this stance reduces the question “what is fair?” to the choice of an aggregation function of the individual costs. Many such functions have been proposed and used in control: the utilitarian sum, the Rawlsian maximin, alpha fairness, and inequality indices such as Atkinson’s [1, 8], Theil’s [45], and Jain’s [24]; see [29, 47] for axiomatic and optimization-oriented overviews and [11, 46, 38] for control applications.
Within the GNE literature, the selection question has mostly been settled by convention in favor of the variational GNE (v-GNE): the refinement of the GNE in which all agents face the same Lagrange multiplier for the shared constraint, characterized as the solution of a variational inequality [16, 28]. The v-GNE owes its popularity to solid mathematical foundations: existence and uniqueness hold under broad assumptions [42, 16], fast semi-decentralized [39, 3] and fully-distributed [48, 9] algorithms are available, and efficiency bounds have been established [27, 10]. On top of these computational merits, the v-GNE is frequently advocated as the fair choice [14, 7, 2]: all agents are charged the same shadow price for the shared resource, whereas at a general GNE the shadow prices differ across agents, which is deemed unfair when individuals are anonymous or indistinguishable to the planner [28, 23]. This fairness claim is arguably not satisfactory. Equal prices are meaningful only if the quantities being priced, the agents’ marginal costs, are measured on comparable scales; if the cost functions are known only up to individual scalings (because they are self-reported, or elicited in heterogeneous units), the v-GNE allocation shifts in ways that are hard to justify. A detailed discussion of the limits of the v-GNE fairness paradigm is given in the conference paper [21].
This chapter deals with the constructive problem that this critique uncovers: how to select a GNE based on an explicit, intentional fairness criterion. The chapter is meant to be a self-contained tutorial on this fair selection problem, requiring no prior familiarity with GNE theory.
We approach the problem from a comparability angle, a notion studied in formal social choice theory [41, 12]. Comparability defines to what extent the costs incurred by different agents are commensurable. By deciding a level of comparability, a planner decides what information about the individual costs is relevant to the resource allocation problem. Conversely, a limited level of comparability can be seen as an invariance condition: it dictates what information about the individual costs (e.g., scale, offset) should not affect the resource allocation. See [43] for a general framework for comparability in control theory. Adequately modeling comparability is of course particularly crucial when optimizing for metrics such as fairness, equality, and equity: because only by defining a priori what can be considered “equal” can we optimize for any such metric meaningfully.
Through this lens, we show that the solution set of GNEs does not rely on cardinal comparability of the agents’ costs because of its very nature of being a set of competitive equilibria. However, v-GNEs require a restrictive notion of comparability, as they fundamentally and inevitably trade off costs: they are a coordinated decision, not the result of agents’ autonomous decisions. The fairness of the resulting tradeoff depends on whether the agents’ costs are unit-comparable. This difference between GNEs and v-GNEs has been pointed out in [16] and [13] as a matter of scale invariance, but it had not been connected to comparability or fairness.
Besides the conceptual analysis, the chapter presents a computational path to fair GNE selection. The selection problem is formulated as a bilevel program in which a fairness metric, chosen a priori and consistent with the comparability at hand, is optimized over the GNE set; we call the resulting solution concept the fair GNE (f-GNE). For the practically important class of games with a single coupling constraint, the GNE set admits a tractable parametric description that makes this bilevel problem solvable with standard tools. For linear-quadratic games, we go further and show, following the methodology of [20], that the f-GNE can be precomputed offline for all values of the problem parameters simultaneously (the quantities that vary between instances but are known at decision time, such as reference setpoints, prices, or the available charging capacity in the EV example) via multiparametric programming [5]. The degree to which this offline precomputation is possible depends on the fairness metric: for some metrics the result is an explicit solution map deployable in real time, while for others a residual online computation remains. This constructive analysis thereby reveals an interesting interplay between the comparability assumptions of a fairness metric and the computational tractability of the associated selection problem.
Throughout, we use an electric vehicle (EV) charging game as a running example, built up progressively from § 2 onward. § 2 introduces GNE and v-GNE definitions and the ladder of comparability notions. § 3 formally establishes the comparability requirements of GNE and v-GNE, showing that Nash equilibria require no comparability while v-GNEs require cardinal unit comparability. § 4 introduces the f-GNE concept, which selects from the GNE set by optimizing an explicit fairness metric. § 5 shows that the selection becomes tractable for games with a single coupling constraint, by parametrizing the GNE set through normalized equilibria. § 6 develops an offline algorithm for linear-quadratic games and discusses how the comparability requirements of a fairness metric relate to the computational tractability of the selection. § 7 applies the full framework to the EV charging game.
Competitive Equilibrium and Comparability
Generalized Nash Equilibrium Problems
Consider a set of self-interested agents each minimizing their cost function , which depends on their own decision and other agents’ decisions . We denote by the vector obtained by stacking all agents’ decisions, i.e., . Throughout, decisions are deterministic and equilibria are in pure strategies, the natural setting for continuous games with strongly convex costs. We will make the following assumption for the entire chapter.
Assumption 1 (Convex differentiable cost functions). The cost functions are strongly convex and continuously differentiable in , for every fixed .
Further, each agent’s feasible set
depends on the decisions of other agents through , yielding a set of coupled optimization problems:
Assumption 2 (Convex constraint sets). The sets are closed and convex and the constraint functions are continuously differentiable.
Decisions that jointly solve (2) are generalized Nash equilibria (GNE) [18 §2], as defined next.
Definition 1 (Generalized Nash Equilibrium). A joint decision is a GNE of (2) if :
with the solution set denoted as .
Intuitively, a GNE is a joint decision for which no agent can reduce its cost by unilaterally changing its own decision.
Running Example (EV Charging: Setup). Agent controls a charging action to reach a desired battery level at minimum cost . A finite total supply couples all agents via . The cost has two opposing components: a penalty for falling short of (incentivizing more charging) and a congestion price proportional to total demand (incentivizing less). Such a demand-dependent price models dynamic energy pricing schemes in which the unit price of electricity increases with aggregate demand to incentivize peak shaving, as proposed, e.g., in [32]. Agents thus compete both over the scarce capacity and over the shared congestion price. The shortfall penalty is quadratic, so the game is linear-quadratic; this structure is immaterial for the conceptual analysis of § 3–§ 5, which holds for general convex costs, but it will be exploited by the explicit algorithm of § 6. The full formulation of this GNE problem appears in § 7.
Under Assumptions 1 and 2, finding a GNE is equivalent to solving the quasi-variational inequality
where and . Equivalently, is a GNE if a suitable constraint qualification holds (e.g., the Mangasarian–Fromovitz or Slater’s condition) and if there exist multipliers such that the following KKT conditions hold:
Here denotes the complementarity condition, understood componentwise: for each constraint , , , and , so that a strictly positive multiplier marks an active (binding) constraint.
In control applications, the majority of works focuses on setups where the coupling constraints are jointly convex [16 Def. 3.6], i.e., the following additional assumption holds.
Assumption 3 (Jointly convex constraints). There exists a non-empty convex set such that .
Notice, in this case, the defining is the same across agents, , , with . Under Assumptions 1 and 3, the subclass of variational GNEs (v-GNEs) can be defined.
Definition 2 (Variational GNE). Consider the GNE problem (2), and let Assumptions 1 and 3 hold. The joint decision is a v-GNE if
and the solution set is denoted by .
Equivalently, under appropriate constraint qualifications and assuming continuous differentiability of the function , is a v-GNE if there exists a multiplier such that the following KKT system is satisfied:
Note the uniform Lagrange multiplier and the uniform constraint function across agents. In general, even in the case of jointly convex constraints, the set of GNE solutions is large, potentially infinite. The v-GNE is a refinement of the GNE, that is, [28, 19].
Remark 1. Assumption 3 makes the v-GNE well-defined, since all agents share the same constraint function , but it does not by itself force the multipliers to be uniform: even under jointly convex constraints, the GNE set contains equilibria whose KKT conditions (4) hold with multipliers that differ across agents. Restricting attention to the solutions with a uniform multiplier is therefore not a consequence of the agents’ individual optimizations; it is an additional selection criterion imposed by the designer. Under this criterion, all agents face an identical shadow price for accessing the shared resource. This has an intuitive fairness interpretation, but it is meaningful only if agents’ costs are measured on comparable scales. The comparability requirement will be made precise in Section 3.
Inter-Agent Cost Comparability
To determine the fairness properties of a joint decision , it is crucial to compare the cost incurred by individual agents. In different contexts, it may be that it is meaningful only to compare the absolute costs, to compare the relative improvements, or to compare costs with respect to a worst-case scenario. What is comparable in a specific application depends on how difficult it is to measure certain information, on whether self-reporting can be trusted, and on what information the social planner considers relevant (see [43] for further discussion in the context of control).
This notion of comparability can be expressed by defining a concept of equivalence between cost functions, i.e., determining what cost functions cannot or should not be distinguished. Equivalently, a specific level of comparability corresponds to a family of transformations of the cost functions that must not affect the joint decision (i.e., for which the decision must be invariant).
In the following, we review a selection of comparability levels commonly used in social choice theory [41], we report the corresponding invariance transformation, and we provide a brief interpretation. Figure 1 illustrates the hierarchy of these comparability levels, together with the solution concepts that will be associated with each level in the remainder of the chapter.
Figure 1. Comparability levels read as nested families of cost transformations, from heterogeneous affine transformations (CNC, outermost ellipse) down to a common affine transformation (CFC, innermost); the region outside all ellipses corresponds to arbitrary agent-specific monotone transformations, i.e., no comparability. Each solution concept is placed in the largest family of transformations under which it is invariant: the NE and the GNE set require no comparability (Observation 1, Remark 2), the v-GNE requires CUC (Proposition 2), and the f-GNE (Section 4) inherits the comparability requirement of its fairness metric (Table 1).
Cardinal Non-Comparability (CNC):
Hence, we cannot compare costs or cost increments across agents, as the coefficients and are heterogeneous.
Cardinal Unit Comparability (CUC):
As is uniform, we can compare cost increments across agents. However, the absolute cost levels are not comparable.
Cardinal Full Comparability (CFC):
A single absolute scale is shared by all agents, so both cost levels and cost increments are comparable.
Moving up this ladder, from CNC to CFC, adds information requirements and, correspondingly, sensitivity to misreported or unobservable cost features.
Running Example (EV Charging: Comparability Preview). Suppose agent 1’s cost is scaled by , modeling a vehicle with a more critical charging need. Under CNC, this scaling is not considered meaningful information, and it should not affect which decision is implemented. Under CUC, the relative scale of the agents’ costs is meaningful: agent 1’s cost increments now count three times as much, and the scaling should affect which GNE is selected. Whether that is desirable depends on whether encodes genuine information that has been accurately measured or reported.
Comparability in Generalized Nash Equilibrium Problems
We now determine what level of inter-agent comparability the GNE solution concepts (reviewed in § 2.1) implicitly assume. As a benchmark, consider first the classical Nash equilibrium problem, in which agents are coupled only through their costs.
Observation 1 (NE requires no comparability). In a Nash equilibrium problem without coupling constraints ( independent of ), agent ’s best response depends only on . Any strictly increasing transformation applied to leaves the best response, and therefore the NE solution set, unchanged. NE is thus invariant under any agent-specific monotone transformation of costs, requiring no inter-agent comparability whatsoever. Agents in a Nash game are purely competitive: only the direction of each agent’s own gradient matters, not its magnitude relative to others.
The restriction to pure strategies matters here: under mixed strategies, a nonlinear would alter agent ’s preferences over random outcomes, and only positive affine transformations preserve expected-cost rankings.
Consider now the generalized game (2) with coupling constraint sets (1) and the problem of finding , as stated in Definition 1. Let Assumptions 1 and 2 hold true. Further, assume that for every agent , a suitable constraint qualification holds at . The following result relates GNE solutions to the cardinal comparability of agents’ costs.
Proposition 1 (Invariance of GNE under CNC). Let Assumptions 1 and 2 hold. The solution set of the GNE problem (2) is invariant under transformations defined in (7).
Proof. The proof is given in [21 App. A]. ∎
Remark 2. The mechanism behind Proposition 1 is visible in the KKT conditions (4): rescaling agent ’s cost by rescales the stationarity condition of agent only, and the rescaling can be absorbed by that agent’s own multiplier, , which remains non-negative. Since each agent has an individual multiplier, the heterogeneous scalings leave the solution set untouched. The invariance of the GNE set in fact extends beyond affine maps: since Definition 1 involves only within-agent cost comparisons, the ordinal argument of Observation 1 applies verbatim, and the GNE set is unchanged under any agent-specific strictly increasing transformation. The restriction to positive affine transformations in Proposition 1 is a matter of class preservation rather than invariance: a nonlinear monotone may destroy the strong convexity and differentiability required by Assumption 1 (e.g., applied to ), in which case the KKT system (4) no longer characterizes the (unchanged) solution set.
Proposition 1 shows that the GNE set is a fairness-neutral object: it is unchanged when the cost of each agent is individually rescaled and offset, and therefore it cannot encode any comparison between the costs incurred by different agents. This is not the case when we consider the refinement to v-GNEs, as the following result shows: the v-GNE is not invariant under heterogeneous rescalings, so the selected solution does depend on how the agents’ costs are scaled against each other.
Proposition 2 (Invariance of v-GNE under CUC). Let Assumptions 1–3 hold. The solution set of the GNE problem (2) is generally not invariant under transformations defined in (7). is invariant under defined in (8).
Proof. The proof is given in [21 App. B].
The intuition for Proposition 2 mirrors the remark above: in the KKT system (6) the multiplier is shared, so it can absorb a common scaling (hence invariance under CUC) but not heterogeneous scalings (hence sensitivity to CNC transformations).
Running Example (EV Charging: Illustration of Props. 1 and 2). Consider a two-agent EV game, , symmetric parameters (§ 7). Both agents receive at the v-GNE. Now scale . The GNE set does not change (Prop. 1): all allocations from through remain equilibria (see Figure 3). But the v-GNE shifts from to , allocating more charge to the agent whose cost was scaled (Prop. 2).
Figure 3. Various fairness metrics, the v-GNE, and how their solution changes with scaling , left to right. Note that on the left all solutions overlap.
The fact that v-GNE, as a solution concept, requires at least Cardinal Unit Comparability (see Figure 1) is particularly important when fairness considerations are invoked to justify it as a refinement of the larger set of GNE solutions. When doing so, the social planner needs to ensure that the comparability of cost increments is possible and meaningful. For example, they need to ensure that (i) the elicitation of cost functions from individuals is robust against strategic manipulation by the agents; (ii) the class of admissible cost functions is rich enough to represent the real cost (more precisely: cost increments) incurred by the agents; and (iii) that enough information from the agents is collected to calibrate the relative scaling of each agent’s cost function.
We propose an alternative approach: to choose one solution in the GNE set based on an explicit fairness criterion. That is the f-GNE, introduced in the next section. Note that by Proposition 1 the GNE set itself is invariant under CNC transformations, so the search space of the selection is scale-free; whether the selected point inherits this invariance depends only on the selection criterion.
Fair Generalized Nash Equilibrium (f-GNE)
As discussed in the Introduction, the set of GNEs is large and selecting one is necessary in real implementations. A common goal is to design a solution concept which protects individual self-interest, ensures strategic stability (thus, a GNE), and additionally optimizes a desired fairness metric consistent with the assumed inter-agent cost comparability. As pointed out previously, -GNE, as a GNE-refinement, does not generally achieve that. Instead, in line with this observation and inspired by the work in [11], we introduce a new approach for “fair” equilibrium selection that consists in solving the bilevel optimization problem
where is a fairness metric that, when minimized, defines the desired efficiency-equity tradeoff. Selection of GNEs has been studied in [6] from an algorithmic perspective, in contrast to the fairness perspective considered here.
The standard metrics in Table 1, common in control applications, represent different points on the comparability ladder introduced in § 2.2, as visualized in Figure 1. All functions are stated as quantities to minimize, consistent with (10). Encoding fairness in a scalar aggregation of the individual costs is itself a design commitment, the welfarist approach of social choice theory: all information deemed relevant to the selection enters through the profile of individual costs, and the aggregation function determines which transformations of those costs leave the selection invariant. Each metric in Table 1 therefore carries an intrinsic comparability level, the weakest assumption of § 2.2 under which its minimizers are well-defined, reported in the last column. Welfarism is not the only route to fairness (procedural notions are an alternative), but it is the one that integrates naturally with the optimization-based selection (10); see [43] for a systematic treatment of social cost functions in control.
Table 1. Fairness metrics and their comparability requirements (see hierarchy in Figure 1 and definitions in § 2.2). By minimizing the function , SW minimizes total cost (efficiency); MM optimizes the worst-off outcome; NBS promotes proportional cost improvements relative to a benchmark ; AI interpolates between SW (), NBS () and MM (); JI minimizes relative variations across agents.
Interestingly, the -GNE is a solution of (10) under a specific problem structure and choice of .
Proposition 3. Let Assumptions 1–3 hold and assume the cost functions of agents are fully decoupled, i.e., is , and utilitarian fairness is considered with . Then .
Proof. The proof is given in [21 App. C].
Note that the connection between the v-GNE solution and the social welfare optimum under decoupled costs has been previously pointed out in [10] and [35].
Running Example (EV Charging: Different f-GNEs). In the two-agent EV game, the GNE set is a one-dimensional arc on the boundary (see Figure 3 in § 7.2). The f-GNE selects a point on this arc. Under NBS (CNC-compatible), the selection is invariant to cost scaling by . Under SW (CUC-required), it shifts with . Under MM (CFC-required), it moves to equalize individual costs.
The main difficulty with (10) is that the constraint (10b) corresponds to the KKT system (4): when there are multiple coupling constraints, there exists no closed-form expression of and even approximating it numerically is a challenge [36]. The next two sections develop two complementary routes to tractability. § 5 treats games with a single coupling constraint: the GNE set then admits a parametric characterization that is valid for general convex costs and reduces the selection to a low-dimensional search. § 6 treats linear-quadratic games, where multiple linear coupling constraints can be handled and the selection can be largely precomputed offline.
Fair Selection under a Single Coupling Constraint
Under Assumption 3 (jointly convex constraints, so for every agent), the GNE set admits a useful parametric characterization via normalized equilibria, recalled next.
Definition 3 (Normalized equilibrium). [36 Dfn. 3.2] Let Assumption 3 hold. A GNE is called a normalized equilibrium if there exist which solve (4) (with for all ) and satisfying
We say is associated with .
Under Assumption 3, the v-GNE is the special case of normalized equilibrium with , consistent with the shared multiplier of (6).
We now specialize to the practically important case of a single scalar coupling constraint (), which covers the EV charging game and is required by the following characterization result.
Proposition 4. [36 Prp. 3.3] Let Assumptions 1–3 hold, and let the coupling constraint be scalar, i.e., (), so that the multipliers in (4) are scalar. If is a GNE satisfying strict complementarity with some (i.e., implies , ), then is a normalized equilibrium.
Consequently, in the case of a single shared constraint, every GNE satisfying strict complementarity can be represented as a normalized equilibrium and can therefore be sought by solving the weighted VI
where is parametrized by the weights1 . GNEs violating strict complementarity need not be represented by any . Whether such equilibria can be recovered as limits of normalized equilibria, or whether restricting the selection to this family preserves the optimum of a given fairness metric, requires additional problem-specific analysis.
For problems in which the desired f-GNE lies in this normalized family, (11) replaces the GNE-set constraint (10b) with a VI parametrized by . The following example carries this out for the Nash bargaining solution.
Example: f-GNE via Nash Bargaining
In order to reduce the informational requirements for the f-GNE solution, we choose a fairness metric that is applicable in a setting of cardinal non-comparability, specifically the Nash bargaining solution (NBS). Using (10) with the NBS metric ensures that is invariant under CNC transformations defined in (7). Since we consider a single coupling constraint, the proposition above allows replacing the GNE-set constraint (11) with the parametrized variational inequality (12), so that (10) becomes:
This reformulation is computationally tractable because the inner problem (14) is a standard (for fixed , strongly monotone) variational inequality, for which efficient projection-type and operator-splitting solvers are available [17]; the outer search over the weights is low-dimensional, since with a single scalar constraint the weights can be normalized to leave degrees of freedom. In the two-agent case study of § 7.2 this structure is exploited in its simplest form: there, the GNE set reduces to a one-dimensional arc of the constraint boundary, and the NBS metric is minimized by a scalar line search along the arc.
How to ensure tractability of (10) for higher-dimensional problems with multiple coupling constraints remains open in general. The following section develops a constructive algorithm for the practically important special case of linear-quadratic games.
Explicit Fair Selection for Linear-Quadratic Games
Section 4 formulated the f-GNE selection as a bilevel problem with the GNE set as a constraint, and Section 5 made it tractable for a single coupling constraint, at the price of an online search. In this section we show that for the special case of linear-quadratic games, the set of GNEs remains tractable even in the presence of multiple constraints. We consider linear-quadratic games parametrized in a parameter vector that collects the quantities that change between problem instances but are known at decision time: reference setpoints, prices, initial conditions, resource capacities (in the EV game, for example, the charge deficits and the available capacity ). We show that the structure of the GNE set consists in a finite collection of possibly overlapping critical regions and, within each region, an affine parametrization of the equilibria. This structure can be computed offline for all parameter values simultaneously, by combining parametric best-response analysis with multiparametric quadratic programming (mpQP) [5, 20]. The extent to which the selection of the f-GNE within this structure can also be precomputed depends on the fairness metric: for social welfare, a convex and uniquely solvable regional problem yields a piecewise affine (PWA) candidate law, while for other metrics the offline computation may yield special-case nonlinear laws or leave a residual optimization online (Section 6.3). Unlike the route of Section 5, this construction does not rely on normalized equilibria and imposes no restriction on the number of (linear) coupling constraints.
Remark 3. The algorithm developed here assumes that agents’ cost functions are quadratic and constraints are linear. This structural commitment must be justified independently: if the quadratic model is only an approximation of the true preferences, the fairness guarantees inherited from the chosen comparability level are correspondingly approximate. Within the quadratic framework, the comparability conditions of Section 3 translate into conditions on the relative scaling of the cost matrices .
Linear-Quadratic GNE Problems
Consider the specialization of (2) in which each agent minimizes a quadratic cost, strictly convex in its own decision, subject to shared linear inequality constraints parametrized by :
where the own-decision Hessian block satisfies , and parameters enter linearly in the cost (via ) and in the constraint right-hand sides (via ). This covers initial conditions, reference setpoints, prices, and resource limits as special cases. The cost matrix acts on the full stacked decision , so agent costs may couple through as in (2). Positive definiteness of the full matrix is not required for a unique best response.
For fixed and , each agent’s subproblem in (13) is a QP in which both the decisions of the other agents and the parameter enter linearly. From the perspective of agent ’s subproblem, the pair therefore plays the role of a joint parameter vector: as it varies over , the optimizer is a continuous PWA function [5]:
where each critical region is a polyhedron in -space corresponding to a fixed active set of inequality constraints, and , with the number of inequality constraints in (13) (the number of rows of ).
Equilibrium Critical Regions
A GNE requires all agents to respond optimally simultaneously. For each combination of per-agent affine laws, substituting (14) across agents yields the parametric linear system
where the matrices , , and collect the best-response coefficients. Depending on its rank and consistency, this system may admit no solution, a unique solution, or an affine family of solutions. We denote its solutions by and call them equilibrium candidates associated with . A candidate is a GNE only if for every agent , because each affine best-response law is valid only on its associated critical region. We distinguish the full-rank and rank-deficient cases below.
Full-rank combination. When is full rank, it produces a unique equilibrium candidate for the fixed active-set combination :
The corresponding equilibrium critical region is
For every , the candidate is a GNE. Computationally, substituting (16) into the linear inequalities defining the individual critical regions gives a polyhedron in -space, whose nonemptiness can be checked by a feasibility linear program.
Rank-deficient combination. Let be a compact singular value decomposition, completed by left and right null-space bases and . If , the system is consistent only at parameters satisfying
At such parameters its candidate solutions form the affine family
where is one particular solution. Regional membership must be imposed on the whole candidate family. Define the joint polyhedron
Every with is a GNE associated with , and is the set of parameters for which this combination produces at least one GNE. Although is polyhedral, computing can require polyhedral projection.
There is no guarantee that a given combination admits any parameter: for many combinations the membership conditions are mutually inconsistent, and the corresponding is empty; these are simply discarded during the enumeration. We assume additionally that the parametrized game admits at least one GNE for every , for example when the joint feasible set is nonempty and compact for every , so that standard existence conditions apply [16]. Under this additional hypothesis, every GNE corresponds to at least one active-set combination, and the nonempty equilibrium critical regions cover . Distinct equilibrium critical regions may overlap. If , both combinations must be examined. They may yield distinct GNEs, but different combinations may also represent the same equilibrium.
The f-GNE as a Multiparametric Program
For a fixed parameter , each full-rank combination with contributes one GNE candidate, whereas each rank-deficient combination may contribute an affine family of GNEs. Within a rank-deficient combination, the regional selection problem is
The affine family (19) spans only the GNEs that share the active-set combination . To compare all applicable combinations, define
A global selector chooses an index in . Hence runtime evaluation may require testing several regions and comparing their candidate values.
Whether (21) admits a PWA explicit solution in depends on the fairness metric. Substituting (19) into the metrics of Table 1:
Social welfare (SW): is quadratic in , and enters its linear term affinely. Its reduced Hessian is . If , the regional selection problem (21) is a strictly convex mpQP, and its unique optimizer is a continuous PWA function of on .
Maximin (MM): Introducing an epigraph variable gives the regional problem
Because the epigraph constraints are quadratic in , this is a parametrized quadratically constrained program rather than a standard mpQP. Even when these constraints are convex, its optimizer is not generally PWA and no explicit solution is guaranteed. The regional MM problem may therefore be retained for online solution unless additional problem-specific structure is available.
Nash bargaining (NBS): Let denote the benchmark allocation used in the NBS metric. The metric is evaluated over GNEs that weakly improve every agent’s cost relative to this benchmark:
On this domain,
is a polynomial of degree at most in . Its global minimization is generally nonconvex and cannot be certified from first-order conditions alone, so a numerical global optimization may remain online. Nevertheless, the equilibrium regions, particular solutions , and null-space bases are computed offline. Each remaining regional problem is posed only in , rather than in the full decision vector , followed, when necessary, by comparison across overlapping combinations.
The complete procedure is summarized in Algorithm 1. For convex, uniquely solvable SW subproblems, regional candidates can be stored as PWA laws. MM and NBS may retain a regional optimization online.
Algorithm 1 Explicit f-GNE for linear-quadratic GNE problems
Input: LQ-GNE (13), parameter set , and fairness metric .
Output: Regional explicit laws and retained online problems.
for each agent do
Solve mpQP (13).
Store the PWA response (14) and regions .
for each combination do
Form parametric linear system (15).
if full rank then
Compute the affine candidate law (16).
Compute the region .
else
Compute via SVD.
Construct as in (20) and project it onto the -space to obtain .
if and then
Compute the PWA law .
else
Leave the regional selection problem for online solution.
if the regional minimizer is available explicitly then
Store , the regional minimizer, and .
else
Store and the regional problem for online solution.
return each with its explicit solution laws or retained regional problem.
At runtime, for the observed parameter , one identifies all regions containing , evaluates the stored candidate laws or solves the retained regional problems, and selects a candidate with the smallest value of .
Case Study: Electric Vehicle Charging Game
Consider an electric vehicle charging game, a simplified version of [33, 32, 31], as played by a finite number of agents . Every agent arrives with an initial charge , and charges its vehicle by , aiming for a desired final charge . The aggregate charge is constrained by an available capacity , which may be insufficient to charge every agent to its desired level. This leads to the coupled optimal control problems
where are the battery leakage rates, and is the charging efficiency. Similarly to [32], we model the congestion price as an affine function of the total demand2, i.e.,
where is a base price and a congestion tariff. Both are set by the energy pricing mechanism and are therefore identical for all agents; the individual preference of each agent, namely how much they value reaching their desired charge relative to the incurred energy cost, is entirely captured by the weight .
Applying the KKT conditions of Definition 2 (eq. (6)) to the EV cost yields the pseudo-gradient with
where is the effective charge deficit. The v-GNE satisfies , . The parameter vector collects all quantities that enter this system: under CUC the absolute values of the weights are meaningful information; under CNC each agent’s cost is defined only up to an individual positive rescaling, and no meaning can be attached to the relative magnitude of the across agents.
Transformations
We now demonstrate Proposition 2 concretely. Three transformations of the EV cost functions are applied; each changes the v-GNE, illustrating that the designer must decide whether the information driving the shift is physically meaningful and should affect the allocation. For each example, we recompute the v-GNE and report the resulting costs and allocations in Figure 2.
Figure 2. Comparison of the v-GNE solution and how it changes under transformations of cost scaling, initial condition and cost function structure.
(i) Scaling of cost functions: with scaling vector . Heterogeneous scaling could represent the case in which the agents’ utilities depend on the additional kilometer range they get from charging their vehicle, and different vehicles have different fuel economy. Would we really deem it desirable that our solution concept allocates more charge to less efficient vehicles?
(ii) Change in the initial charge level of agents from to . The share of charge for agent 1 who arrives with an empty battery increases significantly. However, is it really desirable that agents with lower initial charge are advantaged under the v-GNE?
(iii) Transformed cost: the cost function for reaching the desired charge level is modeled as a quadratic function . What if the true utility is heterogeneous across agents? For instance, one agent needs to reach home but any additional charge will result in small benefit, represented by a logarithm. Another agent has to drive a long distance urgently. Consider the following cost functions:
Is it desirable that the declared need in terms of utility has such a strong effect on the allocation?
The examples show that the v-GNE depends both on cardinal cost representations and on the preference information encoded in the model. Whether these features should influence the allocation is a design choice.
Fairness Metrics
We now showcase the underlying comparability assumptions of a variety of fairness metrics and their susceptibility to changes in the scale of the cost functions. In order to do so, we compare the solution of the f-GNE in (10) under three different a priori valid choices of fairness metrics : (i) social welfare (SW), (ii) maximin (MM), and (iii) Nash bargaining solution (NBS), as introduced in § 4.
Specifically, we consider a situation with two agents in which one unit of charge is available, i.e. , and initially both agents are equivalent and thus receive the same amount of charge , as shown in Figure 3. Then, in a second setting, we scale the cost function of the first agent by a factor of 3 such that . Based on Figure 3, several observations are noteworthy:
As stated in Proposition 1, the set of GNEs is invariant under CNC, and thus under scaling of cost functions.
In the scaled situation, the maximin fairness criterion selects the GNE that allocates the most resources to agent 1 which is worse off under the scaled cost.
Different fairness criteria produce different allocations, with the exception of the Nash bargaining solution, as it is invariant under CNC transformations.
Explicit f-GNE for the EV Charging Game
Algorithm 1 applies directly to the EV game: the costs are quadratic, the constraint is linear, and non-negativity provides individual bounds.
With parameter vector , when the resource constraint is active the matrix has a dimensional null space tangent to the active resource hyperplane, expressing that charge can be shifted between agents while preserving its total. Thus and in (21). In the two-agent numerical experiment below this reduces to a scalar parameter, with tangent direction . We therefore have the following decision rules under the different fairness criteria:
SW: minimizing the aggregate quadratic cost over subject to the critical-region bounds is an mpQP, yielding a piecewise-affine (PWA) allocation law under the convexity and uniqueness conditions stated in § 6.3.
MM: the minimax conditions (equalization of the worst-off agents’ costs, or activity of a region bound) can be solved in closed form for the two-agent regimes considered here, yielding a piecewise nonlinear law. This special-case construction does not imply an explicit MM law in general.
NBS: the objective is polynomial in ; no general closed-form law exists, and in the two-agent experiment a scalar numerical global minimization over the GNE arc is performed online for each parameter instance.
Figure 4 illustrates the difference between these f-GNEs by sweeping the available capacity for an asymmetric two-agent game . For the NBS selection in this simulation, the disagreement benchmark is the no-charge allocation , so that each agent’s bargaining gain is measured relative to its cost when neither agent charges. For below the unconstrained threshold , the coupling constraint is active and the GNE set is a non-trivial arc (gray band); above this threshold the unique Nash equilibrium coincides across all metrics. Several features of the figure deserve comment.
Figure 4. f-GNE allocation for agent 1 as a function of available capacity (two-agent asymmetric EV game, , ). The NBS disagreement benchmark is the no-charge allocation . Gray band: range of agent 1’s allocations over the GNE set. Dotted vertical line: unconstrained threshold . The v-GNE curve is affine and the SW curve piecewise affine in ; the MM and NBS curves are piecewise nonlinear.
The upper boundary of the GNE set equals for (agent 1 can receive the entire supply) but decreases afterwards. The cap is agent 1’s own rationality: at a GNE, agent 1 must not prefer to unilaterally reduce its charge, and beyond the cap the congestion price, which grows with total demand , outweighs the shrinking shortfall benefit.
The v-GNE curve is exactly affine in (slope 0.5) over the whole constrained regime. The SW curve is piecewise affine, as predicted by the mpQP analysis: it runs parallel to the v-GNE (slope 0.5, constant offset) while the welfare optimum is interior to the GNE set, and it exhibits a kink shortly before , where the optimum reaches the upper boundary of the GNE set and follows it. The constant offset between SW and v-GNE, despite both being QCU-based, is caused by the fact that the EV costs are coupled through the congestion price, so the decoupled-cost hypothesis of Proposition 3 fails, and the SW selection (which internalizes the externality) differs from the v-GNE (which equalizes private marginal costs).
The MM curve is not affine: in its first regime it equalizes the two agents’ costs, which yields a nonlinear (rational) expression in , and at it kinks onto upper boundary of the GNE set. The NBS curve is smooth and nonlinear throughout the constrained regime for the no-charge disagreement benchmark used here. All four trajectories converge at , confirming that a unique Nash equilibrium exists once the resource constraint becomes slack.
Discussion and Conclusion
The v-GNE retains the desirable property that agents face the same “shadow price” for accessing a shared resource. In such a setting, it can be interpreted as a coordination mechanism analogous to the emergence of a single clearing price from bids and asks in a competitive market.
However, this interpretation rests on an assumption that the v-GNE makes implicitly: the agents’ costs must be unit comparable. Whether this assumption is defensible is not a mathematical question. Some comparability levels require cost information that may be difficult to quantify, expensive to measure, private, or susceptible to misreporting. A designer may also wish to prevent particular modeled features from influencing the allocation. The examples of Section 7.1 illustrate how both cardinal cost representations and preference information, such as initial charge and utility shape, can affect the selected outcome.
The conclusion is not that fairness should always be pursued under the weakest possible comparability requirement. Maximin, for example, requires full comparability and provides a compelling criterion when the relevant information is meaningful and trustworthy. The Nash bargaining metric, at the other extreme, is invariant to individual cost rescalings and is suitable when less comparability can be defended. The fairness criterion should therefore be chosen intentionally and made explicit, in accordance with the information that is credible in the application. It may differ from the implicit selection embodied by the v-GNE.
Computationally, games with one coupling constraint admit a parametrization by normalized equilibria that reduces fair selection to a lower-dimensional search. For linear-quadratic games with multiple linear constraints, parametric best-response analysis and active-set enumeration provide regional parametrizations of the GNE set. Strictly convex SW selection yields explicit PWA regional laws, whereas MM and NBS may retain regional optimization online. Improving the scalability of this construction and extending it to nonquadratic games with multiple coupling constraints remain open directions.
Altogether, fair GNE selection remains a rich problem at the intersection of comparability, invariance, equilibrium selection, and computation.
Acknowledgements This work was supported by the Swiss National Science Foundation under the NCCR Automation (grant 51NF40 225155) and under the Eccellenza Grant “Markets and Norms” (H.H.N.).
Competing Interests The authors have no conflicts of interest to declare that are relevant to the content of this chapter.
References
- [1]Atkinson, A.B.: On the measurement of inequality. Journal of Economic Theory 2(3), 244–263 (Sep 1970)DOI
- [2]Bassanini, A., La Bella, A., Nastasi, A.: Allocation of railroad capacity under competition: A game theoretic approach to track time pricing. In: Transportation and Network Analysis: Current Trends, pp. 1–17. Springer US (2002)DOI
- [3]Belgioioso, G., Grammatico, S.: Semi-decentralized generalized Nash equilibrium seeking in monotone aggregative games. IEEE Transactions on Automatic Control 68(1), 140–155 (Jan 2023)
- [4]Belgioioso, G., Yi, P., Grammatico, S., Pavel, L.: Distributed generalized Nash equilibrium seeking: An operator-theoretic perspective. IEEE Control Systems Magazine 42(4), 87–102 (Aug 2022)DOI
- [5]Bemporad, A., Morari, M., Dua, V., Pistikopoulos, E.N.: The explicit linear quadratic regulator for constrained systems. Automatica 38(1), 3–20 (Jan 2002)DOI
- [6]Benenati, E., Ananuta, W., Grammatico, S.: Optimal selection and tracking of generalized Nash equilibria in monotone games. IEEE Transactions on Automatic Control 68(12), 7644–7659 (Dec 2023)arxiv.org/abs/2203.07765
- [7]Benenati, E., Grammatico, S.: Probabilistic game-theoretic traffic routing. IEEE Transactions on Intelligent Transportation Systems 25(10), 13080–13090 (Oct 2024)arxiv.org/abs/2303.03295
- [8]Bertsimas, D., Farias, V.F., Trichakis, N.: On the efficiency-fairness trade-off. Management Science 58(12), 2234–2250 (Dec 2012)DOI
- [9]Bianchi, M., Belgioioso, G., Grammatico, S.: Fast generalized Nash equilibrium seeking under partial-decision information. Automatica 136, 110080 (Feb 2022)DOI
- [10]Cadre, H.L., Jacquot, P., Wan, C., Alasseur, C.: Peer-to-peer electricity market analysis: From variational to generalized Nash equilibrium. European J. of Operational Research 282(2), 753–771 (Apr 2020)
- [11]Cadre, H.L., Mou, Y., Höschle, H.: Parametrized inexact-ADMM based coordination games: A normalized Nash equilibrium approach. European J. of Operational Research 296(2), 696–716 (Jan 2022)
- [12]d’Aspremont, C., Gevers, L.: Social welfare functionals and interpersonal comparability. In: Arrow, K.J., Sen, A.K., Suzumura, K. (eds.) Handbook of Social Choice and Welfare, vol. 1, chap. 10, pp. 459–541. Elsevier (2002)
- [13]Dreves, A.: How to select a solution in generalized Nash equilibrium problems. Journal of Optimization Theory and Applications 178(3), 973–997 (Sep 2018)DOI
- [14]Dreves, A., Gerdts, M.: A generalized Nash equilibrium approach for optimal control problems of autonomous cars. Optimal Control Applications and Methods 39(1), 326–342 (Jan 2018)
- [15]Facchinei, F., Fischer, A., Piccialli, V.: Generalized Nash equilibrium problems and newton methods. Mathematical Programming 117(1-2), 163–194 (Jul 2009)
- [16]Facchinei, F., Kanzow, C.: Generalized Nash equilibrium problems. 4OR 5(3), 173–210 (Sep 2007)
- [17]Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. I. Springer-Verlag New York Inc. (Feb 2003)
- [18]Facchinei, F., Pang, J.S.: Nash equilibria: the variational approach. In: Convex Optimization in Signal Processing and Communications, pp. 443–493. Cambridge University Press (Dec 2009)DOI
- [19]Fukushima, M.: Restricted generalized Nash equilibria and controlled penalty algorithm. Computational Management Science 8(3), 201–218 (Aug 2011)
- [20]Hall, S., Bemporad, A.: Solving Multiparametric Generalized Nash Equilibrium Problems and Explicit Game-Theoretic Model Predictive Control (2025), https://arxiv.org/abs/2512.05505
- [21]Hall, S., Dörfler, F., Nax, H.H., Bolognani, S.: The Limits of “Fairness” of the Variational Generalized Nash Equilibrium. In: 64th IEEE Conference on Decision and Control (CDC) (2025)arxiv.org/abs/2504.03540
- [22]Hall, S., Zhang, K., Shilov, I., Nax, H.H., Bolognani, S.: Welfarist Control Design – How to fulfill the societal mandate in multi-agent control? (2026), https://arxiv.org/abs/2606.23931
- [23]Harker, P.T.: Generalized Nash games and quasi-variational inequalities. European Journal of Operational Research 54(1), 81–94 (Sep 1991)DOI
- [24]Jain, R.K., Chiu, D.M.W., Hawe, W.R.: A quantitative measure of fairness and discrimination for resource allocation in shared computer systems. Tech. Rep. DEC-TR-301, Digital Equipment Corporation, Eastern Research Laboratory, Hudson, MA (Sep 1984), available as arXiv:cs/9809099
- [25]Kaisermayer, V., Muschick, D., Horn, M., Gölles, M.: Operation of coupled multi-owner district heating networks via distributed optimization. Energy Reports 7, 273–281 (Oct 2021)DOI
- [26]Krawczyk, J.B.: Coupled constraint Nash equilibria in environmental games. Resour. Energy Econ. 27(2), 157–181 (Jun 2005)DOI
- [27]Kulkarni, A.A.: The Efficiency of Generalized Nash and Variational Equilibria (2019), https://arxiv.org/abs/1908.00702
- [28]Kulkarni, A.A., Shanbhag, U.V.: On the variational equilibrium as a refinement of the generalized Nash equilibrium. Automatica 48(1), 45–55 (Jan 2012)DOI
- [29]Lan, T., Kao, D., Chiang, M., Sabharwal, A.: An axiomatic theory of fairness in network resource allocation. In: IEEE INFOCOM (2010)arxiv.org/abs/0906.0557
- [30]Le Cleac’h, S., Schwager, M., Manchester, Z.: ALGAMES: a fast augmented lagrangian solver for constrained dynamic games. Autonomous Robots 46(1), 201–215 (Jan 2022)
- [31]Liu, Z., Wu, Q., Huang, S., Wang, L., Shahidehpour, M., Xue, Y.: Optimal day-ahead charging scheduling of electric vehicles through an aggregative game model. IEEE Transactions on Smart Grid 9(5), 5173–5184 (Sep 2018)DOI
- [32]Ma, Z., Callaway, D.S., Hiskens, I.A.: Decentralized charging control of large populations of plug-in electric vehicles. IEEE Transactions on Control Systems Technology 21(1), 67–78 (Jan 2013)
- [33]Ma, Z., Zou, S., Ran, L., Shi, X., Hiskens, I.A.: Efficient decentralized coordination of large-scale plug-in electric vehicle charging. Automatica 69, 35–47 (Jul 2016)DOI
- [34]Menache, I., Ozdaglar, A.E.: Network games: Theory, models, and dynamics. Morgan & Claypool Publishers (2011)DOI
- [35]Moret, F., Tosatto, A., Baroche, T., Pinson, P.: Loss allocation in joint transmission and distribution peer-to-peer markets. IEEE Transactions on Power Systems 36(3), 1833–1842 (May 2021)arxiv.org/abs/2001.05396
- [36]Nabetani, K., Tseng, P., Fukushima, M.: Parametrized variational inequality approaches to generalized Nash equilibrium problems with shared constraints. Computational Optimization and Applications 48(3), 423–452 (Apr 2011)
- [37]Nash, J.F.: The bargaining problem. Econometrica 18(2), 155–162 (Apr 1950)
- [38]Neely, M.J., Modiano, E., Li, C.P.: Fairness and optimal stochastic control for heterogeneous networks. IEEE/ACM Transactions on Networking 16(2), 396–409 (Apr 2008)
- [39]Paccagnan, D., Gentile, B., Parise, F., Kamgarpour, M., Lygeros, J.: Nash and Wardrop equilibria in aggregative games with coupling constraints. IEEE Transactions on Automatic Control 64(4), 1373–1388 (Apr 2019)
- [40]Rawls, J.: A Theory of Justice. Harvard University Press (1971)
- [41]Roberts, K.W.S.: Interpersonal Comparability and Social Choice Theory. The Review of Economic Studies 47(2), 421–439 (Jan 1980)DOI
- [42]Rosen, J.B.: Existence and uniqueness of equilibrium points for concave n-person games. Econometrica 33(3), 520–534 (Jul 1965)DOI
- [43]Shilov, I., Elokda, E., Hall, S., Nax, H.H., Bolognani, S.: Welfare and Cost Aggregation for Multi-Agent Control: When to Choose Which Social Cost Function, and Why? IEEE Open Journal of Control Systems 5, 80–90 (2026)
- [44]Siebert, S., Burke, J., Faures, J.M., Frenken, K., Hoogeveen, J., Döll, P., Portmann, F.T.: Groundwater use for irrigation–a global inventory. Hydrology and earth system sciences 14(10), 1863–1880 (Oct 2010)DOI
- [45]Theil, H.: Economics and Information Theory. Studies in mathematical and managerial economics, North-Holland Publishing Company (1967)
- [46]Villa, E., Breschi, V., Tanelli, M.: Fair-MPC: A framework for just decision-making. IEEE Transactions on Automatic Control 70(9), 6005–6020 (Sep 2025)DOI
- [47]Xinyang Chen, V., Hooker, J.N.: A guide to formulating fairness in an optimization model. Annals of Operations Research 326(1), 581–619 (Jul 2023)
- [48]Yi, P., Pavel, L.: An operator splitting approach for distributed generalized Nash equilibria computation. Automatica 102, 111–121 (Apr 2019)DOI



