In this paper we investigate the effect of an underlying social network over agents in a well-known multi-agent resource allocation problem; the housing market. We first show that, when a housing market takes place over a social network with more than two agents and these agents have an option to avoid forwarding information about it to their followers, there does not exist an exchange mechanism that simultaneously satisfies strategy-proofness, Pareto efficiency, and individual rationality. It is also impossible to find a strategy-proof exchange mechanism that always chooses an outcome in a weakened core. These results highlight the difficulty of taking into account the agents' incentive of information diffusion in the resource allocation. To overcome these negative results, we consider two different ways of restricting the problem; limiting the domain of preferences and the structure of social networks.

Mechanism Design for Housing Markets over Social Networks

Distributed Constraint Optimization Problems (DCOPs) are a powerful tool to model multi-agent coordination problems that are distributed by nature. The formulation is suitable for problems where variables are discrete and constraint utilities are represented in tabular form. However, many real-world applications have variables that are continuous and tabular forms thus cannot accurately represent constraint utilities. To overcome this limitation, researchers have proposed the Continuous DCOP (C-DCOP) model, which are DCOPs with continuous variables. But existing approaches usually come with some restrictions on the form of constraint utilities and are without quality guarantees. Therefore, in this paper, we (i) propose an exact algorithm to solve a specific subclass of C-DCOPs; (ii) propose an approximation method with quality guarantees to solve general C-DCOPs; (iii) propose additional C-DCOP algorithms that are more scalable; and (v) empirically show that our algorithms outperform existing state-of-the-art C-DCOP algorithms when given the same communication limitations.

New Algorithms for Continuous Distributed Constraint Optimization Problems

In this work, we consider a student-project-resource matching-allocation problem, where students have preferences over projects and the projects have preferences over students. Although students are many-to-one matched to projects, indivisible resources are many-to-one allocated to projects whose capacities are endogenously determined by the resources allocated to them. Traditionally, this problem is decomposed into two separate problems: (1) resources are allocated to projects based on expectations (resource allocation problem), and (2) students are matched to projects based on the capacities determined in the previous problem (matching problem). Although both problems are well-understood, if the expectations used in the first are incorrect, we obtain a suboptimal outcome. Thus, this problem must be solved as a whole without dividing it in two parts. We show that no strategyproof mechanism satisfies fairness (i.e., no student has justified envy) and weak efficiency requirements on students' welfare. Given this impossibility result, we develop a new strategyproof mechanism that strikes a good balance between fairness and efficiency and assess it by experiments


Game Theoretic Analysis for Two-Sided Matching with Resource Allocation

The ability to cooperate is one of the key features of many multi- agent systems. In this paper, we extend the well-known model of graph-restricted games due to Myerson to signed graphs, where the link between any two players may be either positive or negative. Hence, in our model, it is possible to explicitly define not only that some players are friends (as in Myerson’s model) but also that some other players are enemies. As such our games can express a wider range of situations, e.g., animosities between political parties. We say that a coalition is feasible if every two players are connected by a path of positive edges and no two players are connected by a negative edge. We define the value for signed graph games using the axiomatic approach that closely follows the celebrated char- acterisation of the Myerson value. Furthermore, we propose an algorithm for computing an arbitrary semivalue, including the one proposed by us. Moreover, we consider signed graph games with a priori defined alliances (unions) between players and propose an algorithm for the extension of the Owen value to this setting.


Signed Graph Games: Coalitional Games with Friends, Enemies and Allies

In this paper, we study the two-sided matching problem with soft diversity constraints in which each student belongs to one type and each school imposes soft targets on each type. We first identify limitations of type-specific quotas in a previous model and introduce a new general model that takes different levels of importance of types into account. Then we propose a new algorithm that yields a non-wasteful and fair outcome with respect to different levels of importance.


Multiple Levels of Importance in Matching with Distributional Constraints

S2: Game Theory 5

technical paper

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 

AAMAS 2021

Knowledge Representation, Reasoning and Planning

AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). The aim of the joint conference is to provide a single, high-profile, internationally-respected archival forum for scientific research in the theory and practice of autonomous agents and multi-agent systems.

Browse keynotes, discussions, panels and over 300 presentations.


AAMAS 2020

AAMAS is the leading scientific conference for research in autonomous agents and multi-agent systems. The AAMAS conference series was initiated in 2002 as the merging of three respected scientific meetings: the International Conference on Multi-Agent Systems (ICMAS), the International Workshop on Agent Theories, Architectures, and Languages (ATAL), and the International Conference on Autonomous Agents (AA). 

Makoto Yokoo

5

6

SHORT BIO

Presentations

Mechanism Design for Housing Markets over Social Networks

New Algorithms for Continuous Distributed Constraint Optimization Problems

Game Theoretic Analysis for Two-Sided Matching with Resource Allocation

Signed Graph Games: Coalitional Games with Friends, Enemies and Allies

Multiple Levels of Importance in Matching with Distributional Constraints

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES