Péter Bayer
email: peter.bayer@tse-fr.eu.

Ani Guerdjikova
email: ani.guerdjikova@univ-grenoble-alpes.fr

Cécile Aubert

Roland Bénabou

Francis Bloch

Christophe Bravard

Matthew Jackson

Gyögy Kozics

Stéphane Lemarié

Ronald Peeters

Anastas Tenev

Optimism leads to optimality: Ambiguity in network formation *

Keywords: Ambiguity, network formation, optimism. JEL classification: C72, D81, D85

We analyze a model of endogenous two-sided network formation where players are affected by uncertainty about their opponents' decisions. We model this uncertainty using the notion of equilibrium under ambiguity. Unlike the set of Nash equilibria, the set of equilibria under ambiguity does not always include underconnected and thus inefficient networks such as the empty network. On the other hand, it may include networks with unreciprocated, one-way links, which comes with an efficiency loss as linking efforts are costly. We characterize equilibria under ambiguity and provide conditions under which increased player optimism comes with an increase in connectivity and realized benefits in equilibrium. Next, we analyze network realignment under a myopic updating process with optimistic shocks and derive a global stability condition of efficient networks. Under this condition, a subset of the Pareto optimal equilibrium networks is reached, specifically, networks that maximize the players' total benefits of connections.

Introduction

The question of how social networks form and which structures are both stable and efficient is of primary interest in economic literature. In this paper, we study the effect of perceived strategic uncertainty (ambiguity) and optimism on the outcomes of a network formation game. This question is of interest for two reasons. First, as explained below, empirical literature from social psychology as well as experimental studies on entrepreneurs, suggest that optimism is a relevant factor in network formation, which can improve both individual outcomes and social welfare. Using the concept of equilibrium under ambiguity by [START_REF] Eichberger | Optimism and pessimism in games[END_REF], our model provides a theoretical underpinning for these findings. Second, models of network formation exhibit large indeterminacy, allowing for both Paretodominated and Pareto-dominant equilibrium networks and thus raising the question of equilibrium selection. We address this by introducing a best-response dynamic similar to [START_REF] Kandori | Learning, mutation and long run equilibria in games[END_REF], (henceforth KMR) and [START_REF] Young | The evolution of conventions[END_REF] but with shocks affecting players' optimism. We derive conditions for this dynamic to reach a subset of the equilibrium networks which are not Pareto-dominated by other equilibria.

We model endogenous network formation, whereby a link between two players is treated as a valuegenerating opportunity (recording a duet, publishing a research paper, a productivity-increasing R&D partnership between two companies). As in [START_REF] Bloch | Communication networks with endogenous link strength[END_REF] and [START_REF] Ding | The formation of links and the formation of networks[END_REF], the value of each link depends on the identity of the partners. These values are assumed exogenous and are not subject to network externalities (the quality of a recording or of a published paper does not depend on the set of other recordings or papers; the increase in productivity does not affect the productivity of firms outside of the partnership). Linking is costly and requires efforts from both parties. The value of the link is realized if and only if both parties incur the cost. Notably, an investing player bears the cost even if her intended partner does not reciprocate [START_REF] Bala | A non-cooperative model of network formation[END_REF], thus generating strategic complementarities and a coordination problem on the level of link formation. Negative network externalities arise, because players' costs are assumed convex in the number of maintained links. A player is thus negatively affected by any two of the other players linking to each other, as this increases her potential partners' costs of linking to her and decreases her prospects of obtaining beneficial links. The convex cost assumption is clearly more general and realistic than the linear cost case studied in most of the literature1 . It imposes natural limits on the size of both the equilibrium and the efficient networks (contrary, e.g. to [START_REF] Goyal | Networks of collaboration in oligopoly[END_REF]'s "small costs" case and [START_REF] König | Nestedness in networks: A theoretical model and some applications[END_REF]). At the same time, the separation of the positive externalities on the level of bilateral links from the negative network externalities arising from cost, makes the analysis tractable, despite the fact that the resulting game is not supermodular.

Our first result is a characterization of the set of equilibrium networks for this game. As is common, (see, e.g., [START_REF] Brueckner | Friendship Networks[END_REF], [START_REF] Goyal | Networks of collaboration in oligopoly[END_REF]'s "large costs" case, [START_REF] Westbrock | Natural concentration in industrial research collaboration[END_REF], as well as [START_REF] Griffith | A continuous model of strong and weak ties[END_REF]; Baumann (2019)) this game has multiple Nash equilibria, some of which are Pareto dominated such as the empty network. Pairwise stability [START_REF] Jackson | A strategic model of social and economic networks[END_REF] can be used as a refinement on this set, but does not solve the problem of multiplicity. More restrictive concepts such as the strong equilibrium [START_REF] Jackson | Strongly stable networks[END_REF], or the bilateral equilibrium [START_REF] Goyal | Structural holes in social networks[END_REF], can achieve efficiency, but implicitly rely on the ability of pairs or groups of players to coordinate with respect to their linking decisions, while remaining silent on how such coordination would take place2 .

Instead, here we directly model the strategic uncertainty of the players arising from a lack of a natural coordination device. We follow [START_REF] Eichberger | Optimism and pessimism in games[END_REF] and introduce ambiguity about the strategy chosen by others combined with an attitude towards such ambiguity (optimism/pessimism). Notably, research in social psychology points out the relevance of optimism in the process of social network formation. Optimistic individuals are more likely to form and sustain beneficial links [START_REF] Brissette | The role of optimism in social network development, coping, and psychological adjustment during a life transition[END_REF]Andersson, 2012). The "tendency to expect favorable outcomes" [START_REF] Srivastava | Optimism, effects on relationships[END_REF] means that optimists attach more weight to their partners reciprocating their efforts towards establishing a relationship. Such expectations may become self-fulfilling as partners reciprocate even when without being optimistic. In general, optimism is identified as a pervasive individual feature [START_REF] Peterson | The future of optimism[END_REF], which is positive both for individuals and the society as a whole [START_REF] Freud | The future of an illusion[END_REF][START_REF] Tiger | Optimism: the biology of hope[END_REF].

In economics, experimental studies have shown that ambiguity in the other players' strategies is indeed present, leading to deviations from Nash equilibrium behavior [START_REF] Pulford | Ambiguous games: evidence for strategic ambiguity aversion[END_REF][START_REF] Mauro | Kindness confusion or[END_REF][START_REF] Eichberger | Granny versus game theorist: ambiguity in experimental games[END_REF]Kelsey andLe Roux, 2015, 2017). Attitudes towards such ambiguity show non-negligible rates of both optimism and pessimism [START_REF] Camerer | Ambiguity-aversion and non-additive beliefs in non-cooperative games: experimental evidence[END_REF][START_REF] Ivanov | Attitudes to ambiguity in one-shot normal-form games: an experimental study[END_REF][START_REF] Eichberger | Granny versus game theorist: ambiguity in experimental games[END_REF][START_REF] Li | Trust as a decision under ambiguity[END_REF]. Optimism emerges as a characteristic feature of successful entrepreneurs, which positively correlates with measures of performance, see [START_REF] Bengtsson | Do Women Have a Less Entrepreneurial Personality?[END_REF], [START_REF] Bogliacino | Aspirations, prospect Theory and entrepreneurship: evidence from Colombia[END_REF] and [START_REF] Persson | Entrepreneurial optimism and creative destruction[END_REF]. [START_REF] Holm | Entrepreneurs under uncertainty: An economic experiment in China[END_REF] identifies willingness to accept ambiguity in social interactions and to bet on the "trustworthiness" of a partner, to be a key characteristic of entrepreneurs. [START_REF] Dollinger | Intolerance of ambiguity and the decision to form an alliance[END_REF] confirms that tolerance towards ambiguity is positively related to an entrepreneur's willingness to engage in alliances. This suggests that ambiguity attitudes, and in particular, optimism, are also empirically relevant for the process of network formation.

Finally, optimism is known to act as an equilibrium selection device resulting in Pareto dominant equilibria in coordination games [START_REF] Eichberger | Strategic complements, substitutes and ambiguity: The implications for public goods[END_REF][START_REF] Eichberger | Granny versus game theorist: ambiguity in experimental games[END_REF] and leads to an increase in payoffs in the maximal equilibrium in supermodular games [START_REF] Schipper | The evolutionary stability of optimism, pessimism, and complete ignorance[END_REF].

We first examine the impact of ambiguity and optimism on equilibrium networks. As the game we study is not supermodular, equilibrium existence cannot be established by [START_REF] Topkis | Equilibrium points in nonzero-sum n-person submodular games[END_REF]'s theorem. We prove existence (Proposition 3.3) by showing that, starting from any network, a sequence of unilateral best-responses (under ambiguity) leads to an equilibrium in a finite number of steps. This result provides an algorithm for identifying equilibria under ambiguity in a network formation game, and shows that such equilibria are stable under simple learning dynamics. We provide a characterization of the equilibrium networks under ambiguity.

We next discuss the effect of increased optimism in equilibrium networks under ambiguity. Optimism increases the weight players place on others reciprocating a link and thus increases the maximal number of links a player initiates as a best-response (Proposition 3.5). However, the effect of optimism on actually realized links is ambiguous: a player who becomes more optimistic might sever existing links in favor of more valuable, but unreciprocated ones, resulting in a less connected network. This is precluded by a condition called monotonicity. A network is monotonic (in linking decisions) if for each player, any initiated link is at least as valuable to her in expectation as any of the uninitiated links. If an equilibrium network is monotonic then any increase of the players' optimism parameters results in a weakly more connected equilibrium (Proposition 3.7).

Except for cases of extreme ambiguity, the introduction of ambiguity per se does not resolve the problem of equilibrium multiplicity. Our second set of results thus concerns the impact of ambiguity on network realignment. While equilibrium analysis offers interesting insights, social networks are, by their nature, changeable: relationships and partnerships continuously form and break apart with much of this variation unaccounted for by changes in economic fundamentals. In our model such variations can be attributed to changes in the players' subjective ambiguity perception and optimism. Indeed, high-arousal emotional states (joy, fear, anger) are known to increase ambiguity perception, while low-arousal states (sadness, contentment) decrease it [START_REF] Baillon | Sadder but wiser: The effects of emotional states on ambiguity attitudes[END_REF].

On the other hand, experiences of positive emotions is a key determinant of an individual's optimism (positive psychology) [START_REF] Fredrickson | The role of positive emotions in positive psychology: The broaden-and-build theory of positive emotions[END_REF]. We thus consider the network's evolution under best-response dynamics with random changes in the individuals' ambiguity and optimism parameters. Similarly to KMR, we assume that players have realistic, utility-maximizing preferences (without ambiguity) and play the game accordingly, except in periods when they receive a random shock. Differently from KMR, the deviation in behavior related to the shock is not random, but optimal by their current ambiguity perception and attitude. Shocks are temporary and may be followed by the player becoming again realistic in the next period. Shocks that induce high levels of optimism lead to players more actively pursuing high-value links, possibly by discarding already existing ones. Highly pessimistic players discard existing links without forming new ones. Thus, to capture more interesting cases of network realignment, we focus on shocks that amount to surges of optimism.

Best-response dynamics as in KMR have been studied both in network formation games [START_REF] Watts | A dynamic model of network formation[END_REF] as well as in network games with simultaneous choice of links and actions [START_REF] Ely | Local conventions. The B.E[END_REF]Jackson and Watts, 2002a,b;[START_REF] Goyal | Learning, network formation and coordination[END_REF][START_REF] Hojman | Endogenous networks, social games and evolution[END_REF][START_REF] Galeotti | The law of the few[END_REF][START_REF] Dawid | The evolution of R&D networks[END_REF], see Hellman and Staudigl (2014) for a review. In general, neither uniqueness of the stochastically stable state, nor its efficiency within the set of Nash equilibria are guaranteed3 . Recent research has also identified the role of farsightedness for convergence to optimal networks, [START_REF] Luo | Network formation with myopic and farsighted players[END_REF].

In contrast, the dynamic with optimistic shocks leads to a set of equilibrium networks which are Pareto-undominated in the set of Nash equilibria independently of the starting network or of the probability of optimistic surges, provided that a property we call the 'alignment of preferences' is met (Propositions 4.4 and 4.5). In particular, our dynamic selects the networks that maximize the players' total benefits of connections. Aligned preferences means that all networks that maximize the players' benefits from network connections in the set of Nash equilibrium networks (a social consideration) are monotonic (an individual consideration). Thus, social considerations 'align' with individual ones. This condition is always satisfied if the values of all links are identical. Therefore, surges of individual optimism lead to the formation of an optimal equilibrium network if efficiency is measured by the size of the network, a property that even previously considered pairwise notions fail to satisfy in this relatively simple case. If the condition is not met, a minimal counterexample of three players shows that these dynamics fail to produce the efficient network as the efficient network itself is unstable to surges of optimism.

The rest of the paper is organized as follows: Section 2 introduces the network formation game and defines the equilibrium under ambiguity concept. Section 3 analyzes the static network formation game under ambiguity; we show existence of equilibria, we provide a characterization, and study the comparative statics with respect to the players' attitude towards ambiguity. In Section 4, we turn towards a dynamic analysis of network realignment. We analyze a best-response dynamic with optimistic shocks and analyze its long-term behavior. For aligned preferences, the dynamic almost surely reaches the set of efficient networks in finite time. Section 5 concludes.

The network formation game

Notation and definitions

Let n > 1 and let I = {1, . . . , n} be the finite set of players. A network on this set of players is represented by a binary n × n matrix x. For a disjoint pair i, j ∈ I if x ij = 1, then we say that i has a directed link towards j, or i links to j. If x ij = x ji = 1, we say that i and j are reciprocally linked to each other. As a shorthand we write {i, j} ∈ x to mean x ij = x ji = 1 and {i, j} / ∈ x to mean x ij = x ji = 0. By convention, for every i ∈ I we set the values x ii to 0. Let the set of networks of n players be denoted by X.

The network x ∈ X is undirected if for every disjoint i, j ∈ I it holds that x ij = x ji .

Definition 2.1 (Neighborhoods and degrees in directed networks). For i ∈ I we let

N + i (x) = {j ∈ I : x ij = 1}, N - i (x) = {j ∈ I : x ji = 1}
denote the set of players who player i links to and the set of players who link to player i in network x, respectively. The set

N i (x) = N + i (x) ∩ N - i (x) is called the neighborhood of player i. For i ∈ I let deg + i (x) = |N + i (x)|, deg - i x = |N - i (x)|, and deg i (x) = |N i (x)
| denote player i's out-degree, in-degree, and degree, respectively.

It is clear that for undirected networks, the three neighbor sets and degrees coincide.

Definition 2.2 (Maximal undirected network contained in a network). Let the map y : X → X be defined as follows: for every disjoint i, j ∈ I, y(x) ij = y(x) ji = x ij x ji . The network y(x) is the maximal undirected network contained in x.

For X ′ ⊆ X we let y(X ′ ) denote the image of X ′ under y. We introduce y(X) = Y to denote the set of undirected networks. For Y ′ ⊆ Y we let y -1 (Y ′ ) denote the pre-image of Y ′ , i.e. the set of directed networks, whose maximal undirected network is a member of Y ′ .

For an undirected network y ∈ Y let |y| = i∈I deg i (y)/2 denote the number of links in y.

Definition 2.3. For two undirected networks x, x ′ we write x ≤ x ′ if for every i, j ∈ I we have

x ij ≤ x ′ ij .
As typical, we write x < x ′ to denote the asymmetric part of the relation x ≤ x ′ . For undirected networks x, x ′ ∈ Y , the union and set subtraction operators ∪ and \ are interpreted the same way as for sets. Specifically, the network (x \ x ′ ) ∪ (x ′ \ x), containing all links that appear in exactly one of x and x ′ is called the symmetric difference between x and x ′ . Definition 2.4 (Distance between undirected networks). For two undirected networks

x, x ′ ∈ Y the value ϕ(x, x ′ ) = |(x \ x ′ ) ∪ (x ′ \ x)| is called the distance between x and x ′ .

Game definition

We now define a game of network formation with additive benefits gained from direct interactions. Let W be an n × n non-negative, symmetric, real matrix with the convention w ii = 0 for i ∈ I, called the matrix of benefits. Let c i : N → R + be a strictly increasing, weakly convex function, such that c i (0) = 0, called player i's cost function. We write c = (c i ) i∈I for the vector of cost functions. A network formation game is parameterized by the pair (W, c), which we take as given.

A strategy of player i is a binary n-vector x i = (x ij ) j∈I with x ij = 1 representing the choice by i to link to j, and x ij = 0 representing the choice not to link. By convention we take x ii = 0 for all i ∈ I. The aggregate of the players' decisions (x i ) i∈I forms the directed network x. Let X i denote player i's set of strategies.

The payoff of player i ∈ I is given as follows.

u i (x) = j̸ =i w ij x ij x ji -c i (deg + i (x)). ( 1
)
The interpretation is the following: The players may form costly links with other players to receive the benefit associated with that link as given by the weight matrix. Benefits of links are only realized by the participants if both decide to link to one another. If only one decides to link to the other, a one-sided link is formed without any benefits to either player, if both decide not to link, no link is formed and no benefits are realized. Crucially, players incur costs of all outgoing links even ones that are not reciprocated. Our game therefore bears a resemblance to [START_REF] Myerson | Game theory: analysis of conflict[END_REF]'s independent link-formation process.

We show an application of this game in a model of monopolistic competition between firms with partnerships.

Example 2.5 (Monopolistic competition with partnerships, adapted from [START_REF] Acemoglu | Distance to Frontier, Selection and Economic Growth[END_REF] and [START_REF] König | Endogenous technology cycles in dynamic R&D Networks[END_REF]). Consider a set of n firms, each producing an intermediate good used to produce a final good (a numeraire) according to a production function

y (q 1 , . . . , q n ) = 1 γ n i=1 A 1-γ i q γ i ,
where γ ∈ (0, 1), q i is the amount of the intermediate good i, whereas A i is the productivity of firm i. The production function of firm i transforms a unit of the numeraire good into a unit of the intermediate good. The inverse demand of the final producer for intermediate good i is easily computed to be:

ρ i (q i ) = A i q i 1-γ
implying that the optimal supply of firm i is given by

q * i = γ 1 1-γ A i
and its maximal profit is:

π * i = (1 -γ) γ γ 1-γ A i . Denoting by ϕ = (1 -γ) γ γ 1-γ , π * i = ϕA i .
Suppose that intermediate good producers can engage in partnerships which can generate increases in productivity. These are specific to the firms engaging in the partnership so that the success of a given partnership has no effect on the added value obtained from other partnerships. The increase in productivity is given by

w ij ϕ =
w ji ϕ ≥ 0 for each of the partner-firms and is realized if and only if both firms simultaneously put in a costly effort such as sharing know-how, engaging in further research and development, or coordinating managerial activities. 4 If only one of the firms contributes to the partnership, it bears the cost of the effort, even though no increase in productivity is generated. Let x ij ∈ {0, 1} denote the unilateral decision of firm i to partner with j and thus to incur the cost of such a partnership. The cost of effort is firm-specific and depends on the number of partnerships the firm is actively engaged in, c i j̸ =i x ij with marginal cost increasing in the number of existing partnerships. Thus, the final profit of a given firm can be written as:

π i (x i , x -i ) = ϕ   A i + j̸ =i w ij ϕ x ij x ji   -c i   j̸ =i x ij   = π * i + j̸ =i w ij x ij x ji -c i   j̸ =i x ij  
implying that each firm will select its partnerships to maximize (1).

We continue with a useful notation for marginal benefits and marginal costs.

Definition 2.6 (Marginal benefits, marginal costs). Let a network x ∈ X be given. Then, player i's benefit from her marginal link is w

′ i (x) = min j∈N + i (x) {w ij }. For r ∈ N, player i's marginal cost function is given by c ′ i (r) = c i (r) -c i (r -1) if r is positive and c ′ i (0) = 0.
By convention we have min ∅ = ∞. Note that, while player i's benefit from her marginal link equals the lowest value of her reciprocated link (i.e. her marginal benefit) if x is undirected, in directed networks we look at outgoing links. In the special case of linear cost functions, we denote constant marginal cost of player i by c i .

We assume for simplicity that marginal costs are never equal to marginal benefits, that is, for every natural integer r and disjoint pair of players i, j ∈ I we have w ij ̸ = c ′ i (r). We make this assumption to simplify characterizations by avoiding indifference, but it may also be interpreted as the players always preferring not to link in case they are indifferent. Within the set of all possible matrices W and cost functions c, this property is generic.

We now introduce the equilibrium concepts of the game without ambiguity to serve as benchmarks. For a player i ∈ I, let X -i = j̸ =i X i . The set of best response strategies of player i to the strategy combination chosen by the other players is given by B i (x -i ) defined by:

B i (x -i ) = arg max x i ∈{0,1} n   j̸ =i w ij x ij x ji -c i (deg + i (x))  
As usual in the literature, we write B i (x).

Definition 2.7. A network x is a Nash equilibrium of the game of network formation iff x i ∈ B i (x) for all i ∈ I.

The following characterization follows in a straightforward way.

Lemma 2.8 (Nash equilibrium characterization). A network x * is a Nash equilibrium if and only if it is undirected and

w ′ i (x * ) > c ′ i (deg i (x *
)) for all i ∈ I. Since linking to a player without reciprocation is costly without giving any immediate benefits, every Nash equilibrium is undirected, furthermore, each player's least profitable neighbor must bring more benefit than the marginal cost of the player's links. We denote the set of Nash equilibrium networks by X * .

The standard equilibrium concept for network formation games with two-sided link formation is pairwise stability [START_REF] Jackson | A strategic model of social and economic networks[END_REF]. Definition 2.9 (Pairwise stable equilibria). A network x is pairwise stable if for any pair {i, j} ∈ x we have u i (x) ≥ u i (x \ {i, j}) and u j (x) ≥ u j (x \ {i, j}), for any pair {i, j} / ∈ x we have either

u i (x) > u i (x ∪ {i, j}) or u j (x) > u i (x ∪ {i, j}).
Pairwise stable networks have two properties: no player should be better off deleting any of her existing links, and no two unlinked players should be better off by forming a reciprocated link. Their characterization in our game follows in a straightforward way.

Lemma 2.10 (Pairwise stable equilibrium characterization). The network x * is a pairwise stable equilibrium if and only if if x * is a Nash equilibrium and for every i, j ∈ I for which x * ij = x * ji = 0 we have w ij < max{c ′ i (deg i (x * ) + 1), c ′ j (deg j (x * ) + 1)}. Equivalently, x * is a pairwise stable equilibrium if and only if it is a maximal Nash equilibrium.

Since, in a pairwise stable equilibrium, every mutually profitable link is already formed, any link that did not end up forming must be unprofitable for at least one participant.

In this paper we are interested in the conditions that allow the players' optimism to increase efficiency in network formation games. We raise two notions of efficiency, Pareto optimality and benefitmaximization in the set of Nash equilibria.

Definition 2.11 (Pareto optimal equilibrium network). A Nash equilibrium network x ∈ X * is a Pareto optimal equilibrium network if there does not exist another Nash equilibrium network x ′ ∈ X * such that u i (x ′ ) ≥ u i (x) for all i ∈ I with at least one strict inequality.

Clearly, a Pareto optimal Nash equilibirium network has to be pairwise stable, but not every pairwise stable equilibrium is Pareto optimal. Note that even Pareto optimal equilibrium networks may be Pareto dominated by other networks that are not an equilibrium; our restriction to the set of Nash equilibria guarantees that individual participation constraints are satisfied, a crucial consideration in non-cooperative models of network formation.

Our second efficiency notion measures the players' total benefits. For a network x, let v(x) = i∈I i̸ =j w ij x ij x ji denote the total sum of realized benefits. It is clear that v(x) = v(y(x)).

Definition 2.12 (Maximum-benefit equilibrium networks). The network x * ∈ X * is called a maximumbenefit equilibrium (MBE) network if x ∈ argmax x∈X * v(x).

Let the set of MBE networks be denoted by V * . Such networks maximize total benefits from connections in the society, while ensuring that for each player i, the value she derives from her marginal link exceeds her cost, and i chooses her connections optimally given the behavior of the other players. Thus, they satisfy a participation constraint and an incentive constraint for each individual and can be, in principle, decentralized.

The basis of MBE networks is utilitarian efficiency but without explicitly considering the players' costs -although they do play some role as they are selected from the set of Nash equilibrium networks. Two conceptual reasons may exist to consider MBE in favor of or in addition to utilitarian efficient networks: (1) costs are player-specific constraints of maintaining social links, as such, in certain situations, benefits can be more easily transferable and measurable, while costs are hidden, (2) planners may be interested in the formation of the largest network (e.g. most duets recorded, most papers produced, most production cost-reducing partnerships formed) satisfying the players' participation constraints, rather than the utilitarian efficient one.

If all players' cost functions are linear, i.e. c i (deg

+ i ) = c i • deg + i for constant values c i ,
the notions of pairwise stability, Pareto optimality, and MBE networks coincide in a unique network defined by {i, j} ∈ x ⇔ w ij > max{c i , c j }.

Ambiguity attitudes and equilibrium under ambiguity

The concept of Nash equilibrium presupposes that players have correct beliefs about their opponents' behavior and best-respond to these beliefs. In games with multiple Nash equilibria, such an assumption seems rather strong. While players might indeed entertain beliefs about the behavior of the other players in the game, they might have limited confidence in such beliefs. The theory of ambiguity allows us to model such uncertainty about the other players' strategies by the use of non-additive probabilities called capacities, see [START_REF] Schmeidler | Subjective probability and expected utility without additivity[END_REF]. 5The notion of a capacity is very general. In this paper, we use a special class of capacities, called NEO-additive capacities introduced by [START_REF] Chateauneuf | Choice under uncertainty with the best and the worst in mind: NEO-additive capacities[END_REF]. A NEO-additive capacity is determined by three components: the player i's additive belief about the other players' strategy x -i given by a probability distribution π i on X -i , the strength of the players' perception of ambiguity δ i ∈ [0, 1] and her attitude to it, her degree of optimism, α i ∈ [0, 1].

The NEO-additive capacities thus provide a parsimonious way to capture both ambiguity and the players' potentially heterogeneous response towards it, while remaining analytically tractable and empirically measurable, [START_REF] Baillon | Measuring Ambiguity Attitudes for all (Natural) Events[END_REF]. In contrast to max-min expected utility [START_REF] Gilboa | Maxmin expected utility with a non-unique prior[END_REF], they allow for both ambiguity-loving and ambiguity-averse behavior and have therefore the advantages of the general Choquet expected utility by [START_REF] Schmeidler | Subjective probability and expected utility without additivity[END_REF] and the α-max-min expected utility by [START_REF] Ghirardato | Differentiating Ambiguity and Ambiguity Attitude[END_REF]. 6 Furthermore, the NEO-additive capacities allow for a differentiation between the "objectively verifiable" information captured by the probability distribution π i , which reflects the actually chosen strategy of the other players, and the subjective perception and attitude towards strategic uncertainty, as captured by the parameters δ i and α i . In equilibrium, players' objective beliefs π i are self-confirming in that they coincide with the actually played equilibrium strategies, while for δ i > 0, there is still room for strategic uncertainty which impacts the equilibrium in a non-trivial way (Eichberger and Kelsey, 2014). 7 In this paper, we will restrict attention to pure strategies and thus, to NEO-additive capacities for which π i is a Dirac measure on some strategy combination of the other players, x -i ∈ X -i , π i (x -i ) = 1. Slightly abusing notation, we will write ν i (•|α i , δ i , x -i ) to denote such a capacity, see the Appendix for details.

Given i's subjective beliefs expressed by NEO-additive capacity ν i (•|α i , δ i , x -i ), her Choquet expected payoff from choosing a strategy x i in the network formation game above is given by the Choquet integral of the payoff function u i with respect to ν i , see (3) in the Appendix and can be written as:

U i (x i , ν i (•|α i , δ i , x -i )) (2) = δ i α i max x-i ∈X -i u i (x i , x-i ) + (1 -α i ) min x-i ∈X -i u i (x i , x-i ) + (1 -δ i ) u i (x i , x -i ) = j̸ =i x ij w ij (δ i α i + (1 -δ i )x ji ) -c i (deg + i (x)),
In words, player i's Choquet expected payoff of strategy x i given her subjective belief ν i is the sum of the expected payoff she would obtain under her objective belief π i with weight 1 -δ i , the highest possible payoff attainable by x i with weight δ i α i , and the lowest payoff attainable by x i , with weight δ i (1 -α i ). The expression in the third line obtains by noting that in our network formation game max

x -i ∈X -i u i (x i , x -i ) is always obtained at x ji = 1 for every j ̸ = i, whereas min x -i ∈X -i u i (x i , x -i ) obtains at x ji = 0 for every j ̸ = i.
There are three extreme cases: for a realistic player i (δ i = 0), the Choquet expected payoff of x i given ν i coincides with the payoff of x i given x -i , for an optimistic/pessimistic player i (δ i = α i = 1 and δ i = 1, α i = 0 respectively), the Choquet expected payoff of x i ignores the objective belief π i and equals the largest/smallest payoff available through x i .

In the following, we will treat α i and δ i as parameters and we will write α = (α i ) i∈I and δ = (δ i ) i∈I for the vectors of ambiguity attitudes and ambiguity perceptions.

The best response correspondence of player i given that her beliefs are represented by a NEOadditive capacity v i with parameters α i and δ i is defined as usual by

B i (ν i (•|α i , δ i , x -i )) = arg max x i ∈X i U i (x i , ν i (•|α i , δ i , x -i )).
As most definitions of equilibrium, the equilibrium under ambiguity imposes consistency between equilibrium beliefs and equilibrium behavior. Differently from the standard Nash equilibrium concept, in our framework, players perceive ambiguity about the behavior of their opponents. Hence, their beliefs will in general assign positive weight to strategies, which are not used in equilibrium. The consistency notion is thus imposed on a subset of strategies assigned positive weights, on those that are in the support of the objective beliefs, π i . In the case, in which π i is a Dirac measure on some x -i , the support of π i is given by x -i , the strategy combination played by the other players.

We now adapt the equilibrium under ambiguity concept of [START_REF] Eichberger | Optimism and pessimism in games[END_REF] to our framework as follows: Definition 2.13 [START_REF] Eichberger | Optimism and pessimism in games[END_REF]). For given vectors of parameters of optimism and ambiguity perception (α, δ), a network x * is an equilibrium under ambiguity (EUA) if for every i ∈ I,

x * i ∈ B i (ν * i (•|α i , δ i , x * -i )).
EUA imposes constraints both on players' strategies and on players' beliefs. In particular, whenever player i's best estimate is that strategy combination x * -i will be played by the other players, her equilibrium strategy, x * i is a best response according to her respective equilibrium beliefs given by ν

* i (•|α i , δ i , x * -i ).
It is easily seen that this condition is equivalent to the definition of EUA in Eichberger and [START_REF] Eichberger | Optimism and pessimism in games[END_REF]. It also illustrates the similarity of the concept to the Nash equilibrium as a mutual best-response. We denote by X * (α, δ) the set of equilibria under ambiguity given (α, δ) and continue using X * for the set of equilibria of the game without ambiguity, i.e., δ i = 0 for all i ∈ I.

Equilibria under ambiguity of the network formation game

We begin by a characterization of a player's best response under parameters α i and δ i . To simplify the analysis and avoid the cases of indifference we will discuss ambiguity parameters δ i , α i , i ∈ I such that for every i, j ∈ I and every r ∈ N we have

w ij δ i α i ̸ = c ′ i (r) and w ij (δ i α i + 1 -δ i ) ̸ = c ′ i (r)
, which is a generic setting of parameters.

The behavior of players maximizing ( 2) is showcased by the following characterization.

Lemma 3.1 (Best response under ambiguity). Fix α i and δ i . For x ∈ X and i ∈ I, and

x ′ i ∈ X i let x ′ = (x ′ i , x -i ). Then, x ′ i ∈ B i (ν i (•|α i , δ i , x -i ))
if and only if for every j ̸ = i we have x ′ ij = 1 if and only if the following two properties hold:

1. w ij (δ i α i + (1 -δ i )x ji ) > c ′ i (deg i (x ′ )) (the perceived benefit of linking to j exceeds marginal cost), 2. for every k such that x ′ ik = 0 we have w ij (δ i α i + (1 -δ i )x ji ) ≥ w ik (δ i α i + (1 -δ i )x ki ) (none of the non-neighbors is a better pick than j).
To illustrate the effect of ambiguity, compare the above conditions to the case without it (δ i = 0 for all i). A player i with a belief of her opponents' behavior, x -i , ranks her opponents by the value w ij x ji : their value times their willingness to link to i. Player i's best response will be to link to a selection of her opponents with the highest such value, stopping to form more links once her marginal cost exceeds the best unlinked opponent's perceived value.

Players affected by ambiguity behave very similarly but they do not place full confidence on their beliefs x -i . Instead, they rank their opponents based on a distorted value w ij (α i + (1 -δ i ))x ji . The higher their perception of ambiguity, the less weight they place on their belief, and the more optimistic they are, the stronger they distort towards the belief that any opponent will link to them. Highly optimistic players focus only on the available benefit of a link, w ij , while highly pessimistic ones make their decisions in response to a distorted belief that no opponent will link to them.

The characterization of EUA networks follows immediately.

Corollary 3.2 (EUA characterization). For given parameters (α, δ), the network x * is an EUA if and only if for every trio i, j, k

∈ I such that x * ij = 1, x * ik = 0 we have w ij (δ i α i + x * ji (1 -α i )) ≥ w ik (δ i α i + x * ki (1 -α i ))
and every pair i, j ∈ I , x * ij and x * ji follow the rules presented by Table 1.

As Table 1 shows, each player has three types of opponents in equilibrium which results in a total of nine qualitative types of equilibrium pairwise relations. A player may identify links that she will initiate even if the opponent does not reciprocate. This can only happen if the player is sufficiently optimistic. If such a high-value opponent likewise considers the initiating player valuable enough, a

w ij = w ji > c ′ j (x * ) δ j α j ∈ c ′ j (x * ) δ j α j +1-δ j , c ′ j (x * ) δ j α j < c ′ j (x * ) δ j α j +1-δ j > c ′ i (x * ) δ i α i x * ij = x * ji = 1 x * ij = x * ji = 1 x * ij = 1, x * ji = 0 ∈ c ′ i (x * ) δ i α i +1-δ i , c ′ i (x * ) δ i α i x * ij = x * ji = 1 x * ij = x * ji = 0 or 1 x * ij = x * ji = 0 < c ′ i (x * ) δ i α i +1-δ i x * ij = 0, x * ji = 1 x * ij = x * ji = 0 x * ij = x * ji = 0
Table 1: EUA characterization. Links which are perceived as high-value by a given player are always extended, links with perceived low value are never extended. In-between-value links are extended only if reciprocated, either because the partner to the link perceives them as high-value, or as in-between-value. If, for both partners, the link is perceived as an 'in-between'-value, there may exist some equilibria where a reciprocated link is formed and some where neither direction of the link forms. Note: we use the convention 1/0 = ∞.

reciprocated link forms between them. If the initiating player is low-value for the opponent, a one-way link forms.

A player may also identify low-value opponents to whom she will not link even if that opponent initiates a link towards her. This may either be due to the fact that the player is highly pessimistic, or has other higher value opponents she intends to prioritize. In this case the player may have incoming one-way links from low-value opponents who consider her high-value.

Every other opponent is 'in-between'-value; the player will only form such a link if she believes it will be reciprocated. If an 'in-between'-value opponent considers her as high-value, the opponent will initiate and the player will reciprocate. If she is considered low-value, no links will form. Two players who consider each other 'in-between'-value may link to each other but no directed link can exist between them.

There are two important differences between Nash equilibrium networks and EUA: First, the empty network may not be an EUA as high-value directions will always form in equilibrium. As a result, existence becomes a non-trivial issue (note that whenever the cost function is strictly convex, the game is not supermodular in the players' own strategies and thus, the standard existence result of [START_REF] Topkis | Equilibrium points in nonzero-sum n-person submodular games[END_REF] cannot be used). Second, an EUA network may contain directed links. To obtain a comparison with the set of Nash equilibrium networks, one can take δ i = 0 for all i, in which case the threshold for high-value opponents becomes infinity, effectively eliminating the top row and left column of Table 1, and leading to the characterization in Lemma 2.8.

We now state a general existence result of EUA.

Proposition 3.3 (Existence of EUA). For any network formation game (W, c) and any set of ambiguity parameters (α, δ) such that the assumption of no indifference is satisfied, an equilibrium under ambiguity exists.

Proposition 3.3 shows the existence of pure equilibria. We obtain this result by considering strict best-response dynamics: starting in an arbitrary network, we show that no strict best-response improvement path can revisit a network it had visited before, thus any such path must reach a network where no player can improve. That network is an EUA. Furthermore, the set of EUA is thus given by the absorbing sets of best-response dynamics under ambiguity.

We now examine the effects of increasing players' optimism, starting with its effects on the number of out-neighbors. While we will not obtain a direct result, we are able to derive monotonicity conditions on player optimism and the minimal and maximum number of out-neighbors. We begin with a formal definition of these two concepts. Definition 3.4 (Minimal and maximal out-degree). For player i ∈ I her minimal and maximal out-degree, denoted by d i (α i , δ i ) and d i (α i , δ i ) are defined as

d i (α i , δ i ) = deg + i (x) where x i ∈ B i ν i •|α i , δ i , (x ji = 0) j̸ =i , d i (α i , δ i ) = deg + i (x) where x i ∈ B i ν i •|α i , δ i , (x ji = 1) j̸ =i ,
respectively.

For fixed ambiguity parameters we write d i and d i for the number of links player i offers in a best response to the belief that no players link to i and all players link to i, respectively. Since indifferences of linking and not linking are ruled out, these values are well defined, with d i being the largest degree r such that r ≥ |{j ∈ I :

α i δ i w ij > c ′ i (r)}| holds and d i being the largest degree r such that r ≥ |{j ∈ I : (α i δ i + (1 -δ i ))w ij > c ′
i (r)}| holds. Thus, d i and d i are also lower and upper bounds, respectively, of the number of out-links that player i can have in any EUA network.

For the case of no ambiguity, δ = 0, the values d i (α i , 0) and d i (α i , 0) are independent of α i . In this case, d i (α i , 0) = 0 (absent ambiguity, a player does not link if no player links to her) and we denote d i = d i (α i , 0) as the number of links initiated by a player unaffected by ambiguity when she believes that all other players offer a link to her. It is the maximum number of neighbors a player can have in a best response.

Note that

d i = d i (1, 1) = d i (1, 1
), as a player with δ i = α i = 1 always best responds to the belief that every opponent links to her. Thus, optimists will always have d i out-links in a best response. In contrast, d i (0, 0) = d i (0, 0) = 0, i.e. pessimistic players do not link to anyone.

We now show how changes in player's optimism and confidence impact the lower-and upper bounds.

Proposition 3.5 (Minimal and maximal out-degree comparative statics). Let α i , δ i be given. For every i ∈ I, every δ ′ i > δ i , and every α ′ i > α i , we have

1. d i (α ′ i , δ i ) ≥ d i (α i , δ i ), 2. d i (α ′ i , δ i ) ≥ d i (α i , δ i ), 3. d i (α i , δ ′ i ) ≥ d i (α i , δ i ), 4. d i (α i , δ ′ i ) ≤ d i (α i , δ i ).
Since the perceived value of all potential links increases with the degree of optimism, both d i and d i are increasing in α i (points 1 and 2). An increase in the perception of ambiguity reduces the confidence the player assigns to the events that no one links to her and everyone links to her, respectively leading to an increase of d i (point 3) and an decrease of d i . A higher δ i thus decreases the difference d i -d i which becomes 0 at δ i = 1, as in this case the player's best response is independent of her objective beliefs about x -i . If δ i = 1 for all i, the players' best responses are unique up to indifferences between linking to equal-valued neighbors. Without indifferences, e.g. in case w ij ̸ = w ik for any triple i, j, k, the best responses, and the resulting EUA are unique.

Although points 1 and 2 show that the bounds of the players' out-links increase with respect to their optimism, the realized equilibrium may not be more connected than the old one if the players' optimism increases. This is because a more optimistic player may sever existing links in an attempt to link to higher-value players and these newly initiated links need not be reciprocated. For this reason the comparative statics between player optimism and the size of the equilibrium network is not straightforward. We identify a sufficient condition, called the monotonicity of networks, that guarantees that optimism increases the connectivity of equilibrium networks. Definition 3.6 (Monotonic network). Network x is monotonic in linking decisions (monotonic, for short) for player i if for every j, k ∈ I such that w ij ≥ w ik we have x ij ≥ x ik . Network x is monotonic if for every i ∈ I it is monotonic for i.

If x is monotonic, then all players i link to some selection of their top deg + i (x) choices of opponents. If an undirected network is monotonic, a player can only increase the value of her links by forming more links, not by replacing her existing links with better ones. We show that if an equilibrium is monotonic, then upon an increase in the players' optimism there will always exist an EUA under the new parameters whose undirected restriction is a supergraph of that of the old one.

Proposition 3.7 (Monotonic equilibrium comparative statics). Let x ∈ X * (α, δ) be monotonic and consider an α ′ ≥ α. Then, there exists an EUA network, x ′ ∈ X * (α ′ , δ) such that y(x) ≤ y(x ′ ).

By Proposition 3.7, we thus obtain that if an equilibrium is monotonic, an increase in the players' optimism will lead to more reciprocated links, increasing the value of realized benefits in the network as well.

Example 3.8 (Monotonic equilibrium with increased optimism). To demonstrate this result we consider a network of four players, A, B, C, and D. The links {A, B} and {C, D} give a high value H, while {A, D} and {B, C} offer a low value L with H > L > 0. Links {A, C} and {B, D} give a value of 0. Suppose that for all players we have c ′ i (2) < L. Then, the unique Pareto optimal equilibrium network is x * = {{A, B}, {B, C}, {C, D}, {A, D}}, while any subset of x * constitutes a Nash equilibrium network. Consider the monotonic equilibrium network x = {{A, B}, {C, D}} and parameters δ i and α i such that (( In the special case when all cost functions are linear, the game is supermodular and increased optimism raises equilibrium connectivity regardless of whether the initial equilibrium is monotonic [START_REF] Schipper | The evolutionary stability of optimism, pessimism, and complete ignorance[END_REF].

α i δ i ) + (1 -δ i ))H > c ′ i (1), δ i L > c ′ i (2), and α i δ i L < c ′ i (2). Then, x is the only EUA. Suppose that for all i α i increases to α ′ i in a way that α ′ i δ i L > c ′ i (

Network realignment through optimism

In this section we study the realignment of networks. By network realignment we refer to sequences of link formations and severances that lead from one equilibrium to another. This type of realignment may happen for several reasons. Equilibria that are stable against individual or pairwise changes may break apart due to a coordinated improvement by larger coalitions. Farsighted players may experiment in order to trigger a sequence of changes that increase their individual payoffs. Deviations may also occur randomly. Instead, here we consider exogenous shocks to players' perception of and attitude towards strategic uncertainty as a driver of network realignment. As demonstrated earlier, such shocks modify players' subjective evaluations of their current linking decisions and thus induce changes in individual linking choices.

A motivation to study realignment is to select for equilibria that survive these changes, the conditions under which such equilibria even exist, and the efficiency properties of surviving equilibria. Since the seminal works of KMR and [START_REF] Young | The evolution of conventions[END_REF], models of myopic adaptation with random mutations have been used as a selection device in games with multiple equilibria. In general, such models postulate a best-response type of adaptive dynamics. In each period, a player is chosen at random and revises her strategy by playing a best response to the current strategy profile of her opponents. With strictly positive probability, mutations (such as mistakes, experimentation) occur; instead of playing her best response, the player chooses a strategy at random.

In this section, mutations, instead of leading to a random choice of a strategy, will affect the players' ambiguity parameters, their perception of ambiguity and optimism. Players then behave rationally given these parameters. We choose to focus on mutations that amount to optimistic surges. As shown above, players affected by optimistic surges seek out more and/or better neighbors. We thus explore whether optimistic surges select for efficient equilibria in the long-run. In contrast, pessimistic surges cause links to break down without new ones forming. We comment on the possibility of introducing pessimistic shocks in Section 5.

Our dynamic process takes place in discrete time, t ∈ N. The network at time t will be denoted by x t . Take an initial network structure x t-1 . In period t, a player i t is chosen at random with uniform probability 1/n and receives an opportunity to revise her strategy to x i t . All other players continue playing the strategies corresponding to x t-1 -i t . For player i ∈ I set δi ∈ (0, 1) and ᾱi ∈ [0, 1] such that for every j ∈ I \ {i} and r ∈ {0, n -1} we have c ′ i (r) < ᾱi δi w ij if and only if c ′ i (r) < w ij , and for j, k ∈ I \ {i} with w ij > w ik we have δi ᾱi w ij > w ik . Such values are guaranteed to exist with both δi and ᾱi being close to 1, as the player set is finite. These parameters represent highly optimistic behavior but not complete ignorance (which occurs for δ i = 1). Thus, players' behavior will satisfy three properties: (1) if pressed to make a choice, a player will strictly prefer an unreciprocated link of a higher value to a reciprocated link of a lower value, (2) due to δi < 1 the player will strictly prefer a reciprocated link to an unreciprocated one of equal value, (3) the player always finds it optimal to have exactly d i out-links to her top d i choices, i.e.

d i (ᾱ i , δi ) = d i (ᾱ i , δi ) = d i .
The main parameter governing the dynamic process defined above is the frequency of optimistic shocks, denoted by β ∈ (0, 1). If close to zero, our process resembles a best-response dynamic with regular, but infrequent optimistic shocks, and if close to 1, the players almost always react optimistically. We imagine small values of β to be the most plausible but our analysis is not sensitive to the exact value as long as all players perform both optimistic and realistic actions with positive probability. The ambiguity parameters of player i t at the time of revision are thus given by the following timeindependent probability distribution: δ t i t = 0 and α t i t arbitrary with probability 1 -β, δ t i t = δi t and α t i t = ᾱi t , with probability β,

Given her current ambiguity parameters, the revising player behaves myopically and chooses a best response to x t-1 -i t :

x t i t ∈ B i t (ν i t (•|α t i t , δ t i t , x t-1 -i t )) If the best response B i t (•)
is not a singleton, player i t chooses a best response in B i t (•) uniformly at random. The resulting network at time t, x t , is then given by

x t (x t-1 , i t , α t i t , δ t i t ) = (x t i t , x t-1 -i t ).
In words, any updating player is an optimist with uniform probability β and a best-responder with probability 1 -β.

In what follows, we will shorten the notation of an optimistic player's best response to

x to B o i (x) = B i (ν i (•|ᾱ i , δi , x -i )).
A best-response dynamics with optimistic surges can be interpreted as a myopic response of a player to the current network. As in the standard case, the player holds "static perceptions on the evolution of any variable of the process outside of her control", see [START_REF] Vega-Redondo | Economics and the Theory of Games[END_REF]. In this case, she is informed of the strategy profile x t-1 -i t that prevailed during the preceding period. However, rather than assuming that the same strategy profile will be repeated at period t, she considers x t-1 -i t as the best available estimate of the behavior of other players, assigning to it a (possibly limited) confidence of 1 -δ t i t . In particular, when an optimistic surge occurs, a strictly positive weight is assigned to the strategy profile of the others which would maximize her payoff. This process thus generalizes the standard best-response dynamics to the case in which players assume that others will continue playing their preceding strategies, but perceive ambiguity with regards to such predictions.

The dynamic process thus defined describes a Markov chain on the set X. For x, x ′ ∈ X and β ∈ [0, 1] let p β (x, x ′ ) denote the one-step transition probability from x to x ′ , given that the probability of an optimistic shock is β. It is clear that for every x, x ′ ∈ X with p β (x, x ′ ) > 0 there exists i ∈ I such that either

x ′ i ∈ B i (x) or x ′ i ∈ B o i (x)
and for every j ̸ = i we have x ′ -i = x -i . For m ∈ N let p m β (x, x ′ ) denote the transition probability from x to x ′ in exactly m steps. For a set of networks X ′ ⊆ X let p m β (x, X ′ ) = x ′ ∈X ′ p m β (x, x ′ ) denote the probability of reaching this set from x in exactly m steps.

Definition 4.1 (Successor). For x, x ′ ∈ X and m ∈ N we say that x ′ is an m-successor of x if p m β (x, x ′ ) > 0.

Denote the set of m-successors of network x by S m (x) and let m∈N S m (x) = S(x) denote the set of all successors of x. By convention we include x ∈ S(x).

We introduce the key condition of our convergence results.

Definition 4.2 (Aligned preferences). The players exhibit aligned preferences if every MBE network is monotonic.

Under aligned preferences, MBE networks are not only optimal for a benefit-maximizing society, but also safisfy an individual optimality condition for the players: each player is linked to a selection of her best opponents. This is an appealing property for a game to have, as without it we observe a conflict between efficiency in benefits and the players' incentives.

The notion of aligned preferences also partially resolves the conflict between the two notions of efficiency, MBE and Pareto ptimal equilibria, discussed in Section 2.2. While in general, MBE networks can be Pareto dominated by other equilibrium networks, see Example A.4 in the appendix, our next Lemma shows that in the case of aligned preferences, MBE are Pareto-optimal in the set of Nash equilibria:

Lemma 4.3. Under aligned preferences, MBE networks are Pareto optimal in the set of Nash equilibria.

Due to Lemma 4.3, when preferences are aligned, MBE is a stronger efficiency notion than Pareto optimality.

Proposition 4.4 (Stability of efficient networks under aligned preferences). Suppose that the players exhibit aligned preferences. For every x * ∈ V * and every x ′ ∈ S(x * ) we have x ′ ∈ y -1 (V * ).

By Proposition 4.4, under aligned preferences, the set of MBE networks is stable under our dynamic of optimistic and best-responding players. More precisely, starting the dynamical process in an efficient network, all successor networks will contain an MBE network as well as some additional one-way links. Formally, the set y -1 (V * ) is absorbing under our dynamic process. We now present our second main result. If preferences are aligned, then the dynamic described above always pushes the game towards networks that contain an MBE network, and, possibly, some additional one-way links. If there is a unique MBE network, then it by itself, is a stable equilibrium in terms of our dynamic, allowing for the creation and deletion of additional one-way links. If there is more than one MBE network, then they may communicate with each other under our dynamic but the total realized benefit of players never changes.

Proposition 4.5 (Efficient networks form almost surely under aligned preferences). Suppose that the players exhibit aligned preferences. Then, for every x ∈ X and every β ∈ (0, 1) we have

lim m→∞ p m β (x, y -1 (V * )) = 1.
Proposition 4.5 shows that, under aligned preferences, by the individual updates of players, an MBE network will form almost surely. Combined with 4.4, this means that, in terms of reciprocated links, the set of MBE networks is globally stable under these dynamics.

The key intuition behind the proof is that, from a sufficiently connected but inefficient equilibrium (from which, as we show, we can initiate the process) we can choose a link {i, j} which is part of the efficient network but not part of the current network, and a player i who would initiate this link under an optimistic shock. If this is followed by j being given a best-responding revision opportunity she may reciprocate this link, possibly severing some others. There will then exist a series of best-responses through which we obtain a network which is strictly closer to the desired MBE network (notably by the inclusion of the link {i, j} and the exclusion of some unnecessary links). Since the set of all networks is finite, repeating this process allows the dynamic to reach V * in finite time. Once a network in V * is reached, the value of the network cannot decrease (Proposition 4.4).

We note the difference between our approach and that of KMR. Similarly to their approach, our bestresponse dynamic with optimistic shocks defines a Markov process on the set of strategy combinations and thus, on the set of directed networks. In KMR, the random mutations imply that any strategy can be chosen with strictly positive probability and thus, the Markov process visits any of the Nash equilibria infinitely often. In contrast, in our model, the asymmetric nature of the optimistic shocks implies that the Markov process reaches the set of MBE networks, with probability 1, regardless of initial conditions. Furthermore, the set y -1 (V * ) is absorbing.

We note that letting the probability of optimistic surges β go to 0 does not lead to a further refinement of the set of equilibria. In particular, as the following proposition shows, all MBE are stochastically stable.

Proposition 4.6. There exists a set of probability distributions (μ β ) β∈(0,1) such that for each β ∈ (0, 1), μβ is an invariant probability distribution of the Markov chain (X, p β ) β∈(0,1) and supp lim β→0 μβ = V * .

The following example demonstrates network realignment through optimistic shocks under aligned preferences.

Example 4.7 (Network realignment). Consider the benefit weights given by Example 3.8, but with c ′ i (1) < L and c ′ i (2) > H for all i, that is, each player can have at most one neighbor in equilibrium. Then, the unique MBE network is x * = {{A, B}, {C, D}}, but any undirected network where each player has at most one neighbor is also an equilibrium. Notably, x = {{A, D}, {B, C}} is also pairwise stable, but not stable against optimistic surges. The realignment process that leads from x to x * is shown in Figure 2 If preferences are not aligned, then MBE networks are not always Pareto optimal, and they are also not stable against optimistic shocks; a player who is not linked to her best choice of neighbors, upon experiencing an optimistic shock, will invariably delete her links to her existing neighbors and make offers to her best choices. This can be demonstrated by a minimal counterexample of three players.

Example 4.8. Consider a network of three players with w 12 = H, w 13 = M , and w 23 = L with H > M > L > 0. Suppose that c ′ 1 (1) < H and c ′ 1 (2) > M , as well as c ′ 3 (1) < L and c ′ 3 (2) > M meaning that players 1 and 3 can entertain only one neighbor, while c ′ 2 (2) < L, player 2 can entertain two neighbors. Then, the unique MBE is x * = {{1, 2}, {2, 3}}, which is not monotonic, thus preferences are not aligned. Starting from x * if player 3 receives an optimistic shock she will sever her link running to 2 and offers one to 1 which will be unreciprocated. These networks are shown in Figure 3.

1 2 3 H L M 1 2 3 H L M Figure 3:
The network of Example 4.8. Player 2 can accommodate two neighbors, players 1 and 3 only one. The unique MBE (left) is pairwise stable, but unstable for an optimistic surge by player 3 who will sever her link with 2 and make an unreciprocated offer to 1 instead (right).

We conclude this section by showing convergence in the linear case, which is not covered by the case of aligned preferences. Proposition 4.9. Let the cost functions be linear. Then, for every x ∈ X and every β ∈ (0, 1) and the unique x * ∈ V * we have lim m→∞ p m β (x, y -1 (x * )) = 1.

Proposition 4.9 extends the convergence result laid out in Proposition 4.5 to all games with linear costs, without the precondition of aligned preferences. This is due to the fact that, under linear costs the unique MBE, which coincides with the unique pairwise stable equilibrium, is stable for both optimistic and best-responding deviations.

Concluding remarks

In this paper we investigate a model of network formation with players facing ambiguity with respect to their opponents' linking decisions. We model this uncertainty using NEO-additive beliefs: players respond to mixtures of their rational beliefs as expressed by a probability measure of their opponents' actions, their optimistic beliefs, and their pessimistic ones.

To our knowledge, ours is the first project to consider ambiguity in strategies in a network formation game. This combination of frameworks is natural and fits well with behavioral considerations of network formation: optimistic players believe their linking offers are likely to be reciprocated, pessimistic players believe that opponents are unlikely to reciprocate. These considerations provide behavioral explanation to the existence of asymmetric interactions in social networks, namely, persistent one-way links. Similar explanations are absent in models focusing on joint improvements or individual rational behavior. Directed interactions may arise due to optimism as a player believes the opponent will reciprocate and thus make an offer to link without coordinating with the opponent. Even if the opponent does not reciprocate, if the optimism of the offering player persists, so does the one-way link. Under repeated surges of optimism followed by best-responding behavior, the linking offer is attempted and withdrawn repeatedly.

By explicitly modeling player optimism we also allow the link-formation process to be governed proactively by the players. Under Nash equilibrium, link formation was governed by the players passively best-responding to each other's actions or their beliefs about their opponents. In what has proven to be the modern benchmark tool, pairwise stability, link-formation is governed by the logic of random pairwise interactions where, upon meeting a mutually beneficial opponent, the pair decides to form a link. Here, players remain passive in creating these interactions and only act if the opportunity arises through events outside their control. Under our framework, optimistic players proactively seek out their best possible links, creating linking opportunities through a costly investment.

Our investigation of equilibrium under ambiguity reveals that optimism can, as expected, lead to better equilibrium outcomes by selecting against underconnected equilibria. Too much optimism, on the other hand, makes players blind to their available prospects in favor of the best they could possibly achieve and thus there is no general monotonic relationship between equilibrium connectivity and optimism. Monotonic equilibria, however, do improve in terms of connectivity if the players become more optimistic, as they feature no tradeoff between the players' available links and their best possible links. In these cases, optimism is helpful for the players to seek out additional profitable partners without severing their links to existing ones.

In addition to equilibrium, we study network realignment under ambiguity. Under aligned preferences, best-response dynamics with optimistic shocks lead to all links of a Pareto optimal equilibrium network forming; specifically, one that maximizes benefits from links. This insight sheds some light to the role of optimism in a society: individual optimism begets an optimal social network without relying on formal or informal multilateral coordination devices. It is noteworthy that both optimism and realism are found to be necessary attitudes to produce this result, with optimism being the driving force to seek out newer and better links, while realism compels players to accept the status quo. If the frequency of optimistic shocks is high, efficient networks are reached faster but the system will spend more time in networks with directed links -even after all links of the Pareto optimal equilibrium network have been formed. If this frequency is lower, Pareto optimal equilibria are reached later but players spend more time at their objective best response -i.e. in the actual equilibrium network. This suggests that there is an optimal amount, or rate, of optimism for a society which strikes a balance between the speed of convergence to the set of Pareto optimal equilibrium networks, and mitigating the efficiency loss arising from the wasted effort of extending unreciprocated links. Finding this is an interesting direction for future research.

If preferences are not aligned, optimistic shocks are not enough to produce efficient networks -even the concept of an efficient network becomes more elusive as the efficiency notion that planners may be interested in, the maximum-benefit equilibria, and the one pertaining to the players' well-being, Pareto optimality, are not in agreement. We thus cannot resolve the prevailing conflict between stability and efficiency in the general case. A possible way to relax the aligned preferences condition is by considering a higher degree of player sophistication. For instance, in Example 4.8, a player 2 who is informed of player 1's payoff function may anticipate that player 1 will not sever her first-best link and is thus, unavailable. Alternatively, after several unsuccessful tries, she can also learn that player 1 will never reciprocate. Both would allow player 2 to be satisfied with her second-best outcome, which stabilizes the Pareto optimal equilibrium network. This type of sophisticated selection of neighbors is beyond the scope of this paper.

Our model is without explicit network externalities. This choice simplifies our analysis as players evaluate their linking choices "link-wise". Furthermore, this avoids the additional complexity of modeling the players' beliefs of their neighbors' (neighbors', etc.) links, as well as their responses to these beliefs. As the players' reliable information of links in the network that are distant from them can be scarce, a more general model of ambiguity in networks under explicit network externalities necessitates an epistemic foundation of players' beliefs of distant links. Nevertheless, the model has implicit network externalities due to the convexity of the cost function. For a player, any link that is formed between two non-neighbors makes it more unlikely that those two non-neighbors reciprocate her linking offers.

Finally, we mention pessimism, which, in our model, does not seem to have any positive role in building the network or realigning efficiently. Pessimistic shocks in our model amount to (possibly temporary) severances of links without forming new ones. More generally, pessimism may play a role in preventing the network from becoming too cluttered. This may be to the benefit of society if network interactions bring negative externalities, such as during a pandemic where being part of a connected social component exposes the individual to risk of infection. This is another interesting direction for future research.

A Appendix

A.1 Capacities and NEO-additive Capacities

Let X -i denote the set of all subsets of X -i .

Definition A.1 (Schmeidler (1989)). A capacity on (X -i , X -i ) is a function ν i : X -i → [0, 1] with ν i (∅) = 0, ν i (X -i ) = 1 and ν i (A) ≤ ν(A ′ ), whenever A ⊆ A ′ .
In words, a capacity is a non-additive measure, which is normalized between 0 and 1 and satisfies monotonicity with respect to set inclusion. In particular, a capacity will in general violate additivity: the measures assigned to an event A ⊆ X -i , ν i (A), and its complement X -i \ A, ν i (X -i \ A) need not sum up to 1.

The notion of a capacity is very general. In this paper, we will use a special class of capacities, called NEO-additive capacities which allow for a distinction between the strength of a players' perception of ambiguity and their response to it, optimism or pessimism. These characteristics of the players are captured by two parameters, α i ∈ [0, 1], and δ i ∈ [0, 1]. Definition A.2 [START_REF] Chateauneuf | Choice under uncertainty with the best and the worst in mind: NEO-additive capacities[END_REF]). For a player i, given her ambiguity parameters α i , δ i , and a probability measure π i on (X -i , X -i ), the NEO-additive capacity ν i (•|α i , δ i , π i ) on (X -i , X -i ) is defined as follows:

ν i (A|α i , δ i , π i ) = 0 if A = ∅, 1 if A = X -i , δ i α i + (1 -δ i )π i (A) otherwise.
A NEO-additive capacity can be interpreted as follows: the probability distribution π i player i's belief about the behavior of her opponents. The degree of confidence of i in this belief is given by (1 -δ i ). In particular, if δ i = 0, the degree of confidence is 1, i is not affected by ambiguity, and her subjective beliefs are represented by π i itself. When the degree of confidence (1 -δ i ) < 1, the player perceives ambiguity δ i with respect to her best estimate π i . Intuitively, δ i identifies a set of probability distributions given by the convex combination of π i with the set of all possible probability measures on

X -i , ∆ (X -i ), Π i = (1 -δ i ) {π i } + δ i ∆(X -i )
that the player takes into account when deciding on her strategy.

The effect of such ambiguity on i's beliefs about an event A depends on the player's degree of optimism, α i . When α i = 0, the player is a complete pessimist and her beliefs scale down the probability of any event A (except for the whole event X -i ) by her degree of confidence, (1 -δ i ). For a fully optimistic player with α i = 1, the probabilities of all events (except the impossible one, ∅) are overweighted. More generally, for intermediate degrees of optimism, i will overweigh events with low probability and underweight those with high probabilities.

Definition A.3 [START_REF] Chateauneuf | Choice under uncertainty with the best and the worst in mind: NEO-additive capacities[END_REF]). The Choquet expected payoff with respect to a NEOadditive capacity ν i with parameters α i , δ i and π i such that π i (x -i ) = 1 for some x -i ∈ X -i is given by:

U i (x i , ν i (•|α i , δ i , x -i )) = u i (x i , x-i )dν i (3) = δ i α i max x-i ∈X -i u i (x i , x-i ) + (1 -α i ) min x-i ∈X -i u i (x i , x-i ) + (1 -δ i ) u i (x i , x -i ) = α i max π∈(1-δ i ){π i }+δ i ∆(X -i ) E π [u i (x i , x-i )] + (1 -α i ) min π∈(1-δ i ){π i }+δ i ∆(X -i ) E π [u i (x i , x-i )]

A.2 Aligned preferences conditions

In this section we discuss implications and conditions of the preferences being aligned. Aligned preferences represent a restriction on the players' preferences in a way that individual considerations to link to one's favorite opponents, i.e. play monotonic strategies, are in agreement with social considerations that seek to maximize the players' sum of realized benefits. If preferences are not aligned, MBE networks are not guaranteed to be Pareto optimal. This is illustrated by a counterexample. Suppose that the cost structure is such that

d 1 = d 4 = 2, while d 2 = d 3 = d 5 = d 6 = 1.
Then, the only MBE network is x * = {{1, 2}, {1, 3}, {4, 5}, {4, 6}} for a total weight of 16, but it is not monotonic for any player, hence preferences are not aligned.

Suppose that c 1 (1) = c 4 (1) = 3.8 and c 1 (2) = c 4 (2) = 7.7, which respects d 1 = d 4 = 2. Then, the network given by x = {{1, 4}, {2, 3}, {5, 6}}, with its weight of 15 Pareto dominates x * .

Example A.4 also shows that the reverse of Lemma 4.3 is not true, that is, the existence of an equilibrium network which is monotonic and Pareto optimal does not imply that preferences are aligned. In the example the Pareto optimal equilibrium network is monotonic but preferences are not aligned as it is not an MBE network.

We highlight the special case where the benefits of all links are equal, i.e. players are only interested in the number of their neighbors. In this case preferences are always aligned and MBE networks are the largest equilibrium networks in the number of links. Then, we can derive an even stronger statement, every Nash equilibrium network that is not an MBE network is Pareto dominated by the MBE network closest to it.

Lemma A.5. If for every i, j we have w ij = w for some w ∈ R + , then for every x ′ ∈ X * \ V * and every x ∈ V * that is closest to x ′ in V * , x Pareto dominates x ′ .

Proof: Let x ′ ∈ X * \ V * , let x be an element of V * that is closest to x ′ , and assume that x does not Pareto dominate x ′ . Then, there exists i ∈ I such that deg i (x ′ ) > deg i (x). Hence, there exists a player j ∈ N i (x ′ ) \ N i (x). If deg j (x) < deg j (x ′ ), then either deg j (x) < d j and hence, {i, j} could be added to x, contradicting x ∈ V * , or we have deg j (x ′ ) > d j = deg j (x), contradicting the fact that x ′ is an equilibrium network.

If deg j (x) > deg j (x ′ ), then there must exist k ∈ N j (x) \ N j (x ′ ). Consider the network x ′′ which we get from x by removing the link {j, k} and adding the link {i, j}. It is clear that

x ′′ ∈ X * , since deg i (x ′′ ) ≤ deg i (x ′ ) ≤ d i , deg j (x ′′ ) = deg j (x ′ ) = d j , and deg k (x ′′ ) = deg k (x) -1 < d k . Furthermore,
x ′′ ∈ V * , since x has the same number of links as x ′′ . However, we have ϕ(x ′ , x ′′ ) = ϕ(x ′ , x) -2, thus we contradict the choice of x as a closest element of V * to x ′ . Thus, x must Pareto dominate x ′ .

■

There is no equivalent statement for games with aligned preferences in general as a player i's firstbest network need not be an MBE network and thus it is possible for this player to be worse off in every MBE network.

The condition of aligned preferences is a condition on the game's equilibrium structure and not the primitives. We conclude this section by deriving a set of sufficient conditions on the games primitives (W, c) that implies that preferences are aligned. In fact, the sufficient condition is stronger, as it produces a unique MBE network which is monotonic.

Lemma A.6. Suppose that 1. for every i ∈ I there exists a value wi such that |{k : w ik ≥ w i }| = d i , and 2. for every i, j ∈ I we have w ij ≥ wi ⇔ w ij ≥ wj . Let x * be given as follows:

x * ij = 1 if w ij ≥ w i , x * ij = 0 otherwise.
Then, x * is the unique MBE network and it is monotonic.

Proof: It is clear that x * is monotonic and, by property (2), it is undirected. Furthermore, by property (1) it holds that for every i ∈ I we have deg i (x * ) = d i . Thus, every player has the maximum number of neighbors and is linked to her best choice of d i opponents. Thus, x * is the only MBE network.

■

Lemma A.6 lays out two sufficient conditions for preferences to be aligned: (1) each player must have a well-defined set of 'favorite' opponents to link to that will satiate her, and (2) reciprocity in 'favorite' opponents. The first condition precludes, among other settings, the uniform benefits case; even though uniform benefits represent aligned preferences they do not generally imply uniqueness of the MBE network. If indifferences are not allowed, as is often the case in matching where individuals have a strict ranking of opponents, this condition is automatically satisfied. The second condition ensures reciprocity of links if all players link to their set of favorite opponents and is the main restrictive condition in the lemma. These conditions are strong but, given the matrix of weights, easy to check.

A.3 Proofs for Section 3

Lemma 3.1

The ⇐ direction is clear; if the link towards a player j appears profitable and there is no better alternative to connect to, then player i's best response is to link to j. The ⇒ direction consists of two simple parts: (1) linking to j cannot be a best response if it does not appear profitable, (2) linking to j but not linking to an apparently more profitable k cannot be a best response.

■ Proposition 3.3

We show this statement by the use of strict best-response paths. A strict best-response path is a sequence of networks (x t ) t∈{0,...,T } such that for every t ∈ {1, . . . , T } there exists a player i t such that

x t -i t = x t-1 -i t , x t-1 i t / ∈ B i (ν i (•|α i , δ i , x t ))
, and

x t i t ∈ B i (ν i (•|α i , δ i , x t ))
. In a strict best-response path every period has exactly one player move from a strategy that isn't a best response to the current strategies of her opponents to a best response. We will show that no matter the starting network x 0 , the order of updates, or the length of the sequence, there are no cycles in this process, i.e. there does not exist a non-trivial strict best-response path for which x 0 = x T . Given this fact and due to the finiteness of the set of possible networks with n players, starting from any network, any sequence of such strict improvements by players who are not at their best response will lead to an EUA.

So, for contradiction suppose that such a cycle (x t ) t∈{0,...,T } exists with x 0 = x T . We say that the link {i, j} is changing in this sequence if there exist two time periods t and t ′ such that

x t ij ̸ = x t ′ ij .
It is clear that such links must exist in any strict best-response path.

Claim A.7. In a strict best-response cycle there must exist a changing link {i, j} and a time period t such that x t ij = x t ji = 1.

To show this, suppose for contradiction that such a changing link does not exist. Take a player i and two distinct time periods t < t ′ such that i t = i t ′ = i and for every t ′′ ∈ {t + 1, . . . , t ′ -1} we have i t ′′ ̸ = i. For any cycle such periods may be found by an appropriate time shift. It is clear that t and t ′ cannot be consecutive time periods in a strict best-response path and that there must exist a link {i, j} such that

x t+1 ij ̸ = x t ′ +1 ij otherwise x t ′ i = x t ′ +1 i , contradicting that x t ′ i / ∈ B i (ν i (•|α i , δ i , x t ′ ))
. Since there are no changing reciprocal links we must have

N i (x t ) = N i (x t+1 ) = N i (x t ′ ) = N i (x t ′ +1
). Furthermore, for every k ∈ I with x t ik = 0 and x t ki = 1 we have x t+1 ik = 0, otherwise a changing reciprocal link would appear. Similarly, for every k ∈ I with x t ′ ik = 0 and x t ′ ki = 1 we have

x t ′ +1 ik = 0. It follows that x t+1 i ∈ B i (ν i (•|α i , δ i , x t )) implies x t+1 i ∈ B i (ν i (•|α i , δ i , x t ′
)) as no player can form a link to i, nor delete a link to i that she would reciprocate forming or deleting in t ′ as there can be no changing reciprocated links. Since x t+1 i = x t ′ i due to the fact that i hasn't changed her action between t and t ′ we have

x t ′ i ∈ B i (ν i (•|α i , δ i , x t ′ ))
, a contradiction by the fact that we assumed a strict best-response cycle.

■

Secondly, we show that a strict best-response cycle also cannot contain a reciprocated changing link. The two statements together imply that there are no strict best-response cycles.

Claim A.8. In a strict best-response cycle there cannot be a changing link {i, j} and a time period t such that x t ij = x t ji = 1.

Once again, suppose for contradiction that such a link exists in a strict best-response cycle. Let i, j be a pair and t a time period such that {i, j} is a reciprocated changing link with the largest value w ij , i t = i, x t ij = x t ji = 1, x t+1 ij = 0, and |{k ∈ N i (x t ) :

w ik = w ij }| ≥ |{k ∈ N i (x t+1 ) : w ik = w ij }|.
In words, i, j is a best-value reciprocated changing link that was deleted by i in period t and she does not have more links of value w ij in period t + 1 than in period t. Such i, j and t are guaranteed to exist in a strict best-response cycle.

Let time period t ′ < t be such that i t ′ = i, x t ′ ij = 0, x t ′ +1 ij = 1. As before, for any cycle, such periods may be found by an appropriate time shift.

Let K i = {k : w ik α i δ i > w ij α i δ i + 1 -δ i } denote the set of players whom i strictly prefers to j even if j reciprocates but they do not. If this set is empty, player i will never delete a link with j. It is clear that we must have x t ′ +1 ik = 1 for every k ∈ K i , otherwise we cannot have x t ′ +1 ij = 1 as a best response to x t ′ by Lemma 3.1. This in turn implies that x t ik = 1 for every k ∈ K i , otherwise we would have a time period t ′′ ∈ {t ′ + 1, . . . , t -1} where i deletes her link to a k ∈ K i but keeps the link to j, which cannot happen in a best response.

So, at time t, when i deletes her link to j, every link that offers a better payoff was already formed, and since she cannot have more neighbors of equal value in t + 1 by the choice of j, it is impossible that x t+1 i is a best response to x t provided that x t i was not a best response to x t . This concludes the proof of Claim A.8 and thus of Proposition 3.3.

■ Corollary 3.5

To prove points 1 and 3, the statements on the lower bounds, we set x ji = 0 for all j ∈ I \ {i}. We then have w ij α ′ i δ i ≥ w ij α i δ i and w ij α i δ ′ i ≥ w ij α i δ i , meaning that for any r we have {j :

w ij α ′ i δ i > c ′ i (r)} ⊇ {j : w ij α i δ i > c ′
i (r)}, implying point 1, as well as {j :

w ij α i δ ′ i > c ′ i (r)} ⊇ {j : w ij α i δ i > c ′ i (r)}, implying point 3.
For points 2 and 4, the statements on the upper bounds, we set x ji = 1 for all j ∈ I \ {i}. Then,

w ij (α ′ i δ i + (1 -δ i )) ≥ w ij (α i δ i + (1 -δ i )) and w ij (α i δ ′ i + (1 -δ ′ i )) ≤ w ij (α i δ i + (1 -δ i ))
, meaning that for any r we have {j :

w ij (α ′ i δ i + (1 -δ i )) > c ′ i (r)} ⊇ {j : w ij (α i δ i + (1 -δ i )) > c ′ i (r)}, implying point 2, and {j : w ij (α i δ ′ i + (1 -δ ′ i )) > c ′ i (r)} ⊆ {j : w ij (α i δ i + (1 -δ i )) > c ′ i (r)}, implying point 4. ■ Proposition 3.7
We decompose the network formation game with parameters (α ′ , δ) into two parts: the mutual links that are formed in the equilibrium x of the game (α, δ), y(x) and the remaining links. In particular, we will look at the network formation game with parameters (α ′ , δ) such that wij = 0 for all {i, j} ∈ y(x) (4) wij = w ij for all {i, j} / ∈ y(x)

ci (r) = c i (r + deg i (x)) for r ∈ N, i ∈ I
Clearly, for every i ∈ I the maximal number of links in this game is given by di = di -deg i (x). Furthermore, by Proposition 3.3, this game has an equilibrium -denote such an equilibrium by x. Note that since ci (r) > 0 for all r, xij = 0 holds for all {i, j} ∈ y(x).

For the original game with parameters (α ′ , δ), define the strategy combination x ′ by x ′ ij = 1 for all {i, j} ∈ y(x) and x ′ ij = xij for all {i, j} / ∈ y(x). Note that for each i,

deg + i x ′ = deg + i (x) + deg i (x) (5)
We now show that x ′ ∈ X * (α ′ , δ) by showing that x ′ i satisfies the two conditions in Lemma 3.1, i.e. it is a best response to x ′ -i , starting with condition 1. Take an {i, j} such that x ′ ij = 1. Case 1: If {i, j} ∈ y(x), and there exists some k such that x ′ ik = 1 and {i, k} / ∈ y(x), then we have

w ij α ′ i δ i + (1 -δ i ) x ′ ji ≥ w ik α ′ i δ i + (1 -δ i ) x ′ ki > c′ i deg + i (x) = c ′ i deg + i x ′ ,
where the first inequality follows from the fact that x is monotonic and thus w ij ≥ w ik , the second inequality follows from the fact that x ′ ki = xki and x is an equilibrium of (4) and the equality is a consequence of the definition of c and (5).

Case 2: If {i, j} ∈ y(x) and N + i (x ′ ) = N i (x) then we have

w ij α ′ i δ i + (1 -δ i ) ≥ w ij [α i δ i + (1 -δ i )] > c ′ i (deg i (x)) = c ′ i deg + i x ′ ,
where the first inequality is due to α ′ i ≥ α i , the second is due to the fact that {i, j} ∈ y(x) and x was an EUA of the game with α, and the equality is by the definition of c and (5).

Case

3: If {i, j} / ∈ y(x), then x ′ ij = xij w ij α ′ i δ i + (1 -δ i )x ′ ji > c′ i (deg i (x)) = c ′ i (deg i (x)),
where the inequality holds due to the fact that x is an equilibrium of (4) and the equality is a consequence of the definition of c and (5). Thus, condition 1 of Lemma 3.1 is satisfied whenever x ′ ij = 1. Take next an {i, j} such that x ′ ij = 0. Clearly, {i, j} / ∈ y(x) and thus x ′ ij = xij . Since xij is an equilibrium of the game defined by (4), we have

w ij α ′ i δ i + (1 -δ i ) x ′ ji < c′ i deg + i (x) = c ′ i deg + i x ′ .
Thus, condition 1 of Lemma 3.1) is satisfied whenever x ′ ij = 0 as well. Finally, we check condition 2. Suppose that there exist distinct players i, j and k such that w ij (α

′ i δ i + (1-δ i )x ′ ji ) > w ik (α ′ i δ i +(1-δ i )x ′ ki
), but x ′ ik = 1 and x ′ ij = 0. Clearly, {i, j} / ∈ y(x). If {i, k} ∈ y(x) then x ′ ki = 1, and since w ik ≥ w ij by the fact that x is monotonic, this contradicts w ij (α

′ i δ i + (1 -δ i )x ′ ji ) > w ik (α ′ i δ i + (1 -δ i )x ′ ki )
. Hence, {i, k} / ∈ y(x). Since x is an EUA of the game (4), by condition 2 of Lemma 3.1 we have

w ij α ′ i δ i + (1 -δ i )x ji = w ij α ′ i δ i + (1 -δ i )x ′ ji ≤ w ik (α ′ i δ i + (1 -δ i )x ′ ki ) = w ik (α ′ i δ i + (1 -δ i )x ki ), a contradiction.
Therefore, all conditions of Lemma 3.1 hold.

■

A.4 Proofs for Section 4

Lemma 4.3

Proof: Take an x * ∈ V * . For contradiction, assume an x ∈ X * exists that Pareto dominates x * . Suppose that for every i ∈ I we have deg i (x) ≥ deg i (x * ). Then, for every i ∈ I we have c i (x) ≥ c i (x * ), thus, for u i (x) ≥ u i (x * ) to hold we must have j∈N i (x) w ij ≥ j∈N i (x * ) w ij , for each i ∈ I and strict inequality for at least one player, contradicting the weight-maximality of x * . Thus, there exists a player i with deg i (x) < deg i (x * ). However, since x * is monotonic,

u i (x) ≥ u i (x * ) requires deg i (x) ≥ deg i (x * ), a contradiction. ■ Proposition 4.4
We first prove a supporting statement.

Lemma A.9. Suppose that the players exhibit aligned preferences. For a T ∈ N let (x t ) t∈{0,...,T } be a finite sequence of networks obeying the defined updating rule such that x 0 ∈ V * and x t ∈ y -1 (V * ) for t ∈ {0, . . . , T }. Then, for every t ∈ {0, . . . , T } and every i ∈ I we have w ′ i (x t ) > c ′ i (d i ). Proof: Suppose that we have w ′ i (x t ) < c ′ (d i ). Let t denote the first such period, i.e.

x t i ∈ B i (x t ) or x t i ∈ B o i (x t ).
It is clear that the latter is impossible as optimistic players never initiate or accept such links, thus we must have x t i ∈ B i (x t ). Since y(x t ) ∈ V * and since preferences are aligned x t i is monotonic for i. This means that for every k such that w ′ i (x t ) < w ik we have {i, k} ∈ x t . However, by the definition of d i , this has to imply deg + i (x) > d i , which is also impossible as a best-responding player would not initiate more than d i links.

■

Proof of Proposition 4.4: We first show that y(x ′ ) ∈ X * . Take a sequence (x t ) t∈{0,...,T } obeying the defined updating rule with x 0 ∈ V * . Since x 0 is a Nash equilibrium, then by the updating rule, for every x t we have w ′ i t (x t ) > c ′ i t (deg i t (x t )). Thus, for every t ′ ∈ {0, . . . , T } and every i, j ∈ I with

x t ′ ij = x t ′ ji = 1 we have w ij > c ′ i (deg + i (x t ′ )) ≥ c ′ i (deg i (x t ′ ))
, satisfying the conditions of a Nash equilibrium. Thus, for contradiction, suppose that x ′ ∈ S(x * ) and y(x ′ ) / ∈ V * . Then we must have v(x ′ ) < v(x * ), as v(x ′ ) = v(y(x ′ )) > v(x * ) would contradict the choice of x * as a maximum-benefit equilibrium, while v(x ′ ) = v(x * ) would imply y(x ′ ) ∈ V * . Thus, the value of the network must decrease along the sequence between x * and x ′ . Suppose that x ′ is the earliest element of the sequence with v(x ′ ) < v(x * ), let x denote the element immediately preceding it and let i denote the player who updated between x and x ′ , i.e. x -i = x ′ -i . Since v(x) > v(x ′ ) there must exist {i, j} ∈ x \ x ′ and by Lemma A.9 it must satisfy w ij > c ′ i (d i ). Suppose that x ′ i ∈ B i (x). Then, since i drops her link with j as a best response even though j reciprocates, we must have

w ij < c ′ i (deg + i (x ′ ) + 1) = c ′ i (deg i (x ′ ) + 1). Thus, deg i (x ′ ) + 1 > d i , meaning that deg i (x ′ ) = d i .
Since i made a best response, u i (x) ≤ u i (x ′ ), and since the number of neighbors in x ′ is at maximum, and thus the weak increase in utility did not come through a decrease in costs, the total value of i's links must have weakly increased from x to x ′ . Hence, we have

v(x) = 2 j̸ =i w ij x ij x ji + k̸ =i j̸ =k̸ =i w jk x jk x kj ≥ 2 j̸ =i w ij x ′ ij x ji + k̸ =i j̸ =k̸ =i w jk x jk x kj = v(x ′ ), a contradiction to v(x ′ ) < v(x). Suppose that x ′ i ∈ B o i (x)
. Then, since x ′ i is monotonic for i and i drops her link with j,

deg + i (x ′ ) = d i . Since w ij > c ′ i (d i )
, and yet i chose not to reciprocate j's link, there must exist k ∈ I with w ij = w ik such that {i, k} ∈ x ′ . Since y(x) i is monotonic, and {i, j} ∈ x for every ℓ ∈ I with w iℓ > w ij we have {i, ℓ} ∈ x. Since x ′ i is monotonic for i, {i, ℓ} ∈ x ′ as well. Furthermore, for every ℓ ∈ I with w ij = w iℓ and x ′ iℓ = 1 we must have x ′ ℓi = x ℓi = 1 as well, otherwise deleting a link to an unreciprocated opponent of equal value is better for i than deleting her link to j. Thus, deg +

i (x ′ ) = deg i (x ′ ) = d i . Finally, x ′ i
being monotonic means that i has a reciprocal link to exactly d i of her most favored opponents. So as before we have

v(x) = 2 j̸ =i w ij x ij x ji + k̸ =i j̸ =k̸ =i w jk x jk x kj ≥ 2 j̸ =i w ij x ′ ij x ji + k̸ =i j̸ =k̸ =i w jk x jk x kj = v(x ′ ), a contradiction to v(x ′ ) < v(x). ■ Proposition 4.5
Lemma A.10. For every x ∈ X there exists x * ∈ X * ∩ S(x) such that for all i ∈ I we have w

′ i (x * ) > c ′ i (d i ).
Proof: First we show that there exists x ′ ∈ X * ∩ S (x). Take an arbitrary x ∈ X. Then, suppose that in the next n periods, all players {1, . . . , n} are given an ambiguity-neutral best-responding revision opportunity in increasing order. Call the resulting network x ′ . The probability of this happening is ((1 -β)/n) n > 0, so we must have x ′ ∈ S(x). Then, for every i ∈ I we have w

′ i (x ′ ) > c ′ i deg + i (x ′
) and for every pair with i > j we can have x ′ ij = 1 only if x ji = 1. Thus, repeating the same process in the reverse order will lead to an undirected network x ′′ with w

′ i (x ′′ ) > c ′ i (deg i (x ′′
)) for all i ∈ I, satisfying the equilibrium conditions.

This shows that we can take x ∈ X * at the start. Take a player i such that w

′ i (x) < c ′ i (d i ).
If none can be found, we are done. If such a player exists, suppose that she receives an optimistic revision opportunity. Then since for every

x o i ∈ B o i (x) we have w ′ i (x o i , x -i ) > c ′ i (d i )
, she will sever all links with players giving her less benefits than c ′ i (d i ) and possibly initiate some links to others. Then, allow all her neighbors with whom she severed her links to best-respond in an ambiguity-neutral way, their only best response being is to sever their unreciprocated links towards i and make no other changes. Finally, let player i best-respond to sever all unreciprocated links she had initiated as an optimist. Call the resulting network x ′ . Since p m β (x, x ′ ) > 0 for some m ≤ N i (x) + 1 we must have x ′ ∈ S(x). At x ′ , we clearly have w

′ i (x ′ ) > c ′ (d i ) since all players j ̸ = i with w ij < c ′ i (d i ) now have no outgoing links towards i while N i (x) ⊇ N i (x ′ ). Thus, we have x ′ i ∈ B i (x ′ ), meaning that x ′ ∈ X * . Furthermore, w ′ i (x ′ ) > c ′ i (d i )
, as well as |x ′ | < |x|, since player i lost links and no player gained any. If there exists j ̸ = i with w ′ j (x ′ ) < c ′ j (d j ), we can repeat this process. If the process does not terminate sooner with a desired network, it will terminate by reaching the empty network which trivially satisfies the conditions of the statement of the lemma.

■

The next lemma shows that the learning process enters the set of maximum-benefit equilibria that are monotonic, V * , for any starting state with a positive probability.

Lemma A.11. Suppose that the players exhibit aligned preferences. For every x ∈ X there exists an x * ∈ V * ∩ S(x).

Proof: By Lemma A.10 we may take x ∈ X * such that w ′ i (x) > c ′ i (d i ) for all i ∈ I. Let x * ∈ V * be the closest element of V * to x. If x ≥ x * , then we must have x = x * otherwise we contradict the choice of x * as an element of V * , in which case we are done. If x ̸ ≥ x * , we have x * \ x ̸ = ∅.

We will show that there exists an x ′′ ∈ X * ∩ S(x) which also satisfies w ′ i (x ′′ ) > c ′ i (d i ) for every i ∈ I and for which ϕ(x ′′ , x * ) < ϕ(x, x * ). Through a repeated application of this argument the distance eventually decreases to 0, meaning that we reach x * . We distinguish two cases.

Case 1. There exists a player i and a link {i, j} ∈ x * \ x such that deg i (x) < d i . Let j ∈ argmax j ′ ∈N i (x * )\N i (x) w ij ′ be the most valuable such link for player i. Then let x ′ i be a strategy which is monotonic for i, deg

+ i (x ′ i , x -i ) = d i , and N + i (x ′ i , x -i ) ⊇ (N i (x) ∩ N i (x *
)) ∪ {j}. By Lemma 3.1, and due to x satisfying w

′ i (x) > c ′ i (d i ), we must have x ′ i ∈ B o i (x).
Let player i receive an optimistic revision opportunity and suppose that she revises to

x ′ i . Case 1a. If deg j (x) < d j , then we must have w ij ≥ w ′ j (x * ) > c ′ j (d j ) ≥ c ′ j (deg j (x) + 1). Therefore, B j (x ′ i , x -i
) is a singleton with its only element, which we denote by x ′ j , satisfying x ′ jk = 1 if and only if k ∈ N j (x)∪{i}. Suppose that player j receives a best-responding revision opportunity, and thus, selects the strategy x ′ j . For each k ∈ N i (x) \ N + i (x ′ i , x -i ) let k receive a best-responding revision opportunity, their only best response being is to keep all of their existing links except those with i who had severed her link to each k. Finally, let player i also receive best-responding revision opportunity. Her only best response, which we denote by x ′′ i , is to delete all unreciprocated links she initiated when she moved to x ′ i , that is, x ′′ ik = 1 if and only if k ∈ (N i (x) ∩ N i (x * )) ∪ {j}. Let the resulting network be denoted by x ′′ . It is clear that x ′′ is an equilibrium network, w ′ (x ′′ ) ≥ c ′ (d), and ϕ(x ′′ , x * ) < ϕ(x, x * ). Since the above process leads to x ′′ from x, we have x ′′ ∈ S(x) as well.

Case 1b. If deg j (x) = d j ≥ deg j (x * ), then there must exist a link {j, k} ∈ x \ x * . Since x * is monotonic we must also have w ij ≥ w jk . Thus, there must exist an x ′ j ∈ B j (x ′ i , x -i ) such that x ′ jℓ = 1 if and only if ℓ ∈ (N j (x) \ {k}) ∪ {i}. As before let j receive a best-responding revision opportunity and suppose that she selects x ′ j . Let this be followed by player k best-responding; her only best response being to cut her now unreciprocated link towards j and keeping all her other neighbors.

Then, as before, for each k ′ ∈ N i (x) \ N + i (x ′ i , x -i ) let k ′ receive a best-responding revision opportunity, their only best response being to keep all of their existing links except those with i, who had severed her link to each k ′ . Finally, let i best-respond, her only best response being to delete all unreciprocated links she initiated when she moved to x ′ i , that is,

x ′′ ik = 1 if and only if k ∈ (N i (x) ∩ N i (x * )) ∪ {j}.
Let the resulting network be denoted by x ′′ . As before, x ′′ ∈ X * , satisfies w ′ (x ′′ ) ≥ c ′ (d) and ϕ(x ′′ , x * ) < ϕ(x, x * ), as well as x ′ ∈ S(x), completing Case 1.

Case 2. For every link {i, j} ∈ x * \ x we have deg i (x) = d i and deg j (x) = d j . We will show that there must exist such a link {i, j} for which there exists {i, k} ∈ x \ x * such that w ij > w ik .

Suppose this is not true, i.e. for every i, j, k with {i, j} ∈ x * \ x and {i, k} ∈ x \ x * we have

w ij ≤ w ik . Since deg i (x) = d i for all i with N i (x) ̸ = N i (x * ) we must have deg i (x) ≥ deg i (x * ) for all i.
These two facts imply that v(x) ≥ v(x * ) which can only hold with equality as x * is a maximum-benefit equilibrium network. If deg i (x) > deg i (x * ) for some i ∈ I and deg j (x) ≥ deg j (x * ) for all other j ̸ = i, then v(x) = v(x * ) can hold only if we have such a trio i, j, k with {i, j} ∈ x * \ x, {i, k} ∈ x \ x * , and we have w ij > w ik , a contradiction. So suppose that deg i (x) = deg i (x * ) for all i. Now we will show that under these conditions x is monotonic, a contradiction since that would mean x ∈ V * . Take a player i and suppose that there exist j, k ̸ = i such that {i, j} ∈ x, {i, k} / ∈ x and w ij < w ik . If no such player can be found, x is monotonic. We must have {i, k} / ∈ x * by assumption thus {i, k} ∈ x \ x * . However, due to deg i (x) = deg i (x * ) there must exist an ℓ ∈ N i (x * ) \ {j} and by assumption we must have w ik > w ij ≥ w iℓ . Thus, since {i, k} / ∈ x * , this is a contradiction as x * is monotonic.

Therefore if for every link {i, j} ∈ x * \x we have deg i (x) = d i and deg j (x) = d j , then there must exist {i, j} ∈ x * \ x and a {i, k} ∈ x \ x * such that w ij > w ik . In particular, let j ∈ argmax j ′ ∈N i (x * )\N i (x) w ij ′ and let k ∈ argmin j ′ ∈N i (x)\N i (x * ) w ij ′ . Construct a strategy x ′ i such that it is monotonic and for every ℓ ∈ (N i (x) ∩ N i (x * )) ∪ {j} we have x ′ iℓ = 1. By the fact that w ij > w ik , we must have such a strategy with deg + i (x ′ i , x -i ) = d i as player i can include j to her set of neighbors and exclude k and still maintain an out-degree of d i . By Lemma 3.1, we have x ′ i ∈ B o i (x). As in Case 1, let i receive an optimistic revision opportunity and suppose she picks the optimistic best response x ′ i . From here by the same process as in Case 1b we can reach x ′′ ∈ X * ∩ S(x) with w ′ (x ′′ ) > c ′ (d) and ϕ(x ′′ , x * ) < ϕ(x, x * ).

■

Finally, given that we reach V * , the proof of the Proposition itself follows simply from Proposition 4.4. Proof of Proposition 4.5. By Lemma A.11 for every x ∈ X we have a x * ∈ V * with x * ∈ S(x). Since there are finitely many networks, with probability one, the process enters V * and thus y -1 (V * ). By Proposition 4.4, the game never leaves y -1 (V * ).

■ Proposition 4.6

As shown in Propositions 4.4 and 4.5, for every β > 0, the set y -1 (V * ), is an absorbing set of the Markov chain (X, p β ), while all states outside of y -1 (V * ) are transient. We thus restrict attention to the set y -1 (V * ). Since the Markov process y -1 (V * ), p β need not be irreducible, we partition the set y -1 (V * ) into K ≥ 1 communicating classes: each class consists of a non-empty set of MBE, V k ⊆ V * and the corresponding set y -1 (V k ) and (V k ) K k=1 is a partition of V * . This partition is independent of β as long as β ∈ (0, 1).

Fix k ∈ {1, . . . , K} and consider the set of Markov chains y -1 (V k ), p β β∈(0,1) . Note that each such chain is aperiodic, irreducible and defined on a finite state space and thus has a unique invariant distribution μk,β . The set of stochastically stable states of such a chain is defined as

supp(μ k ) = supp lim β→0 μk,β (6)
provided that the limit exists.

To show existence and characterize the limit, we follow Vega-Redondo (2003, p. 480-481). For x, x ′ ∈ X, denote by p ∞ 0 (x, x ′ ) the transition probability from x to x ′ after an infinite number of applications of the best-response dynamics without optimistic surges, p ∞ 0 = lim m→∞ p m 0 . For a given β ∈ (0, 1) and k ∈ {1, . . . , K}, we define a Markov chain on (V k , Q k,β ) as follows: for x, x ′ ∈ V k , the transition probability Q k,β (x, x ′ ) is the concatenation of the one-step-ahead best-response dynamics with optimistic surges, p β , with p ∞ 0 :

Q k,β (x, x ′ ) = x ′′ ∈y -1 (V k ) p β (x, x ′′ )p ∞ 0 (x ′′ , x ′ )
As we know from the proof of Proposition 3.3 and Proposition 4.5, the best-response dynamics without optimistic surges with a starting point in y -1 (V k ) reaches V k in finite time. Thus, the process is well-defined and satisfies for every β ∈ (0, 1):

1. For every x ∈ V k , Q k,β (x, x) > 0, and thus, (V k , Q k,β ) is aperiodic, because the largest common denominator of the periods in which an element x is reached is 1.

2. For any x, x ′ ∈ V k , x ̸ = x ′ , either Q k,β (x, x ′ ) = 0 or Q k,β (x, x ′ ) = βξ(x, x ′ ), where ξ(x, x ′ ) ∈ (0, 1) is the probability that the best-response dynamics (without optimistic surges) reaches x ′ from x, conditional on an optimistic shock occurring, and is thus independent of β.

3. Q k,β (x, x ′ ) = 0 if and only if Q k,β ′ (x, x ′ ) = 0 for all β ′ ∈ (0, 1).

By the definition of V k , (V k , Q k,β ) is irreducible for all β ∈ (0, 1) and since it is defined on a finite state space and aperiodic, it has a unique probability distribution µ k,β . If µ k,β converges to µ k as β → 0, then the limit on the right hand side of (6) exists and the support of µ k is exactly the set of stochastically stable states of y -1 (V k ), p β , see Young (1993), KMR andVega-Redondo (2003, p. 481):

supp(µ k ) = supp lim β→0 µ k,β = supp(μ k ). ( 7
)
Lemma A.12. For all k ∈ {1...K}, supp (lim β→0 µ k,β ) = V k .

Proof : Fix a k ∈ {1, . . . , K}. Clearly, if |V k | = 1, then µ k,β (x) = 1 for the unique x ∈ V k and for all β ∈ (0, 1) and the statement of the lemma is trivially satisfied. Suppose thus that |V k | ≥ 2. The resistance function defined in Young (1993, p. 68),8 which we here denote by e k (x, x ′ ), satisfies:

0 < Q k,β (x, x ′ ) β e k (x,x ′ ) < ∞.
By property 2, for x ̸ = x ′ such that Q k,β (x, x ′ ) > 0, we have 0 < βξ(x, x ′ ) β e k (x,x ′ ) < ∞, or

e k (x, x ′ ) = 1 iff Q k,β (x, x ′ ) > 0,
and, by convention,

e k (x, x ′ ) = ∞ iff Q k,β (x, x ′ ) = 0.
Following Young (1993, p. 69), consider the set of directed graphs Y on V k such that every x ′ ∈ V k is the initial point of exactly one edge (x ′ , x ′′ ) and for every x ′ there is a path leading to x. Denote the set of all such graphs by Y k,x . The resistance of such a graph Y ∈ Y k,x is given by

E k,x (Y ) = (x ′ ,x ′′ )∈Y
e k (x ′ , x ′′ ).

Denote by E k,x (Y k,x ) the minimal resistance over graphs in Y k,x :

E k,x (Y k,x ) = min Y ∈Y k,x (x ′ ,x ′′ )∈Y
e k (x ′ , x ′′ ).

We will call a graph Y ∈ Y k,x feasible if e k (x ′ , x ′′ ) < ∞, for all (x ′ , x ′′ ) ∈ Y . Since (V k , Q k,β ) is irreducible, there exists a feasible graph for each x. If |V k | = 2, this graph is unique, it is given by (x ′ , x) and has a resistance of

E k,x (Y k,x ) = e k (x ′ , x) = 1 = |V k | -1.
If |V k | > 2, the feasible graph need not be unique. Notably, the graph Y = (x ′ , x 1 ), (x 1 , x 2 ), . . . , (x l , x) , where l = |V k | -2, {x ′ , x 1 , . . . , x l } = V k \ {x} and Q k,β (x ′ , x 1 ) > 0, Q k,β (x λ , x λ+1 ) > 0 for λ ∈ {1, . . . , l -1} and Q k,β (x l , x) > 0 is feasible. The resistance of such a graph is given by the number of its edges:

E k,x (Y ) = |V k | -1.
Since each feasible graph in Y k,x has the same number of edges, it follows that for all x ∈ V k , min

Y ∈Y k,x E k,x (Y ) = E k,x (Y k,x ) = |V k | -1 = min x∈V k min Y ∈Y k,x (x ′ ,x ′′ )∈Y e(x ′ , x ′′ ) = E k,x (Y x ).
Theorem 2 of [START_REF] Young | The evolution of conventions[END_REF] implies that µ k = lim β→0 µ k,β exists and satisfies supp(µ k ) = V k , concluding the proof of the lemma.

■

Let κ = (κ 1 , . . . , κ K ) be such that K k=1 κ k = 1 and κ k > 0 for all k ∈ {1, . . . , K} and consider the probability distribution μβ (κ) = K k=1 κ k μk,β .

For each β ∈ (0, 1), μβ (κ) is an invariant (though not unique) probability distribution of the Markov chain (y -1 (V ), p β ), and since all states outside of y -1 (V ) are transient, also of (X, p β ). Furthermore, for a given κ with κ k > 0 for all k ∈ {1, . . . , K}, (7), together with Lemma A.12, implies:

supp lim β→0 μβ (κ) = supp lim β→0 K k=1 κ k μk,β = supp K k=1 κ k µ k = ∪ K k=1 V k = V * ,
concluding the proof of the proposition.

■

Proposition 4.9

As before, we first show that the dynamic system will take the game into V * , which is a unique network x * in the linear case.

Lemma A.13. Let the cost functions be linear. For every x ∈ X and the unique x * ∈ V * we have x * ∈ S(x).

Proof: By Lemma A.10 we can take x ∈ X * . We show that if x = x * there exists x ′ ∈ S(x) ∩ X * such that ϕ(x ′ , x * ) < ϕ(x, x * ). Take a link {i, j} ∈ x * \ x. Then, we must have w ij > max{c i , c j }. Take the following series of updates: i receives a revision opportunity as an optimist, j receives a revision opportunity as a best-responder, then i receives a revision opportunity as a best-responder. It is clear that an optimistic player i will link to j, as well as keep all of her links to her neighbors in x. A best-responder j will make no changes except reciprocate player i's link. Finally, player i deletes all the unreciprocated links she made as an optimist. For the resulting network, x ′ = x ∪ {i, j}, we have x ′ ∈ X * as well as ϕ(x ′ , x * ) = ϕ(x, x * ) -1.

■

Secondly, we show that once x * is reached, the game never leaves the set y -1 (x * ).

Lemma A.14. Let the cost functions be linear. For the unique x * ∈ V * we have S(x * ) ⊆ y -1 (x * ).

Proof: Suppose for contradiction that there exist a pair x, x ′ ∈ S(x * ) such that x ∈ y -1 (x * ), x ′ ∈ S 1 (x), and x ′ / ∈ y -1 (x * ). Then, there must exist {i, j} ∈ x ′ \ x, with w ij > max{c i , c j }. Clearly, one of i and j must have updated to get from x to x ′ so suppose it was i, i.e. x -i = x ′ -i . If x ′ i ∈ B i (x), then, since x ′ ji = x ji = 1, deleting the link to j cannot be a best response. If x ′ i ∈ B o i (x), then, since w ij > c i , deleting the link to j cannot be an optimistic best response, so we have arrived at a contradiction.

This completes the proof of the proposition.

■

Figure 1 :

 1 Figure 1: The weight network of Example 3.8. Reciprocated links are shown as continuous edges, no linking is indicated by dashed ones. If H > L > 0, and if c ′ i (2) < L then network x * (right panel) is the unique Pareto optimal equilibrium network. There exist parameters αi, δi, under which the underconnected but monotonic network x (left panel) is an EUA. Increasing the optimism parameters to α ′ i > αi can lead to x * being the only EUA.

Figure 2 :

 2 Figure 2: Network realignment from a Pareto dominated pairwise stable equilibrium to an MBE network. An optimistic shock compels A to seek out a new, better partner, severing her link to D and extending one to B. A best-responding B reciprocates A's link and severs the one to C. A best-responding C deletes her unreciprocated link to B. Finally, when D receives an optimistic shock herself, she will extend a link to C which a best-responding C accepts.

Example A. 4 .Figure 4 :

 44 Figure 4: The weight network of example A.4. Links not shown in the figure are assumed to offer no benefits.

  and proceeds as follows. (1) under an optimistic shock, A severs her link to D and extends one to B. (2) a best-responding B severs her link to C and reciprocates A's link. (3) C best responds, cutting her unreciprocated link to B. The network now has the link {A, B} established, which is a Nash equilibrium network, and in network distance terms, closer to x * . (4) under another optimistic shock, D extends a link to C. (5) a best-responding C reciprocates, forming the network x * .

[START_REF] Bloch | Endogenous Structures of Association in Oligopolies[END_REF] and[START_REF] Goyal | Networks of collaboration in oligopoly[END_REF] work with decreasing marginal cost, which seems realistic when the cost of links can be distributed across all members of an association / partners, but not when links are bilateral and costs are player-specific

[START_REF] Dutta | Stable networks[END_REF] show how an allocation rule can be designed so as to implement a strongly stable efficient equilibrium. In general, such rules require transfers.

Two exceptions are the models of[START_REF] König | Nestedness in networks: A theoretical model and some applications[END_REF], in which the unique equilibrium is the complete graph and of[START_REF] Staudigl | Potential games in volatile environments[END_REF], which is a potential game with identical link values and no cost of link formation.

The formal definitions of a capacity and a NEO-additive capacity are relegated to the Appendix.

As is well-known in the literature, a Choquet integral over a NEO-additive capacity can be written as an α-max-min expected utility over a set of probability distributions determined by the parameters πi and δi, see equation (3) in the Appendix.

Other models of ambiguity in games include[START_REF] Hanany | Incomplete information games with ambiguity averse players[END_REF] who concentrate on games with incomplete information, where the ambiguity is about the types of other players, as well as the approach of[START_REF] Riedel | The Strategic Use of Ambiguity[END_REF] in which players using ambiguous randomization devices to decide on their strategies. These motivations are quite different from the strategic uncertainty we seek to model here.[START_REF] Dominiak | Games in Context: Equilibrium under Ambiguity for Belief Functions[END_REF] generalize the equilibrium under ambiguity with NEO-additive capacities to belief functions, which however necessitates a significantly larger number of parameters.

Intuitively, the resistance function in[START_REF] Young | The evolution of conventions[END_REF] corresponds to the number of shocks necessary to induce a transition from x to x ′ .

Theory for helpful comments and suggestions. This research was supported by IUF, Labex MME-DII, the French National Research Agency in the framework of the "Investissements d'avenir" programs ANR-15-IDEX-02 and ANR-17-EURE-0010, and by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No. 789111 -ERC EvolvingEconomics).