Algorithms for stable matching with indifferences
| dc.contributor.advisor | Plaxton, C. Greg | |
| dc.contributor.committeeMember | Gál, Anna | |
| dc.contributor.committeeMember | Ramachandran, Vijaya | |
| dc.contributor.committeeMember | Hatfield, John | |
| dc.creator | Lam, Chi Kit | |
| dc.date.accessioned | 2019-12-19T19:57:33Z | |
| dc.date.available | 2019-12-19T19:57:33Z | |
| dc.date.created | 2019-05 | |
| dc.date.issued | 2019-05-10 | |
| dc.date.submitted | May 2019 | |
| dc.date.updated | 2019-12-19T19:57:33Z | |
| dc.description.abstract | In the stable matching problem, given a two-sided matching market where each agent has ordinal preferences over the agents on the other side, we would like to find a bipartite matching such that no pair of agents prefer each other to their partners. Indifferences in preferences of the agents arise naturally in large-scale centralized matching schemes. We consider stable matching models where indifferences may occur in the preferences and address some of the related algorithmic challenges. In the first part of this dissertation, we study group strategyproofness and Pareto-stability in the stable matching market with indifferences. We present Pareto-stable mechanisms that are group strategyproof for one side of the market. Our key technique involves modeling the stable matching market as a generalized assignment game. In the second part of this dissertation, we study the problem of finding maximum stable matchings when preference lists are incomplete and contain one-sided ties. We present a polynomial algorithm that achieves an approximation ratio of 1 + (1 - [1 over L]) [superscript L], where L is the maximum tie length. Our algorithm is based on a proposal process in which numerical priorities are adjusted according to the solution of a linear program, and are used for tie-breaking purposes. Our main idea is to use an infinitesimally small step size for incrementing the priorities. Our analysis involves a charging argument and an infinite-dimensional factor-revealing linear program. We also show that the same ratio of 1 + (1 - [1 over L]) [superscript L], is an upper bound on the integrality gap, which matches the known lower bound. For the case of one-sided ties where the maximum tie length is two, our result implies an approximation ratio and integrality gap of [5 over 4], which matches the known UG-hardness result. | |
| dc.description.department | Computer Science | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | https://hdl.handle.net/2152/78801 | |
| dc.identifier.uri | http://dx.doi.org/10.26153/tsw/5856 | |
| dc.language.iso | en | |
| dc.subject | Stable matching | |
| dc.subject | Group strategyproofness | |
| dc.subject | Pareto-optimality | |
| dc.subject | Approximation algorithm | |
| dc.subject | Integrality gap | |
| dc.title | Algorithms for stable matching with indifferences | |
| dc.type | Thesis | |
| dc.type.material | text | |
| thesis.degree.department | Computer Sciences | |
| thesis.degree.discipline | Computer Science | |
| thesis.degree.grantor | The University of Texas at Austin | |
| thesis.degree.level | Doctoral | |
| thesis.degree.name | Doctor of Philosophy |