Using Decision-Theoretic Planning Agents in Market-Based Systems

Contents

This paper examines a number of theoretical and practical issues concerning the use of decision-theoretic planning to implement agents in market-based systems. The markets considered here result from the decomposition of complex, intra-organizationai resource allocation problems such as manufacturing scheduling. Although these problems can be formulated as monolithic optimization problems, they tend to be much too large to solve in practice. Markets provide a means of decomposing large resource allocation problems and distributing the computation of a solution over many processors. An important precondition of efficient markets is agent-level rationality. Decision theoretic planning can be used to imple-ment economic rationality and thus decision theoretic plan-ning agents fit well into market-based approaches. The primary challenge in building decision theoretic planning agents is the size of the agent’s state space. Although market-based decomposition results in agent-level problems that are much smaller than the original resource allocation problem, the price mechanism used to achieve independence of the agent-level problems requires that the agents plan over a large number of different resource contingencies. This requirement exacerbates the state space explosion that char-acterizes decision-theoretic planning. The application of state space reduction techniques such as structured dynamic programming and reachability analysis are shown to yield significant reductions in the effective size of the agent-level problems and thereby increase the applicability of decision theoretic planning techniques in market-based systems.