House allocations concern with matchings involving one-sided preferences, where houses serve as a proxy encoding valuable indivisible resources (e.g. organs, course seats, subsidized public housing units) to be allocated among the agents. Every agent must receive exactly one resource. We study algorithmic approaches towards ensuring fairness in such settings. Minimizing the number of envious agents is known to be computationally hard. We present two tractable approaches to deal with the hardness. When the agents are presented with an initial allocation of houses, we aim to refine this allocation by reallocating a bounded number of houses to reduce the number of envious agents. We show an efficient algorithm when the agents express preference for a bounded number of houses and houses are accepted by a bounded number of agents. Next, we consider single peaked preference domain and present a polynomial time algorithm for finding an allocation that minimize the number of envious agents. We further extend it to satisfy Pareto efficiency. Our former algorithm works for other measures of envy such as total envy, or maximum envy, with suitable modifications. Finally, we present an empirical analysis recording the fairness-welfare trade-off of our algorithms.

We study almost envy-freeness in house allocation, where m houses are to be allocated among n agents so that every agent receives exactly one house. An envy-free allocation need not exist, and therefore we may have to settle for relaxations. We study different aggregate measures of envy as markers of fairness. In particular, we define the amount of envy experienced by an agent a w.r.t. an allocation to be the number of agents that agent a envies under that allocation. We quantify the envy generated by an allocation using three different metrics: 1) the number of agents who are envious; 2) the maximum amount of envy experienced by any agent; and 3) the total amount of envy experienced by all agents, and look for allocations that minimize one of the three metrics. We prove a host of algorithmic and hardness results. We also suggest practical approaches for these problems via integer linear program (ILP) formulations and report the findings of our experimental evaluation of ILPs. Finally, we study the price of fairness, which quantifies the loss of welfare we must suffer due to the fairness requirements, and present tight bounds as well as algorithms that simultaneously optimize both welfare and fairness.

We study almost envy-freeness in house allocation, where m houses are to be allocated among n agents so that every agent receives exactly one house. An envy-free allocation need not exist, and therefore we may have to settle for relaxations. We study different aggregate measures of envy as markers of fairness. In particular, we define the amount of envy experienced by an agent a w.r.t. an allocation to be the number of agents that agent a envies under that allocation. We quantify the envy generated by an allocation using three different metrics: 1) the number of agents who are envious; 2) the maximum amount of envy experienced by any agent; and 3) the total amount of envy experienced by all agents, and look for allocations that minimize one of the three metrics. We prove a host of algorithmic and hardness results. We also suggest practical approaches for these problems via integer linear program (ILP) formulations and report the findings of our experimental evaluation of ILPs. Finally, we study the price of fairness, which quantifies the loss of welfare we must suffer due to the fairness requirements, and present tight bounds as well as algorithms that simultaneously optimize both welfare and fairness.