Random Almost-Popular Matchings

Suthee Ruangwises, Osamu Watanabe

For a set $A$ of $n$ people and a set $B$ of $m$ items, with each person having a preference list that ranks all items from most wanted to least wanted, we consider the problem of…