1 Introduction and scope of review

There exists a tremendous body of literature that focuses on intersections of (algorithmic aspects of) computer science and game theory (as well as economic theory). The resulting fields of intersecting disciplines are usually referred to as algorithmic game theory (an excellent introduction and overview is given by Nisan et al. 2007). Many research articles in this field focus on auction contexts (see Krishna 2010). Recently, however, there has been a growing interest in taking a game-theoretic perspective on machine scheduling problems, which has resulted in a fairly large amount of research articles that we aim to review and classify in this article.

Broadly speaking, scheduling problems are concerned with allocating scarce resources over time to perform a set of tasks with the objective of optimizing one or more performance measures (Błażewicz et al. 2007; Leung 2004). Resources, tasks and performance measures can be of very different nature. As indicated above, we will focus on resources that (directly) represent some kind of processor or machine, i.e., machine scheduling problems, and set the scope of our literature review, which complements the articles by Heydenreich et al. (2007) and Christodoulou and Koutsoupias (2009), to include research on

  • machine scheduling problems

  • in offline-settings, where all information regarding the problem is known or has been announced (see below) at the unique time of planning,

  • in a noncooperative game-theoretic context, where players cannot form coalitions

  • and have private information on their own characteristics which they directly (but not necessarily truthfully) announce by making a single claim,

  • in the presence of a central authority that is in charge of designing a rewarding scheme and the scheduling algorithm that determines the final schedule based on the information submitted by the players and the publicly known information.

In order to give a systematic record of the academic efforts in the above field of research, we provide a corresponding hierarchical classification scheme. This scheme augments the classification scheme by Graham et al. (1979) for machine scheduling problems, which is widely used and generally accepted in the scheduling community. We are motivated by the fact that adoptions and extensions of Graham et al. (1979) have been successfully implemented in a variety of other problem fields (see, for example, Allahverdi et al. 2008; Boysen and Fliedner 2010; Boysen et al. 2007, 2009; Brucker et al. 1999; Potts and Kovalyov 2000).

1.1 Scope of review

In this section, we present details on the scope of our literature review and additionally introduce the notation used throughout this article. For the sake of brevity, we assume the reader to be familiar with the basic theory of machine scheduling problems and the main concepts of game theory and refer to Błażewicz et al. (2007), Leung (2004), and Fudenberg and Tirole (1991) for comprehensive introductions to these fields of research.

1.1.1 Machine scheduling problems

The notation used in the scheduling and (algorithmic) game theory communities is not always compatible. Therefore, we will sometimes deviate from the standard scheduling notation. Basically, a machine scheduling problem is characterized by a set J of n jobs (tasks) and a set M of m machines. A feasible schedule o assigns machines of the set M to jobs of the set J in order to complete all jobs under a set of imposed constraints. We denote the set of all feasible schedules of a given machine scheduling problem by O. Jobs and machines are characterized by certain parameters, e.g., processing times or speeds. Furthermore, there exist different performance measures. We assume the reader to be aware of the corresponding definitions and restrict ourselves to giving an overview of the notation relevant for this article in Table 1.

Table 1 Notation: machine scheduling problems
Full size table

As mentioned above, Graham et al. (1979) present a widely used and generally accepted classification scheme for machine scheduling problems. It represents a specific problem by a three-field notation, \(\alpha |\beta |\gamma \), where \(\alpha \) describes the machine environment, \(\beta \) refers to job characteristics, and \(\gamma \) relates to the (global) performance measure (optimality criterion). Each field of the triple includes multiple elements, e.g., \(\alpha = \alpha _1, \alpha _2, \ldots \), which represent specific problem properties. The empty symbol, \(\circ \), denotes the default value of an element and is skipped when a triple is actually specified.

1.1.2 Algorithmic game theory

The games considered throughout this paper have three basic elements: players, strategy spaces, and utility functions. Furthermore, we will restrict ourselves to considering noncooperative games. That is, players cannot form coalitions in order to generate group decisions. In the context of machine scheduling problems, players may be machines or jobs. More generally, one may also think of “owners” of multiple machines or jobs that act as single players. Each player has an associated strategy space that represents the options that the player can select from when the game is played. For example, when the players correspond to jobs, each job may be allowed to select a machine to be processed on. A player’s utility function assigns a utility level to every vector of strategies, i.e., each combination of strategies that can potentially be selected by all players. With respect to machine scheduling problems, the utility level could, for instance, correspond to the completion time of a given job.

We will consider fairly specific problem settings in the field of algorithmic game theory for machine scheduling problems. These settings are characterized by the existence of (rational and selfish) players, who are typically referred to as agents and can make a single claim on some pieces of information that may affect the final schedule. Furthermore, there exists a central authority/planner, who is in charge of designing an interaction protocol, a rewarding scheme (e.g., payments among players), and a scheduling algorithm that determines the final schedule. Within this scope, there are two main streams of literature that differ in the type of information that the agents possess and in the way that the information affects an instance of the considered machine scheduling problem (Fig. 1).

Fig. 1
figure 1

Algorithmic mechanism design (in case of direct revelation) and scheduling games

Full size image
  1. 1.

    In this article, we will focus on one of these streams, which presumes that the agents have private information on some of their own characteristics. Jobs, for instance, may privately know their due dates or job weights. The remaining data, e.g., the number of machines and jobs, is usually assumed to be publicly known. The central planner designs some protocol of interaction that the agents have to follow. This protocol may be fairly general. We will, however, restrict ourselves to considering “direct protocols” that allow the agents to solely (but not necessarily truthfully) announce concrete values that represent their private information when the game begins. In terms of optimization problems, these agents therefore fix a subset of parameters. When acting selfishly, they may try to influence the solution determined by the scheduling algorithm by submitting false information if this can increase their utility. However, by designing appropriate algorithms and rewarding schemes that set the right incentives, the central planner can extract the true information of these players, for example, in order to generate fair solutions with respect to some social criterion that considers the interests of all agents.

  2. 2.

    In the second stream, which we exclude from our review for the sake of brevity (the interested reader may refer to Heydenreich et al. 2007), the (usually completely informed) agents, again pursuing selfish goals, commit decisions on machine-job assignments and thus implicitly fix variables of optimization problems. We can, for example, think of jobs whose strategy spaces correspond to the set of machines, i.e., jobs who can choose to be processed on specific machines.

We would like to stress the fact that the aforementioned fields of research are not always clearly separated in the literature. Similarly, the terms used to identify specific problems within these fields may differ among different articles. We will follow Nisan and Ronen (2001), who define (algorithmic) mechanism design to aim at “study[ing] how privately known preferences [...] can be aggregated toward a ‘social choice’ ” (see also Nisan and Ronen 1999), which corresponds to the first stream described above. Our focus on direct protocols is usually termed direct revelation (see, for example, Nisan 2007). Others use the term “algorithmic mechanism design” in a more general context, even when there is no privately owned information (see, for instance, Immorlica et al. 2009). Problems in the second stream are sometimes referred to as (machine) scheduling games (see, for instance, Harks et al. 2011; Roughgarden and Tardos 2007) or load balancing games (Vöcking 2007). These games are closely related to the categories of congestion games (Rosenthal 1973) and coordination mechanisms (Christodoulou et al. 2009a). In all of these areas, one is usually interested in deciding whether (Nash) equilibria exist, how (in-)efficient these equilibria are when compared to socially optimal solutions, and how fast algorithms can compute them (Harks et al. 2011; Roughgarden and Tardos 2007).

1.1.3 Algorithmic mechanism design

Based on the illustration in Fig. 2, we will now describe the (direct revelation) algorithmic mechanism design setting in the context of machine scheduling problems in more detail. The corresponding notation used throughout this article is summarized in Table 2.

Fig. 2
figure 2

(Reproduced with permission from Kress et al. 2017)

(Direct revelation) algorithmic mechanism design.

Full size image
Table 2 Notation: algorithmic mechanism design
Full size table

Let A denote the set of rational and selfish agents. Each agent \(k \in A\) has a (true) valuation function \(v_k^t: O \rightarrow \mathbb {R}\) that maps every feasible schedule of the considered scheduling problem to a real value. \(v_k^t\) is private information of the agent and is thus sometimes referred to as the agent’s type. Negative values can, for example, relate to costs incurred to a (job) agent due to waiting for being completed.

Each agent \(k \in A\) reports a valuation function \(v_k\) that may deviate from the true valuation function \(v_k^t\) to the mechanism. Each valuation function \(v_k\), \(k \in A\), is element of a publicly known set \(V_k\). We define \(V:=V_1 \times \cdots \times V_{|A|}\). Furthermore, we denote the vector of all valuation functions reported to the mechanism by \(v=(v_1,\ldots ,v_{|A|})\) and the vector of all valuation functions reported to the mechanism except of \(v_k\) by \(v_{-k}=(v_1,\ldots ,v_{k-1},v_{k+1},\ldots ,v_{|A|})\). For the sake of notational convenience, we will use v and \((v_k,v_{-k})\) interchangeably.

The mechanism itself is designed and controlled by a central planner. It is a pair (f, p), composed of a social choice function \(f: V \rightarrow O\) and a vector of payment functions \(p:=(p_1,\ldots ,p_{|A|})\), with \(p_k: V \rightarrow \mathbb {R}\) for all \(k \in A\). The mechanism (f, p) is said to implement the social choice function f. It is efficient, if f maximizes social welfare, i.e., the sum of the valuation functions of all agents (see, e.g., Heydenreich et al. 2008; Mitra 2002, 2001). As described in Sect. 1.1.2, in the context of scheduling problems, the social choice function is an algorithm that determines a feasible schedule based on the valuation functions reported to the mechanism. It is also referred to as the scheduling rule, allocation rule, or allocation function. As the global objective function of a scheduling problem may be non-utilitarian, i.e., differ from aiming to maximize the sum of the valuation functions of all agents, we will use the term efficiency in a broader sense by referring to a mechanism as efficient whenever it optimizes the global optimality criterion of the scheduling problem. By controlling the allocation rule and the payment functions, the central planner can design mechanisms with different features.

Each agent \(k \in A\) selfishly aims to maximize the utility function \(u_k:V \rightarrow \mathbb {R}\), which is assumed to be quasi-linear, i.e., corresponds to the sum of the agent’s valuation of the schedule (determined by the allocation rule) and the (potentially negative) corresponding payment from the mechanism, \(u_k(v_k,v_{-k}) := v_k^t(f(v_k,v_{-k})) + p_k(v_k,v_{-k})\). Sometimes, it is reasonable to focus on individually rational mechanisms (also referred to as voluntary participation mechanisms, see Auletta et al. 2004), that assume (or feature) the utilities of each agent to always be nonnegative (see, for instance, Nisan 2007; Hoeksma and Uetz 2013).

1.1.4 Randomized mechanisms and publicly known distributions

All of the above definitions consider a deterministic problem setting and assume that the agents have no information at all about the private information of the other agents. Unless stated otherwise, these will also be our standard assumptions throughout the remainder of this paper. The literature, however, also considers modified settings. Most important, one can assume the allocation rule to be non-deterministic, i.e., let the scheduling algorithm’s logic employ some degree of randomness, or consider randomized payments. A resulting mechanism is then referred to as a randomized mechanism (Nisan and Ronen 1999, 2001). Moreover, it may sometimes be appropriate to assume that there exists some commonly known probability distribution over the private information of each player (Nisan 2007). In both modified settings, agents are usually assumed to maximize expected utilities. The definitions of the standard setting carry over in a straightforward manner.

1.2 Article overview

The remainder of this article is structured as follows. In Sect. 2, we present an overview of problem categories and problem features that characterize machine scheduling settings in the algorithmic mechanism design literature. This will lay the foundation for our extension of the classification scheme of Graham et al. (1979) in Sect. 3 and allow a structured overview of the literature in Sect. 4. The article closes with a conclusion and an illustration of research challenges that can be identified based on the prior classification of the literature in Sect. 5.

2 Review of problem categories and features

In addition to the classical problem categories of the classification scheme of Graham et al. (1979) and its extensions, the algorithmic mechanism design literature for machine scheduling problems (as restricted in Sect. 1) can be structured based on multiple categories, which we will present in the following sections, where we will also discuss additional problem features that we have not yet introduced.

2.1 Categories, risk attitude, and private information of agents

With respect to categories of agents, there exist two streams of publications. The first group of articles, which follows the seminal work of Nisan and Ronen (1999, 2001), presumes that solely the machines are selfish agents (typically referred to as machine agents), i.e., \(A=M\). Machine agents usually aim for small loads. Similarly, the second stream of publications assumes that only the jobs are selfish agents (job agents), i.e., \(A=J\), mostly aiming at small completion times. Prominent examples of the latter stream are Suijs (1996) or Angel et al. (2006). The literature on job agents that are to be scheduled on a single machine sometimes analyzes the independence of irrelevant alternatives (IIA) property of allocation rules (see, e.g., Heydenreich et al. 2008). It is satisfied if the relative order of any two jobs on the machine is independent of the committed types of all other jobs.

Of course, one may also think of more general settings, where both (a subset of) jobs and (a subset of) machines represent selfish players of the considered game. Even more general, there might be “owners” of multiple jobs or machines that act as single agents. However, to the best of the authors’ knowledge, this setting has not yet been considered in the noncooperative literature.

Concerning the risk attitude, the vast majority of research articles assumes the agents to be risk neutral. Exceptions are Kovalyov and Pesch (2014) and Kovalyov et al. (2016), where job agents are assumed to be “fully” risk averse.

Mechanism design settings can also be classified with respect to the knowledge of agents about the private information of the other agents. The standard case is to assume that agents have no information at all about the other’s private information. Sometimes, however, one assumes that there exists some commonly known distribution over the private information of each agent (see Sect. 1.1.4) or that there are other publicly known restrictions on the private information of each agent. An example for the latter case is to restrict privately known speed factors of machine agents to be natural numbers that are bounded from above by a publicly known constant (Auletta et al. 2004).

2.2 Truthfulness, VCG mechanisms, and approximability

As indicated in Sects. 1.1.2 and 1.1.3, agents selfishly aim to maximize their (expected) utilities and may therefore lie about their true valuation functions. To overcome this problem, the central planner may want to design the mechanism such that agents behave truthfully. The literature considers different concepts of truthfulness. We will briefly outline the concepts that are relevant for this article in this section.

A mechanism is (dominant strategy) incentive compatible or truthful (Nisan 2007) if it guarantees that reporting the true valuation function maximizes the utility function of a rationally acting agent for all possible vectors of claimed valuation functions of the other agents, i.e., if \(u_k(v_k^t,v_{-k}) \ge u_k(v_k,v_{-k})\) for all \(k \in A\), all \(v_k \in V_k\), and all \(v_{-k} \in V_{-k}\).

In case of randomized mechanisms, articles usually apply an adapted notion of truthfulness, referred to as truthfulness in expectation. Formally, let \(E(u_k(v))\) denote the expected value of the utility function of agent \(k \in A\) over the randomization of the mechanism. A mechanism is truthful in expectation if \(E(u_k(v_k^t,v_{-k})) \ge E(u_k(v_k,v_{-k}))\), for all \( k\in A\), \(v_k\in V_k\), and \(v_{-k}\in V_{-k}\). Alternatively, one may slightly deviate from our definition in Sect. 1.1.4 and define a randomized mechanism to allow distributions over deterministic mechanisms. Then, a randomized mechanism is defined to be universally truthful if every deterministic mechanism in the support is dominant strategy incentive compatible (Nisan 2007).

Similarly, when considering the case of publicly known probability distributions over the type spaces of agents (that we will denote by \(\varPhi _{k}\) for agent \(k \in A\)) as described in Sect. 1.1.4, one can apply a weaker notion of truthfulness, referred to as Bayes–Nash incentive compatibility (see, for example, Duives et al. 2015; Heydenreich et al. 2008; Hoeksma and Uetz 2013). Here, for each agent, telling the truth must be (weakly) dominant in expectation over the publicly known distributions over the type spaces of the other agents.

One of the most important general results in the field of mechanism design is the Vickrey–Clarke–Groves mechanism (VCG mechanism), which was suggested by Vickrey (1961) and generalized by Clarke (1971) and Groves (1973). A mechanism is called a VCG mechanism, if the social choice function maximizes social welfare and if the payment functions \(p_k(v)\), \(k\in A\), are given by

$$\begin{aligned} p_k(v) = h_k(v_{-k}) + \sum ^n_{l=1, l\ne k} v_l(f(v)), \end{aligned}$$

where \(h_k(v_{-k}): V_{-k} \rightarrow \mathbb {R}\). Note that \(h_k\), \(k \in A\), is independent of the valuation function \(v_k \in V_k\) reported by agent k. This general definition of the payment functions is referred to as the Groves payments. The Clarke pivot rule specifies \(h_k(v_{-k})=- \max _{o\in \hat{O}} \sum _{l=1,l\ne k}^n v_l(o)\), \(k \in A\), where \(\hat{O} \subseteq O\) is the set of all feasible schedules that the considered scheduling algorithm may compute. The resulting payment functions have specific desirable properties. They are, for example, non-positive, so that the agents never receive payments from the mechanism. Furthermore, a corresponding mechanism is individually rational if \(v_k(o)\ge 0\) for all \(k\in A\) and all \(o\in \hat{O}\). The concept of VCG mechanisms was further generalized by Roberts (1979) to social choice functions that belong to the set of so-called affine maximizers.

A VCG mechanism is (dominant strategy) incentive compatible, but a major drawback is the need to find optimal solutions to the underlying problem of maximizing social welfare, which may be NP-hard (see, for instance, Nisan 2007). Hence, in the context of scheduling problems, VCG mechanisms are oftentimes not appropriate even if the objective function of the specific scheduling problem corresponds to maximizing social welfare. Many researchers are therefore actively trying to explore the boundary between truthfulness (in its most general sense) and computational complexity for specific scheduling problems (see also Sect. 5). It is especially desirable to derive truthful mechanisms with polynomial time computable allocation and payment functions that feature good approximation factors for specific settings, and to determine strong dual bounds on approximation factors for truthful scheduling under non-utilitarian objectives without restricting the analysis to polynomial time allocation functions. If one aims to design a concrete polynomial time truthful mechanism for some NP-hard scheduling domain, one must make use of theoretical results that are related to incentive compatibility and that are suitable for heuristic algorithms. For example, one may have to assure that certain monotonicity conditions are fulfilled by the allocation rule in order to guarantee incentive compatibility (see, e.g., Heydenreich et al. 2007; Lavi and Swamy 2009, for more details).

2.3 Models of execution and constraints on committed data

When agents possess private information on the processing times of jobs, the literature distinguishes between different models of execution. These models differ in the length of the actual time slots that are reserved on the machines once the schedule that has been determined by the scheduling algorithm is implemented. There are two widely used models of execution (see, e.g., Christodoulou et al. 2007a). The strong model of execution assumes that the schedules which are implemented based on the computations of the scheduling algorithms always apply the true processing times of the jobs, no matter which value has been committed by the agents. In contrast, in the weak model of execution, the implemented schedules use the reported processing times. A third model of execution is used by Koutsoupias (2014). Here, the implemented processing times are defined by the maximum of the reported and the true processing times. We refer to this model of execution as the maximum model of execution. The weak and maximum models of execution are especially relevant in applications where the processing of all jobs can actually be observed by the agents. If the true processing times were applied in this case, a lie of an agent who commits a processing time that is larger than its true value would be observable by the other agents, which might not be desirable in the considered application (Koutsoupias 2014). Similarly, there may be applications where the strong model of execution is most suitable, for example, when machine idle times are very costly for their owner or not allowed at all.

Additionally, one may want to constrain the data that the agents are allowed to report to the mechanism without publicly revealing explicit data of their private information. For example, in case of private processing times (release dates), it may be reasonable to restrict the agents to commit processing times (release dates) that are bounded from below by their true values (see, e.g., Angel et al. 2012; Christodoulou et al. 2007a).

2.4 Characteristics of payment schemes

There exist many applications, where mechanisms may be restricted to not include payments for compensation purposes, i.e., where \(p_k(v)=0\) must hold for all \(k \in A\) and \(v \in V\) (see, for example, Koutsoupias 2014). Very broadly speaking, this “constraint can arise from ethical and/or institutional considerations: Many political decisions must be made without monetary transfers; organ donations can be arranged by ‘trade’ involving multiple needy patients and their relatives, yet monetary compensation is illegal” (Schummer and Vohra 2007). In a scheduling context, a setting with payments “is easily challenged when it comes to computational settings. In particular in internet domains payments are notoriously difficult to implement, mainly due to security and banking issues” (Procaccia and Tennenholtz 2009).

Other applications strive for mechanisms that have no surplus or deficit of monetary payments that cannot be redistributed among the agents (Suijs 1996), i.e., where \(\sum _{k\in A} p_k(v) =0\) for all \(v \in V\). These payment schemes are usually referred to as budget-balanced.

Some articles aim to design Bayes–Nash or dominant strategy incentive compatible mechanisms for scheduling problems that minimize the sum of the (expected) payments (see, for instance, Duives et al. 2015; Heydenreich et al. 2008; Hoeksma and Uetz 2013). Mechanisms of this type are usually referred to as optimal mechanisms (see also Hartline and Karlin 2007). Usually, these articles focus on individually rational mechanisms or some approximation guarantee of the scheduling algorithms (given truthful commitments of the agents).

2.5 Other problem categories and features

There exist some mechanism design-related problem features that do not fall into the categories of the above sections. In the following, we list the features that are relevant for this article.

A mechanism is called anonymous if, whenever two agents switch all of their properties, these two agents also switch positions in the resulting schedule (see, for example, Ashlagi et al. 2012).

In a mechanism with verification, the calculation of the payments depends on the results of the execution of the schedule (see, e.g., Nisan and Ronen 1999, 2001). If, for example, the processing time of a job is part of the private information of an agent, additional information on the true processing time becomes available after the execution of the schedule, which depends on the model of execution.

Next, a mechanism is called envy-free, if no agent is able to improve her utility function value by switching both, the position in the schedule and the realized payments, with another agent (see, for instance, Kayı and Ramaekers 2010, 2015).

A mechanism is task-independent if its allocation function decides on the allocation of each job separately, i.e., without considering the characterizing parameters of the other jobs (see, for instance, Christodoulou et al. 2010; Dobzinski and Sundararajan 2008).

When considering a mechanism design setting with machine agents, a mechanism is called locally decisive, if each agent can enforce her allocation by reporting very low or high values but cannot determine how the remaining jobs are allocated among the other agents (see, e.g., Christodoulou et al. 2008).

3 Classification scheme

We are now ready to present our extension of the classification scheme of Graham et al. (1979). The resulting scheme is extensible, i.e., it allows for including more features when needed.

3.1 Review of selected elements of Graham et al. (1979)

We will first review parts of the notation introduced by Graham et al. (1979). With respect to the machine environment \(\alpha \), they define:

\(\bullet \) Machine environment, \(\alpha _{1} \in \{\circ , P, Q, R, \ldots \}\)

\(\qquad \circ \)

Single machine, i.e., \(m=1\).

\(\qquad P\)

Identical (parallel) machines.

\(\qquad Q\)

Uniform (parallel) machines.

\(\qquad R\)

Unrelated (parallel) machines.

\(\bullet \) Number of machines, \(\alpha _{2} \in \{\circ , \mathbb {N} \}\)

\(\qquad \circ \)

m is variable.

      positive integer m

There exists a constant number m of machines.

Regarding the job characteristics \(\beta \), we will only make use of a few elements introduced by Graham et al. (1979):

\(\bullet \) Release dates, \(\beta _{4} \in \{\circ , r_j\}\)

\(\qquad \circ \)

No release dates are specified.

\(\qquad r_j\)

Release dates per job are specified.

\(\bullet \) Processing times, \(\beta _{6} \in \{\circ , t_j=1, \ldots \}\)

\(\qquad \circ \)

Processing times are arbitrary.

\(\qquad t_j=1\)

Each job has unit processing time.

Furthermore, we will make use of the following element (see, for example, Leung and Li 2008):

\(\bullet \) Eligibility constraints, \(\beta _{7} \in \{\circ , M_j\}\)

\(\qquad \circ \)

No eligibility constraints are specified.

\(\qquad M_j\)

Each job \(j \in J\) is associated with a set of eligible machines \(M_j \subseteq M\) on which it can be processed.

Finally, based on Graham et al. (1979) and with respect to the (global) optimality criterion \(\gamma \), i.e., the objective function that the scheduling algorithm aims to optimize based on the publicly known parameters and the values committed by the agents, we define:

\(\bullet \) Global optimality criterion, \(\gamma \in \{C_{max}, \sum C_j, \sum w_jC_j, \max w_jC_j, \sum f_j(C_j), \sum f(C_j), \sum w_jf(C_j), \sum w_jU_j, \sum f(L_i), \sum L_i, \Vert L \Vert _p, \max \min L_i, \ldots \}\):

\(\qquad C_{max}\)

Minimize the makespan, i.e., the maximum of the completion times.

\(\qquad \sum C_j\)

Minimize the sum of completion times.

\(\qquad \sum w_jC_j\)

Minimize the weighted sum of completion times.

\(\qquad \max w_jC_j\)

Minimize the maximum weighted completion time.

\(\qquad \sum f_j(C_j)\)

Minimize the sum of functions \(f_j\) of the completion times of jobs \(j \in J\).

\(\qquad \sum f(C_j)\)

Minimize the sum of a function f of the completion times.

\(\qquad \sum w_jf(C_j)\)

Minimize the weighted sum of a function f of the completion times.

\(\qquad \sum w_jU_j\)

Minimize the total weight of late jobs.

\(\qquad \sum f(L_i)\)

Minimize the sum of a function f of the load of the machines.

\(\qquad \sum L_i\)

Minimize the sum of the loads of the machines.

\(\qquad \Vert L\Vert _p\)

Minimize the \(l_p\) norm of the vector of machine loads L.

\(\qquad \max \min L_i\)

Maximize the minimum load over all machines.

3.2 Including mechanism design settings for machine scheduling problems

We can now propose additional notation that allows to include mechanism design settings. As described in Sect. 2.1, the existing literature can be divided into two groups of articles that either presume the existence of machine agents or job agents. We therefore augment the first two fields of the classification scheme of Graham et al. (1979), that represent the machine environment \(\alpha \) and the job characteristics \(\beta \), with additional elements \(\hat{\alpha }_{l}\) and \(\hat{\beta }_{l}\), \(l=1,2,\ldots \), respectively. Here, the index l refers to the l-th element that refers to mechanism design (indicated by the hat operator) characteristics in the specific field.

First, in order to be able to indicate the risk attitude of the agents, we define the elements \(\hat{\alpha }_{1}\) for machine agents and \(\hat{\beta }_{1}\) for job agents:

\(\bullet \) Risk attitude of agents, \(\hat{\alpha }_{1}, \hat{\beta }_{1} \in \{ \circ , averse, seeking, \ldots \}\)

      \(\circ \)

No agents at all (no mechanism design setting) or all agents are risk neutral.

      averse

All agents are risk averse.

      seeking

All agents are risk seeking.

The elements \(\hat{\alpha }_{2}\) and \(\hat{\beta }_{2}\) specify the set of parameters that are private information of the agents and indicate whether the other agents have some common knowledge about this private information.

\(\bullet \) Private information of machine agents, \(\hat{\alpha }_{2} \in \{\circ , priv_{\rho }\{ \ldots \},\ldots \}\)

      \(\circ \)

No machine agents.

      \(priv_{\rho } \{\ldots \}\)

Each element of the set \(\{\ldots \}\) refers to an entity of private information of the machine agents. A superscript \(\tau \) for some element indicates additional restrictions or assumptions on the agents’ commitments or their implementation that do not publicly reveal explicit data of the private information. Multiple entries in the superscript are separated by commas.

 

   – \(s_i^{\tau }\): Machine agent \(i \in M\) has private information on the speed factor \(s_i\). Potentialentries in superscript \(\tau \):

 

      – ...

 

   – \(t_{ij}^{\tau }\): Machine agent \(i \in M\) has private information on the processing times \(t_{ij}\)for all jobs \(j \in J\). Potential entries in superscript \(\tau \):

 

      – max: The maximum model of execution is applied.

 

      – ...

 

   – ...

 

The subscript \(\rho \) indicates additional restrictions or assumptions (on each piece of private information that can be committed by the machine agents) that are based on publicly known parameters. Multiple entries in the subscript are separated by commas. Potential entries in subscript \(\rho \):

 

   – \(\varPhi \): A distribution of each machine agent’s private information is publicly known.

 

   – \(d_\omega \): The values that can be reported by the machine agents are restricted to beelements of publicly known discrete sets. Each element of the subscript \(\omega \)indicates additional restrictions on these sets:

 

      – f: The sets are finite for all machine agents.

 

      – \(=_i\): The sets are identical for all machine agents.

 

      – \(=_j\): The sets are identical for all jobs (if relevant).

 

      – div: The private information is divisible, i.e., it belongs to a set \(C=\{c_1,c_2,\ldots \}\), where \(c_{i+1}\) is a multiple of \(c_i\) \(\forall \, i\).

 

      – c-div: The private information is c-divisible, i.e., it is a power of a given positive constant c.

 

      – ...

 

   – \(c_\omega \): The values that can be reported by the machine agents are restricted to be elements of publicly known bounded and continuous sets. Each element of the subscript \(\omega \) indicates additional restrictions on these sets:

 

      – \(=_i\): The sets are identical for all machine agents.

 

      – ...

 

   – ...

\(\bullet \) Private information of job agents, \(\hat{\beta }_{2} \in \{\circ , priv_{\rho }\{ \ldots \}, \ldots \}\)

      \(\circ \)

No job agents.

      \(priv_{\rho } \{\ldots \}\)

Each element of the set \(\{\ldots \}\) refers to an entity of private information of the job agents. A superscript \(\tau \) for some element indicates additional restrictions or assumptions on the agents’ commitments or their implementation that do not publicly reveal explicit data of the private information. Multiple entries in the superscript are separated by commas.

 

   – \(r_j^{\tau }\): Job agent \(j \in J\) has private information on its release date \(r_j\). Potential entries in superscript \(\tau \):

 

      – \(\ge \): The release date committed by job agent \(j \in J\) is bounded from below by the true release date.

 

      – ...

 

   – \(d_j^\tau \): Job agent \(j \in J\) has private information on its due date or deadline \(d_j\). Potential entries in superscript \(\tau \):

 

      – ...

 

   – \(w_j^\tau \): Job agent \(j \in J\) has private information on its weight \(w_j\). Potential entries in superscript \(\tau \):

 

      – ...

 

   – \(f_j^\tau \): Job agent \(j \in J\) has private information on the function \(f_j\) that maps every possible completion time of its job to a real value. Potential entries in superscript \(\tau \):

 

      – ...

 

– \(t_{j}^{\tau }\): Job agent \(j \in J\) has private information on its processing time \(t_{j}\). Potential entries in superscript \(\tau \):

 

      – strong: The strong model of execution is applied.

 

      – weak: The weak model of execution is applied.

 

      – \(\ge \): The processing times committed by job agent \(j \in J\) are bounded from below by the true processing times.

 

      – ...

 

   – \(t_{ij}^{\tau }\): Job agent \(j \in J\) has private information on its processing times \(t_{ij}\) that may differ among machines \(i \in M\). The potential entries of the superscript \(\tau \) are defined as above.

 

   – ...

 

The subscript \(\rho \) indicates additional restrictions or assumptions (on each piece of private information that can be committed by the job agents) that are based on publicly known parameters. Multiple entries in the subscript are separated by commas. Potential entries in subscript \(\rho \):

 

   – \(\varPhi \): A distribution of each job agent’s private information is publicly known.

 

   – \(d_\omega \): The values that can be reported by the job agents are restricted to be elements of publicly known discrete sets. Each element of the subscript \(\omega \) indicates additional restrictions on these sets:

 

      – f: The sets are finite for all job agents.

 

      – ...

 

   – ...

Finally, we define elements \(\hat{\alpha }_{3}\) and \(\hat{\beta }_{3}\) that represent the (true) valuation functions of the agents, i.e., their “local” objective functions related to the scheduling problem.

\(\bullet \) Objective of agents, \(\hat{\alpha }_{3}\in \{ L_i, \ldots \}, \hat{\beta }_{3} \in \{ C_j, U_j \ldots \}\)

      \(\hat{\alpha }_{3}=L_i\)

Each machine agent \(i \in M\) aims to minimize its load \(L_i\).

      \(\hat{\beta }_{3}=C_j\)

Each job agent \(j \in J\) aims to minimize its completion time \(C_j\).

      \(\hat{\beta }_{3}=U_j\)

Each job agent \(j \in J\) aims to complete before or at \(d_j\), i.e., to minimize the unit penalty function \(U_j\).

As mentioned above, our classification scheme is extensible. This is indicated by dots in the above notation, which allow for including new problem settings for existing categories, for example, when considering new entities of private information of agents. Furthermore, when considering more general categories of agents or similar problem generalizations or extensions, one can include new symbols to represent those settings.

3.3 Examples

We will now illustrate the above classification scheme by presenting two examples.

\(P||C_{\max }\): We are given an arbitrary number of m parallel identical machines and a set J of n jobs. The processing time \(t_j\) of any job \(j \in J\) is independent of the machines. Each job can be processed by at most one machine at a time, and each machine is capable of processing at most one job at a time. The objective is to assign each job to exactly one machine and find non-preemptive sequences of the resulting subsets of jobs of each machine, so that the makespan is minimized. There is no private information; a mechanism design setting is not considered.

\(P|priv\{t_j^{\mathrm{strong}, \ge }\},C_j|C_{\max }\): The setting is in analogy to \(P||C_{\max }\), but we now consider a mechanism design setting with job agents who aim to minimize their completion times. The processing time of each job agent is private information. The processing times committed to the mechanism are bounded from below by their true values. The strong model of execution is applied.

4 Literature overview

Based on the classification scheme of Sect. 3, we can now present a structured overview of the relevant literature. We will do so by presenting three tables that refer to articles that consider problem settings with job agents (Table 3), machine agents and unrelated machines (Table 4), and machine agents and uniform machines (Table 5).

We will make use of some additional definitions regarding approximability results that we briefly introduce before describing the tables in detail. For a given constant \(c\in \mathbb {R}\), a polynomial algorithm is called a c-approximation algorithm if (in case of a minimization problem) the objective function value determined by the algorithm is bounded from above by c times the optimal objective function value. A polynomial algorithm with an additional arbitrary positive input parameter \(\varepsilon \) that guarantees an objective function value which is bounded from above by \(1+\varepsilon \) times the optimal objective function value is called a polynomial-time approximation scheme (PTAS). If the runtime of the algorithm is polynomial in the size of the problem, denoted by q, and in \(1/\varepsilon \), the algorithm is called fully polynomial-time approximation scheme (FPTAS). Another variant of a PTAS is a quasi-polynomial-time approximation scheme (QPTAS). A QPTAS has time complexity \(q^{polylog(q)}\).

Table 3 Overview—Job agents
Full size table
Table 4 Overview—unrelated machine agents
Full size table
Table 5 Overview—uniform machine agents
Full size table

Within the tables, each article, identified by its authors and publishing year, is classified according to the extended classification scheme presented in Sect. 3. Furthermore, the tables highlight the main contributions of each article (as explicitly stated by the authors) by specifying whether it focuses on selected properties or restricts the analysis to specific settings. These selected properties and restrictions slightly differ among the tables because the literature related to each table usually takes a fairly specific perspective on mechanism design settings for machine scheduling problems.

With respect to the characteristics of the payment scheme (Paym.), we indicate whether an article considers nonzero payments at all (\(\exists \)) and whether the presented payment scheme is budget-balanced (BB). Furthermore, we present information on the question of whether or not the mechanisms presented in an article are individually rational (IR). With regard to the considered mechanisms (Mech.), we indicate if they are randomized (rand.) or deterministic (det.). The column “Opt. Me.” indicates if the authors consider the design of optimal mechanisms. Similarly, the focus on different concepts of truthfulness is illustrated in the column “Truthfuln.”, where we specify whether the authors present results on or restrict their analysis to dominant strategy truthfulness (DS), focus on universally truthful mechanisms (U), consider truthfulness in expectation (IE), or examine Bayes–Nash incentive compatibility (BN).

Furthermore, the tables contain information on the approximability of the considered settings. Most important, we indicate results concerning dual and primal bounds (DB/PB) on approximation factors in the “Approx. Quality” column. Note that, with respect to the dual bounds, the studies under consideration do not restrict to what polynomial time mechanisms can achieve, i.e., the dual bounds even hold for exponential time allocation (and payment) functions (see Sect. 2.2). We additionally indicate whether a primal bound presented in some article is based on a polynomial time allocation function and whether a PTAS, FPTAS, or QPTAS is considered (column “poly.”). If, in this context, the allocation function is a polynomial time algorithm, but the payments are not necessarily computable in polynomial time (and this is also highlighted by the respective authors), this is specified in the last column of a table.

In the last column of the table, we present highlights of the articles as well as additional properties (Table 3) or additional restrictions and assumptions on the considered setting (Tables 4 and 5) that are not covered by the preceding columns. In this context, note that some articles consider relaxations of the original scheduling problems, i.e., by allowing a job to be split into arbitrary fractions among the machines. This is usually referred to as fractional scheduling.

In order to precisely present the information in the tables, we use different symbols to indicate if and how a property or restriction is handled or considered in a given article. First, we use circles to indicate whether a given property is fulfilled or a restriction is considered (\(\bullet \)) or not (\(\circ \)). If the authors of an article have proven a given property to be fulfilled or restrict their analysis to a specific setting, we use a “+”, if they have proven that a given property is not fulfilled, we use a “-”. A blank space indicates that a property or restriction is not explicitly addressed in the corresponding article. If a property is only fulfilled under additional constraints that are not stated elsewhere in the table, we mark these results with a “*”.

5 Research challenges and conclusion

In this article, we have provided a classification scheme and a literature overview on direct revelation mechanism design settings in the context of machine scheduling problems. Based on our classification of the literature, we can identify multiple potential directions and challenges for future research that we briefly outline in this section.

First and foremost, as described in Sect. 2.2, it is challenging to better understand the boundary between truthfulness on the one side and computational complexity and approximation on the other side. For example, in case of \(R,priv\{t_{ij}\}, L_i||C_{max}\), i.e., a multi-parameter setting where machine agents possess more than one piece of private information, Nisan and Ronen (1999, 2001) show that truthfulness excludes optimal solutions to the underlying scheduling problem (even when allowing exponential time allocation and payment functions) by providing a dual bound of 2 on the corresponding approximation factor. This bound can, however, be beaten when allowing randomization (see also Chen et al. 2015; Lu and Yu 2008a, b; Mu’alem and Schapira 2017), which provides evidence for the “power of randomization in algorithmic mechanism design” (Dobzinski and Dughmi 2013). Nisan and Ronen (1999, 2001) furthermore conjecture that no truthful deterministic mechanism can achieve an approximation factor better than m (see Table 4). This so-called Nisan–Ronen conjecture has been settled by Ashlagi et al. (2009, 2012) when restricting the analysis to anonymous mechanisms, but it is still open for the general case. A related predominant question, which has especially been studied a single-parameter setting (see Table 5), is whether or not truthful “efficient computation [is] fundamentally less powerful than ‘classical’ efficient computation” (Dhangwatnotai et al. 2008). Recently, for example, Christodoulou and Kovács (2010, 2013) and Epstein et al. (2013, 2015) have provided the first truthful PTAS for \(Q,priv\{s_i\},L_i||C_{max}\), the existence of which had been a major open question ever since the work of Archer and Tardos (2001), who provided a truthful exponential time deterministic mechanism for minimizing the makespan in this setting.

There also remain plenty of open research questions with respect to classical machine scheduling settings. The existing research presented in Tables 3, 4 and 5, for example, solely focuses on parallel machine settings, while it may also be interesting to analyze dedicated machine environments (flow shop, open shop, or job shop problems) in a game-theoretic context. Furthermore, the literature rarely considers varying job characteristics, as, for example, release dates in offline-settings or precedence relations.

Another interesting avenue for future research is to shift the research focus toward new applications. Most existing research is motivated by the emergence of the internet as a platform for computations (e.g., Nisan and Ronen 2001), for example, when considering the problem of determining an execution sequence for (selfish) computer tasks that have been accepted by a computing service provider. Another application can be found in the literature on job agents that focuses on sequencing problems. Mitra (2002), for instance, describes the following setting: There “is a large multi-unit firm with each unit in need of the facility provided by a particular repair and maintenance unit. The repair and maintenance unit can service only one unit at any given time. Therefore, units which remain unattended, incur a cost for the time they are down. In this framework, the firm’s role is that of a planner wanting to service the units by forming a queue that minimises the total cost of waiting. Each unit’s cost parameter is private information. The objective of the firm is to determine the order in which the units are to be serviced.” Other applications, for example, arising in logistics or production processes like considered by Kovalyov and Pesch (2014) can rarely be found and might thus be an interesting field of study.

Finally, there are many additional potential research directions related to game theory and mechanism design aspects. There are, for example, only very few articles that consider risk averse agents. Moreover, as indicated in Sect. 2.1, it might be interesting to consider more general settings with regard to the categories of agents. For instance, one may let agents control multiple machines or jobs. Furthermore, the literature on job agents and uniform machine agents rarely considers multi-parameter settings. Finally, Tables 3, 4 and 5 reveal diverse literature gaps. One may, for example, analyze budget-balanced payments or the design of optimal mechanisms in case of machine agents. For specific problem settings, it is possible to consider different models of execution, constraints on the committed data, local objective functions, etc.