Equivalent Choice Functions and Stable Mechanisms
Jan Christoph Schlegel

	
	A Multi-Stream Convolutional Neural Network Framework  for Group Activity Recognition
    Sina Mokhtarzadeh Azar     Mina Ghadimi Atigh     Ahmad Nickabadi

Statistical Machine Learning Lab, Amirkabir University of Technology

424 Hafez Ave, Tehran, Iran

{sinamokhtarzadeh,minaghadimi,nickabadi}@aut.ac.ir






    December 30, 2023
==================================================================================================================================================================================================================================


		We study conditions for the existence of stable and
		(group)-strategy-proof mechanisms in a many-to-one matching model with
		contracts if students' preferences are monotone in contract terms.
		We show that “equivalence", properly defined, to a choice profile
		under which contracts are substitutes and the law of aggregate demand holds
		is a necessary and sufficient condition for the existence of a
		stable and (group)-strategy-proof mechanism.
		
		Our result can be interpreted as a (weak) embedding result for
		choice functions under which contracts are observable substitutes
		and the observable law of aggregate demand holds.
		JEL-classification: C78, D47

		Keywords: Matching with contracts; College admission; Substitutes; Observable Substitutes; Strategy-Proofness; Deferred Acceptance
	
	

§ INTRODUCTION

	Centralized clearing houses based on the deferred-acceptance
	mechanism are at the heart of many successful matching
	markets <cit.>.
	Deferred-acceptance mechanisms are appealing because they produce
	stable outcomes, meaning that no subgroup of agents can find a
	mutually beneficial deviation and, thus, would have a reason to
	contract outside the market.[<cit.> provides
		evidence that clearing houses using unstable mechanisms tend to fail
		in practice.] Moreover, it is safe for the applying side of the
	market to report true preferences to the mechanism. Thus, the
	mechanism successfully aggregates the information in the market and
	levels the playing field for both naive and sophisticated participants.
	
	In some applications, the market does not only match agents, but
	determines also the contractual details of the match. In a labor
	market, firms and workers may have some discretion on how to set the
	salary.  In a
	college admission problem, students can be admitted with or without
	a stipend. In the cadet-to-branch match <cit.>,
	cadets can choose between different lengths of service time in
	exchange for a higher priority in their branch of choice. These markets can be understood as hybrids between
	matching markets and auctions and have first been analyzed in the
	seminal paper of <cit.>, with later important
	extensions
	by <cit.>
	among others. The central mechanism design result in this context states that in a model of many-to-one matching with
	endogenous contracting, a generalized version of the deferred-acceptance mechanism can be defined, and is stable and
	group-strategy-proof under the assumption that contracts are
	substitutes for colleges[In the following we call the
		applying side of the market “students" and the admitting side of
		the market “colleges" motivated by the application of college
		admission. However, the model equally applies to the other
		applications mentioned in this introduction.] and the law of
	aggregate demand holds.[This means
		that if we expend the choice set of a college, an equal or larger number of contracts is chosen.] Moreover, the deferred acceptance algorithm is outcome equivalent to the cumulative offer algorithm which is a natural modification of the deferred acceptance algorithm. In the cumulative offer algorithm not only acceptances, but also rejections are deferred; in each round of the algorithm, colleges are allowed to choose among all applications they have received so far including those that they have previously rejected.

	
	In this paper, we study stable and (group)-strategy-proof mechanisms for matching markets with contracts in which students have monotone preferences in contract-terms,[Colleges' preferences are not necessarily
		monotone in our analysis.] and explore how much the assumptions of substitutability and the law of aggregate demand can be relaxed in this context.  Our research question is motivated by the observation that in many applications, there is a natural ordering over contracts terms, and it is reasonable to assume that preferences are monotone with respect to the ordering:  In college admission problems with
	stipends <cit.>, it is natural to assume that students prefer being admitted with a
	stipend to being admitted without a stipend at the same college, or
	more generally, being admitted with a higher stipend than a lower
	stipend at the same college.[There is empirical evidence
		that monotonicity is violated for reported preferences of some
		participants in the Israeli psychology match, see . But it seems
		likely that these monotonicity violations can be attributed to students failing to play the
		weakly dominant strategy of revealing preferences truthfully, rather
		than to them having non-monotone preferences.] In the
	cadet-to-branch matching model of <cit.> the
	contract-term is the service time in the military and it is natural
	to assume that cadets prefer a
	shorter to a longer service in the same branch. This assumption is for example made in the analysis
	of <cit.>.
	For the medical match, mechanisms which allow for flexible salaries
	have been proposed <cit.>, and it seems reasonable
	that doctors in these mechanisms would prefer working for a higher
	salary rather than a lower salary at the same hospital.
	
	We study conditions on choice functions of colleges under which a stable and (group)-strategy-proof matching mechanism exists for our model. Since we work with monotone preferences for students, sufficient conditions on choice functions of colleges are generally weaker. This is because
	certain preference manipulations are ruled out by our model. A
	student must report monotone preferences. Thus, a student cannot, e.g.,
	rank being admitted to a college without a stipend above being
	admitted to the same college with a stipend.[Similarly, weaker
		conditions are sufficient to guarantee the existence of stable
		allocations than those for markets with non-monotone
		preferences. To illustrate this point, consider a college
		admission problem of the following kind: There are two colleges
		c_1,c_2 and three students s_1,s_2,s_3. Suppose there are two
		kinds of contracts: A student can be admitted with stipend
		(represented by the contract term "1") or without stipend
		(represented by the contract term "0"). The colleges have choice
		functions induced (in the usual way) by the following preferences
		
    {(s_1,0),(s_2,0),(s_3,0)}≻_c_1{(s_2,0)}≻_c_1{(s_2,1)}≻_c_1∅≻_c_1…
    {(s_1,0)}≻_c_2{(s_3,0)}≻_c_2∅≻_c_2…

		Suppose student always prefer to be admitted at a college under a
		stipend to being admitted at the same college without a stipend.
		Going through all different cases, one can show that, for any
		preferences satisfying this monotonicity assumption, a stable
		allocation (in the matching with contracts sense) exists. This
		changes if students can report non-monotonic preferences. Consider
		the following preferences:
		
    (c_1,1)≻_s_1(c_2,1) ≻_s_1(c_1,0)≻_s_1(c_2,0)≻_s_1∅
    
    		(c_1,0)≻_s_2(c_1,1)≻_s_2∅≻_s_2…
    
    		(c_2,1)≻_s_3(c_1,1)≻_s_3(c_2,0)≻_s_3(c_1,0)≻_s_3∅

		Student s_2 prefers to go to college c_1 without a stipend
		rather than a stipend. Thus, in a stable allocation it will never be
		the case that s_2 goes to college c_1 with a stipend, because
		otherwise c_1 and s_2 could block that allocation. This in turn
		implies that no stable allocation exists: The allocation that
		matches all three students to c_1 without stipend is blocked by
		student s_3 and college c_2. Any allocation that matches s_1
		to c_2 without stipend is blocked by students s_1,s_2 and s_3
		being admitted to college c_1 without stipend. Any allocation that
		matches s_3 to c_2 without stipend is blocked by student s_1
		being admitted to college c_2 without a stipend. Finally, all
		other allocations are either not individually rational or blocked by
		students s_1,s_2 and s_3 being admitted to college c_1 without
		a stipend.] Our main result is a characterization of a sufficient and necessary (in the maximal domain sense) condition for the existence of a stable and (group)-strategy-proof mechanism in terms of “equivalence" of choice functions: Two choice functions are equivalent if the cumulative offer algorithm yields the same outcome under either choice function, for any preferences and choice functions for the other agents. If for each college an equivalent choice function exists under which contracts are substitutes and the law of aggregate demand holds, then the mechanism that assigns to each profile of preferences the outcome of the cumulative offer algorithm, or equivalently the outcome of the deferred acceptance algorithm, is group-strategy-proof, both under the equivalent choice profile and, by definition of equivalence, under the original choice profile.
	
	
	We proceed as follows: First we show (Theorems <ref> and <ref>) that an equivalent choice function under which contracts are substitutes and the law of aggregate demand holds exists, if and only if under the original choice function contracts are observable substitutes (in the sense of ) and the observable law of aggregate demand holds.[Importantly, observability is meant with respect to offer sequences consistent with monotone preferences for students. Thus, the notions of observable substitutability and the observable law of aggregate demand are weaker than the corresponding notions for the general model with possibly non-monotone preferences.]  The result crucially relies on our monotonicity assumption on preferences: In independent work, <cit.> has considered the corresponding notion of equivalence between choice functions for the general preference domain. He shows that equivalence in that context implies unilateral substitutability which is a much more stringent restriction than observable substitutability. Even if the notion of equivalence is relaxed, by allowing, as in the construction of substitutable completions <cit.>, for non-feasible equivalent choice functions, the corresponding result does not hold on the general preference domain <cit.>.
	
	Our proof is constructive, by providing a natural construction of an equivalent choice function that we call a "virtual choice function", and by showing that the virtual choice function satisfies substitutability and the law of aggregate demand if and only if the original choice function satisfies observable substitutes and the observable law of aggregate demand. Importantly, the constructed virtual choice function is monotone in contract terms, even if the original choice function is non-monotone in contract terms.
	
	Theorems <ref> and <ref> have several important consequences that are subsequently spelled out: First, Theorem <ref> implies (Corollory <ref>) that the deferred acceptance mechanisms is group-strategy-proof if contracts are observable substitutes and the observable law of aggregate demand holds. Second, combining the theorems with a result of <cit.>, we obtain a maximal domain result (Corollary <ref>): 
	The domain of choice profiles that are equivalent to a choice profile under which contracts are substitutes for colleges and the law of aggregate demand holds, form a
	maximal Cartesian and unital[A domain of choice profiles is unital if it contains all profile in which each college has a unit demand choice function, i.e. it chooses at most one contract from each set.] domain for the existence of a stable
	and (group)-strategy-proof mechanism. Equivalently this domain is the domain of profiles under which contracts are observable substitutes and the observable law of aggregate demand holds. Our results are stronger than the result obtained by <cit.> for monotone preferences: For monotone
	preferences,  strategy-proofness of the deferred acceptance mechanism can be strengthened to group-strategy-proofness, and the axiom of “non-manipulability via contractual terms" in the characterization of the maximal domain becomes redundant.
	 Furthermore, the notion of equivalence yields an easier and more interpretable condition on choice functions: In particular, group-strategy-proof of the deferred acceptance mechanism on the maximal domain now follows immediately from well-known previous results due to <cit.> and <cit.> applied to the equivalent choice profile. Third, since an equivalent choice profile can be constructed and the equivalent choice profile is monotone in contract terms (Theorem <ref>), we obtain an
	embedding result (Corollary <ref>) in the sense of <cit.> for the class
	of choice functions under which contracts are observable substitutes
	and the observable law of aggregate demand holds. Thus, if attention
	is restricted to the case of monotone preferences for students, it
	is, in some sense without loss of generality to work with the model
	of matching with salaries of <cit.> rather than
	the full matching with contracts model.

	

 §.§ Related Literature

	Stable many-to-one matching mechanisms and their incentive
	properties have been extensively
	studied <cit.>. Most papers focus
	on the pure matching model or on the matching with contracts
	model. Working
	with monotone preferences makes our model less general than the full
	matching with contracts model. In particular, sufficient
	conditions for stability and the existence of a stable and
	(group)-strategy-proof mechanism from the literature on matching
	with contracts also apply to our model. However, conditions that are
	necessary for the general model with contracts are not necessary
	conditions for the model with monotone preferences. Thus, our results
	are independent of previous results for the matching with
	contracts model. 
	
	In recent related work, <cit.> consider a model of college admissions with stipends where
	complementarities in  contract terms are present for colleges: In
	their model three contract terms {t_+,t_0,t_-} are available,
	interpreted as admission with stipend, admission without stipend but
	with tuition waiver, and admission without either of the two, and
	the number of t_--contracts signed by a college constraints the
	number of t_+-contracts it signs. Importantly, students have
	monotone preferences in these contract terms. The model is a special
	case of ours. In particular, the result for “Max-Min Responsive"
	preferences can be obtained as a special case of ours and for this
	case, their strategy-proofness result can be strengthened to
	group-strategy-proofness. However, <cit.> also
	analyze pairwise-stable outcomes and this part of their analysis
	does not have a counter-part in our paper. 
	
	Our original working paper <cit.> contained a version
	of our maximal domain result for a model of matching with contracts
	where also colleges' choice functions are monotone in
	contract-terms. Technically the two maximal domain results are
	independent. However, the adaption to obtain the previous version of
	the theorem from the current one are minimal.[One has to
		make sure that in the “necessity part" of the maximal domain proof,
		the profile of unit demand choice functions for the other colleges can
		be chosen to be induced by monotone preferences.] The current version of the maximal domain result can also be obtained with a similar proof as the one in the previous version.  For the original version of the theorem, we refer
	the interested reader to the original version of the working paper.
	
	After, our original working paper <cit.>,
	<cit.> released a new version of their paper,
	where the authors extend their analysis to the case of restricted preference domains for the applicant side and show that their analysis of observable substitutes
	and the observable law of aggregate demand extends to restricted
	preference domains if the notion of “observability" is adjusted to the domain restriction. Their additional
	work allows us to shorten the proof of our maximal domain result, since we can now make use of their Theorem 5. As remarked previously, our results in the current paper for
	monotone preferences strengthen the results
	in <cit.> by strengthening strategy-proofness to group-strategy-proofness.
	

§ MODEL AND KNOWN RESULTS

	

 §.§ Model

	There are two finite disjoint sets of agents, a set of colleges
	C and a set of students S. There is a finite set of
	possible contract-terms T which are totally ordered by ⊳. Contract terms could, for example, be different amounts of stipends that a college can pay a student, ordered from high to low stipends; in a labor market, contract terms could be different possible wages ordered from high to low, or working hours from short to long, etc.[More generally, we can deal with the case where the ordering is college-student pair specific, i.e. for each college c∈ C and student s∈ S there is a total ordering ⊳_c,s over contract terms. If "Pareto separability" <cit.> of contracts holds, the set T can be interpreted as the set of "generalized salaries" in the sense of <cit.> and ⊳_c,s is derived from a parameterization of the efficient contract frontier. Thus, also in this case, our results apply.] Colleges can accept students under
	different bilateral contracts. The set of possible contracts
	is X⊆ C× S×  T. For a contract x∈  X, we
	denote by x_C∈ C the college involved in x, by x_S∈ S the
	student involved in X, and by x_ T∈  T the contract term
	involved in x. We write x_ T x_ T' whenever x_ T⊳ x_ T' or x=x'.
	For Y⊆ X and college c∈ C we denote by Y_c={x∈ Y: x_C=c} the set of contracts in Y involving c, and similarly for a student s∈ S we denote by Y_s:={x∈ Y:y_S=s} the set of contracts in Y involving s.
	
	Each college c has a choice function
	Ch_c:2^ X_c→ 2^ X_c that from each set  Y⊆
	X_c chooses a subset of contracts. Each college can only sign one
	contract with any given student, i.e. for each x,y∈ Ch_c(Y) with
	x≠ y we have x_S≠ y_S. Throughout this paper, we assume that all considered choice functions satisfy the irrelevance of rejected contracts (IRC) <cit.>, which means that for all Y⊆  X_c, x∈  X_c∖ Y, 
    x∉
    	Ch_c(Y∪{x})⇒ Ch_c(Y)=Ch_c(Y∪{x}).
 We also define
	a rejection function R_c:2^ X_c→2^ X_c by
	R_c(Y):=Y∖ Ch_c(Y). We denote the set of all choice functions for college c∈ C that satisfy IRC, by 𝒞_c.
	
	
	
	
	Each student s has preferences
	≽_s over different contracts involving him, and an outside
	option which we denote by “∅". We make the following
	assumption on students' preferences:
	
		
  * Preferences are strict, for x,x'∈  X with x'_S=x_S, we have 
    x≠ x'⇒ x≻_x_Sx' or x'≻_x_Sx,
 and 
    x≻_x_S∅  or  ∅≻_x_Sx.

		
		
  2. Preferences are monotone in contract terms, for each x,x'∈  X with x_S=x'_S and x_C=x_C' we have
		
    x_ T⊳ x'_ T⇒ x≻_x_Sx'.

	
	We denote the set of all strict and monotone preferences for student s∈ S by ℛ_s.
	A problem is a pair
	(Ch,≽) consisting of a choice profile Ch=(Ch_c)_c∈
		C∈_c∈ C𝒞_c and a preference profile ≽=(≽_s)_s∈ S∈_s∈ Sℛ_s.
	
	
	An allocation is a set Y⊆  X that contains at most
	one contract per student. We denote the set of allocations by
	𝒜. For Y∈𝒜, we write Y_S:={y_S:y∈ Y}. An allocation Y is
	
		
   individually rational in (Ch,≽) if for each c∈ C, we have Y_c= Ch_c(Y), and for each y∈ Y we have y≻_y_ S∅,
		
   blocked in (Ch,≽) if there are c∈ C and an allocation Z with Z_c≠ Y_c, such that Z_c= Ch_c(Y∪ Z) and for each z∈ Z_c we have z≽_z_SY_z_S,
		
   stable in (Ch,≽) if it is individually rational and not blocked.
	
 In the following, it will be useful to define for each
	set of contracts Y⊆  X_c with a college c the allocation
	
    Y^min:={y∈ Y:∄ y'∈ Y, y_S'=y_S,y_
    	T⊳ y'_ T}
 of contracts that gives each student
	the worst contract among the contract in Y, and the set
	
    𝒰(Y):={x∈  X_c:x_ T y_ T for
    		some y∈ Y with x_S=y_S}
 of contracts,
	not necessarily in Y, which are as least as good for the involved student as his worst contract in Y.[Note that the definitions of Y^min and 𝒰(Y) only depend on ⊳.] 
	We call choice function 
	Ch_c for college c∈ C monotone in contract-terms if for each Y⊆
	X_c we have
	
    Ch_c(Y)⊆ Y^min.

	
	

 §.§ Mechanisms

	A mechanism (for the students) is a mapping from preference
	profiles to allocations
	ℳ:_s∈ Sℛ_s→𝒜. Mechanism
	ℳ is strategy-proof if it is a weakly dominant
	strategy for students to report their true preferences to the
	mechanism, i.e. for each s∈ S,
	≽_-s∈_s'∈ S∖{s}ℛ_s' and
	≽_s,≽'_s∈ℛ_s we have
	
    ℳ(≽_s,≽_-s)≽_sℳ(≽'_s,≽_-s).

	Mechanism ℳ is group-strategy-proof if for each
	S'⊆ S, ≽_-S'∈_s∈ S∖𝒮'ℛ_s and
	≽_S',≽'_S'∈_s∈ S'ℛ_s, there is a s'∈
	S' with
	
    ℳ(≽_S',≽_-S')≽_s'ℳ(≽'_S',≽_-S').

	Let Ch be a choice profile. Mechanism ℳ is Ch-stable if for each ≽∈_s∈ Sℛ_s allocation
	ℳ(≽) is stable in (Ch,≽).
	

 §.§ Examples

	Several examples from applied marked design fit into our model, such as the model of cadet-to-branch matching of <cit.> with the preference restriction of <cit.>, the discrete version of the job matching model of <cit.>, the college admission models of <cit.> and of <cit.>.  The job matching model of <cit.> will play an important role in Section <ref>. 
	

  §.§.§ Job matching with salaries

	A finite Kelso-Crawford economy consists of a finite set of
	firms F, a finite set of workers W, a finite set of salaries
	Σ⊆ℝ_+ and a profile u_i∈ F∪ W
	of utility functions, where for each f∈ F, utility is a functions
	u_f:{(W',p):W'⊆ W,p∈ℝ^W'_+}→ℝ that is strictly decreasing in ℝ_+^W' for each W', and for each
	w∈ W, utility is a function u_w:F×ℝ_+∪{∅}→ℝ that is strictly increasing in ℝ_+ for each f.
	
	The model fits in our framework with C=F, S=W, T=Σ,
	x_T⊳ x_T'⇔ x_T>x_T', X=F×
	W×Σ, choice functions are defined by
	
    Ch_c(Y)=max_Y'⊆ Y^min u_c(Y'_S,(y_T)_y∈ Y'),

	and preferences (≽_s)_s∈ S are induced by utility
	functions, 
    (c,s,t)≻_s(c',s,t')⇔ u_s(c,t)>u_s(c',t'),   (c,s,t)≻_s∅⇔ u_s(c,t)>u_s(∅).

	Note that the constructed market with contracts (Ch,≽) does
	not only satisfy monotonicity of students' preferences, but also
	monotonicity of colleges' choice function.
	We say that workers are gross substitutes for firm f if for each p,p'∈Σ^W such that p≤ p', if p_w'=p_w and w∈argmax_W'⊆ Wu_f(W',p), then w∈argmax_W'⊆ Wu_f(W',p').
	
	

	

 §.§ Stable Allocations

	In general, a stable allocation does not need to exist for our
	model. A sufficient condition for stability is that contracts are
	substitutes for colleges, i.e. if a contract is rejected from some set
	of contracts, then this contract is also rejected from each superset of
	that set of contracts.
	Substitutability
	<cit.>: For each Z⊆ Y⊆  X_c, 
    R_c(Z)⊆ R_c(Y).

	
	Not only is substitutability sufficient for the existence of a
	stable allocation but it also guarantees that the set of stable
	allocations has a lattice structure. If contracts are substitutes
	for colleges, then the set of stable allocation forms a lattice with
	respect to the preferences of students <cit.>. In
	particular, there is a unique stable allocation that is most
	preferred by all students among all stable allocations. We call this
	allocation the student-optimal stable allocation.  It can be
	found by the cumulative offer (CO) algorithm that is
	defined as follows.
	
		
  * Each student applies under his favorite acceptable and unrejected contract or stays alone if he finds no unrejected contract acceptable.
		
  * Each college tentatively accepts the contracts it chooses among the applications it has received so far and rejects all other contracts.
		
  * If no application has been rejected in the current round, the algorithm stops. If some applications are rejected we repeat.
	
	We denote the set of contracts chosen by the colleges in the final round of the CO algorithm for problem (Ch,≽) by 𝒞𝒪(Ch,≽). Alternatively, we can use the deferred acceptance algorithm to find the student optimal stable allocation. In the deferred acceptance (DA) algorithm rejections are permanent: Thus, in 2., colleges only choose among contracts that are proposed in the current round of the algorithm, but not contracts that have been proposed and rejected in a previous round. If contracts are substitutes for colleges, then the deferred acceptance and the cumulative offer algorithm yield the same outcome. The deferred acceptance mechanism for Ch assigns to each ≽∈_s∈ Sℛ_s the outcome of the deferred acceptance algorithm in (Ch,≽).[We use the deferred acceptance algorithm and not the cumulative offer algorithm to define a mechanism, because it yields a well-defined mechanism even in situations where contracts are not substitutes for colleges. The deferred acceptance algorithm always ends in a (potentially unstable) allocation where each student is accepted at at most one college, whereas the cumulative offer algorithm can yield an outcome where multiple colleges accept a student.]
	
	
	Student-optimality is related to group-strategy-proofness. Under
	substitutability and the following additional condition on the
	colleges' choice functions the deferred acceptance mechanism is
	group-strategy-proof.
	Law of Aggregate Demand <cit.>:  For each Z⊆ Y⊆  X_c: 
    Z⊆ Y⇒ |Ch_c(Y)|≥|Ch_c(Z)|.

	
	The following proposition summarizes known results about
	side-optimal stable allocations, the invariance of the set of
	matched students in stable allocations (the rural hospitals
	theorem), and group-strategy-proofness of the deferred acceptance mechanism.
	
		
			
  * If contracts are substitutes for colleges, then the deferred acceptance and the cumulative offer algorithm are equivalent and converge to a stable allocation that is most preferred by all students among all stable allocations.
			
  * If choice functions satisfy, moreover, the law of aggregate demand, then 
				
  * the set of accepted students is the same in all stable allocations and each college accepts the same number of students in each stable allocation,
				
  * the deferred acceptance mechanism is group-strategy-proof.
			
		
	
	

§ RESULTS

	

 §.§ Equivalent Choice Functions

	It is a natural question whether the conditions of
	Section <ref> for the stability and group-strategy-proofness
	of the deferred acceptance mechanism are also necessary. Next we
	provide a counterexample that shows that substitutability and the law
	of aggregate demand are not necessary for the deferred-acceptance
	mechanism to be stable and group-strategy-proof. The example will have the following structure: There is one college c
	for which contracts are not substitutes. For each college except for
	c, contracts are substitutes and the law of aggregate demand
	holds. However, c's choice function can be replaced by another
	choice function, such that 
		
  * under the replacing choice function, contracts are
		substitutes for c and the law of aggregate demand
		holds,
		
  * the outcome of
		the cumulative offer algorithm (which here coincides with the outcome of the deferred acceptance algorithm) is, for all monotone preference profiles for students, the same under the original
		choice profile and the profile where c's choice function is
		replaced. As the deferred acceptance mechanism is group-strategy-proof for the profile
	where we have replaced c's choice function by the other choice
	function, it is by outcome-equivalence also group-strategy-proof for the original choice profile.
	
		The original choice function is from Example 2 in <cit.>. Consider a college admission problem with stipends where T={0,1}, with the interpretation that contract term "0" corresponds to admission without stipend, and contract term "1" corresponds to admission with a stipend. Thus, 1⊳0. For simplicity, we assume that there are two students S={s_1,s_2}. The example can be generalized to more students.
		Consider a college c_1 which can admit up to two students but only has one stipend available. Students are admitted based on merit, and student s_1 is the higher merit student than s_2. If both students are available, the college prefers to allocate the stipend to student s_2 rather than s_1, e.g. because s_2 comes from a lower income background. The choice function of the college Ch_c_1 is induced by preferences 
		
    {(c_1,s_1,0),(c_1,s_2,0)}≻_c_1{(c_1,s_1,0),(c_1,s_2,1)}≻_c_1{(c_1,s_1,1),(c_1,s_2,0)}
    ≻_c_1{(c_1,s_1,0)}≻_c_1{(c_1,s_1,1)}≻_c_1{(c_	,s_2,0)}≻_c_1{(c_1,s_2,1)}

		in the usual way. 
		Now consider the alternative choice function Ch_c_1' induced by preferences:
		
    {(c_1,s_1,0),(c_1,s_2,0)}≻_c_1'{(c_1,s_1,1),(c_1,s_2,0)}≻_c_1'{(c_1,s_1,0)}
    ≻'_c_1{(c_1,s_1,1)}≻_c_1'{(c_1,s_2,0)}≻_c_1'{(c_1,s_2,1)}

		Thus, the preferences differ only in so far as allocation {(c_1,s_1,0),(c_1,s_2,1)} where s_1 is admitted without stipend and s_2 is admitted with stipend is unacceptable under ≽_c_1'. The ranking of all other allocations is the same under both preferences.
		
		Note that under Ch_c_1 contracts are not substitutes as  
    (c_1,s_2,1)∈
    		Ch_c_1({(c_1,s_1,0),(c_1,s_1,1),(c_1,s_2,1)})={(c_1,s_1,0),(c_1,s_2,1)}
 but 
    (c_1,s_2,1)∉ Ch_c_1({(c_1,s_1,1),(c_1,s_2,1)})={(c_1,s_1,1)},
 and that
		under Ch_c_1' contracts are substitutes and the law of aggregate demand holds.
		
		Suppose colleges C∖{c_1} have choice functions
		Ch_-c_1=(Ch_c)_c≠ c_1 under which contracts are substitutes
		and the law of aggregate demand holds. Define Ch:=(Ch_c_1,Ch_-c_1) and
		Ch':=(Ch_c_1',Ch_-c_1). Let ≽∈_s∈ Sℛ_s. We show that the cumulative offer
		algorithm  converges to the
		same allocation for the problems (Ch,≽) and  (Ch',≽). Observe that for all sets Y⊆ X with 
		Ch_c_1 (Y)≠ Ch_c_1'(Y) we have {(c_1,s_1,0),(c_1,s_2,1)}⊆ Y. In
		particular, for the cumulative offer algorithm to differ for the
		two problems, student s_1 must apply to c_1 for admission without stipend
		during the cumulative offer algorithm in (Ch,≽). Note
		however that before s_1 applies to c_1 for admission without stipend, he
		applies to c_1 for admission with stipend, as 1⊳0.
		But once college c_1 tentatively accepts s_1 with a stipend,
		the college will not subsequently drop student s_1, as s_1 has higher merit than s_2. Thus, s_1 will never apply to c_1 for admission without a stipend during the cumulative offer algorithm. Hence, the cumulative offer algorithm for the two problems converges to the same allocation, which
		is the student-optimal stable allocation in (Ch',≽).
		
		Note, moreover, that the equivalent choice function Ch'_c prioritizes merit over need in the following sense: From each set of contracts, an allocation is chosen, where the stipend is either un-allocated or allocated to the higher merit student s_1; whereas under choice function, Ch_c the stipend would be allocated to student s_2, if both students are available and it is possible to admit student s_1 without a stipend.
		
	The example motivates the following definition.[A similar
		notion has been introduced independently by <cit.>.
		However, since <cit.> does not assume monotonicity on
		students' preferences, his notion of equivalence is much stronger.
		See our Remark 1.]
	CO-equivalence:
	Two choice profiles Ch and Ch' are
	CO-equivalent if for each  ≽∈_s∈ Sℛ_s we have 𝒞𝒪(Ch,≽)=𝒞𝒪(Ch',≽).
	Two choice functions Ch_c and Ch_c' are CO-equivalent if for each Ch_-c∈_c'∈ C∖{c}𝒞_c' profiles Ch and Ch':=(Ch'_c,Ch_-c) are CO-equivalent.
	In the following, we use the term "equivalent" instead of "CO-equivalent", since we only consider one notion of equivalence throughout the paper. 
	From the definition and Proposition <ref>, we obtain the following result:
	
		If Ch is equivalent to a profile under which contracts are
		substitutes and the law of aggregate demand holds, then the deferred
		acceptance mechanism for Ch is Ch-stable and group-strategy-proof.
	
	
		Let Ch' be the equivalent profile. Let ≽∈_s∈ Sℛ_s.
		Let Y_1⊆ Y_2⊆…⊆ Y_τ be the set of accumulated offers during the cumulative offer algorithm for (Ch',≽) and Z_1,Z_2,…, Z_τ be the set of proposed contracts during the deferred acceptance algorithm for (Ch',≽). Since contracts under Ch' are substitutes, Part (1) of  Proposition <ref> implies Ch'_c(Y_t)=Ch'_c(Z_t) for t=1,…,τ and each c∈ C. Since Ch and Ch' are equivalent we have Ch_c(Y_t)=Ch'_c(Y_t) for t=1,…,τ and each c∈ C. Thus, Ch_c(Y_t)=Ch'_c(Y_t)=Ch'_c(Z_t)⊆ Z_t for t=1,…,τ and each c∈ C. By IRC for Ch this implies Ch_c(Z_t)=Ch_c(Y_t)=Ch'_c(Z_t) for t=1,…,τ and each c∈ C, and the deferred acceptance algorithm in (Ch,≽) and in (Ch',≽) yield the same outcome. In particular, this implies the stability in (Ch,≽) of the outcome ⋃_c∈ CCh_c(Z_τ) of the deferred acceptance algorithm, since otherwise, if college c∈ C blocks, we would have Ch_c(Y_τ)⊈ Z_τ. Moreover, if under Ch' contracts are substitutes and the law of aggregate demand holds, this implies by Part 2(b) of Proposition <ref> the group-strategy-proofness of the deferred acceptance mechanism for Ch.
	
	As our first main result, we show that for each choice function under which contracts are observable substitutes and the observable law of aggregate demand holds
	we can construct an equivalent choice function under which contracts are substitutes and the law of aggregate demand holds. As an immediate corollary, we will obtain the group-strategy-proofness of the deferred acceptance mechanism under observable substitutes and the observable law of aggregate demand.
	Importantly, we define observable substitutability and the observable law of aggregate demand for monotone preferences by only requiring that the properties hold for observable sequences that can occur under monotone preferences:
	In the following, a sequence of contracts x^1,x^2,…,x^τ is generated
		from monotone preferences if for 1≤ t≤τ and each x∈  X with x_S=x_S^t and
	x_ T⊳ x_ T^t, we have x∈{x^1,…,x^t-1}. A
	sequence x^1,x^2,…,x^τ is observable under Ch_c if for 1≤ t≤τ-1 we have x^t+1_S∉ [Ch_c{x^1,…,x^t}]_S. We call a set of contracts Y⊆  X_c observable under Ch_c, if there is a sequence of contracts
	x^1,…,x^|Y| that is observable under Ch_c and that is generated
	from monotone preferences such that Y={x^1,…,x^|Y|}. We denote the set of all observable sets of contracts under Ch_c by 𝒪(Ch_c). Observable substitutability for monotone preferences is defined as follows:[Alternatively, we could also define observable substitutabilty for monotone preferences, by requiring that the substitutes condition holds for observable sets, i.e. by requiring that for Y,Z∈𝒪(Ch_c) and Z⊆ Y we have R_c(Z)⊆ R_c(Y). See the first part of Lemma <ref> in the appendix. Note that this definition is only equivalent for the case of monotone preferences, but is stronger on the general preference domain.]
	Observable Substitutability (for Monotone Preferences) <cit.>:
	Contracts are observably substitutes
		for monotone preferences under choice function Ch_c if for each observable sequence
	x^1,x^2,…,x^τ under Ch_c that is generated from
	monotone preferences, we have
	
    R_c{x^1,… x^t}⊆ R_c{x^1,…,x^t+1} for each 1≤ t<τ.

	Similarly, we can define an observable version of the law of aggregate demand.
	Observable Law of
		Aggregate Demand (for Monotone Preferences) <cit.>:
	A choice function Ch_c satisfies the observable law of
		aggregate demand for monotone preferences if for each observable
	sequence under Ch_c that is generated from monotone preferences, we
	have
	
    |Ch_c{x^1,… x^t}|≤|Ch_c{x^1,…,x^t+1}| for each 1≤ t<τ.

	
	Since we exclusively deal with monotone preferences, from now one we
	drop the term "for monotone preferences." However, the reader should be aware that the conditions are weaker than the corresponding conditions for general preferences.[In the example in Footnote 6, for example, college c_1's choice function satisfies the monotone versions of the two conditions but not the general preference versions.] With the definition, we have the following result.	
	
		For each choice function Ch_c under which contracts are observable substitutes and the observable law of aggregate demand holds, there exists an equivalent  choice function Ch'_c that is monotone in contract terms such that contracts are substitutes and the law of aggregate demand holds.
	
	To prove the result, we define for each choice function Ch_c a related choice function Ch'_c that we call the
	virtual choice function for Ch_c by 
    Ch'_c(Y):=Y^min∖⋃_Ỹ⊆𝒰(Y),Ỹ∈𝒪(Ch_c)R_c(Ỹ).

	The construction has the following intuition: The set of accumulated offers during an instance of the cumulative offer algorithm is observable. Hence a sufficient condition for equivalence between two choice functions Ch_c and Ch_c' is that Ch_c(Y)=Ch'_c(Y) and therefore R_c(Y)=R_c'(Y) for each Y∈𝒪(Ch_c).  If contracts are substitutes under Ch'_c, then, in particular, contracts that are rejected from an observable (under Ch_c) set are also rejected from each, potentially unobservable, superset of that set. Hence assuming that choices agree on observable sets and contracts are substitutes under Ch_c' for each Y⊆ X_c we have  ⋃_Ỹ⊆ Y,Ỹ∈𝒪(Ch_c) R_c(Ỹ)=⋃_Ỹ⊆ Y,Ỹ∈𝒪(Ch_c) R'_c(Ỹ)⊆ R'_c(Y). Thus, 
    Ch'_c(Y)⊆ Y∖⋃_Ỹ⊆ Y,Ỹ∈𝒪(Ch_c)R_c(Ỹ).
 To guarantee feasibility, Ch'_c(Y) generally has to be a strict subset in the previous expression. Choosing only contracts in Y^min guarantees feasibility and monotonicity of the choice function Ch_c'.
	To guarantee the IRC condition for Ch'_c on sets with Y≠𝒰(Y) we need in general to consider observable subsets of 𝒰(Y) rather than Y. The full proof of the theorem is in the appendix.
	
		A corresponding result to Theorem <ref> does not hold for the case of non-monotonic preferences.
		Without monotonicity, equivalence requires that choices coincide
		on all sets of contracts which contain at most one contract per
		student (see Theorem 1 of ), and equivalence to a choice function under which contracts are substitutes and the law of aggregate demand holds implies unilateral substitutability and the law of aggregate demand. These properties are much stronger than observable substitutability and the observable law of aggregate demand.

	One can show that, for the job matching model with salaries, if the choice function in Theorem <ref> is generated from maximizing preferences that are quasi-linear in salaries, then the choice function and the equivalent virtual choice function are the same. Combining this observation with the maximal domain results of <cit.>, one can show that for quasi-linear preferences, choice profiles under which contracts are substitutes form a maximal domain of choice profiles generated from quasi-linear preferences for the existence of a stable (and strategy-proof) mechanism. This yields an alternative way of proving a result due to .
	Immediately from Theorem <ref> and Proposition <ref> it follows that the deferred acceptance mechanism is stable and group-strategy-proof if contracts are observable substitutes and the observable law of aggregate demand holds.
	
		For each choice profile under which contracts are observable substitutes and the observable law of aggregate demand holds, the deferred acceptance mechanism is stable and group-strategy-proof. 
	
	
		<cit.> prove that observable substitutability, the observable law of aggregate demand and "non-manipulability via contractual terms" are sufficient conditions for the stability and strategy-proofness of the deferred acceptance mechanism. 
		Non-manipulability via contractual terms requires that for each profile in the domain and each college c∈ C the deferred-acceptance mechanism is strategy-proof on the domain of
		preference profiles where only contracts with c
		are acceptable for students. For the case of monotone preferences, Corollary <ref> strengthens the result in two directions: First, strategy-proofness can be replaced by the stronger property of group-strategy-proofness. Second,	whereas non-manipulability via contractual terms is in general independent of the other two properties, Corollary <ref> implies that this property is implied by observable substitutability and the observable law of aggregate demand for monotone preferences.
	The assumption of observable substitutability turns out to be necessary for Theorem <ref>, as we show in the following theorem.
	
		If Ch is equivalent to a profile Ch' under which contracts are substitutes, then contracts are observable substitutes under Ch. If, moreover, the law of aggregate demand holds under Ch', then the observable law of aggregate demand holds under Ch.
	
	

 §.§ A Maximal Domain Result

	Next, we derive several implications of Theorems <ref> and <ref>. Combining the results with Theorem 5 of <cit.> we first characterize a maximal domain of choice profiles for the existence of a stable and strategy-proof mechanism using our notion of equivalence. In the following a choice domain is a set of choice profiles
	𝒟⊆_c∈ C𝒞_c. A choice
	domain 𝒟 is Cartesian if
	𝒟=_c∈ C𝒟_c where
	𝒟_c⊆𝒞_c for each college c∈ C. A
	choice function Ch_c for college c is unit demand if
	|Ch_c(Y)|≤ 1 for all Y⊆  X_c. A choice domain is unital if it includes all profiles of unit demand choice
	functions. We obtain the following corollary of Theorems <ref> and <ref>.
	
		For a domain 𝒟 of choice profiles the following statements are equivalent:
		
			
  * 𝒟 is a maximal Cartesian, unital domain of choice profiles such that a stable and strategy-proof mechanism is guaranteed to exist,
			
  * 𝒟 is the domain of choice profiles that are equivalent to a choice profile under which contracts are substitutes and the law of aggregate demand holds.
		
	
	
		
		Let 𝒟_1 be a maximal Cartesian, unital domain of choice profiles such that a stable and strategy-proof mechanism is guaranteed to exist. Let 𝒟_2 he domain of choice profiles that are equivalent to a choice profile under which contracts are substitutes and the law of aggregate demand holds. By Theorems <ref> and <ref>, 𝒟_2 is the domain of choice profiles under which contracts are observable substitutes and the observable law of aggregate demand holds. By Theorem 5 of <cit.>, 𝒟_1 is a subdomain of the domain of profiles under which contracts are observable substitutes and the observable law of aggregate demand holds, thus 𝒟_1⊆𝒟_2. By Proposition <ref>, for each Ch∈𝒟_2, the deferred acceptance mechanism is stable and strategy-proof. Thus, by maximality 𝒟_1=𝒟_2.

	

	Combining the result with Proposition <ref>, the maximal domain result also holds if strategy-proofness is replaced by group-strategy-proofness.
	
	
	

 §.§ An embedding result

	As a third corollary of Theorem <ref>, we obtain an
	embedding result. In recent work <cit.> shows that
	for each BfYC choice profile as introduced by <cit.> there
	is an equivalent choice profile such that the equivalent problem
	can be embedded into a Kelso-Crawford economy. Formally, an isomorphism
	between a matching market with contracts (Ch,≽) and a
	Kelso-Crawford economy (Σ,u) is a one-to-one mapping
	(f,w,σ):X→ F× W×Σ
	such that
	
		
  * for each x,x'∈ X,  f(x)=f(x') if and only if x'_C=x_C, and w(x)=w(x') if and only if x_S=x_S',
		
  * for each x,x'∈ X we have 
    x≻_x_Sx'⇔ u_w(x)(f(x),σ(x))>u_w(x)(f(x),σ(x))

		and 
    x≻_x_S∅⇔
    		u_w(x)(f(x),σ(x))>u_w(x)(∅),

		
  * for each c∈ C, Y⊆ X_c and f∈ F such that f(x)=f for each x∈ Y we have 
    Ch_c(Y)=argmax_Y'⊆ Y^minu_f({(w(x),σ(x)):x ∈ Y'}),

		
  * for each w∈ W,f∈ F and  σ∈Σ∖{σ(x):x∈ X, f(x)=f,w(x)=w }, we have u_w(f,σ)<u_w(∅).[This item is not required in <cit.>, as he only considers situations in which there is the same number of contracts between any college and student.]
	

	 The above notion of an isomorphism is due to <cit.>. It is different from the notion introduced by <cit.>, and used by <cit.>, and <cit.>: 
			Utility function in the Kelso-Crawford economy satisfy stronger
			regularity conditions in <cit.>.
			In <cit.>, monotonicity of utility functions is only required for salaries corresponding to “un-dominated" contracts
			(see the discussion in ), whereas in
			<cit.> monotonicity can be achieved for all salaries.
			
			To guarantee that utility functions satisfy the stronger regularity condition, <cit.> first constructs an equivalent choice profile. The embedding is then performed for a problem where the original choice profile is replaced by the equivalent choice profile. In contrast to this, the embedding result of <cit.> establishes an isomorphism (with his weaker notion of isomorphism) for the original market with contracts, without the need to first construct an equivalent choice profile. Put differently, the embedding result of <cit.> establishes an isomorphism between the cumulative offer algorithm in the original problem and the salary adjustment process in the Kelso-Crawford economy, whereas the embedding result of <cit.> establishes an isomorphism between the sets of stable allocations in the original problem and the Kelso-Crawford economy, but under a weaker notion of an isomorphism.
			
			In the following, we will establish an embedding result in the sense of <cit.>. An embedding result in the sense of <cit.> does not, in general, hold in our setting.

	
		For each choice profile Ch such that contracts are observable
		substitutes and the observable law of aggregate demand holds, there
		exists an equivalent choice profile Ch', such that for each preference profile ≽, the market (Ch',≽) is isomorphic to a Kelso-Crawford economy (Σ,u) such that workers are gross substitutes for firms.
	
	
		By Theorem <ref>, there exist an equivalent profile Ch' under which contracts are substitutes and the law of aggregate demand holds. Moreover, Ch' can be chosen to be monotone in contract-terms for each college. For each c∈ C, Ch_c' can be rationalized (see Theorem 1 in ) by a strict preference relation ≽'_c over 𝒜_c. The preference relation ≽'_c can be chosen to be monotonic in contract terms. Let (≽_s)_s∈ S be a preference profile for students. For the preference profile ((≽'_c)_c∈ C,(≽_s)_s∈ S), we can construct as in the proof of Theorem 1 in <cit.> a corresponding Kelso-Crawford economy (Σ,u) such that Gross Substitutability for firms hold. Since ≽'_c is monotonic in contract terms for each c∈ C there are no undominated contracts in (Ch',≽). Thus, the embedding is one-to-one and satisfies our definition of an isomorphism, in particular monotonicity of the utility functions in the Kelso-Crawford economy is satisfied.
		
	
		While we use the same notion of isomorphism as
		 <cit.>, we do not assume quasi-linearity of firm
		utility functions in the Kelso-Crawford economy. In this sense, our
		result is weaker. However, our result applies to a larger domain
		of choice functions.


§ CONCLUSION

We have studied a model of matching with contracts with a natural monotonicity condition on applicants' preferences that is satisfied in many practically important matching markets, e.g., for the matching of students to colleges with different stipends or fees, the medical match with flexible salaries, or the cadet-to-branch match if cadets rank branch-of-choice contracts monotonically. Our domain restriction allowed us to obtain a characterization of a maximal domain of choice profiles for which a stable and strategy-proof mechanism exists, which - arguably - is simpler than the corresponding characterization for the general model with non-monotone preferences <cit.>. This indicates that the domain restriction to monotone preferences removes some complexity from the matching model with contracts and, hence, simplifies its analysis while practical relevance is maintained since the monotonicity assumption is satisfied in many real-world matching markets. We hope that these features will make the model with monotone preferences also a useful tool for future research on matching markets with contracts.

Our results also raise interesting questions for the general matching model with contracts: For our model and choice domain, strategy-proofness of the deferred acceptance mechanism implies its group-strategy-proofness.  This is established through the construction of an equivalent choice profile under which contracts are substitutes. Substitutability implies a lattice structure for the set of stable allocations under the equivalent choice profile, and with the lattice structure it is easy to show that strategy-proofness implies group-strategy-proofness (see e.g. the discussion in ). For the general matching model with contracts similar constructions, such as the substitutable completion procedure of <cit.>, are known. For the same reason as before - the set of stable allocations forms a lattice under the substitutable completion of the choice profile - strategy-proofness of the deferred acceptance mechanism implies its group-strategy-proofness. However, in contrast to our model, for the general model with non-monotone preferences, a substitutable completion does not exist for each profile in the maximal domain of <cit.>. It, thus, remains an interesting open question under which conditions the strategy-proofness of a stable matching mechanism for the general model of matching with contracts implies its  group-strategy-proofness.
	RM
	
	

§ PROOF OF THEOREM <REF>

	The proof relies on the following two lemmata that we prove first.
	
		If contracts are observable substitutes  under Ch_c, then for each Y⊆ X_c and for any two maximal sequences x^1,…,x^τ and y^1,…,y^τ'
		in Y that are observable under Ch_c and generated from monotone
		preferences we have
		{x^1,…,x^τ}={y^1,…,y^τ'}.
	
	
		The proof strategy is due to <cit.>. 
		We use induction on the size of the set Y.
		Induction Basis: If |Y|=0, then Y=∅ and trivially the empty sequence is the only observable sequence under Ch_c generated from monotone preferences in Y.     Induction Assumption: For each Y⊆  X_s with
		|Y|≤ n  for any two maximal sequences x^1,…,x^τ and y^1,…,y^τ'
		in Y that are observable under Ch_c and generated from monotone
		preferences we have
		{x^1,…,x^τ}={y^1,…,y^τ'}.
		Induction Step:
		Let |Y|=n+1.	Consider two maximal sequences x^1,…,x^τ and y^1,…,y^τ'
		in Y that are observable under Ch_c and generated from monotone
		preferences. Suppose
		{x^1,…,x^τ}≠{y^1,…,y^τ'}.  Then
		w.l.o.g. there is a 1≤ t≤τ' with
		y^t∉{x^1,…,x^τ}. Choose the smallest such t and
		consider the set Y':=Y∖{y^t}. 
		The sequence y^1,…,y^t-1 is contained in Y', generated from monotone preferences and is observable
		under Ch_c. Extend y^1,… y^t-1 to a maximal sequence
		y^1,…,y^t-1,ỹ^t,…,ỹ^τ̃ in
		Y' that is observable under Ch_c and generated from monotone
		preferences.  Since
		y^t∉{x^1,…,x^τ}, sequence x^1,…,x^τ is a maximal sequence in Y' that is observable under Ch_c and generated from monotone preferences. By the induction assumption, we have
		{y^1 …,y^t-1,ỹ^t,…,ỹ^τ̃}={x^1,…,x^τ}.
		Moreover, y^t_S∈ Ch_c{x^1,…,x^τ}_S, as
		otherwise x^1,…,x^τ,y^t would be observable under Ch_c and generated from
		monotone preferences, contradicting the maximality of x^1,…,x^τ in Y. Since
		y^1,…,y^t is observable and generated from monotone preferences, we have y∈ R_c{y^1,…,y^t-1} for each y∈ X_c with y_S=y^t_S and y_T⊳ y^t_T. By observable substitutability, we	have  y∈
			R_c{y^1 …,y^t-1,ỹ^t,…,ỹ^τ̃} for each y∈ X_c with y_S=y^t_S and y_T⊳ y^t_T. As y^t∉{y^1,…,y^t-1,ỹ^t,…,ỹ^τ̃} this implies y^t_S∉
		Ch_c{y^1 …,y^t-1,ỹ^t,…,ỹ^τ̃}_S. Since y^t_S∈ Ch_c{x^1,…,x^τ}_S, as previously observed, this contradicts
		
    {y^1 …,y^t-1,ỹ^t,…,ỹ^τ̃}={x^1,…,x^τ}.

		
	
	
		If contracts are observable substitutes under Ch_c, then
		
			
  * for Y,Z∈𝒪(Ch_c) with Z⊆ Y we have 
    R_c(Z)⊆ R_c(Y).
 If moreover, the observable law of aggregate demand holds for Ch_c, then 
    |Ch_c(Z)|≤|Ch_c(Y)|,

			
  * for Ch_-c∈_c'∈ C∖{c}𝒞_c and ≽∈_s∈ Sℛ_s the sets of contracts Y_1⊆ Y_2⊆…⊆ Y_τ⊆ X_c proposed to c during the cumulative offer algorithm in (Ch,≽) are observable under Ch_c.
			
			
		
	
	
		
		
		For the first part let Y,Z∈𝒪(Ch_c) with Z⊆ Y. Since Z is observable, we can find a sequence x^1,…,x^|Z| generated from monotone preferences with Z={x^1,…,x^|Z|} that is observable under Ch_c. Maximally extend the sequence in Y to obtain a sequence x^1,…,x^|Z|,x^|Z|+1,…,x^τ generated from monotone preferences that is observable under Ch_c.  By Lemma <ref> and observability of Y we have Y={x^1,…,x^τ} and τ=|Y|. The result follows by applying observable substitutability (resp. the observable law of aggregate demand) to the sequence x^1,…,x^|Y|.
		
		For the second part, note that for t=1 the result holds trivially: by the definition of the cumulative offer algorithm each contract in Y_1 is the unique most preferred contract for the involved agent among all contracts. Thus, ordering the contracts in Y_1 arbitrarily yields an observable sequence under Ch_c generated from monotone preferences.
		Next let 1< t≤τ and suppose that Y_1,…,Y_t-1∈𝒪(Ch_c). Take an observable sequence x^1,…,x^|Y_t-1| under Ch_c generated from monotone preferences such that Y_t-1={x^1,…,x^|Y_t-1|} and enumerate contracts in Y_t∖ Y_t-1={x^|Y_t-1|,… x^|Y_t|} arbitrarily. By the definition of the CO algorithm, for each x∈ Y_t∖ Y_t-1 each x'∈ X_c with x'_S=x_s and x'⊳ x has been rejected in some previous round of the algorithm, i.e. there is a t'<t with x'∈ R_c(Y_t'). By observable sustitutability and the second part applied to Z=Y_t' and Y=Y_t-1, we have x'∈ R_c(Y_t-1)=R_c{x^1,…,x^|Y_t-1|}. Thus, for each x∈ Y_t∖ Y_t-1 we have x_S∉ Ch_c(Y_t-1)_S. Observe furthermore that Y_t∖ Y_t-1 contains at most one contract per student. Thus, repeated application of observable substitutability shows that the sequence x^1,… x^|Y_t| is observable.
	 
	

	With the two lemmata we can prove the theorem.
	
	
		For each Y⊆ X_c, let Y^∨∈𝒪(Ch_c) be defined by Y^∨:={x^1,…,x^τ} where x^1,…,x^τ is a maximal observable subsequence under Ch_c of 𝒰(Y) generated by monotone preferences. By Lemma <ref>, Y^∨ is well-defined and Ỹ⊆ Y^∨ for each Ỹ∈𝒪(Ch_c) with Ỹ⊆𝒰(Y). Thus, by the first part of Lemma <ref>,
		
    ⋃_Ỹ⊆𝒰(Y),Ỹ∈𝒪(Ch_c)R_c(Ỹ)=R_c(Y^∨),

		and therefore the virtual choice function is given by 
    Ch_c'(Y)=Y^min∖ R_c(Y^∨).

		First note that Ch_c' satisfies our assumptions on choice
		functions: By definition Ch_c'(Y)⊆ Y^min⊆ Y,
		and since Y^min contains at most one contract per student, also
		Ch'_c(Y) contains at most one contract per student. The IRC
		condition for Ch_c' will follow from substitutability and the law
		of aggregate demand (see ) for Ch'_c which we
		will establish next.
		
		Let Z⊆ Y⊆  X_c. First we show substitutability, i.e. R_c'(Z)⊆ R_c'(Y). Let x∈ R_c'(Z). If x∈ Y∖ Y^min, then x∈ R'_c(Y), as Ch_c'(Y)⊆ Y^min. If x∈ Y^min, then x∈ Z^min and therefore x∈ R_c(Z̃) for a Z̃∈𝒪(Ch_c) with Z̃⊆𝒰(Z)⊆𝒰(Y). Thus, also x∈ R_c'(Y).
		
		
		By definition of Ch_c' and Y^∨ (resp. Z^∨) we have Ch_c'(Y)_S=Ch_c(Y^∨)_S and Ch_c'(Z)_S=Ch_c(Z^∨)_S. Lemma <ref> implies that Z^∨⊆ Y^∨. Thus, by the first part of Lemma <ref> we 
		obtain the law of aggregate demand for Ch'_c, as
		
    |Ch'_c(Z)|=|Ch'_c(Z)_S|=|Ch_c(Z^∨)|≤|Ch_c(Y^∨)|=|Ch'_c(Y)_S|=|Ch'_c(Y)|.
 
			
		To show that Ch_c' is equivalent to Ch_c, let Ch_-c∈_c'≠ c𝒞_c and ≽∈_s∈ Sℛ_c. By the second part of Lemma <ref>, the sets of proposed contracts Y_1⊆ Y_2⊆…⊆ Y_τ to c during the CO-algorithm in (Ch,≽) are observable.
		Now note that for each Y∈𝒪(Ch_c) we have Y=Y^∨ and, moreover, by observable substitutability Ch_c(Y)⊆ Y^min. Thus, Ch'_c(Y)=Y^min∖ R_c(Y)= Y∖ R_c(Y)=Ch_c(Y). As Ch_c' and Ch_c agree on observable sets, we have Ch_c'(Y_t)=Ch_c(Y_t) for t=1,…, τ. Hence Ch_c' and Ch_c are equivalent.
	
	

§ PROOF OF THEOREM <REF>

	
		
		Let c∈ C and consider a sequence x^1,…,x^τ
		that is observable under Ch_c and generated from monotone
		preferences. We show that
		Ch_c'{x^1,…,x^τ}=Ch_c{x^1,…,x^τ}. Since contracts are substitutes under
		Ch_c' this will imply that contracts are observable substitutes under Ch_c. Moreover, if the law of aggregate demand holds under Ch'_c, then this will imply the observable law of aggregate demand for Ch_c. In the following,
		we denote by ≽^0∈_s∈ Sℛ_s a profile
		such that no contract is acceptable, and for 1≤ t≤τ we
		denote by ≽^t∈_s∈ Sℛ_s a profile such that x≻^t_x_S∅ for
		x∈{x^1,…,x^t} and ∅≻^t_x_Sx for
		x∉{x^1,…,x^t}. First note that
		
    ∅=Ch_c'(∅)=𝒞𝒪(Ch',≽^0)=𝒞𝒪(Ch',≽^0)=Ch_s(∅).

		Next we show that if for 0≤ t<t'≤τ we have
		
    Ch'_c{x^1,…,x^t}=𝒞𝒪(Ch',≽^t)=𝒞𝒪(Ch,≽^t)=Ch_c{x^1,…,x^t}

		then
		
    Ch'_c{x^1,…,x^t'}=𝒞𝒪(Ch',≽^t')=𝒞𝒪(Ch,≽^t')=Ch_c{x^1,…,x^t'}.

		Since Ch_c{x^1,…,x^t}=Ch'_c{x^1,…,x^t} for
		0≤ t<t', observability of  x^1,…,x^t' under Ch_c
		implies observability of  x^1,…,x^t' under Ch'_c.
		
		Let
		Y be the set of proposed contract during the CO-algorithm in (Ch',≽^t'). By (observable) substitutability of Ch_c', the second part of Lemma <ref> applied to (Ch',≽^t')  implies that Y is observable under Ch'_c. Thus, there is a sequence y^1,…,y^t” that is observable under Ch_c and generated from monotone preferences such that Y={y^1,…,y^t”}⊆{x^1,…,x^t'}. Note furthermore that y^1,…,y^t” is a maximal such sequence in the set {x^1,…,x^t'}, since otherwise not all students who are unmatched in the outcome of the CO algorithm in (Ch',≽^t') have proposed under all acceptable contracts.
		Since x^1,…,x^t' is observable under Ch_c' this implies Y={y^1,…,y^t”}={x^1,…,x^t'}.
		By equivalence of Ch and Ch', we have 	
    Ch'_c{x^1,…,x^t'}=𝒞𝒪(Ch',≽^t')=𝒞𝒪(Ch,≽^t')=Ch_c{x^1,…,x^t'}.

		
	
	
