New Zealand


We study the problem of fair allocation of a set of indivisible items among agents with additive valuations, under cardinality constraints. In this setting, the items are partitioned into categories, each with its own limit on the number of items it may contribute to any bundle. We consider the fairness measure known as the maximin share (MMS) guarantee and propose a novel polynomial-time algorithm for finding 1/2-approximate MMS allocations–an improvement from the previously best available guarantee of 11/30.

AAMAS 2022

Guaranteeing Half-Maximin Shares Under Cardinality Constraints

maximin share

indivisible goods

constrained fair allocation

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

poster


Multi-agent task allocation methods seek to distribute a set of tasks fairly amongst a set of agents. In real-world settings, such as fruit farms, human labourers undertake harvesting tasks, organised each day by farm manager(s) who assign workers to the fields that are ready to be harvested. The work presented here considers three challenges identified in the adaptation of a multi-agent task allocation methodology applied to the problem of distributing workers to fields. First, the methodology must be fast to compute so that it can be applied on a daily basis. Second, the incremental acquisition of harvesting data used to make decisions about worker-task assignments means that a data-backed approach must be derived from incomplete information as the growing season unfolds. Third, the allocation must take “fairness” into account and consider worker motivation. Solutions to these challenges are demonstrated, showing statistically significant results based on the operations at a soft fruit farm during their 2020 and 2021 harvesting seasons.

Multi-agent Task Allocation for Fruit Picker Team Formation


Training reinforcement learning agents in real-world environments is costly, particularly for safety-critical applications. Human input can enable an agent to learn a good policy while avoiding unsafe actions, but at the cost of bothering the human with repeated queries. We present a model for safe learning in safety-critical environments from human input that minimises bother cost. Our model, JPAL-HA, proposes an efficient mechanism to harness human preferences and justifications to significantly improve safety during the learning process without increasing the number of interactions with a user. We show this with both simulation and human experiments.

How to train your agent: Active Learning from Human Preferences and Justifications in Safety-critical Environments


Affective reaction is a mechanism that is triggered by a perceived emotion and results in the observer's emotion, subsequently steering the behavior of the observer. It is crucial to understand this mechanism as it constitutes a mediator between the emotional expressions of one agent and the (behavioral) responses of another thus facilitating social interaction among agents. This paper reports on a formal specification of affective reaction based on its psychological analysis using values and value systems as agents' appraisal standards.

Modeling Affective Reaction in Multi-agent Systems


Formal verification of strategic abilities is a hard problem. We propose to use the methodology of assume-guarantee reasoning in order to facilitate model checking of alternating-time temporal logic with imperfect information and imperfect recall.

Towards Assume-Guarantee Verification of Strategic Ability


It is an established fact in behavioral economics that in lab experi-
ments of auctions, human subjects do not adhere to the risk-neutral
Bayesian Nash equilibria of such games. Several attempts at explain-
ing this Overbidding Puzzle focus on the bidders’ psychology and
suggest they may have parametrized utility functions that differ
from the risk-neutral payoff. However, analytical equilibria of the
resulting modified games are generally not available. Consequently,
it has been difficult to identify the specific parameters and assess
the merits of these proposed modifications in explaining empirical
observations.
With recent advances in equilibrium learning, it has become
tractable to compute approximations of Bayesian Nash equilibria.
Building on these advances and Bayesian optimization, we propose
a novel regression framework to infer unobserved parameters of
Bayesian games from behavioral data. We apply our method to two
data sets of human bidding behavior in all-pay auctions. For the first
time, this makes it possible to directly compare the goodness-of-fit
of several proposed qualitative explanations of overbidding.

Approaching the Overbidding Puzzle in All-Pay Auctions: Explaining Human Behavior through Bayesian Optimization and Equilibrium Learning


We study the NP-hard Fair Connected Districting problem: Partition a vertex-colored graph into k connected components (subsequently referred to as districts) so that in every district the most frequent color occurs at most a given number of times more often than the second most frequent color. Fair Connected Districting is motivated by various real-world scenarios, such as district-based elections, where agents of different types, which are one-to-one represented by nodes in a network, have to be partitioned into disjoint districts. We conduct a fine-grained analysis of the (parameterized) computational complexity of Fair Connected Districting: We study its parameterized complexity with respect to various graph parameters, including treewidth, and problem-specific parameters, including the numbers of colors and districts, and its complexity on graphs from different classes (such as paths, stars, and trees).

A Refined Complexity Analysis of Fair Districting over Graphs


We present a Nash equilibrium analysis for single-buyer singleseller multi-unit k-double auctions for scaling-based bidding strategies. We then design a Deep Deterministic Policy Gradient (DDPG) based learning strategy, DDPGBBS, for a participating agent to suggest bids that approximately achieve the above Nash equilibrium. We expand DDPGBBS to be helpful in more complex settings with multiple buyers/sellers trading multiple units in a Periodic Double Auction (PDA), such as the wholesale market in smart-grids. We demonstrate the efficacy of DDPGBBS with Power Trading Agent Competition’s (PowerTAC) wholesale market PDA as a testbed.

Multi-unit Double Auctions: Equilibrium Analysis and Bidding Strategy using DDPG in Smart-grids


The recent emergence of navigational tools has changed traffic patterns and has now enabled new types of congestion-aware routing control like dynamic road pricing. Using the fundamental diagram of traffic flows - applied in macroscopic and mesoscopic traffic modeling - the article introduces a new N-player dynamic routing game with explicit congestion dynamics. The model is well-posed and can reproduce heterogeneous departure times and congestion spill back phenomena. However, as Nash equilibrium computations are PPAD-complete, solving the game becomes intractable for large but realistic numbers of vehicles N. Therefore, the corresponding mean field game is also introduced. Experiments were performed on several classical benchmark networks of the traffic community: the Pigou, Braess, and Sioux Falls networks with heterogeneous origin, destination and departure time tuples. The Pigou and the Braess examples reveal that the mean field approximation is generally very accurate and computationally efficient as soon as the number of vehicles exceeds a few dozen. On the Sioux Falls network (76 links, 100 time steps), this approach enables learning traffic dynamics with more than 14,000 vehicles.

Solving N player dynamic routing games with congestion: a mean field approach


Reconfigurable multi-agent systems consist of a set of autonomous agents, with integrated interaction capabilities that feature oppor tunistic interaction. Agents seemingly reconfigure their interactions interfaces by forming collectives, and interact based on mutual interests. Finding ways to design and analyse the behaviour of these systems is a vigorously pursued research goal. We propose a model checker, named R-CHECK, to allow reasoning about these systems both from an individual- and a system- level. R-CHECK also permits reasoning about interaction protocols and joint missions. R-CHECK supports a high-level input language with symbolic semantics, and provides a modelling convenience for interaction features such as reconfiguration, coalition formation, self-organisation, etc.

R-CHECK: A Model Checker for Verifying Reconfigurable MAS

**Read paper on the following link:**

https://ifaamas.org/Proceedings/aamas2022/pdfs/p1768.pdf

**Abstract:**



Guaranteeing Half-Maximin Shares Under Cardinality Constraints

Downloads

Next from AAMAS 2022

Multi-agent Task Allocation for Fruit Picker Team Formation

Similar lecture

How to Fairly Allocate Easy and Difficult Chores

Guaranteeing Half-Maximin Shares Under Cardinality Constraints

.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

Multi-agent Task Allocation for Fruit Picker Team Formation

Similar lecture

How to Fairly Allocate Easy and Difficult Chores

Downloads