dimacs logo color

Events

Event Calendar

« Previous Month

August 2026

Next Month »
Sun Mon Tue Wed Thu Fri Sat
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Seminar Details

Discussion of: Two-Sided Random Matching Markets: Ex-Ante Equivalence of the Deferred Acceptance Procedures

  • Start Date: October 19, 2020
  • Event Start Time: 4:00 PM
  • Event End Time: 5:00 PM
  • Seminar Series: DIMACS Matching Reading Group
  • Event Location: Online Event
  • Presentation Type: Stand Alone Presentation
  • Abstract:

    The paper to be presented is:

    Title: Two-Sided Random Matching Markets: Ex-Ante Equivalence of the Deferred Acceptance Procedures
    Author: Simon Mauras

    Paper Abstract: Stable matching in a community consisting of N men and N 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.
    When the input preference profile is generated from a distribution, we study the output distribution of two stable matching procedures: women-proposing-deferred-acceptance and men-proposing-deferred-acceptance. We show that the two procedures are ex-ante equivalent: that is, under certain conditions on the input distribution, their output distributions are identical.
    In terms of technical contributions, we generalize (to the non-uniform case) an integral formula, due to Knuth and Pittel, which gives the probability that a fixed matching is stable. Using an inclusion-exclusion principle on the set of rotations, we give a new formula which gives the probability that a fixed matching is the women/men-optimal stable matching. We show that those two probabilities are equal with an integration by substitution.

    Link to paper.

    This week's presenter is: Ariel Schvartzman, DIMACS, Rutgers University.