Looking ahead to the time when autonomous cars will be common, Dresner and Stone proposed a multiagent systems-based intersection control protocol called Autonomous Intersection Management (AIM). They showed that by leveraging the capacities of autonomous vehicles it is possible to dramatically reduce the time wasted in traffic, and therefore also fuel consumption and air pollution. The proposed protocol, however, handles reservation requests one at a time and does not prioritize reservations according to their relative priorities and waiting times, causing potentially large inequalities in granting reservations. For example, at an intersection between a main street and an alley, vehicles from the alley can take an excessively long time to get reservations to enter the intersection, causing a waste of time and fuel. The same is true in a network of intersections, in which gridlock may occur and cause traffic congestion. In this paper, we introduce the batch processing of reservations in AIM to enforce liveness properties in intersections and analyze the conditions under which no vehicle will get stuck in traffic. Our experimental results show that our prioritizing schemes outperform previous intersection control protocols in unbalanced traffic.

The problem of multiagent patrol has gained considerable attention during the past decade, with the immediate applicability of the problem being one of its main sources of interest. In this paper we concentrate on frequency-based patrol, in which the agents' goal is to optimize a frequency criterion, namely, minimizing the time between visits to a set of interest points. We consider multiagent patrol in environments with complex environmental conditions that affect the cost of traveling from one point to another. For example, in marine environments, the travel time of ships depends on parameters such as wind, water currents, and waves. We demonstrate that in such environments there is a need to consider a new multiagent patrol strategy which divides the given area into parts in which more than one agent is active, for improving frequency. We show that in general graphs this problem is intractable, therefore we focus on simplified (yet realistic) cyclic graphs with possible inner edges. Although the problem remains generally intractable in such graphs, we provide a heuristic algorithm that is shown to significantly improve point-visit frequency compared to other patrol strategies. For evaluation of our work we used a custom developed ship simulator that realistically models ship movement constraints such as engine force and drag and reaction of the ship to environmental changes.

A key problem in mechanism design is the construction of protocols that reach socially efficient decisions with minimal information revelation. This can reduce agent communication, and further, potentially increase privacy in the sense that agents reveal no more private information than is needed to determine an optimal outcome. This is not always possible: previous work has explored the tradeoff between communication cost and efficiency, and more recently, communication and privacy. We explore a third dimension: the tradeoff between privacy and efficiency. By sacrificing efficiency, we can improve the privacy of a variety of existing mechanisms. We analyze these tradeoffs in both second-price auctions and facility location problems (introducing new incremental mechanisms for facility location along the way). Our results show that sacrifices in efficiency can provide gains in privacy (and communication), in both the average and worst case.

Cooperative path-finding can be abstracted as computing non-colliding paths for multiple agents between their start and goal locations on a graph. This work proposes a fast algorithm that can provide completeness guarantees for a general class of problems without any assumptions about the graph's topology. Specifically, the approach can address any solvable instance where there are at most n-2 agents in a graph of size n. The algorithm employs two primitives: a "push" operation where agents move towards their goals up to the point that no progress can be made, and a "swap" operation that allows two agents to swap positions without altering the configuration of other agents. Simulated experiments are provided on hard instances of cooperative path-finding, including comparisons against alternative methods. The results are favorable for the proposed algorithm and show that the technique scales to problems that require high levels of coordination, involving hundreds of agents.

The most prominent way to establish trust between buyers and sellers on online auction sites are reputation mechanisms. Two drawbacks of this approach are the reliance on the seller being long-lived and the susceptibility to whitewashing. In this paper, we introduce so-called escrow mechanisms that avoid these problems by installing a trusted intermediary which forwards the payment to the seller only if the buyer acknowledges that the good arrived in the promised condition. We address the incentive issues that arise and design an escrow mechanism that is incentive-compatible, efficient, interim individually rational and ex ante budget-balanced. In contrast to previous work on trust and reputation, our approach does not rely on knowing the sellers' cost functions or the distribution of buyer valuations.

