New Zealand

Fair division is the problem of allocating a set of items among a set of agents in a fair and efficient way. It arises naturally in a wide range of real-life settings. Competitive equilibrium (CE) is a central solution concept in economics to study markets, and due to its remarkable fairness and efficiency properties (e.g., envy-freeness, proportionality, Pareto optimality), it is also one of the most preferred mechanisms for fair division even though there is no money involved.

The vast majority of work in fair division focuses on the case of disposable goods, which all agents like or can throw away at no cost. In this paper, we consider the case of mixed manna under linear utilities where some items are positive goods liked by all agents, some are bads (chores) that no one likes, an the remaining some agents like and others dislike. The recent work of Bogomolnaia et al. Econometrica &#39;17, initiated the study of CE in mixed manna. They establish that a CE always exists and maintains all nice properties found in the case of all goods. However, computing a CE of mixed manna is genuinely harder than in the case all goods due to the non-convex and disconnected nature of the CE set. Our main result is a polynomial-time algorithm for computing a CE of mixed manna when the number of agents or items is constant.


AAMAS 2020

Computing Competitive Equilibria of Mixed Manna

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-23 is the Thirty-Seventh AAAI Conference on Artificial Intelligence. The theme of this conference is to create collaborative bridges within and beyond AI. Like previous AAAI conferences, AAAI-23 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and two new activities: a Bridge Program and a Lab Program. Many of these activities are tailored to the theme of bridges and all are selected according to the highest standards, with additional programs for students and young researchers. 
AAAI is providing you with a conference planner, which you can use to help organize your itinerary of activities. This includes talks to attend in person, talks to attend remotely, breaks with colleagues and your site seeing activities. To access this conference planner, please go to [https://aaai-2023.takemobi.io](https://aaai-2023.takemobi.io).

In order to access this site, you need to register. If you haven't already, please register [here](https://aaai.org/Conferences/AAAI-23/registration/).


AAAI 2023

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines.

Fair division is the problem of allocating a set of items among a set of agents in a fair and efficient way. It arises naturally in a wide range of real-life settings. Competitive equilibrium (CE) is a central solution concept in economics to study markets, and due to its remarkable fairness and efficiency properties (e.g., envy-freeness, proportionality, Pareto optimality), it is also one of the most preferred mechanisms for fair division even though there is no money involved.

The vast majority of work in fair division focuses on the case of disposable goods, which all agents like or can throw away at no cost. In this paper, we consider the case of mixed manna under linear utilities where some items are positive goods liked by all agents, some are bads (chores) that no one likes, an the remaining some agents like and others dislike. The recent work of Bogomolnaia et al. Econometrica '17, initiated the study of CE in mixed manna. They establish that a CE always exists and maintains all nice properties found in the case of all goods. However, computing a CE of mixed manna is genuinely harder than in the case all goods due to the non-convex and disconnected nature of the CE set. Our main result is a polynomial-time algorithm for computing a CE of mixed manna when the number of agents or items is constant.


technical paper

AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). The aim of the joint conference is to provide a single, high-profile, internationally-respected archival forum for scientific research in the theory and practice of autonomous agents and multi-agent systems.

Browse keynotes, discussions, panels and over 300 presentations.


AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). 

Conventional wisdom believes cryptocurrency miners should always work on particular token at their full power.
In this paper, however, we show that miners' equilibrium strategy deviates from it, 
which affects the system security and energy-efficiency.
Specifically, we model mining as a game where each miner has limited mining power and compete for multiple tokens. 
We analyze both pure Nash-equilibrium and Stackelberg-equilibrium of this game, deriving their closed-forms. 
It is suggested that miners might not exert full power, which, compared with fully-powered mining, provides less mining power for a token and thus makes it more vulnerable to attacks, while it helps to reduce energy consumption. 
Simulation results show that with more disparate capacity, this effect is more significant. 
Our results also show that miners should disperse power among all compatible tokens instead of only one, which matches realistic statistics well.


Games of Miners

In full-knowledge multi-robot adversarial patrolling, a group of robots has to detect an adversary who knows the robots' strategy. The adversary can easily take advantage of any deterministic patrolling strategy, which necessitates the employment of a randomised strategy. While the Markov decision process has been the dominant methodology in computing the penetration detection probabilities, we apply enumerative combinatorics to characterise the penetration detection probabilities. It allows us to provide the closed formulae of these probabilities and facilitates characterising optimal random defence strategies. Comparing to iteratively updating the Markov transition matrices, our methods significantly reduces the time and space complexity of solving the problem. We focus on one of four penetration configurations to highlight the technique.


Multi-Robot Adversarial Patrolling Strategies via Lattice Paths

Human language and thought are characterized by the ability to systematically generate a potentially infinite number of complex structures (e.g., sentences) from a finite set of familiar components (e.g., words). Recent works in emergent communication have discussed the propensity of artificial agents to develop a systematically compositional language through playing co-operative referential games. The degree of structure in the input data was found to affect the compositionality of the emerged communication protocols. Thus, we explore various structural priors in multi-agent communication and propose a novel graph referential game. We compare the effect of structural inductive bias (bag-of-words, sequences and graphs) on the emergence of compositional understanding of the input concepts measured by topographic similarity and generalization to unseen combinations of familiar properties. We empirically show that graph neural networks induce a better compositional language prior and a stronger generalization to out-of-domain data. We further perform ablation studies that show the robustness of the emerged protocol in graph referential games.


Analyzing structural priors in multi-agent communication

While reinforcement learning (RL) agents have the remarkable ability to learn by interacting with their environments, this process is often slow and data inefficient. Because environment interaction is typically expensive, many approaches have been studied to speed up RL. One popular method for doing so is to leverage human knowledge via imitation learning (IL), in which a demonstrator provides an example of the desired behavior, and the agent seeks to imitate. In this in-progress work, we propose a new way of integrating IL and deep RL, which we call corrected self imitation learning, where an agent provided with demonstration can learn faster compared to an agent with no demonstration. Our method does not increase the number of environmental interactions compared to a baseline RL method, and works well even in the case when the demonstrator is not an expert. We evaluate our method in the Atari game of Ms. Pac-Man and achieve promising results indicating our method has the potential to speed up deep RL algorithms.


Work-in-progress: Corrected Self Imitation Learning via Demonstrations

Reinforcement learning (RL) is a powerful learning paradigm in which agents can learn to maximize sparse and delayed reward signals. Although RL has had many impressive successes in complex domains, learning can take hours, days, or even years of training data. A major challenge of contemporary RL research is to discover how to learn with less data. Previous work has shown that domain information can be successfully used to shape the reward; by adding additional reward information, the agent can learn with much less data. Furthermore, if the reward is constructed from a potential function, the optimal policy is guaranteed to be unaltered. While such potential-based reward shaping (PBRS) holds promise, it is limited by the need for a well-defined potential function. Ideally, we would like to be able to take arbitrary advice from a human or other agent and improve performance without affecting the optimal policy. The recently introduced dynamic potential based advice (DPBA) method tackles this challenge by admitting arbitrary advice from a human or other agent and improves performance without affecting the optimal policy. The main contribution of this paper is to expose, theoretically and empirically, a flaw in DPBA. Alternatively, to achieve the ideal goals, we present a simple method called policy invariant explicit shaping (PIES) and show theoretically and empirically that PIES succeeds where DPBA fails.



Useful Policy Invariant Shaping from Arbitrary Advice

Learning Context-aware Task Reasoning for Meta Reinforcement Learning

We provide a tutorial of the Virtual Human Toolkit. The Toolkit is a collection of modules, tools, and libraries designed to aid and support researchers and developers with the creation of virtual human conversational characters. The Toolkit is developed at the University of Southern California Institute for Creative Technologies, is freely available for the academic research community, and supports speech recognition, natural language processing, nonverbal behavior generation, nonverbal behavior realization, text-to-speech generation, and rendering. This tutorial focuses on three areas: 1) overview of the main technologies, 2) overview of the overall architecture, and 3) hands-on creation of a basic interactive character. The target audience is interested researchers within the field of interactive agents and related areas with an affinity for technology.

Virtual Human Toolkit Tutorial

Increasingly, much work in AI – from machine learning and natural language processing to planning, perception, and robotics – is based on classical (continuous) optimization. While this foundation has proved to be of considerable practical utility, the increasingly decentralized and networked nature of computation in the 21st century, implies that classical optimization may prove increasingly restrictive, as AI tackles applications that involve massively large networked environments, where data is stored heterogeneously in the “cloud”, and computation involves balancing multiple competing objectives, including cost, privacy, reliability, and security. The aim of this tutorial is to present an elegant mathematical formalism for solving large games that has been extensively studied in network economics, but so far, has not yet played a major role in multiagent AI. The framework is based on variational inequalities, a formalism that extends classical optimization to vector fields. We use a variety of real-world problems, from modeling traffic flow to content distribution on the Internet and green supply chains in sustainable manufacturing, to illustrate the power of this formalism. We also show that work in deep learning on generative adversarial networks results in complex network dynamics, and can be profitably studied this framework. The tutorial will introduce all the necessary mathematics, and should be of interest to AAMAS researchers from a wide variety of backgrounds.

Network Economics, Variational Inequalities and Deep Learning

Fairness in algorithmic decision-making has received growing attention recently. However, fairness in the context of resource allocation has been formally studied for many decades in microeconomics, and for a few decades in computer science. This tutorial will present an overview of this literature, its various fairness definitions, and fair algorithms. The focus will be on recent advances, but no prior background will be required.

The first part of the tutorial will look at the classic setting of cake-cutting, which models allocation of a divisible resource. This part will cover classic fairness notions such as proportionality, envy-freeness, equitability, and Pareto optimality, and explore their interplay with game-theoretic notions such as strategyproofness. This part will end with a discussion on connections between fairness and market equilibria.

The second part of the tutorial will focus on the allocation of indivisible items. This will cover relaxations of proportionality, envy-freeness, and equitability, as well as other fairness notions such as maximin share guarantee. This part will explore static versus dynamic allocations, goods versus chores, private versus public goods, etc.

The tutorial will end with a high-level discussion on how to apply these fairness definitions in other contexts such as voting, machine learning, or ethical decision-making.

Computing Competitive Equilibria of Mixed Manna

Downloads

Next from AAMAS 2020

Games of Miners

Similar lecture

Optimal Pricing Schemes for Identical Items with Time-Sensitive Buyers

Computing Competitive Equilibria of Mixed Manna

.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 2020

Games of Miners

Similar lecture

Optimal Pricing Schemes for Identical Items with Time-Sensitive Buyers

Downloads