Convexity of b-matching Games

1 Introduction

1.1 Background andMotivation

Finding a "reasonable" matching is a fundamental research topic in algorithmic cooperative game theory [Deng and Fang, 2008]. After the seminal work of Shapley and Shubik 1971, the matching game and its variants have been extensively studied.

In this study, we consider the b-matching game [Deng et al., 1999], which is also known as multi-partner assignment game [Sotomayor, 1992; Bir´o et al., 2018]. This game generalizes the matching game [Deng et al., 1999; Bir ´o et al., 2012; Kern and Paulusma, 2003] to allow each individual to have more than one partner. Such a multi-partner setting makes the situation interesting and complex; thus, the game attracts the attention of theorists. Moreover, the game has several real-world applications such as the assignment of roommates [Granot, 1984; Tamir and Mitchell, 1998], the multiple-item version of the seller-buyer assignment [Shapley and Shubik, 1971; Bir´o et al., 2012], and the international kidney exchange [Bir´o et al., 2019]. Therefore, establishing efficient algorithms for the b-matching game is regarded as an important topic in the area.

Formally, the b-matching game is defined as follows. Let G = (V,E) be an undirected graph, where V is the set of vertices, and E is the set of edges. Through the paper, we denote by n = |V | and m = |E|. The vertices have budgets b: V → Z≥1, and the edges have weights c: E → R>0. Let X ⊆ V . A vector x ∈ ZE is a b-matching of X if it satisfies the following conditions:

where δ(v) = {(u, v) ∈ E} be the set of edges incident to v. The first condition is the budget constraint, and the second constraint requires that the support of x is contained in X. The b-matching game is a cooperative game (V, ν) whose characteristic function ν : 2V → R is defined by

The main research focus in algorithmic cooperative game theory is the complexity of finding solution concepts such as the core, the kernel, and the Shapley value. In this viewpoint, the b-matching game is much harder than the matching game. The core non-emptiness problem and the core-membership problem are solvable in polynomial time if b = 1 [Deng et al., 1999; Bir´o et al., 2012] (i.e., the matching game). However, these are co-NP-hard [Bir´o et al., 2018; Bir´o et al., 2019] if b ≥ 3; note that they also showed that these are polynomial if b ≤ 2. Therefore, it will be hopeless to obtain an element in the core in a realistic computational time.

Under these hardness results, we here focus on the convexity, which is often a computationally more tractable concept than the core non-emptiness. A cooperative game (V, ν) is convex if its characteristic function ν is supermodular, i.e., for all X, Y ⊆ V , the following inequality holds:

Any convex game has a non-empty core, and an element of the core is obtained in polynomial time using an evaluation oracle of ν. This implies that we can use the convexity as an alternative (a sufficient condition) of the core non-emptiness. Moreover, a convex game has its own benefits. For example, the Shapley value is in the core, and the kernel contains a unique point that coincides with the nucleolus, which can also be computed in polynomial time.

The b-matching game is not necessarily convex even if b = 1 [Kumabe and Maehara, 2020]. Therefore, we are interested in a condition when the game is convex. Also, we seek an algorithm that can check the convexity of a given b-matching game efficiently.

1.2 Our Contribution

In this study, we give a necessary and sufficient condition of the convexity of a b-matching game (Lemma 3.6). Based on this characterization, we propose a polynomial-time algorithm to check the convexity of a given b-matching game. Formally, the following is our main theorem.

Theorem 1.1. There is an O(n logn +mα(n)) time algorithm to check whether a given b-matching game is convex, where α is the inverse Ackermann function 1

As an application of our characterization, we derive a polynomial-time algorithm to compute the Shapley value of a convex b-matching game. Computing the Shapley value is #P-hard even if b = 1 and c(e) = 1 for all e ∈ E [Aziz and de Keijzer, 2014]; therefore, this result indicates that the convexity yields computational tractability on this game.

1.3 RelatedWork

Matching Games. Matching games are one of the wellstudied games in algorithmic cooperative game theory. Shapley and Shubik 1971 considered the assignment game, which is a 1-matching game on a bipartite graph. Several authors [Deng et al., 1999; Bir´o et al., 2012; Kern and Paulusma, 2003] studied the 1-matching game. The bmatching game is also studied by several authors within several different settings [Deng et al., 1999; Bir´o et al., 2019; Bir´o et al., 2018; Granot, 1984; Sotomayor, 1992; Tamir and Mitchell, 1998].

The b-matching game is a special case of the integral linear production game. The linear production game [Owen, 1975] is defined as follows. Let V be a set of players. For integers n and m, let A ∈ Rn×m, bv ∈ Rn for each v ∈ V , and c ∈ Rm. Then, the characteristic function ν of the linear production game is defined by

The integral linear production game [Deng et al., 2000] assumes the integrality of x to the above problem. The bmatching game is the integral linear production game in which A is the incidence matrix of the graph, and bv = b(v)ev, where ev is the v-th unit vector.

1 The inverse Ackermann function is an extremely slow-growing function, which is less than five for any practical purpose. See [Cormen et al., 2001] for the definition.

Deng et al. 2000 studied the condition of the core nonemptiness of an integral linear production game when A's entries are zero and one, and b(v) = 1 for all v ∈ V . This case is also called the packing game [Deng et al., 1999], synergy coalition game [Conitzer and Sandholm, 2006], and the hypergraph matching game [Kumabe and Maehara, 2020]. Introducing the budget b ≥ 2 makes the situation complicated. Biro et al. [Bir´o et al., 2018; Bir´o et al., 2019] showed that the core non-emptiness problem and the core membership problem are solvable in polynomial time if b(v) ≤ 2 for all v ∈ V ; however, it is co-NP-hard if b(v) ≤ 3 for all v ∈ V . This study aims at studying the b-matching from the convexity perspective.

