There is a fundamental incompatibility between efficiency, interim individual rationality, and budget-balance in mechanism design, even for extremely simple settings. Yet it is possible to specify efficient mechanisms that satisfy participation and budget-balance constraints in expectation, prior to types being realized. We do so here, in fact deriving mechanisms that are individually rational for each agent even ex post of other agents' type realizations. However, participation must still bear some risk of loss. For agents that are risk neutral, we show how the center can extract the entire surplus in expectation, or alternatively provide an equal expected share of the surplus for each participant, without violating dominant strategy incentive compatibility, efficiency, or ex ante budget-balance. We compare these solutions to a third efficient mechanism we design explicitly to address risk aversion in trade settings: payments are defined to minimize the odds of loss, satisfying ex ante participation constraints for agents with attitudes toward risk ranging from neutrality to high loss-aversion.

Cake cutting is a playful name for the problem of fairly dividing a heterogeneous divisible good among a set of agents. The agent valuations for different pieces of cake are typically assumed to be additive. However, in certain practical settings this assumption is invalid because agents may not have positive value for arbitrarily small "crumbs" of cake. In this paper, we propose a new, more expressive model of agent valuations that captures this feature. We present an approximately proportional algorithm for any number of agents that have such expressive valuations. The algorithm is optimal in the sense that no other algorithm can guarantee a greater worst-case degree of proportionality. We also design an optimal approximately proportional and fully envy-free algorithm for two agents.

Trust is crucial in dynamic multi-agent systems, where agents may frequently join and leave, and the structure of the society may often change. In these environments, it may be difficult for agents to form stable trust relationships necessary for confident interactions. Societies may break down when trust between agents is too low to motivate interactions. In such settings, agents should make decisions about who to interact with, given their degree of trust in the available partners. We propose a decision-theoretic model of trust decision making allows controls to be used, as well as trust, to increase confidence in initial interactions. We consider explicit incentives, monitoring and reputation as examples of such controls. We evaluate our approach within a simulated, highly-dynamic multi-agent environment, and show how this model supports the making of delegation decisions when trust is low.

Alternating-time temporal logic (ATL) is a well-known logic for reasoning about strategic abilities of agents. An important feature that distinguishes variants of ATL for imperfect information scenarios is that the standard fixed point characterizations of temporal modalities do not hold anymore. In this paper, we show that adding explicit fixed point operators to the "next-time" fragment of ATL already allows to capture abilities that could not be expressed in ATL. We also illustrate that the new language allows to specify important kinds of abilities, namely ones where the agents can always recompute their strategy while executing it. Thus, the agents are not assumed to remember their strategy by definition, like in the existing variants of ATL. Last but not least, we show that verification of such abilities can be cheaper than for all the variants of `"ATL with imperfect information" considered so far.

The environment is an essential component of multi-agent systems and is often used to coordinate the behaviour of individualagents. Recently many languages have been proposed to specify and implement multi-agent environments in terms of social and normative concepts. In this paper, we first introduce a formal setting of multi-agent environment which abstracts from concrete specification languages. We extend this formal setting with norms and sanctions and show how concepts from mechanism design can be used to formally analyse and verify whether specific normative behaviours can be enforced (or implemented) if agents follow their subjective preferences. We also consider complexity issues of associated problems.

In many multi-agent systems, the emergence of norms is the primary factor that determines overall behavior and utility. Agent simulations can be used to predict and study the development of these norms. However, a large number of simulations is usually required to provide an accurate depiction of the agents’ behavior, and some rare contingencies may still be overlooked completely. The cost and risk involvedwith agent simulations can be reduced by analyzing a system theoretically and producing models of its behavior. We use such a theoretical approach to examine the dynamics of a population of agents playing a coordination game to determine all the norms to which the society can converge, and develop a system of linear recurrence relations that predict how frequently each of these norms will be reached, as well as the average convergence time. This analysis produces certain guarantees about system behavior that canot be provided by a purely empirical approach, and can be used to make predictions about the emergence of norms that numerically match those obtained through large-scale simulations.

We consider the following sequential allocation process. A benevolent central authority has to allocate a set of indivisible goods to a set of agents whose preferences it is totally ignorant of. We consider the process of allocating objects one after the other by designating an agent and asking her to pick one of the objects among those that remain. The problem consists in choosing the "best" sequence of agents, according to some optimality criterion. We assume that agents have additive preferences over objects. The choice of an optimality criterion depends on three parameters: how utilities of objects are related to their ranking in an agent's preference relation; how the preferences of different agents are correlated; and how social welfare is defined from the agents' utilities. We address the computation of a sequence maximizing expected social welfare under several assumptions. We also address strategical issues.

Grammatical agreement is present in many of the world's languages today and has become an essential feature that guides linguistic processing. When two words in a sentence are said to "agree", this means that they share certain features such as "gender", "number", "person" or others. The primary hypothesis of this paper is that marking agreement within one linguistic phrase reduces processing effort as phrasal constituents can more easily be recognized. The drive to reduce processing effort introduces the rise of agreement marking in a population of multiple agents by means of an incrementally aligned mapping between the most discriminatory features of a particular linguistic unit and their associative markers. A series of experiments compare feature selection methods for one-to-one agreement mappings, and show how an agreement system can be bootstrapped.

Such agents may simply respond to their current environment without worrying about An important task in the analysis of multiagent systems the subsequent reaction of other agents; such behavior is said is to understand how groups of selfish players to be myopic. Now, coalition formation by computationally can form coalitions, i.e., work together in teams. In limited agents has been studied by a number of researchers in this paper, we study the dynamics of coalition formation multi-agent systems, starting with the work of [Shehory and under bounded rationality. We consider settings Kraus, 1999] and [Sandholm and Lesser, 1997]. However, where each team's profit is given by a concave myopic behavior in coalition formation received relatively little function, and propose three profit-sharing schemes, attention in the literature (for some exceptions, see [Dieckmann each of which is based on the concept of marginal and Schwalbe, 2002; Chalkiadakis and Boutilier, 2004; utility. The agents are assumed to be myopic, i.e., Airiau and Sen, 2009]). In contrast, myopic dynamics of they keep changing teams as long as they can increase non-cooperative games is the subject of a growing body of their payoff by doing so. We study the properties research (see, e.g.

We present a novel methodology for decision-making by computer agents that leverages a computational concept of emotions. It is believed that emotions help living organisms perform well in complex environments. Can we use them to improve the decision-making performance of computer agents? We explore this possibility by formulating emotions as mathematical operators that serve to update the relative priorities of the agent's goals. The agent uses rudimentary domain knowledge to monitor the expectation that its goals are going to be accomplished in the future, and reacts to changes in this expectation by "experiencing emotions." The end result is a projection of the agent's long-run utility function, which might be too complex to optimize or even represent, to a time-varying valuation function that is being myopically maximized by selecting appropriate actions. Our methodology provides a systematic way to incorporate emotion into a decision-theoretic framework, and also provides a principled, domain-independent methodology for generating heuristics in novel situations. We test our agents in simulation in two domains: restless bandits and a simple foraging environment. Our results indicate that emotion-based agents outperform other reasonable heuristics for such difficult domains, and closely approach computationally expensive near-optimal solutions, whenever these are computable, yet requiring only a fraction of the cost.