United States

Applications such as employees sharing office spaces over
a workweek can be modeled as problems where agents are
matched to resources over multiple rounds. Agents’ require-
ments limit the set of compatible resources and the rounds in
which they want to be matched. Viewing such an application
as a multi-round matching problem on a bipartite compati-
bility graph between agents and resources, we show that a
solution can be found efficiently if one exists. To cope with
situations where a solution does not exist, we consider two
extensions. In the first extension, a benefit function is defined
for each agent and the objective is to find a solution to maxi-
mize the total benefit. For a general class of benefit functions
satisfying certain properties (including diminishing returns),
we show that this multi-round matching problem is efficiently
solvable. This class includes utilitarian and Rawlsian wel-
fare functions. For another benefit function, we show that the
maximization problem is NP-hard. In the second extension,
the objective is to generate advice to each agent (i.e., a subset
of requirements to be relaxed) subject to a budget constraint
so that the agent can be matched. We show that this budget-
constrained advice generation problem is NP-hard. For this
problem, we develop an integer linear programming formu-
lation as well as a heuristic based on local search. We exper-
imentally evaluate our algorithms on synthetic networks and
apply them to two real-world situations: shared office spaces
and matching courses to classrooms.

AAAI 2023

Resource Sharing Through Multi-Round Matchings

mas: applications

mas: coordination and collaboration

mas: other foundations of multiagent systems

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-23 is the Thirty-Seventh AAAI Conference on Artificial Intelligence. The theme of this conference is to create collaborative bridges within and beyond AI. Like previous AAAI conferences, AAAI-23 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and two new activities: a Bridge Program and a Lab Program. Many of these activities are tailored to the theme of bridges and all are selected according to the highest standards, with additional programs for students and young researchers. 
AAAI is providing you with a conference planner, which you can use to help organize your itinerary of activities. This includes talks to attend in person, talks to attend remotely, breaks with colleagues and your site seeing activities. To access this conference planner, please go to [https://aaai-2023.takemobi.io](https://aaai-2023.takemobi.io).

In order to access this site, you need to register. If you haven't already, please register [here](https://aaai.org/Conferences/AAAI-23/registration/).


The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines.

poster

This paper explores reward mechanisms for a query incentive network in which agents seek information from social networks. In a query tree issued by the task owner, each agent is rewarded by the owner for contributing to the solution, for instance, solving the task or inviting others to solve it. The reward mechanism determines the reward for each agent and motivates all agents to propagate and report their information truthfully. In particular, the reward cannot exceed the budget set by the task owner. However, our impossibility results demonstrate that a reward mechanism cannot simultaneously achieve Sybil-proof (agents benefit from manipulating multiple fake identities), collusion-proof (multiple agents pretend as a single agent to improve the reward), and other essential properties. In order to address these issues, we propose two novel reward mechanisms. The first mechanism achieves Sybil-proof and collusion-proof, respectively; the second mechanism sacrifices Sybil-proof to achieve the approximate versions of Sybil-proof and collusion-proof. Additionally, we show experimentally that our second reward mechanism outperforms the existing ones.

Collusion-proof And Sybil-proof Reward Mechanisms For Query Incentive Networks

The last decades are marked by massive and diverse image data, which shows increasingly high resolution and quality. However, some images we obtained may be corrupted, affecting the perception and the application of downstream tasks. A generic method for generating a high-quality image from the degraded one is in demand. In this paper, we present a novel GAN inversion framework that utilizes the powerful generative ability of StyleGAN-XL for this problem. To ease the inversion challenge with StyleGAN-XL, Clustering \& Regularize Inversion (CRI) is proposed. Specifically, the latent space is firstly divided into finer-grained sub-spaces by clustering. Instead of initializing the inversion with the average latent vector, we approximate a centroid latent vector from the clusters, which generates an image close to the input image. Then, an offset with a regularization term is introduced to keep the inverted latent vector within a certain range. We validate our CRI scheme on multiple restoration tasks (i.e., inpainting, colorization, and super-resolution) of complex natural images, and show preferable quantitative and qualitative results. We further demonstrate our technique is robust in terms of data and different GAN models. To our best knowledge, we are the first to adopt StyleGAN-XL for generating high-quality natural images from diverse degraded inputs. Code is available at https://github.com/Booooooooooo/CRI.

High-Resolution GAN Inversion for Degraded Images in Large Diverse Datasets

Although weakly-supervised techniques can reduce the labeling effort, it is unclear whether a saliency model trained with weakly-supervised data (e.g., point annotation) can achieve the equivalent performance of its fully-supervised version. This paper attempts to answer this unexplored question by proving a hypothesis: there is a point-labeled dataset where saliency models trained on it can achieve equivalent performance when trained on the densely annotated dataset. To prove this conjecture, we proposed a novel yet effective adversarial trajectory-ensemble active learning (ATAL). Our contributions are three-fold:  1) Our proposed adversarial attack triggering uncertainty can conquer the overconfidence of existing active learning methods and accurately locate these uncertain pixels. {2)} Our proposed trajectory-ensemble uncertainty estimation method maintains the advantages of the ensemble networks while significantly reducing the computational cost. {3)} Our proposed relationship-aware diversity sampling algorithm can conquer oversampling while boosting performance.
Experimental results show that our ATAL can find such a point-labeled dataset, where a saliency model trained on it obtained $97\%$ -- $99\%$ performance of its fully-supervised version with only ten annotated points per image.

Pixel is All You Need: Adversarial Trajectory-Ensemble Active Learning for Salient Object Detection

Evolutionary anti-coordination games on networks capture real-world strategic situations such as traffic routing and market competition. In such games, agents maximize their utility by choosing strategies (i.e., actions) that differ from their neighbors’ strategies. Two important problems concerning evolutionary games are the existence of a pure Nash equilibrium (NE) and the convergence time of the dynamics. In this work, we study these two problems for anti-coordination games under sequential and synchronous dynamics. For each type of dynamics, we examine two decision-making modes based on whether an agent considers its own previous action (self essential mode) or not (self non-essential mode) in choosing its next action. Using a relationship between anti-coordination games and discrete graphical dynamical systems, we show that for both forms of dynamics, finding an NE can be done efficiently for the self non-essential mode but is computationally intractable under the self essential mode. To cope with this hardness, we identify some special cases for which an NE can be found efficiently, and present the corresponding algorithms. With respect to convergence time, we show that the dynamics converges in a polynomial number of steps in the synchronous case for both modes; for the sequential case, the convergence time is polynomial only for the self non-essential mode. Through experiments, we empirically examine the convergence time and the equilibria for both synthetic and real-world networks.

Networked Anti-Coordination Games Meet Graphical Dynamical Systems: Equilibria and Convergence

The facility location game is an extensively studied problem in mechanism design. In the classical model, the cost of each agent is her distance to the nearest facility. In this paper, we consider a novel model where each facility charges an entrance fee, which is a function of the facility's location. Thus, in our model, the cost of each agent is the sum of the distance to the facility and the entrance fee of the facility. The generalized model captures more real-life scenarios. In our model, the entrance fee function can be an arbitrary function, and the corresponding preferences of agents may not be single-peaked anymore: this makes the problem complex and requires new techniques in the analysis. We systematically study the model and design strategyproof mechanisms with nice approximation ratios and also complement these with nearly-tight impossibility results. Specifically, for one-facility and two-facility games, we provide upper and lower bounds for the approximation ratios given by deterministic and randomized mechanisms, with respect to the utilitarian and egalitarian objectives. Most of our bounds are tight, and these bounds are independent of the entrance fee functions. Our results also match the results of the classical model.

Facility Location Games with Entrance Fees

Epistemic logics typically talk about knowledge of individual agents or groups of explicitly listed agents. Often, however, one wishes to express knowledge of groups of agents specified by a given property, as in ‘it is common knowledge among economists’. We introduce such a logic of common knowledge, which we term abstract-group epistemic logic (AGEL). That is, AGEL features a common knowledge operator for groups of agents given by concepts in a separate agent logic that we keep generic, with one possible agent logic being ALC. We show that AGEL is EXPTIME-complete, with the lower bound established by reduction from standard group epistemic logic, and the upper bound by a satisfiability-preserving embedding into the full µ-calculus. Further main results include a finite model property (not enjoyed by the full µ-calculus) and a complete axiomatization.

Common Knowledge of Abstract Groups

Graph Neural Networks (GNNs) are powerful tools for graph representation learning. Despite their rapid development, GNNs also face some challenges, such as over-fitting, over-smoothing, and non-robustness. Previous works indicate that these problems can be alleviated by random dropping methods, which integrate augmented data into models by randomly masking parts of the input. However, some open problems of random dropping on GNNs remain to be solved. First, it is challenging to find a universal method that are suitable for all cases considering the divergence of different datasets and models. Second, augmented data introduced to GNNs causes the incomplete coverage of parameters and unstable training process. Third, there is no theoretical analysis on the effectiveness of random dropping methods on GNNs. In this paper, we propose a novel random dropping method called DropMessage, which performs dropping operations directly on the propagated messages during the message-passing process. More importantly, we find that DropMessage provides a unified framework for most existing random dropping methods, based on which we give theoretical analysis of their effectiveness. Furthermore, we elaborate the superiority of DropMessage: it stabilizes the training process by reducing sample variance; it keeps information diversity from the perspective of information theory, enabling it become a theoretical upper bound of other methods. To evaluate our proposed method, we conduct experiments that aims for multiple tasks on five public datasets and two industrial datasets with various backbone models. The experimental results show that DropMessage has the advantages of both effectiveness and generalization, and can significantly alleviate the problems mentioned above. A detailed version with full appendix can be found on arXiv: https://arxiv.org/abs/2204.10037.

DropMessage: Unifying Random Dropping for Graph Neural Networks

Modern social networks are dynamic in their nature; new connections are appearing, and old connections are disappearing all the time. However, in our algorithmic and complexity studies, we usually model social networks as static graphs.

In this paper, we propose a new paradigm for the study of the well-known Target Set Selection problem, which is a fundamental problem in viral marketing and the spread of opinion through social networks. In particular, we use temporal graphs to capture the dynamic nature of social networks.

We show that the temporal interpretation is, unsurprisingly, NP-complete in general. Then, we study the computational complexity of this problem for multiple restrictions of both the threshold function and the underlying graph structure and provide multiple hardness lower bounds.

Maximizing Influence Spread through a Dynamic Social Network

Conversational Systems (CSys) represent practical and tangible outcomes of advances in NLP and AI. CSys see continuous improvements through unsupervised training of large language models (LLMs) on a humongous amount of generic training data. However, when these CSys are suggested for use in domains like Mental Health, they fail to match the acceptable standards of clinical care, such as the clinical process in Patient Health Questionnaire (PHQ-9). The talk will present, Knowledge-infused Learning (KiL), a paradigm within NeuroSymbolic AI that focuses on making machine/deep learning models (i) learn over knowledge-enriched data, (ii) learn to follow guidelines in process-oriented tasks for safe and reasonable genera-
tion, and (iii) learn to leverage multiple contexts and stratified knowledge to yield user-level explanations. KiL established Knowledge-Intensive Language Understanding, a set of tasks for assessing safety, explainability, and conceptual flow in CSys.

Targeted Knowledge Infusion To Make Conversational AI Explainable and Safe

A hallmark of human intelligence is that we continue to learn new information and then extrapolate the learned information onto new tasks and domains (Thrun and Pratt (1998)). While this is a fairly intuitive observation, formulating such ideas has proved to be a challenging research problem and continues to inspire new studies. Recently, there has been increasing interest in AI/ML about building models that generalize across tasks, even when they have some form of distribution shifts. How can we ground this research in a solid framework to develop principled methods for better practice? This talk will present my recent works addressing this research question, including understanding information transfer in multitask learning, identifying negative transfers in multitask learning using surrogate models, and positive and negative generalizations in data augmentation.

Premium content

Resource Sharing Through Multi-Round Matchings

Downloads

Next from AAAI 2023

Collusion-proof And Sybil-proof Reward Mechanisms For Query Incentive Networks

Similar lecture

Effective Integration of Weighted Cost-to-go and Conflict Heuristic within Suboptimal CBS

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES