# nearfeasible_stable_matchings_with_budget_constraints__5c0f3c77.pdf

Near-Feasible Stable Matchings with Budget Constraints

Yasushi Kawase Tokyo Institute of Technology and RIKEN AIP Center, Tokyo, Japan. kawase.y.ab@m.titech.ac.jp

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

This paper deals with two-sided matching with budget constraints where one side (ﬁrm or hospital) can make monetary transfers (offer wages) to the other (worker or doctor). In a standard model, while multiple doctors can be matched to a single hospital, a hospital has a maximum quota: the number of doctors assigned to a hospital cannot exceed a certain limit. In our model, a hospital instead has a ﬁxed budget: the total amount of wages allocated by each hospital to doctors is constrained. With budget constraints, stable matchings may fail to exist and checking for the existence is hard. To deal with the nonexistence of stable matchings, we extend the matching with contracts model of Hatﬁeld and Milgrom, so that it handles near-feasible matchings that exceed each budget of the hospitals by a certain amount. We then propose two novel mechanisms that efﬁciently return such a nearfeasible matching that is stable with respect to the actual amount of wages allocated by each hospital. In particular, by sacriﬁcing strategy-proofness, our second mechanism achieves the best possible bound.

1 Introduction

This paper studies a two-sided, one-to-many matching model when there are budget constraints on one side (ﬁrm 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 ﬁxed 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 ﬁrm 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.

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 proﬁtable deviations, may not exist.1

We construct and analyze our mechanisms on a matching with contracts model [Hatﬁeld and Milgrom, 2005], which characterizes a class of mechanisms called the generalized Deferred Acceptance (DA) mechanism. If a mechanism speciﬁcally, the choice function of every hospital satisﬁes three properties, i.e., substitutability, irrelevance of rejected contracts, and law of aggregate demand, then it always ﬁnds 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 ﬁnd a nearby instance with a stable matching. For a choice function that produces a nearfeasible matching, the existing properties are not sufﬁcient 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 efﬁciently. 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 efﬁciently return a near-feasible stable matching

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

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

with respect to the actual amount of wages allocated by each hospital: one is strategy-proof for doctors and the other is not. 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 proﬁtable. 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, f H, BH), where each component is deﬁned as follows. There is a ﬁnite set of doctors D = {d1, . . . , dn} and a ﬁnite set of hospitals H = {h1, . . . , hm}. Let X D H R++ denote a ﬁnite 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 x D, x H, and x W 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 proﬁle, 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 f H = (fh)h H denote hospitals utility proﬁle, 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 ) = P 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 ﬁxed budget Bh R++ that it can distribute as wages to the doctors it admits. Let BH = (Bh)h H be the budget proﬁle. We assume that, for any con-

tract (d, h, w), 0 < w Bh holds. Given X, let

wh = min x Xh x W and wh = max x Xh x W .

Moreover, we use the notation wh(X ) for any X X to denote the total wage that h offers in X , i.e., P x X h x W . 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 x D X for all doctors x D 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. Deﬁnition 1 (B H-stability). We say a matching X is B Hstable 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. Deﬁnition 1, for example, allows a central planner to add or redistribute the budgets and this planner ﬁnds 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 proﬁle 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 brieﬂy describe a class of mechanisms called the generalized DA mechanism [Hatﬁeld and Milgrom, 2005] and its properties. This mechanism uses choice functions Ch D : 2X 2X and Ch H : 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: Ch D(X ) := S d D Chd(X d). Similarly, the choice function of all hospitals Ch H(X ) is S h H Chh(X h) where Chh is a choice function of h. There are alternative ways to deﬁne 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 Ch H. Formally, the generalized DA is given as Algorithm 1.

Algorithm 1: Generalized DA

input: X, Ch D, Ch H output: matching X X

2 for i = 1, 2, . . . do

