Weak ε-Core +

Since the core can be empty, in the traditional model of coalitional game theory, several solution concepts are proposed based on the core, which relax the non-blocking condition. In particular, the weak ε-core, can be obtained by relaxing the non-blocking condition with parameter ε [66].

We first extend weak ε-core for a coalition structure. It is possible to extend other solution concepts. For example, Airiau and Sandip Sen [4] extended the kernel [18] for a coalition structure. In contrast, we concentrate on solution concepts that

are based on the core so that we can utilize the idea of CoreD. To define a fea-sible/allowed payoff vector with a coalition structure, we need to consider whether monetary transfers (side payment) across different coalitions are possible or not. We do not need to consider this issue for the core, since from the non-blocking condi-tion, there will be no monetary transfer among coalitions. However, if we relax the non-blocking condition, by allowing monetary transfers among coalitions, the space of feasible payoff vectors is extended.

In this paper, we concentrate on the case where transfers among coalitions are possible. Allowing transfers among coalitions can be considered more fair. Let us consider the problem of assigning managers to departments. Assume there exists a very talented manager, who can be as successful as others in any department. Also, assume she is the only person who can reduce the deficit of one particular department.

Then, assigning her to that department will maximize the total profit of the company.

In this case, it is clearly unfair to give her no bonus just because her department is making a deficit. The case where transfers among coalitions are not possible is more computationally challenging. We will revisit this topic in Discussion section.

Let us define average excess and the weak ε-core.

Definition 33 (Average excess) For coalition S and payoff vector y, let d(y, S) be the average excess of coalition S defined as follows:

d(y, S) = v(S)−∑

i∈Sy_i

|S| .

Definition 34 (Weak ε-core) The weakε-core forCS^Ais the set of payoff vectors, where each element (denoted as y) satisfies the following two conditions:

• ∀S ∈AC, d(y, S)≤ε (relaxed non-blocking condition),

• ∑

i∈Ay_i =V(CS^A) (efficiency condition).

From this definition, it is clear that if the weak ε-core is non-empty for one coalition structure CS^A, it is also non-empty for an optimal coalition structureCS^∗. Thus, we concentrate on finding the weak ε-core for an optimal coalition structure CS^∗. Similar to the core, we can show that there will be no blocking coalition structure, i.e., the following theorem holds.

Theorem 35 If payoff vector y satisfies d(y, S) ≤ ε for all S ∈ AC, then for all S^′ ̸∈AC, ^V(CSS

′)−∑

i∈S′yi

|S^′| ≤ε holds, where CS^S′ is any coalition structure of S^′. Proof From the definition of a coalition structure,CS^S′ ={S₁, . . . , S_k}, where each S_j ∈ AC is non-overlapping, ∪

S_j =S^′, and V(CS^S′) =v(S₁) +v(S₂) +. . .+v(S_k) holds. Also, from the assumption,

d(y, Sj) = v(S_j)−∑

i∈Sjy_i

|S_j| ≤ε

holds for all S_j. This means v(S_j)≤ε· |S_j|+∑

i∈Sjy_i. Then V(CS^S′)−∑

i∈S^′yi

|S^′|

= v(S₁) +. . .+v(S_k)−∑

i∈S1y_i−. . .−∑

i∈Sky_i

|S^′|

≤ ε· |S₁|+. . .+ε· |S_k|

|S^′| =ε.

Another well-known solution concept based on the core is the strongε-core [66], which tries to minimize the total excess of each coalition, rather than the average excess of each agent. Although we can extend it for a coalition structure, we cannot guarantee the property similar to Thm. 35.

The weak ε-core requires that the payoff vector be efficient. To find an efficient payoff vector, we need to know the exact value of V(CS^∗). Since finding its exact value is NP-hard, it is natural to utilize an approximate, semi-optimal solution. We introduce a new solution concept called the weak ε-core⁺, which can be obtained by an approximate value of V(CS^∗), and define it as follows.

Definition 35 (Weak ε-core⁺) The weak ε-core⁺ is a set of payoff vectors, where each element (denoted as y) satisfies the following two conditions:

• ∀S ∈AC, d(y, S)≤ε (relaxed non-blocking condition),

• V(CS^∗)−n·ε≤∑

i∈Ay_i ≤V(CS^∗) (relaxed efficiency condition).

Here, we relax the efficiency condition so that ∑

i∈Ay_i can be less than V(CS^∗).

However, the difference between V(CS^∗) and ∑

i∈Ayi must be at most n·ε. From this definition, it is clear that for any ε^′ ≤ ε, the weak ε-core⁺ is a superset of the weak ε^′-core⁺, and that the weak ε-core⁺ is a superset of the weak ε-core as long as ε is non-negative (the weak ε-core⁺ becomes empty for ε < 0). Thus, if the weak ε-core is non-empty, the weak ε-core⁺ is also non-empty. Furthermore, we can show that the converse is also true:

Theorem 36 If the weak ε-core⁺ is non-empty, the weak ε-core is also non-empty.

Proof Let us assume the weak ε-core⁺ is non-empty. Thus, we can choose one element y in the weak ε-core⁺. If ∑

i∈Ay_i = V(CS^∗), then y is also an element of the weak ε-core. Otherwise, let us choose σ as V(CS^∗)−∑

i∈Ay_i. Here, σ >0holds.

From y and σ, let us create another payoff vector y^′, such that y_i^′ =yi+σ/n. Then,

∑

i∈Ay_i^′ =V(CS^∗) holds. Also, for each S ∈AC, the following condition holds.

d(y^′, S) = v(S)−∑

i∈Sy_i^′

|S| < v(S)−∑

i∈Sy_i

|S| ≤ε Thus, y^′ is in the weak ε-core, i.e., it is non-empty.

Figure 6.1: Example of weak ε-core⁺

Example 16 Let there be three agents, a, b, and c, and let AC = {{a},{b},{c},{a, b},{b, c},{a, c}}. where v({a}) = v({b}) = v({c}) = 0, v({a, b}) = v({b, c}) =v({a, c}) = 12. The core of this game is empty.

For a given ε, let us choose ε^′ ≤ε, and modify the relaxed efficiency condition to V(CS^∗)−n·ε^′ ≤ ∑

i∈Ay_i ≤ V(CS^∗). Thus, when ε^′ = 0, this condition becomes identical to that of the weakε-core. If we first choose ε= 3, andε^′ = 0, then the weak ε-core⁺ (as well as the weak ε-core) is represented as the smaller shaded triangle in the larger triangle in the leftmost of Fig. 6.1. Here, the height of the larger triangle is equal to V(CS^∗) = 12. Each point therein represents an efficient payoff vector.

y= (4,4,4) is in the weak ε-core⁺ as well as the weakε-core.

Second, let us choose ε^′ = 2/3. Then, the weak ε-core⁺ is represented as the smaller shaded triangle in the larger triangle in the middle of Fig. 6.1. The height of the larger triangle is equal to V(CS^∗)−ε^′ ·n = 10. y = (10/3,10/3,10/3) is in the weak ε-core⁺. If we add (2/3,2/3,2/3)to y, we obtain(4,4,4), which is in the weak ε-core.

Finally, let us choose ε^′ = 1. Then, the weak ε-core⁺ is represented as one point (3,3,3)in the triangle in the rightmost of Fig. 6.1. The height of the triangle is equal to V(CS^∗)−ε^′ ·n = 9. y = (3,3,3) is the only element in the weak ε-core⁺ when ε^′ = 1. If we add (1,1,1) to y, we obtain (4,4,4), which is in the weak ε-core.

The following algorithm checks the weak ε-core⁺-non-emptiness.

Definition 36 (Algorithm ECore⁺(ε))

1. Solve the dual LP problem in Def. 37 for ε to obtain dual solution y^∗ and V^∗ =∑

i∈Ay_i^∗.

2. Check whether y^∗ satisfies the feasibility condition (V^∗ ≤ V(CS^∗)) or not by solving the MIP problem in Def. 38 for ε.

3. If y^∗ satisfies the relaxed efficiency condition, return y^∗ as an element of the weak ε-core⁺. Otherwise, report that the weak ε-core⁺ is empty.

Definitions 37 and 38 are slightly modified Defs. 30 and 32, respectively. Precisely, we define them as follows:

Definition 37 (Dual problem with the relaxed non-blocking condition)

min ∑

i∈Ay_i, subject to ∑

i∈Sjyi+ε· |Sj| ≥v(Sj), ∀Sj ∈AC, y_i ≥0, ∀ i.

Definition 38 (MIP for checking the relaxed efficiency condition)

find x,

subject to ∑

Sj∈ACx_j ·v(S_j)≥V^∗,

∑

j|i∈Sj∈ACx_j ≤1, ∀ i, x_j ∈ {0,1}, ∀ j.

Theorem 37 Algorithm ECore⁺(ε) in Def. 36 is correct, i.e., if it returns y^∗, y^∗ is in the weak ε-core⁺, and if it reports the weak ε-core⁺ is empty, the weak ε-core⁺ is empty.

Proof The proof is basically similar to that of Thm. 34. The only additional issue is to show that V(CS^∗)−n·ε≤∑

i∈Ay_i holds. If A∈SC, this fact is derived from the constraint in Def. 37. Otherwise, it is done from Thm. 35.

Notice that we can use a simple modification of CoreP for checking the non-emptiness of the weak ε-core⁺. In this case, the algorithm first finds V(CS^∗) and then payoff vectory that satisfies the relaxed non-blocking and efficiency conditions.

However, regardless of the value of ε, it needs to find V(CS^∗), and thus its runtime would become too long when the number of elements in AC becomes large.