Asymptotically stable matchings and evolutionary dynamics of preference revelation games in marriage problems

The marriage problem is a simple and basic model of two-sided matching markets which involves one-to-one matchings. Suppose that there are two sets of players $M$ and $W$, often referred to as men and women respectively. Each player has a preference relation defined over the other set and remaining single. A preference profile $P$ is a vector which consists of the preference relations of all players. A matching is said to be stable, if no player is worse off than to remain unmatched, and if no pair of a man and a woman prefer each other to their current partners. Gale and Shapley [1] formulated the marriage problem and showed that the set of stable matchings is always nonempty. In the proof, they presented the so-called deferred acceptance (DA) algorithm, which always yields a stable matching. They also showed the existence of the $M$-optimal stable matching: i.e. a stable matching that is preferred to all the other stable matchings by all men. Similarly, there exists the $W$-optimal stable matching.

In practice, a matching has to be determined based on the reported preferences, because a matchmaker can never know the true preferences of players. A matching algorithm induces the preference revelation game, a noncooperative game where players submit their preferences strategically. We refer to a preference profile submitted by the players as a report profile, in order to distinguish it from the true preference profile. A number of studies have investigated incentives of players to report their true preferences [2, 3, 4, 5, 6] and characterized the set of matchings resulting from the strategic reporting behavior [7, 8, 9, 10]. These studies considered centralized matching markets where participants submit their preferences to a clearinghouse based on which an algorithm generates the matching. Another line of research concerns decentralized markets and has analyzed dynamic processes in which matchings are updated in a pairwise manner [11, 12, 13, 14].

The literature on centralized markets often assumes that a true preference of each player is known to herself and fixed throughout the matching process. However several empirical works on school choice situations cast doubt on its plausibility. Dwenger et al. [15] concluded that participants in the university admissions centralized market in Germany chose to randomize their decisions. The preliminary results by Narita [16] and Grenet et al. [17] both suggest that preferences of players changed in time and learning was the prominent driver of those changes. The current paper explores the possibility of circumventing this problem by adopting an evolutionary uuapproach. The standard setting of game theory is that the game is played exactly once by fully rational players. The contrasting setting of evolutionary game theory [18, 19] is that players are not necessarily rational and their behavior changes in time through such processes as trial-and-error and social learning. Evolutionary dynamics of a game refers to such time evolution of the strategy profile. Since players learn their own and others’ preferences by experience, they need not be aware of their preferences when the process begins, unlike much of the literature on centralized markets.

In this paper, we theoretically investigate what kind of matchings will emerge through evolutionary dynamics of preference revelation games in marriage problems. We consider a class of continuous-time deterministic evolutionary dynamics which contains the famous replicator dynamics. We define the asymptotic stability of a matching, an analogue to the asymptotic stability of a fixed point in dynamical systems. When a matching is asymptotically stable, it is likely to be obtained at the equilibria of evolutionary dynamics. Furthermore, it turns out that an asymptotically stable matching may not exist, but when it does, it is also stable. The simulation results of the replicator dynamics are presented to demonstrate the dynamical robustness of an asymptotically stable matching against perturbation in the strategy profile. The asymptotic stability of a matching indicates the matching will be restored after another matching is realized due to sufficiently small changes in players’ reporting strategies. When a fixed point of a dynamical system is asymptotically stable, it intuitively means that sufficiently small perturbation results in a movement that goes back to the fixed point¹¹1Let $x^{*}$ be a fixed point of a system $\dot{x}=f(x)$. $x^{*}$ is Lyapunov stable if, for each $\epsilon>0$, there exists a $\delta>0$ such that if $\norm{x(0)-x^{*}}<\delta$ then $\norm{x(t)-x^{*}}<\epsilon$ for all $t\geq 0$. $x^{*}$ is attracting if there exists $\delta>0$ such that if $\norm{x(0)-x^{*}}<\delta$ then $\lim_{t\to\infty}x(t)=x^{*}$. $x^{*}$ is asymptotically stable if it is both Lyapunov stable and attracting [20]. . Our asymptotic stability of a matching is similar to the asymptotic stability in dynamical systems, but differs in that a focal state and perturbation are not in the same space. In matching problems, a focal state, a matching, is a point in the matching space, which is the set of all possible matchings. By contrast, perturbation corresponds to a change in the reporting strategy of a player, and players’ strategies are represented by a point in the strategy space.

This research contributes to matching theory in practical and theoretical manner. Firstly, we formulated the asymptotic stability of a matching, which characterize the matchings that emerge through evolutionary dynamics. An asymptotically stable matching is likely to be realized when players experiment or make mistakes occasionary. Furthermore we found that the asymptotic stability of a matching implies its stability. Thus the current paper suggests a novel practical strategy for market designers to implement stable matchings, which is to create a learning phase in which participants can try submitting various preferences and are informed of the would-be matchings many times over. Players would find reporting strategies that appropriately represent their true preferences during this learning phase. Accordingly an asymptotically stable and hence stable matching is realized. We emphasize that our argument does not neccesitate players’ initial awareness of their true preferences, unlike the literature. Secondly, we demonstrate how to employ evolutionary game theory in studying centralized matching markets, thereby opening doors to a novel area of research. Many directions can be taken: analytical research with machinery of evolutionary game theory, numerical analysis of evolutionary dynamics, and empirical work informed by such theoretical studies are all feasible.

The rest of the paper is organized as follows. Section 2 is the preliminaries, where formulation of marriage problems, preference revelation games, and some concepts from evolutionary game theory are presented. In the following section, we formulate the asymptotic stability of a matching. In section 4, we consider two instances of marriage problems and present simulation results of the replicator dynamics of preference revelation games. Section 5 is the discussion, and the concluding remark is in the last section.

In this section, we formulate asymptotic stability of a matching. When a matching is asymptotically stable, it will be restored after another matching is realized due to perturbation, which is a change in the reporting strategy of a player. Asymptotic stability of a matching differs from the asymptotic stability in dynamical systems in that a focal state and perturbation are not in the same space. Whereas a focal state is on the matching space, perturbation occurs in the strategy space. An evolutionary dynamics such as RD of equation (1) describes the time evolution of the strategy distributions in the mixed strategy space. A matching algorithm maps a point in the mixed strategy space to a set of matchings in the matching space. We utilize this relationship between the strategy space and the matching space, and define asymptotic stability of a matching through the asymptotic stability of a corresponding area in the mixed strategy space, where the conventional definition of the asymptotic stability in dynamical systems can be used.

First, we define a partial preimage of a matching $\mu$, a subset of the pure strategy space that corresponds to $\mu$. An obvious requirement for a partial preimage of $\mu$ is that any report profile in the set yields $\mu$ by the algorithm in use. In addition, we require the set to be a cartesian product of the subset of the each player’s pure strategy space. This is because players determine their strategy independently in preference revelation game. Formally, a partial preimage of a matching is defined as follows.

$H(\mu)$ is ”partial” in that it is included in the preimage of $\mu$ under $\Gamma$: i.e. $H(\mu)\subset\quantity{r\in S\mathrel{}\middle|\mathrel{}\Gamma(r)=\mu}$. There may exist multiple partial preimages for a matching. In particular, any subset of $H(\mu)$ is a trivial partial preimage of $\mu$. In later sections, we refer to a nontrivial one that is not included in any other partial preimage of $\mu$ as a non-included partial preimage of $\mu$.

Now, we formulate asymptotic stability of a matching $\mu$ using its partial preimage $H(\mu)=\prod_{i\in I}H^{i}(\mu)$. Let $\Theta(H(\mu))$ denote the subspace of the mixed strategy space spanned by $H(\mu)$:

Note that any mixed report profile in $\Theta(H(\mu))$ yields only $\mu$. Suppose that a mixed strategy profile $x$ is initially in $\Theta(H(\mu))$, and then sufficiently small perturbation drives the point $x$ out of $\Theta(H(\mu))$. While $x$ is not in $\Theta(H(\mu))$, the algorithm may now yield matchings other than $\mu$. If $\Theta(H(\mu))$ is asymptotically stable, $x$ moves back into $\Theta(H(\mu))$ after some time, yielding only $\mu$. In short, $\mu$ will be restored after sufficiently small perturbation, if $\Theta(H(\mu))$ is asymptotically stable. As described in the previous section, under payoff-positive selection dynamics, $\Theta(H(\mu))$ is asymptotically stable if and only if $H(\mu)$ is closed under weakly better replies (cuwbr). In this way, we formulate asymptotic stability of a matching.

An asymptotically stable matching does not always exist, but if it does, it is also stable.

So far, we have discussed game dynamics of preference revelation games theoretically. In this section, we take two instances marriage problems, and present numerical simulations of replicator dynamics (RD) of preference revelation games. We pay particular attention to matchings that will be realized after report profiles evolve for some time according to RD. We consider marriage problems with three players on each side: i.e. $M=\quantity{m_{1},m_{2},m_{3}}$ and $W=\quantity{w_{1},w_{2},w_{3}}$. It is assumed that male players do not use weakly dominated strategies, which means they always report truthfully. Thus in this section, the set of strategic players is $I=W$. All the possible reports are shown in tables 1, where $(m_{1},m_{2},m_{3})$ denotes a preference of a woman who prefers $m_{1}$ to $m_{2}$, and $m_{2}$ to $m_{3}$. We will refer to a pure strategy by its label shown in the tables. The pure strategy space of the game is $S=\quantity{W1,W2,\dots,W6}^{3}$. It is assumed in this section that all players are acceptable. RD of equation (1) were numerically solved with the initial condition where all pure strategies evenly exist: i.e. $x^{i}_{0}=\quantity(\frac{1}{6})_{h\in S^{i}}$ for all $i\in I$. The DA algorithm with men proposing was used in obtaining a matching from a report profile, and matchings were mapped to payoffs by the utility function $u_{\text{conv}}=(25,10,1)$. For example, when a replicator is paired with the most preferable man, its payoff is 25. We say the state $x$ is at the stationary state at time $t$, if the maximum changes in $x^{i}$ during the last few calculation steps were sufficiently small⁵⁵5Let the state at time $t$, which corresponds to the $n$-th calculation point, be $x_{n}$. Let the state at $i$ calculation steps before $x_{n}$ be $x_{n-i}$. We say $x$ is at the stationary at time $t$, if $\max_{i\in I}(\absolutevalue{x^{i}_{n-i}-x^{i}_{n-i-1}})<10^{-5}$ for $i\in\quantity{0,\dots,3}$. . Furthermore, we say that a pure strategy survived when its population share at the stationary state was more than 0.1%.

The marriage problems we investigated are $(M,W,P_{1})$ and $(M,W,P_{2})$, where

The preference of $m_{1}$ is shown first in a preference profile, that of $m_{2}$ second and so on, the last being the preference of $w_{3}$. In the first problem with $P_{1}$, the $M$-optimal and $W$-optimal stable matchings are

Under $\mu^{M}_{1}$, $m_{1}$ is paired with $w_{1}$, $m_{2}$ paired with $w_{2}$, and $m_{3}$ paired with $w_{3}$. The $M$-optimal and $W$-optimal stable matchings do not coincide, but no woman has the incentive to falsify assuming others are truthful⁶⁶6Theorem 1 of Gale and Sotomeyer [4] asserts that there is at least one woman who will be better off by falsifying, if there is more than one stable matching. In the problem with $P_{1}$, no woman has the incentive to misreport even though there are multiple stable matchings, because we assumed that all players were acceptable. . In the second problem⁷⁷7$P_{2}$ was taken from the proof of Theorem 3 in Roth [2]. with $P_{2}$, the $M$-optimal and $W$-optimal stable matchings are

Under $M$-optimal stable algorithms, at least one woman has the incentive to falsify so that $\mu^{W}_{2}$ instead of $\mu^{M}_{2}$ is obtained. For instance, $\mu^{W}_{2}$ is realized if $w_{2}$ falsely reports $W6$.

Before presenting the simulation results, we check if asymptotically stable matchings exist in the two marriage problems⁸⁸8 In practice, we first simulated replicator dynamics and then studied asymptotically stable matchings referring to the simulation results. . In the first problem with $P_{1}$, the following set is a non-included partial preimage of $\mu^{M}_{1}$ under $M$-optimal stable algorithms:

$H(\mu^{M}_{1})$ turns out to be cuwbr, and thus $\mu^{M}_{1}$ is asymptotically stable, as shown in B.1. In the proof, we essentially checked if $\alpha(H(\mu^{M}_{1}))$ of equation (4) satisfied the definition of cuwbr with payoff tables, which was made workable due to the assumption of $I=W$. In the second problem with $P_{2}$, one finds two non-included partial preimages of $\mu^{W}_{2}$ under $M$-optimal stable algorithms:

The following relations hold for $H_{1}$ and $H_{2}$, where $H^{i}$ satisfies $H=\prod_{i\in I}H^{i}$:

