5 papers
An Algorithm for the Assignment Game Beyond Additive Valuations
Eric Balkanski, Christopher En, Yuri Faenza
The assignment game, introduced by Shapley and Shubik (1971), is a classic model for two-sided matching markets between buyers and sellers. In the original assignment game, it is a…
All finite lattices are stable matching lattices
Christopher En, Yuri Faenza
We show that all finite lattices, including non-distributive lattices, arise as stable matching lattices when all agents have path-independent choice functions. This result answers…
Longer Lists Yield Better Matchings
Yuri Faenza, Aapeli Vuorinen
Many centralized mechanisms for two-sided matching markets that enjoy strong theoretical properties assume that the planner solicits full information on the preferences of each par…
Minimum Cut Representability of Stable Matching Problems
Yuri Faenza, Ayoub Foussoul, Chengyue He
We introduce and study Minimum Cut Representability, a framework to solve optimization and feasibility problems over stable matchings by representing them as minimum s-t cut proble…
Scarf's Algorithm on Arborescence Hypergraphs
Karthekeyan Chandrasekaran, Yuri Faenza, Chengyue He +1
Scarf's algorithm--a pivoting procedure that finds a dominating extreme point in a down-monotone polytope--can be used to show the existence of a fractional stable matching in hype…