Matching problems lie at the heart of discrete mathematics. Their rich history reaches back
over 100 years (Konig, 1916), including some milestones of complexity and algorithms, such …

Two fundamental axioms in social choice theory are consistency with respect to a variable
electorate and consistency with respect to components of similar alternatives. In the context …

We consider popular matching problems in both bipartite and non-bipartite graphs with strict
preference lists. It is known that every stable matching is a min-size popular matching. A …

An input to the Popular Matching problem, in the roommates setting (as opposed to the
marriage setting), consists of a graph G (not necessarily bipartite) where each vertex ranks …

We are given a bipartite graph G=(A∪B,E) where each vertex has a preference list ranking
its neighbors: In particular, every a∈A ranks its neighbors in a strict order of preference …

Our input is a directed, rooted graph G=(V∪{r}, E) where each vertex in V has a partial order
preference over its incoming edges. The preferences of a vertex extend naturally to …

An important aspect of multi-agent systems concerns the formation of coalitions that are
stable or optimal in some well-defined way. The notion of popularity has recently received a …

Computational social choice is a research area at the intersection of computer science,
mathematics, and economics that is concerned with aggregation of preferences of multiple …

Matching theory studies how agents and/or objects from different sets can be matched with
each other while taking agents' preferences into account. The theory originated in 1962 with …

In an instance G=(A union B, E) of the stable marriage problem with strict and possibly
incomplete preference lists, a matching M is popular if there is no matching M0 where the …