New Zealand


Following Zhang and Grossi~(AAAI 2021), we study in more depth a variant of weighted voting games in which agents&#39; weights are induced by a transitive support structure. 
This class of simple games is notably well suited to study the relative importance of agents in the liquid democracy framework. We first propose a pseudo-polynomial time algorithm to compute the Banzhaf and Shapley-Shubik indices for this class of game. Then, we study a bribery problem, in which one tries to maximize/minimize the voting power/weight of a given agent by changing the support structure under a budget constraint. We show that these problems are computationally hard and provide several parameterized complexity results.

AAMAS 2022

Computation and Bribery of Voting Power in Delegative Simple Games

manipulation problems

voting power measurement

liquid democracy

AAMAS (International Conference on Autonomous Agents and Multiagent Systems) is the largest and most influential conference in the area of agents and multiagent systems. The aim of the conference is to bring together researchers and practitioners in all areas of agent technology and to provide a single, high-profile, internationally renowned forum for research in the theory and practice of autonomous agents and multiagent systems. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

The AAMAS conference series was initiated in 2002 in Bologna, Italy as a joint event comprising the 6th International Conference on Autonomous Agents (AA), the 5th International Conference on Multiagent Systems (ICMAS), and the 9th International Workshop on Agent Theories, Architectures, and Languages (ATAL).

Subsequent AAMAS conferences have been held in Melbourne, Australia (July 2003), New York City, NY, USA (July 2004), Utrecht, The Netherlands (July 2005), Hakodate, Japan (May 2006), Honolulu, Hawaii, USA (May 2007), Estoril, Portugal (May 2008), Budapest, Hungary (May 2009), Toronto, Canada (May 2010), Taipei, Taiwan (May 2011), Valencia, Spain (June 2012), Minnesota, USA (May 2013), Paris, France (May 2014), Istanbul, Turkey (May 2015), Singapore (May 2016), São Paulo (2017) and Stockholm, Sweden (2018), Montreal (May 2019), Auckland (May 2020, Virtual), London (May 2021, Virtual).
<br>
<br>



A ticket is required to attend this event, please register using the link below:

https://aamas2022-conference.auckland.ac.nz/attending/registration/

Registration Is Required

AAMAS (International Conference on Autonomous Agents and Multiagent Systems) is the largest and most influential conference in the area of agents and multiagent systems. The aim of the conference is to bring together researchers and practitioners in all areas of agent technology and to provide a single, high-profile, internationally renowned forum for research in the theory and practice of autonomous agents and multiagent systems. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).


Following Zhang and Grossi~(AAAI 2021), we study in more depth a variant of weighted voting games in which agents' weights are induced by a transitive support structure. 
This class of simple games is notably well suited to study the relative importance of agents in the liquid democracy framework. We first propose a pseudo-polynomial time algorithm to compute the Banzhaf and Shapley-Shubik indices for this class of game. Then, we study a bribery problem, in which one tries to maximize/minimize the voting power/weight of a given agent by changing the support structure under a budget constraint. We show that these problems are computationally hard and provide several parameterized complexity results.

technical paper


We study wisdom-of-the-crowd effects in liquid democracy on networks where agents are allowed to apportion parts of their voting weight to different proxies. We show that in this setting---unlike in the standard one where voting weight is delegated in full to only one proxy---it becomes possible to construct delegation structures that optimize the truth-tracking ability of the group. Focusing on group accuracy we contrast this centralized solution with the setting in which agents are free to choose their weighted delegations by greedily trying to maximize their own individual accuracy. While equilibria with weighted delegations may be as bad as in the standard delegations setting, they are never worse and may sometimes be better. To gain further insights into this decentralized model we experimentally study quantal response delegation strategies on random networks.

Tracking Truth by Weighting Proxies in Liquid Democracy


We consider the problem of finding a compromise between the opinions of a group of individuals on a number of mutually independent, binary topics.
In this paper, we quantify the loss in representativeness that results from requiring the outcome to have majority support, in other words, the ``price of majority support''.
Each individual is assumed to support an outcome if they agree with the outcome on at least as many topics as they disagree on.
Our results can also be seen as quantifying Anscombes paradox which states that topic-wise majority outcome may not be supported by a majority.
To measure the representativeness of an outcome, we consider two metrics.
First, we look for an outcome that agrees with a majority on as many topics as possible.
We prove that the maximum number such that there is guaranteed to exist an outcome that agrees with a majority on this number of topics and has majority support, equals $\ceil{(t+1)/2}$ where $t$ is the total number of topics.
Second, we count the number of times a voter opinion on a topic matches the outcome on that topic. The goal is to find the outcome with majority support with the largest number of matches.
We consider the ratio between this number and the number of matches of the overall best outcome which may not have majority support.
We try to find the maximum ratio such that an outcome with majority support and this ratio of matches compared to the overall best is guaranteed to exist.
For 3 topics, we show this ratio to be $5/6\approx 0.83$.
In general, we prove an upper bound that comes arbitrarily close to $2\sqrt{6}-4\approx 0.90$ when $t$ is large.
Furthermore, we numerically compute a better upper and a non-matching lower bound in the relevant range for $t$.

The Price of Majority Support


Group decisions are often complicated by a deadline. For example, in committee hiring decisions, the deadline might be a budget's start date or the beginning of a semester. It may be that if no candidate is supported by a strong majority, the default is to hire no one---an option that may cost dearly. Hence, committee members might prefer to agree on a reasonable, rather than the best, candidate, to avoid unfilled positions. Here, we propose a model for the above scenario - Consensus Under a Deadline (CUD)-based on a time-bounded iterative voting process. We provide theoretical convergence guarantees and an analysis of the resulting decision quality. An extensive experimental study demonstrates more subtle features of CUDs, e.g., the difference between two simple types of committee member behavior, lazy vs. proactive voters. Finally, a user study examines the differences between the behavior of rational voting bots and human voters, concluding that it may often be best to have bots play on the humans' behalf.

Reaching Consensus Under a Deadline


Embodied conversational agents benefit from being able to accompany their speech with gestures. Although many data-driven approaches to gesture generation have been proposed in recent years, it is still unclear whether such systems can consistently generate gestures that convey meaning. We investigate which gesture properties (phase, category, and semantics) can be predicted from speech text and/or audio using contemporary deep learning. In extensive experiments, we show that gesture properties related to gesture meaning (semantics and category) are predictable from text features (time-aligned FastText embeddings) alone, but not from prosodic audio features, while rhythm-related gesture properties (phase) on the other hand can be predicted from audio features better than from text. These results are encouraging as they indicate that it is possible to equip an embodied agent with content-wise meaningful co-speech gestures using a machine-learning model.

Multimodal analysis of the predictability of hand-gesture properties


Autonomous agents operating in the real world often need to interact with other agents to accomplish their tasks. For such agents, the ability to model behavior of other agents – both human and artificial – without complete knowledge of their decision factors is essential. Towards realizing this ability, we present Factorial Agent Markov Model (FAMM), a model to represent behavior of other agents performing sequential tasks. In contrast with most existing models, FAMM allows for behavior of other agents to depend on multiple, time-varying latent decision factors and does not assume rationality. To enable learning of FAMM parameters by observing behavior of other agents, we provide a set of variational inference algorithms for the unsupervised, semi-supervised, and supervised settings. These Bayesian learning algorithms for the FAMM enable agents to model other agents using execution traces and domain-specific priors. We demonstrate the utility of FAMM and corresponding learning algorithms using three synthetic domains and benchmark them against existing algorithms for modeling agent behavior. Our numerical experiments demonstrate that, despite the presence of multiple time-varying latent states, our approach is capable of learning predictive models of other agents with semi-supervision.

Factorial Agent Markov Model: Modeling Other Agents' Behavior in presence of Dynamic Latent Decision Factors


Autonomous agents are increasingly being designed for and deployed amongst human end-users. Yet, human users often have little knowledge of how these agents work or what they will do next. This lack of transparency has already resulted in unintended consequences during AI use; a concerning trend which is projected to increase with the proliferation of autonomous agents. To curb this trend and ensure safe use of AI, assisting users in establishing an accurate understanding of agents that they work with is essential. In this work, we present a user-centered framework to address this need for autonomous agents that follow a Markovian policy. Our framework first computes salient instructions of agent behavior by estimating a user’s mental model and utilizing algorithms for sequential decision-making. Next, and in contrast to existing solutions, these instructions are presented interactively to the end-user, thereby enabling an approach to AI transparency that is tailored to each end-user. We evaluate our framework, with emphasis on its interactive features, through experiments with human participants. Our experiments shed light on the role and importance of interactivity for explaining behavior of autonomous agents.

Evaluating the Role of Interactivity on Improving Transparency in Autonomous Agents


Dealing with the challenges of an interconnected globalised world requires to handle plurality. This is no exception when considering value-aligned intelligent systems, since the values to align with should capture this plurality. So far, most literature on value-alignment has just considered a single value system. Thus, this paper advances the state of the art by proposing a method for the aggregation of value systems. By exploiting recent results in the social choice literature, we formalise our aggregation problem as an optimisation problem. We then cast such problem as an Lp-regression problem. By doing so, we provide a general theoretical framework that allows us to model and solve the above-mentioned problem. Our aggregation method allows us to consider a range of ethical principles, from utilitarian (maximum utility) to egalitarian (maximum fairness). We illustrate the aggregation of value systems by considering real-world data from the European Value Study. Specifically, we show how different consensus value systems can be obtained depending on the ethical principle of choice.

Towards Pluralistic Value Alignment: Aggregating Value Systems Through Lp-Regression


In empirical game-theoretic analysis (EGTA), game models are extended iteratively through a process of generating new strategies based on experience with prior strategies. The strategy exploration problem in EGTA is how to direct this process so to construct effective models with minimal iteration. A variety of approaches have been proposed in the literature, including methods based on classic techniques and novel concepts. Comparing the performance of these alternatives can depend sensitively on criteria adopted and measures employed. We investigate some of the methodological considerations in evaluating strategy exploration, proposing and justifying new evaluation methods based on examples and experimental observations. In particular, we emphasize the fact that empirical games create a space of strategies and evaluation should reflect how well it covers the strategically relevant space. Based on this fact, we suggest that the minimum regret constrained profile(MRCP) provides a particularly robust basis for evaluating a space of strategies, and propose a local search method for computing MRCP. However, MRCP computation is not always feasible especially in large games. To evaluate strategy exploration in large games, we propose a new evaluation scheme that measures the strategic coverage of an empirical game. Specifically, we highlight consistency considerations for comparing across different approaches. We show that violation of the consistency considerations could yield misleading conclusions on the performance of different approaches. In accord with consistency considerations, we propose a profile-selection method, which effectively discovers the profile that can represent the strategic coverage of an empirical game through its regret information. We show that our evaluation scheme reveals the authentic learning performance of different approaches compared to previous evaluation methods.

Evaluating Strategy Exploration in Empirical Game-Theoretic Analysis


We consider a budgeted combinatorial multi-armed bandit setting where, in every round, the algorithm selects a \emph{superarm} consisting of one or more arms. The goal is to minimize the total expected regret after all rounds within a limited budget. Existing techniques either fix the budget per round or the number of arms pulled in each round. Our setting is general, where the algorithm decides how many, and which arms to be pulled based on the remaining budget and number of rounds. First, we propose CBwK-Greedy algorithm, which uses a greedy technique to allocate arms to the rounds. Next, we propose a reduction of this problem to Bandits with Knapsacks (BwK) with a single pull. With this reduction, we propose CBwK-UCB that uses PrimalDualBwK ingeniously. We rigorously prove regret bounds for the algorithm CBwK-UCB. Though we do not have theoretical results for CBwK-Greedy, we believe the regret should be similar to CBwK-UCB. We experimentally compare the two algorithms and observe that CBwK-Greedy performs incrementally better than CBwK-UCB. We experimentally show that for very high budgets, the regret goes to zero.

Budgeted Combinatorial Multi-Armed Bandits


In multiagent systems, the complex interaction of fixed incentives can lead agents to outcomes that are poor (\emph{inefficient}) not only for the group, but also for each individual. Price of anarchy is a technical, game-theoretic definition that quantifies the inefficiency arising in these scenarios\textemdash it compares the welfare that can be achieved through perfect coordination against that achieved by self-interested agents at a Nash equilibrium. We derive a differentiable, upper bound on a price of anarchy that agents can cheaply estimate during learning. Equipped with this estimator, agents can adjust their incentives in a way that improves the efficiency incurred at a Nash equilibrium. Agents do so by learning to mix their reward (equiv. negative loss) with that of other agents by following the gradient of our derived upper bound. We refer to this approach as D3C. In the case where agent incentives are differentiable, D3C resembles the celebrated Win-Stay, Lose-Shift strategy from behavioral game theory, thereby establishing a connection between the global goal of maximum welfare and an established agent-centric learning rule. In the non-differentiable setting, as is common in multiagent reinforcement learning, we show the upper bound can be reduced via evolutionary strategies, until a compromise is reached in a distributed fashion. We demonstrate that D3C improves outcomes for each agent and the group as a whole on several social dilemmas including a traffic network exhibiting Braess’s paradox, a prisoner’s dilemma, and several multiagent domains.

Computation and Bribery of Voting Power in Delegative Simple Games

Downloads

Next from AAMAS 2022

Tracking Truth by Weighting Proxies in Liquid Democracy

Similar lecture

Tracking Truth by Weighting Proxies in Liquid Democracy

Computation and Bribery of Voting Power in Delegative Simple Games

.css-70qvj9{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;}Downloads

Next from AAMAS 2022

Tracking Truth by Weighting Proxies in Liquid Democracy

Similar lecture

Tracking Truth by Weighting Proxies in Liquid Democracy

Downloads