Ohio State nav bar

Combinatorics Seminar- Boris Pittel

Combinatorics Seminar
January 23, 2020
10:20AM - 11:15AM
Math Tower 154

Date Range
Add to Calendar 2020-01-23 10:20:00 2020-01-23 11:15:00 Combinatorics Seminar- Boris Pittel Title: On random stable matchings: cyclic ones with strict preferences and two-sided ones with partially ordered preferences Speaker: Boris Pittel - The Ohio State University Abstract: Consider a cyclically ordered collection of r equi-numerous “agent” sets with strict preferences of every agent over the agents from the next set. A weakly stable cyclic matching is a partition of the set of agents into disjoint union of r-long cycles, one agent from each set per cycle, such that there are no destabilizing r-long cycles, i.e. cycles in which every agent strictly prefers its successor to its successor in the matching. Assuming that the preferences are uniformly random and independent, we show that the expected number of stable matchings grows with n (cardinality of each agent set) as (n\log n)^{r-1}. Next we consider a bipartite stable matching problem where preference list of each agent forms a partially ordered set. Each partial order is an intersection of several, k_i for side i, independent, uniformly random, strict orders. For k_1+k_2>2, the expected number of stable matchings is analyzed for three, progressively stronger, notions of stability. The expected number of weakly stable matchings is shown to grow super-exponentially fast. In contrast, for \min(k_1,k_2)>1, the fraction of instances with at least one strongly stable (super-stable) matching is super-exponentially small. Some open problems are discussed. Math Tower 154 Department of Mathematics math@osu.edu America/New_York public

Title: On random stable matchings: cyclic ones with strict preferences and two-sided ones with partially ordered preferences

Speaker: Boris Pittel - The Ohio State University

Abstract: Consider a cyclically ordered collection of r equi-numerous “agent” sets with strict preferences of every agent over the agents from the next set. A weakly stable cyclic matching is a partition of the set of agents into disjoint union of r-long cycles, one agent from each set per cycle, such that there are no destabilizing r-long cycles, i.e. cycles in which every agent strictly prefers its successor to its successor in the matching. Assuming that the preferences are uniformly random and independent, we show that the expected number of stable matchings grows with n (cardinality of each agent set) as (n\log n)^{r-1}. Next we consider a bipartite stable matching problem where preference list of each agent forms a partially ordered set. Each partial order is an intersection of several, k_i for side i, independent, uniformly random, strict orders. For k_1+k_2>2, the expected number of stable matchings is analyzed for three, progressively stronger, notions of stability. The expected number of weakly stable matchings is shown to grow super-exponentially fast. In contrast, for \min(k_1,k_2)>1, the fraction of instances with at least one strongly stable (super-stable) matching is super-exponentially small. Some open problems are discussed.

Events Filters: