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
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=5 . The high peak is at size 2 for all of them. In total, there are 9,078,630 profiles (up to symmetries) and there are 5!=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=7 in 1,000 profiles sampled via the impartial culture model. The high peak is at size 2 for McKelvey and Bordes. Gillies- UC has an even higher peak at size 4 . 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=5 . The plot shows the relative difference, i.e., the ratio. In total, there are 9,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.
Fair resource allocation studies how to distribute scarce goods, services, and computing capacity equitably while accounting for efficiency and constraints.
This paper studies strict majority reasoning in finite electorates using so-called social decision frames: finite sets of voters equipped with distinguished families of coalitions interpreted as those voting blocs evaluated to form a strict majority. A coherence criterion for qualitative majority judgments is identified and shown to give an exact characterization for representability of strict majorities by finitely additive measures. In addition, a minimal natural logic for reasoning about strict majorities is shown to be sound and complete. These developments motivate examination of associated combinatorial questions concerning incoherence in finite families of sets; partial results and a conjecture are given. Finally, the results of this paper are applied to correct a classical representation theorem for weak qualitative probability structures due to Patrick Suppes and to establish a May-type characterization for ordinary strict majority rule for social decision frames.
Lawrence S. Moss, Arthur Paul Pedersen
(†) 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.
We study whether strictly positive marginal values restore the compatibility of envy-freeness up to one good (EF1) and Pareto optimality (PO) for indivisible goods. For two agents, we identify the exact threshold in the number of goods. Every instance with at most seven goods and strictly increasing valuations admits an allocation that is both EF1 and PO, without any submodularity assumption. In contrast, we construct an eight-good instance with normalized, integer-valued, strictly increasing, submodular valuations in which every EF1 allocation is strictly Pareto dominated. Thus, eight goods are necessary and sufficient for a two-agent counterexample. Finally, we strengthen the three-agent NP-hardness result of Chandramouleeswaran and Nimbhorkar (2026): deciding whether an EF1 and PO allocation exists remains NP-hard for normalized, integer-valued, monotone submodular valuations even when zero marginals are confined to eight fixed agent-good pairs, all involving a single agent.
Majority illusion is an undesirable phenomenon in social networks in which agents incorrectly perceive a minority opinion as dominant. This can severely distort collective behavior and decision-making. We study the fundamental question of detecting whether a social network allows for a majority illusion. Formally, in the q-Majority Illusion problem, we ask whether there exists a binary labeling of agents in which at least a q-fraction of agents have the majority of neighbors with the minority label. We investigate how various structural properties of the underlying social network influence the tractability of this question, and provide a detailed map of its computational complexity.
Šimon Schierreich, Ildikó Schlotter
Czech Technical University in Prague · ELTE Centre for Economic and Regional Studies · Budapest University of Technology and Economics