Learning the queue arrivals game equilibrium

As is well known, under Nash equilibrium each agent arrives at a pure or a mixed strategy over all her actions so that no agent gains by deviating unilaterally. Under correlated equilibrium (CE) there is a joint distribution across each agent’s actions so that if through a sample from this distribution, an action is prescribed to each agent privately, then no agent benefits by deviating unilaterally from the prescribed action. In the coarse correlated equilibrium (CCE), each agent is aware of the joint distribution, and sees no benefit in following any other strategy unilaterally, once all the other agents follow the joint distribution. Unlike under CE, under CCE, seeing the sample from the joint distribution, and depending on its value, an agent may have an incentive to change to an action different from the sample.

An agent’s regret at any time refers to the additional loss suffered compared to following a single action that till that time incurs minimum cost.