Nathanaël Gross-Humbert

Nawal Benabbou
email: nawal.benabbou@lip6.fr

Aurélie Beynier
email: auréliebeynier@lip6.fr

Nicolas Maudet
email: nicolas.maudet@lip6.fr

Nathanael Gross--Humbert

Sequential and Swap Mechanisms for Public Housing Allocation with Quotas and Neighbourhood-based Utilities

Keywords: CCS Concepts:, Computing methodologies → Artificial intelligence Multiagent Resource Allocation, Diversity Constraints, Distributed Allocation Mechanisms, Computational Social Choice

We consider the problem of allocating indivisible items to agents where both agents and items are partitioned into disjoint groups.

Following previous works on public housing allocation, each item (or house) belongs to a block (or building) and each agent is assigned a type (e.g. ethnicity group). The allocation problem consists in assigning at most one item to each agent in a good way while respecting diversity constraints. Based on Schelling's seminal work, we introduce a generic individual utility function where the welfare of an agent not only relies on her preferences over the items but also takes into account the fraction of agents of her own type in her own block. In this context, we investigate the issue of stability, understood here as the absence of mutually improving swaps, and we define the cost of requiring it. Then we study the behaviour of two existing allocation mechanisms: an adaptation of the sequential mechanism used in Singapore and a distributed procedure based on mutually improving swaps of items. We first present the theoretical properties of these two allocation mechanisms and we then compare their performances in practice through an experimental study.

INTRODUCTION

Fairly dividing indivisible items among agents is a central problem in multiagent systems (see [START_REF] Bouveret | Fair division of a graph[END_REF], and [START_REF] Aziz | Developments in multi-agent fair allocation[END_REF][START_REF] Walsh | Fair division: The computer scientist's perspective[END_REF] for recent surveys). There are often relations connecting both items (e.g. spatial or temporal relations [START_REF] Bouveret | Fair division of a graph[END_REF]) and agents (e.g. belonging to the same hierarchical structure, or being of the same type). In public housing allocation problems for instance, agents get assigned to locations (houses), belonging to blocks (or buildings). They may of course have preferences over those locations, but importantly, this is also a setting where externalities naturally occur: it makes a difference whether your friends, for instance, get assigned to the same block as you. While agents may naturally seek the proximity of other agents of the same type (a phenomenon well-known as homophily), the objective might be opposite at the society level.

From the designer's perspective, it is indeed often desirable to preserve some diversity. In practice this can be done by imposing some quotas. Recently, several papers have studied variants of these settings (we review the most relevant literature below). However to the best of our knowledge, none of them addressed a model where agents are motivated (to some extent) by such an homophily bias, while the system has a conflicting diversity objective enforced through a system of quotas. In this paper we undertake the study of such a model. Our main research question is to understand the interplay [START_REF] Bó | Fair implementation of diversity in school choice[END_REF] or incentive incompatibility [START_REF] Aygun | College admission with multidimensional privileges: The brazilian affirmative action case[END_REF]. Ágoston et al. [START_REF] Kolos Csaba Ágoston | Stable project allocation under distributional constraints[END_REF] proposed integer programming formulations for two-sided matchings with diversity constraints and studied the stability of the solutions.

Benabbou et al. [START_REF] Benabbou | Diversity constraints in public housing allocation[END_REF] introduced the public-housing allocation problem under diversity constraints inspired from the Singaporean public housing system. Each agent has a type (or group) and each item belongs to a block. The allocation of items to agents has to respect block diversity constraints limiting the percentage of agents of a type in the same block.

The framework is very close to the one studied in this paper but the utility function studied in [START_REF] Benabbou | Diversity constraints in public housing allocation[END_REF] only considered the utility for the items (i.e. called the item-based utility in this paper). The authors describe the sequential mechanism used to allocate new apartments to residents of Singapore and study how diversity constraints impact the social welfare.

Outline of the paper

This paper is organized as follows: in Section 2, we provide a formal definition of the allocation problem under study and introduce our general utility model. In Section 3, we study the price of stability, and we show (among other things) that it is upper bounded by 2 in the general case. In Section 4, we focus on a sequential mechanism that is used to solve real public housing problems. In particular, we show that it does not always return a stable allocation, and that its worst-case error (or utility loss) is unbounded in the general case; a tight upper bound is obtained for a special case. In Section 5, we consider a distributed allocation mechanism based on mutually improving swaps of items, and we show that it always reaches a stable outcome after a finite number of steps. We also show that its worst-case error is unbounded in the general case, and a tight upper bound is obtained for a special case. We conclude with some experiments (Section 6) studying the stability and the efficiency of the existing sequential mechanism, and of the swap-deal mechanism which may possibly take place after the sequential allocation.

OUR MODEL

In this paper, we consider an allocation problem involving a set N of 𝑛 agents, partitioned into a set 𝑇 of 𝑘 types 𝑇 1 , . . . ,𝑇 𝑘 , and a set M of 𝑚 items/houses, partitioned into a set 𝐵 of 𝑙 blocks 𝐵 1 , . . . , 𝐵 𝑙 , where the inequality |N | ≥ |M| holds; note that it is a realistic assumption, especially when considering the allocation of public goods. We denote by T (𝑖) the type of any agent 𝑖 ∈ N and by B (ℎ) the block of any item ℎ ∈ M. Following the work of Benabbou et al. [START_REF] Benabbou | Diversity constraints in public housing allocation[END_REF], diversity constraints are here defined using type-block capacities/quotas 𝜆 𝑝,𝑞 ∈ N, with (𝑝, 𝑞) ∈ [𝑘] × [𝑙], such that 𝜆 𝑝,𝑞 stands for the maximum number of agents of type 𝑇 𝑝 allowed in block 𝐵 𝑞 . Without loss of generality, we assume that the inequality 𝜆 𝑝,𝑞 ≤ |𝐵 𝑞 | holds for all (𝑝, 𝑞) ∈ [𝑘] × [𝑙] since it is not possible to assign more than |𝐵 𝑞 | items in block 𝐵 𝑞 by definition. We also assume that the inequality 𝑝 ∈ [𝑘 ] 𝜆 𝑝,𝑞 ≥ |𝐵 𝑞 | holds for all blocks 𝑞 ∈ [𝑙] otherwise all allocations satisfying diversity constraints would leave some items unassigned. DEFINITION 1 (VALID ALLOCATION). An allocation 𝐴 : N → 2 M is a function that maps every agent 𝑖 ∈ N to a subset 𝐴(𝑖) ⊂ M of items. An allocation 𝐴 is valid iff:

(1) ∀𝑖 ∈ N, |𝐴(𝑖)| ≤ 1 (each agent gets at most one item).

(2) ∀𝑖, 𝑗 ∈ N, 𝐴(𝑖) ∩ 𝐴( 𝑗) = ∅ (agents do not share items).

(3) 𝑖 ∈N 𝐴(𝑖) = M (all items are assigned). Note that checking whether there exists a valid allocation or not can be performed in polynomial time using a network flow formulation [START_REF] Benabbou | Diversity constraints in public housing allocation[END_REF].

Nathanaël Gross-Humbert, Nawal Benabbou, Aurélie Beynier, and Nicolas Maudet Utility model. We assume here that the utility 𝑢 𝑖 (𝐴) of an agent 𝑖 ∈ N for an allocation 𝐴 has two components:

• 𝑢 𝐼 𝑖 (𝐴) ∈ [0, 1]: an item-based utility representing the utility derived by agent 𝑖 for the item 𝐴(𝑖) she receives. If 𝑖 does not receive any item (i.e. 𝐴(𝑖) = ∅), then 𝑢 𝐼 𝑖 (𝐴) = 0. For simplicity, we will denote by 𝑢 𝐼 𝑖 (ℎ) the item-based utility of agent 𝑖 for any item ℎ ∈ M. • 𝑢 𝑁 𝑖 (𝐴) ∈ [0, 1] ∩ Q: a neighbour-based utility which is equal to the fraction of agents of type T (𝑖) assigned to items in block B (𝐴(𝑖)). More formally, when 𝑖 gets an item, it is defined by:

𝑢 𝑁 𝑖 (𝐴) = 𝑗 ∈N: 𝐴( 𝑗) ∈B (𝐴(𝑖)) I(T (𝑖), T ( 𝑗)) |B (𝐴(𝑖))|
where I(T (𝑖), T ( 𝑗)) equals 1 if agents 𝑖 and 𝑗 have the same type, and equals 0 otherwise. If the agent 𝑖 gets no item, then 𝑢 𝑁 𝑖 (𝐴) = 0. The utility of agent 𝑖 ∈ N for allocation 𝐴 is defined by:

𝑢 𝑖 (𝐴) = 𝑢 𝐼 𝑖 (𝐴) + 𝜑 𝑖 × 𝑢 𝑁 𝑖 (𝐴)
where 𝜑 𝑖 ∈ [0, 1] is called the utility trade-off and is used to define the relative importance of the item-based utility and the neighbour-based utility. This type of utility function thus allows to model agents which are both concerned by the item they obtain, as well as their neighbourhood. In this paper, a special focus will be placed on the following two types of behaviour: item-focused and neighbour-focused agents. Agents are said to be item-focused if they only care about the item they receive. Agents are said to be neighbour-focused when they only care about the neighbourhood. More formally:

DEFINITION 2 (ITEM-FOCUSED AGENTS). Agent 𝑖 ∈ N is said to be item-focused when 𝜑 𝑖 = 0 and 𝑢 𝐼 (𝐴) ≠ 0 for some valid allocation 𝐴.

DEFINITION 3 (NEIGHBOUR-FOCUSED AGENTS).

Agent 𝑖 ∈ N is said to be neighbour-focused when 𝜑 𝑖 ≠ 0 and 𝑢 𝐼 (𝐴) = 0 for every valid allocation 𝐴.

Social welfare. When assessing the welfare of the whole society of agents, we rely on the classical utilitarian social welfare:

𝑠𝑤 (𝐴) = ∑ 𝑖 ∈N 𝑢 𝑖 (𝐴)
The house allocation problem with quotas and neighbourhood-based utilities. An instance I of this problem is a tuple I = ⟨N, M, 𝐵,𝑇 , 𝑢 𝐼 , 𝑢 𝑁 , 𝜆, 𝜑⟩ with:

• N, M, 𝐵,𝑇 as defined above,

• 𝜆 = ⟨𝜆 1,1 , • • • , 𝜆 𝑘,𝑙 ⟩ the [𝑘] × [𝑙] matrix of quotas, • 𝑢 𝐼 = ⟨𝑢 𝐼 1 , • • • , 𝑢 𝐼 𝑛 ⟩ the item-based utility profile, • 𝑢 𝑁 = ⟨𝑢 𝑁 1 , • • • , 𝑢 𝑁 𝑛 ⟩ the neighbour-based utility profile, • 𝜑 = ⟨𝜑 1 , • • • , 𝜑 𝑛 ⟩ the utility trade-offs.
Note that the problem of maximizing the utilitarian social welfare is computationally difficult since it is NP-complete even in the special case where 𝜑 𝑖 = 0 for all 𝑖 ∈ N (as proved in [START_REF] Benabbou | Diversity constraints in public housing allocation[END_REF]). It is also known that the problem of maximizing the utilitarian social welfare is NP-complete even when the number of agents of each type is at most 2 and there is only one block with 2 items while all the other blocks contain 1 item (translation of Theorem 3.2 from [START_REF] Elkind | Keeping your friends close: Land allocation with friends[END_REF] to our context). In Appendix A, we propose two mixed-integer linear programs, involving a polynomial number of variables and Manuscript submitted to ACM constraints, for the computation of a valid allocation maximizing the utilitarian social welfare and a stable valid allocation of maximum utilitarian social welfare. In this paper, we will use the same utility trade-off for all agents (simply denoted by 𝜑), as a first step in the study of the interplay between our neighbourhood-based utility model and type-block quotas.

The general case considering possibly different utility trade-offs is discussed in Appendix F.

Motivation and relation to the state of the art. Our utility model takes inspiration from the model of [START_REF] Elkind | Keeping your friends close: Land allocation with friends[END_REF] but the differences are important to notice. First, both our type and neighbourhood relations are partitions among agents ("being of the same type" or "living in the same block"), while they are arbitrary (undirected) graphs in [START_REF] Elkind | Keeping your friends close: Land allocation with friends[END_REF]: they would thus correspond to collections of cliques in their model. [START_REF] Li | Fair resource sharing and dorm assignment[END_REF] studied the dorm assignment problem where a resource is shared by several agents. They considered a similar utility function to ours where the utility of an agent 𝑖 is defined from the utility for the resource and but also from externalities depending on the other agents sharing the resource with the agent 𝑖.

In this context, [START_REF] Li | Fair resource sharing and dorm assignment[END_REF] have been interested in Pareto envy-free assignments. Now regarding the neighbour-based utility specifically, by taking the ratio of agents of the same type, our model is closer in spirit to the model of Simple Symmetric Fractional Hedonic Games (SSFHG) [START_REF] Aziz | Fractional hedonic games[END_REF] where each block can be viewed as a coalition. In such a SSFHG, each agent would assign 1 to an agent of her own type in her own block and 0 to the other agents. The game would be symmetric since for all couples of agents, both agents assign the same value to each other. However, in our context, the size of the blocks (i.e. the coalitions in a SSFHG) is fixed beforehand. This is an important difference that distinguishes our work from Fractional Hedonic Games. To compare to [START_REF] Elkind | Keeping your friends close: Land allocation with friends[END_REF] again, our setting would correspond to the binary friendship-uniform and symmetric case (instances where the preferences of an agent for the others are either 0 or 1, and they are symmetric). Unlike [START_REF] Elkind | Keeping your friends close: Land allocation with friends[END_REF], our neighbour-based utility averages the values for the other agents in the block (i.e. neighbourhood) over the size of the block. This definition is similar to Fractional Hedonic Games but differs from the friendship utility introduced in [START_REF] Elkind | Keeping your friends close: Land allocation with friends[END_REF] except when all blocks have the same size.

Finally, we note that our definition implicitly assumes that an agent counts herself among the agents of her type. To motivate our choice, consider the situation where the residents of a block have to make decisions locally to their block.

When decisions are taken from a voting rule (the majority rule for instance), an agent would want to form the largest coalition in the block with agents sharing her opinion or her preferences on possible decisions. Moreover, with this definition, the model remains consistent when an agent is alone: an agent would prefer to be alone in a small block than in a large block where it would fear to be ignored. Note that not counting the agent herself would lead to a utility of 0 for blocks with different sizes leading the agent to be indifferent between these blocks.

We conclude the section with a technical lemma on the largest utility ratio which may occur between any two valid allocations -it will be useful when analyzing the worst-case utility losses of allocation procedures. LEMMA 1. The largest utility ratio between any two valid allocations is unbounded in the general setting. When 𝜑 ≠ 0 and 𝑘 is a constant, it is upper bounded by 1+𝜑 𝜑 𝑘 and the bound is tight.

The proof is given in Appendix B. Thus the largest utility ratio between any two valid allocations grows with 𝑘 and inversely with 𝜑. For instance, in the Singapore public housing system, agents are partitioned into 𝑘 = 3 types (ethnic groups), and therefore we already know that the worst-cast error of any house allocation procedure returning a valid allocation would be upper bounded by 6 when item-based and neighbour-based utilities are given the same importance (i.e. 𝜑 = 1), whereas it would be upper bounded by 9 when the former is twice as important as the latter (i.e. 𝜑 = 0.5).

Manuscript submitted to ACM

THE PRICE OF STABILITY

A key property of an allocation is stability, whether it is such that no agent would like to deviate from the prescribed allocation. Roth suggested that stability is an important criterion to develop a successful matching mechanism [START_REF] Roth | The economist as engineer: Game theory, experimental economics and computation as tools of design economics[END_REF]. In our context, we shall concentrate on the notion of swap-stability [START_REF] Agarwal | Swap stability in schelling games on graphs[END_REF][START_REF] Massand | Graphical one-sided markets[END_REF]: it shouldn't be the case that two agents would be happy to swap their items (i.e perform a swap-deal), resulting in a valid allocation. DEFINITION 4 (IMPROVING SWAP-DEAL). Given a valid allocation 𝐴, a swap-deal among a pair of agents (𝑖, 𝑗) ∈ N × N is said to be improving if and only if 𝑢 𝑖 (𝐴 𝑖⇔𝑗 ) > 𝑢 𝑖 (𝐴) and 𝑢 𝑗 (𝐴 𝑖⇔𝑗 ) > 𝑢 𝑗 (𝐴), where 𝐴 𝑖⇔𝑗 is the allocation obtained from 𝐴 by swapping the items of agents 𝑖 and 𝑗.

Note that agents are assumed to be myopic and swap-deals only consider the immediate utility improvement. From a given valid allocation 𝐴, some improving swap-deals may lead to an invalid allocation due to type-block quotas. We thus restrict the set of swap-deals that can be applied from an allocation as follows.

DEFINITION 5 (VALID SWAP-DEAL). Given a valid allocation, a swap-deal among a pair of agents (𝑖, 𝑗) ∈ N × N is valid if and only if the resulting allocation satisfies the diversity constraints.

We can now introduce our stability notion and the price of stability. DEFINITION 6 (STABLE ALLOCATION). An allocation 𝐴 is stable if and only if there is no valid improving swap-deal from 𝐴.

The price of stability (PoS) is the largest utility ratio between any valid allocation of maximum social welfare and any valid stable allocation of maximum social welfare. More formally: DEFINITION 7 (PRICE OF STABILITY (POS)). The Price of Stability (PoS) is defined by:

𝑃𝑜𝑆 = sup I 𝑠𝑤 (𝐴 * I ) 𝑠𝑤 (𝐴 ⊤ I )
where 𝐴 * I (resp. 𝐴 ⊤ I ) is the maximum social welfare allocation that is valid (resp. valid and stable) for the instance I.

We begin our analysis with the following positive result.

PROPOSITION 1. PoS = 1 when all agents are item-focused. The same applies to neighbour-focused agents.

PROOF. Here we only need to prove that any valid allocation that maximizes the utilitarian social welfare is stable.

For the case of item-focused agents, the argument is straightforward: if two agents wish to swap and they are allowed to do so, then implementing the swap would strictly increase the utilities of both agents, while leaving the other utilities unchanged, which yields an allocation with a strictly larger utility. Therefore any valid allocation maximizing the social welfare is necessarily stable. For the case of neighbour-focused agents, it can be proved that if two agents wish to swap to increase their utilities, the utilitarian social welfare will increase by twice as much (the detailed proof is given in Appendix C). Thus any improving swap-deal would strictly increase the social welfare, which implies that any valid allocation maximizing the social welfare is necessarily stable. □

Unfortunately, this result no longer holds when we consider the general form of our utility model. In that case, it can be that two agents have an incentive to swap their items, but that the externalities on other agents make it overall damaging for social welfare, as shown in the following example.

Manuscript submitted to ACM EXAMPLE 1. Consider an instance of the problem with a set of 6 agents N = {1, 2, 3, 4, 5, 6} partitioned into 2 types

𝑇 1 = {1, 2, 3}, 𝑇 2 = {4, 5, 6}
, and a set of

6 items M = {ℎ 1 , ℎ 2 , ℎ 3 , ℎ 4 , ℎ 5 , ℎ 6 } partitioned into 2 blocks 𝐵 1 = {ℎ 1 , ℎ 2 , ℎ 3 } and 𝐵 2 = {ℎ 4 , ℎ 5 , ℎ 6 }.
Assume that type-block quotas are defined by 𝜆 𝑝,𝑞 = 3 for all (𝑝, 𝑞) ∈ {1, 2} × {1, 2}. Now set 𝜑 = 1 and define the item-based utilities as follows:

𝑢 𝐼 1 (ℎ 6 ) = 3 4 , 𝑢 𝐼 6 (ℎ 1 ) = 3 4 , 𝑢 𝐼 𝑖 (ℎ 𝑖 ) = 1 for all 𝑖 ∈ {2, 3, 4, 5}
, and 𝑢 𝐼 𝑖 (ℎ 𝑗 ) = 0 for any other agent-item pair (𝑖, 𝑗). In the optimal allocation, agents 1, 2 and 3 get assigned to ℎ 1 , ℎ 2 , and ℎ 3 respectively (in block 𝐵 1 ), while agents 4, 5, and 6 get assigned to ℎ 4 , ℎ 5 , and ℎ 6 respectively (in block 𝐵 2 ), leading to a social welfare of (0+1) + (1+1) + (1+1) + (1+1) + (1+1) + (0+1) = 10. But take agents 1 and 6: by swapping their items, they would gain 3 4 in terms of item-based utility, and lose 2 3 in terms of neighbour-based utility. Therefore, the allocation is not stable. Observe that in the resulting allocation 𝐴 1⇔6 , we have 𝑠𝑤

(𝐴 1⇔6 ) = ( 3 4 + 1 3 ) + (1+ 2 3 ) + (1+ 2 3 ) + (1+ 2 3 ) + (1+ 2 3 ) + ( 3 4 + 1 3 ) = 53 6 < 10.
On the positive side, we establish the following lower and upper bounds on the price of stability.

PROPOSITION 2. In the general case, 1.6 < 𝑃𝑜𝑆 ≤ 2.

The arguments of the proof exploit notions introduced in the next sections. For readability reasons, we thus defer the proof of this result in Appendix D.

A SEQUENTIAL MECHANISM

In this section, we analyze the sequential procedure presented in [START_REF] Benabbou | Diversity constraints in public housing allocation[END_REF] 1 which is a simplified version of the Singaporean public housing allocation process: in some random order, the agents sequentially pick the items that maximize their utilities at the time of their selection, while respecting the diversity constraints (in other words, they are not allowed to pick items in blocks where type-block quotas are reached). This mechanism, called SEQ-mechanism hereafter, is an example of a (constrained) random serial dictatorship or random priority procedure [START_REF] Abdulkadiroglu | Random serial dictatorship and the core from random endowments in house allocation problems[END_REF][START_REF] Bogomolnaia | A new solution to the random assignment problem[END_REF]. This procedure benefits from being simple and requires little information about the agents' preferences: at her turn, an agent only communicates her most preferred item among the remaining admissible items. This is undoubtedly an advantage as discussed in [START_REF] Roth | The economist as engineer: Game theory, experimental economics and computation as tools of design economics[END_REF].

However, this mechanism may "waste" some items due to diversity constraints (see Proposition 3), leading to invalid allocations. Even when it does return a valid allocation, its worst-case utility loss is unbounded in the general case, and is equal to the largest utility ratio between any two valid allocations when 𝜑 ≠ 0 and 𝑘 is a constant (see Proposition 4).

Moreover, it is not guaranteed to return a stable allocation in the general case (see Propositions 5 and 6).

PROPOSITION 3. SEQ-mechanism does not always return a valid allocation, even when all agents are neighbourfocused.

PROOF. Consider an instance with a set of 4 neighbour-focused agents N = {1, 2, 3, 4} partitioned into two types

𝑇 1 = {1, 2} and 𝑇 2 = {3, 4}, a set of 4 items M = {ℎ 1 , ℎ 2 , ℎ 3 , ℎ 4 } partitioned into two blocks 𝐵 1 = {ℎ 1 , ℎ 2 } and 𝐵 2 = {ℎ 3 , ℎ 4 }
, and the following type-block capacities: 𝜆 1,1 = 𝜆 2,1 = 1 (at most one agent per type in block 𝐵 1 ) and

𝜆 1,2 = 𝜆 2,2
= 2 (at most two agents per type in block 𝐵 2 ). When SEQ-mechanism is runned with agent order (1, 2, 3, 4), nothing prevent the first two agents from picking the two items available in block 𝐵 2 , which then forces agent 3 to pick an item in block 𝐵 1 , leaving agent 4 unassigned since her quota is reached in block 𝐵 1 . In that case, the resulting allocation is not valid as one item remains unassigned. □

Note that SEQ-mechanism always returns a valid allocation when we further assume that type-quotas satisfy inequality

𝑙 𝑞=1 𝜆 𝑝,𝑞 ≤ |𝑇 𝑝 | for all 𝑝 ∈ [𝑘]
. These inequalities are naturally verified in problems where the number of agents is very Aurélie Beynier, and Nicolas Maudet large compared to the number of items, or when the type-block quotas are somewhat proportional to the percentages of the groups in the general population (see e.g., [START_REF] Benabbou | Diversity constraints in public housing allocation[END_REF]). Now we analyze the worst-case utility loss of SEQ-mechanism, defined as the largest utility ratio between a social welfare optimum and any valid allocation returned by SEQ-mechanism. . Finally, we assume that all agents 𝑖 ∈ N \𝑇 1 1 are neighbour-focused (i.e., 𝑢 𝐼 𝑖 (𝐴) = 0 for any valid allocation 𝐴), while the remaining agents have a utility of 1 for all items (i.e., 𝑢 𝐼 𝑖 (𝐴) = 1 for any valid allocation 𝐴). Obviously, any allocation 𝐴 * assigning all the items to the agents in 𝑇 1 1 maximizes the utilitarian social welfare and we have:

𝑠𝑤 (𝐴 * ) = ∑ 𝑖 ∈𝑇 1 1 𝑢 𝐼 𝑖 (𝐴 * ) + 𝜑𝑢 𝑁 𝑖 (𝐴 * ) = ∑ 𝑖 ∈𝑇 1 1 1 + 𝜑 × 1 = 𝑘 2 × (1 + 𝜑)
Now consider some agent order such that all the agents in N \𝑇 1 are positioned before the agents in 𝑇 2 1 , which in turn are all positioned before the agents in 𝑇 1 1 . If SEQ-mechanism is applied with this agent order, then we will obtain a valid allocation 𝐴 where blocks only include one agent per type, but no agent from 𝑇 1 1 . The corresponding social welfare is:

𝑠𝑤 (𝐴) = ∑ 𝑖 ∈N\𝑇 1 1 𝑢 𝑖 (𝐴) = ∑ 𝑖 ∈N\𝑇 1 1 0 + 𝜑 × 1 𝑘 = 𝑘 2 × 𝜑 1 𝑘 = 𝜑𝑘
Thus the utility loss of SEQ-mechanism is here equal to:

𝑠𝑤 (𝐴 * ) 𝑠𝑤 (𝐴) = 𝑘 2 × (1 + 𝜑) 𝜑𝑘 = (1 + 𝜑) 𝜑 𝑘
which is exactly equal to the bound of Lemma 1. Note that it grows linearly with 𝑘, which means that it is unbounded in the general case. □

We now focus on stability.

PROPOSITION 5. For some instances, SEQ-mechanism never returns a stable valid allocation, whatever the agent order (even when there exist valid stable allocations).

PROOF. Consider an instance with a set of

4 agents N = {1, 2, 3, 4} partitioned into 2 types 𝑇 1 = {1, 2} and 𝑇 2 = {3, 4},
and a set of

4 items M = {ℎ 1 , ℎ 2 , ℎ 3 , ℎ 4 } partitioned into 2 blocks 𝐵 1 = {ℎ 1 , ℎ 2 } and 𝐵 2 = {ℎ 3 , ℎ 4 }. Assume that quotas are defined by 𝜆 1,1 = 1, 𝜆 2,1 = 2, 𝜆 1,2 = 2 and 𝜆 2,2 = 1. Now set 𝜑 = 1
and define the item-based utilities as follows:

𝑢 𝐼 𝑖 (ℎ 1 ) = 1, 𝑢 𝐼 𝑖 (ℎ 2 ) = 𝑢 𝐼 𝑖 (ℎ 3 ) = 𝑢 𝐼 𝑖 (ℎ 4 ) = 0.
75 for all agents 𝑖 ∈ 𝑇 1 , and

𝑢 𝐼 𝑖 (ℎ 3 ) = 1, 𝑢 𝐼 𝑖 (ℎ 1 ) = 𝑢 𝐼 𝑖 (ℎ 2 ) = 𝑢 𝐼 𝑖 (ℎ 4 ) = 0.
75 for all agents 𝑖 ∈ 𝑇 2 . Whatever the agent order, the sequential mechanism always returns an allocation with only one agent per type in each block since the first agent always picks the item for which she has an item-based utility of 1, which is in the block where her type-block quota is equal to 1. Such an allocation is not stable as the swap-deal among (𝑖, 𝑗) with 𝑖 ∈ 𝑇 1 and 𝑗 ∈ 𝑇 2 such that 𝐴(𝑖) ∈ 𝐵 2 and 𝐴( 𝑗) ∈ 𝐵 1 is a valid improving swap-deal. Note that it is easy to check that the resulting allocation is a valid stable allocation. □

Manuscript submitted to ACM PROPOSITION 6. SEQ-mechanism does not always return a stable allocation, even when all agents are neighbourfocused. It always returns a stable allocation when all agents are item-focused.

PROOF. Consider an instance with a set of 4 neighbour-focused agents N = {1, 2, 3, 4} partitioned into 2 types would be happy to swap their items as they would get a utility of 0

𝑇 1 = {1,
+ 𝜑 × 2/2 > 𝑢 𝑖 (𝐴).
When all agents are item-focused, the proof is straightforward: since their utilities do not depend on the choices made by the other agents, an item-focused agent can only envy an agent that picked an item before her, and therefore it cannot be the case that two item-focused agents wish to exchange their items. □

A SWAP-DEAL MECHANISM

A natural distributed approach in multiagent resource allocation is to start from a valid allocation and let the agents perform bilateral improving swap-deals until they reach a stable outcome [START_REF] Damamme | The power of swap deals in distributed resource allocation[END_REF][START_REF] Endriss | Negotiating socially optimal allocations of resources[END_REF][START_REF] Zheng | K-swaps: Cooperative negotiation for solving task-allocation problems[END_REF]. Swap-deals require very little coordination: the agents do not need to have full knowledge about the utilities and allocation of the other agents, and only two agents have to interact to make a swap. Under such swap mechanisms, the agents have an initial (valid) endowment, which reflects the current state of affairs; for the Singaporean public housing allocation problem, it could be the outcome of the sequential mechanism, as we just proved that it may not be stable (see Propositions 5 and6). Here we focus on a simple swap-deal mechanism where at each step, pairs of agents meet randomly and perform swap-deals if possible; this mechanism will be called SWAP-mechanism hereafter.

When all agents are item-focused or neighbour-focused, it follows from the proof of Proposition 1 that SWAPmechanism will converge to a stable outcome (as any improving swap strictly increases the social welfare). In the general case, our example showing that valid improving swap-deals may decrease social welfare suggests that convergence may not occur (see Example 1). Still, we can prove that the SWAP-mechanism converges to a stable outcome.

PROPOSITION 7. In the general case, SWAP-mechanism will provably reach a stable outcome.

PROOF. It can be proved that the SWAP-mechanism will always reach an equilibrium by analyzing the potential function 𝑝𝑜𝑡 defined by:

𝑝𝑜𝑡 (𝐴) = 𝑠𝑤 (𝐴) + ∑ 𝑖 ∈N 𝑢 𝐼 𝑖 (𝐴)
for any valid allocation 𝐴. To do so, consider some non-stable allocation 𝐴 and some valid improving swap-deal between two agents. Let 𝐴 ′ denote the allocation obtained after the swap-deal is performed. The variation in social welfare Δ𝑈 = 𝑠𝑤 (𝐴 ′ ) -𝑠𝑤 (𝐴) can be decomposed as follows:

Δ𝑈 = 𝜑 (Δ𝑈 1 + Δ𝑈 2 ) + Δ𝑈 3
where Δ𝑈 1 (resp. Δ𝑈 2 ) is the variation in the neighbour-based utilities of the agents who participate (resp. do not participate) in the swap-deal, and Δ𝑈 3 is the variation in the item-based utilities of the two agents participating in the swap-deal (the item-based utilities do not change for the other agents). We know that Δ𝑈 1 = Δ𝑈 2 (see the detailed proof Manuscript submitted to ACM Nathanaël Gross-Humbert, Nawal Benabbou, Aurélie Beynier, and Nicolas Maudet of Proposition 1 given in the supplementary materials), we can thus determine that:

𝑝𝑜𝑡 (𝐴 ′ ) -𝑝𝑜𝑡 (𝐴) = 𝑠𝑤 (𝐴 ′ ) -𝑠𝑤 (𝐴) + ∑ 𝑖 ∈N 𝑢 𝐼 𝑖 (𝐴 ′ ) - ∑ 𝑖 ∈N 𝑢 𝐼 𝑖 (𝐴) = Δ𝑈 + Δ𝑈 3 = 𝜑Δ𝑈 1 + 𝜑Δ𝑈 2 + Δ𝑈 3 + Δ𝑈 3 = 2(Δ𝑈 3 + 𝜑Δ𝑈 1 )
Since Δ𝑈 3 + 𝜑Δ𝑈 1 is the increase in utility of the two agents swapping, it is strictly positive (by definition of improving swap-deals). Thus, 𝑝𝑜𝑡 strictly increases after each swap-deal. Since 𝑝𝑜𝑡 is upper bounded by 3|M| and the number of valid allocations is finite, we will reach an equilibrium after a finite number of steps. □

Now we analyze the worst-case loss of SWAP-mechanism, i.e. the largest utility ratio between a social welfare optimum and any (valid) allocation returned by SWAP-mechanism.

PROPOSITION 8. The worst-case utility loss of SWAP-mechanism is unbounded in the general case. When 𝜑 ≠ 0 and 𝑘 is a constant, it reaches the upper bound of Lemma 1.

The proof of Proposition 8 is given in Appendix E. Now we analyze the price of Price of Anarchy (PoA) [START_REF] Koutsoupias | Worst-case equilibria[END_REF], which is here defined as the largest utility ratio between any valid allocation and any valid stable allocation: DEFINITION 8 (PRICE OF ANARCHY (POA)). The Price of Anarchy (PoA) is defined by:

𝑃𝑜𝐴 = sup I 𝑠𝑤 (𝐴 * I ) 𝑠𝑤 (𝐴 ⊥ I )
where 𝐴 * I (resp 𝐴 ⊥ I ) is a valid allocation (resp. valid stable allocation) of instance I which maximizes (resp. minimizes) the social welfare.

In other words, the PoA (resp. PoS) is the largest utility ratio between any social welfare optimum and one of the worst (resp. best) valid stable allocations. From Lemma 1 and Proposition 8, one can directly derive the following result on the PoA: COROLLARY 1. The PoA is unbounded in the general case. When 𝜑 ≠ 0 and 𝑘 is a constant, it is upper bounded by 1+𝜑 𝜑 𝑘 and the upper bound is tight.

EXPERIMENTS

In this section, we report the results of numerical tests aiming to evaluate the practical performances of the following allocation mechanisms:

• RSEQ: in some random order, the agents sequentially select items at random while respecting the diversity constraints. This procedure will be used as a baseline, generating random allocations using an approach similar to that of SEQ-mechanism.

• SEQ: SEQ-mechanism, as described in Section 4, where in some random order, the agents sequentially select the items maximising their utilities while respecting the diversity constraints.

• RSEQ+SWAP: the two-phase procedure consisting in first running RSEQ and then applying SWAP-mechanism.

• SEQ+SWAP: the two-phase procedure consisting in first running SEQ and then applying SWAP-mechanism. These four mechanisms are compared in terms of utilitarian social welfare in Sections 6.1 and 6.2. In Section 6.1, we consider random instances involving only 40 houses/agents, so as to be able to compute the utilitarian social welfare optimum and empirical price of stability (using the linear programs given in Appendix A). In Section 6.2, these four mechanisms are compared using a real dataset from Singapore real estate, which involves 1350 houses. In Section 6.3, we compare RSEQ+SWAP and SEQ+SWAP in terms of number of swaps that are needed to reach a stable allocation; we generate synthetic datasets of different sizes to study the impact of the number of items/agents on the number of swaps.

Empirical price of stability and comparison of allocation mechanisms

In this subsection, we consider small instances of the house allocation problem with quotas and neighbourhood-based utilities, which allows us to compute the social welfare optimum and empirical price of stability (using the linear programs given in Appendix A). More precisely, we generate 30 instances with 40 houses partitioned into 𝑙 = 5 blocks of same size, and 40 agents partitioned into 𝑘 = 5 types of same size. The type-block quotas are set to 𝜆 𝑝,𝑞 = 2 for all 𝑝, 𝑞 ∈ [START_REF] Aziz | Developments in multi-agent fair allocation[END_REF]. The item-based utilities are uniformly drawn in [0, 1]. We consider two utility trade-offs: 𝜑 = 0.5 and 𝜑 = 1.

For these instances, we have computed the empirical price of stability and it turns out to be exactly equal to 1 -in other words, the social welfare optimum is stable in every generated instance. Table 1 reports the averaged utility loss incurred by the four allocation mechanisms, i.e. the utility ratio between the social welfare optimum and the valid allocation returned by the mechanism 2 . In this table, we observe that RSEQ is outperformed by SEQ, RSEQ+SWAP and SEQ+SWAP, which have relatively similar performances on random data. More precisely, their averaged utility losses are relatively close to the empirical price of stability (when compared to that of RSEQ), and very far from the theoretical upper bound given in Lemma 1 (which is equal to 1+1 1 × 5 = 10 for 𝜑 = 1 and to 1+0.5 0.5 × 5 = 15 for 𝜑 = 0.5). However, the averaged utility losses of SEQ and SEQ+SWAP increase with 𝜑, whereas RSEQ+SWAP is relatively constant. This is mainly due to the fact that the first agents selecting items under SEQ-mechanism have no vision on their future neighbourhoods, and they are not allowed to switch items afterwards (the loss is reduced when applying SWAP right after). We consider two values of 𝜎 2 (variance): 0.01 and 1. In Table 2, we report the social welfare3 of the allocations constructed by the four allocation mechanisms, averaged over 30 runs. In this table, we observe that RSEQ is here also outperformed by SEQ, RSEQ+SWAP, and SEQ+SWAP, in terms of social welfare. The latter three allocation procedures achieve similar performances on all settings, except for Dist(0.01) where SEQ is significantly less efficient than SEQ+SWAP and RSEQ+SWAP. This is due to the fact that agents of the same type have very different item-based utility values under Dist(0.01), which makes them choose different blocks at the first iteration steps of SEQ. Interestingly though, adding SWAP after SEQ allows to significantly improve the social welfare in that case.

RSEQ

Dist(𝜎 2 )

Ethn(𝜎 2 )

𝜎 2 = 0.01 𝜎 2 = 1 𝜎 2 = 0.01 𝜎 2 =

Empirical number of swaps

Now we analyse the number of swaps needed by SWAP-mechanism to reach a stable allocation. More precisely, we compare RSEQ+SWAP and SEQ+SWAP on randomly generated instances with 𝑙 = 10 blocks of equal size, varying the number of agents/items from 100 to 1400 (in steps of 100). The set of agents is divided into 𝑘 = 3 types of size In Figure 1, we report the results obtained on 20 instances (for every value of 𝑛), and linear regressions are applied on the corresponding data points:

|𝑇 1 | = 0.74×𝑛, |𝑇 2 | = 0.13×𝑛,
• For the blue points (RSEQ+SWAP), we obtain a slope of 1.88, an intercept of -141.20 and a correlation factor of 0.998 (very high correlation); • For the red points (SEQ+SWAP), we obtain a slope of 0.08, an intercept of 43.53, and a correlation factor of 0.74 (high correlation).

Thus for both procedures, the number of swaps grows linearly with the number of agents in practice. However, SEQ+SWAP is here clearly the best procedure as it requires far fewer swaps than RSEQ+SWAP to reach a stable outcome. In fact, that number grows very moderately as the size of the instance augments.

Other experiences were made with constant numbers of agents, items and types, but varying the number of blocks. The results suggested that the number of blocks has almost no impact on the empirical time complexity of SWAP-mechanisms.

CONCLUSION

This paper investigated a model where, while agents have an homophily component in their utility function (whose relative importance is determined by a parameter 𝜑), there is a society-wide objective to promote diversity (in that case, through the use of quotas). Our work has connection to (and takes inspiration from) a number of recent works, but it is unique in the combination of these different features. We analyse the properties of two mechanisms: the sequential approach used in Singapore, and the swap-deal approach letting agents exchange their items when this is beneficial. While both exhibit the same worst-case loss (in terms of social utility), this does not mean that the two algorithms are equivalent: we show in particular that the sequential algorithm has several drawbacks, among which the lack of swap stability is certainly the most annoying, as agents can rather easily notice it, and (justifiably) ask for explanations. An easy patch is thus to let agents swap until a stable allocation is reached -but is there such a guarantee? We show that this is the case, despite the fact that swaps may actually decrease social welfare. In other words, stability comes at a price. We provided an upper bound on this price that supports the stability requirement since the worst-case price is constant and quite low. As suggested in the introduction, another compelling argument in favour of a stable mechanism is indeed that in the absence of this property agents may develop their own system to perform swaps. However, such a system would be unlikely to be inclusive, raising concerns of fairness -did anyone really get a chance to swap? This issue happened in practice in the Netherland in 2015, as reported in [START_REF] De | Why a Dutch court stopped high school students from swapping schools[END_REF], when "an Amsterdam court ruled (...) that students going to high school aren't allowed to trade places with each other at different schools." Our results suggest that it may be possible to avoid this issue by allowing swaps in a second phase after the sequential mechanism, as long as they are implemented through a legitimate platform guaranteeing equal access to all users. A challenging issue is to identify actual swap opportunities, but this can be done by eliciting preferences from users on a voluntary basis. In France, web platforms have recently Manuscript submitted to ACM Nathanaël Gross-Humbert, Nawal Benabbou, Aurélie Beynier, and Nicolas Maudet been developed to make easier the exchange of lands between farmers4 and the exchange of public housings in Ile de France 5 . These websites connect the agents and make swaps easier. A related issue which we didn't touch upon here is the problem of manipulability. Finally, there are of course several other metrics which could refine our understanding of the relative merits of these algorithms, for instance it would be good to study various fairness measures. Another interesting issue would be to investigate settings where different agents may have different homophily biases, i.e. different utility trade-offs 𝜑. In Appendix F we show how such problems can be mapped to the setting where 𝜑 is the same for all agents, and discuss which results gets affected by this translation. Finally, while diversity is only assessed through the satisfaction of quotas in this paper, a more ambitious research agenda would be to investigate the interplay between (a metric of) diversity and utility, for instance by adjusting the quota thresholds.

A MIXED-INTEGER-LINEAR PROGRAMMING FORMULATIONS

In order to compute a valid allocation of maximum utilitarian social welfare, one can use the following mixed-integer linear program (involving only a polynomial number of variables/constraints):

max ∑ 𝑖 ∈N ∑ ℎ ∈M 𝑥 𝑖ℎ × 𝑢 𝐼 𝑖 (ℎ) + 𝜑 ∑ 𝑖 ∈N ∑ 𝑗 ∈ T (𝑖) ∑ 𝑞 ∈ [𝑙 ] 𝑠 𝑖 𝑗𝑞 |𝐵 𝑞 | (1) s. t. ∑ ℎ ∈M 𝑥 𝑖ℎ ≤ 1 ∀𝑖 ∈ N (2)
∑ 𝑖 ∈N 𝑥 𝑖ℎ = 1 ∀ℎ ∈ M (3)
∑ 𝑖 ∈𝑇 𝑝 ∑ ℎ ∈𝐵 𝑞 𝑥 𝑖ℎ ≤ 𝜆 𝑝,𝑞 ∀𝑝 ∈ [𝑘], 𝑞 ∈ [𝑙] (4)
𝑏 𝑖𝑞 = ∑ ℎ ∈𝐵 𝑞 𝑥 𝑖ℎ ∀𝑖 ∈ N, 𝑞 ∈ [𝑙] (5)
𝑠 𝑖 𝑗𝑞 ≤ 𝑏 𝑖𝑞 ∀𝑖, 𝑗 ∈ N, 𝑞 ∈ [𝑙] (6)
𝑠 𝑖 𝑗𝑞 ≤ 𝑏 𝑗𝑞 ∀𝑖, 𝑗 ∈ N, 𝑞 ∈ [𝑙] (7)
𝑥 𝑖ℎ ∈ {0, 1}, 𝑏 𝑖𝑞 ∈ {0, 1}, 𝑠 𝑖 𝑗, ∈ {0, 1} ∀𝑖, 𝑗 ∈ N, ℎ ∈ M (8)
where

∑ 𝑞 ∈ [𝑙 ] 𝑠 𝑖 𝑗𝑞 |𝐵 𝑞 | (9) s.t. ∑ ℎ ∈M 𝑥 𝑖ℎ = 1 ∀𝑖 ∈ N (10)
∑ 𝑖 ∈N 𝑥 𝑖ℎ = 1 ∀ℎ ∈ M (11)
∑ 𝑖 ∈𝑇 𝑝 ∑ ℎ ∈𝐵 𝑞 𝑥 𝑖ℎ ≤ 𝜆 𝑝𝑞 ∀𝑝 ∈ [𝑘], 𝑞 ∈ [𝑙] (12)
𝑏 𝑖𝑞 = ∑ ℎ ∈𝐵 𝑞 𝑥 𝑖ℎ ∀𝑖 ∈ N, 𝑞 ∈ [𝑙] (13)
𝑠 𝑖 𝑗𝑞 ≤ 𝑏 𝑖𝑞 ∀𝑖, 𝑗 ∈ N, 𝑞 ∈ [𝑙] (14)
𝑠 𝑖 𝑗𝑞 ≤ 𝑏 𝑗𝑞 ∀𝑖, 𝑗 ∈ N, 𝑞 ∈ [𝑙] (15)
𝑐 𝑖 𝑗1 ≥ ∑ ℎ ∈M (𝑥 𝑗ℎ -𝑥 𝑖ℎ ) × 𝑢 𝐼 𝑖 (ℎ) + 𝜑 ∑ 𝑞 ∈ [𝑙 ] 𝑏 𝑗𝑞 -𝑠 𝑖 𝑗𝑞 |𝐵 𝑞 | + ∑ 𝑎 ∈T (𝑖)\{ 𝑗 } 𝑠 𝑗𝑎𝑞 |𝐵 𝑞 | - ∑ 𝑎 ∈T (𝑖) 𝑠 𝑖𝑎𝑞 |𝐵 𝑞 | ∀𝑖, 𝑗 ∈ N (16)
𝑐 𝑖 𝑗2 ≥ ∑ ℎ ∈M (𝑥 𝑖ℎ -𝑥 𝑗ℎ ) × 𝑢 𝐼 𝑗 (ℎ) + 𝜑 ∑ 𝑞 ∈ [𝑙 ] 𝑏 𝑖𝑞 -𝑠 𝑖 𝑗𝑞 |𝐵 𝑞 | + ∑ 𝑎 ∈T ( 𝑗)\{𝑖 } 𝑠 𝑖𝑎𝑞 |𝐵 𝑞 | - ∑ 𝑎 ∈T ( 𝑗) 𝑠 𝑗𝑎𝑞 |𝐵 𝑞 | ∀𝑖, 𝑗 ∈ N (17)
𝑐 𝑖 𝑗3 × Λ ≥ ∑ 𝑞 ∈ [𝑙 ] 𝜆 𝑇 (𝑖)𝑞 × 𝑏 𝑗𝑞 - ∑ 𝑎 ∈𝑇 (𝑖) 𝑠 𝑗𝑎𝑞 ∀𝑖, 𝑗 ∈ N, 𝑗 ∉ T (𝑖) (18)
𝑐 𝑖 𝑗4 × Λ ≥ ∑ 𝑞 ∈ [𝑙 ] 𝜆 𝑇 ( 𝑗)𝑞 × 𝑏 𝑖𝑞 - ∑ 𝑎 ∈𝑇 ( 𝑗) 𝑠 𝑖𝑎𝑞 ∀𝑖, 𝑗 ∈ N, 𝑗 ∉ T (𝑖) (19)
4

∑ 𝑟 =1 𝑐 𝑖 𝑗𝑟 ≤ 3 ∀𝑖, 𝑗 ∈ N (20)
𝑥 𝑖ℎ ∈ {0, 1} ∀𝑖 ∈ N, ℎ ∈ M (21)
𝑏 𝑖𝑞 ∈ {0, 1}, 𝑠 𝑖 𝑗𝑞 ∈ {0, 1} ∀𝑖, 𝑗 ∈ N, 𝑞 ∈ [𝑙] (22)
𝑐 𝑖 𝑗𝑟 ∈ {0, 1} ∀𝑖, 𝑗 ∈ N, 𝑟 ∈ [4] (23)
where 𝑥 𝑖ℎ , 𝑏 𝑖𝑞 , 𝑠 𝑖 𝑗𝑞 , and 𝑐 𝑖 𝑗𝑟 , with 𝑖, 𝑗 ∈ N , 𝑞 ∈ [𝑙], 𝑟 ∈ [START_REF] Aziz | Fractional hedonic games[END_REF], are the variables of the program, and Λ is a constant defined by

Λ = max 𝑝 ∈ [𝑘 ],𝑞 ∈ [𝑙 ] 𝜆 𝑝𝑞 .
Variables 𝑥 𝑖ℎ , 𝑏 𝑖𝑞 and 𝑠 𝑖 𝑗𝑞 are defined as before. Boolean variables 𝑐 𝑖 𝑗𝑟 , with 𝑟 ∈ [START_REF] Aziz | Fractional hedonic games[END_REF], are used to ensure stability. More precisely, for any two agents 𝑖, 𝑗 ∈ N :

• 𝑐 𝑖 𝑗1 is equal to 1 if and only if 𝑖 prefers the item assigned to agent 𝑗 to hers (Equation ( 16)).

• 𝑐 𝑖 𝑗2 is equal to 1 if and only if 𝑗 prefers the item assigned to agent 𝑖 to hers (Equation ( 17)).

Manuscript submitted to ACM

• 𝑐 𝑖 𝑗3 is equal to 1 if and only if type-block quotas allow agent 𝑖 to receive the item assigned to agent 𝑗 (Equation ( 18)). • 𝑐 𝑖 𝑗4 is equal to 1 if and only if type-block quotas allow agent 𝑗 to receive the item assigned to agent 𝑖 (Equation ( 19)).

Equation ( 20) is used to check that at least one condition is not verified. If they are all verified, then there is a valid improving swap deal between 𝑖 and 𝑗, which means that the allocation is not stable.

B PROOF OF LEMMA 1

PROOF. First, let us prove that the largest utility ratio between any two valid allocations is unbounded in the general case. Given a parameter 𝑘 ∈ N, we consider a family of problem instances I 𝑘 with 𝑘 types of agents, 𝑘 agents per type Let each type of agents and each block of goods be ordered so that we can call 𝑎 𝑝,𝑖 the agent number 𝑖 of type 𝑝 and 𝑏 𝑞,𝑗 the good number 𝑗 of block 𝑞.

Assume that the agents' item-based utilities are defined by:

𝑢 𝐼 𝑝,𝑖 (𝐴) =        1 if item 𝐴(𝑝, 𝑖) = 𝑏 𝑞,𝑗 is in such that 𝑝 = 𝑞 and 𝑖 ≠ 𝑗, 0 otherwise.
and 𝜑 ≠ 0. Obviously, any allocation 𝐴 such that 𝐴(𝑝, 𝑖) = 𝑏 𝑝,𝑖+1[𝑘 ] for all agents 𝑖 ∈ N is valid and maximizes the utilitarian social welfare (every agent receives an item with top utility and blocks are only composed of agents of the same type). Let 𝐴 * I 𝑘 be some optimal allocation of instance I 𝑘 . By definition, we have:

𝑠𝑤 (𝐴 * I 𝑘 ) = 𝑘 ∑ 𝑝=1 𝑘 ∑ 𝑖=1 𝑢 𝐼 𝑝,𝑖 (𝐴 ⊤ I 𝑘 ) + 𝜑𝑢 𝑁 𝑝,𝑖 (𝐴 ⊤ I 𝑘 ) = 𝑘 2 ∑ 𝑖=1 (1 + 𝜑 × 1) = 𝑘 2 ∑ 𝑖=1 (1 + 𝜑) = 𝑘 2 (1 + 𝜑)
Manuscript submitted to ACM Aurélie Beynier, and Nicolas Maudet Now consider any allocation 𝐴 𝑘 such that each block only includes one agent per type, and such that, in each bloc q, the agent 𝑎 𝑞,𝑖 is allocated to a good 𝑏 𝑞,𝑗 with 𝑗 = 𝑖. Allocation 𝐴 𝑘 is obviously valid, and we have:

𝑠𝑤 (𝐴 𝑘 ) = 𝑘 ∑ 𝑝=1 𝑘 ∑ 𝑖=1 𝑢 𝐼 𝑝,𝑖 (𝐴 𝑘 ) + 𝜑𝑢 𝑁 𝑝,𝑖 (𝐴 𝑘 ) = 𝑘 ∑ 𝑝=1 𝑘 ∑ 𝑖=1 0 + 𝜑 × 1 B (𝐴 𝑘 (𝑝, 𝑖)) = 𝑘 2 ∑ 𝑖=1 𝜑 1 𝑘 = 𝜑𝑘
Therefore, for instance I 𝑘 , we have:

𝑠𝑤 (𝐴 * I 𝑘 ) 𝑠𝑤 (𝐴 𝑘 ) = 𝑘 2 (1 + 𝜑) 𝜑𝑘 = 1 + 𝜑 𝜑 𝑘
Since this utility ratio grows linearly 𝑘, the largest utility ration between any two valid allocations is unbounded in the general case.

Now, let us prove that

1+𝜑 𝜑 𝑘 is a tight upper bound when 𝑘 is a constant and 𝜑 > 0. To do so, it is now sufficient to prove that the utility ratio between any two valid allocations cannot be greater than this value. Note that the value 𝑠𝑤 𝑢𝑝 := (1 + 𝜑) × 𝑚 is an obvious upper bound on the utility of a valid allocation (each item is assigned to an agent with an item-based utility equal to 1 and blocks only include agents of the same type). We now focus on the determination of a lower bound on the utility of a valid allocation. Since the item-based utility value can be equal to zero for all agents simultaneously (when they all receive an item for which they have no utility for it), we only need to find a lower bound on the sum of the agents' neighbour-utilities. Let us focus on a block 𝐵 𝑞 , with 𝑞 ∈ [𝑙]. For any valid allocation 𝐴, the sum of the neighbour-utilities in block 𝐵 𝑞 is given by: PROOF. Here we only need to prove that any valid allocation that maximizes the utilitarian social welfare is stable.

For the case of item-focused agents, the argument is straightforward: if two agents wish to swap and they are allowed to do so, then implementing the swap would strictly augment the utilities of both agents, while leaving the other utilities unchanged, which yields an allocation with a strictly larger utility. Therefore any valid allocation maximizing the social welfare is necessarily stable.

For neighbour-focused agents, we now prove that if two agents wish to swap to increase their individual utilities, the utilitarian social welfare will increase by twice as much. For a given non-stable allocation 𝐴, consider a valid improving swap-deal between some agent 𝑖 1 ∈ 𝑇 𝑝 1 with 𝐴(𝑖 1 ) ∈ 𝐵 𝑞 1 and some agent 𝑖 2 ∈ 𝑇 𝑞 2 with 𝐴(𝑖 2 ) ∈ 𝐵 𝑞 2 . Since the item-based component of their utilities is equal to zero, we know that these two agents are of different types and belong to different blocks (i.e., we necessarily have 𝑝 1 ≠ 𝑝 2 and 𝑞 1 ≠ 𝑞 2 ). Let Δ𝑈 be the utility difference between 𝐴 ′ the allocation resulting from the swap-deal and allocation 𝐴, i.e. Δ𝑈 = 𝑠𝑤 (𝐴 ′ ) -𝑠𝑤 (𝐴). Let us decompose Δ𝑈 as follows:

Δ𝑈 = Δ𝑈 1 + Δ𝑈 2
where Δ𝑈 1 (resp. Δ𝑈 2 ) is the change of utility for the agents that are involved (resp. not involved) in the swap-deal. Since the composition of blocks 𝐵 𝑞 1 and 𝐵 𝑞 2 changes, the swap may incur a loss or a gain in utility on the agents in both blocks.

This externalities are measured by 𝑈 2 . For all 𝑝 ∈ [𝑘] and 𝑞 ∈ [𝑙], let 𝐴 𝑝,𝑞 denote the number of agents of type 𝑇 𝑝 in block 𝐵 𝑞 . Using these notations, the swap-deal modifies the utilities of the two swapping agents as follows:

Δ𝑈 1 = 𝑢 𝑖 1 (𝐴 ′ ) -𝑢 𝑖 1 (𝐴) + 𝑢 𝑖 2 (𝐴 ′ ) -𝑢 𝑖 2 (𝐴) = 𝜑 𝐴 𝑝 1 ,𝑞 2 + 1 |𝐵 𝑞 2 | - 𝐴 𝑝 1 ,𝑞 1 |𝐵 𝑞 1 | + 𝐴 𝑝 2 ,𝑞 1 + 1 |𝐵 𝑞 1 | - 𝐴 𝑝 2 ,𝑞 2 |𝐵 𝑞 2 | = 𝜑 𝐴 𝑝 2 ,𝑞 1 -𝐴 𝑝 1 ,𝑞 1 + 1 |𝐵 𝑞 1 | + 𝐴 𝑝 1 ,𝑞 2 -𝐴 𝑝 2 ,𝑞 2 + 1 |𝐵 𝑞 2 |
We now prove that Δ𝑈 2 = Δ𝑈 1 :

Δ𝑈 2 = ∑ 𝑖 ∈𝑇 𝑝 1 \{𝑖 1 } 𝐴(𝑖) ∈𝐵 𝑞 1 ∪𝐵 𝑞 2 𝑢 𝑖 (𝐴 ′ ) -𝑢 𝑖 (𝐴) + ∑ 𝑖 ∈𝑇 𝑝 2 \{𝑖 2 } 𝐴(𝑖) ∈𝐵 𝑞 1 ∪𝐵 𝑞 2 𝑢 𝑖 (𝐴 ′ ) -𝑢 𝑖 (𝐴) = (𝐴 𝑝 1 ,𝑞 1 -1) × 𝐴 𝑝 1 ,𝑞 1 -1 |𝐵 𝑞 1 | - 𝐴 𝑝 1 ,𝑞 1 |𝐵 𝑞 1 | 𝜑 + 𝐴 𝑝 1 ,𝑞 2 𝐴 𝑝 1 ,𝑞 2 + 1 |𝐵 𝑞 2 | - 𝐴 𝑝 1 ,𝑞 2 |𝐵 𝑞 2 | 𝜑 + 𝐴 𝑝 2 ,𝑞 1 𝐴 𝑝 2 ,𝑞 1 + 1 |𝐵 𝑞 1 | - 𝐴 𝑝 2 ,𝑞 1 |𝐵 𝑞 1 | 𝜑 + (𝐴 𝑝 2 ,𝑞 2 -1) 𝐴 𝑝 2 ,𝑞 2 -1 |𝐵 𝑞 2 | - 𝐴 𝑝 2 ,𝑞 2 |𝐵 𝑞 2 | 𝜑 = (𝐴 𝑝 1 ,𝑞 1 -1) -1 𝑀 𝑞 1 𝜑 + 𝐴 𝑝 1 ,𝑞 2 1 𝑀 𝑞 2 𝜑 + 𝐴 𝑝 2 ,𝑞 1 1 𝑀 𝑞 1 𝜑 + (𝐴 𝑝 2 ,𝑞 2 -1)
-1

𝑀 𝑞 2 𝜑 = 𝑢 𝑖 1 (𝐴 ′ ) -𝑢 𝑖 1 (𝐴) + 𝑢 𝑖 2 (𝐴 ′ ) -𝑢 𝑖 2 (𝐴) = Δ𝑈 1
Thus Δ𝑈 = 2Δ𝑈 1 , which means that any improving swap-deal would strictly increase the social welfare. This implies that any valid allocation maximizing the social welfare is necessarily stable. □

D PROOF OF PROPOSITION 2

PROOF. We need to show that we have 𝑃𝑜𝑆 ≤ 2 and 𝑃𝑜𝑆 > 1.6.

𝑃𝑜𝑆 ≤ 2. From Example 1, we know that there exist instances for which no optimal allocation is stable. Let us consider such an instance, and let 𝑂𝑃𝑇 denote such an optimal allocation. From this allocation, we can apply the SWAP-mechanism (presented in Section 5) which consists in performing bilateral improving swap-deals until reaching a stable outcome (see Proposition 7). Let 𝑃𝑂𝑆𝑇 be such an equilibrium. Our aim is to prove that the inequality 𝑠𝑤 (𝑂𝑃𝑇 ) 𝑠𝑤 (𝑃𝑂𝑆𝑇 ) ≤ 2 holds. To do so, let us decompose 𝑠𝑤 (𝑂𝑃𝑇 ) and 𝑠𝑤 (𝑃𝑂𝑆𝑇 ) as follows:

𝑠𝑤 (𝑂𝑃𝑇 ) = 𝑈 𝐼 𝑂𝑃𝑇 + 𝜑𝑈 𝑁 𝑂𝑃𝑇 𝑠𝑤 (𝑃𝑂𝑆𝑇 ) =𝑈 𝐼 𝑃𝑂𝑆𝑇 + 𝜑𝑈 𝑁 𝑃𝑂𝑆𝑇
where 𝑈 𝐼 𝑂𝑃𝑇 (resp. 𝑈 𝐼 𝑃𝑂𝑆𝑇 ) is the sum of the item-based utilities of the agents in the allocation 𝑂𝑃𝑇 (resp. 𝑃𝑂𝑆𝑇 ), and 𝑈 𝑁 𝑂𝑃𝑇 (resp. 𝑈 𝑁 𝑃𝑂𝑆𝑇 ) is the sum of their neighbour-based utilities in the same allocation. We now use 𝑝𝑜𝑡 the potential function introduced in the proof of Proposition 7, which is defined by:

𝑝𝑜𝑡 (𝐴) = 𝑠𝑤 (𝐴) + ∑ 𝑖 ∈N 𝑢 𝐼 𝑖 (𝐴)
In particular, we have 𝑝𝑜𝑡 (𝑂𝑃𝑇 ) = 𝑠𝑤 (𝑂𝑃𝑇 ) +𝑈 𝐼 𝑂𝑃𝑇 and 𝑝𝑜𝑡 (𝑃𝑂𝑆𝑇 ) = 𝑠𝑤 (𝑃𝑂𝑆𝑇 ) +𝑈 𝐼 𝑃𝑂𝑆𝑇 . In the proof of Proposition 7, it is shown that 𝑝𝑜𝑡 strictly increases when performing any valid improving swap. Since 𝑃𝑂𝑆𝑇 is obtained from 𝑂𝑃𝑇 by performing at least one valid improving swap, we have 𝑝𝑜𝑡 (𝑃𝑂𝑆𝑇 ) > 𝑝𝑜𝑡 (𝑂𝑃𝑇 ), i.e. 𝑠𝑤 (𝑃𝑂𝑆𝑇 ) + 𝑈 𝐼 𝑃𝑂𝑆𝑇 > 𝑠𝑤 (𝑂𝑃𝑇 ) + 𝑈 𝐼 𝑂𝑃𝑇 . Moreover, we have 𝑠𝑤 (𝑂𝑃𝑇 ) > 𝑠𝑤 (𝑃𝑂𝑆𝑇 ) since OPT is optimal (and no optimal allocation is stable by hypothesis).

Therefore, we necessarily have 𝑈 𝐼 𝑂𝑃𝑇 < 𝑈 𝐼 𝑃𝑂𝑆𝑇 . Now, note that we have:

𝑠𝑤 (𝑂𝑃𝑇 ) 𝑠𝑤 (𝑃𝑂𝑆𝑇 ) = 𝑠𝑤 (𝑂𝑃𝑇 ) + 𝑠𝑤 (𝑃𝑂𝑆𝑇 ) -𝑠𝑤 (𝑃𝑂𝑆𝑇 ) 𝑠𝑤 (𝑃𝑂𝑆𝑇 ) = 1 + 𝑠𝑤 (𝑂𝑃𝑇 ) -𝑠𝑤 (𝑃𝑂𝑆𝑇 ) 𝑠𝑤 (
𝑃𝑂𝑆𝑇 ) Moreover, we have:

𝑠𝑤 (𝑂𝑃𝑇 ) -𝑠𝑤 (𝑃𝑂𝑆𝑇 ) = 𝑠𝑤 (𝑂𝑃𝑇 ) -𝑠𝑤 (𝑃𝑂𝑆𝑇 ) + 𝑈 𝐼 𝑂𝑃𝑇 -𝑈 𝐼 𝑂𝑃𝑇 = 𝑝𝑜𝑡 (𝑂𝑃𝑇 ) -𝑠𝑤 (𝑃𝑂𝑆𝑇 ) -𝑈 𝐼 𝑂𝑃𝑇 + 𝑈 𝐼 𝑃𝑂𝑆𝑇 -𝑈 𝐼 𝑃𝑂𝑆𝑇 = 𝑝𝑜𝑡 (𝑂𝑃𝑇 ) -𝑝𝑜𝑡 (𝑃𝑂𝑆𝑇 ) + 𝑈 𝐼 𝑃𝑂𝑆𝑇 -𝑈 𝐼 𝑂𝑃𝑇
Therefore, we obtain:

𝑠𝑤 (𝑂𝑃𝑇 ) 𝑠𝑤 (𝑃𝑂𝑆𝑇 ) = 1 + 𝑝𝑜𝑡 (𝑂𝑃𝑇 ) -𝑝𝑜𝑡 (𝑃𝑂𝑆𝑇 ) +𝑈 𝐼 𝑃𝑂𝑆𝑇 -𝑈 𝐼 𝑂𝑃𝑇 𝑠𝑤 (𝑃𝑂𝑆𝑇 ) < 1 + 𝑈 𝐼 𝑃𝑂𝑆𝑇 -𝑈 𝐼 𝑂𝑃𝑇 𝑠𝑤 (𝑃𝑂𝑆𝑇 ) (since 𝑝𝑜𝑡 (𝑂𝑃𝑇 ) < 𝑝𝑜𝑡 (𝑃𝑂𝑆𝑇 )) < 1 + 𝑈 𝐼 𝑃𝑂𝑆𝑇 (𝑃𝑂𝑆𝑇 ) (since 𝑈 𝐼 𝑂𝑃𝑇 ≥ 0) < 2 (since 𝑠𝑤 (𝑃𝑂𝑆𝑇 ) = 𝑈 𝐼 𝑃𝑂𝑆𝑇 + 𝜑𝑈 𝑁 𝑃𝑂𝑆𝑇 )
This means that any equilibrium that is reachable from the optimal allocation is at least half as good as the optimum.

Since the best equilibrium is at least as good as any reachable equilibrium, it is also at least half as good as the optimum.

Thus the utility ratio between any optimal allocation and any equilibrium maximizing the social welfare is strictly smaller than 2 for any instance of our allocation problem with diversity constraints. Since PoS is the least upper bound on this utility ratio over all possible instances, we can conclude that 𝑃𝑜𝑆 ≤ 2 holds.

𝑃𝑜𝑆 > 1.6. We show here that the price of stability is at least 1.6, by providing an instance for which the utility ratio between the optimal and the best (valid) stable allocations reaches this value. More precisely, we consider an instance with 16 agents partitioned into 4 types: • the social welfare is maximized by any allocation assigning all the agents of type 𝑇 𝑝 in block 𝐵 𝑝 , for 𝑝 ∈ {1, . . . , 4}.

𝑇 1 = {𝑎 1,1 , 𝑎 1,2 , 𝑎 1,3 , 𝑎 1,4 },𝑇 2 = {𝑎 2,1 , 𝑎 2,2 , 𝑎 2,3 , 𝑎 2,4 },𝑇 3 = {𝑎 3,1 , 𝑎
1 = {ℎ 1,1 , ℎ 1,2 , ℎ 1,3 , ℎ 1,4 }, 𝐵 2 = {ℎ 2,1 , ℎ 2,2 , ℎ 2,3 , ℎ 2,4 }, 𝐵 3 = {ℎ 3,1 , ℎ 3,2 , ℎ 3,3 , ℎ 3,
In such an allocation, the utility of each agent is 0 + 𝜑 × 4 4 = 1 and the social welfare is equal to 16. Note that such an allocation is not stable, e.g., agents of type 𝑇 1 and agents of type 𝑇 2 want to swap with their items to increase their utilities from 1 to 1 + 𝜀 • any allocation assigning one agent of each type in every block is a valid stable allocation of maximum social welfare.

Its social welfare is equal to 4 × (0 + 𝜑 × 1 4 ) + 4 × (

𝜆 𝑝,𝑞 =        𝑥𝑘 -1 if 𝑝 = 𝑞 𝑥 otherwise
Now, for any allocation 𝐴, we define the agents' utilities as follows: for all types 𝑝 ∈ [𝑘] and all 𝑎 𝑝,𝑖 ∈ 𝑇 𝑝 , the item-based utility of agent 𝑎 𝑝,𝑖 is given by:

𝑢 𝐼 𝑎 𝑝,𝑖 (𝐴) =        1 if 𝐴(𝑎 𝑝,𝑖 ) = ℎ 𝑝,𝑖 0 otherwise
Here the optimal allocation 𝐴 𝑏𝑒𝑠𝑡 is simply defined by 𝐴 𝑏𝑒𝑠𝑡 (𝑎 𝑝,𝑖 ) = ℎ 𝑝,𝑖 for all 𝑝 ∈ [𝑘] and all 𝑎 𝑝,𝑖 ∈ 𝑇 𝑝 , which consists in grouping the agents according to their types, while assigning every item to the single agent with a utility of 1 for it. The We now build an allocation, called 𝐴 𝑤𝑜𝑟𝑠𝑡 , that minimizes the utilitarian social over all possible stable valid allocations.

For this, we first rename the agent: each agent of type 𝑇 𝑝 is identified by a triplet (𝑝, 𝑞, 𝑦) ∈ [𝑘] 6 These results can be shown using our mixed-integer linear programming formulations given in Appendix A, or by enumerating all the valid allocations.

Manuscript submitted to ACM Sequential and Swap Mechanisms for Public Housing Allocation with Quotas and Neighbourhood-based Utilities 23

Thus 𝑥 -1 agents of each type 𝑇 𝑝 are assigned to 𝑥 -1 items of block 𝐵 𝑝 , but none of them receives her favourite item.

Moreover, there is no pair of agents such that both agents would be happy to swap due to the cycling structure.

To When 𝑥 tends towards +∞, this ratio tends towards

(1+𝜑) (𝑥𝑘) 2 𝜑𝑥 2 𝑘 = (1+𝜑)𝑘
𝜑 , which implies that the bound is reached at the limit. □

F NEIGHBOURHOOD-BASED UTILITIES WITH DIFFERENT UTILITY TRADE-OFFS

In the main part of the paper, we assumed that all the agents have the same utility trade-off 𝜑 balancing the relative importance of the item-based utility and the neighbour-based utility. In this section, we discuss whether instances where the agents have different utility trade-offs can be translated to a single utility trade-off instance. More precisely, here we consider instances where each agent 𝑖 has its own utility trade-off 𝜑 𝑖 ∈ (0, 1], and item-based utilities are normalized, i.e.

each agent 𝑖 has at least one item ℎ ∈ M such that 𝑢 𝐼 𝑖 (ℎ) = 0 and at least one item ℎ ∈ M such that 𝑢 𝐼 𝑖 (ℎ) = 1. We first

( 4 )

 4 ∀(𝑝, 𝑞) ∈ [𝑘] × [𝑙], |{𝑖 ∈ 𝑇 𝑝 : 𝐴(𝑖) ∈ 𝐵 𝑞 }| ≤ 𝜆 𝑝,𝑞 (diversity constraints are satisfied).

PROPOSITION 4 .

 4 The worst-case utility loss of SEQ-mechanism is unbounded in the general case. When 𝜑 ≠ 0 and 𝑘 is a constant, it reaches the upper bound of Lemma 1. PROOF. Given a parameter 𝑘 ∈ N, we consider a family of instances with 𝑘 types of agents, 𝑘 blocks of items and 𝑘 items per block (i.e. |𝐵 𝑞 | = 𝑘 for all 𝑞 ∈ [𝑙]). All but the first type of agents are composed of exactly 𝑘 agents (i.e. |𝑇 𝑝 | = 𝑘 for all 𝑝 ∈ {2, . . . , 𝑘 }), whereas the first type 𝑇 1 is partitioned into two groups 𝑇 1 1 and 𝑇 2 1 such that |𝑇 1 1 | = 𝑘 2 and |𝑇 2 1 | = 𝑘. Hence we have 𝑛 = 2𝑘 2 agents and 𝑚 = 𝑘 2 items. The type-block capacities are as follows: 𝜆 1,𝑞 = 𝑘 for all 𝑞 ∈ [𝑙] and 𝜆 𝑝,𝑞 = 1 for all 𝑝 ∈ {2, . . . , 𝑘 } and all 𝑞 ∈ [𝑙]

  Manuscript submitted to ACM Sequential and Swap Mechanisms for Public Housing Allocation with Quotas and Neighbourhood-based Utilities 11

  and |𝑇 3 | = 0.13×𝑛, and type-block quotas are defined by 𝜆 1𝑞 = 0.87× |𝐵 𝑞 |, 𝜆 2𝑞 = 0.25× |𝐵 𝑞 |, and 𝜆 3𝑞 = 0.15 × |𝐵 𝑞 | for all blocks 𝑞 ∈ [𝑙] (following the dataset from Singapore real estate). Item-based utilities are uniformly drawn at random within [0, 1] and 𝜑 is set to 1.

Fig. 1 .

 1 Fig. 1. Linear regression on the number of swaps needed to reach an equilibrium.

  (i.e. |𝑇 𝑝 | = 𝑘 for all 𝑝 ∈ [𝑘]), 𝑘 blocks of items, 𝑘 items per block (i.e. |𝐵 𝑞 | = 𝑘 for all 𝑞 ∈ [𝑙]) and type-block capacities 𝜆 𝑝,𝑞 = 𝑘 for all 𝑝 ∈ [𝑘] and 𝑞 ∈ [𝑙]. Thus, we have 𝑛 = 𝑘 2 agents and 𝑚 = 𝑘 2 items in total, and type-block quotas are not restrictive.

𝑥𝜆 |𝐵 𝑞 | 2 2 =|𝐵

 22 ∑ 𝑖 ∈N 𝐴(𝑖) ∈𝐵 𝑞 𝑢 𝑁 𝑖 (𝐴) = ∑ 𝑖 ∈N 𝐴(𝑖) ∈𝐵 𝑞 ∑ 𝑗 ∈N 𝐴( 𝑗) ∈𝐵 𝑞 I(T (𝑖), T ( 𝑗)) |𝐵 𝑞 | = 1 |𝐵 𝑞 | 𝑘 ∑ 𝑝=1 |{𝑖 ∈ 𝑇 𝑝 : 𝐴(𝑖) ∈ 𝐵 𝑞 }| 2 Therefore, we can obtain a lower bound on this value by solving the following convex optimization problem: 𝑝,𝑞 = |𝐵 𝑞 | 𝑥 𝑝,𝑞 ∈ R + , ∀𝑝 ∈ [𝑘] where 𝑥 𝑝,𝑞 is a continuous variable representing the number of agents of type 𝑇 𝑝 who are assigned to an item in block 𝐵 𝑞 , for all 𝑝 ∈ [𝑘]. The corresponding optimal solution 𝑥 * is such that: ∃𝜆 ∈ R, ∇𝑓 (𝑥 * ) + 𝜆∇𝑔(𝑥 * ) = 0 Manuscript submitted to ACM where 𝑓 (𝑥) = 1 |𝐵 𝑞 | 𝑘 𝑝=1 𝑥 2 𝑝,𝑞 and 𝑔(𝑥) = 𝑘 𝑝=1 𝑥 𝑝,𝑞 -|𝐵 𝑞 |. Thus we know that 𝑥 * and 𝜆 are such that: for all 𝑝 ∈ [𝑘]. Since 𝑘 𝑝=1 𝑥 * 𝑘 = |𝐵 𝑞 | also holds, we obtain 𝜆 = -2 𝑘 and then 𝑥 * 𝑝 = |𝐵 𝑞 | 𝑘 for all 𝑝 ∈ [𝑘]. We finally obtain the following lower bound on the sum of the neighbour-utilities in block 𝐵 𝑞 : ∑ 𝑖 ∈N 𝐴(𝑖) ∈𝐵 𝑞 𝑢 𝑁 𝑖 (𝐴) ≥ 𝑓 (𝑥 * ) |𝐵 𝑞 | 𝑘 for any valid allocation 𝐴. Summing over all blocks 𝐵 𝑞 , 𝑞 ∈ [𝑙], we obtain a lower bound on the sum of the neighbour-𝑞 | = 𝑚 𝑘 Thus for any valid allocation 𝐴, we have: 𝑠𝑤 (𝐴) = ∑ 𝑖 ∈N 𝑢 𝑖 (𝐴) = ∑ 𝑖 ∈N 𝑢 𝐼 𝑖 (𝐴) + 𝜑𝑢 𝑁 𝑖 (𝐴) ≥ 0 + 𝜑 𝑚 𝑘 and therefore 𝑠𝑤 𝑙𝑜𝑤 := 𝜑 𝑚 𝑘 is a lower bound on the utility of any valid allocation. Hence the utility ratio between any two valid allocations cannot be greater than 𝑠𝑤 𝑢𝑝 𝑠𝑤 𝑙𝑜𝑤 = 1+𝜑 𝜑 𝑘. □ C DETAILED PROOF OF PROPOSITION 1

  4 }, and 𝐵 4 = {ℎ 4,1 , ℎ 4,2 , ℎ 4,3 , ℎ 4,4 }. Type-block quotas are defined by 𝜆 𝑝𝑞 = 4 when 𝑝 = 𝑞, and 𝜆 𝑝𝑞 = 1 otherwise. The utility trade-off 𝜑 is equal to 1. The item-based utilities are defined by the matrix 𝑃 𝜖 , with 𝜖 > 0, as follows: ∀𝑖 ∈ 𝑇 𝑝 , ℎ ∈ 𝐵 𝑞 , 𝑢 𝐼 𝑖 (ℎ) = 𝑃 𝑝,𝑞 where 𝑃 𝜖 =

=

  utilitarian social welfare of 𝐴 𝑏𝑒𝑠𝑡 is obviously:𝑠𝑤 (𝐴 𝑏𝑒𝑠𝑡 ) = 𝑝,𝑖 (𝐴) + 𝜑𝑢 𝑁 𝑎 𝑝,𝑖 (𝐴) 𝑘 (𝑥𝑘 -1)(1 + 𝜑)

  2 ×[𝑥]\{(𝑧, 𝑧, 𝑥) : ∀𝑧 ∈ [𝑘]}. Similarly, each item of block 𝐵 𝑝 is identified by a triplet (𝑝, 𝑞, 𝑦) ∈ [𝑘] 2 × [𝑥] \ {(𝑧, 𝑧, 𝑥) : ∀𝑧 ∈ [𝑘]}. By doing so, every item gives a utility of 1 to the agent who shares the same triplet. Now, for all 𝑝 ∈ [𝑘] and for all 𝑦 ∈ [𝑥 -1], we set: 𝐴 𝑤𝑜𝑟𝑠𝑡 (𝑎 (𝑝,𝑝,𝑦) ) ,𝑝,𝑦-1) if 𝑦 ∈ {2, . . . , 𝑥 -1}, ℎ (𝑝,𝑝,𝑥-1) otherwise (i.e. when 𝑦 = 1).

2 𝑥𝑘 - 1 + 𝑥 2 (𝑘 - 1 ) 𝑥𝑘 - 1 = 1 = ( 1 +

 2121111 𝜑𝑘 (𝑥 2 𝑘 -2𝑥 + 1) 𝑥𝑘 -1 It follows that the largest utility ratio between any two valid stable allocations is:𝑠𝑤 (𝐴 𝑏𝑒𝑠𝑡 ) 𝑠𝑤 (𝐴 𝑤𝑜𝑟𝑠𝑡 ) = (1 + 𝜑)(𝑥𝑘 -1)𝑘 𝜑𝑘 (𝑥 2 𝑘-2𝑥+1) 𝑥𝑘-𝜑)(𝑥𝑘 -1) 2𝜑 (𝑥 2 𝑘 -2𝑥 + 1)

  2} and 𝑇 2 = {3, 4}, and a set of 4 items M = {ℎ 1 , ℎ 2 , ℎ 3 , ℎ 4 } partitioned into 2 blocks 𝐵 1 = {ℎ 1 , ℎ 2 } and 𝐵 2 = {ℎ 3 , ℎ 4 }. Assume that type-block quotas are defined by 𝜆 𝑝,𝑞 = 2 for all (𝑝, 𝑞) ∈ {1, 2} × {1, 2}, which implies that they are not restrictive in this example. When we run the sequential procedure with agent order (1, 3, 2, 4), we can obtain an allocation 𝐴 where agents 1 and 3 get an item in block 𝐵 1 and agents 2 and 4 get an item in block 𝐵 2 . In that case, each agent 𝑖 ∈ N has a utility 𝑢 𝑖 (𝐴) = 0 + 𝜑 × 1/2 since the blocks only include one agent per type. Note that agents 2 and 3

Table 1 .

 1 Averaged utility losses on random instances.

SEQ RSEQ+SWAP SEQ+SWAP 𝜑 = 0.5 1.757 ± 0.144 1.073 ± 0.028 1.101 ± 0.023 1.069 ± 0.029 𝜑 = 1 1.695 ± 0.118 1.084 ± 0.027 1.102 ± 0.026 1.074 ± 0.021 6.

2 Comparison of mechanisms on real data from Singapore real estate In

  2700 is the number of agents applying for a house. The type-block quotas are defined by 𝜆 1𝑞 = 0.87 × |𝐵 𝑞 |, 𝜆 2𝑞 = 0.25 × |𝐵 𝑞 |, and 𝜆 3𝑞 = 0.15 × |𝐵 𝑞 | for all blocks 𝑞 ∈ [𝑙] (as defined by the Housing and Development Board in Singapore). In our tests, we set 𝜑 to 1, and for the item-based utilities, we consider the following two utility models (introduced in [6]): Aurélie Beynier, and Nicolas Maudet • The distance-based utility model (Dist(𝜎 2 )): in this model, each agent 𝑖 has a preferred geographic location 𝑝 𝑖 , uniformly drawn at random in [0, 10] 2 . The utility derived by agent 𝑖 for item ℎ in block 𝐵 𝑞 is then generated according to a normal distribution: N (1/𝑑 (𝑝 𝑖 , 𝐿(𝐵 𝑞 )), 𝜎 2 ) where 𝐿(𝐵 𝑞 ) is the location of block 𝐵 𝑞 and 𝑑 (•) is the Euclidean distance. • The ethnicity-based utility model (Ethn(𝜎 2 )): in this model, all agents of the same type have the same preferred location.

this part, we use a dataset from Singapore real estate, with 𝑚 = 1350 houses partitioned into 𝑙 = 9 blocks/buildings of size 128, 162, 156, 249, 108, 94, 104, 190, and 159 respectively (see [6] for a complete description of the dataset). The set N of agents is divided into 𝑘 = 3 types of size |𝑇 1 | = 0.74 × 𝑛, |𝑇 2 | = 0.13 × 𝑛, and |𝑇 3 | = 0.13 × 𝑛 (following the 2010 Singapore census report), where 𝑛 =

Table 2 .

 2 Averaged social welfare values on the dataset from Singapore real estate.

1 RSEQ 903 ± 14 1465 ± 43 1133 ± 84 1466 ± 41 SEQ 989 ± 23 1678 ± 60 1264 ± 99 1706 ± 60 RSEQ+SWAP 1057 ± 19 1659 ± 58 1242 ± 93 1684 ± 55 SEQ+SWAP 1072 ± 23 1690 ± 61 1268 ± 101 1716 ± 61

  Variable 𝑏 𝑖,𝑞 is equal to 1 if agent 𝑖 is assigned to an item in block 𝐵 𝑞 . Variable 𝑠 𝑖 𝑗𝑞 is equal to one if agents 𝑖 and 𝑗 are both assigned to block 𝐵 𝑞 . Equation (2) is used to ensure that every agent is assigned to at most one item, while Equation (3) ensures that every item is assigned to one agent. Equation (4) corresponds to type-block quotas. Equation (5) imposes that variables 𝑏 𝑖𝑞 are equal to 1 if and only if agent 𝑖 is assigned to an item in block 𝐵 𝑞 . Equations (6-7) are used to ensure that boolean variables 𝑠 𝑖 𝑗𝑞 are equal to 0 when agents 𝑖 or 𝑗 are not in 𝐵 𝑞 , and to 1 otherwise (since the objective function is to be maximized).

						Nathanaël Gross-Humbert, Nawal Benabbou,
						Aurélie Beynier, and Nicolas Maudet
	max	∑	∑	𝑥 𝑖ℎ × 𝑢 𝐼 𝑖 (ℎ) + 𝜑	∑	∑
		𝑖 ∈N	ℎ ∈M		𝑖 ∈N	𝑗 ∈T (𝑖)
	Now we propose the following mixed-integer program for finding a valid stable allocation of maximum utilitarian
	social welfare.

𝑥 𝑖ℎ , 𝑏 𝑖,𝑞 and 𝑠 𝑖 𝑗𝑞 , with 𝑖, 𝑗 ∈ N , 𝑞 ∈ [𝑙], are the variables of the program (see Equation (

8

)). Variable 𝑥 𝑖ℎ is equal to one if item ℎ is assigned to agent 𝑖.

  3,2 , 𝑎 3,3 , 𝑎 3,4 }, and 𝑇 4 = {𝑎 4,1 , 𝑎 4,2 , 𝑎 4,3 , 𝑎 4,4 }. It involves 16 items partitioned into 4 blocks: 𝐵

  Hence, the utility ratio between any optimal allocation and any valid stable allocation of maximum social welfare is equal to16 10+12𝜀 , which tends towards 1.6 when 𝜀 tends towards 0. □ PROOF. Given a parameter 𝑥 ∈ N, we consider a family of instances with 𝑘 types of agents, each type containing 𝑥𝑘 -1 agents: for all 𝑝 ∈ [𝑘], 𝑇 𝑝 = {𝑎 𝑝,1 , 𝑎 𝑝,2 , . . . , 𝑎 𝑝,𝑥𝑘-1 }. Similarly, we consider 𝑘 blocks, each of them including 𝑥𝑘 -1 items: for all 𝑞 ∈ [𝑘], 𝐵 𝑞 = {ℎ 𝑞,1 , ℎ 𝑞,2 , . . . , ℎ 𝑞,𝑥𝑘-1 }. For all 𝑝, 𝑞 ∈ [𝑘], the type-quota capacities are defined by:

	1 4 + 𝜀 + 𝜑 × 1 4 ) + 4 × ( 2 4 + 𝜀 + 𝜑 × 1 4 ) + 4 × ( 3 4 + 𝜀 + 𝜑 × 1 4 ) = 10 + 12𝜀.
	E PROOF OF PROPOSITION 8

  allocate the remaining agents (i.e. agents 𝑎 (𝑝,𝑞,𝑦) with 𝑝, 𝑞 ∈ [𝑘], 𝑝 ≠ 𝑞, and 𝑦 ∈ [𝑥]), we consider 𝑘 one-to-one correspondences 𝜎 𝑝 , with 𝑝 ∈ [𝑘], such that 𝜎 𝑝 : {1, . . . , 𝑘 }\{𝑝} → {1, . . . , 𝑘 }\{𝑝} and 𝜎 𝑝 (𝑞) ≠ 𝑞 for all 𝑞 ∈ [𝑘]\{𝑝}.Then, for all 𝑝, 𝑞 ∈ [𝑘], with 𝑞 ≠ 𝑝, and for all 𝑦 ∈ [𝑥], we set:𝐴 𝑤𝑜𝑟𝑠𝑡 (𝑎 (𝑝,𝑞,𝑦) ) = ℎ (𝑞,𝜎 𝑝 (𝑞),𝑦)Thus, for each type 𝑇 𝑝 with 𝑝 ∈ [𝑘], the remaining (𝑘 -1)𝑥 agents are distributed evenly among the blocks 𝐵 𝑞 , with 𝑞 ≠ 𝑝, so that each of them includes exactly 𝑥 agents of type 𝑇 𝑝 . It is easy to check that 𝐴 𝑤𝑜𝑟𝑠𝑡 satisfies type-block quotas, which implies that it is a valid allocation. Moreover, for each type 𝑝 ∈ [𝑘] and each block 𝐵 𝑞 , with 𝑞 ≠ 𝑝, the corresponding 𝑥 agents would be happy to swap their items only with the agents in block 𝐵 𝑝 that own their favourite items, but type-block quotas prevent such swaps from happening (we know that they are not of types 𝑝 or 𝑞 by definition of 𝜎 𝑝 ). Therefore, 𝐴 𝑤𝑜𝑟𝑠𝑡 is a valid stable allocation, whose social welfare is: 𝑠𝑤 (𝐴 𝑤𝑜𝑟𝑠𝑡 ) = 𝑝,𝑖 (𝐴 𝑤𝑜𝑟𝑠𝑡 ) + 𝜑𝑢 𝑁 𝑎 𝑝,𝑖 (𝐴 𝑤𝑜𝑟𝑠𝑡 )

	𝑘	𝑥𝑘-1
	∑ 𝑝=1 𝑘 𝑎 = ∑ 𝑖=1 𝑢 𝐼 𝑥𝑘-1 ∑ ∑ 0 + 𝜑𝑢 𝑁 𝑎 𝑝,𝑖 (𝐴 𝑤𝑜𝑟𝑠𝑡 )
	𝑝=1	𝑖=1
		𝑘	𝑥-1
	= 𝜑	∑	∑
		𝑝=1

𝑖=1

𝑢 𝑁 𝑎 𝑝,𝑖 (𝐴 𝑤𝑜𝑟𝑠𝑡 ) +

𝑘𝑥-1

Manuscript submitted to ACM

This mechanism is referred to as "lottery-based" mechanism in[START_REF] Benabbou | Diversity constraints in public housing allocation[END_REF].Manuscript submitted to ACM

Nathanaël Gross-Humbert, Nawal Benabbou,

RSEQ and SEQ needed to be run respectively 1.87 ± 1.74 and 1.83 ± 1.29 times on average to obtain a valid allocation.Manuscript submitted to ACM

We do not report the averaged utility losses here, as it was not possible to compute the social welfare optimum efficiently using our linear programming formulation (due to the high number of agents/items).Manuscript submitted to ACM

https://www.echangeparcelle.fr

https://www.echangerhabiter.fr Manuscript submitted to ACM

show how to convert such an instance to another one with a unique utility trade-off. We then discuss the convergence of the swap mechanism and investigate the validity of our worst-case results.

Instance transformation. From an instance I 1 where the agents have different utility trade-offs, we define a new instance I 2 with the same components N, M, 𝐵,𝑇 , 𝜆 where the agents have the same utility trade-off 𝜑 = 𝑚𝑖𝑛 𝑖 ∈N 𝜑 𝑖 . More precisely, we consider new utilities (𝑣 𝑖 ) 𝑖 ∈N defined by:

for every allocation 𝐴, where 𝑣 𝐼 𝑖 (𝐴) = 𝜑 𝜑 𝑖 𝑢 𝐼 𝑖 (𝐴) and 𝑣 𝑁 𝑖 (𝐴) = 𝑢 𝑁 𝑖 (𝐴).

On the convergence of the swap-deal mechanism. Note that 𝑣 𝑖 (𝐴) is simply obtained by multiplying 𝑢 𝑖 (𝐴) by a positive value. Therefore, 𝑢 𝑖 and 𝑣 𝑖 correspond to the same ordinal preferences over allocations, meaning that any valid improving swap-deal for (𝑢 𝑖 ) 𝑖 ∈N is also an improving swap-deal for (𝑣 𝑖 ) 𝑖 ∈N , and vice-versa. Since we proved the convergence to an equilibrium in I 1 (see Proposition 8), we can also reach an equilibrium in I 2 by applying the same sequence of swap-deals. We can conclude that the swap mechanism always converges to a stable outcome even when all agents have different utility trade-offs 𝜑.

On the optimal social welfare. Unfortunately, not all our results can be freely translated to the case of a single 𝜑 using our transformation, as some notions such as the social welfare will be altered by the transformation. In particular, the optimal allocation of instance I 1 may be different from the optimal allocation of the translated instance I 2 , as shown in the following example.

EXAMPLE 2. Consider an instance I 1 with 3 agents partitioned into 2 types 𝑇 1 = {1, 2} and 𝑇 2 = {3}, and 3 items partitioned into 2 blocs 𝐵 1 = {ℎ 1 , ℎ 2 } and 𝐵 2 = {ℎ 3 }. The utilities are given by:

01. For this instance, allocation 𝐴 defined by 𝐴(1) = ℎ 1 , 𝐴(2) = ℎ 2 , and 𝐴(3) = ℎ 3 is a valid allocation with maximum social welfare, with 𝑠𝑤 (𝐴) = 3.02. Now let us consider the instance 𝐼 2 obtained from 𝐼 1 using our transformation. Here we have 𝜑 = min{0.01, 1} = 0.01, and (𝑣 𝑖 ) 𝑖 ∈N are given by: