Simple Coalitional Games with Beliefs

1 Introduction

In many multi-agent scenarios, agents have individual goals, but need to form teams (coalitions) in order to achieve those goals. When agents are selfish, i.e., aim to optimize their own utility, stability of the resulting coalitions becomes a major issue: if agents constantly switch coalitions to improve their payoffs, no task will ever be completed. Such settings are often modeled using coalitional games [Myerson, 1991], which provide a rich framework for the study of cooperation (see, e.g., [Shehory and Kraus, 1995]). In particular, coalitional stability can be studied using the notion of the core, which is one of the main solution concepts in coalitional games.

While providing a solid theoretical foundation for the analysis of multi-agent scenarios, traditional models of coalitional game theory fail to capture certain important aspects of interaction between intelligent agents. In particular, realworld agents often embark on the task of forming coalitions while having incomplete information or possessing private beliefs about the capabilities (or types) of potential partners. Hence, in multi-agent applications, we would like to be able to reason about coalition formation and coalitional stability under uncertainty. Nevertheless, until recently, the latter did not receive much attention from the game theory community (an important exception is a paper of Myerson [1984], which, however, approaches this issue from a mechanism design perspective). The last few years have seen some progress on this problem, with a number of models for coalition formation under incomplete information being proposed [Chalkiadakis and Boutilier, 2004; Myerson, 2007; Ieong and Shoham, 2008]. However, all of these papers assume that agent beliefs about other agents' types are represented as probability distributions over possible types. This assumption is not realistic in scenarios where agents may not be well-informed or sophisticated enough to describe their beliefs in this way. Moreover, as the number of agents grows, such models can quickly become computationally intractable. For example, in disaster management or multi-robot exploration scenarios, agents usually have beliefs about others' capabilities, but may not have time and/or bandwidth to check if these beliefs are correct and update them properly.

To address these issues, in this paper we propose a simplified approach to modeling incomplete information. Our model is based on the following idea. Sometimes, an agent's belief about another agent's type can be best described by a single element of the type space, which represents the former agent's best guess about the latter agent's type. While the agents realize that their information may be imprecise, they are unwilling or unable (e.g., due to time and space constraints) to estimate the chances of other agents having a different type, so they operate based on these guesses. In this paper, we provide a formal model for this type of scenario. While it can be viewed as a special case of the probabilistic model mentioned above, our model provides important advantages from both cognitive and computational perspective. Indeed, as argued above, it may be easier for an agent to formulate a single guess about another agent's capabilities than to come up with a distribution that fully describes them. Also, in our model each agent's beliefs can be compactly represented as a vector of types, one for each other agent. Finally, we are able to prove a number of characterization and complexity results for our setting that seem to be difficult to state-and prove-in the general probabilistic model.

The rest of this paper is organized as follows. After introducing the nesessary notation and definitions, we describe our model. We then generalize the well-known notion of a simple game to our setting, and provide a characterization of the core of such games in the setting where coalition structures are not allowed, i.e., the agents are required to form a single team. Simple games are ones in which the value of each coalition is known (or, in our setting, is believed) to be either 0 or 1 (rather than any real number). While less expressive than general games, they still capture a wide range of realistic scenarios and have been studied in the context of multiagent systems (see, e.g., [Bachrach and Rosenschein, 2007; Elkind et al., 2007]). Our characterization result matches the existing characterization result for the core of simple games without beliefs, and allows us to derive a polynomial-time algorithm for checking whether a given outcome is in the core, or whether the core is non-empty. Thus, we show that introducing beliefs in simple games without coalition structures does not increase the complexity of core-related problems.

