Cost Sharing in a Job Scheduling Problem Using the Shapley Value Debasis Mishra Center for Operations Research and Econometrics (CORE) Universit´e Catholique de Louvain Louvain la Neuve, Belgium mishra@core.ucl.ac.be Bharath Rangarajan Center for Operations Research and Econometrics (CORE) Universit´e Catholique de Louvain Louvain la Neuve, Belgium rangarajan@core.ucl.ac.be ABSTRACT A set of jobs need to be served by a single server which can serve only one job at a time. Jobs have processing times and incur waiting costs (linear in their waiting time). The jobs share their costs through compensation using monetary transfers. We characterize the Shapley value rule for this model using fairness axioms. Our axioms include a bound on the cost share of jobs in a group, efficiency, and some independence properties on the the cost share of a job. Categories and Subject Descriptors J.4 [Social and Behaviorial Sciences]: Economics General Terms Economics, Theory 1. INTRODUCTION A set of jobs need to be served by a server. The server can process only one job at a time. Each job has a finite processing time and a per unit time waiting cost. Efficient ordering of this queue directs us to serve the jobs in increasing order of the ratio of per unit time waiting cost and processing time. To compensate for waiting by jobs, monetary transfers to jobs are allowed. How should the jobs share the cost equitably amongst themselves (through transfers)? The problem of fair division of costs among agents in a queue has 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). Study of queueing problems has attracted economists for a long time [7, 17]. Cost sharing is a fundamental problem in many settings on the Internet. Internet can be seen as a common resource shared by many users and the cost incured by using the resource needs to be shared in an equitable manner. The current surge in cost sharing literature from computer scientists validate this claim [8, 11, 12, 6, 24]. Internet has many settings in which our model of job scheduling appears and the agents waiting in a queue incur costs (jobs scheduled on servers, queries answered from a database, data scheduled to be transmitted over a fixed bandwidth network etc.). We hope that our analysis will give new insights on cost sharing problems of this nature. Recently, there has been increased interest in cost sharing methods with submodular cost functions [11, 12, 6, 24]. While many settings do have submodular cost functions (for example, multi-cast transmission games [8]), while the cost function of our game is supermodular. Also, such literature typically does not assume budget-balance (transfers adding up to zero), while it is an inherent feature of our model. A recent paper by Maniquet [15] is the closest to our model and is the motivation behind our work 1 . Maniquet [15] studies a model where he assumes all processing times are unity. For such a model, he characterizes the Shapley value rule using classical fairness axioms. Chun [1] interprets the worth of a coalition of jobs in a different manner for the same model and derives a reverse rule. Chun characterizes this rule using similar fairness axioms. Chun [2] also studies the envy properties of these rules. Moulin [22, 21] studies the queueing problem from a strategic point view when per unit waiting costs are unity. Moulin introduces new concepts in the queueing settings such as splitting and merging of jobs, and ways to prevent them. Another stream of literature is on sequencing games, first introduced by Curiel et al. [4]. For a detailed survey, refer to Curiel et al. [3]. Curiel et al. [4] defined sequencing games similar to our model, but in which an initial ordering of jobs is given. Besides, their notion of worth of a coalition is very different from the notions studied in Maniquet [15] and Chun [1] (these are the notions used in our work too). The particular notion of the worth of a coalition makes the sequencing game of Curiel et al. [4] convex, whereas our game is not convex and does not assume the presence of any initial order. In summary, the focus of this stream of 1 The authors thank Fran¸cois Maniquet for several fruitful discussions. 232 research is how to share the savings in costs from the initial ordering to the optimal ordering amongst jobs (also see Hamers et al. [9], Curiel et al. [5]). Recently, Klijn and S´anchez [13, 14] considered sequencing games without any initial ordering of jobs. They take two approaches to define the worth of coalitions. One of their approaches, called the tail game, is related to the reverse rule of Chun [1]. In the tail game, jobs in a coalition are served after the jobs not in the coalition are served. Klijn and S´anchez [14] showed that the tail game is balanced. Further, they provide expressions for the Shapley value in tail game in terms of marginal vectors and reversed marginal vectors. We provide a simpler expression of the Shapley value in the tail game, generalizing the result in Chun [1]. Klijn and S´anchez [13] study the core of this game in detail. Strategic aspects of queueing problems have also been researched. Mitra [19] studies the first best implementation in queueing models with generic cost functions. First best implementation means that there exists an efficient mechanism in which jobs in the queue have a dominant strategy to reveal their true types and their transfers add up to zero. Suijs [27] shows that if waiting costs of jobs are linear then first best implementation is possible. Mitra [19] shows that among a more general class of queueing problems first best implementation is possible if and only if the cost is linear. For another queueing model, Mitra [18] shows that first best implementation is possible if and only if the cost function satisfies a combinatorial property and an independence property. Moulin [22, 21] studies strategic concepts such as splitting and merging in queueing problems with unit per unit waiting costs. The general cost sharing literature is vast and has a long history. For a good survey, we refer to [20]. From the seminal work of Shapley [25] to recent works on cost sharing in multi-cast transmission and optimization problems [8, 6, 23] this area has attracted economists, computer scientists, and operations researchers. 1.1 Our Contribution Ours is the first model which considers cost sharing when both processing time and per unit waiting cost of jobs are present. We take a cooperative game theory approach and apply the classical Shapley value rule to the problem. We show that the Shapley value rule satisfies many intuitive fairness axioms. Due to two dimensional nature of our model and one dimensional nature of Maniquet"s model [15], his axioms are insufficient to characterize the Shapley value in our setting. We introduce axioms such as independece of preceding jobs" unit waiting cost and independence of following jobs" processing time. A key axiom that we introduce gives us a bound on cost share of a job in a group of jobs which have the same ratio of unit time waiting cost and processing time (these jobs can be ordered in any manner between themseleves in an efficient ordering). If such a group consists of just one job, then the axiom says that such a job should at least pay his own processing cost (i.e., the cost it would have incurred if it was the only job in the queue). If there are multiple jobs in such a group, the probability of any two jobs from such a group inflicting costs on each other is same (1 2 ) in an efficient ordering. Depending on the ordering selected, one job inflicts cost on the other. Our fairness axiom says that each job should at least bear such expected costs. We characterize the Shapley value rule using these fairness axioms. We also extend the envy results in [2] to our setting and discuss a class of reasonable cost sharing mechanisms. 2. THE MODEL There are n jobs that need to be served by one server which can process only one job at a time. The set of jobs are denoted as N = {1, . . . , n}. σ : N → N is an ordering of jobs in N and σi denotes the position of job i in the ordering σ. Given an ordering σ, define Fi(σ) = {j ∈ N : σi < σj} and Pi(σ) = {j ∈ N : σi > σj}. Every job i is identified by two parameters: (pi, θi). pi is the processing time and θi is the cost per unit waiting time of job i. Thus, a queueing problem is defined by a list q = (N, p, θ) ∈ Q, where Q is the set of all possible lists. We will denote γi = θi pi . Given an ordering of jobs σ, the cost incurred by job i is given by ci(σ) = piθi + θi j∈Pi(σ) pj. The total cost incurred by all jobs due to an ordering σ can be written in two ways: (i) by summing the cost incurred by every job and (ii) by summing the costs inflicted by a job on other jobs with their own processing cost. C(N, σ) = i∈N ci(σ) = i∈N piθi + i∈N ¡θi j∈Pi(σ) pj¢. = i∈N piθi + i∈N ¡pi j∈Fi(σ) θj¢. An efficient ordering σ∗ is the one which minimizes the total cost incurred by all jobs. So, C(N, σ∗ ) ≤ C(N, σ) ∀ σ ∈ Σ. To achieve notational simplicity, we will write the total cost in an efficient ordering of jobs from N as C(N) whenever it is not confusing. Sometimes, we will deal with only a subset of jobs S ⊆ N. The ordering σ will then be defined on jobs in S only and we will write the total cost from an efficient ordering of jobs in S as C(S). The following lemma shows that jobs are ordered in decreasing γ in an efficient ordering. This is also known as the weighted shortest processing time rule, first introduced by Smith [26]. Lemma 1. For any S ⊆ N, let σ∗ be an efficient ordering of jobs in S. For every i = j, i, j ∈ S, if σ∗ i > σ∗ j , then γi ≤ γj. Proof. Assume for contradiction that the statment of the lemma is not true. This means, we can find two consecutive jobs i, j ∈ S (σ∗ i = σ∗ j + 1) such that γi > γj. Define a new ordering σ by interchanging i and j in σ∗ . The costs to jobs in S \ {i, j} is not changed from σ∗ to σ. The difference between total costs in σ∗ and σ is given by, C(S, σ) − C(S, σ∗ ) = θjpi − θipj. From efficiency we get θjpi − θipj ≥ 0. This gives us γj ≥ γi, which is a contradiction. An allocation for q = (N, p, θ) ∈ Q has two components: an ordering σ and a transfer ti for every job i ∈ N. ti denotes the payment received by job i. Given a transfer ti and an ordering σ, the cost share of job i is defined as, πi = ci(σ) − ti = θi j∈N:σj ≤σi pj − ti. 233 An allocation (σ, t) is efficient for q = (N, p, θ) whenever σ is an efficient ordering and £i∈N ti = 0. The set of efficient orderings of q is denoted as Σ∗ (q) and σ∗ (q) will be used to refer to a typical element of the set. The following straightforward lemma says that for two different efficient orderings, the cost share in one efficient allocation is possible to achieve in the other by appropriately modifying the transfers. Lemma 2. Let (σ, t) be an efficient allocation and π be the vector of cost shares of jobs from this allocation. If σ∗ = σ be an efficient ordering and t∗ i = ci(σ∗ ) − πi ∀ i ∈ N, then (σ∗ , t∗ ) is also an efficient allocation. Proof. Since (σ, t) is efficient, £i∈N ti = 0. This gives £i∈N πi = C(N). Since σ∗ is an efficient ordering, £i∈N ci(σ∗ ) = C(N). This means, £i∈N t∗ i = £i∈N [ci(σ∗ ) − πi] = 0. So, (σ∗ , t∗ ) is an efficient allocation. Depending on the transfers, the cost shares in different efficient allocations may differ. An allocation rule ψ associates with every q ∈ Q a non-empty subset ψ(q) of allocations. 3. COST SHARING USING THE SHAPLEY VALUE In this section, we define the coalitional cost of this game and analyze the solution proposed by the Shapley value. Given a queue q ∈ Q, the cost of a coalition of S ⊆ N jobs in the queue is defined as the cost incurred by jobs in S if these are the only jobs served in the queue using an efficient ordering. Formally, the cost of a coalition S ⊆ N is, C(S) = i∈S j∈S:σ∗ j ≤σ∗ i θjpj, where σ∗ = σ∗ (S) is an efficient ordering considering jobs from S only. The worth of a coalition of S jobs is just −C(S). Maniquet [15] observes another equivalent way to define the worth of a coalition is using the dual function of the cost function C(·). Other interesting ways to define the worth of a coalition in such games is discussed by Chun [1], who assume that a coalition of jobs are served after the jobs not in the coalition are served. The Shapley value (or cost share) of a job i is defined as, SVi = S⊆N\{i} |S|!(|N| − |S| − 1)! |N|! ¡C(S∪{i})−C(S)¢. (1) The Shapley value allocation rule says that jobs are ordered using an efficient ordering and transfers are assigned to jobs such that the cost share of job i is given by Equation 1. Lemma 3. Let σ∗ be an efficient ordering of jobs in set N. For all i ∈ N, the Shapley value is given by, SVi = piθi + 1 2 ¡Li + Ri¢, where Li = θi £j∈Pi(σ∗) pj and Ri = pi £j∈Fi(σ∗) θj. Proof. Another way to write the Shapley value formula is the following [10], SVi = S⊆N:i∈S ∆(S) |S| , where ∆(S) = C(S) if |S| = 1 and ∆(S) = C(S)−£T S ∆(T). This gives ∆({i}) = C({i}) = piθi ∀i ∈ N. For any i, j ∈ N with i = j, we have ∆({i, j}) = C({i, j}) − C({i}) − C({j}) = min(piθi + pjθj + pjθi, piθi + pjθj + piθj) − piθi − pjθj = min(pjθi, piθj). We will show by induction that ∆(S) = 0 if |S| > 2. For |S| = 3, let S = {i, j, k}. Without loss of generality, assume θi pi ≥ θj pj ≥ θk pk . So, ∆(S) = C(S) − ∆({i, j}) − ∆({j, k}) − ∆({i, k})−∆({i})−∆({j})−∆({k}) = C(S)−piθj −pjθk − piθk − piθi − pjθj − pkθk = C(S) − C(S) = 0. Now, assume for T S, ∆(T) = 0 if |T| > 2. Without loss of generality assume that σ to be the identity mapping. Now, ∆(S) = C(S) − T S ∆(T) = C(S) − i∈S j∈S:j<i ∆({i, j}) − i∈S ∆({i}) = C(S) − i∈S j∈S:j<i pjθi − i∈S piθi = C(S) − C(S) = 0. This proves that ∆(S) = 0 if |S| > 2. Using the Shapley value formula now, SVi = S⊆N:i∈S ∆(S) |S| = ∆({i}) + 1 2 j∈N:j=i ∆({i, j}) = piθi + 1 2 ¡ j<i ∆({i, j}) + j>i ∆({i, j})¢ = piθi + 1 2 ¡ j<i pjθi + j>i piθj¢= piθi + 1 2 ¡Li + Ri¢. 4. AXIOMATICCHARACTERIZATIONOF THE SHAPLEY VALUE In this section, we will define serveral axioms on fairness and characterize the Shapley value using them. For a given q ∈ Q, we will denote ψ(q) as the set of allocations from allocation rule ψ. Also, we will denote the cost share vector associated with an allocation rule (σ, t) as π and that with allocation rule (σ , t ) as π etc. 4.1 The Fairness Axioms We will define three types of fairness axioms: (i) related to efficiency, (ii) related to equity, and (iii) related to independence. Efficiency Axioms We define two types of efficiency axioms. One related to efficiency which states that an efficient ordering should be selected and the transfers of jobs should add up to zero (budget balance). Definition 1. An allocation rule ψ satisfies efficiency if for every q ∈ Q and (σ, t) ∈ ψ(q), (σ, t) is an efficient allocation. 234 The second axiom related to efficiency says that the allocation rule should not discriminate between two allocations which are equivalent to each other in terms of cost shares of jobs. Definition 2. An allocation rule ψ satisfies Pareto indifference if for every q ∈ Q, (σ, t) ∈ ψ(q), and (σ , t ) ∈ Σ(q), we have ¡πi = πi ∀ i ∈ N¢⇒ ¡(σ , t ) ∈ ψ(q)¢. An implication of Pareto indifference axiom and Lemma 2 is that for every efficient ordering there is some set of transfers of jobs such that it is part of an efficient rule and the cost share of a job in all these allocations are same. Equity Axioms How should the cost be shared between two jobs if the jobs have some kind of similarity between them? Equity axioms provide us with fairness properties which help us answer this question. We provide five such axioms. Some of these axioms (for example anonymity, equal treatment of equals) are standard in the literature, while some are new. We start with a well known equity axiom called anonymity. Denote ρ : N → N as a permutation of elements in N. Let ρ(σ, t) denote the allocation obtained by permuting elements in σ and t according to ρ. Similarly, let ρ(p, θ) denote the new list of (p, θ) obtained by permuting elements of p and θ according to ρ. Our first equity axiom states that allocation rules should be immune to such permutation of data. Definition 3. An allocation rule ψ satisfies anonymity if for all q ∈ Q, (σ, t) ∈ ψ(q) and every permutation ρ, we then ρ(σ, t) ∈ ψ(N, ρ(q)). The next equity axiom is classical in literature and says that two similar jobs should be compensated such that their cost shares are equal. This implies that if all the jobs are of same type, then jobs should equally share the total system cost. Definition 4. An allocation rule ψ satisfies equal treatment of equals (ETE) if for all q ∈ Q, (σ, t) ∈ ψ(q), i, j ∈ N, then ¡pi = pj; θi = θj¢⇒ ¡πi = πj¢. ETE directs us to share costs equally between jobs if they are of the same per unit waiting cost and processing time. But it is silent about the cost shares of two jobs i and j which satisfy θi pi = θj pj . We introduce a new axiom for this. If an efficient rule chooses σ such that σi < σj for some i, j ∈ N, then job i is inflicting a cost of piθj on job j and job j is inflicting zero cost on job i. Define for some γ ≥ 0, S(γ) = {i ∈ N : γi = γ}. In an efficient rule, the elements in S(γ) can be ordered in any manner (in |S(γ)|! ways). If i, j ∈ S(γ) then we have pjθi = piθj. Probability of σi < σj is 1 2 and so is the probability of σi > σj. The expected cost i inflicts on j is 1 2 piθj and j inflicts on i is 1 2 pjθi. Our next fairness axiom says that i and j should each be responsible for their own processing cost and this expected cost they inflict on each other. Arguing for every pair of jobs i, j ∈ S(γ), we establish a bound on the cost share of jobs in S(γ). We impose this as an equity axiom below. Definition 5. An allocation rule satisfies expected cost bound (ECB) if for all q ∈ Q, (σ, t) ∈ ψ(q) with π being the resulting cost share, for any γ ≥ 0, and for every i ∈ S(γ), we have πi ≥ piθi + 1 2 ¡ j∈S(γ):σj <σi pjθi + j∈S(γ):σj >σi piθj¢. The central idea behind this axiom is that of expected cost inflicted. If an allocation rule chooses multiple allocations, we can assign equal probabilities of selecting one of the allocations. In that case, the expected cost inflicted by a job i on another job j in the allocation rule can be calculated. Our axiom says that the cost share of a job should be at least its own processing cost and the total expected cost it inflicts on others. Note that the above bound poses no constraints on how the costs are shared among different groups. Also observe that if S(γ) contains just one job, ECB says that job should at least bear its own processing cost. A direct consequence of ECB is the following lemma. Lemma 4. Let ψ be an efficient rule which satisfies ECB. For a q ∈ Q if S(γ) = N, then for any (σ, t) ∈ ψ(q) which gives a cost share of π, πi = piθi + 1 2 ¡Li + Ri¢∀ i ∈ N. Proof. From ECB, we get πi ≥ piθi+1 2 ¡Li+Ri¢∀ i ∈ N. Assume for contradiction that there exists j ∈ N such that πj > pjθj + 1 2 ¡Li + Ri¢. Using efficiency and the fact that £i∈N Li = £i∈N Ri, we get £i∈N πi = C(N) > £i∈N piθi + 1 2 £i∈N ¡Li + Ri¢ = C(N). This gives us a contradiction. Next, we introduce an axiom about sharing the transfer of a job between a set of jobs. In particular, if the last job quits the system, then the ordering need not change. But the transfer to the last job needs to be shared between the other jobs. This should be done in proportion to their processing times because every job influenced the last job based on its processing time. Definition 6. An allocation rule ψ satisfies proportionate responsibility of p (PRp) if for all q ∈ Q, for all (σ, t) ∈ ψ(q), k ∈ N such that σk = |N|, q = (N \ {k}, p , θ ) ∈ Q, such that for all i ∈ N\{k}: θi = θi, pi = pi, there exists (σ , t ) ∈ ψ(q ) such that for all i ∈ N \ {k}: σi = σi and ti = ti + tk pi £j=k pj . An analogous fairness axiom results if we remove the job from the beginning of the queue. Since the presence of the first job influenced each job depending on their θ values, its transfer needs to be shared in proportion to θ values. Definition 7. An allocation rule ψ satisfies proportionate responsibility of θ (PRθ) if for all q ∈ Q, for all (σ, t) ∈ ψ(q), k ∈ N such that σk = 1, q = (N \{k}, p , θ ) ∈ Q, such that for all i ∈ N \{k}: θi = θi, pi = pi, there exists (σ , t ) ∈ ψ(q ) such that for all i ∈ N \ {k}: σi = σi and ti = ti + tk θi £j=k θj . The proportionate responsibility axioms are generalizations of equal responsibility axioms introduced by Maniquet [15]. 235 Independence Axioms The waiting cost of a job does not depend on the per unit waiting cost of its preceding jobs. Similarly, the waiting cost inflicted by a job to its following jobs is independent of the processing times of the following jobs. These independence properties should be carried over to the cost sharing rules. This gives us two independence axioms. Definition 8. An allocation rule ψ satisfies independence of preceding jobs" θ (IPJθ) if for all q = (N, p, θ), q = (N, p , θ ) ∈ Q, (σ, t) ∈ ψ(q), (σ , t ) ∈ ψ(q ), if for all i ∈ N \ {k}: θi = θi, pi = pi and γk < γk, pk = pk, then for all j ∈ N such that σj > σk: πj = πj, where π is the cost share in (σ, t) and π is the cost share in (σ , t ). Definition 9. An allocation rule ψ satisfies independence of following jobs" p (IFJp) if for all q = (N, p, θ), q = (N, p , θ ) ∈ Q, (σ, t) ∈ ψ(q), (σ , t ) ∈ ψ(q ), if for all i ∈ N \ {k}: θi = θi, pi = pi and γk > γk, θk = θk, then for all j ∈ N such that σj < σk: πj = πj, where π is the cost share in (σ, t) and π is the cost share in (σ , t ). 4.2 The Characterization Results Having stated the fairness axioms, we propose three different ways to characterize the Shapley value rule using these axioms. All our characterizations involve efficiency and ECB. But if we have IPJθ, we either need IFJp or PRp. Similarly if we have IFJp, we either need IPJθ or PRθ. Proposition 1. Any efficient rule ψ that satisfies ECB, IPJθ, and IFJp is a rule implied by the Shapley value rule. Proof. Define for any i, j ∈ N, θi j = γipj and pi j = θj γi . Assume without loss of generality that σ is an efficient ordering with σi = i ∀ i ∈ N. Consider the following q = (N, p , θ ) corresponding to job i with pj = pj if j ≤ i and pj = pi j if j > i, θj = θi j if j < i and θj = θj if j ≥ i. Observe that all jobs have the same γ: γi. By Lemma 2 and efficiency, (σ, t ) ∈ ψ(q ) for some set of transfers t . Using Lemma 4, we get cost share of i from (σ, t ) as πi = piθi + 1 2 ¡Li + Ri¢. Now, for any j < i, if we change θj to θj without changing processing time, the new γ of j is γj ≥ γi. Applying IPJθ, the cost share of job i should not change. Similarly, for any job j > i, if we change pj to pj without changing θj, the new γ of j is γj ≤ γi. Applying IFJp, the cost share of job i should not change. Applying this procedure for every j < i with IPJθ and for every j > i with IFJp, we reach q = (N, p, θ) and the payoff of i does not change from πi. Using this argument for every i ∈ N and using the expression for the Shapley value in Lemma 3, we get the Shapley value rule. It is possible to replace one of the independence axioms with an equity axiom on sharing the transfer of a job. This is shown in Propositions 2 and 3. Proposition 2. Any efficient rule ψ that satisfies ECB, IPJθ, and PRp is a rule implied by the Shapley value rule. Proof. As in the proof of Proposition 1, define θi j = γipj ∀ i, j ∈ N. Assume without loss of generality that σ is an efficient ordering with σi = i ∀ i ∈ N. Consider a queue with jobs in set K = {1, . . . , i, i + 1}, where i < n. Define q = (K, p, θ ), where θj = θi+1 j ∀ j ∈ K. Define σj = σj ∀ j ∈ K. σ is an efficient ordering for q . By ECB and Lemma 4 the cost share of job i + 1 in any allocation rule in ψ must be πi+1 = pi+1θi+1 + 1 2 ¡£j<i+1 pjθi+1¢. Now, consider q = (K, p, θ ) such that θj = θi j ∀ j ≤ i and θi+1 = θi+1. σ remains an efficient ordering in q and by IPJθ the cost share of i + 1 remains πi+1. In q = (K \ {i + 1}, p, θ ), we can calculate the cost share of job i using ECB and Lemma 4 as πi = piθi + 1 2 £j<i pjθi. So, using PRp we get the new cost share of job i in q as πi = πi + ti+1 pi j<i+1 pj = piθi + 1 2 ¡£j<i pjθi + piθi+1¢. Now, we can set K = K ∪ {i + 2}. As before, we can find cost share of i + 2 in this queue as πi+2 = pi+2θi+2 + 1 2 ¡£j<i+2 pjθi+2¢. Using PRp we get the new cost share of job i in the new queue as πi = piθi + 1 2 ¡£j<i pjθi + piθi+1 + piθi+2¢. This process can be repeated till we add job n at which point cost share of i is piθi + 1 2 ¡£j<i pjθi + £j>i piθj¢. Then, we can adjust the θ of preceding jobs of i to their original value and applying IPJθ, the payoffs of jobs i through n will not change. This gives us the Shapley values of jobs i through n. Setting i = 1, we get cost shares of all the jobs from ψ as the Shapley value. Proposition 3. Any efficient rule ψ that satisfies ECB, IFJp, and PRθ is a rule implied by the Shapley value rule. Proof. The proof mirrors the proof of Proposition 2. We provide a short sketch. Analogous to the proof of Proposition 2, θs are kept equal to original data and processing times are initialized to pi+1 j . This allows us to use IFJp. Also, contrast to Proposition 2, we consider K = {i, i + 1, . . . , n} and repeatedly add jobs to the beginning of the queue maintaining the same efficient ordering. So, we add the cost components of preceding jobs to the cost share of jobs in each iteration and converge to the Shapley value rule. The next proposition shows that the Shapley value rule satisfies all the fairness axioms discussed. Proposition 4. The Shapley value rule satisfies efficiency, pareto indifference, anonymity, ETE, ECB, IPJθ, IFJp, PRp, and PRθ. Proof. The Shapley value rule chooses an efficient ordering and by definition the payments add upto zero. So, it satisfies efficiency. The Shapley value assigns same cost share to a job irrespective of the efficient ordering chosen. So, it is pareto indifferent. The Shapley value is anonymous because the particular index of a job does not effect his ordering or cost share. For ETE, consider two jobs i, j ∈ N such that pi = pj and θi = θj. Without loss of generality assume the efficient ordering to be 1, . . . , i, . . . , j, . . . , n. Now, the Shapley value of job i is 236 SVi = piθi + 1 2 ¡Li + Ri¢(From Lemma 3) = pjθj + 1 2 ¡Lj + Rj¢− 1 2 ¡Li − Lj + Ri − Rj¢ = SVj − 1 2 ¡ i<k≤j piθk − i≤k<j pkθi¢ = SVj − 1 2 i<k≤j (piθk − pkθi) (Using pi = pj and θi = θj) = SVj (Using θk pk = θi pi for all i ≤ k ≤ j). The Shapley value satisfies ECB by its expression in Lemma 3. Consider any job i, in an efficient ordering σ, if we increase the value of γj for some j = i such that σj > σi, then the set Pi ( preceding jobs) does not change in the new efficient ordering. If γj is changed such that pj remains the same, then the expression £j∈Pi θipj is unchanged. If (p, θ) values of no other jobs are changed, then the Shapley value is unchanged by increasing γj for some j ∈ Pi while keeping pj unchanged. Thus, the Shapley value rule satisfies IPJθ. An analogous argument shows that the Shapley value rule satisfies IFJp. For PRp, assume without loss of generality that jobs are ordered 1, . . . , n in an efficient ordering. Denote the transfer of job i = n due to the Shapley value with set of jobs N and set of jobs N \ {n} as ti and ti respectively. Transfer of last job is tn = 1 2 θn £j<n pj. Now, ti = 1 2 ¡θi j<i pj − pi j>i θj¢ = 1 2 ¡θi j<i pj − pi j>i:j=n θj¢− 1 2 piθn = ti − 1 2 θn j<n pj pi £j<n pj = ti − tn pi £j<n pj . A similar argument shows that the Shapley value rule satisfies PRθ. These series of propositions lead us to our main result. Theorem 1. Let ψ be an allocation rule. The following statements are equivalent: 1) For each q ∈ Q, ψ(q) selects all the allocation assigning jobs cost shares implied by the Shapley value. 2) ψ satisfies efficiency, ECB, IFJp, and IPJθ. 3) ψ satisfies efficiency, ECB, IFJp, and PRθ. 4) ψ satisfies efficiency, ECB, PRp, and IPJθ. Proof. The proof follows from Propositions 1, 2, 3, and 4. 5. DISCUSSIONS 5.1 A Reasonable Class of Cost Sharing Mechanisms In this section, we will define a reasonable class of cost sharing mechanisms. We will show how these reasonable mechanisms lead to the Shapley value mechanism. Definition 10. An allocation rule ψ is reasonable if for all q ∈ Q and (σ, t) ∈ ψ(q) we have for all i ∈ N, ti = α ¡θi j∈Pi(σ) pj − pi j∈Fi(σ) θj¢∀ i ∈ N, where 0 ≤ α ≤ 1. The reasonable cost sharing mechanism says that every job should be paid a constant fraction of the difference between the waiting cost he incurs and the waiting cost he inflicts on other jobs. If α = 0, then every job bears its own cost. If α = 1, then every job gets compensated for its waiting cost but compensates others for the cost he inflicts on others. The Shapley value rule comes as a result of ETE as shown in the following proposition. Proposition 5. Any efficient and reasonable allocation rule ψ that satisfies ETE is a rule implied by the Shapley value rule. Proof. Consider a q ∈ Q in which pi = pj and θi = θj. Let (σ, t) ∈ ψ(q) and π be the resulting cost shares. From ETE, we get, πi = πj ⇒ ci(σ) − ti = cj(σ) − tj ⇒ piθi + (1 − α)Li + αRi = pjθj + (1 − α)Lj + αRj (Since ψ is efficient and reasonable) ⇒ (1 − α)(Li − Lj) = α(Rj − Ri) (Using pi = pj, θi = θj) ⇒ 1 − α = α (Using Li − Lj = Rj − Ri = 0) ⇒ α = 1 2 . This gives us the Shapley value rule by Lemma 3. 5.2 Results on Envy Chun [2] discusses a fariness condition called no-envy for the case when processing times of all jobs are unity. Definition 11. An allocation rule satisfies no-envy if for all q ∈ Q, (σ, t) ∈ ψ(q), and i, j ∈ N, we have πi ≤ ci(σij ) − tj, where π is the cost share from allocation rule (σ, t) and σij is the ordering obtaining by swapping i and j. From the result in [2], the Shapley value rule does not satisfy no-envy in our model also. To overcome this, Chun [2] introduces the notion of adjusted no-envy, which he shows is satisfied in the Shapley value rule when processing times of all jobs are unity. Here, we show that adjusted envy continues to hold in the Shapley value rule in our model (when processing times need not be unity). As before denote σij be an ordering where the position of i and j is swapped from an ordering σ. For adjusted noenvy, if (σ, t) is an allocation for some q ∈ Q, let tij be the 237 transfer of job i when the transfer of i is calculated with respect to ordering σij . Observe that an allocation may not allow for calculation of tij . For example, if ψ is efficient, then tij cannot be calculated if σij is also not efficient. For simplicity, we state the definition of adjusted no-envy to apply to all such rules. Definition 12. An allocation rule satisfies adjusted noenvy if for all q ∈ Q, (σ, t) ∈ ψ(q), and i, j ∈ N, we have πi ≤ ci(σij ) − tij i . Proposition 6. The Shapley value rule satisfies adjusted no-envy. Proof. Without loss of generality, assume efficient ordering of jobs is: 1, . . . , n. Consider two jobs i and i + k. From Lemma 3, SVi = piθi + 1 2 ¡ j<i θipj + j>i θjpi¢. Let ˆπi be the cost share of i due to adjusted transfer tii+k i in the ordering σii+k . ˆπi = ci(σii+k ) − tii+k i = piθi + 1 2 ¡ j<i θipj + θipi+k + i<j<i+k θipj + j>i θjpi − θi+kpi − i<j<i+k θjpi¢ = SVi + 1 2 i<j≤i+k ¡θipj − θjpi¢ ≥ SVi (Using the fact that θi pi ≥ θj pj for i < j). 6. CONCLUSION We studied the problem of sharing costs for a job scheduling problem on a single server, when jobs have processing times and unit time waiting costs. We took a cooperative game theory approach and show that the famous the Shapley value rule satisfies many nice fairness properties. We characterized the Shapley value rule using different intuitive fairness axioms. In future, we plan to further simplify some of the fairness axioms. Some initial simplifications already appear in [16], where we provide an alternative axiom to ECB and also discuss the implication of transfers between jobs (in stead of transfers from jobs to a central server). We also plan to 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. 7. REFERENCES [1] Youngsub Chun. A Note on Maniquet"s Characterization of the Shapley Value in Queueing Problems. Working Paper, Rochester University, 2004. [2] Youngsub Chun. No-envy in Queuing Problems. Working Paper, Rochester University, 2004. [3] Imma Curiel, Herbert Hamers, and Flip Klijn. Sequencing Games: A Survey. In Peter Borm and Hans Peters, editors, Chapter in Game Theory. Theory and Decision Library, Kulwer Academic Publishers, 2002. [4] Imma Curiel, Giorgio Pederzoli, and Stef Tijs. Sequencing Games. European Journal of Operational Research, 40:344-351, 1989. [5] Imma Curiel, Jos Potters, Rajendra Prasad, Stef Tijs, and Bart Veltman. Sequencing and Cooperation. Operations Research, 42(3):566-568, May-June 1994. [6] Nikhil R. Devanur, Milena Mihail, and Vijay V. Vazirani. Strategyproof Cost-sharing Mechanisms for Set Cover and Facility Location Games. In Proceedings of Fourth Annual ACM Conferece on Electronic Commerce, 2003. [7] Robert J. Dolan. Incentive Mechanisms for Priority Queueing Problems. Bell Journal of Economics, 9:421-436, 1978. [8] Joan Feigenbaum, Christos Papadimitriou, and Scott Shenker. Sharing the Cost of Multicast Transmissions. In Proceedings of Thirty-Second Annual ACM Symposium on Theory of Computing, 2000. [9] Herbert Hamers, Jeroen Suijs, Stef Tijs, and Peter Borm. The Split Core for Sequencing Games. Games and Economic Behavior, 15:165-176, 1996. [10] John C. Harsanyi. Contributions to Theory of Games IV, chapter A Bargaining Model for Cooperative n-person Games. Princeton University Press, 1959. Editors: A. W. Tucker, R. D. Luce. [11] Kamal Jain and Vijay Vazirani. Applications of Approximate Algorithms to Cooperative Games. In Proceedings of 33rd Symposium on Theory of Computing (STOC "01), 2001. [12] Kamal Jain and Vijay Vazirani. Equitable Cost Allocations via Primal-Dual Type Algorithms. In Proceedings of 34th Symposium on Theory of Computing (STOC "02), 2002. [13] Flip Klijn and Estela S´anchez. Sequencing Games without a Completely Specified Initial Order. Report in Statistics and Operations Research, pages 1-17, 2002. Report 02-04. [14] Flip Klijn and Estela S´anchez. Sequencing Games without Initial Order. Working Paper, Universitat Aut´onoma de Barcelona, July 2004. [15] Franois Maniquet. A Characterization of the Shapley Value in Queueing Problems. Journal of Economic Theory, 109:90-103, 2003. [16] Debasis Mishra and Bharath Rangarajan. Cost sharing in a job scheduling problem. Working Paper, CORE, 2005. [17] Manipushpak Mitra. Essays on First Best Implementable Incentive Problems. Ph.D. Thesis, Indian Statistical Institute, New Delhi, 2000. [18] Manipushpak Mitra. Mechanism design in queueing problems. Economic Theory, 17(2):277-305, 2001. [19] Manipushpak Mitra. Achieving the first best in sequencing problems. Review of Economic Design, 7:75-91, 2002. [20] Herv´e Moulin. Handbook of Social Choice and Welfare, chapter Axiomatic Cost and Surplus Sharing. North-Holland, 2002. Publishers: Arrow, Sen, Suzumura. [21] Herv´e Moulin. On Scheduling Fees to Prevent 238 Merging, Splitting and Transferring of Jobs. Working Paper, Rice University, 2004. [22] Herv´e Moulin. Split-proof Probabilistic Scheduling. Working Paper, Rice University, 2004. [23] Herv´e Moulin and Rakesh Vohra. Characterization of Additive Cost Sharing Methods. Economic Letters, 80:399-407, 2003. [24] Martin P´al and ´Eva Tardos. Group Strategyproof Mechanisms via Primal-Dual Algorithms. In Proceedings of the 44th Annual IEEE Symposium on the Foundations of Computer Science (FOCS "03), 2003. [25] Lloyd S. Shapley. Contributions to the Theory of Games II, chapter A Value for n-person Games, pages 307-317. Annals of Mathematics Studies, 1953. Ediors: H. W. Kuhn, A. W. Tucker. [26] Wayne E. Smith. Various Optimizers for Single-Stage Production. Naval Research Logistics Quarterly, 3:59-66, 1956. [27] Jeroen Suijs. On incentive compatibility and budget balancedness in public decision making. Economic Design, 2, 2002. 239
cost sharing job scheduling shapley value fairness axiom queueing problem cooperative game theory approach unit waiting cost processing time allocation rule expected cost bound cost share
monetary transfer agent queue problem job schedule