Accepted Papers

Invited Speaker

We are honored to have Prof. Yevgeniy Vorobeychik as our invited speaker at CoopMAS; talk details below.

Towards Robust Collective Decision Making

Collective decision making is a problem of fundamental importance in multi agent systems. This problem exhibits a multitude of conceptual and technical challenges. In this talk, I focus on three of these:

  1. robust decentralized coordination
  2. robust social choice, and
  3. robust team (coalition) formation.
In the first, we consider a setting in which individuals (human subjects) situated on a network aim to achieve global consensus on a decision using only local information. We start by studying the added value of communication in achieving consensus, finding, surprisingly, that local communication fails to improve performance, while constraining communication to simple summaries of local state is helpful. We further show that decentralized coordination on networks is highly susceptible to adversarial manipulation even when very few adversaries are present. We show that adding "trusted" nodes is only marginally helpful, and, surprisingly, can even be harmful.

Considering the issue of robust social choice, we investigate the problem of group-level election control and protection. We model optimal protection of elections as a Stackelberg game in which the defender, who aims to preserve election integrity by deploying limited resources to protecting voter groups, while an adversary aims to subvert the election by attacking these groups. We show how this problem can be addressed in a scalable manner using linear programming combined with a double-oracle method, with oracles representing the best-response sub-problems for both the attacker and defender.

Our final foray is into hedonic coalition (or team) formation, where we focus on maintaining incentives to honestly reveal preferences while achieving a series of important properties, such as efficiency and equity. Our first contribution is in defining a novel property of IMS (iterative matching of soulmates), which we view as a fundamental criterion in team formation. We show that implemeting IMS has several important side-effects, some economic (such as strong incentive compatibility and core uniqueness on restricted preference domains), others computational. We also exhibit a novel mechanism implementing IMS which is also Pareto efficient and individually rational, and has remarkably good empirical incentive and equity properties.

Program Schedule

  • 14:30 - 14:55
    M. Chakraborty, P. Chua, S. Das and B. Juba - Coordinated Versus Decentralized Exploration In Multi-Agent Multi-Armed Bandits
    In this paper, we introduce a multi-agent multi-armed bandit- based model for ad hoc teamwork with expensive communication. The goal of the team is to maximize the total reward gained from pulling arms of a bandit over a number of epochs. In each epoch, each agent decides whether to pull an arm and hence collect a reward, or to broadcast the reward it obtained in the previous epoch to the team and forgo pulling an arm. These decisions must be made only on the basis of her private information and the public information broadcast prior to that epoch. We first benchmark the achievable utility by analyzing an idealized ver- sion of this problem where a central authority has complete knowledge of rewards acquired from all arms in all epochs and uses a multiplica- tive weights update algorithm for deciding which arm to pull. We then introduce a value-of-information based strategy based on the centralized algorithm for making broadcasts in the decentralized setting, and show experimentally that the algorithm converges rapidly to the performance of the centralized method.
  • 14:55 - 15:20
    J. Lou, M. Van der Linden, P. Batra, C. Hajaj, G. Leo, Y. Vorobeychik and M. Wooders - Rotating Proposer Mechanisms for Team Formation
    We consider the problem of partitioning a collection of individuals, endowed with hedonic preferences, into teams (coalitions). First, we study this setting through the lens of a complete information non-cooperative sequential team formation game in which players iteratively recommend teams, which are either accepted or rejected by their prospective members. We show that in this game there always exists a subgame perfect equilibrium in which all team proposals are accepted. Next, we consider team formation as a mechanism design problem, where a center takes a profile of hedonic preferences (which are now private to the players) as input, and returns a partition of players into teams.We introduce a novel class of mechanisms which implement an “always-accept” equilibrium of the corresponding team formation game. We show that these mechanisms are individually rational (IR), and implement iterative matching of soulmates (IMS), an important property in which mutually-preferred teams are always formed. Moreover, we exhibit a subclass of mechanisms, rotating proposer mechanisms (RPM), which are also Pareto efficient. Remarkably, the resulting mechanisms are the first known team formation mechanisms to satisfy these three properties; indeed, this is the case even for the well-known roommate problem (teams of at most 2). While the mechanism is not stable or incentive compatible in general, we show that both these properties hold on an important restricted domain of preferences, and experimentally demonstrate more generally that few players can ever benefit from lying. A major shortcoming of RPM is implementation complexity. We address it by a combination of pruning strategies, and heuristics to compute an approximate subgame perfect equilibrium. Experimentally, we demonstrate that the resulting approximate RPM (which is still IR and implements IMS) remains approximately truthful, and significantly outperforms several known alternatives in terms of social welfare and fairness.
  • 15:20 - 15:35
    A. Igarashi and D. M. Roijers - Multi-Criteria Coalition Formation Games
    When forming coalitions, agents have different utilities per coalition. Game-theoretic approaches typically assume that the scalar utility for each agent for each coalition is public information. However, we argue that this is not a realistic assumption, as agents may not want to divulge this information or are even incapable of expressing it. To mitigate this, we propose the multi-criteria coalition formation game model, in which there are different publicly available quality metrics (corresponding to different criteria or objectives) for which a value is publicly available for each coalition. The agents have private utility functions that determine their preferences with respect to these criteria, and thus also with respect to the different coalitions. Assuming that we can ask agents to compare two coalitions, we propose a heuristic algorithm for finding stable partitions in MC2FGs: local stability search (LSS). We show that while theoretically individually stable partitions need not exist in MC2FGs in general, empirically stable partitions can be found. Furthermore, we show that we can find individually stable partitions after asking only a small number of comparisons, which is highly important when we want to apply this model in practice.
  • 15:35 - 16:00
    A. Perrault and C. Boutilier - Multiple-Profile Prediction-of-Use Games
    Prediction-of-use (POU) games [18] address the mismatch between energy supplier costs and the incentives imposed on consumers by fixed-rate electricity tariffs. However, the framework does not address how consumers should coordinate to maximize social welfare. To address this, we develop MPOU games, an extension of POU games in which agents report multiple acceptable electricity use profiles. We show that MPOU games share many attractive properties with POU games (e.g., convexity). Despite this, MPOU games introduce new incentive issues that prevent the consequences of convexity from being exploited directly, a problem we analyze and resolve. We validate our approach with experimental results using utility models learned from real electricity use data.
  • 16:00 - 16:25
    A. Igarashi, R. Bredereck, D. Peters and Edith Elkind - Group Activity Selection on Social Networks
    We propose a new variant of the group activity selection problem (GASP), where the agents are placed on a social network and activities can only be assigned to connected subgroups. We show that if multiple groups can simultaneously engage in the same activity, finding a stable outcome is easy as long as the network is acyclic. In contrast, if each activity can be assigned to a single group only, finding stable outcomes becomes computationally intractable, even if the underlying network is very simple: the problem of determining whether a given instance of a GASP admits a Nash stable outcome turns out to be NP-hard when the social network is a path, a star, or if the size of each connected component is bounded by a constant. We then study the parameterized complexity of finding outcomes of gGASP that are Nash stable, individually stable or core stable. For the parameter ‘number of activities’, we propose an FPT algorithm for Nash stability for the case where the social network is acyclic and obtain a W[1]-hardness result for cliques (i.e., for classic GASP); similar results hold for individual stability. In contrast, finding a core stable outcome is hard even if the number of activities is bounded by a small constant, both for classic GASP and when the social network is a star. For the parameter ‘number of players’, all problems we consider are in XP for arbitrary social networks; on the other hand, we prove W[1]-hardness results with respect to the parameter ‘number of players’ for the case where the social network is a clique (i.e., for classic GASP).

    The talk by J. Low and T. Rahwan - Efficient Synergy Computation under MC-Nets, is cancelled due to unforseen circumstances

  • 16:30 - 17:00
    Coffee Break
  • 17:00 - 17:25
    Y. Yang and D. Dimitrov - The Complexity of Shelflisting
    Optimal shelflisting invites profit maximization to become sensitive to the ways in which purchasing decisions are order-dependent. We study the computational complexity of the corresponding product arrangement problem when consumers are either rational maximizers, use a satisfying procedure, or apply successive choice. The complexity results we report are shown to crucially depend on the size of the top cycle in consumers' preferences over products and on the direction in which alternatives on the shelf are encountered.
  • 17:25 - 18:25
    Invited Talk - Yevgeniy Vorobeychik
  • 18:25 - 18:30
    CoopMAS 2017 Concludes