Use of Linear Programming to Find an Envy-Free Solution Closest to the Brams–Kilgour Gap Solution for the Housemates Problem |
| |
Authors: | Richard F Potthoff |
| |
Institution: | (1) Department of Political Science, Duke University, Durham, North Carolina 27708-0204, USA |
| |
Abstract: | Although the Gap Procedure that Brams and Kilgour (2001) proposed for determining the price of each room in the housemates problem has many favorable properties, it also has one drawback: Its solution is not always envy-free. Described herein is an approach that uses linear programming to find an envy-free solution closest (in a certain sense) to the Gap solution when the latter is not envy-free. If negative prices are allowed, such a solution always exists. If not, it sometimes exists, in which case linear programming can find it by disallowing negative prices. Several examples are presented. |
| |
Keywords: | bidding envy-freeness fair division housemates problem linear programming |
本文献已被 SpringerLink 等数据库收录! |
|