Mechanism Design for Strategic Project Scheduling

1 Introduction

Resource Constrained Project Scheduling Problems (RCPSPs) [Kolisch and Sprecher, 1996; Pinedo, 2008] have been studied extensively in the context of manufacturing, project management and logistics. The focus is on minimizing the time taken to complete a set of tasks pertaining to a common project within the context of resource constraints. Given the NP-Hard complexity of solving RCPSPs, existing research has focussed on methods for generating high quality solutions efficiently [Vanhoucke and Coelho, 2016; Varakantham et al., 2016; Schutt et al., 2013; Fu et al., 2012].

While RCPSPs represent task scheduling, they do not represent allocation and execution of tasks when multiple selfish individuals/companies are present. For instance, consider the project of organizing an F1 race in a city (can be extended to any other major event or project). There are multiple tasks (putting up barricades, organizing logistics, selling tickets etc.) each of which can be done by different individuals or companies, each having their selfish interest (typically maximizing profits) in performing the task. Resources on which tasks will be performed are the roads, locations for congregating crowds, etc. that are typically controlled by the city. In order to represent such problems, we focus on a strategic variant of RCPSP in this paper.

Apart from the underlying RCPSP, we have the following additions in a strategic RCPSP: (i) There are multiple selfish agents interested in performing tasks. More importantly, different agents can propose different durations and costs for attending a task. Such information is not publicly available at the time of task bidding; (ii) For the central authority, there is a value associated with finishing the project at a certain time. This is typically a monotonically decreasing function of project makespan (duration to finish the project) that rewards early finish to the project. Given these two additions, our goal is to design a mechanism that will ensure agents truthfully reveal their types (durations and costs for tasks) and also finish the project at the earliest possible time. Truthful revelation is a desirable property to avoid delays in projects (due to wrong reporting by agents) or unhappiness on part of agents executing tasks (due to payments that are lower than desired).

There has been a significant focus on mechanism design for machine scheduling problems [Heidenreich et al., 2007]. The general VCG mechanism [Vickrey, 1961; Clarke, 1971; Groves, 1973] can be applied for certain basic scheduling problems without precedence or resource constraints among tasks. A characterisation of mechanisms for two machines showing that only task-independent mechanisms can be truthful was provided in [Dobzinski and Sundararajan, 2008]. Nisan and Ronen [Nisan and Ronen, 2001] examined lower and upper bounds on approximation using deterministic and randomized mechanisms for the unrelated machines scheduling problem. There are multiple key differences between work on selfish machine scheduling and the work presented in this paper: (i) In selfish scheduling, agents are competing for resources to finish their own job. However, in strategic RCPSP, agents are competing to do tasks that are part of a project. There is no competition for resources and are allocated by central authority; (ii) There are temporal dependencies between tasks in RCPSP; and (iii) Each task can require multiple resources of different types and there is a capacity for each resource type in RCPSP. In selfish scheduling, there is typically just one type of resources.

Another thread of interest with respect to mechanism design is in task allocation settings. In [Archer and Tardos, 2007], the problem of hiring a team of agents to perform a project was considered and the cost of truthfulness was evaluated. As an extension of that problem, scenarios where the agents first form teams and then bid for as consolidated groups rather than as individuals were examined in [Skowron et al., 2017]. Different from our work, the problem of hiring a team is assumed without task dependencies and resource capacity constraints. Porter et al. [Porter et al., 2008] considered task allocations where tasks can fail. They provided mechanisms where payment function is dependent on outcome of task execution and not just on reported types. We build on this idea in our mechanisms described later. There have been other works on mechanism design for machine scheduling problems, however there is a major difference. In RCPSP, the processing of tasks might need multiple resources of different types, rather than one machine. Therefore, the focus here is on developing scalable mechanisms for a more general and practically relevant project scheduling problem.

There has also been existing research on resource unconstrained scheduling problems in a decentralised manner using game theory. Nash equilibria for scheduling with controllable processing times was examined in [Agnetis et al., 2015] and in [Est´evez-Fern´andez, 2012], an approach for penalty and reward sharing in projects was proposed. Our work focusses on problems with resource capacity constraints and fixed processing times.

We make three key contributions with respect to designing mechanisms for the strategic RCPSP: (i) We formally define the strategic model and its objective. (ii) We then show that the well known VCG mechanism is not incentive compatible for the strategic RCPSP. (iii) Finally, we provide two mechanisms that build on VCG, namely SCP and ICP with strong theoretical properties. Specifically, our ICP mechanism is able to ensure that truthful behaviour is the dominant strategy and also that it is better for agents to participate in the project with their true type. One practical difference between SCP and ICP is the timing of making payment to agents: in SCP, payments are provided after the whole project completes; while in ICP, an agent can get the payment immediately after the allocated task(s) are performed.

2 Background: RCPSP

The Resource Constrained Project Scheduling Problem (RCPSP) consists of a set of tasks T = {τ1, τ2, ..., τN}. Each task τq has a duration denoted by dq where q = 1, ...,N. There are K types of reusable resources each with a limited capacity represented by Ck. Each task τq requires rqk units of type k resources during execution where k = 1, ..., K. In addition, two dummy tasks τ0 and τN+1 with zero durations are introduced to represent project source and sink, respectively.

A schedule is an assignment of start times to all tasks, i.e. a vector (s1, s2, ...sN), where sq represents the start time of τq. Let eq be the end time of task τq, we then have sq +dq = eq. The project makespan, which is the start time of the sink activity τN+1, can be given by M = sN+1 = maxq=1,...N eq.

There are two types of scheduling constraints, namely precedence constraints and resource constraints. Precedence constraints specify precedence relationships between tasks. τq precedes τz implies that τz cannot start before τq ends, i.e., sz - sq ≥ dq. Resource constraints restrict the total resource consumption during project execution. A schedule is resource feasible if at each time t, the total demand of tasks for any resource type k does not exceed its capacity Ck.

Typically, the objective of RCPSP is to find a start time schedule with the minimum makespan that satisfies both precedence and resource constraints. Instead of a start time schedule, in this paper we focus on computing an execution policy referred to as Partial Order Schedule (POS) ([Policella et al., 2007]) that minimizes the makespan. A POS represents a set of partially ordered tasks such that any embedded temporal feasible solution is guaranteed to be resource feasible. One property of POS is that it can provide an online policy in terms of when and what tasks to start. Within a POS, each task retains a set of feasible start times thereby providing more flexibility than a traditional schedule, where each task is restricted to start at a specific time.

3 Model: Strategic RCPSP

We consider a strategic model of RCPSP where there are multiple selfish agents bidding to perform individual tasks. Unlike in RCPSP, where the only goal is to compute an execution strategy or start time schedule, in a strategic RCPSP, there are three specific goals: (i) An execution strategy (POS) for tasks to be executed; (ii) Allocation of tasks to agents; (iii) Payments to agents for performing allocated tasks. In terms of representation, there are three key components: the underlying RCPSP, valuation function associated with project completion, and models for selfish agents interested in performing individual tasks.

First, we have the underlying RCPSP model as introduced in Section 2. There are precedence constraints between tasks of the form sz - eq ≥ Tqz, where Tqz is an non-negative value that specifies τz can only be started when τq has already finished for a certain time period of Tqz. The second component that adds to the strategic nature of RCPSP is a valuation, V (.) for completion of the project, which is typically a monotonically non-increasing function over the value of project makespan. Finally, we have a set of agents, A = {a1 , ...aM } competing for performing tasks. The set of tasks of interest for agent i is given by Qi . Let diq (θi ) and ciq (θi ) represent the duration of task q and the cost for executing that task, respectively. The actual type of i is denoted by θi = (ci , di ), where ci and di are vectors of costs and durations with

However, the actual type is a private information when agents express their interest in executing tasks and agents may make false declarations for self interests.

We aim to solve the strategic RCPSP by designing mechanisms that can provide incentives to agents so as to reveal truth about their types. This will ensure that individual tasks are executed as expected by agents, which in turn guarantees a successful project delivery. We wish to avoid situations where individual agents indicate lower durations or lower costs to increase the chance of executing a task (in the hope of gaining revenue from the task and not executing it on time). Given that it is hard to predict task durations accurately even for individual agents, mechanisms that over penalize (e.g., million dollars for any wrong reporting) after realising true durations are not applicable.

4 Mechanisms

In this work, we focus on direct revelation mechanisms. That is, the mechanism is directly based on the type reported by agents. Here is the flow of various steps involved in getting a project executed: (1) Agents report types. (2) Based on agents' reported types, a central authority decides on the task allocation and execution policy. (3) Agents then perform their allocated tasks according to the execution policy. (4) Depending on the mechanism, they can receive payments/contracts based either on reported types or on actual type (that is available after actual completion of tasks).

Let Θi denote the type space for agent i. Agent i's reported type ˆ θi may be different from its true type θi in order to gain a favorable outcome. A mechanism, Γ is defined as:

where Θ = Θ1 × · · · × ΘM . The function g(ˆ θ) maps the declaration of agents, ˆ θ to an output o ∈ O that is defined as:

where f(ˆ θ) is the allocation vector with f i q (ˆ θ) = 1 indicating that task τq is allocated to agent i and f i q (ˆ θ) = 0 otherwise. y( ˆ θ) denotes the partially ordered schedule, with yqz(ˆ θ) = 1 representing that task τz can only start after task τq finishes. The execution policy y can also store information about the exact precedence lags, which is the minimum time to wait after previous task finishes. Finally, p(ˆ θ) represents the payment to individual agents from the central for executing the allocated tasks. If a task is not allocated to an agent, then both cost and duration for that agent on the task will be zero.

One key differentiating factor in this mechanism when compared to mechanisms for task allocation or traditional machine scheduling problems is the presence of the execution policy, POS. When agents provide false reports of processing times, the deterministic schedule with fixed starting times of tasks cannot be employed to evaluate the impact of their declarations, because any wrong reporting of durations can render the schedule infeasible. However, by using a POS, we are guaranteed to get a feasible schedule and consequently values of false reporting can be evaluated. We provide specifics of the mechanisms employed in the next two subsections.

4.1 Payments and Participant Utilities

We first define some of the basic terms required for computing payments and utilities. Given the allocation f, POS y and revealed type ˆ θ, the project makespan can be given by M(f( ˆ θ), y(ˆ θ), ˆ θ) = sN+1 (f(ˆ θ), y(ˆ θ), ˆ θ) with N +1 referring to the sink task. Value for the central authority is denoted by V (M(f(ˆ θ), y(ˆ θ), ˆ θ)), where V (·) is a monotonically nonincreasing function over the value of project makespan.

Given the revealed type ˆ θ, welfare for all participants denoted by W(f(ˆ θ), y(ˆ θ), ˆ θ), can be defined as the center's value minus the cost incurred by all agents, i.e.,

where

with C iq (ˆ θ) representing the cost for agent i by performing τq (if it is allocated to i), and V = ∑i V i with V i representing the value contributed by agent i. The solution framework we provide allow for a flexible design of the individual valuation V i . For example, if V (.) is linear with the sole makespan, a direct way to evaluate an agent's contribution by performing task τq is by determining a ratio 0 ≤ ρiq ≤ 1 which can be calculated as the cumulative portions of the task duration over the total makespan, divided by the number of tasks in parallel. That is, V i = V ∑q ρiq = V ∑q ∑t 1/(|Tt| · M), where the duration of τq can be divided into diq time units and |Tt| is the number of tasks in parallel at the tth time unit (t = 1, ...diq ). Note that properties of our proposed mechanisms (which will be introduced in later sections) hold independent of the explicit representation of individual valuation.

Let the superscript -i on a vector denote that the term for agent i has been omitted from the vector. For example, θ-i = (θ1 , ..., θi-1 , θi+1 , ...θM ). W-i () is employed to indicate the welfare of all participants excluding i. Each agent would receive a certain amount of payment from the center after performing the allocated task(s). In the following, we will present payments corresponding to three different mechanisms: (i) VCG payment denoted by piVCG. (ii) Social Completion based Payment denoted by piSCP . (iii) Individual Completion based Payment denoted by piICP .

VCG Mechanism: Following VCG mechanism, payment for i can be defined as the difference of social welfare of other agents (denoted by W-i|i V CG) when i is present, and the optimal welfare (denoted by W-i VCG) when i is not present. That is,

It should be noted that with VCG, agents would have incentive to increase the payoff by misreporting their types, since the utility function depends on the reported types.

SCP Mechanism: Motivated by VCG's lack of incentive compatibility due to dependence on reported types, we propose a payment function that depends not only on the task allocation and execution policy (derived based on the declarations ˆ θ), but also on the actual types (denoted by θ) of agents at completion, which can be defined as:

where W-i,i is a sum of welfare for other participants when i is present and the valuation of i (denoted by V i ), i.e.,

Note that W-i,i is calculated corresponding to the allocation and POS derived based on declarations ˆ θ, but with durations and costs taken from the real types. Since the truth is not publicly known, this term can only be calculated after execution of tasks and realisation of costs and durations. The second termW-i of Eqn 2 on the other hand computes the welfare for all agents excluding i when i is not present, according to reported types of all other agents excluding i, i.e., ˆ θ-i .

In the first term of payment definition pi (ˆ θ) in Eqn 2, the third attribute of welfare depends on the real types of all agents. In other words, agent i has to wait until all tasks by other agents have been completed to receive the payment.

ICP Mechanism: Motivated by the potential inefficiency due to the payment timing, the ICP mechanism relies on a payment function, piICP that agents can get payments immediately after the individual allocations are processed, i.e.

where

Unlike in Eqn 3, W-i,i in Eqn 5 can be calculated corresponding to the allocation and POS from declarations ˆ θ, and the real type of agent i only. Under ICP mechanism, the payment can be decided immediately after an individual agent completes the allocated tasks and contracting can take place before the entire project completion.

Irrespective of the three payment rules, utility for individual agent can be defined as the payment received minus the cost incurred in executing the allocated tasks. That is,

Utility of the centre is the difference between the center's value and the total payments made to all agents:

where the second term can be defined by Eqn 2 or 4 based on which mechanism is applied.

4.2 VCG and SCP

It is well known that if the utility of a participant is depending other participants' types (because of task duration in the context of strategic RCPSP), such interdependent valuations are not incentive compatible to truthfully reveal the type for VCG mechanism ([Postlewaite and McLean, 2015]). We will use a concrete example to show that VCG is not incentive compatible, while SCP is.

Consider a simple case with only one task and no cost involved 1 . Let ˆ θi denote the reported task duration from agent i. After the centre receives all declarations, an allocation together with a payment are calculated. Let ˆ θ1 and ˆ θ2 represent the lowest and second lowest reported durations, respectively. As in most real world cases, we suppose centre' value, V (·) is a non-increasing function with the task duration and i is the wining agent, i.e., ˆ θi = ˆ θ1 < ˆ θ2.

According to VCG payment, an agent would be paid based on the value increase of other agents due to its presence and the total value with and without i are V (ˆ θ1) and V (ˆ θ2), respectively. Thus, the utility of i can be presented as uiV CG = V (ˆ θ1) - V (ˆ θ2) and utilities of all agents except the winner would be zero. Such a mechanism is not incentive compatible, because it is solely based on declaration of each agent and the agents can report wrongly to derive higher incentive.

We overcome this barrier by designing a payment function which is not only based on the declarations, but also on the actual execution of tasks. Following our SCP mechanism, the utility of the winner i can be instead represented as, uiSCP = V (θ1) - V (ˆ θ2), where θ1 is the actual value of the winner i. There are three possible declarations: truth-telling, overreporting and under-reporting. We show that under SCP,

agents have no incentive to misreport for each scenario.

• ˆ θ1 < ˆ θ2 < θ1. In this case, i wins by over-reporting. Given V (·) is non-increasing, we then have uiSCP < 0 (utility is negative).
• ˆ θ1 < θ1 < ˆ θ2. Since θ1 < ˆ θ2, by reporting the truth, i can secure the task. There is no incentive to report a lower value as no utility gain can be obtained.
• θ1 < ˆ θ1 < ˆ θ2. Similar to the previous case, besides receiving no utility gain, there is also a potential risk to losing the task by reporting a higher value. Thus, i has no incentive to lie.
• θ1 = ˆ θ1 < ˆ θ2. Under this scenario, i secures the task and gets a positive utility given by V (θ1) - V (ˆ θ2).

In other words, truth-telling is dominant in this example under the SCP mechanism. We show properties of SCP and ICP with respect to incentive compatibility in later sections.

4.3 MILP for Strategic RCPSP

Another key feature of our proposed SCP and ICP is the integration of an execution policy (i.e., POS) together with task allocation, so that an online decision is always available to tell at each time, what tasks to be executed on which resources. Note that online execution of the generated POS is beyond the scope of this paper. Overall, the proposed solution framework for solving strategic RCPSP contains three processes: task allocating, task executing and payment making.

1 Note that even if cost is not present, time can always be treated as an opportunity cost. Pro-bono projects are one example of cases where cost is irrelevant.

We build on the idea of generating POSs for RCPSP/max using a flow-based continuous time linear model in [Fu et al., 2016; Varakantham et al., 2016] and provide an MILP formulation in Table 1 to determine the optimal allocation and POS. Given the declarations from agents, temporal and resource constraints among tasks, the objective of the MILP is to generate the best task allocation and execution policy POS, where 'best' here is characterized with respect to maximizing welfare for all agents based on the revealed types.

Eqns 8 - 9 compute the actual cost of agent i by processing τq and if it is allocated to i by allocation f. The duration of τq is represented by Eqn 10. Eqn 11 guarantees that for each τq, only one agent is assigned to it. Eqns 12 - 18 are for POS generation. The resource flow variable xkq,z represents the number of resource k transferred directly from τq to τz. The sequencing variables yq,z are for POS construction. Note that in the MILP, start time variables are only used for policy computing. Eqn 13 links starting times of τq and τz with yqz. It is active when yqz = 1 which enforces the precedence relationship. If τq precedes τz, the maximum resource flow from τq to τz is forced to be min{rqk, rzk}, as in Eqn 14. Eqns 15 - 16 are flow conservation constraints. Eqn 18 covers the three relationships between two tasks, either one task precedes another, or both being executed in parallel. All constraints in the optimization model are linear. If V is linear or quadratic, the model can be solved using solvers like CPLEX. In fact, as indicated in [Fu et al., 2016], problems with up to 30 activities can be executed efficiently when minimizing makespan.

To summarize, the overall flow of the strategic RCPSP works as follows: (i) Agents bid for tasks of interest by reporting certain types. (ii) The central will then compute a task allocation together with a POS for project execution using the MILP model in Table 1. (iii) Agents perform allocated tasks following the POS. (iv) Payments are then made to individual agents (at different timings as in SCP and ICP).

4.4 MechanismProperties

In this section, we outline the key properties of our SCP and ICP mechanisms: First, we show that SCP with payment rule in Eqn 2 is Bayes Nash incentive compatible, i.e., an agent always receives the highest utility by reporting its true type when all other agents are truth reporting. We then show that ICP is more powerful than SCP, as it allows for individual rationality and strategy proofness (or general incentive compatibility). Strategy proofness implies that being truthful is the dominant strategy irrespective of what other agents report. Finally, we show that both SCP and ICP ensure center's rationality and economic efficiency. The key notations in mechanism properties are summarized in Table 2.

Bayes Nash Incentive Compatibility of SCP

Consider an arbitrary agent i. Let the optimal allocation based on the true types θ = (θi , θ-i ) denoted by f∗ (θ), or f∗ . From the design of SCP, f∗ optimizes the total welfare, given θ. Let f∗-i denote the optimal allocation based on θ-i . From Eqns 2, 3, and 6, the utility of agent i by reporting θi is:

where W is the optimal welfare based on θ and W-i is the total welfare of all agents except i when i is not present.

We then consider the case when agent i reports ˆ θi , and other agents declare true types θ-i . Let ˜f∗ denote the optimal allocation based on ˜ θ = (ˆ θi , θ-i ). Similarly in Eqn 19, the utility of agent i under allocation˜f∗ can be represented as:

where ˜f∗ is derived based on declarations ˜ θ, while the welfare calculation involves true types θ. Thus, from Eqns 19 and 20,

Since (f∗ , y∗ ) optimizes the welfare based on θ, we then have ui (θ) ≥ ui (˜ θ). That is, given other agents are truthful, by truthfully declaring its type, agent i can get higher utility.

Individual Rationality of ICP

Individual Rationality requires that no agent would lose by participating with the true value, no matter what other agents declare. Consider agent i with its true type θi , and the reported types of other agents except i denoted by ˆ θ-i . Let ¯ θ = (θi , ˆ θ-i ) and the optimal allocation based on ¯ θ denoted by ¯f∗ ( ¯ θ), or ¯f∗ . From Eqns 4 - 6, the utility of agent i is:

where W-i is the total welfare of all agents except i when i is not present and the optimal allocation ˆf∗-i is derived based on ˆ θ-i . Note that inW-i , since i is not involved, the welfare remains unchanged if we append an empty allocation for i to ˆf∗-i , with ˆf∗i=φ = ˆf∗-i ∪ ( ˆ fi = φ). That is,

where the last term represents the total welfare of all agents (including i with zero contribution) based on allocation ˆf∗i=φ (derived from ˆ θ-i ). Given ˆf∗i=φ , the welfare function remain unchanged irrespective of the type of agent i. Thus, we have,

Since (¯f∗ , ¯y∗ ) optimizes W given ¯ θ, we then have ui (¯ θ) ≥ 0. That is, agent i's utility, no matter what other agents report, if it truthfully declares its type, is always non-negative.

Strategy Proofness of ICP

Consider i reports ˆ θi and other agents declare ˆ θ-i . According to Eqn 4 and similar derivations from Eqns 22 to 24, the utility of i in ICP mechanism based on ˆ θ = (ˆ θi , ˆ θ-i ) is,

And the utility based on ¯ θ = (θi , ˆ θ-i ) can be represented as,

Note that the last items in Eqns 25 and 26 are the same, given agent i has empty allocation. Thus,

Since (¯f∗ , ¯y∗ ) is the optimal allocation based on ¯ θ, we then have ¯ui (¯ θ) ≥ ¯ui (ˆ θ). In other words, no matter what declaration other agents provide, by telling the truth, agent i can get the highest utility.

Center's Rationality and Economic Efficiency

A mechanism is said to satisfy center's rationality and economic efficiency if it guarantees that center has non-negative utility and the welfare is optimal if all participants are truthful, respectively. If all agents are truthfully declaring their types, there would be no difference between SCP and ICP in terms of center's utility and social welfares achieved. Thus, we only prove center's rationality and economic efficiency for the SCP mechanism and omit the proof for ICP.

From Eqn 7, the center's utility is the difference between the total value created by agents from attending the allocated tasks and the total payments made to agents. Consider all agents are truth reporting. From Eqn 2, the center's utility is,

where W-i|i is the welfare of participants except i when i is present, f∗ and f∗-i are optimal allocations based on θ and θ-i , respectively. Since f∗-i optimizes the welfare of all agents but i, we then have u#(θ) ≥ 0. That is, if all agents are truthful, the mechanism guarantees the center a non-negative utility.

Since f∗ optimizes the total welfare W based on θ, economic efficiency can be directly achieved. That is, the welfare of all participants is optimal if all agents are truthfully declaring their types.

5 Conclusion

Existing research in RCPSP assumes that a central authority is equipped with all related data of the problem (e.g., processing times of tasks) and is asked to derive a scheduling solution that optimises a certain criteria (e.g. project makespan) with both temporal and resource constraints satisfied. But in the real world project scheduling, decisions might be taken by several individual economic units or agents, aiming at optimising their own objectives rather than the project performance. As such, agents may lie and declare values other than the truth for self interests. In this work, we first define a strategic RCPSP model and then propose mechanisms for the strategic RCPSP, that ensures agents are incentivised to reveal truth about their types and thereby executing the tasks on time to guarantee a successful project delivery.