|
Article Excerpt
A deterministic server is shared by users with identical linear waiting costs, requesting jobs of arbitrary lengths. Shortest jobs are served first for efficiency. The server can monitor the length of a job but not the identity of the job's user, thus merging, splitting, or partially transferring jobs offer cooperative strategic opportunities. Can we design cash transfers to neutralize such manipulations? We prove that mergeproofness and splitproofness are not compatible, and that it is similarly impossible to prevent all transfers of jobs involving three or more agents. On the other hand, robustness against pairwise transfers is feasible and essentially characterizes a one-dimensional set of scheduling methods. This line is borne by two outstanding methods: the merge-proof [S.sup.+] and the split-proof [S.sup.-]. Splitproofness, unlike mergeproofness, is not compatible with several simple tests of equity. Thus, the two properties are far from equally demanding.
Key words: scheduling; queuing; merging; splitting; transferring; linear waiting cost
1. The problem and the punch lines. Dividing the burden of joint externalities raises many issues of incentive compatibility. One of these issues is strategic transferring, merging, or splitting of certain private characteristics of the participants. This type of manipulation is discussed in the fair division literature (see details in [section] 2); here we study it in a simple scheduling problem with transferable utility.
A single deterministic server/machine is shared by users with linear waiting costs, requesting jobs of arbitrary lengths. A job of size [x.sub.i] takes [x.sub.i] units of time to process; an agent's disutility is the waiting time until her job is completed, augmented by a (positive or negative) cash payment selected by the mechanism. The key assumption is that the server can monitor the size of a job but not the identity of the job's user. This creates opportunities for manipulation if two agents i, j can costlessly merge two jobs of sizes [x.sub.i], [x.sub.j] into a single job of size [x.sub.i] + [x.sub.j], reporting to the server under one of the agents names; or if agent i can split his job of size [x.sub.i] into two smaller jobs [x.sup.1.sub.i], [x.sup.2.sub.i] with [x.sup.1.sub.i] + [x.sup.2.sub.i] = [x.sub.i], then request service under two aliases; or, finally, if agent i can transfer a fraction of his job and add it to agent j's job.
The key assumption is realistic when the usage of the server/machine is private and cannot be traced to its actual beneficiary. Think of a tool that agents carry to their private workstation--for instance, a software used on a private machine. Protecting the privacy of the users is often a design constraint, e.g., when they share a single link (access point to a database or phone line). The needs of each user of the link must remain unknown to the server, who cannot detect if and when the link is used by agent i on behalf of agent j. Two more factors affect the feasibility of the strategic maneuvers in question. First, assuming a false identity should be easy, as is the case in huge networks such as the Internet, where protecting the system performance against aliases is an important issue: Douceur [8]. The second factor is the cost of merging, splitting, or transferring jobs: the cost is minimal if the job produces an electronic document, or uses a physical tool easily transported from one job to the next.
Given identical linear waiting costs and the feasibility of cash transfers, efficiency requires that the shortest jobs be served first. Suppose the server does this and performs no monetary transfers (at least when the efficient scheduling order is unique, i.e., all jobs are of different size). This mechanism is highly vulnerable to splitting: given two real jobs [x.sub.1] = 4, [x.sub.2] = 3, Agent 1 can split his job as [x'.sub.1] = [x''.sub.1] = 2 and cut his waiting time by three. Partial transfers may also work: say we have three jobs ([x'.sub.1], [x.sub.2], [x'.sub.3]) = (1, 4, 5); if Agent 3 transfers two units of her job to Agent 1, resulting in ([x'.sub.1], [x.sub.2], [x'.sub.3]) = (3, 4, 3), she will complete [x.sub.3] before Agent 2 is served, and the net gain $4 can be divided between Agents 1 and 3 (we assume a cost of $1 per unit of time). The merging of jobs can only delay their completion, however, hence is not profitable.
Consider next a mechanism serving the longest jobs first, thus maximizing total waiting cost. No matter how it deals with ties, this mechanism is badly vulnerable to merging, as well as to partial transfers: simply use the above examples backward. Nevertheless, the splitting of a job is never profitable.
Can we design a system of cash transfers to prevent in all problems single agents from splitting their jobs, and coalitions from merging them under a single identity? And what about partial transfers of jobs?
Despite the simplicity of our scheduling model, some of the answers to these questions are disappointingly negative. Theorem 4.1 in [section] 4 contains two such statements. If the set of potential users contains at least five agents, a mechanism treating equals equally cannot be both merge proof and split proof. A continuous mechanism (i.e., net waiting costs depend continuously upon the profile of job sizes) cannot be both merge proof and split proof; it is also vulnerable to transfers involving three agents or more (see [section] 8).
On the positive side, we show that the family of merge-proof scheduling mechanisms is fairly large, as is that of split-proof mechanisms: each family contains many efficient mechanisms. We also find that splitproofness, unlike mergeproofness, comes at a high normative cost: it is incompatible with several compelling fairness requirements. Proposition 5.1 in [section] 5 gives a precise content to this statement. We restrict attention to efficient mechanisms (serving successively jobs of increasing size) treating equals equally, and continuous. Then every split-proof mechanism must charge a substantial positive fee to vanishingly small jobs, who create no externality; it must subsidize some jobs in the sense that their net waiting cost is smaller than their size [x.sub.i]; the net cost of agent i cannot be weakly increasing in [x.sub.i]; the ordering of net costs must sometime contradict that of job lengths; and finally the net waiting cost of a given job is unbounded when other jobs become arbitrarily large. By contrast, mergeproofness is compatible with all properties just described.
In [section] 6, we construct a large family of efficient continuous scheduling mechanisms, treating equals equally, and for which the role of mergeproofness and splitproofness is especially easy to describe. Pick a continuous function [theta] from [R.sup.2.sub.+] into R such that [theta](a, b) + [theta](b, a) = min{a, b} for all a, b. Label the set of users N = {1, 2, ..., n} in such a way that [x.sub.1] [less than or equal to] [x.sub.2] [less than or equal to] ... [less than or equal to] [x.sub.n]. The [theta]-mechanism serves the job in the efficient order 1, 2, ..., n and performs cash transfers resulting in the net waiting cost [y.sub.i] = [x.sub.i] + [[summation].sub.j [not equal to] i] [theta]([x.sub.i], [x.sub.j]) for all i. By construction of [theta], this implies [[summation].sub.i][y.sub.i] = n[x.sub.1] + (n - 1)[x.sub.2] + ... + [x.sub.n], so these transfers are balanced.
We call the above mechanism separable because it divides the externality min{[x.sub.i], [x.sub.j]} between agents i, j independent of other job lengths. Proposition 6.1 in [section] 6 characterizes merge-proof separable methods by a system of inequalities (4) slightly less demanding than the superadditivity of [theta] in its first variable, and split-proof separable methods by a similar system (5) slightly more demanding than the subadditivity of [theta] in its first variable.
Two separable mechanisms stand out. The first one, called [S.sup.+], splits the (i, j)-externality equally, namely [[theta].sup.+](a, b) = (1/2) min{a, b}. The second mechanism, called [S.sup.-], uses the function [[theta].sup.-](a, b) = b - (1/2) max{a, b}. The method [S.sup.+] corresponds to the Shapley value of the optimistic stand-alone cooperative game (a coalition S standing alone is served before N/S); the method [S.sup.-] to the Shapley value of the pessimistic stand-alone cooperative game (a coalition S standing alone is served after N/S).
We find that [S.sup.+] is merge proof, whereas [S.sup.-] is split proof--hence the latter shares all unpalatable consequences of splitproofness discussed above.
In [section] 7, we give a characterization result in which the main requirement is immunity to strategic transfer of jobs involving only two agents, combined with cash transfers within a coalition of arbitrary size (recall that strategic transfers among three or more agents are inevitable). We call this property pairwise transfer-proofness. The mechanisms [S.sup.+], [S.sup.-] as well as their affine combinations y = a x [y.sup.+] + (1 - a) x [y.sup.-], a [member of] R, meet this property. Theorem 7.1 characterizes this one-dimensional family of methods. A corollary characterizes the [S.sup.+] mechanism by requiring either that null jobs pay nothing, or that the optimistic stand-alone wait be a lower bound on the net cost ([x.sub.i] [less than or equal to] [y.sub.i]).
2. Related literature. In the fair division literature, the earliest discussion of manipulation by merging, splitting, and transferring is in the rationing problem, where the sum of individual claims exceeds the available cash. Dividing the money in proportion to individual claims is the only method invulnerable to transfers, as well as to merging or splitting of claims: Banker [2]. Extensions of this result are in Moulin [24], de Frutos [6], and Ju [13]. The transfer-proofness property appears in the quasilinear social choice problem (Moulin [23], Ermolov [9], Chun [3]), in axiomatic cost sharing (Sprumont [30]), and more: Miyagawa et al. [22] offer a unified treatment of most of this literature.
We now review the recent and growing microeconomic literature on scheduling. A familiar extension of our model allows linear waiting costs to vary across participants. A scheduling problem consists of a profile of job sizes [x.sub.i] and waiting costs [[delta].sub.i] per unit of time. Agent i's disutility is [[delta].sub.i][w.sub.i] + [t.sub.i], where [w.sub.i] is waiting time until completion of job i and [t.sub.i] is the cash payment. Minimizing total waiting cost requires that the server processes the jobs in the increasing order of the ratios [x.sub.i]/[[delta].sub.i] (Smith [29]).
The mechanism designer can use the cash transfers to ensure truthful (dominant strategy) elicitation of the privately known waiting costs: utilities are linear in money, therefore Vickrey-Clarke-Groves mechanisms can be readily applied: (Dolan [7], Mendelson and Whang [19]). Given linear waiting costs, we can choose a budget-balanced (fully efficient) VCG mechanism: Suijs [31], Mitra [20, 21]. If we elicit job lengths instead of waiting costs, a similar construction is possible (Hain and Mitra [11], Kittsteiner and Moldovanu [15, 16]), provided the VCG mechanisms are suitably generalized to take into account the more complicated allocative externalities from misreporting the size of one's job.
In our model, individual preferences are known to the server, and job size is observable. All the action comes from the inability of the server to detect the true identity of users, and the users' ability to request a job, or part of a job, without revealing the job's true beneficiary.
Cash transfers are also a simple tool to achieve fairness, namely an equitable sharing of the congestion externality. For the scheduling problem with linear waiting costs, several authors simply apply off-the-shelf solution concepts such as the Shapley value or the core to a relevant cooperative game: Pederzoli et al. [27], Potters et al. [28], Hamers et al. [12], Suijs et al. [32]. The most popular solution is the Shapley value of the optimistic stand-alone cooperative game: Potters et al. [28] and Klijn and Sanchez [17]. It plays an important role in the current paper as solution [S.sup.+]. In the case of identical job sizes, this solution is axiomatized by Maniquet [18], while Katta and Sethuraman [14] suggest alternative interpretations of fairness. The Shapley value of the pessimistic stand-alone game corresponds to our second solution [S.sup.-]. With identical job sizes it is axiomatized by Chun [5]. Chun [4] allows for variable job sizes, extends both solutions to this context, and offers parallel characterizations.
The companion paper Moulin [25] discusses the same strategic maneuvers when the server, instead of cash transfers, uses randomization. In that context, efficiency places no restriction on the sequencing of jobs. Splitproofness remains a more demanding property than mergeproofness, yet these two properties are now compatible. A certain probabilistic scheduling rule, the Proportional rule, is characterized by the combination of mergeproofness, splitproofness, and a couple of natural properties of invariance and fairness.
3. The model. The set N contains all potential users of the simple machine. It may be finite or infinite. A scheduling problem involves a finite subset N of N. Agent i's job is completed in exactly [x.sub.i] units of machine time. We always assume [x.sub.i] > 0. Given a scheduling problem (N, x), where x [member of] [R.sup.N.sub.++], the server must choose the ordering [sigma] of N--the sequence--in which the jobs will be processed, and a vector t [member of] [R.sup.N] of monetary transfers such that [[summation].sub.N] [t.sub.i] = 0.
Each agent incurs a waiting cost of $1 per unit of time until completion of his job (a partially completed...
|
