39 citations · 308 across the 129 of their papers we have counts for
23 papers · 1 filter
Fair Allocation under Conflict Constraints
Sarfaraz Equbal, Rohit Gurjar, Ayumi Igarashi +6
We study the fair allocation of indivisible items subject to conflict constraints. In this framework, the items are represented as the vertices of a graph, with edges corresponding…
Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences
Pasin Manurangsi, Krzysztof Sornat
We present a polynomial-time algorithm for computing an optimal committee of size under any given Thiele voting rule for elections on the Voter Interval domain (i.e., when vote…
Fair Allocation of Indivisible Goods with Variable Groups
Paul Gölz, Ayumi Igarashi, Pasin Manurangsi +1
We study the fair allocation of indivisible goods with variable groups. In this model, the goal is to partition the agents into groups of given sizes and allocate the goods to the…
Dividing Conflicting Items Fairly
Ayumi Igarashi, Pasin Manurangsi, Hirotaka Yoneda
We study the allocation of indivisible goods under conflicting constraints, represented by a graph. In this framework, vertices correspond to goods and edges correspond to conflict…
Asymptotic Analysis of Weighted Fair Division
Pasin Manurangsi, Warut Suksompong, Tomohiko Yokoyama
Several resource allocation settings involve agents with unequal entitlements represented by weights. We analyze weighted fair division from an asymptotic perspective: if items…
Asymptotic Fair Division: Chores Are Easier Than Goods
Pasin Manurangsi, Warut Suksompong
When dividing items among agents, two of the most widely studied fairness notions are envy-freeness and proportionality. We consider a setting where chores are allocated to …
Complexity of Round-Robin Allocation with Potentially Noisy Queries
Zihan Li, Pasin Manurangsi, Jonathan Scarlett +1
We study the complexity of a fundamental algorithm for fairly allocating indivisible items, the round-robin algorithm. For agents and items, we show that the algorithm can…
Ordinal Maximin Guarantees for Group Fair Division
Pasin Manurangsi, Warut Suksompong
We investigate fairness in the allocation of indivisible items among groups of agents using the notion of maximin share (MMS). While previous work has shown that no nontrivial mult…
Differentially Private Fair Division
Pasin Manurangsi, Warut Suksompong
Fairness and privacy are two important concerns in social decision-making processes such as resource allocation. We study privacy in the fair allocation of indivisible resources us…
Fixing Knockout Tournaments With Seeds
Pasin Manurangsi, Warut Suksompong
Knockout tournaments constitute a popular format for organizing sports competitions. While prior results have shown that it is often possible to manipulate a knockout tournament by…
The Price of Justified Representation
Edith Elkind, Piotr Faliszewski, Ayumi Igarashi +3
In multiwinner approval voting, the goal is to select -member committees based on voters' approval ballots. A well-studied concept of proportionality in this context is the just…
Justifying Groups in Multiwinner Approval Voting
Edith Elkind, Piotr Faliszewski, Ayumi Igarashi +3
Justified representation (JR) is a standard notion of representation in multiwinner approval voting. Not only does a JR committee always exist, but previous work has also shown thr…
On the Complexity of Fair House Allocation
Naoyuki Kamiyama, Pasin Manurangsi, Warut Suksompong
We study fairness in house allocation, where houses are to be allocated among agents so that every agent receives one house. We show that maximizing the number of envy-free…
Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy Theory
Pasin Manurangsi, Warut Suksompong
We study the allocation of indivisible goods among groups of agents using well-known fairness notions such as envy-freeness and proportionality. While these notions cannot always b…
Algorithmic Persuasion with Evidence
Martin Hoefer, Pasin Manurangsi, Alexandros Psomas
In a game of persuasion with evidence, a sender has private information. By presenting evidence on the information, the sender wishes to persuade a receiver to take a single action…
Consensus Halving for Sets of Items
Paul W. Goldberg, Alexandros Hollender, Ayumi Igarashi +2
Consensus halving refers to the problem of dividing a resource into two parts so that every agent values both parts equally. Prior work has shown that when the resource is represen…
Closing Gaps in Asymptotic Fair Division
Pasin Manurangsi, Warut Suksompong
We study a resource allocation setting where discrete items are to be divided among agents with additive utilities, and the agents' utilities for individual items are drawn…
Approximation and Hardness of Shift-Bribery
Piotr Faliszewski, Pasin Manurangsi, Krzysztof Sornat
In the Shift-Bribery problem we are given an election, a preferred candidate, and the costs of shifting this preferred candidate up the voters' preference orders. The goal is to fi…
The Price of Fairness for Indivisible Goods
Xiaohui Bei, Xinhang Lu, Pasin Manurangsi +1
We investigate the efficiency of fair allocations of indivisible goods using the well-studied price of fairness concept. Previous work has focused on classical fairness notions suc…
When Do Envy-Free Allocations Exist?
Pasin Manurangsi, Warut Suksompong
We consider a fair division setting in which indivisible items are to be allocated among agents, where the agents have additive utilities and the agents' utilities for indi…
Asymptotic Existence of Fair Divisions for Groups
Pasin Manurangsi, Warut Suksompong
The problem of dividing resources fairly occurs in many practical situations and is therefore an important topic of study in economics. In this paper, we investigate envy-free divi…
Computing an Approximately Optimal Agreeable Set of Items
Pasin Manurangsi, Warut Suksompong
We study the problem of finding a small subset of items that is \emph{agreeable} to all agents, meaning that all agents value the subset at least as much as its complement. Previou…
Assigning a Small Agreeable Set of Indivisible Items to Multiple Players
Warut Suksompong
We consider an assignment problem that has aspects of fair division as well as social choice. In particular, we investigate the problem of assigning a small subset from a set of in…