In contrast, we then demonstrate that when coalition structures are allowed, i.e., agents can split into several teams, the complexity of core-related problems can increase dramatically. Specifically, we focus on weighted voting games with beliefs, a natural generalization of the classic weighted voting games (WVGs) [Taylor and Zwicker, 1999] to our setting. The computational complexity of WVGs when coalition structures are allowed has been studied in [Elkind et al., 2008a]. In particular, [Elkind et al., 2008a] show that when the weights of all players are polynomially bounded, there is a polynomial-time algorithm for checking if a given outcome is in the CS-core (a generalization of the concept of the core to games with coalition structures), and leave open the complexity of checking the non-emptiness of the CS-core. In this paper, we demonstrate that both of these problems become computationally hard in the setting with beliefs. These results provide a complexity-theoretic separation between games with and without beliefs in the setting with coalition structures. Moreover, they contribute to our understanding of weighted voting games with beliefs. Such games provide perhaps the simplest possible model for joint task execution by a team of selfish agents under incomplete information, and are therefore interesting in their own right, constituting an important base case in this area. We conclude the paper by positioning our model with respect to other classes of coalitional games, and pointing out directions for future research.

2 Preliminaries and Notation

A (transferable-utility) coalitional game G = (N; u) is given by a set of players N = {1, . . . , n} and a utility function u : 2N → R. The function u maps every subset, or coalition, of players S to a real number u(S), which is called the value of S. Intuitively, u(S) is the profit that the members of S can attain by working together.

This definition can be extended to the setting where each player may have a type, and the payoff of a coalition is determined not only by the list of its members, but also by their types. Formally, a coalitional game with types G = (N; T1, . . . , Tn; u) is described by: (a) a set of players N = {1, . . . , n}; (b) for each player i, a set Ti of this player's possible types; we require ⊥ ̸∈ Ti for all i ∈ N; and (c) a utility function u : T1 ∪ {⊥} × . . . × Tn ∪ {⊥} → R. Given an input vector (T1, . . . , Tn), Ti ∈ Ti ∪ {⊥}, the function u outputs the value of the coalition S = {i | Ti ̸= ⊥} when each i ∈ S has type Ti ∈ Ti. Note that Ti = ⊥ is used to denote the fact that player i does not appear in a given coalition. We write ⃗ T to denote (T1, . . . , Tn).

As an example, consider the setting where each player has either skill A or skill B, but not both, and a coalition has value 1 if it has at least k1 players with skill A and at least k2 players with skill B, and 0 otherwise. This scenario can be modeled by a coalitional game with types where Ti = {A, B} for all i ∈ N, and u(T1, . . . , Tn) = 1 if and only if |{i | Ti = A}| ≥ k1 and |{i | Ti = B}| ≥ k2.

A coalitional game is called monotone if u(S) ≥ u(S′ ) for all S ⊆ N and all S′ ⊂ S. A monotone game is called simple if u(S) ∈ {0, 1} for all S ⊆ N. In such games, we say that S wins if u(S) = 1 and S loses otherwise.

An important special class of simple games is that of weighted voting games (WVGs). A WVG is described by its set of players N, a vector of players' weights w = (w1, . . . ,wn), wi ∈ R for i ∈ N, and a threshold q ∈ R; we write G = (N; w; q). The utility function u(S) of a game G = (N; w; q) is given by u(S) = 1 iff ∑i∈S wi ≥ q.

In some cases, the only acceptable outcome of a game is the formation of the grand coalition, i.e., the coalition of all playersN. However, inmanymulti-agent scenarios it ismore natural for agents to split into groups so that each group performs its own task. This is captured by the notion of a coalition structure, which is a partition CS = {C1 , . . . , Ck } of the set of agents N, i.e., (a) Ci ∩ Cj = ∅ for all i, j = 1, . . . , k, i ̸= j, and (b) ∪ki=1Ci = N. Note that our description of a coalitional game as G = (N; u) does not prescribe whether the grand coalition should form; rather, each coalitional game induces two different games: one where coalition structures are not permitted and one where they are.

The utility function u does not specify how the members of a coalition should divide the value of this coalition. This is captured by the notion of an imputation. In games without coalition structures, an imputation is simply a way to distribute the value of the grand coalition. That is, we say that a vector p = (p1, . . . , pn) is an imputation in a game without coalition structures if (a) pi ≥ 0 for all i ∈ N, and (b) ∑i∈N pi = u(N). In a game with coalition structures, an imputation should distribute the value of each coalition in the coalition structure. That is, we say that p = (p1, . . . , pn) is an imputation for a coalition structure CS = {C1 , . . . , Ck } if (a) pi ≥ 0 for all i ∈ N, and (b) ∑i∈Cj pi = u(Cj ) for all j = 1, . . . , k. Note that the value of each coalition in the coalition structure has to be distributed among its members, i.e., inter-coalitional transfers are not allowed. We write p(S) to denote ∑i∈S pi, and use similar notation for other n-dimensional vectors throughout the paper.

An important consideration in coalitional games is that of stability, which is usually captured by the notion of the core. Roughly speaking, an outcome of a game is stable if no set of players wants to deviate from it. In games without coalition structures, an outcome of a game can be identified with an imputation. Hence, in such games, the core of a game G = (N; u) is defined as the set of all imputations p such that p(S) ≥ u(S) for any S ⊆ N. In games with coalition structures, an outcome is a pair (CS , p), where CS is a coalition structure and p is an imputation for CS. In this setting, the core of a game G = (N; u) consists of all pairs (CS, p) such that CS is a partition of N, p is an imputation for CS, and p(S) ≥ u(S) for any S ⊆ N. In what follows, we refer to the core of a game with coalition structures as its CS-core, and reserve the term core for games without coalition structures.

3 Coalitional Games with Beliefs

In this section, we introduce our model for coalitional games with beliefs. These games are based on coalitional games with types. However, in our model the players' types are not public information. Instead, each player knows his own type and, in addition, has a belief about each other player's type.

Definition 1. A coalitional game with beliefs G = (N; ⃗ T ; u; b1, . . . , bn) is given by a coalitional game with types G′ = (N; ⃗ T ; u) and, for each player i ∈ N, a vector bi = (bi(1), . . . , bi(n)) of that player's beliefs, where bi(j) ∈ Tj denotes i's belief about player j's type. We denote (b1, . . . , bn) by ⃗b. We refer to G′ as the associated game with types of the game G and write G = (G′ , ⃗b).

Note that we do not explicitly specify the players' true types; rather, we assume that i's belief about its own type is correct, i.e., bi(i) is player i's true type. In fact, all of our subsequent results hold true in the case where agents do not know their own true types but only have beliefs about them.

A player i can form a belief about the value of every possible coalition S based on his beliefs about individual players' types by computing u(T1, . . . , Tn), where Tj = bi(j) for j ∈ S and Tj = ⊥ for j ̸∈ S. We will denote i's belief about the value of a coalition S by ui(S).

As argued above, this model is inspired by Bayesian coalitional games with agent-type uncertainty [Chalkiadakis and Boutilier, 2004; Chalkiadakis et al., 2007], but with an important difference. In contrast to that work, we do not assume here that the agents' beliefs are probabilistic. Instead, the agents have "point" beliefs about the type of others. This is a natural assumption in many real-world situations, where probabilistic beliefs are simply not available to the agents, or where reasoning about the full joint distribution over the possible type vectors of all potential coalitions is a practical impossibility for computational reasons.

Now, to describe an outcome of a coalitional game with beliefs, we need to generalize the notion of imputation to this setting. This task is complicated somewhat by the fact that the players may have different beliefs about the value of the coalition to be formed. To tackle this, we adopt an approach used in previous work on coalitional games with uncertainty [Suijs and Borm, 1999; Chalkiadakis and Boutilier, 2004; Chalkiadakis et al., 2007]. Namely, the players have to agree on the shares of the total payoff that each of them is going to get rather than the actual payoff amounts.

Definition 2. We say that d = (d1, . . . , dn) is a demand vector for a coalition structure CS = {C1 , . . . ,Ck } in a game G = (N; ⃗ T ; u; ⃗b) if di ≥ 0 for i ∈ N and d(Cj ) = 1 for each Cj ∈ CS. Given a demand vector d, the expected payoff pi of a player i ∈ Cj is given by diui(Cj ); we refer to p = (p1, . . . , pn) as the expected payoff vector for d.

Similarly to the case of coalitional games with types, we can identify the outcome of a game without coalition structures with a demand vector for {N}. In a game with coalition structures, an outcome is a pair of the form (CS, d), where CS is a partition of N and d is a demand vector for CS. We are now ready to define the core and the CS-core of a coalitional game with beliefs.

Definition 3. Given a game G = (N; ⃗ T ; u; ⃗b) the core of G consists of all demand vectors d such that for any coalition S and any demand vector d′ for {S,N \ S} there exists an i ∈ S such that d′iui(S) ≤ pi. The CS-core of G consists of all pairs (CS, d) such that CS is a partition of N, d is a demand vector for CS, and for any coalition S and any demand vector d′ for {S,N \ S} there exists an i ∈ S such that d′iui(S) ≤ pi.

Intuitively, this definition says that a demand vector d (respectively, a pair (CS, d)) is stable if there is no set S and a demand vector for S which would provide each player in S with a higher expected payoff than d (respectively, (CS, d)).

4 Simple Games with Beliefs

In this section, we define simple coalitional games with beliefs and show that the core of such games can be characterized in essentially the same way as the core of (standard) simple games. Moreover, we demonstrate that this characterization can be used to construct a polynomial-time algorithm for checking whether the core is non-empty or whether a given demand vector is in the core.

For the rest of the section, we only consider games without coalition structures. Recall that in such settings an outcome of a game is simply a demand vector d that satisfies d(N) = 1.

We start by generalizing the notions of monotone and simple games to games with types and games with beliefs. Namely, we say that a game G = (N; ⃗ T ; u) is monotone if u(T1, . . . , Tn) ≤ u(T ′1 , . . . , T ′n ) for any two vectors (T1, . . . , Tn), (T ′1 , . . . , T ′n ) such that for all i ∈ N either Ti = T ′ i or Ti = ⊥. That is, in a monotone game adding players to a coalition (while keeping the types of the other coalition members unchanged) cannot lower the value of a coalition. Furthermore, we say that G is simple if it is monotone and u(T1, . . . , Tn) ∈ {0, 1} for all Ti ∈ Ti ∪ {⊥} and all i ∈ N. Finally, we say that a coalitional game with beliefs G = (G′ ; ⃗b) is monotone (respectively, simple) if its associated game with types G′ is monotone (respectively, simple).

It turns out that for simple games with beliefs, the definition of the core can be simplified considerably.

Proposition 1. A demand vector d is in the core of a simple game with beliefs G if and only if any coalition S ⊆ N such that ui(S) = 1 for all i ∈ S satisfies p(S) = 1.

Proof. Suppose that d is in the core of G. Consider any coalition S such that ui(S) = 1 for all i ∈ S. Clearly, p(S) ≤ p(N) = ∑i∈N diui(N) ≤ 1; we will show that p(S) ≥ 1. Suppose that p(S) < 1 and set ε = 1-p(S) |S| . Construct a demand vector d′ for {S, N\S} by setting d′i = pi+ε

for i ∈ S, d′i = 1 |N\S| for i ∈ N \ S; clearly, we have d′ (S) = d′ (N \ S) = 1. Moreover, we have d′i > pi for all i ∈ S. As ui(S) = 1 for all i ∈ S, this implies ui(S)d′i > pi for all i ∈ S, a contradiction with the definition of the core. Hence, p(S) ≥ 1, as required.

Conversely, suppose that d is not in the core of G. Then, according to Definition 3 there exists a coalition S and a demand vector d′ for {S,N \ S} such that pi < ui(S)d′i for all i ∈ S. For this to be the case, it has to be true that ui(S) = 1 for all i ∈ S. Therefore, we have pi < d′i for all i ∈ S. As d′ (S) = 1, this implies p(S) < 1. That is, S satisfies p(S) < 1, ui(S) = 1 for all i ∈ S, as required.

In simple games without beliefs, there is a very natural characterization of the core that relies on the notion of veto players. A player i is said to be a veto player in a game G = (N; u) if any S ⊆ N such that u(S) = 1 satisfies i ∈ S. By monotonicty, this is equivalent to requiring that u(N \ {i}) = 0. One can then describe the core as follows.

Theorem1. [Taylor and Zwicker, 1999] The core of a simple game G = (N; u) is non-empty if and only if G has a veto player. Moreover, a payoff vector p is in the core of G if and only if pi = 0 for any i that is not a veto player in G.

We will now show that this result can be extended to simple games with beliefs. First, we have to generalize the notion of a veto player to our setting.

Definition 4. A player i is said to be a veto player in a simple game with beliefs G = (N; ⃗ T ; u; ⃗b) if for any S ⊆ N \ {i} we have uj(S) = 0 for some j ∈ S.

That is, i is a veto player if it impossible to form a coalition not involving i so that all of its members believe that this coalition will succeed. It turns out that one can efficiently verify whether a given player is a veto player.

Theorem 2. Consider a simple game with beliefs G = (N; ⃗ T ; u; ⃗b) such that for all S ⊆ N and all i ∈ N one can compute ui(S) in time at most B. Then the algorithm A(G, i) given in Fig. 1 correctly decides whether a player i is a veto player in G and runs in time O(n2B).

Proof. Our algorithm starts with the coalition S = N \ {i} and successively removes players who do not believe that the current coalition can succeed. By monotonicity, they would not believe that any subset of the current coalition can succeed either, so no such player can be a member of a coalition S ⊆ N \ {i} that satisfies uj(S) = 1 for all j ∈ S. After all such players have been deleted, we either obtain an empty coalition (in which case there is no coalition not involving i that believes in its own success, i.e., i is a veto player), or the remaining coalition S satisfies uj(S) = 1 for all j ∈ S, i.e., i is not a veto player. The bound on the running time is immediate from the description of the algorithm.

Note that, unlike in games without beliefs, it is not sufficient to check whether N \ {i} is a winning coalition: it can happen that N \ {i} contains a player who is sceptical about its success and therefore does not provide a witness that i is not a veto player, while a smaller coalition S ⊂ N \ {i} does.

We now prove an analogue of Theorem 1 in our setting.

S = N \ {i}; flag = ⊥; while flag = ⊥ and S ̸= ∅ do flag = ⊤; k0 = 0; for each k ∈ S if flag = ⊤ and uk(S) = 0 k0 = k; flag = ⊥; endif endfor if k0 ̸= 0 then S = S \ {k0}; endwhile if S = ∅ output "i is a veto player"; else output "i is not a veto player";

Theorem 3. The core of a simple coalitional game with beliefs G = (N; ⃗ T ; u; ⃗b) is non-empty if and only if G has a veto player. Moreover, a demand vector d is in the core of G if and only if di = 0 for any i that is not a veto player in G.

Proof. First, suppose that G has a veto player i. Consider a demand vector d that satisfies di = 1, dj = 0 for j ̸= i. Consider any coalition S such that uj(S) = 1 for all j ∈ S. By definition of a veto player, we have i ∈ S. By monotonicity, we have ui(N) = 1, so p(S) ≥ pi = diui(N) = 1. Hence, d is in the core.

Conversely, suppose that G has no veto players. Consider a demand vector d. We have d(N) = 1, so d has at least one non-zero coordinate. Fix any i with di > 0. Since i is not a veto player, there is a coalition S ⊆ N \ {i} such that uj(S) = 1 for all j ∈ S. Moreover, we have p(S) ≤ p(N \ {i}) = 1-pi < 1. Hence, d is not in the core. As this is true for any demand vector d, G has an empty core.

The argument above also demonstrates that any demand vector d with di > 0 for a non-veto player i is not in the core, thus proving the second part of the theorem.

