Scholarlink

<p>We study almost envy-freeness in house allocation, where <i>m</i> houses are to be allocated among <i>n</i> 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 <i>a</i> w.r.t. an allocation to be the number of agents that agent <i>a</i> envies under that allocation. We <i>quantify</i> 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

The Cost and Complexity of Minimizing Envy in House Allocation

  • 期刊论文

  • 发表日期：

    2025年6月11日

查看全文
  • Jayakrishnan Madathil,
  • Neeldhara Misra,
  • Aditi Sethia

摘要

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.