Convexity of Games. The convexity is an important concept in algorithmic cooperative game theory [Deng et al., 1999; Shapley, 1971]. Most combinatorial games are not convex; hence, they need additional conditions to be convex [Deng and Fang, 2008]. Researchers have been devoted their effort for revealing the condition of the convexity for several games, including the minimum base game [Nagamochi et al., 1997], the maximum spanning tree game [Koh and Sanit`a, 2019; Okamoto, 2003], the minimum coloring game [Bietenhader and Okamoto, 2004], and the hypergraph matching game [Conitzer and Sandholm, 2006; Kumabe and Maehara, 2020]. This study aims at adding the b-matching game in this line of studies.

Note that the budget b affects a significant impact on the condition of the convexity. In the matching game case (i.e., b = 1), the game is convex if and only if the underlying graph is a matching, i.e., no two edges intersect [Kumabe and Maehara, 2020]. On the other hand, we can see much more complicated graph structures appear in a convex b-matching game with b ≥ 2.

2 Warm-Up: Unweighted Case

Our goal is to give a necessary and sufficient condition of the convexity of the b-matching game and derive an efficient algorithm for checking the convexity. However, the general case, which will be given in the next section, is very complicated; therefore, as a warm-up, we start from the case when the graph has no edge weights, i.e., c(e) = 1 for all e ∈ E.

The proof strategy for this case and the general case are the same. We first derive a necessary condition of the convexity by considering a small graph. Then, we prove that the derived condition is also sufficient for the convexity.

2.1 Deriving Necessary Conditions

By looking at the interaction of three vertices, we obtain the following lemma.

Lemma 2.1. Suppose that ν is supermodular. If v1, v2, v3 ∈ V satisfy (v1, v3), (v2, v3) ∈ E but (v1, v2) ̸∈ E as in Figure 1, then b(v1) + b(v2) ≤ b(v3) holds.

Proof. We first observe that the following inequality holds:

where the first line is the definition of ν, the second line is the supermodularity of ν, and the third line is from ν({v3}) = 0 and the definition of ν.

Suppose the contrary that b(v1) + b(v2) > b(v3). Then, by Eq. (2.4), we see that min{b(v1), b(v3)} + min{b(v2), b(v3)} ≤ b(v3). This indicates that b(v1) < b(v3) and b(v2) < b(v3). Therefore, b(v1) + b(v2) = min{b(v1), b(v3)}+min{b(v2), b(v3)} ≤ b(v3), which leads to a contradiction.

Using this lemma, we can determine the topology of the graph. Let V = {v1, . . . , vn} be the vertices of the graph. Without loss of generality, we assume that b(v1) ≤ · · · ≤ b(vn). For i = 0, . . . , n, let Gi = G[{v1, . . . , vi}] be the subgraph induced by the vertices {v1, . . . , vi}. 2 We denote by N(v) = {u ∈ V : (u, v) ∈ E} the set of neighbors of v.

Lemma 2.2. Suppose that ν is supermodular. If C is a connected component of Gi-1, then N(vi) ∩ C is either ∅ or C.

Proof. Suppose the contrary. Then, both C ◦ = C ∩ N(vi) and C · = C \N(vi) are non-empty. Because C is connected, there exists u1 ∈ C ◦ and u2 ∈ C · such that (u1, u2) ∈ E. By Lemma 2.1, b(u2) + b(vi) ≤ b(u1) holds. However, this contradicts to the ordering of the vertices.

Lemma 2.2 gives a "canonical representation" for the graph of a convex b-matching game. For X ⊆ V , we refer the root r(X) of X as the vertex in X with the largest index.

Let Ci be the connected component of Gi that contains vi. Note that, by Lemma 2.2, there are edges between vi and all other vertices in Ci. Let Xi,1, . . . ,Xi,ki be the connected components of Ci \ {vi}. Let Fi = {(vi, r(Xi,1)), . . . , (vi, r(Xi,ki ))} be the set of edges from vi to the connected components directed from vi. Then, we construct a directed graph T = (V, ⋃ni=1 Fi). This directed graph is a branching 3 . We refer to this branching as an auxiliary forest. By the construction and Lemma 2.2, the auxiliary forest can reconstruct the original graph by taking its comparability graph. Here, the comparability graph [Brandstadt et al., 1999] of a directed acyclic graph is an undirected graph obtained by taking the transitive closure 4 and forgetting the edge orientations. Figure 2 shows an example of a graph and the corresponding auxiliary forest.

2 For a graph G = (V,E) and a vertex subset X, the subgraph induced by X is a graph G[X] := (X,E[X]) where E[X] = {(u, v) ∈ E : u, v ∈ X}.

3 A directed graph is a branching if the in-degree of a vertex is at most one.

Now we derive a condition about the budgets using the auxiliary forest T. We introduce a few notations. Let Av be the set of proper ancestors 5 of v in T. Let Tv be the set of descendants v in T . For a vertex subset X ⊆ V , we denote by X+ the set of vertices v ∈ X that has no proper ancestor in X, and let X- := X \ X+. Note that T - v = Tv \ {v}.

Using these notations, we obtain the following lemma, which generalizes Lemma 2.1 to the more than three vertices. For X ⊆ V , we denote by b(X) = ∑v∈X b(v).

Lemma 2.3. Suppose that ν is supermodular. Then, for all v ∈ V , we have b(T - v ) ≤ b(v).

Proof. We see

where the first line is from b(u) ≤ b(v) for all u ∈ T - v and there is an edge (u, v) ∈ E because the graph is obtained by the transitive closure of T, the second line is from supermodularity, and the last line follows from ν({v}) = 0 and the fact that each edge in the optimal b-matching consumes two unit of the budget. By arranging these terms we obtain b(T - v ) ≤ b(v).

Now we obtain the following two necessary conditions of the convexity of ν.

Condition U1 G is a comparability graph of a branching.

Condition U2 For every v ∈ V , b(T - v ) ≤ b(v).

2.2 Proving the Sufficiency of Conditions

Now we prove that the above two necessary conditions, Conditions U1 and U2, are also sufficient for the convexity of ν. We first give an explicit formula of ν.

Lemma 2.4. Suppose that Conditions U1 andU2 hold. Then, ν(X) = b(X-) for all X ⊆ V .

4 The transitive closure of a directed graph D = (V, F) is a directed acyclic graph D = (V, F) such that (u, v) ∈ F if there exists a path from u to v in D.

5 Let T = (V, F) be a branching. A vertex u ∈ V is an ancestor of v ∈ V if there exists a path from u to v. Here, v is a descendant of u. We say that u is a proper ancestor (resp. proper descendant) of v if u is an ancestor (resp. descendant) of u and u ̸= v.

Proof. We prove this lemma for a connected X; the general case follows by adding the contributions of the connected components. In this case, X+ consists of a single vertex. Thus, we put X+ = {v}.

We first prove ν(X) ≥ b(X-). By Condition U1, we see that (v, u) ∈ E for all u ∈ X-. We observe that each (v, u) can be used b(u) time because Condition U1 implies b(X-) ≤ b(T - v ), and Condition U2 implies b(T - v ) ≤ b(v). Because the size of this b-matching is b(X-), we have ν(X) ≥ b(X-).

We then prove ν(X) ≤ b(X-). Each unit of an edge in a b-matching of X consumes at least one amount of budgets of vertices in X-. Therefore, ν(X) ≤ b(X-).

Using this representation, we prove that ν is supermodular.

Lemma 2.5. Suppose that Conditions U1 andU2 hold. Then, ν is supermodular.

Proof. We see that b(X+) = b(X)-b(X-) = b(X)-ν(X), where the last equality is Lemma 2.4. Thus, we prove that b(X+) is submodular in X (i.e., -b(X+) is supermodular in X).

We prove the submodularity for the case when X ∪ Y is connected; the general case follows by adding the contributions of the connected components. In this case, (X ∪ Y )+ consists of a single vertex. Thus, we put (X ∪ Y )+ = {v}. Without loss of generality, we assume that v ∈ X+.

We prove b((X ∩ Y )+) ≤ b(Y +) as follows. First,

Thus, it is sufficient to show

for each w ∈ Y +. If w ∈ (X ∩ Y )+ then (X ∩ Y )+ ∩ Tw = {w}; therefore, the above inequality holds in equality. Otherwise,

Here, the first inequality follows from w ̸∈ (X ∩ Y )+, and the second inequality is from Condition U2. Using this inequality, we obtain

Here, the last line follows from (X ∪ Y )+ = {v} = X+ because v ∈ X+.

2.3 Algorithm

Now we propose a polynomial-time algorithm to check the convexity of the b-matching game. By Lemma 2.5, it is sufficient to construct an algorithm that checks Conditions U1 and U2 efficiently.

Our algorithm, shown in Algorithm 1, maintains the family S of the connected components of G[{v1, . . . , vi}] and checks Conditions U1 and U2 in Lines 8 and 4, respectively. This algorithm gives the following theorem.

Algorithm 1 Checking the supermodularity of ν

Input: A graph G = (V, E), budgets b(v) for all v ∈ V

• 1: Sort the vertices in the non-decreasing order of the budgets. Let v1, . . . , vn be the order. 2: S ← ∅ 3: for i = 1, . . . , n do 4: if b(N(vi) ∩ {v1, . . . , vi-1}) > b(vi) then 5: return false 6: end if 7: Let Ci = {C | C ∈ S,C ∩N(vi) ̸= ∅} 8: if | ⋃C∈Ci C| ̸= |N(vi) ∩ {v1, . . . , vi-1}| then 9: return false 10: end if 11: S ← (S \ Ci) ∪ {⋃C∈Ci C ∪ {vi}} 12: end for 13: return true

Theorem 2.6. There is a O(n log n+mα(n)) time algorithm to check whether ν is supermodular, where α(n) is inverseAckerman function.

Proof. The correctness of the algorithm is clear. Now we analyze the time complexity. Sorting the vertices can be done in O(n logn) time. Line 4 is done in O(|N(vi)|) time in each iteration. Thus, it takes O(m) time in total. By maintaining S by the disjoint-set data structure [Galler and Fisher, 1964], Line 8 is evaluated by O(|N(vi)|) queries to the disjoint-set data structure in each step. Therefore, it takes O(mα(n)) time in total. Therefore, the total time complexity is O(n log n + mα(n)).

3 Main Result: Weighted Case

Now we describe our result in the weighted case. The proof strategy is the same as the unweighted case: We first derive necessary conditions of the convexity. Then we prove that these conditions are also sufficient. However, the details are much more complicated than the unweighted case. Therefore, due to the space limitation, we only give an outline of the proof. The complete proof will appear in the full paper.

3.1 Deriving Necessary Conditions

We start from the following lemma. This is a weighted version of Lemma 2.1 and is proved by a similar strategy to Lemma 2.1 with a careful case analysis.

Lemma 3.1. Suppose that ν is supermodular. If v1, v2, v3 satisfy (v1, v3), (v2, v3) ∈ E but (v1, v2) ̸∈ E (see Figure 1), then b(v1) + b(v2) ≤ b(v3).

Lemma 3.1 is syntactically the same as Lemma 2.1. Therefore, it allows us to define the auxiliary forest in the same way as the unweighted case. This means that G should be a comparability graph of a branching. We use the same notations as in the unweighted case. The next lemma is a weighted version of Lemma 2.3.

Lemma 3.2. Suppose that ν is supermodular. Then, for all v ∈ V , we have b(T - v ) ≤ b(v).

The proof is not as easy as Lemma 2.3. We use the following lemma. We write c((u, v)) as c(u, v) for simplicity.

Lemma 3.3. Suppose that ν is supermodular. Consider three vertices v1, v2, v3 such that b(v1) ≤ b(v2) ≤ b(v3) and (v1, v2), (v2, v3), (v3, v1) ∈ E. Then, c(v1, v3) ≥ c(v2, v3).

The proof of Lemma 3.3 is unexpectedly involved. We used a linear programming relaxation and a careful case analysis to prove this lemma.

Thus far, we obtain the following three necessary conditions of supermodularity of ν.

Condition W1 G is a comparability graph of a branching.

ConditionW2 For every v ∈ V , b(T - v ) ≤ b(v).

ConditionW3 For every v1, v2, v3 ∈ V with b(v1) ≤ b(v2) ≤ b(v3) with edges (v1, v2), (v1, v3), we have c(v1, v2) ≤ c(v1, v3).

You should notice that Condition W3 does not assume the existence of (v2, v3) even though Lemma 3.3 assumes. This is because the existence is guaranteed from Condition W1, and by omitting this condition from Condition W3, we can reduce the complexity of checking Condition W3.

Unfortunately, these three conditions are not sufficient to make ν supermodular; Figure 3 shows an example. Therefore, we derive one more condition. For a vertex subset X and a vertex v with Av ∩X ̸= ∅, let aX(v) be the unique vertex in X+ ∩ Av. For a vertex s ∈ V -, let p(s) be the parent (i.e., the immediate ancestor) of s in the auxiliary forest.

Lemma 3.4. Assume that ν is supermodular. Then, the following condition holds:

Condition W4 For all vertex s ∈ V -,

3.2 Proving the Sufficiency of Conditions

Now we obtain the four necessary conditions. We show that these are also sufficient for the convexity of ν.

We first give an explicit formula of ν, which is a weighted version of Lemma 2.4. Then, we obtain the following. The proof is similar to the proof of Lemma 2.4.

We prove the submodularity of ν using this representation as follows. Its proof requires a long chain of inequalities.

Lemma 3.6. Suppose that Conditions W1, W2, W3, and W4 hold. Then, ν is supermodular.

3.3 Algorithm

Now we propose a polynomial-time algorithm to check the convexity of the b-matching game.

We first see that Conditions W1 and W2 are the same as the unweighted case. Therefore, these can be checked by the algorithm for the unweighted case (Algorithm 1). Condition W3 requires that for each vertex v1 ∈ V the ordering of N(v1) ∩ {u ∈ V : b(u) ≥ b(v1)} by b(·) and the ordering by c(v1, ·) coincide. We can check this in O(m) by comparing (v1, v2) and (v1, p(v2)) for each (v1, v2) ∈ E with b(v2) ≥ b(v1). To check Condition W4, we first compute ν(Tv) for all v ∈ V . This is done in O(m) time. Then, we check Condition W4 in O(m) time.

In summary, we obtain the following theorem.

Theorem 3.7. There is a O(n log n+mα(n)) time algorithm to check whether ν is supermodular.

4 The Shapley Value

Our necessary and sufficient condition restricts the graph of a convex b-matching game as a comparability graph of a branching. By exploiting this structure, we can obtain an efficient algorithm to calculate the Shapley value of a convex b-matching game.

The Shapley value is defined as follows [Shapley, 1953]. Imagine that all the players join the coalition one-by-one in random order. Then, the marginal contribution of the player v to the coalition is given by ν(X ∪ {v}) - ν(X), where X is the set of players that appear before v. The Shapley value is the expectation of this quantity. Formally, it is given by

For an efficient computation of the Shapley value, we try to represent the marginal contribution ν(X ∪ {v}) - ν(X) by a simple form.

As a preprocessing, we compute the auxiliary forest T of the graph, which is obtained during the algorithm in Theorem 1.1. For a vertex v ∈ V , we denote by d(v) the depth of v, which is the maximum length of the path in T that ends at v. For example, if v has no parent in T, then d(v) = 0. For i = 0, . . . , d(v) - 1, let avi be the unique ancestor of v with d(avi ) = i.

We first evaluate the contribution of X with X ∩ Av ̸= ∅. This is a direct consequence of Lemma 3.5.

The event aX(v) = avi occurs if and only if avi and v are the first two elements added to X in {av0 , . . . , avi , v} in this order. Therefore, such a probability is 1/(i + 1)(i + 2). This shows the next lemma.

Lemma 4.2. The case X∩Av ̸= ∅ contributes to the Shapley value by

Next, we evaluate the contribution from X with X ∩Av = ∅. This is also a direct consequence of Lemma 3.5.

Lemma 4.3. Suppose that X ∩Av = ∅. Then,

For u ∈ T - v , the event u ∈ X occurs if and only if u and v are the first two elements added to X in Av ∪ {u} in this order. Therefore, such a probability is 1/(d(v)+1)(d(v)+2). Furthermore, for w ∈ T - v and u ∈ T - w , the event aX(u) = w occurs if and only if w and v are the first two elements added to X in Aw in this order, and u is added before v. Therefore, such a probability is 2/(d(w)(d(w) + 1)(d(w) + 2)). From the linearity of the expectation, we obtain the following.

Lemma 4.4. The case X∩Av = ∅ contributes to the Shapley value by

From Lemmas 4.2 and 4.4, the Shapley value of a convex b-matching game is given as follows.

Theorem 4.5. The Shapley value of the player v is given by

This theorem immediately gives an efficient algorithm to compute the Shapley value as follows.

Theorem 4.6. The Shapley values of convex b-matching game is computed in O(n log n + mα(n)) time.

Proof. The algorithm is presented in Algorithm 2. The algorithm computes term of Eq. (4.7) independently: Lines 25 compute the second term in Eq. (4.7) in O(n +m) time. Lines 6-10 compute the first term in Eq. (4.7). Because there are only O(m) summands in the first term, this computation takes O(m) time. Lines 11-15 compute the third term. Because ∑v∈V |T - v | = m, this computation takes O(m) time in total. Therefore, we obtain the correctness and the time complexity of the algorithm.

Algorithm 2 Calculating the Shapley Value

Input: A graph G = (V,E), budgets b(v) for all v ∈ V , weights c(e) for all e ∈ E, such that the b-matching game defined by G, b, c is convex

• 1: Calculate an auxiliary forest T of the game and the depth d(v) for each v ∈ V

• 4: end for

• 6: for v ∈ V do
• 7: for i = 0, . . . , d(v) - 1 do

• 9: end for
• 10: end for
• 11: for v ∈ V do
• 12: for i = 0, . . . , d(v) - 1 do

13:

• 14: end for
• 15: end for
• 16: return sv for all v ∈ V

5 Conclusion

In this study, we give a necessary and sufficient condition of the convexity of the b-matching game. Then, we propose an efficient algorithm to check whether a given game is convex or not. Our characterization also gives an efficient algorithm to compute the Shapley value of a convex b-matching game.

There are several interesting future works. The most important future work is to extend the conditions of the convexity to more general games that include the matching games. A necessary and sufficient condition of the convexity of the hypergraph matching game is given in [Kumabe and Maehara, 2020]. Therefore, it will be natural to expect a characterization on the hypergraph b-matching game, which is a common generalization of the b-matching game and the hypergraph matching game.

Another interesting future work is about integrality. We can prove that Conditions W1 to W4 are still necessary and sufficient conditions for the fractional b-matching game, which relaxes the integrality condition of the problem. This implies the following property: "the fractional b-matching game is convex if and only if the integral b-matching game is convex." The same result is obtained in the hypergraph matching game [Kumabe and Maehara, 2020]. Therefore, we conjecture that the same result holds on the linear production game and the integral linear production game.