Our approach Multi-agent task allocation is an important and challenging yields significant reductions in both run-time and communication, problem, which involves deciding how to assign a set thereby increasing real-world applicability. of agents to a set of tasks, both of which may change over In more detail, in this paper we advance the state-ofthe-art time (i.e., it is a dynamic environment). Moreover, it is often in the following ways: first, we present a novel, necessary for heterogeneous agents to form teams (known as online domain pruning algorithm specifically tailored to coalitions) to complete certain tasks in the environment. In dynamic task allocation environments to reduce the number coalitions, agents can often complete tasks more efficiently of potential solutions that need to be considered.

When to make a decision is a key question in decision making problems characterized by uncertainty. In this paper we deal with decision making in environments where the information arrives dynamically. We address the tradeoff between waiting and stopping strategies. On the one hand, waiting to obtain more information reduces the uncertainty, but it comes with a cost. On the other hand, stopping and making a decision based on an expected utility, decreases the cost of waiting, but the decision is made based on uncertain information. In this paper, we prove that computing the optimal time to make a decision that guarantees the optimal utility is NP-hard. We propose a pessimistic approximation that guarantees an optimal decision when the recommendation is to wait. We empirically evaluate our algorithm and show that the quality of the decision is near-optimal and much faster than the optimal algorithm.

We present a novel approach for identifying exact and approximate behavioral equivalence between models of agents. This is significant because both decision making and game play in multiagent settings must contend with behavioral models of other agents in order to predict their actions. One approach that reduces the complexity of the model space is to group models that are behaviorally equivalent. Identifying equivalence between models requires solving them and comparing entire policy trees. Because the trees grow exponentially with the horizon, our approach is to focus on partial policy trees for comparison and determining the distance between updated beliefs at the leaves of the trees. We propose a principled way to determine how much of the policy trees to consider, which trades off solution quality for efficiency. We investigate this approach in the context of the interactive dynamic influence diagram and evaluate its performance.

Opponent modeling is a critical mechanism in repeated games. It allows a player to adapt its strategy in order to better respond to the presumed preferences of its opponents. We introduce a modeling technique that adaptively balances safety and exploitability. The opponent's strategy is modeled with a set of possible strategies that contains the actual one with high probability. The algorithm is safe as the expected payoff is above the minimax payoff with high probability, and can exploit the opponent's preferences when sufficient observations are obtained. We apply the algorithm to a robot table-tennis setting where the robot player learns to prepare to return a served ball. By modeling the human players, the robot chooses a forehand, backhand or middle preparation pose before they serve. The learned strategies can exploit the opponent's preferences, leading to a higher rate of successful returns.

Coalition formation is a key topic in multi-agent systems. Coalitions enable agents to achieve goals that they may nothave been able to achieve on their own. Previous work hasshown problems in coalition games to be computationally hard. Wooldridge and Dunne (Artifi. Intell. 2006) studied the classical computational complexity of several natural decision problems in Coalitional Resource Games (CRG) - games in which each agent is endowed with a set of resources and coalitions can bring about a set of goals if they are collectively endowed with the necessary amount of resources. The input of coalitional resource games bundles together several elements, e.g., the agent set Ag, the goal set G, the resource set R, etc. Shrot et al. (AAMAS 2009) examine coalition formation problems in the CRG model using the theory of Parameterized Complexity. Their refined analysis shows that not all parts of input act equal - some instances of the problem are indeed tractable while others still remain intractable.We answer an important question left open by Shrot, Aumann,and Kraus by showing that the SC Problem (checking whether a Coalition is Successful) is W[1]-hard when parameterized by the size of the coalition. Then via a single theme of reduction from SC, we are able to show that various problems related to resources, resource bounds, and resource conflicts introduced by Wooldridge et al. are (i) W[1]-hard or co-W[1]-hard w.r.t the size of the coalition; and (ii) Para-NP hard or co-Para-NP-hard w.r.t |R|. When parameterized by |G| or |R| + |Ag|, we give a general algorithm which proves that these problems are indeed tractable.