To achieve an optimal outcome in many situations, agents need to choose distinct actions from one another. This is the case notably in many resource allocation problems, where a single resource can only be used by one agent at a time. How shall a designer of a multi-agent system program its identical agents to behave each in a different way? From a game theoretic perspective, such situations lead to undesirable Nash equilibria. For example consider a resource allocation game in that two players compete for an exclusive access to a single resource. It has three Nash equilibria. The two pure-strategy NE are efficient, but not fair. The one mixed-strategy NE is fair, but not efficient. Aumann's notion of correlated equilibrium fixes this problem: It assumes a correlation device that suggests each agent an action to take. However, such a "smart" coordination device might not be available. We propose using a randomly chosen, "stupid" integer coordination signal. "Smart" agents learn which action they should use for each value of the coordination signal. We present a multi-agent learning algorithm that converges in polynomial number of steps to a correlated equilibrium of a channel allocation game, a variant of the resource allocation game. We show that the agents learn to play for each coordination signal value a randomly chosen pure-strategy Nash equilibrium of the game. Therefore, the outcome is an efficient correlated equilibrium. This CE becomes more fair as the number of the available coordination signal values increases.

As our world becomes better connected and autonomous agents no longer appear to be science fiction, a natural need arises for enabling groups of selfish agents to cooperate in generating plans for diverse tasks that none of them can perform alone in a cost-effective manner. While most work on planning for/by selfish agents revolves around finding stable solutions (e.g., Nash Equilibrium), this work combines techniques from mechanism design with a recently introduced method for distributed planning, in order to find cost optimal (and, thus, social welfare maximizing) solutions. Based on the Vickrey-Clarke-Groves mechanisms, we present both a centralized, and a privacy-preserving distributed mechanism.

Modal Markov Logic for a single agent has previously been proposed as an extension to propositional Markov logic. While the framework allowed reasoning under the principle of maximum entropy for various modal logics, it is not feasible to apply its counting based inference to reason about the beliefs and knowledge of multiple agents due to magnitude of the numbers involved. We propose a modal extension of propositional Markov logicthat avoids this problem by coarsening the state space.The problem stems from the fact that in the single-agent setting, the state space is only doubly exponential in the number of propositions in the domain, but the state space can potentially become infinite in the multi-agent setting. In addition, the proposed framework adds only the overhead of deciding satisfiability for the chosen modal logic on the top of the complexity of exact inference in propositional Markov logic. The proposed framework allows one to find a distribution that matches probabilities of formulas obtained from training data (or provided by an expert). Finally, we show how one can compute lower and upper bounds on probabilities of arbitrary formulas.

Distributed Constraint Problem solving represents a fundamental research area in distributed artificial intelligence and multi-agent systems. The constraint density, or the ratio of the number of constraints to the number of variables, determines the difficulty of either finding a solution or minimizing the set of variable assignment conflicts. Reducing density typically reduces difficulty. We present a fully distributed technique for reducing the effective density of constraint graphs, called Virtual Structure Reduction (VSR). The VSR technique leverages the occurrence of variables that must be assigned the same value based on shared constraints and can improve solver performance using existing algorithms. We discuss our Distributed Constraint Optimization Problem (DCOP) solver, integrated with the Distributed Stochastic Algorithm (DSA), called VSR-DSA. The VSR-DSA algorithm demonstrates performance gains vs DSA in both solution quality and time on 3-coloring problems.

In this paper we offer an approach for reasoning about resource allocation and scheduling in multiagent systems that takes into consideration the costs of preempting an agent from its current task. We apply our methodology to the motivating medical application of allocating doctors to patients in hospitals during mass casualty incidents and demonstrate noticeable improvements in performance (generating far fewer problem patients) over competing approaches that do not model the costs of preemption in sufficient detail. In particular, our approach offers a method for addressing the challenges of cyclical dependencies in the estimation of preemption costs by localized agents through a combination of planning techniques.

The workshop on Trading Agent Design and Analysis focuses on all aspects of the design and evaluation of trading agents, including agent architectures, decision-making algorithms, theoretic analysis of agents or market games, empirical studies of agent performance, agent negotiation strategies, game-theoretic studies, market architectures and other related topics.

In this paper we investigate the applications of Elo ratings (originally designed for 2-player chess) to a heterogeneous nonlinear multiagent system to determine an agent's overall impact on its team's performance. Measuring this impact has been attempted in many different ways, including reward shaping; the generation of heirarchies, holarchies, and teams; mechanism design; and the creation of subgoals. We show that in a multiagent system, an Elo rating will accurately reflect an agent's ability to contribute positively to a team's success with no need for any other feedback than a repeated binary win/loss signal. The Elo rating not only measures ``personal" success, but simultaneously success in assisting other agents to perform favorably.

This work describes a student-friendly, pedagogy-oriented event-handling system for managing multiagent AI simulations in a classroom environment.

Distributed denial of service (DDoS) attacks constitute a rapidly evolving threat in the current Internet. In this paper we introduce Multiagent Router Throttling, a decentralized DDoS response mechanism in which a set of upstream routers independently learn to throttle traffic towards a victim server. We compare our approach against a baseline and a popular throttling technique from the literature, and we show that our proposed approach is more secure, reliable and cost-effective. Furthermore, our approach outperforms the baseline technique and either outperforms or has the same performance as the popular one.

For decades researchers have struggled with the problem of envy-free cake cutting: how to divide a divisible good between multiple agents so that each agent likes his own allocation best. Although an envy-free cake cutting protocol was ultimately devised, it is unbounded, in the sense that the number of operations can be arbitrarily large, depending on the preferences of the agents. We ask whether bounded protocols exist when the agents' preferences are restricted. Our main result is an envy-free cake cutting protocol for agents with piecewise linear valuations, which requires a number of operations that is polynomial in natural parameters of the given instance.