United Kingdom

In this paper, we extend the unavailable candidate model (Tyler Lu and Craig Boutilier, The Unavailable Candidate Model : a Decision-Theoretic View of Social Choice, 2010) and present two new voting rules based on a finer notion of disagreement, called dissatisfaction, which depends on the ranks of the candidates, considered among all the candidates (
 rule) or only among the available candidates (
 rule). We provide algorithmic results for the two rules and show that apparently very different voting rules such as scoring rules or Kemeny rule can be unified under the same aggregation concept: expectation of dissatisfaction under the availability distribution.

AAMAS 2021

Rank Aggregation by Dissatisfaction Minimisation in the Unavailable Candidate Model

AAMAS is the largest and most influential conference in the area of agents and multiagent systems, bringing together researchers and practitioners in all areas of agent technology and providing and internationally renowned high-profile forum for publishing and finding out about the latest developments in the field. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).  

![](https://assets.underline.io/uploads/markdown_image/1/image/ce4604bd54468a006164d16e080204fb.jpg)

Please click on the button below to register for this event.

If you are registered and see this page please check the account email you are logged in with. It must be the same as for the registration.

If you still have trouble accessing the contact please contact support at aamas2021@underline.io 

poster

Asymmetric distributed constraint optimization problems (ADCOPs) in which agents are partially cooperative, is a model for representing multi-agent optimization problems  in which agents, are willing to cooperate in order to achieve a global goal,  as long as some minimal threshold on their personal utility is satisfied.

Partially Cooperative Multi-Agent Periodic Indivisible Resource Allocation

Van Zuylen et al. introduced the notion of a popular ranking in a voting context, where each voter submits a strictly-ordered list of all candidates. A popular ranking pi of the candidates is at least as good as any other ranking sigma in the following sense: if we compare pi to sigma, at least half of all voters will always weakly prefer pi. Whether a voter prefers one ranking to another is calculated based on the Kendall distance.

On Weakly and Strongly Popular Rankings

Relational agents who personalise their message to individual users need to learn about the user first. In the context of an agent who personalises the inclusion of 10 relational cues in its dialogue, we explore training the agent based on first time user’s responses to a single example of each cue prior to the session with the virtual advisor. We designed a between subjects study with three groups: Empathic (all relational cues); Neutral (no relational cues) and Adaptive (only helpful cues included). We found that in the Adaptive group, students received what they found helpful more often than in the other two groups. Analysis of the discrepancy between what user’s found helpful and what they received was least in the Adaptive group and greatest in the Neutral group.

Personalising the Dialogue of Relational Agents for First-Time Users

We explore the possibility of an alternative cryptocurrency that is egalitarian in control, just in the distribution of its created wealth, and forms and grows in a grassroots way; we analyze it via a mathematical entity called a 
 Our main result states sufficient conditions for the establishment of 1:1 exchange rates and distributive justice in a currency network.

Egalitarian and Just Digital Currency Networks

The prevalence of e-commerce applications poses new trust challenges that render traditional Trust and Reputation Management (TRM) approaches inadequate. The first challenge is that TRM is built on evidence (direct or indirect observations) but evidence is becoming increasingly sparse because nowadays users have many more venues to share information. This makes it hard to derive trust models that are robust to attacks such as whitewashing and Sybil attacks. Second, the cost of attacks has reduced significantly due to the widespread presence of bots in e-commerce applications, which tends to invalidate the traditional assumption that majority users are honest.

A Blockchain-Enabled Quantitative Approach to Trust and Reputation Management with Sparse Evidence

Individuals in a social network may form their views as a result of the influence exerted by their connections. In elections, for example, while they might initially support one candidate, social influence may lead them to support another. Here, we investigate whether a recently proposed metric, influence gap, designed to measure the effect of social influence in voting on social networks, is able to predict the outcome of a vote on networks exhibiting community structure, i.e., made of highly interconnected components, and therefore more resembling of real-world interaction. To encode communities, we extend the classical model of caveman graphs to a richer graph family that displays levels of homophily, i.e., where connections and opinions are highly intertwined. We show that, across these graphs, there are important cases when the influence gap correlation is a weak predictor due to communities, and a simpler metric, counting the initial partisan majority, provides a more accurate prediction overall. Using regression models, we further demonstrate that the influence gap combined with the more successful metrics does increase their predictive power for some levels of homophily.

Predicting Voting Outcomes in Presence of Communities

The Possible Winner (PW) problem, a fundamental algorithmic problem in computational social choice, concerns elections where voters express only partial preferences between candidates. A sequence of investigations led to a complete classification of the complexity of this problem for all pure positional scoring rules: the PW problem is in P for the plurality and veto rules, and NP-complete for all other such rules. The PW problem has also been studied on classes of restricted partial orders, such as partitioned partial orders and truncated partial orders; one of the findings is that there are positional scoring rules for which the complexity of the PW problem drops from NP-complete to P on such restricted partial orders. Here, we investigate the PW problem on partial chains, i.e., partial orders that consist of a total order on a subset of their domains. Such orders arise naturally in a variety of settings, including rankings of movies or restaurants. We classify the complexity of the PW problem on partial chains by establishing that, perhaps surprisingly, this restriction does not change the complexity of the problem. Specifically, we show that the PW problem on partial chains is NP-complete for all pure positional scoring rules other than the plurality rule and the veto rule, while, of course, for the latter two rules this problem remains in P.

Classifying the Complexity of the Possible Winner Problem on Partial Chains

We study settings where a set of identical, reusable resources must be allocated in an online fashion to arriving agents. Each arriving agent is patient and willing to wait for some period of time to be matched. When matched, each agent occupies a resource for a certain amount of time, and then releases it, gaining some utility from having done so. The goal of the system designer is to maximize overall utility given some prior knowledge of the distribution of arriving agents. We are particularly interested in settings where demand for the resources far outstrips supply, as is typical in the provision of social services, for example homelessness resources. We formulate this problem as online bipartite matching with reusable resources and patient agents. We develop new, efficient nonmyopic algorithms for this class of problems, and compare their performance with that of greedy algorithms in a variety of simulated settings, as well as in a setting calibrated to real-world data on household demand for homelessness services. We find substantial overall welfare benefits to using our nonmyopic algorithms, particularly in more extreme settings -- those where agents are unwilling or unable to wait for resources, and where the ratio of resource demand to supply is particularly high.

Efficient Nonmyopic Online Allocation of Scarce Reusable Resources

Multi-agent reinforcement learning (MARL) requires coordination to efficiently solve certain tasks. Fully centralized control is often infeasible in such domains due to the size of joint action spaces. Coordination graph based formalization allows reasoning about the joint action based on the structure of interactions. However,they often require domain expertise in their design. This paper introduces the deep implicit coordination graph (DICG) architecture for such scenarios. DICG consists of a module for inferring the dynamic coordination graph structure which is then used by a graph neural network based module to learn to implicitly reason about the joint actions or values. DICG allows learning the tradeoff between full centralization and decentralization via standard actor-critic methods to significantly improve coordination for domains with large number of agents. We apply DICG to both centralized-training-centralized-execution and centralized-training-decentralized-execution regimes. We demonstrate that DICG solves the relative over generalization pathology in predatory-prey tasks as well as outperforms various MARL baselines on the challenging StarCraft II Multi-agent Challenge (SMAC) and traffic junction environments.

Deep Implicit Coordination Graphs for Multi-agent Reinforcement Learning

Traffic congestion is a major challenge in modern urban settings. The industry-wide development of autonomous and automated vehicles (AVs) motivates the question of how can AVs contribute to congestion reduction. Past research has shown that in small scale mixed traffic scenarios with both AVs and human-driven vehicles, a small fraction of AVs executing a controlled multiagent driving policy can mitigate congestion. In this paper, we scale up existing approaches and develop new multiagent driving policies for AVs in scenarios with greater complexity. We start by showing that a congestion metric used by past research is manipulable in open road network scenarios where vehicles dynamically join and leave the road. We then propose using a different metric that is robust to manipulation and reflects open network traffic efficiency. Next, we propose a modular transfer learning approach and use it to scale up the multiagent driving policy to a realistic simulated scenario that is an order of magnitude larger than past scenarios (hundreds rather than tens of vehicles). Our experimental study shows that the resulting policy improves traffic efficiency over human-driven traffic in a large open network, where existing approaches fail to do so. Another key advantage of our modular transfer learning approach is that it avoids collecting samples from entire network, which saves up to 80% of training and data collection time in our experiments. Finally, we show for the first time a distributed multiagent policy that improves congestion over human-driven traffic. The distributed approach is more realistic as it does not require adding communication infrastructure, it relies on existing sensing capabilities, and its complexity scales linearly with the number of vehicles.

Rank Aggregation by Dissatisfaction Minimisation in the Unavailable Candidate Model

Next from AAMAS 2021

Partially Cooperative Multi-Agent Periodic Indivisible Resource Allocation

Similar lecture

Personalising the Dialogue of Relational Agents for First-Time Users

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES