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

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

Abstract

This paper introduces the Indian Buffet Game (IBG), a game-theoretic framework designed to model multi-resource selection in networks where users face uncertainty and negative network externalities. By integrating non-Bayesian social learning with recursive best-response algorithms, the authors demonstrate how users can converge on optimal resource states while mitigating the performance degradation caused by congestion.

Introduction

In modern distributed systems like wireless communications and cloud computing, users often need to make multiple concurrent decisions under uncertainty. For instance, a mobile device might need to select several frequency bands simultaneously without knowing their exact current capacities. This paper, published in 2013, proposes the Indian Buffet Game (IBG) to address these challenges. It blends machine learning, social learning, and game theory to optimize shared resource allocation.

The Indian Buffet Game Framework

The IBG is inspired by the Indian Buffet Process in non-parametric machine learning. In this game, $N$ customers sequentially choose any number of $M$ available "dishes" (resources). Unlike previous models that limited users to a single choice, the IBG allows for multiple concurrent selections.

The game operates in discrete time slots, each divided into three distinct phases to manage the interaction between decision-making and learning.

The three phases of a time slot in the Indian Buffet Game: Decision Making, Dish Sharing, and Social Learning.
  1. Phase 1: Decision Making: Users choose their dishes based on current beliefs and predicted congestion.
  2. Phase 2: Dish Sharing: Users utilize the chosen resources and experience the resulting utility, which is affected by "negative network externality"—the drop in performance as more users share the same resource.
  3. Phase 3: Social Learning: Users update their beliefs about resource quality by observing others.

Non-Bayesian Social Learning

A core contribution of the paper is a non-Bayesian social learning rule. Pure Bayesian learning in such complex environments is often computationally prohibitive. The proposed rule simplifies this into a two-step process.

The non-Bayesian social learning process, where users update their beliefs $p_j^{(t)}$ by combining local signals and the beliefs of others.

First, a user performs a local Bayesian update based on their direct experience with a dish. Second, they update their belief by taking a linear combination of their own intermediate belief and the beliefs shared by other users in the network. This approach ensures that the system eventually converges to the true state of the resources without the overhead of full Bayesian inference.

Strategic Equilibrium and Results

To find the optimal strategy, the authors developed recursive algorithms to identify the Subgame Perfect Nash Equilibrium (SPNE). This requires users to be "forward-looking," predicting how their current choice will influence the decisions of subsequent users.

Key Findings:

  • The Learning Trap: Simulations revealed that "Pure Learning" (learning quality while ignoring congestion) often performs worst. When everyone identifies the "best" dish and rushes to it, the resulting overcrowding destroys the utility for all.
  • Convergence: The non-Bayesian learning rule was proven to converge to the true resource states, typically within 15 time slots in simulations.
  • Social Welfare: The proposed Best Response algorithm consistently outperformed myopic and random strategies, achieving higher total utility across various signal-to-noise ratios.
  • Threshold Structure: In homogeneous settings, the equilibrium follows a threshold structure: for any given dish quality, there is a specific customer index after which no more rational users will select that dish.

Conclusion

The Indian Buffet Game provides a robust framework for managing shared resources in congested environments. While the current model assumes static resource states and user homogeneity, it lays the groundwork for more complex, dynamic systems. Future work may explore heterogeneous user requirements and more computationally efficient algorithms for larger-scale networks.

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