United Kingdom

We study several fairness notions in allocating indivisible chores (i.e., items with non-positive values): envy-freeness and its relaxations. For allocations under each fairness criterion, we establish their approximation guarantees for other fairness criteria. Under the setting of additive cost functions, our results show strong connections between these fairness criteria and, at the same time, reveal intrinsic differences between goods allocation and chores allocation. Furthermore, we investigate the efficiency loss under these fairness constraints and establish their prices of fairness.

AAMAS 2021

Connections between Fairness Criteria and Efficiency for Allocating Indivisible Chores

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 

technical paper

We advocate the development of a discipline of interacting with and extracting information from models, both mathematical (e.g. game-theoretic ones) and computational (e.g. agent-based models). We outline some directions for the development of a such a discipline: - the development of logical frameworks for the systematic formal specification of stylized facts and social mechanisms in (mathematical and computational) social science. Such frameworks would bring to attention new issues, such as <i>phase transitions</i>, i.e. dramatical changes in the validity of the stylized facts beyond some critical values in parameter space. We argue that such statements are useful for those logical frameworks describing properties of ABM. - the adaptation of tools from the theory of reactive systems (such as bisimulation) to obtain practically relevant notions of two systems "having the same behavior". - the systematic development of an adversarial theory of model perturbations, that investigates the robustness of conclusions derived from models of social behavior to variations in several features of the social dynamics. These may include: activation order, the underlying social network, individual agent behavior.

Models We Can Trust: Toward a Systematic Discipline of (Agent-Based) Model Interpretation and Validation (Blue Sky Ideas Track)

In this work, we consider the problem of multi-agent reinforcement learning in directed social networks with a large number of agents. Network dependencies among user activities impact the reward for individual actions and need to be incorporated into policy learning, however, directed interactions entail that the network is partially observable to each user. When estimating policies locally, the insufficient state information makes it challenging for users to effectively learn network dependencies. To address this, we use parameter sharing and ego-network extrapolation in a decentralized policy learning and execution framework. This is in contrast to previous work on social RL that assumes a centralized controller to capture inter-agent dependencies for joint policy learning. We evaluate our proposed approach on Twitter datasets and show that our decentralized learning approach achieves performance nearly equivalent to that of centralized learning approach and superior performance to other baselines.

Towards Decentralized Social Reinforcement Learning via Ego-Network Extrapolation

Artificial agents trained by deep reinforcement learning will likely encounter novel situations after deployment that were never seen during training. Our agent must be 
 to handle such situations well. However, if we cannot rely on the average training or validation reward as a metric, then how can we effectively evaluate robustness? We take inspiration from the practice of 
 in software engineering. Specifically, we suggest that when designing AI agents that collaborate with humans, designers should search for potential edge cases in 
 and 
 and write tests which check that the behavior of the agent in these edge cases is reasonable. We apply this methodology to build a suite of unit tests for the Overcooked-AI environment, and use this test suite to evaluate three proposals for improving robustness. We find that the test suite provides significant insight into the effects of these proposals that were generally not revealed by looking solely at the average validation reward. For our full paper, see https://arxiv.org/abs/2101.05507 arxiv.org/abs/2101.05507

Evaluating the Robustness of Collaborative Agents

In recent work, Gourvès, Lesca, and Wilczynski propose a variant of the classic housing markets model where the matching between agents and objects evolves through Pareto-improving swaps between pairs of adjacent agents in a social network. To explore the swap dynamics of their model, they pose several basic questions concerning the set of reachable matchings. In their work and other follow-up works, these questions have been studied for various classes of graphs: stars, paths, generalized stars (i.e., trees where at most one vertex has degree greater than two), trees, and cliques. For generalized stars and trees, it remains open whether a Pareto-efficient reachable matching can be found in polynomial time.

Object Allocation Over a Network of Objects: Mobile Agents with Strict Preferences

Social choice functions (SCFs) map the preferences of a group of agents over some set of alternatives to a non-empty subset of alternatives. The Gibbard-Satterthwaite theorem has shown that only extremely unattractive single-valued SCFs are strategyproof when there are more than two alternatives. For set-valued SCFs, or so-called social choice correspondences, the situation is less clear. There are miscellaneous--mostly negative--results using a variety of strategyproofness notions and additional requirements. The simple and intuitive notion of Kelly-strategyproofness has turned out to be particularly compelling because it is weak enough to still allow for positive results. For example, the Pareto rule is strategyproof even when preferences are weak, and a number of attractive SCFs (such as the top cycle, the uncovered set, and the essential set) are strategyproof for strict preferences. In this paper, we show that, for weak preferences, only indecisive SCFs can satisfy strategyproofness. In particular, (i) every strategyproof rank-based SCF violates Pareto-optimality, (ii) every strategyproof support-based SCF (which generalize Fishburn's C2 SCFs) that satisfies Pareto-optimality returns at least one most preferred alternative of every voter, and (iii) every strategyproof non-imposing SCF returns a Condorcet loser in at least one profile.

On the Indecisiveness of Kelly-Strategyproof Social Choice Functions

We present a scalable tree search planning algorithm for large multi-agent sequential decision problems that require dynamic collaboration. Teams of agents need to coordinate decisions in many domains, but naive approaches fail due to the exponential growth of the joint action space with the number of agents. We circumvent this complexity through an anytime approach that allows us to trade computation for approximation quality and also dynamically coordinate actions. Our algorithm comprises three elements: online planning with Monte Carlo Tree Search (MCTS), factored representations of local agent interactions with coordination graphs, and the iterative Max-Plus method for joint action selection. We evaluate our approach on the benchmark SysAdmin domain with static coordination graphs and achieve comparable performance with much lower computation cost than our MCTS baselines. We also introduce a multi-drone delivery domain with dynamic, i.e., state-dependent coordination graphs, and demonstrate how our approach scales to large problems on this domain that are intractable for other MCTS methods. We provide an open-source implementation of our algorithm at https://github.com/JuliaPOMDP/FactoredValueMCTS.jl.

Scalable Anytime Planning for Multi-Agent MDPs

Consider a typical organization whose worker agents seek to collectively cooperate for its general betterment. However, each individual agent simultaneously seeks to act to secure a larger chunk than its co-workers of the annual increment in compensation, which usually comes from a fixed pot. As such, the agents in an organization must cooperate and compete. Another feature of many organizations is that a worker receives a bonus, which is often a fraction of previous year’s total profit. As such, the agent derives a reward that is also partly dependent on historical performance. How should the individual agent decide to act in this context? Few methods for the mixed cooperative-competitive setting have been presented in recent years, but these are challenged by problem domains whose reward functions additionally depend on historical information. Recent deep multi-agent reinforcement learning (MARL) methods using long short-term memory (LSTM) may be used, but these adopt a joint perspective to the interaction or require explicit exchange of information among the agents to promote cooperation, which may not be possible under competition. In this paper, we first show that the agent’s decision-making problem can be modeled as an interactive partially observable Markov decision process (I-POMDP) that captures the dynamic of a history-dependent reward. We present an interactive advantage actor-critic method (IA2C+), which combines the independent advantage actor-critic network with a belief filter that maintains a belief distribution over other agents’ models. Empirical results show that IA2C+ learns the optimal policy faster and more robustly than several baselines.

Cooperative-Competitive Reinforcement Learning with History-Dependent Rewards

This paper addresses modeling and simulating pedestrian trajectories when interacting with an autonomous vehicle in a shared space. Pedestrian motion models integrating pedestrians interactions with an autonomous vehicle already exist. However, they fail to accurately predict the individual trajectory of each pedestrian, and they do not deal with the diversity of possible pedestrian interactions with the vehicle in a shared space (front, back or lateral). Moreover, previous works do not sufficiently provide a quantitative evaluation of the model's predictions. In this paper, we propose an hybrid pedestrian model that combines the social force model and a new decision model for conflicting pedestrian-vehicle interactions. The proposed model integrates different observed pedestrians behaviors, as well as the behaviors of the social groups of pedestrians. We validate the model and evaluate its predictive potential through qualitative and quantitative comparisons with ground truth trajectories. The proposed model reproduces observed behaviors that have not been replicated by the social force model and outperforms the social force model at predicting pedestrians trajectories on the used dataset. This model will be used by an autonomous vehicle in a shared space to predict the trajectories of surrounding pedestrians.

An Agent-Based Model to Predict Pedestrians Trajectories with an Autonomous Vehicle in Shared Spaces

Pay-per-last-$N$-shares'' (PPLNS) is one of the most common payout strategies used by mining pools in Proof-of-Work (PoW) cryptocurrencies such as Bitcoin.As with any payment scheme, it is imperative to study issues of incentive compatibility of miners within the pool. For PPLNS this question has only been partially answered; we know that reasonably-sized miners within a PPLNS pool prefer following the pool protocol over employing {\em specific} deviations. In this paper, we present a novel modification to PPLNS where we randomise the protocol in a natural way. We call our protocol ''Randomised pay-per-last-$N$-shares'' (RPPLNS), and note that the randomised structure of the protocol greatly simplifies the study of its incentive compatibility. We show that RPPLNS maintains the strengths of PPLNS (i.e., fairness, variance reduction, and resistance to pool hopping), while also being robust against a richer class of strategic mining than what has been shown for PPLNS.

RPPLNS: Pay-per-last-N-shares with a Randomised Twist

Most frameworks for computing solution concepts in hedonic games are theoretical in nature, and require complete knowledge of all agent preferences, an impractical assumption in real-world settings. This paper presents the first application of strategic hedonic game models on real-world data. We show that PAC stable solutions can reflect Members of Knesset' political positions and reveal politicians who are known to deviate from party lines. Moreover, these models compare favorably to machine learning models.

Connections between Fairness Criteria and Efficiency for Allocating Indivisible Chores

Downloads

Next from AAMAS 2021

Models We Can Trust: Toward a Systematic Discipline of (Agent-Based) Model Interpretation and Validation (Blue Sky Ideas Track)

Similar lecture

Egalitarian and Just Digital Currency Networks

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Connections between Fairness Criteria and Efficiency for Allocating Indivisible Chores

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

Models We Can Trust: Toward a Systematic Discipline of (Agent-Based) Model Interpretation and Validation (Blue Sky Ideas Track)

Similar lecture

Egalitarian and Just Digital Currency Networks

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads