Angelo Fanelli

Dimitris Fotakis

On (approximate) pure Nash equilibria in preference games

In this work we introduce and study a general model of preference game. Our game belongs to the large class of games in which each agent aims at compromising between her innate preferences and the choices of the neighbours. Our game encompasses two models, i.e., the full information and the partial information settings. While in the former each agent is fully aware of the strategies of the neighbours, in the latter each agent has only access to a single representative strategy, which can be regarded as the output of an aggregation function. Both settings are quite general and allow for a systematic study of the fundamental questions related to the existence and efficiency of (approximate) equilibria in the strategic interaction of agents in social networks. Interestingly, our bounds on the price of anarchy are very general and are derived in terms of key features of the game (i.e., social impact, boundary and stretch). Moreover, our results show that the two settings behave very similarly, thus confirming our conjecture that in general the lack of information does not affect the existence and efficiency of the (approximate) equilibria.

Introduction

We refer to preference games as the class of games in which a set of finite agents share a common set of strategies, that are embedded in an (approximate) metric space, and in which each agent aims at choosing the strategy that represents a good compromise between her preferred strategy and the neighbours' strategies. An agent's cost is typically formulated as the sum of two quantities: the first quantity is the cost for choosing a strategy different from her preferred one, usually quantified as the (approximate) distance between her strategy and the preferred one, while the second quantity is the cost for choosing a strategy which is far from the neighbours' strategies.

Numerous games studied in the letterature can be cast as preference games, including models of opinion formation (see e.g., [START_REF] Bindel | How bad is forming your own opinion?[END_REF][START_REF] Bhawalkar | Coevolutionary Opinion Formation Games[END_REF][START_REF] Ghaderi | Opinion Dynamics in Social Networks with Stubborn Agents: Equilibrium and Convergence Rate[END_REF]), or their variants such as discrete preference games, (see e.g., [START_REF] Chierichetti | On discrete preferences and coordination[END_REF][START_REF] Auletta | Generalized Discrete Preference Games[END_REF][START_REF] Auletta | Robustness in discrete preference games[END_REF][START_REF] Lolakapuri | Computational Aspects of Equilibria in Discrete Preference Games[END_REF]).

Copyright c 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

In this paper we introduce and study a quite general model of preference game which encompasses the full and the partial information settings. In the full information setting, inspired by the discrete preference model introduced in [START_REF] Chierichetti | On discrete preferences and coordination[END_REF], we assume that each agent is fully aware of the strategies of her neighbours and respond optimally to them. Instead, in the partial information setting, we assume that each agent has access to a single representative strategy, which can be regarded as the output of an aggregation function that condenses the strategies of her neighbors into a single one. In order to motivate this latter model, we may think of the traditional political voting scenario, where voters have fixed innate preferences over the candidates, but polls (which is a form of preference aggregation) might cause the voters to change their vote (see also [START_REF] Epitropou | Opinion Formation Games with Aggregation and Negative Influence[END_REF], where the model involves an estimation of the average opinion of the agents).

Before presenting the related work (Section 1.3) and outline our conceptual and technical contributions (Section 1.4), we formally describe our model (Section 1.1) and introduce technical concepts (Section 1.2). We next present our results on the existence of (approximate) pure Nash equilibria (Section 2) and the price of anarchy (Section 3 and Section 4). We conclude the paper with an application of our findings on a special case of preference game which we call k-approval voting game (Section 5).

Preference games

We assume a finite population N of n ≥ 2 agents and an underlying strategy space Z, which may be either discrete or continuous. Each agent i has a fixed preferred strategy s i . Let S = {s 1 , . . . , s n }. One of the key ingredient of our model is to allow preferred strategies not to belong to Z. This ensures the agents to have more elaborate preferred strategies and to account for preferences that possibly cannot be fully disclosed in public. So, we assume a strategy "universe" U , and that Z ⊆ U (e.g., Z may be discrete, while U may be the convex hull of Z) and S ⊆ U . Z and S could be disjoint or not. So, we let N S = {i ∈ N : s i ∈ Z} denote the set of agents with preferred strategy in Z; we say that the game is restricted if N S = ∅, unrestricted if N S = N , and semi-restricted otherwise.

We assume a distance function d : U × U → R ≥0 , which quantifies dissimilarity between the strategies; we let d be a approximate metric over U (see Section 1.2 for a formal definition). This function will be used to quantify the agents' costs in a given strategy profile.

The influence exercised by j's strategy on the strategy choice of agent i is quantified by the influence weight w ij ∈ [0, 1]. We refer to the set of agents j such that w ij > 0 as the set of i's neighbours. Another key ingredient of our model is to assume that the influence weights w ij are not necessarily symmetric, have w ii = 0 and are normalized so that j w ij = 1, i.e., the total influence exercised to any agent i sums up to 1. For every agent i, we denote by w i the vector of influence weights (w ij ) j∈N .

We refer to any vector z ∈ Z n as a state (strategy profile) of the game, in which the i-th component, denoted by z(i), represents the strategy of i. If z = (z, . . . , z), we say that z is a consensus on z. We denote by z -i the partial strategy profile obtained from z after removing i's strategy.

The overall cost c i ( z) incurred by i in z can be summarized as the convex combination between two components, i.e.,

c i ( z) = αd s i , z(i) + (1 -α)K( w i , z) ,
where the first component d s i , z(i) is the innate cost of i for z(i), and the second component K( w i , z) is the disagreement cost; the agents only influence each other through this latter term. In this paper we will propose two different definitions of K, corresponding to the full information and partial information settings. The coefficient α ∈ (0, 1) quantifies the confidence of each agent i on her preferred strategy s i , and often referred to as the self-confidence of agent i. We say the agents are compliant when α ∈ (0, 1/2), balanced when α = 1/2, and stubborn otherwise. As usual, each agent i selects her strategy z(i) so as to minimize her cost.

Full information. We assume that each agent has full access to the strategies of the neighbours. We define the disagreement cost of i as

K( w i , z) = j =i w ij d z(i), z(j) . ( 1
)
When K is defined as in (1), we will denote the cost of each agent i in z as c F i ( z). Partial information. We assume that each agent does not have full access to the strategies of the neighbours but to an aggregate value. The major ingredient is an aggregation function aggr which, for each agent i, maps w i and z -i to an aggregated strategy aggr( w i , z -i ) ∈ Z that "summarizes" the strategies in z -i . For brevity, we will usually write aggr i ( z -i ), instead of aggr( w i , z -i ). We define the disagreement cost of i as

K( w i , z) = d z(i), aggr( w i , z -i ) .
(2)

Our results hold for general aggregation functions that satisfy unanimity i.e., if x -i = (x, . . . , x) then aggr i ( x -i ) = x, and consistency i.e., if x and y satisfy j =i w ij d x(j), y(j) = 0 (this quantity corresponds to the relative distance π i ( x, y) between x and y, as defined in Section 1.2) then aggr i ( x -i ) = aggr i ( y -i ). We refer to aggregation functions that satisfy unanimity and consistency as feasible (see Section 1.2 for some examples of feasible aggregation functions). We remark that choosing the aggregation value as an element of Z, instead of U , strongly affects the behaviour of the game. On the other hand, choosing aggr i as an element of U requires more assumptions (e.g., on the strategy space, the aggregation function, or the distance function) in order to derive significant results; we leave this as an interesting direction for further research.

When K is defined as in (2), we will denote the cost of each agent i in z as c P i ( z). A case study: k-approval voting game. As an application of our findings, we introduce an example of preference game in which the strategy space Z consists of all binary strings of length m with k ones, while the preferred strategies lie in the convex hull of Z. Formally,

Z = { u ∈ {0, 1} m | m =1 u( ) = k}, U = { u ∈ [0, 1] m | m =1 u( ) =
k} and an agent i can choose any s i ∈ U as her preferred strategy. We refer to the case m = 2 and k = 1 as the binary strategies setting, since |Z| = 2. We assume that the distance function d is L 2 2 ; namely, for every

u, v ∈ U , d( u, v) = m =1 ( u( ) -v( )) 2 .
As a special case of preference game, also here we can distinguish two versions of the game, namely the full and the partial information. This game is motivated by the k-approval voting and generalises the opinion formation model with binary strategies [START_REF] Ferraioli | Decentralized dynamics for finite opinion games[END_REF]; we discuss in more details about this relation in Section 1.3.

Notation, Definitions and Preliminaries

In this section, we introduce some additional notation and discuss some important preliminaries.

Approximate metric. We assume that, for some 1 ≤ ρ Z ≤ ρ, d : U × U → R ≥0 satisfies (i) d(x, x) = 0, for all x ∈ U ; (ii) symmetry, i.e., d(x, y) = d(y, x), for all x, y ∈ U ; (iii) (approximate) triangle inequality, i.e., d(x, y) ≤ ρ d(x, z)+ d(z, y) , for all x, y, z ∈ U ; and (iv) d(x, y) ≤ ρ Z d(x, z) + d(z, y) , for all x, y, z ∈ Z. In this case, we say that d is a (ρ, ρ Z )-approximate metric. We say that d is an exact metric when ρ = ρ Z = 1, and that d is uniform when it is an exact metric such that d(x, y) = 1 for all x = y.

Examples of Feasible Aggregation Functions. These are aggregation functions that satisfy unanimity and consistency. Notable examples of feasible aggregation functions are the Fréchet median and the Fréchet mean. Given any state z, the Fréchet median of agent i in z, denoted by med i ( z -i ), is any strategy that minimizes the weighted sum of its distances to the strategies in z -i , i.e., med i ( z -i ) ∈ arg min y∈Z j =i w ij d y, z(j) .

(3)

The Fréchet mean of agent i in z, denoted by mean i ( z -i ), is any strategy in Z that minimizes the weighted sum of its squared distances to the strategies in z -i , i.e.,

mean i ( z -i ) ∈ arg min y∈Z j =i w ij d 2 y, z(j) . (4)
Approximate Pure Nash Equilibria, Social Optima and Price of Anarchy. For any state z and any strategy z, we let [ z -i , z] be the new state obtained from z by replacing its i-component z(i) with z and keeping the remaining components unchanged, i.e., [ z -i , z](i) = z and [ z -i , z](j) = z(j) for every j = i. For γ ≥ 1, a strategy z * ∈ Z is a γ-approximate best response of agent i wrt.

z -i if c i ([ z -i , z * ]) ≤ γc i ([ z -i , z]
), for every z ∈ Z (when γ = 1, z * is simply called best response). We say that a state z is a γ-approximate pure Nash equilibrium (or simply γ-equilibrium, for brevity) if every agent i is playing a γ-approximate stable strategy wrt. z -i , i.e., for every agent i and every strategy z ∈ Z, we have c i ( z) ≤ γc i ([ z -i , z]); if γ = 1, we simply refer to z as an exact pure Nash equilibrium (or simply equilibrium). We use E γ ⊆ Z n to denote the set of all γ-approximate pure Nash equilibria of a given preference game. We say that a strategy

x ∈ Z is a γ- approximate dominant strategy of agent i if c i [ x -i , x ] ≤ γc i [ x -i , y]
, for all states x -i and y ∈ Z (when γ = 1, x is simply called dominant strategy).

We measure the efficiency of each state z according to a social objective. We consider two social objectives, the social cost SUM( z) = i∈N c i ( z) and the maximum cost MAX( z) = max i∈N c i ( z). A state o is optimal wrt. SUM, if SUM( o) ≤ SUM( z), for all states z. We let O SUM ⊆ Z n be the set of optimal states wrt. SUM, i.e., O SUM = arg min z∈Z n SUM( z). Optimal states wrt. MAX and O MAX are defined similarly.

For any o ∈ O SUM , the price of anarchy of a game wrt. SUM is POA SUM = max e∈E1 SUM( e)

SUM( o) , if SUM( o) > 0; if SUM( o) = 0 then POA SUM = +∞, when E 1 = O SUM , and POA SUM = 1, when E 1 = O SUM . The definition of POA MAX is similar.
Equivalence and Relative Distance between States. For every pair of states x, y, D( x, y) = {j ∈ N : x(j) = y(j)} denotes the set of agents with different strategies in x and y. If D( x, y) = ∅, we say that x and y are globally equivalent. For every agent i and all pairs of states x, y, we define the relative distance between x and y for i as π i ( x, y) = j =i w ij d x(j), y(j) . Notice that if y = [ x -i , x], for any x, then π i ( x, y) = 0. When π i ( x, y) = 0, we say that x and y are equivalent for i. Notice that D( x, y) = ∅ implies π i ( x, y) = 0 (while the converse may not be true).

Social Impact, Boundary and Stretch. These are the three features of the game which fully characterize the inefficiency of the equilibria, as we will see in Section 3.

The social impact of agent i is δ i = j∈N w ji and quantifies the intensity by which i influences the environment. The global social impact is δ = max j∈N δ j ; it quantifies the asymmetry between the influence received and exercised by any agent in the social network. Since j =i w ij = 1 for every i, we observe that i∈N δ

i = n and δ ∈ [1, n -1].
The boundary of agent i, denoted by β i quantifies how much closer a strategy x can be to s i compared against an equilibrium strategy e(i) of i. Formally,

β i = min e∈E,x = e(i) d(x, s i ) d x, e(i) . (5)
For nontrivial instances, there always exists a strategy x with d(x, e(i)) > 0. Thus, β i is well defined. The (global) boundary is β = min j∈N β j .

The stretch τ i of agent i quantifies how sensitive the aggregation function is wrt. the changes of the state of the game. Formally, we let

τi = inf e∈E y∈Z n πi( e, y)>0 r ≥ 0 d aggr i ( e -i ), aggr i ( y -i ) π i ( e, y) ≤ r .
We define τ i = max{ τi , 1}, so as to account for the case where π i ( e, y) = 0 and d aggr i ( e -i ), aggr i ( y -i ) = 0. Since τ i is used in the price of anarchy bounds, we can restrict its definition to optimal states o, instead of arbitrary states y. We use this more restricted definition in the proofs of Proposition 7.We define the (global) stretch as τ = max j∈N τ j . At the conceptual level, the global stretch quantifies how much we lose, in terms of equilibrium efficiency, because agents only have access to an aggregate of the strategies in z, instead of z itself; in short, the stretch is the parameter that measures the lack of information. We will give the formal evidence of this last statement in Lemma 3 and Remark 1.

Related Work

Our preference game with full information is closely related to both the discrete preference model, introduced in (Chierichetti, Kleinberg, and Oren 2018), and the class of opinion formation games (see e.g., [START_REF] Bindel | How bad is forming your own opinion?[END_REF][START_REF] Bhawalkar | Coevolutionary Opinion Formation Games[END_REF][START_REF] Ghaderi | Opinion Dynamics in Social Networks with Stubborn Agents: Equilibrium and Convergence Rate[END_REF]), whose principles go back to the classical works of [START_REF] Degroot | Reaching a Consensus[END_REF] and [START_REF] Friedkin | Social influence and opinions[END_REF]) on opinion formation.

In the discrete preference model [START_REF] Chierichetti | On discrete preferences and coordination[END_REF], differently from our model, the set of strategies is discrete, d is an exact metric and the influence weights are symmetric and not normalized. The authors show that their model is a potential game, that the price of anarchy can be unbounded and that the price of stability is at most 2. Moreover, the properties of the discrete preference game for richer metrics, such as tree metrics, were studied. Recently, [START_REF] Lolakapuri | Computational Aspects of Equilibria in Discrete Preference Games[END_REF] proved that computing a pure Nash equilibrium for such game is PLS-complete, even in a very restricted setting. The model proposed in [START_REF] Chierichetti | On discrete preferences and coordination[END_REF] has been generalized in [START_REF] Auletta | Generalized Discrete Preference Games[END_REF] and consistency between preferred strategies and equilibrium strategies were considered in [START_REF] Auletta | Robustness in discrete preference games[END_REF].

On the other hand, opinion formation games are characterized by the fact that the set of strategies is the set of points on the real line, d is L 2 2 (i.e., the square of the L 2 norm, motivated by repeated averaging in [START_REF] Degroot | Reaching a Consensus[END_REF][START_REF] Friedkin | Social influence and opinions[END_REF]) and the influence weights are usually symmetric and not normalized. In the last few years, there has been considerable interest in equilibrium properties (e.g., existence, computational complexity, convergence, price of anarchy and stability) of opinion formation (see e.g., [START_REF] Bindel | How bad is forming your own opinion?[END_REF][START_REF] Bhawalkar | Coevolutionary Opinion Formation Games[END_REF] Munagala 2013; Ghaderi andSrikant 2014)). The main message is that these games are well-behaved due to their continuous strategy space. Specifically, they admit a unique equilibrium which can be computed efficiently and has small price of anarchy for symmetric weights.

Our k-approval voting model bears some resemblance to opinion formation with binary strategies [START_REF] Ferraioli | Decentralized dynamics for finite opinion games[END_REF]. Differently from our model, their model is restricted only to binary strategies, the influence weights are symmetric and not normalized. They proved that the price of anarchy is unbounded for α ≤ 1/2.

The partial information setting has strong connections with the class of aggregative games, e.g., [START_REF] Kukushkin | Best response dynamics in finite games with additive aggregation[END_REF][START_REF] Dindos | Better-reply dynamics and global convergence to Nash equilibrium in aggregative games[END_REF][START_REF] Jensen | Aggregative games and best-reply potentials[END_REF][START_REF] Acemoglu | Aggregate comparative statics[END_REF][START_REF] Babichenko | Fast Convergence of Best-Reply Dynamics in Aggregative Games[END_REF]. In this class of games the cost of each agents depends on the his own strategy and an aggregate of the strategies of all the agents.

Aggregating preferences under some metric function has been received attention in algorithms (see e.g., [START_REF] Ailon | Aggregating inconsistent information: Ranking and clustering[END_REF]) and in social choice (see e.g., [START_REF] Anshelevich | Approximating optimal social choice under metric preferences[END_REF]). Ours is the first work where aggregation under metric dissimilarity functions is used in modelling preference games.

Our Contribution

Our conceptual contribution is the new model of preference game which encompasses the full and the partial information settings. While the full information model is mostly inspired by the discrete preference game [START_REF] Chierichetti | On discrete preferences and coordination[END_REF], the partial information one introduces a novel feature in preference games, that is the aggregation function. Both settings are quite general and allow for a systematic study of the fundamental questions related to the existence and efficiency of (approximate) pure Nash equilibria in the strategic interaction of agents in social networks. On the technical side, we provide a comprehensive set of very general results on the existence and the structure of equilibria, and on the price of anarchy of the game. The first general message of these results is that the two settings, despite being very different from each other, behave very similarly, thus confirming our conjecture that in general the lack of information does not affect the existence and efficiency of the (approximate) equilibria. The second message is that our bounds on the price of anarchy are very general and are derived in terms of key features of the game (i.e., social impact, boundary and stretch). The third message is that low self-confidence levels (i.e., α ≤ 1/2) help with the existence of equilibria and simplify their structure, while high self-confidence levels (i.e., α > 1/2) help with the price of anarchy.

Specifically, in Section 2 we show that, unless α > 1/2 and the game is restricted, there always exists a ρapproximate equilibrium both for the full and the partial information case. In fact we observe that the two settings behave almost similarly. Specifically, if the agents are compliant (α < 1/2), any consensus (i.e., a state where all agents adopt the same strategy) is a ρ-equilibrium both for the full information case (Theorem 1) and the partial information one (Theorem 2); if the agents are stubborn (α > 1/2), we show that (when the game is unrestricted), in both settings, the state s in which each agent i adopts her preferred strategy s i is a ρ-equilibrium, and moreover such equilibrium is unique when ρ = 1 (Theorem 3); lastly, if the agents are balanced (α = 1/2), the set of ρ-equilibria in both settings is seemingly larger, as both the set of consensuses and s are ρ-equilibria (theorems 1, 2 and 3). Existence of approximate equilibria for the restricted case with α > 1/2 requires more assumptions (e.g., on the strategy space, the aggregation function, or the distance function) and is an interesting direction for further research.

In Section 3 we consider the price of anarchy wrt. SUM and MAX. We express the bounds on the price of anarchy wrt. social impact, the boundary and stretch of the game. Interestingly, also the bounds on the price of anarchy hold for both the full and the partial information settings, thus proving that the lack of information does not have any impact also on the inefficiency of the equilibria. Specifically, we observe that for compliant and balanced agents (α ∈ (0, 1/2]), the price of anarchy can be either unbounded for the restricted case (Proposition 1) or +∞ for the unrestricted one (Proposition 2); these hold for both objectives. So, if selfconfidence level is low, the price of anarchy of our preference game behaves similarly to that of the discrete preference game [START_REF] Chierichetti | On discrete preferences and coordination[END_REF] and of the opinion formation game with binary strategies (Ferraioli, Goldberg, and Ventre 2016). On the other hand, if the agents are stubborn (α > 1/2), we show that the price of anarchy is bounded from above by ρ Z 1 + δ (1-α) α τ β , wrt. SUM (Theorem 4), and by ρ Z 1 + (1-α) α τ β , wrt. MAX (Theorem 5). We also show that these bounds hold with τ = 1 for the full information setting (Lemma 3 and Remark 1), thus proving that τ is the parameter which quantifies the lack of information. Notice that, in order to provide bounds on the price of anarchy only as functions of α, δ and ρ Z (notice that δ is always upper bounded by n -1), we need additional assumptions on the structure of the game which allow us to estimate the values of τ (for the partial information case) and β; we illustrate several examples in Section 4.

In Section 4, we provide upper bounds on τ and β for several significant cases. Interestingly, our bounds on β depend only on α, while our bounds on τ may depend on the aggregation function, the metric space and the influence weights.

In Section 5, we focus on the k-approval voting game. As we said in the introduction, this game is a spacial case of preference game, it is motivated by the k-approval voting and generalizes the opinion formation model with binary strategies [START_REF] Ferraioli | Decentralized dynamics for finite opinion games[END_REF]. Since d

(defined as L 2
2 ) is a (2, 1)-approximate metric (i.e., ρ = 2 and ρ Z = 1, given that it is equivalent to the Hamming distance when restricted to Z), the results from Section 3 carry over to this special case. The main technical result of Section 5 is an upper bound on β (Theorem 6) which, combined with the results in Section 3, implies interesting upper bounds of 1 + δ(2α -1) -2 τ and 1 + (2α -1) -2 τ on the price of anarchy wrt. SUM and MAX respectively, when α > 1/2. We recall that these bounds, as for the general case, hold with τ = 1 for the full information setting. Our analysis complements the results of [START_REF] Ferraioli | Decentralized dynamics for finite opinion games[END_REF] for the opinion formation model with binary strategies. For the partial information case we can derive specific bounds by applying the bounds on τ illustrated in Section 4. One of the most intriguing directions for further research is to determine under which assumptions the k-approval voting game admits equilibria for α > 1/2.

Existence of Approximate Equilibria

In this section we characterize the existence of equilibria.

Compliant and Balanced Agents.

Theorem 1. In the full information setting, if α ≤ 1/2 then any consensus e ∈ Z n is a ρ-equilibrum.

Lemma 1. In the partial information setting, if α ≤ 1/2 then aggr i ( x -i ) is a ρ-approximate best response for agent i with respect to x -i , for every partial strategy profile x -i . Moreover, if α < 1/2 and ρ = 1, aggr i ( x -i ) is the unique best response.

The following theorem is an immediate consequences of Lemma 1. Theorem 2. In the partial information setting, if α ≤ 1/2, then any consensus e ∈ Z n is a ρ-equilibrium.

Stubborn and Balanced Agents.

Lemma 2. If α ≥ 1/2 then s i is a ρ-approximate dominant strategy for every agent i ∈ N S . Moreover, if α > 1/2 and ρ = 1, s i is the unique dominant strategy.

Theorems 3 is an immediate consequence of Lemma 2. Theorem 3. If α ≥ 1/2 and the game is unrestricted (N S = N ) then s = (s 1 , s 2 , . . . , s n ) is a ρ-approximate equilibrium. Moreover, if ρ = 1 then s is the unique equilibrium.

Price of Anarchy

Compliant and Balanced Agents. This is the case in which the social cost of an equilibrium can be unboundedly larger than the social cost of any optimal configuration. Proposition 1. For α ∈ (0, 1/2], if the game is restricted (N S = ∅), then there exist instances for which both POA SUM and POA MAX are unbounded.

The proof of Proposition 1 considers a strategy universe U = {a, b, s} with Z = {a, b} and s i = s for all agents i ∈ N . If d(b, s) = , for some arbitrarily small > 0, d(a, b) = 1 and d(a, s) = 1 + , d is a metric. Then, the consensus on b is optimal, while the consensus on a is an equilibrium. If, instead, we consider Z = U = {a, s}, with d(a, s) = 1 and s i = s for all agents i, the state s, in which every agent chooses s, is optimal with SUM( s) = MAX( s) = 0, while the consensus on a is an equilibrium. Hence, we show that: Proposition 2. For α ∈ (0, 1/2], if the game is unrestricted (N S = N ), then there exist instances with for which both POA SUM and POA MAX are unbounded. Stubborn Agents. In theorems 4 and 5, we show general bounds on the price of anarchy that depend on δ, τ , β and α. The proof of Lemma 3 follows from the equilibrium condition, the triangle inequality and the definition of stretch. Lemma 3. For every agent i, equilibrium e and state z,

c F i ( e) ≤ ρ Z c F i ( z) + ρ Z (1 -α)π i ( z, e) , and
c P i ( e) ≤ ρ Z c P i ( z) + τ i ρ Z (1 -α)π i ( z, e) .
Proof. For the full information setting, using that e is an equilibrium, we have

c F i ( e) ≤ αd z(i), s i + (1 -α) j =i w ij d z(i), e(j) ≤ αd z(i), s i + ρ Z (1 -α) j =i w ij d z(i), z(j) + ρ Z (1 -α) j =i w ij d z(j), e(j) ≤ ρ Z c F i ( z) + ρ Z (1 -α)π i ( z, e)
, where the first inequality follows from the equilibrium condition, the second from the approximate triangle inequality and the third from the definition of the stretch, c F i ( z) and ρ Z . Analogously, in the partial information setting we have

c P i ( e) ≤ αd z(i), s i + (1 -α)d z(i), aggr i ( e -i ) ≤ αd z(i), s i + ρ Z (1 -α)d z(i), aggr i ( z -i ) + ρ Z (1 -α)d aggr i ( z -i ), aggr i ( e -i ) ≤ ρ Z c P i ( z) + ρ Z (1 -α)d aggr i ( z -i ), aggr i ( e -i ) ≤ ρ Z c P i ( z) + τ i ρ Z (1 -α)π i ( z, e
) . Also in this case the first inequality follows from the equilibrium condition, the second from the approximate triangle inequality, the third from the definition of c P i ( z) and ρ Z and the last from the definition of the stretch.

F i ( e) ≤ ρ Z c F i ( z) + τ i ρ Z (1 -α)π i ( z, e)
, for every agent i, equilibrium e and state z. This allows us to apply the same arguments without making a distinction between the full and partial information. This implies that the bounds on the price of anarchy of theorems 4 and 5 hold with τ = 1 for the full information setting. This is the evidence of the fact that τ is the parameter that measure the lack of information.

Theorem 4. If α > 1/2, POA SUM ≤ ρ Z 1 + δ (1-α) α τ β .
Proof. If E ⊆ O SUM , then POA SUM = 1. Otherwise, let e be any equilibrium and o ∈ O SUM be any optimal state with D( o, e) = ∅. We have

SUM( e) ≤ ρ Z SUM( o) + ρ Z (1 -α) i∈N τ i π i ( o, e) ≤ ρ Z SUM( o) + τ ρ Z (1 -α) i∈N j∈N \{i} w ij d o(j), e(j) = ρ Z SUM( o) + τ ρ Z (1 -α) j∈D( o, e) δ j d o(j), e(j) , (6)
where the first inequality follows from Lemma 3 and the definition of SUM, the second from the definition of τ and π i , and the last step from the definitions of D( o, e) and the social impact of j.

On the other hand,

SUM( o) ≥ α i∈N d o(i), s i = α i∈D( o, s) d( o(i), s i ) ≥ α i∈D( o, e) d o(i), s i ≥ α i∈D( o, e) β i d o(i), e(i) , (7)
where the first inequality follows from Lemma 4 and the second from the definition of boundary (5). Notice that the last expression is strictly larger than 0 because α > 1/2, β i > 0 and d o(i), e(i) > 0 for every i ∈ D( o, e) = ∅. Therefore, we can conclude that

POA SUM ≤ ρ Z SUM( o) + τ ρ Z (1 -α) j∈D( o, e)
δ j d o(j), e(j)

SUM( o) ≤ ρ Z + τ ρ Z (1 -α) j∈D( o, e) δ j d o(j), e(j) α i∈D( o, e) β i d o(i), e(i) ≤ ρ Z 1 + δ (1 -α) α τ β ,
where the first inequality follows from ( 6), the second from ( 7), and the third from the definitions of δ, β.

Theorem 5. If α > 1/2, POA MAX ≤ ρ Z 1 + (1-α) α τ
β . The proof of Theorem 5 is similar to that of Theorem 4.

Some Bounds on the Boundary and Stretch

Next, we show bounds on the boundary and the stretch under quite general assumptions on the structure of the game.

We start with a technical claim which will be used to bound β. Proposition 3. If ρ Z = 1 then for any equilibrium e ∈ E, any agent i, and any strategy x = e(i), we have

d(x, s i ) ≥ d e(i), s i - (1 -α) α d
x, e(i) .

Proposition 4. If α > 1/2 and ρ = 1 then β ≥ 2α-1 2α . Proof. For any equilibrium e ∈ E, any agent i, and any strategy x = e(i), we have

d(x, s i ) ≥ d e(i), s i - (1 -α) α d x, e(i) ≥ d x, e(i) -d(x, s i ) - (1 -α) α d x, e(i) ≥ 2α -1 α d x, e(i) -d(x, s i ),
where the first inequality follows from Proposition 3 and the remaining inequalities from the triangle inequality. The theorem follows by adding d(x, s i ) to each side of the previous inequality and dividing by 2.

Proposition 5. For α > 1/2, if either the game is unrestricted (N S = N ) or d is uniform then β = 1.

We proceed to show some upper bounds on the stretch. Since τ = 1 in the full information case, we next restrict our attention on the partial information case. Proof. In the definition of τ i , we have τ i = 1, if π i ( e, y) = d(aggr i ( e -i ), aggr i ( y -i )) = 0. Hence, we assume that π i ( e, y) > 0.

We let w min (i) = min j =i:wij >0 w ij . Then, π i ( e, y) = j =i w ij d( e(j), y(j)) ≥ w min (i) d min (Z), because e(j), y(j) ∈ Z, there is at least one positive term in the sum, and if either w ij = 0 or d( e(j), y(j)) = 0, the corresponding term is 0. Moreover, d(aggr i ( e -i ), aggr i ( y -i )) ≤ d max (Z), because aggr i ( e -i ), aggr i ( y -i ) ∈ Z. Therefore,

τ i ≤ d max (Z) w min (i) d min (Z)
.

Using that the global stretch τ = max i∈N τ i and that w min = min i∈N w min (i), we conclude the proof of the proposition.

Unless we impose additional structures, the upper bound of Proposition 6 is essentially the best possible, because there are examples where a small change in a single coordinate of a state moves the aggregate to a diametrically different strategy. E.g., consider Z = {0, 1}, e -i = (0, 1, 1), y -i = (0, 0, 1), w i1 = w i3 = 1-ε 2 and w i2 = ε, and the Fréchet median as aggregation function. Clearly, aggr i ( e -i ) = 1, while aggr i ( y -i ) = 0.

For the following propositions, we restrict the definition of τ to optimal states o (either o ∈ O SUM or o ∈ O MAX ), instead of arbitrary states y. Proposition 7. If either every optimum (wrt. any objective) is a consensus or every equilibrium is a consensus then a) τ ≤ 2, if ρ Z = 1 and aggr is the Fréchet median;

b) τ = 1, if d is L 2
2 and aggr is the Fréchet median.

k-Approval Voting Game

In this section we discuss how the results developed in the previous sections can be used, together with other technical considerations, to characterize the equilibria and their efficiency in the k-approval voting game.

Existence of approximate equilibria. The approval voting model does not admit an exact potential function (due to the asymmetry of w ij , even for binary strategies). Instead, since d is a (2, 1)-approximate metric, Theorem 1, Theorem 2 and Theorem 3 apply to this setting, implying the existence of 2-approximate pure Nash equilibria in both the full and partial information settings. Moreover, by using (Ferraioli, Goldberg, and Ventre 2016, Observation 2.2), we can show that our approval voting game admits an equilibrium for the game with binary strategies when α ∈ [0, 1].

Price of anarchy. In order to bound the price of anarchy for the k-approval voting game, we first derive a lower bound on β.

Theorem 6. For every integers k, m, with 0

< k < m, if α > 1/2 then β ≥ 2α-1 2α
2 for the k-approval voting game.

Proof. To obtain a lower bound on β i , we fix an equilibrium e ∈ E and a strategy x ∈ Z with e(i) = x, and find s * i = arg min si∈U d(x, s i )/d(x, e i ). Then, we conclude that β i ≥ d(x, s * i )/d(x, e(i)). Throughout the proof, we let [m] = {1, . . . , m}. We also let x(j), s i (j) and e(i)(j) denote the j-th coordinate (bit) of strategies x, s i and e(i).

To this end, for any fixed strategy x ∈ Z, let C 0 = {j ∈ [m] : x(j) = 0} and let C 1 = {j ∈ [m] : x(j) = 1} be indices j for which x(j) is 0, for C 0 , and 1, for C 1 . We recall that |C 1 | = k and |C 0 | = m -k. Moreover, for the equilibrium strategy e(i) ∈ Z, we let C 01 = {j ∈ C 0 : e(i)(j) = 1} and C 10 = {j ∈ C 1 : e(i)(j) = 0} be indices j where x(j) = e(i)(j). Since both x and e(i) include exactly k ones and m -k zeros, |C 01 | = |C 10 |. In the following, we denote |C 01 | = |C 10 | = , for simplicity, for some 1 ≤ ≤ k. Using this notation, we can write that d(x, e(i)) = 2 .

Our goal is to find min si∈U d(x, s i )/(2 ), for any fixed ∈ {1, . . . , k}, under the constraints that s i ∈ U , x ∈ Z, and e(i) ∈ Z is an equilibrium strategy. We first observe that

d(x, s i ) 2 = 1 2   j∈C0 s i (j) 2 + j∈C1 (1 -s i (j)) 2   , (8)
where

j∈C0∪C1 s i (j) = k and s i ∈ [0, 1] m . ( 9
)
Since e is an equilibrium and d is an exact metric on Z (d is identical to the Hamming distance on Z), we can apply Proposition 3 and obtain

d e(i), s i -d(x, s i ) ≤ (1 -α) α d x, e(i) = (1 -α) α 2 . (10)
Moreover, for any j ∈ C 10 ∪ C 01 , x(j) = e(i)(j), we have

d( e(i), s i ) -d(x, s i ) = j∈C10 s i (j) 2 -(1 -s i (j)) 2 + j∈C01 (1 -s i (j)) 2 -s i (j) 2 = 2 j∈C10 s i (j) -2 j∈C01 s i (j) ,
where, for the last equality, we use the fact that |C 10 | = |C 10 |. Using (10), we conclude that for any equilibrium strategy e(i) ∈ Z and any strategy x ∈ Z with d(x, e(i)) = 2 , s i satisfies

j∈C10 s i (j) - j∈C01 s i (j) ≤ (1 -α)/α. (11)
Therefore, we can find min si∈S d(x, s i )/(2 ) by computing an s i that minimizes (8), subject to ( 9) and ( 11). We can do so by solving a strictly convex minimization problem with linear constraints.

In the supplementary material, we show that the minimizer s * i of ( 8), subject to ( 9) and ( 11), achieves an objective value of d(x, s * i )/(2 ) = 2α-1 2α 2 . Moreover, s * i is defined for any strategy x ∈ Z and any equilibrium strategy e(i) ∈ Z with d(x, e(i)) = 2 > 0, and always attains the same objective value d(x, s

* i )/(2 ) = 2α-1 2α 2 .
The proof of Theorem 6 actually shows something stronger, namely that for any equilibrium strategy e(i) ∈ Z and any x ∈ Z, with x = e(i), there is a preferenced strategy s * i ∈ S, defined as in the proof of Theorem 6, such that d(x, s * i )/d(x, e(i)) = 2α-1 2α 2 . Therefore, the proof of Theorem 6 shows that for any agent i,

β i = 2α-1 2α 2 .
Combined with Theorem 4, Theorem 5 and the fact that ρ Z = 1, Theorem 6 implies that, when α ≥ 1/2, for the k-approval voting game

POA SUM ≤ 1 + δ 4α(1 -α) (2α -1) 2 τ ≤ 1 + δ(2α -1) -2 τ,
and

POA MAX ≤ 1 + δ 4α(1 -α) (2α -1) 2 τ ≤ 1 + (2α -1) -2 τ.
We recall that these bounds hold with τ = 1 for the full information case (see Remark 1). These results complements the results in [START_REF] Ferraioli | Decentralized dynamics for finite opinion games[END_REF] for the binary opinion formation model. By applying Proposition 7, we obtain that these bounds hold with τ = 1 also for the partial information setting when the aggregation function is the Fréchet median and either every optimum (wrt. any objective) or every equilibrium is a consensus.

Proof. We prove the statement for the Fréchet mean. A virtually identical argument applies to the Fréchet median.

Let i be any agent, and x and y be any pair of states. It is straightforward to verify unanimity, namely, that if x -i is a consensus on x ∈ Z, then mean( x -i ) = x. In fact, every term of the summation would be 0 in x.

We proceed to prove consistency. Let us assume that j =i w ij d( x(j), y(j)) = 0. If x(j) = y(j) for all coordinates j = i, then x -i and y -i are identical and mean i ( x -i ) = mean i ( y -i ). So, let us assume that for some coordinates j, x(j) = y(j). Since j =i w ij d( x(j), y(j)) = 0, it must be w ij = 0 for all coordinates j with x(j) = y(j). Equivalently, for every j with w ij > 0, we have that x(j) = y(j). Therefore, for every y ∈ Z, it holds that j∈N \{i}

w ij d 2 y, x(j) = j∈N \{i} wij >0 w ij d 2 y, x(j) = j∈N \{i} wij >0 w ij d 2 y, y(j) = j∈N \{i} w ij d 2 y, y(j) ,
which implies that mean i ( x -i ) = mean i ( y -i ).

B Missing Proofs

Proof of Theorem 1

Proof. Let i be any agent, e any consensus, and x = e(i) any strategy. Using the facts that d( e(i), e(j)) = 0, we obtain that:

c F i e = αd s i , e(i) ≤ ρ αd(s i , x) + αd x, e(i) (12)
≤ ραd(s i , x) + ρ(1 -α)d x, e(i) (13) = ραd(s i , x) + ρ(1 -α) j =i w ij d x, e(i) (14) = ραd(s i , x) + ρ(1 -α) j =i w ij d x, e(j) (15) = ρc F i [ e -i , x]
, where (12) follows from the approximate triangle inequality, (13) from α ≤ 1/2, (14) from j =i w ij = 1, and ( 15) from e(i) = e(j).

Proof of Lemma 1

Proof. Let i be any agent, x any state, and x = aggr i ( x -i ) any strategy. Using the facts that aggr i ( x -i ) ∈ Z and d(aggr i ( x -i ), aggr i ( x -i )) = 0, we obtain that:

c P i [ x -i , aggr i ( x -i )] = αd aggr i ( x -i ), s i ≤ ρ αd x, s i + αd x, aggr i ( x -i ) (16) ≤ ραd x, s i + ρ(1 -α)d x, aggr i ( x -i ) (17) = ρc P i [ x -i , x]
, where ( 16) follows from the approximate triangle inequality and ( 17) from α ≤ 1/2. Notice that if α < 1/2 then ( 17) is strict and hence, when ρ = 1, aggr i ( x -i ) is the unique best response.

Proof of Lemma 2

Proof. Let us assume that α ≥ 1/2. Let i be any agent in N S and let x be any state with x(i) = s i (recall that |Z| ≥ 2).

Since s i ∈ Z, in the full information setting we have

c F i [ x -i , s i ] = αd(s i , s i ) + (1 -α) j =i w ij d s i , x(j) = (1 -α) j =i w ij d s i , x(j) ≤ ρ(1 -α) j =i w ij d s i , x(i) + d x(i), x (j)
≤ ραd s i , x(i) + ρ(1 -α)

j =i w ij d x(i), x(j) = ρc F i ( x)
, where the first inequality follows from the approximate triangle inequality and the second from j =i w ij = 1 and α ≥ 1/2. Notice that if α < 1/2, then the second inequality is strict and hence, when ρ = 1, s i is the unique dominant strategy.

Analogously, in the partial information setting we have

c P i [ x -i , s i ] = αd s i , s i + (1 -α)d s i , aggr i ( x -i ) = (1 -α)d s i , aggr i ( x -i ) ≤ ρ(1 -α) d x i , s i + d x i , aggr i ( x -i ) ≤ ραd x i , s i + ρ(1 -α)d x i , aggr i ( x -i ) = ρc P i ( x)
. Also here, the first inequality follows from the approximate triangle inequality and the second from α ≥ 1/2. If α < 1/2, then the second inequality is strict, hence, s i is a strictly dominant strategy of agent i.

Proof of Proposition 1

Proof. We consider a set of instances with U = {a, b, s}, Z = {a, b} and S = {s}, (i.e., s i = s, for all i ∈ N ), where a, b, s are three distinct elements. Notice that N S = ∅. We recall that 0 < α ≤ 1/2. Since a, b, s are three distinct elements, the distance between every two elements of U is non-negative. Let the distance between b and s be an arbitrarily small positive number, i.e., d(b, s) = > 0. By Theorem 2, the state e in which every agent choses a is an equilibrium; hence, SUM( e) = nαd(a, s) and MAX( e) = αd(a, s). On the other hand, in the state o, in which every agent choses b, SUM( o) = nαd(b, s) = nα > 0 and MAX( o) = αd(b, s) = α > 0. We can conclude that POA SUM = POA MAX ≥ d(a,s) . Since is an arbitrarily small positive number, the claim follows.

Proof of Lemma 4

Proof. Let i be any agent in D( o, e). We prove the claim by showing that i belongs also to D( o, s). If i ∈ N S then, by Theorem 3, e(i) = s i . Since o(i) = e(i), we also have that o

(i) = s i , i.e., i ∈ D( o, s). If i ∈ N \ N S then s i does not belongs to Z. Since o(i) belongs to Z, this trivially implies that o(i) = s i , i.e., i ∈ D( o, s).

Proof of Theorem 5

Proof. Let us consider the full information setting first.

If E ⊆ O MAX , then trivially POA MAX = 1.

Otherwise, let e ∈ E and o ∈ O MAX be two states such that D( o, e) = ∅. We recall that α > 1/2. Let i be one of the agents with maximum cost at equilibrium, i.e., c F i ( e) = MAX( e). We have

MAX( e) ≤ ρ Z MAX( o) + τ i ρ Z (1 -α)π i ( o, e) ≤ ρ Z MAX( o) + τ ρ Z (1 -α) j∈N \{i} w ij d o(j), e(j) , (18)
where the first inequality follows from Lemma 3 and the second from the definition of τ and π i . Notice that, if none of the agents in N \ {i} is in D( o, e), then every term in the summation in ( 18) is 0 and the inequality becomes MAX( e) ≤ MAX( o), which implies POA MAX = 1.

Therefore, let us assume that {N \ {i}} ∩ D( o, e) = ∅ and let j * be any agent in such set maximizing the distance between the strategy at the optimum and the one at the equilibrium, i.e., j * ∈ arg max j∈D( o, e) j =i d o(j), e(j) . Then we can write

MAX( e) ≤ ρ Z MAX( o) + τ ρ Z (1 -α) j∈N \{i} w ij d o(j * ), e(j * ) = ρ Z MAX( o) + τ ρ Z (1 -α)d o(j * ), e(j * ) , (19)
where first step follows from (18) and the definition of j * , and the second from j∈N w ij = 1.

On the other side,

MAX( o) ≥ c F j * ( o) ≥ αd o(j * ), s j * ≥ αβ i • d o(j * ), e(j * ) , (20)
where the last inequality follows from the definition of boundary (5). Notice that the last expression is strictly larger than 0, because α > 1/2, β i > 0 and d o(j * ), e(j * ) > 0. Therefore, we can conclude that

POA MAX ≤ ρ Z MAX( o) + τ ρ Z (1 -α)d o(j * ), e(j * ) MAX( o) ≤ ρ Z + τ ρ Z (1 -α)d o(j * ), e(j * ) αβ i • d o(j * ), e(j * ) ≤ ρ Z 1 + (1 -α) α τ β ,
where the first inequality follows from ( 19), and the last from ( 20) and the definition of β.

For the partial information setting, the same argument applies by replacing c F i with c P i .

Proof of Proposition 3

Proof. Let us first focus on the full information setting. We apply the equilibrium condition and obtain that αd e(i), s i + (1 -α)

j =i w ij d e(i), e(j) ≤ αd(x, s i ) + (1 -α) j =i w ij d x, e(j) ,
which, by triangle inequality on Z, implies

d(x, s i ) ≥ d e(i), s i - (1 -α) α j =i w ij d x, e(j) - j =i w ij d e(i), e (j)
≥ d e(i), s i -(1 -α) α d x, e(i) .

This inequality holds also for the partial information setting. In fact, in this case, if we apply the equilibrium condition, we obtain αd e(i), s

i + (1 -α)d e(i), aggr i ( e -i ) ≤ αd(x, s i ) + (1 -α)d x, aggr i ( e -i ) ,
from which, by applying the triangle inequality on Z, we have

d(x, s i ) ≥ d e(i), s i - (1 -α) α d x, aggr i ( e -i ) -d e(i), aggr i ( e -i ) ≥ d e(i), s i - (1 -α) α d
x, e(i) .

Proof of Proposition 5

Proof. Let us first assume that the game is unrestricted, i.e., N S = N . Let us consider any equilibrium e ∈ E, any agent i and any strategy x = e(i) (recall that |Z| ≥ 2). In order to prove the claim, we need to show that d(x, s i ) = d x, e(i) .

Assuming α > 1/2, by Theorem 3, we get e(i) = s i , which implies that d(x, s i ) = d x, e(i) .

Next, we assume that (U, d) is a uniform metric. As before, we consider any equilibrium e ∈ E, any agent i and any strategy x = e(i). In order to prove the claim, we need to show that d(x, s i ) = d x, e(i) . Notice that, since x = e(i), we have d x, e(i) = 1. Therefore, in order for the claim to hold, it must be that d(x, s i ) = 1. By contradiction, let us assume that d(x, s i ) = 0, or equivalently x = s i . This implies that i belongs to N S . If we assume α > 1/2, by Theorem 3, we get s i = e(i), and by transitivity x = e(i), i.e., d x, e(i) = 0, contradicting the hypothesis.

Proof of Proposition 7

In the proof of Proposition 7, we use the following result: Theorem 7 ((Fanelli 2021)). Let i be any agent, x any state, and y any strategy in Z. If d is L 2 2 and aggr i is the Fréchet median then j∈N \{i} w ij d y, x(j) = d y, aggr i ( x -i ) + j∈N \{i} w ij d aggr i ( x -i ), x(j) .

We are now ready to prove the proposition.

Proof. We proof the clam for the case in which every optimum (wrt. any objective) is a consensus. The proof for the case in which every equilibrium is a consensus is symmetric and follows by simply exchanging the roles of e and o in the argument below.

We start with the proof of (a).

where ( 26) follows from Theorem 7 by setting y = aggr i ( o -i ) and x = e, and ( 27) from the fact that o is a consensus. Hence τi = 1. Using that τ i = max{ τi , 1} and τ = max i∈N τ i , we conclude the proof of (b).

Missing Details from the Proof of Theorem 6

Proof. We complete the proof of Theorem 6, by observing that we can find min si∈S d(x, s i )/(2 ) by computing an s i that minimizes (8), subject to ( 9) and (11). Since ( 8) is a strictly convex function of s i (1), . . . , s i (m) and the constraints of ( 9) and ( 11) are linear on s i (1), . . . , s i (m), we have to solve a strictly convex minimization problem with linear constraints. We observe that

s * i (j) =              2α -1 2α if j ∈ C 01 1 2α if j ∈ C 10 0 if j ∈ C 0 \ C 01 1 if j ∈ C 1 \ C 10
is feasible (i.e., it lies in S and satisfies (11)) and achieves an objective value of d(x, s * i )/(2 ) = 2α-1 2α 2 . Moreover, s * i is defined for any strategy x ∈ Z and any equilibrium strategy e(i) ∈ Z with d(x, e(i)) = 2 > 0 and always attains the same objective value d(x, s * i )/(2 ) = 2α-1 2α 2 .

To confirm that s * i is indeed a minimizer of the above strictly convex minimization problem, we observe that the KKT optimality conditions are satisfied at s * i with KKT multipliers µ = 2α-1 2 α for (11) and 0 for all the constraints of (9). To see this, let We first observe that complementary slackness constraints are satisfied, since g(s * i ) = 0 and all other KKT multipliers are 0. Primal and dual feasibility constraints are also satisfied. Regarding stationarity constraints, we observe that ∇ j f (s * i ) = 0, for any j ∈ C 01 ∪ C 10 , ∇ j f (s * i ) = 2α-1 2 α , for all j ∈ C 01 , and ∇ j f (s * i ) = 1-2α 2 α , for all j ∈ C 10 . Similarly, ∇ j g(s * i ) = 0 for any j ∈ C 01 ∪ C 10 , ∇ j g(s * i ) = -1, for all j ∈ C 01 , and ∇ j g(s * i ) = 1, for all j ∈ C 10 . Therefore, stationarity constraints are also satisfied with KKT multiplier µ = 2α-1 2 α .

Lemma 4 .

 4 If α > 1/2, for every equilibrium e and optimal state o ∈ O SUM with D( o, e) = ∅, we have D( o, e) ⊆ D( o, s), where s = (s 1 , s 2 , . . . , s n ). Remark 1. Since by definition τ i ≥ 1, for simplicty of exposition, in theorems 4 and 5 we relax the claim of Lemma 3 and assume c

Proposition 6 .

 6 It always holds that τ ≤ d max (Z) w min d min (Z) , where d max (Z) = max x,y∈Z d(x, y) is the diameter of Z, d min (Z) = min x =y:d(x,y)>0 d(x, y) is the minimum positive distance in Z, and w min = min i =j:wij >0 w ij is the minimum positive influence weight.

  Let us consider any equilibrium e ∈ E, any social optimum o (either o ∈ O SUM or o ∈ O MAX ) and any agent i. By the definition of the Fréchet median, j∈N \{i} w ij d aggr i ( e -i ), e(j) ≤ j∈N \{i} w ij d aggr i ( o -i ), e(j) .

ww

  have thatd aggr i ( o -i ), aggr i ( e -i ) = j∈N \{i} w ij d aggr i ( o -i ), aggr i ( e -i )(22)≤ j∈N \{i} w ij d aggr i ( o -i ), e(j) + j∈N \{i} w ij d aggr i ( e -i ), e(j) ij d aggr i ( o -i ), e(j) ij d o(j), e(j) = 2 • π i ( o, e),(25)where (22) follows from j∈N \{i} w ij = 1, (23) from the triangle inequality, (24) from (21) and (25) from the fact that o is a consensus. Hence τi ≤ 2. Using that τ i = max{ τi , 1} and τ = max i∈N τ i , we conclude the proof of (a).Let us prove (b) now. Also in this case, let us consider any equilibrium e ∈ E, any social optimum o (either o ∈ O SUM or o ∈ O MAX ) and any agent i. We have thatd aggr i ( o -i ), aggr i ( e -i ) ≤ j∈N \{i} w ij d aggr i ( o -i ), e(j)(26)= j∈N \{i} w ij d o(j), e(j) = π i ( o, e),

Appendix A Feasibility of Fréchet Mean and Fréchet Median

The following proposition shows that both aggregation functions ( 4) and (3) are feasible. Proposition 8. The Fréchet mean and the Fréchet median are feasible aggregation rules.