Implementation in strong core by codes of rights

The challenge of implementation lies in designing a mechanism (i.e., a game form) in which the equilibrium behavior of agents always coincides with the recommendation given by a social choice rule (SCR). If such a mechanism exists, the SCR is implementable. Most early studies of implementation focused on noncooperative solution concepts, such as the Nash equilibrium (Maskin 1999) and its refinements (e.g., Moore and Repullo 1988; Abreu and Sen 1990).

Although implementation theory has had a tremendous success in identifying the class of SCRs that are implementable in various information structures, a nagging criticism of the theory is that many of its constructive proofs rely on questionable tail-chasing procedures to eliminate unwanted equilibria, such as integer or modulo games (Jackson 1992).¹

Since the relevance of the theory depends on the qualities of the devised mechanisms, economists have also been interested in understanding how to circumvent the limitations imposed by such unnatural features by exploring the possibilities offered by approximate (as opposed to exact) implementation (Abreu and Matsushima 1992), as well as by implementation by bounded mechanisms (Jackson 1992; Mukherjee et al. 2019). One additional way around those limitations is offered by implementation by codes of rights, recently proposed by Koray and Yildiz (2018).

As demonstrated in the seminal paper by Koray and Yildiz (2018), an alternative to the noncooperative approach is to allow groups of agents to coordinate their behaviors in a mutually beneficial manner. To move away from non-cooperative modeling, the details of coalition formation are left unspecified. Consequently, coalitions—not individuals—become the basic decision-making units. Here, the role of the solution concept is to explain why, when, and which coalition forms and what it can achieve.

More importantly, the chosen coalitional solution concept is independent of the physical structure under which coalition formation takes place (e.g., Chwe 1994). This structure, often defined by an effectivity relationship, specifies which coalitions can form given a status quo outcome, and what they can achieve when they form (i.e., what new status quo outcomes they can induce). From an implementation viewpoint, the effectivity relationship is the design variable, playing the role of the mechanism.

Koray and Yildiz (2018) formalize this idea and study its implications. In their framework, the implementation of an SCR is achieved by designing a generalization of the effectivity relationship, introduced by Sertel (2001), called a code of rights.²

A code of rights specifies, for each pair of outcomes (x, y), a collection of coalitions \(\gamma (x,y)\) that are effective at moving from x to y. The code of rights is more flexible than the effectivity function, as it allows the strategic options of coalitions to depend on how the status quo outcome is reached (i.e., on the current state).

Note that Koray and Yildiz (2018) introduce the more general concept of rights structures, which the code of rights is a special case of. In a rights structure, the state space may be augmented with other features apart from the set of outcomes Z, such as a preference profile. By restricting attention to the set of outcomes as the state space, the design exercise admits a very intuitive interpretation, bearing a straightforward analogy to the exercise of rights in the real world. This is in contrast to the more general rights structure framework which, although has shown to be more permissive for the implementation exercise, it does not easily conform with our intuition. We believe that the limitations that implementation by codes of rights bears better convey the constraints of the mechanism design exercise in a real world scenario, thus making it more applicable.

As a coalitional solution, Koray and Yildiz (2018) adopt the core defined in terms of strong domination. Outcome x strongly dominates y if a coalition K exists that is effective at moving from x to y, and this move is beneficial for all members of K. The weak core is the set of outcomes that are not strongly dominated.

The core can also be defined in terms of weak domination. That is, x weakly dominates y if a coalition K exists that is effective at moving from x to y, and this move is beneficial for at least one member of K and non-harmful for others. The strong core is the set of all outcomes that are not weakly dominated.

Most studies tend to utilize the notion of the weak core that admits in general more simple results. However, whether one should consider the weak or the strong core as a solution concept is not straightforward. That is, there is no clear reason to prefer one over the other for any environment, as such choice relies heavily on the particular issues that arise in each case. For example, as pointed out in Roth and Postlewaite (1977), in a market with indivisibilities, an important consequence of using weak instead of strong domination is that the strong core has no instability problems. Moreover, in the exchange market model of Shapley and Scarf (1974), the strong core is included in the set of competitive allocations (Wako 1984).

In this paper, we fully characterize the set of implementable SCRs in strong core by codes of rights (Theorem 1). Our characterization consists of the well-known unanimity condition and a new condition that we call SC-monotonicity, a variant of strong monotonicity as found in Korpela et al. (2020), who study implementation in codes of rights in weak core.

The remainder of the paper is divided into four sections. Section 2 sets out the theoretical framework and outlines the implementation model. Section 3 contains our characterization theorem. In Sect. 4 we provide some remarks and applications of our results, while in Sect. 5 we conclude and discuss points for further research.

Our environment consists of a collection of n agents (we write N for the set of agents), a (nonempty) set of outcomes Z. By \(R_{i}\) we denote agent i’s weak preference relation on Z and \(R=(R_{1},...,R_{n})\) denotes a preference profile. As usual, the asymmetric part of \(R_{i}\) we denote by \(P_{i}\). The set of agent i’s admissible preferences is \({\mathcal {R}}_{i}\) and the set of all admissible preference profiles is denoted by \({\mathcal {R}}\).

We focus on complete information environments in which the true preference profile is common knowledge among the agents but unknown to the designer. The power set of N is denoted by \({\mathcal {N}}\), and \({\mathcal {N}}_{0} \equiv {\mathcal {N}}-\{\varnothing \}\) is the set of all nonempty subsets of N. Each group of agents, K (in \({\mathcal {N}}_{0}\)), is a coalition. By slightly abusing notation, for all \(R\in {\mathcal {R}}\) and \(K\in {\mathcal {N}}_{0}\), let x \(P_{K}\) y denote \(xR_{i}y\) for all \(i\in K\), and \(xP_{j}y\) for some \(j\in K\).

The goal of the designer is to implement a social choice rule (SCR) \(F:{\mathcal {R}}\rightarrow 2^{Z}\) defined by \(\varnothing \ne F\left( R\right) \subseteq Z\) for every \(R\in {\mathcal {R}}\). We refer to \(x\in F\left( R\right) \) as an F-optimal outcome at R. To implement his goal, the designer devises a code of rights \(\gamma \), which is a (possibly empty) correspondence \(\gamma :Z\times Z\twoheadrightarrow {\mathcal {N}}\). \(\gamma \) specifies, for each pair of outcomes \(\left( x,y\right) \), a family of coalitions \(\gamma \left( x,y\right) \) entitled to approve a change from outcome x to y.

For any cooperative game \(\left( \gamma ,R\right) \), we say that x (strongly) dominates y if there exists a coalition K such that (i) \(K\in \gamma \left( y,x\right) \) and (ii) \(xP_{i}y\) for all \(i\in K\). The definition of weak domination is obtained by relaxing condition (ii) to read (iia) \(xP_{K}y\). The core of the game \(\left( \gamma ,R\right) \), denoted by \(C\left( \gamma ,R\right) \), is the set of undominated outcomes. The strong core of \(\left( \gamma ,R\right) \), denoted by \(SC\left( \gamma ,R\right) \), is instead the set of weakly undominated outcomes.

Given preference profile R and outcome x, let agent i’s lower contour set be defined by \(L_{i}\left( x,R\right) \equiv \left\{ y\in Z|xR_{i}y\right\} \), and agent i’s strict lower contour set be defined by \(SL_{i}\left( x,R\right) =\{y\in Z|xP_{i}y\}\). Fix any \(i\in N\), any \(R,R^{\prime }\in {\mathcal {R}}\) and any \(x\in Z\). We say that \(R^{\prime } \) is a monotonic transformation of R at x for agent i if \(L_{i} (x,R)\subseteq L_{i}(x,R^{\prime })\). If \(R^{\prime }\) is a monotonic transformation of R at x for each agent \(i\in N\), we say that \(R^{\prime }\) is a monotonic transformation of R at x. F satisfies monotonicity³ provided that for all \(R,R^{\prime }\in {\mathcal {R}}\) and all \(x\in Z\), if \(x\in F\left( R\right) \) and \(R^{\prime }\) is a monotonic transformation of R at x, then \(x\in F\left( R^{\prime }\right) . \)

As we will show later, monotonicity is not a necessary condition for SC-implementation by a code of rights. Thus, we introduce below a new condition, called strong core monotonicity, simply SC-monotonicity, using the following additional notation. For any coalition \(K\in {\mathcal {N}}_{0}\), profile \(R\in {\mathcal {R}}\), and outcome \(x\in Z\), letNow, we define our notion of the “collective lower contour set” of a coalition \(K\in {\mathcal {N}}_0\) at \((x,R)\in Z\times {\mathcal {R}}\) as follows:Finally, given a SCR F, we define:For completeness, we assume that when \(F^{-1}(x)=\emptyset \), \(S\Lambda _K^F(x)=Z\).

At this stage, it would be useful to compare SC-monotonicity with strong monotonicity, which is found to be necessary and almost sufficient for C-implementation in Korpela et al. (2020). First we define:Now, strong monotonicity is stated as follows:

The difference between the two conditions lies in the “collective lower contour set” of a coalition.⁴ Notice that, in the case of strong monotonicity, the collective lower contour set of coalition K is represented by \(\cup _{i\in K}L_i(x,R)\), while it becomes \(S\Lambda _K(x,R)=\cap _{i\in K}L_i(x,R)\bigcup \cup _{i\in K}SL_i(x,R)\) in the case of SC-monotonicity. In the former case, a coalition which is entitled to move from x to y will form when all of its potential members strictly prefer y to x unanimously, i.e. when \(y\notin \cup _{i\in K}L_i(x,R)\). On the other hand, in the latter case dealt with in this paper, a coalition which is entitled to move from x to y will form when all of its potential members weakly prefer y to x with the preference being strict for at least one agent, i.e. when \(y\notin S\Lambda _K(x,R)\).

As we formally show below, SC-monotonicity is a necessary condition for SC-implementation via codes of rights, and it is sufficient when combined with another necessary condition known as unanimity. This condition states that, if an outcome is at the top of the preferences of all agents, then that outcome should be selected by the SCR. The condition can be stated as follows:

We show that SC-monotonicity and unanimity are necessary and sufficient for SC-implementation by codes of rights.

We have studied the problem of implementing a social choice rule with codes of rights when the solution concept is the strong core, by characterizing the set of implementable rules. With our results we also aim to further motivate the study of mechanism design with cooperative game-theoretic devices, a special case of which is a code of rights. Additionally, we aim to outline the relevance of the strong core as a solution concept in economic design.

Our research can be taken further in several directions. Apart from applications of our results in more structured environments, a particularly fruitful avenue would be to relax the myopic assumption in the solution concept. Indeed, it is not clear yet what implications does farsightedness bear for the literature.