Structural Tractability of Shapley and Banzhaf Values in Allocation Games

1 Introduction

Coalitional game theory provides a solid mathematical framework to study scenarios where agents can obtain higher worths by collaborating with each other rather than by acting in isolation (see, e.g., [Nisan et al., 2007; Osborne and Rubinstein, 1994]). In abstract terms, a coalitional game G is a tuple 〈N, v〉, where N is a set of agents and v is a function associating each coalition C ⊆ N with the worth that agents in C can guarantee to themselves. The worth can be freely distributed among the agents and, in fact, the crucial problem is to single out the most desirable distributions (of the worth associated with the grand-coalition N), usually called solution concepts, which can be perceived as fair and stable.

In this paper, we consider the class of allocation games, which provides a framework to analyze fair division problems where monetary compensations are allowed and utilities are quasi-linear [Moulin, 1992]: We are given an allocation scenario A comprising a set of goods and a set of agents, and each agent is to be assigned at most one good she is interested in. Each good g has a value val(g) ∈ R and the worth vA(C) associated with any coalition C ⊆ N is the maximum overall value that can be obtained over the assignments to agents in C only, also called allocations, hereinafter.

Example 1.1. Consider the allocation scenario A0 that is reported in Figure 1, by using an intuitive graphical notation. We have a set {g1, g2, g3, g4} of goods that have to be allocated to three agents. Each edge connects an agent to a good she is interested in. Edges in bold identify an optimal allocation, i.e., a feasible allocation whose sum of values of the allocated goods is the maximum possible one. The value of this allocation is val(g1) + val(g2) + val(g3) = 3 + 2 + 1 = 6.

For each C ⊂ {1, 2, 3} with C ̸= ∅, an optimal allocation restricted to the agents in C is also reported. Then, the associated coalitional game is GA0 =〈{1, 2, 3}, vA0 〉, where vA0 ({1, 2, 3})=6, vA0 ({1, 2})=5, vA0 ({1, 3}) = vA0 ({2, 3})=4, vA0 ({1}) = vA0 ({2})=3, and vA0 ({3})=1. ✁

Allocation games naturally arise in various application domains, ranging from house allocation to room assignmentrent division, to (cooperative) scheduling and task allocation, to protocols for wireless communication networks, and to queuing problems (see, e.g., [Moulin, 1992; Maniquet, 2003; Mishra and Rangarajan, 2007; Greco and Scarcello, 2014b] and the references therein). In these contexts (and when monetary transfers are possible), the prototypical solution concepts considered in the literature are the Shapley value [Shapley, 1953] and the Banzhaf value (or index) [Banzhaf, 1965]. However, it is well known that, in general, computing such values is #P-complete. This is a serious obstruction to their applicability in allocation scenarios involving many agents, and it motivates the design of approximation algorithms and the identification of subclasses of practical interest where exact computation can be carried out efficiently.

In the paper we focus on the latter approach. For a better understanding of the problem, we first strengthen the known hardness results to the case of goods with one possible value only. Then, we look for islands of tractability of allocations problems. To this end, we provide a characterization of the marginal contribution of an agent to any coalition in terms of certain properties of good allocations, which are not required to be optimal ones. Such a technical tool allows us to point out the tractability of allocation games where every good is shared (or claimed for) by two agents at most.

The main result of the paper, also based on the tool discussed above and on further ingredients exploiting constraint satisfaction techniques, is a polynomial-time algorithm for the computation of the Shapley value and the Banzhaf value in allocation games where agent interactions have a tree-like structure-formally, have bounded treewidth [Robertson and Seymour, 1984]. These games capture scenarios of practical interest. For instance, we analyzed an instantiation for the setting described in the Appendix A.1 of the work by [Greco and Scarcello, 2014b] and referring to an allocation problem arising in the ItalianResearchAssessment program. In particular, we analyzed the publications selected by the researchers at the University of Calabria for the period 2004-2010, by discovering that the treewidth of the underlying (co-authorship) graph, consisting of more than 500 nodes, is just 9.

Moreover, the main result and the technical tools used to get it have their own theoretical interest, since the analysis of the complexity of reasoning problems related to coalitional games over classes of instances having some useful structural property is an active topic of research in artificial intelligence. For instance, structural tractability results for the related class of matching games have been recently pointed out by [Aziz and de Keijzer, 2014]; and our techniques might be used to attack some of the problems left open there about games with graphs having bounded treewidth.

2 Formal Framework

Solution Concepts. Coalitional games can be formalized as tuples G = 〈N, v〉 where each coalition C ⊆ N is associated with a real value v(C) meant to encode the worth that agents in C obtain by collaborating with each other. A fundamental problem for a coalitional game G = 〈N, v〉 is to single out the most desirable outcomes, usually called solution concepts, in terms of appropriate notions of worth distributions, i.e., of payoff vectors of the form (x1, ..., x|N|) ∈ R|N| where xi + · · ·+x|N| equals the worth associated with the whole set N of agents. In the paper, we focus on the Shapley value, which is a well-known solution concept such that the payoff associated with each agent i ∈ N is given by

and on the Banzhaf value, for which the payoff of i is

where v(C ∪{i})-v(C) is the marginal contribution of i to the coalition C ∪ {i}.

Allocation Scenario. Assume that a set G of goods have to be allocated to a set N = {1, ..., n} of agents. Each good g ∈ G is associated with a real value val(g) ∈ R, and each agent i ∈ N can receive at most one good taken from her set of interest Ω(i) ⊆ G. The tuple A = 〈N,G,Ω, val〉, with Ω : N → 2G and val : G → R, is an allocation scenario.

Goods are indivisible and unshareable. Hence, an allocation for A is a function π : N → G ∪ {∅} such that: (1) for each agent i ∈ N, π(i) ̸= ∅ implies π(i) ∈ Ω(i); and (2) for each pair i, i′ ∈ N with i ̸= i′ , π(i) ∩ π(i′ ) = ∅ holds. We denote by img(π) the set of all goods in the image of π, i.e., img(π) = {π(i) | i ∈ N ∧ π(i) ̸= ∅}.

By slightly abusing of notation, if S ⊆ G is a set of goods, then val(S) denotes the sum of their values. Moreover, if π is an allocation, then val(π) denotes the value of img(π). An allocation π is optimal (w.r.t. A) if val(π) ≥ val(π′ ) holds, for each allocation π′ . The value associated with any optimal allocation w.r.t. A is hereinafter denoted as opt(A).

Allocation Games. Let A = 〈N, G, Ω, val〉 be an allocation scenario and let C ⊆ N be a set of agents. The restriction of A to C is the sub-scenario A[C] = 〈C,G,ΩC, val〉 where ΩC is the restriction of Ω over C. The allocation game induced by A is the tuple GA = 〈N, vA〉, where vA : 2N → R is such that vA(C) = opt(A[C]), for each C ⊆ N.

The value of an empty set of goods is 0. Then, the definition trivializes for C = ∅, with vA(∅) = 0. Moreover, note that vA(C) ≥ 0 holds, for each C ⊆ N, since the allocation where no agent receives some good is a feasible one.

The following properties are known to hold on every pair C,C′ of sets of agents such that C ′ ⊆ C ⊆ N [Greco and Scarcello, 2014b; Moulin, 1992]:

(allocation) monotonicity: vA(C) ≥ vA(C′ ). Moreover, if π is an optimal allocation for A[C], then there is an optimal allocation π′ for A[C ′ ] such that img(π′ ) ⊆ img(π);

3 Intractability of Computation

Computing the Shapley value is a problem that has been shown to be #P-complete on different classes of games (see, e.g., [Deng and Papadimitriou, 1994; Nagamochi et al., 1997; Bachrach and Rosenschein, 2009; Aziz and de Keijzer, 2014]), including the allocation games [Greco and Scarcello, 2014b]. In particular, hardness has been shown to hold even on instances whose goods have three possible values. Below, we improve the result by showing that there is no advantage in focusing on scenarios where all goods have the same value. To this end, we first focus on the Banzhaf value.

Theorem 3.1. Computing the Banzhaf value is #P-hard on allocation games (under Turing reductions), even for scenarios A = 〈N, G, Ω, val〉 such that |{val(g) | g ∈ G}| = 1.

Proof Sketch. Let (S∪I, E) be a bipartite graph, hence with S ∩ I = ∅ and E ⊆ S × I. Computing the number of subsets C ⊆ S of vertices to which all vertices in I can be matched is #P-hard [Colbourn et al., 1995].

Based on (S ∪ I,E), let us build the allocation scenario A = 〈S ∪ {|S| + 1}, I, Ω, val〉 where nodes in S (resp., I) are transparently viewed as the agents (resp., goods), where val(g) = 1 for each g ∈ I, and where Ω(i) = {g ∈ I |

{i, g} ∈ E} while Ω(|S| + 1) = I. Consider then the allocation game GA = 〈N, vA〉 with N = S ∪ {|S| + 1}, and the Banzhaf value β|S|+1(GA). Observe that, for any given coalition C ⊆ S = N \{|S|+1}, v(C∪{|S|+1})-v(C) = 0 if, and only if, C ⊆ S is a set of vertices to which all vertices in I can be matched. Eventually, β|S|+1(GA)×2|S| is the number of subsets C ⊆ S for which some vertex in I cannot be matched, and 2|S| -β|S|+1(GA)×2|S| is the desired number, which can be computed in polynomial time once the Banzhaf value β|S|+1(GA) is known.

