Liliana Grigoriu (November 29th 2019). Approximation for Scheduling on Parallel Machines with Fixed Jobs or Unavailability Periods [Online First], IntechOpen, DOI: 10.5772/intechopen.89694. 

Trung Dung Ngo and Henrik Schioler (May 1st 2008). Randomized Robot Trophallaxis, Recent Advances in Multi Robot Systems, Aleksandar Lazinica, IntechOpen, DOI: 10.5772/5484.

New Zealand

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

Recent years have seen various designs of strategyproof mechanisms in the facility location game and the obnoxious facility game, by considering the facility as a point. In this paper, we extend that point to be an interval and study a novel activity scheduling game to schedule an activity in the time domain [0, 1] based on all agents’ time reports. The activity lasts for a time period of d with 0 <=d<=1, and each agent i wants his private time 𝑡𝑖 to be within the activity duration [y,y+d] or at least as close as possible. Thus his cost is the time difference between his time t_i and the activity duration [y, y+d]. The social cost is the summation of all agents’ costs. Our objective is to choose the activity starting time 𝑦 so that the mechanisms are strategyproof (truthful) and efficient. We design a mechanism outputting an optimal solution and prove it is group strategyproof. For minimizing the maximum cost, we also design a strategyproof mechanism with approximation ratio 2. In the obnoxious activity scheduling game, each agent prefers his conflict time t_i to be far away from the activity duration [y,y+d]. We respectively design deterministic and randomized group strategyproof mechanisms with provable approximation ratios and also show the lower bounds. Besides, for extension, we consider the cost/utility as the characteristic function and find group strategyproof mechanisms for minimizing the social cost and maximizing the social utility.

Strategyproof Mechanisms for Activity Scheduling

Downloads

Next from AAMAS 2020

Penalty Bidding Mechanisms for Allocating Resources and Overcoming Present Bias

Similar lecture

New Algorithms for Continuous Distributed Constraint Optimization Problems