New Insights on Classic Questions in Matching Theory
Sunday, Jan. 7, 2018 10:15 AM - 12:15 PM
- Chair: Alvin E. Roth, Stanford University
Deferred Acceptance with Compensation Chains
AbstractI introduce a class of algorithms called Deferred Acceptance with Compensation Chains (DACC). DACC algorithms generalize the DA algorithms by Gale and Shapley (1962) by allowing both sides of the market to make offers. The main result is a characterization of the set of stable matchings: a matching is stable if and only if it is the outcome of a DACC algorithm.
Virtual Demand and Stable Mechanisms
AbstractWe study conditions for the existence of stable, strategy-proof mechanisms in a many-to-one matching model with salaries. Workers and ﬁrms want to match and agree on the terms of their match. Firms demand diﬀerent sets of workers at diﬀerent salaries. Workers have preferences over diﬀerent ﬁrm-salary combinations. Workers’ preferences are monotone in salaries. We show that for this model, a descending auction mechanism is the only candidate for a stable mechanism that is strategy-proof for workers. Moreover, we identify a maximal domain of demand functions for ﬁrms, such that the mechanism is stable and strategy-proof.
In the special case, where demand functions are generated by quasi-linear proﬁt functions, our domain reduces to the domain of demand functions under which workers are gross substitutes for ﬁrms. We provide two versions of the results for the quasi-linear case. One for a discrete model, where salaries are restricted to discrete units and one for a continuous model, where salaries can take on arbitrary positive numbers. More generally, we show that several celebrated results (the existence of a worker-optimal stable allocation, the rural hospitals theorem, the strategy-proofness of the worker-optimal stable mechanism) generalize from the discrete to the continuous model.
Lone Wolves in Competitive Equilibria
AbstractThis paper develops a class of equilibrium-independent predictions of competitive equilibrium with indivisibilities. Specifically, we prove an analogue of the "Lone Wolf Theorem" of classical matching theory, showing that when utility is perfectly transferable, any agent who does not participate in trade in one competitive equilibrium must receive his autarky payoff in every competitive equilibrium. Our results extend to approximate equilibria and to settings in which utility is only approximately transferable.
- D4 - Market Structure, Pricing, and Design
- C7 - Game Theory and Bargaining Theory