Ayumi Igarashi

Ayumi Igarashi

Auto-generated profile, based on publicly available information

Ayumi Igarashi

Department of Mathematical Informatics, The University of Tokyo, Tokyo 113-8656, Japan

Research Focus & Metrics

Academic Career Length

6Years (2021-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
9 November 2021 in Autonomous Agents and Multi-Agent Systems
Verified
Journal Article
Closed access
PDF file
HAHaris Aziz
Haris Aziz
ICIoannis Caragiannis
Ioannis Caragiannis
AIAyumi Igarashi
Ayumi Igarashi
TWToby Walsh
Toby Walsh

1 January 2022 in Games and Economic Behavior
Verified
Journal Article
Closed access
VBVittorio Bilò
Vittorio Bilò
ICIoannis Caragiannis
Ioannis Caragiannis
Michele FlamminiMichele Flammini
Michele Flammini
AIAyumi Igarashi
Ayumi Igarashi
Gianpiero MonacoGianpiero Monaco
Gianpiero Monaco
WZWilliam S. Zwicker
William S. Zwicker

11 January 2024 in Games and Economic Behavior
Verified
Journal Article
Closed access
HGHiromichi Goko
Hiromichi Goko
AIAyumi Igarashi
Ayumi Igarashi
YKYasushi Kawase
Yasushi Kawase
KMKazuhisa Makino
Kazuhisa Makino
HSHanna Sumita
Hanna Sumita
MYMakoto Yokoo
Makoto Yokoo

6 September 2024 in ACM Transactions on Economics and Computation
Verified
Journal Article
Open access
EEEdith Elkind
Edith Elkind
PFPiotr Faliszewski
Piotr Faliszewski
AIAyumi Igarashi
Ayumi Igarashi
PMPasin Manurangsi
Pasin Manurangsi
USUlrike Schmidt-Kraepelin
Ulrike Schmidt-Kraepelin
WSWarut Suksompong
Warut Suksompong
In multiwinner approval voting, the goal is to select a k -member committee 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 social welfare (the number of approvals obtained by committee members) or coverage (the number of voters who approve at least one committee member). In this article, we investigate the price of imposing the JR axiom (as well as the more demanding extended justified representation axiom) on social welfare and coverage. Our approach is twofold: We derive worst-case bounds on the loss of welfare/coverage caused by imposing JR and study the computational complexity of finding committees with high welfare that provide JR (obtaining hardness results, approximation algorithms, and an exact algorithm for one-dimensional preferences).

15 April 2023 in Mathematical Programming
Verified
Journal Article
Open access
PDF file
AIAyumi Igarashi
Ayumi Igarashi
WZWilliam S. Zwicker
William S. Zwicker
Fair division has been studied in both continuous and discrete contexts. One strand of the continuous literature seeks to award each agent with a single connected piece—a subinterval. The analogue for the discrete case corresponds to the fair division of a graph, where allocations must be contiguous so that each bundle of vertices is required to induce a connected subgraph. With envy-freeness up to one item (EF1) as the fairness criterion, however, positive results for three or more agents have mostly been limited to traceable graphs. We introduce tangles as a new context for fair division. A tangle is a more complicated cake—a connected topological space constructed by gluing together several copies of the unit interval [0, 1]—and each single tangle $$\mathcal {T}$$ T corresponds in a natural way to an infinite topological class $$\mathcal {G}(\mathcal {T})$$ G ( T ) of graphs, linking envy-free fair division of tangles to EFk fair division of graphs. In addition to the unit interval itself, we show that only five other stringable tangles guarantee the existence of envy-free and connected allocations for arbitrarily many agents, with the corresponding topological classes containing only traceable graphs. Any other tangle $$\mathcal {T}$$ T has a bound r on the number of agents for which such allocations necessarily exist, and our Negative Transfer Principle then applies to the graphs in $$\mathcal {T}$$ T ’s class; for any integer $$k \ge 1$$ k ≥ 1 , almost all graphs in this class are non-traceable and fail to guarantee EFk contiguous allocations for $$r + 1$$ r + 1 or more agents, even when very strict requirements are placed on the valuation functions for the agents. With bounds on the number of agents, however, we obtain positive results for some non-stringable classes. An elaboration of Stromquist’s moving knife procedure shows that the non-stringable lips tangle $$\mathcal {L}$$ L guarantees envy-free allocations of connected shares for three agents. We then modify the discrete version of Stromquist’s procedure in Bilò et al. (Games Econ Behav 131:197–221, 2022) to show that all graphs in the topological class $$\mathcal {G}(\mathcal {L})$$ G ( L ) (most of which are non-traceable) guarantee EF1 allocations for three agents.

1 August 2025 in Mathematics of Operations Research
Verified
Journal Article
Closed access
AIAyumi Igarashi
Ayumi Igarashi
FMFrédéric Meunier
Frédéric Meunier
Dividing a multilayered cake under nonoverlapping constraints captures several scenarios (e.g., allocating multiple facilities over time where each agent can utilize at most one facility simultaneously). We establish the existence of an envy-free multidivision that is nonoverlapping and contiguous within each layer when the number of agents is a prime power, solving partially an open question by Hosseini et al. [Hosseini H, Igarashi A, Searns A (2020) Fair division of time: Multi-layered cake cutting. Proc. 29th Internat. Joint Conf. Artificial Intelligence (IJCAI), 182–188; Hosseini H, Igarashi A, Searns A (2020) Fair division of time: Multi-layered cake cutting. Preprint, submitted April 28, http://arxiv.org/abs/2004.13397 ]. Our approach follows an idea proposed by Jojić et al. [Jojić D, Panina G, Živaljević R (2021) Splitting necklaces, with constraints. SIAM J. Discrete Math. 35(2):1268–1286] for envy-free divisions, relying on a general fixed-point theorem. We further design a fully polynomial-time approximation scheme for the two-layer, three-agent case, with monotone preferences. All results are actually established for divisions among groups of almost the same size. In the one-layer, three-group case, our algorithm is able to deal with any predetermined sizes, still with monotone preferences. For three groups, this provides an algorithmic version of a recent theorem by Segal-Halevi and Suksompong [Segal-Halevi E, Suksompong W (2021) How to cut a cake fairly: A generalization to groups. Amer. Math. Monthly 128(1):79–83]. Funding: This work was partially supported by the Japan Science and Technology Agency [Grant JPMJPR20C], Fusion Oriented REsearch for disruptive Science and Technology [Grant JPMJFR226O], and Exploratory Research for Advanced Technology [Grant JPMJER2301].