Authorship：Lead author,　Last author,　Corresponding author   Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ijcai.org  

In daycare matching problems, complementarities in siblings' preferences can lead to the nonexistence of stable matchings. A similar issue arises in hospital-resident markets with couples, where stability is not guaranteed in theory but often observed in practice when the couple rate is low (e.g., 5%). Yet, these results do not explain why stable matchings are consistently observed in daycare markets, despite a much higher share of sibling applicants (around 20%). To understand this phenomenon, we analyze large random matching markets in which daycare centers have similar priority structures, a common feature in practice. Our analysis reveals that as the market size approaches infinity, the likelihood of stable matchings existing converges to 1. To facilitate our exploration, we refine an existing heuristic algorithm to address a more rigorous stability concept, as the original one may fail to meet this criterion. Through extensive experiments on both real-world and synthetic datasets, we demonstrate the effectiveness of our revised algorithm in identifying stable matchings, particularly when daycare priorities exhibit high similarity.

DOI： 10.24963/ijcai.2025/453

Scopus

researchmap

Other Link： https://dblp.org/db/conf/ijcai/ijcai2025.html#0001YY25

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：AAAI Press  

We study a practical two-sided matching problem of allocating children to daycare centers, which has significant social implications. We are cooperating with several municipalities in Japan and our goal is to devise a reliable and trustworthy clearing algorithm to deal with the problem. In this paper, we describe the design of our new algorithm that minimizes the number of unmatched children while ensuring stability. We evaluate our algorithm using real-life data sets, and experimental results demonstrate that our algorithm surpasses the commercial software that currently dominates the market in terms of both the number of matched children and the number of blocking coalitions (measuring stability). Our findings have been reported to local governments, and some are considering adopting our proposed algorithm in the near future, instead of the existing solution. Moreover, our model and algorithm have broader applicability to other important matching markets, such as hospital-doctor matching with couples and school choice with siblings.

DOI： 10.1609/aaai.v38i20.30244

Scopus

researchmap

Other Link： https://dblp.org/db/conf/aaai/aaai2024.html#0001YTMY24

Language：English   Publishing type：Research paper (scientific journal)  

Authorship：Lead author,　Last author,　Corresponding author   Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Authorship：Lead author   Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：AAAI Press  

In this paper, we study a daycare matching problem in Japan and report the design and implementation of a new centralized algorithm. There are two features that make this market different from the classical hospital-doctor matching problem: i) some children are initially enrolled and prefer to be transferred to other daycare centers; ii) one family may be associated with two or more children and is allowed to submit preferences over combinations of daycare centers. We revisit some well-studied properties including individual rationality, non-wastefulness, as well as stability, and generalize them to this new setting. We design an algorithm based on integer programming (IP) that captures these properties and conduct experiments on five real-life data sets provided by three municipalities. Experimental results show that i) our algorithm performs at least as well as currently used methods in terms of numbers of matched children and blocking coalition; ii) we can find a stable outcome for all instances, although the existence of such an outcome is not guaranteed in theory.

DOI： 10.1609/aaai.v37i12.26694

Scopus

researchmap

Other Link： https://dblp.org/db/conf/aaai/aaai2023.html#0001TMTY23

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：AAAI Press  

We study a fair allocation problem of indivisible items under additive externalities in which each agent also receives utility from items that are assigned to other agents. This allows us to capture scenarios in which agents benefit from or compete against one another. We extend the well-studied properties of envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) to this setting, and we propose a new fairness concept called general fair share (GFS), which applies to a more general public decision making model. We undertake a detailed study and present algorithms for finding fair allocations.

DOI： 10.1609/aaai.v37i5.25680

Scopus

researchmap

Other Link： https://dblp.org/db/conf/aaai/aaai2023.html#0001S0W23

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Aamas 2026 Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems  

This paper studies cooperative games where coalitions are formed online and the value generated by the grand coalition must be irrevocably distributed among the players at each time step. We investigate the fundamental issue of strategic participation incentives and address these concerns by formalizing participation incentive axioms. Our analysis reveals that existing value-sharing mechanisms fail to meet these criteria. Consequently, we propose a family of equal sharing rules that fulfill these desirable participation incentive axioms. Additionally, we refine our mechanisms under superadditive valuations to ensure individual rationality while preserving the previously established axioms.

DOI： 10.65109/VZOJ2040

Scopus

Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

<p>本研究では，学生と学校の両方向マッチング問題に対し，耐戦略性を保証しつつ社会的厚生および定員違反の改善を目的とした，ニューラルネットワークを用いたメニューメカニズムを提案する．提案手法は，各学生に対する学校ごとの受容強度をニューラルネットワークにより出力し，その値に基づき確率的割当を行う．また，定員制約および市場全体の予備枠を考慮した損失関数の最小化により学習を行う．数値実験を通して，社会的厚生，定員制約のトレードオフについて分析した．</p>

DOI： 10.11517/pjsai.jsai2026.0_2yina35

CiNii Research

Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

<p>In this paper, we study two-sided matching under hereditary constraints, which is applicable to problems such as diversity requirements and refugee resettlement. In these settings, a fair and non-wasteful matching may not always exist. To address this incompatibility, a common approach is to balance fairness and non-wastefulness by fully satisfying one while partially relaxing the other. We take a different approach by relaxing both properties simultaneously. We introduce College-Envy-Freeness up to k students (CEF-k) as a relaxed notion of fairness, and Vacant-seat Claim up to l colleges (VC-l) as a relaxed notion of non-wastefulness. We provide a mechanism that satisfies both CEF-k and strategy-proofness (SP). Furthermore, we show that, in a matching market with n students and n schools, for some values of k, the proposed strategy-proof mechanism simultaneously satisfies CEF-k and VC-(n-k-1).</p>

DOI： 10.11517/pjsai.jsai2026.0_2yinb24

CiNii Research

Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

<p>In this paper, we study a two-sided matching problem that arises in the allocation of scarce healthcare resources, such as vaccine distribution. In healthcare rationing, reserve systems are used to reflect multiple priority orders, and a variety of allocation rules have been proposed within theoretical frameworks for analyzing such systems. However, although several allocation rules have been introduced, the relationships among the axioms they satisfy have not been sufficiently organized. To address this gap, we focus on these allocation rules and systematically summarize and compare their objectives and properties. In addition, for properties whose validity has not been clearly established in the existing literature, we provide rigorous definitions and examine whether each rule satisfies them. We present proofs when a property holds and construct counterexamples when it does not, thereby clarifying the limitations and scope of applicability of each rule. This allows us to precisely characterize differences in properties across allocation rules and to make meaningful comparisons among them. Through this organization and verification, we aim to clarify the trade-offs involved in mechanism design for healthcare resource allocation and to provide a foundational basis for future institutional design and theoretical research.</p>

DOI： 10.11517/pjsai.jsai2026.0_4l5gs1b02

CiNii Research

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Autonomous Agents and Multi Agent Systems  

The theory of two-sided matching has been extensively developed and applied to many real-life application domains. As the theory has been applied to increasingly diverse types of environments, researchers and practitioners have encountered various forms of distributional constraints. Arguably, the most general class of distributional constraints would be hereditary constraints; if a matching is feasible, then any matching that assigns weakly fewer students at each college is also feasible. However, under general hereditary constraints, it is shown that no strategyproof mechanism exists that simultaneously satisfies fairness and weak nonwastefulness, which is an efficiency (students’ welfare) requirement weaker than nonwastefulness. We propose a new strategyproof mechanism that works for hereditary constraints called the Multi-Stage Generalized Deferred Acceptance mechanism (MS-GDA). It uses the Generalized Deferred Acceptance mechanism (GDA) as a subroutine, which works when distributional constraints belong to a well-behaved class called hereditary M-convex set. We show that GDA satisfies several desirable properties, most of which are also preserved in MS-GDA. We experimentally show that MS-GDA strikes a good balance between fairness and efficiency (students’ welfare) compared to existing strategyproof mechanisms when distributional constraints are close to an M-convex set^*.

DOI： 10.1007/s10458-025-09713-9

Web of Science

Scopus

researchmap

Authorship：Lead author   Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Frontiers in Artificial Intelligence and Applications  

In this work, we examine a sequential setting of a cooperative game in which players arrive dynamically to form coalitions and complete tasks either together or individually, depending on the value created. Upon arrival, a new player as a decision maker faces two options: forming a new coalition or joining an existing one. We assume that players are greedy, i.e., they aim to maximize their rewards based on the information available at their arrival. The objective is to design an online value distribution policy that incentivizes players to form a coalition structure that maximizes social welfare. We focus on monotone and bounded cooperative games. Our main result establishes an upper bound of 3min/max on the competitive ratio for any irrevocable policy (i.e., one without redistribution), and proposes a policy that achieves a near-optimal competitive ratio of min{1/2, 3min/max}, where min and max denote the smallest and largest marginal contribution of any sub-coalition of players respectively. Finally, we also consider non-irrevocable policies, with alternative bounds only when the number of players is limited.

DOI： 10.3233/FAIA250949

Web of Science

Scopus

researchmap

Other Link： https://dblp.org/db/conf/ecai/ecai2025.html#ZhangS0Y25

Publisher：Proceedings of the Aaai Conference on Artificial Intelligence  

Student placements under diversity constraints are a common practice globally. This paper addresses the selection of students by a single school under a \emph{one-to-one convention}, where students can belong to multiple types but are counted only once based on one type. While existing algorithms in economics and computer science aim to help schools meet diversity goals and priorities, we demonstrate that these methods can result in significant imbalances among students with different type combinations.

To address this issue, we introduce a new property called \emph{balanced representation}, which ensures fair representation across all types and type combinations. We propose a straightforward choice function that uniquely satisfies four fundamental properties: maximal diversity, non-wastefulness, justified envy-freeness, and balanced representation. While previous research has primarily focused on algorithms based on bipartite graphs, we take a different approach by utilizing flow networks. This method provides a more compact formalization of the problem and significantly improves computational efficiency. Additionally, we present efficient algorithms for implementing our choice function within both the bipartite graph and flow network frameworks.

DOI： 10.1609/aaai.v39i13.33547

Scopus

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Cornell University  

We explore solutions for fairly allocating indivisible items among agents assigned weights representing their entitlements. Our fairness goal is weighted-envy-freeness (WEF), where each agent deems their allocated portion relative to their entitlement at least as favorable as any other’s relative to their own. Often, achieving WEF necessi- tates monetary transfers, which can be modeled as third-party subsidies. The goal is to attain WEF with bounded subsidies. / Previous work relied on characterizations of unweighted envy-freeness (EF), that fail in the weighted setting. This makes our new setting challenging. We present polynomial-time algorithms that compute WEF allocations with a guaranteed upper bound on total subsidy for monotone valuations and various subclasses thereof. / We also present an efficient algorithm to compute a fair allocation of items and money, when the budget is not enough to make the allocation WEF. This algorithm is new even for the unweighted setting

CiNii Research

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

<p>In this paper, we study a two-sided matching problem under regional quotas, with a particular focus on hospital-residency matching in Japan. It is well-established that when regional caps are imposed, a fair and non-wasteful matching may not always exist. To overcome this incompatibility, a common approach is to balance fairness and efficiency by fully satisfying one while partially relaxing the other. To address this challenge, we introduce the concepts of weaker fairness (EF-k, REF-k, SEF-k) and weaker efficiency (NW-l). Using constraint programming (CP), we propose algorithms that either satisfy non-wastefulness and relaxed fairness or fairness and relaxed non-wastefulness. Through evaluation experiments, we find that REF-k achieves the highest level of fairness when paired with CP under non-wastefulness constraints. We also compare the performance of CP-based approaches with constrained fairness and NW-l against existing fairness mechanisms, FDA and PLDA. Our results show that CP outperforms FDA while achieving comparable performance to PLDA.</p>

DOI： 10.11517/pjsai.jsai2025.0_2j5gs503

CiNii Research

Web of Science

Publishing type：Research paper (international conference proceedings)   Publisher：International Foundation for Autonomous Agents and Multiagent Systems / ACM  

researchmap

Other Link： https://dblp.org/rec/conf/ifaamas/2025

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems Aamas  

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.

Scopus

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS  

The theory of two-sided matching has been extensively developed and applied to many real-life application domains. As the theory has been applied to increasingly diverse types of environments, researchers and practitioners have encountered various forms of distributional constraints. As a mechanism can handle a more general class of constraints, we can assign students more flexibly to colleges to increase students' welfare. However, it turns out that there exists a trade-off between students' welfare (efficiency) and fairness (which means no student has justified envy). Furthermore, this trade-off becomes sharper as the class of constraints becomes more general. The first contribution of this paper is to clarify the boundary on whether a strategyproof and fair mechanism can satisfy certain efficiency properties for each class of constraints. Our second contribution is to establish a weaker fairness requirement called envy-freeness up to k peers (EF-k), which is inspired by a similar concept used in the fair division of indivisible items. EF-k guarantees that each student has justified envy towards at most k students. By varying k, EF-k can represent different levels of fairness. We investigate theoretical properties associated with EF-k. Furthermore, we develop two contrasting strategyproof mechanisms that work for general hereditary constraints, i.e., one mechanism can guarantee a strong efficiency requirement, while the other can guarantee EF-k for any fixed k. We evaluate the performance of these mechanisms through computer simulation.

Scopus

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)   Publisher：The Japanese Society for Artificial Intelligence  

<p>The theory of two-sided matching has been extensively developed, and it is hoped that matching will reduce students' envies and improve overall welfare. However, it turns out that there exists a trade-off between efficiency and fairness. Therefore, keeping fairness at a certain level that can be applied in the real world also leads to increased efficiency. Our contribution is to establish a weaker fairness requirement called reverse Envy-Freeness from up to k peers (r-EF-k). r-EF-k requires that each student is envied by at most k students. By varying k, r-EF-k can represent different levels of fairness. We discuss mechanism that satisfy r-EF-k and certain efficiency properties.</p>

DOI： 10.11517/pjsai.jsai2024.0_2f6gs501

CiNii Research

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)   Publisher：The Japanese Society for Artificial Intelligence  

<p>In this paper, we explore a two-period matching problem in which agents' preferences may evolve over time. This model enables agents to be matched with different partners over the two periods. Previous research defines dynamic stability as the absence of any single agent or pair of agents gaining an advantage through coalition across any period. We introduce new fairness, nonwastefulness and individually rationality notions tailored for the two-period matching setting and examine its relationship with dynamic stability. We also discuss the existence of matching that simultaneously satisfies the newly introduced fairness and nonwastefulness properties.</p>

DOI： 10.11517/pjsai.jsai2024.0_1i3gs501

CiNii Research

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：International Foundation for Autonomous Agents and Multiagent Systems / ACM  

researchmap

Other Link： https://dblp.org/rec/conf/atal/2024

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS  

Selection under category or diversity constraints is a ubiquitous and widely-applicable problem that is encountered in immigration, school choice, hiring, and healthcare rationing. These diversity constraints are typically represented by minimum and maximum quotas on various categories or types. We undertake a detailed comparative study of applicant selection algorithms with respect to the diversity goals.

Scopus

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ACM  

researchmap

Other Link： https://dblp.org/rec/conf/atal/2023

Language：English  

Language：English  

Language：English  

Language：English  

Language：English  

Language：English  

Language：English  

Language：English