Equilibrium Analysis of the Possibilities of Unenforced Exchange in Multiagent Systems

1 Introduction

In cooperative distributed problem solving [Durfee et al., 1989], the system designer imposes an interaction pro­ tocol and a strategy (a mapping from state history to actions; a way to use the protocol) for each agent. In multiagent systems [Sandholm and Lesser, 1995c; 1995a; 1995b; Rosenschein and Zlotkin, 1994; Durfee et al., 1993; Kraus et al., 1992; Wellman, 1992], the agents are provided with an interaction protocol, but each agent may choose its own strategy. This allows the agents to be constructed by separate designers and/or represent different real world parties. Agents in such systems of­ ten act based on self-interest, and the protocols have to be constructed accordingly. An example interaction protocol is the auction, where some agents bid to take responsibility for a task, which is awarded to the lowest price bidder. The bids are binding: if an agent makes a bid and the task is awarded to it, it must take re­ sponsibility for the task at that price. Among real world agents, this protocol is enforced by law.

1 Supported by ARPA contract N00014-92-J-1698. T . Sandholm also supported by the Finnish Culture Foundation, Honkanen Foundation, and Ella and George Ehrnrooth Foun­ dation. The content does not necessarily reflect the position or the policy of the Government and no official endorsement should be inferred. An early version of this paper appeared in a workshop [Sandholm and Lesser, 1994].

Such enforced protocols are problematic when used among computational agents. First, there may be a lack of laws for interactions of computational agents, or the agents may be governed by different laws-e.g. sited in different countries. It may also be the case that the laws are not strictly enforced or that enforcing them (e.g. by litigation) is impractically expensive. We would like the agents' interactions to work properly independent of fluctuations in enforcement. Secondly, a computational agent may vanish at any point in time, e.g. by killing its own process. Thus, the laws cannot be enforced un­ less the terminated agent represented some real world party and the connection between the agent and the real world party can be traced. For example, the Telescript technology [General Magic, Inc., 1994] follows the ap­ proach of strictly trying to tie each agent to its real world party. On the contrary, we analyze exchanges among more autonomous agents and study possibilities of ex­ change without enforcement (e.g. with unknown real world parties or no litigation possibility). In cases where this type of exchange is possible, it is clearly preferable to. the strictly enforced mode of exchange due to savings in enforcement costs and lack of enforcement uncertainty.

The fulfillment of a mutual contract can be viewed as one agent delivering and the other agent paying. We pro­ pose a method for carrying out such an exchange without enforcement. The exchange is managed so that for both agents-supplier and demander-at any point in the ex­ change, the future gains from carrying out the rest of the exchange (cooperating according to the contract) are larger than the gains from defecting. Defection is equiv­ alent to prematurely terminating the exchange by van­ ishing. For example, defection may be beneficial to a demander agent if the supplier agent has delivered much more than what the demander has yet paid for. By intel­ ligently splitting the exchange into smaller portions, the agents can avoid situations where at least one of them is motivated to defect . We will call a sequence of de­ liveries and payments safe if neither agent is motivated to defect at any point in the exchange. The basic idea of enhancing cooperation by making the present less important compared to the future has been suggested for example in [Axelrod, 1984].

We propose an exchange strategy manager module to be added to each agent's architecture. This module is potentially different for each agent. Its role is to schedule the agent's deliveries (or payments) in such a way that the opponent is not motivated to defect at any point in the exchange. This is in the agent's self-interest. The exchange strategy manager also pro­ vides the agent's negotiator module with information on whether a certain proposed contract can be carried out safely. Unless protocol enforcement is guaranteed, the negotiator should only agree to contracts that can be ex­ ecuted so that the opponent is not motivated to defect at any point of the exchange. Automated negotiation has been mostly studied with respect to e:x: ante rational­ ity: what contracts seem desirable to the agents before they are carried out [Sandholm and Lesser, 1995b; 1995c; 1995a; Sandholm, 1993; Rosenschein and Zlotkin, 1994; Kraus et al., 1992; Wellman, 1992; Durfee et al., 1993). We suggest that contracts should also fulfill the condi­ tion of e:x: post rationality: abiding to the contract should be desirable to the agents at each step of the carrying out of the contract. E:x: post conditions were studied in mul­ tiagent planning without payments in [Brainov, 1994].

This paper is organized as follows. Section 2 handles one exchange in isolation. Conditions for safe exchange are derived and an inherent restriction concerning the completion of the exchange is identified. Section 3 takes the agents' future transactions into account in describing safe exchange in order to solve the completion problem. The role of time in an exchange is discussed in Section 4. Section 5 analyses the case, where the delivering order of independent goods can be varied. A quadratic sequenc­ ing algorithm is presented that finds a safe sequence if one exists. Section 5.1 studies sequencing of interdepen­ dent goods. Section 6 describes the advantages of safe exchange with respect to unfair renegotiation, and Sec­ tion 7 concludes.

2 Exchanging goods and payments

Our model analyzes exchanging goods-information, computation services, or other types-for payments. The exchange proceeds on two axis: the portion of goods of the contract delivered by exchange step n is called :X:n E [0, 1], and the cumulative payment so far is Pn E [O,pcontr]. pcontr is the total payment specified in the contract. The agents can make simultaneous moves and they observe the other agent's moves so far. They value the goods :x: according to nondecreasing functions that are in equivalent units of payment p. The supplier's value function v, ( :x:) describes how much cost the sup­ plier incurs by generating and delivering :x:. The deman­ der's value function vd( :z:) describes what the goods :z: are worth to the demander. Trivially, v,(O) = vd(O) = 0.

At any point in an exchange, an agent has the options of defecting or cooperating. Defecting gives no added gains that have not already been received (when already accounting for the opponent's move on the current step of the exchange) and no added costs, so its net benefit is 0. Therefore a net benefit maximizing supplier agent will cooperate throughout the rest of the exchange from an arbitrary point ( :z:, p) of the exchange if its future compensation is at least as great as its future cost 2 , i.e. pcontr -p ~ v,(1) -v,(x). This assumes that the deman­ der will actually finally increase cumulative payment to pcontr. An equilibrium analysis with respect to this is­ sue will be presented shortly. To facilitate that analysis, pmcu: ( :z:) is defined based on the above intuition:

A rational demander agent will cooperate throughout the rest of the exchange from an arbitrary point ( x, p) if the future compensation it has to pay is smaller than or equal to its added value, i.e. pcontr- p ~ vd(l)- vd(:z:). This assumes that the supplier will finally increase total delivery to 1, which will be shown to be an equilibrium shortly. Now, pmin ( :z:) is defined, Fig. 1 left:

Clearly, pma: ( :z:) and pmin ( :z:) are nondecreasing in :z:. For the supplier to have agreed to the contract, · pm""'(O) ~ 0, and for the demander, pmin(O) ~ 0.

If the agents do not know each other's value functions, they can use bounds they know. The supplier is safe using an upper bound for pmin(:z:), i.e. a lower bound for vd(1) and an upper bound for vd(x). The deman­ der is safe using a lower bound for pm""' ( :z:). Although the agents are safe using these bounds, even possible ex­ changes are disabled if the bounds are too far off.

The next sections present an equilibrium study of when safe exchange can actually occur. The analysis is slightly different for discrete and continuous goods.

2.1 Discrete goods

Discrete goods are goods that are inherently split into atomic chunks. Such chunks cannot be further split, and we assume in this section that the delivery order of the chunks is fixed. For example in the TRACONET (TRAnsportation COoperation NET) multiagent sys­ tem [Sandholm, 1993], agents representing dispatch cen­ ters negotiated over who's vehicles should transport which parcels. Taking care of one parcel is an atomic chunk because the task cannot be split. Sometimes a contract between two agents involved multiple tasks (in order to avoid local optima in distributed task alloca­ tion [Sandholm, 1993]) so the total exchange could have been split into smaller parts. The following theorems de­ scribe the conditions for safe exchange of discrete goods.

2 If equality holds, the agent is indifferent between cooper­ ating and defecting. Throughout this paper we assume that indifferent agents will cooperate. Note also that throughout the paper we analyze only remaining payoffs, not total pay­ offs, because the already incurred payoffs are constant with respect to the remaining game.

Definition 2.1 Supplier's strategy S,: At any point of the exchange, if Pn ::S pmax ( Xn) deliver an amount such that cumulative delivery Xn+l = max{ x E X !Pmin ( x) ::S Pn} · lfpn > pm""'(xn), exit.

Definition 2.2 Demander's strategy Sd: At any point of the exchange, if Pn ;::: pmin(xn), pay an amount such that cumulative payment Pn+l = pm""'(xn)· If Pn < pmin(xn), exit.

Theor.em 2.1 3 With a finite number of discrete goods (discrete X C [0, 1]), for nondecreasing pmin ( x) and pmax (X) I the strategies S, and sd form a subgame perfect Nash equilibrium if for every two consecutive amounts of cumulative delivery x, x' EX, pm""'(x) ;::: pmin(x'). 4 Furthermore, the exchange is completed. Fig. 1 middle.

Theorem 2.2 With a finite number of discrete goods (discrete X C [0, 1]}, for nondecreasing pmin(x) and pmax ( x), there is no subgame perfect Nash equilibrium leading to completion of the exchange if for some two consecutive amounts of cumulative delivery x, x' E X, pm""'(x) < p=in(x'). See Fig. 1 right.

Nash equilibrium [Nash, 1950; Kreps, 1990] means that each agent is motivated to abide to its speci­ fied strategy given that the other agent abides to its specified strategy. Subgame perfection [Selten, 1965; Kreps, 1990] means that the equilibrium is a Nash equi­ librium at any point (xn,Pn) of the exchange, not only the beginning of it. This means that the equilibrium re­ mains an equilibrium after the agents have partially car­ ried out the exchange. Furthermore, it is an equilibrium at points ( x, p) of the exchange that will actually not be reached by the agents in the exchange process. For these reasons, subgame perfection precludes incredible threats/promises and provides some robustness against external perturbances.

From the condition p 771 ""' ( x) ;::: p=in ( x') and the fact that pmin ( x) is nondecreasing we see that the following has to hold for safe exchange: p 771 ""'(x) ;::: pmin(x). In terms of the agents' value functions this can be writ­ ten as vd(x)- v,(x) :::; vd(1)- v,(1). This means that the agents' combined profit must be higher (or equal) at x = 1 than at any other x E [0, 1[. If the agents would have been better off by making the contract for a smaller amount of goods, an isolated safe exchange is impossible. Furthermore, at x = 0 this gives v,(1) ::S vd(1), which is an intuitive condition for the contract to have been made in the first place. Specifically, v,(l) :S pcontT :S vd(l), Fig. 1 left.

3 Proofs of the theorems are omitted due to limited space. They will be published in an extended version of this paper.

4 The equilibria in Theorems 2.1, 2.3, 4.1 and 4.2 are not unique. For example, the strategies that specify that the demander never pays anything and the supplier never delivers anything at any point of the exchange also form a subgame perfect Nash equilibrium.

Theorems 2.1 and 2.2 state that rather stringent con­ ditions have to be met to enable unenforced isolated exchange of discrete goods. Substituting x = 1 in the definitions of p 771 ""' ( x) and p=in ( x) gives p 771 ""' ( 1) = pm·n ( 1) = pccm.tT . According to the theorems, safe ex­ change is possible only if p 771 ""' ( x) ;::: pmin ( x') for any two consecutive x and x'. Let us call the size of the last delivery ll.x. So for safe exchange the following has to hold: p 771 ""' (1 - ll.x) ;::: p=in (1) = p 771 ""' ( 1). Thus the in­ creasing function p 771 ""' ( x) has to be constant during the last step (Fig. 1 middle). This means that the supplier's. value function v,(x) is constant. So an isolated safe ex­ change is possible only if the supplier does not incur any cost from generating and delivering the last chunk. This occurs for example when the supplier has had to acquire a number of the last deliverables atomically. Its cost of acquiring the deliverables can be entirely attributed to the first one, while it can deliver these items separately with only the first one increasing v, ( x) (assuming negli­ gible costs of physically delivering). This may not occur very often in practise (Fig. 1 right). Intuitively, when there is no future benefit to be gained from exchanging, agents are better off defecting on the current move.

If this problem occurs ·in an isolated exchange of a finite number of discrete goods, it spoils the entire ex­ change. On the last move the supplier does not want to increase delivery to x = 1, because the demander would defect. Similarly, the demander does not want to increase cumulative payment above p 771 ""' (1 - ll.x), be­ cause the supplier would defect . Both agents know that the last part of the exchange will not take place due to this. So they can analyze the exchange as if it did not have the last part. Now the second to last part has the same problem (unless the supplier can deliver that part without cost): neither agent wants to initiate that part .. Again, both agents know this and so on. This backward induction can be carried out up to the first exchange. So, neither agent will make any move, and the exchange will not take place. Theoretically, there can be an in­ finite number of discrete goods. In such cases this ex­ change spoiling backward induction argument does not apply because at no point can an agent say that the next move is the last . Backward induction is inapplicable also with continuous goods. This facilitates safe unenforced exchange of continuous goods, as discussed in the next section. In both the discrete and the continuous case, the problem of requiring that the supplier can deliver the last part without costs can be overcome by consid­ ering related future interactions of the agent, Sec. 3.

2.2 Continuous goods

This section analyzes the exchange of continuous goods, i.e. goods that can be split arbitrarily. First, two con­ ditions for safe exchange are presented. Intuitively, the first one states the conditions under which a safe ex­ change can proceed to some amount of cumulative de­ livery. The second one states the conditions under which safe exchange can proceed from some amount of cumu­ lative delivery.

Condition 2.1 Reachability. (Fig. 2} For every point x· E )0, 1),

1. pma:z: ( x·) = pmin ( x·) , and pmao: ( x) is constant in some left neighborhood of x·, or
2. pma"'(x*) > pmin ( x*), and lim,-+:z:·- pm 11 "'(x) > pmm(x*), or
3. pma"'(x*) > pmin(x*), li ma:z: ( ) m:z:-+:z:·- p X pm·n ( x·) 1 and pm 11 "'(x) ~s constant ~n some left neighborhood of x·.

Condition 2.2 Departability. (Fig. 3) For every point x· E [0, 1 [,

1. pm 11 "'(x*) = pmin(x*) , and pmin(x) is constant m some right neighborhood of x·, or
2. pma:z:(x*) > pmin(x*), and lim,-+,·+ pmin(x) < pma:z: ( x· ), or
3. pma"'(x*) > pmin(x*~, pma:z:(x*), and pmm(x) u neighborhood of x·. lim:z:-+o:·+ Pmin(x) constant in some right

Theorem 2.3 With continuous goods (X = [0, 1]}, for nondecreasing pmin ( x) and pma:z: ( x), the strategies S, and Sd form a subgame perfect Nash equilibrium if con­ ditions 2.1 and 2.2 hold. Furthermore, the exchange is completed.

Theorem 2.4 With continuous goods (X = [0, 1]), for non decreasing pmm ( x) and pmao: ( x), there is no subgame perfect Nash equilibrium leading to the completion of the exchange if conditions 2.1 and 2.2 do not hold.

Theorems 2.3 and 2.4 state that isolated unenforced exchange of continuous goods is safe if some initial deliv­ ery can be made, every intermediate amount of delivery can be reached and departed, and the final amount of de­ livery can be reached without exceeding pm 11 "(x) or mov­ ing below pmin ( x). These theorems do not assume conti­ nuity ofpm 11 "(x) (equivalently v,(x)) or pmin(x) (equiv­ alently vd(x)). Neither do they assume that pm 11 "'(x) or pmin(x) is strictly increasing. If pm 11 "'(x) and pmin(x)

are continuous, the exchange can be carried out safely if and only if V:x E [0, 1], either pm 11 "'(x) > pmin(x) or pma:z: ( x) = pmm ( x) and pma:z: ( x) is constant in a left neighborhood of x and pmin ( x) is constant in a right neighborhood of x. If in addition to continuity, pma:z: ( x) and pm·n ( x) are strictly increasing, the exchange can be made safely if and only ifV:x E [0, 1),pm 11 "'(x) > pmin(x) . Isolated safe exchange can be problematic also in the case of continuous goods. Substituting x = 1 into the definitions of pma:z: ( x) and pmin ( x), we see that pma:z: (1) = pcontr = pmm ( 1). From case 1 of condi­ tion 2.1 we see that full delivery ( x = 1) can be reached only if pm 11 "'(x) is constant in some left neighborhood of x = 1. If the value function of the supplier v,(x) is not. constant in the end of the exchange, the exchange cannot be completed. So an isolated safe exchange is possible only if the supplier does not incur any cost from gener­ ating and delivering the last portion of the goods, which was discussed in Section 2.1. This problem is less severe than in the case of finitely many discrete goods because the size of the deliveries can be made decreasing and arbitrarily small-thus making the number of deliveries infinite (Fig. 1 left). This allows the agents to reach a cumulative delivery that is arbitrarily close to 1 because the backward induction argument that disabled the en­ tire exchange in the case of discrete goods does not hold. There is no particular exchange step at which the agents could reason that neither will make a move.

3 Extension 1: Non-isolated exchange

Often an agent interacts with other agents more than once. One interaction may affect the agent's future in­ teractions. For example, if an agent defects in the cur­ rent exchange, its counterpart may not want to take on future contracts with that agent. Moreover, the coun­ terpart can notify other agents that the agent defected. Thus, the agent's interactions with third parties may also be hindered by defecting in the current exchange. The' hindering future impact of a defection can be thought of as an extra cost. This future cost may motivate agents to cooperate in the current exchange even if it would be rational to defect in it when considered in isolation. The methods for calculating defection impacts on the future are beyond the scope of this paper. We assume that both agents know their own and their opponent's defection costs. We denote the supplier's defection cost by c~·f and the demander's by c~·f. The defection costs can be incorporated into the model by redefining pmao: ( x) and pmin(x), Fig. 4:

Pmin' (x) d2 Pcontr- vd(1) + vd(x)- c~·f. (4) In isolated exchange, substituting x = 1 in the defini­ tions of Pma:z:(x) and Pmin(x) gave Pmin(1) = Pcontr = pm 11 "(1). This led to the problem that the exchange could not be carried out to completion-unless pma:z: ( x) was constant in the end of the exchange. In non­ isolated exchange, substituting x = 1 gives pmin' (1) = pcontr- c~·f and pma:z:' ( x) = pcontr + c~·f. The defection penalties give leeway to the exchange, thus possibly en­ abling safe exchange to be completed even if pma:z: ( x) is not constant in the end. The contract price pcant· could be exceeded due to this leeway. To avoid this, the deman­ der's strategy can be modified so that at any point in the exchange, the demander increases cumulative payment to min(pcont·,pma.:'(x)) instead ofpma.:'(:z:). This will not hinder exchange, because the condition takes effect after the full contract price has been paid. Non-isolated exchange is more fruitful than isolated exchange, because it facilitates safe completion. The theorems on the pos­ sibilities of subgame perfect Nash equilibrium exchange ( 2.1, 2.2, 2.3, and 2.4) apply directly to the case of non­ isolated exchange with the new definitions pma.:' ( :z:) and pmin'(:z:) substituted in place of pm"'"'(:z:) and pmin(:z:), and the minor modification in the demander's strategy.

If the agent does not know the defection cost of the opponent, it can use a lower bound for that cost. This way the agent is safe, but if the bound is too far off, even possible exchanges are disabled.

4 Extension 2: The role of time

This section addresses real time in the exchange: will an exchange take place immediately, or will it be infinitely postponed, or something in between? Nonincreasing dis­ count functions f(tn), (0 :::; f(tn) :::; 1, f(O) = 1) are assumed. Subscripts s and d distinguish between the supplier and the demander, and superscripts p and v characterize whether the discount applies to payment or the value of goods. For example, using constant inter­ est rate ( r) compounded interest, the discount function is f(tn) = e-·t,.. First, the role of time in isolated ex­ change is analyzed. Real time is incorporated into the model by allowing the agents to postpone their moves. During the time that one agent is postponing, the other agent can make a delivery or a payment, at which point the first agent can redecide its postponing decision. The players' strategies are redefined to handle time:

Definition 4.1 Supplier's strategy S!imed: At any point of the exchange, immediately deliver an amount such that cumulative delivery :Z:n+l = max{x E Xjpmin(x) :::; Pn} if Pn S Pma.z ( Xn) . Exit if Pn > Pma.z ( Xn) .

Definition 4.2 Demander's strategy S~imed: At any point of the exchange, immediately pay an amount such tha.t cumulative payment Pn+l = pm"'"'(xn)· Exit if Pmm(xn) > Pn·

The following theorem states that neither agent is mo­ tivated to unilaterally deviate from immediate exchange if certain conditions hold on the discount factors.

Theorem 4.1 With a finite number of discrete goods (discrete X C [0, 1]}, for nondecreasing pmin(x) and pma.z (X)' the strategies S!·med and s~·med form a Nash equilibrium if for every two consecutive amounts of cu-. mulative delivery :z: and x', pm"'"'(x) ~ pmin(x'), and Vtn ~ 0, ff ( tn) S J: ( tn), f~ ( tn) ~ Jd ( tn), The equi­ librium is a Nash equilibrium in every subgame that is reached and the exchange is completed immediately.

So, isolated unenforced exchange is feasible if the sup­ plier discounts payments more sharply (or equally) than production costs and the demander discounts the value of goods more sharply (or equally) than payment. The condition on the supplier's discount functions is rather natural. For example in a stable environment, the sup­ plier's current value of producing an item should remain constant, but obviously payment is discounted. The condition on the demander's discount functions is more stringent. It is realistic in the case where the deman­ der needs the goods urgently. An agent need not know the opponent's exact discount functions. It is sufficient to know whether they fulfill the conditions. The equi­ librium concept of the theorem is slightly weaker than subgame perfection because it only guarantees that the equilibrium is a Nash equilibrium in subgames that are reached-not all subgames. In practise this means that if, for some unknown reason, the exchange has been de­ layed, it is not guaranteed that the agents are motivated to proceed immediately or at all. For example, in a sub-. game where ff(tn) = 0, J:(tn) > 0 for the current tn, the supplier is not motivated to proceed immediately be­ cause no payment by the demander can compensate for any cost incurred by the supplier's delivering.

Clearly, by Theorem 2.2, immediate exchange is not possible if the condition on the consecutive x's does not hold. Similarly, by Theorem 2.4, immediate exchange is not possible with continuous goods if conditions 2.1 (reachability) and 2.2 (departability) do not hold. If they do hold, immediate exchange is possible also in the continuous case:

Theorem 4.2 With continuous goods (X = (0, 1]}, for_ nondecreasing fmin ( x) and pma.z ( x), the strategies S!'med and s~·m· form a Nash equilibrium if con­ ditions 2.1 and 2.2 hold, and Vtn ~ 0, ff(tn) :::; J: ( tn), f: ( tn) ~ fd (tn). Furthermore, the equilibrium is a Nash equilibrium in every subgame that is reached and the exchange is completed immediately.

If the conditions on the discount functions do not hold, the outcomes vary. For example, a supplier wants to carry out the exchange at a time tn when its ff(tn) is high and r, ( tn) is low. This may or may not coincide with the time when the demander wants to move. The exact forms of the discount functions define whether the· exchange can be carried out in equilibrium immediately, by slightly postponing (different moves in the exchange may be postponed different amounts), or only by post­ poning indefinitely.

Next, it is shown that time discounts reduce the ad­ vantages of non-isolated exchange. We assume that the current value of each agent's defection cost does not change-which seems realistic. If an agent discounts payments, this means that its absolute value of the de­ fection cost increases with time. The following theorem states that with certain types of discount functions, the exchange cannot proceed outside of the region of isolated exchange (I in Fig. 4) without being delayed. The result that the discount factors on payments need to reach 0 usually means that the delay is indefinitely long. Thus, in such settings, taking advantage of the defection penal­ ties of non-isolated exchange (by moving into region N in Fig. 4) to facilitate safe exchange is usually infeasible. Intuitively, an agent wants to postpone a negative net benefit into the future where it is heavily discounted.

Theorem 4.3 If limt-+oo J: (t) = 0 in any subgame where pmaz (x,.) < Pn :::; pmaz' ( x,.) I and Vt 2: t,., Jr(t) :::; f: ( t), there is no subgame perfect Nash equilibrium that results in reaching (1, pccmtr) before (supplier's) de­ lays have caused J:(t) = ff(t) = 0. Similarly, if limt-+oofHt) = 0 in any subgame where pmin' (x,.) :::; p,. < pmin(x,.), and Vt 2: t,., f:(t) 2: fd(t), there is no subgame perfect Nash equilibrium that results in reach­ ing (1, pcontr) before (demander's) delays have caused f:(t) = !J(t) = 0.

The conditions limt-+oo f:(t) = 0 and ff(t) :::; J:(t) are almost always true. The condition f:(t) 2: fd(t) is true if the demander needs the goods urgently. The supplier's discount function for its goods need not ap­ proach 0 however. Its cost of producing goods (dis­ counted to present) may not even decrease with the pro­ duction date. This may sometimes allow the demander to facilitate exchange by safely over-paying and moving into the upper region N in Figure 4.

The negative result (Theorem 4.3) stems from not con­ sidering indefinite postponing a violation of the contract. This can be changed by specifying deadlines or lateness penalty schedules for the agents in the contract . If the contract i_ - ~t abided to (e.g. deadlines not honored or lateness pena.t, ..... not paid), the defecting agent will suffer the defection penalty (c~·J or c~" 1 ) due to how its de­ fection will affect its future contracts. So, strictly speak­ ing a contract matters only in non-isolated exchange, and therefore forcing timely exchange by deadlines or lateness penalties is possible only in such cases. This highlights the value of Theorems 4.1 and 4.2 for isolated exchange that guarantee that immediate exchange is an equilibrium and does not need to be forced. Even in non-isolated exchange, deadlines and lateness penalties are meaningful only as long as abiding to the deadline or paying the lateness penalty is less expensive than suf­ fering the defection penalty. Lateness penalty schedules are preferable to strict deadlines because they are less risky for the agent who is potentially subject to them, but the other agent can still tailor the lateness penalty schedule to motivate the former to move immediately.

5 Extension 3: Delivery sequencing

So far we have discussed exchanges in which the deliv­ ering order of the goods is fixed beforehand. In this section we analyze an exchange where discrete partial deliveries (individual goods or atomic chunk~) can be delivered in any order, as long as all of them get deliv·· ered. It is assumed (this is relaxed in Section 5.1) that the demander's added value from one chunk does not de­ pend on the other chunks delivered so far, and that the supplier's cost for delivering a chunk does not depend on other chunks delivered earlier. This enables us to asso­ ciate each chunk c with two values, !:::.prz' 11 "' and !:::.prz'i", that fully characterize how much the maximum and the minimum cumulative payments change as c is delivered.

For example, an agent could make a contract to carry out a number of matrix multiplications. Multiplying two matrices neither facilitates nor hinders multiplying some other two, so the chunks are independent with respect to the supplier. The chunks are truly independent if they are independent with respect to the demander also­ based on the uses of the multiplication results.

Call a delivery sequence safe if min(pmaz ( x), pcontr) 2: pm"'( x') for all consequtive x and x'. We provide a fast greedy algorithm that finds a safe ordering if one exists . . The algorithm takes six inputs: a set of chunks C, a vector of !:::.prz' 11 "' values, a vector of !:::.prz'in values, the contract price pcontr, and the defection penalties (c~·J = c~·! = 0 in the case of isolated exchange).

Algorithm 5.1 SEQUENCE-CHUNKS(C,

.6-pmaz .6-pmin pcontr cd·J cd·J; J J I I I d

• 1 p~~"' = pcontr + cd·J pmi_n = pcontr - cdef · tntt 1 1 tntt d ·
• For every c inC do I* Sets bounds for pat x = 0 *I Pini: = Pini: - !:::.prz'a"', Pin~~ = Pin~~ - !:::.prz'in.
• If Pini: < 0 or Pin~~ > 0 return "NO SOLUTION".
• Divide C into two sets POS and NEG s.t. POS = {c E Cj!:::.prz'...,- !:::.pr;'i~ 2: 0} and NEG= {c E Cj!:::.prz' 11 "' - t::.pr;''" < 0} .
• pmaz - p~~"' pmin - p~i.n n - IPOSI ·rL - IN EGI - 1ntt 1 - uut, Pt """n-
• Fori = 1 to np
• F EASIBLES = {c E POSjpmin+t::.p';'i":::; pmaz} IfF EASIBLES = 0 return "NO SOLUTION". c· = argmax !:::.p';' 11 "' - !:::.pr;'in. cEJI'BA.SIBLBS chunk[i] = c·. pmaz = pmaz + !:::.p~az 1 pmin = pmin + !:::.p~in . POS = POS- {c*}.
• pmaz = pcontr + c~·J' pmin = pcontr - c~·J .
• FEASIBLES = {c E NEGjpmin:::; pmu_!:::.prz'a"'} IfF EASIBLES = 0 return "NO SOLUTION". c· = argmax !:::.prz''" - !:::.prz' 11 "'.

1. Fori = n,. + n, down ton,+ 1 cEJI'BASIBLBS chunk[i] = c·.
2. Return the ordered vector "chunk". First chunk to be delivered is in "chunk[!]" .

Step 6 of the algorithm sequences the chunks with posi­ tive !:::.prz' 11 "' - !:::.prz'in in a forward passing greedy manner to try to increase pmaz as much as possible while increas­ ing pmin as little as possible. Intuitively, the algorithm tries to ma.x1m1ze the range of possible safe prices at each :z: . Step 7 just computes pmaz and pmin at the end of the whole sequence of chunks. Step 8 makes a greedy backward pass. It tries to allocate the chunks with neg­ ative t.p';a"' - t.p';in so as to use as little as possible of the beneficial difference t.p';a"' - t.p';in in the end of the sequence. Intuitively, this difference is saved for the middle of the sequence, from where it has time to affect more chunks (lying later in the sequence).

To solve our sequencing problem, we tried several greedy algorithms starting with the intuitive ones. Most of them do not guarantee that a safe sequence is found even if one exists. For example, the algorithms that greedily pass only forward and maximize t.p';a"'-t.p';in or minimize t.p';in can be defeated by counterexamples with just two chunks. Our algorithm cannot be defeated:

Theorem 5.1 Algorithm 5.1 finds a safe ordering if one exists and always terminates in O(ICI 2 ) time.

Sometimes the division of the exchange into chunks is not externally fixed but can be decided by the agents, e.g. at contract time. This can be done top down by gen­ erating a chunking and then testing its safety by running algorithm 5.1. If it is not safe, the chunking can be re­ fined by splitting chunks further . Splitting is monotonic in the sense that no split can make a safe exchange un­ safe. Therefore this splitting algorithm does not need to backtrack. The top down method can be used for con­ tinuous goods also. The minus side of the approach is the need to guess the splits. If they are guessed badly, possibly many more chunks are generated than are nec­ essary to enable safe exchange. A bottom up approach for chunking is to sequence the smallest possible atomic chunks using algorithm 5.1. Next, the agents can see how many atomic chunks they can deliver at once at each step without changing the order and while still keeping the exchange safe. Bottom up chunking requires no guess­ ing of splits but it can be computationally complex if the number of smallest possible chunks is large. It cannot be applied to continuous goods because the number of smallest possible chunks is infinite.

5.1 Sequencing interdependent deliveries

Sometimes partial deliveries are interdependent . The value of a chunk may depend on which chunks have been delivered before it. For example in manufactur­ ing, the first products can be thought of as more costly than subsequent ones because the fixed costs (e.g. rent, acquired equipment) can be associated with the earlier products. Similarly, a data retrieval agent may incur large costs in searching for certain information. Once the information is found, subsequent searches of related information are less expensive. The demander may also value a chunk differently depending on the other chunks delivered so far . In TRACONET (see Section 2.1), the chunks (transport tasks) were interdependent for both the supplier and the demander. Transporting a parcel often affects the marginal cost of transporting others. For example, a vehicle may be able to carry two parcels to adjacent locations, thus reducing the marginal cost of both tasks. Conversely, one parcel may fill up the vehicle so that another task must be handled by a more costly vehicle. Some contracts involved multiple tasks. So if the safe exchange mechanisms of this paper had been used, sequencing of interdependent chunks would have been required. This was not crucial because the agents represented real world dispatch centers whose contracts were enforced by law.

In general, interdependent goods cannot be sequenced in polynomial time in the number of chunks if it is re­ quired that a safe solution is found if one exists. Just . representing the problem requires 0(2ICI) space because for each set of chunks in the power set of all chunks, pmaz and pmsn have to be represented-and in the worst case this information cannot be compressed. Neverthe­ less, if the number of chunks per contract is small-as in TRACONET-exponential search among sequences of chunks is viable. In such cases the advantages of safe unenforced exchange outweigh the extra computational load. Furthermore, special cases of the problem may be solvable in polynomial time, e.g. the case of independent chunks discussed earlier.

6 Renegotiation risk

After an irrevocable delivery or payment, the agent that gained from it may want to renegotiate the contract. For example after the first partial delivery, the demander may want to renegotiate t.he contract for a lower price. The demander knows that the original contract price was safe for the supplier, so now that the supplier has already "lost" the first delivery, the supplier should be willing to carry out the rest of the exchange at a lower price. On the other hand, the supplier knows that any point in the exchange is safe for the demander. Therefore, if the supplier can commit to not renegotiating, the demander is motivated to follow the original contract and to not vanish.

Renegotiation is more likely in unsafe exchange [Lax and Sebenius, 1981; Rai.ffa, 1982]. For example, when an international company initiates a mining venture in a developing country, it has to invest most of the capi­ tal up-front. This unsafe move motivates the developing country to renegotiate the conditions of the mining ven­ ture (profit division etc.). Due to expropriation risk the company cannot avoid renegotiation.

7 Conclusions and future research

This paper presented a method for carrying out mutual exchanges among self-motivated agents without third party enforcement. Larger exchanges were split into smaller parts so that at no point was either agent moti­ vated to defect (in equilibrium) . The maximum size de­ livery that the supplier can safely make at any point in the exchange was shown as well as the maximum amount that the demander can safely pay. The possibility of safe exchange depends on the demander agent's and the sup­ plier agent's value functions for the goods ofthe contract. Safe exchange is enhanced if the supplier incurs most of its cost from the early portion of the exchange, while the possibility that the demander acquires most of its value· already from the early parts hinders safe exchange.

Isolated safe exchange can be carried out entirely only if the supplier can deliver the last part without cost.

With continuous goods it can be carried out arbitrarily close to completion even if this is not the case. Con­ sidering defection's adverse effect on future negotiations often enables completing the exchange.

Under the presented conditions on their discount func­ tions, agents are motivated to carry out isolated ex­ changes immediately. Time discounts reduce the via­ bility of taking advantage of non-isolated exchange. In such cases, immediate moves can be forced by deadlines or lateness penalties.

Some domains allow goods to be delivered in differ­ ent orders. The presented quadratic algorithm . finds a safe ordering for independent goods if one exists. The problem cannot be solved in polynomial time for inter­ dependent goods. Finally, we showed that safe exchange helps prevent unfair renegotiation.

In this paper we looked at totally safe exchanges, where each agent knew its opponent's value function, discount functions, and defection penalty (i.e. cost of making reputation worse). We explained how agents could use bounds for these if they are not exactly known. If the bounds were too far off, even possible exchanges were disabled. Often it is the case that agents can es­ timate a distribution for each of these, although strict bounds are not available or they are too far off. Using these distributions the agents can take a calculated risk of making moves that are unsafe with a certain proba­ bility. This approach of using distributions is also useful to the agent in trying to model the possibility of changes in the opponent 's value function, discount functions or defection penalty that happen during the exchange due to the opponent interacting in its environment (getting other offers, contracts etc.).

Another approach is to try to bound ones losses by making the partial exchanges small enough so that even if the opponent defects, the loss will be within a bound. In both the probabilistic risk method and the loss bound­ ing method there is a tradeoff between making the ex­ change safer by using small partial exchanges and mini­ mizing partitioning costs (e.g. physical per part delivery costs) by using large ones. Finally, either a probabilis­ tic approach or a loss bounding approach can be used to address the risk of the opponent accidentally defecting­ e.g. loosing contact due to a technical fault .

Acknowledgments

We thank Prof. Neil Immerman (Umass Comp Sci) for the backward pass idea for algorithm 5.1, and Prof. Herb Gintis (Umass Economics) for game theoretic comments.