8 papers
Weakly-Popular and Super-Popular Matchings with Ties and Their Connection to Stable Matchings
Gergely Csáji, Frederik Glitzner
The efficient computation of large matchings with desirable guarantees is a crucial objective in market design. However, even in simple two-sided matching markets with weak ordinal…
Ex-post Stability under Two-Sided Matching: Complexity and Characterization
Haris Aziz, Gergely Csáji, Péter Biró
A probabilistic approach to the stable matching problem has been identified as an important research area with several important open problems. When considering random matchings, e…
The NTU Partitioned Matching Game for International Kidney Exchange Programs
Gergely Csáji, Tamás Király, Zsuzsa Mészáros-Karkus
Motivated by the real-world problem of international kidney exchange (IKEP), recent literature introduced a generalized transferable utility matching game featuring a partition of…
Computing Balanced Solutions for Large International Kidney Exchange Schemes When Cycle Length Is Unbounded
Márton Benedek, Péter Biró, Gergely Csáji +3
In kidney exchange programmes (KEP) patients may swap their incompatible donors leading to cycles of kidney transplants. Nowadays, countries try to merge their national patient-don…
Extending Stable and Popular Matching Algorithms from Bipartite to Arbitrary Instances
Gergely Csáji
We consider stable and popular matching problems in arbitrary graphs, which are referred to as stable roommates instances. We extend the 3/2-approximation algorithm for the maximum…
Popular Matchings under Preference Variation and an Algorithm for Popular Common Bases with Integral Comparison Margins
Gergely Csáji
Preference information in matching markets may be incomplete, criterion-dependent, or noisy. We study popular and dominant matchings under four forms of preference variation: indep…