Source-linked AI summary
How Bad is Forming Your Own Opinion?
David Bindel, Jon Kleinberg, Sigal Oren
TL;DR
The paper studies how intrinsic opinions counterbalance network averaging and how network modifications can reduce disagreement at equilibrium. It analyzes equilibrium inefficiency using eigenvalue-based extremal methods and characterizes limits and hardness of edge addition.
Problem
Consensus-focused models omit opinion diversity, motivating the study of equilibrium disagreement and how network changes can reduce its social cost.
Method
The paper models repeated averaging as best-response dynamics, analyzes quadratic-form extremal problems through graph Laplacian eigenvalues, and studies constrained edge-addition problems.
Results
For undirected graphs, the price of anarchy is at most 9/8; adding edges can improve equilibrium cost, while selecting the best k arbitrary edges is NP-hard.
Takeaways & Limitations
Equilibrium disagreement can be bounded structurally, and network design can reduce equilibrium cost even though added edges cannot improve the optimal social cost.
Takeaways & Limitations
With directed graphs, arbitrary node weights are excluded because even two-node examples can make the price of anarchy unbounded.
Abstract
from arXiv · showhide
The question of how people form their opinion has fascinated economists and sociologists for quite some time. In many of the models, a group of people in a social network, each holding a numerical opinion, arrive at a shared opinion through repeated averaging with their neighbors in the network. Motivated by the observation that consensus is rarely reached in real opinion dynamics, we study a related sociological model in which individuals' intrinsic beliefs counterbalance the averaging process and yield a diversity of opinions. By interpreting the repeated averaging as best-response dynamics in an underlying game with natural payoffs, and the limit of the process as an equilibrium, we are able to study the cost of disagreement in these models relative to a social optimum. We provide a tight bound on the cost at equilibrium relative to the optimum; our analysis draws a connection between these agreement models and extremal problems that lead to generalized eigenvalues. We also consider a natural network design problem in this setting: which links can we add to the underlying network to reduce the cost of disagreement at equilibrium?
1 Introduction
The paper models persistent internal beliefs within social averaging, quantifies equilibrium disagreement against the social optimum, and studies how network directionality and added edges affect that cost.
- 1 Introduction: Consensus models overlook persistent disagreement, motivating a framework that quantifies the social cost of nonconsensus.The paper seeks both reasons why consensus fails and a way to measure the resulting disagreement cost.
- 1 Introduction: Persistent internal opinions s_i prevent averaging from generally producing consensus, separating intrinsic beliefs from expressed opinions.Overall opinions represent compromises between persistent internal values and neighbors’ expressed opinions.
- 1 Introduction: Repeated averaging is interpreted as best-response dynamics in a game whose unique Nash equilibrium can differ from the social optimum.The social optimum minimizes the sum of players’ quadratic costs, while individual optimization creates externalities for neighbors.
- Our Results: Undirected Graphs: 9/8 is a tight upper bound on the price of anarchy for undirected graphs, derived through quadratic-form extremal analysis and Laplacian eigenvalues.The same bound extends to heterogeneous internal-opinion coefficients and settings with fixed nodes.
- Our Results: Directed Graphs: Directed graphs permit much larger inefficiency: generalized eigenvalue methods compute the maximum price of anarchy, while some instances have polynomial-in-n lower bounds.Eulerian directed graphs admit bounds of Δ + 1, or O(Δ^2α^-2) for Eulerian asymmetric graphs with edge expansion α.
2 Undirected Graphs
The undirected opinion game has a unique Nash equilibrium and a social optimum, with disagreement measured by their cost ratio. Spectral analysis yields a tight universal price-of-anarchy bound of 9/8, preserved under several model extensions.
- For undirected graphs, the social cost is represented using the weighted Laplacian, and the optimum and equilibrium solve linear systems involving A + I and 1/2A + I.The matrix A = 2L captures disagreement tension on edges.
- The Nash equilibrium is unique, while the social optimum minimizes total player cost; their cost ratio defines the price of anarchy.
- 9/8 is the tight upper bound on the price of anarchy for every graph and internal-opinion vector.The proof relates the ratio to Laplacian eigenvalues and generalized eigenvalue analysis.
- The proof uses simultaneous diagonalization of A, B, and C, reducing the price-of-anarchy ratio to functions of their shared eigenvalues.
- The bound is attained when the relevant matrix has eigenvalue 2, equivalently when the Laplacian has eigenvalue 1, with internal opinions aligned to its eigenvectors.Linear combinations of eigenvectors for eigenvalues 0 and 1 can achieve the maximum.
- 2.1 Arbitrary Node Weights and Players with Fixed Opinions: The 9/8 bound extends to strictly positive node weights and to models containing players with zero internal-opinion weight or fixed-opinion nodes.The fixed-opinion model is reduced to a weighted opinion game, with costs differing by a positive constant.
3 Directed Graphs
Directed graphs can have unbounded price of anarchy even at bounded degree, but spectral and generalized-eigenvalue methods identify worst internal opinions and yield bounds for important graph classes.
- Bounded-degree examples: Θ(n^c) price of anarchy is achievable on bounded-degree trees, showing unbounded disagreement is not caused solely by large in-degree.The exponent c ≤ 1 depends on node in-degrees.
- Bounded-degree examples: For a 2^k-ary directed tree, equilibrium opinions at layer i equal 2^-i, while the optimal social cost is at most 1.The construction directs every edge toward the root, whose internal opinion is 1 while all others are 0.
- Bounded-degree examples: The tree construction gives Θ(log n) PoA for k = 2, Θ(n) for k = log n, and Θ(n^c) for intermediate k.For k = 3, the result is also polynomial in n.
- Model restriction: Arbitrary node weights can make directed-graph PoA unbounded even on a two-node graph, so the analysis restricts attention to uniform node weights.In the example, equilibrium cost is 1/2 while optimal cost is smaller than ε.
- Spectral framework: For a directed graph, PoA is expressed as the generalized Rayleigh quotient sT Cs / sT Bs, but directed B and C lack the simple shared relation present in undirected graphs.This prevents easy arbitrary-graph bounds, while generalized eigenvalue algorithms still find the maximizing internal-opinion vector in polynomial time up to precision ε.
4 Adding Edges to the Graph
The paper studies how adding network edges can reduce equilibrium disagreement, establishing general improvement bounds, hardness results for constrained additions, and polynomial-time methods for selected weighted-edge choices.
- The equilibrium cost can improve by at most the original graph’s price of anarchy when edges are added.
- Adding edges from a specific node: Adding edges from a specific node w is NP-hard to optimize, via a reduction from subset sum.
- Adding edges to a specific node: Adding edges to a specific node w is also NP-hard when the objective is selecting the best people to expose to a media source, via minimum vertex cover.
- Adding an arbitrary set of edges: Finding the best set of arbitrary k edges is NP-hard through a reduction from the k-dense-subgraph problem.
- A 4-approximation is given for optimally adding edges to a directed graph by adding reverse copies of missing edges, while weighted graphs admit ratio 2.
- The optimal weight for a single added edge can be computed in polynomial time, and local edge additions can reduce equilibrium cost when influence aligns with the residual vector.