Mashbat Suzuki

Subquadratic Subsidies for Nonnegative or Nonpositive Valuations

Max Dupré la Tour, Mashbat Suzuki

We study envy-freeness with subsidies for indivisible items beyond additive valuations. Assuming that every single-item marginal value lies in $[- 1, 1]$ , we prove that a total subsi…

Sampford Apportionment Satisfies Threshold Monotonicity

Haris Aziz, Simon Mackenzie, Mashbat Suzuki

Apportionment distributes a fixed number of legislative seats among political parties in proportion to their vote shares. Randomization can satisfy quota in every realization and e…

Anchoring for Truthfulness: The Random-Anchor Volume Mechanism for Multi-Facility Location

Haris Aziz, Simon Mackenzie, Mashbat Suzuki

We study the strategyproof placement of $k$ facilities on the real line for $n$ agents who privately report their locations, without monetary transfers. For two facilities, the…

When One Good Is Not Enough: EF1 and Pareto Optimality Are Not Compatible for Submodular Valuations

Simon Mackenzie, Mashbat Suzuki

One of the central questions in discrete fair division is whether fairness and efficiency can be achieved simultaneously. For indivisible goods, a canonical relaxation of envy-free…

Best-of-Both-Worlds Fairness for Mixed Goods and Chores

Haris Aziz, Xiaolin Bu, Xinhang Lu +4

We study the fundamental problem of fairly dividing indivisible items among agents with additive utilities. In our model, an item can be a good yielding non-negative utilities to s…

Optimal Subsidy Bounds for Goods and Chores: One Dollar Each Suffices

Xinhang Lu, Simon Mackenzie, Mashbat Suzuki

We study the fair allocation of $m$ indivisible items to $n$ agents with additive utilities. In our setting, each indivisible item may be a good, yielding non-negative utility to s…

Counterexamples to EFX for Submodular and Subadditive Valuations

Simon Mackenzie, Mashbat Suzuki

The existence of EFX allocations is a fundamental question in fair division. In this paper, we construct a three-agent, eight-good instance with monotone subadditive valuations suc…

Fair Division with Indivisible Goods, Chores, and Cake

Haris Aziz, Xinhang Lu, Simon Mackenzie +1

We study the problem of fairly allocating indivisible items and a desirable heterogeneous divisible good (i.e., cake) to agents with additive utilities. In our paper, each indivisi…

Fair and Efficient Allocation of Indivisible Mixed Manna

Siddharth Barman, Vishwa Prakash HV, Aditi Sethia +1

We study fair division of indivisible mixed manna (items whose values may be positive, negative, or zero) among agents with additive valuations. Here, we establish that fairness --…

Whoever Said Money Won't Solve All Your Problems? Weighted Envy-free Allocation with Subsidy

Noga Klein Elmalem, Haris Aziz, Rica Gonen +7

We explore solutions for fairly allocating indivisible items among agents assigned weights representing their entitlements. Our fairness goal is weighted-envy-freeness (WEF), where…

Social Welfare Maximization in Approval-Based Committee Voting under Uncertainty

Haris Aziz, Yuhang Guo, Venkateswara Rao Kagita +2

Approval voting is widely used for making multi-winner voting decisions. The canonical rule (also called Approval Voting) used in the setting aims to maximize social welfare by sel…

On the Subsidy of Envy-Free Orientations in Graphs

Bo Li, Ankang Sun, Mashbat Suzuki +1

We study a fair division problem in (multi)graphs where $n$ agents (vertices) are pairwise connected by items (edges), and each agent is only interested in its incident items. We c…

Maximum Welfare Allocations under Quantile Valuations

Haris Aziz, Shivika Narang, Mashbat Suzuki

We propose a new model for aggregating preferences over a set of indivisible items based on a quantile value. In this model, each agent is endowed with a specific quantile, and the…

Approximately Fair and Population Consistent Budget Division via Simple Payment Schemes

Haris Aziz, Patrick Lederer, Xinhang Lu +2

In approval-based budget division, a budget needs to be distributed to candidates based on the voters' approval ballots over these candidates. In the pursuit of a simple, consisten…

Weighted Envy-free Allocation with Subsidy

Haris Aziz, Xin Huang, Kei Kimura +4

We consider the problem of fair allocation of indivisible items with subsidies when agents have weighted entitlements. After highlighting several important differences from the unw…

Approval-Based Committee Voting under Uncertainty

Hariz Aziz, Venkateswara Rao Kagita, Baharak Rastegari +1

We study approval-based committee voting in which a target number of candidates are selected based on voters' approval preferences over candidates. In contrast to most of the work,…

Maximin Fair Allocation of Indivisible Items under Cost Utilities

Sirin Botan, Angus Ritossa, Mashbat Suzuki +1

We study the problem of fairly allocating indivisible goods among a set of agents. Our focus is on the existence of allocations that give each agent their maximin fair share--the v…

Neighborhood Stability in Assignments on Graphs

Haris Aziz, Grzegorz Lisowski, Mashbat Suzuki +1

We study the problem of assigning agents to the vertices of a graph such that no pair of neighbors can benefit from swapping assignments -- a property we term neighborhood stabilit…

Compatibility of Fairness and Nash Welfare under Subadditive Valuations

Siddharth Barman, Mashbat Suzuki

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 subadditiv…

cs.GT2024★ 2 cited

Maximum Flow is Fair: A Network Flow Approach to Committee Voting

Mashbat Suzuki, Jeremy Vollen

In the committee voting setting, a subset of $k$ alternatives is selected based on the preferences of voters. In this paper, our goal is to efficiently compute $ex-ante$ f…