Trust is an important mechanism enabling agents to self-police open and dynamic multi-agent systems (ODMASs). Trusters evaluate the reputation of trustees based on their past observed performance, and use this information to guide their future interaction decisions. Existing trust models tend to concentrate trusters’ interactions on a small number of highly reputable trustees to minimize risk exposure. When a trustee’s servicing capacity is limited, such an approach may cause long delays for trusters and subsequently damage the reputation of trustees. To mitigate this problem, we propose a reputation management approach for trustee agents based on distributed constraint optimization. It helps a trustee to make situation-aware decisions on which incoming requests to serve and prevent the resulting reputation score from being affected by factors out of the trustee’s control. The approach is evaluated through theoretical analysis and within a simulated, highly dynamic multi-agent environment. The results show that it can achieve close to optimally efficient utilization of the trustee agents’ collective capacity in an ODMAS, promotes fair treatment of trustee agents based on their behavior, and significantly outperforms related work in enhancing social welfare.

A key challenge in non-cooperative multi-agent systems is that of developing efficient planning algorithms for intelligent agents to interact and perform effectively among boundedly rational, self-interested agents (e.g., humans). The practicality of existing works addressing this challenge is being undermined due to either the restrictive assumptions of the other agents' behavior, the failure in accounting for their rationality, or the prohibitively expensive cost of modeling and predicting their intentions. To boost the practicality of research in this field, we investigate how intention prediction can be efficiently exploited and made practical in planning, thereby leading to efficient intention-aware planning frameworks capable of predicting the intentions of other agents and acting optimally with respect to their predicted intentions. We show that the performance losses incurred by the resulting planning policies are linearly bounded by the error of intention prediction. Empirical evaluations through a series of stochastic games demonstrate that our policies can achieve better and more robust performance than the state-of-the-art algorithms.

In reputation systems for multiagent-based e-marketplaces, buying agents model the reputation of selling agents based on ratings shared by other buyers (called advisors). With the existence of unfair rating attacks from dishonest advisors, the effectiveness of reputation systems thus heavily relies on whether buyers can accurately determine which advisors to include in trust networks and their trustworthiness. In this paper, we propose two approaches to deal with unfair rating attacks. The first method is to combine the advantages of different categorical trust models. Secondly, we propose a novel multiagent evolutionary trust model (MET) where each buyer constructs its trust network (information about which advisors should be include in the network and their trustworthiness) by the evolutionary model. Experimental results demonstrate the proposed algorithms are more robust than the state-of-the-art trust models against various unfair rating attacks.

In human conversation, meaning is transported through several channels such as verbal and nonverbal behavior. Certain of these behavioral aspects are culturally dependent. Mutual understanding or acceptance is thus, amongst others, depended on the cultural background of the interlocutors. When designing virtual character behavior, culture should be considered as it may improve the character's acceptance by users of certain cultural backgrounds. This paper proposes a hybrid approach for the generation of culture-specific behaviors in a multiagent system. A computational model has been established by refining theoretical knowledge of culture-specific behavior with statistical data extracted from a video corpus of German and Japanese first-time meetings. Evaluation studies of such culturally enhanced virtual characters were conducted in both targeted cultures. Results indicate that human observers tend to prefer character behavior that was designed to resemble their own cultural background.

Coordination in cooperative multiagent systems is an important problem in multiagent learning literature. In practical complex environments, the interactions between agents can be sparse, and each agent's interacting partners may change frequently and randomly. To this end, we investigate the multiagent coordination problems in cooperative environments under the social learning framework. We consider a large population of agents where each agent interacts with another agent randomly chosen from the population in each round. Each agent learns its policy through repeated interactions with the rest of agents via social learning. It is not clear a priori if all agents can learn a consistent optimal coordination policy in such a situation. We distinguish two types of learners: individual action learner and joint action learner. The learning performance of both learners are evaluated under a number of challenging cooperative games, and the influence of the information sharing degree on the learning performance is investigated as well.

Our research is within the subfield of modeling trust and reputation in multi-agent systems for online communities. Specifically, in an online community involving users and entities, users provide opinions (ratings) to entities. For each user, we are interested in addressing two problems: (1) how to accurately model the reputation of entities by aggregating opinions from all the users (advisors); and (2) how to cope with the dishonesty of an advisor in providing opinions as well as her subjectivity difference with the user.

Social norms are one of the mechanisms for decentralized societies to achieve coordination amongst individuals. Such norms are conflict resolution strategies that develop from the population interactions instead of a centralized entity dictating agent protocol.One of the most important characteristics of social norms is that they are imposed by the members of the society, and they are responsible for the fulfillment and defense of these norms. By allowing agents to manage (impose, abide by and defend) social norms, societies achieve a higher degree of freedom by lacking the necessity of authorities supervising all the interactions amongst agents. In this article we summarize the contributions of my dissertation, where we provide an unifying framework for the analysis of social norms in virtual societies, providing an strong emphasis on virtual agents and humans.

The task of explanatory diagnosis conjectures actions to explain observations.This is a common task in real life and an essential ability of intelligent agents.It becomes more complicated in multi-agent scenarios, sinceagents' actions may be partially observable to other agents, andobservations might involve agents' knowledge about the world or other agents' knowledge oreven common knowledge of a group of agents.For example, we might want to explain the observation that $p$ does not hold,but Ann believes $p$, or the observation that Ann, Bob, and Carl commonly believe $p$.In this paper, we formalize the multi-agent explanatory diagnosis task in the framework of dynamic epistemic logic, where Kripke models of actions are used to represent agents' partial observability of actions. Since this task is undecidable in general, we identify important decidable fragments via techniques of reducing the potentially infinite search spaces to finite ones of epistemic states or action sequences.

Distributed Constraint Optimization (DCOP) is a powerful framework for representing and solving distributed combinatorial problems, where the variables of the problem are owned by different agents. Many multi-agent problems include constraints that produce different gains (or costs) for the participating agents. Asymmetric gains of constrained agents cannot be naturally represented by the standard DCOP model. The present paper proposes a general framework for Asymmetric DCOPs (ADCOPs). In ADCOPs different agents may have different valuations for constraints that they are involved in. The new framework bridges the gap between multi-agent problems which tend to have asymmetric structure and the standard symmetric DCOP model. The benefits of the proposed model over previous attempts to generalize the DCOP model are discussed and evaluated. Innovative algorithms that apply to the special properties of the proposed ADCOP model are presented in detail. These include complete algorithms that have a substantial advantage in terms of runtime and network load over existing algorithms (for standard DCOPs) which use alternative representations. Moreover, standard incomplete algorithms (i.e., local search algorithms) are inapplicable to the existing DCOP representations of asymmetric constraints and when they are applied to the new ADCOP framework they often fail to converge to a local optimum and yield poor results. The local search algorithms proposed in the present paper converge to high quality solutions. The experimental evidence that is presented reveals that the proposed local search algorithms for ADCOPs achieve high quality solutions while preserving a high level of privacy.

We investigate two systems of fully proportional representation suggested by Chamberlin & Courant and Monroe. Both systems assign a representative to each voter so that the "sum of misrepresentations" is minimized. The winner determination problem for both systems is known to be NP-hard, hence this work aims at investigating whether there are variants of the proposed rules and/or specific electorates for which these problems can be solved efficiently. As a variation of these rules, instead of minimizing the sum of misrepresentations, we considered minimizing the maximal misrepresentation introducing effectively two new rules. In the general case these "minimax" versions of classical rules appeared to be still NP-hard. We investigated the parameterized complexity of winner determination of the two classical and two new rules with respect to several parameters. Here we have a mixture of positive and negative results: e.g., we proved fixed-parameter tractability for the parameter the number of candidates but fixed-parameter intractability for the number of winners. For single-peaked electorates our results are overwhelmingly positive: we provide polynomial-time algorithms for most of the considered problems. The only rule that remains NP-hard for single-peaked electorates is the classical Monroe rule.