Soc Choice Welf (2016) 47:531–542 DOI 10.1007/s00355-016-0981-0 ORIGINAL PAPER

Characterizations of the cumulative offer process Mustafa Oˇguz Afacan1

Received: 16 December 2015 / Accepted: 19 July 2016 / Published online: 21 July 2016 © Springer-Verlag Berlin Heidelberg 2016

Abstract In the matching with contracts setting, we provide new axiomatic characterizations of the “cumulative offer process” (COP) in the domain of hospital choice functions that satisfy “unilateral substitutes” and “irrelevance of rejected contracts.” We say that a mechanism is truncation-proof if no doctor can ever benefit from truncating his preferences. Our first result shows that the COP is the unique stable and truncation-proof mechanism. Next, we say that a mechanism is invariant to lower-tail preference change if no doctor’s assignment changes after he changes his preferences over the contracts that are worse than his assignment. Our second result shows that a mechanism is stable and invariant to lower-tail preference change if and only if it is the COP. Lastly, by extending Kojima and Manea’s (Econometrica 78:633–653, 2010) result, we show that the COP is the unique stable and weakly Maskin monotonic mechanism.

1 Introduction Hatfield and Milgrom (2005) introduce a matching with contract framework that admits Gale and Shapley (1962)’s standard matching and Kelso and Crawford (1982)’s

I am grateful to the associate editor and the anonymous referee for their through comments and suggestions. I thank Bertan Turhan for his comments. The author gratefully acknowledges the Marie Curie International Reintegration Grant (No: 618263) within the European Community Framework Programme and TÜB˙ITAK (The Scientific and Technological Research Council of Turkey) Grant (No: 113K 763) within the National Career Development Program.

B 1

Mustafa Oˇguz Afacan [email protected] Faculty of Arts and Social Sciences, Sabancı University, 34956 Istanbul, Turkey

123

532

M. O. Afacan

labor market models as its special cases.1 While the matching with contract setting admits many real-life matching problems as its application, including student-school placements, doctor-hospital assignments, and cadet-branch matchings, we employ the doctor-hospital matching terminology in the paper. Hatfield and Milgrom (2005) adopt the substitutes condition in the conventional matching literature [e.g., see Roth and Sotomayor (1990)] and introduce a “cumulative offer process” (henceforth, COP), which is a generalization of the doctor-proposing deferred acceptance algorithm (henceforth, DA) of Gale and Shapley (1962). They then show that the COP produces stable allocations whenever contracts are substitutes. In fact, it produces the doctoroptimal stable allocation—the stable allocation unanimously preferred by doctors to any other stable allocation. Moreover, they show that the COP becomes strategy-proof2 with an additional “law of aggregate demand” condition (LAD). Since then, the COP has been the main mechanism in the matching with contract literature and received attention from researchers. Hatfield and Kojima (2010) introduce two conditions weaker than substitutes (from weaker to stronger): “bilateral substitutes” (BS) and “unilateral substitutes” (US) and show that the COP is stable under the former and produces the doctor-optimal stable allocation under the latter. They also show its immunity against preference manipulations under US and the LAD. All these results are obtained for the case where hospitals have choice functions, rather than preferences, as primitives with an additional “irrelevance of rejected contracts” (IRC) condition by Aygün and Sönmez (2013). In this paper, we provide axiomatic characterizations of the COP in the domain of choice functions that are US satisfying IRC. While there are various axiomatizations of its predecessor DA in the standard matching framework for various domains, to the best of our knowledge, there are only three studies providing characterizations of the COP in the current matching with contract setting. First, Hatfield and Kojima (2010) show that under US and IRC, it is the doctor-optimal stable mechanism. Hatfield et al. (2015) provide three conditions giving the maximal hospital choice function domain to have a stable and strategy-proof mechanism, and within that domain, the COP is the unique such mechanism. Their three conditions are weaker than the combination of US and the LAD. As we do not impose the latter, their results do not imply ours.3 In another recent study, Hirata and Kasuya (2015) show that whenever every hospital’s choice function is induced by some slot-specific priorities, then the COP is the unique stable and strategy-proof rule. Our first characterization concerns the COP’s strategic properties. A preference list is said to be a truncation of another preference list if the relative rankings of the contracts remain the same while the set of contracts that are better than being unassigned shrinks under the truncation. Truncation strategies are well-studied in the literature. Roth and Rothblum (1999) and Ehlers (2008) show that under a large class of mechanisms, including priority and linear programming mechanisms, they continue to be profitable even in a low information setting. Moreover, Mongell and Roth 1 Echenique (2012) shows that under the substitutes condition of Hatfield and Milgrom (2005), matching

with contracts problems can be embedded into Kelso and Crawford (1982)’s setting. 2 That is, no doctor ever has incentive to misreport his preferences. 3 This is also clear from the results. In our setting, the COP is not strategy-proof.

123

Characterizations of the cumulative offer process

533

(1991) empirically document that agents used them in real-life matching problems. Hence, truncation strategies are important for both theoretical and practical purposes; therefore, it is desirable for a mechanism to be at least immune to truncations if it is not strategy-proof. From Hatfield and Milgrom (2005), we know that the COP is not strategy-proof under the substitutes and IRC conditions.4 Yet, Hatfield et al. (2015) find that under a weaker “observable substitutes” condition along with IRC, the COP is at least non-manipulable via truncation. We go beyond this result and show that under the stronger US and IRC conditions, the COP is the unique stable mechanism that is immune to truncations. In the closest result to this, Ehlers (2010) characterizes the COP’s predecessor, DA, in the standard matching domain with responsive choice functions by stability, independence of truncations, and a kind of capacity manipulation-proofness property.5 Our second axiomatization deals with a certain invariance property. One could argue that doctors’ assignments should not depend on their preferences over the contracts that are worse than their assignments. Our invariance axiom formalizes this, and we say that a mechanism is invariant to lower-tail preference change if no doctor’s assignment changes in response to a change in his preferences over the contracts that he finds worse than his assignment. We show that under US and IRC, the COP is the unique stable mechanism that is also invariant to lower-tail preference change. In our last axiomatization, we adapt the weak Maskin monotonicity condition Kojima and Manea (2010) to the matching with contract setting and show that under US and IRC, the COP is the unique stable and weakly Maskin monotonic mechanism. This result generalizes Theorem 3 of Kojima and Manea (2010) that shows that in the usual matching (without contract) setting, the DA is the unique stable and weakly Maskin monotonic rule in the domain of acceptant6 and substitutable choice functions. The COP coincides with the DA under US and IRC [see Hatfield and Kojima (2010) and Aygün and Sönmez (2012)]. Hence, this paper effectively axiomatizes the DA; however, we prefer referring to the mechanism as the COP in order to adhere to the matching with contracts literature. In relation to this, another way of stating the paper’s contribution is that it provides characterizations of the DA in the largest choice function domain up to date.7

4 They assume that hospitals have underlying preferences, inducing their choice functions. IRC is satisfied

whenever choice functions are induced by preferences [see Aygün and Sönmez (2013)]. 5 For any given mechanism and problem, independence of truncations imposes that after a hospital truncates

its preferences so that its assigned doctors at the initial mechanism outcome are better than keeping position empty, the hospital’s assignment does not change. On the other hand, capacity manipulation-proofness refers to non-manipulability by hospitals via capacity misreporting. 6 A choice function is acceptant if it chooses as many doctors as possible up to capacities. 7 As pointed out earlier, Hatfield et al. (2015)’s conditions are weaker than the combination of US and the

LAD. As we do not impose the latter, their domain does not include ours. This fact is also readily observable from the results that the COP is strategy-proof in their domain, yet it is not in the current US and IRC domain (see Hatfield and Milgrom (2005) or Footnote 11). By the same reason, our choice function domain is not included in that of Corollary 1 of Hirata and Kasuya (2015) showing that the COP is the unique stable and strategy-proof rule whenever choice functions are induced by some slot-specific priorities (apart from Corollary 1, Hirata and Kasuya (2015) consider the larger choice function domain that consists of any choice function satisfying IRC).

123

534

M. O. Afacan

2 Related literature Besides the theoretical appeal of the matching with contract framework, its recent surge in the literature shows its practical relevance. Sönmez and Switzer (2013) and Sönmez (2013) formulate cadet-branch matching in the US Army as a matching with contracts problem. Both papers show that the currently used mechanisms fail to admit desirable properties, and they propose to replace them with the COP. Kominers and Sönmez (2016) allow school priorities to change across seats within schools in school choice. They study the problem in the matching with contracts framework and offer the COP to be used and show that their results also have applications to airline seat upgrades and affirmative action problems. Among other recent papers, Aygün and Bo (2014) and Aygün and Turhan (2014) consider affirmative action policies in Brazilian and Indian colleges and document the weaknesses of the current mechanisms. They both study the problem in the matching with contract setting and propose the COP against the currently used mechanisms. Given that the COP has proved to be important for both theoretical and practical purposes, its various properties have been studied in the literature. Hatfield and Kojima (2010) show that under US, no previously rejected contract is accepted in a later step in the course of the COP. This result is shown for the case where hospitals have choice functions, instead of preferences, with additional IRC. Hatfield et al. (2015) obtain the same result even under a weaker “observable substitutes” condition and IRC. Hatfield and Milgrom (2005) introduce a version of the COP in which doctors make offers simultaneously, whereas in Hatfield and Kojima (2010)’s version, doctors make offers sequentially. Hirata and Kasuya (2014) prove that under BS and IRC, these two versions coincide with each other regardless of the order in which doctors make offer in the sequential version. There is a vast literature on the characterization of well-known mechanisms, but the most related characterizations are of the COP and the DA. Apart from the already cited papers in this strand of literature, in the standard matching (without contract) setting, Kojima and Manea (2010) offer axiomatizations of the DA in the domain of acceptant and substitutable choice functions. A notable feature of Kojima and Manea (2010) is that some of their results do not take choice functions as primitives of the problem. Similar approach is employed by Ehlers and Klaus (2014) where they characterize the DA in the standard framework (without contracts) with responsive and coarse priorities. By building on Kojima and Manea (2010)’s results, Morrill (2013) provides characterizations of the DA whenever a substitutable choice function profile is given as a primitive. In the classical setting with responsive choice functions, Gale and Shapley (1962) show that the DA is the doctor-optimal stable mechanism; Alcalde and Barbera (1994) prove that the DA is the unique stable and strategy-proof rule; and Balinski and Sönmez (1999) find that the DA is the only rule that satisfies stability and respecting improvements.

3 The model and results There are finite sets D and H of doctors and hospitals, and a finite set X of contracts. Each contract x ∈ X is associated with one doctor x D ∈ D and one hospital x H ∈ H .

123

Characterizations of the cumulative offer process

535

Each doctor can sign at most one contract. The null contract, denoted by ∅, means that  the doctor has no contract. For X  ⊆ X , let X D = d ∈ D : ∃ x ∈ X  with x D = d . Each doctor d ∈ D has a strict preference relation Pd over {x ∈ X : x D = d}∪{∅}.  = x = d, we write x  R x only if x  P x or Given any two contracts x  , x where x D D d d  x = x. A contract x is acceptable to doctor d if x Pd ∅. It is otherwise unacceptable. The chosen contract of doctor d from X  ⊆ X is given as Cd (X  ) = max Pd



x ∈ X : xD = d



 ∪ {∅} .



We write C D (X  ) = d∈D Cd (X  ) for the set of contracts chosen from X  by some doctor. Let P = (Pd )d∈D be the preference profile of the doctors. Each hospital h has a choice function C h : 2 X → 2 X defined as follows: for any  X ⊆ X,      C h (X  ) ∈ X  ⊆ X  : (for each x ∈ X  , x H = h) and for any x  , x  ∈ X  , x D = x D .

 We write C H (X  ) = h∈H C h (X  ) for the set of contracts chosen from X  by some hospital. The choice function profile of hospitals is C = (C h )h∈H . In the rest of the paper, we fix D, H , and C, thereby suppressing them from the notation and simply denote the problem by P.  . A set of contracts X  ⊆ X is an allocation if x, x  ∈ X  and x = x  imply x D = x D    For any allocation X , let X d be the doctor d’s contract at X (if he does not have any contract, then X d = ∅). We extend the preferences of doctors over the set of allocations in a natural way as follows: for any two allocations X  and X  , X  Pd X  if and only if X d Pd X d . Definition 1 An allocation X  is stable if (1) C D (X  ) = C H (X  ) = X  and (2) there exist no hospital h and set of contracts X  = C h (X  ) such that X  = C h (X  ∪ X  ) ⊆ C D (X  ∪ X  ). A mechanism ψ is a function producing an allocation ψ(P) for any problem P. Mechanism ψ is stable if ψ(P) is stable for every problem P. Hatfield and Milgrom (2005) generalize Gale and Shapley (1962)’s celebrated DA to the matching with contracts problem by introducing the following COP. Step 1: One arbitrarily chosen doctor d offers his first choice contract x1 . Hospital x1 H holds the contract if x1 ∈ C x1 H ({x1 }) and rejects it otherwise. Let A x1 H (1) = {x1 } and Ah  (1) = ∅ for all h  = x1 H . In general, Step t: One arbitrarily chosen doctor currently having no contract held by any hospital offers his preferred contract xt from among those that have not been rejected in the previous steps. Hospital xt H holds the contract if xt ∈ C xt H (A xt H (t − 1) ∪ {xt }) and rejects it otherwise. Let A xt H (t) = A xt H (t − 1) ∪ {xt } and Ah  (t) = Ah  (t − 1) for all h  = xt H . The algorithm terminates when every doctor is matched to a hospital or every unmatched doctor has all acceptable contracts rejected. As there are finitely many

123

536

M. O. Afacan

contracts, the algorithm terminates in some finite step T . The final outcome is  C (A h h (T )). Note that in each step t, x t H chooses from the set of all offers h∈H it accumulates up until this step, including step t’s offer. That is, it chooses from A xt H (t − 1) ∪ {xt }. This is the only difference between the COP and the DA, where in the latter, hospitals never consider the contracts that they reject in earlier steps. The COP may not even produce an allocation without any structure on hospital choice functions. In this regard, the following two conditions have proved to be useful. Definition 2 [Hatfield and Kojima (2010)] Contracts are unilateral substitutes (US) for hospital h if there are no set of contracts Y ⊂ X and pair of contracts x, z ∈ X \ Y such that / Y D , and z ∈ C h (Y ∪ {x, z}). z∈ / C h (Y ∪ {z}), z D ∈ In words, US ensures that if a rejected contract z of doctor z D from Y is chosen whenever a new contract x is available, then that doctor has to have another contract in Y . Definition 3 [Aygün and Sönmez (2013)] Contracts satisfy the irrelevance of rejected contracts (IRC) for hospital h if for any Y ⊂ X and z ∈ X \ Y , z∈ / C h (Y ∪ {z}) ⇒ C h (Y ) = C h (Y ∪ {z}). IRC requires that the removal of rejected contracts has no effect on the chosen sets.8 Hatfield and Kojima (2010) and Aygün and Sönmez (2012) show that the COP produces a stable allocation even under the weaker BS 9 and IRC conditions; thereby the COP is a stable mechanism under US and IRC. In what follows, we provide different axiomatizations of the COP under US and IRC. For a given doctor d with preferences Pd , let Ac(Pd ) = {x ∈ X : x D = d and x Pd ∅}. That is, it is the set of contracts doctor d finds acceptable. A preference list Pd is a  = d, truncation of Pd if Ac(Pd ) ⊂ Ac(Pd ), and for any x, x  ∈ X with x D = x D    x Pd x if and only if x Pd x . Definition 4 A mechanism ψ is truncation-proof if there are no problem P, doctor d ∈ D, and truncation Pd such that ψ(Pd , P−d )Pd ψ(P).10 Roth and Rothblum (1999) and Ehlers (2008) demonstrate that under a large class of mechanisms, truncation strategies are easy to employ in the sense that agents need less information about others’ preferences to profitably employ them. Moreover, Mongell and Roth (1991) show that truncation strategies were employed in real-life matching problems. Therefore, it is desirable for a mechanism to be truncation-proof in both 8 In the many-to-many matching context (without contracts), Blair (1988) and Alkan (2002) use this condition. The latter refers to it as “consistency.” 9 Contracts are BS if there are no set of contracts Y ⊂ X and pair of contracts x, z ∈ X \ Y such that

z∈ / C h (Y ∪ {z}), z D , x D ∈ / Y D , and z ∈ C h (Y ∪ {x, z}). 10 P −d is the preference profile of all doctors but doctor d.

123

Characterizations of the cumulative offer process

537

theory and practice. We already know that the COP is not strategy-proof under US and IRC.11 However, Hatfield et al. (2015) show that the COP is truncation-proof under an “observable substitutes” condition along with IRC together, which is weaker than US and IRC together. In the rest of the paper, with US and IRC, we go beyond that finding and show that the COP is indeed the unique truncation-proof mechanism among all stable mechanisms. We now introduce another axiom, which is new in the literature, although its close variants have been introduced in other settings. It restricts how a mechanism responds to certain changes in preferences. For a given doctor d with his preferences Pd and a   = d and x  R x , that is, it is the contract of himself x, let U (Pd , x) = x  ∈ X : x D d set of all contracts that are no worse than x. Let Pd|U (P ,x) be the restriction of Pd to d U (Pd , x). Definition 5 A mechanism ψ is invariant to lower-tail preference change if for any problem P, any doctor d ∈ D, and any Pd such that Pd| = Pd| , ψd (P) = ψd (Pd , P−d ).

U ( Pd ,ψd (P))

U ( Pd ,ψd (P))

Less formally, it imposes that no doctor’s assignment changes as a result of his preferences change only over the contracts that he finds inferior to his assignment. Different variants of this axiom have been introduced in other contexts.12 For our last axiomatization, let X d = {x ∈ X : x D = d} ∪ {∅}. That is, X d is the set of all doctor d’s contracts, along with the null contract. Following Maskin (1999), we say that Pd is a monotonic transformation of Pd at contract x ∈ X d if x  Pd x, then x  Pd x for any x  ∈ X d . A preference profile of doctors P  is a monotonic transformation of P at an allocation X  if, for every doctor d, Pd is a monotonic transformation of Pd at his contract under X  . Definition 6 (Kojima and Manea (2010)) A mechanism ψ satisfies weak Maskin monotonicity if, for any monotonic transformation P  of P at ψ(P) and for any doctor d, ψ(P  )Rd ψ(P). For any given mechanism ψ, if P  is a monotonic transformation of P at ψ(P), then we can intuitively say that the competition among the doctors decreases at P  because they do not offer some of their contracts that are not achievable at P under ψ. Naturally, this lessened competition among the doctors should not harm them, and weak Maskin monotonicity ensures this to be the case. Kojima and Manea (2010) show that in the usual matching without contract setting, for any given substitutable 11 To see this, consider a pair of doctors d , d and one hospital h. Let P : x, x  , ∅; 1 2 d1 Pd2 : y, y  , ∅. Hospital h’s choice function is induced by the following preferences:           x , {y} , x, y  , {x, y} , x  , y , x  , y  , {x} , y  , ∅. The earlier a contract (set) appears Ph :

in a preference list, the more preferred   it is. It is easy to verify that both US and IRC hold. Under the true preferences, the COP outcome is x  . Let doctor d2 misreport by submitting Pd : y  , ∅. Then, under the 2   false preferences, the COP outcome is x, y  , benefiting doctor d2 . 12 In the random matching context, some stronger variants of this axiom have been used in different papers, including Hashimoto and Hirata (2011), Hashimoto et al. (2014), Bogomolnaia and Heo (2012), and Heo and Yilmaz (2015).

123

538

M. O. Afacan

and acceptant choice function profile, the DA is the only rule satisfying stability and weak Masking monotonicity. Our main theorem shows that their result carries over to the current richer matching with contract framework with more general US choice function domain. Before the main result, we give a lemma, which may be of interest on its own. We say that a mechanism ψ is individually rational for doctors if, for any problem P, C D (ψ(P)) = ψ(P). It is immediate to see that individual rationality for doctors is weaker than stability. Lemma 1 (1) If a mechanism satisfies weak Maskin Monotonicity, then it invariant to lower-tail preference change. (2) If a mechanism is individually rational for doctors and invariant to lower-tail preference change, then it is truncation-proof. Proof See the Appendix.



Theorem 1 Under US and IRC, for any mechanism ψ, the followings are equivalent. (1) (2) (3) (4)

ψ ψ ψ ψ

= C O P. is stable and truncation-proof. is stable and invariant to lower-tail preference change. is stable and weakly Maskin monotonic.

Proof See the Appendix.



Remark 1 It is easy to see that stability is separately independent of truncationproofness, invariance to lower-tail preference change, and weak Maskin monotonicity. By Lemma 1, we know that weak Maskin monotonicity implies invariance to lowertail preference change. In what follows, we observe that there is no further relation among these three conditions (note that by Theorem 1 , with additional stability, each of them implies the others). To see this, consider a problem where there exist one doctor d and one hospital h. Suppose that there are three different contracts: x, x  , and x  . Let Pd : x, x  , x  , ∅ and Pd : x, ∅, x  , x  . Hospital h has preferences as well and let Ph : x, x  , x  , ∅.13 Consider a mechanism ψ such that ψ(Pd ) = {x} and ψ(Pd ) = {∅}, and it coincides with the COP at other instances. Mechanism ψ is truncation-proof; however it is not invariant to lower-tail preference change. Due to Lemma 1, this also shows that truncation-proofness does not imply weak Maskin monotonicity.“ For the converse, let Pd : x, x  , ∅, x  and consider mechanism φ such that φ(Pd ) =       φ(Pd ) = x  , φ(Pd ) = x  , and φ( Pˆd ) = x  for any other Pˆd . Mechanism φ is invariant to lower-tail preference change, yet it is neither truncation-proof nor weakly Maskin monotonic. Now suppose that doctor d has two contracts, x and x  . Let Pd : x, ∅, x  ;  Pd : x, x  , ∅; and Pd: ∅, x, x  . Let Ph : x, x  , ∅. Consider a mechanism ϕ where ϕ(Pd ) = ϕ(Pd ) = x  , ϕ(Pd ) = {∅}, and ϕ coincides with the COP at every other problem. Then, ϕ is weakly Maskin monotonic, yet it is not truncation-proof. 13 Note that the hospital choice function satisfies both US and IRC.

123

Characterizations of the cumulative offer process

539

Remark 2 Our characterizations do not carry over to the larger domain of BS and IRC. First, the COP loses invariance to lower-tail preference changes. Hence, in particular, it is no longer weakly Maskin monotonic (due to Lemma 1). To see this, let D = {d1 , d2 } and H = {h 1 }. Consider the following preference profile (assuming that the hospital’s choice function is generated by its preferences): Pd1 : x, x  , ∅; Pd2 : y, y  , ∅; Ph 1 :



 x, y   x   y  x  ..anything..  ∅.

It is easy to verify that the contracts IRC.14 The COP are BS (not US), satisfying    outcome at the above problem is x, y . Let us now consider Pd1 : x, ∅, x  . Then, COP(Pd1 , Pd2 ) = {y}. Therefore, it is not invariant to lower-tail preference change under BS and IRC. On the other hand, the COP preserves its truncation-proofness under BS and IRC, yet it is no longer unique such rule among other stable mechanisms.15 For the proof, consider the above same set of doctors and hospital along with the same doctor preferences. Let the hospital preferences be as follows: Ph 1 :



   x  , y   x, y   x   y  {x, y}  ..anything..  ∅.

It is easy to verify  the contracts are BS (not US), satisfying IRC. The COP   that  . Consider another stable mechanism φ where it produces , y outcome above is x   x, y  at the above problem and coincides with the COP at other problem instances. It is truncation-proof as well as stable.

Appendix Proof of Lemma 1 (i) Let ψ be a mechanism that satisfies weak Maskin monotonicity. Let us consider a problem P, doctor d, and Pd such that Pd|U (P ,ψ (P)) = Pd|

U (Pd ,ψd (P))

d

d

. This implies that Pd is a monotonic transformation of Pd at ψd (P).

Therefore, P  = (Pd , P−d ) is a monotonic transformation of P at ψ(P). By weak Maskin monotonicity, ψd (Pd , P−d )Rd ψd (P). This also implies that Pd is a monotonic transformation of Pd at ψd (Pd , P−d ). Therefore, P is a monotonic transformation of (Pd , P−d ) at ψ(Pd , P−d ). Then, by weak Maskin monotonicity, ψd (P)Rd ψd (Pd , P−d ). These altogether shows that ψd (Pd , P−d ) = ψd (P). Hence, ψ is invariant to lower-tail preference change. 14 Because the hospital’s choice function is generated by its preferences, the contracts automatically satisfy IRC. 15 To see its truncation-proofness, if a doctor truncates his preferences such that the last offer he makes in the COP under the true preference profile is still acceptable, then the outcome would not change. Otherwise, he becomes unassigned in some step. In this case, from the proof of Theorem 1 of Hatfield and Kojima (2010), we know that none of his contract is accepted after that step; thereby, he becomes unassigned at the end of the COP. Hence, the COP is truncation-proof under BS and IRC.

123

540

M. O. Afacan

(ii) Let ψ be a mechanism that is both individually rational for doctors and invariant to lower-tail preference change.16 Assume for a contradiction that it is not truncation-proof. That is, there exist a problem instance P, doctor d, and truncation Pd of Pd such that ψd (P) = x and ψd (Pd , P−d ) = x  with x  Pd x. Due to the individual rationality for doctors property of ψ and the manipulation via  = d and x  P x  P ∅ (it truncation Pd , there exists a contract x  = x  with x D d d  may be that x = x ). Let Pd be the truncation such that x˜ ∈ / Ac(Pd ) if and only if x˜ D = d and x  Pd x. ˜ Then, due to the invariance to lower-tail preference change property of ψ, we have ψd (Pd , P−d ) = x  . This, along with ψd (P) = x, contradicts ψ being invariant to lower-tail preference change.

Proof of Theorem 1 Due to Lemma 1, we only need to show that (i) ⇒ (iv) and (ii) ⇒ (i). Let us first show the former. That is, we want to show that under US and IRC, the COP is stable and satisfies weak Maskin monotonicity. From Hatfield and Kojima (2010) and Aygün and Sönmez (2012), we already know that the COP is stable under US and IRC. For weak Maskin monotonicity, let P  be a monotonic transformation of P at COP(P) = X  . By definition, X  continues to be stable at P  . Let COP(P  ) = X  . From Hatfield and Kojima (2010), we know that the COP produces the doctor-optimal stable allocation under US and IRC. This, along with the stability of X  , implies that X  Rd X  for any doctor d ∈ D. Hence, COP satisfies weak Maskin monotonicity. Let us now show that (ii) ⇒ (i). That is, we want to prove that if a mechanism is stable and truncation-proof, then it is nothing but the COP. Let ψ be a stable and truncation-proof mechanism. Assume for a contradiction that ψ = C O P, and let P be such that ψ(P) = C O P(P). For ease of notation, let ψ(P) = X  and COP(P) = X  . For any allocation X˜ , similar to the doctor side, let X˜ h be the set of hospital h’s contracts at X˜ .   Let S 0 = d ∈ D : X  Pd X  . From Hatfield and Kojima (2010), X  is the doctoroptimal stable allocation. Thus, since X  is also stable, we know that for every doctor X  is at least as good as X  . This, along with X  = X  , implies that S 0 is a non-empty / Ac(Pd1 ) if set. Let d1 ∈ S 0 and consider Pd1 that is the truncation of Pd1 such that x ∈    1 and only if x D = d1 and X d1 Pd1 x. Let P = (Pd1 , P−d1 ). Note that as X d1 Pd1 X d 1 Rd1 ∅ (the latter is due to the stability of X  ), (X d1 ) H = h for some hospital h. From Hatfield and Kojima (2010) and Aygün and Sönmez (2012), under US and IRC, no previously rejected contract is accepted in a later step in the course of the COP. In other words, the COP coincides with the DA. This simply implies that COP(P 1 ) = X  . On the other hand, due to the truncation-proofness and the stability of ψ, we have ψd1 (P 1 ) = ∅.  Let S 1 = d ∈ D : X  Pd ψ(P 1 ) \ {d1 }. We now claim that S 1 is non-empty. As COP(P 1 ) = X  and the COP produces the doctor-optimal stable allocation under US and IRC, we have X  Rd ψ(P 1 ) for any d ∈ D. If S 1 = ∅, then by strictness 16 From Remark 1, we know that invariance to lower-tail preference change alone does not imply truncation-

proofness.

123

Characterizations of the cumulative offer process

541

of the doctor preferences, X d = ψd (P 1 ) for any d ∈ D \ {d1 }.17 From above,

we 1 1 also have ψd1 (P ) = ∅. Let us now consider the set of contracts ψ(P ) ∪ X d1 .

As X d = ψd (P 1 ) for any d ∈ D \ {d1 }, X  = ψ(P 1 ) ∪ X d1 . From the stability 

