1. Achieving maximum utilization in optimal time for learning or convergence in the Kolkata Paise Restaurant problem.
- Author
-
Biswas, Aniruddha, Sinha, Antika, and Chakrabarti, Bikas K.
- Abstract
In the original version of the Kolkata Paise Restaurant (KPR) problem, where each of the N agents (or players) chooses independently every day (updating their strategy based on past experience of failures) among the N restaurants, where he/she will be alone or lucky enough to be picked up randomly from the crowd who arrived at that restaurant that day, to get the only food plate served there. The objective of the agents is to learn themselves in the minimum (learning) time to have maximum success or utilization probability (f). A dictator can easily solve the problem with f = 1 in no time, by asking every one to form a queue and go to the respective restaurant, resulting in no fluctuation and full utilization from the first day (convergence time τ = 0 ). It has already been shown that if each agent chooses randomly the restaurants, f = 1 - e - 1 ≃ 0.63 (where e ≃ 2.718 denotes the Euler number) in zero time ( τ = 0 ). With the only available information about yesterday's crowd size in the restaurant visited by the agent (as assumed for the rest of the strategies studied here), the crowd avoiding (CA) strategies can give higher values of f but also of τ . Several numerical studies of modified learning strategies actually indicated increased value of f = 1 - α for α → 0 , with τ ∼ 1 / α . We show here using Monte Carlo technique that a modified Greedy Crowd Avoiding (GCA) Strategy can assure full utilization ( f = 1 ) in convergence time τ ≃ e N , with of course non-zero probability for an even larger convergence time. All these observations suggest that the strategies with single step memory of the individuals can never collectively achieve full utilization ( f = 1 ) in finite convergence time and perhaps the maximum possible utilization that can be achieved is about eighty percent ( f ≃ 0.80 ) in an optimal time τ of order ten, even when N the number of customers or of the restaurants goes to infinity. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF