BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260920T111349Z
UID:Seminar-dept-443@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20170613T130000
DTEND:20170613T140000
SUMMARY:School Seminar Series
DESCRIPTION:Dr Chien-Chung Huang: Popularity, Mixed Matchings, and Self-duality\n\nWe consider the problem of matching applicants to jobs under two-sided preferences in a popular and utility-optimal manner. Our\n\ninput instance is a bipartite graph G = (A \cup B,E) with a utility function w: E \rightarrow Q where each vertex u \in A \cup B has a preference list ranking its neighbors in a strict order of preference. For any two matchings M and T in G, let \phi(M,T) be the the number of vertices that prefer M to T. A matching M is popular if \phi(M,T) \geg \phi(T,M) for all matchings T in G. A mixed matching is defined as \Pi = \{(M_0,p_0),\ldots,(M_k,p_k)\} for some matchings M_0,\ldots,M_k and \sum_{i=0}^kp_i = 1, p_i \geq 0 for all i.\n\nThe function \phi(\cdot,\cdot$ easily extends to mixed\n\nmatchings; a mixed matching \Pi is popular if \phi(\Pi,\Lambda) \geq \phi(\Lambda,\Pi) for all mixed matchings \Lambda in G.\n\n\n\nMotivated by the fact that a popular mixed matching could have a much higher utility than all popular matchings, we study the popular fractional matching polytope {\cal P}_G.\n\nOur main result is that this polytope is half-integral (and in the special case where a stable matching is a perfect matching, this polytope is integral), implying that there is always a max-utility popular mixed matching \Pi such that \Pi = {(M_0,\frac{1}{2}),(M_1,\frac{1}{2})} and \Pi can be computed in polynomial time. An immediate consequence is that in order to implement a max-utility popular mixed matching in $G$, we need just one single random bit.\n\n\n\nWe analyze {\cal P}_G whose description may have exponentially many constraints via an extended formulation in m+n dimensions with O(m+n) constraints. The linear program that gives rise to this formulation has an unusual property: self-duality. In other words, this linear program is exactly identical to its dual program. This is a rare case where an LP of a natural problem has such a property. The self-duality of the LP plays a crucial role in our proof of the half-integrality of {\cal P}_G.\n\n\n\nWe also show that our result carries over to the roommates problem, where the given graph G may not be bipartite. The polytope of popular fractional matchings is still half-integral here and thus we can compute a max-utility popular half-integral matching in G in polynomial time. To complement this result, we also show that the problem of computing a max-utility popular (integral) matching in a roommates instance G is NP-hard.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=443
LOCATION:George Holt seminar room H223
END:VEVENT
END:VCALENDAR