Various representations and inference methods have been proposed for lifted probabilistic inference in relational models. Many of these methods choose an order to eliminate (or branch on) the parameterized random variables. Similar to such methods for non-relational probabilistic inference, the order of elimination has a significant role in the performance of the algorithms. Since finding the best order is NP-complete even for non-relational models, heuristics have been proposed to find good orderings in the non-relational models. In this paper, we show that these heuristics are inefficient for relational models, because they fail to consider the population sizes associated with logical variables. We extend existing heuristics for non-relational models and propose new heuristics for relational models. We evaluate the existing and new heuristics on a range of generated relational graphs.

We consider settings where a collective intelligence is formed by aggregating information contributed from many independent agents, such as product reviews, community sensing, or opinion polls. We propose a novel mechanism that elicits both private signals and beliefs. The mechanism extends the previous versions of the Bayesian Truth Serum (the original BTS, the RBTS, and the multi-valued BTS), by allowing small populations and non-binary private signals, while not requiring additional assumptions on the belief updating process. For priors that are sufficiently smooth, such as Gaussians, the mechanism allows signals to be continuous.

We investigate synergy, or lack thereof, between agents in cooperative games, building on the popular notion of Shapley value. We think of a pair of agents as synergistic (resp., antagonistic) if the Shapley value of one agent when the other agent participates in a joint effort is higher (resp. lower) than when the other agent does not participate. Our main theoretical result is that any graph specifying synergistic and antagonistic pairs can arise even from a restricted class of cooperative games. We also study the computational complexity of determining whether a given pair of agents is synergistic. Finally, we use the concepts developed in the paper to uncover the structure of synergies in two real-world organizations, the European Union and the International Monetary Fund.

Mobile geo-location advertising, where mobile ads are targeted based on a user’s location, has been identified as a key growth factor for the mobile market. As with online advertising, a crucial ingredient for their success is the development of effective economic mechanisms. An important difference is that mobile ads are shown sequentially over time and information about the user can be learned based on their movements. Furthermore, ads need to be shown selectively to prevent ad fatigue. To this end, we introduce, for the first time, a user model and suitable economic mechanisms which take these factors into account. Specifically, we design two truthful mechanisms which produce an advertisement plan based on the user’s movements. One mechanism is allocatively efficient, but requires exponential compute time in the worst case. The other requires polynomial time, but is not allocatively efficient. Finally, we experimentally evaluate the trade off between compute time and efficiency of our mechanisms.

Examples range from multiagent planning, That is, we look for the most representative voter and return to crowdsourcing and human computation, to collaborative her ballot as the outcome. In our example, a natural choice filtering for recommender systems, to rank aggregation would be any of the voters voting (0, 1, 1). The distance of for search engines, to coordination and resource allocation this choice to the individual ballots is 42 (21 voters disagree in multiagent systems. Several frameworks have been on 2 issues each), i.e., this solution is only marginally worse proposed in the literature on computational social choice than the solution returned by the distance-based rule--and it (Chevaleyre et al. 2007; Brandt, Conitzer, and Endriss 2013) is optimal in case (1, 1, 1) is infeasible.

Structured preference domains, such as, for example, the domains of single-peaked and single-crossing preferences, are known to admit efficient algorithms for many problems in computational social choice. Some of these algorithms extend to preferences that are close to having the respective structural property, i.e., can be made to enjoy this property by performing minor changes to voters' preferences, such as deleting a small number of voters or candidates. However, it has recently been shown that finding the optimal number of voters or candidates to delete in order to achieve the desired structural property is NP-hard for many such domains. In this paper, we show that these problems admit efficient approximation algorithms. Our results apply to all domains that can be characterized in terms of forbidden configurations; this includes, in particular, single-peaked and single-crossing elections. For a large range of scenarios, our approximation results are optimal under a plausible complexity-theoretic assumption. We also provide parameterized complexity results for this class of problems.

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.

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.