Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

8-2017

Abstract

Organizing large scale projects (e.g., Conferences, IT Shows, F1 race) requires precise scheduling of multiple dependent tasks on common resources where multiple selfish entities are competing to execute the individual tasks. In this paper, we consider a well studied and rich scheduling model referred to as RCPSP (Resource Constrained Project Scheduling Problem). The key change to this model that we consider in this paper is the presence of selfish entities competing to perform individual tasks with the aim of maximizing their own utility. Due to the selfish entities in play, the goal of the scheduling problem is no longer only to minimize makespan for the entire project, but rather, to maximize social welfare while ensuring incentive compatibility and economic efficiency. We show that traditional VCG mechanism is not incentive compatible in this context and hence we provide two new practical mechanisms that extend on VCG. These new mechanisms referred to as Individual Completion based Payments (ICP) and Social Completion based Payments (SCP) provide strong theoretical properties including strategy proofness.

Keywords

Artificial intelligence, Machine design, Economic efficiency, Incentive compatibility, Incentive compatible, Large-scale projects, Project scheduling, Resource-constrained project scheduling problem, Scheduling problem, Strategy-proofness, Scheduling

Discipline

Artificial Intelligence and Robotics | Computer Engineering

Research Areas

Cybersecurity

Publication

Proceedings of the 26th International Joint Conference on Artificial Intelligence, Melbourne, Australia, 2017 August 19-25

Identifier

10.24963/ijcai.2017/619

City or Country

Melbourne, Australia

Additional URL

https://doi.org/10.24963/ijcai.2017/619

Download

Share

COinS