Abstract
We study the existence of group strategy-proof stable rules in many-to-many matching markets under responsiveness of agents’ preferences. We show that when firms have acyclical preferences over workers the set of stable matchings is a singleton, and the worker-optimal stable mechanism is a stable and group strategy-proof rule for firms and workers. Furthermore, acyclicity is the minimal condition guaranteeing the existence of stable and strategy-proof mechanisms in many-to-many matching markets.
Similar content being viewed by others
1 Introduction
Many real-world markets are many-to-many. The canonical example of a many-to-many market is the specialty training followed by junior doctors in the UK (Roth 1991). Other examples of many-to-many markets are markets for part-time workers and the non-exclusive dealings between down-stream firms and up-stream providers. Many-to-many markets are also useful to model multi-unit assignment problems such as course allocations (see Budish 2011; Sönmez and Ünver 2010; Kojima 2013) or the assignment of landing slots (see Schummer and Vohra 2013; Schummer and Abizada 2017). We consider a many-to-many matching market and assume that preferences are responsive (Roth 1985). Under this assumption, no mechanism is stable and strategy-proof for even one side of the market (see Roth and Sotomayor 1990). Furthermore, even in one-to-one markets, there is no mechanism that is stable and strategy-proof for the agents on both sides of the market. Due to these negative results, the literature has concentrated on mechanisms guaranteeing strategy-proofness on one side of the market, thus overlooking preference manipulation from agents on the other side of the market (but see Romero-Medina and Triossi 2013a for capacity manipulation). However, manipulation by agents on both sides of the market is a concern, for example, in different school choice mechanisms (see Abdulkadiroğlu et al. 2005). In this paper, we explore the possibility of designing revelation mechanisms that are stable, strategy-proof, and group strategy-proof for the agents on both sides of the market, by restricting the preference domain. Indeed, stability and strategy-proofness are central concerns in market design. Theoretical and empirical findings suggest that centralized markets that achieve stable outcomes are more successful than centralized markets that do not achieve stable outcomes. In particular, those that do not produce stable outcomes are more likely to break down and be abandoned (see Roth and Sotomayor 1990; Roth 2008; Abdulkadiroğlu and Sönmez 2013).Footnote 1 Additionally, strategy-proofness prevents agents from needing to strategize. This is relevant in markets where agents differ in their sophistication. Finally, group strategy-proofness implies strategy-proofness and prevents welfare losses resulting from collusion among agents. We show that, when the preferences of all agents are responsive and the firms have acyclical preferences, the worker-optimal stable mechanism is group strategy-proof. A cycle in the preferences of the firms occurs when there is an alternating list of firms and workers “on a circle” such that every firm prefers the worker on its clockwise side to the worker on its counterclockwise side and finds both acceptable. We say that preferences are acyclical if there are no cycles.
First, we show that, under responsive preferences, when the preferences of the firms are acyclical, the set of stable matchings is a singleton, and the unique stable matching can be implemented through a procedure that we call Adjusted Serial Dictatorship. In this procedure, each worker, at her turn, selects her favorite firms among those she is acceptable to and that still have vacant positions. We employ this result to show that, under acyclicity, any stable mechanism is group strategy-proof both for firms and workers. We conclude by showing that acyclicity is also the minimal condition guaranteeing the existence of a mechanism that is stable and strategy-proof for the agents on both sides of a many-to-many matching market under responsive preferences. More precisely, we show that if the preferences of the firms have a cycle, there exists a responsive profile of preferences for the workers such that no stable mechanism is strategy-proof. Our results imply that strategy-proofness and group strategy-proofness are equivalent requirements when imposed on a stable mechanism under responsive preferences. In general, group strategy-proofness is more demanding than strategy-proofness. In particular, in the school choice problem, the student-optimal stable mechanism always provides a stable and strategy-proof mechanism. However, efficiency and group strategy-proofness require priorities to satisfy an acyclicity condition (see Ergin 2002). Our characterization contributes in explaining the restrictiveness of imposing strategy-proofness on stable mechanisms in many-to-many matching markets.
Finally, we apply our results to the course allocation problem. In this case, only one side of the market is strategic, and acyclicity is a sufficient condition for the existence of a strategy-proof mechanism. We show that acyclicity is also necessary if the designer cannot condition the mechanism on the capacities of the courses.
1.1 Related literature
Acyclical preferences have been extensively studied in matching markets. The concept of acyclicity that we use coincides with that introduced in Romero-Medina and Triossi (2013b) for one-to-one matching markets. In many-to-one matching markets, Ergin (2002) introduces a weaker notion of acyclicity and shows that the worker-optimal stable mechanism is efficient and group strategy-proof for workers if and only if the preferences of the firms are acyclical. Kesten (2012) and Romero-Medina and Triossi (2013a) find that two different forms of acyclicity are necessary and sufficient conditions for worker-optimal stable matching to be immune to capacity manipulation. Pycia (2012) shows that the core is nonempty in every state if and only if agents’ preferences are pairwise-aligned (a condition equivalent to acyclicity). Furthermore, under pairwise-alignment, the core is a singleton and a large family of games implements the unique core allocation in strong Nash equilibrium.
Core manipulability and its relation to singleton cores have been previously studied. Sönmez (1999) extends previous results by Demange (1987) and shows that there exists an allocation rule that is Pareto efficient, individually rational and strategy-proof if and only if the core is essentially single-valued. Also, in one-to-one matching markets, Demange et al. (1987) study the manipulability of stable matchings by coalitions including agents on both sides of the market. In this case, uniqueness guarantees that a matching is not manipulable. This result does not hold in many-to-many matching markets (see Example 1).
Our results complement those in Kojima (2013) and Jiao and Tian (2017). In a multi-unit assignment problem, Kojima (2013) proves that the worker-optimal stable matching is strategy-proof for workers if and only if any cycle involves only the top-ranked workers, a condition that he calls essential homogeneity, which is weaker than the concept of acyclicity that we employ in this paper.Footnote 2 Jiao and Tian (2017) prove that the worker-optimal stable mechanism is group strategy-proof for workers if preferences satisfy the extended max-min criterion and a quota saturability condition. The preference domain in Jiao and Tian (2017) reflects a high degree of ambiguity aversion. Instead, we assume the preferences to be responsive.Footnote 3 The concept of group strategy-proofness that we employ is stronger than the one in Jiao and Tian (2017). For an allocation to be strategy-proof, they require that no coalition of agents can misrepresent their preferences in a way that makes each member of the coalition strictly better off. This concept is often referred to as group incentive compatibility or weak group strategy-proofness (see Roth and Sotomayor 1990; Hatfield and Kojima 2009; Barberá et al. 2016). Instead, we use the usual concept of group strategy-proofness requiring each member of the coalition to be weakly better off and at least one to be strictly better off. In contrast to Jiao and Tian (2017) and Kojima (2013), we focus on preventing manipulation and collusion by the agents on both sides of the markets.
The structure of this paper is as follows. Section 2 introduces the model. Section 3 presents the results. Section 4 concludes. The proofs are in the “Appendix”.
2 The model
In our model, there are two disjoint and finite sets of agents, the set of firms F and the set of workers W. A generic firm is denoted by f, a generic worker by w and a generic agent by \(v\in V=F\cup W.\) Each worker can work for more than one firm, and firms can hire more than one worker. Let \(P_{F}=\left( P_{f}\right) _{f\in F}\) be a list of firms’ preferences over subsets of workers, where for every \(f\in F\), \(P_{f}\) is a strict order defined on \(2^{W}\). For all \(w,w^{\prime }\in W\), \(wP_{f}w^{\prime }\), \(wP_{f}\emptyset \) and \(\emptyset P_{f}w\) denote \(\left\{ w\right\} P_{f}\left\{ w^{\prime }\right\} \), \(\left\{ w\right\} P_{f}\emptyset \) and \(\emptyset P_{f}\left\{ w\right\} \), respectively. Let \(P_{W}=\left( P_{w}\right) _{w\in W}\) be a list of workers’ preferences over subsets of firms, where for every \(w\in W\), \(P_{w}\) is a strict order defined on \(2^{F}\). For each \(v\in V\), we denote by \(R_{v}\) the corresponding weak preferences. A profile \(P=\left( P_{v}\right) _{v\in V}\) is a list of preference orderings. Given a profile \(P=\left( P_{v}\right) _{v\in V}\) and \(V'\subseteq V,\) we denote by \(P_{V'}\) the vector \(\left( P_{v}\right) _{v\in V'}\). The triple \(\left( F,W,P\right) \) is called a matching market. The favorite group of workers for firm f among those belonging to \(W^{\prime }\) is called the choice set from \(W^{\prime }\). We denote the choice set from \(W^{\prime }\) by \(Ch_{f}(W^{\prime },P_{f})\) or by \(Ch_{f}(W^{\prime })\) when no ambiguity is possible. Formally, \(Ch_{f}(W^{\prime },P_{f})=\max _{P_{f}}\left\{ W^{\prime \prime }:W^{\prime \prime }\subseteq W^{\prime }\right\} \). If \(\emptyset P_{f}W^{\prime }\) firm f prefers not to employ any worker rather than jointly employing the workers in \(W^{\prime }\), then \(W^{\prime }\) is called unacceptable to f. Otherwise \(W^{\prime }\) is acceptable to f. We denote the set of workers who are individually acceptable to f by \(A\left( f,P_{f}\right) \) or \(A\left( f\right) \) when no ambiguity is possible. The maximum number of workers that firm f is willing to hire is f’s capacity, which we denote by \(q_{f}\); formally, \(q_{f}=\max \left\{ \left| W^{\prime }\right| :W^{\prime }P_{f}\emptyset \right\} \).Footnote 4 For every \(w\in W\) and for every \(F'\subseteq F\) , we define \(Ch_{w}(F^{\prime },P_{w})\), \(Ch_{w}(F^{\prime })\), \(A\left( w\right) \), and \(q_{w}\) similarly.
We represent firms’ preferences over acceptable sets of workers through ordered lists. Let \(K>0\) and let \(W_{i}\subseteq W\), \(W_{i}\ne \emptyset \) for every i, \(1\le i\le K\). The notation \(P_{f}:W_{1},W_{2},\ldots ,W_{K}\) means \(W_{i}P_{f}W_{j}\) for every i, j \(1\le i<j\le K\) and \(W_{K}P_{f}\emptyset \); for all \(W'\subseteq W\), \(W'\notin \left\{ W_{1},W_{2},\ldots ,W_{K},\emptyset \right\} \), \(\emptyset P_{f}W'\). Workers’ preferences are represented similarly.
Matchings assign workers to firms. A matching on (F, W, P) is a function \(\mu :V\rightarrow 2^{V}\) such that, for every \((f,w)\in F\times W\): (i) \(\mu (f)\in 2^{W}\), (ii) \(\mu (w)\in 2^{F}\) and (iii) \(f\in \mu (w)\Leftrightarrow w\in \mu (f)\). We denote by \({\mathcal {M}}\) the set of matchings on \(\left( F,W,P\right) \). A matching \(\mu \) is individually rational in \(\left( F,W,P\right) ,\) if \(Ch_{v}(\mu (v))=\mu (v)\) for all \(v\in V\). Individual rationality captures the idea that hiring and joining a firm are voluntary. A matching \(\mu \) is blocked by the pair \((f,w)\in F\times W\), \(f\notin \mu \left( w\right) \), if (i) \(f\in Ch_{w}\left( \mu (w)\cup \left\{ f\right\} \right) \) and (ii) \(w\in Ch_{f}\left( \mu (f)\cup \{w\}\right) \). A firm-worker pair \(\left( f,w\right) \) blocks a matching \(\mu \) if worker w is not employed at f, but she would like to join f and f would like to hire w. A matching \(\mu \) is stable in (F, W, P) if it is individually rational and if no pair blocks it. Otherwise, \(\mu \) is unstable. \(\varGamma (F,W,P)\) denotes the set of matchings that are stable in (F, W, P).
The set of stable matchings may be empty. For this reason, we focus on responsive preferences that guarantee that the set of stable matchings is nonempty (see Alkan 1999). We say that the preferences of a firm, \(P_{f}\), are responsive if, for all \(W^{\prime }\subseteq W\) such that \(\left| W^{\prime }\right| \le q_{f}-1\) and for all \(w,w^{\prime }\in W{\setminus }{W'}\): (i) \(W^{\prime }\cup \left\{ w\right\} P_{f}W^{\prime }\cup \left\{ w^{\prime }\right\} \Leftrightarrow wP_{f}w^{\prime }\) and (ii) \(W^{\prime }\cup \left\{ w\right\} P_{f}W^{\prime }\Longleftrightarrow w\in A\left( f\right) \).
In words, f has responsive preferences if for any two assignments that differ in one worker only, it prefers the assignment containing the most preferred worker. Responsive preferences for workers are defined similarly. The set of responsive preferences for agent \(v\in V\) is denoted by \({\mathcal {P}}_{v}\). For all \(V'\subseteq V\) let \({\mathcal {P}}_{V'}=\prod _{v\in V'}{{\mathcal {P}}_{v}}\). If firms and workers have responsive preferences, the set of stable matchings forms a nonempty lattice (see Alkan 1999). Furthermore, there exists a stable matching that is Pareto superior for workers to all other stable matchings, the worker-optimal stable matching. We denote by \(\mu ^{W}\left( P\right) \), the worker-optimal stable matching of market \(\left( F,W,P\right) \).Footnote 5
A cycle (of length \(T+1\)) in \(P_{F}\) is given by distinct workers \(w_{0},w_{1},\ldots ,w_{T}\in W\) and distinct firms \(f_{0},f_{1},\ldots ,f_{T}\in F\) such that
-
1.
\(w_{T}P_{f_{T}}w_{T-1}P_{f_{T-1}},\ldots ,P_{f_{2}}w_{1}P_{f_{1}}w_{0}P_{f_{0}}w_{T}\);
-
2.
for every t, \(0\le t\le T\), \(w_{t}\in A\left( f_{t+1}\right) \cap A\left( f_{t},\right) \), where \(f_{T+1}=f_{0}\).
A preference profile on individual workers \(P_{F}\) is acyclical if it has no cycles.
Let us assume that a cycle exists. If every worker in a cycle \(w_{t-1}\) is initially assigned to firm \(f_{t}\), every firm is willing to exchange its assigned worker with its successor \(w_{t}\).
A mechanism \(\varphi \) is a function that associates a matching to every preference profile: \(\varphi :{\mathcal {P}}_{V}\rightarrow {\mathcal {M}}\). A mechanism \(\varphi \) is stable if \(\varphi \left( P\right) \) is stable for all \(P\in {\mathcal {P}}_{V}\). An example of stable mechanism is the worker-optimal stable mechanism, \(\mu ^{W} \) which assigns to every profile of preferences \(P\in {\mathcal {P}}_{V}\), the worker-optimal stable matching of market \(\left( F,W,P\right) \), \(\mu ^{W}\left( P\right) \). Let \({\mathcal {D}} \subseteq {\mathcal {P}}_{V}\). A mechanism \(\varphi \) is Pareto optimal on \({\mathcal {D}}\) if for every \(P\in {\mathcal {D}}\), there exists no individually rational matching \(\mu \), such that \(\mu \left( v\right) R_{v}\varphi \left( P\right) \left( v\right) \) for every \(v\in V\) and \(\mu \left( v\right) P_{v}\varphi \left( P\right) \left( v\right) \) for at least one v. A mechanism is Pareto optimal if it implements matchings for which there is no alternative individually rational matching that is weakly preferred by all agents and strongly preferred by at least one agent. A mechanism \(\varphi \) is strategy-proof on \({\mathcal {D}}\) if for every \(v\in V\), \(\varphi (P)\left( v\right) R_{v}\varphi (P'_{v},P_{-v})\left( v\right) \) for every \(P\in {\mathcal {D}}\), \(P'_{v}\in {\mathcal {P}}_{v}\). A mechanism is strategy-proof if reporting her true preference relation is a (weakly) dominant strategy for every agent. A mechanism is group strategy-proof on \({\mathcal {D}}\) if there do not exist \(P\in {\mathcal {D}}\), a nonempty set of agents, \(V'\subseteq V\), P, \(P'_{V'}=\left( P'_{v}\right) _{v\in V'}\in {\mathcal {P}}_{V'}\) such that \(\varphi (P'_{V'},P_{V{\setminus } V'})\left( v\right) R_{v}\varphi (P)\left( v\right) \) for every \(v\in V'\) and \(\varphi (P'_{V'},P_{V{\setminus } V'})\left( v'\right) P_{v'}\varphi (P)\left( v'\right) \) for some \(v'\in V'\). The mechanism \(\varphi \) is group strategy-proof if no subset of agents can benefit by jointly misrepresenting their preferences. Since capacity, in our model, is endogenous to the preference profile, a strategy-proof mechanism prevents capacity manipulation (see Sönmez 1997).
3 Group strategy-proofness and uniqueness
In many-to-many matching markets, if the preferences of both workers and firms are responsive, no stable mechanism is strategy-proof or Pareto optimal for workers (see Roth and Sotomayor 1990). In this section, we prove that the assumption of acyclical preferences is a necessary and sufficient condition to overcome the incompatibility of strategy-proofness, stability and Pareto optimality.
We first show that when the firms have acyclical preferences over individual workers, there exists an underlying order \(w_{1}\),\(w_{2}\),...,\(w_{\left| W\right| }\) on the set of workers that is able to sustain a stable matching through an Adjusted Serial Dictatorship.
Let us assume that \(P_{v}\) is responsive for all \(v\in V\) and that \(P_{F}\) is acyclical and define an order on W as follows. Let \(w_{1}\in W\) be a worker who is always ranked first, among individual workers, by any firm to which she is acceptable. Formally, let \(w_{1}\) be such that, for all \(f\in F\) such that \(w_{1}P_{f}\emptyset \), there exists no \(w\in W\) with \(wP_{f}w_{1}\).Footnote 6 Such a \(w_{1}\) exists because \(P_{F}\) is acyclical. For \(0\le t\le \left| W\right| -1\), let \(w_{t+1}\) be a worker who is never ranked below workers other than \(w_{1},w_{2},\ldots ,w_{t}\) by any firm to which she is acceptable. Formally, let \(w_{t+1}\in W\) be such that, for all \(f\in F\) such that \(w_{t+1}P_{f}\emptyset \), there exists no \(w\in W{\setminus }\left\{ w_{1},w_{2},\ldots ,w_{t}\right\} \) such that \(wP_{f}w_{t+1}.\) Notice that, in general, the selection of \(w_{t}\) is not unique, for every t, \(1\le t\le \left| W\right| -1\) and thus, the procedure defines a family of orders on W. The position of worker w in the sequence is uniquely determined when, for example, w is acceptable to all firms.
Given \(w_{1}\),\(w_{2}\),...,\(w_{\left| W\right| }\) selected as above, we define an Adjusted Serial Dictatorship by letting each worker choose among the firms that she is acceptable to and that still have vacant positions according to \(w_{1}\),\(w_{2}\),...,\(w_{\left| W\right| }\).
Let \(A_{1}\left( P\right) =\{ f:w_{1}\in A\left( f\right) \} \), be the set of firms to which worker \(w_{1}\) is acceptable. Define \(\mu ^{AS}\left( P\right) \left( w_{1}\right) =Ch_{w_{1}}\left( A_{1}\left( P\right) \right) \). For all t, \(1\le t\le \left| W\right| -1\), let \(A_{t+1}\left( P\right) =\{ f:w_{t+1}\in A\left( f\right) ,|\bigcup _{s\le t,f\in \mu ^{AS}\left( P\right) \left( w_{s}\right) }\{ w_{s}\} |<q_{f}\} \), be the set of firms worker \(w_{t+1}\) is acceptable to and that have vacant positions. Define \(\mu ^{AS}\left( P\right) \left( w_{t+1}\right) =Ch_{w_{t+1}}\left( A_{t+1}\left( P\right) \right) \). For every \(f\in F\), let \(\mu ^{AS}\left( f\right) =\bigcup _{f\in \mu ^{AS}\left( w\right) }\left\{ w\right\} \). First, we prove that matching \(\mu ^{AS}\left( P\right) \), the outcome of an Adjusted Serial Dictatorship, is the unique stable matching of market \(\left( F,W,P\right) \).
Proposition 1
Let \(P_{v}\) be responsive for all \(v\in V\) and let \(P_{F}\) be acyclical. Matching \(\mu ^{AS}\left( P\right) \) is the unique stable matching of market \(\left( F,W,P\right) \).
In particular, Proposition 1 implies that all orders that define an Adjusted Serial Dictatorship generate the same stable matching.
Next, we prove our main result: no coalition of agents can benefit from preference manipulation if the worker-optimal stable mechanism \(\mu ^{W}\left( P\right) \) is used, when \(P_{F}\) is acyclical. Let \({\mathcal {D}}_{A}\) be the domain of preference profiles P such that \(P_{F}\) is acyclical. Formally, \( {\mathcal {D}}_{A} = \left\{ \left( P_{F}, P_{W} \right) \in {\mathcal {P}}_{V}: P_{F} \text{ is } \text{ acyclical } \right\} \).
Theorem 1
The worker-optimal stable mechanism \(\mu ^{W}\) is group strategy-proof on \({\mathcal {D}}_{A} \).
Even if the profile of firms’ preferences is acyclical, we do not restrict their message space to acyclical profiles.Footnote 7 Instead, firms can submit arbitrary responsive preference profiles (see the definitions of strategy-proofness and of group strategy-proofness in Sect. 2).
The proof of Theorem 1 is based on the characterization of the worker-optimal stable matching provided in Proposition 1 and the observation that the outcome of any deviation can be reached through a deviation that preserves the acyclicity of the preferences of the firms.
Ergin’s acyclicity (see Ergin 2002) prevents the coalitional deviation of workers in many-to-one matching markets. Essential homogeneity (see Kojima 2013) prevents individual manipulation of the workers. Acyclicity simultaneously prevents individual and coalitional deviations of both firms and workers.
From Theorem 1, follows that the worker-optimal stable mechanism is Pareto optimal if firms’ preferences are acyclical.
Corollary 1
The worker-optimal stable mechanism \(\mu ^{W}\) is Pareto optimal, Pareto optimal for workers and Pareto optimal for firms on \({\mathcal {D}}_{A}\).
Next, we study whether it is possible to weaken the acyclicity requirement and find a mechanism that is stable and strategy-proof for all agents. First we show that without acyclicity, the worker-optimal stable mechanism is not strategy-proof for firms.
Lemma 1
Let \({\mathcal {D}} \subseteq {\mathcal {P}}_{V}\) and assume \({\mathcal {D}} \nsubseteq {\mathcal {D}}_{A}\). Then, the worker-optimal stable mechanism is not strategy-proof for firms on \({\mathcal {D}}\).
The intuition behind Lemma 1 is that, if the preferences of the firms are not acyclic, there exists a profile of preferences for workers such that the resulting market has two stable matchings. In this case, any firm f which strictly prefers the firm-optimal stable matching to the worker-optimal stable matching can successfully manipulate the worker-optimal stable mechanism.
Thus, a singleton core is necessary for the existence of a stable and strategy-proof mechanism. However, having a unique stable matching is not sufficient for the existence of a stable and strategy-proof mechanism. In the next example, we provide a market with a singleton core where an agent can successfully manipulate the unique stable matching because there is a cycle in the preferences of the firms.
Example 1
Let us assume \(F=\left\{ f_{1},f_{2},f_{3}\right\} \) and \(W=\left\{ w_{1},w_{2},w_{3}\right\} \). Consider responsive preferences for all agents. Let \(A\left( f_{1}\right) =\left\{ w_{1},w_{3}\right\} \), \(A\left( f_{2}\right) =\left\{ w_{1},w_{2}\right\} \), and \(A\left( f_{3}\right) =\left\{ w_{2},w_{3}\right\} \). Let \(q_{f}=1\) for all \(f\in F\). Let \(P_{f_{1}}:\left\{ w_{1}\right\} ,\left\{ w_{3}\right\} \), \(P_{f_{2}}:\left\{ w_{2}\right\} ,\left\{ w_{1}\right\} \), and \(P_{f_{3}}:\left\{ w_{3}\right\} ,\left\{ w_{2}\right\} \). Notice \(w_{1}P_{f_{1}}w_{3}P_{f_{3}}w_{2}P_{f_{2}}w_{1}\). Let \(A\left( w_{1}\right) =\left\{ f_{1},f_{2}\right\} \), \(A\left( w_{2}\right) =\left\{ f_{2},f_{3}\right\} \), and \(A\left( w_{3}\right) =\left\{ f_{1},f_{3}\right\} \). Let \(q_{w_{1}}=2\) and \(q_{w_{2}}=q_{w_{3}}=1\). Let \(P_{w_{1}}:\left\{ f_{1},f_{2}\right\} ,\left\{ f_{2}\right\} ,\left\{ f_{1}\right\} \), \(P_{w_{2}}:\left\{ f_{3}\right\} ,\left\{ f_{2}\right\} \) and \(P_{w_{3}}:\left\{ f_{1}\right\} ,\left\{ f_{3}\right\} \). There exists a unique stable matching \(\mu \) where \(\mu \left( f_{i}\right) =\left\{ w_{i}\right\} \) for \(i=1,2,3\). If any stable mechanism is employed and worker \(w_{1}\) reports preferences \(P'_{w_{1}}:\left\{ f_{2}\right\} \), she obtains a position at \(f_{2}\), which she strictly prefers to \(f_{1}\).
The intuition provided by Example 1 and Lemma 1 leads us to prove that acyclicity is the minimal condition guaranteeing the existence of a stable group strategy-proof mechanism.
Proposition 2
Let \({\mathcal {D}} \subseteq {\mathcal {P}}_{V}\) and assume \({\mathcal {D}} \nsubseteq {\mathcal {D}}_{A}\). Then, no stable mechanism is strategy-proof on \({\mathcal {D}}\).
In conclusion, we can integrate the main findings of the section in the following theorem.
Theorem 2
Let \({\mathcal {D}}\subseteq {\mathcal {P}}_{V}\). The following statements are equivalent:
-
1.
There exists a stable and strategy-proof mechanism on \({\mathcal {D}}\).
-
2.
There exists a stable and group strategy-proof mechanism on \({\mathcal {D}}\).
-
3.
\({\mathcal {D}} \subseteq {\mathcal {D}}_{A}\).
Thus \({\mathcal {D}}_{A}\) is the maximal domain of preferences which guarantees the existence of a stable, strategy-proof and group strategy-proof stable mechanism.
3.1 Course allocation
Next, we apply our results to the case where firms are objects to be consumed. Thus, their preferences are to be intended as priorities. This problem is usually called the course allocation problem. It is a one-sided multi-unit assignment problem under priorities, in which only workers are strategic. Formally, a course allocation problem can be identified with a matching market \(\left( F,W,P_{F},P_{W}\right) \), where F is identified with the set of courses to be distributed among the workers W, who now play the role of students. For every \(f\in F\), let \(\succ _{f}\) be the restriction of \(P_{f}\) to individual students. Formally, for every \(w,w'\in W\cup \left\{ \emptyset \right\} \), let \(w\succ _{f}w'\) if and only if \(wP_{f}w'\). The set of stable matchings depends only on the preferences of the workers, on the preferences of the firms over individual workers, and on the capacities of the firms. We denote a course allocation problem as by \(\left( F,W,\succ _{F},P_{W},q\right) \), where \(\succ _{F}=\left( \succ _{f}\right) _{f\in F}\) and \(q=\left( q_{f}\right) _{f\in F}\). We call \(\left( \succ _{F},q\right) \) a priority structure.
The priority structure \(\left( \succ _{F},q\right) \) satisfies essential homogeneityFootnote 8 if there are no \(f_{0},f_{1},\ldots ,f_{T}\in F,\) \(w_{0},w_{1},\ldots ,w_{T}\in W\) and \(W_{0},W_{1}\ldots ,W_{T}\subseteq W{\setminus }\left\{ w_{0},w_{1},\ldots ,w_{T}\right\} \) such that:
-
1.
\(w_{T}\succ _{f_{T}}w_{T-1}\succ _{f_{T-1}}\ldots \succ _{f_{2}}w_{1}\succ _{f_{1}}w_{0}\succ _{f_{0}}w_{T}\);
-
2.
for every t, \(0\le t\le T\), \(w_{t}\in A\left( f_{t+1}\right) \cap A\left( f_{t},\right) \), where \(f_{T+1}=f_{0}\).
-
3.
for every t, \(0\le t\le T\), \(\left| W_{t+1}\right| =q_{t+1}-1\) and \(w\succ _{f_{t+1}}w_{t}\) for each \(w\in W_{t+1}\) where \(f_{T+1}=f_{0}\).
From the proof of Theorem 1 in Kojima (2013), it follows that essential homogeneity is equivalent to the existence of a stable mechanism that is strategy-proof for students.Footnote 9 Essential homogeneity is weaker than acyclicity but it does not guarantee that the set of stable matchings is a singleton (see Romero-Medina and Triossi 2013b), nor the existence of a mechanism that is stable and strategy-proof for the agents on the two sides of the market.
Acyclicity is a sufficient but not necessary condition for the existence of a stable mechanism that is strategy-proof for workers when capacities are given. However, in several practical course allocation problems, capacities are decided year by year depending on infrastructure and expected demand. In such situations, only \(\succ _{F}\) can be assumed as given, and the objective of the designer is to devise a strategy-proof mechanism that works for any capacity vector \(q=\left( q_{f}\right) _{f\in F}\). We next prove that this is possible only if \(\succ _{F}\) is acyclical.
Lemma 2
Assume that \(\succ _{F}\) has a cycle. Then, there exists a vector of capacities q such that no stable mechanism is strategy-proof for workers, when the priority structure is \(\left( \succ _{F},q\right) \).
Thus acyclicity is a minimal condition on priorities that guarantees strategy-proofness for any vector of capacity q. The result suggests that, if a revelation mechanism is to be used, the use of acyclical priorities is the only choice that guarantees stability and truthful behavior by students.
Proposition 3
The following statements are equivalent in the domain of responsive preferences for workers:
-
1.
There exists a stable mechanism that is strategy-proof for workers for every \(q=\left( q_{f}\right) _{f\in F}\).
-
2.
There exists a stable mechanism that is group strategy-proof for workers for every \(q=\left( q_{f}\right) _{f\in F}\).
-
3.
\(\succ _{F}\) is acyclical.
4 Conclusions
In this paper, we prove that the worker-optimal stable mechanism is group strategy-proof and Pareto optimal in many-to-many matching markets if the preferences of the firms are acyclical. In this case, the unique stable matching can be obtained through an Adjusted Serial Dictatorship.
The restriction to acyclical priorities is particularly appropriate in situations where preferences reflect an underlying merit-based ranking. In these cases, a serial dictatorship is an appealing implementation mechanism (see also Ehlers and Klaus 2003).
Acyclicity is the minimal condition guaranteeing the existence of a strategy-proof stable mechanism in many-to-many markets. This result can be interpreted as negative because acyclicity is a strong restriction. This interpretation suggests that whenever the restriction of acyclical preferences or priorities is not deemed reasonable or appropriate, the designer should explore alternative options. A first alternative is weakening the equilibrium requirements. A second possibility is to weaken the stability requirement on the mechanism.
Notes
Romero-Medina and Triossi (2020) show that the equivalence between strategy-proofness and group strategy-proofness also holds in the multi-unit assignment problem.
The two domains are unrelated.
For every set S, the symbol \(\left| S\right| \) denotes the cardinality of S.
Sotomayor (1999) studies the relationship between different stability concepts in many-to-many matching markets. In particular, she points out that the core and the set of stable matchings may have an empty intersection so that the set of setwise-stable matchings may be empty under separable preferences (which is a stronger requirement than responsive preferences). See also Sotomayor (2004).
Notice that, formally, we are comparing singletons: for example, as previously defined, \(wP_{f}w_{1}\) means \(\left\{ w\right\} P_{f}\left\{ w_{1}\right\} \).
This would be inconsistent, since the set of acyclical preference profiles is not a Cartesian product. We thank an associated editor for the observation.
This definition adapts that proposed in Kojima (2013), accounting for situations where courses have different eligibility requirements.
Romero-Medina and Triossi (2020) prove that essential homogeneity is also equivalent to the existence of a stable mechanism that is group strategy-proof for students.
In particular, for all \(v\in V\) and all \(v'\in \mu ^{W}(P'_{V'},P_{V{\setminus } V'})\left( v\right) \), \(v'P_{v}\emptyset \).
The proof of the existence of such \(P''_{f}\) is available upon request.
References
Abdulkadiroğlu A, Sönmez T (2003) School choice: a mechanism design approach. Am Econ Rev 93:729–747. https://doi.org/10.1257/000282803322157061
Abdulkadiroğlu A, Pathak PA, Roth AE (2005) The New York City high school match. Am Econ Rev 95:364–367. https://doi.org/10.1257/aer.20151425
Abdulkadiroğlu A, Sönmez T (2013) Matching markets: theory and practice. In: Acemoglu A, Arellano M, Deckel E (eds) Advances in economics and econometrics, tenth world congress, vol II. Cambridge University Press, Cambridge, pp 3–47
Alkan A (1999) On the properties of stable many-to-many matchings under responsive preferences. In: Alkan A, Aliprantis CD, Yannelis NC (eds) Current trends in economics: theory and applications. Studies in economic theory, vol 8. Springer, Berlin, Heidelberg, pp 29–39
Balinski M, Sönmez T (1999) A tale of two mechanisms: student placement. J Econ Theory 84:73–94. https://doi.org/10.1006/jeth.1998.2469
Barberá S, Berga D, Moreno B (2016) Group strategy-proofness in private good economies. Am Econ Rev 106:1073–1099. https://doi.org/10.1257/aer.20141727
Budish E (2011) The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. J Polit Econ 119:1061–1103. https://doi.org/10.1086/664613
Demange G (1987) Nonmanipulable cores. Econometrica 55:1057–1074. https://doi.org/10.2307/1911261
Demange G, Gale D, Sotomayor M (1987) A further note on the stable matching problem. Discrete Appl Math 16:217–222. https://doi.org/10.1016/0166-218X(87)90059-X
Ehlers L, Klaus B (2003) Coalitional strategy-proof and resource-monotonic solutions for multiple assignment problems. Soc Choice Welf 21:265–280. https://doi.org/10.1007/s00355-003-0259-1
Ergin HI (2002) Efficient resource allocation on the basis of priorities. Econometrica 70:2489–2497. https://doi.org/10.1111/j.1468-0262.2002.00447.x
Hatfield JW, Kojima F (2009) Group incentive compatibility for matching with contracts. Games Econ Behav 67:745–749. https://doi.org/10.1016/j.geb.2009.01.007
Jiao Z, Tian G (2017) The blocking lemma and strategy-proofness in many-to-many matchings. Games Econ Behav 102:44–55. https://doi.org/10.1016/j.geb.2016.10.015
Kesten O (2012) On two kinds of manipulation for school choice problems. Econ Theory 51:677–693. https://doi.org/10.1007/s00199-011-0618-6
Kojima F (2013) Efficient resource allocation under multi-unit demand. Games Econ Behav 82:1–14. https://doi.org/10.1016/j.geb.2013.06.005
Pycia M (2012) Stability and preference alignment in matching and coalition formation. Econometrica 80(1):323–362. https://doi.org/10.3982/ECTA7143
Romero-Medina A, Triossi M (2013a) Games with capacity manipulation, incentives and Nash equilibria. Soc Choice Welf 41:701–720. https://doi.org/10.1007/s00355-012-0703-1
Romero-Medina A, Triossi M (2013b) Acyclicity and singleton cores in matching markets. Econ Lett 118:237–239. https://doi.org/10.1016/j.econlet.2012.10.032
Romero-Medina A, Triossi M (2020) Strategy-proof and group strategy-proof stable mechanisms: an equivalence. Int J Econ Theory 16:349–354. https://doi.org/10.1111/ijet.12214
Roth AE (1985) The college admissions problem is not equivalent to the marriage problem. J Econ Theory 36:277–288. https://doi.org/10.1016/0022-0531(85)90106-1
Roth AE (1991) A natural experiment in the organization of entry-level labor markets: regional markets for new physicians and surgeons in the United Kingdom. Am Econ Rev 81:415–440
Roth AE (2008) What have we learned from market design? Econ J 118:285–310. https://doi.org/10.1111/j.1468-0297.2007.02121.x
Roth AE, Sotomayor M (1990) Two-sided matching: a study in game-theoretic modeling and analysis. Cambridge University Press, Cambridge
Schummer J, Abizada A (2017) Incentives in landing slot problems. J Econ Theory 170:29–55. https://doi.org/10.1016/j.jet.2017.04.003
Schummer J, Vohra RV (2013) Assignment of arrival slots. Am Econ J Microecon 5:164–185. https://doi.org/10.1257/mic.5.2.164
Sönmez T (1997) Manipulation via capacities in two-sided matching markets. J Econ Theory 77:197–204. https://doi.org/10.1006/jeth.1997.2316
Sönmez T (1999) Strategy-proofness and essentially single-valued cores. Econometrica 67:677–689. https://doi.org/10.1111/1468-0262.00044
Sönmez T, Ünver U (2010) Course bidding at business schools. Int Econ Rev 51:99–123. https://doi.org/10.1111/j.1468-2354.2009.00572.x
Sotomayor M (1999) Three remarks on the many-to-many stable matching problem. Math Soc Sci 38:55–70. https://doi.org/10.1016/S0165-4896(98)00048-1
Sotomayor M (2004) Implementation in the many-to-many matching market. Games Econ Behav 46:199–212. https://doi.org/10.1016/S0899-8256(03)00047-2
Funding
Open access funding provided by Università Ca’ Foscari Venezia within the CRUI-CARE Agreement.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
We thank the associate editor and the two reviewers for their careful reading of our manuscript and their many insightful comments and suggestions. Both authors acknowledge financial support from Ministerio Economía y Competitividad (Spain) under project ECO2017-87769-P and from Fondecyt under project No. 1151230. Romero-Medina acknowledges the financial support from Ministerio Economía y Competitividad (Spain) MDM 2014-0431, and Comunidad de Madrid H2019/HUM-5891. Triossi acknowledges the financial support from the Institute for Research in Market Imperfections and Public Policy, ICM IS130002, Ministerio de Economía, Fomento y Turismo (Chile), and from Ca’ Foscari University of Venice under project MAN.INS_TRIOSSI.
Appendix
Appendix
Proof of Proposition 1
First, we show that any matching \(\mu ^{AS}\) obtained from an Adjusted Serial Dictatorship is stable. The definition of \(\mu ^{AS}=\mu ^{AS}(P)\) implies that it is individually rational. Next, we prove by contradiction that there is no pair blocking \(\mu ^{AS}\). Assume that there exists a pair \(\left( f,w_{s}\right) \in F\times W\) blocking \(\mu ^{AS}\). We have \(\mu ^{AS}\left( w_{s}\right) =Ch_{w_{s}}\left( A_{s}\left( P\right) \right) \). First, assume that \(\left| \mu ^{AS}\left( f\right) \right| <q_{f}\). Then, \(f\in A_{s}\left( P\right) \), yielding a contradiction. Second, consider the case in which \(\left| \mu ^{AS}\left( f\right) \right| =q_{f}\). Because \(\left( f,w_{s}\right) \) blocks \(\mu \), \(w_{s}P_{f}w'\) for some \(w'\in \mu ^{AS}\left( f\right) \). From the definition of the sequence \(w_{1},w_{2},\ldots ,w_{\left| W\right| }\), it follows that \(w'=w_{t}\) for some \(t>s\). Thus, \(f\in A_{s}\left( P\right) \), yielding a contradiction.
We prove by contradiction that there is exactly one stable matching. Assume that \(\nu \ne \mu ^{AS}\) is a stable matching. Let s be the minimum of the indexes t such that \(\nu \left( w_{t}\right) \ne \mu ^{AS}\left( w_{t}\right) \). Such an s exists because W is finite. Since \(\nu \) is individually rational and \(\mu ^{AS}\left( w_{t}\right) =\nu \left( w_{t}\right) \) for all \(t<s\), \(\nu \left( w_{s}\right) \subseteq \) \(\{ f:w_{s}\in A(f),|\bigcup _{t<s,f\in \nu \left( w_{t}\right) }\{ w_{t}\}|<q_{f}\} =\)\(\{ f:w_{s}\in A\left( f\right) ,|\bigcup _{t<s,f\in \mu ^{AS}\left( w_{t}\right) }\{w_{t}\}|<q_{f}\} =A_{s}\left( P\right) \). Since \(\nu \left( w_{s}\right) \subseteq A_{s}\left( P\right) \), \(\mu ^{AS}\left( w_{s}\right) =Ch_{w_{s}}\left( A_{s}\left( P\right) \right) \) and \(\mu ^{AS}\left( w_{s}\right) \ne \nu \left( w_{s}\right) \), then \(\mu ^{AS}\left( w_{s}\right) P_{w_{s}}\nu \left( w_{s}\right) \). There are two possibilities.
-
(a)
\(\mu ^{AS}\left( w_{s}\right) {\setminus }\nu \left( w_{s}\right) \ne \emptyset \). From the acyclicity of \(P_{F}\), the definition of an Adjusted Serial Dictatorship and the minimality of s follows that for all \(f\in \mu ^{AS}\left( w_{s}\right) {\setminus }\nu \left( w_{s}\right) \) and each \(w\in {\nu \left( f\right) {\setminus }\mu ^{AS}\left( f\right) }\), \(w_{s}P_{f}w\). Assume that \(\left| \nu \left( w_{s}\right) \right| <q_{w_{s}}\) and let \(f\in \mu ^{AS}\left( w_{s}\right) {\setminus }\nu \left( w_{s}\right) \). If \(\left| \nu \left( f\right) \right| <q_{f}\), then \(\left( f,w_{s}\right) \) blocks \(\nu \), which yields a contradiction. If \(\left| \nu \left( f\right) \right| =q_{f}\), there exists \(w\in {\nu \left( f\right) {\setminus }\mu ^{AS}\left( f\right) }\). As observed, \(w_{s}P_{f}w\), then \(\left( f,w_{s}\right) \) blocks \(\nu \), which yields a contradiction. Assume that \(\left| \nu \left( w_{s}\right) \right| =q_{w_{s}}\). Then, there exists \(f\in \mu ^{AS}\left( w_{s}\right) {\setminus }\nu \left( w_{s}\right) \) and \(f'\in {\nu \left( w_{s}\right) {\setminus }\mu ^{AS}\left( w_{s}\right) }\), such that \(fP_{w_{s}}f'\). If \(\left| \nu \left( f\right) \right| <q_{f}\), then \(\left( f,w_{s}\right) \) blocks \(\nu \), which yields a contradiction. If \(\left| \nu \left( f\right) \right| =q_{f}\), there exists \(w\in {\nu \left( f\right) {\setminus }\mu ^{AS}\left( f\right) }\). As observed above, \(w_{s}P_{f}w\), then \(\left( f,w_{s}\right) \) blocks \(\nu \), which yields a contradiction.
-
(b)
\(\mu ^{AS}\left( w_{s}\right) \subsetneqq \nu \left( w_{s}\right) \). We have \(\left| \mu ^{AS}\left( w_{s}\right) \right| <\left| \nu \left( w_{s}\right) \right| \le q_{w_{s}}\), because \(\nu \) is individually rational. Let \(f\in \nu \left( w_{s}\right) {\setminus }\mu ^{AS}\left( w_{s}\right) \). If \(\left| \nu \left( f\right) \right| <q_{f}\), then \(\left( f,w_{s}\right) \) blocks \(\nu \), which yields a contradiction. Let \(\left| \nu \left( f\right) \right| =q_{f}\). Then, there exists \(w\in {\nu \left( f\right) {\setminus }\mu ^{AS}\left( f\right) }\). From the acyclicity of \(P_{F}\), the definition of an Adjusted Serial Dictatorship, and the minimality of s follows that \(w_{s}P_{f}w\), then \(\left( f,w_{s}\right) \) blocks \(\nu \), which yields a contradiction.\(\square \)
Proof of Theorem 1
We prove the claim by contradiction. Let \(P_{F}\) be acyclical and assume that there exists a nonempty set of agents \(V'\subseteq V\), a responsive profile of preferences \(P=\left( P_{v}\right) _{v\in V}\), and a responsive profile \(P'_{V'}=\left( P'_{v}\right) _{v\in V'}\) such that \(\mu ^{W}(P'_{V'},P_{V{\setminus } V'})\left( v\right) R_{v}\mu ^{W}(P)\left( v\right) \) for every \(v\in V'\) and \(\mu ^{W}(P'_{V'},P_{V{\setminus } V'})\left( v'\right) P_{v'}\mu ^{W}(P)\left( v'\right) \) for some \(v'\in V'\). Then, \(\mu ^{W}(P'_{V'},P_{V{\setminus } V'})\) is individually rational for all agents.Footnote 10
The strategy of the proof is as follows. In (a) we show that there exists a profile of acyclical preferences that guarantees the same outcome as \(\left( P'_{V'},P_{V{\setminus } V'}\right) \) to all members of coalition \(V'\). In (b) we show that any deviating coalition includes at least one firm. In (c) we prove that at least one firm in \(V'\) strictly benefits from the deviation. In (d) we prove that there is no loss of generality in assuming that a coalition of firms is deviating. Finally, in (e) we prove that the argument leads to a contradiction.
-
(a)
Let \(f\in F\cap V'\). Consider the following strict order, \({\hat{P}}_{f}\) on \(W\cup \left\{ \emptyset \right\} \). For all \(w,w'\in W\), \(w{\hat{P}}_{f}\emptyset \) \(\iff \) \(w\in \mu ^{W}(P'_{V'},P_{V{\setminus } V'})\). If \(w\in \mu ^{W}(P'_{V'},P_{V{\setminus } V'})\) and \(w'\notin \mu ^{W}(P'_{V'},P_{V{\setminus } V'})\), then \(w{\hat{P}}_{f}w'\). If \(w,w'\in \mu ^{W}\left( P'_{V'},P_{V{\setminus } V'}\right) \left( f\right) \), then \(w{\hat{P}}_{f}w' \iff wP_{f}w'\). If \(w,w'\notin \mu ^{W}\left( P'_{V'},P_{V{\setminus } V'}\right) \left( f\right) \), then \(w{\hat{P}}_{f}w' \iff wP_{f}w'\). Let \(P''_{f}\) be responsive preferences with capacity \(\left| \mu ^{W}(P'_{V'},P_{V{\setminus } V'}\left( f\right) \right| \) on \(2^{W}\) such that, for all \(w,w'\in W\), \(wP''_{f}w'\) \(\iff \) \(w{\hat{P}}_{f}w'\) and \(wP''_{f}\emptyset \) \(\iff \) \(w{\hat{P}}_{f}\emptyset \).Footnote 11 For every \(w\in W\cap V'\), define \({\hat{P}}_{w}\) and \(P''_{w}\) in the same way.
Notice that for all \(w,w'\in A\left( f,P''_{f}\right) \subseteq A\left( f,P_{f} \right) \), \(wP''_{f}w' \iff wP_{f}w'\). It follows that any cycle in \(P''_{f}\) would be a cycle in \(P_{f}\). Thus, \(P''_{f}\) is acyclical. Let \(w_{1},w_{2},\ldots ,w_{\left| W\right| }\) be an order used to generate \(\mu ^{AS}\left( P\right) =\mu ^{W}\left( P\right) \) as an Adjusted Serial Dictatorship. Then, \(w_{1},w_{2},\ldots ,w_{\left| W\right| }\) can be used to generate an Adjusted Serial Dictatorship leading to \(\mu ^{AS}\left( P''_{V'},P_{V{\setminus } V'}\right) \)=\(\mu ^{W}\left( P''_{V'},P_{V{\setminus } V'}\right) \). We show that the deviation \(P''_{V'}\) is profitable for the members of \(V'\), which is \(\mu ^{W}\left( P''_{V'},P_{V{\setminus } V'}\right) \left( v\right) R_{v}\mu ^{W}\left( P\right) \left( v\right) \) for every \(v\in V'\) and \(\mu ^{W}\left( P''_{V'},P_{V{\setminus } V'}\right) \left( v'\right) P_{v'}\mu ^{W}\left( P\right) \left( v'\right) \) for some \(v'\in V'\). More precisely, we prove \(\mu ^{W}\left( P''_{V'},P_{V{\setminus } V'}\right) =\mu ^{W}\left( P'_{V'},P_{V{\setminus } V'}\right) \), which implies the claim. Matching \(\mu ^{W}\left( P'_{V'},P_{V{\setminus } V'}\right) \) is stable in market \(\left( F,W, \left( P''_{V'},P_{V{\setminus } V'}\right) \right) \). Since \(\left( P''_{F'},P_{F{\setminus } V'}\right) \) is acyclical, by Proposition 1, market \(\left( F,W, \left( P''_{V'},P_{V{\setminus } V'}\right) \right) \) has a unique stable matching, thus \(\mu ^{W}\left( P'_{V'},P_{V{\setminus } V'}\right) =\mu ^{W}\left( P''_{V'},P_{V{\setminus } V'}\right) \). It follows that the deviation \(P''_{V'}\) is profitable for the members of \(V'\).
-
(b)
From now on, let \(\mu =\mu ^{AS}\left( P\right) =\mu ^{W}\left( P\right) \) and let \(\rho =\mu ^{AS}\left( P''_{V'},P_{V{\setminus } V'}\right) =\mu ^{W}\left( P''_{V'},P_{V{\setminus } V'}\right) \). We prove by contradiction that any deviating coalition must include at least a firm, which is \(V'\cap F\ne \emptyset \). Assume that \(V'\subseteq W\), and let s be the minimum of the indexes t such that \(\rho \left( w_{t}\right) \ne \mu \left( w_{t}\right) \). Since all workers with an index lower than s are matched to the same firms under \(\mu \) and under \(\rho \) and \(V'\subseteq W\), we have \(A_{s}\left( P''_{V'},P_{V{\setminus } V'}\right) =A_{s}\left( P\right) \). If \(w_{s}\in V'\), then \(\mu \left( w_{s}\right) P_{w_{s}}\rho \left( w_{s}\right) \), which yields a contradiction. Otherwise, if \(w_{s}\in W{\setminus } V'\), \(\rho \left( w_{s}\right) =\mu ^{AS}\left( P''_{V'},P_{V{\setminus } V'}\right) \left( w_{s}\right) =Ch\left( A_{s}\left( P''_{V'},P_{V{\setminus } V'}\right) ,P_{w_{s}}\right) \left( w_{s}\right) \). Since \(A_{s}\left( P''_{V'},P_{V{\setminus } V'}\right) =A_{s}\left( P\right) \), then \(\rho \left( w_{s}\right) =Ch\left( A_{s}\left( P\right) ,P_{w_{s}}\right) =\mu \left( w_{s}\right) \), which also yields a contradiction, because, by hypothesis \(\rho \left( w_{s}\right) \ne \mu \left( w_{s}\right) \).
-
(c)
From (b), \(V'\cap F\ne \emptyset \). We prove that at least one firm \(f\in V'\cap F\) strictly benefits from the deviation, which is we prove that there exists \(f\in F'\cap V\) such that \(\rho \left( f\right) P_{f}\mu \left( f\right) \). By contradiction assume that \(\rho \left( f\right) =\mu \left( f\right) \) for all \(f\in V'\cap F\). Let s be the minimum of the indexes t such that \(\rho \left( w_{t}\right) \ne \mu \left( w_{t}\right) \). Since all workers with an index lower than s are matched to the same firms under \(\mu \) and under \(\rho \), we have \(A_{s}\left( P''_{V'},P_{V{\setminus } V'}\right) \subseteq A_{s}\left( P\right) \). Thus, if \(f\in \mu \left( w_{s}\right) {\setminus } V'\), \(f\in A_{s}\left( P''_{V'},P_{V{\setminus } V'}\right) \). Finally, since \(\rho \left( f\right) =\mu \left( f\right) \) for all \(f\in V'\cap F\), if \(f\in \mu \left( w_{s}\right) \cap V'\), \(f\in A_{s}\left( P''_{V'},P_{V{\setminus } V'}\right) \). It follows that \(\mu \left( w_{s}\right) \subseteq A_{s}\left( P''_{V'},P_{V{\setminus } V'}\right) \subseteq A_{s}\left( P\right) \). Let \(w_{s}\in V'\cap W\). By definition \(\rho (w_{s})=\mu ^{AS}\left( P''_{V'},P_{V{\setminus } V'}\right) \left( w_{s}\right) =Ch_{w_{s}}\left( A_{s}\left( P''_{V'},P_{V{\setminus } V'}\right) ,P''_{w_{s}}\right) \). Since \(A_{s}\left( P''_{V'},P_{V{\setminus } V'}\right) \subseteq A_{s}\left( P\right) \), \(\mu \left( w_{s}\right) =\) \(Ch_{w_{s}}\left( A_{s}\left( P\right) ,P_{w_{s}}\right) R_{w_{s}}Ch_{w_{s}}\left( A_{s}\left( P''_{V'},P_{V{\setminus } V'}\right) ,P{}_{w_{s}}\right) \). Also \(Ch_{w_{s}}\left( A_{s}\left( P''_{V'},P_{V{\setminus } V'}\right) ,P{}_{w_{s}}\right) R_{w_{s}}Ch_{w_{s}}\left( A_{s}\left( P''_{V'},P_{V{\setminus } V'}\right) ,P''_{w_{s}}\right) =\rho \left( w_{s}\right) \), thus \(\mu \left( w_{s}\right) R_{s}\rho \left( w_{s}\right) \). Since \(w_{s}\in V'\), \(\rho \left( w_{s}\right) R_{w_{s}}\mu \left( w_{s}\right) \), thus \(\rho \left( w_{s}\right) =\mu \left( w_{s}\right) \) which yields a contradiction, because, by hypothesis \(\rho \left( w_{s}\right) \ne \mu \left( w_{s}\right) \). Now, let \(w_{s}\in W{\setminus } V'\). Since \(A_{s}\left( P''_{V'},P_{V{\setminus } V'}\right) \subseteq A_{s}\left( P\right) \) and \(\mu \left( w_{s}\right) =Ch_{w_{s}}\left( A_{s}\left( P\right) ,P_{w_{s}}\right) \), \(\mu \left( w_{s}\right) R_{w_{s}}Ch_{w_{s}}\left( A_{s}\left( P''_{V'},P_{V{\setminus } V'}\right) ,P{}_{w_{s}}\right) =\rho \left( w_{s}\right) \). Since \(\mu \left( w_{s}\right) \subseteq A_{s}\left( P''_{V'},P_{V{\setminus } V'}\right) \), also \(\rho \left( w_{s}\right) =Ch_{w_{s}}\left( A_{s}\left( P''_{V'},P_{V{\setminus } V'}\right) ,P{}_{w_{s}}\right) R_{w_{s}}Ch_{w_{s}}\left( \mu \left( w_{s}\right) \right) =\mu \left( w_{s}\right) \), because \(\mu \) is, in particular, individually rational. It follows \(\rho \left( w_{s}\right) =\mu \left( w_{s}\right) \), which yields a contradiction, because, by hypothesis \(\rho \left( w_{s}\right) \ne \mu \left( w_{s}\right) \).
-
(d)
From (b), \(V'\cap F\ne \emptyset \). We prove that there is no loss of generality in assuming that \(V'\subseteq F\). More precisely, we prove that \(\mu ^{W}\left( P''_{V'\cap F},P_{V{\setminus } V'\cap F}\right) \left( v\right) R_{v} \mu \left( v\right) \), for every \(v\in V'\cap F\) and \(\mu ^{W}\left( P''_{V'\cap F},P_{V{\setminus } V'\cap F}\right) \left( v'\right) P_{v'} \mu \left( v'\right) \) for some \(v'\in V'\cap F\). Thus, if coalition \(V'\) can manipulate \(\mu ^{W}\), coalition \(V'\cap F\ne \emptyset \) can manipulate \(\mu ^{W}\). Let \(\sigma =\mu ^{W}\left( P''_{V'\cap F},P_{V{\setminus } V'\cap F}\right) \). We prove \(\sigma =\rho \), which, from (a), implies the claim. We prove by contradiction that matching \(\sigma \) is stable in market \(M= \left( F,W,\left( P''_{V'},P_{V{\setminus } V'}\right) \right) \). Assume that \(\sigma \) is blocked by pair \(\left( f,w\right) \) in market M. The definition of \(P''_{V'}\) implies that \(\left( f,w\right) \) blocks in market \(N= \left( F,W,\left( P''_{V'\cap F},P_{V{\setminus } V'\cap F}\right) \right) \) as well, which yields a contradiction because \(\sigma =\mu ^{W}\left( P''_{V'\cap F},P_{V{\setminus } V'\cap F}\right) \). Next, observe that the preference profiles of the firms in markets M and N are \(\left( P''_{V'\cap F},P_{F{\setminus } V'}\right) \), which is acyclical. By Proposition 1, markets M and N have a unique stable matching. Since \(\sigma \) is stable in markets M and N, \(\sigma =\rho \). It follows that \(\sigma \left( v\right) R_{v} \mu \left( v\right) \), for each \(v\in V'\cap F\). From \(\left( c\right) \), there exists \(v'\in V'\cap F\) such that \(\sigma \left( v'\right) P_{v'} \mu \left( v'\right) \).
-
(e)
By (d), we can assume \(V'\subseteq F\). Matching \(\mu \) is stable in market M. Since \(\rho \) is the worker-optimal stable matching in market M, \(\mu \left( f\right) R_{f}\rho \left( f\right) \) for all \(f\in F\) (see Alkan 1999). Since \(P''_{V'}\) is a profitable coalitional deviation for the firms \(f\in V'\), \(\rho \left( f\right) R_{f}\mu \left( f\right) \) for all \(f\in V'\). Since preferences are strict \(\mu \left( f\right) =\rho \left( f\right) \) for all \(f\in V'\), in contradiction with the fact that at least one firm in \(V'\) strictly benefits from the deviation.
\(\square \)
Proof of Lemma 1
Assume \({\mathcal {D}} \nsubseteq {\mathcal {D}}_{A}\). Thus, there exists \(\left( P_{F},P_{W}\right) \in {\mathcal {D}}\) such that \(P_{F}\) has a cycle. Let \(f_{0},f_{1},\ldots ,f_{T}\), \(w_{0},w_{1},\ldots ,w_{T}\) be such that \(w_{i}P_{f_{i}}w_{i-1}P_{f_{i}} \emptyset \) for \(i=0,1,\ldots ,T\), where \(w_{-1}=w_{T}\). Set \(q_{w_{i}}=1\) and \(A\left( w_{i}\right) = \left\{ f_{i},f_{i+1} \right\} \) for \(i=0,1,\ldots ,T\) and \(f_{T+1}=f_{0}\). Set \(P_{w_{i}}:\left\{ f_{i+1}\right\} ,\left\{ f_{i}\right\} \) for \(i=0,1,\ldots ,T\). For all \(w\notin \left\{ w_{0},w_{1},\ldots ,w_{T}\right\} \), let \(P_{w}\) be such that \(A\left( w\right) =\emptyset \). Let \(\mu ^{W}\) be the worker-optimal stable mechanism. We have \(\mu ^{W}\left( P\right) \left( w_{i}\right) =\left\{ f_{i+1}\right\} \) for \(i=0,1,\ldots ,T-1\) and \(\mu ^{W}\left( w_{T}\right) =\left\{ f_{0}\right\} \). Then, \(P'_{f_{1}}=\left\{ w_{1}\right\} \) is a profitable deviation from the truth-telling strategy for \(f_{1}\). \(\square \)
Proof of Proposition 2
Assume \({\mathcal {D}} \nsubseteq {\mathcal {D}}_{A}\). Thus there exists \(\left( P_{F},P_{W}\right) \in {\mathcal {D}}\) such that \(P_{F}\) has a cycle. Let \(P_{W}\) be the profile of preferences defined in the proof of Lemma 1. By contradiction, assume that there exists a stable and strategy-proof mechanism, \(\varphi \). There are exactly two stable matchings, \(\mu ^{W}\left( P\right) \) and \(\mu ^{F}\left( P\right) \), where \(\mu ^{W}\left( P\right) \left( w_{i}\right) =\left\{ f_{i+1}\right\} \) for \(i=0,1,\ldots ,T\), where \(f_{T+1}=f_{0}\) and \(\mu ^{F}\left( P\right) \left( w_{i}\right) =\left\{ f_{i}\right\} \) for \(i=0,1,\ldots ,\)T. From the proof of Lemma 1, it follows that \(\varphi \left( P\right) =\mu ^{F}\left( P\right) \). In this case, \(P'_{w_{0}}=\left\{ f_{1}\right\} \) is a profitable deviation from the truth-telling strategy for \(w_{0}\). \(\square \)
Proof of Lemma 2
Let \(f_{0},f_{1},\ldots ,f_{T}\), \(w_{0},w_{1},\ldots ,w_{T}\) such that \(w_{i}\succ _{f_{i}}w_{i-1}\) \(i=0,1,\ldots ,T\), where \(w_{-1}=w_{T}\). Set \(q_{f}=1\) for all \(f\in F\). Set \(q_{w_{0}}=2\), \(q_{w_{i}}=1\) for \(i=1,2,\ldots ,T\), and \(A\left( w_{i}\right) = \left\{ f_{i},f_{i+1} \right\} \) for \(i=0,1,\ldots ,T\) and \(f_{T+1}=f_{0}\). Set \(P_{w_{0}}:\left\{ f_{1},f_{0}\right\} ,\left\{ f_{1}\right\} ,\left\{ f_{0}\right\} \), \(P_{w_{1}}:\left\{ f_{2}\right\} ,\left\{ f_{1}\right\} \), and set \(P_{w_{i}}:\left\{ f_{i+1}\right\} ,\left\{ f_{i}\right\} \) for \(i=1,2,\ldots ,T\). For all \(w\notin \left\{ w_{0},w_{1},\ldots ,w_{T}\right\} \), let \(P_{w}\) such that \(A\left( w\right) \subseteq F{\setminus }\left\{ f_{0},f_{1},\ldots ,f_{T}\right\} \). Let \(\varphi \) be a stable mechanism. We have \(\varphi \left( P,q\right) \left( f_{i}\right) =\left\{ w_{i}\right\} \) for \(i=0,1,\ldots ,T\). Let \(P'_{w_{0}}=\left\{ f_{1}\right\} \). Then, \(\left\{ f_{1}\right\} =\varphi \left( P'_{w_{0}},P{}_{-w_{0}},q\right) \left( w_{0}\right) P_{w_{0}}\left\{ f_{0}\right\} =\varphi \left( P\right) \left( w_{0}\right) \), which implies the claim. \(\square \)
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Romero-Medina, A., Triossi, M. Two-sided strategy-proofness in many-to-many matching markets. Int J Game Theory 50, 105–118 (2021). https://doi.org/10.1007/s00182-020-00741-1
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00182-020-00741-1