This result is a key ingredient to prove the following.

Theorem 3.2. Computing the Shapley value is #P-hard on allocation games (under Turing reductions), even for scenarios A = 〈N, G, Ω, val〉 such that |{val(g) | g ∈ G}| = 1.

Proof Idea. The result is established by showing that the Banzhaf value of allocation games can be computed in polynomial time based on the knowledge of the Shapley value, so that this latter concept turns out to be #P-hard too. This property was known to hold over (certain) simple games [Aziz et al., 2009]. For its proof, we exploit some of the arguments of that paper and the fact that, for each agent i ∈ N, the Shapley value and the Banzhaf value can be rewritten as follows:

where, for each h ∈ {0, ..., n - 1}, it holds that βi(GA, h) = ∑C⊆N\{i},|C|=h (v(C ∪ {i}) - v(C)).

From these results, it turns out that acting on the values of goods does not help very much in identifying tractable classes of instances. So, we next consider different kinds of restrictions based on the "interactions" that emerge among agents.

4 Characterizations of The Shapley Value

Throughout the section, assume that an allocation scenario A = 〈N, G, Ω, val〉 is given. Let {w1, ..., wm} = {val(g) | g ∈ G} ∪ {0} be the set of all values associated with goods in G (plus the null value 0, if not present), and assume that w1 > w2 > · · · > wm. W.l.o.g, assume also that wm = 0.

4.1 ACloser Look at Marginal Contributions

We start with a simple reformulation. Let i ∈ N be an agent, let h ∈ {0, ..., n - 1}, let ℓ ∈ {1, ...,m}, and let us denote by #ciℓ (GA, h) the number of coalitions C such that |C| = h and vA(C ∪ {i}) - vA(C) ≥ wℓ. Then, the coefficients βi(GA, h) in the expressions illustrated in Equation (1) can be rewritten as follows, by simple algebraic manipulations and by exploiting the monotonicity of allocation games.

Hence, counting the number of coalitions to which some given marginal contribution can be provided is deeply related to the computation of the Shapley and Banzhaf values of allocation games. We now further explore this specific task.

For each "level" ℓ ∈ {1, ...,m} over the possible values, an agent i ∈ N is said to be dependent at level ℓ (short: ℓdependent) if for each g ∈ Ω(i) with val(g) ≥ wℓ, there is an agent j ∈ N \ {i} such that g ∈ Ω(j). In particular, note that any agent having goods with value at least wℓ and which are not shared with any other agent is not dependent at level ℓ; in fact, all her marginal contributions are at least wℓ, independently of the coalition to be considered. Let Gℓ = (Nℓ,Eℓ) be the undirected graph where Nℓ is the set of all ℓ-dependent agents and where {i, j} ∈ Eℓ if, and only if, there is a good g ∈ Ω(i) ∩ Ω(j) with val(g) ≥ wℓ. Then, a coalition R ⊆ Nℓ of agents is called a component at level ℓ (short: ℓ-component) if the subgraph of Gℓ induced by the nodes in R is connected. As a special case, if there is no good g ∈ Ω(i) with val(g) ≥ wℓ, then {i} is an ℓ-component.

Example 4.2. Consider the scenario A0 reported in Figure 1. We have w1 = val(g1). Moreover, {1, 2} and {3} are the only subset-maximal components at level 1. Indeed, g1 ∈ Ω(1) ∩ Ω(2), and there is no good in Ω(3) with value w1. ✁

If C ⊆ N is a coalition and i ̸∈ C is an agent, then we denote by piℓ (C) the ℓ-part of C w.r.t. i. This is the emptyset if i ̸∈ Nℓ; otherwise, piℓ (C) is the subset-maximal (in fact, unique) ℓ-component R ⊆ C ∪ {i} with i ∈ R. These concepts play a key role to characterize marginal contributions.

Theorem 4.3. Let C ⊆ N be a coalition and let i ∈ N \C be an agent for which there is a good g ∈ Ω(i) with val(g) ≥ wℓ. Then, the following statements are equivalent:

1. vA(C ∪ {i}) - vA(C) ≥ wℓ;
2. there is an allocation ¯π for A[piℓ (C)] such that val(¯π(j)) ≥ wℓ, for each j ∈ piℓ (C).

Proof Idea. If i ̸∈ Nℓ, then piℓ (C) = ∅ and (2) trivially holds. Moreover, its marginal contribution to any coalition is at least wℓ. So, (1) holds, too. In the remaining, consider the case where i ∈ Nℓ, so that i ∈ piℓ (C). Let R = piℓ (C) \ {i} and let S = C \ R. Here, we show how to deal with the case S = ∅. The result can be generalized by noticing that agents in S do not "interact" with agents in R (w.r.t. level wℓ).

(1)⇒(2) Assume that (2) does not hold for optimal applications. That is, there is an optimal allocation ¯π for A[R∪ {i}] and of an agent j ′ ∈ R ∪ {i} such that val(¯π(j ′ )) < wℓ. Consider the following two possible cases. First, assume that val(¯π(i)) < wℓ. Since the restriction of ¯π over the agents in R is a feasible allocation for A[R], then we immediately get that vA(R) ≥ val(¯π) - val(¯π(i)) > val(¯π) - wℓ, and hence vA(R ∪ {i}) - vA(R) < wℓ. Second, assume that val(¯π(i)) ≥ wℓ. We start by observing that, due to the optimality of ¯π, for each agent j ′ ∈ R ∪ {i} with val(¯π(j ′ )) < wℓ, {g | g ∈ Ω(j ′ )∧val(g) ≥ wℓ} ⊆ img(¯π). That is, goods that might be in principle allocated to an agent j ′ ∈ R ∪ {i} with val(¯π(j ′ )) < wℓ and having value at least wℓ are actually allocated to some different agent in R ∪ {i}. Given that R∪{i} is an ℓ-component (and that, in particular, each agent is ℓ-dependent), we are guaranteed about the existence of a succession i = j ′1 , j ′2 , ..., j ′h such that ¯π(j ′x ) ∩ Ω(j ′x+1 ) ̸= ∅, for each x ∈ {1, ..., h-1}; and val(π(j ′h )) < wℓ. Consider then the function ¯π-i : R→G∪{∅}with ¯π-i(j ′x+1 ) = ¯π(j ′x ), for each x ∈ {1, ..., h-1}; and ¯π-i(j ′′ ) = ¯π(j ′′ ), for each j ′′ ∈ R \ {j ′2 , ..., j ′h}. Then, ¯π-i is an allocation for A[R] and we have that val(¯π-i) = val(¯π) - val(¯π(j ′h )). Hence, vA(R) ≥ val(¯π-i) = val(¯π) - val(¯π(j ′h )) > val(¯π) -wℓ. That is, vA(R ∪ {i}) - vA(R) < wℓ. In both cases, we have derived a contradiction with (1).

(2)⇒(1) Let ¯π′ be an allocation for A[R ∪ {i}] such that val(¯π′ ) ≥ wℓ, for each j ∈ R ∪ {i}. We can show that there is an optimal allocation ¯π for A[R ∪ {i}] with the same property. Because of the allocation monotonicity property, there is also an optimal allocation ¯π-i for A[R] such that img(¯π-i) ⊆ img(¯π). Hence, for each j ∈ R, val(¯π-i(j)) ≥ wℓ. Now, observe that vA(R ∪ {i}) = val(img(¯π)) and vA(R) = val(img(¯π-i)). So, vA(R ∪ {i}) - vA(R) coincides with the value of one of the goods in img(¯π), and vA(R ∪ {i}) - vA(R) ≥ wℓ.

Example 4.4. By continuing with Example 4.2, note that {1, 2} = p1ℓ ({2, 3}) holds, for ℓ ∈ {1, 2}. Therefore, the allocation for A0[{1, 2}] depicted in Figure 1 witnesses, by Theorem 4.3, that vA0 ({1, 2, 3}) - vA0 ({2, 3}) ≥ w2. ✁

4.2 Bounded Sharing

Our analysis intensively uses Theorem 4.3. The first outcome is an island of tractability based on the notion of bounded sharing. Formally, for a given level ℓ, define the sharing degree of an allocation scenario A, denoted by sdℓ(A), as the maximum, over all goods g with val(g) ≥ wℓ, of |{j ∈ N | g ∈ Ω(j)}|. Intuitively, it measures the maximum number of agents competing for the same good (with value at least wℓ).

Theorem 4.5. The Shapley and Banzhaf values of allocation games GA can be computed in polynomial time on scenarios A = 〈N, G, Ω, val〉 such that sdℓ(A) ≤ 2, for each level ℓ.

Proof Idea. Let i be an agent in N, and let h ∈ {0, ..., n-1}. The line of the proof is to show that:

• X = 0, if h < |piℓ (N \{i})|-1; or if i is not ℓ-dependent, or the subgraph of Gℓ induced by the nodes in piℓ (N \ {i}) contains a cycle, or there are two agents j and j ′ in piℓ (N \ {i}) with |Ω(j) ∩ Ω(j ′ ) ∩ {g | val(g) ≥ wℓ}| > 1.

In particular, the value derives by analyzing the allocations of Theorem 4.3.(2) on the scenario A such that sdℓ(A) ≤ 2. The result is then established because of this closed form, of Theorem 4.1, and of the expressions in Equation (1).

5 Bounded Treewidth

We now move to allocation games where the interactions among agents have a tree-like structure. We use the technical tools provided in Section 4, by combining them with CSP techniques that are of interest in their own.

For any scenario A = 〈N, G, Ω, val〉, let G(A) = (N, E) be the undirected graph such that {i, j} ∈ E if, and only if, there is a good g ∈ Ω(i) ∩ Ω(j). Moreover, recall that a tree decomposition of a graph G = (N,E) is a pair 〈T, χ〉, where T = (V, F) is a tree, and χ is a function assigning to each vertex p ∈ V a set of nodes χ(p) ⊆ N, such that the following conditions are satisfied: (1) ∀b ∈ N, ∃p ∈ V such that b ∈ χ(p); (2) ∀{b, d} ∈ E, ∃p ∈ V such that {b, d} ⊆ χ(p); (3) ∀b ∈ N, the set {p ∈ V | b ∈ χ(p)} induces a connected subtree of T. The width of 〈T, χ〉 is maxp∈V |χ(p) - 1|, and the treewidth of G (short: tw(G)) is the minimum width over all its tree decompositions (see, e.g., [Robertson and Seymour, 1984]).

5.1 Preliminaries on CSPs

A constraint satisfaction problem (short: CSP) instance is a triple I = 〈Var , U, C〉, where Var is a finite set of variables, U is a finite domain of values, and C = {C1, C2, . . . , Cq} is a finite set of constraints (see, e.g., [Dechter, 2003]).

Each constraint Cv, for 1 ≤ v ≤ q, is a pair (Sv, rv), where Sv ⊆ Var is a set of variables called the constraint scope, and rv is a constraint relation, i.e., a set of substitutions θ : Sv → U indicating the allowed combinations of simultaneous values for the variables in Sv. A substitution from a set V ⊆ Var to U is often viewed as the set of pairs of the form X/u, where θ(X) = u is the value to which X ∈ V is mapped. For each variable X ∈ Var, its domain is the set of all elements u ∈ U for which some constraint relation contains a substitution θ with θ(X) = u. A substitution θ satisfies Cv if its restriction to Sv occurs in rv. A solution to I is a substitution θ : Var ↦→ U satisfying all constraints. The set of all solutions is denoted by Θ(I). If W is a set of variables, then Θ(I,W) denotes the set of all solutions in Θ(I) restricted to the variables in W. Variables outside W can be viewed as auxiliary ones-they are used for internal encoding activities, and they are not required in the output.

With each CSP instance I, we can naturally associate the graph G(I) whose nodes are the variables and where there is an edge between any pair of variables appearing within the same scope. Deciding whether there is a solution (and compute one, if any) is generally NP-hard, but it is known to be feasible in polynomial time on classes of CSP instances I whose associated graphs have treewidth bounded by some given constant [Gottlob et al., 2013]. Recently, these kinds of structural tractability results have been generalized to counting problems, as summarized below.

Theorem 5.1 (cf. [Pichler and Skritek, 2013; Greco and Scarcello, 2014a]). Counting the number of substitutions in Θ(I,W) is feasible in polynomial time, on classes of CSP instances I such that the treewidth of G(I) is bounded by a constant, and the size of the domain of each variable not in W is bounded by some constant, too.

Note that, differently from the case of the standard decision and computation problems, the result is established under the additional condition that auxiliary variables have a bounded domain. If the condition is not met, then #P-complete instances can be exhibited [Pichler and Skritek, 2013].

5.2 CSP Encoding (for the Banzhaf Value)

In order to establish a tractability result, we shall encode the computation of the coefficients #ciℓ (GA, h) in terms of a counting problem over a suitably defined CSP instance and we shall then make use of Theorem 5.1. The challenge is to end up with an encoding using a constant number of values for the auxiliary variables. For instance, the natural encoding where some variable Xj (associated with an agent j ∈ N) can take as values the goods in Ω(j) is not useful here. In fact, we propose an encoding that uses both the given allocation scenario A and a tree decomposition TD = 〈T, χ〉 of G(A). The idea is that each good is associated with some distinguished vertex of T, while suitable variables in the labels of the tree encode the roadmaps to reach such goods. In particular, their domain just contains the needed road signs (five values are enough). This is detailed below.

