A central concept in social choice theory is that of a Condorcet winner: an outcome that defeats every alternative in a pairwise majority vote. While compelling, this notion is famously fragile, as Condorcet’s paradox shows that such a winner need not exist at all. This tension between desirability and nonexistence motivates much of modern voting theory.
In this talk, we explore how these ideas arise in matching problems, where voters’ preferences over potential matches induce an election over all possible matchings. The appropriate analogue of a Condorcet winner in this setting is a popular matching, defined via pairwise elections between matchings that account carefully for ties in preferences. As in classical social choice, popular matchings are highly appealing when they exist, but unfortunately, they often do not.
To address this, we study a natural relaxation: instead of a single winning matching, we allow a set of matchings that collectively defeats any alternative matching. This leads to the notion of the popular dimension, defined as the minimum size of such a winning set, in the worst case, for a given class of matching problems. We will present algorithmic results and open questions on the popular dimension for three classical settings: the house allocation problem, the marriage problem, and the roommates problem.
Joint work with Frank Connor, Louis-Roy Langevin, Ndiamé Ndiaye, Rohit Vasishta and Adrian Vetta.
(Agnes Totschnig) [MIT]
Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .
Import automatique depuis https://webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.go.ics par sync_icals_to_drupal.py pour GT-GO