Indian Buffet Game With Negative Network Externality and Non-Bayesian Social Learning

Chunxiao Jiang, Yan Chen, Yang Gao, K. J. Ray Liu

TL;DR

This paper introduces the "Indian Buffet Game," a novel framework for understanding how rational users make multiple, interdependent choices in a dynamic environment with uncertain system states. It proposes a non-Bayesian social learning algorithm to help users learn these states and designs recursive best-response algorithms to find equilibrium strategies, demonstrating improved performance over simpler decision-making approaches.

What Problem Does This Paper Address?

In many real-world scenarios, users must make multiple decisions simultaneously, and their choices negatively impact each other's utility (e.g., choosing the same Wi-Fi channel). Furthermore, the underlying quality or state of the options (like channel capacity) is often uncertain. Traditional social learning models often assume independent utilities and don't account for this complex interplay of learning, decision-making, and negative externalities. This paper tackles this gap by modeling a situation where users learn about uncertain system states and make multiple, interdependent choices, aiming to maximize their utility while considering the impact on others.

Methods

The core of the paper is the Indian Buffet Game, a new game-theoretic model inspired by the Indian Buffet Process in machine learning. Users (customers) sequentially choose from multiple dishes (options) to maximize their utility. This utility is influenced by the dish's quality (which depends on an unknown state) and the number of other users choosing the same dish (negative externality).

Key methodological contributions include:

  • Non-Bayesian Social Learning: A novel algorithm where users update their beliefs about dish states based on observed signals and the decisions of others. This differs from traditional Bayesian learning by using a simpler, linear update rule.
  • Recursive Best-Response Algorithms: For two scenarios (with and without a budget constraint on the number of dishes), the authors develop algorithms to find the subgame perfect Nash equilibrium. These algorithms recursively predict future decisions to inform current optimal choices.
  • Analysis of Equilibrium Properties: The paper characterizes the Nash equilibrium, showing a "threshold structure" in the homogeneous case without budget constraints and an "equal-sharing property" with budget constraints.

Datasets

Not discussed in the paper. The paper focuses on theoretical modeling and simulation-based evaluation.

Key Insights and Ideas

  • Interdependence is Crucial: The paper highlights that ignoring negative network externalities and focusing solely on individual utility or social learning leads to suboptimal outcomes.
  • Non-Bayesian Learning Suffices: A simpler, non-Bayesian social learning approach can effectively guide users to learn system states and achieve good performance, even without full Bayesian rationality.
  • Budget Constraints Couple Decisions: The introduction of a budget constraint significantly couples the decision-making process for different dishes, making it more complex than the independent dish selection scenario.
  • Early Movers Advantage (and Fairness Issues): In the homogeneous case without budget constraints, customers who decide earlier tend to get higher utilities, leading to potential unfairness. This is addressed by dynamically changing decision orders in simulations.

Key Results

  • Improved Social Welfare: The proposed "Best Response" algorithm, which incorporates both social learning and negative externality considerations, consistently outperforms myopic (no learning), learning-only, and random strategies in terms of social welfare across various signal qualities.
  • Fast Learning Convergence: The non-Bayesian social learning algorithm demonstrates a fast convergence rate, learning the true dish states within approximately 15 time slots in simulations.
  • Equilibrium Characterization: The paper theoretically proves the existence of subgame perfect Nash equilibria and characterizes their properties (threshold structure, equal-sharing) under specific conditions.
  • Budget Constraint Impact: The case with budget constraints shows slower learning convergence compared to the unconstrained case, as users receive fewer signals.

Limitations and Future Work

  • Homogeneous vs. Heterogeneous: While the paper analyzes both homogeneous (identical users/dishes) and heterogeneous settings, the theoretical proofs for equilibrium properties are often stronger for the homogeneous case.
  • Signal Quality Assumption: The learning algorithm's effectiveness is shown to depend on a signal quality parameter (w > 1/5).
  • Future Work: The authors suggest exploring more complex scenarios, such as dynamic dish states, different types of externalities, and extending the framework to other applications. They also mention the potential for further analysis of the learning convergence rate under different conditions.

Summary updated

BibTeX
@article{jiang2015indian,
  author = {Chunxiao Jiang and Yan Chen and Yang Gao and K. J. Ray Liu},
  title = {{Indian Buffet Game With Negative Network Externality and Non-Bayesian Social Learning}},
  journal = {IEEE Trans. Syst. Man Cybern. Syst.},
  year = {2015},
  doi = {10.1109/tsmc.2014.2376880},
}
Figure