We start by building a tree decomposition with certain desirable properties. Let 〈T ′ , χ′ 〉 be a tree decomposition of G(A) whose width is k > 0. Note that, for each good g ∈ G, we are guaranteed about the existence of a vertex v′g in T ′ such that χ(v′g ) ⊇ {j | g ∈ Ω(j)}. Indeed, the agents in {j | g ∈ Ω(j)} form a clique in G(A).

In a pre-processing step, we modify 〈T ′ , χ′ 〉 by adding a fresh vertex vg as a child of v′g , whose label is χ(vg) = χ(v′g ) ∩ {j | g ∈ Ω(j)}. By iterating over all goods, we get the desired tree where each good g is associated with a distinguished vertex (in fact, leaf) vg labeled by the agents to whom g can be allocated. Of course, the transformation is feasible in polynomial time. Eventually, we further transform the decomposition by making it binary: For each vertex v with children v1, ..., vn, we can create a novel vertex ¯ v as a child of v and with its label, by subsequently appending under it all these children but v1. Let TD = 〈T, χ〉 be the resulting tree decomposition, having the same width as 〈T ′ , χ′ 〉.

Example 5.2. Figure 2 illustrates a width-2 tree decomposition ¯ TD0 of G(A0), by evidencing the vertices that are univocally associated with the goods in {g1, g2, g3, g4}. Moreover, note that the decomposition is defined over a binary tree. ✁

The input to our encoding is the allocation scenario A, the agent i ∈ N, the natural number ℓ, and the tree decomposition TD = 〈T, χ〉. Note that, for the moment, we do not consider the size h. Then, we define the encoding ξ such that ξ(A, i, ℓ, TD) is the CSP instance 〈Var , U, C〉, where

• Var = ⋃j∈N {Xj, Yj} ∪ {Xv j | v is in T ∧ j ∈ χ(v)};
• U = {0, 1, ⊙,↙,↘, ↑};

and where C is defined as follows, with constraint relations being reported in tabular form in Figure 3:

1. For each agent j ∈ N and vertex v in T with j ∈ χ(v), there is a constraint (Sv,j , rv,j) with Sv,j = {Xv j ,Xj};
2. For each good g with val(g) ≥ wℓ and each j ∈ χ(vg), there is a constraint (Sg,j , rg,j) such that Sg,j = {Xvg j };
3. For each agent j ∈ N, there is a constraint (Sj, rj) such that Sj = {Yj,Xj};
4. For each pair of agents j ∈ N and j ′ ∈ N that are adjacent in Gℓ, there is a constraint (Sj,j ′ , rj,j ′) such that Sj,j ′ = {Yj,Xj,Xj ′};
5. For each non-leaf vertex v whose left (resp., right) child is v1 (resp., v2), and for each j ∈ χ(v), there is a constraint (S′v,j , r′v,j ) such that S′v,j = {Xv j ,Xv1 j ,Xv2 j };
6. For each good g with val(g) ≥ wℓ and for each pair j, j ′ ∈ χ(vg) with g ∈ Ω(j)∩Ω(j ′ ), there is a constraint (Sg,j,j ′ , rg,j,j ′ ) such that Sg,j,j ′ = {Xvg j ,Xvg j ′ };
7. No further constraint is in C.

Theorem 5.3. The following properties hold:

• (a) ξ(A, i, ℓ, TD) can be built in polynomial time;
• (b) the domain of each variable in ξ(A, i, ℓ, TD) consists of at most 5 distinct elements;
• (c) tw(G(ξ(A, i, ℓ, TD))) ≤ 5× (tw(G(A)) +1);
• (d) if θ is a solution to ξ(A, i, ℓ, TD), then Rθ = {j | θ(Yj) = 1 ∧ j ̸= i} is such that vA(Rθ ∪ {i})-vA(Rθ) ≥ wℓ;
• (e) if R ⊆ N \{i} is such that vA(R∪{i})-vA(R) ≥ wℓ, then there is a solution θ to ξ(A, i, ℓ, TD) with R = Rθ;
• (f) ∑n-1 h=0 #ciℓ (GA, h) = |Θ(ξ(A, i, ℓ, TD), {Y1, ..., Yn})|.

Proof Sketch. Property (a) and Property (b) are immediate.

Concerning Property (c) note that, if TD = 〈T, χ〉, then the tuple 〈T, χξ〉 such that for each vertex v in T, χξ(v) = ⋃j∈χ(v) {Xj , Yj , Xv j } ∪ {Xv1 j ,Xv2 j | v is not a leaf} is a tree decomposition of G(ξ(A, i, ℓ, TD)). Note that the decomposition does not depend on i and ℓ. As an example, the modified label associated with the root node of the tree decomposition of the graph G(A0) in Example 5.2 is shown in Figure 2.

