An important subclass of social choice functions, so-called majoritarian (or C1) functions, only take into account the pairwise majority relation between alternatives. In the absence of majority ties--e.g., when there is an odd number of agents with linear preferences--the majority relation is antisymmetric and complete and can thus conveniently be represented by a tournament. Tournaments have a rich mathematical theory and many formal results for majoritarian functions assume that the majority relation constitutes a tournament. Moreover, most majoritarian functions have only been defined for tournaments and allow for a variety of generalizations to unrestricted preference profiles, none of which can be seen as the unequivocal extension of the original function. In this paper, we argue that restricting attention to tournaments is justified by the existence of a conservative extension, which inherits most of the commonly considered properties from its underlying tournament solution.

Most work building on the Stackelberg security games model assumes that the attacker can perfectly observe the defender's randomized assignment of resources to targets. This assumption has been challenged by recent papers, which designed tailor-made algorithms that compute optimal defender strategies for security games with limited surveillance. We analytically demonstrate that in zero-sum security games, lazy defenders, who simply keep optimizing against perfectly informed attackers, are almost optimal against diligent attackers, who go to the effort of gathering a reasonable number of observations. This result implies that, in some realistic situations, limited surveillance may not need to be explicitly addressed.

We introduce the simultaneous model for cake cutting (the fair allocation of a divisible good), in which agents simultaneously send messages containing a sketch of their preferences over the cake. We show that this model enables the computation of divisions that satisfy proportionality -- a popular fairness notion -- using a protocol that circumvents a standard lower bound via parallel information elicitation. Cake divisions satisfying another prominent fairness notion, envy-freeness, are impossible to compute in the simultaneous model, but admit arbitrarily good approximations.

The probabilistic serial rule is one of the most well-established and desirable rules for the random assignment problem. We present the egalitarian simultaneous reservation social decision scheme – an extension of probabilistic serial to the more general setting of randomized social choice. We consider various desirable fairness, efficiency, and strategic properties of social decision schemes and show that egalitarian simultaneous reservation compares favorably against existing rules. Finally, we define a more general class of social decision schemes called simultaneous reservation, that contains egalitarian simultaneous reservation as well as the serial dictatorship rules. We show that outcomes of simultaneous reservation characterize efficiency with respect to a natural refinement of stochastic dominance.

Balanced knockout tournaments are one of the most common formats for sports competitions, and are also used in elections and decision-making. We consider the computational problem of finding the optimal draw for a particular player in such a tournament. The problem has generated considerable research within AI in recent years. We prove that checking whether there exists a draw in which a player wins is NP-complete, thereby settling an outstanding open problem. Our main result has a number of interesting implications on related counting and approximation problems. We present a memoization-based algorithm for the problem that is faster than previous approaches. Moreover, we highlight two natural cases that can be solved in polynomial time. All of our results also hold for the more general problem of counting the number of draws in which a given player is the winner.

The growing Electric Vehicles' (EVs) popularity among commuters creates new challenges for the smart grid. The most important of them is the uncoordinated EV charging that substantially increases the energy demand peaks, putting the smart grid under constant strain. In order to cope with these peaks the grid needs extra infrastructure, a costly solution. We propose an Adaptive Management of EV Storage (AMEVS) algorithm, implemented through a learning agent that acts on behalf of individual EV owners and schedules EV charging over a weekly horizon. It accounts for individual preferences so that mobility service is not violated but also individual benefit is maximized. We observe that it reshapes the energy demand making it less volatile so that fewer resources are needed to cover peaks. It assumes Vehicle-to-Grid discharging when the customer has excess capacity. Our agent uses Reinforcement Learning trained on real world data to learn individual household consumption behavior and to schedule EV charging. Unlike previous work, AMEVS is a fully distributed approach. We show that AMEVS achieves significant reshaping of the energy demand curve and peak reduction, which is correlated with customer preferences regarding perceived utility of energy availability. Additionally, we show that the average and peak energy prices are reduced as a result of smarter energy use.

Scoring involves the compression of a number of quantitative attributes into a single meaningful value. We consider the problem of how to generate scores in a setting where they should be weakly monotone (either non-increasing or non-decreasing) in their dimensions. Our approach allows an expert to score an arbitrary set of points to produce meaningful, continuous, monotone scores over the entire domain, while exactly interpolating through those inputs. In contrast, existing monotone interpolating methods only work in two dimensions and typically require exhaustive grid input. Our technique significantly lowers the bar to score creation, allowing domain experts to develop mathematically coherent scores. The method is used in practice to create the LEED Performance scores that gauge building sustainability.

In this paper, we discuss a computational approach to the cognitivetask of social planning. First, we specify a class of planningproblems that involve an agent who attempts to achieve its goalsby altering other agents' mental states. Next, we describe SFPS,a flexible problem solver that generates social plans of this sort,including ones that include deception and reasoning about otheragents' beliefs. We report the results for experiments on socialscenarios that involve different levels of sophistication and thatdemonstrate both SFPS's capabilities and the sources of its power.Finally, we discuss how our approach to social planning has beeninformed by earlier work in the area and propose directions foradditional research on the topic.

Our research aims at building interactive robots and agents that can expand their knowledge by interacting with human users. In this paper, we focus on learning goal-oriented tasks from situated interactive instructions. Learning the structure of novel tasks and how to execute them is a challenging computational problem requiring the agent to acquire a variety of knowledge including goal definitions and hierarchical control information. We frame acquisition of novel tasks as an explanation-based learning (EBL) problem and propose an interactive learning variant of EBL for a robotic agent. We show that our approach can exploit information in situated instructions along with the domain knowledge to demonstrate fast generalization on several tasks. The knowledge acquired transfers across structurally similar tasks. Finally, we show that our approach seamlessly combines agent-driven exploration with instructions for mixed-initiative learning.

This paper presents an agent-based model that studies the emergence and evolution of a language system of logical constructions, i.e. a vocabulary and a set of grammatical constructions that allow the expression of logical combinations of categories. The model assumes the agents have a common vocabulary for basic categories, the ability to construct logical combinations of categories using Boolean functions, and some general purpose cognitive capacities for invention, adoption, induction and adaptation. But it does not assume the agents have a vocabulary for Boolean functions nor grammatical constructions for expressing such logical combinations of categories through language. The results of the experiments we have performed show that a language system of logical constructions emerges as a result of a process of self-organisation of the individual agents' interactions when these agents adapt their preferences for vocabulary and grammatical constructions to those they observe are used more often by the rest of the population, and that such a language system is transmitted from one generation to the next.