Resource Allocation Game on Social Networks: Best Response Dynamics and Convergence

Wei-Chun Lee, Vasilis Livanos, Ruta Mehta, Hari SundaramarXiv 2018 · arXiv

Introduction

In the study of social networks, models for information diffusion or opinion formation often operate under the implicit assumption that agents possess infinite resources to maintain their connections. However, time is a fundamentally inelastic resource. When an individual with a finite time endowment must choose how to distribute their attention across multiple social ties, they engage in a strategic resource allocation game.

This paper introduces a formal model for these interactions, characterized by a "bottleneck" constraint: the actual time spent between two individuals is limited by the participant who proposes the least amount of time. This research explores whether such a system reaches a stable equilibrium and how different behavioral strategies—specifically "pessimism" versus "optimism"—impact the collective welfare of the network.

The Resource Allocation Model

The authors define a game where each player $i$ has a fixed time endowment $\beta_i$ and a set of private preferences $w_{ij}$ for their neighbors $j$. The utility for each player is modeled using a concave function to represent diminishing returns, reflecting the reality that the initial moments of an interaction are typically more valuable than the later ones.

Crucially, the realized interaction $f_{ij}^*$ is defined as: $$f_{ij}^* = \min\{f_{ij}, f_{ji}\}$$ where $f_{ij}$ is the time player $i$ proposes to spend with $j$. This non-differentiable "min" function introduces significant mathematical complexity, as it prevents the game from being categorized as a standard potential game where a single global function can easily track the system's progress toward equilibrium.

Dynamics and Convergence

The core of the analysis focuses on Best-Response (BR) Dynamics, examining two primary update methods:

  1. Sequential Moves: Players take turns updating their proposals one by one.
  2. Simultaneous Moves: All players update their proposals concurrently.

Through rigorous mathematical derivation, the authors prove that while simultaneous moves can lead to infinite loops or "cycling," sequential best-response dynamics always converge to a Nash Equilibrium. To prove this, they developed a novel two-level potential function approach, moving beyond traditional game theory tools to account for the unique constraints of the bottleneck interaction.

Behavioral Strategies: Pessimism vs. Optimism

A key contribution of the paper is the distinction between two behavioral types in the face of resource "slack" (unused time):

  • Pessimistic Players: These agents only propose as much time as their neighbors are currently offering. If a neighbor offers 10 minutes, the pessimistic player will not propose more than 10, even if they have extra time available.
  • Optimistic Players: These agents use their slack to propose more time to neighbors than they are currently receiving, essentially "signaling" availability in hopes that the neighbor might reciprocate in a future update.

Simulation and Results

To test the efficiency of these strategies, the researchers conducted 10,000 simulations on a 10x10 grid (a 4-regular graph) with random edge weights and uniform resource constraints ($\beta = 1000$).

The results highlight a significant advantage for optimistic behavior:

  • Social Welfare: The optimistic strategy reached an equilibrium with a mean quality of 0.908 relative to the global optimum.
  • Pessimistic Lag: The pessimistic strategy achieved a lower mean quality of 0.806.
  • Reliability: The optimistic approach showed lower variance, suggesting it is a more robust strategy for reaching high-quality social outcomes across different network configurations.

Furthermore, the authors analyzed the Price of Stability (PoS) and the Price of Anarchy (PoA). They found that the PoS is 1, meaning the best possible social outcome is always a stable equilibrium. However, the PoA is unbounded, indicating that without proactive (optimistic) behavior, a network can become trapped in highly inefficient, "lazy" equilibria.

Conclusion and Future Directions

The study demonstrates that while resource allocation on networks is complex, sequential adjustments lead to stability. Moreover, "optimism" acts as a catalyst for network efficiency, allowing agents to discover better configurations that a pessimistic approach would overlook.

The authors identify several avenues for future work to address current limitations:

  1. Asymmetric Interactions: Future models could account for digital communications where the time cost is not identical for both parties (e.g., one sender, many readers).
  2. Dynamic Tie Strength: While this model uses static weights ($w_{ij}$), real-world social ties often strengthen through the very act of spending time together.
  3. Simultaneous Convergence: Identifying specific "damping" factors that might allow simultaneous updates to converge remains an open theoretical challenge.

Summary updated

Abstract

The decisions that human beings make to allocate time has significant bearing on economic output and to the sustenance of social networks. The time allocation problem motivates our formal analysis of the resource allocation game, where agents on a social network, who have asymmetric, private interaction preferences, make decisions on how to allocate time, a bounded endowment, over their neighbors. Unlike the well-known opinion formation game on a social network, our game appears not to be a potential game, and the Best-Response dynamics is non-differentiable making the analysis of Best-Response dynamics non-trivial. In our game, we consider two types of player behavior, namely optimistic or pessimistic, based on how they use their time endowment over their neighbors. To analyze Best-Response dynamics, we circumvent the problem of the game not being a potential game, through the lens of a novel two-level potential function approach. We show that the Best-Response dynamics converges point-wise to a Nash Equilibrium when players are all: optimistic; pessimistic; a mix of both types. Finally, we show that the Nash Equilibrium set is non-convex but connected, and Price of Anarchy is unbounded while Price of Stability is one. Extensive simulations over a stylized grid reveals that the distribution of quality of the convergence points is unimodal-we conjecture that presence of unimodality is tied to the connectedness of Nash Equilibrium.
BibTeX
@misc{lee2018resource,
  author = {Wei-Chun Lee and Vasilis Livanos and Ruta Mehta and Hari Sundaram},
  title = {{Resource Allocation Game on Social Networks: Best Response Dynamics and Convergence}},
  year = {2018},
  eprint = {1808.08260},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1808.08260},
}
Figure