Theorem 3 provides an efficient algorithm for checking whether the core is non-empty or whether a given demand vector is in the core. Indeed, we can first check, for each player i ∈ N, if i is a veto player (by Theorem 2, this can be done in polynomial time). The core is non-empty if the answer is "yes" for at least one i ∈ N. Furthermore, to check if d is in the core, we can check if di > 0 for any non-veto player i; if the answer is "yes", d is not in the core. We summarize these observations in the following theorem.

Theorem 4. Given a simple coalitional game with beliefs G and a demand vector d, one can check in polynomial time if G has an empty core, or if d is in the core of G.

5 Computational Complexity: The Case of Weighted Voting Games with Beliefs

In this section, we consider the complexity of computing the CS-core in simple games with beliefs. It is known that even in full-information settings the CS-core is computationally more demanding than the core [Elkind et al., 2008a]. We will now show that introducing beliefs adds another layer of complexity: for weighted voting games some natural CS-core-related problems that are polynomial-time solvable in the absense of beliefs become computationally intractable when beliefs are introduced.

We start by specializing the concept of coalitional games with beliefs to WVGs. For these games, it is natural to identify a player's type with his weight. Players may also have beliefs about the threshold. However, there is no loss of generality in assuming that the threshold is publicly known: a game (N;w; q) has the same set of winning coalitions as the game (N; αw; αq), and therefore we can rescale all beliefs so that the players have the same belief about the threshold.

Hence, we say that a weighted voting game with beliefs is given by a set of players N = {1, . . . , n}, n belief vectors b1, . . . , bn, where bi = (bi(1), . . . , bi(n)) describes the beliefs of player i about the weights of the other players, and a threshold q; we write ⃗b = (b1, . . . , bn) and G = (N; ⃗b; q). We will abuse notation by writing bi(S) = ∑j∈S bi(j). The utility function of a WVG with beliefs G = (N; ⃗b; q) satisfies ui(S) = 1 if bi(S) ≥ q, and ui(S) = 0 otherwise. In the computational problems considered in the rest of this section, we assume that bi(j) ∈ Z for all i, j ∈ N.

[Elkind et al., 2008a] shows that many natural problems related to the CS-core are computationally hard when the weights are given in binary. However, for the important special case where all weights are polynomial in the number of agents, it gives a polynomial-time algorithm for checking if a given outcome is in the CS-core. Interestingly, it turns out that in our setting this problem is hard even if all weights are believed to be at most n (the number of players). This illustrates that introducing beliefs results in a quantifiable increase in the computational complexity of the problem.

Theorem 5. Given a game G = (N; ⃗b; q) and an outcome (CS, d), it is coNP-complete to decide whether (CS, d) is in the CS-core of G, even if bi(j) ≤ n for all i, j ∈ N.

Proof. Let p be the expected payoff vector for (CS, d). Clearly, if an outcome is not in the CS-core of G, one can easily prove this by exhibiting a coalition S such that p(S) < 1 but bi(S) ≥ q (and hence ui(S) = 1) for all i ∈ S. It follows that our problem is in coNP. To show coNP-hardness, we will demonstrate that the complementary problem of checking whether (CS, d) is not in the CS-core of G is NP-hard. To this end, we provide a reduction from a classic NP-hard problem CLIQUE [Garey and Johnson, 1990].

An instance of CLIQUE is given by an undirected graph G = (V,E), |V | = t, and an integer k. It is a "yes"-instance if G contains a clique (a complete subgraph) of size at least k and a "no"-instance otherwise. Given an instance of CLIQUE, we construct an instance of our problem as follows.

Suppose that V = {v1, . . . , vt}. We create n = 2t players u1, . . . , ut, v1, . . . , vt and set q = k. The players' beliefs about each other's weights are defined as follows. For i = 1, . . . , t, we set bui (vi) = k, bui (vj) = 0 for j = 1, . . . , t, j ̸= i, bui (uj) = 0 for j = 1, . . . , t. Furthermore, for i = 1, . . . , t we set bvi (ui) = k-1, bvi (uj) = 0 for j = 1, . . . , t, j ̸= i, and bvi (vj) = 1 if i = j or (vi, vj) ∈ E and bvi (vj ) = 0 otherwise.

Let CS = {C1 , . . . ,Ct}, where for i = 1, . . . , t we set Ci = {ui, vi}. Observe that we have bui (Ci ) = k, bvi (Ci ) = k, i.e., each player believes that he belongs to a winning coalition. Finally, for i = 1, . . . , t set dui =

1 - 1/(k + 1), dvi = 1/(k + 1). Clearly, d is a demand vector for CS, and the corresponding expected payoff vector p satisfies pui = dui , pvi = dvi for i = 1, . . . , t.

One can show that (CS , d) is in the CS-core of our game if and only if the graph G does not have a clique of size at least k. The proof is omitted due to space restrictions.

Remark 1. We can show that the problem remains coNPcomplete even if bi(j) ∈ {0, 1} for all i, j ∈ N.

Another computational problem considered in [Elkind et al., 2008a] is that of checking whether the CS-core of a WVG is non-empty. Specifically, [Elkind et al., 2008a] shows that this problem is hard if the weights are given in binary. However, it leaves open the question of whether this problem remains intractable if weights are polynomial in the number of players. We will now show that the corresponding problem for WVGs with beliefs is NP-hard even if all weights are at most linear in the number of players.

Theorem 6. It is NP-hard to check if a game G = (N; ⃗b; q) has a non-empty CS-core, even if bi(j) ≤ n for all i, j ∈ N.

Proof. The reduction is from PARTITION INTO TRIANGLES (PT) [Garey and Johnson, 1990]. An instance of PT is given by a graph G = (V,E), |V | = 3t. It is a "yes"-instance if G can be partitioned into triangles, i.e., there is a family of sets V1, . . . , Vt ⊂ V such that (1) |Vi| = 3 for all i = 1, . . . , t; (2) ∪ti=1Vi = V ; (3) each Vi is a triangle, i.e., for any i = 1, . . . , t and any u, w ∈ Vi we have (u, w) ∈ E. Otherwise, it is a "no"-instance.

Fix an instance G = (V, E) of PT with V = {v1, . . . , v3t}. Let N ′ = {1, . . . , 3t}, N ′′ = {3t+1, 3t+2, 3t+3}, and set N = N ′ ∪N ′′ . Let q = 6t+1. For i, j ∈ N ′ , set bi(j) = 3t if i = j or (vi, vj) ∈ E and bi(j) = 0 otherwise. Furthermore, set bi(j) = 3t and bj(i) = 1 for all i ∈ N ′ , j ∈ N ′′ . Finally, set bi(j) = 3t for all i, j ∈ N ′′ . Let G = (N; ⃗b; q).

Suppose that G is a "yes"-instance of PT, and let {V1, . . . , Vt} be the corresponding partition. Consider the outcome (CS, d), where CS = {C1 , . . . ,Ct ,Ct+1 }, Ci = {j | vj ∈ V i } for i = 1, . . . , t, Ct+1 = N ′′ , and di = 13 for all i ∈ N. It is not hard to see that (CS, d) is in the CS-core of G. Conversely, if G cannot be partitioned into triangles, G has an empty CS-core; the proof is omitted for brevity.

6 Discussion

Recall that in transferable utility games (TU games), the worth of each coalition is given by a single number, which is the total payoff available to the members of this coalition; this payoff can be freely distributed between the members of that coalition. In contrast, in non-transferable utility games (NTU games), the worth of a coalition C, |C| = k, is described by a vector of length k, which, for each player i ∈ C, describes the utility that i derives from participating in C. In such games, players cannot make payments to each other.

We constructed coalitional games with beliefs on the basis of TU games. Perhaps surprisingly, it turns out that they share certain features with both TU games and NTU games. Indeed, in the spirit of TU games, the players have to agree on how to distribute the profits achieved by a coalition; this agreement is captured by the demand vector. On the other hand, since each player in our games assigns his own utility to a coalition to be formed, he may not be able to transfer some of this utility to other players, especially if these players are much more pessimistic about the value of this coalition. This is of course in the spirit of NTU games. To give a simple example, consider a game in which u1({1}) = 0, u2({2}) = 1, u1({1, 2}) = 10, u2({1, 2}) = 0. Player 1 is eager to form a coalition with player 2, and would gladly offer a lion's share of its value (believed to be 10) to him. However, there is no demand vector that will make this proposal attractive for 2.

In fact, if the demand vectors for each coalition were fixed in advance (i.e., for each potential coalition S and each member of that coalition i player i's share of S's profit was part of the game description rather than subject to negotiation between the members of S), coalitional games with beliefs would be equivalent to (hedonic) NTU games: player i's value for a coalition S would be given by diui(S). In contrast, in this paper we allow the players to negotiate the payoffs resulting from an expected outcome. This provides the players more flexibility and is therefore more natural in incomplete information scenarios.

We now describe two well-known classes of games that bear certain similarities to the weighted voting games with beliefs considered in the previous section. We hope that this discussion will help the reader appreciate the properties of our model, and its differences from existing related models.

Vector weighted voting games. In k-vector weighted voting games [Taylor and Zwicker, 1999; Elkind et al., 2008b], the value of each coalition is determined using a set of k weight vectors w1 , . . . ,wk and k thresholds q1 , . . . , qk : a coalition S is considered to be winning if it wins in each of the component games, i.e., we have wi (S) ≥ qi for i = 1, . . . , k. The similarity with WVGs with beliefs is obvious: in those games, too, the value of each coalition is determined using a set of weight vectors (one for each player). However, while in vector WVGs the number of weight vectors used to determine the value of each coalition is given exogenously (i.e., it is fixed to k independently of the coalition), in WVGs with beliefs the number (and the actual list) of weight vectors is determined endogenously: only the weight vectors (i.e., beliefs) of the coalition's members have to be taken into account.

Additively separable hedonic games. Additively separable hedonic games are described by a weighted directed graph whose vertices are players, and the weight wij of an edge (i, j) corresponds to the utility i extracts from being in a coalition with j; note that we may have wij ̸= wji. Given a coalition S, the payoff of a player i ∈ S is given by pi = ∑j∈S wij . While the weight wij appears to play a similar role to the belief bi(j) in the WVGs with beliefs, there are two important differences between these classes of games. First, as argued above, additively separable games are NTU games, while WVGs with beliefs are not. Second, there is no notion of a threshold in additively separable games.

A related class of TU games is defined by Deng and Papadimitriou [1994]: the games considered in this paper are also represented by a weighted (undirected) graph, and the value of a coalition S is determined as u(S) = ∑i,j∈S wij.

WVGs with beliefs are different from those games as well: the games of [Deng and Papadimitriou, 1994] allow for arbitrary transfers of utility between players, and do not involve any notion of a threshold.

7 Conclusions

In this paper, we developed a model for coalitional games with beliefs, which allows us to reason about coalition formation under uncertainty while being significantly less complex than the more general Bayesian models. We proved a characterization result for the core of simple games with beliefs, which matches the known result for the setting without beliefs, and can be used to derive polynomial-time algorithms for core-related problems. On the other hand, we showed that incomplete information can increase the complexity of the CS-core-related problems. In doing so, we introduced and analyzed weighted voting games with beliefs, which provide a convenient model for simple task allocation scenarios under uncertainty, and are therefore of independent interest.

We believe that our results provide a natural framework for modeling the behavior of selfish agents under incomplete information. Also, we hope they will prove useful for studying more sophisticated incomplete information scenarios, such as the full Bayesian setting.

Acknowledgements This research is supported by the ALADDIN (Autonomous Learning Agents for Decentralised Data and Information Networks) project, which is jointly funded by a BAE Systems and EPSRC strategic partnership (EP/C548051/1), as well as by EPSRC (GR/T10664/01) and ESRC (ES/F035845/1).