Kolkata Paise Restaurant Problem: Difference between revisions

The Kolkata Paise Restaurant Problem (KPR) draws its name from the once-common "paise restaurants" in Kolkata—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 was 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 El Farol Bar problem corresponds to only two choices for each individual (to go to the bar or remain at home to avoid the over-crowded bar). The KPR game is therefore an extension of the El Farol Bar problem with many choices for each individual. For an overview of the early developments in the KPR model, see. When restricted to just two players, the KPR game shares structural similarities with classic anti-coordination games such as the Chicken Game or the Hawk-Dove Game. Moreover, the algorithmic elements of the KPR model—particularly in how agents make decentralized matching decisions—bear resemblance to the Gale-Shapley algorithm. For further comparisons and studies related to the "Kolkata Game" or "Kolkata Algorithm," see.

Background

The theory of KPR is rooted in the history of the social sciences and in particular computational sociology and Econophysics.

The theory of social science was first introduced by Auguste Comte in 1853 . Based on positivistic philosophy Comte's main goal was to describe human behavior using scientific tools. He wanted to reproduce the success of the hard sciences of his time. Accordingly, he coined his theory "Social Physics". Comte described a hierarchy of the sciences from mathematics and physics at the bottom through chemistry biology and Social Physics at the top.

In its beginning social physics research was mainly established on the ground of Probability theory and early notions of Statistics, developed during the 17 and 18 centuries.  The first notions of probability theory came as early as the 17^th century with the work of Pascal and de Fermat, in their 1654 correspondence on the problem of points . Later in 1657 Huygens wrote what is known as the first book on probability theory . The Normal distribution was introduced by de-Moivre in 1733 . In 1763 Bayes introduced the Bayes Theorem. Gauss (1809) introduced the use of normal distributions in error estimation and the least square estimator, thereby introducing the foundations of statistical inference.  Laplace (1812) generalized the work of de-Moivre introducing the Central Limit Theorem, he also re-discovered and developed the Bayesian inference systematically.  Legendre (1905) re-discovered the method of least squares.  In 1933 Kolmogorov formulated the notion of probability theory as we use it today, with random variables, measurable functions, sampling, etc.

Statistics soon became not just a theory used to collect data but as a way of thinking . As early as 1662 Graunt investigated birth and death rates in London to draw conclusions on life expectations and urban mortality, Petty coined the notion of "political arithmetic".  Later in 1842 Quetele introduced the notion of the "average man" (l'homme moyen). F.Galton in 1869 used correlation and regression to study human traits and to define biometrics.

During the 20^th century the major bulk of social scientists used what are now called quantitative methods, these were simple statistical methods including questionnaires, correlations, regressions, Bayesian decision theory etc.  In 1921 Wright introduced the Path analysis, a graphical model where the nodes are social variables and the edges’ weights are the correlations between the variables. Its goal was to suggest possible causations between correlated variables.

Over the years, the Social Sciences moved apart from the hard-core sciences, the term "social Physics" was hardly used. Toward the end of the 20^th century, new methods known as qualitative methods were introduced. These included interviews, ethnographic observations, narrative analysis, grounded theory and more. By 1990, economists were conducting experiments with what would later be called "KPR" via games to simulate coordination in decentralized markets.

The emergence of computers brought new research tools. In the midst of the 20^th century von-Neumann and Morgenstein were investigating game theory and economic behavior. In 1967 Swanson discussed social change, political instability, revolution and culture structure, his theory, although non-computational highly influenced the later computational sociology theory. Coleman was investigating the micro-macro social relations. These were the first steps towards a simulation-based theory, later to become the Agent Based Modelling. In 1957 Orcutt suggested simulating society as an ensemble of units having attributes as income and age, simulating their transitions and hence a socio-economic system. In 1971 Schelling introduces his famous segregation model. Schelling’s work stressed the fact that simulations could ‘explain’ phenomena that the quantitative methods could not.

Agent Based Modeling introduces the use of ‘emergent properties’ into the social sciences, where local interactions between neighboring agents yield some global emergent property.  "More is different" was the name Anderson gave the phenomenon. Anderson also discussed the question whether the emergent phenomenon should be considered as a new physical law and when do we need it. Best examples of emergent properties are the behavior of swarm of social insects like bees and swaps, or flocks of birds and fish, but humans are also social animals. Theories like epidemiology can be easily simulated by ABM, likewise trends in economy, traffic in urban design, flow of information, dispersion of viruses etc. The way social animals or social agents solve problem by emergent behavior is also known today as "swarm intelligence"

The theory of computational sociology is a step forward in the direction of Comte's original idea. Computational sociology is a subfield of sociology that uses computational methods—such as simulations, algorithms, network analysis, and data mining—to model, understand, and analyze social phenomena . Computational sociology is a step towards putting Social Sciences back on the ground of hard-core sciences. The theory was boosted mainly by simulation methods such as Agent-Base Modeling, Spin Lattice (Ising, Pots, Random Fields Ising) Models etc.

The theory of Econophysics takes computational sociology a step forward. It introduces notions from physics (mainly statistical mechanics, condensed matter physics) into the social theory, such as phase transition, condensation, etc. A crowd of people could be in different phases, it could have well organized form, it could be clustered or organized in trails, or it could be random, we could fine-tune the parameters that change its behavior from one phase into the other. We could also investigate the type (rate) of phase change, is it continuous or is it sharp, very similar to what we can do in thermodynamics and statistical mechanics. Similarly, the clustering of a group of people could be sometime described by a Bose-Einstein condensation, where a preferential choice is made when one decides to which subgroup to join.  Inserting such terms into the social context is like introducing a new language that could easily formulate our insights and perhaps predict and explain new phenomena.

The term "Econophysics" was first introduced by Stanley in 1995 at a conference in Kolkata (Proc. in 1996 ). Stanley and Mantegna discussed fluctuation of financial indices, and showed that the shape of the distributing of returns showed a self-similarity property . Moreover, the distribution had a large tail and was similar to a truncated Levi distribution. Clearly this resembles the behavior of well-known physical systems near criticality.  Since then, a plethora of research Econophysics papers appeared, to mention some, Plerou discussed cross correlations in financial time series, Bouchaud, Mézard and Potters discussed stock order books, Dragulescu-Yakovenko and Chakraborti-Chakrabarti discussed statistical mechanics of income and wealth distributions (see Wikipedia entry on kinetic exchange models of markets), Cont and Bouchaud discussed herd behavior.

The KPR game is a prototype example by which we can demonstrate Econophysics principles. One can manipulate the parameters of the game to introduce new emergent behaviors. One also can force local relationships between the agents and investigate the change in the overall emergent properties.

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.
• At each restaurant only one of the players arriving there (prospective customers) is randomly chosen and served (payoff = 1). The rest leave without food for that day (payoff = 0; no time/money left for another search).
• Players do not know each other's choices but have access to historical data of past selections.
• The ideal outcome is perfect coordination, where each player chooses and picks a different restaurant in short convergence time. However this becomes difficult (in absence parallel communication exchanges) in KPR game. This leads to inefficiencies (some restaurants overcrowded, others 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.

Applications

The KPR model can describe various real-life resource allocation problems, such as:

• Hospital resource distribution: Patients prefer top-rated hospitals, even if local hospitals have available beds. Overcrowding in top hospitals leaves some patients unattended, while other hospitals remain underutilized.

• Ride-hailing services: Passengers compete for taxis, sometimes overwhelming some areas while others remain unpopulated.
• Online resource access: Users competing for limited online resources (e.g., booking slots, bandwidth allocation, computer job allocation problem in Internet of Things computer.).
• Dynamics of Dining Clubs in the KPR Problem.
• AI benchmarking: Algorithms optimizing decentralized resource use are evaluated using KPR-inspired problems.

It has been pointed-out that the anti-coordination game has broad real-world applications, and that the use of lotteries to resolve conflicts over specific resources would turn any anti-coordination game (or MAD Chairs game) into KPR. For example, if contests for positions of authority were settled via lottery, instead of via election, then the game to win such positions would become KPR. However, lottery enforcement might not be sustainable in some real-world situations (thus revealing Coordination or MAD Chairs as the underlying model). For example, if contests for jobs were settled randomly, then the unemployed might retaliate with political pressure to regulate employment. This dynamic also appears in the board game "Eketorp".

Strategies & Optimization

In KPR problem, strategies are evaluated on the basis of their aggregate payoff or the utilization fraction. For $\lambda =1$, 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 $\lambda N$ agents randomly selects one of the $N$ restaurants. The probability $P(n)$ that exactly $n$ agents choose the same restaurant is:

$P(n)={\binom {\lambda N}{n}}p^{n}(1-p)^{\lambda N-n};\quad p={\frac {1}{N}}$,

giving a Poisson distribution in the limit $N\to \infty$:

$P(n)={\frac {\lambda ^{n}}{n!}}\exp(-\lambda ).$

The fraction of restaurants not chosen by any agent is then $P(n=0)=\exp(-\lambda )$, giving the utilization fraction equal to $1-\exp(-\lambda )$. This becomes equal to $1-\exp(-1)\approx 0.63$ for $\lambda =1$, 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 or they do not 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) there 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 $N$.

Increased utilization fraction for customers, each having a fixed low budget allowance for local search using Traveling Salesman Problem (TSP) type algorithm, have also been studied. 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 $N$ salesmen each solving a local TSP to complete visiting $N$ 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 deriving 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 places) have been explored in 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 application of KPR to optimized job allocation problems in Internet-of-Things, see. Stability of the KPR, induced by the introduction of dining clubs have also 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.

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 .

Consider a game where Alice and Bob are asked a yes-no question, there are 4 possible pairs of questions (C,C), (C,D), (D,C) or (D,D), and these are chosen randomly. In the (C,C) question they get a reward 1 for uncorrelated answer (1,0) or (0,1) and in the other cases they get a reward 1 for correlated answers (1,1) or (0,0). The game is repeated. Alice and Bob are not allowed to communicate during the game, however they can decide in advance on a strategy. They could agree to always answer (1,1) and such a strategy will yield a 75% success. Alternatively, they can each toss a coin, and it is easy to show that such a strategy will yield a 50% success.  Suppose now they share a maximally entangled two qubit state:

$\rho ={\frac {1}{\sqrt {2}}}\left(|00\rangle +|11\rangle \right)$.

Define the locally unitary operator:

$U(\theta )=\left({\begin{matrix}\cos \theta &\sin \theta \\-\sin \theta &\cos \theta \end{matrix}}\right)$

Alice and Bob can apply such unitary operators on $\rho$ and then measure their entangled state in the $|0\rangle ,|1\rangle$ basis. Alice uses $U_{C}=U(-\theta )$ , $U_{D}=U(\theta )$, Bob uses $V_{C}=U(2\theta ),V_{D}=U(0)$. It is easy to show that for $\theta =\pi /8$ Alice and Bob will win at 85% of the cases. The unitary operators on the entangled state produce un-correlated pair of "coins" for the (C,C) questions, and correlated pair of "coins" for the other questions.

Therefore, using entangled state, unitary operators, and quantum measurement can improve the success of such games.

We can use the above example to define a quantum strategy of a game. The players are sharing an entangled state, and they are allowed to use local unitary operators. Following the local operations, a quantum measurement of the state will yield a probability distribution of the payoffs defined by the game. The entanglement is the "strategic" part of quantum strategy, and the local unitary operators are the "tactical" part of the quantum strategy .

Quantum strategies could change the Nash equilibria landscape, it could erase classical Nash equilibrium strategies, and build new quantum Nash equilibrium strategies, moreover, one can get quantum Nash equilibria with possible different payoffs than the classical ones.

For example, in Eisert's quantum Prisoner dilemma , the old Nash equilibrium is no longer valid, there exists a new Nash equilibrium strategy, in the form of two identical local unitary matrices. Moreover, in the new Nash equilibrium both players have better payoff than in the classical case, the payoff equals the classical payoff for mutual cooperation and therefore the players escape the dilemma.

In the above setup of Eisert's quantum Prisoner dilemma there is the possibility of "stirring", where one player can undo the other players actions, by playing a strategy that "commutes through" J - the entangling operator. This looks like the player is operating on the space before it was entangled, destroying the temporal order of the game (entangle --> strategy --> unentangled --> measure). However, if we restrict the local unitary operations (such as using a subset of SU(2)-matrices) we can prevent stirring..

In general, player A's local operations can always affect the joint state and hence the reduced density matrix for B may change. Clearly, if we allow non-local operations then stirring is possible.

A mixed quantum strategy (defined as in the similar classical case) is a strategy where each of the player has a probability distribution over local unitary operations which are applied to a density matrix that is shared among the players. The mixed quantum state should not be separable, otherwise the whole game resembles a classical one. In general, a mixed quantum strategy will yield Nash equilibria.

Flitney and Abbott introduced a quantum version of the Monty – Hall game. There it was shown that introducing quantum strategy erases the classical Nash equilibrium, and mixed quantum strategy over maximally entangled states brings back the classical Nash equilibrium.

In a repeated game, introducing quantum strategies could have effect on the stability of the classical Nash equilibrium, in the Evolutionary Stability Strategy sense . A stable Nash equilibrium could turn into a non-stable one by an invasion of ‘quantum mutants’, and visa-versa, an evolutionary unstable Nash equilibrium could become stable under quantum ‘mutations’ .

In a repeated CHSH game Reichardt, Unger and Vazirani showed that the above quantum strategy is robust; if Alice and Bob play the CHSH game many times and if they win in a about 85 percent of the times, then we can conclude that they are using a close form of the above quantum strategy. Moreover, the above quantum strategy is generating: if Alice and Bob are using strategies which could depend on the success of previous games, and if they win in about 85 percent of the times, then we can conclude that there are enough independent games played with the above quantum strategy.

Quantum Minority and KPR Games:

KPR is a minority game, and for minority games we can use quantum theory to improve the success probability. The secret lies in writing the conditions to win in an entanglement.

For example, suppose there are 4 players and 2 roads A and B to go to work. We let the players use the following entanglement:

${\frac {1}{\sqrt {8}}}\left(|0001\rangle +|0010\rangle +|0100\rangle +|1000\rangle -|1110\rangle -|1101\rangle -|1011\rangle -|0111\rangle \right)$

The players will measure the state in the $|0\rangle ,|1\rangle$ basis and interpret them as using roads A or B. In two cases out of 8 the first player will be in a minority, the same is true for the other players. Classically each player will win with probability 1/8. Therefore, writing the rules of the game into an entanglement improve the probability of winning.

Similarly, Sharif and Heydari used a qutrit to formulate the entanglement in a 3 player 3 roads game; see also . Sharif and Heydari also generalized their results to multi-player multi-choice quantum games

The problem will arise in the complexity of building the entanglement or scaling it to a KPR game. Also, the quantum minority game implicitly assumes all players cooperate in using the measurement, this will become hard to get when the group becomes large.

Dining Clubs and Evolutionary Cooperation

Harlalka, Belmonte and Griffin and Harlalka and Griffin introduced the concept of dining clubs into the KPR problem. A dining club consists of agents who agree to manage their restaurant choice centrally, but who have no control or interaction with individuals outside the dining club. Thus, no two club members can possibly collide with one another, but may collide with non-club members. When one club is available and $g$ agents are part of it while $n$ agents are non-club (or free) members, we have $N=n+g$ total agents and the probability that a club member eats is,

$p_{g}(n,g)=\sum _{k=0}^{n}{\binom {n}{k}}\left({\frac {n+g-1}{n+g}}\right)^{n-k}\left({\frac {1}{n+g}}\right)^{k}{\frac {1}{k+1}}$,

while the probability a non-club member eats is,

$p_{n}(n,g)=\sum _{k=0}^{n-1}{\binom {n-1}{k}}\left({\frac {n}{n+g}}{\frac {1}{k+1}}+{\frac {g}{n+g}}{\frac {1}{k+2}}\right)\left({\frac {n+g-1}{n+g}}\right)^{n-k-1}\left({\frac {1}{n+g}}\right)^{k}$.

Letting $g=\alpha n$ and assuming $n\to \infty$, that is assuming an infinitely large agent population yields asymptotic probabilities,

$p_{g}(\alpha )=\left(1-e^{-{\frac {1}{\alpha +1}}}\right)(\alpha +1)$ and $p_{n}(\alpha )=-\alpha ^{2}+e^{-{\frac {1}{\alpha +1}}}\left(\alpha ^{2}+\alpha -1\right)+1$.

When $\alpha =0$ and there are no dining club members, the probability that any agent eats returns to the expected $1-e^{-1}$. Generally speaking for $\alpha >0$, we have $p_{g}(\alpha )>p_{n}(\alpha )$. If the agents are aware of this and have a choice, this creates an incentive to form a type of coalition in the sense of cooperative game theory.

Harlaka, Belmonte and Griffin rephrase the problem of coalition formation as an evolutionary game by letting,

$\beta ={\frac {g}{N}}$,

be the proportion of agents currently playing the dining club strategy, and assuming that this proportion must follow the replicator equation,

${\dot {\beta }}=\beta \left[p_{g}(\beta )-{\bar {p}}(\beta )\right]$,

where $p_{g}(\beta )$ is the probability that an agent in the dining club eats, written in terms of $\beta$ given as,

$p_{g}(\beta )={\frac {1-e^{\beta -1}}{1-\beta }}$,

and

${\bar {p}}(\beta )=e^{\beta -1}(\beta -1)+1$.

A solution curve for the replicator equation in the Kolkata Paise dining club formulation.

The solution curve for the replicator dynamics is shown to the right. Like a logistic equation, the dynamics have an unstable fixed point at $\beta =0$ and a stable fixed point at $\beta =1$. Under these dynamics, the population will evolve naturally toward a centrally managed dining club. Harlalka and Griffin show a similar result for imitation dynamics.

Meal Sharing and Freeloading

If the dining clubs impose a food tax of proportion $0<\kappa <1$ on members that successfully eat (i.e., those that do not collide with a non-club member), then the optimal tax rate is,

$\kappa ^{*}=1-p_{g}(\beta )$.

Collected food is then placed into a common pot and equally shared. This tax rate ensures that no member eats less than the expected amount $p_{g}(\beta )$ for the club size (given by $\beta$). When non-club members can freeload on this communal pot of food, it has the potential to destabilize the club, causing the members to leave the club in favor of the non-club group. As a consequence, the dining club collapses.. Conditions for this collapse are given by Harlalka, Belmonte and Griffin

Multiple Dining Clubs

The problem can be extended to the case of multiple dining clubs, with the expressions for probability becoming more complex as the number of dining clubs grows. In the case of two dining clubs of size $g_{1}$ and $g_{2}$ and a free (non-club) population of size $n$, the probability that a member of dining club 1 eats is,

$p_{1}(n,g_{1},g_{2})=\sum _{k=0}^{n}\left[{\binom {n}{k}}\left({\frac {1}{n+g_{1}+g_{2}}}\right)^{k}\left({\frac {n+g_{1}+g_{2}-1}{n+g_{1}+g_{2}}}\right)^{n-k}P(n,g_{1},g_{2})\right]$,

where,

$P(n,g_{1},g_{2})=\left({\frac {n+g_{1}}{n+g_{1}+g_{2}}}\right){\frac {1}{k+1}}+\left({\frac {g_{2}}{n+g_{1}+g_{2}}}\right){\frac {1}{k+2}}$.

Exchanging $g_{1}$ and $g_{2}$ produces the $p_{2}(n,g_{1},g_{2})$, the probability a member of dining club 2 eats. A non-club member eats with probability,

$p_{n}(n,g_{1},g_{2})=\sum _{k=0}^{n-1}\left[{\binom {n-1}{k}}\left({\frac {1}{n+g_{1}+g_{2}}}\right)^{k}\left({\frac {n+g_{1}+g_{2}-1}{n+g_{1}+g_{2}}}\right)^{n-k-1}Q(n,g_{1},g_{2})\right]$,

where,

$${\begin{aligned}Q(n,g_{1},g_{2})=\left[{\frac {n+g_{1}}{n+g_{1}+g_{2}}}{\frac {n+g_{2}}{n+g_{1}+g_{2}}}{\frac {1}{k+1}}+\left({\frac {g_{1}}{n+g_{1}+g_{2}}}{\frac {n+g_{1}}{n+g_{1}+g_{2}}}+{\frac {g_{2}}{n+g_{1}+g_{2}}}{\frac {n+g_{2}}{n+g_{1}+g_{2}}}\right){\frac {1}{k+2}}+\right.\\\left.{\frac {g_{1}}{n+g_{1}+g_{2}}}{\frac {g_{2}}{n+g_{1}+g_{2}}}{\frac {1}{k+3}}\right].\end{aligned}}$$Despite the complexity, it is known that systems with multiple dining clubs evolve to a single dining club in the absence of perfectly symmetric initial conditions or exogenous forces like freeloading.