COMSOC Video Seminar tomorrow: Suzuki and Tomlinson

[Dominik Peters]

Dear all,

The next COMSOC Video Seminar is happening tomorrow Monday, 2026-02-02, at 06:00 Redmond, 09:00 New York, 15:00 Paris, 01:00 Sydney (+1), to hear from Mashbat Suzuki (UNSW) on the "Compatibility of Fairness and Nash Welfare under Subadditive Valuations" and from Kiran Tomlinson (Microsoft Research) about "Exclusion Zones of Instant Runoff Voting". Abstracts below. You can join the meeting via https://meeting.comsocseminar.org as usual. Hope to see many of you there!

Best

Dominik

on behalf of the organizing committee

Mashbat Suzuki (UNSW) 

Compatibility of Fairness and Nash Welfare under Subadditive Valuations

We establish a compatibility between fairness and efficiency, captured via Nash Social Welfare (NSW), under the broad class of subadditive valuations. We prove that, for subadditive valuations, there always exists a partial allocation that is envy-free up to the removal of any good EFX and has NSW at least half of the optimal; here, optimality is considered across all allocations, fair or otherwise. We also prove, for subadditive valuations, the universal existence of complete allocations that are envy-free up to one good EF1 and also achieve a factor 1/2 approximation to the optimal NSW. Our EF1 result resolves an open question posed by Garg, Husic, Li, Végh, and Vondrák (STOC 2023). 

In addition, we develop a polynomial-time algorithm which, given an arbitrary allocation à as input, returns an EF1 allocation with NSW at least $\frac{1}{e^{2/e}}\approx \frac{1}{2.08}$ times that of Ã. Therefore, our results imply that the EF1 criterion can be attained simultaneously with a constant-factor approximation to optimal NSW in polynomial time (with demand queries), for subadditive valuations. The previously best-known approximation factor for optimal NSW, under EF1 and among $n$ agents, was $O(n)$ -- we improve this bound to $O(1)$. 

It is known that EF1 and exact Pareto efficiency (PO) are incompatible with subadditive valuations. Complementary to this negative result, the current work shows that we regain compatibility by just considering a factor $1/2$ approximation: EF1 can be achieved in conjunction with $\frac{1}{2}$-PO under subadditive valuations. As such, our results serve as a general tool that can be used as a black box to convert any efficient outcome into a fair one, with only a marginal decrease in efficiency. 

Joint work with Siddharth Barman

--

Kiran Tomlinson (Microsoft Research)

Exclusion Zones of Instant Runoff Voting

Recent research on instant runoff voting (IRV) shows that it exhibits a striking combinatorial property in one-dimensional preference spaces: there is an "exclusion zone" around the median voter such that if a candidate from the exclusion zone is on the ballot, then the winner must come from the exclusion zone. Thus, in one dimension, IRV cannot elect an extreme candidate as long as a sufficiently moderate candidate is running. In this work, we examine the mathematical structure of exclusion zones as a broad phenomenon in more general preference spaces. We prove that with voters uniformly distributed over any d-dimensional hyperrectangle (for d>1), IRV has no nontrivial exclusion zone. However, we also show that IRV exclusion zones are not solely a one-dimensional phenomenon. For irregular higher-dimensional preference spaces with fewer symmetries than hyperrectangles, IRV can exhibit nontrivial exclusion zones. As a further exploration, we study IRV exclusion zones in graph voting, where nodes represent voters who prefer candidates closer to them in the graph. Here, we show that IRV exclusion zones present a surprising computational challenge: even checking whether a given set of positions is an IRV exclusion zone is NP-hard. We develop an efficient randomized approximation algorithm for checking and finding exclusion zones. We also report on computational experiments with exclusion zones in two directions: (i) applying our approximation algorithm to a collection of real-world school friendship networks, we find that about 60% of these networks have probable nontrivial IRV exclusion zones; and (ii) performing an exhaustive computer search of small graphs and trees, we also find nontrivial IRV exclusion zones in most graphs. While our focus is on IRV, the properties of exclusion zones we establish provide a novel method for analyzing voting systems in metric spaces more generally.

Joint work with Johan Ugander and Jon Kleinberg