Yuko Sakurai

AAAI Conference 2026 Short Paper

Behavioral-Similarity and Clustering-Based Methods for Static Graph Estimation in Hybrid GNNs (Student Abstract)

• Ryusei Otani
• Keichi Namikoshi
• Yuko Sakurai
• Mingyu Guo
• Satoshi Oyama

In this study, we propose two methods to estimate static graphs from a single dynamic graph and integrate them into hybrid Graph Neural Networks (GNNs), which combine long-term static structure with transient dynamic interactions. Since static graphs are often unavailable and attributes may be difficult to use at scale or under privacy constraints, we introduce: (i) a “behavioral similarity” estimator based on normalized co-occurrence, which requires no attributes, and (ii) an attribute-aware K-means + k-NN estimator that is more efficient than cosine similarity. Experiments on multiple real-world datasets show that both methods consistently improve predictive accuracy and training efficiency, underscoring the importance of static graph choice in hybrid GNNs.

AAAI Conference 2026 Short Paper

Social Influence-Based Mutual Acknowledgement Token Exchange (Student Abstract)

• Shoma Mizuno
• Keichi Namikoshi
• Yuko Sakurai

External incentive mechanisms have been studied as a method to promote cooperation in sequential social dilemmas involving multiple autonomous agents. Mutual Acknowledgment Token Exchange (MATE) is one such approach: by enabling agents to exchange acknowledgment tokens, it induces cooperation without additional training. However, MATE’s use of fixed, manually tuned token values limits adaptability to nonstationary environments and can constrain performance. To enable a dynamically adapted token, we introduce Social Influence-based MATE (SI-MATE), which allows agents to share their individual improvement signals and to self-punishment in response to inequality. Experiments in a four-agent environment show that SI-MATE outperforms MATE across multiple metrics, including learning speed.

AAAI Conference 2025 Short Paper

Counterfactual Explanations of Time Varying Rankings (Student Abstract)

• Ryusei Ohtani
• Yuko Sakurai
• Satoshi Oyama

Counterfactual explanations in Explainable AI (XAI) identify which features to change to alter an outcome, but existing methods adjust only the features of a single agent. We present a new approach to re-evaluating rankings that is based on predictions of future features of the other agents in a ranking system. It uses an algorithm that provides a more realistic counterfactual explanation of changing the ranking of a particular agent. Computer experiments demonstrated that the proposed algorithm can capture the time variation of the entire ranking system in the inference results.

AIJ Journal 2022 Journal Article

Measuring power in coalitional games with friends, enemies and allies

• Oskar Skibski
• Takamasa Suzuki
• Tomasz Grabowski
• Yuko Sakurai
• Tomasz Michalak
• Makoto Yokoo

JAAMAS Journal 2021 Journal Article

Gini index based initial coin offering mechanism

• Mingyu Guo
• Zhenghui Wang
• Yuko Sakurai

Abstract As a fundraising method, Initial Coin Offering (ICO) has raised billions of dollars for thousands of startups. Existing ICO mechanisms place more emphasis on the short-term benefits of maximal fundraising while ignoring the problem of unbalanced token allocation, which negatively impacts subsequent fundraising and has bad effects on introducing new investors and resources. We propose a new ICO mechanism which uses the concept of Gini index for the very first time as a mechanism design constraint to control allocation inequality. Our mechanism has an elegant and straightforward structure, which makes it explainable. It allows the agents to modify their bids as a price discovery process, while limiting the bids of whales. Under natural technical assumptions, we show that under our mechanism most agents have simple dominant strategies and the equilibrium revenue approaches the optimal revenue asymptotically in the number of agents. We verify our mechanism using real ICO dataset we collected, and confirm that our mechanism performs well in terms of both allocation fairness and revenue.

AAMAS Conference 2021 Conference Paper

Mechanism Design for Public Projects via Neural Networks

• Guanhua Wang
• Runqi Guo
• Yuko Sakurai
• Muhammad Ali Babar
• Mingyu Guo

We study mechanism design for nonexcludable and excludable binary public project problems. We aim to maximize the expected number of consumers and the expected agents’ welfare. For the nonexcludable public project model, we identify a sufficient condition on the prior distribution for the conservative equal costs mechanism to be the optimal strategy-proof and individually rational mechanism. For general distributions, we propose a dynamic program that solves for the optimal mechanism. For the excludable public project model, we identify a similar sufficient condition for the serial cost sharing mechanism to be optimal for 2 and 3 agents. We derive a numerical upper bound. Experiments show that for several common distributions, the serial cost sharing mechanism is close to optimality. The serial cost sharing mechanism is not optimal in general. We design better performing mechanisms via neural networks. Our approach involves several technical innovations that can be applied to mechanism design in general. We interpret the mechanisms as price-oriented rationing-free (PORF) mechanisms, which enables us to move the mechanism’s complex (e. g. , iterative) decision making off the neural network, to a separate simulation process. We feed the prior distribution’s analytical form into the cost function to provide high-quality gradients for efficient training. We use supervision to manual mechanisms as a systematic way for initialization. Our approach of “supervision and then gradient descent” is effective for improving manual mechanisms’ performances. It is also effective for fixing constraint violations for heuristic-based mechanisms that are infeasible.

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.

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.

AAAI Conference 2019 Conference Paper

Unknown Agents in Friends Oriented Hedonic Games: Stability and Complexity

• Nathanaël Barrot
• Kazunori Ota
• Yuko Sakurai
• Makoto Yokoo

We study hedonic games under friends appreciation, where each agent considers other agents friends, enemies, or unknown agents. Although existing work assumed that unknown agents have no impact on an agent’s preference, it may be that her preference depends on the number of unknown agents in her coalition. We extend the existing preference, friends appreciation, by proposing two alternative attitudes toward unknown agents, extraversion and introversion, depending on whether unknown agents have a slightly positive or negative impact on preference. When each agent prefers coalitions with more unknown agents, we show that both core stable outcomes and individually stable outcomes may not exist. We also prove that deciding the existence of the core and the existence of an individual stable coalition structure are respectively NPNP -complete and NP-complete.

AAAI Conference 2017 Short Paper

Coalition Structure Generation Utilizing Graphical Representation of Partition Function Games

• Kazuki Nomoto
• Yuko Sakurai
• Makoto Yokoo

Forming effective coalition is a central research challenge in AI and multi-agent systems. The Coalition Structure Generation (CSG) problem is well-known as one of major research topics in coalitional games. The CSG problem is to partition a set of agents into coalitions so that the sum of utilities is maximized. This paper studies a CSG problem for partition function games (PFGs), where the value of a coalition differs depending on the formation of other coalitions generated by non-member agents. Traditionally, in PFGs, the input of a coalitional game is a black-box function called a partition function that maps an embedded coalition (a coalition and the coalition structure) to its value. Recently, a novel concise representation scheme called the Partition Decision Trees (PDTs) has been proposed. The PDTs is a graphical representation based on multiple rules. In this paper, we propose new algorithms that can solve a CSG problem by utilizing PDTs representation. More specifically, we modify PDTs representation to effectively handle negative value rules and apply the depth-first branch and bound algorithm. We experimentally show that our algorithm can solve a CSG problem well.

IJCAI Conference 2017 Conference Paper

Core Stability in Hedonic Games among Friends and Enemies: Impact of Neutrals

• Kazunori Ohta
• Nathanaël Barrot
• Anisse Ismaili
• Yuko Sakurai
• Makoto Yokoo

We investigate hedonic games under enemies aversion and friends appreciation, where every agent considers other agents as either a friend or an enemy. We extend these simple preferences by allowing each agent to also consider other agents to be neutral. Neutrals have no impact on her preference, as in a graphical hedonic game. Surprisingly, we discover that neutral agents do not simplify matters, but cause complexity. We prove that the core can be empty under enemies aversion and the strict core can be empty under friends appreciation. Furthermore, we show that under both preferences, deciding whether the strict core is non-empty, is NP^NP-complete. This complexity extends to the core under enemies aversion. We also show that under friends appreciation, we can always find a core stable coalition structure in polynomial time.

AAAI Conference 2015 Conference Paper

A Graphical Representation for Games in Partition Function Form

• Oskar Skibski
• Tomasz Michalak
• Yuko Sakurai
• Michael Wooldridge
• Makoto Yokoo

We propose a novel representation for coalitional games with externalities, called Partition Decision Trees. This representation is based on rooted directed trees, where non-leaf nodes are labelled with agents’ names, leaf nodes are labelled with payoff vectors, and edges indicate membership of agents in coalitions. We show that this representation is fully expressive, and for certain classes of games significantly more concise than an extensive representation. Most importantly, Partition Decision Trees are the first formalism in the literature under which most of the direct extensions of the Shapley value to games with externalities can be computed in polynomial time.

IJCAI Conference 2015 Conference Paper

A Pseudo-Polynomial Algorithm for Computing Power Indices in Graph-Restricted Weighted Voting Games

• Oskar Skibski
• Tomasz P. Michalak
• Yuko Sakurai
• Makoto Yokoo

Weighted voting games allow for studying the distribution of power between agents in situations of collective decision making. While the conventional version of these games assumes that any agent is always ready to cooperate with all others, recently, more involved models have been proposed, where cooperation is subject to restrictions. Following Myerson [1977], such restrictions are typically represented by a graph that expresses available communication links among agents. In this paper, we study the time complexity of computing two well-known power indices – the Shapley-Shubik index and the Banzhaf index – in the graph-restricted weighted voting games. We show that both are #P-complete and propose a dedicated dynamic-programming algorithm that runs in pseudo-polynomial time for graphs with the bounded treewidth.

IJCAI Conference 2013 Conference Paper

Accurate Integration of Crowdsourced Labels Using Workers' Self-Reported Confidence Scores

• Satoshi Oyama
• Yukino Baba
• Yuko Sakurai
• Hisashi Kashima

We have developed a method for using confidence scores to integrate labels provided by crowdsourcing workers. Although confidence scores can be useful information for estimating the quality of the provided labels, a way to effectively incorporate them into the integration process has not been established. Moreover, some workers are overconfident about the quality of their labels while others are underconfident, and some workers are quite accurate in judging the quality of their labels. This differing reliability of the confidence scores among workers means that the probability distributions for the reported confidence scores differ among workers. To address this problem, we extended the Dawid-Skene model and created two probabilistic models in which the values of unobserved true labels are inferred from the observed provided labels and reported confidence scores by using the expectation-maximization algorithm. Results of experiments using actual crowdsourced data for image labeling and binary question answering tasks showed that incorporating workers’ confidence scores can improve the accuracy of integrated crowdsourced labels.

AAMAS Conference 2013 Conference Paper

Quality-Control Mechanism Utilizing Worker's Confidence for Crowdsourced Tasks

• Yuko Sakurai
• Tenda Okimoto
• Masaaki Oka
• Masato Shinoda
• Maokoto Yokoo

We propose a quality control mechanism that utilizes workers’ self-reported confidences in crowdsourced labeling tasks. Generally, a worker has confidence in the correctness of her answers, and asking about it is useful for estimating the probability of correctness. However, we need to overcome two main obstacles in order to to use confidence for inferring correct answers. First, a worker is not always wellcalibrated. Since she is sometimes over/underconfident, her level of confidence does not always accurately reflect the probability of correctness. In addition, she does not always truthfully report her actual confidence. Therefore, we design an indirect mechanism that enables a worker to declare her confidence by choosing a desirable reward plan from the set of plans that correspond to different confidence intervals. Our mechanism ensures that choosing the plan matching the worker’s true confidence maximizes her expected utility.

AAMAS Conference 2010 Conference Paper

Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms

• Atsushi Iwasaki
• Vincent Conitzer
• Yoshifusa Omori
• Yuko Sakurai
• Taiki Todo
• Mingyu Guo
• Makoto Yokoo

This paper analyzes the worst-case efficiency ratio of false-name-proofcombinatorial auction mechanisms. False-name-proofness generalizesstrategy-proofness, by assuming that a bidder can submit multiple bidsunder fictitious identifiers. Even the well-known Vickrey-Clarke-Grovesmechanism is not false-name-proof. It has previously been shown thatthere is no false-name-proof mechanism that always achieves a Paretoefficient allocation. Hence, if false-name bids are possible, we need to sacrifice efficiency to some extent. This leaves the natural question of how much surplusmust be sacrificed. To answer this question, this paper focuses on worst-case analysis. Specifically, we consider thefraction of the Pareto-efficient surplus that we obtain, and try tomaximize this fraction in the worst case, under the constraint offalse-name-proofness. As far as we are aware, this is the first attempt to examine theworst-case efficiency of false-name-proof mechanisms. We show that the worst-case efficiency ratio of any false-name-proofmechanism that satisfies some apparently minor assumptions is atmost $2/(m+1)$ for auctions with $m$ different goods. We also observe that the worst-case efficiency ratioof existing false-name-proof mechanisms is generally $1/m$ or 0. Finally, we propose a novel mechanism, called the adaptive reserve price mechanism, which is false-name-proof when all bidders are single-minded, and its worst-case efficiency ratio is $2/(m+1)$, i. e. , optimal.

AAMAS Conference 2009 Conference Paper

Characterizing False-name-proof Allocation Rules in Combinatorial Auctions

• Taiki Todo
• Atsushi Iwasaki
• Makoto Yokoo
• Yuko Sakurai

A combinatorial auction mechanism consists of an allocation rule that defines the allocation of goods for each agent, and a payment rule that defines the payment of each winner. There have been several studies on characterizing strategyproof allocation rules. In particular, a condition called weakmonotonicity has been identified as a full characterization of strategy-proof allocation rules. More specifically, for an allocation rule, there exists an appropriate payment rule so that the mechanism becomes strategy-proof if and only if it satisfies weak-monotonicity. In this paper, we identify a condition called sub-additivity which characterizes false-name-proof allocation rules. Falsename-proofness generalizes strategy-proofness, by assuming that a bidder can submit multiple bids under fictitious identifiers. As far as the authors are aware, this is the first attempt to characterize false-name-proof allocation rules. We can utilize this characterization for developing a new false-name-proof mechanism, since we can concentrate on designing an allocation rule. As long as the allocation rule satisfies weak-monotonicity and sub-additivity, there always exists an appropriate payment rule. Furthermore, by utilizing the sub-additivity condition, we can easily verify whether a mechanism is false-name-proof. To our surprise, we found that two mechanisms, which were believed to be false-nameproof, do not satisfy sub-additivity; they are not false-nameproof. As demonstrated in these examples, our characterization is quite useful for mechanism verification.

AAMAS Conference 2008 Conference Paper

Beyond quasi-linear utility: strategy/false-name-proof multi-unit auction protocols

• Yuko Sakurai
• Yasumasa Saito
• Atsushi Iwasaki
• Makoto Yokoo

We develop strategy/false-name-proof multi-unit auction protocols that can handle non-quasi-linear utilities. One almost universal assumption in auction theory literature is that each bidder has quasi-linear utility, except for some works on budget-constrained bidders. In particular, the celebrated VCG protocol is strongly believed to critically depend on the quasi-linear assumption and will break down if this assumption does not hold. We show that with a simple modification, the VCG can handle non-quasi-linear utilities by sacrificing efficiency to a certain extent. The basic idea of this modification is that tentative allocation and payments are determined assuming quasi-linear utilities, but each bidder can choose the actual number of units to obtain based on his non-quasi-linear utility. The modified VCG only uses the gross utility of each bidder. Requiring gross utilities only is an advantage since collecting the entire utility function can be costly. However, determining tentative allocation and payments without considering actual non-quasi-linear utilities can cause significant efficiency loss. Furthermore, the VCG is not robust against false-name-proof. Thus, we propose a new false-name-proof open ascending auction protocol in which each bidder declares his demand for a series of prices. This protocol can improve efficiency without collecting entire utility functions.

AAMAS Conference 2003 Conference Paper

A False-name-Proof Double Auction Protocol for Arbitrary Evaluation Values

• Yuko Sakurai
• Makoto Yokoo

AAMAS Conference 2002 Conference Paper

An Average-case Budget-Non-Negative Double Auction Protocol

• Yuko Sakurai
• Makoto Yokoo

UAI Conference 2001 Conference Paper

A Dynamic Programming Model for Determining Bidding Strategies in Sequential Auctions: Quasi-linear Utility and Budget Constraints

• Hiromitsu Hattori
• Makoto Yokoo
• Yuko Sakurai
• Toramatsu Shintani

In this paper, we develop a new method for finding an optimal biddingstrategy in sequential auctions, using a dynamic programming technique. Theexisting method assumes that the utility of a user is represented in anadditive form. Thus, the remaining endowment of money must be explicitlyrepresented in each state, and the calculation of the optimal biddingstrategy becomes time-consuming when the initial endowment of money mbecomes large.In this paper, we develop a new problem formalization that avoids explicitlyrepresenting the remaining endowment, by assuming the utility of a user canbe represented in a quasi-linear form, and representing the payment as astate-transition cost. Experimental evaluations show that we can obtainmore than an m-fold speed-up in the computation time. Furthermore, we havedeveloped a method for obtaining a semi-optimal bidding strategy underbudget constraints, and have experimentally confirmed the efficacy of thismethod.

AIJ Journal 2001 Journal Article

Robust combinatorial auction protocol against false-name bids

• Makoto Yokoo
• Yuko Sakurai
• Shigeo Matsubara

AAAI Conference 1999 Conference Paper

A Limitation of the Generalized Vickrey Auction in Electronic Commerce: Robustness against False-Name Bids

• Yuko Sakurai
• Makoto Yokoo
• Shigeo Matsubara
• NTT Communication Science Laboratories

Electronic Commerce (EC) has rapidly grownwith the expansion of the Internet. Among these activities, auctionshaverecently achievedhugepopularity, andhavebecome a promisingfield for applyingagent andArtificial Intelligence technologies. Although the Internet provides an infrastructure for much cheaper auctioning with manymoresellers and buyers, we mustconsider the possibility of a newtype of cheating, i. e. , an agenttries to get some profit bysubmitting several bids underfictitious names (false-namebids). Althoughfalse-namebids are easier to execute than forming collusion, the vulnerability of auction protocols to false-namebids has not beendiscussedbefore. In this paper, weexaminethe robustness of the generalized Vickreyauction (G. V. A.)against false-name bids. TheG. V. A. has the best theoretical background among various auction mechanisms, i. e. , it has proved to be incentive compatibleand be able to achieve a Pareto efficient allocation. Weshowthat false-name bids maybe effective, i. e. , the G. V. A. loses incentive compatibilityunderthe possibility of false-namebids, when the marginal utility of an itemincreasesor goods are complementary. Moreover, weprove that there exists nosingle-roundsealed-bid auction protocol that simultaneously satisfies individualrationality, Pareto efficiency, andincentivecompatibilityin all cases if agents can submitfalse-namebids.