Keywords: matching mechanism; stability; fairness; equity; symmetry; group theory.

1 Introduction↩︎

In this paper we analyze issues about fairness for matching models with two sides. In these models there are two disjoint sets of agents and each agent on one side has preferences over the agents on the other side. Agents on different sides have to be matched taking into account these preferences. A wide range of allocation problems from diverse fields can be analyzed within such framework. Well-known examples include the college admissions market, the labour market for medical interns, auction markets and the living kidney donors market.

Our focus is, in particular, on the most basic example of matching models with two sides, the so called marriage model (Gale and Shapley, 1962), where agents on the two sides are interpreted as men and women. For simplicity, we adopt the terminology related to Gale and Shapley’s metaphor along the paper. We denote the two disjoint sets by \(W\) and \(M\) and refer to their elements as women and men, respectively; the set \(W \cup M\) is denoted by \(I\) and its elements are called individuals. We assume that the sizes of the two sets \(W\) and \(M\) are equal.¹ Moreover, the preference relation of each woman is modelled by a linear order on the set \(M\); analogously, the preference relation of each man is modelled by a linear order on the set \(W\). Since the two sets \(W\) and \(M\) are fixed, a marriage model is described by a profile of linear orders, one for each individual. Given a marriage model, we are interested to determine a matching, that is, an idempotent bijective function from \(I\) to \(I\) that associates every woman with a man and every man with a woman. Stability is a highly desirable property a matching may meet. A matching is stable if there is no blocking pair, namely, a woman and a man who both prefer each other to their current partners in the matching.

In their seminal paper, Gale and Shapley (1962) proved that every marriage model admits a stable matching and also described an algorithm that finds such a matching. The algorithm involves more rounds. In the first round, every woman makes a proposal to the man she prefers most; every man who receives proposals from different women chooses his most preferred woman and gets temporarily matched with her, while all the other women who proposed to him are rejected. In each subsequent round, each unmatched woman makes a proposal to her most-preferred man to whom she has not yet proposed (regardless of whether that man is already matched), and each man who receives some proposals gets matched to the woman he prefers most among the ones who proposed to him and the woman he has been already matched to, if any. In particular, if he has a provisional partner and he prefers another woman to her, he rejects the provisional partner who becomes unmatched again. This process is repeated until all women have been matched to a partner. The role of the two groups of individuals can be reversed with men proposing matches and women deciding whether to accept or reject each proposal. In general, the stable matchings produced by the two versions of the algorithm are different. Gale and Shapley also proved that the stable matching generated by the algorithm when women propose is optimal for all the women, in the sense that it associates each woman with the best partner she can have among all the stable matchings. For this reason, it is called woman-optimal stable matching. However, it is the worst stable matching for the other side of the market: indeed, it associates each man with the worst partner he can get among all the stable matchings.² Symmetrically, the man-optimal stable matching is the stable matching which results from the algorithm when the men propose: it is the best stable matching for men and the worst stable matching for women.

The purpose of matching theory is, however, more general than determining a set of matchings for a specific marriage model. In fact, its objective is to determine a method able to select a sensible set of matchings for any conceivable marriage model, namely a correspondence that associates a set of matchings with each preference profile. Such correspondence is called a matching mechanism. Hence, a matching mechanism operates as a centralized clearinghouse that collects the preferences of all market participants and provides a set of matchings; whether those matchings can be determined by using efficient algorithms is an important question for practical applications that has received considerable attention. Several properties may be imposed on a matching mechanism. First of all, a matching mechanism is required to be non-empty valued. Especially when used for practical applications, a matching mechanism should also be able to select a unique matching for each preference profile, that is, it should be resolute. Stability is a further desirable property for matching mechanisms, particularly from a practical point of view: a matching mechanism is stable if it selects a set of stable matchings for each preference profile. Among stable matching mechanisms, the two mechanisms \(GS_w\) and \(GS_m\), which associate with each preference profile the woman-optimal stable matching and the man-optimal stable matching respectively, are very popular and have been implemented in practice, for instance, in the National Resident Matching Program (NRMP) to match doctors to residency programs or fellowships and also in some school districts to match students to high schools (Roth, 1984, Abdulkadiroğlu and Sönmez, 2003). In terms of applications, there is evidence that stable matching mechanisms perform better than unstable ones in those situations where agents voluntarily accept the proposed matching; in fact, in many cases, matching mechanisms that are not stable had largely failed and been abandoned while the stable ones succeeded and survived (see, for example, Roth, 1991). However, when a matching is imposed to agents, stability loses its fundamental role and other properties involving equity and fairness appear more compelling. In fact, a matching mechanism is expected to be non-discriminatory towards agents, that is, some form of equity should be satisfied. The two mechanisms \(GS_w\) and \(GS_m\) clearly fail such objective because they favor one side of the market (women and men, respectively) over the other. This has motivated the design of alternative matching mechanisms able to select stable matchings other than the woman-optimal and the man-optimal stable matchings in order to reduce the conflict of interests between women and men, and to treat the two parts more fairly. We can mention, among others, the Sex-Equal matching mechanism (Gusfield and Irving, 1989 and Romero-Medina, 2001) and the Egalitarian Stable maching mechanism (Gusfield and Irving, 1989). All these mechanisms share a common approach: first, a measure is introduced to quantify the fairness of a matching; then, such measure is optimized (usually, minimized due to its interpretation) on the set of stable matchings. A recap of several of these matching mechanisms can be found in Cooper and Manlove (2020).

In this paper, we take a different approach to fairness based on the idea of an equal treatment of all individuals: a mechanism is fair if a change in the identities of the individuals results into the same change in the output.³ Given the bilateral nature of the model, equity may concern either just agents belonging to the same group (women or men) or the totality of individuals. Indeed, in many situations, it is natural to require that no woman should gain a systematic advantage over the other women on the basis of her identity and, symmetrically, no man should gain a systematic advantage on the other men on the basis of his identity. In other words, an equal-treatment of individuals should be guaranteed within each group. This property is called anonymity and has been considered in the literature on two-sided matchings (see, for instance, Sasaki and Toda, 1992, and Hałaburda, 2010). On the other hand, in other circumstances, it could be natural to impose a form of equity across the two sets of individuals by requiring that neither women nor men should have an advantage on the other group solely on the basis of their gender. A fairness notion of the latter kind has been firstly introduced in Masarani and Gokturk (1989) under the name of gender indifference: roughly speaking, it states that if we swap agents belonging to different sets in a specific way (that is, we rename women as men and men as women according to a given rule), this should result in a corresponding change of names in the matchings selected by the matching mechanism.⁴ A more general version of gender indifference has been provided by Ökzal-Sanver (2004) under the name of gender fairness. Gender fairness, which implies anonymity⁵, takes into account more general changes in the identities of individuals: women are renamed as men and men are renamed as women in any possible fashion.

In this paper we introduce a general notion of fairness for matching mechanisms that we call symmetry. Anonymity, gender indifference and gender fairness can be seen as special instances of this notion. In order to provide an intuition for the concept of symmetric mechanisms, we need to introduce some preliminary notions. First of all, we use permutations over the set \(I\) of individuals in order to model changes in the individual identities. In particular, we are interested in changes in the identities that are consistent with the presence of two different types of individuals in the market. Hence, we focus on permutations \(\varphi\) over \(I\) that keep the partition \(\{W,M\}\) of \(I\) fixed, that is, \(\{\varphi(W)\,, \varphi(M)\}= \{M,W\}\). These permutations form a subgroup \(G^*\) of the symmetric group \(\mathrm{Sym}(I)\) of all the permutations on \(I\). A permutation \(\varphi\) in \(G^*\) may refer to a change in the individuals’ identities either within the sets \(W\) and \(M\) or across the sets \(W\) and \(M\). In the former case, \(\varphi\) is such that \(\varphi(W)=W\) and \(\varphi(M)=M\); in the latter case, \(\varphi\) is such that \(\varphi(W)=M\) and \(\varphi(M)=W\). Every permutation in \(G^*\) also affects the preference relation associated with each individual. Suppose, for instance, that \(W=\{1,2,3\}\) and \(M=\{4,5,6\}\) and let \(\varphi\in G^*\) be the permutation that switches \(1\) and \(4\), \(2\) and \(5\), \(3\) and \(6\). If woman 1’s preferences on \(M\) are \([5,6,4]^T\)⁶, when individual identities are modified according to \(\varphi\), we get that man 4’s preferences on \(W\) are \([2,3,1]^T\). Given then a preference profile \(p\), namely a complete list of individual preferences, and a permutation \(\varphi\in G^*\), we can build the preference profile \(p^\varphi\) obtained by \(p\) by changing individuals’ identities according to \(\varphi\). Consider now a subset \(U\) of \(G^*\). We say that a matching mechanism \(F\) is \(U\)-symmetric if, for every preference profile \(p\) and every \(\varphi\in U\), the set of matchings associated with \(p^{\varphi}\) by \(F\) corresponds to the set of the matchings associated with \(p\) by \(F\), each of them modified according to \(\varphi\).

The definition of \(U\)-symmetry is very general and able to recover the notions of fairness that we have listed before. In fact, gender fairness coincides with the notion of \((G^*\setminus G)\)-symmetry which, in turn, agrees with \(G^*\)-symmetry, the strongest possible version of \(U\)-symmetry; anonymity is equivalent to \(G\)-symmetry, where \(G\) is the subgroup of \(G^*\) formed by all the permutations \(\varphi\) such that \(\varphi(W)=W\) and \(\varphi(M)=M\); gender indifference coincides with \(\{\varphi\}\)-symmetry, where \(\varphi\) is any idempotent element of \(G^*\setminus G\), that is, a matching. We remark that our concept of \(U\)-symmetry allows to model diverse levels of fairness depending on which subsets \(U\) of \(G^*\) are considered.

The matching mechanism that associates with any preference profile the set of all stable matchings is \(G^*\)-symmetric but it is far from being resolute. Moreover, as one may expect, the matching mechanisms \(GS_w\) and \(GS_m\) are resolute, \(G\)-symmetric (i.e. anonymous) but fail to be \(G^*\)-symmetric (i.e. gender fair). Both the Sex-Equal and the Egalitarian Stable matching mechanisms, introduced to reduce the conflict of interests between the two parts, are \(G^*\)-symmetric but not resolute.

The problem we are mainly concerned with in this paper is the existence of matching mechanisms that are resolute, satisfy some form of symmetry and possibly further optimality properties like, for instance, stability. For a model where the sizes of \(W\) and \(M\) are equal, the main results we get are listed below; in (D), (E) and (F), \(\varphi\) can be any matching.

• If the size of \(W\) is odd, then there exists a resolute and \(G^*\)-symmetric matching mechanism.

• If the size of \(W\) is even, then there exists no resolute and \(G^*\)-symmetric matching mechanism.

• There exists no resolute, \(G^*\)-symmetric and minimally optimal⁷ matching mechanism.

• If the size of \(W\) is 2, then there exists a resolute, \(\{\varphi\}\)-symmetric and stable matching mechanism.

• If the size of \(W\) is at least 3, then there exists no resolute, \(\{\varphi\}\)-symmetric and stable matching mechanism.

• There exists a resolute, \(\{\varphi\}\)-symmetric and weakly Pareto optimal⁸ matching mechanism.

• There exists no resolute, \(G^*\)-symmetric and stable matching mechanism.

Theorem (G) is an immediate consequence of Theorem (C) and, when the size of \(W\) is at least 3, of Theorem (E). All the aforementioned results are proved by exploiting notions and techniques from group theory. An algebraic approach based on symmetric groups and groups actions has been already successfully used in social choice literature (Eğecioğlu, 2009, Bubboloni and Gori, 2014, 2015, 2016, 2021, Doğan and Giritligil, 2015). To the best of our knowledge, this is the first time that such an approach has been employed in matching theory to provide possibility and impossibility results. We remark that impossibility results concerning stability, resoluteness and some sort of fairness have been provided in the literature about matching mechanisms. Masarani and Gokturk (1989) basically show that resoluteness, \(G^*\)-symmetry, stability and a further axiom called maximin optimality cannot coexist. Endriss (2020) proves instead Theorem (E). In particular, he first shows that stability and gender-indifference can be encoded in a specific formal language; then, he proves that an impossibility result involving those properties can be reduced to an impossibility result where the sizes of \(W\) and \(M\) is three, that this latter case can be fully automated using SAT solving technology, and that the automated proof can be made human-readable. In the paper, we propose a proof of Theorem (E) which differs from the one provided by Endriss.

2 Preliminaries↩︎

Throughout the paper, \(\mathbb{N}\) denotes the set of positive integers and we set \(\mathbb{N}_0=\mathbb{N}\cup\{0\}\). Let \(n,m\in \mathbb{N}\). We set \(\ldbrack n \rdbrack\coloneq\{x\in \mathbb{N}: x\leq n\}\). If \(m\) divides \(n\), we write \(m\mid n\). For a prime number \(r\in \mathbb{N}\), we denote by \(|n|_r\) the \(r\)-part of \(n\), that is, the maximum power of \(r\) dividing \(n\). Given \(x\in \mathbb{Z}\), we denote the equivalence class of \(x\) modulo \(n\) by \([x]_n\coloneq\{x+kn: k\in \mathbb{Z}\}\). Note that, for every \(x\in \mathbb{Z}\), \([x]_n\cap \ldbrack n \rdbrack\) is a singleton whose unique element can be taken as a canonical representative for the set \([x]_n\).

Given the sets \(A\), \(B\) and \(C\) and the functions \(f:A\to B\) and \(g:B\to C\), we denote by \(gf\) the right-to-left composition of \(f\) and \(g\), that is, the function from \(A\) to \(C\) defined, for every \(a\in A\), by \(gf(a)\coloneq g(f(a))\). Given a finite set \(X\), we denote by \(|X|\) the size of \(X\).

2.1 Permutations, groups and actions↩︎

Let \(X\) be a nonempty and finite set of size \(n\in \mathbb{N}\). We denote by \(\mathrm{Sym}(X)\) the group of the bijective functions from \(X\) to itself with the product defined, for every \(\sigma_1,\sigma_2\in \mathrm{Sym}(X)\), by the composition \(\sigma_1\sigma_2\in \mathrm{Sym}(X)\). The neutral element of \(\mathrm{Sym}(X)\) is given by the identity function on \(X\), denoted by \(id_X\). The group \(\mathrm{Sym}(X)\) is called the symmetric group on \(X\) and its elements are called permutations of \(X\). Among the permutations, cycles play a main role. Let \(k\in \mathbb{N}\), with \(2\leq k\leq |X|\). Then \(\gamma\in \mathrm{Sym}(X)\) is called a \(k\)-cycle if there exist \(x_1,\dots, x_k\in X\) distinct, such that \(\gamma(x_i)=x_{i+1}\) for all \(i\in\ldbrack k-1\rdbrack\), \(\gamma(x_k)=x_{1}\), and \(\gamma(x)=x\) for all \(x\in X\setminus \{x_1,\dots, x_k\}\) (if any). In such a case \(\gamma\) is denoted by \((x_1\dots x_k)\) and the set \(\{x_1,\dots, x_k\}\) is called the support of \((x_1\dots x_k)\). For instance, if \(X=\ldbrack 6\rdbrack\), the permutation \(\gamma=(134)\in\mathrm{Sym}(X)\) is the 3-cycle such that \(\varphi(1)=3\), \(\varphi(2)=2\), \(\varphi(3)=4\), \(\varphi(4)=1\), \(\varphi(5)=5\), \(\varphi(6)=6\).

Let \(G\) be a finite group and \(Z\subseteq G\). If \(Z\) is a subgroup of \(G\) we write \(Z\leq G.\) We denote by \(\langle Z\rangle\) the subgroup of \(G\) generated by \(Z\), that is, the intersection of the subgroups of \(G\) containing \(Z\). If \(Z=\{z\}\), we write \(\langle z\rangle\) instead of \(\langle \{z\}\rangle\). Recall that, since \(G\) is finite, \(\langle Z\rangle\) is formed by all possible finite products of elements in \(Z\). We say that \(G\) is cyclic if there exists \(z\in G\) such that \(G=\langle z\rangle\). In such a case, we have \(G=\{z^k:k\in\mathbb{N}\}\). Moreover, if \(|G|=n\), then \(n\) is the minimum \(k\in\mathbb{N}\) such that \(z^k=1\). For \(z\in G\), the order of \(z\) is given by \(|z|\coloneq|\langle z\rangle|\). By Lagrange Theorem, we have that \(|z|\) divides \(|G|\).

Let \(u,v\in G\) and \(U\le G\). Given \(g\in G\), the conjugate of \(u\) through \(g\) is \(u^g\coloneq gug^{-1}\in G\) and the conjugate of \(U\) through \(g\) is \(U^g\coloneq\{u^g:g\in G\}\le G\). We say that \(u\) and \(v\) are conjugate in \(G\) if there exists \(g\in G\) such that \(u^g=v\). We recall that conjugate elements have the same order. Moreover, conjugation is a homomorphism. In other words \((uv)^g=u^gv^g\). \(U\) is called normal in \(G\) if, for every \(g\in G\), \(U^g=U\).

