News & Events
Department Events & Announcements

Events

  • Nov
    29

    CS Distinguished Lecture Series - Claire Mathieu "Two-sided matching markets with correlated random preferences"

    Department of Computer Science

    12:00 PM

    EVENT DETAILS

    This will be a virtual seminar

    Abstract

    Stable matching in a community consisting of men and women is a classical combinatorial problem that has been the subject of intense theoretical and empirical study since its introduction in 1962 in a seminal paper by Gale and Shapley, who designed the celebrated ``deferred acceptance'' algorithm for the problem.
    In the input, each participant ranks participants of the opposite type, so the input consists of a collection of permutations, representing the preference lists. A bipartite matching is unstable if some man-woman pair is blocking: both strictly prefer each other to their partner in the matching. Stability is an important economics concept in matching markets from the viewpoint of manipulability. The unicity of a stable matching implies non-manipulability, and near-unicity implies limited manipulability, thus these are mathematical properties related to the quality of stable matching algorithms.
    This work is a theoretical study of the effect of correlations on approximate manipulability of stable matching algorithms. Our approach is to go beyond worst case, assuming that some of the input preference lists are drawn from a distribution. Our model encompasses a discrete probabilistic process inspired by a popularity model introduced by Immorlica and Mahdian, that provides a way to capture correlation between preference lists. Approximate manipulability is approached from several angles : when all stable partners of a person have approximately the same rank; or when most persons have a unique stable partner. Another quantity of interest is a person's number of stable partners. Our results aim to paint a picture of the manipulability of stable matchings in a ``beyond worst case'' setting.

    This is joint work with Hugo Gimbert and Simon Mauras

    Biography

    Claire Mathieu is a research director in Computer Science at CNRS (Centre National de la Recherche Scientifiqie) in France. She works on the design and analysis of algorithms. She has published over a hundred papers and is in particular author of: Mathieu C., L’Algorithmique, Paris, Fayard/Collège de France, coll. « Leçons inaugurales du Collège de France », no273, 2018 ; édition électronique : Collège de France, DOI : 10.4000/ books.cdf.5609.

    more less

    TIME Monday, November 29, 2021 at 12:00 PM - 1:00 PM

    ADD TO CALENDAR SHARE

    CONTACT Pamela Villalovoz    pmv@northwestern.edu EMAIL

    CALENDAR Department of Computer Science

  • Nov
    29

    Fall Classes resume 8 a.m.

    University Academic Calendar

    All Day

    EVENT DETAILS

    TIME Monday, November 29, 2021

    ADD TO CALENDAR SHARE

    CONTACT Office of the Registrar    nu-registrar@northwestern.edu EMAIL

    CALENDAR University Academic Calendar

  • Nov
    30

    IDEAL Seminar - Benjamin Lovitz, University of Waterloo

    Department of Computer Science

    3:00 PM

    EVENT DETAILS

    TIME Tuesday, November 30, 2021 at 3:00 PM - 4:00 PM

    ADD TO CALENDAR SHARE

    CONTACT Pam Villalovoz    pmv@northwestern.edu EMAIL

    CALENDAR Department of Computer Science

  • Dec
    4

    Fall classes end

    University Academic Calendar

    All Day

    EVENT DETAILS

    TIME Saturday, December 4, 2021

    ADD TO CALENDAR SHARE

    CONTACT Office of the Registrar    nu-registrar@northwestern.edu EMAIL

    CALENDAR University Academic Calendar

  • Dec
    11

    Northwestern Engineering PhD Hooding and Master's Recognition Ceremony

    McCormick School of Engineering and Applied Science

    4:00 PM Pick-Staiger Concert Hall

    EVENT DETAILSmore info

    TIME Saturday, December 11, 2021 at 4:00 PM - 5:30 PM

    LOCATION Pick-Staiger Concert Hall    map it

    ADD TO CALENDAR SHARE

    CONTACT Northwestern Engineering Events    northwestern-engineering-events@northwestern.edu EMAIL

    CALENDAR McCormick School of Engineering and Applied Science

  • Dec
    27

    Winter Recess - University Closed

    University Academic Calendar

    All Day

    EVENT DETAILS

    TIME Monday, December 27, 2021

    ADD TO CALENDAR SHARE

    CONTACT Office of the Registrar    nu-registrar@northwestern.edu EMAIL

    CALENDAR University Academic Calendar

  • Dec
    28

    Winter Recess - University Closed

    University Academic Calendar

    All Day

    EVENT DETAILS

    TIME Tuesday, December 28, 2021

    ADD TO CALENDAR SHARE

    CONTACT Office of the Registrar    nu-registrar@northwestern.edu EMAIL

    CALENDAR University Academic Calendar

  • Dec
    29

    Winter Recess - University Closed

    University Academic Calendar

    All Day

    EVENT DETAILS

    TIME Wednesday, December 29, 2021

    ADD TO CALENDAR SHARE

    CONTACT Office of the Registrar    nu-registrar@northwestern.edu EMAIL

    CALENDAR University Academic Calendar

  • Dec
    30

    Winter Recess - University Closed

    University Academic Calendar

    All Day

    EVENT DETAILS

    TIME Thursday, December 30, 2021

    ADD TO CALENDAR SHARE

    CONTACT Office of the Registrar    nu-registrar@northwestern.edu EMAIL

    CALENDAR University Academic Calendar

  • Jan
    3

    Winter Classes begin 8 a.m.

    University Academic Calendar

    All Day

    EVENT DETAILS

    TIME Monday, January 3, 2022

    ADD TO CALENDAR SHARE

    CONTACT Office of the Registrar    nu-registrar@northwestern.edu EMAIL

    CALENDAR University Academic Calendar