Equations (14) and (15) indicate that neither $H_{1}$ nor $H_{2}$ is cuwbr. Indeed, one can show that there is no partial preimage of $\mu^{W}_{2}$ that is cuwbr, implying that $\mu^{W}_{2}$ is not asymptotically stable. Details on the proofs are in B.2 and B.3. In addition, there is no partial preimage of $\mu^{M}_{2}$ that is cuwbr, since $w_{1}$’s reporting $W1$ earns a higher payoff when others are reporting truthfully. Therefore, no asymptotically stable matching exists in the second problem.

In figures 1, the time evolution of $x^{i}$ and the resulting matchings are presented. In the first problem (figure 1), truthful reportings of all players have survived. All the possible report profiles at the stationary state result in the $M$-optimal stable matching $\mu^{M}_{1}$. One can see that although the values of some $x^{i}_{h}$ changed after perturbation (e.g. $x^{w_{1}}_{W1}$ at $t=2$), the set of surviving reports were always $H(\mu^{M}_{1})$, and the resulting matching remained $\mu^{M}_{1}$ regardless of the perturbations. This demonstrates the asymptotic stability of $H(\mu^{M}_{1})$ and thus $\mu^{M}_{1}$. In the second problem (figure 1), truthful reporting went extinct in the $w_{2}$ population. All the possible report profiles at the stationary state result in the $W$-optimal stable matching $\mu^{W}_{2}$, not $\mu^{M}_{2}$. However, while the set of surviving reports was $H_{1}(\mu^{W}_{2})$ at $t=3$, it changed to $H_{2}(\mu^{W}_{2})$ as the result of the perturbation at $t=3$. In short, even though $\mu^{W}_{2}$ seemed robust against the perturbations, it is not asymptotically stable in our definition. We will explore this situation in the next section.

To conclude this section, we briefly discuss the simulation results. Firstly, the selection favored only one matching in both cases, even though several strategies coexisted in many player populations at the stationary state. This is not due to the choice of the preference profiles. Assuming that three players are present on each side and all players are acceptable, there are $6^{6}$ possible preference profiles. We fixed the preference of $m_{1}$ without loss of generality, and conducted the simulation of RD for all $6^{5}$ possible preference profiles in case of $I=W$. Except the 18 cases (0.2%) where $x$ kept fluctuating and thus we could not determine the final states, only one matching was possible at the final state in all instances. These observations imply that it is natural to consider the asymptotic stability of a matching. Secondly, the simulation results were consistent with previous research on the incentives of players. In the first problem, where no woman has the incentive to misreport, the truthful reporting strategies of women survived. In the second problem, at least one woman has the incentive to falsify, and only the false reporting survived in the $w_{2}$ population accordingly. Still, $w_{2}$ truthfully reported the most preferable men, which is consistent with the result of Roth [2] that no woman has the incentive to falsify her most preferred man.

The simulation result of the second problem $(M,W,P_{2})$ in figure 1 suggests that the $W$-optimal stable matching $\mu^{W}_{2}$ was restored after small perturbations were given, even though $\mu^{W}_{2}$ is not asymptotically stable. What equations (14) and (15) tell us about two non-included partial preimages of $\mu^{W}_{2}$ are that $H_{1}$ is not cuwbr because $W5$ of $w_{2}$ is a weakly better reply to some $x\in\Theta(H_{1})$, and that $H_{2}$ is not cuwbr because $W2$ of $w_{1}$ is a weakly better reply to some $x\in\Theta(H_{2})$. Suppose that the current population state is $x\in\Theta(H_{1})$, and some replicators in $w_{2}$ population start to use $W5$. This would move the population state to $x^{\prime}\in\Theta(H^{\prime})$, where

If we start from $x\in\Theta(H_{2})$ and some replicators in $w_{1}$ population come to use $W2$, the population state would also get $x^{\prime}\in\Theta(H^{\prime})$. In addition, one can show that $x^{\prime}\in\Theta(H^{\prime})$ evolves into another state $x^{\prime\prime}\in\Theta(H_{1}\cup H_{2})$, where only $\mu^{W}_{2}$ is obtained, as long as selection dynamics are payoff-positive⁹⁹9Details are in C. . Therefore $\mu^{W}_{2}$ will in fact be restored after small perturbations are given.

