Kolkata Paise Restaurant (KPR) Problem
The KPR problem is a repeated game, played between a large number of agents having no interaction among themselves. In KPR, prospective customers (the agents) choose from restaurants each evening (time ) in parallel decision mode. Each restaurant has the same price for a meal but a different rank (agreed upon by all the customers) and can serve only one customer. If more than one customer arrives at any restaurant on any evening, one of them is randomly chosen and is served and the rest do not get dinner that evening. Information regarding the customer distributions for earlier evenings is available to everyone. Each evening, each customer chooses a restaurant independent of the others. Each customer wants to go to the restaurant with the highest possible rank while avoiding a crowd so as to be able to get dinner there.[more]
In Kolkata, there were very cheap and fixed rate "Paise Restaurants" (also called "Paise Hotels'') that were popular among the daily laborers in the city. During lunch hours, the laborers used to walk (to save the transport costs) to one of these restaurants and would miss lunch if they got to a restaurant where there were too many customers. Walking down to the next restaurant would mean failing to report back to work on time! Paise is the smallest Indian coin and there were indeed some well-known rankings of these restaurants, as some of them would offer tastier items compared to the others.
The KPR problem seems to have a trivial solution: suppose that somebody assigns a restaurant to each person and rotates them on successive evenings—the fairest way; call that the dictated solution. This, however, is NOT a true solution of the KPR problem, where each agent decides on his own every evening, based on complete information about past events. In KPR, the customers try to evolve a learning strategy to eventually get to something like the dictated solution.
Let the strategy chosen by each customer in the KPR game be such that, at any time , the probability of arriving at the ranked restaurant is given by
where denotes the number of customers arriving at the ranked restaurant on the evening and , denote two parameters.
Let be the utilization fraction, which is the percentage of people getting food on any evening. In this Demonstration, the histogram gives the distribution of against the fraction itself for different values of the parameters and in the expression for for , the number of agents and of restaurants, when the data is averaged over 2000 time steps or evenings. You can change the strategy for probabilistic choices of differently ranked restaurants by changing the values of the parameters and . For example, the random choice of restaurants by the customers (independent of rank) corresponds to and .
On a collective level, we look for the fraction of customers getting dinner in any evening and also its distribution for various strategies of the game. The distribution will be Gaussian with most probable utility fraction . We get for , (pure random choice); for , (strict rank-dependent choice); and for , (avoiding-past-crowd choice).[less]
Contributed by: Asim Ghosh (Saha Institute of Nuclear Physics, Kolkata, India) and Bikas K. Chakrabarti (Saha Institute Nuclear Physics & Indian Statistical Institute, Kolkata, India) (March 2011)
Open content licensed under CC BY-NC-SA
For more information, see:
A. S. Chakrabarti, B. K. Chakrabarti, A. Chatterjee, and M. Mitra, "The Kolkata Paise Restaurant Problem and Resource Utilization," Physica A 388, 2009 pp. 2420–2426.
A. Ghosh, A. S. Chakrabarti, and B. K. Chakrabarti, "Kolkata Paise Restaurant Problem in Some Uniform Learning Strategy Limits."