
| Original State   | A tion   | Destination State   | Probability   |      |            |                                       |         |
|------------------|----------|---------------------|---------------|------|------------|---------------------------------------|---------|
| e trl            | time     | e trl               | ei-response   | time |            |                                       |         |
| ej               | tk       | ei                  | ei            | yes  | tk+1       | R tk+1 tk P ei > (t)dt R tk+1 tk P ei |         |
| ej               | tk       | ei                  | ei            | no   | tk+1       | 1                                     | > (t)dt |
| ei               | tk       | wait                | ei            | yes  | tk+1       | R tk+1 tk P ei > (t)dt R tk+1 tk P ei |         |
| ei               | tk       | wait                | ei            | no   | tk+1       | 1                                     | > (t)dt |
| ei               | tk       | D                   | ei            | no   | tk  Dvalue | 1                                     |         |

 time is the urrent time, typi ally dis retized and ranging from 0 to our deadline, | i.e., a set ft0 = 0; t1; t2; : : : ; tn = g.
If ei-response is not null or if time = , then the agent is in a terminal state. In the former ase, the de ision is the value of ei-response.

We an spe ify the set of a tions for this MDP representation as  = E [ fD; waitg. The set of a tions subsumes the set of entities, E, sin e the agent an transfer de ision-making ontrol to any one of these entities. The D a tion is the oordinationhange a tion that hanges oordination onstraints, as dis ussed earlier. The \wait" a tion puts o transferring ontrol and making any autonomous de ision, without hanging oordination with the team. The agent should reason that \wait" is the best a tion when, in time, the situation is likely to hange to put the agent in a position for an improved autonomous de ision or transfer-ofontrol, without signi ant harm. For example, in the E-Elves domain, at times loser to a meeting, users an generally make more a urate determinations about whether they will arrive on time, hen e it is sometimes useful to wait when the meeting is a long time o.

The transition probabilities (spe ied in Table 2) represent the ee ts of the a tions as a distribution over their ee ts (i.e., the ensuing state of the world). If, in a state with time = tk, the agent 
hooses an a
tion that transfers de
ision-making 
ontrol to an entity, ei , other than the agent itself, the out
ome is a state with 
ontrol ling-entity = ei and time = tk+1. There are two possible out
omes for ei-response: either the entity responds with a de ision during this transition (produ ing a terminal state), or it does not, and we derive the probability distribution over the two from P. The \wait" a tion has a similar bran h, ex ept that the ontrol ling-entity remains un hanged. Finally, the D a tion o urs instantaneously, so there is no time for the ontrolling entity to respond, but the resulting state ee tively moves to an earlier time (e.g., from tk to tk  Dvalue).

We an derive the reward fun tion for this MDP in a straightforward fashion from our strategy model. Table 3 presents the omplete spe i ation of this reward fun tion.

In transitions that take up time, i.e., transferring ontrol and not re eiving a response

(Table 3, row 1) or \wait" (Table 3, row 2), the agent in urs the wait ost of that interval.

In transitions where the agent performs D, the agent in urs the ost of that a tion (Table 3, row 3). In terminal states with a response from ei, the agent derives the expe
ted quality of that entity's de ision (Table 3, row 4). A poli y that maximizes the reward that an agent expe ts to re eive a ording to this AA MDP model will orrespond exa tly to an optimal
