The Kolkata Paise Restaurant Problem and Resource Utilization

Abstract

We study the dynamics of the "Kolkata Paise Restaurant problem". The problem is the following: In each period, N agents have to choose between N restaurants. Agents have a common ranking of the restaurants. Restaurants can only serve one customer. When more than one customer arrives at the same restaurant, one customer is chosen at random and is served; the others do not get the service. We first introduce the one-shot versions of the Kolkata Paise Restaurant problem which we call one-shot KPR games. We then study the dynamics of the Kolkata Paise Restaurant problem (which is a repeated game version of any given one shot KPR game) for large N. For statistical analysis, we explore the long time steady state behavior. In many such models with myopic agents we get under-utilization of resources, that is, we get a lower aggregate payoff compared to the social optimum. We study a number of myopic strategies, focusing on the average occupation fraction of restaurants.

revtex4, 8 pages, 3 figs, accepted in Physica A

Cited by in corpus (29)

• Statistics of the Kolkata Paise Restaurant Problem
• Three-player quantum Kolkata restaurant problem under decoherence
• Cooperation amongst competing agents in minority games
• Zipf's law in city size from a resource utilization model
• Continuous transition of social efficiencies in the stochastic strategy Minority Game
• Phase transitions in crowd dynamics of resource allocation
• Statistical Mechanics of Competitive Resource Allocation using Agent-based Models
• Socio-economic inequalities: a statistical physics perspective
• No-boarding buses: Synchronisation for efficiency
• Development of Econophysics: A biased account and perspective from Kolkata
• Mean Field Equilibria for Competitive Exploration in Resource Sharing Settings
• Emergence of Distributed Coordination in the Kolkata Paise Restaurant Problem with Finite Information
• Parallel Minority Game and it's application in movement optimization during an epidemic
• Phase transition in the Kolkata Paise Restaurant problem
• Optimal coordination of resources: A solution from reinforcement learning
• Strategies in Symmetric Kolkata Restaurant Problem
• Coupled effects of market impact and asymmetric sensitivity in financial markets
• Self-organization in a distributed coordination game through heuristic rules
• Quantum solution to a three player Kolkata restaurant problem using entangled qutrits
• Mean Field Equilibria for Resource Competition in Spatial Settings
• An introduction to multi-player, multi-choice quantum games
• Forager with intermittent rest: Better for survival?
• Achieving Maximum Utilization in Optimal Time for Learning or Convergence in the Kolkata Paise Restaurant Problem
• Achieving perfect coordination amongst agents in the co-action minority game
• The Saga of KPR: Theoretical and Experimental developments
• Does Partial Consumption Help Foraging?
• Centralized and Distributed Age of Information Minimization with non-linear Aging Functions in the Internet of Things
• Econophysics Through Computation
• Spontaneous divergence of disease status in an economic epidemiological game