Arrow Research search

Author name cluster

Ayumi Igarashi

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.

36 papers
1 author row

Possible papers

36

AAAI Conference 2026 Conference Paper

Fair Allocation of Indivisible Goods with Variable Groups

  • Paul Gölz
  • Ayumi Igarashi
  • Pasin Manurangsi
  • Warut Suksompong

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 groups in a fair manner. We show that for any number of groups and corresponding sizes, there always exists an envy-free up to one good (EF1) outcome, thereby generalizing an important result from the individual setting. Our result holds for arbitrary monotonic utilities and comes with an efficient algorithm. We also prove that an EF1 outcome is guaranteed to exist even when the goods lie on a path and each group must receive a connected bundle. In addition, we consider a probabilistic model where the utilities are additive and drawn randomly from a distribution. We show that if there are n agents and the number of goods m is divisible by the number of groups k, then an envy-free outcome exists with high probability if m = ω(log n), and this bound is tight. On the other hand, if m is not divisible by k, then an envy-free outcome is unlikely to exist as long as m = o(√n).

PDF Details DOI

AAMAS Conference 2026 Conference Paper

Maximin Shares with Lower Quotas

  • Hirota Kinoshita
  • Ayumi Igarashi

We study the fair division of indivisible items among 𝑛 agents with heterogeneous additive valuations, subject to lower and upper quotas on the number of items allocated to each agent. Such constraints are crucial in various applications, ranging from personnel assignments to computing resource distribution. This paper focuses on the fairness criterion known as maximin shares (MMS) and its approximations. Under arbitrary lower and upper quotas, we show that a 2𝑛 3𝑛−1 -MMS allocation of goods exists and can be computed in polynomial time, while we also present a polynomial-time algorithm for finding a 3𝑛−1 2𝑛 -MMS allocation of chores. Furthermore, we consider the generalized scenario where items are partitioned into multiple categories, each with its own lower and upper quotas. In this setting, our algorithm computes an 𝑛 2𝑛−1 -MMS allocation of goods or a 2𝑛−1 𝑛 -MMS allocation of chores in polynomial time. These results extend previous work on the cardinality constraints, i. e. , the special case where only upper quotas are imposed.

PDF

AAMAS Conference 2026 Conference Paper

Mechanism-Informed Learning for Fair Division

  • Ryota Maruo
  • Tomohiko Yokoyama
  • Ayumi Igarashi
  • Koh Takeuchi

Fair division provides a simple yet powerful framework for modeling fairness in resource allocation. While existing literature typically assumes complete information about preferences, many practical scenarios involve incomplete preferences, posing challenges in computing fair allocations. In this paper, we propose mechanisminformed preference learning, a framework that integrates neural networks with differentiable approximations of classical fair division mechanisms—adjusted winner, round-robin, and movingknife—to estimate fair allocations from incomplete preferences. Experiments on real-world household chore preference data show that our mechanism-informed framework achieves fairer allocations, compared to methods without mechanism information.

PDF

AAMAS Conference 2025 Conference Paper

Asymptotic Existence of Class Envy-free Matchings

  • Tomohiko Yokoyama
  • Ayumi Igarashi

We consider a one-sided matching problem where agents who are partitioned into disjoint classes and each class must receive fair treatment in a desired matching. This model, proposed by Benabbou et al. [9], aims to address various real-life scenarios, such as the allocation of public housing and medical resources across different ethnic, age, and other demographic groups. Our focus is on achieving class envy-free matchings, where each class receives a total utility at least as large as the maximum value of a matching they would achieve from the items matched to another class. While class envy-freeness for worst-case utilities is unattainable without leaving some valuable items unmatched, such extreme cases may rarely occur in practice. To analyze the existence of a class envyfree matching in practice, we study a distributional model where agents’ utilities for items are drawn from a probability distribution. Our main result establishes the asymptotic existence of a desired matching, showing that a round-robin algorithm produces a class envy-free matching as the number of agents approaches infinity.

PDF

IJCAI Conference 2025 Conference Paper

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 conflicts between a pair of goods. Each agent is allocated an independent set in the graph. In a recent work of Kumar et al. (AAMAS, 2024), it was shown that a maximal EF1 allocation exists for interval graphs and two agents with monotone valuations. We significantly extend this result by establishing that a maximal EF1 allocation exists for any graph when the two agents have monotone valuations. To compute such an allocation, we present a polynomial-time algorithm for additive valuations, as well as a pseudo-polynomial time algorithm for monotone valuations. Moreover, we complement our findings by providing a counterexample demonstrating a maximal EF1 allocation may not exist for three agents with monotone valuations; further, we establish NP-hardness of determining the existence of such allocations for every fixed number n >= 3 of agents. All of our results for goods also apply to the allocation of chores.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Fair and Efficient Completion of Indivisible Goods

  • Vishwa Prakash HV
  • Ayumi Igarashi
  • Rohit Vaish

We formulate the problem of fair and efficient completion of indivisible goods, defined as follows: Given a partial allocation of indivisible goods among agents, does there exist an allocation of the remaining goods (i.e., a completion) that satisfies fairness and economic efficiency guarantees of interest? We study the computational complexity of the completion problem for prominent fairness and efficiency notions such as envy-freeness up to one good (EF1), proportionality up to one good (Prop1), maximin share (MMS), and Pareto optimality (PO), and focus on the class of additive valuations as well as its subclasses such as binary additive and lexicographic valuations. We find that while the completion problem is significantly harder than the standard fair division problem (wherein the initial partial allocation is empty), the consideration of restricted preferences facilitates positive algorithmic results for threshold-based fairness notions (Prop1 and MMS). On the other hand, the completion problem remains computationally intractable for envy-based notions such as EF1 and EF1+PO even under restricted preferences.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Individually Stable Dynamics in Coalition Formation over Graphs

  • Angelo Fanelli
  • Laurent Gourvès
  • Ayumi Igarashi
  • Luca Moscardelli

Coalition formation over graphs is a well studied class of games whose players are vertices and feasible coalitions must be connected subgraphs. In this setting, the existence and computation of equilibria, under various notions of stability, has attracted a lot of attention. However, the natural process by which players, starting from any feasible state, strive to reach an equilibrium after a series of unilateral improving deviations, has been less studied. We investigate the convergence of dynamics towards individually stable outcomes under the following perspective: what are the most general classes of preferences and graph topologies guaranteeing convergence? To this aim, on the one hand, we cover a hierarchy of preferences, ranging from the most general to a subcase of additively separable preferences, including individually rational and monotone cases. On the other hand, given that convergence may fail in graphs admitting a cycle even in our most restrictive preference class, we analyze acyclic graph topologies such as trees, paths, and stars.

PDF Details DOI

AIJ Journal 2024 Journal Article

Class fairness in online matching

  • Hadi Hosseini
  • Zhiyi Huang
  • Ayumi Igarashi
  • Nisarg Shah

We initiate the study of fairness among classes of agents in online bipartite matching where there is a given set of offline vertices (aka agents) and another set of vertices (aka items) that arrive online and must be matched irrevocably upon arrival. In this setting, agents are partitioned into classes and the matching is required to be fair with respect to the classes. We adapt popular fairness notions (e. g. envy-freeness, proportionality, and maximin share) and their relaxations to this setting and study deterministic algorithms for matching indivisible items (leading to integral matchings) and for matching divisible items (leading to fractional matchings). For matching indivisible items, we propose an adaptive-priority-based algorithm, Match-and-Shift, prove that it achieves 1 2 -approximation of both class envy-freeness up to one item and class maximin share fairness, and show that each guarantee is tight. For matching divisible items, we design a water-filling-based algorithm, Equal-Filling, that achieves ( 1 − 1 e ) -approximation of class envy-freeness and class proportionality; we prove 1 − 1 e to be tight for class proportionality and establish a 3 4 upper bound on class envy-freeness. Finally, we discuss several challenges in designing randomized algorithms that achieve reasonable fairness approximation ratios. Nonetheless, we build upon Equal-Filling to design a randomized algorithm for matching indivisible items, Equal-Filling-OCS, which achieves 0. 593-approximation of class proportionality.

Details DOI

AAMAS Conference 2024 Conference Paper

Keeping the Harmony Between Neighbors: Local Fairness in Graph Fair Division

  • Halvard Hummel
  • Ayumi Igarashi

We study the problem of allocating indivisible resources under the connectivity constraints of a graph 𝐺. This model, initially introduced by Bouveret et al. (published in IJCAI, 2017), effectively encompasses a diverse array of scenarios characterized by spatial or temporal limitations, including the division of land plots and the allocation of time plots. In this paper, we introduce a novel fairness concept that integrates local comparisons within the social network formed by a connected allocation of the item graph. Our particular focus is to achieve pairwise-maximin fair share (PMMS) among the "neighbors" within this network. For any underlying graph structure, we show that a connected allocation that maximizes Nash welfare guarantees a (1/2)-PMMS fairness. Moreover, for two agents, we establish that a (3/4)-PMMS allocation can be efficiently computed. Additionally, we demonstrate that for three agents and the items aligned on a path, a PMMS allocation is always attainable and can be computed in polynomial time. Lastly, when agents have identical additive utilities, we present a pseudo-polynomialtime algorithm for a (3/4)-PMMS allocation, irrespective of the underlying graph 𝐺. Furthermore, we provide a polynomial-time algorithm for obtaining a PMMS allocation when 𝐺 is a tree.

PDF

AAAI Conference 2024 Conference Paper

Reachability of Fair Allocations via Sequential Exchanges

  • Ayumi Igarashi
  • Naoyuki Kamiyama
  • Warut Suksompong
  • Sheung Man Yuen

In the allocation of indivisible goods, a prominent fairness notion is envy-freeness up to one good (EF1). We initiate the study of reachability problems in fair division by investigating the problem of whether one EF1 allocation can be reached from another EF1 allocation via a sequence of exchanges such that every intermediate allocation is also EF1. We show that two EF1 allocations may not be reachable from each other even in the case of two agents, and deciding their reachability is PSPACE-complete in general. On the other hand, we prove that reachability is guaranteed for two agents with identical or binary utilities as well as for any number of agents with identical binary utilities. We also examine the complexity of deciding whether there is an EF1 exchange sequence that is optimal in the number of exchanges required.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Repeated Fair Allocation of Indivisible Items

  • Ayumi Igarashi
  • Martin Lackner
  • Oliviero Nardi
  • Arianna Novaro

The problem of fairly allocating a set of indivisible items is a well-known challenge in the field of (computational) social choice. In this scenario, there is a fundamental incompatibility between notions of fairness (such as envy-freeness and proportionality) and economic efficiency (such as Pareto-optimality). However, in the real world, items are not always allocated once and for all, but often repeatedly. For example, the items may be recurring chores to distribute in a household. Motivated by this, we initiate the study of the repeated fair division of indivisible goods and chores, and propose a formal model for this scenario. In this paper, we show that, if the number of repetitions is a multiple of the number of agents, there always exists a sequence of allocations that is proportional and Pareto-optimal. On the other hand, irrespective of the number of repetitions, an envy-free and Pareto-optimal sequence of allocations may not exist. For the case of two agents, we show that if the number of repetitions is even, it is always possible to find a sequence of allocations that is overall envy-free and Pareto-optimal. We then prove even stronger fairness guarantees, showing that every allocation in such a sequence satisfies some relaxation of envy-freeness. Finally, in case that the number of repetitions can be chosen freely, we show that envy-free and Pareto-optimal allocations are achievable for any number of agents.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Class Fairness in Online Matching

  • Hadi Hosseini
  • Zhiyi Huang
  • Ayumi Igarashi
  • Nisarg Shah

We initiate the study of fairness among classes of agents in online bipartite matching where there is a given set of offline vertices (aka agents) and another set of vertices (aka items) that arrive online and must be matched irrevocably upon arrival. In this setting, agents are partitioned into a set of classes and the matching is required to be fair with respect to the classes. We adopt popular fairness notions (e.g. envy-freeness, proportionality, and maximin share) and their relaxations to this setting and study deterministic and randomized algorithms for matching indivisible items (leading to integral matchings) and for matching divisible items (leading to fractional matchings). For matching indivisible items, we propose an adaptive-priority-based algorithm, MATCH-AND-SHIFT, prove that it achieves (1/2)-approximation of both class envy-freeness up to one item and class maximin share fairness, and show that each guarantee is tight. For matching divisible items, we design a water-filling-based algorithm, EQUAL-FILLING, that achieves (1-1/e)-approximation of class envy-freeness and class proportionality; we prove (1-1/e) to be tight for class proportionality and establish a 3/4 upper bound on class envy-freeness.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Fair Division with Two-Sided Preferences

  • Ayumi Igarashi
  • Yasushi Kawase
  • Warut Suksompong
  • Hanna Sumita

We study a fair division setting in which a number of players are to be fairly distributed among a set of teams. In our model, not only do the teams have preferences over the players as in the canonical fair division setting, but the players also have preferences over the teams. We focus on guaranteeing envy-freeness up to one player (EF1) for the teams together with a stability condition for both sides. We show that an allocation satisfying EF1, swap stability, and individual stability always exists and can be computed in polynomial time, even when teams may have positive or negative values for players. Similarly, a balanced and swap stable allocation that satisfies a relaxation of EF1 can be computed efficiently. When teams have nonnegative values for players, we prove that an EF1 and Pareto optimal allocation exists and, if the valuations are binary, can be found in polynomial time. We also examine the compatibility between EF1 and justified envy-freeness.

PDF Details DOI

AAAI Conference 2023 Conference Paper

How to Cut a Discrete Cake Fairly

  • Ayumi Igarashi

Cake-cutting is a fundamental model of dividing a heterogeneous resource, such as land, broadcast time, and advertisement space. In this study, we consider the problem of dividing indivisible goods fairly under the connectivity constraints of a path. We prove that a connected division of indivisible items satisfying a discrete counterpart of envy-freeness, called envy-freeness up to one good (EF1), always exists for any number of agents n with monotone valuations. Our result settles an open question raised by Bilò et al. (2019), who proved that an EF1 connected division always exists for four agents with monotone valuations. Moreover, the proof can be extended to show the following (1) ``secretive" and (2) ``extra" versions: (1) for n agents with monotone valuations, the path can be divided into n connected bundles such that an EF1 assignment of the remaining bundles can be made to the other agents for any selection made by the “secretive agent”; (2) for n+1 agents with monotone valuations, the path can be divided into n connected bundles such that when any ``extra agent” leaves, an EF1 assignment of the bundles can be made to the remaining agents.

PDF Details DOI

TCS Journal 2023 Journal Article

Justifying groups in multiwinner approval voting

  • Edith Elkind
  • Piotr Faliszewski
  • Ayumi Igarashi
  • Pasin Manurangsi
  • Ulrike Schmidt-Kraepelin
  • Warut Suksompong

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 through experiments that the JR condition can typically be fulfilled by groups of fewer than k candidates, where k is the target size of the committee. In this paper, we study such groups—known as n / k -justifying groups—both theoretically and empirically. First, we show that under the impartial culture model, n / k -justifying groups of size less than k / 2 are likely to exist, which implies that the number of JR committees is usually large. We then present efficient approximation algorithms that compute a small n / k -justifying group for any given instance, and a polynomial-time exact algorithm when the instance admits a tree representation. In addition, we demonstrate that small n / k -justifying groups can often be useful for obtaining a gender-balanced JR committee even though the problem is NP-hard.

Details DOI

AAAI Conference 2023 System Paper

Kajibuntan: A House Chore Division App

  • Ayumi Igarashi
  • Tomohiko Yokoyama

Couples often encounter the challenge of sharing house chores. This raises the fundamental question of how to divide chores. In this paper, we present a new application for a fair division of household chores. Our platform, called Kajibuntan, allows couples to specify the set of chores to be shared, their preferences over them, and the current allocation. Our tool visualizes the current allocation and makes proposals according to their preferences based on the theory of fair division. The goal of our tool is to provide a systematic and transparent system to divide household chores and help creating harmony in the home.

PDF Details DOI

AAMAS Conference 2022 Conference Paper

Fair and Truthful Mechanism with Limited Subsidy

  • Hiromichi Goko
  • Ayumi Igarashi
  • Yasushi Kawase
  • Kazuhisa Makino
  • Hanna Sumita
  • Akihisa Tamura
  • Yu Yokoi
  • Makoto Yokoo

The notion of envy-freeness is a natural and intuitive fairness requirement in resource allocation. With indivisible goods, such fair allocations are unfortunately not guaranteed to exist. Classical works have avoided this issue by introducing an additional divisible resource, i. e. , money, to subsidize envious agents. In this paper, we aim to design a truthful allocation mechanism of indivisible goods to achieve both fairness and efficiency criteria with a limited amount of subsidy. Following the work of Halpern and Shah, our central question is as follows: to what extent do we need to rely on the power of money to accomplish these objectives? We show that, when agents have matroidal valuations, there is a truthful allocation mechanism that achieves envy-freeness and utilitarian optimality by subsidizing each agent with at most 1, the maximum marginal contribution of each item for each agent. The design of the mechanism rests crucially on the underlying matroidal M-convexity of the Lorenz dominating allocations. For superadditive valuations, we show that there is a truthful mechanism that achieves envy-freeness and utilitarian optimality, with each agent receiving a subsidy of at most 𝑚; furthermore, we show that the amount 𝑚 is necessary even when agents have additive valuations.

PDF

AAAI Conference 2022 Conference Paper

The Price of Justified Representation

  • Edith Elkind
  • Piotr Faliszewski
  • Ayumi Igarashi
  • Pasin Manurangsi
  • Ulrike Schmidt-Kraepelin
  • Warut Suksompong

In multiwinner approval voting, the goal is to select kmember committees based on voters’ approval ballots. A well-studied concept of proportionality in this context is the justified representation (JR) axiom, which demands that no large cohesive group of voters remains unrepresented. However, the JR axiom may conflict with other desiderata, such as coverage (maximizing the number of voters who approve at least one committee member) or social welfare (maximizing the number of approvals obtained by committee members). In this work, we investigate the impact of imposing the JR axiom (as well as the more demanding EJR axiom) on social welfare and coverage. Our approach is threefold: we derive worst-case bounds on the loss of welfare/coverage that is caused by imposing JR, study the computational complexity of finding ‘good’ committees that provide JR (obtaining a hardness result, an approximation algorithm, and an exact algorithm for one-dimensional preferences), and examine this setting empirically on several synthetic datasets.

PDF Details

AIJ Journal 2021 Journal Article

Schelling games on graphs

  • Aishwarya Agarwal
  • Edith Elkind
  • Jiarui Gan
  • Ayumi Igarashi
  • Warut Suksompong
  • Alexandros A. Voudouris

We study strategic games inspired by Schelling's seminal model of residential segregation. These games are played on undirected graphs, with the set of agents partitioned into multiple types; each agent either aims to maximize the fraction of her neighbors who are of her own type, or occupies a node of the graph and never moves away. We consider two natural variants of this model: in jump games agents can jump to empty nodes of the graph to increase their utility, while in swap games they can swap positions with other agents. We investigate the existence, computational complexity, and quality of equilibrium assignments in these games, both from a social welfare perspective and from a diversity perspective. Some of our results extend to a more general setting where the preferences of the agents over their neighbors are defined by a social network rather than a partition into types.

Details DOI

AAAI Conference 2021 Conference Paper

The Price of Connectivity in Fair Division

  • Xiaohui Bei
  • Ayumi Igarashi
  • Xinhang Lu
  • Warut Suksompong

We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. Our focus is on the well-studied fairness notion of maximin share fairness. We introduce the price of connectivity to capture the largest gap between the graph-specific and the unconstrained maximin share, and derive bounds on this quantity which are tight for large classes of graphs in the case of two agents and for paths and stars in the general case. For instance, with two agents we show that for biconnected graphs it is possible to obtain at least 3/4 of the maximin share with connected allocations, while for the remaining graphs the guarantee is at most 1/2. Our work demonstrates several applications of graph-theoretic tools and concepts to fair division problems.

PDF Details

IJCAI Conference 2020 Conference Paper

Fair Division of Time: Multi-layered Cake Cutting

  • Hadi Hosseini
  • Ayumi Igarashi
  • Andrew Searns

We initiate the study of multi-layered cake cutting with the goal of fairly allocating multiple divisible resources (layers of a cake) among a set of agents. The key requirement is that each agent can only utilize a single resource at each time interval. Several real-life applications exhibit such restrictions on overlapping pieces, for example, assigning time intervals over multiple facilities and resources or assigning shifts to medical professionals. We investigate the existence and computation of envy-free and proportional allocations. We show that envy-free allocations that are both feasible and contiguous are guaranteed to exist for up to three agents with two types of preferences, when the number of layers is two. We further devise an algorithm for computing proportional allocations for any number of agents when the number of layers is factorable to three and/or some power of two.

PDF Details DOI

IJCAI Conference 2019 Conference Paper

Fair Allocation of Indivisible Goods and Chores

  • Haris Aziz
  • Ioannis Caragiannis
  • Ayumi Igarashi
  • Toby Walsh

We consider the problem of fairly dividing a set of items. Much of the fair division literature assumes that the items are ``goods'' i. e. , they yield positive utility for the agents. There is also some work where the items are ``chores'' that yield negative utility for the agents. In this paper, we consider a more general scenario where an agent may have negative or positive utility for each item. This framework captures, e. g. , fair task assignment, where agents can have both positive and negative utilities for each task. We show that whereas some of the positive axiomatic and computational results extend to this more general setting, others do not. We present several new and efficient algorithms for finding fair allocations in this general setting. We also point out several gaps in the literature regarding the existence of allocations satisfying certain fairness and efficiency properties and further study the complexity of computing such allocations.

PDF Details

AAAI Conference 2019 Conference Paper

Forming Probably Stable Communities with Limited Interactions

  • Ayumi Igarashi
  • Jakub Sliwinski
  • Yair Zick

A community needs to be partitioned into disjoint groups; each community member has an underlying preference over the groups that they would want to be a member of. We are interested in finding a stable community structure: one where no subset of members S wants to deviate from the current structure. We model this setting as a hedonic game, where players are connected by an underlying interaction network, and can only consider joining groups that are connected subgraphs of the underlying graph. We analyze the relation between network structure, and one’s capability to infer statistically stable (also known as PAC stable) player partitions from data. We show that when the interaction network is a forest, one can efficiently infer PAC stable coalition structures. Furthermore, when the underlying interaction graph is not a forest, efficient PAC stabilizability is no longer achievable. Thus, our results completely characterize when one can leverage the underlying graph structure in order to compute PAC stable outcomes for hedonic games. Finally, given an unknown underlying interaction network, we show that it is NP-hard to decide whether there exists a forest consistent with data samples from the network.

PDF Details

AAMAS Conference 2019 Conference Paper

Hedonic Diversity Games

  • Robert Bredereck
  • Edith Elkind
  • Ayumi Igarashi

We consider a coalition formation setting where each agent belongs to one of the two types, and agents’ preferences over coalitions are determined by the fraction of the agents of their own type in each coalition. This setting differs from the well-studied Schelling’s model in that some agents may prefer homogeneous coalitions, while others may prefer to be members of a diverse group, or a group that mostly consists of agents of the other type. We model this setting as a hedonic game and investigate the existence of stable outcomes using hedonic games solution concepts. We show that a core stable outcome may fail to exist and checking the existence of core stable outcomes is computationally hard. On the other hand, we propose an efficient algorithm to find an individually stable outcome under the natural assumption that agents’ preferences over fractions of the agents of their own type are single-peaked.

PDF

AAAI Conference 2019 Conference Paper

Pareto-Optimal Allocation of Indivisible Goods with Connectivity Constraints

  • Ayumi Igarashi
  • Dominik Peters

We study the problem of allocating indivisible items to agents with additive valuations, under the additional constraint that bundles must be connected in an underlying item graph. Previous work has considered the existence and complexity of fair allocations. We study the problem of finding an allocation that is Pareto-optimal. While it is easy to find an efficient allocation when the underlying graph is a path or a star, the problem is NP-hard for many other graph topologies, even for trees of bounded pathwidth or of maximum degree 3. We show that on a path, there are instances where no Pareto-optimal allocation satisfies envy-freeness up to one good, and that it is NP-hard to decide whether such an allocation exists, even for binary valuations. We also show that, for a path, it is NP-hard to find a Pareto-optimal allocation that satisfies maximin share, but show that a moving-knife algorithm can find such an allocation when agents have binary valuations that have a non-nested interval structure.

PDF Details

IJCAI Conference 2019 Conference Paper

Robustness against Agent Failure in Hedonic Games

  • Ayumi Igarashi
  • Kazunori Ota
  • Yuko Sakurai
  • Makoto Yokoo

We study how stability can be maintained even after any set of at most k players leave their groups, in the context of hedonic games. While stability properties ensure an outcome to be robust against players' deviations, it has not been considered how an unexpected change caused by a sudden deletion of players affects stable outcomes. In this paper we propose a novel criterion that reshapes stability form robustness aspect. We observe that some stability properties can be no longer preserved even when a single agent is removed. However, we obtain positive results by focusing on symmetric friend-oriented hedonic games. We prove that we can efficiently decide the existence of robust outcomes with respect to Nash stability underdeletion of any number of players or contractual individual stability under deletion of a single player. We also prove that symmetric additively separable games always admit an individual stable outcome that is robust with respect to individual rationality.

PDF Details

AAMAS Conference 2019 Conference Paper

Robustness against Agent Failure in Hedonic Games

  • Ayumi Igarashi
  • Kazunori Ota
  • Yuko Sakurai
  • Makoto Yokoo

In many real-world scenarios, stability is a key property in coalition formation to cope with uncertainty. In this paper, we propose a novel criterion that reshapes stability from robustness aspect. Specifically, we consider the problem of how stability can be maintained even after a small number of players leave the entire game, in the context of hedonic games. While one cannot guarantee the existence of robust outcomes with respect to most of the stability requirements, we identify several classes of friend-oriented and enemy-oriented games for which one can find a desired outcome efficiently. We also show that a symmetric additively hedonic game always admits an outcome that is individually stable and robust with respect to individual rationality.

PDF

IJCAI Conference 2019 Conference Paper

Schelling Games on Graphs

  • Edith Elkind
  • Jiarui Gan
  • Ayumi Igarashi
  • Warut Suksompong
  • Alexandros A. Voudouris

We consider strategic games that are inspired by Schelling's model of residential segregation. In our model, the agents are partitioned into k types and need to select locations on an undirected graph. Agents can be either stubborn, in which case they will always choose their preferred location, or strategic, in which case they aim to maximize the fraction of agents of their own type in their neighborhood. We investigate the existence of equilibria in these games, study the complexity of finding an equilibrium outcome or an outcome with high social welfare, and also provide upper and lower bounds on the price of anarchy and stability. Some of our results extend to the setting where the preferences of the agents over their neighbors are defined by a social network rather than a partition into types.

PDF Details

AAAI Conference 2018 Conference Paper

Cooperative Games With Bounded Dependency Degree

  • Ayumi Igarashi
  • Rani Izsak
  • Edith Elkind

Cooperative games provide a framework to study cooperation among self-interested agents. They offer a number of solution concepts describing how the outcome of the cooperation should be shared among the players. Unfortunately, computational problems associated with many of these solution concepts tend to be intractable—NP-hard or worse. In this paper, we incorporate complexity measures recently proposed by Feige and Izsak (2013), called dependency degree and supermodular degree, into the complexity analysis of cooperative games. We show that many computational problems for cooperative games become tractable for games whose dependency degree or supermodular degree are bounded. In particular, we prove that simple games admit efficient algorithms for various solution concepts when the supermodular degree is small; further, we show that computing the Shapley value is always in FPT with respect to the dependency degree. Finally, we observe that, while determining the dependency among players is computationally hard, there are efficient algorithms for special classes of games.

PDF Details

AAAI Conference 2018 Conference Paper

Multiwinner Elections With Diversity Constraints

  • Robert Bredereck
  • Piotr Faliszewski
  • Ayumi Igarashi
  • Martin Lackner
  • Piotr Skowron

We develop a model of multiwinner elections that combines performance-based measures of the quality of the committee (such as, e. g. , Borda scores of the committee members) with diversity constraints. Specifically, we assume that the candidates have certain attributes (such as being a male or a female, being junior or senior, etc.) and the goal is to elect a committee that, on the one hand, has as high a score regarding a given performance measure, but that, on the other hand, meets certain requirements (e. g. , of the form “at least 30% of the committee members are junior candidates and at least 40% are females”). We analyze the computational complexity of computing winning committees in this model, obtaining polynomial-time algorithms (exact and approximate) and NPhardness results. We focus on several natural classes of voting rules and diversity constraints.

PDF Details

AAMAS Conference 2017 Conference Paper

Coalition Formation in Structured Environments

  • Ayumi Igarashi

We study coalition formation games in which cooperation among the players is restricted by some combinatorial structures. We investigate the existence and computational issues related to stable outcomes in such games. In particular, we show that acyclicity is often sufficient for several notions of stability.

PDF

IJCAI Conference 2017 Conference Paper

Fair Division of a Graph

  • Sylvain Bouveret
  • Katarína Cechlárová
  • Edith Elkind
  • Ayumi Igarashi
  • Dominik Peters

We consider fair allocation of indivisible items under an additional constraint: there is an undirected graph describing the relationship between the items, and each agent's share must form a connected subgraph of this graph. This framework captures, e. g. , fair allocation of land plots, where the graph describes the accessibility relation among the plots. We focus on agents that have additive utilities for the items, and consider several common fair division solution concepts, such as proportionality, envy-freeness and maximin share guarantee. While finding good allocations according to these solution concepts is computationally hard in general, we design efficient algorithms for special cases wherethe underlying graph has simple structure, and/or the number of agents---or, less restrictively, the number of agent types---is small. In particular, despite non-existence results in the general case, we prove that for acyclic graphs a maximin share allocation always exists and can be found efficiently.

PDF Details

AAAI Conference 2017 Conference Paper

Group Activity Selection on Social Networks

  • Ayumi Igarashi
  • Dominik Peters
  • Edith Elkind

We propose a new variant of the group activity selection problem (GASP), where the agents are placed on a social network and activities can only be assigned to connected subgroups. We show that if multiple groups can simultaneously engage in the same activity, finding a stable outcome is easy as long as the network is acyclic. In contrast, if each activity can be assigned to a single group only, finding stable outcomes becomes intractable, even if the underlying network is very simple: the problem of determining whether a given instance of a GASP admits a Nash stable outcome turns out to be NPhard when the social network is a path, a star, or if the size of each connected component is bounded by a constant. On the other hand, we obtain fixed-parameter tractability results for this problem with respect to the number of activities.

PDF Details

AAMAS Conference 2017 Conference Paper

On Parameterized Complexity of Group Activity Selection Problems on Social Networks

  • Ayumi Igarashi
  • Robert Bredereck
  • Edith Elkind

In Group Activity Selection Problem with graph structure (gGASP), players form coalitions to participate in activities and have preferences over pairs of the form (activity, group size); moreover, a group of players can only engage in the same activity if the members of the group form a connected subset of the underlying communication structure. We study the parameterized complexity of finding outcomes of gGASP that are Nash stable, individually stable or core stable. For the parameter ‘number of activities’, we propose an FPT algorithm for Nash stability for the case where the social network is acyclic and obtain a W[1]-hardness result for cliques (i. e. , for classic GASP); similar results hold for individual stability. In contrast, finding a core stable outcome is hard even if the number of activities is bounded by a small constant, both for classic GASP and when the social network is a star. For the parameter ‘number of players’, all problems we consider are in XP for arbitrary social networks; on the other hand, we prove W[1]-hardness results with respect to the parameter ‘number of players’ for the case where the social network is a clique (i. e. , for classic GASP).

PDF

AAMAS Conference 2017 Conference Paper

Supermodular Games on Social Networks

  • Ayumi Igarashi

Cooperative games offer an elegant framework to model cooperation among self-interested agents. A central question of these games is how to distribute the payoff to each player when all players cooperate and derive some benefits. In this work, we consider cooperative transferable utility games where a subset of players can form a coalition if and only if they are connected in the underlying communication structure. We propose a relaxed notion of supermodularity, called quasi-supermodularity, for such games, and identify a class of networks where many of these problems are polynomial-time solvable for relaxed-supermodular games. We complement these results by showing that without supermodularity, these problems become hard even if the underlying graph is a tree.

PDF

AAMAS Conference 2016 Conference Paper

Hedonic Games with Graph-restricted Communication

  • Ayumi Igarashi
  • Edith Elkind

We study hedonic coalition formation games in which cooperation among the players is restricted by a graph structure: a subset of players can form a coalition if and only if they are connected in the given graph. We investigate the complexity of finding stable outcomes in such games, for several notions of stability. In particular, we provide an efficient algorithm that finds an individually stable partition for an arbitrary hedonic game on an acyclic graph. We also introduce a new stability concept—in-neighbor stability—which is tailored for our setting. We show that the problem of finding an inneighbor stable outcome admits a polynomial-time algorithm if the underlying graph is a path, but is NP-hard for arbitrary trees even for additively separable hedonic games; for symmetric additively separable games we obtain a PLS-hardness result. General Terms Algorithms, Economics, Theory

PDF
v2026.09.13