In the second problem with $P_{2}$, $\mu^{W}_{2}$ is not asymptotically stable, even though it will be restored after small perturbations. The essentials behind this confusing situation are two non-included partial preimages of $\mu^{W}_{2}$, one of which contains a weakly better reply to the other and vice versa. All partial preimages are not cuwbr and thus $\mu^{W}_{2}$ is not asymptotically stable by our definition, but still, a mixed strategy profile $x$ moves only within partial preimages of the same matching. In order to characterize the robustness of $\mu^{W}_{2}$, we propose a weaker property of a matching, quasi-asymptotic stability:

When $n=1$, it is equivalent to the asymptotic stability of Definition 2. $\mu^{W}_{2}$ is quasi-asymptotically stable with $\quantity{H_{1},H_{2}}$. We presume the quasi-asymptotic stability portrays some kind of dynamical stability of a matching similar to the asymptotic stability, but we have not yet been able to neither prove it nor find a counterexample.

In the current paper, preference relations are described by numerical values. Obviously, the payoff values must satisfy $u^{i}_{1}>\dots>u^{i}_{n}$, but still there are countless candidates for the utility function. To examine whether the choice of the utility function affects the dynamics, we conducted simulations of RD in the two marriage problems with two other utility functions, $u_{\text{lin}}=(15,10,5)$ and $u_{\text{conc}}=(5\sqrt{3},5\sqrt{2},5)$. The utility function used in the preceding section was $u_{\text{conv}}=(25,10,1)$. $u_{\text{conv}}$, $u_{\text{lin}}$ and $u_{\text{conc}}$ are convex, linear and concave, respectively. In the first problem with $P_{1}$, the dynamics of $x^{i}$ did not seem to be affected by the choice of the utility function, but their time scales differed. The dynamics with the linear utility function is shown in figure 2. In the second problem with $P_{2}$, transient dynamics slightly varied and the share of $W1$ in the $w_{1}$ population at the last state was also affected by the choice of the utility function. Figure 2 shows the dynamics with the concave utility function. Nevertheless, strategies that survived remained the same regardless of the utility function. Our analysis have mainly focused on the last states of dynamics and the matchings which were obtained there. Thus, in view of the observations above, we expect our simulation results to be independent on the choice of the utility function.

Although the literature on centralized matching markets often assumes that a true preference of each player is known to herself and fixed throughout the matching process, several empirical results [15, 16, 17] cast doubt on the assumption. To circumvent the problem, evolutionary dynamics of preference revelation games are considered. We formulated the asymptotic stability of a matching, which indicates the dynamical robustness of the matching against sufficiently small changes in players’ reporting strategies. We showed that the asymptotic stability of a matching implies its stability, thereby contributing a practical suggestion on how to obtain stable matchings in centralized markets: by having a learning phase during which players find reporting strategies that suit their true preferences through trial and error, an asymptotically stable and hence stable matching would be obtained. Note that our insight does not assume players’ initial awareness of their true preferences, unlike much of the literature.

We believe the current paper lays a foundation for dynamical approach to centralized matching markets with evolutionary dynamics of preference revelation games, and there is plenty of room for future research. One issue that should be tackled is the difficulty in finding asymptotically stable matchings. We checked the asymptotic stability according to its definition, looking at payoff matrices, but this procedure quickly becomes unfeasible as the number of players increase. Our approach with continuous-time deterministic selection dynamics is applicable to wider range of problems, provided the payoff function is deterministic and thus payoffs are never determined randomly. We assumed preferences were strict and $M$-optimal stable algorithms were used, but players’ preferences need not be strict. When preferences are not strict, deterministic payoff functions can be constructed by employing matching algorithms that have deterministic tie-breaking rules. Our approach can also be adopted to many-to-one or many-to-many matching problems. In these cases, payoff functions are likely to be much complicated and straightforward analysis may get cumbersome. Directions for future research include analyses of other types of game dynamics, such as ones with mutations or on graphs, and search for connections between the asymptotic stability of a matching and stochastic stability analyzed in research on decentralized markets [12, 13, 14]. Another interesting topic would be a partial preimage of a matching. We introduced a partial preimage to formulate the asymptotic stability of a matching based on the concept, but a partial preimage itself may hold information that characterizes the matching. For instance, the cardinality of a non-included partial preimage is likely to reflect the likelihood that a matching is realized when all players randomly submit their reports.