econ.THFeb 16, 2026

Majoritarian Assignment Rules

Authors: Felix Brandt, Haoyuan Chen, Chris Dong, Patrick Lederer, Alexander Schlenga

Organizations: Technical University of Munich, Munich, Germany · HPI, University of Potsdam, Potsdam, Germany · ILLC, University of Amsterdam, Amsterdam, The Netherlands

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

A central problem in multiagent systems is the fair assignment of objects to agents. In this paper, we initiate the analysis of classic majoritarian social choice functions in assignment. Exploiting the special structure of the assignment domain, we show a number of surprising results with no counterparts in general social choice. In particular, we establish a near one-to-one correspondence between preference profiles and majority graphs. This correspondence implies that key properties of assignments -- such as Pareto-optimality, least unpopularity, and mixed popularity -- can be determined solely by the associated majority graph. We further show that all Pareto-optimal assignments are semi-popular and belong to the top cycle. Elements of the top cycle can thus easily be found via serial dictatorships. Our main result is a complete characterization of the top cycle, which implies the top cycle can only consist of one, two, all but two, all but one, or all assignments. By contrast, we find that the uncovered set contains only very few assignments.

Figures & tables

Figure 1. Size distributions of UCs for n=5n=5 . The high peak is at size 22 for all of them. In total, there are 9,078,6309,078,630 profiles (up to symmetries) and there are 5!=1205!=120 different assignments. A plot showing data for the four assignment rules McKelvey uncovered set, Bordes uncovered set, Gillies uncovered set, and the Pareto rule. It depicts the frequency with which each cardinality occurs across all profiles for five agents and houses. It can be seen that a size of two occurs way more often for the uncovered set than for the Pareto rule. In general, the uncovered sets often return fewer outcomes than the Pareto rule. This is particularly true for the Gillies uncovered set.
Figure 2. Size distributions of UCs for n=7n=7 in 1,0001,000 profiles sampled via the impartial culture model. The high peak is at size 22 for McKelvey and Bordes. Gillies- UC\mathit{UC} has an even higher peak at size 44 . A plot showing data for the four assignment rules McKelvey uncovered set, Bordes uncovered set, Gillies uncovered set, and the Pareto rule. It depicts the frequency with which each cardinality occurs across one thousand profiles sampled uniformly at random for seven agents and houses. It can be seen that a size of two (and small sizes in general) occurs way more often for the uncovered set than for the Pareto rule. In general, the uncovered sets often return fewer outcomes than the Pareto rule. This is particularly true for the Gillies uncovered set. The Gillies uncovered set has size four even more often than size two.
Figure 3. Cumulative distributions of the ratio of UC and PO sizes for n=5n=5 . The plot shows the relative difference, i.e., the ratio. In total, there are 9,078,6309,078,630 profiles up to symmetry. We note that the plots for McKelvey and Bordes almost perfectly align. A plot showing data for the three assignment rules McKelvey uncovered set, Bordes uncovered set, Gillies uncovered set, comparing their sizes with the Pareto rule. It depicts the frequency with which each relative cardinality with respect to the Pareto rule occurs across all profiles for five agents and houses. It can be seen that often the uncovered sets have between ten and fifty percent of the size of the set of all Pareto-optimal assignments. In general, the uncovered sets often return fewer outcomes than the Pareto rule. This is particularly true for the Gillies uncovered set. Between ten and one hundred percent, many different ratios occur regularly.
More in this topic

Fair Resource Allocation

Fair resource allocation studies how to distribute scarce goods, services, and computing capacity equitably while accounting for efficiency and constraints.

See all 56 papers

Explore similar work

CardsList

  1. The Measurable Majority

    Jun 22, 2026Lawrence S. Moss, Arthur Paul PedersenSocial Choice TheoryMajority Voting

    (†) Dept. of Mathematics, Indiana University, Bloomington. · (‡) Dept. of Computer Science & the Intel Investigations Lab, the City College of New York · the Graduate Center & Remote Sensing Earth Systems Institute, the City University of New York.

  2. Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO

    Jul 25, 2026Nicholas TehSocial Choice TheoryFair Resource Allocation

    University of Oxford, UK

  3. What Makes Majority Illusion Easy to Detect?

    Jun 2, 2026Šimon Schierreich, Ildikó SchlotterSocial Network Analysis

    Czech Technical University in Prague · ELTE Centre for Economic and Regional Studies · Budapest University of Technology and Economics