United Kingdom

We present a methodology to robustly estimate the competitive equilibria (CE) of combinatorial markets under the assumption that buyers do not know their precise valuations for bundles of goods, but instead can only provide noisy estimates. We first show tight lower- and upper-bounds on the buyers&#39; utility loss, and hence the set of CE, given a uniform approximation of one market by another. We then present two probably-approximately-correct algorithms for learning CE with finite-sample guarantees. The first is a baseline and the second leverages a connection between the first welfare theorem of economics and uniform approximations to adaptively prune value queries when it is determined that they are provably not part of a CE. Extensive experimentation shows that pruning achieves better estimates than the baseline with far fewer samples.

AAMAS 2021

Learning Competitive Equilibria in Noisy Combinatorial Markets

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 present a methodology to robustly estimate the competitive equilibria (CE) of combinatorial markets under the assumption that buyers do not know their precise valuations for bundles of goods, but instead can only provide noisy estimates. We first show tight lower- and upper-bounds on the buyers' utility loss, and hence the set of CE, given a uniform approximation of one market by another. We then present two probably-approximately-correct algorithms for learning CE with finite-sample guarantees. The first is a baseline and the second leverages a connection between the first welfare theorem of economics and uniform approximations to adaptively prune value queries when it is determined that they are provably not part of a CE. Extensive experimentation shows that pruning achieves better estimates than the baseline with far fewer samples.

poster

Mechanism design has traditionally assumed that the set of participants are fixed and known to the mechanism (the market owner) in advance. However, in practice, the market owner can only directly reach a small number of participants (her neighbours). Hence the owner often needs costly promotions to recruit more participants in order to get desirable outcomes such as social welfare or revenue maximization. In this paper, we propose to incentivize existing participants to invite their neighbours to attract more participants. However, they would not invite each other if they are competitors. We discuss how to utilize the conflict of interest between the participants to incentivize them to invite each other to form larger markets. We will highlight the early solutions and open the floor for discussing the fundamental open questions in the settings of auctions, coalitional games, matching and voting.

Mechanism Design Powered by Social Interactions (Blue Sky Ideas Track)

A self-governed society must have decision rules by which group decisions are made, and these rules are often codified in a written constitution. One of the defining features of a constitution is its degree of entrenchment, or how hard it is to change by amendment. If it is too easy to make amendments, then the constitution can change too frequently, leading to chaos. On the other hand, if it is too hard to make amendments, then this can also be destabilizing, as voters may begin to see the rules as less legitimate, or even seek to overturn the status quo in a revolt. As norms, priorities, and circumstances change over time and over generations a constitution must be able to adapt. Our work considers a stylized model of constitutions that use reality-aware supermajority rules to make decisions. We propose principles for designing amendment procedures for changing decision rules in these constitutions and propose a novel procedure based on these principles.

How to Amend a Constitution? Model, Axioms, and Supermajority Rules

In this work we present a novel succinct representation for large partially observed cooperative games. The proposed representation exploits estimates over marginal contributions to form compact rules representing collaboration patterns with uncertain value. Specifically, given an initial set of MC-nets rules that use prior beliefs over values instead of the actual ones, we propose two types of merging that lead to a new set of even more compact rules.

A Succinct Representation Scheme for Cooperative Games under Uncertainty

Complex networks and reputation systems are fundamental mechanisms to sustain cooperation in populations of self-regarding agents. These mechanisms are typically studied in isolation. In online social platforms, however, behavioral dynamics are likely to result from their combination. Here we investigate the relationship between social networks and reputation-based cooperation (in a Prisoner’s Dilemma setting) in large populations. We develop a new evolutionary game-theoretical model and study dynamics in networks with varying degrees of community structure. We show that networks exhibiting modular structures hamper global cooperation: reputation-based group identities emerge in different communities and strategies that uniquely cooperate with in-group members fixate, sustaining polarization and group bias. Global cooperation is recovered provided that inter-community edges are added.

Social Network Interventions to Prevent Reciprocity-driven Polarization

Off-policy evaluation (OPE) is the problem of evaluating new policies using historical data obtained from a different policy. In the recent OPE context, most studies have focused on single-player cases, and not on multi-player cases. In this study, we propose OPE estimators constructed by the doubly robust and double reinforcement learning estimators in two-player zero-sum Markov games. The proposed estimators project exploitability that is often used as a metric for determining how close a policy profile (i.e., a tuple of policies) is to a Nash equilibrium in two-player zero-sum games. We prove the exploitability estimation error bounds for the proposed estimators. We then propose the methods to find the best candidate policy profile by selecting the policy profile that minimizes the estimated exploitability from a given policy profile class. We prove the regret bounds of the policy profiles selected by our methods. Finally, we demonstrate the effectiveness and performance of the proposed estimators through experiments.

Off-Policy Exploitability-Evaluation in Two-Player Zero-Sum Markov Games

Multi-agent reinforcement learning (MARL) has been increasingly used in a wide range of safety-critical applications, which require guaranteed safety (e.g., no unsafe states are ever visited) during the learning process.Unfortunately, current MARL methods do not have safety guarantees. Therefore, we present two shielding approaches for safe MARL. In centralized shielding, we synthesize a single shield to monitor all agents' joint actions and correct any unsafe action if necessary.In factored shielding, we synthesize multiple shields based on a factorization of the joint state space observed by all agents; the set of shields monitors agents concurrently and each shield is only responsible for a subset of agents at each step.Experimental results show that both approaches can guarantee the safety of agents during learning without compromising the quality of learned policies; moreover, factored shielding is more scalable in the number of agents than centralized shielding.

Safe Multi-Agent Reinforcement Learning via Shielding

The study of exploration in the domain of decision making has a long history but remains actively debated. From the vast literature that addressed this topic for decades under various points of view (e.g., developmental psychology, experimental design, artificial intelligence), intrinsic motivation emerged as a concept that can practically be transferred to artificial agents. Especially, in the recent field of Deep Reinforcement Learning (RL), agents implement such a concept (mainly using a novelty argument) in the shape of an exploration bonus, added to the task reward, that encourages visiting the whole environment. This approach is supported by the large amount of theory on RL for which convergence to optimality assumes exhaustive exploration. Yet, Human Beings and mammals do not exhaustively explore the world and their motivation is not only based on novelty but also on various other factors (e.g., curiosity, fun, style, pleasure, safety, competition, etc.). They optimize for life-long learning and train to learn transferable skills in playgrounds without obvious goals. They also apply innate or learned priors to save time and stay safe. For these reasons, we propose to learn an exploration bonus from demonstrations that could transfer these motivations to an artificial agent with little assumptions about their rationale. Using an inverse RL approach, we show that complex exploration behaviors, reflecting different motivations, can be learnt and efficiently used by RL agents to solve tasks for which exhaustive exploration is prohibitive.

Show Me the Way: Intrinsic Motivation from Demonstrations

Goal recognition is the problem of determining an agent's intent by observing its actions. In the context of AI research, the problem is tackled for two quite different purposes: to determine an agent's most probable goal or, for human-aware planning including planned  or strategic  deception, to determine an observer's most likely belief about that goal. Making no distinction, contemporary models tend to assume an infallible observer, deceived only while it has limited access to information or if the environment itself is only partially observable. Focusing on the second purpose, we propose an extended framework that incorporates formal definitions of confirmation bias, selective attention and memory decay. In contrast to pre-existing models, our approach combines explicit consideration of prior probabilities with a principled representation of observer confidence and distinguishes between potential observations  i.e., every observable event within the observer's frame of reference  and recalled observations which we model as a function of attention and memory. We show that when these factors are taken into consideration, false beliefs may arise and can be made to persist, even in a fully observable environment  thus providing a perceptual model readily incorporated into the "thinking" of an adversarial agent for the purpose of strategic deception.

Extended Goal Recognition: A Planning-Based Model for Strategic Deception

We consider exploration tasks in which an autonomous mobile robot incrementally builds maps of initially unknown indoor environments. In such tasks, the robot makes a sequence of decisions on where to move next that, usually, are based on knowledge about the observed parts of the environment.   In this paper, we present an approach that exploits a prediction of the geometric structure of the unknown parts of an environment to improve exploration performance. In particular, we leverage an existing method that reconstructs the layout of an environment starting from a partial grid map and that predicts the shape of partially observed rooms on the basis of geometric features representing the regularities of the indoor environment. Then, we originally employ the predicted layout to estimate the amount of new area the robot would observe from candidate locations in order to inform the selection of the next best location and to early stop the exploration when no further relevant area is expected to be discovered. Experimental activities show that our approach is able to exploit the predicted layout of partially observed rooms in order to speed up the exploration.

Exploration of Indoor Environments through Predicting the Layout of Partially Observed Rooms

We present an ascending-price mechanism for a multi-sided market with a variety of participants, such as manufacturers, logistics agents, insurance providers, and assemblers. Each deal in the market may consist of a combination of agents from separate categories, and different such combinations are simultaneously allowed. This flexibility lets multiple intersecting markets be resolved as a single global market. Our mechanism is obviously-truthful, strongly budget-balanced, individually rational, and attains almost the optimal gain-from-trade when the market is sufficiently large.

Learning Competitive Equilibria in Noisy Combinatorial Markets

Next from AAMAS 2021

Mechanism Design Powered by Social Interactions (Blue Sky Ideas Track)

Similar lecture

Promoting Fair Proposers, Fair Responders or Both? Cost-Efficient Interference in the Spatial Ultimatum Game