United Kingdom

We study the complexity of finding a Walrasian equilibrium in markets where the agents have  k -demand valuations. These valuations are an extension of unit-demand valuations where a bundle&#39;s value is the maximum of its  k -subsets&#39; values. For unit-demand agents, where the existence of a Walrasian equilibrium is guaranteed, we show that the problem is in quasi-NC. For $k=2$, we show that it is NP-hard to decide if a Walrasian equilibrium exists even if the valuations are submodular, while for $k=3$ the hardness carries over to budget-additive valuations. In addition, we give a polynomial-time algorithm for markets with 2-demand single-minded valuations, or unit-demand valuations.

AAMAS 2021

Walrasian Equilibria in Markets with Small Demands

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 

We study the complexity of finding a Walrasian equilibrium in markets where the agents have  k -demand valuations. These valuations are an extension of unit-demand valuations where a bundle's value is the maximum of its  k -subsets' values. For unit-demand agents, where the existence of a Walrasian equilibrium is guaranteed, we show that the problem is in quasi-NC. For $k=2$, we show that it is NP-hard to decide if a Walrasian equilibrium exists even if the valuations are submodular, while for $k=3$ the hardness carries over to budget-additive valuations. In addition, we give a polynomial-time algorithm for markets with 2-demand single-minded valuations, or unit-demand valuations.

technical paper

Artificial intelligence (AI) planning models play an important role in decision support systems for disaster management e.g. typhoon contingency plan development. However, constructing an AI planning model always requires significant amount of manual effort, which becomes a bottleneck to emergency response in a time-critical situation. In this demonstration, we present a framework of automating a domain model of planning domain definition language from natural language input through deep learning techniques. We implement this framework in a typhoon response system and demonstrate automatic generation of typhoon contingency plan from official typhoon plan documents.

ATPT: Automate Typhoon Contingency Plan Generation from Text

We model interpretive blindness, a type of epistemic bias that poses a problem for learning from testimony, in which one acquires information from text or conversation but lacks direct access to ground truth. Interpretive blindness arises when a co-dependence between background beliefs and interpretation leads to a dynamic process of bias hardening that impedes or precludes learning. We argue that when bodies of data are argumentatively complete, even constraints from hierarchical Bayesian learning designed to promote good epistemic practices will fail to stop interpretive blindness.

Interpretive Blindness and the Impossibility of Learning from Testimony

We present the first explicit-state method for analysing and ensuring the safety of DRL agents for Atari games. Our method only requires access to the emulator. We give a suite of 42 properties that characterise "safe behaviour" for 31 games. We evaluate the safety of the best available DRL agents which, as our experiments show, violate most of our properties. We propose a countermeasure that implements shielding using bounded explicit-state exploration. Our method improved their overall safety, producing the safest DRL agents for Atari games currently available.

Shielding Atari Games with Bounded Prescience

Humans can move their bodies and eyes actively to perceive the state of the environment they are surrounded by. Autonomous robots are needed to learn this ability, so called active perception, to behave as humans do. In this paper, we propose a reinforcement learning algorithm to make the robots have the perceptual ability. In our algorithm, we simultaneously train two agents which control the robot and its sensor on the robot to achieve a task. We conducted experiments on navigation tasks in a 3D environment where useful information for the task achievement is partially occluded. The experimental results show that our algorithm can obtain better perceptual behavior and achieve higher success rates than conventional reinforcement learning algorithms.

Simultaneous Learning of Moving and Active Perceptual Policies for Autonomous Robot

We address the problem of multiagent credit assignment  in a large scale multiagent system. Difference rewards (DRs) are an effective tool to tackle this problem, but their exact computation is known to be challenging even for small number of agents. We propose a scalable method to compute difference rewards based on aggregate information in a multiagent system with large number of agents by exploiting the symmetry present in several practical applications. Empirical evaluation on two multiagent domains  air-traffic control and cooperative navigation, shows better solution quality than previous approaches.

Approximate Difference Rewards for Scalable Multigent Reinforcement Learning

In this paper, we present a novel approach for optimising long-term tactical and strategic decision-making in football (soccer) by encapsulating events in a league environment across a given time frame. We model the teams' objectives for a season and track how these evolve as games unfold to give a fluent objective that can aid in decision-making games. We develop Markov chain Monte Carlo and deep learning-based algorithms that make use of the fluent objectives in order to learn from prior games and other games in the environment and increase the teams’ long-term performance. Simulations of our approach using real-world datasets from 760 matches shows that by using optimised tactics with our fluent objective and prior games, we can on average increase teams mean expected finishing distribution in the league by up to 35.6%.

Optimising Long-Term Outcomes using Real-World Fluent Objectives: An Application to Football

Can artificial agents benefit from human conventions? Human societies manage to successfully self-organize and resolve the tragedy of the commons in common-pool resources, in spite of the bleak prediction of non-cooperative game theory. On top of that, real-world problems are inherently large-scale and of low observability. One key concept that facilitates human coordination in such settings is the use of conventions. Inspired by human behavior, we investigate the learning dynamics and emergence of temporal conventions, focusing on common-pool resources. Extra emphasis was given in designing a realistic evaluation setting: (a) environment dynamics are modeled on real-world fisheries, (b) we assume decentralized learning, where agents can observe only their own history, and (c) we run large-scale simulations (up to 64 agents).

Improved Cooperation by Exploiting a Common Signal

Taxi fleets and car aggregation systems are an important component of the urban public transportation system. Taxis and cars in taxi fleets and car aggregation systems (e.g., Uber) are dependent on a large number of self-controlled and profit-driven taxi drivers, which introduces inefficiencies in the system. There are two ways in which taxi fleet performance can be optimized: (i) Operational decision making: improve assignment of taxis/cars to customers, while accounting for future demand; (ii) strategic decision making: optimize operating hours of (taxi and car) drivers. Existing research has primarily focused on the operational decisions in (i) and we focus on the strategic decisions in (ii).

Adaptive Operating Hours for Improved Performance of Taxi Fleets

We study how wealth inequality influences behavioral dynamics in groups of independent reinforcement learners facing a threshold public goods dilemma with uncertain returns. The game allows individuals to contribute or not to a common pool to reduce their chances of future losses. The non-linearity introduced by the threshold, the stochasticity introduced by the risk and the wealth heterogeneity of players result in a game setting with multiple equilibria. We find that the learners' dynamics in this case play a major role in determining the attained equilibrium point. Our results suggest that, under individual-based learning, wealth inequality can have sizable effects on the emerging collective behaviors, decreasing the overall chances of group success. Moreover, we compute the class-based Nash equilibria (i.e., where same wealth-class agents are assumed to play the same strategy) for this game and compare the performance of groups composed of independent learning agents with the performance obtained under the payoff maximizing class-based Nash equilibrium. We find that the learned strategies never really match optimal performance for all tested values of risk.

Cooperation between Independent Reinforcement Learners under Wealth Inequality and Collective Risks

In service robot applications, planning is often integrated with task allocation.  Linear Temporal Logic (LTL) as an expressive high-level formalism is widely used for task specification, and allows for formalised restrictions on temporal sequences of tasks.   In multiagent planning, a Multi-Objective Markov Decision Process extends the standard model with vector rewards capturing possibly conflicting planning objectives. Such objectives include the success rates of accomplishing individual tasks, and the cost budgets for individual agents. In this paper, we consider the problem of concurrently allocating LTL task sequences to a team of agents and calculating optimal task schedulers simultaneously, satisfying cost and probability thresholds. We reduce this problem to multi-objective scheduler synthesis for a team MDP structure, whose size is linear in the number of agents. Our preliminary experiment demonstrates the scalability of our approach.

Walrasian Equilibria in Markets with Small Demands

Downloads

Next from AAMAS 2021

ATPT: Automate Typhoon Contingency Plan Generation from Text

Similar lecture

An Online Human-Agent Interaction System: A Brain-controlled Agent Playing Games in Unity

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Walrasian Equilibria in Markets with Small Demands

.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

ATPT: Automate Typhoon Contingency Plan Generation from Text

Similar lecture

An Online Human-Agent Interaction System: A Brain-controlled Agent Playing Games in Unity

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads