
| No. Bids   | MDP   |     |     |
|------------|-------|-----|-----|
| Date       | e A   |     |     |
| 7/20/00    | 25%   | 26% |     |
| g          |       |     |     |
| 7/27/00    | 7     | 14% | 20% |
| 8/3/00     | 8     | 29% | 2%  |

Table 6: Auction results. The "MDP" column shows the percentage of available auction time remaining when the MDP ose to close the auction.  The "eA" column shows the percentage of available auction time remaining when the strategy eA,
with EQ c ( t ) proportional to the number of bids received ("No.  Bids" column),
the general MDP code with three simple lines of code implementing the eA strategy, which we determined to be optimal for the particular parameters of the problem. Using log files recorded during the actual auctions reported in (Scerri, Pynadath, & Tambe, 2001), we experimentally verified that both the MDP and the eA strategy produced the same result.

Table 6 shows the percentage of available auction time remaining (e.g., if the auction was opened four days before the role should be performed, closing the auction one day before would correspond to 25%) when the MDP version and the eA version of the code closed the auction. The number of bids is used to estimate the agent's expected decision quality. The timing of the auction closing is close, certainly within just a few hours. The result is not precisely the same for the MDP and strategy implementations, because the MDP
implementation was more reactive to incoming bids than the strategy implementation.

To confirm that the need for strategies was not a phenomenon unique to the particular settings of the E-Elves, an experiment was run with randomly generated configurations of entities. The wait cost for each configuration increased exponentially, with the rate of accrual varying from configuration to configuration. The configurations contained between 3 and 25 entities, with randomly chosen Markovian response probabilities and randomly chosen, but constant, decision-making quality. The cost and value of a D action was also randomly selected. In each configuration, there was an agent that could respond instantly, but with lower decision quality than any of the other entities. For each configuration, the optimal transfer-of-control strategy was found. Figure 10(a) shows the percentage of optimal strategies (z-axis) that were of each length (y-axis "|Opt. Strat.|"), separated according to the rate at which wait costs accrued (x-axis, "Wait Cost Param"). The figure shows that if the rate at which the wait cost accrues is very low, most optimal strategies are of length one, with the agent just handing control to the entity with the highest decision-making quality. When the rate of wait cost accrual is high, most strategies are of length two, with the agent briefly giving the best decision maker an opportunity to make the decision but taking back control and acting before the wait costs became too high. For intermediate values of the wait cost parameter, there was considerably more variation in the length of the optimal strategy. Figure 10(b) shows the percentage of optimal strategies for each length when the wait cost parameter is 0.12 (i.e., a slice through Figure 10(a)). Hence, strategies often contained several transfers of control and several coordination changes. Thus, this experiment shows that complex transfer-of-control strategies are useful, not only in E-Elves,