Network Game Equilibrium in Vee Relationships

Welcome back. In our previous lesson, we developed a sophisticated framework for modeling the emotional externalities within a vee relationship. By incorporating concepts from Social Decision Theory and Rabin's reciprocity model, we can now represent jealousy and compersion as integral components of each partner's utility function, making payoffs explicitly dependent on the actions and outcomes of others in the network.

Now that we have players (H, P1, P2), a network structure (the vee), and rich, network-dependent utility functions, we can address a fundamental question: What constitutes a stable outcome in this complex system? This lesson aims to answer that by defining a network game equilibrium in the context of a vee relationship. Your familiarity with Nash equilibrium provides a strong foundation, as we will be extending that core idea to settings where both player actions and the network structure itself are objects of analysis.

What is a Game on a Network?

First, let's formalize the environment. A "game on a network" is a strategic interaction where players' payoffs are determined by their own choices and the choices of their immediate neighbors in a given network. A comprehensive paper by Jackson and Zenou, "Games on Networks," provides the standard definitions for this field.

Games on Networks

This paper lays out the foundational concepts for analyzing strategic behavior on networks. We will use it to establish a precise language for our analysis.

Please read the introductory section "Background Definitions". Pay attention to the definitions of Players and Networks, which formalizes the graph notation we've been using. Then, focus on the section Games on Networks, which defines the action spaces and the payoff function u_i : A \times G(N) \to \mathbb{R}. The key takeaway is the definition of a pure strategy Nash equilibrium in this context.

As the reading clarifies, a pure strategy Nash equilibrium (PSNE) for a game on a fixed network is a profile of actions, one for each player, such that no single player has an incentive to unilaterally change their action, given the actions of others.

Let's ground this in our vee model:

Players, $N = {H, P 1, P 2}$ .
Network, $g_{v ee}$ , is fixed: the links are $H - P 1$ and $H - P 2$ . The neighborhood of the hinge is $N_{H} (g) = {P 1, P 2}$ , while for the partners, $N_{P 1} (g) = {H}$ and $N_{P 2} (g) = {H}$ .
Actions, $A_{i}$ , for each player $i$ , could be binary (e.g., {Invest, Don't Invest}) or continuous (e.g., amount of time to offer).
Payoffs, $u_{i} (a, g_{v ee})$ , are the utility functions we developed in the last lesson. Crucially, a player's payoff $u_{i}$ depends directly on the actions of their neighbors, ${a_{j}}_{j \in N_{i} (g)}$ . Due to the externality terms (jealousy/compersion), $u_{i}$ can also be indirectly affected by the actions of players who are not direct neighbors. For instance, $u_{P 1}$ depends on $a_{H}$ , but also on $a_{P 2}$ because P2's actions influence P2's outcome, which in turn may enter P1's positional utility function. This is what the paper refers to as "indirect network effects."

An equilibrium is a state where the chosen actions of H, P1, and P2 are mutually consistent best responses. For example, if the actions are (Invest, Don't Invest, Invest) for (H, P1, P2), this is an equilibrium only if H finds "Invest" to be the best response to P1 not investing and P2 investing, P1 finds "Don't Invest" optimal given H's and P2's investment, and so on.

Characterizing Equilibria: Complements and Substitutes

The nature of the equilibrium often depends on the type of strategic interaction. As an expert in operations research, you know that classifying problems is key to solving them. In network games, a primary distinction is between games of strategic complements and strategic substitutes.

Games on Networks

This reading explores two major classes of network games and provides powerful concepts for characterizing their equilibria.

First, read the definitions of strategic complements and substitutes. Then, jump to the subsection Coordination Games. Focus on the definition of a q-cohesive set. This gives us a precise condition for the existence of an equilibrium where a subgroup of players takes a different action from the rest.

Let's examine how these concepts define equilibria in a vee:

Strategic Complements (e.g., Coordination Games):
These are games where a player's incentive to take an action increases as more of their neighbors take that action. Think of adopting a shared calendar or a specific communication style; it's more valuable if your partners also use it.
- Equilibrium Definition: For a coordination game with a threshold $q$ (the minimum fraction of neighbors that must take action 1 for you to also prefer action 1), an equilibrium where a set of players $S$ chooses action 1 and the rest choose 0 exists if and only if:
  1. $S$ is q-cohesive: every player in $S$ has at least a fraction $q$ of their neighbors also in $S$ .
  2. The complement, $N ∖ S$ , is (1-q)-cohesive: every player outside $S$ has at least a fraction $1 - q$ of their neighbors also outside $S$ .
- In a Vee: Let's say $q = 0.6$ . This means you need more than half your partners to agree.
  - Can ${H}$ be a stable group playing '1' while ${P 1, P 2}$ play '0'? No. H has 0% of neighbors playing '1', which is less than $q = 0.6$ .
  - Can ${P 1}$ be a stable group? No. P1's only neighbor is H, who is playing '0'.
  - The only stable equilibria are typically where everyone plays '1' (the set $N$ is 1-cohesive) or everyone plays '0' (the empty set is trivially cohesive, and its complement $N$ is 1-cohesive, which is greater than $1 - q = 0.4$ ). This formalism confirms the intuitive all-or-nothing outcomes of many coordination problems.
Strategic Substitutes (e.g., "Best-Shot" Games):
These are games where a player's incentive to take an action decreases as more of their neighbors take it. A classic example is providing a local public good. Imagine "planning a date night" is a costly action, but once one person in a neighborhood does it, everyone benefits and the others prefer not to duplicate the effort.
- Equilibrium Definition: As noted in the Jackson and Zenou paper (Example 2), the pure-strategy Nash equilibria of a best-shot game correspond exactly to the maximal independent sets of the network. An independent set is a set of nodes where no two nodes are linked. A maximal independent set cannot be made larger without violating this property. The players in the maximal independent set are the ones who take the costly action (e.g., provide the good).
- In a Vee: The vee graph $g_{v ee}$ has exactly two maximal independent sets:
  1. ${H}$ : The hinge.
  2. ${P 1, P 2}$ : The two partners.
- This implies two possible pure-strategy Nash equilibria for a best-shot game on a vee:
  1. Equilibrium 1: The Hinge takes the action, and both partners free-ride. (H plans the dates, P1 and P2 benefit).
  2. Equilibrium 2: Both partners take the action, and the Hinge free-rides. (P1 and P2 both plan dates for their respective dyads, H benefits from both).

These examples show how the network structure interacts with the game's strategic nature to produce specific, characterizable equilibrium outcomes.

Equilibrium of the Network Itself: Is the Vee Stable?

So far, we have assumed the vee network is fixed. But a complete definition of equilibrium must also consider the stability of the relationship structure itself. Would the players choose to maintain this vee structure, or would they prefer to change it? The field of strategic network formation addresses this.

The foundational concept is pairwise stability, introduced by Jackson and Wolinsky. A second paper, "Definitions of Equilibrium in Network Formation Games" by Bloch and Jackson, provides a fantastic overview of this and related concepts.

Definitions of Equilibrium in Network Formation Games

This paper compares different ways to define a stable network. It moves our focus from the stability of actions on a network to the stability of the network itself.

Please read Section 2, "Modeling Networks," and Section 3.1, Pairwise stable networks. This introduces the core concept. Then, read about the linking game and its equilibria in Section 3.2, focusing on the definitions of Nash Stability (NS) and Pairwise Nash Stability (PNS).

Let's unpack these crucial definitions in the context of our vee.

Pairwise Stability (PS): A network $g$ is pairwise stable if:
1. No Severing: For every existing link, neither of the two players involved would be better off by deleting it.
  - Vee Application: Is $u_{H} (g_{v ee}) \geq u_{H} (g_{v ee} - H P 1)$ ? Does the hinge want to break up with P1? Is $u_{P 1} (g_{v ee}) \geq u_{P 1} (g_{e m pt y})$ ? Does P1 want to leave the relationship entirely? These conditions must hold for all links.
2. No Adding: For any two players who are not linked, it's not the case that they would both be better off by adding a link.
  - Vee Application: The crucial test here is the potential link between P1 and P2. The vee is stable against becoming a triad only if it's NOT the case that both $u_{P 1} (g_{t r ia d}) > u_{P 1} (g_{v ee})$ AND $u_{P 2} (g_{t r ia d}) > u_{P 2} (g_{v ee})$ . If both partners would benefit from forming a relationship with each other (perhaps to increase their bargaining power or share information), then the vee structure is not pairwise stable.
Pairwise Nash Stability (PNS): This is a stronger concept that refines both Nash stability from Myerson's linking game and pairwise stability. As the paper notes, it is effectively the intersection of the two: PNS = PS ∩ NS. It requires the network to be immune to unilateral link severances by any individual and bilateral link additions by any pair. This is an excellent candidate for a formal definition of a stable relationship structure.

A network game equilibrium, in its most complete sense, is a state where a Nash equilibrium of actions is being played on a stable network structure (e.g., a pairwise stable network). This means not only is nobody incentivized to change their behavior within the relationship structure, but nobody is incentivized to change the structure itself.

Conclusion

In this lesson, we have formally defined what an equilibrium means in a game played on a network. We have seen that this concept has two distinct but interconnected layers: the stability of players' actions and the stability of the network itself.

Key Takeaways:

A game on a network involves players whose payoffs depend on the actions of their neighbors in a fixed graph. A pure strategy Nash equilibrium in this context is a profile of actions where no player can benefit by unilaterally deviating.
For games of strategic complements (coordination), equilibria can be characterized by q-cohesive sets, which require groups of players taking an action to be sufficiently internally connected.
For games of strategic substitutes (anti-coordination), equilibria often correspond to maximal independent sets of the network graph. In a vee, this points to two possible equilibria: one where the hinge acts alone, and one where the two partners act.
A pairwise stable network is one where no player wishes to sever a link and no two unlinked players mutually wish to add one. This provides a formal definition for the stability of the vee structure itself, particularly against evolving into a triad.
A comprehensive network game equilibrium combines these ideas: it is a Nash equilibrium of actions being played on a network structure that is itself stable.

In our next lesson, we will build on this foundation. We've defined what makes a system stable, but is it also resilient? We will distinguish between game-theoretic stability (the equilibrium concepts we just discussed) and network-theoretic resilience, which measures how a network's functionality holds up against shocks and disruptions.

Recommended resources

What is a Game on a Network?

Characterizing Equilibria: Complements and Substitutes

Equilibrium of the Network Itself: Is the Vee Stable?

Conclusion