Introduction
We study the many-to-one bipartite matching problem, where we have a bipartite graph G = ( A ∪ P , E ) G = (\mathcal{A} \cup\mathcal{P}, E) G = ( A ∪ P , E ) A \mathcal{A} A P \mathcal{P} P p ∈ P p \in\mathcal{P} p ∈ P q + ( p ) q^{+}(p) q + ( p ) p p p M M M M M M p p p q + ( p ) q^{+}(p) q + ( p ) M M M [2 ] or the one-sided preference list setting, and can be used to model different problems such as assigning applicants to jobs, students to courses [3 ] , papers to referees [4 ] , students to schools [5 ] , and rental inventories to customers [6 ] .
In certain applications, such as allocating students to courses or projects [7 , 8 , 9 ] , a course may require a minimum number of students to be assigned in order to be operational. This can be readily captured by associating a lower quota with a course or post, which denotes the minimum number of applicants that need to be assigned to a post in any feasible allocation. That is, for a post p p p q + ( p ) q^{+}(p) q + ( p ) q − ( p ) q^{-}(p) q − ( p ) M M M p p p M ( p ) M(p) M ( p ) p p p M M M M M M p p p q − ( p ) ≤ ∣ M ( p ) ∣ ≤ q + ( p ) q^{-}(p) \le|M(p)| \le q^{+}(p) q − ( p ) ≤ ∣ M ( p ) ∣ ≤ q + ( p ) fixed quota setting throughout the paper. In the presence of lower quotas, there are simple instances where no feasible matching exists. For example, consider the matching M 1 M_1 M 1 Figure 1 . In M 1 M_1 M 1 p 3 p_3 p 3 p 5 p_5 p 5
Figure 1. Example instance G G G ∣ A ∣ = ∣ P ∣ = 7 |\mathcal{A}| = |\mathcal{P}| = 7 ∣ A ∣ = ∣ P ∣ = 7 p 1 p_1 p 1 a 3 a_3 a 3 p 2 p_2 p 2 a 3 a_3 a 3 lower value and an upper value . In the fixed quota setting these numbers represent rigid lower and upper quotas. In the soft quota setting these numbers are the lower and the upper targets, respectively. Matching M 1 M_1 M 1 Figure 1 (iii) is an infeasible matching in the fixed quota setting since the posts p 3 p_3 p 3 p 5 p_5 p 5 M 1 M_1 M 1
In many practical applications, quotas need not be as rigid as assumed in the fixed quota setting, and relaxing lower quotas and augmenting upper quotas have been considered in the literature. Lower quotas have been extensively investigated in the two-sided preference list setting called the Hospital Residents problem [10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 ] . Here, the lower quota of a hospital denotes the minimum number of residents (doctors) needed for the smooth functioning of the hospital. As mentioned earlier, in the presence of lower quotas, a feasible matching may not always exist. Therefore, relaxing these lower quotas has been considered as a solution. For instance, instead of hospitals closing down due to the lack of a minimum number of doctors, they may simply reduce their service levels, as described in the work of Goko et al. [10 ] . Similarly, in the context of school choice, capacity planning to augment the number of available seats has recently been considered in multiple works [18 , 19 , 20 ] . Motivated by such applications, we relax the fixed quota assumption by proposing and studying a soft quota setting for the assignment problem in the one-sided preferences model.
Soft Quota Setting
An instance of the problem in the soft quota setting consists of a bipartite graph G = ( A ∪ P , E ) G = (A \cup P, E) G = ( A ∪ P , E ) p p p ℓ ( p ) \ell(p) ℓ ( p ) u ( p ) u(p) u ( p ) p p p ℓ ( p ) \ell(p) ℓ ( p ) u ( p ) u(p) u ( p ) p p p p p p M M M
d M ( p ) = max { 0 , ℓ ( p ) − ∣ M ( p ) ∣ , ∣ M ( p ) ∣ − u ( p ) } . d_M(p) = \max\{0, \ell(p) - |M(p)|, |M(p)| - u(p)\}. d M ( p ) = max { 0 , ℓ ( p ) − ∣ M ( p ) ∣ , ∣ M ( p ) ∣ − u ( p )} . Our goal in the soft quota setting is to compute an assignment that has two orthogonal optimization objectives:
(i) Minimizing deviation. For a matching M M M d t o t ( M ) d_{tot}(M) d t o t ( M ) d m a x ( M ) d_{max}(M) d ma x ( M )
d t o t ( M ) = ∑ p ∈ P d M ( p ) d m a x ( M ) = max p ∈ P d M ( p ) d_{tot}(M) = \sum_{p \in P} d_M(p) \qquad d_{max}(M) = \max_{p \in P} d_M(p) d t o t ( M ) = p ∈ P ∑ d M ( p ) d ma x ( M ) = p ∈ P max d M ( p ) (ii) Optimality with respect to preferences. Two well-studied notions of optimality in the fixed quota setting for the one-sided preference list model are rank-maximality [21 , 22 , 23 , 24 ] , and fairness [25 ] . A rank-maximal matching matches the maximum number of applicants to rank 1 posts, subject to that, the maximum number of applicants to rank 2 posts, and so on. A fair matching minimizes the number of unmatched applicants, subject to that, minimizes the number of applicants matched to the last rank posts, and so on. The signature of a matching allows us to formalize these notions. Let r r r M M M σ ( M ) \sigma(M) σ ( M ) r + 1 r + 1 r + 1 ( x 1 , x 2 , … , x r , x r + 1 ) (x_1, x_2, \ldots, x_r, x_{r+1}) ( x 1 , x 2 , … , x r , x r + 1 ) x i x_i x i i i i M M M i ∈ [ r ] i \in[r] i ∈ [ r ] x r + 1 x_{r+1} x r + 1 M M M
Definition 1 (Rank-maximality). For two matchings M M M M ′ M' M ′
σ ( M ) = ( x 1 , x 2 , … , x r , x r + 1 ) and σ ( M ′ ) = ( y 1 , y 2 , … , y r , y r + 1 ) , \sigma(M) = (x_1, x_2, \ldots, x_r, x_{r+1}) \text{ and } \sigma(M') = (y_1, y_2, \ldots, y_r, y_{r+1}), σ ( M ) = ( x 1 , x 2 , … , x r , x r + 1 ) and σ ( M ′ ) = ( y 1 , y 2 , … , y r , y r + 1 ) , we say that M ≻ R M ′ M \succ_R M' M ≻ R M ′ M M M M ′ M' M ′ i i i 1 ≤ i ≤ r 1 \le i \le r 1 ≤ i ≤ r x i > y i x_i > y_i x i > y i 1 ≤ j ≤ i − 1 1 \le j \le i - 1 1 ≤ j ≤ i − 1 x j = y j x_j = y_j x j = y j ≻ R \succ_R ≻ R
Definition 2 (Fairness). For two matchings M M M M ′ M' M ′ G G G
σ ( M ) = ( x 1 , x 2 , … , x r , x r + 1 ) and σ ( M ′ ) = ( y 1 , y 2 , … , y r , y r + 1 ) , \sigma(M) = (x_1, x_2, \ldots, x_r, x_{r+1}) \text{ and } \sigma(M') = (y_1, y_2, \ldots, y_r, y_{r+1}), σ ( M ) = ( x 1 , x 2 , … , x r , x r + 1 ) and σ ( M ′ ) = ( y 1 , y 2 , … , y r , y r + 1 ) , we say that M ≻ F M ′ M \succ_F M' M ≻ F M ′ M M M M ′ M' M ′ i i i 1 < i ≤ r + 1 1 < i \le r + 1 1 < i ≤ r + 1 x i < y i x_i < y_i x i < y i i + 1 ≤ j ≤ r + 1 i + 1 \le j \le r + 1 i + 1 ≤ j ≤ r + 1 x j = y j x_j = y_j x j = y j ≻ F \succ_F ≻ F
In the fixed quota setting, where the lower quota of every post is zero, optimal matchings under both these notions are guaranteed to exist and can be efficiently computed using the algorithms given in Irving et al. [21 ] , Paluch [22 ] and Huang et al. [25 ] . Even in the presence of lower quotas, an optimal matching among all feasible matchings can be efficiently computed by extending the algorithm given in Huang et al. [25 ] .
By definition, rank-maximality and fairness optimize the head and tail end of the signature, respectively, and one may perform poorly on the other criterion. Given an input signature ρ \rho ρ M M M σ ( M ) ⪰ R ρ \sigma(M) \succeq_R \rho σ ( M ) ⪰ R ρ σ ( M ) ⪰ F ρ \sigma(M) \succeq_F \rho σ ( M ) ⪰ F ρ weak dominance , and was introduced and studied in Santhini et al. [26 , 27 ] .
Definition 3 (Weak dominance). For two matchings M M M M ′ M' M ′ G G G
σ ( M ) = ( x 1 , x 2 , … , x r , x r + 1 ) and σ ( M ′ ) = ( y 1 , y 2 , … , y r , y r + 1 ) , \sigma(M) = (x_1, x_2, \ldots, x_r, x_{r+1}) \text{ and } \sigma(M') = (y_1, y_2, \ldots, y_r, y_{r+1}), σ ( M ) = ( x 1 , x 2 , … , x r , x r + 1 ) and σ ( M ′ ) = ( y 1 , y 2 , … , y r , y r + 1 ) , we say that M ⪰ D M ′ M \succeq_D M' M ⪰ D M ′ M M M M ′ M' M ′
∑ j = 1 ℓ x j ≥ ∑ j = 1 ℓ y j for all ℓ ∈ [ r + 1 ] . \sum_{j=1}^{\ell} x_j \ge\sum_{j=1}^{\ell} y_j \quad\text{for all } \ell\in[r+1]. j = 1 ∑ ℓ x j ≥ j = 1 ∑ ℓ y j for all ℓ ∈ [ r + 1 ] . In the fixed quota setting, for a given signature, deciding whether the instance admits a matching that weakly dominates the signature is NP-hard [26 , 27 ] .
Our Problems
In our soft quota setting, there is no restriction on the number of applicants that can be assigned to a post. Thus, we care about deviation as well as preference optimality and this defines our problems.
Deviation first, preference optimality next. There exist applications where having as low deviation as possible is required and, subject to that, optimality with respect to preferences needs to be respected. For example, in allocating projects to students [28 ] or dividing political representatives to seats [29 , 30 , 31 ] it is desirable to minimize the difference between input values and the assigned numbers. In a similar spirit, we consider minimizing the deviation from target values. Let M \mathcal{M} M G G G M t \mathcal{M}_t M t M m \mathcal{M}_m M m Figure 2 (i). We define our first set of problems for the notions of rank-maximality and fairness:
Figure 2. OPT-MIN-Y and OPT-SIGN-MIN-Y illustration, where Y ∈ { t o t , m a x } Y \in\{tot, max\} Y ∈ { t o t , ma x } ∈ { R M M , F A I R } \in\{RMM, FAIR\} ∈ { R M M , F A I R }
OPT-MIN-TOT: The goal is to compute a matching that satisfies the notion OPT with respect to preferences in the set M t \mathcal{M}_t M t M t \mathcal{M}_t M t
Preference optimality first, deviation next. Analogously, there exist applications where preference optimality has to be respected first, and subject to that, we would like to minimize a deviation parameter of interest. Since, in the soft quota setting, there is no bound on the upper quota of a post, it is not immediate how to determine the set of matchings in which we wish to compute a rank-maximal or fair matching. To address this, we first introduce an additional input to our problem – a signature requirement, ρ \rho ρ [26 , 27 ] , in the context of a different notion of preference optimality, namely weak dominance .
For a fixed notion of preference optimality, a matching M M M σ ( M ) ⪰ O P T ρ \sigma(M) \succeq_{\mathrm{OPT}} \rho σ ( M ) ⪰ OPT ρ M O P T \mathcal{M}_{\mathrm{OPT}} M OPT Figure 2 (ii). Let M t ′ \mathcal{M}'_t M t ′ M m ′ \mathcal{M}'_m M m ′ M O P T \mathcal{M}_{\mathrm{OPT}} M OPT
The order in which we consider the two orthogonal parameters for optimization provides a trade-off between deviation and preference optimality. As expected, when the deviation is optimized first, the output matching has a weak signature. In contrast, when preference optimality is given precedence, a higher deviation is incurred. Thus, our problems offer a trade-off based on the user requirement. To illustrate the optimal solutions for the different problems considered, we use our example instance G G G Figure 1 .
Illustrative example
We consider the example instance with seven applicants and seven posts, along with the preferences of applicants over posts, as shown in Figure 1 (i). For each post, two values – a lower value and an upper value – are given, as in Figure 1 (ii). In the soft quota setting, these values represent the lower and the upper targets, respectively. First, we illustrate our problems for the optimality notion of rank-maximality. Table 1 shows the optimal solutions for each of the problems, along with parameters of the matching. We begin by considering the problems of the type deviation first, preference optimality next. See the first two rows of Table 1 . Note that, in the example instance given in Figure 1 , the posts p 2 p_2 p 2 p 3 p_3 p 3 a 3 a_3 a 3 p 2 p_2 p 2 p 3 p_3 p 3 p 4 p_4 p 4 p 5 p_5 p 5
Table 1. Optimal matchings in the instance given in Figure 1 corresponding to our problems. For the preference optimality first type problems, we consider the input signature as (4, 0, 0, 3). We consider preference optimality as rank-maximality.
Observation 1. Any matching in the example instance given in Figure 1 must have a maximum deviation of at least one and a total deviation of at least two.
It can be verified that the matchings M 1 M_1 M 1 M 2 M_2 M 2 Table 1 are optimal for the problems RMM-MIN-TOT and RMM-MIN-MAX respectively.
Now we turn to problems where preference optimality is considered first and, subject to that, deviation is minimized. For concreteness, we fix the requirement for signature as ( 4 , 0 , 0 , 3 ) (4, 0, 0, 3) ( 4 , 0 , 0 , 3 ) p 1 p_1 p 1 M R \mathcal{M}_{R} M R M R \mathcal{M}_{R} M R M 3 M_3 M 3 M 4 M_4 M 4 Table 1 are optimal for the problems RMM-SIGN-MIN-TOT and RMM-SIGN-MIN-MAX respectively.
Note that the signatures of the matchings M 3 M_3 M 3 M 4 M_4 M 4
Next, we illustrate our problems and their solutions for the notion of fairness using the example instance G G G Figure 1 . Table 2 shows the optimal solutions for each of the problems, along with the parameters of the matching. Note that these matchings are different from the matchings given in Table 1 . We first consider the problems of the type deviation first, preference optimality next. From Observation 1, any matching in G G G M 5 M_5 M 5 M 6 M_6 M 6 Table 2 are optimal for the problems FAIR-MIN-TOT and FAIR-MIN-MAX respectively.
Table 2. Optimal matchings in the instance given in Figure 1 corresponding to our problems. For the preference optimality first type problems, we consider the input signature as ( 4 , 0 , 3 , 0 ) (4,0,3,0) ( 4 , 0 , 3 , 0 )
Now, we turn to problems where preference optimality is considered first and subject to that deviation is minimized. For concreteness, we fix the signature as ( 4 , 0 , 3 , 0 ) (4,0,3,0) ( 4 , 0 , 3 , 0 ) p 1 p_1 p 1 p 1 p_1 p 1 p 6 p_6 p 6 p 7 p_7 p 7 M F \mathcal{M}_F M F M F \mathcal{M}_F M F M 7 M_7 M 7 M 6 M_6 M 6 Table 2 , are optimal for the FAIR-SIGN-MIN-TOT and FAIR-SIGN-MIN-MAX problems, respectively.
Our Results
We show the following new results in our paper.
Theorem 4. OPT-SIGN-MIN-MAX and OPT-SIGN-MIN-TOT admit polynomial time algorithms, where OPT can be one of rank-maximality (RMM) or fairness (FAIR).
Theorem 5. OPT-MIN-MAX and OPT-MIN-TOT admit polynomial time algorithms, where OPT can be one of rank-maximality or fairness.
Proposition 1. DOM-SIGN-MIN-MAX and DOM-SIGN-MIN-TOT are N P NP N P k = 0 k = 0 k = 0 p ∈ P p \in\mathcal{P} p ∈ P ℓ ( p ) = 0 \ell(p) = 0 ℓ ( p ) = 0
The above hardness is obtained from the hardness of DOM-Q problem considered in [27 ] by viewing quotas as targets.
Our Techniques. The algorithms for computing minimum total deviation matchings are based on a flow network that we design. Flow networks are used to compute Pareto-optimal matchings [32 , 33 , 9 ] , rank-maximal matchings [34 ] and weakly dominant matchings [27 , 26 ] in the literature. For computing matchings with minimum value of maximum deviation we reduce the problem to an appropriate problem in the fixed quota setting, which can be solved efficiently.
Generalized soft quota setting. Given our positive results for the problems in the soft quota setting for the optimality notions rank-maximality and fairness, it is natural to consider a generalization of our setting, where every deviation is associated with a cost. That is, every post p p p c ℓ ( p ) c_\ell(p) c ℓ ( p ) c u ( p ) c_u(p) c u ( p ) § 7 .
Related Works
Biproportional apportionment. Our soft quota setting is similar to the biproportional apportionment problem [29 , 30 , 31 ] , which deals with the fair division of political representatives among states. Political representatives correspond to applicants, and states correspond to posts in our model. Many methods [30 , 31 ] for the biproportional apportionment problem reduce the problem to a flow network to minimize the absolute or relative min-max error. Note that the min-max error in the biproportional apportionment problem considered in the works of Pukelsheim et al. [30 ] and Serafini and Simeone [31 ] corresponds to the min-max deviation in our model. However, the biproportional apportionment problem does not involve any preferences, whereas in our setting we have preferences associated with edges.
Soft bounds. The recent works [35 , 36 , 37 , 38 , 39 ] in the two-sided preferences model allow soft bounds on the capacity constraints. These works focus on the controlled school choice problem, in which students are associated with types and schools have soft bounds on the quota of each type. However, there are hard constraints on the number of students that can be assigned to each school or type. In the work by Aziz et al. [38 ] and Echenique and Yenmez [36 ] , lower-side deviation (or relaxation) from the target quotas or reserves is allowed. Our model has no hard capacity constraints, and target soft quotas are allowed to deviate on both sides. In the work by Ehlers et al. [35 ] , students are associated with a single type, and for each type, there is a lower violation and upper violation w.r.t. an allocation, and these are analogous to the lower deviation and upper deviation in our model. Gonczarowski et al. [37 ] considered a matching problem in the two-sided matching market with soft diversity constraints that allocate candidates to Pre-Military Academics programs (PMA). Here, each PMA defines a set of populations (or types) that they are interested, and specifies a soft minimum target and hard maximum quota for such populations. For more information, refer to the survey paper by Aziz et al. [40 ] .
Other models of flexibility. In the context of school choice problem, capacity planning is studied in [41 , 42 , 19 , 18 , 43 ] . In the work by Gajulapalli et al. [41 ] , flexible quotas are used to increase the capacity of some schools. In the work by Rios et al. [42 ] , flexible quotas are used as a tie-breaker. In the work by Bobbio et al. [19 ] , the authors study the school choice problem in an expanded market, where some schools can increase their capacity to either allocate students who are previously unassigned or to improve the assignment of the previously assigned students. The budget used for capacity expansion in the work by Bobbio et al. [19 ] is analogous to the total upper deviation of posts in our model. In Abe et al. [18 ] , Monte Carlo tree search based solutions for the capacity expansion problem are studied. In the work of Limaye and Nasre [44 ] and Santhini et al. [27 , 26 ] , programs have costs instead of quotas, which allows flexibility. In all these works, the flexibility of upper quotas is considered, whereas in our work, we allow posts to deviate on both upper and lower targets.
To the best of our knowledge, this is the first work that investigates soft quotas in the one-sided preference list model.
Our problems consider optimizing two objective functions – deviation and preference optimality – and hence can be regarded as a special case of a multi-objective optimization problem [45 , 46 , 47 ] . These works differ from our work in terms of the problem setup and the objectives considered.
Organization of the paper. Throughout the paper, we present the results with OPT set to rank-maximality (RMM). Analogous results for fairness can be obtained with minor modifications to our algorithms, as outlined in the relevant sections. In § 3 and § 4 , we focus on problems where the objective is to minimize the total deviation. The former section addresses preference-optimality-first type problems (the MIN-TOT variant in Theorem 4), while the latter discusses deviation-first type problems (the MIN-TOT variant in Theorem 5). In § 5 , we present results for the MIN-MAX problems by exploiting the connection between the fixed quota setting and the soft quota setting. § 6 explores the simultaneous optimization of total deviation and maximum deviation. Results for the generalized soft quota setting are described in § 7 , and we conclude with a discussion in § 8 .
Minimizing Total Deviation: Preference Optimality First
In this section, we present the results for minimizing total deviation for the preference optimality first, deviation next type of problems. As mentioned earlier, apart from the input instance these problems have a signature as part of the input. Recall that OPT can be instantiated with either rank-maximality or fairness. We present the results for rank-maximality in detail and state the necessary modifications required for fairness.
An instance of RMM-SIGN-MIN-TOT problem consists of a graph G G G ρ \rho ρ M R \mathcal{M}_{R} M R M ∈ M R M \in\mathcal{M}_{R} M ∈ M R σ ( M ) ⪰ R ρ \sigma(M) \succeq_{R} \rho σ ( M ) ⪰ R ρ M M M M R \mathcal{M}_{R} M R
Overall idea. Consider an optimal matching M ∗ M^{*} M ∗ M ∗ M^{*} M ∗ Δ ∗ \Delta^{*} Δ ∗ M ∗ M^{*} M ∗ lower target, whereas another subset of posts, disjoint from the previous set, incur deviation with respect to the upper target. Let l d ∗ ld^{*} l d ∗ u d ∗ ud^{*} u d ∗ Δ ∗ = l d ∗ + u d ∗ \Delta^{*} = ld^{*} + ud^{*} Δ ∗ = l d ∗ + u d ∗ l d ld l d u d ud u d l d + u d = Δ ld + ud = \Delta l d + u d = Δ H ( l d ∗ , u d ∗ ) H_{(ld^{*},ud^{*})} H ( l d ∗ , u d ∗ ) M ∗ M^{*} M ∗ f ∗ f^{*} f ∗ H ( l d ∗ , u d ∗ ) H_{(ld^{*},ud^{*})} H ( l d ∗ , u d ∗ ) Δ \Delta Δ Δ \Delta Δ l d + u d ld + ud l d + u d
Construction of the network
For a given instance G G G Δ \Delta Δ l d ld l d u d ud u d H ( l d , u d ) = ( V H , E H ) H_{(ld,ud)} = (V_{H}, E_{H}) H ( l d , u d ) = ( V H , E H ) H ( l d , u d ) H_{(ld,ud)} H ( l d , u d )
V H = { s , d ′ , d ′ ′ , t } ∪ A ∪ { p ′ , p ′ ′ : p ∈ P } . V_{H} = \{s, d', d'', t\} \cup\mathcal{A} \cup\{p',p'' : p \in\mathcal{P}\}. V H = { s , d ′ , d ′′ , t } ∪ A ∪ { p ′ , p ′′ : p ∈ P } . For every applicant a a a G G G a a a V H V_{H} V H p p p G G G V H V_{H} V H p ′ p' p ′ p ′ ′ p'' p ′′ s s s t t t d ′ d' d ′ d ′ ′ d'' d ′′
Demand and capacity of the edges in E H E_{H} E H Every edge e ∈ E H e \in E_{H} e ∈ E H [ q − ( e ) , q + ( e ) ] [q^{-}(e),q^{+}(e)] [ q − ( e ) , q + ( e )] E H E_{H} E H
E 1 = { ( s , a ) : a ∈ A } \mathcal{E}_1=\{(s,a):a\in A\} E 1 = {( s , a ) : a ∈ A } [ 0 , 1 ] [0,1] [ 0 , 1 ]
E 2 = { ( a , p ′ ) , ( a , p ′ ′ ) : ( a , p ) ∈ E } \mathcal{E}_2=\{(a,p^{\prime}),(a,p^{\prime\prime}):(a,p)\in E\} E 2 = {( a , p ′ ) , ( a , p ′′ ) : ( a , p ) ∈ E } [ 0 , 1 ] [0,1] [ 0 , 1 ]
E 3 = { ( p ′ , t ) : p ∈ P } \mathcal{E}_3=\{(p^{\prime},t):p\in P\} E 3 = {( p ′ , t ) : p ∈ P } [ ℓ ( p ) , u ( p ) ] [\ell(p),u(p)] [ ℓ ( p ) , u ( p )]
E 4 = { ( p ′ ′ , d ′ ′ ) : p ∈ P } \mathcal{E}_4=\{(p^{\prime\prime},d^{\prime\prime}):p\in P\} E 4 = {( p ′′ , d ′′ ) : p ∈ P } [ 0 , u d ] [0,ud] [ 0 , u d ]
E 5 = { ( d ′ , p ′ ) : p ∈ P } \mathcal{E}_5=\{(d^{\prime},p^{\prime}):p\in P\} E 5 = {( d ′ , p ′ ) : p ∈ P } [ 0 , l d ] [0,ld] [ 0 , l d ]
E 6 = { ( s , d ′ ) , ( d ′ ′ , t ) } \mathcal{E}_6=\{(s,d^{\prime}),(d^{\prime\prime},t)\} E 6 = {( s , d ′ ) , ( d ′′ , t )} [ l d , l d ] [ld,ld] [ l d , l d ] [ u d , u d ] [ud,ud] [ u d , u d ]
Cost of the edges in E H E_H E H All the edges in E H E_H E H E 2 \mathcal{E}_2 E 2 ( a , p ) (a,p) ( a , p ) G G G i i i ( a , p ′ ) (a,p^{\prime}) ( a , p ′ ) ( a , p ′ ′ ) (a,p^{\prime\prime}) ( a , p ′′ ) E 2 \mathcal{E}_2 E 2 − ( n + 1 ) r − i -(n+1)^{r-i} − ( n + 1 ) r − i n = ∣ A ∣ n=|A| n = ∣ A ∣
As in standard reductions, there is a natural correspondence between edges in E 2 \mathcal{E}_2 E 2 Figure 3 for an illustration. A flow f f f H ( l d , u d ) H_{(ld,ud)} H ( l d , u d ) e ∈ f ∩ E H e\in f\cap E_H e ∈ f ∩ E H f f f c o s t ( f ) cost(f) cos t ( f )
Figure 3. Flow network H ( l d , u d ) H_{(ld,ud)} H ( l d , u d ) Δ = l d + u d \Delta= ld + ud Δ = l d + u d
∑ e ∈ E H f ( e ) ⋅ c o s t ( e ) \sum_{e\in E_H} f(e)\cdot cost(e) e ∈ E H ∑ f ( e ) ⋅ cos t ( e ) where f ( e ) f(e) f ( e ) c o s t ( e ) cost(e) cos t ( e ) e e e e e e M M M σ ( M ) = ( x 1 , x 2 , … , x r , x r + 1 ) \sigma(M)=(x_1,x_2,\ldots,x_r,x_{r+1}) σ ( M ) = ( x 1 , x 2 , … , x r , x r + 1 ) M M M c o s t ( M ) cost(M) cos t ( M )
− ∑ j = 1 r x j ⋅ ( n + 1 ) r − j . -\sum_{j=1}^{r}x_j\cdot(n+1)^{r-j}. − j = 1 ∑ r x j ⋅ ( n + 1 ) r − j . We have the following lemma regarding the cost assignment.
Lemma 1. Let M , M ′ M,M^{\prime} M , M ′ σ ( M ) ≻ R σ ( M ′ ) \sigma(M)\succ_R\sigma(M^{\prime}) σ ( M ) ≻ R σ ( M ′ ) c o s t ( M ) < c o s t ( M ′ ) cost(M)<cost(M^{\prime}) cos t ( M ) < cos t ( M ′ ) i i i − ( n + 1 ) r − i -(n+1)^{r-i} − ( n + 1 ) r − i
Proof. Let σ ( M ) = ( x 1 , x 2 , … , x r , x r + 1 ) \sigma(M)=(x_1,x_2,\ldots,x_r,x_{r+1}) σ ( M ) = ( x 1 , x 2 , … , x r , x r + 1 ) σ ( M ′ ) = ( y 1 , y 2 , … , y r , y r + 1 ) \sigma(M^{\prime})=(y_1,y_2,\ldots,y_r,y_{r+1}) σ ( M ′ ) = ( y 1 , y 2 , … , y r , y r + 1 ) i i i σ ( M ) \sigma(M) σ ( M ) σ ( M ′ ) \sigma(M^{\prime}) σ ( M ′ ) x j = y j x_j=y_j x j = y j j < i j<i j < i x i > y i x_i>y_i x i > y i
The cost difference between the matchings M M M M ′ M^{\prime} M ′
c o s t ( M ′ ) − c o s t ( M ) = ∑ j = 1 r ( x j − y j ) ( n + 1 ) r − j = ( x i − y i ) ( n + 1 ) r − i + ∑ j = i + 1 r ( x j − y j ) ( n + 1 ) r − j . cost(M^{\prime})-cost(M)=\sum_{j=1}^{r}(x_j-y_j)(n+1)^{r-j}=(x_i-y_i)(n+1)^{r-i}+\sum_{j=i+1}^{r}(x_j-y_j)(n+1)^{r-j}. cos t ( M ′ ) − cos t ( M ) = j = 1 ∑ r ( x j − y j ) ( n + 1 ) r − j = ( x i − y i ) ( n + 1 ) r − i + j = i + 1 ∑ r ( x j − y j ) ( n + 1 ) r − j . Now, since x i − y i ≥ 1 x_i-y_i\geq1 x i − y i ≥ 1
c o s t ( M ′ ) − c o s t ( M ) ≥ ( n + 1 ) r − i + ∑ j = i + 1 r ( x j − y j ) ( n + 1 ) r − j ≥ ( n + 1 ) r − i − ∑ j = i + 1 r y j ( n + 1 ) r − j ≥ ( n + 1 ) r − i − ( ∑ j = i + 1 r y j ) ( n + 1 ) r − i − 1 . \begin{aligned}
cost(M^{\prime})-cost(M)\geq(n+1)^{r-i}+\sum_{j=i+1}^{r}(x_j-y_j)(n+1)^{r-j} \\
&\geq(n+1)^{r-i}-\sum_{j=i+1}^{r}y_j(n+1)^{r-j} \\
&\geq(n+1)^{r-i}-\left(\sum_{j=i+1}^{r}y_j\right)(n+1)^{r-i-1}.
\end{aligned} cos t ( M ′ ) − cos t ( M ) ≥ ( n + 1 ) r − i + j = i + 1 ∑ r ( x j − y j ) ( n + 1 ) r − j ≥ ( n + 1 ) r − i − j = i + 1 ∑ r y j ( n + 1 ) r − j ≥ ( n + 1 ) r − i − ( j = i + 1 ∑ r y j ) ( n + 1 ) r − i − 1 . Additionally, using the fact that ∑ j = i + 1 r y j ≤ ∑ j = 1 r y j ≤ n \sum_{j=i+1}^{r}y_j\leq\sum_{j=1}^{r}y_j\leq n ∑ j = i + 1 r y j ≤ ∑ j = 1 r y j ≤ n
c o s t ( M ′ ) − c o s t ( M ) ≥ ( n + 1 ) r − i − n ( n + 1 ) r − i − 1 = ( n + 1 ) r − i − 1 > 0. cost(M^{\prime})-cost(M)\geq(n+1)^{r-i}-n(n+1)^{r-i-1}=(n+1)^{r-i-1}>0. cos t ( M ′ ) − cos t ( M ) ≥ ( n + 1 ) r − i − n ( n + 1 ) r − i − 1 = ( n + 1 ) r − i − 1 > 0. We have the following remark regarding the cost assignment.
Proof: Let f f f H ( l d , u d ) H_{(l_d,u_d)} H ( l d , u d ) M f M_f M f M ( l d , u d ) \mathcal{M}_{(l_d,u_d)} M ( l d , u d ) M f M_f M f M ( l d , u d ) \mathcal{M}_{(l_d,u_d)} M ( l d , u d ) M ′ ∈ M ( l d , u d ) M' \in\mathcal{M}_{(l_d,u_d)} M ′ ∈ M ( l d , u d ) σ ( M ′ ) ≻ R σ ( M f ) \sigma(M') \succ_R \sigma(M_f) σ ( M ′ ) ≻ R σ ( M f ) c o s t ( M ′ ) < c o s t ( M f ) cost(M') < cost(M_f) cos t ( M ′ ) < cos t ( M f ) M ′ ∈ M ( l d , u d ) M' \in\mathcal{M}_{(l_d,u_d)} M ′ ∈ M ( l d , u d ) f ′ f' f ′ M ′ M' M ′ c o s t ( f ′ ) = c o s t ( M ′ ) cost(f') = cost(M') cos t ( f ′ ) = cos t ( M ′ ) f f f
It is worth noting that our reductions apply to any notion of optimality that can be encoded as a maximum weight matching problem.
Total deviation of a flow versus total deviation of the corresponding matching
The flow network H ( l d , u d ) H_{(l_d,u_d)} H ( l d , u d ) H ( l d , u d ) H_{(l_d,u_d)} H ( l d , u d ) f f f f f f H ( l d , u d ) H_{(l_d,u_d)} H ( l d , u d ) M M M G G G
M = { ( a , p ) ∣ f ( a , p ′ ) = 1 or f ( a , p ′ ′ ) = 1 , a ∈ A , p ∈ P } . M = \{(a,p) \mid f(a,p') = 1 \text{ or } f(a,p'') = 1,\ a \in\mathcal{A},\ p \in\mathcal{P}\}. M = {( a , p ) ∣ f ( a , p ′ ) = 1 or f ( a , p ′′ ) = 1 , a ∈ A , p ∈ P } . For any applicant a a a ( s , a ) (s,a) ( s , a ) p ′ p' p ′ p ′ ′ p'' p ′′ f f f p ′ p' p ′ p ′ p' p ′ f f f f ( d ′ , p ′ ) f(d',p') f ( d ′ , p ′ ) p ′ ′ p'' p ′′ p ′ ′ p'' p ′′ f f f f ( p ′ ′ , d ′ ′ ) f(p'',d'') f ( p ′′ , d ′′ ) p ∈ P p \in\mathcal{P} p ∈ P p p p f f f
d f ( p ) = f ( d ′ , p ′ ) + f ( p ′ ′ , d ′ ′ ) . d_f(p) = f(d',p') + f(p'',d''). d f ( p ) = f ( d ′ , p ′ ) + f ( p ′′ , d ′′ ) . Similar to the definition of total deviation of a matching, we define total deviation of the flow f f f H ( l d , u d ) H_{(l_d,u_d)} H ( l d , u d )
Definition 6 (Total deviation of a flow). The total deviation of a flow f f f H ( l d , u d ) H_{(l_d,u_d)} H ( l d , u d )
d t o t ( f ) = ∑ p ∈ P f ( d ′ , p ′ ) + f ( p ′ ′ , d ′ ′ ) . d_{\mathrm{tot}}(f) = \sum_{p \in\mathcal{P}} f(d',p') + f(p'',d''). d tot ( f ) = p ∈ P ∑ f ( d ′ , p ′ ) + f ( p ′′ , d ′′ ) . By the construction of the network H ( l d , u d ) H_{(l_d,u_d)} H ( l d , u d ) f f f H ( l d , u d ) H_{(l_d,u_d)} H ( l d , u d ) d t o t ( f ) = Δ = l d + u d d_{\mathrm{tot}}(f) = \Delta= l_d + u_d d tot ( f ) = Δ = l d + u d
Some pathological cases. Having defined the correspondence between a flow in H ( l d , u d ) H_{(l_d,u_d)} H ( l d , u d ) H ( l d , u d ) H_{(l_d,u_d)} H ( l d , u d ) G G G ( a , p ) (a,p) ( a , p ) p p p ℓ ( p ) = 0 \ell(p) = 0 ℓ ( p ) = 0 u ( p ) = 1 u(p) = 1 u ( p ) = 1
Scenario 1: Consider the flow network H ( 1 , 1 ) H_{(1,1)} H ( 1 , 1 ) Δ = 2 \Delta= 2 Δ = 2 H ( 1 , 1 ) H_{(1,1)} H ( 1 , 1 ) f f f ⟨ s , d ′ , p ′ , t ⟩ \langle s,d',p',t\rangle ⟨ s , d ′ , p ′ , t ⟩ ⟨ s , a , p ′ ′ , d ′ ′ , t ⟩ \langle s,a,p'',d'',t\rangle ⟨ s , a , p ′′ , d ′′ , t ⟩ d t o t ( f ) = 2 d_{tot}(f) = 2 d t o t ( f ) = 2 Figure 4 (i) for an illustration). Since f ( d ′ , p ′ ) > 0 f(d',p') > 0 f ( d ′ , p ′ ) > 0 p p p f f f p p p ( p ′ ′ , d ′ ′ ) (p'',d'') ( p ′′ , d ′′ ) f f f d t o t ( f ) = 2 d_{tot}(f) = 2 d t o t ( f ) = 2 f f f ( a , p ) (a,p) ( a , p ) p p p ( d ′ , p ′ ) (d',p') ( d ′ , p ′ ) ( p ′ ′ , d ′ ′ ) (p'',d'') ( p ′′ , d ′′ ) p p p ( d ′ , p ′ ) (d',p') ( d ′ , p ′ ) ( p ′ ′ , d ′ ′ ) (p'',d'') ( p ′′ , d ′′ ) f f f
(a) Scenario 1: Total deviation of the flow f f f M = { ( a , p ) } M = \{(a,p)\} M = {( a , p )} H ( 1 , 1 ) H_{(1,1)} H ( 1 , 1 ) f f f
(b) An ( l d , u d ) (ld,ud) ( l d , u d ) f ′ f' f ′ H ( 1 , 1 ) H_{(1,1)} H ( 1 , 1 ) H ( 0 , 0 ) H_{(0,0)} H ( 0 , 0 ) f ′ f' f ′ M = { ( a , p ) } M = \{(a,p)\} M = {( a , p )}
Figure 4. Scenario 1 where d t o t ( f ) ≠ d t o t ( M ) d_{tot}(f) \ne d_{tot}(M) d t o t ( f ) = d t o t ( M ) ( l d , u d ) (ld,ud) ( l d , u d ) f ′ f' f ′
Scenario 2: Consider the flow network H ( 0 , 1 ) H_{(0,1)} H ( 0 , 1 ) Δ = 1 \Delta= 1 Δ = 1 H ( 0 , 1 ) H_{(0,1)} H ( 0 , 1 ) f f f ⟨ s , a , p ′ ′ , d ′ ′ , t ⟩ \langle s,a,p'',d'',t\rangle ⟨ s , a , p ′′ , d ′′ , t ⟩ d t o t ( f ) = 1 d_{tot}(f) = 1 d t o t ( f ) = 1 f f f ( a , p ) (a,p) ( a , p ) f ( p ′ , t ) = 0 < u ( p ) f(p',t) = 0 < u(p) f ( p ′ , t ) = 0 < u ( p ) f ( p ′ ′ , d ′ ′ ) > 0 f(p'',d'') > 0 f ( p ′′ , d ′′ ) > 0 f f f f ( p ′ ′ , d ′ ′ ) > 0 f(p'',d'') > 0 f ( p ′′ , d ′′ ) > 0 p p p ( p ′ , t ) (p',t) ( p ′ , t ) ( p ′ , t ) (p',t) ( p ′ , t ) f f f f ( p ′ ′ , d ′ ′ ) > 0 f(p'',d'') > 0 f ( p ′′ , d ′′ ) > 0
Scenario 3: Consider the flow network H ( 1 , 0 ) H_{(1,0)} H ( 1 , 0 ) Δ = 1 \Delta= 1 Δ = 1 H ( 1 , 0 ) H_{(1,0)} H ( 1 , 0 ) f f f ⟨ s , d ′ , p ′ , t ⟩ \langle s,d',p',t\rangle ⟨ s , d ′ , p ′ , t ⟩ d t o t ( f ) = 1 d_{tot}(f) = 1 d t o t ( f ) = 1 f ( p ′ , t ) = 1 > ℓ ( p ) f(p',t) = 1 > \ell(p) f ( p ′ , t ) = 1 > ℓ ( p ) f ( d ′ , p ′ ) > 0 f(d',p') > 0 f ( d ′ , p ′ ) > 0 f f f ( d ′ , p ′ ) (d',p') ( d ′ , p ′ ) ( p ′ , t ) (p',t) ( p ′ , t ) ℓ ( p ) \ell(p) ℓ ( p ) ( p ′ , t ) (p',t) ( p ′ , t ) f f f f ( d ′ , p ′ ) > 0 f(d',p') > 0 f ( d ′ , p ′ ) > 0
Good flow and correcting flow
To address the discrepancies as illustrated in the pathological cases and ensure that the total deviation of the flow corresponds to the total deviation of the matching, a feasible flow in our flow network should satisfy additional properties, which are listed below as Property 1.
Property 1. Let f f f H ( l d , u d ) H_{(l_d,u_d)} H ( l d , u d ) f f f p ∈ P p \in\mathcal{P} p ∈ P
(i) at most one of the edges ( d ′ , p ′ ) (d',p') ( d ′ , p ′ ) ( p ′ ′ , d ′ ′ ) (p'',d'') ( p ′′ , d ′′ ) f f f
(ii) if f ( p ′ ′ , d ′ ′ ) > 0 f(p'',d'') > 0 f ( p ′′ , d ′′ ) > 0 f ( p ′ , t ) = u ( p ) f(p',t) = u(p) f ( p ′ , t ) = u ( p )
(iii) if f ( d ′ , p ′ ) > 0 f(d',p') > 0 f ( d ′ , p ′ ) > 0 f ( p ′ , t ) = ℓ ( p ) f(p',t) = \ell(p) f ( p ′ , t ) = ℓ ( p )
We note a useful observation below about good flows.
Observation 2. Let f f f H ( l d , u d ) H_{(l_d,u_d)} H ( l d , u d ) M M M G G G p ∈ P p \in\mathcal{P} p ∈ P d f ( p ) = d M ( p ) d_f(p) = d_M(p) d f ( p ) = d M ( p ) d t o t ( f ) = d t o t ( M ) d_{\mathrm{tot}}(f) = d_{\mathrm{tot}}(M) d tot ( f ) = d tot ( M )
Proof: Let f f f H ( l d , u d ) H_{(l_d,u_d)} H ( l d , u d ) f f f p p p ( d ′ , p ′ ) (d',p') ( d ′ , p ′ ) ( p ′ ′ , d ′ ′ ) (p'',d'') ( p ′′ , d ′′ ) M M M f f f p p p p p p M M M ∣ M ( p ) ∣ = f ( p ′ ′ , d ′ ′ ) + f ( p ′ , t ) − f ( d ′ , p ′ ) |M(p)| = f(p'',d'') + f(p',t) - f(d',p') ∣ M ( p ) ∣ = f ( p ′′ , d ′′ ) + f ( p ′ , t ) − f ( d ′ , p ′ ) p p p M M M d M ( p ) = max { 0 , ℓ ( p ) − ∣ M ( p ) ∣ , ∣ M ( p ) ∣ − u ( p ) } d_M(p) = \max\{0,\ell(p)-|M(p)|,|M(p)|-u(p)\} d M ( p ) = max { 0 , ℓ ( p ) − ∣ M ( p ) ∣ , ∣ M ( p ) ∣ − u ( p )}
Case 1: p ∈ P p \in\mathcal{P} p ∈ P f ( d ′ , p ′ ) = f ( p ′ ′ , d ′ ′ ) = 0 f(d',p') = f(p'',d'') = 0 f ( d ′ , p ′ ) = f ( p ′′ , d ′′ ) = 0 d f ( p ) = 0 d_f(p) = 0 d f ( p ) = 0 f ( p ′ ′ , d ′ ′ ) = 0 f(p'',d'') = 0 f ( p ′′ , d ′′ ) = 0 p ′ ′ p'' p ′′ f f f ∣ M ( p ) ∣ = f ( p ′ , t ) ≤ u ( p ) |M(p)| = f(p',t) \leq u(p) ∣ M ( p ) ∣ = f ( p ′ , t ) ≤ u ( p ) f ( d ′ , p ′ ) = 0 f(d',p') = 0 f ( d ′ , p ′ ) = 0 ( p ′ , t ) (p',t) ( p ′ , t ) A \mathcal{A} A f f f ∣ M ( p ) ∣ ≥ ℓ ( p ) |M(p)| \geq\ell(p) ∣ M ( p ) ∣ ≥ ℓ ( p ) d M ( p ) = 0 = d f ( p ) d_M(p) = 0 = d_f(p) d M ( p ) = 0 = d f ( p )
Case 2: p ∈ P p \in\mathcal{P} p ∈ P f ( p ′ ′ , d ′ ′ ) > 0 f(p'',d'') > 0 f ( p ′′ , d ′′ ) > 0 f ( d ′ , p ′ ) = 0 f(d',p') = 0 f ( d ′ , p ′ ) = 0 d f ( p ) = f ( p ′ ′ , d ′ ′ ) d_f(p) = f(p'',d'') d f ( p ) = f ( p ′′ , d ′′ ) f ( p ′ , t ) = u ( p ) f(p',t) = u(p) f ( p ′ , t ) = u ( p ) f ( d ′ , p ′ ) = 0 f(d',p') = 0 f ( d ′ , p ′ ) = 0 ( p ′ , t ) (p',t) ( p ′ , t ) ∣ M ( p ) ∣ = u ( p ) + f ( p ′ ′ , d ′ ′ ) |M(p)| = u(p) + f(p'',d'') ∣ M ( p ) ∣ = u ( p ) + f ( p ′′ , d ′′ ) d M ( p ) = f ( p ′ ′ , d ′ ′ ) = d f ( p ) d_M(p) = f(p'',d'') = d_f(p) d M ( p ) = f ( p ′′ , d ′′ ) = d f ( p )
Case 3: p ∈ P p \in\mathcal{P} p ∈ P f ( d ′ , p ′ ) > 0 f(d',p') > 0 f ( d ′ , p ′ ) > 0 f ( p ′ ′ , d ′ ′ ) = 0 f(p'',d'') = 0 f ( p ′′ , d ′′ ) = 0 d f ( p ) = f ( d ′ , p ′ ) d_f(p) = f(d',p') d f ( p ) = f ( d ′ , p ′ ) f ( p ′ , t ) = ℓ ( p ) f(p',t) = \ell(p) f ( p ′ , t ) = ℓ ( p ) f ( p ′ ′ , d ′ ′ ) = 0 f(p'',d'') = 0 f ( p ′′ , d ′′ ) = 0 ∣ M ( p ) ∣ = ℓ ( p ) − f ( d ′ , p ′ ) |M(p)| = \ell(p) - f(d',p') ∣ M ( p ) ∣ = ℓ ( p ) − f ( d ′ , p ′ ) d M ( p ) = f ( d ′ , p ′ ) = d f ( p ) d_M(p) = f(d',p') = d_f(p) d M ( p ) = f ( d ′ , p ′ ) = d f ( p )
Thus, for every post, the deviation with respect to a good flow and the deviation with respect to the corresponding matching are the same. This immediately implies that the total deviation of a good flow and that of the corresponding matching are the same.
It is not immediate how to compute a good flow in a flow network. However, given a feasible flow in H ( l d , u d ) H_{(l_d,u_d)} H ( l d , u d ) different flow network. We need the following notation. For an edge ( a , p ) (a,p) ( a , p ) G G G ⟨ s , a , p ′ , t ⟩ \langle s,a,p',t\rangle ⟨ s , a , p ′ , t ⟩ true path , and the path ⟨ s , a , p ′ ′ , d ′ ′ , t ⟩ \langle s,a,p'',d'',t\rangle ⟨ s , a , p ′′ , d ′′ , t ⟩ extended path . For a post p p p G G G ⟨ s , d ′ , p ′ , t ⟩ \langle s,d',p',t\rangle ⟨ s , d ′ , p ′ , t ⟩ dummy path . Note that, corresponding to an applicant a a a p p p G G G p p p G G G min { l d , u ( p ) } \min\{l_d,u(p)\} min { l d , u ( p )} f f f H ( l d , u d ) H_{(l_d,u_d)} H ( l d , u d ) p ∈ P p \in\mathcal{P} p ∈ P f f f p ′ , p ′ ′ p',p'' p ′ , p ′′ p p p bad with respect to the flow f f f
Suppose we have a bad post p p p G G G f f f p p p p p p
Definition 7 (correcting flow). Let f f f H ( l d , u d ) H_{(l_d,u_d)} H ( l d , u d ) p p p f f f f ′ f' f ′ H ( l d , u d ) H_{(l_d,u_d)} H ( l d , u d ) s s s t t t p p p f ′ f' f ′ f f f
(i) There exists a network H ( l d ′ , u d ′ ) H_{(l_{d'},u_{d'})} H ( l d ′ , u d ′ ) f ′ f' f ′ H ( l d ′ , u d ′ ) H_{(l_{d'},u_{d'})} H ( l d ′ , u d ′ ) l d ′ + u d ′ < l d + u d l_{d'} + u_{d'} < l_d + u_d l d ′ + u d ′ < l d + u d
(ii) The matchings corresponding to f f f f ′ f' f ′
(iii) Status of any post q ∈ P ∖ { p } q \in\mathcal{P} \setminus\{p\} q ∈ P ∖ { p } f f f f ′ f' f ′
We describe the types of a correcting flow f ′ f' f ′
( l d , u d ) (l_d,u_d) ( l d , u d ) p p p 1 ( i ) 1(i) 1 ( i ) f ( d ′ , p ′ ) > 0 f(d',p') > 0 f ( d ′ , p ′ ) > 0 f ( p ′ ′ , d ′ ′ ) > 0 f(p'',d'') > 0 f ( p ′′ , d ′′ ) > 0 p p p p p p ⟨ s , a , p ′ ′ , d ′ ′ , t ⟩ \langle s,a,p'',d'',t\rangle ⟨ s , a , p ′′ , d ′′ , t ⟩ ⟨ s , a , p ′ , t ⟩ \langle s,a,p',t\rangle ⟨ s , a , p ′ , t ⟩ f ′ f' f ′ H ( l d ′ , u d ′ ) H_{(l_{d'},u_{d'})} H ( l d ′ , u d ′ ) l d ′ = l d − 1 l_{d'} = l_d - 1 l d ′ = l d − 1 u d ′ = u d − 1 u_{d'} = u_d - 1 u d ′ = u d − 1
u d u_d u d p p p 1 ( i i ) 1(ii) 1 ( ii ) f ( p ′ ′ , d ′ ′ ) > 0 f(p'',d'') > 0 f ( p ′′ , d ′′ ) > 0 f ( p ′ , t ) < u ( p ) f(p',t) < u(p) f ( p ′ , t ) < u ( p ) p p p ⟨ s , a , p ′ ′ , d ′ ′ , t ⟩ \langle s,a,p'',d'',t\rangle ⟨ s , a , p ′′ , d ′′ , t ⟩ ⟨ s , a , p ′ , t ⟩ \langle s,a,p',t\rangle ⟨ s , a , p ′ , t ⟩ f ′ f' f ′ H ( l d ′ , u d ′ ) H_{(l_{d'},u_{d'})} H ( l d ′ , u d ′ ) l d ′ = l d l_{d'} = l_d l d ′ = l d u d ′ = u d − 1 u_{d'} = u_d - 1 u d ′ = u d − 1
l d l_d l d p p p 1 ( i i i ) 1(iii) 1 ( iii ) f ( d ′ , p ′ ) > 0 f(d',p') > 0 f ( d ′ , p ′ ) > 0 f ( p ′ , t ) > ℓ ( p ) f(p',t) > \ell(p) f ( p ′ , t ) > ℓ ( p ) p p p f ′ f' f ′ H ( l d ′ , u d ′ ) H_{(l_{d'},u_{d'})} H ( l d ′ , u d ′ ) l d ′ = l d − 1 l_{d'} = l_d - 1 l d ′ = l d − 1 u d ′ = u d u_{d'} = u_d u d ′ = u d
Note that in each of the above cases, if applicant a a a p p p p p p q ∈ P ∖ { p } q \in\mathcal{P} \setminus\{p\} q ∈ P ∖ { p } q q q f ′ f' f ′ Figure 4 (ii).
Lemma 2. If f f f H ( l d , u d ) H_{(l_d,u_d)} H ( l d , u d ) 1 1 1 f ∗ f^* f ∗ f f f H ( l d , u d ) H_{(l_d,u_d)} H ( l d , u d ) 1 1 1
Proof: Let p p p f f f p p p p ′ , p ′ ′ p',p'' p ′ , p ′′ p p p 1 ( i ) 1(i) 1 ( i ) f ( d ′ , p ′ ) > 0 f(d',p') > 0 f ( d ′ , p ′ ) > 0 f ( p ′ ′ , d ′ ′ ) > 0 f(p'',d'') > 0 f ( p ′′ , d ′′ ) > 0
x p = min { f ( d ′ , p ′ ) , f ( p ′ ′ , d ′ ′ ) } . x_p = \min\{f(d',p'), f(p'',d'')\}. x p = min { f ( d ′ , p ′ ) , f ( p ′′ , d ′′ )} . We apply x p x_p x p ( l d , u d ) (l_d,u_d) ( l d , u d ) f ′ f' f ′ ( d ′ , p ′ ) (d',p') ( d ′ , p ′ ) ( p ′ ′ , d ′ ′ ) (p'',d'') ( p ′′ , d ′′ ) f ′ f' f ′ p ′ p' p ′ p ′ ′ p'' p ′′ 1 ( i ) 1(i) 1 ( i ) f ′ f' f ′ p ′ p' p ′ p ′ ′ p'' p ′′
Case 1: f ′ ( d ′ , p ′ ) > 0 f'(d',p')>0 f ′ ( d ′ , p ′ ) > 0 f ′ ( p ′ ′ , d ′ ′ ) = 0 f'(p'',d'')=0 f ′ ( p ′′ , d ′′ ) = 0 p ′ , p ′ ′ p',p'' p ′ , p ′′ f ′ ( d ′ , p ′ ) > 0 f'(d',p')>0 f ′ ( d ′ , p ′ ) > 0 f ′ ( p ′ , t ) = u ( p ) > ℓ ( p ) f'(p',t)=u(p)>\ell(p) f ′ ( p ′ , t ) = u ( p ) > ℓ ( p ) p ′ , p ′ ′ p',p'' p ′ , p ′′
y p = min { f ′ ( d ′ , p ′ ) , f ′ ( p ′ , t ) − ℓ ( p ) } . y_p=\min\{f'(d',p'),f'(p',t)-\ell(p)\}. y p = min { f ′ ( d ′ , p ′ ) , f ′ ( p ′ , t ) − ℓ ( p )} . In this case, we apply y p y_p y p l d ld l d
Case 2: f ′ ( p ′ ′ , d ′ ′ ) > 0 f'(p'',d'')>0 f ′ ( p ′′ , d ′′ ) > 0 f ′ ( d ′ , p ′ ) = 0 f'(d',p')=0 f ′ ( d ′ , p ′ ) = 0 p ′ , p ′ ′ p',p'' p ′ , p ′′ f ′ ( p ′ ′ , d ′ ′ ) > 0 f'(p'',d'')>0 f ′ ( p ′′ , d ′′ ) > 0 f ′ ( p ′ , t ) = ℓ ( p ) < u ( p ) f'(p',t)=\ell(p)<u(p) f ′ ( p ′ , t ) = ℓ ( p ) < u ( p ) p ′ , p ′ ′ p',p'' p ′ , p ′′
z p = min { f ′ ( p ′ ′ , d ′ ′ ) , u ( p ) − f ′ ( p ′ , t ) } . z_p=\min\{f'(p'',d''),u(p)-f'(p',t)\}. z p = min { f ′ ( p ′′ , d ′′ ) , u ( p ) − f ′ ( p ′ , t )} . In this case, we apply z p z_p z p u d ud u d
Let f ~ \tilde{f} f ~ p ′ , p ′ ′ p',p'' p ′ , p ′′ p p p f ~ \tilde{f} f ~ f f f f ∗ f^* f ∗ H ( l d ′ , u d ′ ) H(ld',ud') H ( l d ′ , u d ′ ) l d ′ + u d ′ < l d + u d ld'+ud'<ld+ud l d ′ + u d ′ < l d + u d
We are ready to design our flow network based algorithm, which employs linear search over a specific range to compute an optimal matching. For an optimal matching M ∗ M^* M ∗ G G G
Claim 1. The total deviation of M ∗ M^* M ∗ ∑ p ∈ P ℓ ( p ) − ∣ A ∣ \sum_{p\in\mathcal{P}}\ell(p)-|\mathcal{A}| ∑ p ∈ P ℓ ( p ) − ∣ A ∣
Proof: Let l d ∗ ld^* l d ∗ M ∗ M^* M ∗ l d ∗ ≥ ∑ p ∈ P ℓ ( p ) − ∣ M ∗ ∣ ld^*\geq\sum_{p\in\mathcal{P}}\ell(p)-|M^*| l d ∗ ≥ ∑ p ∈ P ℓ ( p ) − ∣ M ∗ ∣ M ∗ M^* M ∗ d t o t ( M ∗ ) d_{\mathrm{tot}}(M^*) d tot ( M ∗ ) l d ∗ ld^* l d ∗ ∣ M ∗ ∣ ≤ ∣ A ∣ |M^*|\leq|\mathcal{A}| ∣ M ∗ ∣ ≤ ∣ A ∣ d t o t ( M ∗ ) d_{\mathrm{tot}}(M^*) d tot ( M ∗ ) ∑ p ∈ P ℓ ( p ) − ∣ A ∣ \sum_{p\in\mathcal{P}}\ell(p)-|\mathcal{A}| ∑ p ∈ P ℓ ( p ) − ∣ A ∣
Claim 2. The total deviation of M ∗ M^* M ∗ ∑ p ∈ P ℓ ( p ) + ∣ A ∣ \sum_{p\in\mathcal{P}}\ell(p)+|\mathcal{A}| ∑ p ∈ P ℓ ( p ) + ∣ A ∣
Proof: Observe that for any matching, the maximum value possible for upper deviation is ∣ A ∣ |\mathcal{A}| ∣ A ∣ ∑ p ∈ P ℓ ( p ) \sum_{p\in\mathcal{P}}\ell(p) ∑ p ∈ P ℓ ( p ) M ∗ M^* M ∗ ∑ p ∈ P ℓ ( p ) + ∣ A ∣ \sum_{p\in\mathcal{P}}\ell(p)+|\mathcal{A}| ∑ p ∈ P ℓ ( p ) + ∣ A ∣
Thus, it is enough to search for the value of total deviation Δ \Delta Δ [ max { 0 , ∑ p ∈ P ℓ ( p ) − ∣ A ∣ } , ∑ p ∈ P ℓ ( p ) + ∣ A ∣ ] \left[\max\left\{0,\sum_{p\in\mathcal{P}}\ell(p)-|\mathcal{A}|\right\},\sum_{p\in\mathcal{P}}\ell(p)+|\mathcal{A}|\right] [ max { 0 , ∑ p ∈ P ℓ ( p ) − ∣ A ∣ } , ∑ p ∈ P ℓ ( p ) + ∣ A ∣ ] Δ \Delta Δ Δ \Delta Δ l d ld l d u d ud u d H ( l d , u d ) H(ld,ud) H ( l d , u d )
To compute RMM-SIGN-MIN-TOT, we use linear search to find the optimum value of Δ \Delta Δ Δ \Delta Δ Δ + 1 \Delta+1 Δ + 1
Algorithm 1: Algorithm for RMM-SIGN-MIN-TOT
set l o w = max { 0 , ∑ p ∈ P ℓ ( p ) − ∣ A ∣ } \mathrm{low}=\max\{0,\sum_{p\in P}\ell(p)-|A|\} low = max { 0 , ∑ p ∈ P ℓ ( p ) − ∣ A ∣ } h i g h = ∑ p ∈ P ℓ ( p ) + ∣ A ∣ \mathrm{high}=\sum_{p\in P}\ell(p)+|A| high = ∑ p ∈ P ℓ ( p ) + ∣ A ∣ Δ = l o w \Delta=\mathrm{low} Δ = low
while Δ ≤ h i g h \Delta\le\mathrm{high} Δ ≤ high do
set f o u n d = 0 \mathrm{found}=0 found = 0
for each of the Δ + 1 \Delta+1 Δ + 1 Δ \Delta Δ l d \mathrm{ld} ld u d \mathrm{ud} ud Δ = l d + u d \Delta=\mathrm{ld}+\mathrm{ud} Δ = ld + ud do
construct H ( l d , u d ) H_{(\mathrm{ld},\mathrm{ud})} H ( ld , ud )
if H ( l d , u d ) H_{(\mathrm{ld},\mathrm{ud})} H ( ld , ud ) then
compute a min-cost flow f f f M M M
if σ ( M ) ⪰ R ρ \sigma(M)\succeq_R\rho σ ( M ) ⪰ R ρ then
set f o u n d = 1 \mathrm{found}=1 found = 1
if f o u n d = = 0 \mathrm{found}==0 found == 0 then
set Δ = Δ + 1 \Delta=\Delta+1 Δ = Δ + 1
else
return f ∗ = f f^*=f f ∗ = f M ∗ = M M^*=M M ∗ = M
deviation l d \mathrm{ld} ld u d \mathrm{ud} ud H ( l d , u d ) H_{(\mathrm{ld},\mathrm{ud})} H ( ld , ud ) f f f M M M f f f M M M σ ( M ) ⪰ R ρ \sigma(M)\succeq_R\rho σ ( M ) ⪰ R ρ Δ \Delta Δ
Correctness of the Algorithm for RMM-SIGN-MIN-TOT. Given the lower and upper bound for the deviation of the optimal matching M ∗ M^* M ∗ σ ( M ) ≺ R ρ \sigma(M)\prec_R\rho σ ( M ) ≺ R ρ ( l d , u d ) (\mathrm{ld},\mathrm{ud}) ( ld , ud )
Claim 3. If at Algorithm 1, σ ( M ) ≺ R ρ \sigma(M)\prec_R\rho σ ( M ) ≺ R ρ M ′ M' M ′ l d \mathrm{ld} ld u d \mathrm{ud} ud σ ( M ′ ) ⪰ R ρ \sigma(M')\succeq_R\rho σ ( M ′ ) ⪰ R ρ
Proof. Note that any matching in G G G l d \mathrm{ld} ld u d \mathrm{ud} ud H ( l d , u d ) H_{(\mathrm{ld},\mathrm{ud})} H ( ld , ud ) M M M f f f E 2 E_2 E 2 H ( l d , u d ) H_{(\mathrm{ld},\mathrm{ud})} H ( ld , ud ) M M M l d \mathrm{ld} ld u d \mathrm{ud} ud σ ( M ) ≺ R ρ \sigma(M)\prec_R\rho σ ( M ) ≺ R ρ l d \mathrm{ld} ld u d \mathrm{ud} ud ρ \rho ρ
Now assume that our algorithm outputs a solution. Let Δ ∗ \Delta^* Δ ∗ Δ \Delta Δ l d ∗ \mathrm{ld}^* ld ∗ u d ∗ \mathrm{ud}^* ud ∗ H ( l d ∗ , u d ∗ ) H_{(\mathrm{ld}^*,\mathrm{ud}^*)} H ( ld ∗ , ud ∗ ) f ∗ f^* f ∗ Δ ∗ \Delta^* Δ ∗
Claim 4. The flow f ∗ f^* f ∗ H ( l d ∗ , u d ∗ ) H_{(\mathrm{ld}^*,\mathrm{ud}^*)} H ( ld ∗ , ud ∗ )
Proof. If this is not the case, then f ∗ f^* f ∗ H ( l d ∗ , u d ∗ ) H_{(\mathrm{ld}^*,\mathrm{ud}^*)} H ( ld ∗ , ud ∗ ) f ′ f' f ′ H ( l d ′ , u d ′ ) H_{(\mathrm{ld}',\mathrm{ud}')} H ( ld ′ , ud ′ ) l d ′ + u d ′ < l d ∗ + u d ∗ \mathrm{ld}'+\mathrm{ud}'<\mathrm{ld}^*+\mathrm{ud}^* ld ′ + ud ′ < ld ∗ + ud ∗ f ∗ f^* f ∗ f ′ f' f ′ Δ ∗ \Delta^* Δ ∗
Since f ∗ f^* f ∗ H ( l d ∗ , u d ∗ ) H_{(l d^*,u d^*)} H ( l d ∗ , u d ∗ ) M ∗ M^* M ∗
Time complexity of Algorithm 1. For a flow network H = ( V H , E H ) H=(V_H,E_H) H = ( V H , E H ) T H = O ( ( ∣ E H ∣ log ∣ V H ∣ ) ( ∣ E H ∣ + ∣ V H ∣ log ∣ V H ∣ ) ) T_H=O((|E_H|\log|V_H|)(|E_H|+|V_H|\log|V_H|)) T H = O (( ∣ E H ∣ log ∣ V H ∣ ) ( ∣ E H ∣ + ∣ V H ∣ log ∣ V H ∣ )) [48 ] . Given an optimal total deviation value Δ ∗ \Delta^* Δ ∗ H H H Δ ∗ + 1 \Delta^*+1 Δ ∗ + 1 Δ ∗ \Delta^* Δ ∗ [ l o w , h i g h ] [\mathrm{low},\mathrm{high}] [ low , high ] l o w = max { 0 , ∑ p ∈ P ℓ ( p ) − ∣ A ∣ } \mathrm{low}=\max\{0,\sum_{p\in\mathcal{P}}\ell(p)-|\mathcal{A}|\} low = max { 0 , ∑ p ∈ P ℓ ( p ) − ∣ A ∣ } h i g h = ∑ p ∈ P ℓ ( p ) + ∣ A ∣ \mathrm{high}=\sum_{p\in\mathcal{P}}\ell(p)+|\mathcal{A}| high = ∑ p ∈ P ℓ ( p ) + ∣ A ∣ O ( ( ( 2 ∣ A ∣ ) ( ∑ p ∈ P ℓ ( p ) + ∣ A ∣ + 1 ) ⋅ T H ) O(((2|\mathcal{A}|)(\sum_{p\in\mathcal{P}}\ell(p)+|\mathcal{A}|+1)\cdot T_H) O ((( 2∣ A ∣ ) ( ∑ p ∈ P ℓ ( p ) + ∣ A ∣ + 1 ) ⋅ T H ) ℓ ( p ) \ell(p) ℓ ( p ) p p p ℓ ( p ) > ∣ A ∣ \ell(p)>|\mathcal{A}| ℓ ( p ) > ∣ A ∣ ℓ ( p ) \ell(p) ℓ ( p ) ∑ p ∈ P ℓ ( p ) \sum_{p\in\mathcal{P}}\ell(p) ∑ p ∈ P ℓ ( p ) p ∈ P p\in\mathcal{P} p ∈ P ℓ ( p ) ≤ ∣ A ∣ \ell(p)\le|\mathcal{A}| ℓ ( p ) ≤ ∣ A ∣
Illustration of algorithm for RMM-SIGN-MIN-TOT. Given the instance G G G Figure 1 and an input signature ( 4 , 0 , 0 , 3 ) (4,0,0,3) ( 4 , 0 , 0 , 3 ) [ l o w , h i g h ] [\mathrm{low},\mathrm{high}] [ low , high ] l o w = 0 \mathrm{low}=0 low = 0 h i g h = 12 \mathrm{high}=12 high = 12 Δ = 0 \Delta=0 Δ = 0 Δ = 1 \Delta=1 Δ = 1 Δ = 3 \Delta=3 Δ = 3 ( 2 , 1 ) (2,1) ( 2 , 1 ) ( 3 , 0 ) (3,0) ( 3 , 0 )
For Δ = 4 \Delta=4 Δ = 4 H ( l d , u d ) H_{(l d,u d)} H ( l d , u d ) ( l d , u d ) (l d,u d) ( l d , u d ) l d + u d = 4 l d+u d=4 l d + u d = 4 H ( 2 , 2 ) H_{(2,2)} H ( 2 , 2 ) f f f ( a 1 , p 1 ) (a_1,p_1) ( a 1 , p 1 ) ( a 3 , p 2 ) (a_3,p_2) ( a 3 , p 2 ) ( a 4 , p 7 ) (a_4,p_7) ( a 4 , p 7 ) ( a 5 , p 4 ) (a_5,p_4) ( a 5 , p 4 ) ( a 6 , p 6 ) (a_6,p_6) ( a 6 , p 6 ) f f f ⟨ s , a , p ′ , t ⟩ \langle s,a,p',t\rangle ⟨ s , a , p ′ , t ⟩ ( a 2 , p 1 ) (a_2,p_1) ( a 2 , p 1 ) ( a 7 , p 1 ) (a_7,p_1) ( a 7 , p 1 ) p 3 p_3 p 3 p 5 p_5 p 5
Observe that f f f H ( 2 , 2 ) H_{(2,2)} H ( 2 , 2 ) f f f M 3 M_3 M 3 Table 1 . Since σ ( M 3 ) ⪰ R ( 4 , 0 , 0 , 3 ) \sigma(M_3)\succeq_{\mathcal{R}}(4,0,0,3) σ ( M 3 ) ⪰ R ( 4 , 0 , 0 , 3 ) M 3 M_3 M 3
Modification for Fairness
For solving the problem FAIR-SIGN-MIN-TOT, we construct the same network H ( l d , u d ) H_{(l d,u d)} H ( l d , u d ) Figure 3 , where l d + u d = Δ l d+u d=\Delta l d + u d = Δ H ( l d , u d ) H_{(l d,u d)} H ( l d , u d ) E 2 \mathcal{E}_2 E 2
For an edge ( a , p ′ ) (a,p') ( a , p ′ ) ( a , p ′ ′ ) (a,p'') ( a , p ′′ ) E 2 \mathcal{E}_2 E 2 ( a , p ) (a,p) ( a , p ) G G G i i i ( n + 1 ) i (n+1)^i ( n + 1 ) i
We have the following lemma regarding the above cost assignment.
Lemma 3. Let M , M ′ M,M' M , M ′ σ ( M ) ≻ F σ ( M ′ ) \sigma(M)\succ_{\mathcal{F}}\sigma(M') σ ( M ) ≻ F σ ( M ′ ) c o s t ( M ) < c o s t ( M ′ ) cost(M)<cost(M') cos t ( M ) < cos t ( M ′ ) i i i ( n + 1 ) i (n+1)^i ( n + 1 ) i r + 1 r+1 r + 1 ( n + 1 ) r + 1 (n+1)^{r+1} ( n + 1 ) r + 1
Note that our algorithm and proofs can be easily modified with respect to the notion of fairness.
Minimizing Total Deviation: Deviation First
In this section, we present the results for minimizing total deviation for the deviation first, preference optimality next type of problems.
Algorithm for RMM-MIN-TOT
Given an instance of the soft quota setting, our goal is to compute a matching that is rank-maximal among all matchings that have a minimum value of total deviation. First, we consider the simpler problem of computing a minimum total deviation matching in G G G ignoring applicant preferences.
Given an instance G G G G x G_x G x p p p q − ( p ) q^{-}(p) q − ( p ) q + ( p ) q^{+}(p) q + ( p ) M M M p ∈ P p \in\mathcal{P} p ∈ P q − ( p ) ≤ ∣ M ( p ) ∣ ≤ q + ( p ) q^{-}(p) \leq|M(p)| \leq q^{+}(p) q − ( p ) ≤ ∣ M ( p ) ∣ ≤ q + ( p ) G G G G x G_x G x G x G_x G x M M M M M M G G G M M M G G G G x G_x G x G G G
We observe that in an optimal matching M ∗ M^* M ∗ G G G p p p u ( p ) u(p) u ( p ) M ∗ M^* M ∗ ∣ M ∗ ( p ) ∣ − u ( p ) |M^*(p)| - u(p) ∣ M ∗ ( p ) ∣ − u ( p ) p p p M ∗ M^* M ∗ G G G G x G_x G x
Minimizing total deviation. Given the instance G G G G ′ G' G ′ p p p ℓ ′ ( p ) = u ′ ( p ) = ℓ ( p ) \ell'(p) = u'(p) = \ell(p) ℓ ′ ( p ) = u ′ ( p ) = ℓ ( p ) G x ′ G'_x G x ′ q − ( p ) = 0 q^{-}(p) = 0 q − ( p ) = 0 q + ( p ) = ℓ ( p ) q^{+}(p) = \ell(p) q + ( p ) = ℓ ( p ) p p p G x ′ G'_x G x ′ G ′ G' G ′
Lemma 4. Any maximum matching in G x ′ G'_x G x ′ G ′ G' G ′
Proof: Let M ′ M' M ′ G x ′ G'_x G x ′ M ′ M' M ′ G x ′ G'_x G x ′ M ′ M' M ′ G ′ G' G ′ M M M G ′ G' G ′ d t o t ( M ) d_{\mathrm{tot}}(M) d tot ( M ) G ′ G' G ′ d t o t ( M ′ ) d_{\mathrm{tot}}(M') d tot ( M ′ ) G ′ G' G ′ M M M G ′ G' G ′ p p p ∣ M ( p ) ∣ ≤ ℓ ( p ) |M(p)| \leq\ell(p) ∣ M ( p ) ∣ ≤ ℓ ( p ) G x ′ G'_x G x ′ M M M M ′ M' M ′ u ′ ( p ) = ℓ ( p ) u'(p) = \ell(p) u ′ ( p ) = ℓ ( p ) p p p ∣ M ∣ = ∑ p ∈ P ℓ ( p ) − d t o t ( M ) |M| = \sum_{p \in\mathcal{P}} \ell(p) - d_{\mathrm{tot}}(M) ∣ M ∣ = ∑ p ∈ P ℓ ( p ) − d tot ( M ) ∣ M ′ ∣ = ∑ p ∈ P ℓ ( p ) − d t o t ( M ′ ) |M'| = \sum_{p \in\mathcal{P}} \ell(p) - d_{\mathrm{tot}}(M') ∣ M ′ ∣ = ∑ p ∈ P ℓ ( p ) − d tot ( M ′ ) ∣ M ∣ > ∣ M ′ ∣ |M| > |M'| ∣ M ∣ > ∣ M ′ ∣ M ′ M' M ′ G x ′ G'_x G x ′
Now we establish an interesting connection between the minimum value of total deviation in the soft quota instance G ′ G' G ′ G G G
Lemma 5. The minimum value of total deviation of G ′ G' G ′ G G G
Proof: Let k ′ k' k ′ G ′ G' G ′ k ′ k' k ′ G ′ G' G ′ G ′ ⊆ G G' \subseteq G G ′ ⊆ G G G G k k k k ≤ k ′ k \le k' k ≤ k ′ k < k ′ k < k' k < k ′ M M M G G G k k k G G G
In the soft quota setting instance G ′ G' G ′ M M M G ′ G' G ′ p p p u ′ ( p ) = ℓ ( p ) u'(p) = \ell(p) u ′ ( p ) = ℓ ( p ) u ( p ) u(p) u ( p ) G G G M ′ M' M ′ G ′ G' G ′ p p p max { 0 , ∣ M ( p ) ∣ − ℓ ( p ) } \max\{0, |M(p)| - \ell(p)\} max { 0 , ∣ M ( p ) ∣ − ℓ ( p )} p p p G ′ G' G ′ M ′ M' M ′ M ′ M' M ′ G ′ G' G ′ k k k M M M G G G k ′ k' k ′ G ′ G' G ′
By Lemma 4 and Lemma 5, any maximum matching M ′ M' M ′ G x ′ G'_x G x ′ G G G M ′ M' M ′ G G G G x G_x G x p p p G x G_x G x q + ( p ) = u ( p ) q^+(p) = u(p) q + ( p ) = u ( p ) M ′ M' M ′ G x G_x G x M ′ M' M ′ G x G_x G x
For an illustration, consider the soft quota instance G G G Figure 1 . We construct the soft quota instance G ′ G' G ′ G x ′ G'_x G x ′ M ′ = { ( a 1 , p 1 ) , ( a 3 , p 3 ) , ( a 5 , p 5 ) } M' = \{(a_1,p_1),(a_3,p_3),(a_5,p_5)\} M ′ = {( a 1 , p 1 ) , ( a 3 , p 3 ) , ( a 5 , p 5 )} G x ′ G'_x G x ′ M ′ M' M ′ G x G_x G x M = { ( a 1 , p 1 ) , ( a 3 , p 3 ) , ( a 5 , p 5 ) , ( a 6 , p 7 ) , ( a 7 , p 6 ) } M = \{(a_1,p_1),(a_3,p_3),(a_5,p_5),(a_6,p_7),(a_7,p_6)\} M = {( a 1 , p 1 ) , ( a 3 , p 3 ) , ( a 5 , p 5 ) , ( a 6 , p 7 ) , ( a 7 , p 6 )} M M M G x G_x G x 2 2 2 G G G
Since we disregarded preferences, the above procedure does not guarantee a matching that is optimal with respect to the preferences. For example, the matching M M M G G G M 1 M_1 M 1 Table 1 ) is more rank-maximal than M M M G G G
We construct the instance G ′ G' G ′ G G G M M M G ′ G' G ′
We augment the matching M M M G x G_x G x M ∗ M^* M ∗ G G G M ∗ M^* M ∗
Step (A): Computing RMM-MIN-TOT in G ′ G' G ′ G ′ G' G ′ H H H M M M H H H
M M M G ′ G' G ′ G G G
M M M G ′ G' G ′ M M M G G G
We construct the flow network H H H p p p ℓ ( p ) \ell(p) ℓ ( p ) D p \mathcal{D}_p D p D = ⋃ p ∈ P D p \mathcal{D} = \bigcup_{p\in\mathcal{P}} \mathcal{D}_p D = ⋃ p ∈ P D p H H H
V ( H ) = { s , t } ∪ ( A ∪ D ) ∪ P . V(H) = \{s,t\} \cup(\mathcal{A} \cup\mathcal{D}) \cup\mathcal{P}. V ( H ) = { s , t } ∪ ( A ∪ D ) ∪ P . The edge set E ( H ) E(H) E ( H )
E s A = { ( s , a ) : a ∈ A } \mathcal{E}_{sA}=\{(s,a):a\in\mathcal{A}\} E s A = {( s , a ) : a ∈ A } E s D = { ( s , d ) : d ∈ D p , p ∈ P } \mathcal{E}_{sD}=\{(s,d):d\in\mathcal{D}_p,p\in\mathcal{P}\} E sD = {( s , d ) : d ∈ D p , p ∈ P } E A P = { ( a , p ) : a ∈ A , p ∈ P } \mathcal{E}_{AP}=\{(a,p):a\in\mathcal{A},p\in\mathcal{P}\} E A P = {( a , p ) : a ∈ A , p ∈ P } E D P = { ( d , p ) : d ∈ D p , p ∈ P } \mathcal{E}_{DP}=\{(d,p):d\in\mathcal{D}_p,p\in\mathcal{P}\} E D P = {( d , p ) : d ∈ D p , p ∈ P } E P t = { ( p , t ) : p ∈ P } \mathcal{E}_{Pt}=\{(p,t):p\in\mathcal{P}\} E P t = {( p , t ) : p ∈ P } Cost of the edges in H H H For an edge ( a , p ) (a,p) ( a , p ) G ′ G' G ′ i i i E A P \mathcal{E}_{AP} E A P − ( ( n + 1 ) r + ( n + 1 ) r − i ) -((n+1)^r+(n+1)^{r-i}) − (( n + 1 ) r + ( n + 1 ) r − i ) H H H
Capacity of the edges in H H H For an edge ( p , t ) (p,t) ( p , t ) E P t \mathcal{E}_{Pt} E P t ℓ ( p ) \ell(p) ℓ ( p ) H H H
Consider the cut { t , V ( H ) ∖ { t } } \{t,V(H)\setminus\{t\}\} { t , V ( H ) ∖ { t }} ∑ p ∈ P ℓ ( p ) \sum_{p\in\mathcal{P}}\ell(p) ∑ p ∈ P ℓ ( p ) ∑ p ∈ P ℓ ( p ) \sum_{p\in\mathcal{P}}\ell(p) ∑ p ∈ P ℓ ( p ) p p p ⟨ s , d , p , t ⟩ \langle s,d,p,t\rangle ⟨ s , d , p , t ⟩ d ∈ D p d\in\mathcal{D}_p d ∈ D p ∑ p ∈ P ℓ ( p ) \sum_{p\in\mathcal{P}}\ell(p) ∑ p ∈ P ℓ ( p ) H H H ∑ p ∈ P ℓ ( p ) \sum_{p\in\mathcal{P}}\ell(p) ∑ p ∈ P ℓ ( p ) f f f H H H
Definition 8 (Total deviation of a max-flow). The total deviation of a max-flow f f f H H H
d t o t ( f ) = ∑ p ∈ P d f ( p ) d_{\mathrm{tot}}(f)=\sum_{p\in\mathcal{P}}d_f(p) d tot ( f ) = p ∈ P ∑ d f ( p ) where
d f ( p ) = ∑ d ∈ D p f ( d , p ) d_f(p)=\sum_{d\in\mathcal{D}_p}f(d,p) d f ( p ) = d ∈ D p ∑ f ( d , p ) is the incoming flow to the vertex p p p
There is a natural correspondence between a flow f f f H H H M M M G ′ G' G ′
M f = { ( a , p ) ∣ f ( a , p ) = 1 , ( a , p ) ∈ E A P } . M_f=\{(a,p)\mid f(a,p)=1,\ (a,p)\in\mathcal{E}_{AP}\}. M f = {( a , p ) ∣ f ( a , p ) = 1 , ( a , p ) ∈ E A P } . Cost of a max-flow in H H H G ′ G' G ′ For a max-flow f f f H H H c o s t ( f ) cost(f) cos t ( f )
c o s t ( f ) = ∑ e ∈ E ( H ) f ( e ) ⋅ c ( e ) cost(f)=\sum_{e\in E(H)}f(e)\cdot c(e) cos t ( f ) = e ∈ E ( H ) ∑ f ( e ) ⋅ c ( e ) where f ( e ) f(e) f ( e ) c ( e ) c(e) c ( e ) e e e H H H H H H G ′ G' G ′
Lemma 6. Let f , f ′ f,f' f , f ′ H H H M f , M f ′ M_f,M_{f'} M f , M f ′ G ′ G' G ′ ∣ M f ∣ > ∣ M f ′ ∣ |M_f|>|M_{f'}| ∣ M f ∣ > ∣ M f ′ ∣ c o s t ( f ) < c o s t ( f ′ ) cost(f)<cost(f') cos t ( f ) < cos t ( f ′ )
Proof. For a post p p p E D P \mathcal{E}_{DP} E D P E A P \mathcal{E}_{AP} E A P H H H E A P \mathcal{E}_{AP} E A P E A P \mathcal{E}_{AP} E A P f f f
c o s t ( f ) ≤ ∣ M f ∣ ( − ( n + 1 ) r ) − ∣ M f ∣ cost(f)\leq|M_f|\left(-(n+1)^r\right)-|M_f| cos t ( f ) ≤ ∣ M f ∣ ( − ( n + 1 ) r ) − ∣ M f ∣ where the equality is achieved when all edges are of rank r r r f ′ f' f ′
c o s t ( f ′ ) ≥ ∣ M f ′ ∣ ( − ( n + 1 ) r ) − ∣ M f ′ ∣ ( ( n + 1 ) r − 1 ) cost(f') \ge|M_{f'}|\left(-(n+1)^r\right)-|M_{f'}|\left((n+1)^{r-1}\right) cos t ( f ′ ) ≥ ∣ M f ′ ∣ ( − ( n + 1 ) r ) − ∣ M f ′ ∣ ( ( n + 1 ) r − 1 ) and the equality is achieved when all edges are of rank 1. To show that c o s t ( f ) < c o s t ( f ′ ) cost(f) < cost(f') cos t ( f ) < cos t ( f ′ )
∣ M f ∣ ( ( n + 1 ) r ) + ∣ M f ∣ > ∣ M f ′ ∣ ( ( n + 1 ) r ) + ∣ M f ′ ∣ ( ( n + 1 ) r − 1 ) . |M_f|\left((n+1)^r\right)+|M_f|>|M_{f'}|\left((n+1)^r\right)+|M_{f'}|\left((n+1)^{r-1}\right). ∣ M f ∣ ( ( n + 1 ) r ) + ∣ M f ∣ > ∣ M f ′ ∣ ( ( n + 1 ) r ) + ∣ M f ′ ∣ ( ( n + 1 ) r − 1 ) . Since ∣ M f ∣ − ∣ M f ′ ∣ ≥ 1 |M_f|-|M_{f'}|\ge1 ∣ M f ∣ − ∣ M f ′ ∣ ≥ 1 ∣ M f ′ ∣ ≤ n |M_{f'}|\le n ∣ M f ′ ∣ ≤ n
( ∣ M f ∣ − ∣ M f ′ ∣ ) ( n + 1 ) r + ∣ M f ∣ − ∣ M f ′ ∣ ( n + 1 ) r − 1 ≥ ( n + 1 ) r + ∣ M f ∣ − n ( n + 1 ) r − 1 = ( n + 1 ) r − 1 + ∣ M f ∣ > 0. \begin{aligned}
\left(|M_f|-|M_{f'}|\right)(n+1)^r+|M_f|-|M_{f'}|(n+1)^{r-1}\ge(n+1)^r+|M_f|-n(n+1)^{r-1} \\
&= (n+1)^{r-1}+|M_f|>0.
\end{aligned} ( ∣ M f ∣ − ∣ M f ′ ∣ ) ( n + 1 ) r + ∣ M f ∣ − ∣ M f ′ ∣ ( n + 1 ) r − 1 ≥ ( n + 1 ) r + ∣ M f ∣ − n ( n + 1 ) r − 1 = ( n + 1 ) r − 1 + ∣ M f ∣ > 0. Thus, c o s t ( f ) < c o s t ( f ′ ) cost(f)<cost(f') cos t ( f ) < cos t ( f ′ )
Lemma 7. Let f f f H H H M f M_f M f G ′ G' G ′ M f M_f M f G ′ G' G ′
Proof. Suppose not, let M ∗ M^* M ∗ G ′ G' G ′ f ∗ f^* f ∗ G ′ G' G ′ p p p ℓ ′ ( p ) = u ′ ( p ) = ℓ ( p ) \ell'(p)=u'(p)=\ell(p) ℓ ′ ( p ) = u ′ ( p ) = ℓ ( p ) M ∗ M^* M ∗ ∣ M ∗ ∣ > ∣ M f ∣ |M^*|>|M_f| ∣ M ∗ ∣ > ∣ M f ∣ c o s t ( f ∗ ) < c o s t ( f ) cost(f^*)<cost(f) cos t ( f ∗ ) < cos t ( f )
Given the connection between the total deviations of G G G G ′ G' G ′ G G G G ′ G' G ′
Corollary 1. Any min-cost flow in H H H G G G
We now prove the preference optimality of the matching obtained in Step (A).
Lemma 8. Any min-cost flow in H H H G ′ G' G ′
Proof. Let f f f H H H M f M_f M f G ′ G' G ′ M f M_f M f G ′ G' G ′ M f M_f M f G ′ G' G ′ M f ′ M_{f'} M f ′ G ′ G' G ′ f ′ f' f ′ H H H M f ′ M_{f'} M f ′ ∣ M f ∣ = ∣ M f ′ ∣ |M_f|=|M_{f'}| ∣ M f ∣ = ∣ M f ′ ∣
Since σ ( M f ′ ) ≻ R σ ( M f ) \sigma(M_{f'})\succ_R\sigma(M_f) σ ( M f ′ ) ≻ R σ ( M f ) i i i σ ( M f ′ ) j ≻ R σ ( M f ) j \sigma(M_{f'})_j\succ_R\sigma(M_f)_j σ ( M f ′ ) j ≻ R σ ( M f ) j σ ( M f ′ ) j = σ ( M f ) j \sigma(M_{f'})_j=\sigma(M_f)_j σ ( M f ′ ) j = σ ( M f ) j j < i j<i j < i i i i G ′ G' G ′ E \mathcal{E} E − ( n + 1 ) r + ( n + 1 ) r − i -(n+1)^r+(n+1)^{r-i} − ( n + 1 ) r + ( n + 1 ) r − i H H H
Since ∣ M f ∣ = ∣ M f ′ ∣ |M_f|=|M_{f'}| ∣ M f ∣ = ∣ M f ′ ∣ − ( n + 1 ) r -(n+1)^r − ( n + 1 ) r c o s t ( f ′ ) cost(f') cos t ( f ′ ) c o s t ( f ) cost(f) cos t ( f ) c o s t ( f ′ ) < c o s t ( f ) cost(f')<cost(f) cos t ( f ′ ) < cos t ( f )
We observe that every minimum total deviation matching in G G G ∣ M ∣ |M| ∣ M ∣
Lemma 9. Let N N N G G G d t o t ( N ) = d t o t ( M ) d_{\mathrm{tot}}(N)=d_{\mathrm{tot}}(M) d tot ( N ) = d tot ( M ) ∣ N ∣ ≥ ∣ M ∣ |N|\ge|M| ∣ N ∣ ≥ ∣ M ∣
Proof: Since M M M G ′ G' G ′ d t o t ( M ) = ∑ p ∈ P ℓ ( p ) − ∣ M ∣ d_{\mathrm{tot}}(M)=\sum_{p\in P}\ell(p)-|M| d tot ( M ) = ∑ p ∈ P ℓ ( p ) − ∣ M ∣ N N N G G G d t o t ( N ) ≥ ∑ p ∈ P ℓ ( p ) − ∣ N ∣ d_{\mathrm{tot}}(N)\ge\sum_{p\in P}\ell(p)-|N| d tot ( N ) ≥ ∑ p ∈ P ℓ ( p ) − ∣ N ∣ d t o t ( N ) = d t o t ( M ) d_{\mathrm{tot}}(N)=d_{\mathrm{tot}}(M) d tot ( N ) = d tot ( M ) ∑ p ∈ P ℓ ( p ) − ∣ M ∣ ≥ ∑ p ∈ P ℓ ( p ) − ∣ N ∣ \sum_{p\in P}\ell(p)-|M|\ge\sum_{p\in P}\ell(p)-|N| ∑ p ∈ P ℓ ( p ) − ∣ M ∣ ≥ ∑ p ∈ P ℓ ( p ) − ∣ N ∣ ∣ N ∣ ≥ ∣ M ∣ |N|\ge|M| ∣ N ∣ ≥ ∣ M ∣
In Step (A), we compute a matching M M M G ′ G' G ′ M ∗ M^* M ∗ G G G M M M G x G_x G x M M M j j j M j M_j M j ∣ M ∣ + j |M|+j ∣ M ∣ + j G x G_x G x d t o t ( M ) = d t o t ( M j ) d_{\mathrm{tot}}(M)=d_{\mathrm{tot}}(M_j) d tot ( M ) = d tot ( M j )
Step (B): Computing a solution for RMM-MIN-TOT in G G G M M M Our algorithm is iterative, and we begin with the matching M 0 = M M_0=M M 0 = M j − 1 j-1 j − 1 M j − 1 M_{j-1} M j − 1 ∣ M ∣ + j − 1 |M|+j-1 ∣ M ∣ + j − 1 d t o t ( M ) d_{\mathrm{tot}}(M) d tot ( M ) j j j M j − 1 M_{j-1} M j − 1 G x G_x G x s s s t t t H j H_j H j M j M_j M j ∣ M ∣ + j |M|+j ∣ M ∣ + j d t o t ( M ) d_{\mathrm{tot}}(M) d tot ( M ) M ∗ = M 0 M^*=M_0 M ∗ = M 0 M j M_j M j σ ( M j ) ≻ R σ ( M ∗ ) \sigma(M_j)\succ_R\sigma(M^*) σ ( M j ) ≻ R σ ( M ∗ ) M ∗ = M j M^*=M_j M ∗ = M j H j H_j H j s s s t t t M ∗ M^* M ∗
We now describe the construction of the directed graph H j H_j H j H j H_j H j
V ( H j ) = { s , t } ∪ A ∪ P . V(H_j)=\{s,t\}\cup A\cup P. V ( H j ) = { s , t } ∪ A ∪ P . Let A ′ A' A ′ M j − 1 M_{j-1} M j − 1 P ′ P' P ′ ℓ ( p ) ≤ ∣ M j − 1 ( p ) ∣ < u ( p ) \ell(p)\le|M_{j-1}(p)|<u(p) ℓ ( p ) ≤ ∣ M j − 1 ( p ) ∣ < u ( p ) p ∈ P ′ p\in P' p ∈ P ′ d M j − 1 ( p ) = 0 d_{M_{j-1}}(p)=0 d M j − 1 ( p ) = 0 P ′ P' P ′ P ′ P' P ′
For any iteration j j j p p p ∣ M j − 1 ( p ) ∣ < ℓ ( p ) |M_{j-1}(p)|<\ell(p) ∣ M j − 1 ( p ) ∣ < ℓ ( p ) p p p M j − 1 M_{j-1} M j − 1 a a a p p p M j − 1 M_{j-1} M j − 1 ( a , p ) (a,p) ( a , p ) M j − 1 M_{j-1} M j − 1 p p p j = 0 j=0 j = 0 M 0 = M M_0=M M 0 = M G ′ G' G ′ G G G
In an optimal matching, no post incurs a deviation from the upper target.
Now, we define our edge set E ( H j ) E(H_j) E ( H j )
E ( H j ) = E s A ′ ∪ E A P ∪ E P A ∪ E P ′ t where, E s A ′ = { ( s , a ) : a ∈ A ′ } E A P = { ( a , p ) : ( a , p ) ∈ E ∖ M j − 1 } E P A = { ( p , a ) : ( a , p ) ∈ E ∩ M j − 1 } E P ′ t = { ( p , t ) : p ∈ P ′ } \begin{aligned}
E(H_j)&=\mathcal{E}_{sA'}\cup\mathcal{E}_{AP}\cup\mathcal{E}_{PA}\cup\mathcal{E}_{P't}\text{ where,}\\
\mathcal{E}_{sA'}&=\{(s,a):a\in A'\}\\
\mathcal{E}_{AP}&=\{(a,p):(a,p)\in E\setminus M_{j-1}\}\\
\mathcal{E}_{PA}&=\{(p,a):(a,p)\in E\cap M_{j-1}\}\\
\mathcal{E}_{P't}&=\{(p,t):p\in P'\}
\end{aligned} E ( H j ) E s A ′ E A P E P A E P ′ t = E s A ′ ∪ E A P ∪ E P A ∪ E P ′ t where, = {( s , a ) : a ∈ A ′ } = {( a , p ) : ( a , p ) ∈ E ∖ M j − 1 } = {( p , a ) : ( a , p ) ∈ E ∩ M j − 1 } = {( p , t ) : p ∈ P ′ } Cost of the edges in H j H_j H j ( a , p ) ∈ E (a,p) \in E ( a , p ) ∈ E i i i
if ( a , p ) ∈ E A P (a,p) \in\mathcal{E}_{AP} ( a , p ) ∈ E A P − ( n + 1 ) r − i -(n+1)^{r-i} − ( n + 1 ) r − i
if ( p , a ) ∈ E P A (p,a) \in\mathcal{E}_{PA} ( p , a ) ∈ E P A ( n + 1 ) r − i (n+1)^{r-i} ( n + 1 ) r − i
All other edges in H j H_j H j 0 0 0
The following observation establishes the correspondence between the alternating components in the symmetric difference of two matchings and the directed graph H j H_j H j
Observation 3. Let N N N G x G_x G x ∣ M ∣ + j |M|+j ∣ M ∣ + j d t o t ( M ) d_{\mathrm{tot}}(M) d tot ( M ) M j − 1 ⊕ N M_{j-1} \oplus N M j − 1 ⊕ N H j H_j H j M j − 1 ⊕ N M_{j-1} \oplus N M j − 1 ⊕ N s s s t t t H j H_j H j
We now prove an important property of the directed graph H j H_j H j
Claim 5. There are no negative cost directed cycles in H j H_j H j
Proof: We prove the claim by induction on the number of iterations. Base case is trivial as the initial matching M 0 = M M_0=M M 0 = M ∣ M ∣ |M| ∣ M ∣ d t o t ( M ) d_{\mathrm{tot}}(M) d tot ( M ) M j − 1 M_{j-1} M j − 1 ∣ M ∣ + j − 1 |M|+j-1 ∣ M ∣ + j − 1 d t o t ( M ) d_{\mathrm{tot}}(M) d tot ( M ) H j H_j H j C C C H j H_j H j C C C M j − 1 M_{j-1} M j − 1
Let M ′ = M j − 1 ⊕ C M'=M_{j-1} \oplus C M ′ = M j − 1 ⊕ C C C C ∣ M ′ ∣ = ∣ M j − 1 ∣ = ∣ M ∣ + j − 1 |M'|=|M_{j-1}|=|M|+j-1 ∣ M ′ ∣ = ∣ M j − 1 ∣ = ∣ M ∣ + j − 1 d t o t ( M ′ ) = d t o t ( M j − 1 ) = d t o t ( M ) d_{\mathrm{tot}}(M')=d_{\mathrm{tot}}(M_{j-1})=d_{\mathrm{tot}}(M) d tot ( M ′ ) = d tot ( M j − 1 ) = d tot ( M ) C C C cost ( M ′ ) < cost ( M j − 1 ) \operatorname{cost}(M')<\operatorname{cost}(M_{j-1}) cost ( M ′ ) < cost ( M j − 1 ) σ ( M ′ ) ≻ R σ ( M j − 1 ) \sigma(M') \succ_R \sigma(M_{j-1}) σ ( M ′ ) ≻ R σ ( M j − 1 ) H j H_j H j
Now we describe our augmentation process. Let T j ′ T'_j T j ′ s s s t t t H j H_j H j T j = T j ′ ∩ E T_j=T'_j \cap E T j = T j ′ ∩ E G x G_x G x H j H_j H j T j T_j T j M j − 1 M_{j-1} M j − 1 M j − 1 M_{j-1} M j − 1 T j T_j T j M j = M j − 1 ⊕ T j M_j=M_{j-1} \oplus T_j M j = M j − 1 ⊕ T j
For a set S ⊆ E S \subseteq E S ⊆ E # i ( S ) \#_i(S) # i ( S ) i i i S S S
Definition 9 (Signature of a path T j T_j T j T j T_j T j M j − 1 M_{j-1} M j − 1 r r r ( x 1 , x 2 , … , x r ) (x_1,x_2,\ldots,x_r) ( x 1 , x 2 , … , x r ) σ ( T j ) \sigma(T_j) σ ( T j )
x i = # i ( T j ∩ M j − 1 ) − # i ( T j ∖ M j − 1 ) x_i=\#_i(T_j \cap M_{j-1})-\#_i(T_j \setminus M_{j-1}) x i = # i ( T j ∩ M j − 1 ) − # i ( T j ∖ M j − 1 ) Note that, unlike the signature of a matching, which contains non-negative values, σ ( T j ) \sigma(T_j) σ ( T j ) σ ( T j ) \sigma(T_j) σ ( T j ) cost ( T j ) \operatorname{cost}(T_j) cost ( T j )
cost ( T j ) = ∑ i = 1 r x i ( n + 1 ) r − i . \operatorname{cost}(T_j)=\sum_{i=1}^{r}x_i(n+1)^{r-i}. cost ( T j ) = i = 1 ∑ r x i ( n + 1 ) r − i . We observe the following:
Observation 4. ∑ i = 1 r x i = − 1 \sum_{i=1}^{r} x_i=-1 ∑ i = 1 r x i = − 1
Since T j T_j T j T j T_j T j T j T_j T j σ ( M j − 1 ) = ( y 1 , y 2 , … , y r ) \sigma(M_{j-1})=(y_1,y_2,\ldots,y_r) σ ( M j − 1 ) = ( y 1 , y 2 , … , y r ) i i i x i x_i x i i i i M j − 1 M_{j-1} M j − 1
Observation 5. For any i ∈ [ r ] i\in[r] i ∈ [ r ] x i ≤ y i x_i\le y_i x i ≤ y i
Since M j = M j − 1 ⊕ T j M_j=M_{j-1}\oplus T_j M j = M j − 1 ⊕ T j σ ( M j ) = σ ( M j − 1 ) − σ ( T j ) \sigma(M_j)=\sigma(M_{j-1})-\sigma(T_j) σ ( M j ) = σ ( M j − 1 ) − σ ( T j )
Observation 6. Every component in σ ( M j ) \sigma(M_j) σ ( M j )
Observation 6 follows from Observation 5. We state a series of claims to prove the correctness of Step (B). We ensure that our augmentations do not change the value of total deviation of the resulting matching, and this is stated in Claim 6.
Claim 6. If d t o t ( M ) = k d_{\mathrm{tot}}(M)=k d tot ( M ) = k d t o t ( M j ) = k d_{\mathrm{tot}}(M_j)=k d tot ( M j ) = k
Proof: We need to show that at each iteration j j j j = 0 j=0 j = 0 M 0 = M M_0=M M 0 = M k k k M j − 1 M_{j-1} M j − 1 j − 1 j-1 j − 1 k k k T j ′ T'_j T j ′ s s s t t t H j H_j H j T j T_j T j j j j T j T_j T j a a a M j − 1 M_{j-1} M j − 1 p p p ℓ ( p ) ≤ ∣ M j − 1 ( p ) ∣ < u ( p ) \ell(p)\le|M_{j-1}(p)|<u(p) ℓ ( p ) ≤ ∣ M j − 1 ( p ) ∣ < u ( p ) M j − 1 M_{j-1} M j − 1 T j T_j T j p ′ ≠ p p'\ne p p ′ = p P \mathcal{P} P ∣ M j ( p ′ ) ∣ = ∣ M j − 1 ( p ′ ) ∣ |M_j(p')|=|M_{j-1}(p')| ∣ M j ( p ′ ) ∣ = ∣ M j − 1 ( p ′ ) ∣ p p p ∣ M j ( p ) ∣ = ∣ M j − 1 ( p ) ∣ + 1 |M_j(p)|=|M_{j-1}(p)|+1 ∣ M j ( p ) ∣ = ∣ M j − 1 ( p ) ∣ + 1 ℓ ( p ) ≤ ∣ M j − 1 ( p ) ∣ < u ( p ) \ell(p)\le|M_{j-1}(p)|<u(p) ℓ ( p ) ≤ ∣ M j − 1 ( p ) ∣ < u ( p ) p p p d t o t ( M j ) = k d_{\mathrm{tot}}(M_j)=k d tot ( M j ) = k k k k
Next, we show that as the cost of path decreases, signature of the path with respect to rank-maximality also decreases.
Claim 7. Let T j ′ T'_j T j ′ Q j ′ Q'_j Q j ′ s s s t t t H j H_j H j M T = M j − 1 ⊕ T j M_T=M_{j-1}\oplus T_j M T = M j − 1 ⊕ T j M Q = M j − 1 ⊕ T Q M_Q=M_{j-1}\oplus T_Q M Q = M j − 1 ⊕ T Q c o s t ( T j ′ ) < c o s t ( Q j ′ ) cost(T'_j)<cost(Q'_j) cos t ( T j ′ ) < cos t ( Q j ′ ) σ ( M T ) ≻ R σ ( M Q ) \sigma(M_T)\succ_R\sigma(M_Q) σ ( M T ) ≻ R σ ( M Q ) σ ( T j ) ≺ R σ ( Q j ) \sigma(T_j)\prec_R\sigma(Q_j) σ ( T j ) ≺ R σ ( Q j )
Proof: By our cost assignment, c o s t ( T j ′ ) = c o s t ( M T ) − c o s t ( M j − 1 ) cost(T'_j)=cost(M_T)-cost(M_{j-1}) cos t ( T j ′ ) = cos t ( M T ) − cos t ( M j − 1 ) c o s t ( Q j ′ ) = c o s t ( M Q ) − c o s t ( M j − 1 ) cost(Q'_j)=cost(M_Q)-cost(M_{j-1}) cos t ( Q j ′ ) = cos t ( M Q ) − cos t ( M j − 1 ) c o s t ( T j ′ ) < c o s t ( Q j ′ ) cost(T'_j)<cost(Q'_j) cos t ( T j ′ ) < cos t ( Q j ′ ) c o s t ( M T ) < c o s t ( M Q ) cost(M_T)<cost(M_Q) cos t ( M T ) < cos t ( M Q ) M T M_T M T M Q M_Q M Q σ ( M T ) ≻ R σ ( M Q ) \sigma(M_T)\succ_R\sigma(M_Q) σ ( M T ) ≻ R σ ( M Q ) σ ( M T ) = σ ( M j − 1 ) − σ ( T j ) \sigma(M_T)=\sigma(M_{j-1})-\sigma(T_j) σ ( M T ) = σ ( M j − 1 ) − σ ( T j ) σ ( M Q ) = σ ( M j − 1 ) − σ ( Q j ) \sigma(M_Q)=\sigma(M_{j-1})-\sigma(Q_j) σ ( M Q ) = σ ( M j − 1 ) − σ ( Q j ) σ ( M T ) ≻ R σ ( M Q ) \sigma(M_T)\succ_R\sigma(M_Q) σ ( M T ) ≻ R σ ( M Q ) σ ( T j ) ≺ R σ ( Q j ) \sigma(T_j)\prec_R\sigma(Q_j) σ ( T j ) ≺ R σ ( Q j )
To prove the correctness of the augmentation step, we assume inductively that M j − 1 M_{j-1} M j − 1 ∣ M j − 1 ∣ |M_{j-1}| ∣ M j − 1 ∣ d t o t ( M ) d_{\mathrm{tot}}(M) d tot ( M )
Lemma 10. Let N N N G X G_X G X ∣ N ∣ = ∣ M j − 1 ∣ + 1 |N|=|M_{j-1}|+1 ∣ N ∣ = ∣ M j − 1 ∣ + 1 d t o t ( N ) = d t o t ( M j − 1 ) d_{\mathrm{tot}}(N)=d_{\mathrm{tot}}(M_{j-1}) d tot ( N ) = d tot ( M j − 1 ) M j − 1 M_{j-1} M j − 1 Q Q Q M j − 1 ⊕ N M_{j-1}\oplus N M j − 1 ⊕ N s s s t t t Q ′ Q' Q ′ H j H_j H j c o s t ( N ) − c o s t ( M j − 1 ) = c o s t ( Q ′ ) cost(N)-cost(M_{j-1})=cost(Q') cos t ( N ) − cos t ( M j − 1 ) = cos t ( Q ′ )
Proof: The symmetric difference M j − 1 ⊕ N M_{j-1}\oplus N M j − 1 ⊕ N ∣ N ∣ = ∣ M j − 1 ∣ + 1 |N|=|M_{j-1}|+1 ∣ N ∣ = ∣ M j − 1 ∣ + 1 M j − 1 M_{j-1} M j − 1 Q Q Q
a post p p p M j − 1 M_{j-1} M j − 1 Q Q Q p p p p p p M j − 1 M_{j-1} M j − 1 M j − 1 M_{j-1} M j − 1 Q Q Q M j − 1 M_{j-1} M j − 1 ℓ ( p ) ≤ ∣ M j − 1 ( p ) ∣ < u ( p ) \ell(p) \leq\lvert M_{j-1}(p) \rvert< u(p) ℓ ( p ) ≤ ∣ M j − 1 ( p )∣ < u ( p ) p ∈ P ′ p \in P' p ∈ P ′ Q Q Q s s s t t t Q ′ Q' Q ′ H j H_j H j
Let H = ( M j − 1 ⊕ N ) ∖ Q H = (M_{j-1} \oplus N) \setminus Q H = ( M j − 1 ⊕ N ) ∖ Q H ′ H' H ′ M j − 1 M_{j-1} M j − 1 H H H H ′ H' H ′ Q Q Q N N N ∣ H ′ ∣ = ∣ M j − 1 ∣ \lvert H' \rvert= \lvert M_{j-1} \rvert ∣ H ′ ∣ = ∣ M j − 1 ∣ d t o t ( H ′ ) = d t o t ( M j − 1 ) d_{\mathrm{tot}}(H') = d_{\mathrm{tot}}(M_{j-1}) d tot ( H ′ ) = d tot ( M j − 1 ) M j − 1 M_{j-1} M j − 1 cost ( M j − 1 ) = cost ( H ′ ) = cost ( N ) − cost ( Q ) \operatorname{cost}(M_{j-1}) = \operatorname{cost}(H') = \operatorname{cost}(N) - \operatorname{cost}(Q) cost ( M j − 1 ) = cost ( H ′ ) = cost ( N ) − cost ( Q ) cost ( N ) − cost ( M j − 1 ) = cost ( Q ′ ) \operatorname{cost}(N) - \operatorname{cost}(M_{j-1}) = \operatorname{cost}(Q') cost ( N ) − cost ( M j − 1 ) = cost ( Q ′ )
Now we prove the following property about the matching M j M_j M j j j j
Lemma 11. The matching M j M_j M j j j j ∣ M ∣ + j \lvert M \rvert+ j ∣ M ∣ + j d t o t ( M ) d_{\mathrm{tot}}(M) d tot ( M )
Proof: We prove this by induction on the number of iterations. The base case j = 0 j = 0 j = 0 M j − 1 M_{j-1} M j − 1 ∣ M ∣ + j − 1 \lvert M \rvert+ j - 1 ∣ M ∣ + j − 1 d t o t ( M ) d_{\mathrm{tot}}(M) d tot ( M ) H j H_j H j H j H_j H j T j ′ T'_j T j ′ s s s t t t H j H_j H j M j − 1 M_{j-1} M j − 1 M j = M j − 1 ⊕ T j M_j = M_{j-1} \oplus T_j M j = M j − 1 ⊕ T j M j M_j M j ∣ M ∣ + j \lvert M \rvert+ j ∣ M ∣ + j d t o t ( M j ) = d t o t ( M ) d_{\mathrm{tot}}(M_j) = d_{\mathrm{tot}}(M) d tot ( M j ) = d tot ( M ) N N N ∣ N ∣ = ∣ M ∣ + j \lvert N \rvert= \lvert M \rvert+ j ∣ N ∣ = ∣ M ∣ + j d t o t ( N ) = d t o t ( M ) d_{\mathrm{tot}}(N) = d_{\mathrm{tot}}(M) d tot ( N ) = d tot ( M )
By Lemma 10, there exists an M j − 1 M_{j-1} M j − 1 Q Q Q M j − 1 ⊕ N M_{j-1} \oplus N M j − 1 ⊕ N s s s t t t Q ′ Q' Q ′
cost ( N ) − cost ( M j − 1 ) = cost ( Q ′ ) . \operatorname{cost}(N) - \operatorname{cost}(M_{j-1}) = \operatorname{cost}(Q'). cost ( N ) − cost ( M j − 1 ) = cost ( Q ′ ) . Since, T j ′ T'_j T j ′ s s s t t t cost ( T j ′ ) ≤ cost ( Q ′ ) \operatorname{cost}(T'_j) \leq\operatorname{cost}(Q') cost ( T j ′ ) ≤ cost ( Q ′ )
cost ( M j ) − cost ( M j − 1 ) = cost ( T j ′ ) ≤ cost ( Q ′ ) = cost ( N ) − cost ( M j − 1 ) . \operatorname{cost}(M_j) - \operatorname{cost}(M_{j-1}) = \operatorname{cost}(T'_j) \leq\operatorname{cost}(Q') = \operatorname{cost}(N) - \operatorname{cost}(M_{j-1}). cost ( M j ) − cost ( M j − 1 ) = cost ( T j ′ ) ≤ cost ( Q ′ ) = cost ( N ) − cost ( M j − 1 ) . Thus, cost ( M j ) ≤ cost ( N ) \operatorname{cost}(M_j) \leq\operatorname{cost}(N) cost ( M j ) ≤ cost ( N ) σ ( M j ) ⪰ R σ ( N ) \sigma(M_j) \succeq_R \sigma(N) σ ( M j ) ⪰ R σ ( N ) N N N M j M_j M j ∣ M ∣ + j \lvert M \rvert+ j ∣ M ∣ + j d t o t ( M ) d_{\mathrm{tot}}(M) d tot ( M )
Our iterative procedure halts in iteration j j j H j H_j H j s s s t t t M ∗ = M 0 M^* = M_0 M ∗ = M 0 j j j M j M_j M j σ ( M j ) ≻ R σ ( M ∗ ) \sigma(M_j) \succ_R \sigma(M^*) σ ( M j ) ≻ R σ ( M ∗ ) M ∗ = M j M^* = M_j M ∗ = M j M ∗ M^* M ∗
Lemma 12. The matching M ∗ M^* M ∗ G G G
Proof: From Claim 6, every matching M j M_j M j N N N G G G q ≥ 0 q \geq0 q ≥ 0 ∣ N ∣ = ∣ M ∣ + q \lvert N \rvert= \lvert M \rvert+ q ∣ N ∣ = ∣ M ∣ + q Lemma 11 , the matching M q M_q M q ∣ M ∣ + q \lvert M \rvert+ q ∣ M ∣ + q σ ( M q ) ⪰ R σ ( N ) \sigma(M_q) \succeq_R \sigma(N) σ ( M q ) ⪰ R σ ( N ) M ∗ M^* M ∗ M j M_j M j σ ( M ∗ ) ⪰ R σ ( N ) \sigma(M^*) \succeq_R \sigma(N) σ ( M ∗ ) ⪰ R σ ( N ) N N N G G G M ∗ M^* M ∗ G G G
Illustration of algorithm for RMM-MIN-TOT. For an illustration, consider the soft quota setting instance G G G Figure 1 , and consider the instance G ′ G' G ′ M = { ( a 1 , p 1 ) , ( a 3 , p 2 ) , ( a 5 , p 4 ) } M = \{(a_1,p_1),(a_3,p_2),(a_5,p_4)\} M = {( a 1 , p 1 ) , ( a 3 , p 2 ) , ( a 5 , p 4 )} σ ( M ) = ( 1 , 2 , 0 ) \sigma(M) = (1,2,0) σ ( M ) = ( 1 , 2 , 0 ) d t o t ( M ) = 2 d_{\mathrm{tot}}(M) = 2 d tot ( M ) = 2 G ′ G' G ′ G G G s s s t t t H 1 H_1 H 1 s s s t t t T 1 ′ = ⟨ s , a 6 , p 6 , t ⟩ T_1' = \langle s,a_6,p_6,t\rangle T 1 ′ = ⟨ s , a 6 , p 6 , t ⟩ cost ( T 1 ) = − ( n + 1 ) 2 \operatorname{cost}(T_1) = -(n+1)^2 cost ( T 1 ) = − ( n + 1 ) 2 σ ( T 1 ) = ( − 1 , 0 , 0 ) \sigma(T_1) = (-1,0,0) σ ( T 1 ) = ( − 1 , 0 , 0 ) N 1 = { ( a 1 , p 1 ) , ( a 3 , p 2 ) , ( a 5 , p 4 ) , ( a 6 , p 6 ) } N_1 = \{(a_1,p_1),(a_3,p_2),(a_5,p_4),(a_6,p_6)\} N 1 = {( a 1 , p 1 ) , ( a 3 , p 2 ) , ( a 5 , p 4 ) , ( a 6 , p 6 )} ( 2 , 2 , 0 ) (2,2,0) ( 2 , 2 , 0 ) N 1 N_1 N 1 G G G s s s t t t T 2 ′ = ⟨ s , a 4 , p 7 , t ⟩ T_2' = \langle s,a_4,p_7,t\rangle T 2 ′ = ⟨ s , a 4 , p 7 , t ⟩ cost ( T 2 ) = − 1 \operatorname{cost}(T_2) = -1 cost ( T 2 ) = − 1 σ ( T 2 ) = ( 0 , 0 , − 1 ) \sigma(T_2) = (0,0,-1) σ ( T 2 ) = ( 0 , 0 , − 1 ) N 2 = { ( a 1 , p 1 ) , ( a 3 , p 2 ) , ( a 4 , p 7 ) , ( a 5 , p 4 ) , ( a 6 , p 6 ) } N_2 = \{(a_1,p_1),(a_3,p_2),(a_4,p_7),(a_5,p_4),(a_6,p_6)\} N 2 = {( a 1 , p 1 ) , ( a 3 , p 2 ) , ( a 4 , p 7 ) , ( a 5 , p 4 ) , ( a 6 , p 6 )} ( 2 , 2 , 1 ) (2,2,1) ( 2 , 2 , 1 ) H 3 H_3 H 3 s s s t t t N 2 N_2 N 2 G G G N 2 N_2 N 2 M 1 M_1 M 1 Table 1 .
Modification for Fairness
For the total deviation variant of the problem FAIR-MIN-TOT, we begin by constructing the network H H H § 4.1 . We modify the cost assignment on the edges in H H H
Cost of the edges in H H H
For every edge ( a , p ) ∈ E A P (a,p) \in\mathcal{E}_{AP} ( a , p ) ∈ E A P i i i ( n + 1 ) i (n+1)^i ( n + 1 ) i
Due to the cost assignment, any min-cost flow in H H H M M M G ′ G' G ′
In Step (B), we augment the matching M M M G x G_x G x G G G H j H_j H j
Cost of the edges in H j H_j H j For an edge ( a , p ) ∈ E (a,p) \in E ( a , p ) ∈ E i i i
The procedure of augmentation is the same as that described in Step (B).
MIN-MAX Variants
To solve the MIN-MAX type problems in the soft quota setting, namely, OPT-SIGN-MIN-MAX and OPT-MIN-MAX, we exploit their connection to related problems in the fixed quota setting. In particular, to obtain our solutions, we compute optimal matchings (with respect to preferences) among all the matchings that are feasible in the fixed quota setting instance.
We consider an instance of fixed quota setting G G G p p p q ‾ ( p ) \underline{q}(p) q ( p ) q ‾ ( p ) \overline{q}(p) q ( p ) p p p G G G q ‾ G ( p ) \underline{q}_G(p) q G ( p ) q ‾ G ( p ) \overline{q}_G(p) q G ( p ) G G G [21 , 22 , 25 ] . Now, we extend these algorithms to compute an optimal matching among all feasible matchings by adapting the algorithm in [25 ] . Assuming that feasible matchings exist in G G G
Given an instance G G G G ′ G' G ′ G G G G ′ G' G ′
Reduction from RMM-LQ to MAX-CARD-RMM
Given an instance G G G G ′ G' G ′ G ′ G' G ′ A \mathcal{A} A P \mathcal{P} P G G G p ∈ P p \in\mathcal{P} p ∈ P q G ′ − ( p ) = 0 q^-_{G'}(p) = 0 q G ′ − ( p ) = 0 q G ′ + ( p ) = q G + ( p ) q^+_{G'}(p) = q^+_G(p) q G ′ + ( p ) = q G + ( p ) p ∈ P p \in\mathcal{P} p ∈ P q G + ( p ) − q G − ( p ) q^+_G(p) - q^-_G(p) q G + ( p ) − q G − ( p ) r + 1 r+1 r + 1 p p p U = ∑ p ∈ P q G + ( p ) U = \sum_{p\in\mathcal{P}} q^+_G(p) U = ∑ p ∈ P q G + ( p ) U U U G ′ G' G ′ G G G
Claim 8. G ′ G' G ′ U U U G G G
Proof: Suppose that G G G M M M M ′ M' M ′ G ′ G' G ′ M M M ∣ M ′ ∣ = U |M'| = U ∣ M ′ ∣ = U M ′ M' M ′ M M M p p p M ′ M' M ′ q G ′ + ( p ) = q G + ( p ) q^+_{G'}(p) = q^+_G(p) q G ′ + ( p ) = q G + ( p ) ∣ M ′ ∣ = U |M'| = U ∣ M ′ ∣ = U
On the other hand, suppose that G ′ G' G ′ M ′ M' M ′ ∣ M ′ ∣ = U |M'| = U ∣ M ′ ∣ = U M M M G G G p ∈ P p \in\mathcal{P} p ∈ P M ′ M' M ′ p ∈ P p \in\mathcal{P} p ∈ P p p p M ′ M' M ′ q G + ( p ) − q G − ( p ) q^+_G(p) - q^-_G(p) q G + ( p ) − q G − ( p ) p p p M ′ M' M ′ q G − ( p ) q^-_G(p) q G − ( p ) p p p ∣ M ( p ) ∣ = q G − ( p ) |M(p)| = q^-_G(p) ∣ M ( p ) ∣ = q G − ( p ) M M M G G G □ \square □
:::
We state the following claim about a feasible matching in G G G G ′ G' G ′ U U U
Claim 9. Let G G G G ′ G' G ′
For any feasible matching M M M G G G σ ( M ) = ( x 1 , x 2 , … , x r ) \sigma(M) = (x_1, x_2, \ldots, x_r) σ ( M ) = ( x 1 , x 2 , … , x r ) S = ∑ i = 1 r x i S = \sum_{i=1}^{r} x_i S = ∑ i = 1 r x i M ′ M' M ′ G ′ G' G ′ σ ( M ′ ) = ( x 1 , x 2 , … , x r , U − S ) \sigma(M') = (x_1, x_2, \ldots, x_r, U-S) σ ( M ′ ) = ( x 1 , x 2 , … , x r , U − S )
For a maximum matching M ′ M' M ′ G ′ G' G ′ σ ( M ′ ) = ( x 1 , x 2 , … , x r , x r + 1 ) \sigma(M') = (x_1, x_2, \ldots, x_r, x_{r+1}) σ ( M ′ ) = ( x 1 , x 2 , … , x r , x r + 1 ) ∣ M ′ ∣ = U |M'| = U ∣ M ′ ∣ = U M M M G G G σ ( M ) = ( x 1 , x 2 , … , x r ) \sigma(M) = (x_1, x_2, \ldots, x_r) σ ( M ) = ( x 1 , x 2 , … , x r )
The proof of the above claim follows directly from the proof of Claim 8.
Lemma 13. Let M ′ M' M ′ G ′ G' G ′ ∣ M ′ ∣ = U |M'| = U ∣ M ′ ∣ = U M M M G G G M M M G G G
Proof. Since ∣ M ′ ∣ = U |M'| = U ∣ M ′ ∣ = U G G G M ′ M' M ′ σ ( M ′ ) = ( x 1 , x 2 , … , x r , x r + 1 ) \sigma(M') = (x_1, x_2, \ldots, x_r, x_{r+1}) σ ( M ′ ) = ( x 1 , x 2 , … , x r , x r + 1 ) M M M G G G σ ( M ) = ( x 1 , x 2 , … , x r ) \sigma(M) = (x_1, x_2, \ldots, x_r) σ ( M ) = ( x 1 , x 2 , … , x r ) M M M G G G M 1 M_1 M 1 G G G σ ( M 1 ) = ( y 1 , y 2 , … , y r ) \sigma(M_1) = (y_1, y_2, \ldots, y_r) σ ( M 1 ) = ( y 1 , y 2 , … , y r ) M 1 ′ M'_1 M 1 ′ G ′ G' G ′ M 1 M_1 M 1 G G G σ ( M 1 ′ ) = ( y 1 , y 2 , … , y r , U − S ) \sigma(M'_1) = (y_1, y_2, \ldots, y_r, U-S) σ ( M 1 ′ ) = ( y 1 , y 2 , … , y r , U − S ) S = ∑ i = 1 r y i S = \sum_{i=1}^{r} y_i S = ∑ i = 1 r y i σ ( M 1 ) ≻ R σ ( M ) \sigma(M_1) \succ_R \sigma(M) σ ( M 1 ) ≻ R σ ( M ) G G G σ ( M 1 ′ ) ≻ R σ ( M ′ ) \sigma(M'_1) \succ_R \sigma(M') σ ( M 1 ′ ) ≻ R σ ( M ′ ) G ′ G' G ′ M ′ M' M ′ G ′ G' G ′
Modifications for fairness. Given an instance G G G G ′ G' G ′ H H H [25 ] , both problems RMM-LQ and FAIR-LQ admit an O ~ ( r m n ) \widetilde{O}(rmn) O ( r mn )
Minimizing maximum deviation in the soft quota setting
Having described the algorithms for the problems RMM-LQ and FAIR-LQ in the fixed quota setting, we now go back to our original problem of minimizing maximum deviation in the soft quota setting. To solve the MIN-MAX type problems in the soft quota setting, namely OPT-MIN-MAX and OPT-SIGN-MIN-MAX, we use a reduction to problems in the fixed quota setting and apply the algorithms for the problems RMM-LQ and FAIR-LQ. We describe our algorithms for the preference optimality as rank-maximality. Analogously, we can solve the problems for the notion of fairness.
We begin by presenting a useful observation about an optimal solution to the problem RMM-MIN-MAX.
Observation 7. Let M ∗ M^* M ∗ Δ ∗ \Delta^* Δ ∗ p p p M ∗ M^* M ∗ Δ ∗ \Delta^* Δ ∗
Proof. Suppose not. Then the lower deviation of all posts with respect to M ∗ M^* M ∗ Δ ∗ \Delta^* Δ ∗ M ∗ M^* M ∗ Δ ′ \Delta' Δ ′ d max ( M ∗ ) = Δ ∗ d_{\max}(M^*) = \Delta^* d m a x ( M ∗ ) = Δ ∗ p ∈ P p \in\mathcal{P} p ∈ P Δ ∗ \Delta^* Δ ∗ P u \mathcal{P}_u P u M ∗ M^* M ∗ ∣ M ∗ ( p ) ∣ > u ( p ) + Δ ′ |M^*(p)| > u(p) + \Delta' ∣ M ∗ ( p ) ∣ > u ( p ) + Δ ′
We construct a matching M ′ M' M ′ M ∗ M^* M ∗ p ∈ P u p \in\mathcal{P}_u p ∈ P u ∣ M ∗ ( p ) ∣ − u ( p ) − Δ ′ |M^*(p)| - u(p) - \Delta' ∣ M ∗ ( p ) ∣ − u ( p ) − Δ ′ p p p M ∗ M^* M ∗ M ′ M' M ′ p p p M ′ M' M ′ Δ ′ \Delta' Δ ′ p ∉ P u p \notin\mathcal{P}_u p ∈ / P u M ′ M' M ′ p p p M ′ M' M ′ Δ ′ \Delta' Δ ′ d max ( M ′ ) = Δ ′ < Δ ∗ d_{\max}(M') = \Delta' < \Delta^* d m a x ( M ′ ) = Δ ′ < Δ ∗ M ∗ M^* M ∗
Next, we describe the reduction from soft quota setting to the fixed quota setting.
Reduction from soft quota setting to the fixed quota setting. Given an instance G G G Δ \Delta Δ H Δ H_{\Delta} H Δ H Δ H_{\Delta} H Δ G G G p p p q − ( p ) = max { 0 , ℓ ( p ) − Δ } q^{-}(p)=\max\{0,\ell(p)-\Delta\} q − ( p ) = max { 0 , ℓ ( p ) − Δ } q + ( p ) = u ( p ) + Δ q^{+}(p)=u(p)+\Delta q + ( p ) = u ( p ) + Δ H Δ H_{\Delta} H Δ H Δ ′ H_{\Delta'} H Δ ′ Δ ′ ≥ Δ \Delta' \ge\Delta Δ ′ ≥ Δ
Next, we present the algorithms for the RMM-MIN-MAX and RMM-SIGN-MIN-MAX problems.
Algorithm for RMM-MIN-MAX
Given an instance G G G ℓ ( p ) \ell(p) ℓ ( p ) ∣ A ∣ |\mathcal{A}| ∣ A ∣ ∣ A ∣ |\mathcal{A}| ∣ A ∣ [ 0 , ∣ A ∣ ] [0,|\mathcal{A}|] [ 0 , ∣ A ∣ ] Δ \Delta Δ H Δ H_{\Delta} H Δ Δ \Delta Δ [ 0 , ∣ A ∣ ] [0,|\mathcal{A}|] [ 0 , ∣ A ∣ ] Δ \Delta Δ Δ ∗ \Delta^{*} Δ ∗ Δ \Delta Δ Δ ∗ \Delta^{*} Δ ∗ H Δ ∗ H_{\Delta^{*}} H Δ ∗
Algorithm for RMM-SIGN-MIN-MAX
Given an instance G G G ρ \rho ρ M M M M R \mathcal{M}_{R} M R M R \mathcal{M}_{R} M R ρ \rho ρ ℓ ( p ) \ell(p) ℓ ( p ) ∣ A ∣ |\mathcal{A}| ∣ A ∣ ∣ A ∣ |\mathcal{A}| ∣ A ∣ [ 0 , ∣ A ∣ ] [0,|\mathcal{A}|] [ 0 , ∣ A ∣ ] M R \mathcal{M}_{R} M R Δ \Delta Δ H Δ H_{\Delta} H Δ H Δ H_{\Delta} H Δ M M M H Δ H_{\Delta} H Δ σ ( M ) ⪰ R ρ \sigma(M) \succeq_{R} \rho σ ( M ) ⪰ R ρ M M M Δ \Delta Δ [ 0 , ∣ A ∣ ] [0,|\mathcal{A}|] [ 0 , ∣ A ∣ ] Δ \Delta Δ
Below, we illustrate the execution of our algorithms for RMM-MIN-MAX and RMM-SIGN-MIN-MAX for the example instance in Figure 1 .
Illustration of algorithm for RMM-MIN-MAX. Given the instance G G G Δ \Delta Δ G Δ G_{\Delta} G Δ Δ = 1 \Delta=1 Δ = 1 G 1 G_{1} G 1 M 2 M_{2} M 2 Table 1 is a solution to the RMM-LQ problem in G 1 G_{1} G 1 G G G
Illustration of algorithm for RMM-SIGN-MIN-MAX. Given the instance G G G Δ \Delta Δ G Δ G_{\Delta} G Δ Δ \Delta Δ G Δ G_{\Delta} G Δ Δ = 2 \Delta= 2 Δ = 2 G 2 G_{2} G 2 M 4 M_{4} M 4 Table 1 , is a solution to the RMM-LQ problem in G 2 G_{2} G 2 σ ( M 4 ) ⪰ R ( 4 , 0 , 0 , 3 ) \sigma(M_{4}) \succeq_{R} (4, 0, 0, 3) σ ( M 4 ) ⪰ R ( 4 , 0 , 0 , 3 ) M 4 M_{4} M 4
Modification for Fairness in the soft quota setting
In this section, we state the necessary modifications required to solve the problems FAIR-MIN-MAX and FAIR-SIGN-MIN-MAX.
Algorithm for FAIR-MIN-MAX. Given an instance G G G § 5.3 , we first compute the minimum value of maximum deviation, say Δ ∗ \Delta^{*} Δ ∗ Δ ∗ \Delta^{*} Δ ∗ H Δ ∗ H_{\Delta^{*}} H Δ ∗
Algorithm for FAIR-SIGN-MIN-MAX. Given an instance G G G ρ \rho ρ M M M M F M_{\mathcal{F}} M F M F M_{\mathcal{F}} M F ρ \rho ρ § 5.4 , we guess a maximum deviation value Δ \Delta Δ H Δ H_{\Delta} H Δ H Δ H_{\Delta} H Δ M M M H Δ H_{\Delta} H Δ σ ( M ) ⪰ F ρ \sigma(M) \succeq_{\mathcal{F}} \rho σ ( M ) ⪰ F ρ M M M Δ \Delta Δ [ 0 , ∣ A ∣ ] [0,|\mathcal{A}|] [ 0 , ∣ A ∣ ] Δ \Delta Δ
Optimizing both total deviation and maximum deviation
Our problems so far have been defined to optimize either the total deviation or the maximum deviation, but not both simultaneously. A natural question is whether there exists a matching that optimizes both the total deviation and the maximum deviation. To define our problems concretely, we fix the optimality notion as rank-maximality. In § 6.1 , we consider preference optimality first type of problems followed by deviation first type of problems in § 6.2 .
Preference optimality first
Recall that, in the preference optimality first type of the problem, we are given an instance of the soft quota setting along with a signature. The goal is to compute a matching that satisfies the signature with respect to rank-maximality while optimizing either the total deviation or the maximum deviation. The set of matchings that meet the signature requirement with respect to rank-maximality is denoted by M R \mathcal{M}_R M R M R \mathcal{M}_R M R M t ′ \mathcal{M}'_t M t ′ M m ′ \mathcal{M}'_m M m ′ M t ′ \mathcal{M}'_t M t ′ M m ′ \mathcal{M}'_m M m ′ Figure 2 ).
Having seen efficient algorithms for the RMM-SIGN-MIN-TOT and RMM-SIGN-MIN-MAX problems, we now define a problem that aims to optimize both total deviation and maximum deviation simultaneously. That is, given an instance G G G ρ \rho ρ M t ′ \mathcal{M}'_t M t ′ M m ′ \mathcal{M}'_m M m ′ Q 1 Q_1 Q 1 Figure 5 ), where the TM in the name indicates that our goal is to optimize both total and maximum deviations simultaneously. If the intersection of M t ′ \mathcal{M}'_t M t ′ M m ′ \mathcal{M}'_m M m ′
Figure 5. Optimizing both total deviation and maximum deviation for the problem RMM-SIGN-MIN-Y, where Y ∈ { T O T , M A X } Y \in\{TOT, MAX\} Y ∈ { T O T , M A X }
RMM-SIGN-MIN-TM _M M M t ′ \mathcal{M}'_t M t ′ M _M M Q 2 Q_2 Q 2 Figure 5 ), where the TM _M M M t ′ \mathcal{M}'_t M t ′
RMM-SIGN-MIN-MT _T T M m ′ \mathcal{M}'_m M m ′ T _T T Q 3 Q_3 Q 3 Figure 5 ), where the MT _T T M m ′ \mathcal{M}'_m M m ′
We solve the above problems in polynomial time by adapting our algorithm for the problem RMM-SIGN-MIN-TOT. Recall that, for a given total deviation Δ \Delta Δ ( l d , u d ) (ld,ud) ( l d , u d ) Δ = l d + u d \Delta= ld + ud Δ = l d + u d H ( l d , u d ) H_{(ld,ud)} H ( l d , u d ) Figure 3 ) admits a feasible flow, then the total deviation of the corresponding matching is at most Δ \Delta Δ Figure 3 , the lower deviation for a post p p p ( d ′ , p ′ ) (d',p') ( d ′ , p ′ ) ( p ′ ′ , d ′ ′ ) (p'',d'') ( p ′′ , d ′′ )
Suppose that, for a given instance G G G ρ \rho ρ Δ t ′ \Delta'_t Δ t ′ Δ m ′ \Delta'_m Δ m ′ M t ′ \mathcal{M}'_t M t ′ Δ t ′ \Delta'_t Δ t ′ M m ′ \mathcal{M}'_m M m ′ Δ m ′ \Delta'_m Δ m ′
Algorithm for RMM-SIGN-MIN-TM. To determine whether the set M t ′ ∩ M m ′ \mathcal{M}'_t \cap\mathcal{M}'_m M t ′ ∩ M m ′ Figure 3 . We note that, since the optimal value of total deviation is Δ t ′ \Delta'_t Δ t ′ H Δ t ′ H_{\Delta'_t} H Δ t ′ Δ t ′ = l d + u d \Delta'_t=ld+ud Δ t ′ = l d + u d Δ m ′ \Delta'_m Δ m ′
For every post p ∈ P p \in\mathcal{P} p ∈ P ( d ′ , p ′ ) (d',p') ( d ′ , p ′ ) ( p ′ ′ , d ′ ′ ) (p'',d'') ( p ′′ , d ′′ ) Δ m ′ \Delta'_m Δ m ′ l d ld l d u d ud u d
Let the modified network be H ′ H' H ′ ( l d , u d ) (ld,ud) ( l d , u d ) Δ t ′ \Delta'_t Δ t ′ H ( l d , u d ) ′ H'_{(ld,ud)} H ( l d , u d ) ′ Δ t ′ \Delta'_t Δ t ′ ( l d ∗ , u d ∗ ) (ld^*,ud^*) ( l d ∗ , u d ∗ ) M M M M t ′ \mathcal{M}'_t M t ′ M m ′ \mathcal{M}'_m M m ′ M t ′ \mathcal{M}'_t M t ′ M m ′ \mathcal{M}'_m M m ′
Algorithm for RMM-SIGN-MIN-Tm _m m In the problem RMM-SIGN-MIN-Tm _m m M t ′ \mathcal{M}'_t M t ′ M t ′ \mathcal{M}'_t M t ′ Δ m ′ \Delta'_m Δ m ′ Δ t ′ \Delta'_t Δ t ′ i ∈ [ Δ m ′ , Δ t ′ ] i \in[\Delta'_m,\Delta'_t] i ∈ [ Δ m ′ , Δ t ′ ] Figure 3 .
For every post p ∈ P p \in\mathcal{P} p ∈ P ( d ′ , p ′ ) (d',p') ( d ′ , p ′ ) ( p ′ ′ , d ′ ′ ) (p'',d'') ( p ′′ , d ′′ ) i i i l d ld l d u d ud u d i ∈ [ Δ m ′ , Δ t ′ ] i \in[\Delta'_m,\Delta'_t] i ∈ [ Δ m ′ , Δ t ′ ]
Let the modified network be H ′ H' H ′ ( l d , u d ) (ld,ud) ( l d , u d ) Δ t ′ \Delta'_t Δ t ′ H ( l d , u d ) ′ H'_{(ld,ud)} H ( l d , u d ) ′ ( l d ∗ , u d ∗ ) (ld^*,ud^*) ( l d ∗ , u d ∗ ) M M M i i i i i i M t ′ \mathcal{M}'_t M t ′ O ( Δ t ′ 2 ) O(\Delta_t'^2) O ( Δ t ′2 ) H ′ H' H ′ Δ t ′ \Delta'_t Δ t ′ ∣ A ∣ |\mathcal{A}| ∣ A ∣
Algorithm for RMM-SIGN-MIN-MT _T T In the problem RMM-SIGN-MIN-MT _T T M m ′ \mathcal{M}'_m M m ′ M m ′ \mathcal{M}'_m M m ′ Δ t ′ \Delta'_t Δ t ′ min { ∣ P ∣ ⋅ Δ m ′ , ∑ p ∈ P ℓ ( p ) + ∣ A ∣ } \min\{|\mathcal{P}|\cdot\Delta'_m,\sum_{p\in\mathcal{P}}\ell(p)+|\mathcal{A}|\} min { ∣ P ∣ ⋅ Δ m ′ , ∑ p ∈ P ℓ ( p ) + ∣ A ∣ } Figure 3 .
For every post p ∈ P p \in P p ∈ P ( d ′ , p ′ ) (d',p') ( d ′ , p ′ ) ( p ′ ′ , d ′ ′ ) (p'',d'') ( p ′′ , d ′′ ) Δ m ′ \Delta'_m Δ m ′ l d ld l d u d ud u d
Let the modified network be H ′ H' H ′ Δ \Delta Δ Δ \Delta Δ ( l d ∗ , u d ∗ ) (ld^*,ud^*) ( l d ∗ , u d ∗ ) M M M Δ \Delta Δ Δ \Delta Δ M m ′ \mathcal{M}'_m M m ′
Deviation first
Now, we consider analogous problems in the deviation first variant. Recall that, in the deviation first type of the problem, we are given an instance of the soft quota setting, and our goal is to compute a rank-maximal matching among all matchings that optimize either the total deviation or the maximum deviation. We denote the set of matchings that minimize total deviation (or max deviation respectively) by M t \mathcal{M}_t M t M m \mathcal{M}_m M m M t \mathcal{M}_t M t M m \mathcal{M}_m M m
We define analogous problems to optimize the total deviation and maximum deviation simultaneously as described in § 6.1 . Given an instance G G G M t \mathcal{M}_t M t M m \mathcal{M}_m M m Q 4 Q_4 Q 4 Figure 6 ), where the TM in the problem name indicates that our goal is to optimize both the total and the maximum deviation simultaneously. If the intersection of M t \mathcal{M}_t M t M m \mathcal{M}_m M m
Figure 6. Optimizing both total deviation and maximum deviation for the problem RMM-MIN-Y, where Y ∈ { T O T , M A X } Y \in\{TOT, MAX\} Y ∈ { T O T , M A X }
RMM-MIN-TM _M M M t \mathcal{M}_t M t M _M M Q 5 Q_5 Q 5 Figure 6 ), where the TM _M M M t \mathcal{M}_t M t
RMM-MIN-TM _{\mathrm{M}} M M m \mathcal{M}_m M m M _{\mathrm{M}} M Figure 6 ), where TM _{\mathrm{M}} M M m \mathcal{M}_m M m
We solve the above problems in polynomial time by adapting our algorithm for the problem RMM-SIGN-MIN-TOT. Suppose that, for a given instance G G G Δ t \Delta_t Δ t Δ m \Delta_m Δ m M t \mathcal{M}_t M t Δ t \Delta_t Δ t M m \mathcal{M}_m M m Δ m \Delta_m Δ m
Algorithm for RMM-MIN-TM _{\mathrm{M}} M M t \mathcal{M}_t M t M m \mathcal{M}_m M m § 6.1 , we restrict the maximum deviation of a post p p p Δ m \Delta_m Δ m M _{\mathrm{M}} M Figure 3 as follows.
We set u d = 0 ud = 0 u d = 0 l d = Δ t ld = \Delta_t l d = Δ t Δ t \Delta_t Δ t M t \mathcal{M}_t M t
For every post p ∈ P p \in\mathcal{P} p ∈ P ( d ′ , p ′ ) (d',p') ( d ′ , p ′ ) Δ m \Delta_m Δ m l d ld l d
We retain the demands and capacities of all other edges as they are in the original network given in Figure 3 .
Let the modified network be H ′ H' H ′ H ( Δ t , 0 ) ′ H'_{(\Delta_t,0)} H ( Δ t , 0 ) ′ M M M M M M Δ t \Delta_t Δ t H ( Δ t , 0 ) ′ H'_{(\Delta_t,0)} H ( Δ t , 0 ) ′ d t o t ( M ) = Δ t d_{\mathrm{tot}}(M) = \Delta_t d tot ( M ) = Δ t d m a x ( M ) = Δ m d_{\mathrm{max}}(M) = \Delta_m d max ( M ) = Δ m M M M M _{\mathrm{M}} M H ( Δ t , 0 ) ′ H'_{(\Delta_t,0)} H ( Δ t , 0 ) ′ M t \mathcal{M}_t M t M m \mathcal{M}_m M m
Algorithm for RMM-MIN-Tm _{\mathrm{m}} m m _{\mathrm{m}} m M t \mathcal{M}_t M t M t \mathcal{M}_t M t Δ m \Delta_m Δ m Δ t \Delta_t Δ t i ∈ [ Δ m , Δ t ] i \in[\Delta_m,\Delta_t] i ∈ [ Δ m , Δ t ] Figure 3 .
We set u d = 0 ud = 0 u d = 0 l d = Δ t ld = \Delta_t l d = Δ t Δ t \Delta_t Δ t M t \mathcal{M}_t M t
For every post p ∈ P p \in\mathcal{P} p ∈ P ( d ′ , p ′ ) (d',p') ( d ′ , p ′ ) i i i l d ld l d i ∈ [ Δ m , Δ t ] i \in[\Delta_m,\Delta_t] i ∈ [ Δ m , Δ t ]
We retain the demands and capacities of all other edges as they are in the original network given in Figure 3 .
Let the modified network be H ′ H' H ′ i i i H ( Δ t , 0 ) ′ H'_{(\Delta_t,0)} H ( Δ t , 0 ) ′ i i i i i i M t \mathcal{M}_t M t O ( Δ t 2 ) O(\Delta_t^2) O ( Δ t 2 ) H ′ H' H ′ Δ t \Delta_t Δ t ∣ A ∣ |\mathcal{A}| ∣ A ∣
Algorithm for RMM-MIN-MT _{\mathrm{T}} T T _{\mathrm{T}} T M m \mathcal{M}_m M m M m \mathcal{M}_m M m Δ m \Delta_m Δ m min { ∣ P ∣ ⋅ Δ m , ∑ p ∈ P ℓ ( p ) } \min\{|\mathcal{P}|\cdot\Delta_m,\sum_{p\in\mathcal{P}}\ell(p)\} min { ∣ P ∣ ⋅ Δ m , ∑ p ∈ P ℓ ( p )} Figure 3 .
We set u d = 0 ud=0 u d = 0 l d = Δ ld=\Delta l d = Δ
For every post p ∈ P p\in\mathcal{P} p ∈ P ( d ′ , p ′ ) (d',p') ( d ′ , p ′ ) Δ m \Delta_m Δ m l d ld l d
We retain the demands and capacities of all other edges as they are in the original network given in Figure 3 .
Let the modified network be H ′ H' H ′ Δ \Delta Δ H ( Δ , 0 ) ′ H'_{(\Delta,0)} H ( Δ , 0 ) ′ Δ \Delta Δ Δ \Delta Δ M m \mathcal{M}_m M m
Generalized Soft Quota Setting
Having considered the problems in the soft quota setting, we now generalize our framework. In the soft quota setting, deviating by one unit from the given targets incurs a uniform deviation cost across all the posts. A natural generalization of the soft quota setting involves associating costs with these deviations. In an instance G G G generalized soft quota setting , every post p p p c ℓ ( p ) c_{\ell}(p) c ℓ ( p ) c u ( p ) c_u(p) c u ( p )
As in the soft quota setting, our goal in the generalized soft quota setting is to compute an assignment that has two orthogonal optimization objectives:
(i) Minimizing deviation cost. For a matching M M M d t c ( M ) d_{\mathrm{tc}}(M) d tc ( M ) d m c ( M ) d_{\mathrm{mc}}(M) d mc ( M ) P ℓ P_{\ell} P ℓ P u P_u P u M M M p p p P ℓ P_{\ell} P ℓ P u P_u P u
d t c ( M ) = ∑ p ∈ P ℓ d M ( p ) ⋅ c ℓ ( p ) + ∑ p ∈ P u d M ( p ) ⋅ c u ( p ) d_{\mathrm{tc}}(M)=\sum_{p\in P_{\ell}}d_M(p)\cdot c_{\ell}(p)+\sum_{p\in P_u}d_M(p)\cdot c_u(p) d tc ( M ) = p ∈ P ℓ ∑ d M ( p ) ⋅ c ℓ ( p ) + p ∈ P u ∑ d M ( p ) ⋅ c u ( p ) and
d m c ( M ) = max { max p ∈ P ℓ d M ( p ) ⋅ c ℓ ( p ) , max p ∈ P u d M ( p ) ⋅ c u ( p ) } d_{\mathrm{mc}}(M)=\max\left\{\max_{p\in P_{\ell}}d_M(p)\cdot c_{\ell}(p),\max_{p\in P_u}d_M(p)\cdot c_u(p)\right\} d mc ( M ) = max { p ∈ P ℓ max d M ( p ) ⋅ c ℓ ( p ) , p ∈ P u max d M ( p ) ⋅ c u ( p ) } (ii) Optimality with respect to preferences. As done earlier, we use rank-maximality and fairness as our notions of optimality.
Our Problems and Results
In the generalized soft quota setting, we care about deviation cost as well as preference optimality, and this defines our problems.
Deviation cost first. In this type of problem, we give precedence to minimizing the deviation cost first, and subject to that, we optimize the preferences. Let M \mathcal{M} M G G G M t c \mathcal{M}_{tc} M t c M m c \mathcal{M}_{mc} M m c
OPT-MIN-TOT-DC: The goal is to compute a matching that satisfies the notion O P T OPT O P T M t c \mathcal{M}_{tc} M t c
OPT-MIN-MAX-DC: The goal is to compute a matching that satisfies the notion O P T OPT O P T M m c \mathcal{M}_{mc} M m c
Preference optimality first. This type of problem has a signature requirement ρ \rho ρ M O P T \mathcal{M}_{OPT} M O P T M t c ′ \mathcal{M}'_{tc} M t c ′ M m c ′ \mathcal{M}'_{mc} M m c ′ M O P T \mathcal{M}_{OPT} M O P T
For the maximum deviation cost variants, as well as for the OPT-MIN-TOT-DC problem, we show that our algorithms in the soft quota setting can be extended to solve the analogous problems in the generalized soft quota setting. For the problem OPT-SIGN-MIN-TOT-DC, we are not aware of any hardness or algorithmic results. We show polynomial time algorithms for solving special cases of the problem OPT-SIGN-MIN-TOT-DC.
Minimizing maximum deviation cost
To solve the MIN-MAX-DC type problems in the generalized soft quota setting, namely OPT-MIN-MAX-DC and OPT-SIGN-MIN-MAX-DC, we use a reduction to problems in the fixed quota setting. We describe the algorithms for the notion of rank-maximality.
We begin by presenting a useful observation about an optimal solution to the problem RMM-MIN-MAX-DC.
Observation 8. Let M ∗ M^* M ∗ C ∗ C^* C ∗ p p p M ∗ M^* M ∗ p p p C ∗ C^* C ∗
Proof: Suppose not. Then the lower deviation cost of every post with respect to M ∗ M^* M ∗ C ∗ C^* C ∗ M ∗ M^* M ∗ C ′ C' C ′ d m c ( M ∗ ) = C ∗ d_{mc}(M^*) = C^* d m c ( M ∗ ) = C ∗ p ∈ P p \in\mathcal{P} p ∈ P C ∗ C^* C ∗ P u \mathcal{P}_u P u M ∗ M^* M ∗
∣ M ∗ ( p ) ∣ > u ( p ) + ⌈ C ′ c u ( p ) ⌉ . (1) |M^*(p)| > u(p) + \left\lceil\frac{C'}{c_u(p)} \right\rceil. \tag*{(1)} ∣ M ∗ ( p ) ∣ > u ( p ) + ⌈ c u ( p ) C ′ ⌉ . (1) We construct a matching M ′ M' M ′ M ∗ M^* M ∗ p ∈ P u p \in\mathcal{P}_u p ∈ P u ∣ M ∗ ( p ) ∣ − u ( p ) − ⌊ C ′ c u ( p ) ⌋ \lvert M^*(p)\rvert-u(p)-\left\lfloor\frac{C'}{c_u(p)}\right\rfloor ∣ M ∗ ( p )∣ − u ( p ) − ⌊ c u ( p ) C ′ ⌋ p p p M ∗ M^* M ∗ M ′ M' M ′ p p p M ′ M' M ′ C ′ C' C ′ p ∉ P u p \notin\mathcal{P}_u p ∈ / P u M ′ M' M ′ p p p M ′ M' M ′ C ′ C' C ′ d m c ( M ′ ) = C ′ < C ∗ d_{mc}(M')=C'<C^* d m c ( M ′ ) = C ′ < C ∗ M ∗ M^* M ∗
Next, we describe the reduction from generalized soft quota setting to the fixed quota setting.
Reduction from generalized soft quota setting to the fixed quota setting. Given an instance G G G C C C H C H_C H C H C H_C H C G G G p p p q − ( p ) = max { 0 , ℓ ( p ) − ⌊ C c ℓ ( p ) ⌋ } q^-(p)=\max\{0,\ell(p)-\left\lfloor\frac{C}{c_\ell(p)}\right\rfloor\} q − ( p ) = max { 0 , ℓ ( p ) − ⌊ c ℓ ( p ) C ⌋ } q + ( p ) = u ( p ) + ⌊ C c u ( p ) ⌋ q^+(p)=u(p)+\left\lfloor\frac{C}{c_u(p)}\right\rfloor q + ( p ) = u ( p ) + ⌊ c u ( p ) C ⌋ H C H_C H C H C ′ H_{C'} H C ′ C ′ ≥ C C'\ge C C ′ ≥ C
Let C ℓ ∗ = max p ∈ P c ℓ ( p ) C_\ell^*=\max_{p\in\mathcal{P}}c_\ell(p) C ℓ ∗ = max p ∈ P c ℓ ( p ) C u ∗ = max p ∈ P c u ( p ) C_u^*=\max_{p\in\mathcal{P}}c_u(p) C u ∗ = max p ∈ P c u ( p )
Algorithm for RMM-MIN-MAX-DC. Given an instance G G G ℓ ( p ) \ell(p) ℓ ( p ) ∣ A ∣ \lvert\mathcal{A}\rvert ∣ A ∣ ∣ A ∣ ⋅ C ℓ ∗ \lvert\mathcal{A}\rvert\cdot C_\ell^* ∣ A ∣ ⋅ C ℓ ∗ [ 0 , ∣ A ∣ ⋅ C ℓ ∗ ] [0,\lvert\mathcal{A}\rvert\cdot C_\ell^*] [ 0 , ∣ A ∣ ⋅ C ℓ ∗ ] C C C H C H_C H C C C C [ 0 , ∣ A ∣ ⋅ C ℓ ∗ ] [0,\lvert\mathcal{A}\rvert\cdot C_\ell^*] [ 0 , ∣ A ∣ ⋅ C ℓ ∗ ] C C C C ∗ C^* C ∗ C C C C ∗ C^* C ∗ H C ∗ H_{C^*} H C ∗
Algorithm for RMM-SIGN-MIN-MAX-DC. Given an instance G G G ρ \rho ρ M M M M R \mathcal{M}_{\mathcal{R}} M R M R \mathcal{M}_{\mathcal{R}} M R ρ \rho ρ ℓ ( p ) \ell(p) ℓ ( p ) ∣ A ∣ \lvert\mathcal{A}\rvert ∣ A ∣ ∣ A ∣ \lvert\mathcal{A}\rvert ∣ A ∣ [ 0 , ∣ A ∣ ⋅ max { C ℓ ∗ , C u ∗ } ] [0,\lvert\mathcal{A}\rvert\cdot\max\{C_\ell^*,C_u^*\}] [ 0 , ∣ A ∣ ⋅ max { C ℓ ∗ , C u ∗ }] M R \mathcal{M}_{\mathcal{R}} M R C C C H C H_C H C M M M H C H_C H C σ ( M ) ⪰ R ρ \sigma(M) \succeq_R \rho σ ( M ) ⪰ R ρ M M M C C C [ 0 , ∣ A ∣ ⋅ ( max { C u ∗ , C u ∗ } ) ] [0,|\mathcal{A}| \cdot(\max\{C_u^*, C_u^*\})] [ 0 , ∣ A ∣ ⋅ ( max { C u ∗ , C u ∗ })] C C C
Algorithm for RMM-MIN-TOT-DC
Given an instance G G G M ∗ M^* M ∗
For a given instance G G G G x G_x G x p p p q − ( p ) = 0 q^-(p)=0 q − ( p ) = 0 q + ( p ) = u ( p ) q^+(p)=u(p) q + ( p ) = u ( p ) G ′ G' G ′ G G G p p p ℓ ′ ( p ) = u ′ ( p ) = ℓ ( p ) \ell'(p)=u'(p)=\ell(p) ℓ ′ ( p ) = u ′ ( p ) = ℓ ( p ) G x ′ G'_x G x ′ G ′ G' G ′
An instance G G G { a 1 , a 2 } \{a_1,a_2\} { a 1 , a 2 } { p 1 , p 2 } \{p_1,p_2\} { p 1 , p 2 } Figure 7 . The edge set of G G G Figure 7 (i). The applicant preferences are shown in Figure 7 (i); however, they are not needed for the illustration. Each post in G G G Figure 7 (ii). While the upper deviation cost values y y y y ′ y' y ′ p p p ℓ ( p ) = u ( p ) \ell(p)=u(p) ℓ ( p ) = u ( p ) G G G G = G ′ G=G' G = G ′ M 1 M_1 M 1 M 2 M_2 M 2 G ′ G' G ′ Figure 7 (iii). Both M 1 M_1 M 1 M 2 M_2 M 2 G x ′ G'_x G x ′
Figure 7. An instance G G G Figure 7 (i) shows the edge set of G G G Figure 7 (ii). Two matchings M 1 M_1 M 1 M 2 M_2 M 2 G G G Figure 7 (iii) along with their total deviation cost.
Recall that in the soft quota setting, the minimum values of total deviation in G ′ G' G ′ G G G
Lemma 14. Minimum value of total deviation cost in G ′ G' G ′ G G G
As illustrated by the example in Figure 7 , the approach in § 4.1 cannot be applied directly, and we propose the following modification. To compute a RMM-MIN-TOT-DC matching in G G G
We construct an instance G ′ G' G ′ G G G p p p ℓ ′ ( p ) = u ′ ( p ) = ℓ ( p ) \ell'(p)=u'(p)=\ell(p) ℓ ′ ( p ) = u ′ ( p ) = ℓ ( p ) G ′ G' G ′ M M M M M M G ′ G' G ′
We augment the matching M M M G x G_x G x q − ( p ) = 0 q^{-}(p)=0 q − ( p ) = 0 q + ( p ) = u ( p ) q^{+}(p)=u(p) q + ( p ) = u ( p ) M ∗ M^* M ∗ G G G § 4.1 .
Next, we describe the procedure for computing a rank-maximal matching among all matchings with the minimum total deviation cost.
Computing RMM-MIN-TOT-DC in G ′ G' G ′
Given the instance G ′ G' G ′ H H H M M M H H H
The construction of the network H H H § 4.1 for the network description). The costs are assigned as follows:
For an edge ( a , p ) (a,p) ( a , p ) G ′ G' G ′ i i i E A P \mathcal{E}_{AP} E A P − ( ( n + 1 ) r + ( n + 1 ) r − i ) -((n+1)^r+(n+1)^{r-i}) − (( n + 1 ) r + ( n + 1 ) r − i )
For an edge ( d , p ) (d,p) ( d , p ) E D P \mathcal{E}_{DP} E D P ( n + 1 ) r + 1 ⋅ c ℓ ( p ) (n+1)^{r+1}\cdot c_{\ell}(p) ( n + 1 ) r + 1 ⋅ c ℓ ( p ) c ℓ ( p ) c_{\ell}(p) c ℓ ( p )
There is a natural correspondence between a flow f f f H H H M M M G ′ G' G ′
M = { ( a , p ) ∣ f ( a , p ) = 1 , ( a , p ) ∈ E A P } . M=\{(a,p)\mid f(a,p)=1,\ (a,p)\in\mathcal{E}_{AP}\}. M = {( a , p ) ∣ f ( a , p ) = 1 , ( a , p ) ∈ E A P } . Note that, by our construction, a max-flow in H H H ∑ p ∈ P ℓ ( p ) \sum_{p\in P}\ell(p) ∑ p ∈ P ℓ ( p ) f f f c o s t ( f ) cost(f) cos t ( f )
Definition 10 (Total deviation cost of a max-flow). Total deviation cost of a max-flow f f f H H H
d t c ( f ) = ∑ p ∈ P d f ( p ) ( n + 1 ) r + 1 dtc(f)=\frac{\sum_{p\in P}d_f(p)}{(n+1)^{r+1}} d t c ( f ) = ( n + 1 ) r + 1 ∑ p ∈ P d f ( p ) where d f ( p ) = ∑ d ∈ D p f ( d , p ) ⋅ ( n + 1 ) r + 1 ⋅ c ℓ p d_f(p) = \sum_{d \in D_p} f(d,p) \cdot(n+1)^{r+1} \cdot c_{\ell p} d f ( p ) = ∑ d ∈ D p f ( d , p ) ⋅ ( n + 1 ) r + 1 ⋅ c ℓ p p p p
We now focus on matchings in G ′ G' G ′ G x ′ G'_x G x ′ M M M G x ′ G'_x G x ′ f f f H H H d t c ( M ) = d t c ( f ) d_{tc}(M) = d_{tc}(f) d t c ( M ) = d t c ( f ) f f f H H H M M M G ′ G' G ′ H H H
Cost of a max-flow in H H H G ′ G' G ′ By the design of our network, we ensure that the cost of a max-flow in H H H G ′ G' G ′
Lemma 15. Let f , f ′ f, f' f , f ′ H H H M f , M f ′ M_f, M_{f'} M f , M f ′ G ′ G' G ′ d t c ( M f ) < d t c ( M f ′ ) d_{tc}(M_f) < d_{tc}(M_{f'}) d t c ( M f ) < d t c ( M f ′ ) cost ( f ) < cost ( f ′ ) \operatorname{cost}(f) < \operatorname{cost}(f') cost ( f ) < cost ( f ′ )
Proof: For a post p p p E D P \mathcal{E}_{DP} E D P E A P \mathcal{E}_{AP} E A P H H H E A P \mathcal{E}_{AP} E A P E D P \mathcal{E}_{DP} E D P ( n + 1 ) r + 1 (n+1)^{r+1} ( n + 1 ) r + 1 E D P \mathcal{E}_{DP} E D P d t c ( M f ) = d t c ( f ) d_{tc}(M_f) = d_{tc}(f) d t c ( M f ) = d t c ( f ) E D P \mathcal{E}_{DP} E D P f f f d t c ( M f ) ⋅ n r + 1 d_{tc}(M_f) \cdot n^{r+1} d t c ( M f ) ⋅ n r + 1 E A P \mathcal{E}_{AP} E A P f f f
cost ( f ) ≤ ∣ M f ∣ ( − ( n + 1 ) r ) − ∣ M f ∣ + d t c ( M f ) ⋅ ( n + 1 ) r + 1 . \operatorname{cost}(f) \le|M_f|\left(-(n+1)^r\right)-|M_f|+d_{tc}(M_f)\cdot(n+1)^{r+1}. cost ( f ) ≤ ∣ M f ∣ ( − ( n + 1 ) r ) − ∣ M f ∣ + d t c ( M f ) ⋅ ( n + 1 ) r + 1 . where the equality is achieved when all edges are of rank r r r f ′ f' f ′
cost ( f ′ ) ≥ ∣ M f ′ ∣ ( − ( n + 1 ) r ) − ∣ M f ′ ∣ ( ( n + 1 ) r − 1 ) + d t c ( M f ′ ) ⋅ ( n + 1 ) r + 1 . \operatorname{cost}(f') \ge|M_{f'}|\left(-(n+1)^r\right)-|M_{f'}|\left((n+1)^{r-1}\right)+d_{tc}(M_{f'})\cdot(n+1)^{r+1}. cost ( f ′ ) ≥ ∣ M f ′ ∣ ( − ( n + 1 ) r ) − ∣ M f ′ ∣ ( ( n + 1 ) r − 1 ) + d t c ( M f ′ ) ⋅ ( n + 1 ) r + 1 . where the equality is achieved when all edges are of rank 1.
We show that ∣ M f ∣ ≥ ∣ M f ′ ∣ |M_f| \ge|M_{f'}| ∣ M f ∣ ≥ ∣ M f ′ ∣ ∣ M f ∣ < ∣ M f ′ ∣ |M_f| < |M_{f'}| ∣ M f ∣ < ∣ M f ′ ∣ E D P \mathcal{E}_{DP} E D P f f f f ′ f' f ′ ∑ p ∈ P ℓ ( p ) − ∣ M f ∣ \sum_{p \in\mathcal{P}} \ell(p)-|M_f| ∑ p ∈ P ℓ ( p ) − ∣ M f ∣ ( n + 1 ) r + 1 (n+1)^{r+1} ( n + 1 ) r + 1 d t c ( M f ) ⋅ ( n + 1 ) r + 1 d_{tc}(M_f)\cdot(n+1)^{r+1} d t c ( M f ) ⋅ ( n + 1 ) r + 1 ∑ p ∈ P ℓ ( p ) − ∣ M f ′ ∣ \sum_{p \in\mathcal{P}} \ell(p)-|M_{f'}| ∑ p ∈ P ℓ ( p ) − ∣ M f ′ ∣ ( n + 1 ) r + 1 (n+1)^{r+1} ( n + 1 ) r + 1 d t c ( M f ′ ) ⋅ ( n + 1 ) r + 1 d_{tc}(M_{f'})\cdot(n+1)^{r+1} d t c ( M f ′ ) ⋅ ( n + 1 ) r + 1 ∣ M f ∣ < ∣ M f ′ ∣ |M_f| < |M_{f'}| ∣ M f ∣ < ∣ M f ′ ∣ d t c ( M f ) ⋅ ( n + 1 ) r + 1 > d t c ( M f ′ ) ⋅ ( n + 1 ) r + 1 d_{tc}(M_f)\cdot(n+1)^{r+1} > d_{tc}(M_{f'})\cdot(n+1)^{r+1} d t c ( M f ) ⋅ ( n + 1 ) r + 1 > d t c ( M f ′ ) ⋅ ( n + 1 ) r + 1 d t c ( M f ) < d t c ( M f ′ ) d_{tc}(M_f) < d_{tc}(M_{f'}) d t c ( M f ) < d t c ( M f ′ )
Using the facts d t c ( M f ) < d t c ( M f ′ ) d_{tc}(M_f) < d_{tc}(M_{f'}) d t c ( M f ) < d t c ( M f ′ ) ∣ M f ∣ ≥ ∣ M f ′ ∣ |M_f| \ge|M_{f'}| ∣ M f ∣ ≥ ∣ M f ′ ∣ cost ( f ) < cost ( f ′ ) \operatorname{cost}(f) < \operatorname{cost}(f') cost ( f ) < cost ( f ′ )
Lemma 16. Let f f f H H H M f M_f M f G ′ G' G ′ M f M_f M f G ′ G' G ′
Proof: Suppose not. Let M ∗ M^* M ∗ G ′ G' G ′ f ∗ f^* f ∗ d t c ( M ∗ ) < d t c ( M f ) d_{tc}(M^*) < d_{tc}(M_f) d t c ( M ∗ ) < d t c ( M f ) cost ( f ∗ ) < cost ( f ) \operatorname{cost}(f^*) < \operatorname{cost}(f) cost ( f ∗ ) < cost ( f ) f f f
Given the connection between the total deviation cost of G G G G ′ G' G ′ Lemma 14 , which is independent of the preferences, we know that the minimum total deviation cost in G G G G ′ G' G ′
Corollary 2. Any min-cost max-flow in H H H G G G
We now prove the preference optimality of the matching obtained by step (A).
Lemma 17. Any min-cost max-flow in H H H G ′ G' G ′
Proof of Lemma 17 is a direct generalization of the proof of Lemma 8.
In step (A), we have computed a matching M M M G ′ G' G ′ G G G
Special case of RMM-SIGN-MIN-TOT-DC
Given an instance G G G ρ \rho ρ c ℓ c_\ell c ℓ c u c_u c u Figure 3 , we can solve this problem efficiently. We then extend this approach to a special case, where posts are divided into a constant number of partitions, with each partition having a uniform lower and upper deviation cost across all its posts. We provide an efficient algorithm for this case, which we describe below.
We consider the case of the RMM-SIGN-MIN-TOT-DC problem, where posts in P \mathcal{P} P P 1 ∪ P 2 ∪ … ∪ P k \mathcal{P}_1 \cup\mathcal{P}_2 \cup\ldots\cup\mathcal{P}_k P 1 ∪ P 2 ∪ … ∪ P k p ∈ P i p \in\mathcal{P}_i p ∈ P i x i x_i x i y i y_i y i Figure 3 as follows.
We remove all the outgoing edges from d ′ d' d ′ d i ′ d'_i d i ′ i ∈ [ k ] i \in[k] i ∈ [ k ] d ′ d' d ′ d i ′ d'_i d i ′ [ l d i , l d i ] [ld_i,ld_i] [ l d i , l d i ]
For each i ∈ [ k ] i \in[k] i ∈ [ k ] d i ′ d'_i d i ′ p ′ p' p ′ p ∈ P i p \in\mathcal{P}_i p ∈ P i [ 0 , l d i ] [0,ld_i] [ 0 , l d i ]
We remove all incoming edges to d ′ ′ d'' d ′′ d i ′ ′ d''_i d i ′′ i ∈ [ k ] i \in[k] i ∈ [ k ] d i ′ ′ d''_i d i ′′ d ′ ′ d'' d ′′ [ u d i , u d i ] [ud_i,ud_i] [ u d i , u d i ]
For each i ∈ [ k ] i \in[k] i ∈ [ k ] p ′ ′ p'' p ′′ d i ′ ′ d''_i d i ′′ p ∈ P i p \in\mathcal{P}_i p ∈ P i [ 0 , u d i ] [0,ud_i] [ 0 , u d i ]
In this network, for each i ∈ [ k ] i \in[k] i ∈ [ k ] l d i ld_i l d i u d i ud_i u d i P i \mathcal{P}_i P i { ( l d i , u d i ) } 1 ≤ i ≤ k \{(ld_i,ud_i)\}_{1\leq i\leq k} {( l d i , u d i ) } 1 ≤ i ≤ k
Observe that, for a given i ∈ [ k ] i \in[k] i ∈ [ k ] P i \mathcal{P}_i P i ∣ A ∣ ⋅ ∣ P i ∣ |\mathcal{A}| \cdot|\mathcal{P}_i| ∣ A ∣ ⋅ ∣ P i ∣ ( l d i , u d i ) (ld_i,ud_i) ( l d i , u d i ) ( ∣ A ∣ ⋅ ∣ P i ∣ + 1 ) 2 (|\mathcal{A}| \cdot|\mathcal{P}_i|+1)^2 ( ∣ A ∣ ⋅ ∣ P i ∣ + 1 ) 2 { ( l d i , u d i ) } 1 ≤ i ≤ k \{(ld_i,ud_i)\}_{1\leq i\leq k} {( l d i , u d i ) } 1 ≤ i ≤ k O ( n 4 k ) O(n^{4k}) O ( n 4 k ) ∣ A ∣ = O ( ∣ P ∣ ) |\mathcal{A}|=O(|\mathcal{P}|) ∣ A ∣ = O ( ∣ P ∣ ) M M M σ ( M ) ⪰ R ρ \sigma(M) \succeq_R \rho σ ( M ) ⪰ R ρ M M M O ( n 4 k ⋅ T ( n ) ) O(n^{4k} \cdot T(n)) O ( n 4 k ⋅ T ( n )) T ( n ) T(n) T ( n )
Discussion
In this work, we study the problem of computing optimal matchings with one-sided preferences in the soft quota setting. We consider two orthogonal optimization parameters, namely the deviation of the matching and preference optimality. For the preference optimality notions of rank-maximality and fairness, we present efficient algorithms. Our algorithms rely on exponential weights on the edges of the flow network. It would be interesting to design algorithms that do not need large weights.
We also explore a natural generalization of the soft quota setting, where every deviation is associated with a cost. In this generalized soft quota setting, we present efficient algorithms for rank-maximality and fairness when the objective is to optimize the maximum deviation cost. For minimizing total deviation cost, we provide an efficient algorithm for the case where no signature requirement is imposed. However, when a signature requirement is imposed, we are not aware of any hardness or algorithmic results for minimizing total deviation cost, leaving it as an open problem.
Acknowledgements
We thank Govind S Sankar for his valuable contributions and insightful discussions that greatly assisted us in the initial stages of this work.
Appendix
Lemma 3. Let M , M ′ M, M' M , M ′ σ ( M ) ≻ F σ ( M ′ ) \sigma(M) \succ_{\mathcal{F}} \sigma(M') σ ( M ) ≻ F σ ( M ′ ) cost ( M ) < cost ( M ′ ) \operatorname{cost}(M) < \operatorname{cost}(M') cost ( M ) < cost ( M ′ ) i i i ( n + 1 ) i (n+1)^i ( n + 1 ) i r + 1 r+1 r + 1 ( n + 1 ) r + 1 (n+1)^{r+1} ( n + 1 ) r + 1
Proof: Let σ ( M ) = ( x 1 , x 2 , … , x r , x r + 1 ) \sigma(M) = (x_1, x_2, \ldots, x_r, x_{r+1}) σ ( M ) = ( x 1 , x 2 , … , x r , x r + 1 ) σ ( M ′ ) = ( y 1 , y 2 , … , y r , y r + 1 ) \sigma(M') = (y_1, y_2, \ldots, y_r, y_{r+1}) σ ( M ′ ) = ( y 1 , y 2 , … , y r , y r + 1 ) i i i σ ( M ) \sigma(M) σ ( M ) σ ( M ′ ) \sigma(M') σ ( M ′ ) x j = y j x_j = y_j x j = y j j > i j > i j > i x i < y i x_i < y_i x i < y i
The cost difference between the matchings M M M M ′ M' M ′
cost ( M ′ ) − cost ( M ) = ∑ j = 1 r + 1 ( y j − x j ) ( n + 1 ) j = ( y i − x i ) ( n + 1 ) i + ∑ j = 1 i − 1 ( y j − x j ) ( n + 1 ) j . \operatorname{cost}(M') - \operatorname{cost}(M) = \sum_{j=1}^{r+1}(y_j-x_j)(n+1)^j = (y_i-x_i)(n+1)^i + \sum_{j=1}^{i-1}(y_j-x_j)(n+1)^j. cost ( M ′ ) − cost ( M ) = j = 1 ∑ r + 1 ( y j − x j ) ( n + 1 ) j = ( y i − x i ) ( n + 1 ) i + j = 1 ∑ i − 1 ( y j − x j ) ( n + 1 ) j . Now, since y i − x i ≥ 1 y_i-x_i \ge1 y i − x i ≥ 1
cost ( M ′ ) − cost ( M ) ≥ ( n + 1 ) i + ∑ j = 1 i − 1 ( y j − x j ) ( n + 1 ) j ≥ ( n + 1 ) i − ∑ j = 1 i − 1 x j ( n + 1 ) j ≥ ( n + 1 ) i − ( ∑ j = 1 i − 1 x j ) ( n + 1 ) i − 1 . \begin{aligned}
\operatorname{cost}(M')-\operatorname{cost}(M) \ge(n+1)^i+\sum_{j=1}^{i-1}(y_j-x_j)(n+1)^j \\
&\ge(n+1)^i-\sum_{j=1}^{i-1}x_j(n+1)^j \\
&\ge(n+1)^i-\left(\sum_{j=1}^{i-1}x_j\right)(n+1)^{i-1}.
\end{aligned} cost ( M ′ ) − cost ( M ) ≥ ( n + 1 ) i + j = 1 ∑ i − 1 ( y j − x j ) ( n + 1 ) j ≥ ( n + 1 ) i − j = 1 ∑ i − 1 x j ( n + 1 ) j ≥ ( n + 1 ) i − ( j = 1 ∑ i − 1 x j ) ( n + 1 ) i − 1 . Additionally, using the fact that ∑ j = 1 i − 1 x j ≤ ∑ j = 1 r + 1 x j = n \sum_{j=1}^{i-1}x_j \le\sum_{j=1}^{r+1}x_j=n ∑ j = 1 i − 1 x j ≤ ∑ j = 1 r + 1 x j = n
cost ( M ′ ) − cost ( M ) ≥ ( n + 1 ) i − n ( n + 1 ) i − 1 = ( n + 1 ) i − 1 > 0. \operatorname{cost}(M')-\operatorname{cost}(M) \ge(n+1)^i-n(n+1)^{i-1}=(n+1)^{i-1}>0. cost ( M ′ ) − cost ( M ) ≥ ( n + 1 ) i − n ( n + 1 ) i − 1 = ( n + 1 ) i − 1 > 0. □ \square □