of X  and X d1 Pd1 ∅, we have X h = C h (ψ(P 1 ) ∪ {X d1 }) ⊆ C D ψ(P 1 ) ∪ X d1 , contradicting the stability of ψ(P 1 ) at P 1 . Therefore, S 1 is non-empty. Let d2 ∈ S 1 and, similar to above, consider Pd2 that is the truncation of Pd2 such that x ∈ / Ac(Pd2 ) if and only if x D = d2 and X d2 Pd2 x. As the same as before, since X  Pd2 ψ(P 1 )Rd2 ∅, we have (X d2 ) H = h for some hospital h. Let us define 1 ). By the same reason as above, COP(P 2 ) = X  and ψ (P 2 ) = ∅. P 2 = (Pd2 , P−d d2 2 Moreover, by the definition of P 2 and the fact that COP is the doctor-optimal stable mechanism, either ψd1 (P 2 ) = ∅ or ψd1 (P 2 ) = X d1 .   Let us now define S 2 = d ∈ D : X  Pd ψ(P 2 ) \ {d1 , d2 }. Similar to above, we claim that S 2 is non-empty. As COP(P 2 ) = X  and it is the doctor-optimal stable allocation, X  Rd ψ(P 2 ) for any d ∈ D. If S 2 = ∅, then X d = ψd (P 2 ) for any d ∈ D \ {d1 , d2 }. From above, we also have ψd2 (P 2 ) = ∅. We have two cases to consider. Let us first consider the case where ψd1 (P 2 ) = X d1 . In this case, similar to above, consider

the set of contracts X  = ψ(P 2 ) ∪ X d2 . Then, from the stability of X  and the 



⊆ C D ψ(P 2 ) ∪ X d2 , fact that X d2 Pd2 ∅, we have X h = C h ψ(P 2 ) ∪ X d2 contradicting the stability of ψ(P 2 ) at P 2 . Let us consider the other case of ψd1 (P 2 ) = ∅. If (X d1 ) H = h, then



X  = ψ(P 2 ) ∪ X d1 ∪ X d2 . Due to the same arguments as above, X h = 







⊆ C D ψ(P 2 ) ∪ X d1 ∪ X d2 , contradicting C h ψ(P 2 ) ∪ X d1 ∪ X d2

the stability of ψ(P 2 ) at P 2 . If (X d1 ) H = h, then let X˜ = ψ(P 2 ) ∪ X d2 . Again by 



the same arguments above, X˜ h = C h ψ(P 2 ) ∪ X d2 ⊆ C D ψ(P 2 ) ∪ X d2 , contradicting the stability of ψ(P 2 ) at P 2 . Hence, S 2 is non-empty. If we keep applying the same arguments above, each iteration would give us a different doctor. This, however, contradicts the finiteness of the doctor set, contradicting our starting supposition that ψ = C O P. This finishes the proof.



17 Note that we cannot invoke the rural hospitals theorem under US and IRC. To see this, consider two doctors, say d1 and d2 , and one hospital h. Let Pd1 : x, x  , ∅; Pd2 : y, ∅, and     P : x  , {x, y} , {x} , x  , y , {y} , ∅. Both US and IRC hold. There are two stable allocations here:  h  x and {x, y}, showing the failure of the rural hospitals theorem.

123

542

M. O. Afacan

References Alcalde J, Barbera S (1994) Top dominance and the possibility of strategy-proof stable solutions to matching problems. Econ Theory 4(3):417–435 Alkan A (2002) A class of multipartner matching markets with a strong lattice structure. Econ Theory 19(4):737–746 Aygün O, Bo I (2014) College Admission with Multidimensional Privileges: The Brazilian Affirmative Action Case, Mimeo Aygün O, Sönmez T (2012) The importance of irrelevance of rejected contracts in matching under weakened substitutes conditions, Mimeo Aygün O, Sönmez T (2013) Matching with contracts: comment. Am Econ Rev 103(5):2050–2051 Aygün O, Turhan B (2014) Dynamic reserves in matching markets with contracts: theory and applications, mimeo Balinski M, Sönmez T (1999) A tale of two mechanisms: student placement. J Econ Theory 84:73–94 Blair C (1988) The lattice structure of the set of stable matchings with multiple partners. Math Oper Res 13(4):619–628 Bogomolnaia A, Heo EJ (2012) Probabilistic assignment of objects: characterizing the serial rule. J Econ Theory 147(5):2072–2082 Echenique F (2012) Contracts vs salaries in matching. Am Econ Rev 102(1):594–601 Ehlers L (2008) Truncation strategies in matching markets. Math Oper Res 33(2):327–335 Ehlers L (2010) Manipulation via capacities revisited. Games Econ Behav 69(2):302–311 Ehlers L, Klaus B (2014) Strategy-proofness makes the difference: deferred-acceptance with responsive priorities. Math Oper Res 39:949–966 Gale D, Shapley LS (1962) College admissions and the stability of marriage. Am Math Mon 69:9–15 Hashimoto T, Hirata D (2011) Characterizations of the probabilistic serial mechanism, mimeo Hashimoto T, Hirata D, Kesten O, Kurino M, Unver MU (2014) Two axiomatic approaches to the probabilistic serial mechanism. Theor Econ 9:253–277 Hatfield JW, Kojima F (2010) Substitutes and stability for matching with contracts. J Econ Theory 145:1704– 1723 Hatfield JW, Kominers SD, Westkamp A (2015) Stability, strategy-proofness, and cumulative offer mechanisms, Mimeo Hatfield JW, Milgrom PR (2005) Matching with contracts. Am Econ Rev 95(4):913–935 Heo EJ, Yilmaz O (2015) A characterization of the extended serial correspondence. J Math Econ 59:102–110 Hirata D, Kasuya Y (2014) Cumulative offer process is order-independent. Econ Lett 124:37–40 Hirata D, Kasuya Y (2015) On stable and strategy-proof rules in matching markets with contracts, Working Paper, SSRN id 654639 Kelso AS, Crawford JVP (1982) Job matching, coalition formation, and gross substitutes. Econometrica 50(6):1483–1504 Kojima F, Manea M (2010) Axioms for deferred acceptance. Econometrica 78(2):633–653 Kominers SD, Sönmez T (2016) Matching with slot-specific priorities: theory. Theor Econ 11:683–710 Maskin E (1999) Nash equilibrium and welfare optimality. Rev Econ Stud 66:23–38 Mongell S, Roth AE (1991) Sorority rush as a two-sided matching mechanism. Am Econ Rev 81(3):441–464 Morrill T (2013) An alternative characterization of the deferred acceptance algorithm. Int J Game Theory 42:19–28 Roth AE, Rothblum UG (1999) Truncation strategies in matching markets-in search of advice for participants. Econometrica 67(1):21–43 Roth AE, Sotomayor MO (1990) Two-sided matching: a study in game-theoretic modeling and analysis. Econometric Society Monographs. Cambridge Univ. Press, Cambridge Sönmez T (2013) Bidding for army career specialties: improving the ROTC branching mechanism. J Political Econ 121(1):186–219 Sönmez T, Switzer TB (2013) Matching with (branch-of-choice) contracts at the United States Military Academy. Econometrica 81(2):451–488

123