A Nash-Bargaining-Based Mechanism for One-Sided Matching Markets and Dichotomous Utilities

Mechanisms based on maximizing Nash Social Welfare (NSW) have proven to be fair and efficient for a wide variety of fair division problems. We study the fractional allocations maximizing NSW, i.e., a Nash-bargaining-based mechanism, for one-sided matching markets with endowments, under dichotomous utilities, and show that they are the solutions of a rational convex program (RCP). Moreover, we provide a simple combinatorial polynomial time algorithm to maximize NSW by identifying the Nash bargaining points with the equilibrium of a novel type of market, the variable-budget market model. Lastly, we show that maximizing NSW is strategyproof under the assumption that the agents' disagreement utilities are public knowledge.