On envy-free perfect matching

Consider a situation in which individuals – the buyers – have different valuations for the products of a given set. An envy-free assignment of product items to buyers requires that the items obtained by every buyer be purchased at a price not larger than his/her valuation, and each buyer’s welfare (difference between product value and price) be the largest possible. Under this condition, the problem of finding prices maximizing the seller’s revenue is known to be APX-hard even for unit-demand bidders (with several other inapproximability results for different variants), that is, when each buyer wishes to buy at most one item. Here, we focus on Envy-free Complete Allocation, the special case where a fixed number of copies of each product is available, each of the n buyers must get exactly one product item, and all the products must be sold. This case is known to be solvable in O(n^4) time. We revisit a series of results on this problem and, answering a question found in Leonard (1983), show how to solve it in O(n^3) time by connections to perfect matchings and shortest paths.