Kolkata Paise Restaurant Problem

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.