2025/04/23 by Elmalem, Noga Klein, Gonen, Rica, Segal-Halevi, Erel
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2504.16852
Rebuild and Divide is an urban renewal process that involves the demolition of old buildings and the construction of new ones. Original homeowners are compensated with upgraded apartments, while surplus units are sold for profit, so theoretically it is a win-win project for all parties involved. However, many rebuild-and-divide projects withheld or delayed due to disagreements over the assignment of new units, claiming they are not "fair". The goal of this research is to develop algorithms for envy-free allocation of the new units. The main challenge is that, in contrast to previous work on envy-free allocation, the envy depends also on the value of the old units, as people with more valuable old units are entitled to more valuable new units. We introduce three models that capture different notions of fairness: (1) the Difference Model, where agents evaluate their gains relative to others; (2) the Envy Sum Model, which permits some envy as long as the total envy does not exceed that of the original allocation; and (3) the Ratio Model, where fairness is assessed based on the proportional value of old apartments. For each model, we establish an envy criterion and seek a payment vector and allocation that ensure envy-freeness. These models present both theoretical challenges and intriguing insights. Additionally, within the Envy Sum Model, we present a mechanism that computes an allocation and payment scheme that minimizes total envy. We also analyze the mechanism's vulnerability to manipulation and identify conditions under which it is obviously manipulable.