Abstract
In the theory of two-sided matching markets there are two standard models: (i) the marriage model due to Gale and Shapley and (ii) the assignment model due to Shapley and Shubik. Recently, Eriksson and Karlander introduced a hybrid model, which was further generalized by Sotomayor. In this paper, we propose a common generalization of these models by utilizing the framework of discrete convex analysis introduced by Murota, and verify the existence of a pairwise-stable outcome in our general model.
Introduction
In the theory of two-sided matching markets there are two standard models: (i) the marriage model due to Gale and Shapley [11] and (ii) the assignment model due to Shapley and Shubik [28] . The former does not allow money or transferable utilities whereas the latter does (see Roth and Sotomayor [26] ). Our goal is to propose a common generalization of these models, and to verify the existence of a pairwise-stable outcome 1 in our model. Our model includes several well known special cases as shown in Fig. 1 .
Introduction
In the marriage model there are sets of men and women of the same size, and each person has a strict preference order on persons of the opposite gender. A matching is a set of disjoint man-woman pairs. Gale and Shapley [11] introduced the concept of pairwise-stability 2 of a matching, and gave a constructive proof 1 Several concepts of stability such as pairwise-stability, corewise-stability, and setwise-stability have been discussed for the marriage and assignment models, and their extensions. This paper concentrates on the most elementary concept, pairwise-stability, since a special case of our model, the many-to-many marriage model, may not have a setwise-stable matching [30] . 2 In the marriage model the three concepts of pairwise-stability, corewise-stability, and setwisestability are equivalent.
Introduction
of the existence of such a matching (also see Sotomayor [29] ). Since Gale and Shapley's paper a large number of variations and extensions have been proposed, and algorithmic progress has also been made (see e.g., Gusfield and Irving [13] and Baïou and Balinski [2] ). Recently, Fleiner [7] extended the marriage model to the framework of matroids, and showed the existence of a pairwise-stable outcome. The preference of each person in his model can be described by a linear utility function on a matroidal domain. Eguchi and Fujishige [5] extended this formulation to a more general one in terms of discrete convex analysis, which was developed by Murota [17, 18, 20] as a unified framework in discrete optimization. In the Eguchi-Fujishige model, the preference of each agent is described by a discrete concave function, called an M -concave function 3 . The Eguchi-Fujishige model is also a concrete example (in terms of utility functions) of the generalized models (in terms of choice functions with substitutability) by Roth [24, 25] , Sotomayor [30] , Alkan and Gale [1] , and Fleiner [8] , because an M -concave function defines a choice function with substitutability (see Lemma 5.2) .
Introduction
In the other standard model, the assignment model, if a man and a woman form a partnership, then they obtain a total profit that may be divided into payoffs. An outcome consists of payoff vectors for men and women, and a matching. Shapley and Shubik [28] showed that the core 4 of this model is nonempty. Various extensions of this model have also been proposed. Sotomayor [31] showed the existence of a pairwise-stable outcome in a many-to-many model in which each agent is permitted to form multiple partnerships with agents of the opposite set without multiple partnerships of each pair 5 model due to Eriksson and Karlander [6] and Sotomayor's generalization [32] 8 . In the Eriksson-Karlander model, the set of agents is partitioned into two categories, one of "rigid" agents and the other of "flexible" agents. Rigid agents do not receive side payments, as in the marriage model, while flexible agents do, as in the assignment model. Sotomayor [32] investigated this hybrid model and gave a non-constructive proof of the existence of a pairwise-stable outcome.
Introduction
We propose a common further generalization that preserves the existence of a pairwise-stable outcome. Our model has the following features:
Introduction
• the preference of agents on each side is expressed by a discrete concave utility function, called an M -concave function,
Introduction
• each agent is permitted to form partnerships with more than one agent on the opposite side,
Introduction
• each pair is permitted to form multiple partnerships,
Introduction
• the set of pairs is arbitrarily partitioned into a set of flexible pairs and a set of rigid pairs.
Introduction
An M -concave function has nice features as a utility function, as we shall discuss in the next section. Our main result is that our model always has a pairwise-stable outcome. Corollaries are the existence of pairwise-stable outcomes in the abovementioned special cases of our models (see Fig. 1 ). Although the present work is motivated by theoretical considerations, we believe it will contribute toward reinforcing the applicability of the two-sided matching market models.
Introduction
This paper is organized as follows. Section 2 explains M -concavity together with its properties and gives characterizations of pairwise-stability of the marriage model and the assignment model in terms of utility functions. Section 3 describes our model based on discrete convex analysis. Section 4 shows that several existing models are special cases of our model. Section 5 proposes an algorithm for finding a pairwise-stable outcome and prove its correctness, which shows our main theorem.
Preliminaries

M -Concavity
Let E be a nonempty finite set, and let Z and R be the sets of integers and reals, respectively. Let Z E be the set of integral vectors x = (x(e) : e ∈ E). Also, let 8 The three concepts of stability are equivalent in their models.
The Marriage Model and the Assignment Model
In this subsection we characterize pairwise-stability of the marriage model and the assignment model in terms of utility functions. These characterizations will be useful to understand pairwise-stability in our model. Let M and W denote two disjoint sets of agents and E = M ×W . Agents in M and W are interpreted as men and women, respectively. To each pair (i, j) ∈ E, a pair (a ij , b ij ) ∈ R 2 is associated. Here a ij and b ij are interpreted as profits of i and j in the assignment model. And they define preferences in the marriage model: man i ∈ M prefers j 1 to j 2 if a ij 1 > a ij 2 , and i is indifferent between j 1 and j 2 if a ij 1 = a ij 2 (similarly, the preferences of woman j ∈ W are defined by b ij 's). We assume that a ij > 0 if j is acceptable to i, and a ij = −∞ otherwise, and b ij > 0 if i is acceptable to j, and b ij = −∞ otherwise. Let {0, 1} E denote the set of all 0-1 vectors x on E, i.e., x ij = 0 or 1 for all (i, j) ∈ E. Define two aggregated utility functions f M for M and f W for W as follows: for all
The Marriage Model and the Assignment Model
As shown in Example 1, f M and f W are M -concave.
The Marriage Model and the Assignment Model
We now consider the marriage model. A matching is a subset of E such that every agent appears at most once. Given a matching X, i ∈ M (respectively j ∈ W ) is called unmatched in X if there exists no j ∈ W (resp. i ∈ M ) with (i, j) ∈ X. A matching X is called pairwise-stable
The Marriage Model and the Assignment Model
The above-defined pairwise-stability in the marriage model can also be characterized in terms of utility functions f M and f W given by (2.1) and (2.2). Let 1 denote 10 Here we consider weak pairwise-stability for a variation in which indifference is allowed.
The Marriage Model and the Assignment Model
Note that strong pairwise-stability is defined by the conditions (m1), (m2), and (m3 ) [ 
The Marriage Model and the Assignment Model
This characterization can be interpreted as follows. We note that a 0-1 vector x satisfying (2.4) and (2.5) must be a matching since
The Marriage Model and the Assignment Model
For a matching x, condition (2.4) (resp. (2.5)) says that each man (resp. woman) selects one of the best partners among partners in z M (resp. z W ). Therefore, (2.3) guarantees that there is no pair whose members prefer each other to their partners in x or to being alone in x. Conversely, for a pairwise-stable matching x, z M can be constructed as follows. Set z M (i, j) = 0 for all pairs (i, j) ∈ E such that i prefers j to his partner or to being alone in x (note that by pairwise-stability of x, j does not prefer i to her partner or to being alone in x), and set z M (i, j) = 1 otherwise. Similarly, z W can be constructed from x. Then, (2.3)∼(2.5) hold.
The Marriage Model and the Assignment Model
The assignment model allows side payments, which is not the case for the marriage model. An outcome is a triple consisting of payoff vectors q = (
The Marriage Model and the Assignment Model
, and a subset X ⊆ E, denoted by (q, r; X). An outcome (q, r; X) is called pairwise-stable if (a1) X is a matching,
The Marriage Model and the Assignment Model
where 0 denotes a zero vector of an appropriate dimension and p ij (= b ij − r j = q i − a ij ) means a side payment from j to i for each (i, j) ∈ X. The pairwisestability says that no pair (i, j) ∈ X will be better off by forming a partnership. Shapley and Shubik [28] proved the existence of a pairwise-stable outcome by linear programming duality and integrality. The maximum weight bipartite matching problem with weights (a ij + b ij ) and its dual problem are formulated as linear programs:
The Marriage Model and the Assignment Model
Recall that the primal problem has an integral optimal solution, a matching. Thus, (q, r; X) is pairwise-stable if and only if x = χ X , q and r are optimal solutions of the above dual problems, because (a1) and (a4) require primal and dual feasibility and because (a2) and (a3) A pairwise-stable outcome (q, r; X) gives x = χ X together with p satisfying (2.6) and (2.7) by putting p ij = b ij − r j for all (i, j) ∈ E. Conversely, x = χ X and p satisfying (2.6) and (2.7) lead us to a pairwise-stable outcome (q, r; X) such that q i = a ij + p ij and r j = b ij − p ij for all (i, j) ∈ X and q i = 0 (resp. r j = 0) for all i (resp. j) unmatched in X.
Model Description and the Main Theorem
Let M and W denote two disjoint sets of agents and E be a finite set. In our model, utilities (in monetary terms) of M and W over E are, respectively, described by Mconcave functions
Model Description and the Main Theorem
In the exemplary models described in Sections 2.2 and 4, E = M ×W , and f M and f W can be regarded as aggregations of the utilities of M -agents and W -agents (see Remark 1 given below). We assume that E is arbitrarily partitioned into two subsets F (the set of flexible elements) and R (the set of rigid elements) 13 . We also assume that f M and f W satisfy:
Model Description and the Main Theorem
(A) Effective domains dom f M and dom f W are bounded and hereditary, and have 0 as a common minimum point, where heredity means that
Model Description and the Main Theorem
. Heredity implies that each agent can arbitrarily decrease the multiplicity of partnerships he is in part of without permission from his partners, similarly as in other two-sided matching market models. Let z be an integral vector such that
Model Description and the Main Theorem
Condition (3.1) states that there are no side payments for rigid elements. Condition (3.2) replaces the upper bound vector 1 in (2.4) by z. Obviously, if E = R then our model includes the marriage model, and if E = F then it includes the assignment model. Before giving our main result, we give two illustrations of our model.
Example 3: We consider the problem of allocating dance partners between set
We assume that they have the following preferences:
Example 3: We consider the problem of allocating dance partners between set
• everyone wants to dance as many times as possible, up to four times,
Example 3: We consider the problem of allocating dance partners between set
• w 1 and w 2 are indifferent for m 2 ,
Example 3: We consider the problem of allocating dance partners between set
• every woman wants to dance with m 1 and m 2 as equally as possible. 13 In the Eriksson-Karlander model [6] , M and W are, respectively, partitioned into {M F , M R } and {W F , W R }, and we have
Example 3: We consider the problem of allocating dance partners between set
Denoting by x ij the number of times m i and w j dance together, we can describe their preferences by the following four utility functions:
Example 3: We consider the problem of allocating dance partners between set
Then, the two aggregated utility functions
Example 3: We consider the problem of allocating dance partners between set
concave functions defined by the laminar families
Example 3: We consider the problem of allocating dance partners between set
2)} and 
respectively (see Example 2), namely M -concave functions, where the pairs (m i , w j ) are abbreviated by (i, j). Thus, the problem can be formulated by our model with
Our main result is the following theorem about the existence of an f M f Wpairwise-stable solution in our model. A proof of the main theorem will be given in Section 5. 
Remark 1: In our model, each of M and W is regarded as a single aggregate agent but can be interpreted as a set of agents. Let
M = {1, · · · , m}, W = {1, · · · , w}, and E = M × W . Also, define E i = {i} × W for all i ∈ M , and E j = M × {j} for all j ∈ W . Suppose that each agent i ∈ M has an M -concave utility function f i : Z E i → R ∪ {−∞} on E i , and that each agent j ∈ W has an M -concave utility function f j : Z E j → R ∪ {−∞} on E j . Aggregations f M (x) = i∈M f i (x| E i ) and f W (x) = j∈W f j (x| E j ) in x ∈ Z E are also M -dom f M ∪ dom f W ⊆ {y ∈ Z E | 0 ≤ y ≤ z}. One can see that x ∈ dom f M ∩ dom f W is an f M f W -x ∈ arg max{f M [+p](y) | y| R M ≤ z M }, x ∈ arg max{f W [−p](y) | y| R W ≤ z W }.(e) ≥ 0 because f M [+p](x) ≥ f M [+p](x − χ e ) and f M (x) = f M (x − χ e ) = 0. Remark 4: When E = F , x ∈ dom f M ∩ dom f W is an f M f W -arg max(f 1 + f 2 ) = arg max(f 1 [+p * ]) ∩ arg max(f 2 [−p * ]). Since (A) guarantees that dom (f M + f W ) is
Existing Special Models
The marriage model and the assignment model are special cases of our model as described in Section 2.2. In this section we show that several extensions of these models are also special cases of ours.
Extensions of the Marriage Model
Fleiner [7] has generalized the marriage model to matroids. A triple M = (E, I, >) is called an ordered matroid, if I is the family of independent sets of a matroid on E and > is a linear order on E. An element e ∈ E is dominated by X ⊆ E if e ∈ X or there exists Y ∈ I such that Y ⊆ X, {e} ∪ Y ∈ I and e > e for all e ∈ Y . The set of elements dominated by X is denoted by D M (X). Given two ordered matroids
Extensions of the Marriage Model
The marriage model (M, W, {a ij }, {b ij }) without indifference can be formulated as the matroidal model. Let E be the set of pairs (i, j) with a ij , b ij > 0. Also, define
Extensions of the Marriage Model
are the families of independent sets of matroids. Then, X is a matching if and only if X ∈ I M ∩ I W . By defining linear orders > M and > W on E so that (i, , j) . Hence, the set of M M M W -kernels coincides with the set of pairwise-stable matchings. The matroidal model can easily be modified so that indifference is allowed.
Extensions of the Marriage Model
Eguchi and Fujishige [5] proposed a model based on M -concavity, which is a restriction of our model in which E = R and dom 
Extensions of the Marriage Model
which are M -concave by Example 1. From basic theorems in matroid theory, we can show that a subset X of E is an M M M W -kernel if and only if it is f M f Wpairwise-stable for the M -concave functions specified by (4.1).
Extensions of the Marriage Model
Our model with E = R includes all of the above-mentioned models.
Extensions of the Assignment Model
Sotomayor [33] proposed an extension of the assignment model in which M and W denote sets of firms and workers, respectively, and each firm i ∈ M has a quota of 
Extensions of the Assignment Model
It is in the core if it is feasible and q(M ) + r(W ) ≥ P (M , W ) for all coalitions M ⊆ M and W ⊆ W . She showed that an element of the core is derived from a dual optimal solution of the transportation problem:
Extensions of the Assignment Model
which implies the nonemptiness of the core. Therefore, in our context, by defining M -concave functions f M and f W as
Extensions of the Assignment Model
an f M f W -pairwise-stable solution x, together with p, gives a money allocation (q, r) in the core. Such an allocation (q, r) is defined by
Extensions of the Assignment Model
However, the converse does not necessarily hold, as the core may strictly contain the set of dual optimal solutions (see [ 
33, Example 2]).
Kelso and Crawford [15] introduced a many-to-one labor market model in which the profit function of each firm satisfies gross substitutability and the utility function of each worker is strictly increasing (not necessarily linear) in salary. Danilov, Koshevoy, and Murota [4] provided, for the first time, a model that is based on discrete convex analysis. Our model is closely related to these models.
A Hybrid Model
Eriksson and Karlander [6] proposed a hybrid model of the marriage model and the assignment model. In this model, agents are partitioned into two categories, called flexible agents and rigid agents, that is, M and W are partitioned into (M F , M R ) and (W F , W R ), and F and R are defined by
A Hybrid Model
A generalization of the hybrid model was also given by Sotomayor [32] . Here, we adopt the notion of pairwise-stability of her generalized version. An outcome (q, r; X) is called pairwise-stable if (h1) X is a matching,
A Hybrid Model
When E = R (resp. E = F ), Conditions (h1)∼(h6) are obviously equivalent to (m1)∼(m3) (resp. (a1)∼(a4)). As is seen from the discussion in Section 2.2, our model includes this hybrid model as a special case.
Proof
In this section we prove our main theorem, Theorem 3.1. We give a constructive proof by combining two algorithms, one for the marriage case and the other for the assignment case. We divide our arguments into three parts that deal with (i) a variant of the marriage model,
Proof
(ii) a variant of the assignment model, and (iii) a combination of the two.
Proof
Readers will easily understand the argument for the general model (iii) by first understanding the algorithms for (i) and (ii). The algorithm for (i) is interesting in its own right as it is a natural generalization of the Gale-Shapley algorithm [11] . On the other hand, the other parts of our constructive proof are rather technical; for example, the algorithm for (ii), called a successive shortest path algorithm, is a generalization of an algorithm for a network flow problem.
The Marriage Case
For a given partition (F, R) we give an algorithm for finding
The Marriage Case
2)
The Marriage Case
Here it should be noted that (F, R) can be any partition of E and that if E = R and if there exist z M , z W ∈ Z E satisfying (3.2), (5.1), and (5.2) with
The Marriage Case
Hence the algorithm proposed below can find an f M f W -pairwise-stable solution with respect to (∅, E).
The Marriage Case
We first state three fundamental lemmas, which hold without Assumption (A). 
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
Proof. (a): Let x 2 be a minimizer of {x 1 
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
Suppose, to the contrary, that there exists e ∈ E with min{z 2 (e), x 1 (e)} > x 2 (e). Then e ∈ supp
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
(5.4) If e = 0, then x 1 (e ) < x 2 (e ) ≤ z 2 (e ) ≤ z 1 (e ). Hence x 1 − χ e + χ e ≤ z 1 , which implies f (x 1 ) ≥ f (x 1 − χ e + χ e ). This, together with (5.4), yields f (x 2 ) ≤ f (x 2 + χ e − χ e ). Moreover, since z 2 (e) > x 2 (e), we have x 2 = x 2 + χ e − χ e ≤ z 2 . It follows that x 2 ∈ arg max{f (y) | y ≤ z 2 } and x 2 (e ) ≥ min{z 2 (e ), x 1 (e )} if e = 0, which contradicts the minimality of
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
Suppose, to the contrary, that there exists e ∈ E with min{z 2 (e), x 1 (e)} > x 2 (e). Then e ∈ supp
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
(5.5)
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
Since x 2 (e) < z 2 (e), we have
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
This, together with (5.5), yields f (x 1 ) ≤ f (x 1 − χ e + χ e ). Obviously
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
However, this contradicts the minimality of x 1 because x 2 (e ) ≥ min{z 2 (e ), x 1 (e )} if e = 0. Proof. Assume to the contrary that the assertion is not satisfied. Let x be a point minimizing {y(e) − z 2 (e) | e ∈ supp + (y − z 2 )} in y subject to y ≤ z 1 and f (y) > f (x). By the assumption, there exists e ∈ E with x (e) > z 2 (e) > x(e). By (M ) for x , x, and e, there exists e ∈ supp
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
Since x + χ e − χ e ≤ z 2 , we have f (x) ≥ f (x + χ e − χ e ), which implies f (x ) ≤ f (x − χ e + χ e ). Obviously, x − χ e + χ e ≤ z 1 , However, this contradicts the minimality of x because if e = 0, then z 2 (e ) ≥ x(e ) > x (e ). ((i, j) ) represents firm i's quota of time units for hiring worker j. This is a proposal step. Next is a rejection step. Given the offer of firms, workers maximize the aggregated utility f W among possible allocations less than or equal to x M . For workers' choice x W and e = (i, j), if x W (e) < x M (e) then z M (e) is updated as x W (e) because worker j does not supply more than x W (e) time units to firm i. Our algorithm iterates the above two steps until x M = x W .
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
To describe our algorithm in more detail, we assume that we are initially given
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
2), (5.1) and the following:
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
We can easily compute these initial vectors by setting z M = z| R , z W = 0, and finding x M and x W such that
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
Here is our algorithm.
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
Step
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
Step 2.
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
Step 3. For each e∈R with x M (e)>x W (e), set z M (e) := x W (e), z W (e) := z(e) 15 .
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
Step 4. If
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
. Else go to Step 1.
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
From (A), x M and x W are well-defined within the effective domains and G GS terminates after at most e∈R z(e) iterations, because e∈R z M (e) strictly decreases at each iteration. In order to show that the outputs of G GS satisfy (3.2), (5.1), (5.2), and (5.3), we establish two lemmas. Let us assume that x
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
M , and z 
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
Because of the way in which we modified z M , z W , and x M , we have
Lemma 5.1 ([19]): Let f : Z E → R ∪ {−∞} be an M -concave function and U be a nonempty subset of E. Define the function f
The following is a by-product of Theorem 5.6. 
The Assignment Case
In this subsection we explain a successive shortest path algorithm (SSP) for finding a maximizer of f M +f W . It is a modified version of an algorithm given by Moriguchi and Murota [16] . As discussed in Remark 4, SSP finds an f M f W -pairwise-stable solution with respect to (E, ∅). We recall that SSP is used as a basic procedure for finding an f M f W -pairwise-stable solution for our general case.
The Assignment Case
Before describing SSP, we state several known results on M -concave functions.
The Assignment Case
. Functionf is called an M-concave function and can be characterized by the following exchange property 16 [17, 18] :
The Assignment Case
(M) for all x, y ∈ domf and all e ∈ supp
The Assignment Case
In particular, an M-concave function is also M -concave. We denote
The Assignment Case
Thus, the problem of finding an f M f W -pairwise-stable solution with respect to (E, ∅) is equivalent to that of finding a maximizer off M +f W . The maximizers of an M-concave function have a useful characterization
17
. [20] . 17 The sum of two M-concave functions is not M-concave in general. So we need a sophisticated characterization for the maximizers of the sum of two M-concave functions (see Theorem 3.2). 
(M) is written as (−M-EXC) in
Now, we return to explaining SSP. Letx M andx W be arbitrary maximizers of f M andf W , respectively. We construct a directed graph G = (Ê, A) and an arc length ∈ R A as follows. Arc set A has two disjoint parts: 14) and ∈ R A is defined by
(M) is written as (−M-EXC) in
The length function is nonnegative due to Theorem 5.8. For a set S of specified source vertices ofÊ, let d :Ê → R ∪ {+∞} denote the shortest distances from S to all vertices in G with respect to . Then, for all arcs a = (e, e ) ∈ A
(M) is written as (−M-EXC) in
Let t be an arbitrary vertex ofÊ reachable from S, and definep ∈ RÊ byp(e) = min{d(e), d(t)} for all e ∈Ê. It follows from the nonnegativity of that for all arcs a = (e, e ) ∈ A (a) +p(e) −p(e ) ≥ 0.
(M) is written as (−M-EXC) in
The above system of inequalities is equivalent tô
(M) is written as (−M-EXC) in
for all e, e ∈Ê, which is further equivalent tô
(M) is written as (−M-EXC) in
by Theorem 5.8. Note that for each arc a = (e, e ) ∈ A, p (a) = (a)+p(e)−p(e ) is the length of a in the directed graph defined in the same way as above forf
(M) is written as (−M-EXC) in
Also note that p (a) = 0 for all arcs a in a shortest path from S to t.
(M) is written as (−M-EXC) in
Let P be a shortest path from S to t in G with the minimum number of arcs. Since p (a) = 0 for all a ∈ P ,
(M) is written as (−M-EXC) in
Since P has the minimum number of arcs,
(M) is written as (−M-EXC) in
for all vertices e and e of P such that (e, e ) ∈ P and e appears earlier than e in P . Furthermore, arcs of A M and A W appear alternately in P . For otherwise, assume that two consecutive arcs (e, e ), (e , e ) ∈ P belong to A M . Then, by (M)
(M) is written as (−M-EXC) in
which yields (e, e ) + (e , e ) ≥ (e, e ), a contradiction to the minimality (with respect to the number of arcs) of P . Consequently, The above discussion leads us to Algorithm SSP for finding a maximizer of f M +f W described as follows.
The General Case
In this subsection, we give an algorithm for finding an f M f W -pairwise-stable solution for the general case, that is, an algorithm for finding
The General Case
The algorithm has the following two phases: (5.24) , and the following conditions:
The General Case
Note that if we further get (5.25), then
The General Case
Phase 1 relies on two algorithms, G GS and SSP described in the previous subsections (see Fig. 2 ). (a) For any x ∈ arg max{f (y) | y ≤ z 1 }, there exists e ∈ {0} ∪ E such that
The General Case
(b) For any x ∈ arg max{f (y) | y ≤ z 2 }, there exists e ∈ {0} ∪ E such that 
The General Case
Modify x W slightly if necessary, and go to G GS. Proof. Assertion (a) holds trivially. We will prove (b) and (c) by induction on the number of iterations from Step 1 through Step 6. We assume that (b) and (c) hold at the lth iteration, and we show that these statements also hold at the (l + 1)st iteration. We next show that Phase 1 terminates in a finite number of iterations. To show this, we state a lemma. In the sequel we assume that G GS in Phase 1 is executed as shown in Lemma 5.14. Then we have the following lemma. Proof. We first observe that Step 1 with x M | R = x W | R is executed finitely many times. Let e and e be the elements defined in the previous Step 6. By the discussion in Section 5.1, if G GS has inputs with x M | R = x W | R , then either z M (e) or z M (e ) is decreased by at least one. Since Steps 2∼6 preserve z M and z W , and since Step 1 does not increase z M , Step 1 with x M | R = x W | R is executed finitely many times, due to (A).
The General Case
We next observe that the cycle of Steps 1∼6 in which (5.26) (i.e., x M | R = x W | R ) is retained is executed consecutively finitely many times, by showing that either α = {x M (e ) − x W (e ) | e ∈ supp + (x M − x W )} is decreased by one or β = {x M (e ) | e ∈ R} is increased by one at each iteration. Let e, e and a be the elements defined in Step 6. If (5.26) holds just after Step 6, then we have one of the following two cases: (i) e ∈ T \ R, (ii) e ∈ R, a ∈ A M and e ∈Ê \ R. We first assume that either case (i) or the subcase of (ii) where e ∈ T \ R occurs. As we assumed on the basis of Lemma 5.14, Step 1 with (5.26) changes neither x M nor x W . Lemma 5.13 (b) yields that S ∩ T = ∅. Since there always exists a path from S to T , an execution of Steps 3∼5 reduces α by one. Furthermore,
The General Case
Step 6 does not increase α. We next assume that the other subcase of (ii) where e ∈ E \ T occurs. In this case, an execution of Steps 3∼5 decreases α by one and Step 6 increases α by one, and hence α remains the same. However β is increased by one. Thus, the cycle of Steps 1∼6 preserving (5.26) is executed consecutively finitely many times, due to (A).
The General Case
Hence, Phase 1 terminates in a finite number of iterations.
The General Case
Before explaining Phase 2, we state a lemma. 

{'paper_id': '16107414', 'title': 'A General Two-Sided Matching Market with Discrete Concave Utility Functions †', 's2_url': 'https://api.semanticscholar.org/CorpusID:16107414', 'source': 'S2ORC'}