Author name cluster

Mashbat Suzuki

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

1 author row

AAMAS Conference 2025 Conference Paper

Neighborhood Stability in Assignments on Graphs

Haris Aziz
Grzegorz Lisowski
Mashbat Suzuki
Jeremy Vollen

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 stability. We assume that agents’ utilities are based only on their preferences over the assignees of adjacent vertices and that those preferences are binary. Having shown that even this very restricted setting does not guarantee neighborhood stable assignments, we focus on special cases providing such guarantees. We show that when the graph is a cycle or a path, a neighborhood stable assignment always exists for any preference profile. Also, we give a general condition under which neighborhood stable assignments always exist. For each of these results, we give a polynomial-time algorithm to compute a neighborhood stable assignment.

PDF

AAMAS Conference 2025 Conference Paper

Weighted Envy-free Allocation with Subsidy

Haris Aziz
Xin Huang
Kei Kimura
Indrajit Saha
Zhaohong Sun
Mashbat Suzuki
Makoto Yokoo

We consider the problem of fair allocation of indivisible items with subsidies when agents have weighted entitlements. Specifically, we extend the envy-freeability studied in the unweighted case to the weighted envy-freeability and delve deeper into its properties. We first highlight various important differences from the unweighted case, e. g. , the sufficient conditions that lead to envy-freeability in the unweighted case do not lead to weighted envy-freeability in the weighted case. We then present various results concerning weighted envy-freeability including general characterizations, algorithms for achieving and testing weighted envy-freeability, lower and upper bounds of the amount of subsidies for weighted envy-freeable allocations. Additionally, we design algorithms that ensure weighted envy-freeability while incorporating other fairness properties, such as weighted envy-freeness up to one item transfer.

PDF

AAAI Conference 2024 Conference Paper

Envy-Free House Allocation under Uncertain Preferences

Haris Aziz
Isaiah Iliffe
Bo Li
Angus Ritossa
Ankang Sun
Mashbat Suzuki

Envy-freeness is one of the most important fairness concerns when allocating items. We study envy-free house allocation when agents have uncertain preferences over items and consider several well-studied preference uncertainty models. The central problem that we focus on is computing an allocation that has the highest probability of being envy-free. We show that each model leads to a distinct set of algorithmic and complexity results, including detailed results on (in-)approximability. En route, we consider two related problems of checking whether there exists an allocation that is possibly or necessarily envy-free. We give a complete picture of the computational complexity of these two problems for all the uncertainty models we consider.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Fair Lotteries for Participatory Budgeting

Haris Aziz
Xinhang Lu
Mashbat Suzuki
Jeremy Vollen
Toby Walsh

In pursuit of participatory budgeting (PB) outcomes with broader fairness guarantees, we initiate the study of lotteries over discrete PB outcomes. As the projects have heterogeneous costs, the amount spent may not be equal ex ante and ex post. To address this, we develop a technique to bound the amount by which the ex-post spend differs from the ex-ante spend---the property is termed budget balanced up to one project (BB1). With respect to fairness, we take a best-of-both-worlds perspective, seeking outcomes that are both ex-ante and ex-post fair. Towards this goal, we initiate a study of ex-ante fairness properties in PB, including Individual Fair Share (IFS), Unanimous Fair Share (UFS) and their stronger variants, as well as Group Fair Share (GFS). We show several incompatibility results between these ex-ante fairness notions and existing ex-post concepts based on justified representation. One of our main contributions is a randomized algorithm which simultaneously satisfies ex-ante Strong UFS, ex-post full justified representation (FJR) and ex-post BB1 for PB with binary utilities.

PDF Details DOI

JAIR Journal 2024 Journal Article

Mixed Fair Division: A Survey

Shengxin Liu
Xinhang Lu
Mashbat Suzuki
Toby Walsh

Fair division considers the allocation of scarce resources among agents in such a way that every agent gets a fair share. It is a fundamental problem in society and has received significant attention and rapid developments from the game theory and artificial intelligence communities in recent years. The majority of the fair division literature can be divided along at least two orthogonal directions: goods versus chores, and divisible versus indivisible resources. In this survey, besides describing the state of the art, we outline a number of interesting open questions and future directions in three mixed fair division settings: (i) indivisible goods and chores, (ii) divisible and indivisible goods (mixed goods), and (iii) indivisible goods with subsidy which can be viewed like a divisible good.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Mixed Fair Division: A Survey

Shengxin Liu
Xinhang Lu
Mashbat Suzuki
Toby Walsh

The fair allocation of resources to agents is a fundamental problem in society and has received significant attention and rapid developments from the game theory and artificial intelligence communities in recent years. The majority of the fair division literature can be divided along at least two orthogonal directions: goods versus chores, and divisible versus indivisible resources. In this survey, besides describing the state of the art, we outline a number of interesting open questions in three mixed fair division settings: (i) indivisible goods and chores, (ii) divisible and indivisible goods (i.e., mixed goods), and (iii) fair division of indivisible goods with subsidy.

PDF Details DOI

AAMAS Conference 2023 Conference Paper

Fair Allocation of Two Types of Chores

Haris Aziz
Jeremy Lindsay
Angus Ritossa
Mashbat Suzuki

We consider the problem of fair allocation of indivisible chores under additive valuations. We assume that the chores are divided into two types and under this scenario, we present several results. Our first result is a new characterization of Pareto optimal allocations in our setting and a polynomial-time algorithm to compute an envy-free up to one item (EF1) and Pareto optimal allocation. We then turn to the question of whether we can achieve a stronger fairness concept called envy-free up any item (EFX). We present a polynomial-time algorithm that returns an EFX allocation. Finally, we show that for our setting, it can be checked in polynomial time whether an envy-free allocation exists or not.

PDF

NeurIPS Conference 2022 Conference Paper

Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism

Haris Aziz
Alexander Lam
Mashbat Suzuki
Toby Walsh

Proportionality is an attractive fairness concept that has been applied to a range of problems including the facility location problem, a classic problem in social choice. In our work, we propose a concept called Strong Proportionality, which ensures that when there are two groups of agents at different locations, both groups incur the same total cost. We show that although Strong Proportionality is a well-motivated and basic axiom, there is no deterministic strategyproof mechanism satisfying the property. We then identify a randomized mechanism called Random Rank (which uniformly selects a number $k$ between $1$ to $n$ and locates the facility at the $k$'th highest agent location) which satisfies Strong Proportionality in expectation. Our main theorem characterizes Random Rank as the unique mechanism that achieves universal truthfulness, universal anonymity, and Strong Proportionality in expectation among all randomized mechanisms. Finally, we show via the AverageOrRandomRank mechanism that even stronger ex-post fairness guarantees can be achieved by weakening universal truthfulness to strategyproofness in expectation.

PDF Details