Near-Feasible Stable Matchings with Budget Constraints

1 Introduction

This paper studies a two-sided, one-to-many matching model when there are budget constraints on one side (firm or hospital), i.e., the total amount of wages that it can pay to the other side (worker or doctor) is limited. The theory of two-sided matching has been extensively developed. See the book by Roth and Sotomayor [1990] or Manlove [2013] for a comprehensive survey. In this literature, rather than fixed budgets, maximum quotas are typically used, i.e., the total number of doctors that each hospital can hire is limited.

Some real-world examples are subject to matching with budget constraints: a college can offer stipends to students to recruit better students while the budget for admission is limited, a firm can offer wages to workers under the condition

∗A full version can be found at http://arxiv.org/abs/1705.07643. Supported in part by KAKENHI 26280081, 16K16005, and 17H01787.

Atsushi Iwasaki

University of Electro-Communications and RIKEN AIP Center, Tokyo, Japan. iwasaki@is.uec.ac.jp

that employment costs depend on earnings in the previous accounting period, a public hospital can offer salaries to doctors in the case where the total amount relies on funds from the government, and so on. To establish our model and concepts, we use doctor-hospital matching as a running example.

However, most papers on matching with monetary transfers assume that budgets are unrestricted (e.g., [Kelso and Crawford, 1982]). When they are restricted, stable matchings may fail to exist [Mongell and Roth, 1986; Abizada, 2016]. In particular, Abizada considers a subtly different model from ours and shows that (coalitional) stable matchings, where groups of doctors and hospitals have no profitable deviations, may not exist. 1

We construct and analyze our mechanisms on a "matching with contracts" model [Hatfield and Milgrom, 2005], which characterizes a class of mechanisms called the generalized Deferred Acceptance (DA) mechanism. If a mechanismspecifically, the choice function of every hospital-satisfies three properties, i.e., substitutability, irrelevance of rejected contracts, and law of aggregate demand, then it always finds a "stable" allocation and is strategy-proof for doctors. However, in the presence of budget constraints, the hospital's choice function cannot satisfy these properties because stable matchings may not exist.

To deal with the nonexistence of stable matchings, we focus on a near-feasible matching that exceeds the budget of each hospital by a certain amount. This idea can be interpreted as one in which, for each instance of a matching problem, our mechanisms find a "nearby" instance with a stable matching. For a choice function that produces a nearfeasible matching, the existing properties are not sufficient to ensure the optimality of the hospitals' utilities. To resolve this, we devise a new property, which we call compatibility, on the matching with contract model. Moreover, from a practical point of view, we need to compute choice functions efficiently. However, computing each hospital's choice function is NP-hard because it is equivalent to solving a knapsack problem.

Building upon these ideas, we propose two novel mechanisms that efficiently return a near-feasible stable matching with respect to the actual amount of wages allocated by each hospital: one is strategy-proof for doctors and the other is not.

1 He also proposes a modified deferred acceptance mechanism that produces a pairwise stable matching, and that is strategy-proof for doctors.

The idea of near-feasible matchings closely relates to Nguyen and Vohra [2015]. They examine matchings with couples where joint preference lists over pairs of hospitals are submitted (e.g., [Kojima et al., 2013; Perrault et al., 2016]), and then develop an algorithm that outputs a stable matching, in which the number of doctors assigned to each hospital differs (up or down) from the actual maximum quota by at most three. Alternatively, Dean et al. [2006] examine a problem similar to ours, restricting each hospital to having only a lexicographic utility. We instead allow each hospital to have an additive utility. In any case, it must be emphasized that those studies discuss no strategic issue, i.e., misreporting a doctor's preference may be profitable. The literature on matching has found strategy-proofness for doctors, i.e., each doctor has no incentive to misreport his or her preference, to be a key property in a wide variety of settings [Abdulkadiro˘glu and S¨onmez, 2003].

2 Preliminaries

This section describes a model for two-sided matchings with budget constraints. A market is a tuple (D,H,X,≻D, fH, BH), where each component is defined as follows. There is a finite set of doctors D = {d1, . . . , dn} and a finite set of hospitals H = {h1, . . . , hm}. Let X ⊆ D × H × R++ denote a finite set of contracts where each contract x ∈ X is of the form x = (d, h,w). Here, R++ is the set of positive real numbers. A contract means that hospital h ∈ H offers wage w ∈ R++ to doctor d. A hospital can choose a wage freely within R++ and can offer a doctor multiple contracts with different wages. Each contract is acceptable for each hospital h.

Furthermore, for any subset of contracts X′ ⊆ X, let X′d denote {(d′ , h′ ,w′ ) ∈ X′ | d′ = d} and X′h denote {(d′ , h′ ,w′ ) ∈ X′ | h′ = h}. We use the notation xD, xH, and xW to describe the doctor, the hospital, and the wage associated with a contract x ∈ X, respectively.

Let ≻D= (≻d)d∈D denote the doctors' preference profile, where ≻d is the strict relation of d ∈ D over Xd ∪ {∅}, i.e., x ≻d x′ means that d strictly prefers x to x′ . ∅ indicates a null contract. Let fH = (fh)h∈H denote hospitals' utility profile, where fh : Xh → R++ is a function such that for any two sets of contracts X′ ,X′′ ⊆ Xh, hospital h prefers X′ to X′′ if and only if fh(X′ ) > fh(X′′ ) holds. We further assume that fh is additive for all h ∈ H, i.e., fh(X′ ) = ∑x∈X′ fh(x) holds for any X′ ⊆ Xh. We assume, instead of priority orderings, cardinal utilities as used in some previous work [Barber`a et al., 2004; Bouveret and Lang, 2011; Budish and Cantillon, 2012]. However, this does not matter for our theoretical results. Indeed, a cardinal utility can be transformed into a priority ordering ≻h over contracts Xh for each hospital h ∈ H, where, for any two contracts x, x′ ∈ Xh, x ≻h x′ if and only if fh(x) > fh(x′ ).

Each hospital h has a fixed budget Bh ∈ R++ that it can distribute as wages to the doctors it admits. Let BH = (Bh)h∈H be the budget profile. We assume that, for any contract (d, h, w), 0 < w ≤ Bh holds. Given X, let

Moreover, we use the notation wh(X′ ) for any X′ ⊆ X to denote the total wage that h offers in X′ , i.e., ∑x∈X′h xW .

We call a subset of contracts X′ ⊆ X a matching if |X′d | ≤ 1 for all d ∈ D. A matching X′ ⊆ X is B′H -feasible if wh(X′ ) ≤ B′h for all h ∈ H. Let us next explain the notion of a blocking set (or coalition). Given a matching X′ , another matching X′′ ⊆ Xh for hospital h is a blocking coalition if X′′ ≻xD X′ for all doctors xD of x ∈ X′′ \ X′ , fh(X′′ ) > fh(X′h ), and wh(X′′ ) ≤ B′h . If such X′′ exists, we say X′′ blocks X′ . Then we obtain a stability concept.

Definition 1 (B′H -stability). We say a matching X′ is B′H - stable if it is B′H -feasible and there exists no blocking coalition.

As we will see, when no hospital is allowed to violate the given constraints BH, conventional stable matchings (B′H = BH) may not exist. Definition 1, for example, allows a central planner to add or redistribute the budgets and this planner finds a problem instance with B′H (≥ BH) whose B′H -stable matching is guaranteed to exist. If each contract has the same amount of wage w, we can regard a budget constraint Bh for each hospital h as its maximum quota of ⌊Bh/w⌋.

A mechanism is a function that takes a profile of doctors' preferences as input and returns matching X′ . We say a mechanism is stable if it always produces a B′H -stable matching for certain B′H . We also say a mechanism is strategyproof for doctors if no doctor ever has any incentive to misreport her preference, regardless of what the other doctors report.

Next, we briefly describe a class of mechanisms called the generalized DA mechanism [Hatfield and Milgrom, 2005] and its properties. This mechanism uses choice functions ChD : 2X → 2X and ChH : 2X → 2X . For each doctor d, its choice function Chd(X′ ) chooses {x}, where x = (d, h,w) ∈ X′d such that x is the most preferred contract within X′d (we assume Chd(X′ ) = ∅ if ∅ ≻d x for all x ∈ X′d ). Then, the choice function of all doctors is given as: ChD(X′ ) := ⋃d∈D Chd(X′d ). Similarly, the choice function of all hospitals ChH(X′ ) is ⋃h∈H Chh(X′h ) where Chh is a choice function of h. There are alternative ways to define the choice function of each hospital Chh. As we discuss later, the mechanisms considered in this paper can be expressed by the generalized DA with different formulations of ChH. Formally, the generalized DA is given as Algorithm 1.

Algorithm 1: Generalized DA

input: X,ChD,ChH output: matching X′ ⊆X 1 R(0) ← ∅; 2 for i = 1, 2, . . . do 3 Y (i) ←ChD(X \ R(i-1) ), Z (i) ←ChH(Y (i) ); 4 R(i) ←R(i-1) ∪ (Y (i) \ Z (i) ); 5 if Y (i) = Z (i) then return Y (i) ;

Here, R(i) is a set of rejected contracts at the ith iteration. Doctors cannot choose contracts in R(i) . Initially, R(0) is empty. Thus, each doctor can choose her most preferred contract. The chosen set by doctors is Y (i) . Then, hospitals choose Z (i) , which is a subset of Y (i) . If Y (i) = Z (i) , i.e., no contract is rejected by the hospitals, the mechanism terminates. Otherwise, it updates R(i) and repeats the same procedure.

Hatfield and Milgrom define a notion of stability, which we refer to as HM-stability.

Definition 2. (HM-STABILITY) A matching X′ ⊆ X is said to be HM-stable if X′ satisfies (i) X′ = ChD(X′ ) = ChH(X′ ) and (ii) there exists no hospital h and set of contracts X′′ ̸= Chh(X′h ) such that X′′ = Chh(X′h ∪ X′′ ) ⊆ ChD(X′ ∪X′′ ).

HM-stability unifies stability concepts that are designed for each context of (standard) matching problems without constraints. Indeed, it implies BH-stability if we require the choice functions of hospitals to strictly satisfy budget constraints BH. Let us next see the properties for ChH.

Definition 3. (SUBSTITUTABILITY, SUB) For any X′ , X′′ ⊆ X with X′′ ⊆ X′ , X′′ \ChH(X′′ ) ⊆ X′ \ChH(X′ ).

Definition 4. (IRRELEVANCE OF REJECTED CONTRACTS, IRC) For any X′ ⊆ X and X′′ ⊆ X \ X′ , ChH(X′ ) = ChH(X′ ∪X′′ ) holds if ChH(X′ ∪X′′ ) ⊆ X′ .

Definition 5. (LAW OF AGGREGATE DEMAND, LAD) For any X′ ,X′′ with X′′ ⊆ X′ ⊆ X, |ChH(X′′ )| ≤ | ChH (X′ )|.

Hatfield and Milgrom proved that if ChH satisfies SUB and IRC, the generalized DA always produces a matching that is HM-stable. If ChH further satisfies LAD, it is strategy-proof for doctors.

2.1 Impossibility and Intractability

When no hospital is allowed to violate the given constraints, it is known that stable matchings may not exist [Mongell and Roth, 1986; McDermid and Manlove, 2010; Abizada, 2016]. This raises the issue of the complexity of deciding the existence of a BH -stable matching. McDermid and Manlove considered a special case of our model and proved NP-hardness. Hamada et al. [2017] examined a similar model to ours and Abizada [2016] and proved that the existence problem is ΣP2 - complete.

To deal with the nonexistence of stable matchings, we focus on a near-feasible matching that exceeds each budget by a certain amount. For each instance of a matching problem, our mechanisms find a nearby instance with a stable matching. The following theorem implies that, to obtain a stable matching, at least one hospital h needs to increase its budget by nearly wh.

Theorem 1. For any positive reals α < β < 1, there exists a market (D, H, X, ≻D, fH, BH) such that wh ≤ β·Bh and no stable matching exists in any inflated market (D,H,X,≻D, fH, B′H ) if Bh ≤ B′h ≤ (1 + α)Bh for all h ∈ H.

Although we omit the proof due to space limitations, we obtained this theorem by generalizing an example where no stable matching exists according to parameters α and β.

3 New Property: Compatibility

This section introduces a new property, which we call compatibility, to extend Hatfield and Milgrom's framework for a situation where budget constraints may be violated. Let us first consider the following choice function for a hospital h:

for each X′ ⊆ Xh. 2 In this case, evaluating Ch∗h is computationally hard because the problem is equivalent to the wellknown knapsack problem, which is an NP-hard problem (see e.g., [Kellerer et al., 2004]). Hence, the choice function is not practical. Even worse, the generalized DA does not always produce a BH -stable matching because such a matching need not exist. Furthermore, even if there exists a BH-stable matching, the generalized DA with the choice function may produce an unstable matching.

What choice function Chh can we construct when we allow it to violate budget constraints? Strategy-proofness is still characterized by SUB, IRC, and LAD because changing the budgets of hospitals does not affect doctors' preferences. However, SUB and IRC are not sufficient to admit a stable matching in our sense.

Intuitively, to admit such a stable matching, the set of contracts chosen by the choice function does maximize the hospital's utility. Otherwise, a hospital with non-optimal utility can form a blocking coalition. To prevent this, we need to introduce a new property.

Definition 6. (COMPATIBILITY, COM) Consider a hospital h with a utility function fh, a budget Bh, and contracts Xh. For any X′′ ⊆ X′ ⊆ Xh such that wh(X′′ ) ≤ max{Bh,wh(Chh(X′ ))}, it holds that

With this property, the output of the choice function Chh is guaranteed to be the optimal solution for a knapsack problem with a certain capacity that is greater than or equal to the predefined capacity.

We next prove that COM together with SUB and IRC characterizes stable matchings when budget constraints may be violated.

Theorem 2. Suppose that for every hospital the choice function satisfies SUB, IRC, and COM. The generalized DA produces a matching X′ that is B′H -stable where B′H = (max{Bh, wh(X′ )})h∈H .

Proof. Let the mechanism terminate at the lth iteration, i.e., X′ = Y (l) = Z (l) . From its definition, it is immediately derived that the union of Y (i) and R(i) is nondecreasing in i(≤ l), i.e., for any i ∈ {2, 3, . . . , l},

For notational simplicity, we refer to Y (i) ∪R(i) as T (i) .

2 When ties occur in the argmax above, we break ties arbitrarily, for example, by choosing the lexicographically smallest one with respect to a fixed order of doctors.

Next, to obtain ChH(X′ ∪R(l) ) = X′ for any X′ , we claim that ChH(T (i) ) = Z (i) for any i ∈ {1, 2, . . . , l}. For the base case i = 1, we have ChH(T (1) ) = ChH(Y (1) ) = Z (1) since R(1) = Y (1) \ Z (1) ⊆ Y (1) . For the general case i > 1, we suppose ChH(T (i-1) ) = Z (i-1) . From (1), we rewrite the SUB condition as T (i-1) \ChH (T (i-1) ) ⊆ T (i) \ChH (T (i) ). By the inductive hypothesis, we transform the left side of the equation (Y (i-1) ∪ R(i-1) ) \ Z (i-1) to

Hence, it holds that R(i-1) ⊆ T (i) \ ChH(T (i) ) and thus ChH(T (i) ) includes no contract in R(i-1) . Together with the IRC condition, ChH(T (i) ) is equal to

The third equality holds because Y (i) ∩R(i-1) = ∅ and Y (i) ∪ R(i) = Y (i) ∪ (R(i-1) ∪ (Y (i) \ Z (i) )) = Y (i) ∪ R(i-1) . Consequently, we obtain the claim and since X′ = Y (l) = Z (l) , we get ChH(X′ ∪ R(l) ) = X′ .

Next, since Chh is COM, fh(Chh(X′h ∪R(l) h )) ≥ fh(X′′ ) holds for any X′′ ⊆ X′h ∪ R(l) h such that wh(X′′ ) ≤ max{Bh, wh(Chh(X′h ∪R(l) h ))}. Here, as Chh(X′h ∪R(l) h ) = X′h , we have fh(Chh(X′h )) ≥ fh(X′′ ) holds for any X′′ ⊆ X′h ∪ R(l) h such that wh(X′′ ) ≤ B′h .

Suppose, contrary to our claim, that X′′ ⊆ Xh is a blocking coalition for a hospital h. By the definition of blocking coalition, (i) X′′ ⪰xD X′ for all x ∈ X′′ , (ii) fh(X′′ ) > fh(X′h ), and (iii) wh(X′′ ) ≤ B′h . The condition (i) implies x ∈ X′ ∪ R(l) for all x ∈ X′′ , and hence, X′′ ⊆ X′h ∪ R(l) h holds. This contradicts the fact that ChH(X′ ∪ R(l) ) = X′ for any X′ . Therefore, X′ is B′H -stable where B′H = (max{Bh, wh(X′ )})h∈H.

Note that this theorem does not specify how much budget a hospital may exceed. Here, one can define a choice function such that the hospital affords to hire all of the doctors who have accepted its contracts much beyond the predefined budgets. The theorem simply ensures that if a choice function satisfies COM, in addition to SUB and IRC, the generalized DA admits a B′H -stable matching X′ with B′h = max{Bh, wh(X′ )} for each hospital.

We also remark that if each hospital h knows the selectable contracts, i.e., Y (l) h ∪R(l) h , in advance, it only needs to select argmax{fh(X′′ ) | X′′ ⊆ X′h ∪ R(l) h , wh(X′′ ) ≤ B′h } for a certain budget B′h (≥ Bh). However, the selectable contracts are difficult to predict because the resulting set depends on the choice function itself. It is not so straightforward to design or find a choice function such that it satisfies the required properties and only violates budget constraints to an acceptable extent.

4 Near-Feasible Stable Mechanisms

In matching with constraints [Kamada and Kojima, 2015; Goto et al., 2016; Kurata et al., 2017], designing a desirable mechanism essentially tailors choice functions for hospitals to satisfy necessary properties and constraints simultaneously. We tackle this challenging task as an analogue to approximation or online algorithms for knapsack problems.

Let us start from Dantzig's greedy algorithm for fractional knapsack problems [Dantzig, 1957]. It greedily selects contracts with respect to utility per wage and then outputs an optimal but fractional solution. We need to develop an algorithm that always provides an integral solution. Roughly speaking, we have to provide an algorithm (choice function) that satisfies the necessary properties, e.g., SUB and COM, for any set of contracts X′ given at each round of the generalized DA. At the same time, we need to let the algorithm determine how much budget should be exceeded beyond the predefined one (how many contracts should be chosen). Indeed, at each round, it is difficult to predict the amount of excess over the budgets without violating the necessary properties. In what follows, we propose two choice functions that adaptively specify how much budgets should be spent within the generalized DA process.

4.1 Strategy-Proof Stable Mechanism

This subsection proposes a strategy-proof mechanism that outputs a matching X′ that is B′H -stable where B′h is at most wh · ⌈Bh/wh ⌉ for any h ∈ H. Let kh = ⌈Bh/wh ⌉. The choice function greedily takes the top min{kh, |X′ |} contracts according to utility per wage. Formally, it is given as Algorithm 2.

Algorithm 2:

input: X′ ⊆Xh output: Chh(X′ )

• 1 Initialize Y ← ∅;
• 2 Sort X′ in descending order of utility per wage;
• 3 for i = 1, 2, . . . ,min{kh, |X′ |} do
• 4 add the ith contract in X′ to Y ;
• 5 return Y ;

We remark that we can implement the mechanism to run in O(|X| log |X|) time by using heaps.

Next, let us illustrate this mechanism via an example.

Example 1. Consider a market with five doctors D = {d1, d2, d3, d4, d5} and two hospitals H = {h1, h2}. The set of offered contracts is

Here, h1 offers the doctors wages from 42 to 57, while h2 offers each of them wage 100. We assume that the preferences of the doctors are

The utilities of the hospitals are given in Table 1. Each hospital has a common fixed budget 100 (Bh1 = Bh2 = 100). First, each doctor chooses her most preferred contract;

Since ⌈Bh1 /wh1 ⌉ = 3, Chh1 (X′ ) chooses the top three contracts according to the ranking of utilities per wage shown in Table 1, i.e., {(d4, h1, 55), (d3, h1, 42), (d2, h1, 50)}. As well, Chh2 (X′ ) chooses the top ⌈Bh2 /wh2 ⌉ = 1 contract, i.e., {(d5, h2, 100)}.

Then, d1 chooses her second preferred contract,

Chh2 (X′ ) is {(d1, h2, 100)}, whose utility per wage is larger than (d5, h2, 100).

Next, d5 chooses her second preferred contract, i.e., (d5, h1, 50), whose utility per wage is 2.02. Since this is higher than the other contract in X′h1 , (d2, h1, 50) is rejected. Thus, d2 chooses her second preferred contract, i.e., (d2, h2, 100);

Chh2 (X′ ) = {(d1, h2, 100)}, since it has a higher utility per wage than (d2, h2, 100). Finally, since d2 no longer has a preferred contract:

No contract is rejected and the mechanism terminates.

We claim that the choice function satisfies the following properties.

Lemma 1. For each hospital h, the choice function defined in Algorithm 2 is SUB, IRC, LAD, and COM.

Proof. It is straightforward that the choice function is SUB, IRC, and LAD because it simply picks at most the top min{kh, |X′ |} contracts. Next, let us turn to COM. Let X′′ ⊆ X′ ⊆ Xh. If |X′ | ≤ kh, since the choice function picks all contracts in X′ , fh(Chh(X′ )) = fh(X′ ) ≥ fh(X′′ ) clearly holds. On the other hand, if |X′ | > kh, since it picks kh contracts, we have wh(Chh(X′ )) ≥ wh · kh ≥ Bh. Thus, it is sufficient to claim that

Since the choice function greedily pick kh contracts with respect to the utility per wage, the chosen contracts yield the optimal utility of a fractional knapsack problem [Dantzig,

1957]. Also, to maximize the utility of hospital h with X′′ , we need to solve an integral knapsack problem. Therefore, fh(Chh(X′ )) is at least

Note that the first inequality is derived from the fact that the optimal value of the fractional knapsack problem is never worse than that of the integral one. Thus, the choice function Chh satisfies COM. The proof is complete.

Next, we show the upper bound of the increment of the budgets. The following lemma clearly holds from | Chh(X′ )| ≤ kh and xW ≤ wh for all x ∈ Xh.

Lemma 2. For each choice function defined in Algorithm 2 and a set of contracts X′ ⊆ Xh, it holds that

Now, we summarize the arguments on the above in the following theorem:

Theorem 3. The generalized DA mechanism with the choice functions defined in Algorithm 2 is strategy-proof for doctors and it produces a B′H -stable matching such that Bh ≤ B′h ≤ wh · kh for any h ∈ H. In addition, the mechanism can be implemented to run in O(|X| log |X|) time.

Finally, note that, omitting the detailed proof, this mechanism is almost tight as long as we use the choice functions that satisfy LAD and COM. More precisely, for any wh , wh, and Bh, there exists a set of contracts Xh and an additive utility function fh such that any choice function Chh satisfies wh(Chh(X′ )) > wh · (Bh -wh)/wh for some X′ ⊆ Xh.

4.2 Non-Strategy-Proof Stable Mechanism

This subsection proposes a stable mechanism that is not strategy-proof, but improves the budget bound, i.e., this mechanism outputs a matching X′ that is B′H -stable where B′h is at most Bh + wh for any h ∈ H. This bound is best possible from Theorem 1.

As with the first one, the second choice function greedily picks the top min{kh, |X′ |} contracts. However, kh is defined as min {k | ∑ki=1 x(i) ≥ Bh}, where x(i) denotes the ith highest contract with respect to utility per wage. Formally, it is given as Algorithm 3. Note that the running time is O(|X| log |X|), as with the first mechanism. Here, we show the properties that this mechanism satisfies.

Lemma 3. For each hospital, the choice function defined in Algorithm 3 is SUB, IRC, and COM.

Proof. IRC clearly follows from the definition of the choice functions. Next, we claim that the choice functions satisfy SUB. Let X′′ ⊆ X′ ⊆ Xh. By definition, the utility

Algorithm 3:

input: X′ ⊆Xh output: Chh(X′ ) 1 Initialize Y ← ∅; 2 Sort X′ in descending order of utility per wage; 3 for i = 1, 2, . . . , |X′ | do 4 let x be the ith contract in X′ ; 5 if wh(Y ) < Bh then Y ← Y ∪ {x}; 6 return Y ;

per wage of any contract in Chh(X′ ) (⊇ Chh(X′ ) ∩ X′′ ) is higher than that of any contract in X′ \ Chh(X′ ) (⊇ X′′ \ Chh(X′ )). Hence, we can partition X′′ into two subsets: H = Chh(X′ ) ∩ X′′ and L = X′′ \ Chh(X′ ). Any contract in H has higher utility per wage than any contract in L. When Chh takes X′′ as an input, it first picks all of the contracts in H and some contracts in L. Therefore, we obtain Chh(X′ ) ∩ X′′ ⊆ Chh(X′′ ) and derive the SUB property:

Finally, we prove COM. Let X′ = {x(1) , . . . , x(|X′ |) } ⊆ Xh, where the contracts are arranged in decreasing order of the utility per wage. If wh(X′ ) ≤ Bh, then it is clear that Chh(X′ ) = X′ and fh(Chh(X′ )) ≥ fh(X′′ ) hold for any X′′ ⊆ X′ . Otherwise, let Chh(X′ ) = {x(1) , . . . , x(k) }. Here,

holds. As described in Lemma 1, since the greedy solution Chh(X′ ) is optimal, we have fh(Chh(X′ )) ≥ fh(X′′ ) for any X′′ ⊆ X′ such that wh(X′′ ) ≤ wh(Chh(X′ )). Thus, the lemma holds.

It is straightforward to demonstrate that Algorithm 3 does not satisfy LAD. In Example 1, when a set of contracts {(d2, h1, 50), (d3, h1, 42), (d4, h1, 55)} is given, the choice function chooses all the three contracts. Here, if (d1, h1, 57) is further added, it chooses only two contracts, i.e., {(d1, h1, 57), (d2, h1, 50)}. Thus, the second mechanism fails to satisfy LAD.

Next, we show an upper bound of the increment of the budgets. Since our choice function chooses a set of contracts that exceeds the capacity by at most one contract, we have the following lemma.

Lemma 4. For each choice function defined in Algorithm 3 and a set of contracts X′ ⊆ Xh, it holds that

Now, we summarize the results for our second mechanism.

Theorem 4. The generalized DA mechanism with the choice functions defined in Algorithm 3 produces a set of contracts X′ that is B′H -stable where Bh ≤ B′h < Bh + wh for any h ∈ H. In addition, the mechanism can be implemented to run in O(|X| log |X|) time.

5 Discussion

Based on insights gained so far, we examine two special cases of hospitals' utilities, although we omit the details here. First, let us restrict each hospital to having a utility over a set of contracts that is proportional to the total amount of wages, e.g., for every h ∈ H and X′ ∈ Xh, the utility fh(X′ ) is simply the total amount of wages wh(X′ ). In this case, we can make the second mechanism strategy-proof without sacrificing the budget bound by applying techniques from online removable knapsack problems [Iwama and Taketomi, 2002; Iwama and Zhang, 2007; Han et al., 2015; Cygan et al., 2016]. Furthermore, by giving up strategy-proofness, we can construct a stable mechanism that may increase the budget by a factor of up to one-half.

Second, we assume that each hospital has the same utility across contracts, e.g., for every h ∈ H and X′ ∈ Xh, the utility fh(X′ ) is simply the number of contracts |X′ |. In this case, we immediately obtain a strategy-proof mechanism that always produces a conventional stable matching, which never violates the given budget constraints.

Our model assumes that the amount of predefined budgets is flexible up to a certain amount. There is certainly some realistic situation where this assumption is justified. Indeed, in firm-worker matchings, if a firm finds an application from some worker who is appropriate for the business, the CEO would agree to increasing the employment cost. In doctorhospital matchings, hospitals can make an association that pools some funds in advance and subsidizes the expense of salaries according to matching results. Alternatively, even when budgets must not be exceeded, we can let our mechanisms work by setting the budget Bh to Bh -wh in advance. Our second mechanism produces a B′H -stable matching such that Bh - wh ≤ B′h ≤ Bh for any h ∈ H.

Let us finally note that there is a certain amount of recent studies on two-sided matchings in the AI and multi-agent systems community, although this literature has been established mainly in the field across algorithms and economics. Drummond and Boutilier [2013; 2014] examine preference elicitation procedures for two-sided matching. In the context of mechanism design, Hosseini et al. [2015] consider a mechanism for a situation where agents' preferences dynamically change. Kurata et al. [2017] deal with strategy-proof mechanisms for affirmative action in school choice programs (diversity constraints), while Goto et al. [2016] handle regional constraints, e.g., regional minimum/maximum quotas are imposed on hospitals in urban areas so that more doctors are allocated to rural areas.

6 Conclusion

This paper deals with matching with budget constraints, introduced a concept of near-feasible matchings and proposed two novel mechanisms that return a stable matching in polynomial time: one is strategy-proof and the other is not. Furthermore, we derived the bound of increment of the budgets. In particular, the best possible bound is obtained by sacrificing strategy-proofness. In future work, we would like to derive the lower bound for strategy-proof mechanisms and extend our results to matching problems with other constraints.