Complexity of Pure Equilibria in Bayesian Games

1 Introduction

Game theory has a very general scope, encompassing questions that are basic to all of the social sciences, and offering insights into any economic, political, or social situation that involves multiple players that have different goals and preferences. In its generality, game theory may be defined as the study of mathematical models of conflict and cooperation between intelligent rational decision-makers, cf., e.g., [Myerson, 1997]. Not surprisingly, in Artificial Intelligence the framework of game theory has been immediately recognized to be very appealing, being the means for an artificial agent to act with rationality and intelligence when interacting with others. Additionally, game theory demonstrated its effectiveness in the recent results on algorithms for load balancing and routing in large networks and the Internet, where it has been extensively used for distributing the logic of the decision processes among many nodes (cf., e.g., [Feldmann et al., 2003]).

The most well known form of games studied in the literature is that of strategic games. In this context, the main solution concept is that of equilibrium (called Nash equilibrium in games with complete information [Nash, 1951]). Equilibria model scenarios in which no player can improve his utility by unilaterally changing his strategy, or equivalently, such that the strategy chosen by any player is the best response to the strategies chosen by the others. Any strategy which is not a best response indicates that the corresponding player is not acting rationally, because he could improve his utility by choosing a different one. Although the existence of equilibria in strategic games is guaranteed, when the so called randomized strategies are allowed (cf. Section 2), I-00198 Roma, Italy tmancini@dis.uniroma1.it this is not true in the important case in which strategies are forced to be pure [Gottlob et al., 2003]. In case of randomized strategies, the problem of computing an equilibrium was recently shown to be PPAD-complete, even for two-player games [Chen and Deng, 2006]; and, further results have been established for strategic games under various restrictions (cf., e.g., [Gilboa and Zemel, 1989; Megiddo and Papadimitriou, 1991; Papadimitriou, 1994b; Conitzer and Sandholm, 2003; Daskalakis and Papadimitriou, 2005]).

On the other hand, in this paper we consider games with incomplete information (aka Bayesian Games) that have been specifically introduced in the literature [Harsanyi, 1968] to account for uncertainties in the knowledge that the single players have about the games and their counterparts. Indeed, in these games players' payoff depends not only on the actions of the other players but also on their own private type, for which a probability distribution is a priori known.

The equilibrium concept relevant for this kind of games is that of Bayesian Equilibrium, in which each player plays a best response to the other players in expectation over their private types. The complexity of deciding the existence of a Bayesian Equilibrium in case of pure strategies (short: ∃PBE problem) has been recently investigated by Conitzer and Sandholm [2003], who proved its NP-hardness for symmetric two-players games, in the case where, for each player, the utility function and the probability distribution over other players' types are represented extensively as tables (called Standard Normal Form (SNF) in Section 2). Moreover, tractable classes of Bayesian Games have also been singled out in [Singh et al., 2004], where an efficient algorithm is provided for finding approximate equilibria when the utility function of each player depends only on the actions and realized types of some neighbor players (cf. Graphical Normal Form (GNF)), and when the kind of interaction formed by the neighborhood relation is a tree.

However, a complete picture of the complexity of Bayesian Games is still missing in the literature, both for pure and randomized strategies. As an example, it is not known what happens if, unlike [Conitzer and Sandholm, 2003], the utility functions and the probability distributions are not explicitly represented as tables (cf. General Normal Form (GenNF)); and it has been left open in [Singh et al., 2004] if the tractability result holds for larger classes of games in GNF, e.g., for games whose players interactions have tree-like structure.

The aim of this paper is precisely to shed lights on these aspects, by focusing on the case of pure strategies. Our contributions are as follows:

• ✄ In Section 3 we show that the result of Conitzer and Sandholm is tight, since ∃PBE is NP-complete, even if only one among the utility function and the probability distribution is represented as a table, for each player in the game.
• ✄ We study ∃PBE on the class of games in GenNF, and we show that the need of dealing with incomplete information has a strong impact on the intrinsic complexity of the games. Indeed, we show that the problem is PP-hard, which is quite surprisingly given that deciding the existence of a Pure Nash equilibrium is NP-complete [Gottlob et al., 2003].
• ✄ We continue the analysis of ∃PBE on games in GenNF, under the assumption that the utility functions and the probability distributions range over real numbers with a fixed-precision. In this scenario, we prove that the problem is, in fact, complete for the class PP.
• ✄ Given that it is not generally known how efficient heuristics can be devised for problems hard for PP, it appears crucial to identify tractable classes of games. In Section 4, we face this problem and we show that ∃PBE is feasible in polynomial time not only on classes of acyclic games, but also on games of bounded hypertree width [Gottlob et al., 2002] which is one of the broadest known generalizations of hypergraph acyclicity.

2 Games of Incomplete Information

Preliminaries. Given sets S and R, a S-tuple with components in R is a total function from S to R. A S-tuple is denoted by a bold-face lowercase letter, e.g., t. Set R can be either a set of atomic values or a set of functions. Given a S-tuple t and an element s ∈ S (resp. a set S ⊆ S), we denote by t[s] (resp. t[S]) the value of the s-component of tuple t (resp. the tuple obtained by taking only t's s-components, with s ∈ S). By t-s (resp. t-S ) instead, we denote the (S - {s})-tuple (resp. the (S - S)-tuple) obtained by t by removing t's s-component (resp. all t's s-components, with s ∈ S). Furthermore, given a S-tuple t, an element s ∈ S, and an element r ∈ R, we denote by ts→r the tuple obtained from t by replacing its s-component with r (i.e., the S-tuple t′ such that, for each i ∈ S - {s}, t′ [i] = t[i], and t′ [s] = r), and by 〈t; tx〉, x ̸∈ S the (S ∪ {x})-tuple t′ such that, t′ [s] = t[s], ∀s ∈ S, and t′ [x] = tx.

Finally, for a set S, we denote by Δ(S) the set of all probability distributions over elements in S, i.e., the set of realvalued functions τ : S → [0, 1] such that ∑s∈S τ (s) = 1.

Bayesian Games. A strategic game G consists of a set of players N and, for each player i ∈ N, of a set of possible actions Ai and an utility function ui : ×i∈N Ai → ℜ, that describes the payoff of player i as a function of his own and other players' actions. The behavior of a strategic game is as follows: each player i simultaneously chooses an action in his set Ai. The tuple of actions chosen by all players is called the action-profile, and it is denoted by ˆa. As a consequence of this choice, each player i receives a payoff of ui(ˆa).

These games are also called games with complete information, because players have all perfect information about the game. Bayesian games [Harsanyi, 1968] have been introduced to account for situations in which such assumption cannot be made, since there may be information which is uncertain, or unobservable by some players. This uncertainty is modelled by introducing unknown parameters, the types of the different players, into the utility functions.

Definition 1 (Bayesian Game [Harsanyi, 1968]). A Bayesian Game G consists of a set of players N and, for each player i ∈ N:

• A set of possible actions Ai;
• A set of possible types Ti;
• A probability function pi : Ti → Δ(×j∈N -{i} Tj ), assigning a probability distribution over ×j∈N -{i} Tj to each possible type of player i. We write pi(·|ti) to denote the belief that player i has over the types of the other players when he has type ti ∈ Ti;
• An utility function ui : ×i∈N Ai × ×i∈N Ti → ℜ, that describes the payoff of player i as a function of the actions of all players and their types (including i's). ✷

Although probability functions pi(·|ti) can be given separately for each player i, a common assumption is that a prior joint distribution P(×i∈N Ti) over all the type profiles (i.e., N-tuples t) exists, and is common knowledge among all players. Under this assumption, the single functions pi(·|ti) can be built by the single players according to the Bayes' Rule. Indeed, as for the reasonability of this assumption (called the consistent beliefs assumption), it can be proven that every Bayesian Game with finite type set can be transformed into an equivalent game with consistent beliefs.

A Bayesian Game behaves as follows:

1. At the beginning, each player i "gets revealed" his realized type ˆ ti ∈ Ti by an external entity (usually called "Nature"). Under the consistent beliefs assumption, we can think that the realized types for all players are drawn from the joint prior distribution P(·).

Each player i knows only his realized type ˆ ti, and does not know the realized types of the other players (this realizes the incompleteness of information discussed so far). The N-tuple of realized types of all players is called the realized type-profile, and it is denoted by ˆ t.

1. According to their realized types, each player i simultaneously chooses an action, in his set Ai. The tuple of actions chosen by all players is called the action-profile, and it is denoted by ˆa.
2. As a consequence of this choice, and depending on the realized type-profile, each player i receives a payoff of ui(ˆa, ˆ t). We observe that, for the players to be able to evaluate their actual payoffs, information about the realized types of the other players must be observable after the games terminates. Indeed, since this information is

hidden when actions have to be decided, what the players can evaluate is their expected payoff, according to the probability distribution P (·) on types.

Given a Bayesian Game G and a player i ∈ N, a randomized strategy for i is a probability function σi : Ti → Δ(Ai), i.e., a total function assigning, to each type in Ti, a probability distribution over the set of actions available to player i. We write σi(·|ti) to denote the probability distribution over Ai when the type of player i is ti ∈ Ti. Hence, σi(ai|ti) is the probability with which player i will choose action ai ∈ Ai in case his realized is ti. A randomized strategy profile is a N-tuple σ of randomized strategies, one for each player. In this paper we are interested in pure strategy profiles, i.e., strategy profiles σ such that, for each player i ∈ N, the strategy for player i, σ[i] = σi(·) assigns, to each type ti ∈ Ti, a single action in Ai (and not a probability distribution over the actions). We write σi(ti) to denote the action ai ∈ Ai chosen by player i when his type is ti. A pure strategy can be equivalently regarded as a randomized strategy where all probability distributions (one for each type ti ∈ Ti) assign 1 to action σi(ti), and 0 to the others.

Definition 2. A Pure Bayesian Equilibrium (PBE) is a strategy profile σ, with each σi(·) = σ[i] being a pure strategy for player i ∈ N, such that, for every type ti ∈ Ti:

where, to ease notation, we denoted by a the N-tuple such that a[k] = σk(t-i [k]) for k ̸= i (i.e., the action expected to be played by player k according to strategy profile σ when he is of type t-i [k]), and a[i] = ai. ✷

It is well known that, although every Bayesian Game has a BE, it does not necessarily have a PBE.

It can be observed that games with complete information are a particular case of Bayesian Games in which all players may assume only one type. All the definitions made for Bayesian Games (strategies, strategy profiles and equilibria) are generalizations of analogous notions for games with complete information. In particular, equilibria in games with complete information are called (Pure) Nash Equilibria [Nash, 1951].

Representing games. Games can be represented in different ways. Below we briefly review the most used ones:

Standard Normal Form (SNF): In games of this form (cf., e.g. [Osborne and Rubinstein, 1994]),sets N and Ai, Ti, i ∈ N are represented explicitly, P(t) and ui(a, t), ∀i ∈ N are represented by tables of |N|+1 and 2|N| + 1 columns, having ∏i∈N |Ti| and ∏i∈N (|Ti| × |Ai|) tuples, respectively. This form is also known as Strategic Form (cf., e.g., [Myerson, 1997]).

Graphical Normal Form (GNF): This form is suitable to represent games in which the utility function of each player depends only on the actions chosen and realized types of a subset of the other players (cf., e.g., [Kearns et al., 2001; Vickrey and Koller, 2002]). For each player i, let Xi be the set of players j such that ui(t, a) does not depend on t[j] and a[j]. Players in N - Xi - {i} are called the neighbors of player i, and denoted by Neigh(i). The representation is similar to SNF, but tables for utility functions ui(·) may have a reduced number of columns. In particular, for each player i, column relative to actions and types of players in set Xi can be omitted.

General Normal Form (GenNF): This is the most compact representation for a game, since P(t) and ui(a, t), i ∈ N can be given by (succinctly encoded) functions that can be computed in polynomial-time in the size of their input (such form is a generalization of that defined in [Gottlob et al., 2003] for games with complete information). We also assume that a polynomial-time computable function Neigh(·) : N → 2N that, for each player, returns his neighbors, is part of the representation. We will see that such function is very useful in case the interaction among players is restricted (cf. Section 4). It can be observed that games in SNF and GNF are trivially in GenNF (as for the former, the function Neigh(·) would return the set N - {i} for any player i ∈ N).

3 Intractability results

In this section, we face the complexity of deciding whether a Bayesian Game has a PBE (the ∃PBE problem). We start with the class of games in SNF.

Theorem 1. ∃PBE for games in SNF is NP-complete. Hardness holds even for symmetric, two-players games, while membership holds even if only one among P(·) and the various ui(·) is given explicitly as a table.

Proof. (Hardness) Hardness follows from [Conitzer and Sandholm, 2003, Theorem 2], where the NP-complete Set Covering problem is reduced to ∃PBE of a game in SNF with only 2 players. Actually, the definition of a Bayesian Game given there is more restricted than ours, since the utility function of player i does not depend on the realized types of the other players.

(Membership) We prove the membership in NP for the more general case of N unbounded and only one of the functions among P(·) and ui(·) represented as a table. In this case, the size of the input is exponential in the number of players |N|. Problem ∃PBE can be solved by guessing a strategy-profile σ in polynomial time (it consists in guessing an action for every pair player/type), and checking whether σ is a PBE. The latter task can be performed in polynomial time in the size of the input, since, for each player and for each type, formula (1) in Definition 2 can be evaluated in time polynomial in the size of the table encoding P(·) (which, in turn, is smaller than that encoding ui(·)).

By using the same line of reasoning as in the proof above, we get a similar result for games in GNF.

Let us now turn to games in GenNF. We next show that ∃PBE is hard for the class PP (aka majority-P) of languages that can be decided by a nondeterministic Turing machine in polynomial time where the acceptance condition is that a majority (more than half) of computation paths accept (cf., e.g., [Papadimitriou, 1994a]). This class contains NP and is contained in PSPACE.

Theorem 3. ∃PBE for games in GenNF with unbounded number of players is PP-hard. The result holds also for games in which players can assume just two types.

Proof. We reduce the canonical PP-complete MAJ-SAT problem (cf., e.g., [Papadimitriou, 1994a]) to ∃PBE. Given a propositional formula ϕ over n variables as input, MAJSAT(ϕ) is true iff more than half of its possible assignments satisfies it.

Let V be the set of variables of formula ϕ. We build a Bayesian Game G that has a PBE iff MAJ-SAT(ϕ) is true. The game has a set of n+3 players N = V ∪{eval}∪{R, S}, with the following characteristics:

• Players in V (corresponding to the variables of formula ϕ) may assume one of two types {true, false}, have only one available action nop, and utility functions which evaluate always to 0.
• eval ("evaluator") may assume only one type, but has two available actions: count and pass. His utility function ueval(·) is defined as follows:

• Players R and S may assume only one type, and have two available actions a1 and a2. Their utility functions uR(·) and uS(·) are such that they evaluate to 0 if aeval = count, while, in the other cases (where aeval = pass) they are defined as follows (independently on the types and actions of players in V ):

The idea behind such choice for uR and uS is that, if aeval = count both a1 or a2 are always best-responses for players R and S; on the other hand, if aeval = pass, their utility functions prevent the existence of a PBE.

• P(·) ∈ Δ(×i∈V∪{eval}∪{R,S} Ti) is uniform: since |Teval| = |TR| = |TS| = 1 and |Tv| = 2 for each v ∈ V , this means that, for each type-profile t, P(t) = 1/2n.

We now show that MAJ-SAT(ϕ) is true iff G has a PBE.

(only if)-part. If MAJ-SAT(ϕ) is true, we observe that any strategy-profile σ such that σ[eval] = count is a PBE. In fact, that strategy is an equilibrium for players in V ∪{R, S} since their expected payoff cannot be different from 0. Moreover, action count is a best-response for player eval, that achieves an expected payoff of 1/2n · #ϕ > 1/2 (with #ϕ > 2n-1 being the number of models of formula ϕ and 1/2 being the payoff that he would obtain by unilaterally changing his action into pass).

(if)-part. As for the other direction, if MAJ-SAT(ϕ) is false, eval would play pass, which guarantees him higher utility, but in this case, it can be observed that the structure of the utility functions for players R and S prevents them from reaching an equilibrium.

The reader may now wonder whether the problem is, in fact, complete for PP. While this might appears at a first sight very natural, the formal proof has to take care of the fact that both P(·) and ui(·) (for each i ∈ N) are real-valued functions. Hence, to prove the membership result, we next restrict ourselves to real values with fixed-precision, i.e., we assume that all the values of interest for the game comes as multiples of a value ϵ = 10-c , for some fixed natural number c.

Theorem 4. In the fixed-precision setting, ∃PBE for games in GenNF with unbounded number of players is PP-complete.

Proof. (Sketch.) Assume, wlog, that all such functions range in the domain of reals in [0, 1]. Then, we can regard all the functions in the game as ranging in the integer domain [0, 1/ϵ]. We can now build a NP Turing Machine Mep ("ep" stands for "expected payoff") that, given as input i ∈ N, ti ∈ Ti, ai ∈ Ai, σ-i, and a boolean accept, behaves as follows: guesses a tuple t-i and then performs pi(t-i |ti) · ui(a, t) ≤ (1/ϵ)2 additional branches (with a and t defined as in formula (1)), accepting (resp. rejecting) on all of them if accept is true (resp. false). Such machine will have

computation paths, all accepting or all rejecting, depending on the value for accept. Build now a second Turing Machine M that, given σ, behaves as follows: for each triple (i, ti, ai), (i ∈ N, ti ∈ Ti, ai ∈ Ai - {σ[i]}) makes two branches, on one invoking Mep(i, ti,σ[i],σ-i, true) and on the other Mep(i, ti, ai,σ-i, false). Such machine will have a number of accepting paths lower than that of rejecting ones if and only if σ is not a PBE. Machine M clearly operates in NP.

Finally, we conclude this section by observing that the number of players plays a crucial role in the PP-hardness above.

Theorem 5. ∃PBE for games in GenNF is NP-complete, if the number of players |N| is bounded by a constant.

Proof. (Hardness) The hardness follows from Theorem1.

(Membership) Problem ∃PBE can be solved by guessing a strategy-profile σ in polynomial time (it consists in guessing an action for every pair player/type), and checking whether σ is a PBE. In case of |N| bounded by a constant, formula (1) clearly shows that such task can be performed in polynomial time.

4 Tractability results

In order to look for tractable cases of the ∃PBE problem, we might think of issuing some suitable restrictions on the games. For instance, one may think about restrictions on the maximum number of neighbors of each player, on the maximum number of types of each player, and on the kinds of interaction among players.

Results in Section 3 show that, exploiting only one of the restrictions above is not enough: requiring the size of the neighborhood, or the maximum number of types for each player to be bounded by a constant does not lead to tractability (cf., respectively, Theorem 1 and [Gottlob et al., 2003] for the more restricted case of games with complete information, i.e., games in which players can assume only one type). On the other hand, it is possible to show that, by combining orthogonal, but weaker restrictions, we can obtain somewhat appealing tractable cases. To this end, we will exploit the concepts of intricacy, hyper-graph and hypertree-width of a game [Gottlob et al., 2003] below, and we show that the problem ∃PBE becomes polynomial in case of games G having bounded intricacy (or, equivalently, the small neighborhood property), bounded number of types, and whose associated hypergraph H(G) has bounded hypertree-width.

Definitions of intricacy and hyper-graph have been proposed for games with complete information only, but we show that they can be used, without modification, also in the context of Bayesian Games. Formally, given a game G, the intricacy of G, i(G), is defined as

where ||G|| is the size of the representation of G.

A game G that has bounded intricacy, i.e., for which i(G) ≤ k for a fixed constant k, also enjoys the so-called small neighborhood property: for each player j ∈ N, |Neigh(j)| ∈ O(log ||G||/ log |Aj|). It can be observed that while bounded neighborhood implies bounded intricacy, the reverse does in general not hold. Hence, bounding intricacy could be a suitable restriction for those games in which bounding the number of neighbors is too severe.

Moreover, given a game G, the hyper-graph H(G) = (V,E) of G has players as vertices, i.e., V = N, and set of hyper-edges defined as E = {{j ∪Neigh(j)} | j ∈ N}. For a game G, its associated hypergraph encodes the structural interactions among the players. In many cases, these interaction are not too intricate, and the notion of hypertree-width helps in singling out these scenarios.

Definition 3 ([Gottlob et al., 2002]). Given a hypergraph H = (VH, EH), a hypertree decomposition of H is a hypertree HD = 〈T, χ, λ〉 for H, where T = (VT , ET ) is a tree, and χ and λ are labelling functions that associate to each vertex p ∈ VT two sets χ(p) ⊆ VH and λ(p) ⊆ EH. Moreover, HD satisfies all the following conditions:

1. For each hyper-edge h ∈ EH of H, there exists p ∈ VT s.t. h ⊆ χ(p);
2. For each vertex v ∈ VH of H, the set {p ∈ VT | v ∈ χ(p)} induces a (connected) subtree of T ;
3. For each p ∈ VT , χ(p) ⊆ ⋃e∈λ(p) e;
4. For each p ∈ VT , (⋃e∈λ(p) e)∩(⋃p′ ∈Tp χ(p′ )) ⊆ χ(p), where Tp is the set of nodes in the subtree rooted at p.

The width of HD ismaxp∈VT |λ(p)|. The hypertree-width hw(H) of an hyper-graph H is the minimum width over all its hypertree decompositions. ✷

To prove our main tractability result, we will exploit a transformation from a Bayesian Game into a game with complete information, and show that it preserves important structural properties of the game. The transformation is called the type-agent representation of a Bayesian Game, as it was originally discussed in [Harsanyi, 1968]. In the type-agent representation there is a player (called, to avoid confusion, typeagent) for every possible pair (i, ti), with i ∈ N and ti ∈ Ti. The set of actions available to each type-agent (i, ti) is exactly the set Ai of actions available to player i. The idea is that type-agent (i, ti) is responsible for selecting the action that player i would use in the original Bayesian Game if ti is his realized type. Hence, an action profile for the new game is a tuple a having a component a[(i, ti)] for each type-agent (i, ti). Also the utility functions of each type-agent (i, ti) are derived from that of player i, being defined as the conditionally expected utility to player i given that ti is his realized type. Formally, the utility function for type-agent (i, ti), v(i,ti)(a), is as follows:

where, to ease notation, we denoted by a′ the N-tuple having a[(j, t[j])] as its j-component a′ [j], for all j ∈ N.

BEs of the original game are in one-to-one correspondence with Nash Equilibria of the new game with complete information.

Theorem 6. ∃PBE is feasible in polynomial time for the class of games having bounded hypertree-width, bounded intricacy, and bounded number of types, even with unbounded number of players.

Proof. We exploit the transformation of the Bayesian Game G into a game G′ with complete information described above. We remind the PBEs of G are in one-to-one correspondence with Pure Nash Equilibria of G′ . G′ has a set N ′ of ∑i∈N |Ti| type-agents (i, ti) (with ti ∈ Ti), each one having utility function v(i,ti)(·) defined as in (3).

Since, in the Bayesian Game G, player i has only set Neigh(i) as neighbors, functions v(i,ti)(·) and ui(·) do not depend on actions and types of players in set Xi = N - Neigh(i) - {i}. Hence, a can be regarded as a tuple in Ai × ×j∈Neigh(i) A|Tj | j . Moreover, by splitting tuple t-i into 〈t-i Neigh(i) ; t-i Xi 〉, pi(t-i |ti) = pi(t-i Neigh(i) , t-i Xi |ti) can be rewritten as pi(t-i Neigh(i) |ti) · pi(t-i Xi |t-i Neigh(i) , ti). Hence, v(i,ti)(·) becomes:

Since, the subexpression in parentheses evaluates to 1, the formula can be rewritten as:

On the other hand, from formula (2) we obtain, for every player j ∈ N: i(G)×log ||G|| ≥ |Neigh(j)|×log |Aj |.Wlog, we can assume that, for each j ∈ N, |Aj| ≥ 2, hence log |Aj | ≥ 1. Thus, we have |Neigh(j)| ≤ i(G) · log ||G||.

We now show that, for every type-agent (i, ti), function v(i,ti)(·) can be computed in polynomial time in ||G||. This is because, given an action-profile a, computing v(i,ti)(a) accounts to sum out ∏j∈Neigh(i) |Tj| factors (each one evaluable in polynomial time), and, as we observed above, we have that, for each j ∈ N, such value is polynomial in ||G|| if the game has bounded intricacy and the number of types available to each player is bounded by a constant T .

Hence, we have shown how G can be transformed in polynomial time into the game G′ . In order to conclude the proof, it remains to show that deciding whether Nash equilibria exist in G′ can also be made in polynomial time.

Theorem 5.3 of [Gottlob et al., 2003] claims that this problem is polynomial for games with complete information which have bounded hypertree-width and bounded intricacy. What we show next is that the reduction above is such that G′ meets all these conditions.

Bounded Intricacy: Any type-agent (i, ti) will have at most Neigh(i) · T neighbors in G′ . Hence, i(G′ ) ≤ i(G) · T .

Bounded hypertree-width: Given the hypergraph H(G) associated to G, with bounded hypertree-width hw(G), we can build the hypergraph for G′ as follows: the nodes are the typeagents (i, ti), and for each type-agent (i, ti), an hyper-edge eG′ (i,ti) exists connecting (i, ti) to all the variables occurring in v(i,ti)(·), i.e., all type-agents (j, tj) with j ∈ Neigh(i) and tj ∈ Tj. Such a hypergraph has hypertree-width bounded by hw(G) · T . To show this, we present a procedure that computes an hyper-tree decomposition 〈T ′ , χ′ , λ′ 〉 of G′ from an hyper-tree decomposition 〈T, χ, λ〉 of G of minimal width. The transformation is as follows: (1) T ′ = T; (2) For every node v ∈ T , λ′ (v) = {eG′ (i,ti) |eGi ∈ λ(v) ∧ ti ∈ Ti}, with eGi being the hyper-edge in H(G) defined by {i}∪Neigh(i); (3) For every node v ∈ T , χ′ (v) = {(i, ti)|i ∈ χ(v) ∧ ti ∈ Ti};

It can be seen that 〈T ′ , χ′ , λ′ 〉 satisfies all the conditions to be an hypertree-decomposition of H(G′ ), and has width bounded by hw(G) · T .

Acknowledgments

This work was supported by a Royal Society Wolfson Research Merit Award, allowing G. Gottlob to invite G. Greco and T. Mancini to Oxford.

In addition, G. Greco's work was supported by M.I.U.R. under project "tocai.it: Tecnologie Orientate alla Conoscenza per Aggregazioni di Imprese in Internet".