Abstract
We study the problem of matching markets with ties, where one side of themarket does not necessarily have strict preferences over members at its otherside. For example, workers do not always have strict preferences over jobs,students can give the same ranking for different schools and more. Inparticular, assume w.l.o.g. that workers' preferences are determined by theirutility from being matched to each job, which might admit ties. Notably, incontrast to classical two-sided markets with strict preferences, there is nolonger a single stable matching that simultaneously maximizes the utility forall workers. We aim to guarantee each worker the largest possible share from the utilityin her best possible stable matching. We call the ratio between the worker'sbest possible stable utility and its assigned utility the \emph{Optimal StableShare} (OSS)-ratio. We first prove that distributions over stable matchingscannot guarantee an OSS-ratio that is sublinear in the number of workers.Instead, randomizing over possibly non-stable matchings, we show how to achievea tight logarithmic OSS-ratio. Then, we analyze the case where the real utilityis not necessarily known and can only be approximated. In particular, weprovide an algorithm that guarantees a similar fraction of the utility comparedto the best possible utility. Finally, we move to a bandit setting, where weselect a matching at each round and only observe the utilities for matches weperform. We show how to utilize our results for approximate utilities togracefully interpolate between problems without ties and problems withstatistical ties (small suboptimality gaps).