The basic unit in our syntactical framework for recursive agent
modeling is the situation. At any point in time, an agent is in
a situation, and all the other agents present are in their respective
situations. An agent's situation contains not only the situation the
agent thinks it is in but also the situations the agent thinks the
others are in (these situations might then refer to others and so on
...). In this work, we have adopted RMM's assumption that common
knowledge
cannot arise in practice. Common knowledge would be represented in our
framework by having situations refer back to themselves either
directly or transitively. Conversely, cycles or loops of reference
between situations imply the presence of common knowledge. They are,
therefore, disallowed since common knowledge can not be achieved in
many common situations of interest to us, such as in asynchronous
message-passing system [4]. Allowing
agents to jump to assumptions about common knowledge can simplify
coordination reasoning, since agents can use fixed-point equilibrium
notions and axioms based on mutual beliefs and plans. While leaping to
such assumptions can, at times, be a viable method for keeping
coordination practical [1], it also introduces
risks that we wish to avoid.
A situation has both a physical and a mental component. The physical component refers to the physical state of the world and the mental component to the mental state of the agent, i.e. what the agent is thinking about itself and about the other agents around it. Intuitively, a situation reflects the state of the world from some agent's point of view by including what the agent perceives to be the physical state of the world and what the agent is thinking. A situation evaluates to a strategy, which is a prescription for what action(s) the agent should take. A strategy has a probability associated with each action the agent can take, and the sum of these probabilities must always equal 1.
Let S be the set of situations an agent might encounter, and A the set of all other relevant agents. A particular situation s is recursively defined as:
The matrix M has the payoff the agent, in situation s, expects to get for each combination of actions that all the agents might take. The matrix M can either be stored in memory as is, or it can be generated from a function (which is stored in the agent's memory) that takes as inputs any relevant aspects of the physical world, and previous history. The relevant aspects of the physical world are stored in W, the physical component of the situation. The rest of s constitutes the mental component of the situation.
The probabilistic distribution function f(x) gives the probability that the strategy x is the one that the situation s will evaluate to. It need not be a perfect probabilistic distribution; it is merely used as a useful approximation for guiding our search through the recursive models. That is, our algorithm will employ it as a heuristic for determining which recursive models to expand. We use f(x) to calculate the strategy that the agent in the situation is expected to choose, using standard expected value formulas from probability theory. The values of this function are usually calculated from previous experience. In practice, some simplifying assumptions can be made about how to calculate (i.e. learn) this value, as we shall explain in Section 3.2. We also note that the knowledge encompassed by f(x) is not the real knowledge, which is contained in the matrices, but is the search knowledge used only for guiding the search through the recursive models. There is no guarantee that the predictions produced by f(x) will be correct. The models, on the other hand, are always considered to be correct.
A situation s also includes the set of situations which the agent in s believes the other agents are in. Each agent a is believed to be in r, with probability p. The value of r can either be a situation or, if the modeling agent has no more knowledge, it can be the Zero Knowledge strategy (r = ZK).