Computational complexity of voting manipulation is one of the most actively studied topics in the area of computational social choice, starting with the groundbreaking work of [Bartholdi et al., 1989]. Most of the existing work in this area, including that of [Bartholdi et al., 1989], implicitly assumes that whenever several candidates receive the top score with respect to the given voting rule, the resulting tie is broken according to a lexicographic ordering over the candidates. However, till recently, an equally appealing method of tiebreaking, namely, selecting the winner uniformly at random among all tied candidates, has not been considered in the computational social choice literature. The first paper to analyze the complexity of voting manipulation under randomized tiebreaking is [Obraztsova et al., 2011], where the authors provide polynomial-time algorithms for this problem under scoring rules and—under an additional assumption on the manipulator’s utilities—for Maximin. In this paper, we extend the results of [Obraztsova et al., 2011] by showing that finding an optimal vote under randomized tie-breaking is computationally hard for Copeland and Maximin (with general utilities), as well as for STV and Ranked Pairs, but easy for the Bucklin rule and Plurality with Runoff.

Distributed constraint optimization problems (DCOPs) are a model for representing multi-agent systems in which agents cooperate to optimize a global objective. The DCOP model has two main advantages: it can represent a wide range of problem domains, and it supports the development of generic algorithms to solve them. Firstly, this paper presents some advances in both complete and approximate DCOP algorithms. Secondly, it explains that the DCOP model makes a number of unrealistic assumptions that severely limit its range of application. Finally, it points out hints on how to tackle such limitations.

Multiagent planning has seen much progress with the development of formal models such as Dec-POMDPs. However, the complexity of these models—NEXP-Complete even for two agents—has limited scalability. We identify certain mild conditions that are sufficient to make multiagent planning amenable to a scalable approximation w.r.t. the number of agents. This is achieved by constructing a graphical model in which likelihood maximization is equivalent to plan optimization. Using the Expectation-Maximization framework for likelihood maximization, we show that the necessary inference can be decomposed into processes that often involve a small subset of agents, thereby facilitating scalability. We derive a global update rule that combines these local inferences to monotonically increase the overall solution quality. Experiments on a large multiagent planning benchmark confirm the benefits of the new approach in terms of runtime and scalability.

Slinko and White, (2008) have recently introduced a new model of coalitional manipulation of voting rules under limited communication, which they call safe strategic voting. The computational aspects of this model were first studied by Hazon and Elkind, (2010), who provide polynomial-time algorithms for finding a safe strategic vote under k-approval and the Bucklin rule. In this paper, we answer an open question of Hazon and Elkind, (2010) by presenting a polynomial-time algorithm for finding a safe strategic vote under the Borda rule. Our results for Borda generalize to several interesting classes of scoring rules.

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?

A systematic study on the abstract level is the first step towards algorithms that solve the problem. We show that different semantics of ability in ATL Ultimately, we show that what agents can achieve is more give rise to different validity sets. As a consequence, sensitive to the strategic model of an agent (and a precise notion different notions of ability induce different of achievement) than it was generally realized. No less strategic logics and different general properties importantly, our study reveals that some natural properties - of games. Moreover, the study can be seen as the usually taken for granted when reasoning about action - may first systematic step towards satisfiability-checking cease to be universally true if we change the strategic setting.

Continuous state DEC-MDPs are critical for agent teams in domains involving resources such as time, but scaling them up is a significant challenge. To meet this challenge, we first introduce a novel continuous-time DEC-MDP model that exploits transition independence in domains with temporal constraints. Moreimportantly, we present a new locally optimal algorithm called SPAC. Compared to the best previous algorithm, SPAC finds solutions of comparable quality substantially faster; SPAC also scales to larger teams of agents.

We propose a novel online planning algorithm for ad hoc team settings — challenging situations in which an agent must collaborate with unknown teammates without prior coordination. Our approach is based on constructing and solving a series of stage games, and then using biased adaptive play to choose actions. The utility function in each stage game is estimated via Monte-Carlo tree search using the UCT algorithm. We establish analytically the convergence of the algorithm and show that it performs well in a variety of ad hoc team domains.

Temporal regulations are needed to express commitments The proposal of Elisa Marengo's thesis is to extend to achieve something and in a specified order. For commitment protocols in order to (i) allow for expressing instance, an insurance company commits to paying an innetwork commitments to temporal regulations, and surgeon for a procedure only after a covered patient (ii) to supply a tool for expressing laws, conventions has undergone the procedure. Patterns of interaction, instead, and the like, in order to specify legal interactions.

We develop a general framework for social choice problems in which a limited number of alternatives can be recommended to an agent population. In our budgeted social choice model, this limit is determined by a budget, capturing problems that arise naturally in a variety of contexts, and spanning the continuum from pure consensus decision making (i.e., standard social choice) to fully personalized recommendation. Our approach applies a form of segmentation to social choice problems— requiring the selection of diverse options tailored to different agent types—and generalizes certain multi-winner election schemes. We show that standard rank aggregation methods perform poorly, and that optimization in our model is NP-complete; but we develop fast greedy algorithms with some theoretical guarantees. Experiments on real-world datasets demonstrate the effectiveness of our algorithms.