# Fair Rent Division on a Budget Revisited

Stéphane Airiau, Hugo Gilbert, Umberto Grandi, Jérôme Lang, Anaëlle
Wilczynski

► To cite this version:

Stéphane Airiau, Hugo Gilbert, Umberto Grandi, Jérôme Lang, Anaëlle Wilczynski. Fair Rent Division on a Budget Revisited. 26th European Conference on Artificial Intelligence (ECAI 2023), European Association for Artificial Intelligence (EurAI); Polish Artificial Intelligence Society (PSSI), Sep 2023, Kraków, Poland. 10.3233/faia230253. hal-04261690

HAL Id: hal-04261690

https://hal.science/hal-04261690v1

Submitted on 27 Oct 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Fair Rent Division on a Budget Revisited

Stéphane Airiauª, Hugo Gilbertª, Umberto Grandiᵇ, Jérôme Langᶜ and Anaëlle Wilczynskiᵈ

ªLAMSADE, PSL, Université Paris-Dauphine, CNRS {stephane.airiau, hugo.gilbert}@lamsade.dauphine.fr

ᵇIRIT, Université Toulouse Capitole, umberto.grandi@ut-capitole.fr

ᶜLAMSADE, CNRS, PSL, Université Paris-Dauphine, jerome.lang@dauphine.fr

ᵈMICS, CentraleSupélec, Université Paris-Saclay, anaelle.wilczynski@centralesupelec.fr

**Abstract.** Rent division consists in simultaneously computing an allocation of rooms to agents and a payment, starting from an individual valuation of each room by each agent. When agents have budget limits, it is known that envy-free solutions do not necessarily exist. We propose two solutions to overcome this problem. In the first one, we relax envy-freeness to account for budget disparities. In the second one, we allow fractional allocations, in which agents may change rooms during the duration of the lease.

## 1 Introduction

A set of *n* agents agree to pay collectively the rent of a flat that contains *n* rooms. Rooms are not alike: an agent prefers some rooms to others. We assume preferences are modeled by valuations representing the maximum amount that a given agent is willing to pay for a given room. How should we assign rooms to agents and how should the rent be divided? This is the standard rent division problem. It is known that, provided that the valuations given to the different rooms by a given agent sum up to the rent, there always exists an allocation that is individually rational (no agent should pay more for a room than her maximum payment for that room), envy-free (no agent would prefer the allocation to another agent – room and payment – to their own), and that maximises both utilitarian and egalitarian social welfare [11]. This solution is implemented in the spladdit.org platform [12] and is its most popular application.

The standard problem is often not realistic, because agents usually have a budget, that is, a maximum amount of money they can afford to pay. Searching for individually rational envy-free solutions to rent division with individual budgets is nontrivial [17] and may result in a failure to meet both conditions, as shown in the following example.

**Example 1.** *Example with no individually rational envy-free solution respecting the budget constraints. The rent of the flat is 1000. Two agents value two rooms as follows:*

<table><thead><tr><th></th><th>room r<sub>1</sub></th><th>room r<sub>2</sub></th><th>budget</th></tr></thead><tbody><tr><td>agent 1</td><td>800</td><td>400</td><td>600</td></tr><tr><td>agent 2</td><td>800</td><td>400</td><td>500</td></tr></tbody></table>

If $r_2$ is assigned to 1, and $r_1$ to 2, then individual rationality implies that 1 pays at most 400, therefore 2 has to pay at least 600, which exceeds her budget. Thus $r_1$ must be assigned to 1, and $r_2$ to 2. Because of her budget constraint, agent 1 cannot pay more than 600. Because of individual rationality, 2 cannot pay more than 400 for $r_2$; so, to reach the total rent of 1000, 1 must pay 600 and

2 must pay 400. Assuming utilities are quasi-linear, 1's utility is 800 - 600 = 200 (her valuation for $r_1$ minus her payment), and 2's utility is 400 - 400 = 0. However, the utility 2 would enjoy from 1's share is 800 - 600 = 200 > 0, and hence 2 envies 1.

Example 1 shows that we cannot simultaneously satisfy individual rationality, budget limits, and envy-freeness.<fnref n="1" /> Should we conclude that the agents should give up renting the flat and look for another one? We believe not, and propose two solutions:

1. Allocate $r_1$ to 1 with payment 600 and $r_2$ to 2 with payment 400. The allocation is individually rational and respects individual budgets. It is not envy-free in the classical sense, but we may argue that 2's envy towards 1 is not justified: if 2 was allocated $r_1$ with payment 600, she would not be able to pay. Therefore, this allocation satisfies a weakening of envy-freeness, that we call *budget-friendly* envy-freeness (B-EF).

2. Allocate $r_1$ to 1 and $r_2$ to 2 for the first half of the year and then swap the rooms for the second half, asking a payment of 500 to each agent. This *fractional* allocation is envy-free (provided preferences do not depend on time), is individually rational, and respects budgets.

We explore these two ways of enlarging the set of fair allocations: budget-friendly envy-freeness and fractional allocations. After discussing related work, we present the basic definitions in Section 3. Section 4 defines B-EF, and shows algorithms to find a B-EF solution if either payments or the allocation is fixed. Section 5 turns to fractional envy-free allocations, which can be computed in polynomial time when they exist, and considers the *temporal implementation* of fractional allocations, with the aim to minimise the number of times agents have to change room. Last, we experimentally show in Section 6 that relaxing EF to B-EF and considering fractional allocations make it possible to enlarge significantly the set of instances for which a fair solution to a rent division problem exists.

## 2 Related Work

**Rent division.** The rent division problem was first studied in the economics literature and more recently became the most used application on the spladdit.org webpage. Initially, spladdit implemented an algorithm by Abdulkadiroğlu et al. [2], which was updated based on the work of Gal et al. [11], who provided a linear program that finds a solution maximising both the utility of the worst-off agent and

<footnote n="1">¹ A similar example can be constructed even if, for each agent, the sum of all valuations is equal to the rent.</footnote>
minimising the gap between the best and the worst-off agent. For a unifying treatment of contributions in rent division in economics and computer science we refer to recent work by Velez [20].

**Envy-freeness with budgets.** Our work takes its roots in the contribution of Procaccia et al. [17], who developed a polynomial algorithm to compute the maximin envy-free solution for rent division under budget. In the presence of individual budgets, the algorithm of Gal et al. [11] cannot be used as the existence of payments making any efficient allocation of rooms envy-free is not guaranteed. The general results of Segal-Halevi [18] are also not applicable since the preferences induced by the budget constraint are not continuous. Our paper tackles the problem left open by Procaccia et al. [17] of what solution to propose when no envy-free solution exists. To the best of our knowledge the work of Velez [21] is the only other paper considering budgets. The solution proposed is to lift the assumption of quasi-linearity of preferences and ask agents to report their marginal disutility for exceeding their budget. Velez [22] investigates the incentive-compatibility of such mechanisms. Our notion of budget-friendly envy-freeness draws inspiration from work on envy-freeness in fair division with budgeted bidders [3, 4, 13, 14], and is related (in spirit) to justified envy-freeness in two-sided matching [1].

**Randomised matching and fair division.** Allowing randomised solutions is a thoroughly studied idea in fair division and matching problems [6, 15]. Indeed, allowing more expressive solutions through, e.g., time sharing mechanisms, makes it possible to increase fairness guarantees and to bypass impossibility results [5, 7]. Randomised solutions for the rent division problem (without budgets) have been already investigated by Dufton and Larson [9], who studied to which extent randomised mechanisms can be strategy-proof and provide envy-freeness guarantees once a deterministic solution is sampled. Technically speaking, a fractional allocation and a randomised allocation are identical objects, but their interpretations differ. Also, our focus is not on strategyproofness but on envy-freeness: we determine if an envy-free fractional solution exists when agents have budgets and we seek for an implementation of such a solution that minimises the number of room swaps.

# 3 The Model

In this section, we present the model of rent division with individual budgets, and the properties of individual rationality and envy-freeness that are the focus of this paper.

## 3.1 Basic definitions

We consider a set $R$ of $n$ rooms that need to be allocated to a set $A$ of $n$ agents. Each agent $i \in A$ has a valuation $v_{ij} \in \mathbb{R}^+$ over each room $j \in R$, and $L$ is the total rent that needs to be paid to secure the rooms. Note that differently than previous work we do not assume that $\sum_{j \in R} v_{ij} = L$. A rent division problem is a tuple $(n, V, L)$ where $V = (v_{ij})_{i \in A, j \in R}$.

A solution to a rent division problem consists of an assignment $\sigma: A \to R$ and a payment vector $p: A \to \mathbb{R}$, such that $\sum_{i \in A} p_i = L$. Note that payments can possibly be negative. An assignment $\sigma$ is efficient if $\sum_{i \in A} v_{i\sigma(i)}$ is maximal over all possible allocations. Now we add a budget $b_i \in \mathbb{R}^+$ for each agent $i$. A solution is affordable if $p_i \le b_i$ for all $i \in A$. Without loss of generality, we assume that $\sum_{i \in A} b_i \ge L$ (the agents can afford the total rent). A

rent division problem with individual budgets is a tuple $(n, V, L, b)$, where $\langle n, V, L \rangle$ is a rent division problem and $b = (b_1, \dots, b_n)$.

## 3.2 Envy-freeness

In line with previous work, we assume that agents have quasi-linear utilities, and say that a solution $(\sigma, p)$ is *envy-free* (EF) if no agent can increase her utility by exchanging her assigned room and payment with another agent: $(\sigma, p)$ is EF if $v_{i\sigma(i)} - p_i \ge v_{i\sigma(j)} - p_j$ for all agents $i, j \in A$. While a rent division problem with unlimited budgets always admits an EF solution [19], this is not true in our setting, as shown by the following example.

**Example 2.** Consider two rooms $r_1$ and $r_2$, and two agents with budget 500 each. Both agents value $r_1$ at 600 and $r_2$ at 400. The total rent is 1000, hence each agent has to pay 500, and the agent who gets $r_2$ envies the agent who gets $r_1$.

## 3.3 Individual rationality

A solution $(\sigma, p)$ is *individually rational* (IR) if for all agents $i$ we have that $v_{i\sigma(i)} - p_i \ge 0$. Under our assumptions EF does not imply IR, as can be seen in the following example.

**Example 3.** Consider the following 2-agent rent division problem where $L = 1000$:

<table><thead><tr><th></th><th>room r<sub>1</sub></th><th>room r<sub>2</sub></th><th>budget</th></tr></thead><tbody><tr><td>agent 1</td><td>600</td><td>100</td><td>700</td></tr><tr><td>agent 2</td><td>100</td><td>300</td><td>300</td></tr></tbody></table>

Let $\sigma$ assign $r_1$ to 1 paying 700 and $r_2$ to 2 paying 300. $(\sigma, p)$ is not IR, since the utility of 1 is $-100$, but it is EF: 2 (resp. 1) would have utility $-600$ (resp. $-200$) if she received $r_1$ and had to pay 700 (resp. received $r_2$ and had to pay 300), which is less than their current utility.

An IR solution to a rent division problem under budget can be found in polynomial time by solving a matching problem.

**Proposition 1.** We can determine if there exists an IR and affordable allocation in polynomial time.

**Proof sketch.** Consider the bipartite graph $((A, R), E)$. Add arcs $e_{a,r} \in E$ between each vertex $a \in A$ and $r \in R$ with weight $\min\{b_a, v_{ar}\}$. This weight is the maximal price that agent $a$ can pay for room $r$ in an IR affordable allocation. It is sufficient to test if the matching of maximal weight on $((A, R), E)$ has total payoff greater than $L$, otherwise no IR and affordable allocation exists. $\square$

# 4 Budget-Friendly Envy-Freeness

When individual payments are bounded by a budget, the notion of envy can be restricted to rooms an agent can afford, obtaining a natural relaxation of envy-freeness.

**Definition 1.** A solution $(\sigma, p)$ is budget-friendly envy-free (B-EF) if for all agents $i$ we have that:

$$v_{i\sigma(i)} - p_i \ge v_{i\sigma(j)} - p_j \text{ for all agents } j \in A \text{ such that } p_j \le b_i.$$

For two agents $i, j \in A$, we will say that agent $i$ is B-envious of agent $j$ when $v_{i\sigma(i)} - p_i < v_{i\sigma(j)} - p_j$ and $p_j \le b_i$.
**Example 4.** Consider a two-agent rent division problem with rent $L = 800$. The individual valuations and budgets are given in the following table:

<table><thead><tr><th></th><th>room r<sub>1</sub></th><th>room r<sub>2</sub></th><th>budget</th></tr></thead><tbody><tr><td>agent 1</td><td>500</td><td>200</td><td>500</td></tr><tr><td>agent 2</td><td>700</td><td>300</td><td>300</td></tr></tbody></table>

Let $\sigma$ allocate $r_1$ to agent 1 and $r_2$ to agent 2, and let $p_1 = 500$ and $p_2 = 300$. In $(\sigma, p)$, 1 does not envy 2, but 2 envies 1 because she would get utility $700 - 500 = 200$ if she was assigned $r_1$ with payment 500, therefore $(\sigma, p)$ is not EF. However, $(\sigma, p)$ is B-EF: 2 does not envy 1 under Definition 1 because 1's payment (500) exceeds 2's budget (300).

Observe that the allocation $\sigma$ in Example 4 is not efficient. This contrasts with the classical setting of rent division where EF solutions are necessarily based on efficient allocations. Still, we can show that B-EF solutions are Pareto-optimal. One can show that this implies that B-EF solutions are based on Pareto-optimal allocations.

**Proposition 2.** If $(\sigma, p)$ is a B-EF solution then $(\sigma, p)$ is a Pareto-optimal solution, i.e., there is no solution $(\theta, q)$ such that for all $i \in A$ we have $v_{i\theta(i)} - q_i \ge v_{i\sigma(i)} - p_i$, and such that $v_{i\theta(i)} - q_i > v_{i\sigma(i)} - p_i$, for some agent $i \in A$.

*Proof.* Let $(\sigma, p)$ be a B-EF solution. Let us assume towards a contradiction that there exists another solution $(\theta, q)$ that Pareto-dominates $(\sigma, p)$. We first prove that all rooms are paid the same price in $(\sigma, p)$ and $(\theta, q)$. Let us assume there exists a room $j$ for which the price is strictly larger in $(\theta, q)$ than in $(\sigma, p)$. Let $k, l$ be the two agents such that $\theta(k) = \sigma(l) = j$. Our assumption is that $q_k > p_l$. We obtain that:

$$v_{k\sigma(k)} - p_k \le v_{k\theta(k)} - q_k \quad (\text{Pareto-domination of } (\sigma, p) \text{ by } (\theta, q)) \\ < v_{k\sigma(l)} - p_l \quad (q_k > p_l \text{ and } \theta(k) = \sigma(l)).$$

Since $p_l < q_k \le b_k$, agent $k$ B-envies $l$ in $\sigma$, yielding a contradiction. Hence no room has a larger price in $(\theta, q)$ than in $(\sigma, p)$. As $\sum_{i \in A} q_i = \sum_{i \in A} p_i = L$, this entails that all rooms have exactly the same price in both solutions. Let $k \in A$ be such that $v_{k\sigma(k)} - p_k < v_{k\theta(k)} - q_k$ (such an agent exists by Pareto dominance). Let $l \in A$ be such that $\sigma(l) = \theta(k)$. We obtain that:

$$v_{k\sigma(k)} - p_k < v_{k\theta(k)} - q_k \\ = v_{k\sigma(l)} - p_l \quad (\text{as } \sigma(l) = \theta(k) \text{ and } p_l = q_k)$$

Since $p_l = q_k \le b_k$, $k$ B-envies $l$ in $(\sigma, p)$, a contradiction. $\square$

<figure><img src="image_2.png" /></figure>

## 4.1 Computing B-EF solutions

An IR and B-EF solution, if existing, can be found by solving the following mixed-integer linear program.<fnref n="2" /> We use binary variables $x_{ij}$ for $i \in A$ and $j \in R$ to model the assignment, and continuous variables $p_i$ for $i \in A$ for the payments:

$x_{ij}, c_{ij}, d_{ij}$ are binary variables for $(i, j) \in A \times R$ 
$\lambda \in \mathbb{R}, p_i \in \mathbb{R}$ for $i \in A$

$$\begin{array}{ll} \sum_{i \in A} x_{ij} = 1 & \forall j \in R \\ \sum_{j \in R} x_{ij} = 1 & \forall i \in A \\ \sum_{i \in A} p_i = L \\ p_i \le b_i & \forall i \in A \\ (\sum_{j \in R} x_{ij}v_{ij}) - p_i \ge 0 & \forall i \in A \end{array}$$

For B-EF care must be taken for expressing that one agent can envy another when she can afford the payment.

$$\begin{array}{l} \sum_{j \in R} v_{ij}x_{ij} - p_i + Mc_{ii'} \ge \sum_{j \in R} v_{ij}x_{i'j} - p_{i'} \quad \forall i, i' \in A \\ c_{ii'} + d_{ii'} = 1 \quad \forall i, i' \in A \\ p_{i'} - c_{ii'}M \le b_i \quad \forall i, i' \in A \\ b_i - d_{ii'}M + \lambda \le p_{i'} \quad \forall i, i' \in A \end{array}$$

Recall that for B-EF an agent $i$ can envy another agent $i'$ only when she can afford the payment, i.e. when $p_{i'} \le b_i$. Our idea is to add in the envy-free statement a value $c_{ii'}M$ (where $M$ is a sufficiently large positive constant<fnref n="3" />) and enforce that $c_{ii'} = 0$ if and only if $p_{i'} \le b_i$. To do so, we introduce binary variables $d_{ii'}$, a continuous variable $\lambda \ge 0$, three constraints and we set the objective function as maximising $\lambda$. A B-EF solution exists if there exists a solution to the MILP satisfying the constraints and yielding a strictly positive $\lambda$ value. The first constraint ensures that one of $c_{ii'}$ or $d_{ii'}$ has value 1 and the other 0. The remaining two constraints are about affording the payment. If $i$ can afford the payment of $i'$, i.e., $b_i \ge p_{i'}$, then it is not possible to have $c_{ii'} = 1$, for otherwise $d_{ii'}$ would be 0 and no value of $\lambda > 0$ would satisfy the constraint $b_i + \lambda \le p_{i'}$. Thus, in this case $c_{ii'} = 0$, $d_{ii'} = 1$, $\lambda$ is bounded by $p_{i'} - b_i + M > 0$, and the envy statement applies from agents $i$ to $i'$ as intended. When $i$ cannot afford the payment of $i'$, i.e., $b_i < p_{i'}$, then $c_{ii'}$ must be 1 to satisfy the constraint $p_{i'} - c_{ii'}M \le b_i$. Then $d_{ii'} = 0$ and $\lambda$ is bounded by $p_{i'} - b_i > 0$.

We conjecture that the general problem of finding B-EF solutions is NP-hard, but we do not have a proof. However, in practice, the number of agents (and rooms) is small, so the number of allocations is reasonably small. Below we give an algorithm that, given a fixed initial allocation, computes a payment vector that satisfies B-EF, whenever there exists one, in pseudo-polynomial time. Further, we also give a polynomial-time algorithm that finds a B-EF solution, if any, in polynomial time when the payment vector is fixed.

## 4.2 Computing B-EF solutions: fixed allocation

Here, we fix an allocation and we check in pseudo-polynomial time whether a B-EF solution exists, and when it does, we output a corresponding price vector. To obtain our pseudo-polynomiality result we restrain in this subsection the input parameters $L$, $v_{ij}$ and $b_i$ to $\mathbb{Z}^+$ for all $i \in A$ and $j \in R$.

We first define a weakening of budget envy-freeness: given a solution $(\sigma, p)$, we say that agent $i$ strongly B-envies (SB-envies) $j$ if $p_j < b_i$ and $v_{i\sigma(j)} - p_j > v_{i\sigma(i)} - p_i$; and that $(\sigma, p)$ is weakly budget envy-free (WB-EF) if no agent SB-envies another one. Remark that if $i$ B-envies $j$ but does not strongly B-envies $j$ then $p_j = b_i$ and $v_{i\sigma(j)} - p_j > v_{i\sigma(i)} - p_i$.

Our result uses Algorithm 1 of Kempe et al. [14], which finds minimal payments for a given allocation so that the resulting solution is WB-EF, and runs in pseudo-polynomial time. As Kempe et al. [14] do not use the concept of a rent, we add a final processing stage guaranteeing that the payments sum up to the rent, and that the solution is B-EF (not only WB-EF).

Algorithm 1 of [14] starts from a lower bound on initial agents' payments, and iteratively increases payments in order to eliminate SB-envy relations by reasoning on a weighted envy graph $G_p$: given

<footnote n="2">² A B-EF solution does not always exist, as can be seen by adapting the introductory example by Procaccia et al. [17] or in Example 2.</footnote>

<footnote n="3">³ E.g., $M$ can be set to $(\max_{ij} v_{ij}) + (\max_{i} b_i) + (\sum_{i \in A} b_i)$ which is a loose upper bound on envy as $-(\sum_{i \in A} b_i)$ is a lower bound on the possible payment of an agent.</footnote>
**Algorithm 1: B-EF payment, allocation fixed**

**Data:** instance $\langle n, V, L, b \rangle$, allocation $\sigma$

1. Start from $p_i = L - \sum_{k \in A \setminus \{i\}} b_k$, $\forall i \in A$;

2. Run Strong B-Envy Removal (cf. Algorithm 1 of [14]);

3. Run Final Payment Increase;

4. **return** $(\sigma, p)$

**Algorithm 2: Strong B-Envy Removal**

**Data:** instance $\langle n, V, L, b \rangle$, allocation $\sigma$, payment $p$

1. **while** There exists edge $(i, j) \in G_p$ with $p_j < p_i - \lambda_{ij}$ **do**

2. $p_j \leftarrow \min\{b_i, p_i - \lambda_{ij}\}$;

3. delete $(u, k)$ from $G_p$ for all $(u, k)$ such that $p_k \ge b_u$;

4. **if** $p_j > b_j$ or $p_j > v_{j\sigma(j)}$ **then return** no solution;

5. **if** $\sum_{i \in A} p_i > L$ **then return** no solution;

6. **return** $(\sigma, p)$

an allocation $\sigma$ and a payment vector $p$, $G_p$ is defined by taking $n$ nodes, adding edge $(i, j)$ if $p_j < b_i$, and labeling it with $\lambda_{ij} = v_{i\sigma(i)} - v_{i\sigma(j)}$. That is, $G_p$ contains an edge from $i$ to $j$ if $i$ can afford the price paid by $j$. Observe that the labels of the edges do not depend on the payments: they only represent the potential envy generated by the allocation $\sigma$.

**Theorem 1.** Given a fixed allocation $\sigma$, we can determine in pseudo-polynomial time whether there exists a payment vector $p$ such that $(\sigma, p)$ is affordable, IR, and B-EF.

*Proof sketch.* Our Algorithm 1 starts from an initial payment vector $p = (L - \sum_{k \in A \setminus \{1\}} b_k, \dots, L - \sum_{k \in A \setminus \{n\}} b_k)$ and draws the envy graph $G_p$. It then uses Algorithm 2 (which corresponds to Algorithm 1 in [14]) to remove SB-envy, if possible, among the agents. If the algorithm does not output a payment vector, or if the sum of payments exceeds the rent, then no solution exists. If Algorithm 2 returns a solution such that the sum of the payments is lower than the rent, then we increase the payments uniformly (up to the budget or the valuation of the assigned room) to obtain a B-EF solution using Algorithm 3. If this is not possible because of an incompatibility with B-EF, budget limits, or IR, then we output that there is no solution. □

We explain our proposed algorithm on the following example:

**Example 5.** Let $n = 3$, $R = \{r_1, r_2, r_3\}$, $L = 1000$, valuations and budgets as follows:

<table><thead><tr><th></th><th>room r1</th><th>room r2</th><th>room r3</th><th>budget</th></tr></thead><tbody><tr><td>agent 1</td><td>340</td><td>300</td><td>500</td><td>300</td></tr><tr><td>agent 2</td><td>290</td><td>350</td><td>470</td><td>380</td></tr><tr><td>agent 3</td><td>200</td><td>370</td><td>485</td><td>400</td></tr></tbody></table>

Consider the allocation $\sigma(i) = r_i$ for $i = 1, 2, 3$. We start from initial payments $p = (220, 300, 320)$, and draw the corresponding envy graph $G_p$:

<figure><img src="image_3.png" /></figure>

**Algorithm 3: Final Payment Increase**

**Data:** instance $\langle n, V, L, b \rangle$, allocation $\sigma$, payments $p$

1. $A' \leftarrow \{i \in A : p_i < \min\{b_i, v_{i\sigma(i)}\}\}$;

2. **while** $\sum_{i \in A} p_i < L$ **do**

3. **if** $A' = \emptyset$ **then return** no solution;

4. $\forall i \in A', m_i \leftarrow \min\{b_i, v_{i\sigma(i)}, \min_{j \in A \setminus A'} \sum_{p_j \le b_i} v_{i\sigma(i)} - v_{i\sigma(j)} + p_j\}$;

5. $q \leftarrow \max\{0, \min\left\{\frac{L - \sum_{i \in A} p_i}{|A'|}, \min_{i \in A'}\{m_i - p_i\}\right\}\}$;

6. **for each** $i \in A'$ **do** $p_i \leftarrow p_i + q$;

7. $A' \leftarrow \{i \in A' : p_i < m_i\}$;

8. **if** $(\sigma, p)$ is not B-EF **then return** no solution;

9. **return** $(\sigma, p)$

Then, when we run Algorithm 2, we can select the edge (2, 1) in $G_p$ such that $p_1 < p_2 - \lambda_{21}$, i.e., $\lambda_{21} = 60 < 300 - 220 = 80$. We treat this edge by updating $p_1$ to $\min\{380, 300 - 60\} = 240$. Then, we can select edge (2, 3) where $p_3 < p_2 - \lambda_{23}$, i.e., $-120 < -20$. We treat this edge by updating $p_3$ to $\min\{380, 300 - (-120)\} = 380$, hence, removing edge (2, 3) from $G_p$. We finally obtain payment $p = (240, 300, 380)$. This payment generates no SB-envy, and the sum of the payments is lower than the rent.

Now we increase the payment of the agents to reach the rent using Algorithm 3. We can first uniformly increase the payment of all agents by 20, reaching payment $p = (260, 320, 400)$, implying that agent 3 reaches her budget (and thus she will not be part of subset $A'$ anymore). Finally, we can uniformly increase the payment of agents 1 and 2 by 10, reaching payment $p = (270, 330, 400)$ to exactly reach the rent.

In Algorithm 2, we have at most $n^2$ edges to check at each iteration of the while loop, and we will have at most $n(\sum_{i \in A} b_i)$ iterations. So the algorithm runs in $(\sum_{i \in A} b_i)n^3$ operations. In Algorithm 3, the while loop runs for at most $n$ iterations, and each iteration of the loop requires $n^2$ operations due to Line 4. Hence, the algorithm runs in $O(n^3)$ operations. To sum up, we obtain a pseudo-polynomial algorithm, running in time $O((\sum_{i \in A} b_i)n^3)$, which is very reasonable.

Obtaining a polynomial algorithm would be even better. We thought of reusing Algorithm 2 of [14], which is claimed to compute a WB-EF solution in polynomial time, but we have doubts about its correctness (and no proof is given in [14]).

Still, now that we know that given an initial allocation, we can compute a payment vector that satisfies B-EF, whenever there exists one, in time $O((\sum_{i \in A} b_i)n^3)$. This implies that given the valuations, the rent and the budgets, we can compute a solution, if any, in time $O((\sum_{i \in A} b_i)n!n^3)$. In everyday rent division problems, $n$ is low (typically, no more than 5), therefore we can compute a solution in a reasonable amount of time.

**Discussion about the polynomial algorithm by Kempe et al. [14].**
We explain here our doubts about Algorithm 2 by Kempe et al. [14], which is claimed to be a polynomial-time algorithm for finding minimal payments that make the solution affordable, IR, and WB-EF, given an initial allocation. We start with the following example with two agents and two rooms, and the following valuations:

<table><thead><tr><th></th><th>room r1</th><th>room r2</th><th>budget</th></tr></thead><tbody><tr><td>agent 1</td><td>400</td><td>500</td><td>450</td></tr><tr><td>agent 2</td><td>0</td><td>500</td><td>500</td></tr></tbody></table>
Let $\sigma$ allocate $r_1$ to agent 1 and $r_2$ to agent 2. Starting with payments $p = (0, 0)$, we obtain the following envy graph $G_p$.

<figure><img src="image_4.png" /></figure>

Algorithm 2 by Kempe et al. [14] runs a while loop which is executed while there exists a negative cycle in $G_p$. At the end of the while loop the algorithm returns an affordable, IR, and B-EF price vector or claims that none exist. Note that in our example there is no negative cycle in $G_p$. Hence the algorithm would just return $p = (0, 0)$ which is not B-EF as agent 1 B-envies agent 2.

Note that in a positive cycle containing one negative arc, such as in the previous example, we can treat the negative arc by raising payments along the cycle (in a similar way as does Algorithm 1 in [14]) without having to pass twice by the same arc. This may not be true with more than one negative arc in such a positive cycle.

We believe that it may be possible to give some conditions, like those established in Algorithm 2 of Kempe et al. [14], to identify the agent from which to start the treatment of negative arcs in a positive cycle, in order to avoid treating several times the same arc in the cycle, but we leave this for future work.

## 4.3 Computing B-EF solutions: fixed payments

In practice, agents looking for flat-sharing will often search for apartments with a rent corresponding to their accumulated budget. In such a case, the payments are fixed as each agent $i$ must pay $b_i$ to reach the total rent $L$. We show that, more generally, given any fixed payment vector $p$, we can efficiently determine if there exists an assignment $\sigma$ of agents to rooms such that $(\sigma, p)$ is affordable, IR, and B-EF.

**Theorem 2.** Given a fixed payment vector $p$, we can determine if there exists an assignment $\sigma$ of agents to rooms such that $(\sigma, p)$ is affordable, IR, and B-EF in polynomial time.

*Proof sketch.* First, we can easily check whether the payments are compatible with an affordable solution which meets the rent. Our algorithm tries to build an IR and B-EF assignment in a greedy fashion considering agents in decreasing order w.r.t. payments, as follows: We partition the set of agents into $k$ groups $(B_1, \dots, B_k)$, i.e., $\bigcup_{\ell=1}^k B_\ell = A$ and $B_\ell \cap B_{\ell'} = \emptyset$ for every $\ell \neq \ell' \in [k]$, such that for all agents $i, j \in B_\ell, p_i = p_j$, and for all agents $i \in B_\ell$ and $j \in B_{\ell'}$ with $\ell < \ell'$, we have that $p_i > p_j$. Then, we consider sets $B_\ell$ with increasing values of $\ell$ (hence, with decreasing payments), and try to assign each agent $i$ in $B_\ell$ to a room in $\text{top}(i)$, the set compounded of her most preferred rooms within the remaining ones. This is done by considering a bipartite graph and determining if there exists a perfect matching in this graph. If there is no such an assignment, or if it violates an IR or B-EF constraint, then we conclude that no valid solution exists.

One can prove that this algorithm returns an assignment $\sigma$ such that $(\sigma, p)$ is affordable, IR and B-EF iff such an assignment exists. The key idea is that, for an assignment to be IR and B-EF, each agent $i$ must receive a room in $\text{top}(i)$. ☐

The algorithm described in the proof of Theorem 2 is illustrated in the next example.

**Example 6.** Consider the following 4-agent rent division problem where $L = 1000$:

<table><thead><tr><th></th><th>r<sub>1</sub></th><th>r<sub>2</sub></th><th>r<sub>3</sub></th><th>r<sub>4</sub></th><th>budget = payment</th></tr></thead><tbody><tr><td>agent 1</td><td>100</td><td>450</td><td>600</td><td>300</td><td>400</td></tr><tr><td>agent 2</td><td>400</td><td>400</td><td>700</td><td>200</td><td>250</td></tr><tr><td>agent 3</td><td>400</td><td>100</td><td>500</td><td>250</td><td>250</td></tr><tr><td>agent 4</td><td>300</td><td>100</td><td>400</td><td>300</td><td>100</td></tr></tbody></table>

The budgets sum to the rent, therefore the payment $p_i$ for each $i$ is fixed to her budget. The agents are partitioned into 3 groups w.r.t. their payments: $B_1 = \{1\}$, $B_2 = \{2, 3\}$, and $B_3 = \{4\}$. We can define for each agent her top subset of rooms, i.e., their most preferred rooms among the remaining ones by considering the agents in the order of their group: $\text{top}(1) = \{r_3\}$, $\text{top}(2) = \{r_1, r_2\}$, $\text{top}(3) = \{r_1\}$, and $\text{top}(4) = \{r_4\}$. A perfect matching, that satisfies the IR and B-EF constraints, can be found at each step $\ell \in [3]$ between agents in $B_\ell$ and rooms in $\bigcup_{i \in B_\ell} \text{top}(i)$. This process results in the unique assignment $\sigma$ such that $(\sigma, p)$ is IR and B-EF, where $\sigma(1) = r_3$, $\sigma(2) = r_2$, $\sigma(3) = r_1$, and $\sigma(4) = r_4$. Note that if, we change $v_{1,r_2}$ from 450 to 460, such an assignment $\sigma$ would not exist because agent 1 would necessarily B-envy agent 2.

# 5 Fractional Solutions

In this section, we propose a second alternative to envy-free allocations under individual budgets. The idea is to allow agents to spend a fraction of their time in different rooms, and we study possible implementations of the resulting fractional allocation that minimise the number of room swaps.

**Definition 2.** A fractional solution to a rent division problem is an $n \times n$ bistochastich matrix $X$, with $x_{ij}$ be the fraction of time agent $i$ spends in room $j$, and a price vector $p: A \to \mathbb{R}$, such that $\sum_{i \in A} p_i = L$.

The definitions of IR and EF easily extend to fractional solutions. We say that $(X, p)$ is individually rational under quasi-linear utilities if for all agents $i$ we have that $\sum_{j \in R} x_{ij}v_{ij} - p_i \ge 0$. Further, we say that a fractional solution $(X, p)$ is *envy-free* under quasi-linear utilities if the following holds for all agents $i$ and $i'$ in $A$:

$$ \sum_{j \in R} x_{ij}v_{ij} - p_i \ge \sum_{j \in R} x_{i'j}v_{ij} - p_{i'}. $$

Observe that the initial Example 2 admits a fractional EF-solution: let agent 1 spend 6 months a year in room $r_1$ and the remaining part in room $r_2$ (and symmetrically for agent 2). If both agents pay 500 their utility is 0 and by symmetry no agent envies the other. However, fractional EF-allocations do not always exist, as shown by the following example.

**Example 7.** Consider the following rent division problem under budget with $L = 1000$:

<table><thead><tr><th></th><th>room r<sub>1</sub></th><th>room r<sub>2</sub></th><th>budget</th></tr></thead><tbody><tr><td>agent 1</td><td>700</td><td>400</td><td>700</td></tr><tr><td>agent 2</td><td>800</td><td>300</td><td>300</td></tr></tbody></table>

The only affordable allocation is non-fractional: it assigns room $r_2$ to agent 2 at a price of 300, with 1 envying 2.

Allowing fractional allocations is a significant weakening that allows to obtain a solution for quite many instances for which there would be otherwise no solution. To illustrate this, we define below a family of instances for which this is indeed the case.
**Proposition 3.** For each budget vector $b = (b_1, \dots, b_n)$ such that $\frac{L}{n} \le b_i < L$, there exists a rent division problem which does not admit an affordable EF solution but admits a fractional one.

*Proof.* We first show that if $b_i \ge \frac{L}{n}$ for all $i \in A$, then $\langle n, V, L, b \rangle$ admits an affordable fractional EF allocation. To see this, fix payments $p_i = \frac{L}{n}$ to be equal for all agents. The fractional solution where all agents spend the same fraction of time in each room, i.e., $x_{ij} = 1/n$ for all $i$ and $j$, is an affordable EF solution.

Now, for all $i \in A$ we fix agent $i$'s evaluation of room $r_1$ at $b_i$, zero otherwise – that is, for all $i, v_{i1} = b_i$ and $v_{ij} = 0$ for $j \ge 2$. Assume, w.l.o.g., that an allocation gives room $r_1$ to agent 1. Given that $b_1 < L$ then $p_i > 0$ for at least one other agent, who has negative utility and envies agent 1. So no allocation is EF. □

## 5.1 Computing fractional solutions

Fractional solutions that are IR and EF, when they exist, can be found in polynomial time by using the following Linear Program (LP). The LP considers as variables $x_{ij} \in [0, 1]$ for $i \in A$ and $j \in R$ for the fraction of time $i$ spends in room $j$, and $p_i$ for $i \in A$ as the price of agent $i$. The set of linear constraints is the following, formalising that each agent has a room allocated all of the time, that the payments sum to the rent, with the last two lines enforcing IR and EF:

$$ 
\begin{array}{ll}
\sum_{i \in A} x_{ij} = 1 & \forall j \in R \\
\sum_{j \in R} x_{ij} = 1 & \forall i \in A \\
\sum_{i \in A} p_i = L & \\
p_i \le b_i & \forall i \in A \\
(\sum_{j \in R} x_{ij}v_{ij}) - p_i \ge 0 & \forall i \in A \\
(\sum_{j \in R} x_{ij}v_{ij}) - p_i \ge (\sum_{j \in R} x_{i'j}v_{ij}) - p_{i'} & \forall i, i' \in A
\end{array}
$$

When this set of linear constraints has a solution, it may in fact have many solutions. As in Procaccia et al. [17] (cf. their Theorem 1), the objective function can be defined so as to maximise a fairness criterion, such as: $\maxmin$ (with one additional variable $y$, add constraints $y \le (\sum_{j \in R} x_{ij}v_{ij}) - p_i$ for all agents $i$ and, as objective function, maximise $y$); or $\equitability$ (with one additional variable $y$, add constraints $y \ge (\sum_{j \in R} x_{ij}v_{ij}) - p_i - (\sum_{j \in R} x_{i'j}v_{ij}) + p_{i'}$ for any $i$ and $i'$ and, as objective function, minimise $y$).

## 5.2 Implementing fractional allocations

A fractional solution to a rent division problem can give rise to multiple practical implementations, depending on the sequence of room swaps that agents perform. By Birkhoff's theorem we know that any bistochastic matrix $X$ can be decomposed as the convex combination of permutation matrices. In our terminology, this implies that for any fractional solution $X$ there exist $\lambda_1, \dots, \lambda_k \in (0, 1]$, with $\sum_t \lambda_t = 1$, and $\sigma_1, \dots, \sigma_k$ deterministic solutions, such that for all $i \in A$ and $j \in R$ we have that $\sum_{\{t|\sigma_t(i)=j\}} \lambda_t = x_{ij}$. In line with previous work, we call such a representation a Birkhoff-von Neumann (BvN) decomposition of $X$ of size $k$. The order in which the permutations of a BvN decomposition are considered gives rise to different implementations of a given fractional solution $X$ in terms of room swaps:

**Definition 3.** An implementation $I$ of length $k$ of a fractional solution $X$ is given by $(\Lambda, <)$ where $\Lambda$ is a $k$-BvN decomposition of $X$ and $<$ is an ordering on $[k] = 1, \dots, k$.

When $I$ is fixed, for simplicity we will assume that $\sigma_1, \dots, \sigma_k$ are given following ordering $<$. To discriminate between possible implementations of a fractional solution $X$, we define a natural notion that counts the overall number of swaps that an agent has to perform:

**Definition 4.** Given an implementation $I$ of $X$, the switch price of agent $i$ in $I$ is

$$S_i(I) = |\{t \in \{1, \dots, k-1\} : \sigma_t(i) \neq \sigma_{t+1}(i)\}|.$$

The following example shows that an implementation in which agents never move back to the same room is not guaranteed to exist:

**Example 8.** Consider the following fractional allocation $X$:

<table><thead><tr><th></th><th>room r<sub>1</sub></th><th>room r<sub>2</sub></th><th>room r<sub>3</sub></th></tr></thead><tbody><tr><th>agent 1</th><td>0.6</td><td>0.3</td><td>0.1</td></tr><tr><th>agent 2</th><td>0.2</td><td>0.5</td><td>0.3</td></tr><tr><th>agent 3</th><td>0.2</td><td>0.2</td><td>0.6</td></tr></tbody></table>

Agents 1 and 3 have to spend 60% of the time in a room, and agent 2 only 50%. Thus, one of 1 and 3 has to go back to the same room in any implementation of $X$.

## 5.3 Computing minimal-switching implementations

We now show that finding an implementation of a fractional solution minimising the number of switches is computationally hard. We begin by the following decision problem.

### MINSUM-SWITCH-IMPLEMENTATION

INPUT: Fractional solution $X$, $k \in \mathbb{N}$

QUESTION: is there an implementation $I$ of $X$ such that $\sum_{i \in A} S_i(I) \le k$?

**Theorem 3.** MINSUM-SWITCH-IMPLEMENTATION is NP-complete.

*Proof sketch.* Membership to NP is straightforward. For hardness we reduce from PARTITION. Given an instance $U = \{v_1, \dots, v_n\}$ of PARTITION with $S = \sum_{i=1}^n v_i$, create a $3n \times 3n$ bistochastic matrix $X$ as depicted on Table 1. We first observe that $X$ admits an implementation in which no agent returns to the same room iff there is an implementation with $\sum_{i \in A} S_i(I) = (n+2)n+3n+2n = n^2+7n$ (this can be seen by counting the number of non-zero cells in each row of $X$). Further, for each value $v \in U$ and agent in $A_i^1$, there is a room $R^*(i, v) \in \{R_1^1, R_2^1, \dots, R_n^1\}$ with value $v$ in the matrix. We call $R^*(i, v)$ the $v$-corresponding room for agent $A_i^1$. One can prove that there is a solution to PARTITION iff $X$ admits an implementation with $\sum_{i \in A} S_i(I) \le n^2 + 7n$, which is equivalent to the existence of an implementation where no agent returns in any room. □

Now, we show that even if the deterministic allocations composing a BvN decomposition are fixed, finding an ordering that minimises the switch cost is an intractable problem.

### MINSUM-SWITCH-ORDERING

INPUT: BvN decomposition $\Lambda$ of length $k$, $K \in \mathbb{N}$

QUESTION: is there an ordering $<$ over $[k]$ such that $\sum_{i \in A} S_i(I) \le K$ where $I = (\Lambda, <)$?

**Theorem 4.** MINSUM-SWITCH-ORDERING is NP-complete.
<table><caption>**Table 1.** The matrix used in the reduction of Theorem 3. It can be made bistochastic by dividing every cell by 3S.</caption><thead><tr><th></th><th>R<sup>1</sup><sub>1</sub></th><th>R<sup>1</sup><sub>2</sub></th><th>...</th><th>R<sup>1</sup><sub>n</sub></th><th>R<sup>2</sup><sub>1</sub></th><th>R<sup>2</sup><sub>2</sub></th><th>...</th><th>R<sup>2</sup><sub>n</sub></th><th>R<sup>3</sup><sub>1</sub></th><th>R<sup>3</sup><sub>2</sub></th><th>...</th><th>R<sup>3</sup><sub>n</sub></th></tr></thead><tbody><tr><th>A<sup>1</sup><sub>1</sub></th><td>v<sub>1</sub></td><td>v<sub>n</sub></td><td>...</td><td>v<sub>2</sub></td><td>S</td><td>0</td><td>...</td><td>0</td><td>S</td><td>0</td><td>...</td><td>0</td></tr><tr><th>A<sup>1</sup><sub>2</sub></th><td>v<sub>2</sub></td><td>v<sub>1</sub></td><td>...</td><td>v<sub>n</sub></td><td>0</td><td>S</td><td>...</td><td>0</td><td>0</td><td>S</td><td>...</td><td>0</td></tr><tr><th>...</th><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td></tr><tr><th>A<sup>1</sup><sub>n</sub></th><td>v<sub>n</sub></td><td>v<sub>n-1</sub></td><td>...</td><td>v<sub>1</sub></td><td>0</td><td>0</td><td>...</td><td>S</td><td>0</td><td>0</td><td>...</td><td>S</td></tr><tr><th>A<sup>2</sup><sub>1</sub></th><td>2S</td><td>0</td><td>...</td><td>0</td><td>1/2S</td><td>0</td><td>...</td><td>0</td><td>1/2S</td><td>0</td><td>...</td><td>0</td></tr><tr><th>A<sup>2</sup><sub>2</sub></th><td>0</td><td>2S</td><td>...</td><td>0</td><td>0</td><td>1/2S</td><td>...</td><td>0</td><td>0</td><td>1/2S</td><td>...</td><td>0</td></tr><tr><th>...</th><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td></tr><tr><th>A<sup>2</sup><sub>n</sub></th><td>0</td><td>0</td><td>...</td><td>2S</td><td>0</td><td>0</td><td>...</td><td>1/2S</td><td>0</td><td>0</td><td>...</td><td>1/2S</td></tr><tr><th>A<sup>3</sup><sub>1</sub></th><td>0</td><td>0</td><td>...</td><td>0</td><td>3/2S</td><td>0</td><td>...</td><td>0</td><td>3/2S</td><td>0</td><td>...</td><td>0</td></tr><tr><th>A<sup>3</sup><sub>2</sub></th><td>0</td><td>0</td><td>...</td><td>0</td><td>0</td><td>3/2S</td><td>...</td><td>0</td><td>0</td><td>3/2S</td><td>...</td><td>0</td></tr><tr><th>...</th><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td></tr><tr><th>A<sup>3</sup><sub>n</sub></th><td>0</td><td>0</td><td>...</td><td>0</td><td>0</td><td>0</td><td>...</td><td>3/2S</td><td>0</td><td>0</td><td>...</td><td>3/2S</td></tr></tbody></table>

*Proof sketch.* Membership to NP is straightforward. Hardness is shown by reduction from the NP-hard HAMMING SALESMAN PROBLEM (HSP) [10]. An instance of HSP is a string $P = v_1...v_n, L$, where $v_i \in \{0, 1\}^m$, for some $n$ and $m$, and $L$ is an integer in binary representation. The question is whether there exists a Hamiltonian cycle over vertices $v_i$ of total cost less than $L$, where the distance between two nodes is given by the Hamming distance. One can show that finding a Hamiltonian path instead of a Hamiltonian cycle is also NP-hard. Consider now an instance $P = v_1...v_n, L$ of HSP. We create an instance of MINSUM-SWITCH-ORDERING with 2m agents and 2m rooms. For each vertex $v$ we create a deterministic allocation $\sigma^v$ of the rooms as follows: agent $i$ will be assigned to room $i$ (resp. $m+i$) and agent $m+i$ will be assigned to room $m+i$ (resp. $i$) if the $i$-th bit of $v$ is 0 (resp. 1), for all $i$ in $[m]$. It is clear that the switch cost between $\sigma^v$ and $\sigma^{v'}$ is equal to two times the Hamming distance between $v$ and $v'$. Thus, there is a one-to-one correspondence between Hamiltonian paths on vertices of $P$ and orderings of solutions $\sigma^v$. It is therefore sufficient to run MINSUM-SWITCH-ORDERING on an implementation composed of $\sigma^v$ for $v \in P$ and $K = 2L$ to obtain a solution to the initial HSP instance. $\square$

We conjecture that minimising the maximum switch cost is NP-hard as well. Dufossé and Uçar [8] showed that the problem of finding a BvN decomposition with the smallest support (i.e., with the smallest $k$) is NP-hard, but this does not necessarily correspond to an implementation which minimises the switch cost.

Even if we showed that finding minimal-switching implementations is computationally hard, the number of agents in typical rent division problems is low, thus the size $k$ of a BvN decomposition is also likely to be small, since $k \le n^2$. Hence, finding minimal-switching implementations can still be performed, e.g., by working on the polytope of deterministic assignments. For instance, MINSUM-SWITCH-ORDERING can easily be solved by dynamic programming in $O^*(2^k)$ by using the formula:

$$ \Delta(\sigma, S) = \min_{\sigma' \in S \setminus \{\sigma\}} (sc(\sigma, \sigma') + \Delta(\sigma', S \setminus \{\sigma\})) $$

where $sc(\sigma, \sigma') = |\{i \in A | \sigma(i) \neq \sigma'(i)\}|$ is the switch-cost incurred by moving from $\sigma$ to $\sigma'$ and $\Delta(\sigma, S)$ is the minimal switch cost incurred by ordering permutations in $S \subseteq \Lambda$ under the constraint that $\sigma$ is placed in the first position. The base cases are $\Delta(\sigma, \{\sigma\}) = 0$, and the optimal MINSUM-SWITCH-ORDERING value is obtained by considering $\min_{\sigma \in \Lambda} \Delta(\sigma, \Lambda)$.

# 6 Discussion

We proposed two approaches to increase the number of instances where a fair rent division is returned. The first one relaxes the notion

<figure><img src="image_5.png" /><figcaption>**Figure 1.** Proportion of rent division instances that admit a solution that is IR and EF, B-EF, fractional (F-EF), or an extension of fractional with B-EF replacing EF (F-BEF), depending on the tightness of the agents’ budgets.</figcaption></figure>

of envy-freeness to take budget discrepancies into consideration. The second one allows for fractional allocations that are implemented by having agents swap their rooms (and minimising the number of swaps). We can of course combine the two approaches and define B-EF fractional solutions. We leave this mostly for further study (but see below for how we considered it in our experiments).

We evaluated in simulations the number of additional solutions that our proposals can provide in synthetically generated rent division problems. We generated the agents’ valuations of rooms starting from a base value $M_j$ for each room $j$, sampled from a uniform distribution in [25, 50]. All other parameters are sampled from the following normal distributions:

$$ v_{ij} \sim \mathcal{N}(M_j, \alpha M_j), \quad L \sim \mathcal{N}\left(\sum_{j \in R} M_j, \alpha \sum_{j \in R} M_j\right), \\ b_i \sim \mathcal{N}\left(\sum_{j \in R} \frac{M_j}{n}, \alpha \sum_{j \in R} \frac{M_j}{n}\right), $$

where $0 < \alpha < 1$. In this way, we generate rent division problems where agents have correlated valuations for the rooms, and have a budget that is roughly one $n$-th of the rent to be paid (i.e., the agents can pay the rent but their budget is tight). We discarded all instances that did not admit an IR solution, and we then increased the individual budgets by multiplying them by a *budget tightness* factor which varies between 1 and 2.

Figure 1 presents our findings for 3 agents setting $\alpha = 0.1$. We observe that B-EF and fractional solutions increase significantly the fraction of instances in which a fair allocation exists. In the extreme case of budget tightness equal to 1, there are twice more instances with a B-EF solution than with a classical EF solution. As expected, when the budget is less tight it becomes more and more likely to find a solution (irrespective of the fairness criteria).<fnref n="4" /> We find similar results for $n \in \{2, 4, 5\}$ and different values of $\alpha$.

Identifying the computational complexity of determining the existence of B-EF solutions seems to be a challenging open problem. A further interesting direction is to estimate the robustness of our solutions under perturbations of the individual budgets, in line with [16], who however focuses on the agents’ valuations.

<footnote n="4">⁴ There exist however (few) rent division problems that do not admit an IR and EF solution, even with unlimited budgets (recall that we do not assume that individual valuations sum to the rent).</footnote>
Acknowledgements

This work is supported by the ANR project AGAPE (ANR-18-
CE23-0013), ANR project SCONE (ANR 18-CE23-0009-01), and
the PRAIRIE 3IA Institute (ANR-19-P3IA-0001). This work was
conducted while Umberto Grandi was on leave at CNRS.

References

[1] Atila Abdulkadiroğlu and Tayfun Sönmez, ‘School choice: A mechanism design approach’, *American Economic Review*, **93**(3), 729–747, (2003).

[2] Atila Abdulkadiroğlu, Tayfun Sönmez, and M Utku Ünver, ‘Room assignment-rent division: A market approach’, *Social Choice and Welfare*, **22**(3), 515–538, (2004).

[3] Gagan Aggarwal, Shan Muthukrishnan, Dávid Pál, and Martin Pál, ‘General auction mechanism for search advertising’, in *Proceedings of the 18th International Conference on World Wide Web (WWW)*, (2009).

[4] Itai Ashlagi, Mark Braverman, Avinatan Hassidim, Ron Lavi, and Moshe Tennenholtz, ‘Position auctions with budgets: Existence and uniqueness’, *The B.E. Journal of Theoretical Economics*, **10**(1), (2010).

[5] Haris Aziz, ‘A probabilistic approach to voting, allocation, matching, and coalition formation’, in *The Future of Economic Design*, 45–50, Springer, (2019).

[6] Anna Bogomolnaia and Hervé Moulin, ‘A new solution to the random assignment problem’, *Journal of Economics Theory*, **100**(2), 295–328, (2001).

[7] Florian Brandl, Felix Brandt, and Hans Georg Seedig, ‘Consistent probabilistic social choice’, *Econometrica*, **84**(5), 1839–1880, (2016).

[8] Fanny Dufossé and Bora Uçar, ‘Notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices’, *Linear Algebra and its Applications*, **497**, 108–115, (2016).

[9] Lachlan Dufton and Kate Larson, ‘Randomised room assignment-rent division’. Presented at the IJCAI Workshop on Social Choice and Artificial Intelligence, Barcelona, Spain, 2011.

[10] Jarmo Ernvall, Jyrki Katajainen, and Martti Penttonen, 'NP-completeness of the Hamming salesman problem', *BIT Numerical Mathematics*, **25**(1), 289–292, (1985).

[11] Ya'akov Gal, Moshe Mash, Ariel D Procaccia, and Yair Zick, ‘Which is the fairest (rent division) of them all?’, *Journal of the ACM (JACM)*, **64**(6), 1–22, (2017).

[12] Jonathan R Goldman and Ariel D Procaccia, ‘Spliddit: unleashing fair division algorithms’, *ACM SIGecom Exchanges*, **13**(2), 41–46, (2014).

[13] Monika Henzinger and Veronika Loitzenbauer, ‘Truthful unit-demand auctions with budgets revisited’, *Theoretical Computer Science*, **573**, 1–15, (2015).

[14] David Kempe, Ahuva Mu'alem, and Mahyar Salek, 'Envy-free allocations for budgeted bidders', in *Proceedings of the 5th International Workshop on Internet and Network Economics (WINE)*, (2009).

[15] Jinpeng Ma, ‘On Randomized Matching Mechanisms’, *Economic Theory*, **8**(2), 377–381, (1996).

[16] Dominik Peters, Ariel D Procaccia, and David Zhu, ‘Robust rent division’, in *Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS)*, (2022).

[17] Ariel D. Procaccia, Rodrigo A. Velez, and Dingli Yu, ‘Fair rent division on a budget’, in *Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI)*, (2018).

[18] Erel Segal-Halevi, ‘Generalized rental harmony’, *The American Mathematical Monthly*, **129**(5), 403–414, (2022).

[19] Lars-Gunnar Svensson, ‘Large indivisibles: an analysis with respect to price equilibrium and fairness’, *Econometrica: Journal of the Econometric Society*, 939–954, (1983).

[20] Rodrigo A Velez, ‘Equitable rent division’, *ACM Transactions on Economics and Computation (TEAC)*, **6**(2), 1–25, (2018).

[21] Rodrigo A Velez, ‘A polynomial algorithm for maxmin and minmax envy-free rent division on a soft budget’, *Social Choice and Welfare*, **59**, 1–26, (2022).

[22] Rodrigo A Velez, ‘Equitable rent division on a soft budget’, *Games and Economic Behavior*, **139**, 1–14, (2023).