Voting rules are powerful tools that allow multiple agents to aggregate their preferences in order to reach joint decisions. A common flaw of some voting rules, known as the no-show paradox, is that agents may obtain a more preferred outcome by abstaining from an election. We study strategic abstention for set-valued voting rules based on Kelly's and Fishburn's preference extensions. Our contribution is twofold. First, we show that, whenever there are at least five alternatives, every Pareto-optimal majoritarian voting rule suffers from the no-show paradox with respect to Fishburn's extension. This is achieved by reducing the statement to a finite---yet very large---problem, which is encoded as a formula in propositional logic and then shown to be unsatisfiable by a SAT solver. We also provide a human-readable proof which we extracted from a minimal unsatisfiable core of the formula. Secondly, we prove that every voting rule that satisfies two natural conditions cannot be manipulated by strategic abstention with respect to Kelly's extension. We conclude by giving examples of well-known Pareto-optimal majoritarian voting rules that meet these requirements.

We consider the design and enactment of multiagent protocols that describe collaboration using "normative" or "social" abstractions, specifically, commitments. A (multiagent) protocol defines the relevant social states and how they progress; each participant maintains a local projection of these states and acts accordingly. Protocols expose two important challenges: (1) how to compose them in a way that respects commitments and (2) how to verify the compliance of the parties with the social states. Individually, these challenges are inadequately studied and together not at all. We motivate the notion of a social context to capture how a protocol may be enacted. A protocol can be verifiably enacted when its participants can determine each other's compliance. We first show the negative result that even when protocols can be verifiably enacted in respective social contexts, their composition cannot be verifiably enacted in the composition of those social contexts. We next show how to expand such a protocol so that it can be verifiably enacted. Our approach involves design rules to specify composite protocols so they would be verifiably enactable. Our approach demonstrates a use of dialectical commitments, which have previously been overlooked in the protocols literature.

Costly preference elicitation has also been studied The last two decades have seen a growing interest in the setting of auctions; notably by Conen and Sandholm in the development of automated agents that are [2001] and Parkes [2005]. These works are primarily able to negotiate on the user's behalf. When representing aimed at designing mechanisms that can avoid unnecessary a user in a negotiation, it is essential for the elicitation. Costly preference elicitation may alternatively be agent to understand the user's preferences, without cast as a problem in which agents have to allocate costly computational exposing them to elicitation fatigue. To this end, we resources to compute their valuation [Larson and propose a new model in which a negotiating agent Sandholm, 2001], but this work focuses on interactions between may incrementally elicit the user's preference during different strategies.

The bioinformatics is an interdisciplinary area of study where one of the objectives is to deal with the analysis and interpretation of large sets of data generated from various large-scale biological experiments. The example of one such large-scale biological experiment is measuring the expression levels of tens of thousands of genes simultaneously under some environmental condition. Microarray is one of the essential technologies used by the biologist to measure genome-wide expression levels of genes in a particular organism. As microarrays technologies have become more prevalent, the challenges 1 associated with collecting, managing, and analyzing the data from each experiment have essentially increased. Robust laboratory protocols, improved understanding of the complex experimental design and falling prices of commercial platforms, all these have combined to drive the field to more complex experiments, generating huge amounts of data (Brazma and Vilo, 2000).

Autonomous mobility on demand systems, though still in their infancy, have very promising prospects in providing urban population with sustainable and safe personal mobility in the near future. While much research has been conducted on both autonomous vehicles and mobility on demand systems, to the best of our knowledge, this is the first work that shows how to manage autonomous mobility on demand systems for better passenger experience. We introduce the Expand and Target algorithm which can be easily integrated with three different scheduling strategies for dispatching autonomous vehicles. We implement an agent-based simulation platform and empirically evaluate the proposed approaches with the New York City taxi data. Experimental results demonstrate that the algorithm significantly improve passengers' experience by reducing the average passenger waiting time by up to 29.82% and increasing the trip success rate by up to 7.65%.

Decentralized POMDPs provide an expressive framework for multiagent sequential decision making. However, the complexity of these models---NEXP-Complete even for two agents---has limited their scalability. We present a promising new class of approximation algorithms by developing novel connections between multiagent planning and machine learning. We show how the multiagent planning problem can be reformulated as inference in a mixture of dynamic Bayesian networks (DBNs). This planning-as-inference approach paves the way for the application of efficient inference techniques in DBNs to multiagent decision making. To further improve scalability, we identify certain conditions that are sufficient to extend the approach to multiagent systems with dozens of agents. Specifically, we show that the necessary inference within the expectation-maximization framework can be decomposed into processes that often involve a small subset of agents, thereby facilitating scalability. We further show that a number of existing multiagent planning models satisfy these conditions. Experiments on large planning benchmarks confirm the benefits of our approach in terms of runtime and scalability with respect to existing techniques.

A linear function submission-based double-auction (LFS-DA) mechanism for a regional electricity network is proposed in this paper. Each agent in the network is equipped with a battery and a generator. Each agent simultaneously becomes a producer and consumer of electricity, i.e., a prosumer and trades electricity in the regional market at a variable price. In the LFS-DA, each agent uses linear demand and supply functions when they submit bids and asks to an auctioneer in the regional market.The LFS-DA can achieve an exact balance between electricity demand and supply for each time slot throughout the learning phase and was shown capable of solving the primal problem of maximizing the social welfare of the network without any central price setter, e.g., a utility or a large electricity company, in contrast with conventional real-time pricing (RTP). This paper presents a clarification of the relationship between the RTP algorithm derived on the basis of a dual decomposition framework and LFS-DA. Specifically, we proved that the changes in the price profile of the LFS-DA mechanism are equal to those achieved by the RTP mechanism derived from the dual decomposition framework except for a constant factor.

The article introduces a ceteris paribus modal logic, called CP, interpreted on the equivalence classes induced by finite sets of propositional atoms. This logic is studied and then used to embed three logics of strategic interaction, namely atemporal STIT, the coalition logic of propositional control (CL PC) and the starless fragment of the dynamic logic of propositional assignments (DL PA). The embeddings highlight a common ceteris paribus structure underpinning the key operators of all these apparently very different logics and show, we argue, remarkable similarities behind some of the most influential formalisms for reasoning about strategic interaction.

Multi-agent path-finding (MAPF) is important for applications such as the kind of warehousing done by Kiva systems. Solving the problem optimally is NP-hard, yet finding low-cost solutions is important. Bounded-suboptimal MAPF algorithms, such as enhanced conflict-based search (ECBS), often do not perform well in warehousing domains with many agents. We therefore develop bounded-suboptimal MAPF algorithms, called CBS+HWY and ECBS+HWY, that exploit the problem structure of a given MAPF instance by finding paths for the agents that include edges from user-provided highways, which encourages a global behavior of the agents that avoids collisions. On the theoretical side, we develop a simple approach that uses highways for MAPF and provides suboptimality guarantees. On the experimental side, we demonstrate that ECBS+HWY can decrease the runtimes and solution costs of ECBS in Kiva-like domains with many agents if the highways capture the problem structures well.

Conflict-Based Search (CBS) and its generalization, Meta-Agent CBS are amongst the strongest newly introduced algorithms for Multi-Agent Path Finding. This paper introduces ICBS, an improved version of CBS. ICBS incorporates three orthogonal improvements to CBS which are systematically described and studied. Experimental results show that each of these improvements reduces the runtime over basic CBS by up to 20x in many cases. When all three improvements are combined, an even larger improvement is achieved, producing state-ofthe art results for a number of domains.