Concerning Property (d), assume that θ is a solution to ξ(A, i, ℓ, TD) and let ¯Rθ be the set {j | θ(Xj) = 1 ∧ j ̸= i}.

Let j be any agent in ¯Rθ ∪ {i}. First, we claim that there is a vertex v∗ in T such that θ(Xv∗ j )=⊙. By contradiction, assume there is no such vertex. Let v be the vertex in TD that is the closest to the root with j ∈ χ(v). Because of the constraint (Sv,j, rv,j) of type 1, we have that θ(Xv j ) ∈ {↙,↘}. If v is a non-leaf vertex, then because of constraint (S′v,j , r′v,j ) of type 5, we have that θ(Xw j ) ∈ {↙,↘} holds, with w ∈ {v1, v2} being one of its two children in T. In particular, given the constraint of type 1, for the child w it must be the case that j ∈ χ(w) holds. Therefore, we can apply the argument again on w, and so top-down from w we can eventually reach a leaf ¯ v such that θ(¯ v) ∈ {↙,↘}. But, this is impossible by the constraint (S¯ v,j , r¯ v,j) of type 1. So, we know that for each j ∈ ¯Rθ ∪ {i}, there is a vertex v∗ in T such that θ(Xv∗ j )=⊙. Moreover, for each vertexw in the path connecting v and v∗ , θ(w) ∈ {↙,↘}. Therefore, because of constraints of type 5, for each vertex u with j ∈ χ(u) and not occurring in this path, it is the case that θ(u) = ↑.

Hence, for each j ∈ ¯Rθ ∪{i}, there is precisely one vertex v∗ such that θ(Xv∗ j )=⊙. Because of the constraints of type 1 and 2, it holds that v∗ = vg, for some good g ∈ Ω(j) with val(g) ≥ wℓ. Moreover, because of the constraints of type 6, there is no other agent j ′ such that θ(Xv∗ j ′ )=⊙. In the light of these properties, the function π : N → G such that π(j) = g, for each j ∈ ¯Rθ ∪ {i} with θ(Xvg j )=⊙, and π(¯j) = ∅, for each other agent ¯j, is well-defined and is an allocation. In particular, for each agent j ∈ ¯Rθ ∪ {i}, val(π(j)) ≥ wℓ.

Let now Rθ = {j | θ(Yj) = 1 ∧ j ̸= i}. Observe that, because of the constraints of type 3, it holds that ¯Rθ ⊆ Rθ. In particular, θ(Xi) = 1. Moreover, note that because of the constraints of type 4, whenever θ(Xj ′) = 1 and θ(Yj) = 1 with j and j ′ being adjacent in Gℓ, then θ(Xj) = 1 holds, too. Hence, ¯Rθ ∪ {i} ⊇ piℓ (Rθ). It follows that we can apply Theorem 4.3 on the coalition Rθ, and we conclude that vA(Rθ ∪ {i}) - vA(Rθ) ≥ wℓ.

Consider now Property (e). If R ⊆ N \ {i} is a coalition with vA(R ∪ {i}) - vA(R) ≥ wℓ, then by Theorem 4.3 there is an allocation π such that val(π(j)) ≥ wℓ, for each j ∈ piℓ (R). Consider the substitution θ such that: θ(Yj) = 1 iff j ∈ R ∪ {i}; θ(Xj) = 1 iff j ∈ piℓ (R); θ(Xvg j ) = ⊙ iff π(j) = g; θ(Xv j ) = 0 iff j ̸∈ R; θ(Xv j ) = ↑ iff θ(Xvg j ) = ⊙ holds for a vertex vg that is not in the subtree of T rooted at v; θ(Xv j ) = ↙ (resp., θ(Xv j ) = ↘) if θ(Xvg j ) = ⊙ for a vertex vg that occurs in the subtree rooted at the left (resp., right) child of v. By inspecting the constraints, it can be checked that θ is in fact a solution to ξ(A, i, ℓ, TD).

Finally, Property (f) derives by Property (d), by Property (e), by the fact that θ(Yi) = θ(Xi) = 1 holds in any solution, and by the definition of #ciℓ (GA, h).

By combining Theorem 5.3, Theorem 5.1, Theorem 4.1, and Equation (1), we get the tractability result.

Corollary 5.4. The Banzhaf value of allocation games GA can be computed in polynomial time on scenarios A = 〈N, G, Ω, val〉 such that tw(G(A)) is bounded by a constant.

5.3 From the Banzhaf Value to the Shapley Value

The encoding ξ discussed so far does not take h as a parameter. In fact, it just provides us a way to compute the value ∑n-1 h=0 #ciℓ (GA, h) and, hence, the Banzhaf value. In order to compute the contribution #ciℓ (GA, h) for each cardinality of the coalitions and, hence, the Shapley value by Theorem 4.1 and Equation (1), we need a way to filter, out of all possible solutions, those θ such that |Rθ| = h. This is not immediate (by preserving structural properties and the bound on the domains), so that a careful construction is in order.

Theorem 5.5. The Shapley value of allocation games can be computed in polynomial time on all allocation scenarios whose interaction graphs have bounded treewidth.

Proof Idea. Consider this class of allocation scenarios A with tw(G(A)) ≤ k, for some fixed natural number k. Then, a width-k tree decomposition TD of G(A) and the encoding I = ξ(A, i, ℓ, TD) can be computed in polynomial time. Let TD′ be a tree decomposition of G(I) whose width is bounded by 5 × (k + 1) (cf. Theorem 5.3). Consider the modified CSP instance I ′ = ζ(I, {Y1, ..., Yn}, h, TD′ ) = 〈Var ′ ,U ′ ,C′ 〉 such that: Var ′ = Var ∪ {Wv | v is in T ′}; U ′ = U ∪ {0, ..., h}; and C′ = C ∪ {(Sv, rv) | v is in T ′}.

In particular, for each non-leaf vertex v in T ′ with children v1 and v2, we have Sv = χ′ (v) ∪ {Wv,Wv1 ,Wv2 }. Moreover, rv contains all possible substitutions θ over the variables in Sv such that θ(Wv), θ(Wv1 ), θ(Wv2 ) ∈ {0, ..., h} and θ(Wv) - |{Yj ∈ Sv | v = cr(j) ∧ θ(Yj) = 1}| = θ(Wv1 ) + θ(Wv2 ), where cr(j) is the vertex v∗ that is the closest to the root and such that Yj ∈ χ′ (v∗ ). Additionally, if v is the root of T ′ , then we require that θ(Wv) = h + 1 holds. Instead, if v is a leaf, then Sv = χ′ (v) ∪ {Wv}, and rv contains all possible substitutions θ over Sv such that θ(Wv) = |{Yj ∈ Sv | v = cr(j) ∧ θ(Yj) = 1}|.

Note that tw(G(I ′ )) ≤ tw(G(I)) + 3. Moreover, by Theorem 5.3 and the above encoding, it can be checked that |Θ(I ′ , {Y1, ..., Yn})| coincides with #ciℓ (GA, h). We then get the Shapley value by using Theorem 4.1 and Equation (1). Unfortunately, we cannot apply Theorem 5.1 on I ′ and {Y1, ..., Yn}, since the auxiliary variables Wv do not have a bounded domain. However, we can add such variables to the output variables without altering the number of solutions, because |Θ(I ′ , {Y1, ..., Yn})| = |Θ(I ′ , {Y1, ..., Yn} ∪ (Var ′ \ Var)| holds. Thus, Theorem 5.1 applied on I ′ with output variables {Y1, ..., Yn}∪(Var ′ \Var ), ensures that #ciℓ (GA, h) can be computed in polynomial-time.

6 Conclusion

We have studied the problem of computing the Shapley value and the Banzhaf value of allocation games, which are coalitional games implicitly (and succinctly) specified in terms of an underlying allocation scenario. We have shown that the problem is #P-complete, even in stringent settings. Motivated by this bad news, we identified islands of tractability by focusing either on scenarios with sharing degree at most 2 or such that the interactions among agents have a tree-like structure. This way, real world applications with useful structural properties can efficiently be dealt with. Moreover, the technical tools used to get the results may have a wider spectrum of applicability, beyond allocation problems.

A variant of the proposed framework considers scenarios where agents must necessarily get some good. In this case, it makes sense to have goods with negative values, too. In fact, we remark that our algorithms can be extended to manage these cases as well, by just considering suitable negative levels. Our work leaves open the technical question of whether tractability still holds over scenarios with sharing degree bounded by some constant greater than 2 (e.g., sdℓ(A) ≥ 3). Moreover, it might stimulate further research to analyze the complexity of other solution concepts over allocation games, such as the nucleolus [Schmeidler, 1969]. Finally, we point out that since our technical elaborations are often rather involved, their immediate/na¨ıve implementation might be unpractical. Indeed, there is much room for practical improvements, for instance, by adopting implementation strategies used for decomposition methods in data-intensive applications (e.g., in the evaluation of SQL queries) and parallel solutions. This might constitute another interesting avenue of further research.

Acknowledgments

1. Greco's work was also supported by a Kurt G¨odel Research Fellowship, awarded by the Kurt G¨odel Society.