have a distributed, coordinated execution of the R-MAX algorithm, and the result follows immediately from the properties of R-MAX. Note that Case 1 does not require perfect monitoring.

We note that many cases can be reduced to this case. Indeed, below we present techniques for handling a number of more difficult cases in which an ordering does not exist, that work by reduction to Case 1. We note that in special games in which there is sufficient asymmetry in the game (e.g., different action set sizes, different off-diagonal payoffs) it is possible to devise more efficient methods for generating an ordering (e.g., via randomization). Case 2:  A commonly known ordering over the agents, and knowledge of the action-set size of all agents.  First, suppose that the agents not only know the action set sizes of each other, but also share a common ordering over the actions of each agent.

This induces a natural lexicographic ordering over the joint actions based on the ordering of each agent's actions and the ordering over the agents. Thus, we are back in case 1.

In fact, we do not really need a common ordering over the action set of each agent. To see this, consider the following algorithm:
- Each agent will represent ea joint action as a vector. The k th component of this vector is the index of the action performed by agent k in this joint action. Thus, (3, 4)
denotes the joint action in which the first agent according to the common ordering performs its third action, and the second agent performs its fourth action.

- At each point, the agent will choose the appropriate joint action using R- MAX. The choice will be identical for all agents, provided the model is identical.

- Because each agent only performs its aspect of the joint action, there cannot be any confusion over the identities of the actions. Thus, if R- MAX determines that the current action is (3,4), then agent 1 will perform its third action and agent 2 will perform its fourth action.
The model is initialized in an identical manner by all agents. It is updated identically by all agents because at each point, they all choose the same vector and their rewards are identical. The fact that when the chosen joint action is (3,4) agent 1 does not know what precisely is the fourth action of agent 2 does not matter.

Following Case 2, we can show that we can deal efficiently with a perfect monitoring setup.

Case 3:  Perfect  Monitoring.   We can reduce the case of perfect monitoring to Case 2 above as follows. First, we make the action set sizes known to all agents as follows: In the first phases of the game, each agent will play its actions one after the other, returning to its first action, eventually. This will expose the number of actions. Next, we establish a common ordering over the agents as follows: Each agent randomly selects an action. The agent that selected an action with a lower index will be the first agent. Thus, we are now back in Case 2.