Planning Games

1 Introduction

Work in domain-independent AI planning has made substantial progress in recent years - today, we can efficiently solve sophisticated problems of varying expressivity, and we better understand the relationship between the problem structure and the worst-case time complexity of solving it. Much progress has been made in the area of multi-agent (MA) systems as well: great performance improvements have been achieved in various concrete domains, and computational game theory became an important theoretical basis for MA systems research. Still, multi-agent planning seems to lack simple generic models that extend the basic single-agent STRIPS planning model (and its various off-springs) with appropriate game-theoretic constructs.

An obvious difference between single-agent planning and multi-agent planning is that each agent brings into a MA system its own abilities, and together the agents are able to achieve more than they could achieve in isolation. Even the basic setting of a fully cooperative MA system, where the goal definition remains similar to that of single-agent planning, raises interesting computational questions, some of which have been explored within the scope of the multi-entity model [Moses and Tennenholtz, 1995] and MA-STRIPS planning [Brafman and Domshlak, 2008]. More so, when agents are self-interested, immediate and well known complications arise, and additional structure is needed.

Moshe Tennenholtz Microsoft Israel R&D Center & Technion-IIT moshet@microsoft.com

The first issue is modeling the personal costs and benefits of each agent. The cost is naturally captured by the total cost of the actions carried out by the agent. The benefit component is less obvious: the agents may either attempt to achieve a joint goal that has some (possibly different) value to each agent, or they may pursue individual goals. The second issue is that of the solution concept. In contrast to MA planning for fully cooperative agents, the solution concept is no longer obvious once the agents are self-interested. For instance, if agent ϕ prefers plan π to plan π′ , while agent ϕ′ prefers plan π′ to plan π, which plan should be chosen for the system? What should be criteria for selecting one solution among a set of possible solutions is the basic question tackled in gametheory; this suggests incorporating some game-theoretic ideas in planning models.

Previous work have considered planning for self-interested agents in fully adversarial settings (e.g., [Ben Larbi et al., 2007; Bowling et al., 2003]). In contrast, we consider MA planning for self-interested, yet ready to cooperate agents. We approach this problem both conceptually and computationally. The challenge here is to define natural classes of strategic games and respective solution concepts that properly capture the context of MA planning. We suggest two basic models corresponding to variants of what we call planning games. The precise strategy space vary between the two models, but in both, each strategy is a course of action of a single agent (referred as local plan), and a joint strategy is a multi-agent plan of the whole system.

In our first model, called coalition-planning games, each agent has its own goal, as well as a set of actions it is able to perform. To achieve its goal, an agent may either need, or just find it cost-efficient, to be assisted by some other agents. The question is, when would a coalition of agents work jointly to achieve their individual goals without being tempted to do something else. In other words, under what conditions a plan for such a MA system will be stable? We consider a coalition's joint plan to be stable if no subset of its agents would benefit by joining an alternative coalition. Capturing the specifics of planning agents, this concept is in the spirit both of the strong equilibrium in non-cooperative games [Aumann, 1959], and of the core in Non-TransferableUtility (NTU) cooperative games [Aumann and Pelleg, 1960].

Our second model, called auction-planning games, captures problems in which coalitions of agents compete for the achievement of a single goal which yields a monetary reward. For instance, consider an auction in which coalitions bid for a construction contract. Such a coalition must not only be able to achieve the goal, but also have a winning bid. Moreover, its members should have no reason to switch to another coalition. Capturing all that, our concept of stable solutions is in the spirit of the classical core [von Neumann and Morgenstern, 1944], yet adapted to the strategic setting of selfinterested planning agents.

Planning games address many realistic problems in which the complexity of the domain stems from the interplay of game-theoretic and planning issues. However, planning games also contributes to computational game-theory; by introducing new structures of agent interaction that go beyond the previous work on local structure in games (e.g. [Kearns and Littman, 2001; Leyton-Brown and Tennenholtz, 2003; Ieong and Shoham, 2005]). In graphical games, for instance, the payoff of each agent depends on a small number of neighboring agents [Kearns and Littman, 2001]. In contrast, in planning games each agent can depend indirectly on every other agent, because the outcome of a joint plan depends on all agents participating in it. Despite that, for both types of planning games, we show that when a certain graphical structure induced by the system is acyclic, stable plans can be found in time polynomial in the description size of the MA system.

2 Background

We assume familiarity with the basic concepts of AI planning, and in particular, the STRIPS formalism. Our formalism and algorithms build upon the work of Brafman and Domshlak [2008] (BD, for short) who investigated the worstcase time complexity of planning for cooperative MA systems. BD introduce a minimal extension of STRIPS to the cooperative MA setting. A MA-STRIPS problem for a system of agents Φ = {ϕi}ki=1 is given by a 4-tuple Π = 〈P, {Ai}ki=1 , I,G〉 where P is a finite set of atoms, I ⊆ P and G ⊆ P encode the initial state and goal, respectively, and, for 1 ≤ i ≤ k, Ai is the set of actions that agent ϕi is capable of performing. Each action a ∈ A = ⋃ Ai has the STRIPS syntax and semantics; a = 〈pre(a), add(a), del(a)〉 is given by its preconditions, add effects, and delete effects.

BD make the simple agents assumption that the (suitably formalized) local planning problem of each agent can be solved in polynomial time. In this case, the sole cause of complexity of MA planning stems from the interactions between agents. Intuitively, if the agents are completely independent, then MA planning reduces to multiple independent singleagent planning problems, and consequently, the overall time complexity is linear in the number of agents. However, if the MA system is strongly coupled, the complexity might be exponential in the number of agents. BD identify a concrete, quantifiable parameter of the MA system that captures its degree of coupling, and show that any MA-STRIPS problem can be compiled into a constraint satisfaction problem (CSP), efficiently solvable when that parameter's value is not too high.

We adopt and, for ease of presentation further strengthen the simple agents assumption, requiring each agent's plan to be bounded in length. This simplifies some technicalities, allowing us to focus on the game-theoretic constructions; all our results extend with no complications to simple agents with unbounded local plans. Moreover, the key computational questions remain-the size of the joint plans grows linearly, and thus the size of the plan space grows exponentially with the number of agents.

We highlight the following technical details of BD's compilation of a planning problem Π into a CSP.

• (a) The CSP of Π is defined over variables bijectively corresponding to the agents Φ, with the variable domain D(ϕ) containing sequences of annotated actions, bounded in length by a fixed δ.
• (b) Each annotated action of agent ϕi is a tuple (a, t, {(j1, t1), . . . , (jm, tm)}) where a ∈ Ai, t and all ti are time points, and each ji is an identity of some other agent. The semantics of such a tuple is "at time t, ϕi will perform action a, and it requires agents ϕjl to provide the jl-th precondition of a at time tjl ."
• (c) There are unary and binary constraints. Each unary constraint ensures that a sequence of annotated actions is self-consistent. That is, if one annotated action of ϕ requires it to supply itself with some precondition, then another annotated action in the sequence must produce this precondition at the right time. Such self-consistent sequences of annotated actions are called the agent's strategies. Strategies may include less than δ actions; in particular, we use ⊥ (the null strategy) to denote an empty sequence. The binary constraints capture inter-agent dependencies. θ ∈ D(ϕ) and θ′ ∈ D(ϕ′ ) satisfy their constraint if whenever θ′ requires a precondition by ϕ at time t, θ contains an action producing this precondition at t, and vice versa. In that case, we say that θ and θ′ match.
• (d) The constraint network induced by that CSP is isomorphic to the agent interaction graph (AIG) IGΠ in which the nodes are the agents, and there is an edge between two agents if an action of one of them either adds or deletes a precondition of some action of the other agent.

Any set of pair-wise matching strategies θ1, . . . , θk of the respective agents (that is, any solution to the CSP), constitutes a valid plan for Π. BD show that such a CSP can be solved in time exponential only in wδ, where w is the tree-width of IGΠ. In particular, if IGΠ is acyclic, then w = 1, and thus Π can be solved in time exponential only in δ, regardless of the number of agents involved.

3 Coalition-Planning Games

BD exploit the structure of the MA system to achieve tractability, within a model that assumes that agents are fully cooperative, working together to achieve a mutual goal. In many realistic settings, however, agents are self-interested, have personal goals and costs, and are motivated to act to increase their personal net benefit. Yet, because different agents may have different capabilities, they may still find it beneficial to cooperate with each other. This creates some interesting tension between their private utility maximization and the need to provide incentives to other agents whose help they desire. To capture such settings, which introduce a gametheoretic flavor into the planning problem, we consider a minimal extension of the MA-STRIPS formalism to self-interested agents, which we call coalition-planning games (CoPG). MASTRIPS extended STRIPS by associating actions with agents, and CoPG extends MA-STRIPS by associating a single subgoal with each agent and associating personal costs with actions. The subgoals are associated with personal values, or reward, as well. Formally:

Definition 1 A coalition-planning game (CoPG) for a system of agents Φ is a tuple Π = 〈P, A, I, G, c, r〉 where atoms P, initial state I, and actions A are defined as in a MASTRIPS. G ⊂ P is a set of goal atoms, one per agent, with gϕ ∈ G denoting the personal goal of agent ϕ, c is an action cost function c : A → ℜ+, and r : Φ → ℜ is a function capturing the reward each agent associates with its own goal.

A joint strategy of the agents induces a (possibly parallel) plan π that contains the actions each agent performs at each time step according to its own strategy. We use π|ϕ to denote the actions of agent ϕ within π. The reward agent ϕ obtains from plan π, denoted by rϕ(π), is r(ϕ) if π achieves gϕ, and zero otherwise. The personal cost of each agent in a plan π, denoted cϕ(π), is the sum of costs of its actions in π, i.e., ∑a∈π|ϕ c(a). As π|ϕ corresponds to a strategy θ ∈ D(ϕ), we also use cϕ(·) for strategies, as in cϕ(θ). The net value of a plan π to agent ϕ (or its utility) is uϕ(π) = rϕ (π) - cϕ (π).

As common in situations where cooperation of selfish agents is required, we look for solutions which have some notion of stability. Intuitively, a solution is stable if there exists no set of agents, all of which can increase their utility by jointly adopting a different plan.

Definition 2 A solution π for a coalition-planning game Π of agents Φ is called stable iff there is no alternative plan π′ involving a subset of agents Φ′ ⊆ Φ such that uϕ(π′ ) > uϕ(π) for all ϕ ∈ Φ′ .

Roughly speaking, our definition of stability is in the spirit of strong equilibrium in non-cooperative games. A strong equilibrium [Aumann, 1959] is a strategy profile, one strategy for each agent, such that a deviation by any subset of the agents will not be beneficial to at least one of them, assuming that the other agents stick to their strategies. In a planning domain the idea of "sticking" to strategies may be problematic, since these may require pre-conditions that the deviating agents no longer supply. In our definition of stability we therefore assume that the other agents take the "null action", i.e., do not interfere with the deviation. This is consistent with the idea that a stable plan is one in which no subset of agents can "complain" that they can all do better. In the full version of this paper we also consider the case where the other agents are adversarial, i.e., they may perform arbitrary actions that could interfere with the deviating plan. The latter is similar to the notion of c-acceptable strategies defined by Aumann [1959]. These definitions are also in the spirit of the NTU-core [Aumann and Pelleg, 1960], but this concept refers to coalition outcomes rather than to strategic agent behavior.

algorithm CoPG-Acyclic(Π, Φ) input: an acyclic CoPG Π over k agents Φ output: a stable plan for Π fix a topological ordering ϕ1, . . . , ϕk over Φ for i = k down to 1: for each θ ∈ D(ϕi): if for some child ϕj of ϕi, θ has no matches in D(ϕj) then remove θ fromD(ϕi) D∗ (ϕi) = {θ ∈ D(ϕi)| θ does not require preconditions from ϕ′is parent} ˆuϕ =maxθ∈D∗(ϕ) ¯uϕ(θ) for each θ ∈ D(ϕi): if ¯uϕi (θ) < ˆuϕi then remove θ fromD(ϕi) for i = 1 to k: select θϕi ∈ D(ϕi) matching θϕj selected for the parent ϕj of ϕi merge {θϕ1 , . . . , θϕk } into a joint plan π return π

We now show that under the "simple agent" assumption discussed earlier, planning for coalition-planning games forming acyclic agent interaction graph is tractable. Our algorithm is based on the common message-passing approach for solving graphical reasoning problems such as CSPs. However, as stability does not seem to have a direct CSP interpretation, we provide a special purpose algorithm which we describe below. To simplify the presentation, we pose the (easy to drop) assumption that the goals of all the agents are different, and ϕ will be the only agent that can achieve gϕ.

The overall flow of the algorithm is similar to the two-pass algorithm for solving CSP with an acyclic constraint graph, which is conveniently viewed as a tree. At the first, bottomup phase, each node ϕ in its turn, gets a message with D(ϕ′ ) from each of its children ϕ′ , all of whom were previously processed. Given these children's domains, ϕ removes from D(ϕ) any strategy that does not match at least one strategy in the domain of each child. At the second, top-down phase, we select an arbitrary strategy θϕ of the root variable ϕ, and pass it to ϕ's children. Given θϕ, each child ϕ′ of ϕ selects a strategy θϕ′ ∈ D(ϕ′ ) that matches θϕ, and passes it to its own children. Such a matching strategy θϕ′ is guaranteed to exist, or otherwise θϕ would have been discarded at the bottom-up phase. The process proceeds this way down the tree until it reaches the leaves, and a valid plan is then straightforwardly constructed from the selected strategies {θϕi }ki=1 .

By itself, the above scheme finds a plan, but not necessarily a stable one. In order to limit the algorithm's output to stable plans, we add a stability check to the bottom-up phase, as follows. First, we define the potential utility ¯uϕ(θϕ) of agent ϕ from its strategy θϕ as ¯uϕ(θϕ) = r(ϕ) - cϕ(θϕ). It is "potential" because it is realized only if θϕ is completed to a valid plan π, in which case uϕ(π) = ¯uϕ (θϕ ).

Let D∗ (ϕ) ⊆ D(ϕ) denote the set of strategies in the pruned domain of ϕ that do not require the support of ϕ's parent. That is, all the requests (if any) to support preconditions in a strategy θϕ ∈ D∗ (ϕ) are only from the children of ϕ. Let ˆuϕ = maxθ∈D∗ (ϕ) ¯uϕ(θ). That is, ˆuϕ is the highest utility ϕ can get from a plan that does not involve any of its ancestors. We discard from D(ϕ) all strategies θ such that ¯uϕ(θ) < ˆuϕ. Note that in particular any strategy θ whose induced cost cϕ(θ) is greater than r(ϕ) is discarded, and if D∗ (ϕ) includes any strategy with induced cost lower than r(ϕ), then ⊥ is also discarded from D(ϕ).

Figure 1 summarizes the algorithm, and we now provide a small example illustrating it. Consider a coalition-planning game over five agents Φ = {ϕ1, . . . , ϕ5}, with the agent interaction graph being as depicted in Figure 2. Assume that each agent ϕ has two possible goal-achieving strategies, θϕ and θ′ϕ , with induced costs cϕ(θϕ) < cϕ(θ′ϕ ), and that the personal utilities r(ϕ) exceed these costs, providing ¯uϕ(θϕ) > ¯uϕ(θ′ϕ ) > 0. The inter-agent relationship between the personal agent strategies is depicted in Figure 2; for instance, θϕ1 requires some preconditions from ϕ2, and ϕ2 can provide the required support by adopting θ′ϕ2 .

In the bottom-up phase, D∗ (ϕ4) = {θϕ4 , θ′ϕ4 , ⊥}, therefore ˆuϕ4 = ¯uϕ4 (θϕ4 ). θ′ϕ4 and ⊥ provide lower utility to ϕ4, and thus are discarded, and the refined domain D(ϕ4) = {θϕ4 } is sent to ϕ2. ϕ5 has D∗ (ϕ5) = {θ′ϕ5 , ⊥}, hence ˆuϕ5 = ¯uϕ5 (θ′ϕ5 ), and only ⊥ is discarded from D(ϕ5). Next, ϕ2 finds that θϕ4 (the only strategy received from ϕ4) matches its strategies θ′ϕ2 and ⊥, but not θϕ2 (because θϕ4 does not provide the requirements of θϕ2 from ϕ4). Therefore, the strategy θϕ2 is discarded from D(ϕ2), and the modified domain {θ′ϕ2 , ⊥} is now evaluated against D(ϕ5), with θ′ϕ5 matching both θ′ϕ2 and ⊥. Here, too, ⊥ is discarded as ϕ2 has proved to have a better alternative θ′ϕ2 . Proceeding now with agent ϕ3, both its non-null strategies require ϕ1's support, and thus D∗ (ϕ3) = {⊥}, ˆuϕ3 = 0, and no strategy is discarded from the domain. When ϕ1 is processed, θϕ1 matches only ⊥ in D(ϕ3), whereas θ′ϕ1 matches all strategies of D(ϕ3). Both strategies also match θ′ϕ2 , and θ′ϕ1 also matches ⊥ of ϕ2. As both stategies of ϕ1 have a match with each child, ˆuϕ1 = ¯uϕ1 (θϕ1 ) and θ′ϕ1 and ⊥ are discarded. Table 1 shows the domains of the nodes after processing. For the top-down phase, the only possible joint strategy is (θϕ1 , θ′ϕ2 , θϕ4 , θ′ϕ5 ) and ⊥ for ϕ3. There are other feasible joint strategies in which all agents achieve their goals, for example (θ′ϕ1 , θ′ϕ2 , θ′ϕ4 , θ′ϕ5 , θϕ3 ). However, the latter joint strategy has several deviations. For example, ϕ1 deviates to

θϕ1 , and {ϕ2, ϕ5} jointly deviate to their θ strategies.

Theorem 1 For any coalition-planning game Π over simple agents, if IGΠ is acyclic, then a stable plan exists, and algorithm CoPG-Acyclic returns such a plan.

Note that the algorithm does not return all stable plans, but it is guaranteed to return at least one. Also, if the null plan (⊥ strategy for all agents) is stable, then it is the only stable plan.

4 Auction-Planning Games

In coalition-planning games agents are motivated by their selfish goals but do not compete with each other. We now consider scenarios in which each agent aims at joining a coalition that jointly satisfies a goal, and does so in cost lower than competing coalitions. Satisfying a goal yields a certain monetary gain on whose distribution the related coalition must decide. Perhaps most immediate application of this model is procurement auctions. While classical auction theory considers the bidding agents and their values to be fixed, in practice bidding may require cooperation of multiple selfish parties, each with its own capabilities (e.g., products it can supply under different preconditions with different costs and constraints). Our model captures this process of preparation for bidding where agents must combine their capabilities in a non-trivial manner.

First, we consider a setting in which the winning coalition gets a fixed bonus plus its plan's cost. We then consider a setting in the spirit of 2nd price (reverse) auction; here the winning coalition is paid the cost associated with the cheapest plan of the complementary coalition. In both cases (i) the gains are to be distributed among the coalition members, and (ii) a coalition is stable if no subset of its members can join some non-winning agents and form a joint plan with a distribution of payments that is more beneficial to all. This setting induces a game with side payments, and the solution concept is in the spirit of the core solution. However, in our setting, the value of a coalition is determined by its possible joint plans and strategic distribution of gain, rather than being given exogenously. In addition, our solution concept considers deviations by coalitions involving both winning and non-winning members. Hence, planning games suggest new, natural ways of combining elements of cooperative and noncooperative game theory.

Definition 3 An auction-planning game (AuPG) for a system of agents Φ is a tuple Π = 〈P, A, I, G, c, r〉, where P , A, I, and G are as in MA-STRIPS, c is an action cost function c : A → ℜ+, and r : A∗ → ℜ+ is a specification of the reward of the coalition selected to achieve the goal.

A solution σ for a AuPG is a triplet 〈πσ, Γσ , ˆ rσ〉 where πσ is a MA-STRIPS plan for Π, Γσ ⊆ Φ is a coalition performing πσ, and ˆ rσ : Γσ → ℜ+ is a division of the reward r(πσ) among the coalition members such that ∑ϕ∈Γσ ˆ rσ(ϕ) = r(πσ). We make a natural assumption that r(·) is monotonically increasing in the cost of the chosen coalition. Hence, given a partition of Φ into coalitions, the coalition having the lowest-cost plan is selected and granted the reward.

4.1 Fixed-Bonus RewardModel

In our first setting, the winning coalition is granted the cost of its plan c(πσ) = ∑a∈πσ c(a) plus some fixed bonus B > 0, that is, r(πσ) = c(πσ) +B. A rational agent will not participate in a plan for a personal reward lower than its personal costs in that plan, and thus each member ϕ ∈ Γσ is paid cϕ(π)+bσ(ϕ), such that ∑ϕ∈Γσ bσ(ϕ) = B, and hence ϕ's utility is uϕ(σ) = bσ(ϕ). Because the reward is distributed within the winning coalition, the utility of the agents outside it is trivially zero. With divisible utilities, coalitions will always (weakly) prefer to use their lowest-cost plan. We use c∗ (Γ) to denote the lowest cost with which Γ can attain the goal; c∗ (Γ) = ∞ denotes inability of Γ to attain the goal.

Definition 4 A solution σ is a winning bid if for any Γ ⊆ Φ \ Γσ, and for any Γ ⊂ Γσ, holds c(πσ) < c∗ (Γ). That is, neither agents outside Γσ, nor any strict subset of Γσ, have a plan with a lower cost.

This definition is based on an implicit model of the auction issuer, or auctioneer, who chooses the coalition for which the reward is the lowest. Furthermore, the auctioneer prevents manipulation of the reward by not selecting coalitions which include redundant members, because such coalitions potentially inflate their bonus as those redundant members could otherwise be part of a competing coalition.

Definition 5 A winning-bid σ is stable if there is no winningbid σ′ ̸= σ with uϕ(σ′ ) > uϕ(σ) for all ϕ ∈ Γσ′ .

We say that a coalition is stable if it has a stable winningbid solution. It turns out that stable coalitions in fixed-bonus AuPGs have a verifiable topological characterization.

Lemma 2 A coalition Γσ with a winning-bid solution σ is stable unless there exist coalitions Γ and Γ′ , both having goal achieving plans, such that (i) the three coalitions are pairwise non-disjoint, and (ii) neither Γσ∩Γ′ is included in Γσ∩Γ nor the other way round. Furthermore, if such Γ and Γ′ do exist, and both have winning-bids, then Γσ is not stable.

Lemma 2 implies that refuting the stability of a winningbid requires a cycle of coalitions. Because a winning-bid coalition is required to be minimal, and thus connected in the agent interaction graph, a cycle of coalitions implies a cycle in the AIG. Thus, if the AIG is acyclic, any winning-bid is stable. We can therefore construct a stable solution σ as follows: (i) find a cost-optimal plan π for Φ, (ii) define Γσ to be the set of agents that participate in π, and (iii) allocate the reward to prevent deviations by intersecting subsets. The last step can be done efficiently similar to the method used by the algorithm we present below.

4.2 Second-Cost RewardModel

We now take the auction analogy one step further, and define the reward to be the cost of the second-best solution. This model strengthens the attractiveness of lower-cost coalitions because they have higher utility to distribute among their agents. The reward specification includes a reserve price ρ, denoting the maximal possible reward, that is, r(πσ) = min{ρ, minΓ⊆Φ\Γσ c∗ (Γ)}.

As with a fixed bonus, acyclic agent-interaction graphs are easier to handle because for a given coalition there exists a single threat on its stability. Therefore, a coalition that obtains the best possible bonus (the bonus-optimal coalition), must be stable. Note that the bonus-optimal plan may not be the cost-optimal one; a higher cost coalition may have weaker competition by its complement and hence achieve a higher bonus. In order to find a bonus-optimal coalition, we iterate over the cuts of AIG. Each edge (ϕ′ , ϕ′′ ) defines a pair of "directional" cuts ϕ′-ϕ′′ and ϕ′′-ϕ′ . By Γϕ′-ϕ′′ we denote the nodes on the ϕ′ side of the edge. In addition, π∗ (Γ) refers to a cost-optimal plan for each Γ ⊆ Φ. A plan may actively involve only a subset of Γ, denoted henceforce by ¯Γ(π∗ (Γ)).

The cut-bonus-optimal coalition of ϕ′-ϕ′′ is defined as a bonus-optimal coalition among all coalitions Γ in Γϕ′-ϕ′′ that fulfill two conditions: (1) they include ϕ′ , (2) their second-best coalition is on the other side of the edge (that is, ¯Γ(π∗ (Φ \ Γ)) ⊆ Γϕ′′-ϕ′ ). The cut value V (ϕ′-ϕ′′ ) is the bonus obtained by the respective cut-bonus-optimal coalition.

For example, consider the AIG in Figure 3(a), for which the possible goal-achieving coalitions are listed in Figure 3(b) along with their respective costs. The cut-bonus-optimal coalition of the cut ϕ5-ϕ7 is {ϕ1, ϕ4, ϕ5}, whose secondbest coalition is {ϕ6, ϕ7} and hence it achieves a bonus of 7-4 = 3. The cut-bonus-optimal coalition of the cut ϕ7-ϕ5 is {ϕ6, ϕ7}, a coalition which in fact does not have a winningbid (or, in other words, obtains negative bonus).

Lemma 3 Let B∗ be the highest bonus possible for Π. Then there exists a cut ϕ′-ϕ′′ such that V (ϕ′-ϕ′′ ) = B∗ .

An immediate corollary is that a coalition that obtains a bonus which is the maximum cut value in IGΠ, is a bonusoptimal coalition for Π. It is therefore sufficient to find all the cut values, while recording which coalition achieves each one. Our algorithm, depicted in Figure 4, computes a cutbonus-optimal coalition, for a cut ϕ′-ϕ′′ , as follows. It first computes a cost-optimal plan, constrained to include ϕ′ . 1 If its second-best is in the other side of the cut, we are done. Otherwise, as shown in the proof of Theorem 4, the path between ϕ′ and that second-best (denoted path(·, ·)), must be part of the cut-bonus-optimal plan. Hence in each iteration, the set which constrains the cut-bonus-optimal planning problem grows, until the cost-optimal plan converges to

1 Participation constraint is added by removing ⊥ from the domain of the agents that must participate.

algorithm AuPG-Acyclic(Π, Φ)

input: an acyclic, second-cost AuPG Π over agents Φ output: a stable winning-bid plan for Π for each cut ϕ′-ϕ′′ : loop Ω = {ϕ′ } find Γ∗ϕ′ = ¯Γ(π∗ (Γϕ′-ϕ′′ )) under constraint Ω ⊆ Γ∗ϕ′ find ˆΓϕ′ = ¯Γ(π∗ (Φ \ Γ∗ϕ′ )) if ˆΓϕ′ ⊆ Γϕ′′-ϕ′ then endloop else Ω = Ω ∪ path(Ω, ˆΓϕ′ ) V (ϕ′-ϕ′′ ) := c∗ ( ˆΓϕ′ ) - c∗ (Γ∗ϕ′ ) select ϕ = arg maxϕ′ maxϕ′′ V (ϕ′-ϕ′′ ) σ = 〈π∗ (Γ∗ϕ ), Γ∗ϕ , Comp-Div(Γ∗ϕ )〉 return σ procedure Comp-Div(Γ)

perform bottom-up scan of Γ, allocate all the reward to the first node whose subtree in IGΠ includes a winning bid.

Figure 4: Algorithm for stable winning-bid planning in acyclic AuPGs with the second-cost reward model.

the cut-bonus-optimal one. The algorithm executes a number of cost-optimal planning problems which is in the worstcase quadratic in |Φ|, hence it is polynomial under the simple agents assumption and given the results of BD.

Theorem 4 For any acyclic AuPG Π with the second-cost reward model, there exists a stable winning-bid solution, and algorithm AuPG-Acyclic returns such a solution.

We demonstrate the algorithm using the AIG in Figure 3(a). Assume that the sets S of agents, listed in the first four rows of Figure 3(b), are the only coalition with goal achieving plans, and their respective costs are c∗ (S). The bonusoptimal plan is {ϕ1, ϕ4, ϕ5}, with a bonus of 3, given that its second-best coalition is {ϕ6, ϕ7}. We show that the computation of V (ϕ5-ϕ7) identifies the right coalition and its value. First, we find a cost-optimal plan on Γϕ5-ϕ7 , under the constraint that ϕ5 participates, and get Γ∗ϕ5 = {ϕ3, ϕ5}. Next, we find cost-optimal plan on Φ \ {ϕ3, ϕ5}, returning ˆΓϕ5 = {ϕ2, ϕ4}. Because this second-best is within the same side of the cut, the loop does not terminate. Now comes the key idea of the algorithm: {ϕ2, ϕ4} must intersect with the real bonus-optimal plan. Hence we add the path from ϕ5 to

{ϕ2, ϕ4}, which consists just of the node ϕ4, to Ω. Next we find cost-optimal plan under the constraint that ϕ5 and ϕ4 must participate. We get {ϕ1, ϕ4, ϕ5}, and its second best plan is by {ϕ6, ϕ7}, which is on the other side of the cut, and hence the loop terminates. If we take the additional two sets in Figure 3(b) into account, that second iteration outputs {ϕ2, ϕ4, ϕ5} with cost 3.5, which is not yet the cut-bonusoptimal because its second best is by {ϕ1} with cost 5.9. We add ϕ1 to Ω, and the next iteration finds {ϕ1, ϕ4, ϕ5}.

To compute reward division, we find cost-optimal plan of each subtree Γϕ1 , Γϕ4 , and Γϕ5 , and compare to the cost-optimal plan of its complement to find out whether it is a winning-bid. We find that Γϕ1 and Γϕ4 do not have a winning-bid (because {ϕ3, ϕ5} has a cheaper plan), but {ϕ3, ϕ5} ∈ Γϕ5 does have one. Hence ϕ5's reward is its cost plus B∗ = 3, while ϕ4 and ϕ1 get just their cost back.

Finally, assume that c∗ (ϕ1) = c∗ ({ϕ2, ϕ4}) = 6.1. The cut-bonus-optimal coalition of ϕ5-ϕ7 is still {ϕ1, ϕ4, ϕ5}, with the same value 3. However, V (ϕ5-ϕ4) = 3.1, obtained by {ϕ3, ϕ5}, hence it is now the bonus-optimal plan.

Acknowledgements

Ronen Brafman and Carmel Domshlak are partially supported by ISF grant 8254320. Ronen Brafman is also supported in part by the Paul Ivanier Center for Robotics Research and Production Management, and the Lynn and William Frankel Center for Computer Science. Yagil Engel is supported in part by an Aly Kaufman fellowship at the Technion.