Text

Fully Polynomial-Time Approximation Schemes for Fair Rent Division

We study the problem of fair rent division that entails splitting the rent and allocating the rooms of an apartment among agents in a fair manner (i.e., under the imposed rents, no agent has a strictly stronger preference for any other agent’s room). The utility functions specify the cardinal preferences of the agents for the rooms for every possible room rent. Although envy-free solutions are guaranteed to exist under reasonably general utility functions, efficient algorithms for finding them were known only for quasilinear utilities. This work addresses this notable gap and develops a fully polynomial-time approximation scheme for fair rent division with minimal assumptions on the utility functions. Envy-free solutions correspond to equilibria of a two-sided matching market with monetary transfers; hence, this work also provides efficient algorithms for finding approximate equilibria in such markets. We complement the algorithmic results by proving that the fair rent division problem lies in the intersection of the complexity classes polynomial parity arguments on directed graphs and polynomial local search.

Ketersediaan

Informasi Detail

Judul Seri

MATHEMATICS OF OPERATIONS RESEARCH; Vol.47 No.3 August 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 1970-1998

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

RESOURCE ALLOCATION
FIXED POINTS
FPTAS
EQUILIBRIUM COMPUTATION
ENVY-FREENESS
FAIR RENT DIVISION

Info Detail Spesifik

https://doi.org/10.1287/moor.2021.1196

Pernyataan Tanggungjawab

Eshwar Ram Arunachaleswaran, Siddharth Barman, Nidhi Rathi

Versi lain/terkait

Lampiran Berkas

Komentar