Transfers and exchange-stability in two-sided matching problems

Restructuring is an ongoing process in today’s dynamic business world where companies are constantly looking for ways to enhance efficiency, to gain competitive edge, and to keep up with industry trends. A tension exists, however, between a job allocation that is best from an individual worker’s or department’s point of view and that of the organization as a whole. Thus, centralized restructuring that involves moving staff across different departments in an institution, potentially, leaves some staff worse-off. When a restructuring schedule is devised one should consider, therefore, the opportunity for an ex-post reorganization by some departments or workers that may undermine the process as a whole.

The focus of study is the class of Pareto optimal matchings of workers to departments within an organization, and, within this set, we pay particular attention to those matchings that maximize an organization’s overall reward. We characterize the set of Pareto optimal matchings and the set of matchings that maximize the institution’s total reward by means of two stability notions: contractual exchange stability and compensational exchange stability, respectively.

Contractual exchange stability requires that any deviation, i.e. workers changing their assigned department or departments exchanging subsets of workers, is approved by all affected parties. Underlying this stability notion is the assumption that an agent grants approval to a deviation only if his reward does not decrease as a result of the change. Our notion of contractual exchange stability is in the spirit of the notion of contractual individual stability introduced by Bogomolnaia and Jackson (2002) and analyzed in the context of hedonic coalition formation games. Like contractual exchange stability, the notion of individual contractual stability presumes that an agent can leave her current coalition only if her group mates in that coalition agree to the move. These agents on their part agree only if they are at least as well off without the leaving member of the coalition as when she is in. Two aspects distinguish our study of contractual stability from that by Bogomolnaia and Jackson (2002): the cardinal representation of preferences and the deviation possibilities. The former difference is inconsequential as only the ordinal properties of agents’ preferences are utilized in the analysis of contractual exchange stability. The latter difference is driven by the fact that we focus on a two-sided many-to-one matching environment which is intrinsically more restrictive than that of coalition formation: for example, same-sided agents cannot be matched to each other without also being matched to an agent from the opposite side in a matching problem whereas any subset of agents can form a coalition in a coalition formation problem.

The cardinal representation of agents’ preferences is instead essential in the definition of compensation exchange stability. Compensation exchange stability allows the deviating parties to compensate the agents that are made worse-off by the change. Thus, a deviation is viable only if the net increase in rewards of the deviating agents exceeds the total losses of those agents whose rewards decrease due to the deviation. Clearly, some deviations which are not allowed under the notion of contractual exchange stability (because they leave some agents worse-off) are possible under the notion of compensational exchange stability (because those agents can be compensated).

Our notion of compensation exchange stability, just like the notion of contractual exchange stability, has its counterpart in the coalition formation literature. For example, Lazarova et al. (2011) use a similar notion in the context of coalitional games. These authors, however, focus on unilateral deviations in that context, whereas here deviations may involve multiple agents. Like in hedonic coalition formation games discussed above, in coalitional games there are no restrictions on the set of coalitions that may form, whereas in a matching problem such restrictions exist.

An important class of two-sided matching problems with a cardinal representation of agents’ preferences is the assignment problem. Seminal works that discuss algorithms for finding assignments with maximum total rewards are Knuth (1955) and Koopmans and Beckmann (1957) while Shapley and Shubik (1971) seminally define and study the notion of an assignment game.¹ In an assignment problem every tuple of matched agents is characterized by a cardinal value that is taken to represent the productivity or overall surplus that these agents can generate when matched together. In contrast, in the matching environment studied here every agent in a matched tuple is assigned a cardinal reward that represents the (share of the) value she is guaranteed in the matching. Our choice of assumptions is motivated, on the one hand, by our research question—the characterization of the set of Pareto optimal matchings and the set of matchings that maximize the agents’ total reward, respectively by means of stability notions—as it allows us to abstract away from the problem of how the joint surplus is shared among the matched agents and focus on the specificities of the deviation possibilities instead. On the other hand, it is motivated by the particular application that we have in mind—institutional organization and re-structuring—where workers are guaranteed a salary and departments face well-defined budgets.

This setting also directs our search for appropriate stability notions to be used in the analysis. Our notions of stability are related to the notion of exchange stability developed by Alcalde (1995) in the context of one-to-one matching problems. Gale and Shapley (1962) establish the concept of pairwise stability, which is adopted by Shapley and Shubik (1971) in the analysis of assignment games and the posterior literature. An important difference between the notions of exchange stability and those used in the matching literature is that in the former agents are only allowed to “swap” partners (i.e. the deviation involves agents from the same side) and are not allowed to opt out (i.e., unmatched agents are not considered) whereas in the latter agents are only allowed to “divorce”, i.e. opt out of a matching to be unmatched or deviate to a matching with a new partner from the opposite side. Importantly, Alcalde (1995) shows the independence of the set of exchange stable outcomes and the set of pairwise stable outcomes in the context of a standard one-to-one matching problem where no transfers between agents are allowed. Like Alcalde (1995), we take the view that an analysis based on exchange stability should be taken as complementary to that based on pairwise stability and that the choice of a stability notion should be driven by the research focus. In this study, our choice of stability notions is driven by our task to characterize two desirable sets of outcomes from an institution’s point of view.² Last, we point out that our framework for exchange stability is different from that of Alcalde (1995) in the sense that we consider many-to-one matching problems with peer effects (i.e. the reward of a worker in a matching depends on the group of coworkers assigned to the same department) and, moreover, allow for monetary rewards. In the former aspect our work is related to the literature on many-to-one matching problems with peer effects (cf. Dutta and Massó (1997) and more recently Pycia (2012)). We differ from these works in the adopted stability notions (in our case this is exchange stability, whereas they usually consider extensions of pairwise stability) and again in our focus on the sets of matching that maximize the total agents’ reward (as the many-to-one matching literature assumes ordinal preferences). Among the generalized assignment games works, e.g. Sotomayor (1999), on the other hand, we are not aware of any study where peer effects are modelled.

The adopted framework of cardinal representation of preferences allows us to also address the question if, given an initial matching of workers to departments, there exists a compensation schedule such that a centralized restructuring towards a matching of maximum total reward of the organization will be ex-post stable, in the sense that there will be no subset of workers or departments who can all by deviation obtain a higher reward. We analyze this question by introducing a transferable utility cooperative game, called a compensation matching game, and by showing that each compensation matching game has a nonempty core, which ensures that a compensation schedule as described above exists.

The paper is structured as follows. Section 2 provides notions on matchings for matching problems with monetary rewards and peer effects used throughout the paper. In Sect. 3, we characterize Pareto optimality of matchings by means of contractual exchange stability on the class of strict matching problems. In Sect. 4, we characterize matchings with maximum total reward by means of compensational exchange stability. Section 5 analyzes the existence of stable compensation schedules when an organization restructures the initial situation towards a matching of maximum total reward.

We consider two distinct types of economic agents: workers and departments. For ease of notation, we use lower case letters to denote a generic member i within the set of workers \(\mathcal {N}\), and upper case letters to denote a generic department H within the set of departments \(\mathcal {D}\). A vector of natural numbers \(q=(q_H)_{H\in \mathcal {D}}\) represents the capacity of each department with \(q_H\) being the capacity of department H with \(q_H\ge 1\). We assume that \(|\mathcal {N}|=\sum _{H\in \mathcal {D}}q_H\), i.e. the total number of workers equals the total capacity available at the departments. An allocation of workers to departments forms a partition of the set of workers in \(\mathcal {N}, P=\{P_H\}_{H\in \mathcal {D}}\), such that the size of the partition elements is consistent with the departmental capacity, i.e. \(|P_H|=q_H\) for all \(H\in \mathcal {D}\). The set of all such partitions is denoted by \(\mathcal {P}(\mathcal {N},\mathcal {D},q)\). If no confusion arises, we write \(\mathcal {P}\) instead of \(\mathcal {P}(\mathcal {N},\mathcal {D},q)\).

An allocation of workers to departments is given by a matching \(\mu \) where \(\mu :\mathcal {N}\rightarrow \mathcal {D}\) such that \(P(\mu )=\{\mu ^{-1}(H)\}_{H\in \mathcal {D}}\in \mathcal {P}\). The class of matchings is denoted by \(\mathcal {M}(\mathcal {N},\mathcal {D},q)\). If no confusion arises, we write \(\mathcal {M}\) instead of \(\mathcal {M}(\mathcal {N},\mathcal {D},q)\). Notice that in our definition of a matching, we do not allow for workers to remain unmatched and for departments to have unfilled capacity. The choice of our assumption is driven by the particular environment that we have in mind, where existing workers are allocated to existing departments and firing or a closure of a department are not a possibility. Alcalde (1995) study a model with similar characteristics. This assumption is also common in the assignment problem literature, where the goal is to find an assignment with the highest total value (see Pentico 2007 for a review). As our focus is on the set of Pareto optimal matchings and the set of matchings of maximum total reward (formally defined below), the assumption is inconsequential as long as any outcome in which a department has unfilled capacity or a worker is unmatched yields strictly lower reward than any other outcome where all departments have full capacity and all workers are matched to a department.³

We assume that for each worker a matching leads to a monetary reward which depends on the department to which he is assigned and the identity of his peers in that department. Thus, for each \(i\in \mathcal {N}\) there is a monetary reward function \(r_i\) where for each \((\mathcal {S}_i,H)\) with \(H\in D\) and \(\mathcal {S}_i\in 2^{N\setminus \{i\}}\) such that \(|\mathcal {S}_i|=q_H-1, r_i(\mathcal {S}_i,H)\) can be read as the reward that worker i receives when matched to department H with a set of coworkers \(\mathcal {S}_i\subseteq \mathcal {N}\setminus \{i\}\).

Similarly, we assume that for each department \(H\in \mathcal {D}\), there is a monetary reward function \(\pi _H:\{\mathcal {S}\subset \mathcal {N}\mid |\mathcal {S}|=q_H \}\rightarrow \mathbb {R}\).

Given a matching \(\mu \in \mathcal {M}\), we will use the shorthand notation \(r_i(\mu )\) to denote the monetary reward obtained by worker \(i\in \mathcal {N}\) when the department to which i belongs and the set of i’s coworkers are given by matching \(\mu \), i.e. \(r_i(\mu )=r_i(\mu ^{-1}(\mu (i))\setminus \{i\},\mu (i))\). Similarly, \(\pi _H(\mu )\) denotes the reward obtained by department \(H\in \mathcal {D}\) from the set of workers assigned by \(\mu \) to H, i.e. \(\pi _H(\mu )=\pi _H(\mu ^{-1}(H))\).

The tuple \((\mathcal {N},\mathcal {D},q,r,\pi )\) with \(r=(r_i)_{i\in \mathcal {N}}\) and \(\pi =(\pi _H)_{H\in \mathcal {D}}\) as above defines a many-to-one matching problem with peer effects and monetary evaluations or simply matching problem.

Strict preference profiles are a common assumption in many matching models (cf. Gale and Shapley 1962). Recently, some authors have investigated the link between indifference and inefficiencies, e.g. Erdil and Ergin (2008). In our setting, a matching problem is called strict if

In a Pareto optimal matching it is not possible to make any agent better-off by changing their department, in the case of a worker, or their workers, in the case of a department, without making another agent worse-off. The formal definition of a Pareto optimal matching is given below.

We will characterize Pareto optimality of matchings by means of a stability notion called contractual exchange stability. Recall that in our set up, departments have fixed capacities and the number of available workers is consistent with the available capacities. Thus, it seems natural to assume that an agents’ only possibility for deviation is to perform some switch with other agents on the same side (i.e. workers can exchange departments with other workers and departments can exchange workers with other departments) provided that the exchange meets certain contractual criteria. In particular, if worker i prefers the department and coworkers of worker j in matching \(\mu \), and vice versa, then i and j can exchange their places provided that their respective departments and peers are not made worse-off by the swap. Similarly, if two departments, G and H, can generate higher rewards by exchanging a (sub-)set of their workers under \(\mu \), then, they can perform the swap provided that none of the involved workers is made worse-off. The description above is limited to two-way exchanges, but we assume that three-way or even more complicated exchanges can be performed as long as the affected parties (peers or departments) do not earn a lower reward as a result of the exchange.

In the above definition, it is required that the blocking coalition contains at least two agents of the same type who agree to a switch and these agents can earn a strictly higher reward as a result of the switch [requirements (ii) and (ii\('\))]. Requirements (iii) and (iii\('\)) of the definition, on the other hand, are important only for those agents who are affected by the switches proposed by the blocking coalition. For all other agents, this requirement is automatically satisfied.

Below we introduce the notion of a contractually exchange stable matching.

The following example illustrates the need for restricting to the class of strict matching problems in Theorem 1.

Note that the requirement of a strict matching problem in Theorem 1 is only used to show that every contractually exchange stable matching is Pareto optimal. Therefore, we have the following result.

In the preceding section, the set of Pareto optimal matchings was characterized by means of a stability notion—contractual exchange stability—that presumes that agents can exercise veto power on deviations involving members of their coalition. As discussed in the introduction, the set of Pareto optimal matchings are desirable from a central manager’s point of view due to their efficiency. Within the set of Pareto optimal matchings some outcomes may be more desirable than others. In particular, all Pareto optimal matchings can be ranked on the basis of corresponding total joint rewards of all workers and departments. A central manager may thus be interested not only in achieving a Pareto optimal matching, but also in achieving a Pareto optimal matching that corresponds to maximum total reward. Note that we will refer to such matchings as matchings of maximum total reward and give a formal definition of this notion below. The question that this section addresses is what kind of stability notion characterize this subset of the set of Pareto optimal matchings, namely, the set of matchings of maximum total reward.

Note that every matching \(\mu \) of maximum total reward is automatically Pareto optimal.

Next, we present a new stability notion, compensational stability, to (later) characterize the set of matchings of maximum total reward. In contrast to the notion of contractual stability, compensation stability exploits the cardinal property of the agents’ reward function. Underlying the notion of compensation stability is the additional assumption that deviating agents can use the increase in their reward due to their deviation to compensate agents adversely affected by the deviation.

In this section, we analyze situations in which there is an initial matching of workers to departments which does not generate maximum total reward. Thus, there exists a possible restructuring where agents are reassigned by means of a matching of maximum total reward. The question that arises is how to compensate those workers or departments that are worse off in the new situation. This question will be analyzed using a cooperative matching game with transferable utility.

A cooperative (transferable utility) game in characteristic function form is a pair (N, v) where N is a finite set of players and \(v:2^N\rightarrow \mathbb {R}\) satisfying \(v(\emptyset )=0\). In general, \(v(\mathcal {C})\) represents the maximal joint reward that coalition \(\mathcal {C}\in 2^N\) can obtain when its members cooperate in an optimal way, without help of the players in \(N\setminus \mathcal {C}\).

The core of a game (N, v) is defined byi.e. the core is the set of efficient allocations of v(N) to which no coalition can reasonably object. An important subclass of games with nonempty core is the class of convex games (see Shapley (1971)). A game (N, v) is said to be convex if \(v(\mathcal {C}^1\cup \{i\})-v(\mathcal {C}^1)\le v(\mathcal {C}^2\cup \{i\})-v(\mathcal {C}^2)\) for every \(i\in N\) and every \(\mathcal {C}^1\subseteq \mathcal {C}^2\subseteq N\setminus \{i\}\).

Before starting with the formal analysis of compensation in matching problems with an initial matching, we provide an illustrative example.

Given a matching problem \((\mathcal {N},\mathcal {D},q,r,\pi )\) and an arbitrary initial matching \(\mu _0\), we are interested in studying adequate compensations among the workers and departments when they come together to improve their joint situation by adopting a matching of maximum total reward. To do this, we define a corresponding cooperative game whose core elements provide stable allocations of the extra rewards obtained by means of cooperation.

Let \((\mathcal {N},\mathcal {D},q,r,\pi )\) be a matching problem with constraints and let \(\mu _0\) be an initial matching. We denote by \(\mathcal {M}^{\text {max}}\) the set of matchings of maximal total reward, i.e.For \(i\in \mathcal {N}\) and \(\hat{\mu }\in \mathcal {M}^{\text {max}}\), we denote by \(d_i(\hat{\mu })\) the difference of reward for agent \(i\in \mathcal { N}\) when going from \(\mu _0\) to \(\hat{\mu }\), i.e. \(d_i(\hat{\mu })=r_i(\hat{\mu })-r_i(\mu _0)\); we set \(d_i^+(\hat{\mu })=\max \{0,r_i(\hat{\mu })-r_i(\mu _0)\}\) and \(d_i^-(\hat{\mu })=-\min \{0,r_i(\hat{\mu })-r_i(\mu _0)\}\). Note that for every \(\hat{\mu }\in \mathcal {M}^{\text {max}}\) it follows \(d_i(\hat{\mu })=d_i^+(\hat{\mu })-d_i^-(\hat{\mu })\). We analogously define \(d_H(\hat{\mu })=\pi _H(\hat{\mu })-\pi _H(\mu _0)\), and set \(d_H^+(\hat{\mu })=\max \{0,\pi _H(\hat{\mu })-\pi _H(\mu _0)\}\), and \(d_H^-(\hat{\mu })=-\min \{0,\pi _H(\hat{\mu })-\pi _H(\mu _0)\}\) for every \(H\in \mathcal {D}\) and every \(\hat{\mu }\in \mathcal {M}^{\text {max}}\).

Note that given a matching with maximum total reward \(\hat{\mu }\), we conservatively assume that a coalition \(\mathcal {C}\) is required to compensate all agents that suffer from changing the initial situation. Being conservative, it is also assumed that a most disadvantageous (from the perspective of \(\mathcal {C}\)) matching of maximum total reward will be adopted. Note that \(v(\mathcal {N}\cup \mathcal {D})\) equals the increase in total rewards achievable by adopting any matching with maximum total reward.

The following example illustrates the computation of matching games with constraints.

It turns out that each compensation matching game has a nonempty core. This can be shown using a relation between compensation matching games and bankruptcy games. A bankruptcy problem is defined by a tuple (N, E, c) where \(N=\{1,\ldots ,n\}\) is the set of agents, E is the estate that must be shared among the agents, and \(c\in \mathbb {R}^{N}\) is the vector of claims of the agents satisfying \(\sum _{i\in N}c_{i}\ge E\). Bankruptcy problems have being studied from a game theoretical viewpoint in O’Neill (1982). Given a bankruptcy problem (N, E, c), the corresponding bankruptcy game, \((N,v_{(N,E,c)})\), is defined byfor every \(\mathcal {C}\subset N\). In Curiel et al. (1987) it is shown that bankruptcy games are convex.

The following example illustrates the construction of a bankruptcy game given a matching problem and an initial matching and the convexity property of these games.

Theorem 3 tells us that we can find a compensation schedule such that a centralized restructuring resulting in a matching of maximum total reward of the organization will be ex-post stable, in the sense that there will be no subset of workers or departments who can by deviation obtain a higher reward. Still, the core of matching games may contain many possible allocations, thus, the question remains what allocation will be selected. The following example illustrates how such a selection could be conducted.