In this work we evaluate the performance of a policy shaping algorithm using 26 human teachers. We examine if the algorithm is suitable for human-generated data on two different boards in a pac-man domain, comparing performance to an oracle that provides critique based on one known winning policy. Perhaps surprisingly, we show that the data generated by our 26 participants yields even better performance for the agent than data generated by the oracle. This might be because humans do not discourage exploring multiple winning policies. Additionally, we evaluate the impact of different verbal instructions, and different interpretations of silence, finding that the usefulness of data is affected both by what instructions is given to teachers, and how the data is interpreted.

Multi-robot inverse reinforcement learning (mIRL) is broadly useful for learning, from observations, the behaviors of multiple robots executing fixed trajectories and interacting with each other. In this paper, we relax a crucial assumption in IRL to make it better suited for wider robotic applications: we allow the transition functions of other robots to be stochastic and do not assume that the transition error probabilities are known to the learner. Challenged by occlusion where large portions of others' state spaces are fully hidden, we present a new approach that maps stochastic transitions to distributions over features. Then, the underconstrained problem is solved using nonlinear optimization that maximizes entropy to learn the transition function of each robot from occluded observations. Our methods represent significant and first steps toward making mIRL pragmatic.

We present a new model that describes the process of electing a group of representatives (e.g., a parliament) for a group of voters. In this model, called the voting committee model, the elected group of representatives runs a number of ballots to make final decisions regarding various issues. The satisfaction of voters comes from the final decisions made by the elected committee. Our results suggest that depending on a single-winner election system used by the committee to make these final decisions, different multi-winner election rules are most suitable for electing the committee. Furthermore, we show that if we allow not only a committee, but also an election rule used to make final decisions, to depend on the voters' preferences, we can obtain an even better representation of the voters.

In this paper we investigate the model-checking problem of pushdown multi-agent systems for ATL* specifications.To this aim, we introduce pushdown game structures over which ATL* formulas are interpreted. We show an algorithm that solves the addressed model-checking problem in 3ExpTime. We also provide a 2ExpSpace lower bound by showing a reduction from the word acceptance problem for deterministic Turing machines with doubly exponential space.

The margin of victory of an election is a useful measure to capture the robustness of an election outcome. It also plays a crucial role in determining the sample size of various algorithms in post election audit, polling etc. In this work, we present efficient sampling based algorithms for estimating the margin of victory of elections. More formally, we introduce the (c, ε, δ)–MARGIN OF VICTORY problem, where given an election E on n voters, the goal is to estimate the margin of victory M(E) of E within an additive factor of cM(E)+εn. We study the (c, ε, δ)–MARGIN OF VICTORY problem for many commonly used voting rules including scoring rules, approval, Bucklin, maximin, and Copelandα. We observe that even for the voting rules for which computing the margin of victory is NP-Hard, there may exist efficient sampling based algorithms, as observed in the cases of maximin and Copelandα voting rules.

We consider the computational complexity of computing welfare maximizing partitions for fractional hedonic games — a natural class of coalition formation games that can be succinctly represented by a graph. For such games, welfare maximizing partitions constitute desirable ways to cluster the vertices of the graph. We present both intractability results and approximation algorithms for computing welfare maximizing partitions.

In this paper we study the exchange of indivisible objects where agents’ possible preferences over the objects are strict and share a common structure among all of them, which represents a certain level of asymmetry among objects. A typical example of such an exchange model is a re-scheduling of tasks over several processors, since all task owners are naturally assumed to prefer that their tasks are assigned to fast processors rather than slow ones. We focus on designing exchange rules (a.k.a.mechanisms) that simultaneously satisfy strategyproofness, individual rationality, and Pareto efficiency. We first provide a general impossibility result for agents’ preferences that are determined in an additive manner, and then show an existence of such an exchange rule for further restricted lexicographic preferences. We finally find that for the restricted case, a previously known equivalence between the single-valuedness of the strict core and the existence of such an exchange rule does not carry over.

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.

Online multi-task learning is an important capability for lifelong learning agents, enabling them to acquire models for diverse tasks over time and rapidly learn new tasks by building upon prior experience. However, recent progress toward lifelong reinforcement learning (RL) has been limited to learning from within a single task domain. For truly versatile lifelong learning, the agent must be able to autonomously transfer knowledge between different task domains. A few methods for cross-domain transfer have been developed, but these methods are computationally inefficient for scenarios where the agent must learn tasks consecutively. In this paper, we develop the first cross-domain lifelong RL framework. Our approach efficiently optimizes a shared repository of transferable knowledge and learns projection matrices that specialize that knowledge to different task domains. We provide rigorous theoretical guarantees on the stability of this approach, and empirically evaluate its performance on diverse dynamical systems. Our results show that the proposed method can learn effectively from interleaved task domains and rapidly acquire high performance in new domains.

In 1990, Thomas Schwartz proposed the conjecture that every nonempty tournament has a unique minimal TEQ-retentive set (TEQ stands for tournament equilibrium set). A weak variant of Schwartz's Conjecture was recently proposed by Felix Brandt. However, both conjectures were disproved very recently by two counterexamples. In this paper, we prove sufficient conditions for infinite classes of tournaments that satisfy Schwartz's Conjecture and Brandt's Conjecture. Moreover, we prove that TEQ can be calculated in polynomial time in several infinite classes of tournaments. Furthermore, our results reveal some structures that are forbidden in every counterexample to Schwartz's Conjecture.