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

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 &lt;=d&lt;=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.

AAMAS 2020

Strategyproof Mechanisms for Activity Scheduling

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

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.

technical paper

From skipped exercise classes to last-minute cancellation of dentist appointments, underutilization of reserved resources abounds. Likely reasons include uncertainty about the future, further exacerbated by present bias. In this paper, we unite resource allocation and commitment devices through the design of contingent payment mechanisms, and propose the two-bid penalty-bidding mechanism. This extends an earlier mechanism proposed by Ma et al. (2019), assigning the resources based on willingness to accept a no-show penalty, while also allowing each participant to increase her own penalty in order to counter present bias. We establish a simple dominant strategy equilibrium, regardless of an agent's level of present bias or degree of "sophistication". Via simulations, we show that the proposed mechanism substantially improves utilization and achieves higher welfare and better equity in comparison with mechanisms used in practice and mechanisms that optimize welfare in the absence of present bias.

Penalty Bidding Mechanisms for Allocating Resources and Overcoming Present Bias

Many websites that recommend various services use crowdsourcing to collect reviews and rankings. These rankings, usually concerning a subset of all the offered alternatives, are then aggregated. Motivated by such scenarios, we axiomatise a family of positional scoring rules for profiles of possibly incomplete individual preferences. Many opportunities arise for the agents to manipulate the outcome in this setting. They may lie in order to obtain a better result by: (i) switching the order of a ranked pair of alternatives, (ii) omitting some of their truthful preferences, or (iii) reporting more preferences than the ones they truthfully hold. After formalising these new concepts, we characterise all positional scoring rules that are immune to manipulation.

Strategic Manipulation with Incomplete Preferences: Possibilities and Impossibilities for Positional Scoring Rules

Vaccination is a standard public health intervention for controlling the spread of epidemics. However, the supply of vaccines is typically limited, and therefore, their deployment needs to be optimized. Further, vaccines are produced over time, so the strategies have to be temporal. We study the problem \prob{} of designing vaccination strategies, within available budget constraints, to minimize the spread of an outbreak. This is a challenging stochastic optimization problem. We design a bicriteria approximation algorithm, which combines a linear programming based rounding, along with the sample average approximation technique. Our approach also provides the empirical approximation factor for the problem instance, relative to the optimum. We find that the approximation factor is significantly better than the worst case bound, and, in practice, is a small constant factor. Further, our method shows significantly better performance than all prior heuristics for this problem. With additional pruning techniques, we are able to scale our algorithm to networks with millions of edges.

Designing Effective and Practical Interventions to Contain Epidemics

We propose a game-theoretic approach to generalizing the classical Schelling model. At the core of our model are two features that did not receive much attention before. First, we allow multiple individuals to occupy the same location. Second, each individual's choice of location is influenced by their social network neighbors that also choose the same location. In addition, an individual's choice is influenced by others in the adjacent locations in a network-structured way, which captures the main spirit of the classical Schelling model and its numerous extensions. Our solution concept is a stable configuration represented as a pure-strategy Nash equilibrium (PSNE). We show that even for various special cases of the problem, computing or counting PSNE is provably hard. We give algorithms for computing PSNE, including efficient algorithms for several special cases. We highlight some of the attractive features of our model, such as predicting very few PSNE, through experiments.

Schelling Models with Localized Social Influence: A Game-Theoretic Framework

Report-sensitive spot-checking in peer grading systems

We develop a methodology for comparing two or more agent-based models that are developed for the same domain, but may differ in the particular data sets (e.g., geographical regions) to which they are applied, and in the structure of the model. Our approach is to learn a response surface in the common parameter space of the models and compare the regions corresponding to qualitatively different behaviors in the models. As an example, we develop an active learning algorithm to learn phase transition boundaries in contagion processes in order to compare two agent-based models of rooftop solar panel adoption.

An Active Learning Method for the Comparison of Agent-based Models

Deployment of a Plug-in multi-agent system for

Detection of anomalies and faults is a key element for long-term robot autonomy, because, together with subsequent diagnosis and recovery, allows to reach the required levels of robustness and persistency. The aim of my PhD thesis is to develop new techniques to model and quantitatively compare observed robot behaviors with nominal ones. My goal is to propose approaches for detecting anomalous behaviors of robot systems involved in complex long-term autonomy scenarios, both online, while robots are operating, and offline, after robots have completed a run of their tasks.

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

Strategyproof Mechanisms for Activity Scheduling

.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

Penalty Bidding Mechanisms for Allocating Resources and Overcoming Present Bias

Similar lecture

New Algorithms for Continuous Distributed Constraint Optimization Problems

Downloads