9853

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.
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).
  • Contributed by: Asim Ghosh (Saha Institute of Nuclear Physics, Kolkata, India) and Bikas K. Chakrabarti (Saha Institute Nuclear Physics & Indian Statistical Institute, Kolkata, India)

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

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."

PERMANENT CITATION

Contributed by: Asim Ghosh (Saha Institute of Nuclear Physics, Kolkata, India) and Bikas K. Chakrabarti (Saha Institute Nuclear Physics & Indian Statistical Institute, Kolkata, India)
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+