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 ij \(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 (FWP) 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 (FWP) 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 (FWP).

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. 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. 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. 1.

    There exists a stable and strategy-proof mechanism on \({\mathcal {D}}\).

  2. 2.

    There exists a stable and group strategy-proof mechanism on \({\mathcal {D}}\).

  3. 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. 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. 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. 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. 1.

    There exists a stable mechanism that is strategy-proof for workers for every \(q=\left( q_{f}\right) _{f\in F}\).

  2. 2.

    There exists a stable mechanism that is group strategy-proof for workers for every \(q=\left( q_{f}\right) _{f\in F}\).

  3. 3.

    \(\succ _{F}\) is acyclical.

The proof easily follows from Theorem 1 and Lemma 2.

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.