--- title: "The Tractability of the Shapley Value over Bounded Treewidth Matching Games" authors: - "Gianluigi Greco" - "Francesco Lupia" - "Francesco Scarcello" doi: "10.24963/ijcai.2017/145" url: "https://ijcai.org/proceedings/2017/145" pdf: "https://ijcai.org/proceedings/2017/0145.pdf" venue: "Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence" year: 2017 pages: "1046-1052" track: "Main track" keywords: - "Agent-based and Multi-agent Systems: Cooperative Games" - "Combinatorial & Heuristic Search: Combinatorial search/optimisation" - "Knowledge Representation, Reasoning, and Logic: Game Theory" --- # The Tractability of the Shapley Value over Bounded Treewidth Matching Games Gianluigi Greco, Francesco Lupia, Francesco Scarcello *Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence*, pages 1046-1052. DOI: [10.24963/ijcai.2017/145](https://doi.org/10.24963/ijcai.2017/145) ## Abstract Matching games form a class of coalitional games that attracted much attention in the literature. Indeed, several results are known about the complexity of computing over them {solution concepts}. In particular, it is known that computing the Shapley value is intractable in general, formally #P-hard, and feasible in polynomial time over games defined on trees. In fact, it was an open problem whether or not this tractability result holds over classes of graphs properly including acyclic ones. The main contribution of the paper is to provide a positive answer to this question, by showing that the Shapley value is tractable for matching games defined over graphs having bounded treewidth. The proposed technique has been implemented and tested on classes of graphs having different sizes and treewidth at most three. ## Full text ## 1 Introduction Coalitional games are mathematical models suited to study value distribution problems among rational agents that can obtain higher payoffs by collaborating with each other rather than by acting in isolation [Osborne and Rubinstein, 1994]. In the paper, we focus on the problem of computing the Shapley value [Shapley, 1953] in matching games, a class of coalitional games where the value that agents guarantee to themselves is defined in terms of matchings over an underlying graph. In particular, let G=(N,E) be a graph whose set N of nodes is transparently viewed as a given set of agents. Then, for each coalition C ⊆ N, the value vG(C) that agents in C achieve by collaborating is given by the cardinality of a maximum matching 1 in the subgraph induced by C. Example 1.1. Consider the graph G = (N,E) in Figure 1, with N = {a, b, c, d, i} being the set of its nodes. A matching in this graph is M = {{a, i}, {b, c}}, and is depicted in bold. Note that there is no matching including more than two edges, so that vG(N) = 2. The figure also reports the subgraphs induced by the nodes in {a, d, c, i} and 1 A generalization of these games can be defined by equipping graphs with edge-weighing functions and by looking for weighted matchings. This extension is not considered in the paper. Figure 1: The graph G and the matching M in Example 1.1 (left). The subgraphs induced by two coalitions (right). ![Image](https://ijcai.org/proceedings/2017/fulltext/145/image_000000_185704d9dbb86091e88f92235c129a785bd01197ce4085175d3418a06a0372fb.png) {b, c, d, i}. Again, maximum matchings consisting of two edges are evidenced. Therefore, we can immediately conclude that vG({a, d, c, i}) = vG({b, c, d, i}) = 2. ✁ Matching games have attracted much attention in the literature, due to their wide spectrum of applicability. For instance, when restricted to bipartite graphs, they go under the name of assignment games and form a natural model to study distribution problems in matching markets (see, e.g., [Roth and Sotomayor, 1990; Shapley and Shubik, 1971]). Several results are already known in the literature about the complexity of computing over them solution concepts, that is, value distributions embodying desirable fairness and stability requirements. For instance, results have been derived for the core [Deng et al., 1999; Alkan and Gale, 1990; Chalkiadakis et al., 2016], the least core [Kern and Paulusma, 2003], and the nucleolus [Bir´o et al., 2011; Kern and Paulusma, 2003; Chen et al., 2012; Greco et al., 2014]. Aziz and de Keijzer [2014] observed that computing the Shapley value is generally intractable over matching games, formally it is #P-complete. Moreover, they showed that it is computable in polynomial time when the maximum degree of the underlying graphs is two, and they asked whether this result can be extended to a non-trivial class of graphs of degree at least three. The question has been then addressed by Bousquet [2015], who showed that the Shapley value over trees can be computed in polynomial time, and left open the problem of assessing whether the result can be extended to larger classes of structures, such as the graphs having bounded treewidth [Robertson and Seymour, 1984]. In the paper, we provide a positive answer to this question left open in the literature. The result is established via a polynomial-time algorithm whose design exploits: (i) some useful characterizations we derive for certain properties of matchings, (ii) an encoding for such properties in terms of monadic second order logic (MSO) formulas, and (iii) known tractability results for MSO formulas over graphs having bounded treewidth. As a further (more practical) contribution, the algorithm has been implemented and its scalability has been experimentally validated. Notably, our analysis and result also apply to the Banzhaf value [Banzhaf, 1965], a closely-related solution concept. ## 2 Preliminaries Matching Games. Let G = (N,E) be a graph, where N and E are the sets of its nodes and edges, respectively. Any edge e ∈ E is a subset of nodes with |e| = 2. Recall that a set M ⊆ E is a matching (in G) if e1 ∩ e2 = ∅, for each pair of distinct edges e1, e2 ∈ M. We say that M is maximum if |M| ≥ |M ′ |, for each matching M ′ . The cardinality of a maximum matching in G is denoted by max(G). The matching game associated with the graph G = (N, E) is the tuple GG=〈N, vG〉, where nodes in N are transparently viewed as agents. Moreover, vG is the function associating with each coalition C ⊆ N the value vG(C) = max(G[C]), with G[C] being the subgraph induced by the nodes in C. In the paper, we are interested in the computation of solution concepts for matching games, i.e., of ways of dividing the total value vG(N) over each agent i ∈ N. In particular, we focus on the Shapley value, which is a well-known solution concept such that the payoff associated with each agent i ∈ N is Treewidth. A tree decomposition of a graph G = (N, E) is a pair 〈T, χ〉, where T is a tree, and χ is a labeling function assigning to each vertex p in T a set of nodes χ(p) ⊆ N, such that the following conditions are satisfied: (1) for each node x ∈ N, there exists p in T such that x ∈ χ(p); (2) for each edge {x, y} ∈ E, there exists p in T such that {x, y} ⊆ χ(p); and, (3) for each node x ∈ N, the subgraph of T induced by all nodes p such that x ∈ χ(p) is connected. The width of 〈T, χ〉 is the number maxp∈T (|χ(p)| - 1). The treewidth of G, denoted by tw(G), is the minimum width over all its tree decompositions. Treewidth is a true generalization of acyclicity: G is acyclic if, and only if, tw(G) = 1. A class of graphs has bounded treewidth if there is some k with tw(G) ≤ k, for every graph G in the class (see [Gottlob et al., 2016] for a recent survey on decomposition methods). Example 2.1. Consider the graph G in Figure 1. We have tw(G) > 1, for instance because of the cycle over the nodes a, c, and d. In fact, tw(G) = 2 holds, as it is witnessed by the tree decomposition reported in Figure 2. ✁ ## 3 Useful Properties onMaximumMatchings The first ingredient for showing tractability over bounded treewidth matching games is to derive some properties of maximummatchings that simplify the subsequent analysis. Figure 2: A width-2 tree decomposition of G. ![Image](https://ijcai.org/proceedings/2017/fulltext/145/image_000001_6c911d526cb490567d4665d71f676de82f51f6bf6684ec0dadf5c7d8198dec40.png) Let M be a matching in a graph G = (N,E). A node x ∈ N is said M-matched if there is some edge e ∈ M with x ∈ e; otherwise, x is M-exposed. A path is a sequence of distinct nodes π1, ..., πm, with m > 1, such that {πj, πj+1} ∈ E, for each j ∈ {1, ...,m - 1}. The path is said M-alternating if each pair of adjacent edges satisfy {πj, πj+1} ∈ M and {πj+1, πj+2} ̸∈ M, or vice-versa (j ∈ {1, ...,m- 2}). Moreover, the path is M-augmenting if it is M-alternating, and π1 and πm are M-exposed; in fact, they are the only M-exposed nodes occurring in the path. Note that M is a maximum matching if, and only if, there is no M-augmenting path [Berge, 1957]. Example 3.1. Consider again the graph G and the matching M of Figure 1. Note that d is M-exposed and, for instance, that i, a, d is M-alternating. However, i is M-matched and thus the path is not M-augmenting. In fact, there is no Maugmenting path, as M is a maximum matching. ✁ The following definition introduces a crucial notion for analyzing matching games. Definition 3.2. A node x ∈ N is blocked by a matching M if - x is M-exposed, and - for each M-alternating path π1, ..., πm with π1 = x, it holds that πm is M-matched. Example 3.3. Consider node i in our running example. It is easy to check that i is not blocked by the matching M = {{a, i}, {b, c}}. Moreover, note that i is not blocked by the matching {{b, c}}, while it is blocked by {{a, d}, {b, c}}. ✁ Actually, since any single edge is an alternating path, the following is an equivalent characterization of Definition 3.2. Fact 3.4. A node x ∈ N is blocked by M if, and only if, for each M-alternating path π1, ..., πm with π1 = x, it holds that πm is M-matched and {π1, πm} ̸∈ M. We next show that, for this notion, it is not necessary to focus on maximum matchings. Lemma 3.5. A node i ∈ N is blocked by some maximum matching if, and only if, it is blocked by some matching. Proof Sketch. Assume that i is blocked by a matching M1 for which there exists an M1-augmenting path π′1 , ..., π′h . Consider the matching M2 obtained from M1 by removing all edges traversed by π′1 , ..., π′h and by adding all edges in E \ M1 traversed by π′1 , ..., π′h . That is, M2 is the matching obtained by "augmenting" M1 via the path π′1 , ..., π′h . Clearly, |M2| > |M1|. Moreover, note that each node π′j , with j ∈ {1, ..., h}, is not M2-exposed. Now, let ¯π1, ..., ¯πq be any M2-alternating path with ¯π1 = i. We shall show that the node ¯πq is not M2-exposed and {¯π1, ¯πq} ̸∈ M2. Claim. ¯π1, ..., ¯πq and π′1 , ..., π′h do not share any edge. By contradiction, consider the smallest index k ∈ {1, ..., q-1} and an index j ∈ {1, ..., h-1} such that π′j = ¯πk and π′j+1 = ¯πk+1. Note that if k = 1, then the path ¯πk, π′j+1 , ..., π′h would witness that i is not blocked by M1, which is impossible. Indeed, we would have that ¯πk = i and that ¯πk, π′j+1 , ..., π′h is M1-alternating, with π′h being M1-exposed (for this latter property, just recall that π′1 , ..., π′h is M1-augmenting). This means that we necessarily have k > 1, and that ¯π1, ..., ¯πk is an M1-alternating path. Now, in the case where j = 1 holds, we have ¯πk = π′1 . Therefore, the path ¯π1, ..., ¯πk would again witness that i is not blocked by M1, which is impossible. So, we have j > 1. Hence, the node ¯πk = π′j is adjacent to the nodes ¯πk-1, π′j-1 , and ¯πk+1 = π′j+1 . Recall that π′1 , ..., π′h is M1-alternating and assume first that the edge {π′j , π′j-1 } is in M1. Then, {¯πk-1, π′j } ̸∈ M1 because π′j (= ¯πk) is matched to someone else. Because M1 and M2 are equal for edges in the path ¯π1, ..., ¯πk below k, it follows that ¯π1, ..., ¯πk-1, π′j , π′j-1 , ..., π′1 is M1-alternating. The same holds if we assume instead that the edge {π′j , π′j-1 } is not in M1. Indeed, in this case {π′j , π′j+1 } ∈ M1 and thus, by definition of M2, {¯πk, ¯πk+1} ̸∈ M2 and {¯πk-1, ¯πk} ∈ M2 by alternation, that is, {¯πk-1, π′j } ∈ M1, because the two matchings are equal below k. Again, we get that ¯π1, ..., ¯πk-1, π′j , π′j-1 , ..., π′1 is M1-alternating. Since π′1 is M1-exposed, this contradicts that i is blocked byM1. ⋄ Given the above claim, we derive that ¯π1, ..., ¯πq is also M1-alternating; hence, {¯π1, ¯πq} ̸∈ M1. It then follows that {¯π1, ¯πq} ̸∈ M2, because we have already observed that ¯π1 = i cannot occur in the path π′1 , ..., π′h and thus cannot become M2-matched. To conclude, we have then to show that ¯πq is M2-matched. This is trivial if ¯πq ∈ {π′1 , ..., π′h }. Otherwise, if ¯πq ̸∈ {π′1 , ..., π′h }, then ¯πq is M2-matched because it is M1-matched and it does not occur in the path where the two matchings may differ. Now, either M2 is a maximum matching, or we can repeat the above construction, until we eventually get a sequence M1,M2, ....,Mℓ of matchings such that i is blocked by each of them and |M1| < |M2| < ... < |Mℓ|, with the latter being a maximum matching of the given graph. Example 3.6. Recall from Example 3.3 that node i is blocked by the matching {{a, d}, {b, c}}. This is actually a maximum matching. In fact, it can be checked that {{a, d}, {b, c}} is the only matching blocking i. ✁ ## 4 Characterization of Marginal Contribution Our second step is to relate the fact that an agent i is blocked (cf. Definition 3.2) with the value of the quantity vG(C ∪ {i}) - vG(C), for each given C ⊆ N, occurring in the definition of the Shapley value. Note that this value is known as the marginal contribution of agent i to coalition C ∪ {i}. Assume hereinafter that C ⊆ N is a coalition and let i be a node in N \C. We show that the condition of i being blocked by some matching in the subgraph G[C ∪ {i}] precisely determines the marginal contribution of i to C ∪ {i}-note in the proof the role played by Lemma 3.5. Figure 3: A matching that does not block node i (left). A maximum matching that blocks i (right). ![Image](https://ijcai.org/proceedings/2017/fulltext/145/image_000002_2ae7574de625429345aa92348dff21f77ff0f9898e1ef30063514b19207ff479.png) Lemma 4.1. The following statements are equivalent: - (1) vG(C ∪ {i}) - vG(C) = 0; - (2) i is blocked by some matchingM in G[C ∪ {i}]. Proof. (1)⇒(2) Let M be a maximum matching in G[C]. Since vG(C ∪ {i}) - vG(C) = 0, M is also a maximum matching in G[C ∪ {i}]. Consider, then, any M-alternating path π1, ..., πm in G[C ∪ {i}] with π1 = i. Since M is a matching in G[C] and i ̸∈ C, then π1 is clearly M-exposed in G[C∪{i}]. In particular, {π1, πm} ̸∈ M. Assume now, by contradiction, that πm is M-exposed, too. Then, π1, ..., πm is M-augmenting in G[C ∪ {i}], which is impossible. (2)⇒(1) Because of Lemma 3.5, we can assume that M is a maximum matching in G[C ∪ {i}]. Because i is blocked by M, we know that i must be M-exposed. Then, M is also a maximum matching in G[C] and we have concluded, since vG(C ∪ {i}) - vG(C) = 0 holds. We continue the chain of equivalences of Lemma 4.1, by providing a number of conditions that can easily be checked. In the following, given the graph G = (N,E), we define rE as the set of pairs ⋃{x,y}∈E {(x, y), (y, x)}. Lemma 4.2. The following statements are equivalent: - (2) i is blocked by some matchingM in G[C ∪ {i}]; (3) There are sets B ⊆ rE, I ⊆ N, and O ⊆ N satisfying on G[C ∪ {i}] the conditions (a),...,(f) of Figure 4. Before providing the proof of the result, consider the coalition C = {a, b, c, d} and Figure 3, which shows two examples of sets B, I, and O. Intuitively, B encodes some matching, whose edges are however oriented according to the way they are traversed along some alternating path starting at node i. Any edge can actually be traversed in both directions. For instance, for the matching {{a, d}, {b, c}}, the paths i, a, d, c, b and i, b, c, d, a show that the two edges {a, d} and {b, c} can be traversed in both directions. Note that the sets on the left part of Figure 3, with B = {(b, c)} violate Condition (d). Instead, the sets on the right part of Figure 3, with B = {(a, d), (b, c), (d, a), (c, b)} satisfy all conditions and, by Lemma 4.2, they witness that i is blocked by some matching (in fact, precisely by the maximum matching {{a, d}, {b, c}}). Proof Sketch of Lemma 4.2. (2)⇒(3) Assume that i is blocked by some matching M in G[C ∪ {i}], and consider (a) i ̸∈ I; The distinguished node i does not belong to the set I. The set B is meant to encode all the edges of the matching M in G[C ∪ {i}] (cf. Lemma 4.2.(2)), by adding an orientation to them. The condition states that for each element (x, y) ∈ B, the destination node y belongs to I. If the source node of an edge in G[C ∪ {i}] belongs to I, then the destination node must belong to O. Every node x ∈ O must have an outgoing edge that belongs to B. By looking at the undirected version of B, every node cannot have more than one incident edge. For the distinguished node i, every outgoing edge does not belong to B and the destination node belongs to O. Figure 4: Properties in Lemma 4.2.(3) that must hold on sets B ⊆ rE, I ⊆ N, and O ⊆ N. the sets B, I, and O built as follows. For each edge {x, y} in G[C ∪{i}] if there is an M-alternating path π1, ..., πm in this subgraph with π1 = i and such that x = πj and y = πj+1, for some index j ∈ {1, ..., m-1}, and {x, y} is in M, then (x, y) is in B, x ∈ O, and y ∈ I. For each edge {i, y} ∈ E \M, we set y ∈ O. No other element is in B, I, or O. Note that the sets trivially satisfy (a), (b), and (e). Concerning (c), let π1, ..., πm be an M-alternating path in G[C ∪ {i}] with π1 = i such that, for some index j ∈ {2, ...,m}, πj = x with x ∈ I and {πj-1, πj} ∈ M hold. Note that πj-1 ∈ O. Then, assume that {x, y} is in E with y ∈ C and y ̸= πj-1. We have that {x, y} ̸∈ M and π1, ..., πj , y is M-alternating. Since i is blocked by M, y is M-matched and {π1, y} ̸∈ M. Therefore, there is an edge {y, z} ∈ M and the path π1, ..., πj , y, z is M-alternating, too. By construction, this entails that y ∈ O. Concerning (d), assume first that there is anM-alternating path π1, ..., πm with π1 = i such that, for some index j ∈ {1, ..., m - 1}, πj = x with x ∈ O and where {πj , πj+1} ∈ M holds. In this case, (x, πj+1) ∈ B holds, by construction. The other possibility is that {i, x} ∈ E \ M. In this case, since i is blocked by M, there must be a node z ̸= i such that {x, z} ∈ M. Again, by construction, we have (x, z) ∈ B. Concerning (f), note that there is no x ∈ N with {i, x} ∈ M; otherwise, the path i, x would witness that i is blocked by M. By construction, we hence have (i, x) ̸∈ B and x ∈ O. (3)⇒(2) Assume that B, I, and O satisfy all the properties listed in the statement. Consider the set M = {{x, y} | (x, y) ∈ B, x ∈ C ∪ {i}, y ∈ C ∪ {i}}. Because of (e), it is immediate that M is a matching in G[C ∪ {i}]. Moreover, by (a), (b), and (f), we derive that there is no node y ∈ N such that {i, y} is inM, that is, i isM-exposed. Consider then any M-alternating path π1, ..., πm of G[C ∪{i}] with π1 = i. We shall show that πm is M-matched. To this end, we first claim that, for each natural number h ≥ 1 such that 2h+1 ≤ m, it holds that {π2h-1, π2h} ̸∈ M, (π2h, π2h+1) ∈ B, π2h ∈ O. For h = 1, we have just to observe that {π1, π2} ̸∈ M and, by (f) π2 ∈ O. Moreover, from (d) we necessarily have (π2, z) ∈ B with z = π3, because {π2, π3} ∈ M, by alternation, and (e) must hold. So, let us assume that the property holds at some natural number h, and we show that it holds at h + 1 with 2(h + 1) + 1 ≤ m, too. Indeed, we know that (π2h, π2h+1) ∈ B and hence {π2h, π2h+1} ∈ M, by construction. Moreover, by (b), π2h+1 ∈ I. By (c), π2h+2 ∈ O. By alternation, {π2h+1, π2h+2} ̸∈ M. Then, as in the base case, by (d) and (e), (π2h+2, π2h+3) ∈ B and {π2h+2, π2h+3} ∈ M. In the light of this result, if m is odd, then we can immediately conclude that πm is M-matched. Otherwise, we know that (πm-2, πm-1) ∈ B. By (b), πm-1 ∈ I. By (c), πm ∈ O. By (d), there is a node z such that (πm, z) ∈ B. Then, we conclude that πm is M-matched. ## 5 Tractability Results We are now ready to discuss the third ingredient of our elaboration, namely the use of tractability results for the evaluation of certain logic formulas bounded-treewidth graphs. ## 5.1 MSO Formulas Recall that we viewed any graph G = (N,E) as a structure whose domain is N and where the set of its edges is encoded as a binary relation rE = ⋃{x,y}∈E {(x, y), (y, x)}. Over structures of this kind, we can build monadic second order (MSO) logic formulas by using the relation rE, individual variables, the logical connectives ∨, ∧, and ¬, and the quantifiers ∃ and ∀. Moreover, these formulas allow the use of node and edge variables, ranging over the possible subsets of N and rE, respectively, of the membership relation ∈, and of the quantifiers ∃ and ∀ over node and edge variables. In addition, it is often convenient to use symbols like =, ⊆, ⊂, ∩, ∪, and →with their usual meaning, as abbreviations. The fact that a MSO formula φ holds over G is denoted by G |= φ. Example 5.1. The well-known 3-coloring problem on G = (N, E) can be encoded via the following MSO formula φ: Indeed, G |= φ if, and only if, there exists a partition of the nodes in N into three disjoint sets of nodes R, B, and Y (corresponding to nodes colored red, blue, and yellow) and such that no adjacent nodes take the same color. ✁ A basic relationship between treewidth and MSO is illustrated in the following master theorem. Theorem 5.2 (cf. [Courcelle, 1990]). Let φ be a fixed MSO sentence, let k be a fixed constant, and let Ck be a class of graphs having treewidth bounded by k. Then, for each G ∈ Ck, deciding whether G |= φ is feasible in linear time. For instance, from the above theorem and Example 5.1, we can immediately conclude that 3-colorability is a property that can be checked in linear time on classes of graphs having bounded treewidth-in general, the problem is known to be NP-complete (see, e.g., [Garey and Johnson, 1979]). To our ends, however, we need a recently proposed histogram version of Courcelle's theorem, which allows us to count solutions of a given size to MSO formulas on graphs having bounded treewidth. The result it recalled below. Let φ(C) be a MSO sentence, where C is a free, i.e., not quantified, node set variable and, for each ˆ C ⊆ N, let φ( ˆ C) denote the formula where C is fixed to be the set ˆ C. Then, for each graph G = (N,E) and each natural number d ∈ {1, ..., |N|}, define histogram(φ(C), G, d) as the number of subsets ˆ C ⊆ N with | ˆ C| = d and such that G |= φ( ˆ C). Theorem 5.3 (simplified from [Elberfeld et al., 2010]). Let φ(C) be a fixed MSO sentence, let k be a fixed constant, and let Ck be a class of graphs having treewidth bounded by k. Then, for each G = (N, E) ∈ Ck and for each natural number d ∈ {1, ..., |N|}, computing histogram(φ(C),G, d) is feasible in deterministic logspace (hence, polynomial time). For an illustration, let φ(R) be the formula obtained from the one discussed in Example 5.1 by dropping the existential quantification of R. Then, histogram(φ(R),G, 3) returns the number of triples of nodes that can be colored with the same color (red) in some valid coloring of G. According to the above result, this number can be computed in polynomial time, whenever G is taken from some class of graphs having bounded treewidth. ## 5.2 Putting It All Together The above result is the basis for our complexity analysis of the Shapley value. The characterization illustrated in Section 3 for the marginal contribution will also play a crucial role here. Theorem 5.4. The Shapley value can be computed in polynomial time on matching games defined over any class of graphs having bounded treewidth. Proof. Let us start by noticing that, for each agent i ∈ N, the Shapley value can be rewritten as follows: where n = |N| and, for each h ∈ {0, ..., n - 1}, it holds that We show that the value of the expression in Equation 1 can be computed in polynomial time. The basic observation is that we can build a Monadic Second Order (MSO) formula φi(C) encoding conditions (a)- (f) in Lemma 4.2, where G is viewed as a relational structure over domain N and relation rE. In particular, B is an existentially-quantified edge-set variable, I and O are existentially-quantified node-set variables, and C is a free node-set variable. Then, given Lemma 4.1 and Lemma 4.2, the number of coalitions C ⊆ N \ {i} for which vG(C ∪ {i}) -vG(C) = 0 holds and with |C| = h coincides with the number of coalitions ˆ C ⊆ N \ {i} with | ˆ C| = h for which G |= φi( ˆ C). This number can be computed in polynomial time because of Theorem 5.3 and, based on it, the value of the expression in Equation 1 can be easily computed (in polynomial time, too) by observing that vG(C ∪ {i}) - vG(C) ∈ {0, 1}, for each C ⊆ N \ {i}. A similar approach can be used to prove the tractability on graphs having bounded treewidth of the Banzhaf value, 2 for which the payoff of i is In this case we are even able to derive a linear time algorithm, rather than a polynomial-time one. Theorem 5.5. The Banzhaf value can be computed in linear time on matching games defined over any class of graphs having bounded treewidth. Proof Sketch. We shall show that, for each node i ∈ N, we can compute in linear time the value of the expression Indeed, we can proceed as in the proof of Theorem 5.4, by eventually noticing that the number of coalitions C ⊆ N \{i} for which vG(C ∪{i})-vG(C) = 0 holds coincides with the number of coalitions ˆ C ⊆ N \ {i} for which G |= φi( ˆ C). In this case, however, a linear-time algorithm follows and thus we conclude, by recalling that counting all instantiations of a free node variable leading to satisfy a given MSO formula was shown to be feasible in linear time over graphs having bounded treewidth [Courcelle et al., 2001]. 2 The question of whether this value is intractable over arbitrary matching games is not addressed in the literature, and is an interesting avenue of research, though outside the scope of this paper. Figure 5: Illustration of directed edge encoding. ![Image](https://ijcai.org/proceedings/2017/fulltext/145/image_000003_ae0c1099c306ceb7b41d29bf2efcc4fbdc3d866ceb09ccb1d095ac99b257d12e.png) ## 6 MSO in Practice An interesting feature of our approach to show the tractability of the Shapley value over bounded treewidth games is that the MSO encoding provides us with a declarative, yet "executable" specification for its computation. Indeed, we directly followed the steps shown in the proof of Theorem 5.4 by implementing them in a JAVA system prototype and by delegating to the MSO solver Sequoia [Langer, 2013] the computation of the histogram of the formula in that proof Implementation Issues. Note that Sequoia supports the evaluation of MSO formulas defined over graphs whose nodes can be equipped with some input labels. However, only undirected graphs can be dealt with. This is not problematic when checking the existence of an edge (x, y) ∈ rE, since rE is a symmetric relation. However, the set B in Lemma 4.2 is a set of directed edges. In order to deal with the orientation of edges in B, we transformed every undirected edge {x, y} in the input graph by adding two auxiliary nodes labeled "fresh", as depicted in Figure 5. Then, in the specifications reported in Figure 4, a set of "fresh" nodes BN can be used to simulate the set B, with the intended meaning that (x, y) ∈ B (resp., (y, x) ∈ B) if, and only if, there are two fresh nodes e(x,y) and e(y,x) as in Figure 5 and where e(x,y) ∈ BN (resp., e(y,x) ∈ BN). Benchmark. In order to assess the performances of the prototype implementation, we considered a benchmark of synthetic instances taken from three distinct families of graphs, namely (complete binary) trees, ladder graphs, and Halin graphs. These are well-known classes of graphs (whose treewidth is 1, 2, and 3, respectively) which can be used to evaluate the behavior of the prototype for different treewidth values and for growing sizes of the input graphs. In addition, we considered some real graphs corresponding to author relationships of scientific works in a university (see [Greco and Scarcello, 2013; 2014]). Results. Experiments have been performed on a dedicated machine equipped with an Intel Core i7-3770k 3.5 GHz processor, 12 GB (DDR 1600 MHz) of RAM, and operating system Linux Debian Jessie. Our Java algorithms were executed on the JDK 1.8.0 05-b13 and the GNU g++-4.9 compiler was used to compile Sequoia. Results are reported in Table 1. It can be checked that, for any fixed treewidth value, the prototype nicely scales w.r.t. the size considered of the input graphs. As expected, however, performances deteriorate at the growing of the treewidth. In addition to the timings, it is very interesting to consider the overall number of blocked coalitions that Sequoia has discovered, for each given instance of the benchmark. In many cases, this number is impressive, thereby witnessing the effectiveness of the symbolic computation exploited by the MSO solver. In fact, we remark that results are reported for graphs up to 100 nodes, for which a na¨ıve computation method based on explicitly enumerating all possible (2100 ) coalitions is clearly unfeasible. Table 1: Summary of experimental results. | INSTANCE | N. OF NODES | N. OF EDGES | TW | TIME [SEC] | N. OF BLOCKING COALITIONS | |------------|---------------|---------------|------|--------------|-----------------------------| | TREE | 10 | 9 | 1 | 1.9 | 301 | | TREE | 20 | 19 | 1 | 2.7 | 242451 | | TREE | 30 | 29 | 1 | 2.7 | 344506149 | | TREE | 40 | 39 | 1 | 3.0 | 3.28E+11 | | TREE | 50 | 49 | 1 | 3.0 | 2.96E+14 | | TREE | 60 | 59 | 1 | 3.2 | 2.70E+17 | | TREE | 70 | 69 | 1 | 3.2 | 1.46E+20 | | TREE | 80 | 79 | 1 | 3.3 | 3.65E+20 | | TREE | 90 | 89 | 1 | 3.3 | 4.96E+20 | | TREE | 100 | 99 | 1 | 3.9 | 6.01E+20 | | LADDER-3 | 6 | 7 | 2 | 37.1 | 16 | | LADDER-6 | 12 | 16 | 2 | 144.2 | 1024 | | LADDER-9 | 18 | 22 | 2 | 57.8 | 65536 | | LADDER-12 | 24 | 34 | 2 | 19.6 | 4194304 | | LADDER-15 | 30 | 43 | 2 | 22.7 | 268435456 | | LADDER-18 | 36 | 52 | 2 | 20.0 | 17179869184 | | LADDER-21 | 42 | 61 | 2 | 458.3 | 1.09E+12 | | LADDER-24 | 48 | 70 | 2 | 20.1 | 7.03E+13 | | LADDER-27 | 54 | 79 | 2 | 612.6 | 4.50E+15 | | LADDER-30 | 60 | 88 | 2 | 33.7 | 2.88E+17 | | HALIN-6 | 6 | 9 | 3 | 195.7 | 14 | | HALIN-8 | 8 | 12 | 3 | 930 | 58 | | HALIN-10 | 10 | 16 | 3 | 194.4 | 237 | | HALIN-12 | 12 | 18 | 3 | 3510.2 | 867 | | HALIN-15 | 15 | 23 | 3 | 539.6 | 6990 | | COAUTH-1 | 10 | 12 | 2 | 7.5 | 230 | | COAUTH-2 | 15 | 15 | 2 | 20.3 | 5040 | | COAUTH-3 | 20 | 27 | 3 | 435.4 | 193998 | | COAUTH-4 | 25 | 28 | 2 | 95.4 | 5909504 | | COAUTH-5 | 30 | 37 | 3 | 477.6 | 211235477 | | COAUTH-7 | 35 | 42 | 2 | 70.1 | 9817601112 | | COAUTH-8 | 40 | 45 | 2 | 95.4 | 2.37E+11 | | COAUTH-9 | 45 | 50 | 2 | 84.7 | 1.10E+13 | ## 7 Conclusion Computing the Shapley value has been shown to be #Pcomplete on different classes of games (see, e.g., [Deng and Papadimitriou, 1994; Nagamochi et al., 1997; Bachrach and Rosenschein, 2009]), including matching games [Aziz and de Keijzer, 2014]. Moving from these bad news, we have faced the questions left open by [Aziz and de Keijzer, 2014; Bousquet, 2015], by showing that the Shapley value (and the Banzhaf value) of matching games can be computed in polynomial time over graphs having bounded treewidth. Note that for the related class of allocation games [Moulin, 1992], the Shapley value is also known to be #P-complete, but it is tractable when restricted over graphs having bounded treewidth [Greco et al., 2015]. Despite the similarities with allocation games, inspection reveals that the approach of [Greco et al., 2015] cannot be extended to matching games. Moreover, our approach differs from the one used by [Bousquet, 2015] to show tractability of matching games over trees. An interesting avenue of further research is to assess whether, on bounded treewidth games, the Shapley value is not only tractable, but even fixed-parameter tractable, that is, solvable in time f(k) · ||G||O(1) , for each G ∈ Ck, for some function f depending only on the width k. Moreover, it is open whether tractability still holds over weighted graphs. ## References 1. [Alkan and Gale, 1990] Ahmet Alkan and David Gale. The core of the matching game. Games and Economic Behav- ior, 2(3):203-212, 1990. 2. [Aziz and de Keijzer, 2014] Haris Aziz and Bart de Keijzer. Shapley meets shapley. In Proc. of STACS'14, pp. 99-111. 3. [Bachrach and Rosenschein, 2009] Yoram Bachrach and Jeffrey S. Rosenschein. Power in threshold network flow games. Autonomous Agents and Multi-Agent Systems, 18(1):106-132, 2009. 4. [Banzhaf, 1965] John F. Banzhaf. Weighted Voting Doesn't Work: A Mathematical Analysis. Rutgers Law Rev., 19:317-343, 1965. 5. [Berge, 1957] Claude Berge. Two Theorems in Graph The- ory. Proceedings of the National Academy of Sciences of the United States of America, 43(9):842-844, 1957. 6. [Biró et al., 2011] Péter Biró, Walter Kern, and Daniël Paulusma. Computing solutions for matching games. In- ternational Journal of Game Theory, 41(1):75-90, 2011. 7. [Bousquet, 2015] Nicolas Bousquet. The shapley value of matching games on trees. http://www.math.mcgill.ca/ nbousquet/shapley.pdf, 2015. 8. [Chalkiadakis et al., 2016] Georgios Chalkiadakis, Gian- luigi Greco, and Evangelos Markakis. Characteristic function games with restricted agent interactions: Core- stability and coalition structures. Artificial Intelligence, 232:76-113, 2016. 9. [Chen et al., 2012] Ning Chen, Pinyan Lu, and Hongyang Zhang. Computing the nucleolus of matching, cover and clique games. In Proc. of AAAI'12, pp. 1319-1325. 10. [Courcelle, 1990] Bruno Courcelle. Graph rewriting: An al- gebraic and logic approach. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics. The MIT Press, 1990. 11. [Courcelle et al., 2001] Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Applied Mathemat- ics, 108:23-52, 2001. 12. [Deng and Papadimitriou, 1994] Xiaotie Deng and Chris- tos H. Papadimitriou. On the complexity of cooperative solution concepts. Mathematics of Operations Research, 19:257-266, 1994. 13. [Deng et al., 1999] Xiaotie Deng, Toshihide Ibaraki, and Hi- roshi Nagamochi. Algorithmic aspects of the core of com- binatorial optimization games. Mathematics of Operations Research, 24(3):751-766, 1999. 14. [Elberfeld et al., 2010] Michael Elberfeld, Andreas Jakoby, and Till Tantau. Logspace Versions of the Theorems of Bodlaender and Courcelle. In Proc. of FOCS'10, pp. 143- 152. 15. [Garey and Johnson, 1979] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., 1979. [Gottlob et al., 2016] Georg Gottlob, Gianluigi Greco, Nicola Leone, and Francesco Scarcello. Hypertree decompositions: Questions and answers. In Proc. of PODS'16, pp. 57-74. 16. [Greco et al., 2015] Gianluigi Greco, Francesco Lupia, and Francesco Scarcello. Structural tractability of shapley and banzhaf values in allocation games. In Proc. of IJCAI'15, pp. 547-553. 17. [Greco et al., 2014] Gianluigi Greco, Enrico Malizia, Luigi Palopoli, and Francesco Scarcello. The complexity of the nucleolus in compact games. Transactions on Computa- tion Theory, 7(1):3:1-3:52, 2014. 18. [Greco and Scarcello, 2013] Gianluigi Greco and Francesco Scarcello. Fair division rules for funds distribution: The case of the italian research assessment program (VQR 2004-2010). Intelligenza Artificiale, 7(1):45-56, 2013. 19. [Greco and Scarcello, 2014] Gianluigi Greco and Francesco Scarcello. Mechanisms for fair allocation problems: No- punishment payment rules in verifiable settings. Journal of Artificial Intelligence Research, 49:403-449, 2014. 20. [Kern and Paulusma, 2003] Walter Kern and Daniel Paulusma. Matching games: The least core and the nucleolus. Mathematics of Operations Research, 28(2):294-308, 2003. 21. [Langer, 2013] Alexander Langer. Fast algorithms for de- composable graphs. PhD thesis, RWTH Aachen Univer- sity, 2013. 22. [Moulin, 1992] Herve Moulin. An application of the Shap- ley value to fair division with money. Econometrica, 60(6):1331-1349, 1992. 23. [Nagamochi et al., 1997] Hiroshi Nagamochi, Dao-Zhi Zeng, Naohisa Kabutoya, and Toshihide Ibaraki. Complexity of the minimum base game on matroids. Mathematics of Operations Research, 22:146-164, 1997. 24. [Osborne and Rubinstein, 1994] Martin J. Osborne and Ariel Rubinstein. A Course in Game Theory. The MIT Press, 1994. 25. [Robertson and Seymour, 1984] Neil Robertson and Paul D. Seymour. Graph minors iii: Planar tree-width. Journal of Combinatorial Theory, Series B, 36(1):49-64, 1984. 26. [Roth and Sotomayor, 1990] Alvin. E. Roth and Marilda A. Oliveira Sotomayor. Two-Sided Matching: A Study in Game Theoretic Modelling and Analysis. Cambridge Uni- versity Press, 1990. 27. [Shapley, 1953] Lloyd S. Shapley. A value for n-person games. Contributions to the theory of games, 2:307-317, 1953. 28. [Shapley and Shubik, 1971] Lloyd S. Shapley and Martin Shubik. The assignment game I: The core. International Journal of Game Theory, 1(1):111-130, 1971.