A note on solving the envy-free perfect matching problem with qualities of items
share
In the envy-free perfect matching problem, n items with unit supply are available to be sold to n buyers with unit demand. The objective is to find allocation and prices such that both seller's revenue and buyers' surpluses are maximized – given the buyers' valuations for the items – and all items must be sold. A previous work has shown that this problem can be solved in cubic time, using maximum weight perfect matchings to find optimal envy-free allocations and shortest paths to find optimal envy-free prices. In this work, I consider that buyers have fixed budgets, the items have quality measures and so the valuations are defined by multiplying these two quantities. Under this approach, I prove that the valuation matrix have the inverse Monge property, thus simplifying the search for optimal envy-free allocations and, consequently, for optimal envy-free prices through a strategy based on dynamic programming. As result, I propose an algorithm that finds optimal solutions in quadratic time.
READ FULL TEXT