Efficiency and Equilibrium in Task Allocation Economies with Hierarchical Dependencies

1 Introduction

We consider task allocation problems in which compet­ ing agents desire to accomplish tasks, which may re­ quire complex chains of production activity. In order to perform a particular task, an agent may need to achieve some subtasks, which may in turn be delegated to other agents, forming a supply chain through a hi­ erarchy of task achievement. Constraints on the task assignment arise from resource contention, where agents would need a common resource (e.g., a subtask achieve­ ment , or something tangible like a piece of equipment) to accomplish their own tasks. We assume that agents are self-interested and have private information, and so we must allocate in a decentralized manner.

We take a market-based approach to decentralized resource allocation, utilizing the large body of so­ lution methods and analytical techniques from eco­ nomics. Auctions mediate negotiation and determine prices and allocations. Prices indicate relative values of resources to guide local agent decisions. Experience with the market-oriented programming approach has verified that it works predictably and effectively in convex do­ mains [Wellman, 1993]. Discrete problems, such as the task allocation domain considered here, provide addi­ tional challenges.

In previous work [1998], we proposed a market proto­ col that reliably constructs supply chains in a decentral­ ized manner. In this paper we generalize the model and protocol to account for multiple competing demands for multiple end tasks. We bound the inefficiency of a type of approximate equilibrium in proportion to the num­ ber of agents and the bidding parameters in a particular market protocol. This protocol converges to an approxi­ mate equilibrium with respect to all agents, except those which may acquire unneeded inputs. We introduce a de­ commitment phase to allow ·such agents to decommit from their input contracts. Experiments indicate that the augmented market protocol produces highly efficient allocations on average.

We describe the task allocation problem in Section 2. We discuss price systems and competitive equilibrium in Section 3, and survey some market protocols for decen­ tralized resource allocation in Section 4. In Section 5 we analyze the equilibrium properties of the extended protocol , and in Section 6 we examine its efficiency. We describe related task allocation work in Section 7.

2 Problem Description

Tasks are performed on behalf of particular agents; if two agents need a subtask then it would have to be performed twice to satisfy them both. In this way, tasks are the same as any other discrete resource. Hence we make no distinction in our model, and use the term "good" to refer to both.

We describe the problem in terms of bipartite graphs. A task dependency network is a directed, acyclic graph, (V, E). The vertices are V = G U A, where G is the set of goods, A = C uTI uS is the set of agents, C is the set of consumers, TI is the set of producers, and S is the set of suppliers. The edges, E , connects agents with goods they can use or provide. There exists an edge (g, a) from g E G to a E A when agent a can make use of one unit of g, and an edge (a, g) when a can provide one unit of g. When an agent can acquire or provide multiple units of a good, we represent each unit as a separate edge. The goods can be traded only in integer quantities.

A consumer wishes to acquire one unit of one good from a set of some high-level goods. A producer can produce a single unit of an output good conditional on acquiring a certain number each of some fixed set of input goods. A producer 's input requirements are complementary in that it must acquire each of its in­ puts; it cannot accomplish anything with only a partial set. A supplier can supply a set of goods, up to some maximum quantity for each, without requiring any input goods.

An allocation is a subgraph (V', E') ~ (V, E). For g E G, an edge (a, g) E E' means that agent a provides g, and (g, a) E E' means a .acquires g. An agent is in an allocation graph iff it acquires or provides a good. A good is in an allocation graph iff it is bought or sold.

A producer is active iff it provides its output . A producer is feasible iff it is inactive or acquires all its inputs. Consumers and suppliers are always feasible. An allocation is feasible iff all producers are feasible and all goods are in material balance , that is the number of edges into a good equals the number of edges out.

A solution is a feasible allocation such that one or more consumers acquire a desired good. If c E C n V' for solution (V', E'), then (V', E') is a solution for c.

Each supplier s has some opportunity cost oc.(g) for supplying one unit (s, g) of good g. The total opportunity cost to s for allocation E' is oc.(E') = L (s,g)EE' oc.(g) . 1 The cost might represent the value s could obtain from putting the goods to some other use, or some actual, direct cost incurred in supplying the goods.

We assume that a consumer has preferences over dif­ ferent possible goods, but wishes to obtain only a single unit of one good. 2 Thus, a consumer c obtains value vc(g) for obtaining a single unit of good g, and, for allo­ cation E', obtains value vc(E') = max(g,c)EE' Vc(g).

