Hitoshi Kiya and Izumi Ito (March 1st 2010). Phase Scrambling for Image Matching in the Scrambled Domain, Signal Processing, Sebastian Miron, IntechOpen, DOI: 10.5772/8520.

Soo Wook Kim and Kanghwa Choi (February 1st 2008). A Dynamic Resource Allocation on Service Supply Chain, Supply Chain, Vedran Kordic, IntechOpen, DOI: 10.5772/5351.

Holger Voos (January 1st 2009). Agent-Based Distributed Resource Allocation in Continuous Dynamic Systems, Multiagent Systems, Salman Ahmed and Mohd Noh Karsiti, IntechOpen, DOI: 10.5772/6593. 

New Zealand

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&#39; 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


AAMAS 2020

Game Theoretic Analysis for Two-Sided Matching with Resource Allocation

stages 

COLING, the International Conference on Computational Linguistics, is one of the premier conferences for natural language processing and computational linguistics. Often grouped within the field of artificial intelligence, but actually pre-dating the development of artificial intelligence, advances in computational linguistics and natural language processing are now some of the major drivers behind the use of artificial intelligence for commercial and social applications – for example, on-line search, machine translation and with voice-assisted conversational devices.

First established in 1965, the biennial COLING conference is held in diverse parts of the globe and attracts participants from both top-ranked research centers and emerging countries. Today, the most important developments in our field are taking place not only in universities and academic research institutes, but also in industrial research departments and in technological startups. COLING conferences provide opportunities for all these communities to showcase their exciting developments.

COLING 2020

COLING, the International Conference on Computational Linguistics, is one of the premier conferences for natural language processing and computational linguistics. Often grouped within the field of artificial intelligence, but actually pre-dating the development of artificial intelligence, advances in computational linguistics and natural language processing are now some of the major drivers behind the use of artificial intelligence for commercial and social applications – for example, on-line search, machine translation and with voice-assisted conversational devices.

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


technical paper

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

We study the well-known Sequential Posted Pricing scheme with one item, under the Bayesian setting that the value of each participating agent to the item is drawn from her own value distribution, which is known to the auctioneer as prior information. Each agent comes in to the auction market sequentially, and is offered a take-it-or-leave-it price. The goal of the auctioneer is to maximize her expected revenue.
This family of mechanisms has been proved to perform well compared to optimal mechanism under the Bayesian framework in various settings, but nothing was previously known on the complexity of computing an optimal sequential posted pricing. 

In this paper, we show that finding an optimal sequential posted pricing is NP-complete even when the value distributions are of support size three. For the upper bound, we introduce polynomial-time algorithms when the distributions are of support size at most two, or their values are drawn from any identical distributions. As a by-product, we also show the same results hold for order-oblivious posted pricing scheme where after the auctioneer posts the prices, agents come into the auction in an adversarial order.
We also study the constrained sequential posted pricing where the auction only runs for a fixed number of $\tau$ rounds, and give polynomial-time algorithms when the distributions are of support size at most two. Moreover, we extend our algorithm to cases when the values are decayed with time or the item has several copies. To the best of our knowledge, this is the first result that fully characterizes the computational complexity of sequential posted pricing family. 


On the Complexity of Sequential Posted Pricing

The Belief Desire Intention (BDI) model of agency is a popular and mature paradigm for designing and implementing multiagent systems. There are several agent implementation platforms that follow the BDI model. In BDI systems, the agents typically have to pursue multiple goals, and often concurrently. The way in which the agents commit to achieving their goals forms their intentions. There has been much work on scheduling the intentions of agents. However, most of this work has focused on scheduling the intentions of a single agent with no awareness and consideration of other agents that may be operating in the same environment. They schedule the intentions of the single-agent in order to maximise the total number of goals achieved. In this work, we investigate techniques for scheduling the intentions of an agent in a multiagent setting, where an agent is aware (or partially aware) of the intentions of other agents in the environment. We use a Monte Carlo Tree Search (MCTS) based approach and show that our intention-aware scheduler generates better outcomes in cooperative, neutral (selfish) and adversarial settings than the state-of-the-art schedulers that do not consider other agents' intentions.

Intention-Aware Multiagent Scheduling

Threshold task games (TTGs) are a class of cooperative games in which participants form coalitions to complete tasks associated with different rewards and thresholds for success. We provide efficient algorithms for computing approximately optimal coalition structures in TTGs. We also present non-trivial bounds on the cost of stability for this class. We put our theoretical results to practice; we design a web-based framework which allows human players to interact in a collaborative task-based model. Our analysis of human play in two different countries shows that players succeed in general to form optimal coalition structures, and converge to approximately stable payoff divisions.


Threshold Task Games: Theory, Platform and Experiments

Recent work studied Stackelberg security games with multiple defenders, in which heterogeneous defenders allocate security resources to protect a set of targets against a strategic attacker. Equilibrium analysis was conducted to characterize outcomes of these games when defenders act independently. Our starting point is the observation that the use of resources in equilibria may be inefficient due to lack of coordination. We explore the possibility of reducing this inefficiency by coordinating the defenders---specifically, by pooling the defenders' resources and allocating them jointly. The defenders' heterogeneous preferences then give rise to a collective decision-making problem, which calls for a mechanism to generate joint allocation strategies. We seek a mechanism that encourages coordination, produces efficiency gains, and incentivizes the defenders to report their true preferences and to execute the recommended strategies. Our results show that, unfortunately, even these basic properties clash with each other and no mechanism can achieve them simultaneously, which reveals the intrinsic difficulty of achieving meaningful defense coordination in security games. On the positive side, we put forward mechanisms that fulfill some of these properties and we identify special cases of our setting where more of these properties are compatible.


Mechanism Design for Defense Coordination in Security Games

The problem of probabilistic goal recognition consists of automatically inferring a probability distribution over a range of possible goals of an autonomous agent based on the observations of its behavior. The state-of-the-art approaches for probabilistic goal recognition assume the full knowledge about the world the agent operates in and possible agent’s operations in this world. In this paper, we propose a framework for solving the probabilistic goal recognition problem using process mining techniques for discovering models that describe the observed behavior and diagnosing deviations between the discovered models and observations. The framework imitates the principles of observational learning, one of the core mechanisms of social learning exhibited by humans, and relaxes the above assumptions. The reported experimental results confirm the effectiveness and efficiency of the approach, both for rational and irrational agents’ behaviors.


Goal Recognition Using Off-The-Shelf Process Mining Techniques

Trajectory-User Linking (TUL), which links trajectories to users, is a recently introduced trajectory mining task with a wide spectrum of applications, ranging from personalized recommendation systems and location-based social networks to potential criminals identification. Previous approaches on solving the TUL task generally rely on classic models or Recurrent Neural Network (RNN) models. However, their prediction accuracy is always not satisfactory due to the following reasons: 1) trajectory data is low-sampling and sparse; 2) user mobility patterns are high-order and multi-periodic; and 3) previous approaches fail to utilize existing abundant features. In this paper, we propose DeepTUL, which is composed of a feature representation layer and a recurrent network with attention mechanism, to solve TUL task. DeepTUL not only combines multiple features that govern user mobility to model high-order and complex mobility patterns, but also learns from labeled historical trajectory to capture multi-periodic nature of user mobility and alleviate the data sparsity problem. Extensive experiments show that DeepTUL yields significant improvements over the existing methods on two types of real-life mobility datasets (i.e., check-in dataset and WLAN dataset). Moreover, DeepTUL provides intuitive interpretation into the trajectory-user linking.


Trajectory-User Linking with Attentive Recurrent Network

We propose a deep reinforcement learning algorithm for semi-cooperative multi-agent tasks, where agents are equipped with their separate reward functions, yet with some willingness to cooperate. It is intuitive that defining and directly maximizing a global reward function leads to cooperation because there is no concept of selfishness among agents. However, it may not be the best way of inducing such cooperation due to problems that arise from training multiple agents with a single reward (e.g., credit assignment). In addition, agents may intentionally be given separate reward functions to induce task prioritization whereas a global reward function may be difficult to define without diluting the effect of different tasks and causing their reward factors to be disregarded. Our algorithm, called Peer Evaluation-based Dual DQN (PED-DQN), proposes to give peer evaluation signals to observed agents, which quantify how they strategically value a certain transition. This exchange of peer evaluation among agents over time turns out to render agents to gradually reshape their reward functions so that their action choices from the myopic best response tend to result in a more cooperative joint action.

Inducing Cooperation through Reward Reshaping based on Peer Evaluations in Deep Multi-Agent Reinforcement Learning

Given the preferences of several agents over a set of alternatives, there may be competing views on which of the alternative would be “best” to choose. We propose a formal model, grounded in social choice theory, for providing a justification for a given choice in the context of a given corpus of basic normative principles (so-called axioms) on which to base any possible step-by-step explanation for why a given target alternative should be elected in a given situation. Thus, our notion of justification has both an explanatory and a normative component. We also develop an algorithm for computing such justifications that exploits the analogy between
the notion of explanation and the concept of minimal unsatisfiable subset used in constraint programming. Finally, we report on an application of a proof-of-concept implementation of our approach for an experimental study of the explanatory power of several axioms proposed in the social choice literature.


Automated Justification of Collective Decisions via Constraint Solving

In this work, we study the fair resource sharing problem, where a set of resources needs to be shared by a set of agents. Each agent is unit-demand and each resource can serve a limited number of agents. The agents have (heterogeneous) preferences for the resources, and preferences for other agents with whom they share the resources. Our definition of fairness is mainly captured by envy-freeness. Due to the fact that an envy-free assignment may not exist even in simple settings, we propose a way to relax the definition: Pareto envy-freeness, where an assignment is Pareto envy-free if for any two agents i and j, agent i does not envy agent j for her received resource or the set of agents she shares the resource with. We study
to what extent Pareto envy-free assignments exist. Particularly, we are interested in a typical model, dorm assignment problem, where a number of students need to be accommodated to the dorms with the same capacity and the students’ preferences for dorm-mates are binary. We show that when the capacities of the dorms are 2, a Pareto envy-free assignment always exists and can be found in polynomial time; however, if the capacities increase to 3, Pareto envy-freeness cannot be guaranteed any more.


Game Theoretic Analysis for Two-Sided Matching with Resource Allocation

Downloads

Next from AAMAS 2020

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

Similar lecture

How low can you go? Dimensionality in Lexical Semantic Change Detection

Game Theoretic Analysis for Two-Sided Matching with Resource Allocation

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

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

Similar lecture

How low can you go? Dimensionality in Lexical Semantic Change Detection

Downloads