The computational complexity of relevant corerelatedquestions for coalitional games is addressed from the coalition structure viewpoint, i.e., withoutassuming that the grand-coalition necessarily forms. In the analysis, games are assumed to be in "compact" form, i.e., their worth functions are implicitly given as polynomial-time computable functions over succinct game encodings provided as input. Within this setting, a complete picture of the complexity issues arising with the core, as well as with the related stability concepts of least core and cost of stability, is depicted. In particular, the special cases of superadditive games and of games whose sets of feasible coalitions are restricted over tree-like interaction graphs are also studied.

We address the issue of manipulating games through communication. In the specific setting we consider (a variation of Boolean games), we assume there is some set of environment variables, the value of which is not directly accessible to players; each player has their own beliefs about these variables, and makes decisions about what actions to perform based on these beliefs. The communication we consider takes the form of (truthful) announcements about the value of some environment variables; the effect of an announcement about some variable is to modify the beliefs of the players who hear the announcement so that they accurately reflect the value of the announced variables. By choosing announcements appropriately, it is possible to perturb the game away from certain rational outcomes and towards others. We specifically focus on the issue of stabilisation: making announcements that transform a game from having no stable states to one that has stable configurations.

Binary aggregation studies problems in which individuals express yes/no choices over a number of possibly correlated issues, and these individual choices need to be aggregated into a collective choice. We show how several classical frameworks of Social Choice Theory, particularly preference and judgment aggregation, can be viewed as binary aggregation problems by designing an appropriate set of integrity constraints for each specific setting. We explore the generality of this framework, showing that it makes available useful techniques both to prove theoretical results, such as a new impossibility theorem in preference aggregation, and to analyse practical problems, such as the characterisation of safe agendas in judgment aggregation in a syntactic way. The framework also allows us to formulate a general definition of paradox that is independent of the domain under consideration, which gives rise to the study of the class of aggregation procedures of generalised dictatorships.

We propose a formal model for argumentationbased dialogues between agents, using assumptionbased argumentation (ABA). The model is given in terms of ABA-specific utterances, trees drawn from dialogues and legal-move and outcome functions. We prove a formal connection between these dialogues and argumentation semantics. We illustrate persuasion as an application of the dialogue model.

The RoboCup robot soccer Small Size League has been running since 1997 with many teams successfully competiting and very effectively playing the games. Teams of five robots, with a combined autonomous centralized perception and control, and distributed actuation, move at high speeds in the field space, actuating a golf ball by passing and shooting it to aim at scoring goals. Most teams run their own pre-defined team strategies, unknown to the other teams, with flexible game-state dependent assignment of robot roles and positioning. However, in this fast-paced noisy real robot league, recognizing the opponent team strategies and accordingly adapting one's own play has proven to be a considerable challenge. In this work, we analyze logged data of real games gathered by the CMDragons team, and contribute several results in learning and responding to opponent strategies. We define episodes as segments of interest in the logged data, and introduce a representation that captures the spatial and temporal data of the multi-robot system as instances of geometrical trajectory curves. We then learn a model of the team strategies through a variant of agglomerative hierarchical clustering. Using the learned cluster model, we are able to classify a team behavior incrementally as it occurs. Finally, we define an algorithm that autonomously generates counter tactics, in a simulation based on the real logs, showing that it can recognize and respond to opponent strategies.

In elections, an alternative is said to be a Condorcet winner if it is preferred to any other alternative by a majority of voters. While this is a very attractive solution concept, many elections do not have a Condorcet winner. In this paper, we propose a setvalued relaxation of this concept, which we call a Condorcet winning set: such sets consist of alternatives that collectively dominate any other alternative. We also consider a more general version of this concept, where instead of domination by a majority of voters we require domination by a given fraction theta of voters; we refer to this concept as theta-winning set. We explore social choice-theoretic and algorithmic aspects of these solution concepts, both theoretically and empirically.

We report on results from experiments where human traders interact with software-agent traders in a real-time asynchronous continuous double auction (CDA) experimental economics system. Our experiments are inspired by the seminal work reported by IBM at IJCAI 2001, where it was demonstrated that software-agent traders could consistently outperform human traders in real-time CDA markets. IBM tested two trading-agent strategies, ZIP and a modified version of GD, and in a subsequent paper they reported on a new strategy called GDX that was demonstrated to outperform GD and ZIP in agent vs. agent CDA competitions, on which basis it was claimed that GDX "...may offer the best performance of any published CDA bidding strategy.". In this paper, we employ experiment methods similar to those pioneered by IBM to test the performance of "Adaptive Aggressive" (AA) algorithmic traders. The results presented here confirm Vytelingum's claim that AA outperforms ZIP, GD, and GDX in agent vs. agent experiments. We then present the first results from testing AA against human traders in human vs. agent CDA experiments, and demonstrate that AA's performance against human traders is superior to that of ZIP, GD, and GDX. We therefore claim that, on the basis of the available evidence, AA may offer the best performance of any published bidding strategy.

We consider scenarios where several agents must aggregate their preferences over a large set of candidates with a combinatorial structure. That is, each candidate is an element of the Cartesian product of the domains of some variables. We assume agents compactly express their preferences over the candidates via soft constraints. We consider a sequential procedure that chooses one candidate by asking the agents to vote on one variable at a time. While some properties of this procedure have been already studied, here we focus on independence of irrelevant alternatives, non-dictatorship, and strategy-proofness. Also, we perform an experimental study that shows that the proposed sequential procedure yields a considerable saving in time with respect to a non-sequential approach, while the winners satisfy the agents just as well, independently of the variable ordering and of the presence of coalitions of agents.

We address the issue, in cognitive agents, of possible loss of previous information, which later might turn out to be correct when new information becomes available. To this aim, we propose a framework for changing the agent's mind without erasing forever previous information, thus allowing its recovery in case the change turns out to be wrong. In this new framework, a piece of information is represented as an argument which can be more or less accepted depending on the trustworthiness of the agent who proposes it. We adopt possibility theory to represent uncertainty about the information, and to model the fact that information sources can be only partially trusted. The originality of the proposed framework lies in the following two points: (i) argument reinstatement is mirrored in belief reinstatement in order to avoid the loss of previous information; (ii) new incoming information is represented under the form of arguments and it is associated with a plausibility degree depending on the trustworthiness of the information source.

We consider a framework for preference aggregation on multiple binary issues, where agents' preferences are represented by (possibly cyclic) CP-nets. We focus on the majority aggregation of the individual CP-nets, which is the CP-net where the direction of each edge of the hypercube is decided according to the majority rule. First we focus on hypercube Condorcet winners (HCWs); in particular, we show that, assuming a uniform distribution for the CP-nets, the probability that there exists at least one HCW is at least 1-1/e, and the expected number of HCWs is 1. Our experimental results confirm these results. We also show experimental results under the Impartial Culture assumption. We then generalize a few tournament solutions to select winners from (weighted) majoritarian CP-nets, namely Copeland, maximin, and Kemeny. For each of these, we address some social choice theoretic and computational issues.