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.

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.

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.

Abstract We study mechanism design for nonexcludable and excludable binary public project problems. Our aim is to maximize the expected number of consumers and the expected agents’ welfare. We first show that for the nonexcludable public project model, there is no need for machine learning based mechanism design. We identify a sufficient condition on the prior distribution for the existing 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 existing serial cost sharing mechanism to be optimal for 2 and 3 agents. We derive a numerical upper bound and use it to 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 propose three machine learning based approaches for designing better performing mechanisms. We focus on the family of largest unanimous mechanisms , which characterizes all strategy-proof and individually rational mechanisms for the excludable public project model. A largest unanimous mechanism describes an iterative mechanism, which is defined by an exponential number of mechanism parameters. Our first approach describes the largest unanimous mechanism family using a neural network and training is carried out by minimizing a cost function that combines the mechanism design objective and the constraint violation penalty. We interpret the largest unanimous mechanisms as price-oriented rationing-free (PORF) mechanisms, which enables us to move the mechanisms’ iterative decision making off the neural network, to a separate simulation process, therefore avoiding the vanishing gradient problem. We also feed the prior distribution’s analytical form into the cost function to achieve high-quality gradients for efficient training. Our second approach treats the mechanism design task as a Markov Decision Process with an exponential number of states. During the Markov decision process, the non-consumers are gradually removed from the system. We train multiple neural networks, each for a different number of remaining agents, to learn the optimal value function on the states. Training is carried out by supervised learning toward a set of manually prepared base cases and the Bellman equation. Our third approach is based on reinforcement learning for a Partially Observable Markov Decision Process . Each RL episode randomly draws a type profile, which is hidden from the RL agent (mechanism designer). The RL agent only observes which cost share offers have been accepted under the largest unanimous mechanism under discussion. We use a continuous action space reinforcement learning approach to adjust the offer policy (i.e., adjust mechanism parameters). Lastly, our first two approaches use “supervision to manual mechanisms” as a systematic way for network initialization, which is potentially valuable for machine learning based mechanism design in general.

We extend the well-known model of graph-restricted games due to Myerson to signed graphs. In our model, it is possible to explicitly define not only that some players are friends (as in Myerson's model) but also that some other players are enemies. As such our games can express a wider range of situations, e.g., animosities between political parties. We define the value for signed graph games using the axiomatic approach that closely follows the celebrated characterization of the Myerson value. Furthermore, we propose an algorithm for computing an arbitrary semivalue, including the extension of the Myerson value proposed by us. We also develop a pseudo-polynomial algorithm for power indices in weighted voting games for signed graphs with bounded treewidth. Moreover, we consider signed graph games with a priori defined alliances (unions) between players and propose algorithms to compute the extension of the Owen value to this setting.

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.

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.

This paper presents a new way of formalizing the coalition structure generation problem (CSG) so that we can apply constraint optimization techniques to it. Forming effective coalitions is a major research challenge in AI and multi-agent systems. CSG involves partitioning a set of agents into coalitions to maximize social surplus. Traditionally, the input of the CSG problem is a black-box function called a characteristic function, which takes a coalition as input and returns the value of the coalition. As a result, applying constraint optimization techniques to this problem has been infeasible. However, characteristic functions that appear in practice often can be represented concisely by a set of rules, rather than treating the function as a black box. Then we can solve the CSG problem more efficiently by directly applying constraint optimization techniques to this compact representation. We present new formalizations of the CSG problem by utilizing recently developed compact representation schemes for characteristic functions. We first characterize the complexity of CSG under these representation schemes. In this context, the complexity is driven more by the number of rules than by the number of agents. As an initial step toward developing efficient constraint optimization algorithms for solving the CSG problem, we also develop mixed integer programming formulations and show that an off-the-shelf optimization package can perform reasonably well.

The cake cutting problem is concerned with the fair allocation of a divisible good among agents whose preferences vary over it. Recently, designing strategy-proof cake cutting mechanisms has caught considerable attention from AI and MAS researchers. Previous works assumed that an agent’s utility fu nction is additive so that theoretical analysis becomes tractable. However, in practice, agents have non-additive utility over a resource. In this paper, we consider the all-or-nothing utility function as a representative example of non-additive utility because it can widely cover agents’ preferences for such real-world resources as the usage of meeting rooms, time slots for computational resources, bandwidth usage, and so on. We first show the incompatibility between envy-freeness and Pareto efficiency when each agent has all-or-nothing utility. We next propose two strategy-proof mechanisms that satisfy Pareto efficiency, which are based on the serial dictatorship mechanism, at the sacrifice of envy-freeness. To address computational feasibility, we propose a heuristic-based allocation algorithm to find a near-optimal allocation in time polynomial in the number of agents, since the problem of finding a Pareto efficient allocation is NP-hard. As another approach that abandons Pareto efficiency, we develop an envy-free mechanism and show that one of our serial dictatorship based mechanisms satisfies proportionality in expectation, which is a weaker definition of proportionality. Finally, we evaluate the efficiency obtained by our proposed mechanisms by computational experiments.

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.

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.

We develop a flexible reward plan to elicit truthful predictive probability distribution over a set of uncertain events from workers. In our reward plan, the principal can assign rewards for incorrect predictions according to her similarity between events. In the spherical proper scoring rule, a worker's expected utility is represented as the inner product of her truthful predictive probability and her declared probability. We generalize the inner product by introducing a reward matrix that defines a reward for each prediction-outcome pair. We show that if the reward matrix is symmetric and positive definite, the spherical proper scoring rule guarantees the maximization of a worker's expected utility when she truthfully declares her prediction.

This paper studies a mechanism to incentivize agents who predict their own future actions and truthfully declare their predictions. In a crowdsouring setting (e.g., participatory sensing), obtaining an accurate prediction of the actions of workers/agents is valuable for a requester who is collecting real-world information from the crowd. If an agent predicts an external event that she cannot control herself (e.g., tomorrow's weather), any proper scoring rule can give an accurate incentive. In our problem setting, an agent needs to predict her own action (e.g., what time tomorrow she will take a photo of a specific place) that she can control to maximize her utility. Also, her (gross) utility can vary based on an eternal event. We first prove that a mechanism can satisfy our goal if and only if it utilizes a strictly proper scoring rule, assuming that an agent can find an optimal declaration that maximizes her expected utility. This declaration is self-fulfilling; if she acts to maximize her utility, the probabilistic distribution of her action matches her declaration, assuming her prediction about the external event is correct. Furthermore, we develop a heuristic algorithm that efficiently finds a semi-optimal declaration, and show that this declaration is still self-fulfilling. We also examine our heuristic algorithm's performance and describe how an agent acts when she faces an unexpected scenario.

We develop a mechanism for setting discriminated reward prices in order to group crowd workers according to their abilities. Generally, a worker has a certain level of 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 to utilize confidence for inferring correct answers. One is that a worker is not always well-calibrated. Since she is sometimes over/underconfident, her confidence does not always coincide with the probability of correctness. The other is that she does not always truthfully report her confidence. Thus, 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 a plan including true confidence maximizes the worker's expected utility. We also propose a method that composes a set of plans that can achieve requester-specified accuracy in estimating the correct answer using a small number of workers. We show our experimental results using Amazon Mechanical Turk.

We propose a keyword auction protocol called the GSP-ExR (GSP with an exclusive right) in which the number of advertisements displayed around search results can be dynamically adjusted. It is an extension of the generalized second-price (GSP) auction

We propose a keyword auction protocol called the Generalized Second Price with an Exclusive Right (GSP-ExR). In existing keyword auctions, the number of displayed advertisements is determined in advance. Thus, we consider adjusting the number of advertisements dynamically based on bids. In the GSP-ExR, the number of slots can be either 1 or K. When K slots are displayed, the protocol is identical to the GSP. If the value per click of the highest ranked bidder is large enough, then this bidder can exclusively display her advertisement by paying a premium. Thus, this pricing scheme is relatively simple and seller revenue is at least as good as the GSP. Also, in the GSP-ExR, the highest ranked bidder has no incentive to change the number of slots by over/under-bidding as long as she retains the top position.

Internet auctions have become an integral part of electronic commerce (EC) and a promising field for applying agent technologies. Although the Internet provides an excellent infrastructure for large-scale auctions, we must consider the possibility of a new type of cheating, i.e., a bidder trying to profit from submitting several bids under fictitious names (false-name bids). Double auctions are an important subclass of auction protocols that permit multiple buyers and sellers to bid to exchange a good, and have been widely used in stock, bond, and foreign exchange markets. If there exists no false-name bid, a double auction protocol called PMD protocol has proven to be dominant-strategy incentive compatible. On the other hand, if we consider the possibility of false-name bids, the PMD protocol is no longer dominant-strategy incentive compatible. We develop a new double auction protocol called the Threshold Price Double auction (TPD) protocol, which is dominant strategy incentive compatible even if participants can submit false-name bids. The characteristics of the TPD protocol is that the number of trades and prices of exchange are controlled by the threshold price. Simulation results show that this protocol can achieve a social surplus that is very close to being Pareto efficient.

The purpose of this paper is to analyze a collective decision making problem in an open, dynamic environment, such as the Internet. More specifically, we study a class of mechanism design problems where the designer of a mechanism cannot completely identify the participants (agents) of the mechanism. A typical example of such a situation is Internet auctions. The main contributions of this paper are as follows. We develop a formal model of a mechanism design problem in which false-name declarations are possible, and prove that the revelation principle still holds in this model. When false-name declarations and hiding are possible, we show that there exists no auction protocol that achieves Pareto efficient allocations in a dominant strategy equilibrium for all cases. We show a sufficient condition where the Clarke mechanism is robust against false-name declarations (the concavity of the maximal total utility of agents).

Article An efficient approximate algorithm for winner determination in combinatorial auctions Share on Authors: Yuko Sakurai NTT Communication Science Laboratories, 2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-0237 Japan NTT Communication Science Laboratories, 2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-0237 JapanView Profile , Makoto Yokoo NTT Communication Science Laboratories, 2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-0237 Japan NTT Communication Science Laboratories, 2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-0237 JapanView Profile , Koji Kamei NTT Communication Science Laboratories, 2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-0237 Japan NTT Communication Science Laboratories, 2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-0237 JapanView Profile Authors Info & Claims EC '00: Proceedings of the 2nd ACM conference on Electronic commerceOctober 2000 Pages 30–37https://doi.org/10.1145/352871.352875Published:17 October 2000 38citation453DownloadsMetricsTotal Citations38Total Downloads453Last 12 Months5Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access