1 Introduction
An effectivity function (Moulin and Peleg
1982) describes the allocation of power among coalitions of individuals. More precisely, given a set of individuals and a set of alternatives, an effectivity function assigns to each coalition of individuals a collection of subsets of alternatives. Effectivity functions derive from many concepts in game theory and social choice theory: for example game forms, social choice correspondences, simple games. More generally, effectivity functions can be used to describe the distribution of power or rights. For instance, a constitution can be modelled as an effectivity function (Gärdenfors
1981; Peleg
1998): alternatives are social states, and to say that a coalition is effective for a set of alternatives means that this group of individuals is legally entitled to the social state being in the designated set.
According to this last interpretation an effectivity function is a centralized concept describing the rights of individuals. This leads directly to the question whether we can find a set of decentralized rules (practical laws) such that individuals and coalitions, by acting according to these rules, obtain the same rights as described by the effectivity function. In more formal terms: can we find a game form which provides all coalitions with the same power as the effectivity function? This question was already answered in Moulin (
1983), who showed that any monotonic and superadditive effectivity function can be represented by a game form. An important further question is whether we can find rules (in accordance with the constitution) such that there is a situation in which the society is stable, that is, in some state of equilibrium. Peleg et al. (
2002) answered this question by characterizing effectivity functions that have a Nash consistent representation, i.e., a game form representing the effectivity function and having a Nash equilibrium for any profile of preferences of the individuals. See Peleg and Peters (
2010) for an extensive treatment of this topic and related issues.
An important open question in this area is the following. If we take into account that information may be incomplete—individuals are not sure about the preferences, i.e., types, of other individuals—when is it possible to have a representation of an effectivity function that is Bayesian Nash consistent? d’Aspremont and Peleg (
1988) consider ordinal Bayesian incentive compatible representations of committees: they study effectivity functions derived from simple games and their representation by so-called decision schemes, which assign probability distributions over the alternatives, such that there exists a Bayesian incentive compatible Nash equilibrium under incomplete information with private values. Recently, Peleg and Zamir (
2014) show that, without additional restrictions except for the standard ones, effectivity functions can be Bayesian Nash consistently represented by generalized decision schemes; their proof of this result uses the uniform core (Abdou and Keiding
1991). The question under which conditions such a representation by a deterministic game form exists, remains open.
In the present paper we consider the case of incomplete information with private values: the preference of a type of a player does not depend on the types of the other players. Compared to d’Aspremont and Peleg (
1988) and Peleg and Zamir (
2014) we impose a considerably stronger requirement: given an effectivity function, when does there exist a representing game form such that, for any information structure (i.e., vector of type sets of the players), there exists an ex post Nash equilibrium for any preference profile, that is, a strategy combination which results in a Nash equilibrium for every realization of the types?
On the one hand, this is a very desirable situation, since players do not have to rely on their beliefs about the types of the others, and they do not have to spend time and effort on finding out the types of the other players. Moreover, every ex post equilibrium has the no regret property which means that no player has an incentive to change his action even if he were to be informed of the true types of the other players. These considerations are similar to the ones justifying implementation in ex post Nash equilibrium (e.g., Bergemann and Morris
2008). It is also a first step towards characterizing Bayesian Nash consistent representations, as every ex post Nash equilibrium is a Bayesian Nash equilibrium for any vector of beliefs.
On the other hand, as can be expected, this requirement turns out to be rather restrictive. Our main result is as follows. An effectivity function (for
\(n\) individuals or players) has an ex post Nash consistent representation exactly if there exists an
\((n-1)\)-player coalition and a subset
\(C\) of alternatives for which this coalition is effective, such that all other
\((n-1)\)-player coalitions are effective for all singletons in this set
\(C\). The intuition behind this condition is that in equilibrium there is one player restricted to choose his most preferred alternative from
\(C\), while all other players are restricted in such a way that they are not able to influence the outcome by unilateral deviation. In the case
\(n=2\) this condition is equivalent to at least one of the two players being a so-called singleton player: a singleton player is a player for whom all minimal sets for which this player is effective, are singletons. We also show that, if only one of the players has more than one type, then ex post Nash consistency imposes no additional restrictions compared to Nash consistency (as in Peleg et al.
2002). In the final part of the paper we provide a short discussion on effectivity functions that have no ex post Nash consistent representation, but for which a representation exists if we restrict the number of types—a special case being the mentioned one where only one player has more than one type. Throughout the paper we concentrate on existence of ex post Nash equilibria and leave other possible properties (e.g., Pareto optimality of such equilibria) from consideration.
The approach of looking for equilibrium consistent representations of effectivity functions should be distinguished from the approach followed by implementation theory. Suppose we are given a social choice correspondence. In implementation theory one looks for a game form of which, for each profile of preferences, the set of equilibrium outcomes coincides with the set of outcomes assigned by the social choice correspondence. No condition is put on off equilibrium outcomes. In contrast, in an equilibrium consistent representation the outcomes attainable in the game form by individuals and coalitions should coincide with the outcomes attainable via the social choice correspondence or, equivalently, its associated effectivity function. In this sense, requiring equilibrium consistent representation is a strengthening compared to implementation; the weakening is that only existence of an equilibrium outcome is required. Nevertheless, for a given equilibrium consistent representing game form, one can construct a social choice correspondence by assigning all equilibrium outcomes to a given preference profile; then, obviously, this social choice correspondence is implemented by the game form.
The literature on implementation theory also deals with implementation in ex post equilibrium. This solution concept is mainly used in situations with interdependent valuations, because of tractability and robustness against informational assumptions. Several authors show that for one-dimensional signals, ex post implementation is possible if the single crossing property is satisfied (Cremer and McLean
1985; Dasgupta and Maskin
2000; Bergemann and Välimäki
2002; Perry and Reny
2002). More recent work deals with ex post equilibria in multidimensional signal settings. Jehiel et al. (
2006) show that the only ex post implementable social choice functions in a generic class of environments are constant functions, whereas Bergemann and Morris (
2008) provide conditions for full implementation in ex post equilibrium if the genericity requirement fails.
The organization of the paper is as follows. Section
2 introduces definitions and notations. In Sect.
3, we present our basic representing game form. This game form is extended and modified in several ways in the rest of the paper. Section
4 analyzes the case of two players, and Sect.
5 generalizes to more than two players.
Notation For a finite set \(D\), \(\vert D \vert \) denotes the number of elements of \(D\); \(P(D)\) denotes the set of all subsets of \(D\); \(P_0(D)\) denotes the set of all non-empty subsets of \(D\).
2 The model
Let \(N=\{1,\ldots ,n\}\) (where \(n\ge 2\)) be the set of players, and let \(A\) be a finite set of alternatives, \(\vert A \vert \ge 2\). A binary relation \(R\) over \(A\) is a subset \(R\subseteq A\times A\), where \((a,b)\in R\) is written as \(aRb\) (read \(aRb\) as \(a\) is weakly preferred over \(b\)). A binary relation is complete if for all \(a,b\in A\), we have \(aRb\) or \(bRa\). A binary relation is transitive if \(aRb\) and \(bRc\) jointly imply \(aRc\), for all \(a,b,c\in A\). A preference ordering
\(R\) on \(A\) is a complete and transitive binary relation. The set of all preference orderings on \(A\) is denoted by \(W\). If \(R\in W\) and \(a,b\in A\), then \(a P b\) means \(aRb\) and not \(bRa\). If \(a\in A\) and \(R\in W\), then \(L(a,R)=\{b\in A\mid aRb\}\) is the lower contour set of \(a\), i.e. the set of alternatives not strictly preferred to \(a\). For a set \(S\), \(W^S=\{f\mid f:S\rightarrow W\}\) is the set of mappings from \(S\) to \(W.\)
An effectivity function (EF) is a function \(E{:} P(N)\rightarrow P(P_0(A))\) that satisfies the following conditions: (i) \(E(N)=P_0(A)\); (ii) \(E(\emptyset )=\emptyset \); and (iii) \(A\in E(S)\) for all \(S\in P_0(N)\). As a general interpretation, \(B\in E(S)\) means that coalition \(S\) can force the final alternative to be an element of \(B\). The interpretation of the three conditions is fairly obvious: (i) the grand coalition has complete power in terms of \(E\), (ii) the empty set has no power, and (iii) an alternative from \(A\) must prevail.
An effectivity function
\(E\) is
monotonic (with respect to players as well as alternatives) if
$$\begin{aligned}{}[B\in E(S),B'\in P_0(A), B\subseteq B', \hbox { and } S\subseteq S']\Rightarrow B'\in E(S'). \end{aligned}$$
For
\(B\in P_0(A)\) and
\(S\in P_0(N)\),
\(B\) is
minimal for coalition
\(S\) if
\(B\in E(S)\) and there is no
\(B'\in E(S)\) such that
\(B'\varsubsetneq B\). A monotonic effectivity function
\(E\) is completely determined by these minimal sets.
The effectivity function
\(E\) is
superadditive if
$$\begin{aligned}{}[B_i\in E(S_i),i=1,2, \text{ and } S_1\cap S_2=\emptyset ] \Rightarrow B_1\cap B_2\in E(S_1\cup S_2). \end{aligned}$$
Note that a superadditive effectivity function is also monotonic with respect to players: for
\(S\subseteq S'\) and
\(B\in E(S)\), superadditivity implies that
\(B=B\cap A\in E(S\cup (S'{\setminus } S))=E(S')\). Monotonicity and superadditivity are natural properties in view of the interpretation given above. Moreover, effectivity functions derived from game forms have these properties.
The
polar of
\(E\) is the effectivity function
\(E^*\) defined by:
\(E^*(\emptyset )=\emptyset \), and for
\(S\in P_0(N)\)
$$\begin{aligned} E^*(S)=\{B\in P_0(A) \mid B\cap B'\ne \emptyset \text{ for } \text{ all } B'\in E(N{\setminus } S)\}. \end{aligned}$$
Thus, if
\(B\in E^*(S)\), then the complementary coalition
\(N{\setminus } S\) cannot prevent
\(S\) from obtaining an alternative from
\(B\); in particular,
\(A{\setminus } B\notin E(N{\setminus } S)\). The function
\(E^*\) reflects a weaker effectivity condition than
\(E\): whereas
\(E\) tells us what each coalition can guarantee on its own,
\(E^*\) tells us what each coalition cannot be kept from.
\(E\) is maximal if \(E\) is superadditive and \(E=E^*\). Observe that if \(E\) is superadditive, then \(E(S)\subseteq E^*(S)\) for all \(S\): if \(B \in E(S)\) then superadditivity implies \(B \cap B' \ne \emptyset \) for all \(B' \in E(N {\setminus } S)\), so that \(B \in E^*(S)\). Also notice that a maximal effectivity function is monotonic. Indeed, a superadditive effectivity function is monotonic with respect to players; and if \(B\in E^*(S)\) and \(B\subseteq C\), then obviously \(C\cap B'\ne \emptyset \) for all \(B'\in E(N{\setminus } S)\) and thus \(C\in E^*(S)\). Hence, if \(E\) is maximal then \(E\) is monotonic with respect to alternatives since \(E^*\) is.
The following results are well-known (e.g., Peleg and Peters
2010; Boros et al.
2010; or Crama and Hammer
2011). For completeness, we provide the proofs.
The following result will be useful in the sequel.
A
game form is an
\((n+2)\)-tuple
\(\Gamma =(\Sigma ^1,\ldots ,\Sigma ^n;\pi ;A)\), where (i)
\(\Sigma ^i\) is the (non-empty, finite) set of possible actions
1 of player
\(i\in N\); and (ii)
\(\pi :\Sigma ^1\times \dots \times \Sigma ^n\rightarrow A\) is the outcome function. Throughout the paper we assume that
\(\pi \) is surjective. For
\(S\in P_0(N)\) we denote
\(\Sigma ^S=\prod _{i\in S} \Sigma ^i\).
Let
\(\Gamma =(\Sigma ^1,\ldots ,\Sigma ^n;\pi ;A)\) be a game form. For
\(S\in P_0(N)\) and
\(\sigma ^S\in \Sigma ^S\), we define
\(B (\sigma ^S)=\{\pi (\sigma ^S,\sigma ^{N{\setminus } S})\mid \sigma ^{N{\setminus } S}\in \Sigma ^{N{\setminus } S}\}\). The effectivity function
\(E^{\Gamma }\), associated with
\(\Gamma \), is defined in the following way:
\(E^{\Gamma }(\emptyset )=\emptyset \) and for
\(S\in P_0(N)\),
$$\begin{aligned} E^{\Gamma }(S)=\{B \in P_0(A) \mid B(\sigma ^S) \subseteq B \quad \text{ for } \text{ some } \sigma ^S\in \Sigma ^S\}. \end{aligned}$$
Note that
\(E^{\Gamma }\) is monotonic and superadditive. Let
\(E:P(N)\rightarrow P(P_0(A))\) be an effectivity function. A game form
\(\Gamma \) is a
representation of
\(E\) if
\(E(S)=E^{\Gamma }(S)\) for every
\(S\in P_0(N)\). Basically, this means that the game form distributes the same power among the players as the effectivity function does.
An
information structure is an
\(n\)-tuple
\(T=(T^1,\ldots ,T^n)\), where
\(T^i\) is the finite set of
types of player
\(i=1,\ldots ,n\). We denote by
\(T^N = \prod _{i\in N} T^i\) the set of type profiles. With some abuse of notation we denote by
\(W^{T}\) the set of all preference ordering profiles: a profile
\(R^{T} \in W^{T}\) has dimension
\(\sum _{i\in N} |T^i|\) and assigns a preference ordering to each type of each player. We assume that preferences are private valued, i.e., they do not depend on types of the other players. If
\(\Gamma =(\Sigma ^1,\ldots ,\Sigma ^n;\pi ;A)\) is a game form, then
\((\Gamma ,T,R^{T})\) is a game of incomplete information in the sense of Harsanyi (
1967). The set of strategies of player
\(i\) in this game is the set
\(S^i=\{s^i\mid s^i: T^i\rightarrow \Sigma ^i\}\). We denote
\(S^N=\prod _{i\in N} S^i\). We do not introduce type probabilities since we will only consider ex post Nash equilibrium. A strategy profile
\(s=(s^1,\ldots ,s^n)\in S^N\) is an
ex post
\((Nash)\)
equilibrium (EPE) of
\((\Gamma ,T,R^{T})\) if for all
\(i\in N\), all
\(t=(t^1,\ldots ,t^n)\in T^N\) and all
\(\sigma ^i\in \Sigma ^i\),
$$\begin{aligned} \pi (s(t))R^{t^i} \pi (s^{-i}(t^{-i}),\sigma ^i), \end{aligned}$$
where
\(s^{-i}(t^{-i})\) is the vector
\((s^j(t^j))_{j\ne i}\). Let
\(s\in S^N\) be an EPE, then we call
\(\pi (s(t))\) the Nash outcome for
\(t\in T^N\). Game form
\(\Gamma \) is
ex post
\((\textit{Nash})\)
consistent for
\(T\) if
\((\Gamma ,T,R^{T})\) has an EPE for every
\(R^{T} \in W^{T}\). If
\(\mathcal {T}\) is an arbitrary collection of information structures – that is, with possibly different type set cardinalities – then we say that game form
\(\Gamma \) is
ex post
\((Nash)\)
consistent for
\(\mathcal {T}\) if
\((\Gamma ,T,R^{T})\) has an EPE for every
\(T \in \mathcal {T}\) and every
\(R^{T} \in W^{T}\). Specifically, if
\(\mathcal {T}= \{T\}\) with
\(\vert T^i\vert =1\) for every
\(i\in N\), then an ex post consistent game form
\(\Gamma \) is
Nash consistent (cf. Peleg et al.
2002). We say that effectivity function
\(E\) has an
ex post consistent representation for a collection
\(\mathcal {T}\) of information structures if there exists a game form
\(\Gamma \) such that
\(\Gamma \) is a representation of
\(E\) and
\(\Gamma \) is ex post consistent for
\(\mathcal {T}\). We say that
\(E\) has an
ex post consistent representation if there exists a game form
\(\Gamma \) such that
\(\Gamma \) represents
\(E\) and
\(\Gamma \) is ex post consistent for every information structure
\(T\).
Notation In the sequel, instead of \(E(\{i\})\), we usually write \(E(i)\).
In this section we present the basic game form which is used throughout the paper. We focus on this particular game form as it is one of the simplest game forms that yields the desired results. Later, we will extend and modify this game form to obtain our main results. Alternative representing game forms can be found in many places, notably Peleg (
1998), Peleg et al. (
2002), Peleg and Peters (
2010), and Boros et al. (
2010).
Let \(E\) be a monotonic and superadditive effectivity function. We fix a numbering of the alternatives in \(A\), say \(A=\{a_1,\ldots ,a_{|A|}\}\). For \(i\in N\) let \(F^i=\{(S,B)\mid i\in S\subseteq N \text{ and } B\in E(S)\}\). We define the game form \(G_0=(\Sigma ^1,\ldots ,\Sigma ^n;\pi ;A)\) as follows. The set of actions of \(i\in N\) is the set \(\Sigma ^i=\{(f,k)\mid f\in F^i \text{ and } k\in \{1,\ldots ,\vert A\vert \}\}\). The idea is that if \(B\in E(S)\) and \(f^i=(S,B)\) for all \(i\in S\), then the outcome is guaranteed to be within \(B\). The integer \(k\) is to make sure that every \(i\in S\) can cause every \(a\in B\) to be the outcome.
Let \(\sigma =(\sigma ^1,\ldots ,\sigma ^n)\in \Sigma ^N = \prod _{i\in N}\Sigma ^i\), where \(\sigma ^i=(f^i,k^i)\in \Sigma ^i\) for \(i\in N\). We say that coalition \(S\in P_0(N)\) is formed if there is \(B\in E(S)\) such that \(f^i=(S,B)\) for all \(i\in S\). Define \(D\in P_0(A)\) as follows. If no coalition is formed, then \(D=A\). Otherwise, let \(\{S_1,\ldots ,S_r\}\) be the collection of formed coalitions. For each \(j\in \{1,\ldots ,r\}\), there is \(B_j \in E(S_j)\) such that \(f^i=(S_j,B_j)\) for all \(i\in S_j\). Then let \(D=\bigcap _{j=1}^r B_j\). Note that \(D\ne \emptyset \) because \(E\) is superadditive and formed coalitions are pairwise disjoint. Suppose \(D=\{a_{j_1},\ldots ,a_{j_{|D|}}\}\) with \(j_1 < \ldots < j_{|D|}\). We define \(\pi (\sigma )=a_{j_p}\), where \(p=\sum \limits _{i\in N} k^i \text{(mod } |D|\text{) }+1\). Thus, given \(D\), every player can cause any \(a\in D\) to be the outcome by choosing \(k^i\) accordingly.
Proof
We first show that \(E(S)\subseteq E^{G_0}(S)\) for all \(S\in P_0(N)\). Let \(S\in P_0(N)\) and \(B\in E(S)\). Choose \(\sigma ^i=((S,B),1)\) for all \(i\in S\). Then the coalition \(S\) is formed and hence by definition of \(\pi \), \(\pi (\sigma ^{S},\tau ^{N{\setminus } S})\in B\) for all \(\tau ^{N{\setminus } S}\in \Sigma ^{N{\setminus } S}\). So, \(B(\sigma ^S)\subseteq B\).
In order to prove the converse inclusion, let \(S\in P_0(N)\) and \(B\in E^{G_0}(S)\). Since \(E(N)=P_0(A)\) and \(A\in E(S)\) for all \(S\in P_0(N)\), we can assume that \(S\ne N\) and \(B\ne A\). We show that \(B\in E(S)\). Let \(\sigma ^S\in \Sigma ^S\) be such that \(B(\sigma ^S)\subseteq B\) and for each \(i \in N {\setminus } S\) choose \(\tau ^i\) such that \(f^i=(N{\setminus } S,A)\). Consider the action profile \((\sigma ^S,\tau ^{N{\setminus } S})\). In this profile, since \(B \ne A\), \(S\) contains at least one formed coalition. Let \(\{S_1,\ldots ,S_r\}\) denote the set of all formed coalitions within \(S\); hence, for each \(j=1,\ldots ,r\) and \(i\in S_j\), \(\sigma ^i=(f^i,k^i)\) with \(f^i=(S_j,B_j)\) for some \(B_j \in E(S_j)\). Thus, for \((\sigma ^S,\tau ^{N{\setminus } S})\), the set of formed coalitions is \(\{S_1,\ldots ,S_r,N{\setminus } \bigcup _{j=1}^r S_j\}\). Since \(B_j\in E(S_j)\) for all \(j\in \{1,\ldots ,r\}\), and \(\bigcup _{j=1}^r S_j\subseteq S\), superadditivity and monotonicity imply \(\bigcap _{j\in J} B_j\in E(S)\). It remains to show that \(\bigcap _{j\in J} B_j\subseteq B(\sigma ^S)\), since then monotonicity implies that \(B\in E(S)\).
Take \(a\in \bigcap _{j\in J} B_j\). Since \(S\ne N\), given \(\sum _{i\in S}k^i\), \(N{\setminus } S\) is able to choose \(\sum _{i\in N{\setminus } S}k^i\) such that \(\pi (\sigma ^S,\tau ^{N{\setminus } S})=a\). Hence \(a\in B(\sigma ^S)\) for every \(a\in \bigcap _{j\in J} B_j\), which completes the proof. \(\square \)
4 Two-person effectivity functions
Throughout this section we assume that
\(N=\{1,2\}\). The following result is from Peleg et al. (
2002), see Remark 3.13 in the paper.
The original condition for the existence of a Nash consistent representation is condition (ii) in Lemma
5.1 below. However, for two players, it follows as a corollary from superadditivity and condition (ii) in Lemma
5.1 that
\(E\) must be maximal.
4.1 One-sided incomplete information
In this subsection, we consider the case of one-sided incomplete information. Without loss of generality, we assume that \(\vert T^1\vert \ge 1\) and \(\vert T^2\vert =1\). This means that the preference ordering of one player is commonly known, while the other player possibly has multiple types.
The main theorem of this subsection shows that in case of one-sided incomplete information, ex post consistent representation imposes no further conditions on the effectivity function compared to Nash consistent representation.
4.2 Two-sided incomplete information
In this subsection, still for two players, we consider the case of two-sided incomplete information.
A player \(i\in N\) is a singleton player if all minimal sets of player \(i\) in \(E(i)\) are singletons.
The following theorem characterizes all two-player effectivity functions with an ex post consistent representation for all information structures in which both players have at least two types. In fact, its proof shows that if there exists an ex post consistent representation of \(E\), then any representation is ex post consistent.