The Kolkata Paise Restaurant Problem (KPR Problem) is a mathematical game for competitive resource allocation without any coordination. Its name is drawn from the once-common "Paise Restaurants" in the Indian city named Kolkata. These were affordable eateries from the early 1900s to the 1970s that offered fixed-price meals at extremely low costs (see for references to the few that still exist today; Paise is the smallest denomination of the Indian Rupee). The KPR problem is an anti-coordination game that models how a large number of individuals (players) compete for limited resources without direct communication or coordination.
The problem becomes trivial—yet optimally efficient—if a non-playing coordinator or Dictator intervenes. By simply instructing all players to form a queue and visit the restaurant matching their position in the line on the first day, and then rotate to the next restaurant each subsequent day (following periodic boundary conditions), full resource utilization is achieved immediately. This ensures food for all customers, maximum revenue for all restaurants, and requires no learning or convergence time.
However, the true complexity of the problem arises when individuals act independently, each making decisions based on personal experiences of past success or failure, or available information about previous crowd sizes at the restaurants. In this decentralized setting, players aim to maximize their own payoff, which incidentally also drives optimal utilization and revenue at the system level—but only through emergent, self-organized behavior.
The KPR model generalizes the El Farol Bar problem (see for the initial formulation), extending it from binary choice (go or stay home) to multiple options. For foundational work on KPR, see and for some early reviews see. When reduced to two players, the game aligns with classic anti-coordination models like the Chicken Game or Hawk–Dove Game. Tamir argued, following Anderson's "More is different", that this extension to large number of choices for all the players make KPR game much more complex and appropriate for decentralized optimization problems, than the finite option/choice games. For a study on the emergence of distributed coordination in the KPR problem with finite information, see. Algorithmically, KPR shares traits with the Gale–Shapley algorithm in decentralized matching contexts. Broader connections to the "Kolkata Game" or "Kolkata Algorithm" appear in studies such as Refs.
Problem Definition
There are N restaurants and λN players (prospective customers); typically λ=1. N can be arbitrarily large. Each day, customers independently choose a restaurant based on their past experience of success or failure. Players do not know each other's choices but have access to historical data of past selections. At each restaurant, only one of the players (prospective customers) arriving there is randomly chosen and served (payoff = 1). The rest of those arriving at that restaurant leave without food for that day (payoff = 0; no time/money left for another search). The ideal outcome is perfect coordination (like that achieved in the presence of a dictator), where each player picks a different restaurant in zero or short convergence time. However, this becomes difficult (in the absence of parallel communication exchanges or of a dictator) in the KPR game. This leads to inefficiencies (some restaurants can serve one from the crowd, others are empty) or partial utilization. The KPR objective is to evolve the collective 'parallel learning' algorithms for maximizing the utilization fraction in minimum (preferably less than lnN order) time.
Strategies & Optimization
In KPR problem, strategies are evaluated on the basis of their aggregate payoff or the utilization fraction. For , this is given by the average fraction of attended restaurants or by the average fraction of agents getting food on any day.
In the random choice case of the KPR problem, each of the agents randomly selects one of the restaurants. The probability that exactly agents choose the same restaurant is: ,
giving a Poisson distribution in the limit :
The fraction of restaurants not chosen by any agent is then , giving the utilization fraction equal to . This becomes equal to for , meaning about 63% of restaurants are utilized or about 63% agents get food on any day in this case. The convergence time is zero.
For the random choice case discussed above, the agents do not have any memory, nor do they employ any learning strategy. A minimal learning stochastic strategy, with utilization fraction ~0.79, gives each customer a probability of choosing the same restaurant as yesterday's one varying inversely with the crowd size there (number of players who chose that restaurant) yesterday, while choosing among the other restaurants with uniform probability. This is a better result than the above-mentioned simple random choice (or noise trader) case, though the convergence time seems to grow very weakly, perhaps logarithmically or even more weakly, with (see also).
Increased utilization fraction for customers, each having a fixed low budget allowance for local search using Traveling Salesman Problem (TSP) type algorithm, has also been studied by Kastampolidou, Papalitsas and Andronikos. Employing a locally clustered structure (of size determined by the amount of the little travel budget allowed for each of the agents here) of the restaurant distribution (which is of course globally uniformly over the entire city), each agent can visit multiple restaurants to search optimally for a vacant one and get food there. This approach is effectively equivalent to salesmen each solving a local TSP to complete visiting cities. Of course, some agents will still fail to get a vacant restaurant within his/her local neighborhood, allowed by the little budget, and full utilization will not be possible for any finite budget allowed. This approach helps derive a probabilistic formula, leading to increased utilization fraction, confirming its clear advantage.
Strategies without an external dictator (such as caste and turn-taking strategies) are available to achieve full utilization of resources if objective orderings of players and resources are available to all players. In some cases, a social norm (e.g., alphabetical sort) could provide that ordering; in others, history of play would eventually provide it (e.g., sorting resources by popularity and sorting players by winnings, skill-estimate, or debt-ranking).
Extensions of KPR for on-call car hire problems (restaurants effectively having also the options for moving to their chosen locations) have been explored in by Martin et al. and see for the mean field solution of a generalized KPR problem in the same resource competition in spatial settings of the vehicle-for-hire market. For a detailed analysis and review on strategic driver relocations for higher efficiencies of ride-hailing platforms in KPR-like context, see.
For application of KPR to optimized job allocation problems in Internet-of-Things, see by Park and Saad. Stability of the KPR, induced by the introduction of dining clubs have also been studied. One can see for a study on the impact of expert opinions (or even of faiths) on such evolving mutually competing search strategies for the resources.
See also for application of KPR model to anthropological and sociological analysis of the models of polytheism, and for an algorithmic application to cancer therapy, see.
Extensions to quantum games for three player KPR have been studied, where, dimensionality permitted, each player can achieve much higher mean payoff. For some recent studies in the context of three player KPR Game on the advantages of higher payoffs in quantum games when the initial state is maximally entangled, see. See for a general introduction to econophysics, sociophysics, classical KPR, quantum games and quantum KPR, and see for a later review on classical and quantum KPR games.
One may see for an early attempt to exploit KPR type strategies for developing Artificial Intelligence or AI models. For a study of KPR-like approaches related to graph partitioning problem, see. Recently the KPR game has been extended (to Musical Chair type games) and that has been exploited for creating a new benchmark for evaluating the AI algorithms.
Tournaments The KPR Problem can be studied via tournaments to establish its grandmaster strategy, much as the Prisoner's dilemma was studied to discover/establish Tit for tat, Generous tit for tat, and zero-determinant strategies (etc). The open-source MAD Chairs software creates an otree server as standard for human subjects experiments, but allows tournaments also to include AI and hardcoded strategies for the KPR Problem (and for the MAD Chairs game, which differs from KPR in that overcrowded restaurants, like lifeboats, produce no wins).
No strategy performed well against all others in Axelrod's Prisoner's Dilemma tournaments, so Axelrod ranked them on total winnings, but the grandmaster strategy for the KPR tournament rankings shown above is more clear: The turntaking strategy achieves both high outcomes and also edge over each other individual strategy (or over caste which has edge over other strategies) when the compared strategies have equal populations, where "edge" refers to the average lowest outcome minus the average lowest outcome of the compared strategy. In other words, no coalition competing against turntaking would be sustainable because it would include a member who should rationally expect to improve their outcomes by defecting to turntaking. Assuming that each alien society would reach the same conclusion by running its own tournaments, turntaking is a universal basis for coordination. It sorts restaurants by popularity and patrons by debt of favors owed to each other, and any player can independently calculate these from history of play (the grandmaster strategy does employ coordination to break ties, but realistic situations have rich histories that make ties rare).
Applications The KPR model can describe various real-life resource allocation problems, such as:
Ride-hailing services: Ridesharing company passengers and the taxi drivers compete for on-call-hire Taxis, sometimes overwhelming some areas while others remain unpopulated, unless properly matched dynamically (based on anticipated crowd distribution or past crowd size records) by the on-call service managers. Online resource access: Users competing for limited computing resources (e.g., booking slots, Bandwidth allocation, etc.). Here the Computer management needs appropriate job allocation dynamically, anticipating/extrapolating from the sizes of the incoming jobs and of the Queues, in the context of Internet of Things. Dining Clubs in KPR: Where the clubs can proxy (anticipating the choices) on behalf of the players, who are not willing to take the risk of overcrowded restaurant choice and consequent failure to get the food. AI benchmarking: Algorithms optimizing decentralized resource utilization generated employing KPR-inspired strategies.
Quantum Games and Quantum Strategies
We start with a simple example of a quantum game demonstrating the use of quantum entanglement in the definition of the game strategy. The setup was introduced by Cluse, Horn, Shimony and Holt in the context of the hidden variable theory, and later became a prototype example in quantum game theory. The 'game' was also used as a test for quantumness in the context of quantum computers.