3 Y (i) Ch D(X \ R(i 1)), Z(i) Ch H(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

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

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. Hatﬁeld and Milgrom deﬁne a notion of stability, which we refer to as HM-stability.

Deﬁnition 2. (HM-STABILITY) A matching X X is said to be HM-stable if X satisﬁes (i) X = Ch D(X ) = Ch H(X ) and (ii) there exists no hospital h and set of contracts X = Chh(X h) such that X = Chh(X h X ) Ch D(X X ).

HM-stability uniﬁes 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 Ch H.

Deﬁnition 3. (SUBSTITUTABILITY, SUB) For any X , X X with X X , X \ Ch H(X ) X \ Ch H(X ).

Deﬁnition 4. (IRRELEVANCE OF REJECTED CONTRACTS, IRC) For any X X and X X \ X , Ch H(X ) = Ch H(X X ) holds if Ch H(X X ) X .

Deﬁnition 5. (LAW OF AGGREGATE DEMAND, LAD) For any X , X with X X X, | Ch H(X )| | Ch H(X )|.

Hatﬁeld and Milgrom proved that if Ch H satisﬁes SUB and IRC, the generalized DA always produces a matching that is HM-stable. If Ch H further satisﬁes 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; Mc Dermid and Manlove, 2010; Abizada, 2016]. This raises the issue of the complexity of deciding the existence of a BH-stable matching. Mc Dermid 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 ΣP 2 - 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 ﬁnd 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, f H, BH) such that wh β Bh and no stable matching exists in any inﬂated market (D, H, X, D, f H, 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 Hatﬁeld and Milgrom s framework for a situation where budget constraints may be violated. Let us ﬁrst consider the following choice function for a hospital h:

Ch h(X ) = arg max X X , wh(X ) Bh fh(X )

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 sufﬁcient 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.

Deﬁnition 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

fh(Chh(X )) fh(X ).

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 predeﬁned 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 satisﬁes 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 deﬁnition, 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},

Y (i) R(i) Y (i 1) R(i 1). (1)

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

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

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

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

(R(i 1) \ Z(i 1)) (Y (i 1) \ Z(i 1))

= R(i 2) (Y (i 1) \ Z(i 1)) = R(i 1).

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

Ch H(T (i) \ R(i 1)) = Ch H((Y (i) R(i)) \ R(i 1))

= Ch H((Y (i) R(i 1)) \ R(i 1)) = Ch H(Y (i)) = Z(i).

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 Ch H(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 deﬁnition of blocking coalition, (i) X x D 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 Ch H(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 deﬁne a choice function such that the hospital affords to hire all of the doctors who have accepted its contracts much beyond the predeﬁned budgets. The theorem simply ensures that if a choice function satisﬁes 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 arg max{fh(X ) | X X h R(l) h , wh(X ) B h} for a certain budget B h ( Bh). However, the selectable contracts are difﬁcult to predict because the resulting set depends on the choice function itself. It is not so straightforward to design or ﬁnd a choice function such that it satisﬁes 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 satisﬁes 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 predeﬁned one (how many contracts should be chosen). Indeed, at each round, it is difﬁcult 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 ﬁve doctors D = {d1, d2, d3, d4, d5} and two hospitals H = {h1, h2}. The set of offered contracts is

X = {(d1, h1, 57), (d2, h1, 50), (d3, h1, 42), (d4, h1, 55), (d5, h1, 50), (d1, h2, 100), (d2, h2, 100), (d3, h2, 100), (d4, h2, 100), (d5, h2, 100)}. 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

d1: (d1, h1, 57) d1 (d1, h2, 100), d2: (d2, h1, 50) d2 (d2, h2, 100), d3: (d3, h1, 42) d3 (d3, h2, 100), d4: (d4, h1, 55) d4 (d4, h2, 100), d5: (d5, h2, 100) d5 (d5, h1, 50).

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

Table 1: Utilities of hospitals and utilities per wage.

x Xh1 fh1 fh1/w x Xh2 fh2 fh2/w (d1, h1, 57) 111 1.95 (d1, h2, 100) 50 0.50 (d2, h1, 50) 98 1.96 (d2, h2, 100) 30 0.30 (d3, h1, 42) 83 1.98 (d3, h2, 100) 20 0.20 (d4, h1, 55) 110 2.00 (d4, h2, 100) 10 0.10 (d5, h1, 50) 101 2.02 (d5, h2, 100) 40 0.40

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

X = {(d1, h1, 57), (d2, h1, 50), (d3, h1, 42), (d4, h1, 55), (d5, h2, 100)}.

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,

X = {(d1, h2, 100), (d2, h1, 50), (d3, h1, 42), (d4, h1, 55), (d5, h2, 100)}.

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);

X = {(d1, h2, 100), (d2, h2, 100), (d3, h1, 42), (d4, h1, 55), (d5, h1, 50)}.

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:

X = {(d1, h2, 100), (d3, h1, 42), (d4, h1, 55), (d5, h1, 50)}.

No contract is rejected and the mechanism terminates. We claim that the choice function satisﬁes the following properties. Lemma 1. For each hospital h, the choice function deﬁned 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 sufﬁcient to claim that

fh(Chh(X )) fh(X ) if wh(X ) wh(Chh(X ))

for any X X X. 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

max z [0,1]X

x X fh(x) zx | X

x X x W zx wh(Chh(X ))

max z {0,1}X

x X fh(x) zx | X

x X x W zx wh(Chh(X ))

x Y fh(x) | X

x Y x W wh(Chh(X ))

Note that the ﬁrst 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 satisﬁes 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 x W wh for all x Xh. Lemma 2. For each choice function deﬁned in Algorithm 2 and a set of contracts X Xh, it holds that

wh(Chh(X )) wh kh (= wh Bh/wh ).

Now, we summarize the arguments on the above in the following theorem: Theorem 3. The generalized DA mechanism with the choice functions deﬁned 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 satisﬁes 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 ﬁrst one, the second choice function greedily picks the top min{kh, |X |} contracts. However, kh is deﬁned as min n k | Pk i=1 x(i) Bh o , 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 ﬁrst mechanism. Here, we show the properties that this mechanism satisﬁes. Lemma 3. For each hospital, the choice function deﬁned in Algorithm 3 is SUB, IRC, and COM.

Proof. IRC clearly follows from the deﬁnition of the choice functions. Next, we claim that the choice functions satisfy SUB. Let X X Xh. By deﬁnition, the utility

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

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 ﬁrst 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:

X \ Ch(X ) X \ (Chh(X ) X ) X \ Chh(X ).

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,

wh({x(1), . . . , x(k 1)}) < Bh wh({x(1), . . . , x(k)})

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 deﬁned in Algorithm 3 and a set of contracts X Xh, it holds that

wh(Chh(X )) < Bh + wh.

Now, we summarize the results for our second mechanism.

Theorem 4. The generalized DA mechanism with the choice functions deﬁned 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 sacriﬁcing 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 predeﬁned budgets is ﬂexible up to a certain amount. There is certainly some realistic situation where this assumption is justiﬁed. Indeed, in ﬁrm-worker matchings, if a ﬁrm ﬁnds 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 ﬁnally 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 ﬁeld 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 afﬁrmative 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 sacriﬁcing 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.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

References [Abdulkadiro glu and S onmez, 2003] Atila Abdulkadiro glu and Tayfun S onmez. School choice: A mechanism design approach. American Economic Review, 93(3):729 747, 2003. [Abizada, 2016] Azar Abizada. Stability and incentives for college admissions with budget constraints. Theoretical Economics, 11(2):735 756, 2016. [Barber a et al., 2004] Salvador Barber a, Walter Bossert, and Prasanta Pattanaik. Ranking sets of objects. In Handbook of Utility Theory, volume 2. Kluwer Academic Publishers, 2004. [Bouveret and Lang, 2011] Sylvain Bouveret and J erˆome Lang. A general elicitation-free protocol for allocating indivisible goods. In IJCAI, pages 73 78, 2011. [Budish and Cantillon, 2012] Eric Budish and Estelle Cantillon. The multi-unit assignment problem: Theory and evidence from course allocation at Harvard. American Economic Review, 102(5):2237 2271, 2012. [Cygan et al., 2016] Marek Cygan, Łukasz Je z, and Jiˇr ı Sgall. Online knapsack revisited. Theory of Computing Systems, 58(1):153 190, 2016. [Dantzig, 1957] George Dantzig. Discrete-variable extremum problems. Operations Research, 5(2):266 277, 1957. [Dean et al., 2006] Brian Dean, Michel Goemans, and Nicole Immorlica. The unsplittable stable marriage problem. In Proceedings of the 5th IFIP International Conference on Theoretical Computer Science, pages 65 75, 2006. [Drummond and Boutilier, 2013] Joanna Drummond and Craig Boutilier. Elicitation and approximately stable matching with partial preferences. In IJCAI, pages 97 105, 2013. [Drummond and Boutilier, 2014] Joanna Drummond and Craig Boutilier. Preference elicitation and interview minimization in stable matchings. In AAAI, pages 645 653, 2014. [Goto et al., 2016] Masahiro Goto, Atsushi Iwasaki, Yujiro Kawasaki, Ryoji Kurata, Yosuke Yasuda, and Makoto Yokoo. Strategyproof matching with regional minimum and maximum quotas. Artiﬁcial Intelligence, 235:40 57, 2016. [Hamada et al., 2017] Naoto Hamada, Anisse Ismaili, Takamasa Suzuki, and Makoto Yokoo. Weighted matching markets with budget constraints. In AAMAS, pages 317 325, 2017. [Han et al., 2015] Xin Han, Yasushi Kawase, and Kazuhisa Makino. Randomized algorithms for online knapsack problems. Theoretical Computer Science, 562:395 405, 2015. [Hatﬁeld and Milgrom, 2005] John Hatﬁeld and Paul Milgrom. Matching with contracts. American Economic Review, 95(4):913 935, 2005.

[Hosseini et al., 2015] Hadi Hosseini, Kate Larson, and Robin Cohen. Matching with dynamic ordinal preferences. In AAAI, pages 936 943, 2015. [Iwama and Taketomi, 2002] Kazuo Iwama and Shiro Taketomi. Removable online knapsack problems. In Proceedings of the 29th International Colloquium on Automata, Languages, and Programming (ICALP), pages 293 305, 2002. [Iwama and Zhang, 2007] Kazuo Iwama and Guochuan Zhang. Optimal resource augmentations for online knapsack. In Proceedings of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pages 180 188, 2007. [Kamada and Kojima, 2015] Yuichiro Kamada and Fuhito Kojima. Efﬁcient matching under distributional constraints: Theory and applications. American Economic Review, 105(1):67 99, 2015. [Kellerer et al., 2004] Hans Kellerer, Ulrich Pferschy, and David Pisinger. Knapsack Problems. Springer, 2004. [Kelso and Crawford, 1982] Alexander Kelso and Vincent Crawford. Job matching, coalition formation, and gross substitutes. Econometrica, 50(6):1483 1504, 1982. [Kojima et al., 2013] Fuhito Kojima, Parag Pathak, and Alvin Roth. Matching with couples: Stability and incentives in large markets. The Quarterly Journal of Economics, 128(4):1585 1632, 2013. [Kurata et al., 2017] Ryoji Kurata, Naoto Hamada, Atsushi Iwasaki, and Makoto Yokoo. Controlled school choice with soft bounds and overlapping types. Journal of Artiﬁcial Intelligence Research, 58:153 184, 2017. [Manlove, 2013] David Manlove. Algorithmics of Matching Under Preferences. World Scientiﬁc Publishing Company, 2013. [Mc Dermid and Manlove, 2010] Eric Mc Dermid and David Manlove. Keeping partners together: algorithmic results for the hospitals/residents problem with couples. Journal of Combinatorial Optimization, 19:279 303, 2010. [Mongell and Roth, 1986] Susan Mongell and Alvin Roth. A note on job matching with budget constraints. Economics Letters, 21(2):135 138, 1986. [Nguyen and Vohra, 2015] Thanh Nguyen and Rakesh Vohra. Near feasible stable matchings. In Proceedings of the 16th ACM Conference on Economics and Computation, pages 41 42, 2015. [Perrault et al., 2016] Andrew Perrault, Joanna Drummond, and Fahiem Bacchus. Strategy-proofness in the stable matching problem with couples. In AAMAS, pages 132 140, 2016. [Roth and Sotomayor, 1990] Alvin Roth and Marilda Sotomayor. Two-Sided Matching: A Study in Game Theoretic Modeling and Analysis. Cambridge University Press, 1990.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)