Fatma Aslan

Jean Lainé

Competitive Equilibria in Shapley-Scarf Markets with Couples ⋆

Keywords:

We investigate the existence and properties of competitive equilibrium in Shapley-Scarf markets involving an exogenous partition of individuals into couples. The presence of couples generates preference interdependencies which cause existence problems. For both cases of transferable and non-transferable income among partners, we establish properties for preferences that are sufficient for the existence of an equilibrium. Moreover, we show that these properties define a maximal preference domain.

Introduction

A Shapley-Scarf market [START_REF] Shapley | On cores and indivisibility[END_REF] refers to a pure exchange economy without money, which involves finitely many individuals, each owning an indivisible good and having use of only one good. [START_REF] Shapley | On cores and indivisibility[END_REF] prove the non-emptiness of the core in such markets and introduce the Top-Trading-Cycles (TTC) algorithm (attributed to David Gale), which always terminates at an allocation in the core. [START_REF] Roth | Weak versus strong domination in a market with indivisible goods[END_REF] show that if individual preferences over goods are described by linear orders, the TTC outcome is the unique element of the strict core and the unique competitive allocation. The TTC algorithm also satisfies various desirable properties. Its outcome is Pareto efficient.1 Moreover, it defines a strategy-proof allocation mechanism [START_REF] Roth | Incentive compatibility in a market with indivisible goods[END_REF], and this mechanism is the unique one satisfying strategy-proofness, Pareto efficiency, and individual rationality [START_REF] Ma | Strategy-proofness and the strict core in a market with indivisibilities[END_REF]. 2Beyond its classical interpretation as the housing market, a Shapley-Scarf market provides a relevant framework for the analysis of professional mobility, through which employees move from their current job (good) to another one made available by their employer or by the market. Many real-life mobility campaigns are organized as centralized procedures, in which individuals report to a central authority their preference list of available jobs, and the authority reassigns jobs so that each individual gets exactly one job.

A noteworthy fact in the design of a job mobility procedure is that some individuals live in couples. This leads to a significant departure from the classical Shapley-Scarf market, where individuals' well-being only depends on the job they get. In contrast, individuals living in couple care not only about their own job but also about the one assigned to their partner. The consequences of externalities in preferences have been paid attention mainly for two-sided allocation problems. 3 Notable exceptions are [START_REF] Hong | Core and top trading cycles in a market with indivisible goods and externalities[END_REF], and [START_REF] Massand | Graphical one-sided markets[END_REF], where the existence of core-stable solutions is investigated for specific types of externality in Shapley-Scarf markets. 4 The disturbing role of ⋆ Both authors are grateful to Onur Doğan, Gilbert Laffond, Jordi Massó and Walter Trockel for helpful discussions. We thank the Co-Editor Alessandro Citanna and two anonymous referees for valuable suggestions and comments. The research reported in this paper has been supported by the National Research, Development and Innovation Fund (TUDFO/51757/2019-ITM, Thematic Excellence Program).

* Corresponding author fatma.aslan@gtdh.bme.hu (F. Aslan); jean.laine@lecnam.net (J. Lainé)

couples for existence of certain solutions is not new. Indeed, [START_REF] Doğan | The core of shapley-scarf markets with couples[END_REF] show that a Shapley-Scarf market with couples where partners have joint preferences may have an empty core. This paper aims to investigate how the existence and properties of competitive equilibrium accommodate situations where individuals care not only about the good they receive but also about the good received by their partner. As equilibrium allocations closely relate to the TTC algorithm in markets without couples, a natural complementary issue is studying how the original properties of the TTC algorithm are impacted by this specific externality in preferences.

A competitive equilibrium in a Shapley-Scarf market without couples is defined as a situation where each individual is assigned to exactly one good, which she prefers the most among those with a price not exceeding the price of her currently owned good (interpreted as her income). Many real-life job mobility procedures are based on the computation of a score. Each applicant is assigned a number of points, or a score, which mimics a price. One example of such procedures is the one designed for French teachers in primary and secondary schools. In this procedure, the scores of applicants result from their professional history, as well as their private data (marital status, number of children, level of seniority as a teacher, duration of the last position, personal difficulties such as the care of a disabled child). A significant input in the computation method is also the nature of their current position. For instance, the wish to avoid teaching staff shortage in some district may motivate raising the score of teachers in that district. Applicants are ranked according to their respective scores, and this ranking determines the priority given to each applicant in the allocation procedure. Applicants with a high priority rank usually choose a popular position in terms of location or job quality. Hence, popular positions being accessible only to high score people, they are given a high market value (defined as the score of their tenants). A consequence is that a score of each applicant can be interpreted as a proxy for her income or the market value (price) of her currently held position. This motivates the relevance of competitive equilibrium as a solution to job mobility design.

We model a centralized procedure where each individual submits a preference list over bundles of two goods, the one she receives and the one her partner receives. This very general definition of preferences admits as special cases the one where couples submit joint preference lists, and also the one where each individual submits a preference list for herself, the central authority aggregating partners' lists through some pre-specified device. Beyond the will of generality, this choice is motivated by the fact that most real-life mobility procedures for couples discard the possibility for couples of making joint claims. Exceptions may prevail for couples of civil servants whose careers are administrated by the same entity, and whose target is moving together to the same district. For instance, since 2018, a procedure of joint mobility allows French primary school teachers to condition their mobility to a given new area to the fact that their partners also get a position in that area. According to this procedure, both partners must report the same rankings of targeted positions. In contrast, the Scottish Foundation Allocation Scheme (SFAS) for medical school graduates stipulates that applicants who want to be assigned geographically close positions may require to be treated as a couple. However, such applicants are asked to submit separate preference lists, which are aggregated by considering their geographic concern to generate a joint preference list (for more details see [START_REF] Biró | Stable matching with couples: an empirical study[END_REF].

Another critical issue in our model is whether income (or score level) is transferable among partners. In most real-life situations, the budget constraint prevails individual-wise. However, the aforementioned procedure of French joint mobility of primary schools teacher allocates to each partner the average score in the couple, which is a typical example of transferable income.

There is no natural definition of a competitive equilibrium for such an economy. We focus on a specific concept of market equilibrium, in which each couple gets a budget-constrained Pareto efficient bundle of goods. In the case where income is (resp. not) transferable among partners, we call weak (resp. strong) this equilibrium. Obviously, if partners submit the same preference list, Pareto efficiency resumes to maximizing the couple well-being under the relevant budget constraint.

We show that strong and weak equilibria may fail to exist with unrestricted preferences. Moreover, we identify two properties upon preferences which generate domains respectively maximal for the existence of strong and weak equilibria. Here, maximality means that existence is ensured at all profiles selected from the domain, but may fail when enlarging the domain with a preference that shows a minimal departure from the property. More precisely, -The domain of responsive preferences is maximal for the existence of strong equilibria. Responsiveness holds if each individual has two linear orders over goods, one for herself and one for her partner, and gets better off with a Pareto improving change with respect to these linear orders. In the case where the order over the partner's good coincides with the partner's order over her own goods, we get couple responsiveness. Interestingly enough, we show that with couple responsive preferences, the TTC algorithm always ends up at a strong equilibrium allocation. However, the TTC algorithm no longer defines a strategy-proof mechanism.

-The domain of weakly lexicographic preferences is maximal for the existence of weak equilibria. An individual has a weakly lexicographic preference if it satisfies the following property. For each subset of goods, there exists an element of this subset (called the priority good), and for each possible bundle of goods assigned to the couple, one of the two partners is given priority. Then, any bundle of goods assigning the priority good to the partner having priority for this bundle is preferred to any bundle not doing so. Moreover, since weak equilibrium allocations belong to the core, this existence result generalizes the main result of [START_REF] Doğan | The core of shapley-scarf markets with couples[END_REF].

For each type of equilibrium, we provide a constructive proof of existence based on a modification of the TTC algorithm. As for the TTC algorithm for non-transferable income, this modified version is shown to be manipulable.

Both preference domains describe rather severe restrictions. In particular, they preclude complementarities between goods, which usually prevail when the distance between partners' goods matters. Moreover, since responsiveness and the weakly lexicographic properties are logically independent, one cannot argue that the existence of equilibrium is made more or less problematic by income transferability. However, we show that under income transferability equilibrium allocations are Pareto efficient and are core-stable when coalitions are not entitled to break couples. In contrast, an equilibrium allocation without transferable income can be Pareto dominated and core-unstable.

The paper is organized as follows. Section 2 is devoted to preliminaries. We formalize Shapley-Scarf markets with couples in Section 2.1. Weak and strong equilibria are defined in Section 2.2. Alternative preference domains are introduced in Section 2.3. All results are stated in Section 3. Properties of equilibrium allocations (set-comparison, individual rationality, core stability, and Pareto efficiency) are studied in Section 3.1. Existence results are presented in Section 3.2. In Section 3.3., we establish the maximality of the responsive and weakly lexicographic preference domains. We conclude the paper with further comments, especially on alternative equilibrium concepts that may be considered and on the relationship between our model and models with multiple types of indivisible goods. Finally, all proofs are postponed to an Appendix.

A model of Shapley-Scarf markets with couples

Preliminaries

We consider a finite set = {1, … , } of individuals confronting a set = {1, … , } of purely indivisible goods, where is even. Individuals (resp. goods) are denoted by , , (resp. , , ). Each individual initially owns exactly one good, and exchanging goods is done without money. An allocation is a bijection from to . For the sake of simplicity, we write an allocation as an ordered vector ( (1), … , ( )). The set of allocations is denoted by Σ. The initial allocation is denoted by 0 . At the eventual cost of relabelling goods, one can assume 0 ( ) = for all . Under this assumption, allocations are equivalently defined as permutations of .

We assume there exists an exogenous partition of into couples, denoted by  = { 1 , … , ∕2 }. We denote the couple containing individual by ( ).

Given an allocation together with a couple = { , } with < , we denote the bundle of goods that allocates to partners in by = ( ( ), ( )). A significant departure from standard Shapley-Scarf markets is that individuals' well being not only depends on their own assigned good but also depends on the allotment of their mate. Hence, each individual's preferences are over the bundle of goods assigned to their couple.5 Let = {( , ) ∈ × ∶ ≠ }. Preferences of individual are represented by a linear order over , and we write ( ) ̄ ( ) if and only if individual ranks allocation above allocation ̄ . With a notational abuse, we write ̄ if and only if ( ) ̄ ( ) . A profile is an -tuple = ( ) ∈ of linear orders over , and Π stands for the set of all profiles. Definition 1. A Shapley-Scarf market with couples is a triple  = ( , , ) where is the number of goods and individuals,  is a partition of the set of individuals into couples, and is a profile.

Competitive equilibrium

Consider a Shapley-Scarf market without couples involving individuals, where each individual initially owns good . Pick a vector = ( 1 , … , ) assigning price to each good in . The budget set of an individual at is { ∈ ∶ ≤ }. An allocation and a price vector form a competitive equilibrium if for each individual , ( ) the most-preferred good in the his budget set at prices .

There is no natural definition of competitive equilibrium in the presence of couples. First, at least two types of budget sets can be retained, which respectively forbids and authorize income transfers between partners. Second, assumptions have to be made on how individuals take their partner's situation into account when comparing allocations.

The two types of budget sets are formalized below. Pick ∈ with ( ) = { , } and pick a price vector = ( 1 , … , ).

Definition 2. The strong budget set of for is the subset of allocations ( ) = { ∈ Σ ∶ ( ) ≤ and ( ) ≤ }. The weak budget set of for is the subset of allocations

( ) = { ∈ Σ ∶ ( ) + ( ) ≤ + }.
Observe that ( ) = ( ) and ( ) = ( ) for all { , } ∈ . Therefore, we can write ( ) = ( ) ( ) and ( ) = ( ) ( ) for all ∈ . Furthermore, it is obvious that ( ) ⊆ ( ) for all and all . We turn to the treatment of interdependency between preferences. Having in mind a centralized procedure aiming at properly addressing the existence of couples, we focus on an equilibrium concept based on couple welfare rather than individual welfare. More precisely, partners' welfare are extended to couple welfare by means of the Pareto criterion. Hence, an equilibrium allocation prevails when there is no other allocation ′ assigning some couple to a bundle of goods ′ that is affordable at the current price vector and Pareto-dominates the bundle for . Put differently, an equilibrium allocation assigns a price-constrained Pareto optimal bundle to each couple.

Formally, given a price vector and a couple , a -optimum for is an allocation ∈ ( ) ∈ { ( ), ( )} such that there is no ′ ∈ ( ) such that ′ for all ∈ . If ( ) = ( ), is called a strong -optimum for and if ( ) = ( ), is called a weak -optimum for . We denote the set of strong and weak -optima for by  ( ),  ( ) respectively.

Definition 3. A (resp. weak) strong equilibrium for  is a 2-tuple ( , ) ∈ Σ × ℝ + such that ∈  ( ) (resp.  ( )) for all ∈ .
We denote the sets of strong and weak equilibria by () and

() respectively and we denote the sets of strong and weak equilibrium allocations by () and () respectively. The following examples illustrate the definition of weak and strong equilibria.

Example 1. Pick  = (4, , ) where  = { 1 , 2 } = {{1, 2}, {3, 4}}
, and has the form below:

⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 2 3 4 (3, 4) (3, 4) (3, 2) (3, 2) (1, 4) (1, 4) (1, 2) (3, 1) … … … (1, 2) … ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ Let = (3, 4, 1, 2) and = (2, 2, 3, 1). Since 1 + 2 = 3 + 4 , ∈ 1 ( ) ∩ 2 ( )
. Individuals 1 and 2 get their first best bundles, therefore, ∈  1 ( ). Moreover, 2 + 3 > 3 + 4 and 1 + 3 > 3 + 4 ensure that individuals 3 and 4 get with their first best bundle in their weak budget set, so ∈  2 ( ). Thus ( , ) ∈ () and ∈ ().

However, ( , ′ ) ∉ () for some price vector ′ . First observe that strong budget feasibility of w.r.t. ′ requires

′ 1 = ′ 3 and ′ 2 = ′ 4 . Moreover, ( , ′ ) ∈ () implies ′ 2 > ′ 4 (otherwise ∉  2 ( ′ ))
, in contradiction with budget feasibility. This shows that ∉ ().

Example 2. Pick  = (4, , ) where  = { 1 , 2 } = {{1, 2}, {3, 4}}, and preferences are such that:

⎛ ⎜ ⎜ ⎜ ⎝ 1 2 3 4 (2, 1) (2, 1) (4, 3) (4, 3) (1, 2) (1, 2) (3, 4) (3, 4) … … … … ⎞ ⎟ ⎟ ⎟ ⎠
Pick the initial allocation 0 = (1, 2, 3, 4) and the price vector = (1, 3, 1, 3). Although = (2, 1, 4, 3) satisfies 0 for all , is budget feasible for no couple since 2 > 1 and 4 > 3 . Thus

0 ∈  1 ( ) ∩  2 ( ). Therefore ( 0 , ) ∈ ().
Observe also that ( 0 , ′ ) is a weak equilibrium for no price vector ′ . Indeed,

( 0 , ′ ) ∈ () requires ′ 2 + ′ 1 > ′ 1 + ′ 2 (otherwise 0 ∉  1 ( ) ) and ′ 4 + ′ 3 > ′ 3 + ′ 4 (otherwise 0 ∉  2 ( ))
, which is impossible. Therefore, 0 ∉ ().

Restrictions upon preferences

We show below that the existence of equilibria is sensitive to the structure of preferences. Attention will be paid to three restricted preference domains, starting with the domain of responsive preferences. Definition 4. An individual with = { , } has a responsive preference if there exists a 2-tuple (≻ , ≻ ) of linear orders over such that ∀ , , ∈ ,

≻ implies [( , ) ( , )] and ≻ implies [( , ) ( , )].
Responsiveness holds if each individual has a linear order over goods for each of all her partners (including herself), and gets better off with a Pareto improving change with respect to these linear orders. Observe that in Definition 4, ≻ may not coincide with ≻ . If each individual ranks goods allocated to her partner according to her partner's ranking, any unilateral improvement of one partner's well-being will benefit both partners. This special case is called couple responsiveness.

Definition 5. An individual with = { , } has a couple responsive preference if it is responsive and ≻ = ≻ =≻ .

A profile = ( ) ∈ is called (resp. couple) responsive if is (resp. couple) responsive for all ∈ . The set of (resp. couple) responsive profiles is denoted by Π (resp. Π ). 6Preferences are called joint if we have = for all { , } ∈ . Clearly, if preferences are joint and responsive, they are couple responsive. The set of all joint preference profiles is denoted by Π .

We now introduce lexicographic and weakly lexicographic preferences. Denote by  the set of subsets of with cardinality at least 2. Moreover, given any ∈  , we define Σ( | ) = { ∈ Σ ∶ { ( ), ( )} ⊆ } as the set of allocations assigning a bundle of goods in to couple .

Definition 6. An individual has lexicographic preferences if there exist a good-priority mapping ∶  → and a partner-priority mapping

∶  → ( ) such that ∀ ⊆  , 1. ( ) ∈ , 2. ∀ , ′ ∈ Σ( ( ) | ), ′ if ( ( )) = ( ) and ′ ( ( )) ≠ ( ).
An individual has lexicographic preferences if when facing any subset of goods available for trade, there exist a unique good = ( ) in and a unique partner = ( ) ∈ ( ) such that ranks any allocation where is assigned to above any other one assigning to some other good. A profile is called lexicographic if it involves lexicographic preferences. As with responsiveness, the lexicography property qualifies the link between the one-dimensional thinking that individuals frequently employ with the multi-dimensional nature of the allocations. Individuals with lexicographic preferences prioritize goods, tying each one to the partner that good should be allocated to, and they are better off when a higher priority good has been assigned to the appropriate partner. Note that partners may have different ways to prioritize goods and partners.

A profile = ( ) ∈ is called lexicographic if is lexicographic for all ∈ . Π will stand for the set of all lexicographic profiles. 7Moreover, observe that the lexicographic property and couple responsiveness are logically independent.8 Under lexicographic preferences, the partner given priority is designated regardless of the good received by the other partner. A weakening of the lexicographic property is obtained if the priority partner may depend on the entire bundle allocated to the couple. Given any element of  , we define = {{ , } ⊆ ∶ ≠ }.

Definition 7. An individual with

= { , } has weakly lexicographic preferences if there exist a good-priority mapping ∶  → and a contingent partner-priority mapping ∶ → such that ∀ ⊆  ,

1. ( ) ∈ , 2. ∀ , ′ ∈ Σ( | ), ∀ ∈ ∖{ ( )}, we have ′ if ( { , ( )}) = ( ), ( ∖ { , ( )}) = , and ′ ( { , ( )}) ≠ ( ).
An individual ∈ has weakly lexicographic preferences if the following conditions are verified:

-for each subset of goods , there exists a good ( ) in , called the priority good, -for each possible bundle of goods { , } ∈ assigned to the couple, one partner { , } is given priority, -any bundle of goods assigning the priority good to the partner having priority for this bundle is preferred to any bundle not doing so.

Hence, the only difference between lexicographic and weakly lexicographic preferences is making the priority partner conditional or not to the couple allotment. For an illustration, consider the two linear orders and ′ defined over bundles in = {1, 2, 3, 4}.

⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ′ (1, ) (1, ) (2, ) ( , 2) (3, ) (3, ) (3, 1) (3, 1) (3, 2) (2, 3) (1, 2) (1, 2) … … ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
Then is lexicographic, while ′ is weakly lexicographic but not lexicographic.

A profile = ( ) ∈ is called weakly lexicographic if is weakly lexicographic for all ∈ . Π will stand for the set of weakly lexicographic profiles. Clearly, Π ⊂ Π .

Results

We start with a set-comparison between the weak and strong equilibrium sets. It turns out that none is contained in the other, even under the preference restrictions defined in Section 2.3. Proposition 1. There exists  = ( , , ) such that () ≠ ∅, () ≠ ∅ and,

1. ∈ Π , () ⊈ () and () ⊈ () 2. ∈ Π ∩ Π , () ⊈ () and () ⊈ ()
The remaining part of this section is organized into three subsections. Section 3.1 is devoted to the properties of equilibrium allocations. In Section 3.2, we establish two preference restrictions that respectively ensure the existence of strong and weak equilibria. We show in Section 3.3 that both restrictions define a maximal domain of existence.

Properties of equilibria

It is well-known that equilibrium allocations in Shapley-Scarf markets without couples are individually rational, core stable, and Pareto optimal in the case of strict preferences. We investigate these properties for equilibria in the presence of couples. It appears that a completely different picture prevails. Indeed, a strong equilibrium allocation may violate all three properties. In contrast, Pareto optimality and stability for a specific notion of core hold for weak equilibrium allocations.

Individual Rationality:

An allocation is individually rational for ∈ if ( ) ≠ 0 ( ) implies ( ) 0 ( ) . The set of individually rational allocations for is denoted by Σ( 0 , ), and the set of individually rational allocations at a profile = ( ) ∈ is defined as Σ( 0 , ) = ∩ ∈ Σ( 0 , ). Not surprisingly, individual rationality may not hold at equilibrium allocations, unless partners have the same preference over bundles. Indeed, assigning one individual to her first-best affordable bundle leaves no room for Pareto improvement, while this bundle may make her partner less well off than with the initial bundle.

Proposition 2.

1. There exists  = ( , , ) such that ∈ Π ∩ Π where ∈ ( ) ∩ ( ) is not individually rational. 2. ∈ ( ) ∪ ( ) is individually rational for all  = ( , , ) such that ∈ Π .

Core Stability:

An allocation is core-stable if there is no coalition of individuals that can make all its members strictly better off by exchanging their initial endowments. Since in Shapley-Scarf markets without couples, an individual's well-being depends only on her assigned good, core stability is defined without reference to the situation of individuals not in the coalition. In contrast, preference interdependence in markets with couples makes this situation critical, at least in cases where coalitions break couples. Alternative core concepts are the -core [START_REF] Hart | Endogenous formation of coalitions[END_REF][START_REF] Chander | The core of an economy with multilateral environmental externalities[END_REF] and the -core [START_REF] Aumann | Von neumann-morgenstern solutions to cooperative games without side payments[END_REF]. According to the -core, coalitions can only block via allocations where each individual not in the coalition receives her initial good. In contrast, according to the -core, a coalition is blocking if only if all its members can be made better off regardless of what is allocated to individuals not in the coalition. The critical role played by the situation of outsiders disappears if coalitions are admissible only if they do not break couples. This restriction leads to the concept of -core stability. Definition 8. Pick any  = ( , , ). Given , ′ ∈ Σ, a ( ′ , )-blocking coalition is a non-empty subset of such that { ′ ( )} ∈ = and ′ for all ∈ .

1. The -core of  is the subset Ω () of Σ which contains all allocations for which there is no ( ′ , )-blocking coalition satisfying ∀ ∈ , ∈ ⇒ ( ) ⊆ . 2. The -core of  is the subset Ω () of Σ which contains all allocations for which there is no ( ′ , )-blocking coalition satisfying ∀ ∈ ∖ , ′ ( ) = 0 ( ). 3. The -core of  is the subset Ω () of Σ which contains all allocations for which there is no ( ′ , )-blocking coalition such that is a ( ′′ , )-blocking coalition for all ′′ ∈ Σ with ∀ ∈ , ′ ( ) = ′′ ( ).

We show that a strong equilibrium allocation may be unstable for all three concepts of core. Moreover, while always -core stable, a weak equilibrium allocation may also be -core unstable (hence -core unstable).

Proposition 3.

1. There exists  = ( , ,

) with ∈ Π ∩Π such that () ⊈ Ω () and () ⊈ Ω (). 2. () ⊆ Ω () for all  = ( , , ). 3. There exists  = ( , , ) such that () ⊈ Ω ().
As an immediate corollary of Proposition 3, we get that a strong (resp. weak) equilibrium allocation may not be in the -core. Indeed, observe that for any , Ω () ⊆ Ω () and Ω () ⊆ Ω ().

We conclude this subsection with Pareto optimality.

Pareto optimality:

An allocation is Pareto optimal in  = ( , , ) if there is no ′ ≠ such that either ( ) = ′ ( ) or ′ for all ∈ . It is already known that in standard Shapley-Scarf markets, an equilibrium allocation may be Pareto dominated only when indifference is allowed (Emmerson et al., 1972;[START_REF] Roth | Weak versus strong domination in a market with indivisible goods[END_REF]. Although indifference between bundles is precluded in our setting, we first observe that a strong equilibrium allocation may be Pareto dominated. To see why, consider market  = (4, , ) where  = {{1, 2}, {3, 4}}, and is any couple responsive profile having the form as below: where = (2,1,2,1). However 0 is Pareto dominated by ′ = (2, 1, 4, 3). However, every weak equilibrium allocation is Pareto optimal, as stated in the next proposition. What can be deduced from Proposition 3 and Proposition 4 is that an allocation procedure based on the competitive mechanism should allow for income transferability, since Pareto efficiency and core stability (for admissible coalitions consistent with the couple structure) hold at equilibrium while both may fail when partners face individual income constraint. Obviously, this statement holds only when an equilibrium exists. We now address the existence of equilibria.

⎛ ⎜ ⎜ ⎜ ⎝ 1 , 2 3 , 4 (2, 1) (4, 3) (1, 2) (3, 4) … … ⎞ ⎟ ⎟ ⎟ ⎠ We have ( 0 , ) ∈ ()

Existence of equilibria

Our first observation is that without restriction upon preferences a strong or weak equilibrium may fail to exist, as illustrated by the next example.

Example 3. Consider  = (8, , ) where  = { 1 , 2 , 3 , 4 } = {{1, 2}, {3, 4}, {5, 6}, {7, 8}}, and is such as below:

⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 , 2 3 , 4 5 , 6 7 , 8 (5, 2) (3, 2) (4, 6) (5, 8) (1, 4) (3, 7) (1, 6) (7, 8) (1, 2) (3, 4) (5, 6) … … … … ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ By Proposition 2.2, () ∪ () ⊆ Σ( 0 , ).
It is easily checked that Σ( 0 , ) contains the 4 allocations where 0 , 1 = (1, 4, 3, 2, 5, 6, 7, 8), 2 = (5, 2, 3, 4, 1, 6, 7, 8), and 3 = (1, 2, 3, 7, 4, 6, 5, 8). Suppose ( 0 , ) ∈ ().

Then 0 ∈  2 ( ) requires 7 > 4 , while 0 ∈  3 ( ) ∩  4 ( ) implies 4 > 5 and 5 > 7 . Hence 7 > 4 > 5 > 7 , clearly a contradiction. Similarly, -if ( 1 , ) ∈ (), then 1 ∈  1 ( ) ∩  3 ( ) implies 5 > 1 > 5 , which is impossible. -if ( 2 , ) ∈ (), then 2 ∈  2 ( ) ∩  3 ( ) ∩  4 implies 7 > 4 > 5 > 7 , which is impossible. -if ( 3 , ) ∈ (), then 3 ∈  1 ( ) ∩  2 ( ) implies 4 > 2 > 4 , again an impossibility.
Therefore, () = ∅. Finally, since all allocations ∈ Σ( 0 , ) are such that for all = { , } ∈ , either ( ) = or ( ) = , the same argument shows that () = ∅.

We establish below for each type of equilibrium a condition on preferences that is sufficient for existence.

Existence of strong equilibria

Preferences in the market described by Example 3 are not responsive. It turns out that responsiveness is a sufficient condition for the existence of a strong equilibrium. Moreover, we show that under couple responsiveness, the wellknown Top-Trading-Cycle algorithm (hereafter TTC) always terminates at a strong equilibrium allocation. We start with briefly recalling how TTC operates.

We define a TTC sequence  as a partition { } =1,…, of into non-empty set such that;

-∀ ∈ {1, … , }, = { 1 , … , } satisfies +1 ≻ for all = 1, … , and for all ∈ = ∖ ⋃ 1≤ ′ < ′ (with the convention + 1 = 1), -+1 = ∅.9 A TTC allocation assigns goods to individuals consistently with a top-trading sequence: ( ) = +1 for all ∈ {1, … , } and all ∈ {1, … , }. Hence, TTC is a multi-stage trade procedure where each agent is involved in one and only one stage, and is assigned her most preferred good among those available at that stage. While TTC brings a strong equilibrium allocation with couple responsive preferences, it may not do so with responsive preferences. However, operating a slight modification of TTC allows to prove the existence of strong equilibria.

Proposition 5.

() ≠ ∅ for  = ( , , ) where ∈ Π . Moreover, if ∈ Π , the TTC allocation is a strong equilibrium allocation.

It is well-known that in markets without couples, a competitive equilibrium allocation is characterized as an outcome of TTC. Moreover, the equilibrium allocation is unique if preferences are strict. In contrast, the existence of couples allows for multiple equilibria even without indifference. Moreover, an equilibrium allocation may not be a TTC outcome, as shown by the following example.

Example 4. Define  = (6, , ) where  = {{1, 2}, {3, 4}, {5, 6}}, and is given by:

⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 , 2 3 , 4 5 , 6 (2, 3) (4, 5) (6, 1) (3, 2) (5, 4) (1, 6) (1, 3) (3, 5) (5, 1) (1, 2) (3, 4) (5, 6) … … … ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
where can be made couple responsive w.r.t. linear orders over goods as below:

• [3 ≻ 2 ≻ 1 ≻ ... ∀ = 1, 2], • [5 ≻ 4 ≻ 3 ≻ ... ∀ = 3, 4] • [1 ≻ 6 ≻ 5 ≻ ... ∀ = 5, 6].

One gets

= (3, 2, 5, 4, 1, 6), and ( , ) ∈ () with = (2, 1, 2, 1, 2, 1). Moreover, = (2, 3, 4, 5, 6, 1) can be sustained as a strong equilibrium allocation with = (1, 1, 1, 1, 1, 1). We also note that is not Pareto optimal, since for all ∈ .

Another well-known property of TTC algorithm is that it defines a strategy-proof allocation mechanism for markets with singles [START_REF] Roth | Incentive compatibility in a market with indivisible goods[END_REF]. This is no longer the case for markets with couples, even in the case of joint preferences. To see why, consider the next example.

Example 5. Let  = (4, , ) where 1 = {1, 2}, 2 = {3, 4}, and is given by:

⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 , 2 3 , 4 (4, 3) (3, 1) (2, 3) (3, 4) (2, 4) … (4, 2) … ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
Clearly, one may complete so as to ensure couple responsiveness. The outcome of TTC is = (4, 2, 3, 1). If individual 1 reports any (couple responsive) preference with (2, 3) at top instead of her true preference, the outcome becomes = (2, 4, 3, 1), and misrepresenting is worthwhile since 1 .

Whether (couple) responsiveness is a severe restriction or not is a matter of context. For instance, it seems rather natural in the case of task reassignment within a team. However, since it precludes complementarity between goods, it seems less natural in all situations where goods are distributed across several locations and where distance matters to partners. In terms of design (and putting aside strategic concerns), a by-product of Proposition 5 is that with couple responsiveness, it suffices to ask individuals to report their own preference list over goods in order to get an

Existence of weak equilibria

We turn to the existence of weak equilibria. The next example shows that (couple) responsiveness is no longer sufficient for existence when income becomes transferable. Example 6. Consider  = (8, , ) where  = {{1, 2}, {3, 4}, {5, 6}, {7, 8}}, ∈ Π ∩ Π is the profile below: 4 5 ,6 7 ,8 (7,2) (2,4) (3,6) (7,4) (7,3) (2,1) (8,6) (7,5) (1,2) (5,4) (3,8) (8,4

⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 , 2 3 ,
) … (3, 4) (5, 6) (7, 8) … … … ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
By Proposition 2.2, () ⊆ Σ( 0 , ). Moreover, the set of individually rational allocations Σ( 0 , ) contains the 4 allocations 0 , 1 = (7, 3, 2, 1, 5, 6, 8, 4), 2 = (1, 2, 5, 4, 3, 6, 7, 8), and 3 = (1, 2, 3, 4, 8, 6, 7, 5).

+ 7 > 1 + 2 > 3 + 4 , -if ( 3 , ) ∈ (), then 5 > 3 > 5 , -if ( 0 , ) ∈ (), then 3 > 5 > 3 ,
Since all situations being impossible, we conclude that () = ∅.

We show below that weakly lexicographic preferences ensure the existence of weak equilibria. More precisely, define Π 0 ⊂ Π as the set of profiles = ( ) ∈ such that each preference is weakly lexicographic in restriction to Σ( 0 , ). We will prove that any Shapley-Scarf market  = ( , , ) such that ∈ Π 0 admits a weak equilibrium. This property is a weakening of the lexicographic property introduced in [START_REF] Doğan | The core of shapley-scarf markets with couples[END_REF], which is shown to be sufficient for the non-emptiness of -core in the case of joint preferences. Since a weak equilibrium allocation belongs to the -core (by Proposition 3.2), we both strengthen this result and extend it to a broader setting, where preferences are not necessarily joint. The argument is based on a modified version of TTC (hereafter called MTTC).

We introduce some useful notions before defining MTTC formally. For any individual , we write ( ) = { , }. Pick any profile in Π 0 together with a non-empty subset of goods and an allocation . We define a -TTC with respect to allocation as an ordered subset of individuals , = { } 1≤ ≤ satisfying the two conditions below:

1. For all 1 ≤ ≤ , ( ) ∩ , = { }, 2. For all 1 ≤ ≤ -1, ( +1 ) = ( ), and ( ) ∈ { ( 1 ), ( 1 )}.

Condition (1) says that , involves at most one partner in each couple. According to condition (2), each individual in , points to the individual endowed with her (necessarily unique) priority good in at , while the last individual points either the first individual 1 (in case 1 owns the priority good of in ) or her partner 1 (in case 1 owns the priority good of in ) . It is obvious to show that a -TTC w.r.t. exists for all subsets and all allocations . Note that a -TTC may be a singleton { } if either ( ) = ( ) or ( ) = ( ).

Given a -TTC w.r.t. , (i.e., , ) we define the allocation , by: 1) .

1. ∀ ∈  such that ∩ , = ∅, , = , 2. ∀ ∈ {1, … , }, , ( ) = ( ), 3. ∀ ∈ {1, … , -1}, , ( ) = ( ), and
, ( 1 ) = ( 1 ) if ( ) = ( 1 ) ( 1 ) if ( ) = (
The construction of , works as follows. We call outsider (resp. insider) any couple with no (resp. one) partner involved in , . For each insider couple, we call active (resp. inactive) the partner (resp. not) involved in , . The allocation , 1. keeps all outsider couples at their current bundle assigned by , 2. assigns each active partner her priority good in , 3. assigns each inactive partner the same good as in , maybe except for the first one. The partner 1 of the first active individual 1 keeps the same good as in if the last active partner points to 1 . Otherwise, 1 gets her partner's current good ( 1 ).

The definitions of a -TTC together with its associated allocation are illustrated in Example 7. The cycle , 0 = {1, 4} is depicted in Figure 1 (a). In this figure, individuals are circled, while goods are in squares. A link between an individual and a square indicates the good currently owned by the individual. Moreover, we indicate for each individual her priority good for the set of goods which is available for trade. Arrows from circle 1 to circle 4 and from circle 4 to circle 2 express that individual 1 (resp. 4) points to individual 4 (resp. 2). Trades make individual 1 getting good 4 and individual 4 getting good 2. Since individual 2 is left without good, she is given her partner's current good, that is good 1 (as shown by the dashed arrow between circles 2 and 1 in Figure 1(a)). The resulting allocation , 0 = (4, 1, 3, 2) is depicted in Figure 1(b) 1 2

1 2

1 = 4 2 = 3 3 4 3 4 3 = 2 4 = 2 (a) , 0 = {1, 4} 1 2 4 1 3 4 3 2 (b) , 0 = (4, 1, 3, 2)
Figure 1: and its associated allocation MTTC consists in forming successive -TTC, starting with = , and continuing with nested subsets of goods and individuals, some goods being definitely assigned on the way. Formally, the algorithm operates as follows:

Define = 1 and = 1 .

Stage 1: Form a 1 -TTC w.r.t. 0 and write 1 = 1 , 0 .

• Construct the allocation 1 = 1 associated with 1 .

• Remove from 1 the set 1 = { ∈ 1 ∶ = ( 1 ) for some ∈ 1 }, and define 2 = 1 ∖ 1 .

• Remove from 1 all individuals in 1 , and define 2 = 1 ∖ 1 .

• For each ∈ 2 with ∈ 1 , the preference of over remaining bundles is updated as follows: we define ( 2 ) as a good in 2 which maximizes in the subset of allocations Σ 2 = { ∈ Σ ∶ ( ( ), ( )) ∈ {( , 1 ( ), ( 1 ( ), ))} with ∈ 2 }.

Stage s: Form a -TTC w.r.t. -1 and write = , -1 .

• Construct the allocation = associated with .

• Remove from the set = { ∈ ∶ = ( ) for some ∈ }, and define +1 = ∖ .

• Remove from all individuals in , and define +1 = ∖ .

• For each ∈ +1 with ∈ ∪ 1≤ ′ ≤ ′ , the preference of over remaining bundles is updated as follows:

( +1 ) is a good in +1 which maximizes in the subset of allocations Σ +1 = { ∈ Σ ∶ ( ( ), ( )) ∈ {( , ( ), ( ( ), ))} with ∈ +1 }. at each stage . Since is finite, and since at each step, at least one individual receives her final good, the algorithm terminates in ≤ steps. The final outcome is defined as follows: ∀ = { , } with ∈ , ∈ ′ , and < ′ , is the bundle in {( ′ ( ), ( )), ( ( ), ′ ( ))} which maximizes in Σ ′ +1 . It is obviously seen that is individually rational for the active member in each couple. However, as shown below in Example 8, may fail individual rationality for the inactive member in some couple.

This algorithm is close in spirit to TTC. It consists of forming successive trading cycles, starting with the whole sets of goods and individuals. It continues with nested subsets of goods and individuals, some goods being definitely assigned on the way. At the first stage, each individual (with weakly lexicographic preferences) points to the individual owning 's priority good. This allows forming a cycle where each couple has at most one active partner. This cycle prescribes an allocation that assigns each active partner to her priority good, and each inactive partner her initial good, except the first one, who may receive her partner's initial good. Active partners and assigned priority goods are removed from the market. An important feature is the preference update, whereby inactive partners borrow in the next stages their partner's preference over allocations where the couple keeps the first assigned priority good. The same procedure is applied in all subsequent stages. Hence, every couple is involved in two trading cycles, one per partner. The first active partner "dictates" her preference to the second active partner. Thus, both assigned priority goods refer to the same partner's well-being. Once all goods are allocated, the final allocation is obtained by (re)allocating the two priority goods among the two partners so as to maximize the satisfaction of the first active one.

For an illustration, consider the following example.

Example 8. Consider  = (4, , ) with  = {{1, 2}, {3, 4}}, and ∈ Π such as below:

⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 2 3 4 (3, 4) (3, 1) (2, 1) (1, 2) (2, 4) (2, 3) (3, 2) (3, 2) (4, 1) (3, 4) (2, 4) (4, 2) (3, 1) (2, 4) (1, 3) (4, 1) (2, 3) (4, 1) (4, 1) (3, 4) (2, 1) (1, 2) (1, 2) … … … … ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
The priority goods w.r.t. are 1 ( ) = 4, 2 ( ) = 3, 3 ( ) = 2 and 4 ( ) = 2 respectively. Hence, as in Example 7, 1 = {1, 4} and ′1 = {2, 3} are the twow.r.t. 0 which can be formed at stage 1. If 1 = {1, 4} is formed, the algorithm terminates in 2 stages. Stage 1: All goods being available, and starting from 0 , individual 1 points individual 4, who owns the priority good of the individual 1 ( 1 ( ) = 4), while individual 4 points the partner of individual 1 who has her priority good 2 ( 4 ( ) = 2). This is shown in Figure 1(a). Therefore, 1 = (4, 1, 3, 2), depicted in Figure 1(b).

Stage 2:

The remaining sets of individuals and goods are respectively 2 = {2, 3} and 2 = {1, 3}. Since individual 1 has traded in stage 1, her partner 2 borrows individual 1's preference and acts accordingly. Hence, individual 2 claims for goods (3, 4), which is the best bundle for individual 1 among those assign good 4 to the couple. Thus 2 = 3 and 2 points to individual 3 who currently owns good 3, as shown in Figure 2(a). Similarly, since individual 3's partner 4 prefers (1, 2) to (3, 2), we have 3 = 1 and individual 3 points to individual 2, who currently owns good 1. This gives 2 -= 2 = {2, 3}, together with the allocation 2 = (4, 3, 1, 2), as depicted in Figure 2(b).

Finally, since swapping goods 3 and 4 is the best option for individual 1, while swapping goods 1 and 2 is not beneficial to individual 4, the final outcome is = (3, 4, 1, 2), as shown in Figure 2(c).

1 2 4 1 2 = 3 3 4 3 2 3 = 1 (a) 2 = {2, 3} 1 2 4 3 3 4 1 2 (b) 2 = (4, 3, 1, 2) 1 2 3 4 3 4 1 2 (c) = (3, 4, 1, 2) Figure 2: MTTC Algorithm
Note that is individually rational. However, this is not always the case. If ′1 = {2, 3} is formed first instead of 1 = {1, 4}, we get 2 = 2 = {1, 4}, and ′1 = (1, 3, 2, 4). Individuals 1 and 4 both point to individual 1, leading to ′2 = {1} and ′2 = (1, 3, 2, 4). Since getting good 1 (resp. keeping good 2) is the best option for individual 2 (resp.

3), the final outcome is ′ = (3, 1, 2, 4). Observe that ′ is individually rational for individuals 1,2 and 3 but not for individual 4, who is here the inactive member of couple {3, 4}. Proposition 6. In all  = ( , , ) with ∈ Π 0 , every outcome of MTTC is a weak equilibrium allocation.

We showed above that under couple responsiveness, a strong equilibrium may not be reachable by TTC. Similarly, under weakly lexicographic preferences, a weak equilibrium may not be reachable by MTTC. This is illustrated by Example 9.

Example 9. Let  = (6, , ) where  = {{1, 2}, {3, 4}, {5, 6}}, and where ∈ Π ∩ Π is such as below, where ( , ) stands for any ranking of bundles ( , ) with ∈ .

⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 , 2 3 , 4 5 , 6 (3, 2) (2, 4) (1, 6) (3, 5) (1, 4) (5, 6) (3, 1) (3, 4) ( ∖{1, 5}, 6) (1, 2) … … (1, ∖{2}) … ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
Since 3 ( ) = 4 ( ) = 4 and 5 ( ) = 6 ( ) = 6, we can assume w.l.o.g. individual 4 gets good 4 in the first stage and individual 6 gets good 6 in the second stage of the algorithm. The resulting allocation 2 at the second stage coincides with the initial allocation 0 = (1,2,3,4,5,6). Goods 4 and 6 are removed at the second stage of the algorithm. Hence 3 = {1, 2, 3, 5}, 3 = {1, 2, 3, 5}. In the third stage, = {1, 3} is the unique 3 -TTC w.r.t. 2 . Now consider = (3, 2, 1, 4, 5, 6) and = (2, 3, 2, 2, 1, 1). Check that ( , ) ∈ () while cannot be obtained as final outcome of the algorithm.

Similar to TTC being manipulable (under couple responsive preferences), MTTC is manipulable (under weakly lexicographic preferences), as shown by Example 10.

Example 10. Let  = (6, , ) where = {{1, 2}, {3, 4}, {5, 6}} and is given by:

⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 , 2 3 , 4 5 , 6 (5, 3) (1, 4) (1, 6) ( ∖{5}, 3) (1, ∖{4}) (5, 6) (1, 2) (2, .) … … (3, 4) … ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
Obviously, can be completed so as to become weakly lexicographic.

Check that = (2, 3, 1, 4, 5, 6) is the unique outcome of MTTC algorithm. If individual 1 reports any (weakly lexicographic) preference with (5, 3) 1 (5, ∖{3}) 1 (1, 2) 1 ... where instead of her true preference, one gets ′ = (5, 3, 2, 4, 1, 6) as final outcome. Since ′ 1 , strategy-proofness is violated.

As for responsiveness, weakly lexicographic preferences do not take into account the potential complementarity that may exist between goods. However, since responsiveness and the weakly lexicographic properties are logically independent, we cannot argue that the existence of one type of equilibrium requires stronger assumptions than the existence of the other. Observe that individual rankings of bundles are needed as informational inputs for running MTTC (under weakly lexicographic preferences). Since submitting preference lists over goods is enough for running TTC (under couple responsive preferences), and since couple responsiveness does not guarantee the existence of a weak equilibrium, one can argue that existence with income transferability requires more information than nontransferability.

Maximal domains

A preference domain  ⊂ Π is called maximal for some property if is satisfied at all profiles selected from , and is violated when  is enlarged with any preference showing a minimal departure from . The notion of minimal departure is the one retained in [START_REF] Doğan | The core of shapley-scarf markets with couples[END_REF] for Shapley-Scarf markets with joint preferences.

Given two linear orders and ′ over , define -index of by ( ) = min{ ( , ′ ) ∶ ′ satisfies }, where stands for the Kemeny distance between linear orders. Hence, the -index of is the minimal number of pairwise comparisons of bundles to be reverted for to satisfy . The minimal departure from property is associated with an -index 1. If stands for the (weakly) lexicographic property, the -index is called the (weakly) lexicographic index. Similarly, if stands for the responsiveness property, the -index is called the responsiveness index. [START_REF] Doğan | The core of shapley-scarf markets with couples[END_REF] (Proposition 3, page 65) prove that the -core may be empty in some market where all preferences but one are lexicographic, and the non-lexicographic preference has an index 1. Since by Proposition 3.2, the -core always contains the set of weak equilibrium allocations, a weak equilibrium may fail to exist under these preferences.

Now consider profile below giving joint preferences of two couples:

⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 , 2 3 , 4 (2, 3) (4, 3) (4, 3) (4, 2) (3, 1) (4, 1) (1, 3) (1, 3) (4, 1) (2, 3) (2, 1) (3, 4) (1, 2) … … ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
Preferences of individuals 1 and 2 have lexicographic index 1, while preferences of 3 and 4 are lexicographic. However, preferences of 1 and 2 being weakly lexicographic, a weak equilibrium exists by Proposition 6. As a consequence, the domain of lexicographic preferences is not maximal for the existence of weak equilibria and -core. Proposition 7 shows that, provided a sufficient number of goods, the weakly lexicographic domain is maximal for the existence of weak equilibrium.

Proposition 7. If ≥ 8, Π 0 is maximal for the existence of weak equilibrium.

We conclude this section by showing that the responsive domain is maximal for the existence of strong equilibria in markets with at least eight goods. Proposition 8. If ≥ 8, Π is maximal for the existence of strong equilibria.

Further comments

We conclude this paper with several additional comments. The first one is that our model can be extended to arbitrary coalition structures, and all results can be adapted against a significant notational cost.

Second, we already mentioned that alternative equilibrium concepts could be considered. We briefly define two of them, each describing a specific type of cooperation within couples. Call (resp. weak) selfish equilibrium an 2tuple ( , ) such that ∀ ∈ , ∈ arg max ( ) ( ) (resp.

∈ arg max ( ) ( ) ). Selfish equilibria pertain to the lowest degree of cooperation, since each partner maximizes her own well-being among bundles affordable for the couple. Another equilibrium concept, called coordinated equilibrium, is defined as follows. Given an allocation and a price vector , define the strong ( , )-restricted budget set for individual (with partner ) is the subset of allocations ( , ) = { ′ ∈ ( ) ( ) ∶ ′ ( ) = ( )}. The weak ( , )-restricted budget set is similarly defined. A ( , )-restricted budget set for contains all affordable allocations which endow her partner with the same good as in . The strong (resp. weak) best response of to ( , ) is the set Φ ( , ) = arg max ( , ) . (resp. Φ ( , ) = arg max ( , ) ). A (resp. weak) coordinated equilibrium is a 2-tuple such that ∀ ∈ , ∈ Φ ( , ) (resp.

∈ Φ ( , )). Hence, coordinated equilibria relate to a Nash-type coordination scheme within couples. A detailed analysis of selfish and coordinated equilibria can be found in [START_REF] Aslan | Essays on allocation procedures of indivisibles[END_REF]. In particular, one can show that couple responsiveness is sufficient for the existence of strong selfish and strong coordinated equilibria. Moreover, couple responsiveness combined with the weakly lexicographic property is sufficient for the existence of weak coordinated equilibria, while a weak selfish equilibrium may fail to exist under lexicographic preferences.

Another comment is about the relation between markets with couples and markets with multiple types of indivisible goods. Our model is closely related to another type of market, where individuals are initially endowed with 2 goods, each being assigned to a specific purpose. We refer to these markets as markets for posted goods. Formally, let = {1, … , } be the set of individuals, and = {1, … , } ∪ {1 ′ , … , ′ } be the set of goods. Define ℍ = {( , ) ∈ × ∶ ≠ }. An element ( , ) of ℍ is interpreted as a bundle where good used for purpose 1 and good for purpose 2. Each individual has preferences represented by a linear order over ℍ. A profile is an -= ( ) ∈ . An allocation is a mapping from to ℍ. We define the initial allocation 0 by 0 ( ) = ( , ′ ) for all ∈ . A market for posted goods is defined as a triple = ( , , ). A (resp. strong, weak) equilibrium is a 2-tuple ( , ) where is an allocation and ∈ ℝ 2 + such that ∀ ∈ , the bundle ( ) ∈ ℍ is maximal for in the (resp. strong, weak) budget set defined by . For an illustration, consider individuals as airline companies. In a market with couples, a couple is a consortium of two companies, each owning one plane and all planes operating on the same route. In a market for posted goods, each company owns two planes, each operating on a specific route. Each plane has a range compatible with every route. Companies can exchange planes, while its two lines must be operated. It should be obvious that markets with couples having joint preferences and markets for posted goods are formally equivalent. They only differ in the interpretation of allocations. As a consequence, both markets have the same equilibrium sets. Moreover, responsiveness and the lexicographic structure formally equivalent for both. Therefore, all results below can also be stated for markets for posted goods. In addition, income transferability seems as plausible in markets for posted goods. This motivates further the interest of this assumption, beyond the fact that it can be observed in real job mobility procedures.

If partners' preferences are different, the two markets are no longer formally equivalent. Nonetheless, they can be related in terms of equilibrium existence. Say that a market with couples  and a market  for posted goods are equilibrium-equivalent if () = ∅ ⇔ () = ∅. One of the two implications is easily established. Let ( , ) be an equilibrium (weak or strong) of  = ( , , ). Then one can find a market with couples  also admitting ( , ) as equilibrium. To see why, define  = (2 , , ) where  = {{ , ′ } ∶ ∈ {1, … , } and ′ ∈ {1 ′ , … , ′ }}, and is a profile of 2 linear orders over such that ∀ ∈ {1, … , }, = . Moreover, initially assign good to ∈ {1, … , } and good ′ to individual ′ ∈ {1 ′ , … , ′ }. Since ∀ ∈ {1, … , }, the bundle ( ) is the unique best element of 's budget set for , the bundle ( ) is budget-constrained Pareto optimal for couple { , ′ }. Therefore ( , ) is an equilibrium for .

The reverse implication is more problematic. Indeed, the Pareto criterion generates for the two partners' preferences a quasi-ordering over bundles. Hence, there is no obvious way to define preferences in a related market for posted goods. If preferences are linear orders consistent with the Pareto quasi-ordering, it is easy to find examples where an equilibrium allocation of a market with couples is not an equilibrium allocation in the market for posted goods. However, if ( , ) is an equilibrium for  where for all couples { , ′ }, the bundle ( ( ), ( ′ )) is uniquely top-ranked by partner among all affordable bundles, it is obviously checked that ( , ) is an equilibrium for the market  where individual preferences over bundles are given by 's ones in . Actually, all of our results show the existence of such equilibria in . Therefore, they can be restated for markets for posted goods even without assuming joint preferences.

Shapley-Scarf markets with couples and markets for posted goods both differ from markets for multiple types of goods [START_REF] Konishi | On the shapley-scarf economy: the case of multiple types of indivisible goods[END_REF][START_REF] Cechlárová | On the complexity of the shapley-scarf economy with several types of goods[END_REF], and from markets where individuals trade multiple indivisible goods [START_REF] Sönmez | Strategy-proofness and essentially single-valued cores[END_REF][START_REF] Pápai | Strategyproof exchange of indivisible goods[END_REF]. To pursue the illustration above, in a market for multiple types of goods (hereafter KQW markets), individuals are airline companies, each owning one landing slot in two different airports. In contrast with the case of posted goods, slots can be traded only if they relate to the same airport. If all companies own two or more slots in the same airport, we get a market for multiple goods.

A KQW market (with two types of goods) is defined as a triple  = ( , 1 × 2 , ), where is the cardinality of the set of individuals , 1 and 2 are two sets of goods ( being interpreted as the set of goods with type = 1, 2.) Each individual initially owns exactly one good of each type, and has preferences over bundles of goods defined as a linear order over 1 × 2 . A profile is an -tuple = ( ) ∈ of linear orders. An allocation is a one-to-one mapping from to 1 × 2 . A (resp. strong, weak) equilibrium is a 2-tuple ( , ) such that ∀ ∈ , the bundle ( ) ∈ 1 × 2 is maximal for in the subset of 1 × 2 containing all (resp. strong, weak) budget-feasible bundles w.r.t. . Since only type-wise trades are allowed in KQW markets, they are not formally equivalent to markets with couples.

Still, it is rather easy to show that given any KQW market  = ( , 1 × 2 , ), there exists a market with couples  = (2 , , ) that is equilibrium-equivalent to . To see why, let 1 = { 1 , … , } and 2 = { 1 , … , }, and consider w.l.o.g. the initial allocation 0 where 0 ( ) = ( , ) for all ∈ {1, … , }. Now define the market with couples  (with initial allocation ( 0 ( ), 0 ( ′ )) = 0 ( ) for all ) as follows:  = {{ , ′ } ∶ ∈ {1, … , }}, and profile = ( 1 , 1 ′ , … , , ′ ) satisfies for all ∈ {1, … , } the following conditions: -= ′ , -∀( , ′ ), ( , ′ ) ∈ ∩ [ 1 × 2 ], ( , ′ ) ( , ′ ) iff ( , ′ ) ( , ′ ), -∀( , ′ ) ∈ ∩ [ 1 × 2 ], ∀( , ′ ) ∉ ∩ [ 1 × 2 ], ( , ′ ) ( , ′ ), -∀( , ′ ), ( , ′ ) ∉ ∩ [ 1 × 2 ], arbitrarily ranks ( , ′ ) and ( , ′ ). Given any allocation in , define allocation in  by ∀{ , ′ } ∈ , ( ( ), ( ′ )) = ( ). By definition of , for all , ( ) is the unique top-ranked bundle in 1 × 2 for in some budget set ( ) = {( , ) ∈ 1 × 2 ∶ ( ) ≤ ( ) and ( ) ≤ ( )} if and only if ( ( ), ( ′ )) is the unique bundle in top-ranked by in the budget set ( ) = {( , ) ∈ ∶ ( ) ≤ ( ) and ( ) ≤ ( )}. Therefore, ( , ) ∈ () iff ( , ) ∈ (). The same argument holds for weak equilibria.

To conclude on this point, although markets for couples, markets for posted goods and KQW markets describe neither the same preference structure nor the same type of trade, existence results for one type of market allow to get similar existence results for the other two types.

Finally, we suggest two open research questions. We have shown that in the presence of couples, multiple strong and weak equilibria allocations may exist. This raises the following questions. Can one characterize the sets of trading cycles that are associated with strong equilibrium allocations in markets with responsive preferences? In a similar vein, can one characterize the sets of trading cycles that are associated with strong equilibrium allocations in markets with weakly lexicographic preferences? 3,1) (2,6) (6,2) (1,4) (1,4) (1,6) (1,2) (5,4) (5,6 Moreover, since 3 + 4 < 1 + 6 , partners in 2 get their first-best budget-feasible bundle. Furthermore, partners in 3 also get their first-best budget-feasible bundle. This ensures ( , ) ∈ (). Now if ( , ′ ) ∈ () for some ′ , strong budget feasibility requires ′ 1 = ′ 3 = ′ 5 and ′ 2 = ′ 4 = ′ 6 . Moreover, ∈  2 ( ′ ) implies ′ 1 > ′ 3 , in contradiction with strong budget feasibility. Observe that ( ′ , ) ∈ () where ′ = (3, 4, 1, 6, 5, 2) and = (3, 2, 3, 2, 1, 2). Thus ∈ ()∖ (). Finally, pick  = (4, , ) where  = { 1 , 2 } = {{1, 2}, {3, 4}}, and ∈ Π ∩ Π such as below:

⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝
⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 , 2 3 , 4 (2, 1) (4, 3) (2, 3) 2) (2, 4) (4, 1) (1, 2) (3, 4) … … ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
It is easily checked that ( 0 , ) ∈ () where = (1, 2, 1, 2). Since = (2, 1, 4, 3) ∈ 1 ( ′ ) ∩ 2 ( ′ ) for all price vectors ′ , and since 0 for all , 0 ∉ (). Thus 0 ∈ ()∖ (). This proves assertion 2.

A.2. Proof of Proposition 2

Assertion 1: Consider  = (4, , ) where  = { 1 , 2 } = {{1, 2}, {3, 4}}, and where is any coalition responsive and weakly lexicographic profile having the form

⎛ ⎜ ⎜ ⎜ ⎝ 1 2 3 4
(2, 1) (1, 2) (4, 3) (3, 4) (1, 2) (2, 1) (3, 4) (4, 3)

… … … … ⎞ ⎟ ⎟ ⎟ ⎠ Check that ( , ) ∈ () ∩
() where = (2, 1, 4, 3) and = (2, 2, 1, 1). Since 0 for = 2, 4, is not individually rational.

Assertion 2: Let ( , ) ∈ (). If there exists = { , } ∈  such that ( , ) , ∈ Π implies that ( , ) . Since 0 ∈ ( ), this contradict ∈  ( ). The same argument also applies for ( , ) ∈ ().

A.3. Proof of Proposition 3

Assertion 1: Consider  = (4, , ) where  = {{1, 2}, {3, 4}}, and is any coalition responsive and weakly lexicographic profile having the form

⎛ ⎜ ⎜ ⎜ ⎝ 1 , 2 3 , 4 (2, 1) (4, 3) (1, 2) (3, 4) … … ⎞ ⎟ ⎟ ⎟ ⎠

  is Pareto optimal for all  = ( , , ).

Example 7 .

 7 Let  = (4, , ) with  = {{1, 2}, {3, 4}} and ∈ Π . Assume that priority goods for are 1 ( ) = 4, 2 ( ) = 3, 3 ( ) = 2 and 4 ( ) = 2. This allows to build the two -(w.r.t. 0 ) , 0 = {1, 4} and ′ , 0 = {2, 3}. Note that the set of goods traded through , 0 does not coincide with the set of involved individuals. This happens since the last active individual in the cycle points to the good owned by the partner of the first active individual.

  If ( 1 , ) ∈ (), then one must have 8 + 6 > 5 + 6 and 7 + 5 > 7 + 8 , which is impossible. Similarly, -if ( 2 , ) ∈ (), one must have 8 + 4 > 7 + 8 and 3

This is no longer true if indifference is allowed(Emmerson, 1972). With preferences as weak orders,[START_REF] Wako | A note on the strong core of a market with indivisible goods[END_REF] shows that strict core is included in the set of competitive allocations.[START_REF] Wako | Some properties of weak domination in an exchange market with indivisible goods[END_REF] shows that every non-competitive allocation is weakly dominated by some competitive allocation and the non-empty strict core is the unique von Neumann-Morgenstern solution.

Further properties of Shapley-Scarf markets may be found in[START_REF] Bird | Group incentive compatibility in a market with indivisible goods[END_REF],[START_REF] Sönmez | Implementation in generalized matching problems[END_REF],[START_REF] Abdulkadiroğlu | House allocation with existing tenants[END_REF][START_REF] Sönmez | Strategy-proofness and essentially single-valued cores[END_REF][START_REF] Sönmez | Strategy-proofness and essentially single-valued cores[END_REF].

The reader may refer to[START_REF] Roth | Two-sided matching: A study in game-theoretic modeling and analysis[END_REF],[START_REF] Sasaki | Two-sided matching problems with externalities[END_REF],[START_REF] Dutta | Stability of matchings when individuals have preferences over colleagues[END_REF],[START_REF] Roth | The redesign of the matching market for american physicians: Some engineering aspects of economic design[END_REF],[START_REF] Cantala | Matching markets: the particular case of couples[END_REF],[START_REF] Klaus | Stable matchings and preferences of couples[END_REF],[START_REF] Echenique | A solution to matching with preferences over colleagues[END_REF],[START_REF] Klaus | Some things couples always wanted to know about stable matchings (but were afraid to ask)[END_REF],[START_REF] Hafalir | Stability of marriage with externalities[END_REF],[START_REF] Mumcu | Stable one-to-one matchings with externalities[END_REF],[START_REF] Bando | Many-to-one matching markets with externalities among firms[END_REF],[START_REF] Pycia | Stability and preference alignment in matching and coalition formation[END_REF],[START_REF] Bando | A modified deferred acceptance algorithm for many-to-one matching markets with externalities among firms[END_REF],[START_REF] Pycia | Matching with externalities[END_REF],[START_REF] Fisher | Matching with aggregate externalities[END_REF]. See also[START_REF] Bando | Two-sided matching with externalities: A survey[END_REF] for a recent survey.

[START_REF] Hong | Core and top trading cycles in a market with indivisible goods and externalities[END_REF], each individual cares about others only when comparing allocations assigning her to the same good. They show that with this type of egocentric preferences, the properties of the TTC algorithm essentially remain satisfied. In[START_REF] Massand | Graphical one-sided markets[END_REF], an individual's well-being utility depends on the intrinsic valuation of the assigned good as well as the allocation within the individual's local neighbourhood, specified by means of a weighted graph.

As a consequence, we assume that no individual is sensitive to what prevails for other couples.

[START_REF] Klaus | Stable matchings and preferences of couples[END_REF] show that couple responsiveness (which they call responsiveness) plays an important role in the existence of stable matchings in two-sided markets with couples. See also[START_REF] Klaus | Some things couples always wanted to know about stable matchings (but were afraid to ask)[END_REF].

[START_REF] Doğan | The core of shapley-scarf markets with couples[END_REF] show that lexicographic preferences ensure the non-emptiness of the core in a setting similar to the present one, under the assumption of joint preferences. We comment on this result below.

See Example 2 in[START_REF] Doğan | The core of shapley-scarf markets with couples[END_REF].

Observe that defining a TTC sequence requires each individual being endowed with a linear order over the goods she is assigned to. This requirement is met by couple responsiveness.

A. Appendix

A.1. Proof of Proposition 1

Assertion 1: The two profiles defined in Example 1 and Example 2 can be completed so as to get ∈ Π . Moreover, check that in Example 1, ( , ) ∈ () where = (1, 4, 3, 2) and = (1, 1, 2, 1). Similarly, in Example 2, ( , ) ∈ () where = (2, 1, 4, 3) and = (1, 1, 1, 1). Therefore, assertion 1 is shown by Example 1 and Example 2.

Assertion 2: Pick  = (6, , ), where  = { 1 , 2 , 3 } = {{1, 2}, {3, 4}, {5, 6}}, and ∈ Π ∩ Π such as below Check that ( 0 , ) ∈ () where = (2, 1, 2, 1). Let ′ = (2, 1, 4, 3). Since is a ( ′ , 0 )-blocking coalition, 0 ∉ Ω () ∪ Ω ().

Assertion 2: Pick ( , ) ∈ (), and suppose ∉ Ω (). Thus, there exist ⊆ and ′ ∈ Σ such that ∪ ∈ ′ ( ) = for all ∈ , and ∀ ∈ , ′ and ( ) ⊆ . By definition of (), we have

, in contradiction with ∪ ∈ ′ ( ) = . Assertion 3: Consider  = (4, , ) where  = {{1, 2}, {3, 4}}, and has the form

() where = (3, 1, 2, 4) and = (1, 1, 1, 1). Check that = {1, 3} is a ( ′ , )-blocking coalition for any ′ ∈ {(3, 2, 1, 4), (3, 4, 1, 2)}. Thus ∉ Ω ().

A.4. Proof of Proposition 4

Let ( , ) ∈ () and suppose there exist ′ ∈ Σ and ⊆ such that ′ for all ∈ , while all ∈ ∖ are indifferent between and ′ . Since is a profile of strict preferences, ′ ( ) = ( ) for all ∈ ∖ . Moreover, by definition of a weak equilibrium,

for all ∈ . By weak budget feasibility,

A.5. Proof of Proposition 5

Consider a market  = ( , , ) with ∈ Π . By definition of Π , each individual in = { , } can be assigned a vector of linear orders

For each ∈ , pick a specific partner ∈ and define profile ̃ over by ∀ ∈ , ∀ ∈ , ̃ = . Now consider the outcome of the TTC algorithm applied to  = ( , , ̃ ). For each ∈ , define

A.6. Proof of Proposition 6

Define the price vector by: for all ∈ , = 1 2 ⇔ ∈ , where 1 ≤ ≤ . First, observe that + = ( ) + ( ) for all { , } ∈ : makes all weak budget constraints binding. To see why, pick any = { , }, and suppose w.l.o.g. that ∈ and ∈ ′ , with < ′ . Suppose first that ( ) = . By definition of , = ( ) = 1 2 , and = ′ ( ) = 1 2 ′ . Since ∈ {( ′ ( ), ( )), ( ( ), ′ ( ))}, we get + = ( ) + ( ) = 1 2 + 1 2 ′ . Similarly, suppose that ( ) = . Since ∈ , then = ( ) = 1 2 , and = ′ ( ) = 1 2 ′ , and the same conclusion follows.

Suppose that ( , ) ∉ (). Thus, there exist and an allocation ∈ ( ) ( ) such that and .

Suppose that ∈ and ∈ ′ , with ′ > . By construction, ( ) ∈ { ( ), ( )}. Since the outcome is individually rational for the active partner in each couple, and since preferences are weakly lexicographic in restriction to individually rational bundles, implies that either ( ) ∈ { ( ), ( )} or there exists ∉ with ∈ { ( ), ( )}. In the latter case, we get ≥ 1 2 -1 ≥ 1 2 + 1 2 ′ = + , in contradiction with ∈ ( ) ( ). In the former case, since gets at stage ′ the priority good in ′ according to 's preference (given that already owns ( )), there must exist ′ ∉ ′ with ′ ∈ { ( ), ( )}. Thus, ( ) + ( ) ≥ 1 2 + 1 2 ′ -1 > 1 2 + 1 2 ′ = + , again in contradiction with ∈ ( ) ( ). This completes the proof.

A.7. Proof of Proposition 7

Consider  = (8, , ) where 1 = {1, 2}, 2 = {3, 4}, 3 = {5, 6}, 4 = {7, 8} and is given by:

observe that 1 and 2 can be completed so as to have a weakly lexicographic index 1 (in restriction to bundles ranked above the initial bundle (1, 2)). Moreover, for any > 8, we can extend by adding up couples where both partners rank their initial endowment first without harming the argument. Now, by Proposition 2.2, ( ′ ) ⊆ Σ( 0 , ). The reader will check that Σ( 0 , ) = { 0 , 1 , 2 , 3 }, where 1 = (5, 2, 3, 4, 1, 6, 7, 8), 2 = (1, 4, 3, 2, 5, 6, 7, 8), and 3 = (1,2,3,7,4,6,5,8).

Hence 5 > 7 > 5 , which is impossible. Similarly, ( 2 , ) ∈ () implies 5 > 1 > 5 , and if ∈ { 0 , 3 }, ( , ) ∈ () implies 4 > 2 > 4 . This shows that () = ∅, and the proof is complete.

A.8. Proof of Proposition 8

Consider  = (8, , ), where 1 = {1, 2}, 2 = {3, 4}, 3 = {5, 6}, 4 = {7, 8}, and is given by:

Clearly, 1 and 2 can be completed so as to have a responsiveness index 1 (in restriction to bundles ranked above the initial bundle (1, 2)). Moreover, as in the proof of Proposition 7, we can extend to any > 8 by adding up couples where both partners rank their initial endowment first without harming the argument. Observe that  is very similar to the market considered in Example 3. By Proposition 2.2, () ⊆ Σ( 0 , ). It is easy to check that Σ( 0 , ) = { 0 , ..., 4 } where 1 = (1, 4, 3, 2, 5, 6, 7, 8), 2 = (5, 2, 3, 4, 1, 6, 7, 8), 3 = (1, 2, 3, 7, 4, 6, 5, 8), 4 = (5, 4, 3, 2, 1, 6, 7, 8). By the same argument as in Example 3, we get ∈ () only if = 4 . If ( 4 , ) ∈ (), strong budget feasibility implies that 5 ≤ 1 . Thus (5, 2) ∈ 1 ( ), while (5, 2) 1 (5, 4) and (5, 2) 2 (5,4). This contradicts 4 ∈  1 ( ). Therefore () = ∅, and the proof is complete.