Definition 1 (value of an allocation) The value of allocation (V', E') is:

Definition 2 (efficient allocations) The set of efficient allocations contains all feasible al­ locations (V*, E*) such that value((V*, E*)) max(v',E')(value((V',E')) I (V',E') is feasible).

1 We overload the notation for opportunity cost and agent value, using as an argument either a single good or a set of edges.

2 More complicated consumer value functions can be ex­ pressed through combinations of multiple consumers and pro­ ducers. For instance, a group of consumers, each desiring a single separate good, effectively represents an additive value function over the set of goods. If a consumer has prefer­ ences over bundles of goods, the bundles can be represented as output goods of producers, with the inputs of a producer corresponding to the components of the respective output bundle. Note that transformations such as this may not be strategically equivalent, in that the group of consumers may not behave as would the single agent they represent .

One could find efficient allocations using centralized search techniques, but we assume that we are con­ strained to solve the problem in a decentralized fashion. In the following, we examine an abstract framework for how a price system can guide decentralized task alloca­ tion. We also examine market protocols for decentralized task allocation.

3 Price Systems and Competitive Equilibrium

In the general-equilibrium approach to economic re­ source allocation, we posit a price system p, which assigns to each good g a nonnegative number p(g) as its price. Intuitively, prices indicate the relative global value of the goods. Therefore, agents may use the prices as a guide to their local decision making.

We assume each agent has a quasilinear utility func­ t ion. Its utility is the sum of the "money" it holds and the value (or negative cost) obtained from its allocation of goods. Agents wish to maximize t heir surplus.

Definition 3 (surplus) The surplus, a(a,E',p), of agent a with allocation E' at prices p, is the utility gain from E', defined as follows:

• Va(E') - L (g,a)EE' p(g), if a E c,
• L (a,g)EE' p(g)- L (g,a)EE' p(g) , if a E II,
• L (a,g)EE' p(g)- OCa(E'), if a E S.

Informally, an allocation (V', E') is a competitive equilibrium at prices p if (V', E') is feasible and assigns to each agent an allocation that optimizes the agent's surplus at p. A competitive equilibrium allocation is stable in the sense that no agent would want a different allocation at the equilibrium prices.

We should generally expect that iterative auction pro­ tocols with discrete bid adjustments would overshoot exact equilibria by at least a small amount. However, approximate equilibrium is a useful concept for analyz­ ing such protocols [Demange et al., 1986; Walsh et al., 1998]. We define and discuss properties and existence of a >-.-iS-competitive equilibrium-a particular type of approximation equilibrium relevant to task dependency networks. The ).. and <5 parameterize an agent 's maxi­ mum error in surplus optimization.

Denote as Ha(p), the maximum surplus that agent a can obtain in (V, E), at some prices p, subject to feasi­ bility. That is,

such that a is feasible at E'.

Definition 4 (>-.-iS-competitive equilibrium) Given the parameters:

• <5 E ~+ U { 0} ,
• )...,. E ~+ U {0} for all 1r E II,
• N.,., the number of input units required by 1r E II

an allocation (V', E') is in >.-J-competitive equilibrium at prices p iff:

1. For all a E A, a(a,E', p) 2:0.
2. For all c E C, a(c, E' ,p) 2: Hc(P) - J.
3. For all 1r E II, a(n, E',p) 2: H,r(P)- (NrrArr + J), and 1r is feasible at E'-
4. 4- For all s E S, a(s,E',p) = Hs(P)-
5. All goods are in material balance at p.

Figure 1 shows a >.-J-equilibrium for AB-C-D-to-E = J ~ L Goods are indicated by circles, consumers and suppli­ ers are represented as boxes, and producers are indicated by curved boxes. A solid arrow from a good to an agent indicates that the agent buys the good, and a solid ar­ row from an agent to a good indicates that the agent sells the good. Dashed arrows indicate input/output ca­ pabilities not part of the allocation. Shaded agents re­ ceive non-null allocations. Agent values and good prices are shown under their respective nodes. Note that for 1r = B-C-D-to-E, a(n, E' ,p) = 0 2: Hrr(P)- (Nrr>-rr + J) = 1 - 4. Thus 1r obeys the producer conditions for >.-J­ competitive equilibrium.

A >.-J-competitive equilibrium corresponds to the standard notion of a competitive equilibrium when >-rr = J = 0 for all producers 1r. Bikhchandani and Marner [1997] and Gul and Stacchetti [1997] show that, in an exchange economy, any competitive equilibrium set of prices supports an optimal allocation. We extend this result below to the class of production economies repre­ sented by task allocation economies. We show this by proving the more general result that a >.-iS-competitive equilibrium is suboptimally efficient by a fixed bound, LrrETI[NrrArr + J] + ICIJ.

Lemma 1 The value of a feasible allocation (V', E'), at any prices p, can be expressed as:

Proof sketch. 3 Since supply equals demand in a feasi­ ble allocation, all the price terms cancel out and we are Figure 2: An economy with a >.-J-competitive equilib­ rium solution when 3,\B-C-D-to-E + J > L

3 Complete proofs of all results appear at http://www-personal.engin.umich.edu/-wew/Papers/ ijcai99-extended.ps.Z.

left with the original formula for the value of a solution (Definition 1). D

Theorem 2 If (V', E') is a >.-J-competitive equilibrium for (V, E) at some prices p, then (V', E') is a feasible allocation with a nonnegative value that differs from the value of an efficient allocation by at most LrrETI[Nrr>-rr + J] + ICIJ-

Proof sketch. We can compare the value of (V', E') to another feasible allocation (V*, E*) , agent-wise, using Equation (1). The >.-J-competitive equilibrium condi­ tions imposed on the agents imply a global value differ­ ence that obeys the stated bound. D

Not all task allocation economies have competitive equilibria (technically, this is due to complementarity of inputs for producers). However, we can always specify J and Arr values such that a >.-J-competitive equilibrium exists, even when a competitive equilibrium does not ex­ ist. For example, we can do this by setting prices of the goods desired by the consumers higher than their val­ ues and the prices of all other goods to zero (if there are an; suppliers that could sell directly to consumers with positive surplus on both sides, we can set the prices so that only these suppliers trade with those consumers). We then set J and the Arr values sufficiently high such that Hrr(P) - (NrrArr + J) ~ 0 for all 7r E II. Hence producers could obey the >.-J-competitive equilibrium conditions by being inactive. Unfortunately, we can­ not generally specify a >.-J-competitive equilibrium for some fixed, problem-independent values of J and >-rr­ Indeed, the necessary values to obtain a non-solution >.-J-equilibrium are proportional to the highest consumer value and the depth of the network.

Figure 2 shows the constraints on AB-C-D-to-E and J in order to have a solution in >.-J-competitive equilibrium for a particular economy. The only solution involves all agents except B-C-D-to-E. The constraints on the prices of goods A and B ensure that suppliers A and B sell their goods. The constraint on the price of good C en­ sures that supplier C does not sell its good. The con­ straint on the price of good E ensures that A-B-to-E is active. The constraint on the price of good D en­ sures that B-C-D-to-E does not trade any goods. Finally, the constraint on the price of good F ensures that 0 -E-to-F is active and also that the consumer buys good F. The constraint on the price of good F requires 3As-C-D-to-E + c5 > 1 to have a A-<5-competitive equilib­ rium solution. Since this solution is the only efficient allocation, it is the only candidate allocation for a pure competitive equilibrium. But since the parameters must be nonzero, there is no pure competitive equilibrium. Note that to sustain the solution in A-<5-competitive equi­ librium the constraints on the prices for goods A and D, and hence the c5 and As.c-D-to-E values, rise linearly with the cost of supplier A.

4 Market Protocols

The previous section sidesteps the issue of how we might compute an approximate competitive equilibrium. The market-based approach, which we adopt, is to design' an auction mechanism that mediates negotiation and determines prices and allocations. The auctions along with the agents constitute an economy , or market , for the task allocation problem.

The agents' bidding policies govern their interaction with the auctions. The key distinction between the auc­ tion mechanism and bidding policies is that the former is under the control of the system designers, whereas the latter are determined by individual agents. Together, these specifications for behavior constitute a market protocol. The market protocol as a whole is our subject of analysis.

In economies characterized by infinite divisibility of goods , nonincreasing returns to scale, and gross sub­ stitutes, equilibria always exist and the tatonnement protocol converges to a competitive equilibrium. The WALRAS protocol is a variant of tatonnement, that can be implemented in a distributed manner across goods [Cheng and Wellman, 1998] . Highly efficient allo­ cations can be achieved in discrete exchange economies for which each agent wants only a single good [Fried­ man and Rust, 1993; McAfee and McMillan, 1987; Vickrey, 1961] or have non-complementary preferences for multiple goods [Demange et al., 1986]. However, economies with discrete goods and complementary pref­ erences of agents can lack equilibria, and thus provide a much greater challenge to obtaining efficient allocations.

Many researchers have proposed combinatorial auc­ tions to address the problem resulting from discrete goods and complementarities [Rassenti et al., 1982; Sandholm, to appear]. Combinatorial auctions allocate and price bundles of goods. Wurman and Wellman have shown that there always exists a competitive equilibrium set of prices on bundles that supports an efficient allo­ cation [1999]. Approximation techniques can be used to make the computation tractable [Fujishima et al., 1999; Sandholm, to appear]. However, except in some re­ stricted domains [Rothkopf et al., 1998; Sandholm, to appear] a combinatorial auction must generally perform a search over a combinatorial number of bundles.

In this work, we focus on computationally feasible auctions that price individual goods. The ideal such auction would induce a protocol resulting in a (near) competi­ tive equilibrium when one exists, and would produce a highly efficient allocations otherwise. Unfortunately, no protocol has yet been proposed that always converges to near competitive equilibrium, even when one exists, in economies with discrete goods and complementarities.

Lacking an ideal mechanism, many researchers have considered simultaneous ascending auctions [Milgrom, 1997]. When agents bid according to a straightforward rule, the auctions guarantee near-optimal performance in economies with no complementarities [Demange et al., 1986]. Observations of their performance in the United States FCC radio spectrum sale suggests that they can produce high-quality allocations even when complemen­ tarities exist [McAfee and McMillan, 1996]. In the fol­ lowing sections we analyze a variant simultaneous as­ cending auction for the task allocation problem.

5 SAMP-SB Protocol

In the "Simultaneous Ascending (M+1)st-Price with Simple Bidding" (SAMP-SB) protocol (extended from our previous work [1998] to allow multiple consumers with preferences for multiple goods), agents negotiate for the goods through auction mediators, one for each good. An auction in turn determines the price and allocation of its respective good. We assume reliable, asynchronous message passing.

5.1 Auction Mechanism

The task allocation market includes a separate auction for each good of potential value. Auctions operate simul­ taneously and asynchronously. Agents submit bids for goods they wish to buy or sell. A bid specifies the price below/above which the agent is willing to buy/sell. Auc­ tions respond with price quotes. A price quote specifies the current going price and the number of units the re­ cipient would trade at what price, given the current bid state. Agents may in turn respond with further bids. Each auction requires that an agent's successive bids in­ crease by no less than some (generally small) positive increment <5.

When the market reaches quiescence- a state in which no new bids or price quotes are issued- the auc­ tions clear. Each bidder is notified of the final prices and how many units it transacted in each good. The ascending rule serves a key role in establishing relation­ ships between market quiescence and solution conver­ gence of the economy [Walsh and Wellman, 1998]. In particular, the market always reaches quiescence with the bidding policies described in Section 5.2.

According to the the (M + 1 )st-price rules [Satterth­ waite and Williams, 1989; Wurman et al., 1998], an auction balances reported supply and demand at a uni­ form clearing price . Winners include all buyers/sellers strictly above/below the price, and, to maximize the benefits from trade, some agents at the clearing price.

5.2 Bidding Policies

Although multiagent system designers do not generally have control over the agents' behaviors, any conclusions about the outcome of a protocol must be based on some assumptions about these behaviors. In this work, we in­ vestigate the equilibrium and efficiency properties of a set of policies that obey the ascending auction bid con­ straints and require only local, private information.

Let the current going prices specified by the last price quotes be P- Supplier s places a one-time bid of OCs(g), for each unit (s, g) E E it can supply. When consumer c is not winning a good, it bids p(g*) + D for good g* = argmaxgEG 1 (g,c)EE[vc(g)- p(g)] if Vc(g*)- p(g*) ~ D, otherwise it stops bidding. A producer ?T initially bids zero for its output g". When the prices of its inputs change, ?T bids max(l::(g,,.)EE p(g) + kA,. , f3 +D) for g", where k is the number of input bids ?T is currently los­ ing, and f3 is its previous bid for g.,.. A producer initially bids zero for each input good, and raises its bid on input g by D when it is winning its output but losing its bid for g. The Arr and D parameters correspond to parame­ ters in a A-D-competitive equilibrium, as described in the following section.

5.3 Equilibrium Convergence of SAMP-SB

A-D-competitive equilibria do not always exist for fixed Arr and D, and even when they do, the SAMP-SB protocol is not guaranteed to converge to one. Figure 3 shows the results of a run 4 of SAMP-SB when Arr = D = 1 for all producers ?T. Note that B-C-D-to-E has a negative surplus, which is a violation of defining Condition (1) of a A-D-competitive equilibrium. However, if no inactive producer buys a positive-price input in quiescence, then the economy is in A-D-competitive equilibrium.

Theorem 3 The prices and allocation determined in quiescence by the SAMP-SB protocol is a A-D-competitive equilibrium iff .no inactive producer buys any positive­ price input.

Proof sketch. Case only if: Condition (3) of A-D­ competitive equilibrium fails if an inactive producer buys any positive-price input. Case if: The bidding policies, auctions, and theorem conditions ensure a(a, g, p) ~ 0 for all a E A. Consumer c E C maintains at most a single bid such that a(c,E',p) ~ Hc(P)- D. If ?T E II is active in quiescence, a(1r,E',p) = H,.(p). The theorem guar­ antees a(?T ,E',p) = 0 when ?Tis inactive, which occurs only if Hrr(P) ~ NrrA,. +D. The bidding policies ensure ?T is feasible. Supplier s E S sells g iff p(g) ~ occ(g), hence a ( s, E', p) = H s (p) _ The auctions ensure material balance. D

4 The nondeterminism of an asynchronous system implies that different runs may produce different results.

5.4 Contract Decommitment

Value is lost when inactive producers purchase some inputs at positive prices. Figure 3 shows a run of SAMP-SB in which B-C-D-to-E buys good C, even though it does not sell its output. A straightforward protocol extension for correcting the inefficiency is to remove the wasteful dead ends by selective contract de­ commitment.

We propose a contract decommitment protocol that is applied after SAMP-SB reaches quiescence. Each inactive producer that wins some inputs at a positive price can decommit from its contracts for its inputs. The protocol is applied recursively to the producers that lose their outputs due . to decommitment (we refer to SAMP-SB with decommitment as SAMP-SB-D) . When the decommitment process terminates, agents ex­ change goods as specified by the remaining contracts.

In Figure 3, both B-C-D-to-E would decommit from its contract with supplier C. Clearly, Theorem 3 implies that no agent decommits iff SAMP-SB produced a A-D­ competitive equilibrium. Moreover, if we remove all pro­ ducers that decommit, and all supplier resources corre­ sponding to decommited contracts, the remaining agents are in A-D-competitive equilibrium. Note that whereas some producers can lose money in the SAMP-SB proto­ col, no agent receives a negative surplus from participat­ ing in SAMP-SB-D.

6 Empirical Efficiency and Equilibrium Analysis of SAMP-SB

We conducted a series of 3300 randomly generated simulations in order to empirically evaluate how often SAMP-SB converges to equilibrium as well as its aver­ age quality. We ran 100 trials for each of 5- 15 goods and each of 1-3 consumers.

For a trial with N goods, we imposed a total order on the goods. Goods N and N - 1 had a number­ chosen from [1, 4]-of suppliers. All other goods i had a number-chosen from [1, 4]-of sellers with output i, each of which had a 2/N chance of being a supplier and a (N- 2)/N chance of being a producer. To ensure the network was acyclic, a producer with output i had two randomly chosen input goods j and k, such that j, k > i. Each consumer desired a single good. One consumer de­ sired good 1, and the other consumers desired randomly chosen goods. We drew consumer valuations uniformly from [0, 10N] and supplier costs uniformly from [0, 5N]. We fixed D = A,. = L

Mean PEV for SAMP-SB

83

Mean PEV for SAMP-SB-D

97

Percentage of trials in .X-<5-equilibrium

37

Mean non-equilibrium PEV of SAMP-SB 73

Mean non-equilibrium PEV of SAMP-SB-D 95

Table 1: Distributions over percentage of the efficient value (PEV) ranges, mean PEV, and equilibrium attain­ ment for 3300 trials.

As a benchmark, for each economy we computed the value of an efficient (optimal) allocation using A* search with an admissible heuristic. We ran SAMP-SB and SAMP-SB-D, and computed the resulting percentage of the efficient value (P EV). We discarded all trials for which the efficient value was zero, and substituted a new trial using a different configuration but the same number of consumers and goods.

Table 1 shows the distributions over ranges of PEV and mean PEV for SAMP-SB and SAMP-SB-D. The decommitment protocol greatly increases the PEV of SAMP-SB, raising the overall mean from 83% to 97%. The distribution of the PEV of SAMP-SB-D is quite high: 85% of the trials had 100% efficiency and 95% of the trials had at least 90% efficiency.

The SAMP-SB protocol reached .X-<5-equilibrium in over 37% of the trials. When we remove all .X-<5equilibrium trials from the trial set, the mean PEV of SAMP-SB decreases from 83% to 73%. This is not sur­ prising because the trials that reach .X-<5-equilibrium have high PEV values (Theorem 2). However, the PEV of SAMP-SB-D decreases only a small amount, from 97% to 95%. We might conclude from these simulations that the majority of efficiency loss from the SAMP-SB proto­ col can be attributed to inactive producers that acquire some inputs, with the resulting wasted costs of suppliers that feed into them.

We note that the PEV numbers we report are some­ what arbitrary in that they depend on the particular method for generating trials. Moreover, if a solution forms for a consumer in a particular economy, then we can get an arbitrarily high PEV by setting the con­ sumer's value arbitrarily high, while holding constant the rest of the configuration. We attempted to mitigate this effect by setting consumer values at reasonable lev­ els.

7 Related Work in Task Allocation

The CONTRACT NET protocol forms supply chains top­ down in a greedy fashion [Davis and Smith, 1983]. This approach produces satisficing allocations when there are no resource limitations. However, the firm resource con­ straints we impose in our model would generally require CONTRACT NET to backtrack in order to guarantee a fea­ sible allocation. Additionally, since the allocation policy is loosely specified in the original work, we cannot draw any conclusions about the efficiency of the approach.

Sandholm [1993] examines a specialization of CON­ TRACT NET for a generalization of Task Oriented Do­ mains (TODs) [Rosenschein and Zlotkin, 1994]. Agents begin with an initial allocation of tasks and negotiate task exchanges until there are no more mutually ben­ eficial trades. The trades can greatly increase the al­ location quality, but the system may get stuck in local minima.

Sandholm's model includes local constraints on task achievement, but does not impose a hierarchical depen­ dency structure. Thus each locally feasible bilateral trade can be executed immediately and independently of other trades. We cannot generally apply an incre­ mental trading protocol to our task allocation model. A local exchange may require reallocation throughout the entire network to maintain production feasibility.

Andersson and Sandholm [1998] find that decommit­ ment protocols increase the quality of the resulting allo­ cations in variants of TODs. With incremental trading, decommitment gives agents the opportunity to engage in other more cost-effective task allocation contracts.

8 Conclusions and Future Work

We have shown that we can bound the inefficiency of a .X-<5-competitive equilibrium in a task dependency net­ work in proportion to the number of agents and the bid­ ding parameters in the SAMP-SB protocol. SAMP-SB can sometimes converge to a .X-<5-competitive equilib­ rium, when one exists. When combined with contract decommitment, SAMP-SB produces highly efficient al­ locations on average.

SAMP-SB relies on the competitive assumption that agents take price quotes as the actual prices, and do not attempt to manipulate them. Although this assump­ tion is reasonable when there are many agents trading in each good- and hence no agent has significant market power-this assumption is less realistic in thinner mar­ kets. An agent may have opportunities to gain higher surplus by using other bidding policies, particularly if it has knowledge of other agents' preferences or behav­ ior. An enforcement mechanism could ensure that agents correctly follow the decommitment protocol, but the po­ tential to decommit may still affect agents' negotiation policies. We seek to establish conditions under which it is rational for agents to play SAMP-SB-D, and to an­ alyze strategic behavior when these conditions do not hold.

We wish to examine the possibility of including com­ binatorial auctions with SAMP-SB in the task allocation market. If we can identify portions of task networks with structures amenable to feasible bundle pricing, we may be able to increase the efficiency of allocations.

Acknowledgments

This work was supported by a NASA/Jet Propul­ sion Laboratory Graduate Student Researcher fellow­ ship, a DARPA Information Survivability grant, and a NSF /DARPA/NASA Digital Library Initiative grant. A portion of this work was performed at the 1998 Santa Fe Institute Workshop on Computational Economics. We also thank the anonymous reviewers for helpful sugges­ tions.