Deterministic matching method ensures fair and efficient worker allocation
A Weakly Group Strategy-Proof and Pareto-Stable Matching Mechanism with Two-Sided Indifferences under Gross Substitutes
Computer Science and Game Theory
Summary
Matching workers to jobs can be tricky, especially when both sides have ties in preferences. The authors found a way to assign workers to firms so that no group of workers can benefit by lying, and everyone gets a fair and efficient match. Their method handles complex preferences and runs quickly, making it practical for real-world job markets. This helps improve how we pair workers and companies fairly, even when choices are not clear-cut.
What this means in practice
- •For human resources teams: Assign workers to firms fairly and efficiently, even when firms and workers have ties in preferences and complex constraints.
- •For online labor platform operators: Design matching systems that prevent groups of workers from manipulating outcomes and ensure stable job assignments.$Commercial implications: Enables platforms to offer fair and manipulation-resistant job matching services improving user trust and retention.
Authors
Yasushi Kawase, Ryosuke Sato
Abstract
We study finite many-to-one matching markets with indifferences on both sides and publicly known firm preferences over sets of workers. A standard approach breaks ties uniformly at random and runs deferred acceptance, which is strategy-proof for workers but may select a weakly stable matching that is Pareto dominated under the agents' original preferences. For the broad class of markets in which each firm's preferences admit a gross substitutes (GS) representation, we construct a deterministic generalized deferred acceptance mechanism that is weakly stable, Pareto efficient with respect to both sides, worker weakly group strategy-proof, and implementable in strongly polynomial time given value oracles for the GS representations. This domain includes nonresponsive firm preferences, such as additive scores under matroid constraints and assignment values. Our analysis bridges ordinal matching with indifferences and competitive equilibria under imperfectly transferable utility. Although the mechanism uses only ordinal comparisons, it returns a seller-optimal equilibrium matching of a tiered auxiliary market, and the equilibrium structure of this market yields the stability, efficiency, and incentive guarantees.