An action of \(G\) on \(X\) is a group homomorphism from \(G\) to \(\mathrm{Sym}(X)\). Assume that \(G\) acts on \(X\) through the action \(f\). For every \(g\in G\) and \(x\in X\), we usually write \(x^g\) instead of \(f(g)(x)\). In particular, the action is not explicitly mentioned. Given \(x\in X\), the \(G\)-orbit of \(x\) is the set \(x^G \coloneq\{x^g\in X:g\in G\}\); the \(G\)-stabilizer of \(x\) is the subgroup of \(G\) defined by \(\mathrm{Stab}_G(x) \coloneq\{g\in G: x^g=x\}\). A well-known result establishes that, for every \(x\in X\), \[|x^G|=\frac{|G|}{|\mathrm{Stab}_G(x)|},\] so that, in particular, \(|x^G|\) divides \(|G|\). The set \(X^G \coloneq\{x^G\subseteq X:x\in X\}\) is a partition⁹ of \(X\) called the set of the \(G\)-orbits of \(X\) or, alternatively, the set of orbits of \(G\) on \(X\). The reference to \(X\) is usually omitted when \(X\) is clear from the context.

If \(G\le \mathrm{Sym}(X)\), we can consider the natural action \(f\) of \(G\) on \(X\) defined, for every \(\varphi\in G\), by \(f(\varphi)=\varphi\), so that \(f(\varphi)(x)=x^\varphi=\varphi(x)\) for all \(x\in X\). Thus, with respect to that action, for every \(x\in X\), we have \(x^G=\{\varphi(x)\in X:\varphi\in G\}\) and \(\mathrm{Stab}_G(x) =\{\varphi\in G: \varphi(x)=x\}\).

Let now \(\varphi\in \mathrm{Sym}(X)\). Since \(\langle \varphi\rangle\le\mathrm{Sym}(X)\), we can consider the natural action of \(\langle \varphi\rangle\) on \(X\). Given \(x\in X\), we have that \(x^{\langle \varphi\rangle}=\{\varphi^n(x)\in X:n\in\mathbb{N}\}\) and \(|x^{\langle \varphi\rangle}|=1\) if and only if \(x\) is a fixed point for \(\varphi\), that is \(\varphi(x)=x\). The set of the \(\langle \varphi\rangle\)-orbits of \(X\), that is the set \(X^{\langle \varphi\rangle}=\{x^{\langle \varphi\rangle}\subseteq X: x\in X\}\), is also called the set of the orbits of \(\varphi\) on \(X\). Let \(r=|X^{\langle \varphi\rangle}|\in\mathbb{N}\) be the number of the distinct orbits of \(\varphi\) and let \(x_1,\dots, x_r\in X\) be such that \(X^{\langle \varphi\rangle}=\{x_j^{\langle \varphi\rangle}:j\in \ldbrack r \rdbrack\}\). The elements \(x_1,\dots, x_r\) are called representatives of the orbits of \(\varphi\). The type of \(\varphi\) is the unordered list \(T_{\varphi}\coloneq[|x_1^{\langle \varphi\rangle}|,\dots,|x_r^{\langle \varphi\rangle}|]\) whose elements, called the parts of \(T_\varphi\), are the sizes of the orbits of \(\varphi\). We have that \(\sum_{j=1}^r|x_j^{\langle \varphi\rangle}|=n\) and \(|\varphi|=\mathrm{lcm}(|x_1^{\langle \varphi\rangle}|,\dots,|x_r^{\langle \varphi\rangle}|)\). When we need to emphasize the distinct parts \(b_1,\dots, b_s\) of \(T_{\varphi}\), the notation \(T_{\varphi}=[b_1^{(r_1)},\dots, b_s^{(r_s)}]\) will be used, where, for every \(i\in\ldbrack s\rdbrack\), \(r_i\) counts how many times \(b_i\) appears in \(T_\varphi\). As an example, if the type of \(\varphi\) is \(T_{\varphi}=[1,1,2,2,3,4,4,4]\), then we can write \(T_{\varphi}=\left[1^{(2)},2^{(2)},3,4^{(3)}\right]\). If \(\varphi\neq id_X\), then the set \(K=\{j\in \ldbrack r \rdbrack:|x_j^{\langle \varphi\rangle}|\geq 2\}\) has size \(k\ge 1\). A fundamental theorem on permutations assures that \(\varphi\) is the product of \(k\) disjoint cycles \((\gamma_j)_{j\in K}\), where, for every \(j\in K\), \(\gamma_j\in\mathrm{Sym}(X)\) is a \(|x_j^{\langle \varphi\rangle}|\)-cycle whose support is \(x_j^{\langle \varphi\rangle}\). In particular, \(|\gamma_j|=|x_j^{\langle \varphi\rangle}|\). Moreover, such a decomposition is unique up to a reordering of the cycles.

Note that the computation of the conjugation of a cycle \((x_1\dots\, x_k)\in \mathrm{Sym}(X)\) by \(\psi \in \mathrm{Sym}(X)\) is particularly simple. Indeed, we have \((x_1\dots\, x_k)^{\psi}=(\psi(x_1)\dots\, \psi(x_k)).\) It is also well known that, given \(\varphi_1, \varphi_2\in \mathrm{Sym}(X)\), we have \(T_{\varphi_1}=T_{\varphi_2}\) if and only if \(\varphi_1\) and \(\varphi_2\) are conjugate in \(\mathrm{Sym}(X)\).

Given \(S\subseteq \mathrm{Sym}(X)\) and \(\varphi\in \mathrm{Sym}(X)\), we set \[\varphi S\coloneq\left\{\rho \in \mathrm{Sym}(X): \exists\sigma \in Ssuch that \rho=\varphi\sigma\right\},\] \[S\varphi \coloneq\left\{\rho \in \mathrm{Sym}(X): \exists\sigma \in Ssuch that \rho=\sigma\varphi\right\}.\] Of course, \(id_X\, S=S\) and \(S\, id_X=S\). Moreover, for every \(\varphi_1,\varphi_2\in \mathrm{Sym}(X)\), we have that \((\varphi_1\varphi_2)S=\varphi_1(\varphi_2 S)\), \(S(\varphi_1\varphi_2)=(S \varphi_1)\varphi_2\), and \((\varphi_1 S)\varphi_2=\varphi_1(S\varphi_2)\). In particular, given \(\varphi_1,\varphi_2,\varphi_3,\varphi_4\in \mathrm{Sym}(X)\), we have that the writing \(\varphi_1\varphi_2S\varphi_3\varphi_4\) without brackets is unambiguous: in any way we perform the operations we always get the same set. Note that if \(S\subseteq T\) and \(\varphi\in \mathrm{Sym}(X)\), then \(\varphi S\subseteq \varphi T\) as well as \(S\varphi\subseteq T\varphi.\)

2.2 Relations↩︎

Let \(X\) be a nonempty and finite set. A relation on \(X\) is a subset of \(X^2\). The set of the relations on \(X\) is denoted by \(\mathbf{R}(X)\). If \(R,R'\in \mathbf{R}(X)\) and \(R'\subseteq R\) we say that \(R'\) refines \(R\).

Let \(R\in \mathbf{R}(X)\). Given \(x,y\in X\), we usually write \(x\succeq_R y\) instead of \((x,y)\in R\) and \(x\succ_R y\) instead of \((x,y)\in R\) and \((y,x)\notin R\). We say that \(R\) is complete if, for every \(x,y\in X\), \(x\succeq_R y\) or \(y\succeq_R x\); antisymmetric if, for every \(x,y\in X\), \(x\succeq_R y\) and \(y\succeq_R x\) imply \(x=y\); transitive if, for every \(x,y,z\in X\), \(x\succeq_Ry\) and \(y\succeq_R z\) imply \(x\succeq_R z\); a linear order if it is complete, transitive and antisymmetric. The set of linear orders on \(X\) is denoted by \(\mathbf{L}(X)\).

Consider \(R\in \mathbf{L}(X)\). Given \(x\in X\), we set \(\mathrm{Rank}_R(x)=|\{y\in X: y\succeq_{R} x\}|\). If \(|X|=n\), we usually represent \(R\) by a column vector \([x_1,\ldots, x_n]^T\), where \(X=\{x_1,\ldots, x_n\}\) and, for every \(i,j\in \ldbrack n \rdbrack\), \(x_i\succeq_R x_j\) if and only if \(i\le j\). Such a representation completely encodes the relation \(R\). Note also that if \(R=[x_1,\ldots, x_n]^T\), then, for every \(i\in\ldbrack n\rdbrack\), \(\mathrm{Rank}_R(x_i)=i\). Thus, for every \(x\in X\), the number \(\mathrm{Rank}_R(x)\) represents the position of \(x\) in the column vector representing \(R\).

Let \(X,Y\) be finite sets with \(X\subseteq Y\). Let \(R\) be a relation on \(X\) and \(\varphi\in\mathrm{Sym}(Y)\). We denote by \(\varphi R\) the relation on \(\varphi(X)\) defined by \[\label{prodottorel} \varphi R \coloneq\left\{(x,y)\in \varphi(X)^2: (\varphi^{-1}(x),\varphi^{-1}(y))\in R\right\}.\tag{1}\] Note that, for every \(x,y\in X\), \((x,y)\in R\) if and only if \((\varphi(x),\varphi(y))\in\varphi R\). It can be easily checked that if \(\varphi_1,\varphi_2\in\mathrm{Sym}(Y)\), then \((\varphi_1\varphi_2)R=\varphi_1(\varphi_2 R)\). Hence the writing \(\varphi_1\varphi_2 R\) is unambiguous.

3 Preference profiles and the group \(G^*\)↩︎

Let \(W\) and \(M\) be two finite disjoint sets with \(|W|=|M|=n\ge 2\) and let \(I=W\cup M\). We refer to the sets \(W\), \(M\) and \(I\) as the set of women, the set of men and the set of the individuals, respectively. For simplicity, we assume \(W=\{1,\ldots,n\}\) and \(M=\{n+1,\ldots,2n\}\). In order to simplify the reading, we adopt the following rule throughout the paper (with few exceptions): the letter \(x\) is used to denote the elements of \(W\), the letter \(y\) is used to denote the elements of \(M\) and the letter \(z\) is used to denote the elements of \(I\), that is, individuals for whom it is not important to specify whether they belong to \(W\) or \(M\).

Each woman has preferences on the set \(M\) and each man has preferences on the set \(W\). We assume that the preferences of women are represented by linear orders on \(M\) and that the preferences of men are represented by linear orders on \(W\). A preference profile \(p\) is a function from \(I\) to \(\mathbf{L}(W)\cup \mathbf{L}(M)\) such that, for every \(x\in W\), \(p(x)\in \mathbf{L}(M)\) and, for every \(y\in M\), \(p(y)\in \mathbf{L}(W)\). We denote by \(\mathcal{P}(W,M)\) the set of preference profiles. A preference profile \(p\in\mathcal{P}(W,M)\) can be represented by a table like the following one: \[\begin{array}{|ccc||ccc|} \hline 1&\ldots&n&n+1&\ldots&2n\\ \hline \hline p(1)&\ldots&p(n)&p(n+1)&\ldots&p(2n)\\ \hline \end{array}\] For instance, let \(W=\{1,2,3\}\) and \(M=\{4,5,6\}\); a preference profile \(p\in \mathcal{P}(W,M)\) is represented in the next table: \[\label{tablep} \begin{array}{|ccc||ccc|} \hline 1&2&3&4&5&6\\ \hline \hline 4&4&6&2&3&3\\ 5&6&5&1&1&2\\ 6&5&4&3&2&1\\ \hline \end{array}\tag{2}\] In particular, the first three columns are the preferences of the women on the set \(M\) and the last three columns are the preferences of the men on the set \(W\): \[p(1)=[4,5,6]^T\in \mathbf{L}(M), \quad p(2)=[4,6,5]^T\in \mathbf{L}(M), \quad p(3)=[6,5,4]^T\in \mathbf{L}(M),\] \[p(4)=[2,1,3]^T\in \mathbf{L}(W), \quad p(5)=[3,1,2]^T\in \mathbf{L}(W), \quad p(6)=[3,2,1]^T\in \mathbf{L}(W).\]

We consider now the subgroups of \(\mathrm{Sym}(I)\) given by¹⁰ \[G^*\coloneq\{\varphi\in \mathrm{Sym}(I): \{\varphi(W)\,,\varphi(M)\}=\{W,M\}\},\] and \[G\coloneq\{\varphi\in G^*: \varphi(W)=W,\,\varphi(M)=M\},\] where \(G\le G^*\). For instance, if \(W=\{1,2,3\}\) and \(M=\{4,5,6\}\), then \((1 2 3)(4 6)\) is a permutation in \(G\) while \((1 4 2 6)(3 5)\) is a permutation in \(G^*\setminus G\). Note that the permutations in \(G\) permute women’s names among women and men’s names among men; the permutations in \(G^*\setminus G\) rename each woman with one of the men’s names and each man with one of the women’s names. Clearly \(G^*\setminus G\neq \varnothing\) because \(|W|=|M|.\) It is easily checked that \(|G|=(n!)^2\) and \(|G^*|=2(n!)^2\). Thus the index of \(G\) in \(G^*\) is \(2\). In particular, \(G\) is a normal subgroup of \(G^*\) and, for every \(\varphi_1, \varphi_2\in G^*\setminus G\), we have \(\varphi_1 \varphi_2\in G\). In \(G\) we can distinguish two further subgroups of \(G^*\), namely \[G_W\coloneq\{\varphi\in G: \varphi(y)=yfor all y\in M\},\] \[G_M\coloneq\{\varphi\in G: \varphi(x)=xfor all x\in W\}.\] Observe that \(G_W\) consists of those permutations of individuals’ names that leave men’s names unchanged; \(G_M\) consists of those permutations of individuals’ names that leave women’s names unchanged. We have that \(G_W\cong G_M \cong \mathrm{Sym}(\ldbrack n \rdbrack)\). In particular, \(|G_W|=|G_M|=n!\). Moreover, \(G=G_W\times G_M\).

Given \(p\in \mathcal{P}(W,M)\) and \(\varphi\in G^*\), taking into account the definition 1 , we denote by \(p^\varphi\) the preference profile defined, for every \(z\in I\), by \[\label{action-w} p^\varphi(z)=\varphi p(\varphi^{-1}(z)).\tag{3}\]

It is easily checked that \(p^\varphi\) actually belongs to \(\mathcal{P}(W,M)\). Indeed, if \(\varphi\in G\), then, for every \(x\in W\) [\(y\in M\)], \(\varphi^{-1}(x)\in W\) [\(\varphi^{-1}(y)\in M\)] so that \(p(\varphi^{-1}(x))\in \mathbf{L}(M)\) [\(p(\varphi^{-1}(y))\in \mathbf{L}(W)\)]. Moreover, since \(\varphi(W)=W\) [\(\varphi(M)=M\)], by definition 1 , we have that \(\varphi p(\varphi^{-1}(x))\in \mathbf{L}(M)\) [\(\varphi p(\varphi^{-1}(y))\in \mathbf{L}(W)\)]. If instead \(\varphi\in G^*\setminus G\), then, for every \(x\in W\) [\(y\in M\)], \(\varphi^{-1}(x)\in M\) [\(\varphi^{-1}(y)\in W\)] so that \(p(\varphi^{-1}(x))\in \mathbf{L}(W)\) [\(p(\varphi^{-1}(y))\in \mathbf{L}(M)\)]. Moreover, since \(\varphi(M)=W\) [\(\varphi(W)=M\)], by definition 1 , we have that \(\varphi p(\varphi^{-1}(x))\in \mathbf{L}(M)\) [\(\varphi p(\varphi^{-1}(y))\in \mathbf{L}(W)\)].

It is useful to note that 3 is equivalent to state that, for every \(z\in I\), \[\label{action-w2} p^\varphi(\varphi(z))=\varphi p(z).\tag{4}\] The preference profile \(p^\varphi\) is the preference profile obtained by \(p\) via changing individuals’ names according to \(\varphi\). If \(\varphi\in G\), then \(p^\varphi\) is obtained by \(p\) by permuting women’s names among women and by permuting men’s names among men. If instead \(\varphi\in G^*\setminus G\), then \(p^\varphi\) is obtained by \(p\) by exchanging women’s and men’s names. If \(p\in\mathcal{P}(W,M)\) is represented by \[\begin{array}{|ccc||ccc|} \hline 1&\ldots&n&n+1&\ldots&2n\\ \hline \hline p(1)&\ldots&p(n)&p(n+1)&\ldots&p(2n)\\ \hline \end{array}\] and \(\varphi \in G^*\), then, recalling 4 , it is clear that \(p^\varphi\) is represented by following table, where the columns have to be rearranged in such a way that in the first row of the table we have numbers from 1 to \(2n\) in an increasing order \[\begin{array}{|ccc||ccc|} \hline \varphi(1)&\ldots&\varphi(n)&\varphi(n+1)&\ldots&\varphi(2n)\\ \hline \hline \varphi p(1)&\ldots&\varphi p(n)&\varphi p(n+1)&\ldots&\varphi p(2n)\\ \hline \end{array}.\] For instance, consider the preference profile \(p\) represented in table 2 . If \(\varphi=(123)(46)\in G\), then \[p^{\varphi}= \begin{array}{|ccc||ccc|} \hline 2&3&1&6&5&4\\ \hline \hline 6&6&4&3&1&1\\ 5&4&5&2&2&3\\ 4&5&6&1&3&2\\ \hline \end{array} = \begin{array}{|ccc||ccc|} \hline 1&2&3&4&5&6\\ \hline \hline 4&6&6&1&1&3\\ 5&5&4&3&2&2\\ 6&4&5&2&3&1\\ \hline \end{array}.\] If instead \(\varphi=(1426)(35)\in G^*\), then \[\label{tablep2} p^{\varphi}= \begin{array}{|ccc||ccc|} \hline 4&6&5&2&3&1\\ \hline \hline 2&2&1&6&5&5\\ 3&1&3&4&4&6\\ 1&3&2&5&6&4\\ \hline \end{array} = \begin{array}{|ccc||ccc|} \hline 1&2&3&4&5&6\\ \hline \hline 5&6&5&2&1&2\\ 6&4&4&3&3&1\\ 4&5&6&1&2&3\\ \hline \end{array}.\tag{5}\]

The following simple lemma will turn out crucial for our purposes.

If we consider a set \(P\) of preference profiles and a subset \(U\) of \(G^*\), there is no guarantee, in general, that, for every \(p \in P\) and \(\varphi\in U\), \(p^\varphi\in P\). The next definition addresses this point.

Note that, for every \(U\subseteq G^*\), \(\mathcal{P}(W,M)\) is \(U\)-symmetric and any \(P\subseteq \mathcal{P}(W,M)\) is \(\{id_I\}\)-symmetric. Moreover, if \(V\subseteq U\subseteq G^*\) and \(P\subseteq \mathcal{P}(W,M)\) is \(U\)-symmetric, then \(P\) is \(V\)-symmetric, as well.

The next proposition shows that, without losing generality, the concept of \(U\)-symmetry for a subset of \(\mathcal{P}(W,M)\) could have been equivalently defined by considering only subgroups of \(G^*\).

4 Matchings and matching mechanisms↩︎

4.1 Matchings↩︎

A (two-sided) matching is a permutation \(\mu\in \mathrm{Sym}(I)\) such that

• for every \(x\in W\), \(\mu(x)\in M\);

• for every \(y\in M\), \(\mu(y)\in W\);

• for every \(z\in I\), \(\mu(\mu(z))=z\).

The set of matchings is denoted by \(\mathcal{M}(W,M)\).

For instance, if \(W=\{1,2,3\}\) and \(W=\{4,5,6\}\), then: \[\mathcal{M}(W,M)=\{(14)(25)(36),(14)(26)(35),(16)(25)(34),(15)(24)(36),(15)(26)(34),(16)(24)(35)\}.\] The next proposition states some useful characterizations of the set of matchings, along with the fact that any conjugate in \(G^*\) of a matching is a matching as well.

An important property a matching may meet is stability. Its definition is as follows.

Note that a pair \((x,y)\in W\times M\) blocks a matching \(\mu\) when \(x\) prefers \(y\) to her assigned partner under \(\mu\), and \(y\) prefers \(x\) to his assigned partner under \(\mu\). Gale and Shapley (1962) proved that for every \(p\in \mathcal{P}(W,M)\), a stable matching exists and provided an algorithm to find such a matching. In this algorithm, each side is assigned a specific role: individuals on one side make proposals to individuals on the other side who are allowed to accept or refuse the proposals. Hence, the algorithm has two distinct versions, each producing a stable matching. Those matchings, in general, differ from each other, but both possess a special property. Indeed, Gale and Shapley proved that the matching resulting from the algorithm where women make proposals associates each woman with the best possible partner she can have within stable matchings, and each man with the worst possible partner he can have within stable matchings. Symmetrically, the algorithm where men make proposals associates each man with the best possible partner he can have within stable matchings, and each woman with the worst possible partner she can have within stable matchings. For such reasons, in the literature, these two matchings are frequently referred to as the woman-optimal stable matching and the man-optimal stable matching, respectively.

Let us introduce now two optimality conditions for matchings. The first one is well known; the second one, to the best of our knowledge, is new.

Thus, a matching is not weakly Pareto optimal for \(p\) if there exists another matching making every individual better off; a matching is not minimally optimal for \(p\) if all the individuals are matched with their least preferred choice. Note that, given a preference profile \(p\), there exists at most one matching that is not minimally optimal for \(p\).

The following proposition describes the relation among stability, weak Pareto optimality and minimal optimality.

4.2 Matching mechanisms↩︎

Thus, a mm on \(P\subseteq \mathcal{P}(W,M)\) is a procedure that allows to select a set of matchings for any given preference profile in \(P\). When the domain of a mm is not specified, it is assumed to be the whole set \(\mathcal{P}(W,M)\). In what follows, we denote by \(TO\) the mm that associates with any \(p\in \mathcal{P}(W,M)\) the whole set \(\mathcal{M}(W,M)\); by \(ST\) the mm that associates with any \(p\in \mathcal{P}(W,M)\) the set of all the matchings that are stable for \(p\); by \(GS_w\) (\(GS_m\)) the mm that associates with any \(p\in \mathcal{P}(W,M)\) the set having as unique element the woman-optimal (man-optimal) stable matching for \(p\); by \(GS\) the mm that associates with any \(p\in \mathcal{P}(W,M)\) the set whose elements are the woman-optimal stable matching and the man-optimal stable matching for \(p\); by \(WPO\) the mm that associates with any \(p\in \mathcal{P}(W,M)\) the set of the matchings that are weakly Pareto optimal for \(p\); by \(MO\) the mm that associates with any \(p\in \mathcal{P}(W,M)\) the set of the matchings that are minimally optimal for \(p\).

Let us introduce now some basic definitions.

Since in principle we are interested in procedures that select a single matching whatever individual preferences are, resolute mms are particularly important. Of course, if \(F\) is resolute, then \(F\) is decisive. Note that \(GS\), \(ST\), \(WPO\), \(MO\) and \(TO\) are decisive but they are not in general resolute, while \(GS_w\) and \(GS_m\) are resolute (Gale and Shapley, 1962).

The next definition is crucial for our purposes.

Note that if \(F\), \(H\) and \(K\) are mms on \(P\), then \(K\subseteq H\) and \(H\subseteq F\) imply \(K\subseteq F\). It is immediate to show that \(GS\subseteq ST\subseteq WPO\subseteq MO\subseteq TO\), \(GS_w\subseteq GS\) and \(GS_m\subseteq GS\).

Given a mm \(F\) on \(P\), it is natural to interpret any refinement of \(F\) as a way to reduce the ambiguity of \(F\). In particular, the refinements of \(F\) that are resolute, simply called the resolute refinements of \(F\), are particularly important as they allow to completely eliminate the ambiguity of \(F\). Of course, any decisive mm admits in general many resolute refinements so that, it becomes important to understand whether some of them fulfill desirable properties.

The next definitions focus on some special properties of a mm.

Note that a mm \(F\) on \(P\) is stable [weakly Pareto optimal; minimally optimal] if and only if \(F\) is a refinement of \(ST\) [\(WPO\); \(MO\)] restricted to \(P\).

The next definition introduces the main concept of the paper.

Condition \((a)\) guarantees that, for every \(p \in P\) and \(\varphi \in U\), \(p^{\varphi}\in U\) (see Definition 1). Condition \((b)\) states that, for every \(p\in P\) and \(\varphi\in U\), the set of matchings associated with \(p^{\varphi}\) by \(F\) corresponds to the set of the matchings associated with \(p\) by \(F\), each of them modified according to \(\varphi\). Indeed, note that, due to the definitions in Section 2.2 and Proposition 2\((iii)\), \[\varphi F(p)\varphi^{-1}=\left\{\sigma\in \mathcal{M}(W,M): \exists \mu \in F(p) such that \sigma=\varphi\mu\varphi^{-1}\right\}.\] As an example, consider \(W=\{1,2,3\}\) and \(M=\{4,5,6\}\) and let \(P\subseteq \mathcal{P}(W,M)\), \(U\subseteq G^*\) and \(F\) be a \(U\)-symmetric mm. Assume that the preference profile \(p\) defined in 2 belongs to \(P\), \(\varphi=(1426)(35)\in U\) and \(F(p)=\{(14)(25)(36),(15)(26)(34)\}\). By condition (a) in Definition 12, we get that \(p^\varphi\), the preference profile defined in 5 , belongs to \(P\). We can thus compute the value of \(F\) at \(p^\varphi\). Recalling now condition (b) in Definition 12 and how conjugation performs on permutations, we get \[\begin{align} F(p^\varphi)&=&\big\{\varphi(14)(25)(36)\varphi^{-1},\varphi (15)(26)(34) \varphi^{-1}\big\}\\ &=&\big\{(\varphi(1)\varphi(4))(\varphi(2)\varphi(5))(\varphi(3)\varphi(6)),(\varphi(1)\varphi(5))(\varphi(2)\varphi(6))(\varphi(3)\varphi(4))\big\}\\ &=&\{(42)(63)(51),(43)(61)(52)\}=\{(15)(24)(36),(16)(25)(34)\}. \end{align}\] The example clearly shows that, if \(F\) is \(U\)-symmetric, a change in the individuals’ names according to each permutation in \(U\) entails a corresponding change of names in all the matchings in the output. That is, the notion of \(U\)-symmetry pertains to fairness. In particular, if \(F\) is \(G_W\)-symmetric, then women are equally treated among themselves by \(F\); if \(F\) is \(G_M\)-symmetric, then men are equally treated among themselves by \(F\); if \(F\) is \(G\)-symmetric, then women are equally treated among themselves and men are equally treated among themselves by \(F\); if \(F\) is symmetric then women are equally treated among themselves, men are equally treated among themselves and the two groups of women and men are equally treated. Note that, if \(U\subseteq V\subseteq G^*\) and \(F\) is a mm on \(P\) that is \(V\)-symmetric, then \(F\) is \(U\)-symmetric. In particular, if \(F\) is symmetric, then it is \(U\)-symmetric for all \(U\subseteq G^*\).

Definition 12 provides a generalization of several properties present in the literature, all of them rightly linked to the concept of fairness and related to matching mechanisms defined on \(\mathcal{P}(W,M)\). Indeed, the standard concept of anonymity, called peer-indifference by Masarani and Gokturk (1989), coincides with the \(G\)-symmetry; the property of gender-indifference introduced by Masarani and Gokturk (1989) coincides with the \(\{\varphi\}\)-symmetry, where \(\varphi\) is a suitable element of \(\mathcal{M}(W,M)\) (see also Endriss, 2020); the property of gender-fairness by Ökzal-Sanver (2004) coincides with the \((G^*\setminus G)\)-symmetry. Of course, a mm \(F\) on \(P\) satisfies both peer-indifference and gender-indifference if and only if \(F\) satisfies \((G\cup\{\varphi\})\)-symmetry.

The next important proposition states that the concept of \(U\)-symmetry could have been equivalently defined involving only subgroups \(U\) of \(G^*\).

Because of Proposition 4, from now on, we are allowed to focus only on subgroups of \(G^*\). Proposition 4 implies some further interesting consequences. Before describing them, we need the following simple propositions.

By Propositions 4 and 5, we deduce that gender fairness, that is \((G^*\setminus G)\)-symmetry, coincides with symmetry. In particular, gender fairness implies \(G\)-symmetry, that is, anonymity (see Proposition 3.1 in Ökzal-Sanver, 2004). By Propositions 4 and 6, we can also deduce that a matching mechanism is both peer-indifferent and gender-indifferent, that is it is \((G\cup\{\varphi\})\)-symmetric, if and only if it is symmetric.

The next proposition, whose proof is in the appendix, shows that \(GS_w\) and \(GS_m\), which satisfy the crucial property of resoluteness, fail to fulfill symmetry, even though they are \(G\)-symmetric. On the other hand, we have that \(GS\), \(ST\), \(WPO\), \(MO\) and \(TO\) are symmetric but not resolute.

Some stable matching mechanisms have been introduced in the literature with the aim to guarantee more equity between the two sets \(W\) and \(M\) than the one obtained by \(GS_w\) and \(GS_m\). The Sex-Equal mechanism, introduced by Gusfield and Irving (1989) and analyzed in Romero-Medina (2001), and the Egalitarian Stable mechanism, introduced in Gusfield and Irving (1989), are two of them. Roughly speaking, both of them are based on the idea to quantify first, for every stable matching, the envy perceived by every individual and then consider the stable matchings minimizing a suitable function involving the level of envy of all the individuals. Given a preference profile \(p\), a matching \(\mu\) and \(z\in I\), we have that the number \(\mathrm{Rank}_{p(z)}(\mu(z))-1\) counts the number of individuals envied by \(z\) under the matching \(\mu\). Indeed, consider for instance, \(x \in W\). Then \(x\) envies the partners of all the men \(y\in M\) such that \(y \succ_{p(x)} \mu(x)\) and their number is exactly \(\mathrm{Rank}_{p(x)}(\mu(x))-1\). For every \(p\in\mathcal{P}(W,M)\) and \(\mu\in\mathcal{M}(W,M)\), we can consider then the quantities
\[\delta(p,\mu) \coloneq \left|\sum_{x \in W}\mathrm{Rank}_{p(x)}(\mu(x))-\sum_{y \in M}\mathrm{Rank}_{p(y)}(\mu(y))\right|,\] and \[e(p,\mu) \coloneq \sum_{x \in W}\mathrm{Rank}_{p(x)}(\mu(x))+\sum_{y \in M}\mathrm{Rank}_{p(y)}(\mu(y)).\] Since \[\sum_{x \in W}\mathrm{Rank}_{p(x)}(\mu(x)) \quadand \quad\sum_{y \in M}\mathrm{Rank}_{p(y)}(\mu(y))\] basically represent the aggregate level of envy of the men and the aggregate level of envy of the women, we have that \(\delta(\mu,p)\) measure the distance between those two values while \(e(\mu, p)\) measures the overall level of envy in the society. The Sex-Equal mm, denoted by \(SE\), is the mm defined, for every \(p\in\mathcal{P}(W,M)\), by \[SE(p) \coloneq \underset{\mu \in ST(p)}{\mathrm{arg\,min}}\; \delta(p,\mu);\] the Egalitarian Stable mm, denoted by \(ES\), is the mm defined, for every \(p\in\mathcal{P}(W,M)\), by \[ES(p) \coloneq \underset{\mu \in ST(p)}{\mathrm{arg\,min}}\; e(p,\mu).\] Of course, \(SE\) and \(ES\) are decisive and stable. Moreover, the following proposition, proved in the appendix, holds true.

The matching mechanisms \(SE\) and \(ES\) are then further examples of symmetric matching mechanisms. However, by Example 1 in Romero-Medina (2001, page 201), we get that they are not resolute.

Proving or disproving the existence of resolute and symmetric mms, possibly satisfying further properties (e.g. stability, weak Pareto optimality, minimal optimality), is certainly an interesting and not trivial problem. Since a resolute and symmetric mm can be seen as a resolute and symmetric refinement of \(TO\) and since many properties of matching mechanisms can be described using the concept of refinement (e.g. stability, weak Pareto optimality, minimal optimality), the aforementioned existence problem can be seen as a special case of the following general existence problem.

Let \(U\le G^*\), \(P\subseteq \mathcal{P}(W,M)\), and \(F\) be a mm on \(P\). Find conditions on \(U\), \(P\) and \(F\) that guarantee the existence of a resolute refinement of \(F\) that is \(U\)-symmetric.

In Section 5 we propose a series of results that lead to determine convenient necessary and sufficient conditions for the existence of \(U\)-symmetric resolute refinements of a given matching mechanism. In Section 7 we apply these conditions to prove a variety of possibility and impossibility results under the assumption that \(P=\mathcal{P}(W,M)\) and when \(U=G^*\) or \(U=\langle \varphi\rangle\) with \(\varphi\in\mathcal{M}(W,M)\). The intermediate Section 6 is devoted to prove some technical facts about \(G^*\)-stabilizers that turn out to be fundamental and preliminary for getting the results in Section 7.

5 General existence conditions↩︎

The next proposition shows that, given a subgroup \(U\) of \(G^*\) and a \(U\)-symmetric \(P\subseteq \mathcal{P}(W,M)\), \(U\) naturally acts on the set of preference profiles \(P\). This result allows to exploit many general facts from group theory.

Thanks to the fact that the function \(f\) defined in Proposition 9 is an action of \(G^*\) on \(\mathcal{P}(W,M)\), we can transfer to the framework of matching theory notation and results concerning the action of a group on a set. Let \(U\le G^*\) and \(P\subseteq \mathcal{P}(W,M)\) be \(U\)-symmetric. For every \(p\in P\), the \(U\)-orbit of \(p\) in \(P\) is \(p^U=\{p^\varphi\in P: \varphi\in U\}\). We denote by \(R\) the size of the set \(P^U=\{p^U:p\in P\}\) of the \(U\)-orbits.¹¹ A system of representatives of the \(U\)-orbits of \(P\) is any \((p_j)_{j=1}^{R}\in P^{R}\) such that \(P^U=\{p_j^{U} : j\in \ldbrack R \rdbrack\}\). For every \(p\in P\), the stabilizer of \(p\) in \(U\) is \(\mathrm{Stab}_U(p)=\{\varphi\in U : p^\varphi=p \}\le U\).

In the next definition we introduce, for every \(U\le G^*\), a matching mechanism, denoted by \(C^U\). Such a matching mechanism plays a crucial role to address the aforementioned Main Problem, as shown by all the subsequent results of the section.

Given a preference profile \(p\), \(C^U(p)\) selects all the matchings that are left unchanged by the permutations of individuals’ names that leave \(p\) unchanged.

6 Properties of the \(G^*\)-stabilizers↩︎

Consider a subgroup \(U\) of \(G^*\). It is clear from Theorem 12 that the existence of a resolute and \(U\)-symmetric refinement of a given \(U\)-symmetric mm is strongly related with the information we have about the matching mechanism \(C^{U}\). The definition of \(C^U\) makes clear that the more precise is the knowledge of the structure of the \(U\)-stabilizers of preference profiles the more detailed is the information about \(C^U\). Since, for every \(p\in \mathcal{P}(W,M)\), \(\mathrm{Stab}_U(p)=\mathrm{Stab}_{G^*}(p)\cap U\), in the present section we focus on the \(G^*\)-stabilizers. In particular, in Section 6.1 we present some algebraic facts about semi-regular groups of permutations that are useful for our purposes. In Section 6.2, we prove that \(G^*\)-stabilizers are in fact semi-regular groups so that the results proved in Section 6.1 can be exploited. In particular, Theorem 17 will play a crucial role in Section 7.

6.1 Semi-regular subgroups of \(G^*\)↩︎

We start this section recalling some classic definitions from the theory of permutation groups (see, for instance, Wielandt, 2014). Let \(X\) be a nonempty and finite set and \(S\) be a subgroup of \(\mathrm{Sym}(X)\). \(S\) is called semi-regular if, for every \(x\in X\), we have \(\mathrm{Stab}_S(x)=\{id_X\}\); transitive if, for every \(x,y\in X\), there exists \(s\in S\) such that \(s(x)=y\); regular if \(S\) is transitive and semi-regular. It is immediate to verify that \(S\) is transitive if and only if \(S\) admits a unique orbit on \(X\). Moreover, if \(S\) is transitive, then \(|X|\) divides \(|S|\) because, once chosen \(x\in X\), we have \(|X|=|x^S|=\frac{|S|}{|\mathrm{Stab}_S(x)|}\).

The following proposition describes some general properties of semi-regular groups of permutations.

We emphasize the strong consequence of semi-regularity expressed by Proposition 13\((v)\): two permutations of \(S\leq \mathrm{Sym}(X)\), which coincide on a single element of \(X\), coincide on the whole \(X\).

From here on, we focus on the properties of semi-regular subgroups of \(G^*\) under the assumption that \(n\) is odd.

Let \(U\) and \(V\) be groups with \(U\le V\). Recall that the centralizer of \(U\) in \(V\) is defined by \[C_{V}(U)\coloneq\{v\in V: \forall u \in U,\;uv=vu\}\le V.\] We now present a basic but useful result about centralizers. The first part is well-known from group theory. For the sake of completeness, we provide the complete proof of each part.

Let us prove now the main result of the section.

6.2 Semi-regularity of the \(G^*\)-stabilizers↩︎

In this section we analyze the \(G^*\)-stabilizers of preference profiles with the main purpose to show that they are always semi-regular subgroups of \(G^*\) (Theorem 19). The next proposition is the main auxiliary result of the section: it characterizes the types of permutations belonging to the \(G^*\)-stabilizers of a preference profile.

We now describe, up to group isomorphisms, the whole family of stabilizers when \(n=3\). Let \(n=3\) and consider \(p\in \mathcal{P}(W,M)\). By Theorem 19 and Proposition 13, we know that the size of \(\mathrm{Stab}_{G^*}(p)\) divides 6 so that it belongs to the set \(\{1,2,3,6\}\). As a consequence, up to isomorphisms, we have \(\mathrm{Stab}_{G^*}(p)\in\{1,C_2, C_3, C_6, S_3\}\).¹² Interestingly, all those cases can arise. Indeed, consider the following preference profiles \[p_1=\begin{array}{|ccc||ccc|} \hline 1&2&3&4&5&6\\ \hline \hline 4&4&4&1&1&1\\ 5&5&5&2&2&3\\ 6&6&6&3&3&2\\ \hline \end{array}\,, \quad p_2=\begin{array}{|ccc||ccc|} \hline 1&2&3&4&5&6\\ \hline \hline 4&4&4&1&1&1\\ 5&5&5&2&2&2\\ 6&6&6&3&3&3\\ \hline \end{array}\,, \quad p_3=\begin{array}{|ccc||ccc|} \hline 1&2&3&4&5&6\\ \hline \hline 4&5&6&2&3&1\\ 5&6&4&1&2&3\\ 6&4&5&3&1&2\\ \hline \end{array}\,,\] \[p_4=\begin{array}{|ccc||ccc|} \hline 1&2&3&4&5&6\\ \hline \hline 4&5&6&1&2&3\\ 5&6&4&2&3&1\\ 6&4&5&3&1&2\\ \hline \end{array}\,, \quad p_5=\begin{array}{|ccc||ccc|} \hline 1&2&3&4&5&6\\ \hline \hline 4&5&6&1&2&3\\ 5&6&4&3&1&2\\ 6&4&5&2&3&1\\ \hline \end{array}\,.\] A computation shows that \[\begin{array}{l} \mathrm{Stab}_{G^*}(p_1)=\{id_I\}\cong 1,\\ \\ \mathrm{Stab}_{G^*}(p_2)= \langle(14)(25)(36)\rangle\cong C_2,\\ \\ \mathrm{Stab}_{G^*}(p_3)=\langle (123)(456)\rangle\cong C_3,\\ \\ \mathrm{Stab}_{G^*}(p_4)= \langle (153426)\rangle\cong C_{6},\\ \\ \mathrm{Stab}_{G^*}(p_5)=\{id_I, (123)(456),(132)(465), (14)(26)(35), (15)(24)(36),(16)(25)(34)\}\cong S_3. \end{array}\]

The proof of the next two propositions is in the appendix.

7 Main results↩︎

This section contains the main possibility and impossibility results of the paper. Before providing them, it is useful to observe that, for every preference profile \(p\in \mathcal{P}(W,M)\), the set of matchings that the matching mechanism \(C^{G^*}\) associates with \(p\) can be written as follows: \[\label{imp} C^{G^*}(p)=\{\mu\in C_{G^*}(\mathrm{Stab}_{G^*}(p))\cap(G^*\setminus G): |\mu|=2\}.\tag{13}\] This simple remark will be useful in the proofs of Theorem 22, Theorem 23 and Theorem 24.

7.1 Main results about symmetry↩︎

We start by proving an impossibility result when \(n\) is even and a possibility result when \(n\) is odd.

Given the possibility result stated in Theorem 23, one may wonder whether it is possible, for the case \(n\) odd, to be more ambitious and ask for some further property, like minimal optimality, and still get the existence. The next result shows that the answer is negative.

Taking into account Theorems 22 and 24, we get the following general impossibility result.

As a consequence of the previous theorem, a weaker impossibility result can be obtained.

We emphasize that, for \(n\ge 3\), the above corollary is a consequence of a result by Endriss (2020) where, however, a completely different line of proof has been followed. For the content of Endriss’ theorem see Theorem 30 below.

7.2 Main results about symmetry with respect to a matching↩︎

Now we move our focus on the notion of \(\langle \varphi\rangle\)-symmetry, where \(\varphi\in\mathcal{M}(W,M)\). We start by providing two preliminary results.

By using Proposition 27, we can prove an interesting existence result.

Given Theorem 28, one may wonder whether it is possible to replace the assumption of weak Pareto optimality with the stronger property of stability and still get existence. The next two results show that this can be actually done if and only if \(n=2\). Note that Theorem 30 corresponds to Theorem 6 in Endriss (2020). The proof in Endriss is based both on first-order logic and on satisfiability (SAT) solving techniques. In fact, it is first shown that some properties of matching mechanisms, including stability and \(\langle \varphi\rangle\)-symmetry, can be encoded in a specific formal language. Then, it is proved that impossibility results involving these properties can be reduced to impossibility results for the case with three women and three men and that the analysis of this latter case can be fully automated using SAT solving technology. Here, we propose an elementary proof of that impossibility result.

8 Conclusions↩︎

In this paper we proved, under the assumption \(|W|=|M|\), several possibility and impossibility results for matching mechanisms satisfying resoluteness, a given level of symmetry, (i.e. \(G^*\)-symmetry or \(\langle \varphi\rangle\)-symmetry), and possibly other desirable properties (i.e. stability, weak Pareto optimality and minimal optimality). These results are obtained by employing suitable algebraic methods based on group theory, an approach not yet explored in matching theory. Our paper demonstrates that such an approach is fruitful and able to provide novel and remarkable insight into issues that pertain to fairness.

The theorems we proved state that: resoluteness and \(G^*\)-symmetry are consistent with each other if and only if the size of \(W\) and \(M\) is odd (Theorem 22 and Theorem 23); resoluteness and \(G^*\)-symmetry are inconsistent with minimal optimality, definitely a very weak condition (Theorem 24 and Theorem 25); there exist resolute and \(\langle\varphi\rangle\)-symmetric matching mechanisms that are weak Pareto optimal but none of them can be stable, unless the size of \(W\) and \(M\) is 2 (Theorem 28, Theorem 29, Theorem 30). The conclusions that we can draw from these results could be recap as follows: when we restrict attention to resolute matching mechanisms, the highest level of symmetry is incompatible with any sort of optimality condition while weaker symmetry conditions, still involving a comparison between the two groups of agents, are incompatible with strong optimality conditions, like stability, but may be consistent with other interesting optimality conditions, like weak Pareto optimality.

All these findings constitute a first step in the direction of a complete understanding of the Main Problem described in Section 4. The next steps naturally consist in analyzing whether it is possible to identify suitable preference domain restrictions that guarantee the existence of resolute matching mechanisms satisfying strong optimality conditions, like stability, while maintaining a sufficiently high level of symmetry. We believe that Theorem 12, as well as the analysis of the \(G^*\)-stabilizers presented in Section 6, will turn out to be fundamental tools for carrying on such a research project in the future.

Appendix↩︎

The authors are grateful to Pablo Spiga for inspiring discussions and very valuable suggestions about centralizers of semi-regular subgroups. Daniela Bubboloni is supported by GNSAGA of INdAM (Italy) and by the national project PRIN 2022- 2022PSTWLB - Group Theory and Applications - CUP B53D23009410006. Claudia Meo is supported by the national project PRIN 2022 - 2022HLPMKN - Externalities and Fairness in Allocations and Contracts.

Abdulkadiroğlu, A., Sönmez, T., 2003. School choice: A mechanism design approach. American Economic Review 93 (3), 729–747.

Bubboloni, D., Gori, M., 2014. Anonymous and neutral majority rules. Social Choice and Welfare 43, 377–401.

Bubboloni, D., Gori, M., 2015. Symmetric majority rules. Mathematical Social Sciences 76, 73–86.

Bubboloni, D., Gori, M., 2016. Resolute refinements of social choice correspondences. Mathematical Social Sciences 84, 37–49.

Bubboloni, D., Gori, M., 2021. Breaking ties in collective decision-making. Decisions in Economics and Finance 44, 411–457.

Cooper, F., Manlove, D., 2020. Algorithms for new types of fair stable matchings. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 20:1-20:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020).

Doğan, O., Giritligil, A.E., 2015. Anonymous and neutral social choice: existence results on resoluteness. Murat Sertel Center for Advanced Economic Studies, Working paper series 2015–01.

Eğecioğlu, Ö., 2009. Uniform generation of anonymous and neutral preference profiles for social choice rules. Monte Carlo Methods and Applications 15, 241–255.

Endriss, U., 2020. Analysis of One-to-One Matching Mechanisms via SAT Solving: Impossibilities for Universal Axioms. The Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI-20), 1–8.

Gale, D., Shapley, L. S., 1962. College admissions and the stability of marriage. The American Mathematical Monthly 69 (1), 9–15.

Gusfield, D., Irving, R. W., 1989. The stable marriage problem: structure and algorithms. The MIT Press.

Hałaburda, H., 2010. Unravelling in two-sided matching markets and similarity of preferences. Games and Economic Behavior 69 (2), 365–393.

Klaus, B., Klijn, F., 2006. Procedurally fair and stable matching. Economic Theory 27 (2), 431–447.

Knuth, D.E., 1976. Mariages stables et leurs relations avec d’autres problèmes combinatoires. Montreal: Les Presses de l’Université de Montreal.

Masarani, F., Gokturk, S.S., 1989. On the existence of fair matching algorithms. Theory and Decision 26, 305–322.

zkal-Sanver, İ., 2004. A note on gender fairness in matching problems. Mathematical Social Sciences 47 (2), 211–217.

Romero-Medina, A., 2001. ‘Sex-equal’ stable matchings. Theory and Decision 150, 197–212.

Roth, A. E., 1984. The evolution of the labor market for medical interns and residents: a case study in game theory. Journal of Political Economy 92 (6), 991–1016.

Roth, A. E., 1991. A natural experiment in the organization of entry-level labor markets: Regional markets for new physicians and surgeons in the United Kingdom. The American Economic Review 81 (3), 415–440.

Roth, A. E., Sotomayor, M. A., 1990. Two–sided matchings. A study in game-theoretic modeling and analysis. Cambridge University Press.

Sasaki, H., Toda, M., 1992. Consistency and characterization of the core of two-sided matching problems. Journal of Economic Theory 56 (11), 218–227.

Wielandt, H., 2014. Finite permutation groups. Academic Press, New York.

---

1. Most applications involve sets of agents having different sizes; however, in some circumstances assuming the same size is not a restriction. Consider, for instance, a university which offers to its near-graduate students the opportunity to experience a short-term work experience in selected public and private organizations and companies. Assume further that there are \(n\) internship programs available and that each program is interested to select exactly one student. If the university preliminarily shortlists \(n\) students among the ones applying, we face a situation where \(n\) students have to be assigned to \(n\) internship programs. A good assignment should consider both the preferences of each student over the companies who offer such internships and the preferences of each company/organization over the students.↩︎

2. This property is a consequence of a more general result due to Knuth (1976). See, also, Roth and Sotomayor (1990), Theorem 2.13 and Corollary 2.14.↩︎

3. Our interpretation of fairness is somehow close to the concept of procedural fairness analyzed in Klaus and Klijn (2006) and based on probabilistic considerations: a (random) mechanism is procedurally fair whenever each agent has the same probability to move at a certain point in the procedure that determines the final probability distribution.↩︎

4. Masarani and Gokturk (1989) only consider resolute matching mechanisms (or, matching algorithms, as they call them). Moreover, they account only for a specific change in the identities of individuals, namely, if \(W=\{1,\ldots, n\}\) and \(M=\{n+1,\ldots, 2n\}\), then woman 1 becomes man \(n+1\) and vice versa, woman 2 becomes man \(n+2\) and vice versa, and so on. See also Endriss (2020).↩︎

5. See Proposition 3.1 in Ökzal-Sanver (2004). See also Section 4.2.↩︎

6. Throughout the paper we represent linear orders with column vectors. The interpretation is as follows: in the preference list of woman 1, man 5 is her first choice, man 6 is her second choice and man 4 is her worst choice.↩︎

7. Minimal optimality is a property much weaker than stability: a matching \(\mu\) is minimally optimal if there is at least an individual who does not get her/his worst choice under \(\mu\). A matching mechanism is minimally optimal if it only selects minimally optimal matchings.↩︎

8. Weak Pareto optimality is a property weaker than stability and stronger than minimal optimality: a matching \(\mu\) is weak Pareto optimal if there is no other matching \(\mu'\) that makes all the individual better off. A matching mechanism is weakly Pareto optimal if it only selects weakly Pareto optimal matchings.↩︎

9. A partition of a nonempty set \(X\) is a set of nonempty pairwise disjoint subsets of \(X\) whose union is \(X\).↩︎

10. \(G^*\) is known by group theorists as the wreath product of \(\mathrm{Sym}(\ldbrack n \rdbrack)\) with the cyclic group of order 2. Note also that \(G^*=\langle G,\mu\rangle=G\rtimes \langle\mu\rangle\), where \(\mu\) is, for instance, the element of \(G^*\) that switches, for every \(x\in W=\ldbrack n \rdbrack\), the woman \(x\) and the man \(x+n\).↩︎

11. The number \(R\) depends of course on \(U\) and \(P\). We avoid more precise notation since \(U\) and \(P\) are always clear from the context.↩︎

12. It is customary to denote by 1 the trivial group, by \(C_n\) the cyclic group of order \(n\), and by \(S_n\) the group \(\mathrm{Sym}(\ldbrack n \rdbrack)\).↩︎