(New) 1 May 2026, Computational Social Choice Seminar, Jannik Matuschke

Abstract

We study matching problems in which agents form one side of a bipartite graph and have preferences over objects on the other side. A prominent solution concept in this context is that of a (weak) Condorcet winner, i.e., a matching that is preferred over any other matching by a (weak) majority of the agents. It is well known, however, that such Condorcet winners need not exist. We therefore turn to a natural and prominent relaxation: a set of matchings is a Condorcet-winning set if, for every competing matching, a majority of agents prefers their favorite matching in the set over the competitor. The Condorcet dimension is the smallest cardinality of a Condorcet-winning set.
Our main results reveal a connection between Condorcet-winning sets and Pareto optimality: Any Pareto-optimal set of two matchings is a Condorcet-winning set. This implication continues to hold even when we impose additional matroid constraints on the set of matched objects, and even when agents' valuations are given as partial orders. When preferences are strict, Pareto-optimal pairs of matchings exist and can be easily computed, implying an upper bound of 2 on the Condorcet dimension. However, surprisingly, under general partial order preferences, Pareto-optimal solutions may not exist and the Condorcet dimension may depend on the number of agents. We provide tight bounds on the Condorcet dimension also for this case, as well as hardness results for computing small Condorcet winning sets and Pareto-optimal matchings.
This is joint work with Telikepalli Kavitha and Ulrike Schmidt-Kraepelin.

For more information on the Computational Social Choice Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/.