000269073 001__ 269073
000269073 005__ 20190814170608.0
000269073 037__ $$aCONF
000269073 245__ $$aStable Fractional Matchings
000269073 260__ $$c2019
000269073 269__ $$a2019
000269073 336__ $$aConference Papers
000269073 520__ $$aWe study a generalization of the classical stable matching problem that allows for cardinal preferences (as opposed to ordinal) and fractional matchings (as opposed to integral). After observing that, in this cardinal setting, stable fractional matchings can have much higher social welfare than stable integral ones, our goal is to understand the computational complexity of finding an optimal (i.e., welfare-maximizing) or nearly-optimal stable fractional matching. We present simple approximation algorithms for this problem with weak welfare guarantees and, rather unexpectedly, we furthermore show that achieving better approximations is hard. This computational hardness persists even for approximate stability. To the best of our knowledge, these are the first computational complexity results for stable fractional matchings. En route to these results, we provide a number of structural observations.
000269073 700__ $$aCaragiannis, Ioannis
000269073 700__ $$aFilos-Ratsikas, Aris
000269073 700__ $$aKanellopoulos, Panagiotis
000269073 700__ $$aVaish, Rohit
000269073 773__ $$tThe 20th ACM conference on Economics and Computation (ACM EC '19)
000269073 85641 $$uhttps://arxiv.org/pdf/1902.06698.pdf
000269073 909C0 $$xU10406$$0252184$$pLIA
000269073 909CO $$ooai:infoscience.epfl.ch:269073$$pIC$$pconf
000269073 91899 $$9LIA2019
000269073 973__ $$aEPFL
000269073 980__ $$aCONF