Efficiency vs. Stability in Network Formation

What Makes a Relationship Network "Efficient"?

In network theory, "efficiency" is a measure of the overall value or welfare a network generates for its members. While several measures exist, the most direct is utilitarian welfare, which is simply the sum of the utilities of all individuals in the network. An efficient network is one that maximizes this total sum.

This approach allows us to ask: which configuration of relationships—a vee, a triad, or something else—creates the most collective happiness or benefit?

The note "Note on Network Game" provides a clear definition of efficiency based on this idea.

As you've just read, a network is efficient if it maximizes ${\sum }_i{u}_i(g)$. We can now use this tool to compare the potential relationship structures for our three individuals: the Hinge (H), Partner 1 (P1), and Partner 2 (P2).

Calculating the Efficiency of Vee vs. Triad

Let's use the same utility function from our previous lesson, $U_i(g)={\sum }_{j\ne i}{\delta }^{d(i,j)}-n_i(g)\cdot c$, to calculate the total welfare for the three most relevant structures for our group of three: the empty network (no relationships), the vee, and the triad (everyone involved with everyone else).

1. Empty Network ($g_{empty}$): No links exist.

   • Total Welfare: $W(g_{empty})=0+0+0=0$.

2. Vee ($g_{vee}$): Links are {P1, H} and {H, P2}. This is a "star network" with n=3.

   • As we calculated before, $U_{P1}=U_{P2}=\delta +{\delta }^2-c$ and $U_H=2\delta -2c$.
   • Total Welfare: $W(g_{vee})=(\delta +{\delta }^2-c)+(2\delta -2c)+(\delta +{\delta }^2-c)=4\mathbf{\delta }+2{\mathbf{\delta }}^2-4\mathbf{c}$.

3. Triad ($g_{triad}$): Links are {P1, H}, {H, P2}, and {P1, P2}. This is a "complete network."

   • Each player has two links and is distance 1 from both others. Utility for each is $U_i=2\delta -2c$.
   • Total Welfare: $W(g_{triad})=3\times (2\delta -2c)=6\mathbf{\delta }-6\mathbf{c}$.

Now, which is most efficient? It depends on the parameters $\delta$ (benefit) and $c$ (cost).

• Triad vs. Vee: The triad is more efficient if $W(g_{triad})>W(g_{vee})$.

  $$6\delta -6c>4\delta +2{\delta }^2-4c$$ $$2c<2\delta -2{\delta }^2$$ $$\mathbf{c}<\mathbf{\delta }(1-\mathbf{\delta })$$

  This means the triad is the optimal structure when the cost of maintaining relationships is very low.

• Vee vs. Triad: Conversely, the vee is more efficient when the cost is higher.

  $$\mathbf{c}>\mathbf{\delta }(1-\mathbf{\delta })$$

The efficient structure, the one that is "best for the group," is not fixed; it depends on the cost-benefit parameters of the relationships.

The Conflict Between Stability and Efficiency

Here is where the tension becomes clear. Let's place our findings for efficiency alongside our findings for stability from the last lesson.

• Vee Stability: A vee is pairwise stable if and only if $\mathbf{\delta }(1-\mathbf{\delta })\le \mathbf{c}\le \mathbf{\delta }$.
• Triad Stability: A triad is stable if no one wants to sever a link. Severing a link turns the triad into a vee. A player's utility changes from $2\delta -2c$ to $\delta +{\delta }^2-c$. They will not sever if $2\delta -2c\ge \delta +{\delta }^2-c$, which simplifies to $\mathbf{c}\le \mathbf{\delta }(1-\mathbf{\delta })$.

Let's analyze three scenarios based on the cost $c$:

Scenario 1: Low Cost ($c<\delta (1-\delta )$)

• Efficiency: The triad is the most efficient structure.
• Stability: The triad is stable, and the vee is unstable (P1 and P2 have a mutual incentive to form a link).
• Outcome: Here, individual incentives align with collective good. The stable outcome is also the efficient one. The vee would naturally evolve into a triad.

Scenario 2: Medium Cost ($\delta (1-\delta )\le c\le \delta$)

• Efficiency: The vee is more efficient than the triad. Assuming the total welfare is positive ($4\delta +2{\delta }^2-4c>0$), the vee is the efficient structure.
• Stability: This is the exact range where the vee is stable.
• Outcome: Again, incentives align. The stable structure is the efficient one.

Scenario 3: High Cost ($c>\delta$)

• Efficiency: Let's assume parameters where the vee is still efficient overall (i.e., $W(g_{vee})>0$). For example, let $\delta =0.8$. The vee is efficient if $c<\delta +{\delta }^2/2=0.8+0.32=1.12$.
• Stability: The vee is unstable because $c>\delta$. The hinge's private incentive is to sever a link, as the cost $c$ outweighs her direct benefit $\delta$.
• Outcome: Here lies the conflict. The group is best off in a vee configuration, but the hinge, acting in her own self-interest, will dissolve it. The network will degrade into a less efficient state (a single dyad or an empty network), even though this makes the group as a whole worse off.

This third scenario perfectly illustrates the tension. It arises because of network externalities. The hinge's decision to maintain her links is based only on her private utility. She doesn't factor in the indirect benefit (${\delta }^2$) that her relationship with P1 creates for P2, and vice-versa. Because she doesn't internalize this positive externality that she provides to the network, she may make a decision that is locally rational for her but globally inefficient for the group.

The MIT lecture notes summarize this fundamental issue well.

Quantifying the Inefficiency: Price of Anarchy

In fields like operations research and computer science, there's a formal way to measure the loss in efficiency due to selfish behavior: the Price of Anarchy (PoA). It's the ratio of the welfare of the worst possible stable outcome to the welfare of the best possible (efficient) outcome.

Let's apply this to our "High Cost" scenario ($\delta <c<\delta +{\delta }^2/2$):

• Efficient Welfare: The optimal structure is the vee, so $W_{eff}=W(g_{vee})=4\delta +2{\delta }^2-4c$.
• Stable Welfare: The only stable network is the empty graph (since all links would be severed), so $W_{stable}=0$.

The Price of Anarchy would be $\frac{W_{stable}}{W_{eff}}=\frac{0}{4\delta +2{\delta }^2-4c}=0$.

A PoA of 0 represents a total failure of the system to achieve efficiency. All potential value is destroyed because individual incentives are not aligned with the group's best interest. This quantifies the tension in a way that should be familiar from your work in optimization and efficiency analysis.

Conclusion

In this lesson, we have moved from stability to efficiency, uncovering a fundamental conflict in network formation.

• Key Takeaways:
  • Efficiency measures the total welfare of a network, often calculated as the sum of all players' utilities. The most efficient network is the one that is best for the group as a whole.
  • The tension between stability and efficiency arises from externalities. A player's decision to form or sever a link may not account for the costs (negative externalities) or benefits (positive externalities) it imposes on others.
  • In a vee, the hinge does not internalize the indirect benefits her relationships create between the non-hinge partners. This can lead to her severing a link even when it makes the overall group worse off, resulting in an inefficient but stable outcome (like an empty network).
  • The Price of Anarchy is a formal metric used to quantify the loss of efficiency caused by this misalignment of individual and group incentives.

Preview of the next lesson:
We've seen how a vee can be unstable, with incentives for players to either add a link (forming a triad) or sever a link (dissolving the structure). In our next lesson, we will begin to model these changes explicitly by looking at how one structure transitions to another in a network formation game.