Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

35.1 Introduction

Cost sharing among agents in a queue is a fundamental problem in many practical applications. For example, computer programs are regularly scheduled on servers, data are scheduled to be transmitted over networks, jobs are scheduled in shop-floor on machines, and queues appear in many public services (post offices, banks, etc…). Study of queueing problems has attracted economists for a long time.

In this chapter we study job scheduling situations, where agents have to process jobs. In particular, we consider the problem of a planner who has to provide a facility to a finite group of agents. Each agent has one job to process using this facility. The facility can be used by only one agent at a time; therefore, the planner will have to order the agents in a queue.

An stream of literature related to job scheduling problems is on sequencing games, first introduced by Curiel et al. [1], where they assume the presence of an initial ordering of jobs. In summary, the focus of this stream of research is how to share the savings in costs form the initial ordering to the optimal ordering amongst jobs (also see Hamers et al. [4] and Curiel et al. [2]).

In this work, we propose a cost sharing mechanism for the previous problem. We have two main assumptions: First, we suppose we know the costs for processing any set of jobs in any order. Second, we suppose that agents will process their jobs according to the order that generates the minimum cost to them, therefore they have no preferences in the order their jobs are processed.

We use the concept of potential of a cooperative game to establish this cost sharing mechanism. Hart and Mas-Colell [5] established a new form to generate the value of a game. They start with the definition of a set of games in which a real function is defined, called the potential of the game. This function must be defined in such a way that the following two conditions are satisfied: (1) the gain or participation of each player is equal to the difference in potential between the game that is considered and the one that results when he abandons the game, and, (2) the sum of gains or participations add to what all the players get in that game. Surprisingly, these participations coincide with its corresponding Shapley value.

The chapter is organized as follows. We first recall the main basic features of job scheduling problems and the potential of a cooperative game. In Sect. 35.3 we show that the previous ideas could be applied, with appropriate modification, to determine a cost sharing mechanism for job scheduling problems. Finally, in Sect. 35.4, we present some properties of the mechanism proposed in this work.

35.2 The Model

Let us consider a finite set of participating agents, denoted by N = { 1, 2, …, n}. The group of permutations of a set of agents S ⊆ N, will be denoted by \(\theta _{S} =\{\theta: S \rightarrow S\mid \theta\) is bijective}. For each subset \(S \subseteq N\), let us denote by S π a list of jobs ordered according to permutation π ∈ θ S . Thus, the list \(S_{\pi } = \left [2,1,4\right ]\) represents the situation where agent 2 processes his job in first place, then agent 1 processes his job in second place and finally, agent 4 processes his job, for S = { 1, 2, 4}. A list with no jobs is denoted by \(\left [\varnothing \right ]\).

On the other hand, Π(S) will denote the set of lists of S with all possible orders for its process, i.e., \(\varPi (S) = \left \{S_{\pi }\mid \pi \in \theta _{S}\right \}\). For example, if N = { 1, 2, 3, 4} and S = { 1, 3, 4}, then \(\varPi (S) = \left \{\left [1,3,4\right ],\left [1,4,3\right ],\left [3,1,4\right ],\left [3,4,1\right ],\left [4,1,3\right ],\left [4,3,1\right ]\right \}\). Additionally, we will denote the cardinality of a set by its corresponding lower-case letter, for instance \(n = \left \vert N\right \vert\), \(s = \left \vert S\right \vert\), \(t = \left \vert T\right \vert\), and so on.

Also, let \(E_{N} = \cup _{S\subseteq N}\varPi (S)\) be the set of all lists of jobs in any order.

Definition 35.1.

A mapping

$$\displaystyle{ c: E_{N} \rightarrow \mathbb{R} }$$
(35.1)

that assigns a real value, c(S π ), to each list of jobs S π is called a job scheduling problem. The set of job scheduling problems with agent set N is denoted by P N, i.e.,

$$\displaystyle{ P^{N} =\{ c: E_{ N} \rightarrow \mathbb{R}\mid c\left [\varnothing \right ] = 0\} }$$

If c ∈ P N and S π  ∈ E N , then the value c(S π ) represents the cost for processing the jobs of the list S π .

Given c 1, c 2 ∈ P N and λ ∈ ℝ, we define the sum c 1 + c 2 and the product λ c 1, in P N, in the usual form, i.e.,

$$\displaystyle{ (c_{1} + c_{2})(S_{\pi }) = c_{1}(S_{\pi }) + c_{2}(S_{\pi })\ \ \ \text{ and }\ \ \ (\lambda c_{1})(S_{\pi }) =\lambda c(S_{\pi }) }$$

respectively. It is easy to verify that P N is a vector space with these operations.

A solution on P N is a function \(\varphi: P^{N} \rightarrow \mathbb{R}^{n}\). If \(\varphi\) is a solution and c ∈ P N, then we can interpret \(\varphi _{i}(c) \in \mathbb{R}\) as the cost which agent i should expect from the problem c.

Next, we present some basic ideas related to cooperative games and potential of a cooperative game. For a brief revision of the concepts of cooperative games that are mentioned here, such as the Shapley value, see Driessen [3].

Shapley [6] characterized a unique solution (denoted by Sh) for cooperative gamesFootnote 1:

$$\displaystyle{ \mathit{Sh}_{i}(N,v) =\sum _{\{S\subseteq N:i\notin S\}}\frac{s!(n - s - 1)!} {n!} \left [v(S \cup \{ i\}) - v(S)\right ] }$$

Now, let (N, v) a cooperative game and let us denote by \(G =\{ (S,v_{S})\mid S \subseteq N\}\) the family of subgames of (N, v). The potential of a game is defined as a function

$$\displaystyle{ P: G \rightarrow \mathbb{R} }$$

such that for every \(S \subseteq N\),

$$\displaystyle{ \mathop{\sum }\limits_{j \in S}\left [P(S,v_{S}) - P(S\setminus \{j\},v_{S\setminus \{j\}})\right ] = v(S) }$$

with the condition that \(P(\varnothing,v_{\varnothing }) = 0\). Furthermore, it is assumed that the loss of potential

$$\displaystyle{ P(S,v_{S}) - P(S\setminus \{j\},v_{S\setminus \{j\}}) }$$

when the player j abandons the game, is equal to the amount that corresponds to this player in the game (S, v S ). Moreover, it turns out that this difference is equal to the Shapley value of player j in the game (S, v S ).

35.3 The Potential of Job Scheduling Problems

We need to define the loss of potential when one agent abandons a problem. A priori it could be from any list, so we propose the average loss of potential instead. Let us formalize this idea.

For each \(S \subseteq N\,\), S o will denote the list in Π(S) that generates the lowest cost for processing the jobs in S, i.e., S o is such that \(c(S_{o}) =\min \left \{c(S_{\pi })\right \}_{\pi \in \theta _{S}}\). Let us denote

$$\displaystyle{ \overline{\mathit{Pot}}(S\setminus \{i\}) =\mathop{\sum }\limits_{ T_{\pi } \in \varPi (S\setminus \{i\})}\frac{\mathit{Pot}(T_{\pi })} {(s - 1)!} }$$
(35.2)

Definition 35.2.

We define the potential of the job scheduling problem c ∈ P N as a function

$$\displaystyle{ \mathit{Pot}: E_{N} \rightarrow \mathbb{R} }$$
(35.3)

such that \(\mathit{Pot}(\left [\varnothing \right ]) = 0\) and

$$\displaystyle{ \mathop{\sum }\limits_{i \in S}\left [\mathit{Pot}(S_{\pi }) -\overline{\mathit{Pot}}(S\setminus \{i\})\right ] = c(S_{\pi }) }$$
(35.4)

for every \(S \subseteq N\) and every π ∈ θ S .

As in Hart and Mas-Colell [5], we will suppose that

$$\displaystyle{ \mathit{Pot}(N_{o}) -\overline{\mathit{Pot}}(N\setminus \{i\}) }$$
(35.5)

is the amount that agent i should pay for processing his job. This amount is the average of the loss of potential when the agent i abandons the system. It is easy to see that (35.4) is equivalent to the following recursive expression,

$$\displaystyle{ \mathit{Pot}(S_{\pi }) = \frac{c(S_{\pi })} {s} +\mathop{\sum }\limits_{ i \in S}\mathop{\sum }\limits_{T_{\pi } \in \varPi (S\setminus \{i\})}\frac{\mathit{Pot}(T_{\pi })} {s!} }$$
(35.6)

for every S ⊆ N and every π ∈ θ S , which determines the potential of the job scheduling problem. Now, \(\varphi (c)\) denotes the vector of costs for processing the jobs of agents N, i.e., the vector with entry i is given by

$$\displaystyle{ \varphi _{i}(c) = \mathit{Pot}(N_{o}) -\overline{\mathit{Pot}}(N\setminus \{i\}) }$$
(35.7)

and we will call it a cost sharing mechanism for the job scheduling problem c.

Example 35.1.

In this example, we have three agents with set of jobs N = { 1, 2, 3}, where the cost function c is given by

$$\displaystyle{ \begin{array}{|c||c|c|c|c|c|c|c|c|c|} \hline S_{\pi } &[1]&[2]&[3]&[1,2]&[2,1]&[1,3]&[3,1]&[2.3]&[3,2] \\ \hline c(S_{\pi })& 10 & 18 & 12 & 21 & 25 & 19 & 22 & 27 & 26 \\ \hline \end{array} }$$
$$\displaystyle{ \begin{array}{|c||c|c|c|c|c|c|} \hline S_{\pi } &[1,2,3]&[1,3,2]&[2,1,3]&[2,3,1]&[3,1,2]&[3,2,1] \\ \hline c(S_{\pi })& 35 & 37 & 31 & 30 & 40 & 35 \\ \hline \end{array} }$$

Notice that N o  = [2, 3, 1] . In order to compute Pot(N o ) using (35.6), we need to generate all subproblems as the result of removing one job. We repeat this process in each case until there are no jobs. Observe that for lists with one job, say [a], \(\mathit{Pot}(\left [a\right ]) = c([a])\). While if the list has two jobs, then \(\mathit{Pot}([b,d]) = \frac{1} {2}\left [c([b,d]) + c([b]) + c([d])\right ]\). Thus

$$\displaystyle{ \begin{array}{|c||c|c|c|c|c|c|c|c|c|c|} \hline S_{\pi } &[1]&[2]&[3]&[1,2]&[2,1]&[1,3]&[3,1]& [2.3] &[3,2]&[2,3,1] \\ \hline \mathit{Pot}(S_{\pi })& 10 & 18 & 12 &49/2&53/2&41/2& 22 &57/2& 28 & 35 \\ \hline \end{array} }$$

Now, we can calculate the costs for the job scheduling problem using (35.7):

$$\displaystyle{ \overline{\mathit{Pot}}(N\setminus \{1\}) = \frac{1} {2}\left (\frac{57} {2} + 28\right ) = \frac{113} {4} }$$
$$\displaystyle{ \overline{\mathit{Pot}}(N\setminus \{2\}) = \frac{1} {2}\left (\frac{41} {2} + 22\right ) = \frac{85} {4} }$$
$$\displaystyle{ \overline{\mathit{Pot}}(N\setminus \{3\}) = \frac{1} {2}\left (\frac{49} {2} + \frac{53} {2} \right ) = \frac{51} {2} }$$

Thus, the vector of costs for processing the jobs is

$$\displaystyle{ \varphi (c) = \left [\begin{array}{c} 35 - 113/4 \\ 35 - 85/4 \\ 35 - 51/2 \end{array} \right ] = \left [\begin{array}{c} 27/4 \\ 55/4 \\ 19/2 \end{array} \right ] = \left [\begin{array}{c} 6.75\\ 13.75 \\ 9.5 \end{array} \right ] }$$

35.4 Properties of the Potential

The next theorem establishes an explicit expression for the potential of the job scheduling problem.

Theorem 35.1.

For each S π ∈ E N , we have that

$$\displaystyle{ \mathit{Pot}(S_{\pi }) = \frac{c(S_{\pi })} {s} +\mathop{\sum }\limits_{ T \subsetneq S}\mathop{\sum }\limits_{L_{\pi } \in \varPi (T)}\frac{(s - t)!} {s!t} \cdot c(L_{\pi }) }$$
(35.8)

Proof.

The proof is by induction on the cardinality of S π . For one job, i.e., \(\left \vert S_{\pi }\right \vert = 1\), both (35.6) and (35.8) are equal to c(S π ). Let us suppose that (35.6) and (35.8) are equal for \(T_{\pi } \in \varPi (S\setminus \{i\})\) for every π ∈ θ S and every j ∈ N. Then,

$$\displaystyle{ \mathop{\sum }\limits_{i \in S}\mathop{\sum }\limits_{T_{\pi } \in \varPi (S\setminus \{i\})}\frac{\mathit{Pot}(T_{\pi })} {s!} =\mathop{\sum }\limits_{ i \in S}\mathop{\sum }\limits_{T_{\pi } \in \varPi (S\setminus \{i\})}\left [\frac{c(T_{\pi })} {s!t} +\mathop{\sum }\limits_{ R \subsetneq T}\mathop{\sum }\limits_{L_{\pi } \in \varPi (R)}\frac{(t - r)!} {s!t!r} \cdot c(L_{\pi })\right ] }$$

Now, since in the third sum \(T = S\setminus \{i\}\), then \(t = s - 1\) and we have that

$$\displaystyle\begin{array}{rcl} & =& \mathop{\sum }\limits_{i \in S}\mathop{\sum }\limits_{T_{\pi } \in \varPi (S\setminus \{i\})} \frac{c(T_{\pi })} {s!(s - 1)} +\mathop{\sum }\limits_{ i \in S}\mathop{\sum }\limits_{R \subsetneq S\setminus \{i\}}\mathop{\sum }\limits_{L_{\pi } \in \varPi (R)}\frac{(s - r - 1)!(s - 1)!} {s!(s - 1)!r} \cdot c(L_{\pi }) {}\\ & =& \mathop{\sum }\limits_{i \in S}\mathop{\sum }\limits_{T_{\pi } \in \varPi (S\setminus \{i\})} \frac{c(T_{\pi })} {s!(s - 1)} +\mathop{\sum }\limits_{ i \in S}\mathop{\sum }\limits_{R \subsetneq S\setminus \{i\}}\mathop{\sum }\limits_{L_{\pi } \in \varPi (R)}\frac{(s - r - 1)!} {s!r} \cdot c(L_{\pi }) {}\\ & =& \mathop{\sum }\limits_{i \in S}\mathop{\sum }\limits_{R \subsetneq S\setminus \{i\}}\mathop{\sum }\limits_{L_{\pi } \in \varPi (R)}\frac{(s - r - 1)!} {s!r} \cdot c(L_{\pi }) {}\\ & =& \mathop{\sum }\limits_{R \subsetneq S}\mathop{\sum }\limits_{L_{\pi } \in \varPi (R)}\frac{(s - r - 1)!(s - r)} {s!r} \cdot c(L_{\pi }) =\mathop{\sum }\limits_{ R \subsetneq S}\mathop{\sum }\limits_{L_{\pi } \in \varPi (R)}\frac{(s - r)!} {s!r} \cdot c(L_{\pi }) {}\\ & =& \mathit{Pot}(S_{\pi }) -\frac{c(S_{\pi })} {s} {}\\ \end{array}$$

Now, the next result provides us an alternative way to compute the cost sharing mechanism \(\varphi (c)\) for the job scheduling problem c. For \(S \subseteq N\), we will denote by

$$\displaystyle{ \mu (S) =\mathop{\sum }\limits_{ T_{\pi } \in \varPi (S)}c(T_{\pi }) }$$

Theorem 35.2.

The cost for agent i in the job scheduling problem c is given by

$$\displaystyle{ \varphi _{i}(c) = \frac{c(N_{o})} {n} +\mathop{\sum }\limits_{\{ S \subsetneq N: i \in S\}}\left [\frac{(n - s)!} {n!s} \cdot \mu (S) -\frac{(s - 1)!} {n!} \cdot \mu (N\setminus S)\right ] }$$
(35.9)

Proof.

By the previous theorem, we have that

$$\displaystyle\begin{array}{rcl} \overline{\mathit{Pot}}(N\setminus \{i\})& =& \mathop{\sum }\limits_{S_{\pi } \in \varPi (N\setminus \{i\})} \frac{\mathit{Pot}(S_{\pi })} {(n - 1)!} {}\\ & =& \mathop{\sum }\limits_{S_{\pi } \in \varPi (N\setminus \{i\})}\left [ \frac{c(S_{\pi })} {(n - 1)!s} +\mathop{\sum }\limits_{ T \subsetneq S}\mathop{\sum }\limits_{L_{\pi } \in \varPi (T)} \frac{(s - t)!} {(n - 1)!s!t} \cdot c(L_{\pi })\right ] {}\\ \end{array}$$

Since \(S = N\setminus \{i\}\), then \(s = n - 1\) and so

$$\displaystyle\begin{array}{rcl} & =& \frac{\mu (N\setminus \{i\})} {(n - 1)!(n - 1)} +\mathop{\sum }\limits_{ S_{\pi } \in \varPi (N\setminus \{i\})}\mathop{\sum }\limits_{T \subsetneq S} \frac{(s - t)!} {(n - 1)!s!t} \cdot \mu (T) {}\\ & =& \frac{\mu (N\setminus \{i\})} {(n - 1)!(n - 1)} +\mathop{\sum }\limits_{ T \subsetneq N\setminus \{i\}}\frac{(n - t - 1)!(n - 1)!} {(n - 1)!(n - 1)!t} \cdot \mu (T) {}\\ & =& \frac{\mu (N\setminus \{i\})} {(n - 1)!(n - 1)} +\mathop{\sum }\limits_{ T \subsetneq N\setminus \{i\}}\frac{(n - t - 1)!} {(n - 1)!t} \cdot \mu (T) {}\\ \end{array}$$

Notice that for T = N∖{i}, \(t = n - 1\) and \(\frac{(n-t-1)!} {(n-1)!t} = \frac{1} {(n-1)!(n-1)}\). Then

$$\displaystyle{ =\mathop{\sum }\limits_{ T \subseteq N\setminus \{i\}}\frac{(n - t - 1)!} {(n - 1)!t} \cdot \mu (T) =\mathop{\sum }\limits_{\{ T \subsetneq N: i \in T\}} \frac{(t - 1)!} {(n - 1)!(n - t)} \cdot \mu (N\setminus T) }$$

On the other hand,

$$\displaystyle\begin{array}{rcl} \mathit{Pot}(N_{o})& =& \frac{c(N_{o})} {n} +\mathop{\sum }\limits_{ T \subsetneq N}\mathop{\sum }\limits_{L_{\pi } \in \varPi (T)}\frac{(n - t)!} {n!t} \cdot c(L_{\pi }) {}\\ & =& \frac{c(N_{o})} {n} +\mathop{\sum }\limits_{ T \subsetneq N}\frac{(n - t)!} {n!t} \cdot \mu (T) {}\\ & =& \frac{c(N_{o})} {n} +\mathop{\sum }\limits_{\{ T \subsetneq N: i \in T\}}\frac{(n - t)!} {n!t} \cdot \mu (T) +\mathop{\sum }\limits_{\{ T \subsetneq N: i\notin T\}}\frac{(n - t)!} {n!t} \cdot \mu (T) {}\\ & =& \frac{c(N_{o})} {n} +\mathop{\sum }\limits_{\{ T \subsetneq N: i \in T\}}\frac{(n - t)!} {n!t} \cdot \mu (T) +\mathop{\sum }\limits_{\{ T \subsetneq N: i \in T\}} \frac{t!} {n!(n - t)} \cdot \mu (N\setminus T){}\\ \end{array}$$

Therefore,

$$\displaystyle\begin{array}{rcl} \varphi _{i}(N,c)& =& \mathit{Pot}(N_{o}) -\overline{\mathit{Pot}}(N\setminus \{i\}) {}\\ & =& \frac{c(N_{o})} {n} +\mathop{\sum }\limits_{\{ T \subsetneq N: i \in T\}}\frac{(n - t)!} {n!t} \cdot \mu (T) +\mathop{\sum }\limits_{\{ T \subsetneq N: i \in T\}} \frac{t!} {n!(n - t)} \cdot \mu (N\setminus T) {}\\ & & -\mathop{\sum }\limits_{\{T \subsetneq N: i \in T\}} \frac{(t - 1)!} {(n - 1)!(n - t)} \cdot \mu (N\setminus T) {}\\ & =& \frac{c(N_{o})} {n} +\mathop{\sum }\limits_{\{ S \subsetneq N: i \in S\}}\left [\frac{(n - s)!} {n!s} \cdot \mu (S) -\frac{(s - 1)!} {n!} \cdot \mu (N\setminus S)\right ] {}\\ \end{array}$$

Example 35.2.

We compute the cost sharing mechanism for the job scheduling problem in Example 35.3:

$$\displaystyle\begin{array}{rcl} \mu (\{1\})& =& 10\text{, }\mu (\{2\}) = 18\text{, }\mu (\{3\}) = 12 {}\\ \mu (\{1,2\})& =& 46\text{, }\mu (\{1,3\}) = 41\text{, }\mu (\{2,3\}) = 53 {}\\ \end{array}$$

and therefore,

$$\displaystyle\begin{array}{rcl} \varphi _{1}(c)& =& \frac{30} {3} + \frac{1} {3}(10) -\frac{1} {6}(53) + \frac{1} {12}(46) -\frac{1} {6}(12) + \frac{1} {12}(41) -\frac{1} {6}(18) = \frac{27} {4} {}\\ \varphi _{2}(c)& =& \frac{30} {3} + \frac{1} {3}(18) -\frac{1} {6}(41) + \frac{1} {12}(46) -\frac{1} {6}(12) + \frac{1} {12}(53) -\frac{1} {6}(10) = \frac{55} {4} {}\\ \varphi _{3}(c)& =& \frac{30} {3} + \frac{1} {3}(12) -\frac{1} {6}(46) + \frac{1} {12}(41) -\frac{1} {6}(18) + \frac{1} {12}(53) -\frac{1} {6}(10) = \frac{19} {2} {}\\ \end{array}$$

The next result establishes a relation between the cost sharing mechanism given by (35.7) and the Shapley value. The process of bargaining generates a cooperative game in a natural way: when the coalition of agents \(S \subsetneq N\) is formed they can generate an efficiency \(\frac{\mu (S)} {s!}\), and if N is formed, they can generate c(N o ). In other words, if c ∈ P N, we can associate a cooperative game in characteristic function form w c as follows:

$$\displaystyle{ w_{c}(S) = \left \{\begin{array}{cc} c(N_{o})&\text{if }S = N \\ \frac{\mu (S)} {s!} & \text{if }S \subsetneq N \end{array} \right. }$$
(35.10)

Theorem 35.3.

For c ∈ P N we have that

$$\displaystyle{ \varphi (c) = \mathit{Sh}(N,w_{c}) }$$

Proof.

By the proof of the previous theorem,

$$\displaystyle\begin{array}{rcl} \mathit{Pot}(N_{o})& =& \frac{c(N_{o})} {n} +\mathop{\sum }\limits_{ T \subsetneq N}\frac{(n - t)!} {n!t} \cdot \mu (T) {}\\ & =& \frac{w(N)} {n} +\mathop{\sum }\limits_{ T \subsetneq N}\frac{(n - t)!(t - 1)!} {n!} \cdot \frac{\mu (T)} {t!} {}\\ & =& \frac{w(N)} {n} +\mathop{\sum }\limits_{ T \subsetneq N}\frac{(n - t)!(t - 1)!} {n!} \cdot w_{c}(T) {}\\ \end{array}$$

Observe that \(\frac{(n-t)!(t-1)!} {n!} = \frac{1} {n}\) for T = N, then

$$\displaystyle\begin{array}{rcl} & =& \mathop{\sum }\limits_{T \subseteq N}\frac{(n - t)!(t - 1)!} {n!} \cdot w_{c}(T) {}\\ & =& \mathop{\sum }\limits_{\{T \subseteq N: i \in S\}}\frac{(n - t)!(t - 1)!} {n!} \cdot w_{c}(T) +\mathop{\sum }\limits_{\{ T \subseteq N: i\notin S\}}\frac{(n - t)!(t - 1)!} {n!} \cdot w_{c}(T) {}\\ & =& \mathop{\sum }\limits_{\{T \subseteq N: i\notin S\}}\frac{(n - t - 1)!t!} {n!} \cdot w_{c}(T \cup \{ i\}) +\mathop{\sum }\limits_{\{ T \subseteq N: i\notin S\}}\frac{(n - t)!(t - 1)!} {n!} \cdot w_{c}(T) {}\\ \end{array}$$

In a similar way,

$$\displaystyle\begin{array}{rcl} \overline{\mathit{Pot}}(N\setminus \{i\})& =& \mathop{\sum }\limits_{T \subseteq N\setminus \{i\}}\frac{(n - t - 1)!} {(n - 1)!t} \cdot \mu (T) {}\\ & =& \mathop{\sum }\limits_{T \subseteq N\setminus \{i\}}\frac{(n - t - 1)!(t - 1)!} {(n - 1)!} \cdot \frac{\mu (T)} {t!} {}\\ & =& \mathop{\sum }\limits_{\{T \subseteq N: i\notin S\}}\frac{(n - t - 1)!(t - 1)!} {(n - 1)!} \cdot w_{c}(T) {}\\ \end{array}$$

Therefore,

$$\displaystyle\begin{array}{rcl} \varphi _{i}(N,c)& =& \mathit{Pot}(N_{o}) -\overline{\mathit{Pot}}(N\setminus \{i\}) {}\\ & =& \mathop{\sum }\limits_{\{T \subseteq N: i\notin S\}}\frac{(n - t - 1)!t!} {n!} \cdot w_{c}(T \cup \{ i\}) {}\\ & & +\mathop{\sum }\limits_{\{T \subseteq N: i\notin S\}}\frac{(n - t)!(t - 1)!} {n!} \cdot w_{c}(T) {}\\ & & -\mathop{\sum }\limits_{\{T \subseteq N: i\notin S\}}\frac{(n - t - 1)!(t - 1)!} {(n - 1)!} \cdot w_{c}(T) {}\\ & =& \sum _{\{T\subseteq N:i\notin S\}}\frac{(n - t - 1)!t!} {n!} \left [w_{c}(T \cup \{ i\}) - w_{c}(T)\right ] {}\\ & =& \mathit{Sh}_{i}(N,w_{c}) {}\\ \end{array}$$

Example 35.3.

The cooperative game associated with the job scheduling problem in Example 35.3 is given by

$$\displaystyle{ \begin{array}{|c||c|c|c|c|c|c|c|} \hline S & \{1\} & \{2\} & \{3\} &\{1,2\}& \{1,3\} & \{2,3\} &\{1,2,3\} \\ \hline w_{c}(S)&10&18&12& 23 &41/2&53/2& 30 \\ \hline \end{array} }$$

Remark 35.1.

The solution for the job scheduling problem c given by (35.9), is efficient with respect to N o by construction. According to (35.4),

$$\displaystyle{ \mathop{\sum }\limits_{i \in N}\varphi _{i}(c) =\mathop{\sum }\limits_{ i \in N}\left [\mathit{Pot}(N_{o}) -\overline{\mathit{Pot}}(S\setminus \{i\})\right ] = c(N_{o}) }$$

Observe that the group of permutations of the set of agents, θ N , acts on E N in a natural way:

$$\displaystyle{ \theta \left (\left [l_{1},l_{2},\ldots,l_{s}\right ]\right ) = \left [l_{\theta (1)},l_{\theta (2)},\ldots,l_{\theta (s)}\right ] }$$

for θ ∈ θ N and \(\left [l_{1},l_{2},\ldots,l_{s}\right ] \in E_{N}\). For every θ ∈ θ N and c ∈ P N, we define (θ ⋅ c) ∈ P N as:

$$\displaystyle{ (\theta \cdot c)(S_{\pi }) = c(\theta ^{-1}(S_{\pi })) }$$

We can easily verify that w θ⋅ c  = θ ⋅ w c for every θ ∈ θ N and every c ∈ P N.

Remark 35.2.

From the previous observation, the symmetry of the Shapley value and Theorem 7, the solution given by (35.9) satisfies a symmetry condition:

$$\displaystyle{ \varphi (\theta \cdot c) =\theta \cdot \varphi (c) }$$

for every θ ∈ θ N and c ∈ P N. This is true since

$$\displaystyle{ \varphi (\theta \cdot c) = \mathit{Sh}(N,w_{\theta \cdot c}) = \mathit{Sh}(N,\theta \cdot w_{c}) =\theta \cdot \mathit{Sh}(N,w_{c}) =\theta \cdot \varphi (c) }$$

Such symmetry condition implies that the selected allocation only depends on the cost function c, and not, for instance, on the numbering of the agents.

35.5 Conclusion

We studied the problem of sharing costs for a job scheduling problem on a single server, when jobs are ordered in a queue. We took a cooperative game theory approach and propose a cost sharing mechanism for the previous problem, by using a modification of the concept of potential of a cooperative game. In fact, it was established a relation between such cost sharing mechanism and the Shapley value of a certain cooperative game.

This cost sharing mechanism was provided for the case where we suppose we know the costs for processing any set of jobs in any order and where agents will process their jobs according to the order that generates the minimum cost to them, therefore they have no preferences in the order their jobs are processed.

In future, we plan to further look at cost sharing mechanisms other than the Shapley value. Investigating the strategic power of jobs in such mechanisms is another line of future research.