In this paper we conceptualize abstract argumentation in terms of successful and unsuccessful attacks, such that arguments are accepted when there are no successful attacks on them. We characterize the relation between attack semantics and Dung's approach, and we define an SCC recursive algorithm for attack semantics using attack labelings.

Typical solutions for agents assessing trust relies on the circulation of information on the individual level, i.e. reputational images, subjective experi- ences, statistical analysis, etc. This work presents an alternative approach, inspired to the cognitive heuristics enabling humans to reason at a categorial level. The approach is envisaged as a crucial ability for agents in order to: (1) estimate trustworthiness of unknown trustees based on an ascribed mem- bership to categories; (2) learn a series of emer- gent relations between trustees observable proper- ties and their effective abilities to fulfill tasks in sit- uated conditions. On such a basis, categorization is provided to recognize signs (Manifesta) through which hidden capabilities (Kripta) can be inferred. Learning is provided to refine reasoning attitudes needed to ascribe tasks to categories. A series of ar- chitectures combining categorization abilities, indi- vidual experiences and context awareness are eval- uated and compared in simulated experiments.

Forming effective coalitions is a major research challenge in AI and multi-agent systems (MAS). Thus, coalitional games, including Coalition Structure Generation (CSG), have been attracting considerable attention from the AI research community. Traditionally, the input of a coalitional game is a black-box function called a characteristic function. A range of previous studies have found that many problems in coalitional games tend to be computationally intractable when the input is a black-box function. Recently, several concise representation schemes for a characteristic function have been proposed. Although these schemes are effective for reducing the representation size, most problems remain computationally intractable. In this paper, we develop a new concise representation scheme based on the idea of agent types. Intuitively, a type represents a set of agents, which are recognized as having the same contribution. This representation can be exponentially more concise than existing concise representation schemes. Furthermore, this idea can be used in conjunction with existing schemes to further reduce the representation size. Moreover, we show that most of the problems in coalitional games, including CSG, can be solved in polynomial time in the number of agents, assuming the number of possible types is fixed.

Envy-freeness is a well-known fairness concept for analyzing mechanisms. Its traditional definition requires that no individual envies another individual. However, an individual (or a group of agents) may envy another group, even if she (or they) does not envy another individual. In mechanisms with monetary transfer, such as combinatorial auctions, considering such fairness requirements, which are refinements of traditional envy-freeness, is meaningful and brings up a new interesting research direction in mechanism design. In this paper, we introduce two new concepts of fairness called envy-freeness of an individual toward a group, and envy-freeness of a group toward a group. They are natural extensions of traditional envy-freeness. We discuss combinatorial auction mechanisms that satisfy these concepts. First, we characterize such mechanisms by focusing on their allocation rules. Then we clarify the connections between these concepts and three other properties: the core, strategy-proofness, and false-name-proofness.

The VCG mechanism is the gold standard for combinatorial auctions (CAs), and it maximizes social welfare. In contrast, the revenue-maximizing (aka optimal) CA is unknown, and designing one is NP-hard. Therefore, research on optimal CAs has progressed into special settings. Notably, Levin [1997] derived the optimal CA for complements when each agent's private type is one-dimensional. We introduce a new research avenue for increasing revenue where we poke holes in the allocation space — based on the bids — and then use a welfare-maximizing allocation rule within the remaining allocation set. In this paper, the first step down this avenue, we introduce a new form of "reserve pricing" into CAs. We show that Levin's optimal revenue can be 2-approximated by using "monopoly reserve prices" to curtail the allocation set, followed by welfare-maximizing allocation and Levin's payment rule. A key lemma of potential independent interest is that the expected revenue from any truthful allocation-monotonic mechanism equals the expected virtual valuation; this generalizes Myerson's lemma [1981] from the single-parameter environment. Our mechanism is close to the gold standard and thus easier to adopt than Levin's. It also requires less information about the prior over the bidders' types, and is always more efficient. Finally, we show that the optimal revenue can be 6-approximated even if the "reserve pricing" is required to be symmetric across bidders.

We investigate the emergence and stability of social conventions for efficiently resolving conflicts through reinforcement learning. Facilitation of coordination and conflict resolution is an important issue in multi-agent systems. However, exhibiting coordinated and negotiation activities is computationally expensive. In this paper, we first describe a conflict situation using a Markov game which is iterated if the agents fail to resolve their conflicts, where the repeated failures result in an inefficient society. Using this game, we show that social conventions for resolving conflicts emerge, but their stability and social efficiency depend on the payoff matrices that characterize the agents. We also examine how unbalanced populations and small heterogeneous agents affect efficiency and stability of the resulting conventions. Our results show that (a) a type of indecisive agent that is generous for adverse results leads to unstable societies, and (b) selfish agents that have an explicit order of benefits make societies stable and efficient.

It is well known that cheating occurs in sports. In cup competitions, a common type of sports competition, one method of cheating is in manipulating the seeding to unfairly advantage a particular team. Previous empirical and theoretical studies of seeding manipulation have focused on competitions with unrestricted seeding. However, real cup competitions often place restrictions on seedings to ensure fairness, wide geographic interest, and so on. In this paper, we perform an extensive empirical study of seeding manipulation under comprehensive and realistic sets of restrictions. A generalized random model of competition problems is proposed. This model creates a realistic range of problem instances that are used to identify the sets of seeding restrictions that are hard to manipulate in practice. We end with a discussion of the implications of this work and recommendations for organizing competitions so as to prevent or reduce the opportunities for manipulating the seeding.

One approach for artificially intelligent agents wishing to maximise some performance metric in a given domain is to learn from a collection of training data that consists of actions or decisions made by some expert, in an attempt to imitate that expert's style. We refer to this type of agent as an expert imitator. In this paper we investigate whether performance can be improved by combining decisions from multiple expert imitators. In particular, we investigate two existing approaches for combining decisions. The first approach combines decisions by employing ensemble voting between multiple expert imitators. The second approach dynamically selects the best imitator to use at runtime given the performance of the imitators in the current environment. We investigate these approaches in the domain of computer poker. In particular, we create expert imitators for limit and no limit Texas Hold'em and determine whether their performance can be improved by combining their decisions using the two approaches listed above.

In this context, while it methods (see, e.g., [Shehory and Kraus, 1998; Sandholm et is desirable to generate a coalition structure that al., 1999; Sen and Dutta, 2000; Dang and Jennings, 2004; maximizes the sum of the values of the coalitions, Rahwan et al., 2009b]). In this context, an important line of the space of possible solutions is often too large research is the development of anytime CSG algorithms. In to allow exhaustive search. Thus, a fundamental particular, an algorithm is "anytime" if it can return a solution open question in this area is the following: Can we at any point of time during its execution, and the quality of its search through only a subset of coalition structures, solution improves monotonically until termination. This is and be guaranteed to find a solution that is within particularly desirable in the multi-agent system context since a desirable bound β from optimum? If so, what is the agents might not always have sufficient time to run the the minimum such subset?

The design of multiagent simulations devoted to complex systems, addresses the issue of modeling behaviors that are involved at different space, time, behavior scales, each one being relevant so as to represent a feature of the phenomenon. We propose here a generic formalism intended to represent multiple environments, endowed with their own spatiotemporal scales and with behavioral rules for the agents they contain. An environment can be nested inside any agent, which itself is situated in one or more environments. This leads to a lattice decomposition of the global system, which appears to be necessary for an accurate design of multi-scale systems. This uniform representation of entities and behaviors at each abstraction level relies upon an interaction-oriented approach for the design of agent simulations, which clearly separates agents from interactions, from the modeling to the code. We also explain the implementation of our formalism within an existing interaction-based platform.