GT
Seminars are given every Friday from 2:00 to 3:00 (usually in room 178, but not for the time being). You are welcome 10 minutes earlier for tea, coffee and cake.
In order to receive the announcements, just send an email to sympa@diff.u-bordeaux.fr with subject "subscribe labri.go-gt Cookie Monster", where Cookie is your first name and Monster your last name.
See the agenda of the seminars: webmel.u-bordeaux.fr/service/user/bf-labri.go@u-bordeaux.fr/gt.html https://webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.go.html; to add it to yours webmel.u-bordeaux.fr/service/user/bf-labri.go@u-bordeaux.fr/gt.ics https://webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.go.ics , or flash the following QRCode:
Next talks:
The online talks are available here : https://webconf.u-bordeaux.fr/b/mar-ef4-zed.
Vendredi 23 Janvier à 14h - Agnes Totschnig
The Popular Dimension of Matchings
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.

