Alladi Ramakrishnan Hall

Matching under preferences: stability is ubiquitous but popularity is hard to find

Sushmita Gupta

NISER Bhubaneshwar

Matching under preferences is a research topic that finds
numerous applications in practice as diverse as assigning students to
colleges, workers to firms, kidney donors to recipients, users to servers
in a distributed internet service, to just name a few. Indeed this topic
is
at the heart of the intersection between Computer Science and Economics,
and has been recognized as such by Nobel prize in Economics.

In the first part of the talk, we will discuss canonical problems in this
area, namely, stable matching and its generalization, popular matching.
In
the second part of the talk, I will present a new result published in
SODA'19 that resolved arguably the main open problem in the subarea of
popular matching: In an arbitrary graph, deciding if a popular matching
exists is NP-complete. The computational complexity of this problem had
been unknown for over a decade, during which it was repeatedly posed as a
fundamental open question.