6.4 From Probability on Runs to Probability Assignments

6.4 From Probability on Runs to Probability Assignments

In this section, I assume for simplicity that each agent starts with a probability on the set of runs. From that, I provide one natural way of deriving the probability assignments. The basic idea is simple. Roughly speaking, the probability of a point (r′, m′) according to the probability assignment at (r, m) is the probability of r′, conditioned on the set of runs that the agent considers possible at (r, m).

It is easy to see how this works in Example 6.3.2. At the point (r¹, 1), Alice considers two points possible: (r¹, 1) and (r², 1). She ascribes these points each probability 1/2. She considers two runs possible, namely r¹ and r². The probability of (r¹, 1) is just the conditional probability of r¹ given {r¹, r²}, and similarly for (r², 1). At (r¹, 1), Bob considers four points possible: (r¹, 1), (r², 1), (r³, 1), and (r⁴, 1). He ascribes these points probability 1/3, 1/3, 1/6, and 1/6, respectively, since this is the probability of the runs that they are on (conditional on the set of all runs).

To make this precise, it is helpful to have some notation that relates sets of runs to sets of points. If is a set of runs and U is a set of points, let U() be the set of runs in going through some point in U and let U() be the set of points in U that lie on some run in . That is,

The condition that the agents' probability assignments in the probability system (, ₁, …, _m) are determined by a (prior) probability on runs can now be formalized as follows:

PRIOR. For each agent i, there exists a probability space , _i, μ_,i such that (_i(r, m)) ∈ _,i and μ_,i((_i(r, m))) > 0 for all r, m, i (i.e., the set of runs that agent i considers possible at any point has positive probability) and _i(r, m) = (W_r,m,i, _r,m,i, μ_r,m,i), where

• W_r,m,i = _i(r, m);

• _r,m,i = {_i(r, m)() : ∈ _,i;

• μ_r,m,i(U) = μ_,i((U) | (_i(r, m)), for U ∈ _r,m,i.

If a system satisfies PRIOR, a set U of points is measurable if it consists of all the points that lie on the runs in some measurable subset of runs; the probability of U (according to μ_r,m,i) is just the probability of the set of runs going through U (according to μ_i, _i) conditioned on the set of runs going through _i(r, m).

It is easy to see that the probability assignments defined this way satisfy CONS and SDP. (Indeed, as promised, agent i's probability assignment at the point (r, m) is determined by _i(r, m), and hence by agent i's local state at (r, m).) Moreover, if the agents have a common prior on runs (i.e., if _i = _j and μ_i = μ_j for all i and j), then CP holds as well (Exercise 6.5). An SDP system is one where PRIOR holds and the agents have a common prior on runs.

What is the connection between _i(r, m) and _i(r, m + 1) in systems satisfying PRIOR? Since _i(r, m) and _i(r, m + 1) are each obtained by conditioning the prior probability on agent i's current information, it seems that _i(r, m + 1) should be, roughly speaking, the result of conditioning _i(r, m) on _i(r, m + 1). In general, this is not true.

Example 6.4.1

Consider the system described in Example 6.3.2, where Alice tosses two coins, with one modification. Assume that although Alice knows the outcome of the first coin toss after she has tossed it, she forgets it after she tosses the second coin. Thus, Alice's state has the form (i, o), where i ∈ {0, 1, 2} is the time and o ∈ {〈〉, heads, tails} describes the outcome of the coin toss in the previous round (o =〈〉 at time 0, since no coin was tossed in the previous round). Suppose that, in fact, Alice tosses two heads (so that run r¹ occurs). In this case, μ_r¹_{, 1,A}(r¹, 1) = 1/2. This seems reasonable; at time 1, after observing heads, Alice assigns probability 1/2 to the point (r¹, 1), where the coin will land heads in the next round. After all, given her information, r¹ is just as likely as r². If she is using conditioning, after observing heads in the next round, Alice should assign the point (r¹, 2) probability 1. However, μ_r¹_{, 2,A}(r¹, 2) = 2/3 since Alice forgets the outcome of the first coin toss at time 2. Thus, at time 2, Alice considers both r¹ and r³ possible, even though at time 1 she knew that r³ was impossible.

As Example 6.4.1 suggests, a necessary condition for conditioning to be applicable is that agents do not forget, in a sense I now make precise. This observation is closely related to the observation made back in Section 3.1 that conditioning is appropriate only if the agents have perfect recall.

Modeling perfect recall in the systems framework is not too difficult, although it requires a little care. In this framework, an agent's knowledge is determined by his local state. Intuitively, an agent has perfect recall if his local state is always "growing," by adding the new information he acquires over time. This is essentially how the local states were modeled in Example 6.3.1. In general, local states are not required to grow in this sense, quite intentionally. It is quite possible that information encoded in r_i(m)— i's local state at time m in run r—no longer appears in r_i(m + 1). Intuitively, this means that agent i has lost or "forgotten" this information. There is a good reason not to make this requirement. There are often scenarios of interest where it is important to model the fact that certain information is discarded. In practice, for example, an agent may simply not have enough memory capacity to remember everything he has learned.

Nevertheless, there are many instances where it is natural to model agents as if they do not forget. This means, intuitively, that an agent's local state encodes everything that has happened (from that agent's point of view) thus far in the run. That is, an agent with perfect recall should, essentially, be able to reconstruct his complete local history from his current local state. This observation motivates the following definition.

Let agent i's local-state sequence at the point (r, m) be the sequence of local states that she has gone through in run r up to time m, without consecutive repetitions. Thus, if from time 0 through time 4 in run r agent i has gone through the sequence 〈s_i, s_i, s′_i, s_i, s_i〉 of local states, where sⁱ ≠ sⁱ, then her local-state sequence at (r, 4) is 〈s_i, s_i, s_i〉. Agent i's local-state sequence at a point (r, m) essentially describes what has happened in the run up to time m, from i's point of view. Omitting consecutive repetitions is intended to capture the fact that agent i is not aware of time passing, so she cannot distinguish a run where she stays in a given state s for three rounds from one where she stays in s for only one round.

An agent has perfect recall if her current local state encodes her whole local-state sequence. More formally, agent i has perfect recall in system if at all points (r, m) and (r′, m′) in , r, m) ~_i (r′, m′), then agent i has the same local-state sequence at both (r, m) and (r, m). Thus, agent i has perfect recall if she "remembers" her local-state sequence at all times. In a system with perfect recall, r_i(m) encodes i's local-state sequence in that, at all points where i's local state is r_i(m), she has the same local-state sequence. A system where agent i has perfect recall is shown in Figure 6.5, where the vertical lines denote runs (with time 0 at the top) and all points that i cannot distinguish are enclosed in the same region.

Figure 6.5: A system where agent i has perfect recall.

How reasonable is the assumption of perfect recall? That, of course, depends on the application. It is easy to see that perfect recall requires every agent to have a number of local states at least as large as the number of distinct local-state sequences she can have in the system. In systems where agents change state rather infrequently, this may not be too unreasonable. On the other hand, in systems where there are frequent state changes or in long-lived systems, perfect recall may require a rather large (possibly unbounded) number of states. This typically makes perfect recall an unreasonable assumption over long periods of time, although it is often a convenient idealization and may be quite reasonable over short time periods.

In any case, perfect recall gives the desired property: μ_{r, m+1,i} is essentially the result of conditioning μ_r,m,i on the set of points that lie on runs going through points in _i(r, m + 1). To make this precise, given a set U of points, let U_{r, m,i} be the set of points in _i(r, m) that are on the same runs as points in U; that is, U_r,m,i = {(r′, m′) ∈ (r, m) : (r′, m′′) ∈ U for some m′′}.

Proposition 6.4.2

If (, ₁, …, _n) is a probability system satisfying PRIOR where agents have perfect recall, then for all points (r, m) and agents i, if U ∈ _r,m+1,i, then U_r,m,i ∈ _r,m,i and

Proof See Exercise 6.8.

The assumption of perfect recall is crucial in Proposition 6.4.2; it does not hold in general without it (Exercise 6.7).

The sets U_r,m,i have a particularly elegant form if one additional assumption is made, namely, that agents know the time. This assumption already arose in the discussion of Example 6.3.1, when I assumed that Bob knew at time 1 that it was time 1, and thus knew that Alice had chosen a number; it is also implicit in all the other examples I have considered so far. Perhaps more significant, game theorists (almost always) assume that agents know the time when analyzing games, as do linguists when analyzing a conversation. The assumption is not quite as common in computer science; asynchronous systems, where agents do not necessarily have any idea of how much time has passed between successive moves, are often considered. Nevertheless, even in the computer science literature, protocols that proceed in "phases" or rounds, where no agent starts phase m + 1 before all agents finish phase m, are often considered.

The assumption that agents know the time is easily captured in the systems framework. is synchronous for agent i if for all points points (r, m) and (r′, m′) in , if (r, m) ~_i (r′, m′), then m = m′. Thus, if is synchronous for agent i, then at time m, agent i knows that it is time m, because it is time m at all the points he considers possible. is synchronous if it is synchronous for all agents.

It is easy to see that the system of Example 6.3.1 is synchronous, precisely because Bob's local state at time 1 is tick. If Bob's state at both time 0 and time 1 were 〈〉, then the resulting system would not have been synchronous for Bob.

Given a set U of points, let U⁻₋ ={(r, m) : (r, m + 1) ∈ U}; that is, U⁻ consists of all the points preceding points in U.

Proposition 6.4.3

If is synchronous for agent i and agent i has perfect recall in , then U_r,m,i = U⁻.

Proof See Exercise 6.8.

That means that if is synchronous for agent i and agent i has perfect recall in , then the sets U_r,m,i and (_i(r, m + 1))_r,m,i in the statement of Proposition 6.4.2 can be replaced by U⁻ and _i(r, m + 1)⁻, respectively. Thus, the following corollary holds:

Corollary 6.4.4

If (, ₁, …, _n) is a synchronous probability system satisfying PRIOR where agents have perfect recall, then for all points (r, m) and agents i, if U ∈ _{r,m + 1,i}, then U_r,m,i ∈ _r,m,i and