Room Allocation and Rent Division: Mechanism Design

Mechanism design for fair room allocation and rent division.

Problem statement

Imagine that you and your friend decide to rent an apartment together for an year. Having visited several properties, you have successfully finalized a place and completed the paperwork. But before the move-in process, there's an important issue, which is, different rooms in the apartment have different specifications and features. For e.g. one room has larger floor space, while the other one comes with a large window and a better view. So, how do you decide who gets to live in which room?

Naive solution

One might be inclined to start with a random room allocation, switch rooms halfway through the year and split the rent equally every month. While this approach is simple, it has some obvious drawbacks. First, room preferences can change with seasons—for example, the room with the big window is ideal in the summer for ventilation but it may lead to a lower room temperature during the winter season. Second, switching rooms means the extra hassle of packing up and moving things all over again. And when more than two friends are involved, changing rooms throughout the year becomes impractical. Hence, it is preferrable to consider an alternative solution to this problem.

Fair mechanism for room allocation and rent division

Fortunately, the problem of room allocation and rent division has been studied extensively in the field of game theory and mechanism design. In this article, we will look at one such solution proposed in the paper “Which Is the Fairest Rent Division of Them All?”.

Model

Let's begin by describing the model. Suppose there are \(N\) people renting an apartment with N rooms. Index these people and rooms as \(1,2,3\) all the way up to \(N\). Now, we ask each person to submit their valuation for each room such that they add up to the total rent.

\[\sum_j V_ij = R,\quad \forall i \]

We use \(V_{ij}\) to denote the valuation assigned by the \(i^{th}\) person to the \(j^{th}\) room. For the sake of clarity, we can accumulate these valuations and form a matrix. Using this valuation matrix, we want to design a fair mechanism to identify two things: first, an allocation function \(A\) that determines who gets to live in which room, and second, a rent division vector \(p\), whose \(i^{th}\) component decides the rent for occupying the \(i^{th}\) room.

Fairness

But wait a second, what do we mean by a "fair" mechanism? As fairness is a subjective idea, it can be defined in several ways. For our discussion, we will adopt envy-freeness as the criteria for fairness, since it is a widely accepted in the field of mechanism design.

To understand the envy-free property in the context of the room allocation and rent division problem, let's define a utility function or a payoff function for each person as the difference between his valuation of the room assigned to him and the rent of that room.

\[\text{Utility}_i=V_{iA(i)}-p_{A(i)}\]

For e.g. if the person \(i\) is allocated the room \(j\), his payoff would be equal to \(V_{ij}-p_j\). We say that the room allocation function A and the rent division vector p solved by the mechanism satisfies the envy-free property if, for the given price vector \(p\), each person achieves their highest payoff by choosing the allocated room. Mathematically, these conditions can written be written as a set of inequalities.

\[V_{i A(i)} - r_A(i) \geq V_{ij} - p_j,\quad \forall i,j\]

As it turns out, these inequalities admit multiple solutions. So, to narrow down the search further, we impose another criteria on our mechanism, which is, out of all feasible solutions find the one that maximizes the worst payoff.

\[\max_{A,p} \min_i V_{i A(i)} - p_{A(i)}\]

This is known as maxmin solution. Selecting maxmin as the second criteria for fairness is grounded in philosophical principles and aligns with the standard notion of 'equitability' which focuses on reducing social disparities.

To sum things up, we have formulated our fair mechanism as an optimization problem to addresses the room allocation and rent division problem. The solution of this optmization problem guarantees two properties: envy-freeness and equitability.

Algorithm for solving the optimization problem

While the formulation as an optimization problem may have seemed straightforward, it is not yet clear how easy or difficult it is to solve this optimization problem. To address this, the paper also provides an efficient algorithm to compute a solution in polynomial time.

To understand the algorithm design process, I would encourage you to go through the details in the paper.

Python code

Here's a python code for the proposed mechanism.


import numpy as np
from scipy.optimize import linear_sum_assignment
import pulp

def room_allocation_rent_division(data):
    """
    Solve the maximin envy-free rent division problem.

    Params:
        values: n x n matrix (2D numpy array) of player values for rooms
                each row sums to 1 (or can be normalized)
    Returns:
        assignment: list of room index for each player
        prices: list of computed prices (sum to 1)
        utilities: utility of each player
    """
    values = np.array(data["values"])
    n = values.shape[0]

    # === Step 1: Find a welfare-maximizing assignment
    # We maximize sum of values. Hungarian (linear_sum_assignment) is for minimization,
    # so we transform values -> -values to maximize.
    cost = -values.copy()  # negative to convert to minimization
    row_ind, col_ind = linear_sum_assignment(cost)

    # assignment: row_ind[i] player matched to room col_ind[i]
    # we want sigma[i] = the assigned room for player i
    sigma = [-1]*n
    for i, j in zip(row_ind, col_ind):
        sigma[i] = j

    # === Step 2: Solve an LP for envy-free prices maximizing min utility
    problem = pulp.LpProblem("MaximinRentDivision", pulp.LpMaximize)

    # Variables
    # p[j] = price of room j
    p = [pulp.LpVariable(f"p_{j}", lowBound=None) for j in range(n)]
    # R = minimum utility
    R = pulp.LpVariable("R")

    # Objective: maximize the minimum utility over all players
    problem += R, "Maximize_minimum_utility"

    # Prices must sum to 1 (total rent normalized to 1)
    problem += pulp.lpSum(p[j] for j in range(n)) == 1

    # Envy-freeness + min utility constraints
    for i in range(n):
        room_i = sigma[i]
        # utility for player i is v_{i,room_i} - p[room_i] >= R
        problem += values[i, room_i] - p[room_i] >= R

        # Envy-freeness: v_iσ(i) - p_σ(i) >= v_{ij} - p_j for all j
        for j in range(n):
            problem += values[i, room_i] - p[room_i] >= values[i, j] - p[j]

    # Solve LP
    problem.solve(pulp.PULP_CBC_CMD(msg=False))

    # Extract prices
    prices = [p[j].value() for j in range(n)]
    # Compute utilities
    utilities = [values[i, sigma[i]] - prices[sigma[i]] for i in range(n)]

    return(({"allocation": [int(x) for x in sigma], "prices": prices, "utilities": [float(x) for x in utilities]}))

# Example usage
V = [
    [0.6, 0.4, 0.0],
    [0.2, 0.5, 0.3],
    [0.3, 0.3, 0.4]
]
output = room_allocation_rent_division({"values": V})
print("Assignment:", output["allocation"])
print("Prices:", output["prices"])
print("Utilities:", output["utilities"])

Resources

If you don't care about the theory but are interested to see how the algorithm works in practice, you can visit Spliddit and try their Share Rent app. The app offers a black-box implementation of the discussed fair mechanism, wrapped in a clean user interface. So, all you need to do is feed it with valuations and the app will do all the calculations for you.

Author

Anurag Gupta is an M.S. graduate in Electrical and Computer Engineering from Cornell University. He also holds an M.Tech degree in Systems and Control Engineering and a B.Tech degree in Electrical Engineering from the Indian Institute of Technology, Bombay.

Comment

Past Comments

No comments yet. Be the first!