New Zealand


We study the problem of finding fair and efficient allocations of a set of indivisible items to a set of agents, where each item may be a good (positively valued) for some agents and a bad (negatively valued) for others, i.e., a mixed manna. As fairness notions, we consider arguably the strongest possible relaxations of envy-freeness and proportionality, namely envy-free up to any item (EFX and EFX_0), and proportional up to the maximin good or any bad (PropMX and PropMX_0). Our efficiency notion is Pareto-optimality (PO).

We study two types of instances: (i) Separable, where the item set can be partitioned into goods and bads, and (ii) Restricted mixed goods (RMG), where for each item j, every agent has either a non-positive value for j, or values j at the same v_j &gt; 0. We obtain polynomial-time algorithms for the following:

* Separable instances: PropMX_0 allocation.
* RMG instances: Let pure bads be the set of items that everyone values negatively.
- PropMX allocation for general pure bads
- EFX+PropMX allocation for identically-ordered pure bads
- EFX+PropMX+PO allocation for identical pure bads.

Finally, if the RMG instances are further restricted to binary mixed goods where all the v_j&#39;s are the same, we strengthen the results to guarantee EFX_0 and PropMX_0 respectively.

AAMAS 2022

(Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna

pareto-optimality

mixed manna

proportionality

envy-freeness

fair division

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


We study the problem of finding fair and efficient allocations of a set of indivisible items to a set of agents, where each item may be a good (positively valued) for some agents and a bad (negatively valued) for others, i.e., a mixed manna. As fairness notions, we consider arguably the strongest possible relaxations of envy-freeness and proportionality, namely envy-free up to any item (EFX and EFX_0), and proportional up to the maximin good or any bad (PropMX and PropMX_0). Our efficiency notion is Pareto-optimality (PO).

We study two types of instances: (i) Separable, where the item set can be partitioned into goods and bads, and (ii) Restricted mixed goods (RMG), where for each item j, every agent has either a non-positive value for j, or values j at the same v_j > 0. We obtain polynomial-time algorithms for the following:

* Separable instances: PropMX_0 allocation.
* RMG instances: Let pure bads be the set of items that everyone values negatively.
- PropMX allocation for general pure bads
- EFX+PropMX allocation for identically-ordered pure bads
- EFX+PropMX+PO allocation for identical pure bads.

Finally, if the RMG instances are further restricted to binary mixed goods where all the v_j's are the same, we strengthen the results to guarantee EFX_0 and PropMX_0 respectively.

poster


In the Binary Networked Public Goods game, every player needs to decide if she participates in a public project whose utility is shared equally by the community. We study the problem of deciding if there exists a pure strategy Nash equilibrium (PSNE) in such games. The problem is already known to be NP-complete. We provide fine-grained analysis of this problem under the lens of parameterized complexity theory. We consider various natural graph parameters and show either W[1]-hardness or exhibit an FPT algorithm. Hence, our work allows us to understand the situations better where PSNE serves as a reliable solution concept versus where it is not.

On Parameterized Complexity of Binary Networked Public Goods Game


Bayesian persuasion studies how an informed sender should partially disclose information so as to influence the behavior of self-interested receivers. In the last years, a growing attention has been devoted to relaxing the assumption that the sender perfectly knows receiver's payoffs. The first crucial step towards such an achievement is to study the case in which a receiver's payoffs depend on their unknown type, which is randomly determined by a known finite-supported probability distribution. This begets considerable computational challenges, as computing a sender-optimal signaling scheme is inapproximable up to within any constant factor, even in basic settings with a single receiver. In this work, we circumvent this issue by leveraging ideas from mechanism design. In particular, we introduce a type reporting step in which the receiver is asked to report their type to the sender, after the latter has committed to a menu defining a signaling scheme for each possible receiver's type. Surprisingly, we prove that, with a single receiver, the addition of this type reporting stage makes the sender's computational problem tractable. Then, we extend our Bayesian persuasion framework with type reporting to settings with multiple receivers, focusing on the widely-studied case of no inter-agent externalities and binary actions. In such setting, we show that it is possible find a sender-optimal solution in polynomial-time by means of the ellipsoid method, given access to a suitable polynomial-time separation oracle. This can be implemented for supermodular and anonymous sender's utility functions. As for the case of submodular sender's utility functions, we first approximately cast the sender's problem into a linearly-constrained mathematical program whose objective function is the multi-linear extension of the sender's utility. Then, we show how to find in polynomial-time an approximate solution to the program by means of a continuous greedy algorithm. This provides a (1 -1/e)-approximation to the problem, which is tight.

Bayesian Persuasion Meets Mechanism Design: Going Beyond Intractability with Type Reporting


We study the effects of spoofing attacks on frequent call markets (FCMs). Spoofing---a strategic manipulation to mislead market participants by creating spurious limit orders---could harm the market efficiency and has been declared illegal in many countries. However, this practice is still very common, which inspired extensive research on measuring, detecting and curbing such manipulation in the popular market model of continuous double auctions (CDAs). In this paper, we extend this research to frequent call markets and use agent-based modelling to simulate spoofing in this context. Specifically, we apply empirical game-theoretic analysis (EGTA) to compute equilibria of agent-based markets, and demonstrate that while spoofing may be profitable in both market models, it has less impact on FCMs compared to CDAs. Finally, we explore several FCM mechanism designs to help to curb this type of market manipulation even further.

The spoofing resistance of frequent call markets


The last-mile delivery market is highly competitive and is saturated with numerous small operators. In this context, the fierce competition between operators, joint with the rapid increase in the demand for home-delivery, results in a significant increase in urban freight traffic further worsening congestion and pollution. To resolve these issues, previous research has studied the implementation of collaborative last-mile operations, with organisations sharing resources in the form of inventory space or transportation capacity. However, a common limitation of the proposed models is ignoring the effects of externalities such as network congestion due to the increased number of vehicles from selfish routing, and time windows. 

This study proposes a framework to quantify the worst efficiency loss in the urban last-mile delivery system by formulating the fully-decentralised and fully-centralised last-mile delivery problem. In doing so, we develop a Multi-depot Vehicle Routing Problem with Time Windows and Congestible Network that is solved using a bespoke Parallel Hybrid Genetic Algorithm that overcomes the non-linearities from modelling endogenous network congestion. 

The model is evaluated using a case study based on central London to assess the efficiency gaps of a realistic last-mile delivery operation. Our results show that the relative efficiency loss tends to fluctuate the most with a small number of customers until it stabilises to less than 15% for instances with over 100 customers without considering time windows. However, time windows could significantly exacerbate the degradation of efficiency and this degradation is 25% on average.

The Competition and Inefficiency in Urban Road Last-Mile Delivery


The multi-agent pickup and delivery (MAPD) problem, in which multiple agents iteratively carry materials without collisions, has received attention, but the conventional MAPD algorithms usually assume grid-like environments that are specifically designed such as automated warehouses. In these environments, many pickup/delivery locations are deployed where agents can stay for a long time, and the detours to avoid collision are plentiful because of freedom of movement. In contrast, a maze-like environment such as a rescue or a construction site generally has fewer pickup/delivery locations and the numbers may be unbalanced, resulting in many agents concentrating on these locations and inefficient operations. Moreover, the agents easily get stuck to avoid other agents and are deadlocked. Therefore, we propose a deadlock avoidance method, standby-based deadlock avoidance (SBDA), to improve transportation efficiency even in a maze-like environment. The SBDA is an algorithm using standby nodes, which is determined in real-time using the articulation-point-finding algorithm, and in which the agent is guaranteed to wait for any finite time. We demonstrated that our proposed method outperforms the conventional methods in maze-like restricted environments. Then, we analyze how the parameter for selecting standby nodes affects the performance.

Standby-Based Deadlock Avoidance Method for Multi-Agent Pickup and Delivery Tasks


Object pose estimation methods allow finding locations of objects in unstructured environments. This is a highly desired skill for autonomous robot manipulation as robots need to estimate the precise poses of the objects in order to manipulate them. In this paper, we investigate the problems of tactile pose estimation and manipulation for category-level objects. Our proposed method uses a Bayes filter with a learned tactile observation model and a deterministic motion model. Later, we train policies using deep reinforcement learning where the agents use the belief estimation from the Bayes filter. Our models are trained in simulation and transferred to the real world. We analyze the reliability and the performance of our framework through a series of simulated and real-world experiments and compare our method to the baseline work. Our results show that the learned tactile observation model can localize the pose of novel objects at 2-mm and 1-degree resolution for position and orientation, respectively. Furthermore, we experiment on a bottle opening task where the gripper needs to reach the desired grasp state to open the bottle cap.

Tactile Pose Estimation and Policy Learning for Unknown Object Manipulation


Moving target defense (MTD) has emerged as a key technique that can be used in various security applications to reduce the threat of attackers by taking away their ability to perform reconnaissance and exploit vulnerabilities. However, most of the existing research in the field assumes unrealistic access to information about the attacker's motivations and/or actions when developing MTD strategies. Many of the existing approaches also assume complete knowledge regarding the vulnerabilities of a particular application and how each of these vulnerabilities can be exploited by an attacker. In this work, we propose an algorithm that generates effective MTD strategies for web applications that does not rely on prior knowledge about the attackers. Our approach assumes that the only information the defender receives about its own reward function, is via interaction with the attacker in a repeated game setting. We evaluate our algorithm using data which is mined from the National Vulnerability Database to show that it matches the performance of the state of the art techniques, despite using much less information.

Moving Target Defense under Uncertainty for Web Applications


For cooperative mutliagent reinforcement learning tasks, we propose a novel value factorization framework in the popular centralized training with decentralized execution paradigm, called multiagent Q-learning with sub-team coordination (QSCAN). This framework could flexibly exploit local coordination within sub-teams for effective factorization while honoring the individual-global-max (IGM) condition.
QSCAN encompasses the full spectrum of sub-team coordination according to sub-team size, ranging from the monotonic value function class to the entire IGM function class, with familiar methods such as QMIX and QPLEX located at the respective extremes of the spectrum. Empirical results show that QSCAN's performance dominates state-of-the-art methods in predator-prey tasks and the Switch challenge in MA-Gym.

Multiagent Q-learning with Sub-Team Coordination


This extended abstract presents an agent-based model to enable simulations to be performed of evacuations from a multi-floor building, thus including the movement in staircases. In the model, agents select exits and staircases based on familiarity level with the building layout, spatial distance to exits, preference to evacuate via the
main entrance/exit, and visibility of exits and staircases. The agentbased model has been validated using the empirical findings of an evacuation drill in the staircase of a four-floor building. The novel contribution of this research is the development of a more realistic agent-based model aimed at providing decision support for the layout design of buildings and evacuation behavioral management in emergency evacuation. That is, the agent-based model mimics people’s natural movement in staircases, and involves agents’ exit and staircase selection, and movement on floors. Simulations have been performed to investigate the effect on evacuation time of (i)
number of agents and their familiarity with the building layout, and (ii) exit selection of agents.

An Agent-based Model for Emergency Evacuation from a Multi-floor Building

**Read paper on the following link:**

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

**Abstract:**



(Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna

Downloads

Next from AAMAS 2022

On Parameterized Complexity of Binary Networked Public Goods Game

Similar lecture

Beyond Cake Cutting: Allocating Homogeneous Divisible Goods

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

(Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible 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 2022

On Parameterized Complexity of Binary Networked Public Goods Game

Similar lecture

Beyond Cake Cutting: Allocating Homogeneous Divisible Goods

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads