A Characterization of n-Player Strongly Monotone Scheduling Mechanisms

1 Introduction

Using the power of crowdsourcing and cloud computing to compute complicated tasks that consist of multiple sub-tasks is a major challenge in multi-agent systems. When assigning the tasks to different agents/cloud providers, we have to provide the agents with the right incentives to truthfully report the times they need to complete the tasks, and execute the tasks that are assigned to them.

Combinatorial auctions constitute another important class of problems. Here multiple items are auctioned simultaneously, and we need to motivate the agents to report their true valuations for the items. Can we characterize all allocation algorithms that are truthful for these two settings?

Fifteen years ago Nisan and Ronen posed their famous - still open- question about the approximability of the optimum makespan in unrelated machine scheduling by truthful scheduling mechanisms [Nisan and Ronen, 2001]. In this strategic version of the unrelated machines problem, we are given n machines and m tasks, and the machines are owned by selfish agents, each of them holding the vector

∗Work supported by the French National Research Agency through the ANR project CoCoRICo-CoDec, ANR-number DS0805.

1 The (normalized) payments are uniquely determined by the allocation function of the mechanism; thus the assumptions concern properties of the allocation.

Angelina Vidali

Pierre and Marie Curie University, UPMC-LIP6, France. Angelina.Vidali@lip6.fr

ti = (tij)mj=1 of running times (costs) on his machine i as private information. A scheduling mechanism consists of an allocation algorithm, and a payment scheme (p1, . . . , pn). Having received the bid vectors t′i for the costs from the respective agents, the matrix t′ is used as input of the allocation algorithm, and the payments to each agent are calculated according to the payment scheme. The utility of player i is then pi - costi, where costi is defined as the total running time of the received jobs on machine i, i.e., the finish time of the machine. Note that for each player, the costs incurred from the different tasks are additive. A similar problem to unrelated scheduling is that of combinatorial auctions (CAs) with additive bidder valuations: we get a model equivalent to additive CAs by assuming negative values of tij, and leaving the scheduling model unchanged otherwise.

We are interested in truthful mechanisms, where bidding t′i = ti is a dominant strategy for every agent. It is well known that weak monotonicity (WMON) of the allocation function is necessary and sufficient for truthful implementability (see [Saks and Yu, 2005; Archer and Kleinberg, 2008]). Thus, the problem boils down to searching for monotone allocation algorithms for unrelated scheduling.

Nisan and Ronen conjectured that no mechanism can yield an approximation of the makespan by a factor smaller than min(n,m), the approximation ratio of the VCG mechanism, that gives each task to the player bidding the smallest cost for that task. The attempts to prove lower bounds based merely on monotonicity, have only given small constants as lower bounds [Christodoulou et al., 2007; Koutsoupias and Vidali, 2007; Mu'alem and Schapira, 2007]. 2 Narrowing the gap between the constant factor lower bound and the upper bound n became a paradigmatic problem of algorithmic mechanism design, and directed much attention to mechanisms with additive bidder valuations in general (see, eg., [Lavi, 2007]).

While monotonicity characterized truthful mechanisms well in the (single-parameter) related machines case (see [Epstein et al., 2013] and references therein), it is much more difficult to exploit it in multi-parameter settings like unrelated scheduling. A different approach is to improve our understanding by investigating the global structure of WMON allocations. To this end we strive for global, closed form characterizations. Even though it seems extremely hard to provide a complete characterization for the original problem, attempts to characterize restricted, in some way purified classes of WMON mechanisms prove to be very useful: they develop insight, while new types of allocations might be discovered along the way.

2 A lower bound n has been established adding the anonymity assumption [Ashlagi et al., 2012].

In this paper we assume strong monotonicity (SMON), a condition that parallels Arrow's Independence of Irrelevant Alternatives (IIA) condition, and which is the strict version of the WMON property (see Definition 3). 3 We completely characterize SMON mechanisms for two tasks, and at the same time identify a new class of monotone allocations.

Related work. Characterizations by weak monotonicity [Myerson, 1981; Saks and Yu, 2005; Gui et al., 2005; Archer and Kleinberg, 2008; Frongillo and Kash, 2012], and cycle monotonicity [Rochet, 1987] describe truthfully implementable allocations in a local fashion. Complete characterizations, of implementable allocations describe them in a global fashion. The most important result of this type is due to Roberts who showed that for unrestricted domains the only implementable social choice rules are affine maximizers [Roberts, 1979], a generalization of VCG mechanisms. However, the requirement of unrestricted valuations does not apply to most of the realistic setups with richer structure.

Characterizations for domains with high economic importance like combinatorial auctions or the scheduling domain seem very hard to obtain, even with additional restrictions. The characterizations we know for the case of n players, either concern domains where SMON can be assumed without loss of generality [Roberts, 1979; Papadimitriou et al., 2008], or put additional restrictions [Lavi et al., 2003; 2009; Dobzinski and Nisan, 2011; Christodoulou and Kov´acs, 2011]. The only complete characterization results for additive bidders in the multi-parameter setting are for two players [Dobzinski and Sundararajan, 2008; Christodoulou et al., 2008]. These characterizations involve affine minimizers, or threshold mechanisms, or a combination of these. 4 We define these allocation rules next.

Definition 1 (affine minimizer). An allocation function A is an affine minimizer if there exist positive multiplicative constants λi for each player i, and additive constants ca one for each allocation a, such that for every input matrix t = {tij}n×m the allocation A(t) = {aij}n×m minimizes ∑ni=1 ∑mj=1 λi · aij · tij + ca (where aij is 1 if player i gets task j and 0 otherwise).

Threshold allocations are exactly those that admit additive payment functions over the received tasks/items [Vidali, 2009]. Restricted to SMON mechanisms, they coincide (assuming proper tie-breaking) with task-independent mechanisms, that allocate each task by an arbitrary monotone single item allocation. These single item mechanisms were characterized as virtual utility maximizers in [Mishra and Quadir, 2012].

3 It is known [Mu'alem and Schapira, 2007] that SMON mechanims can only approximate the makespan by factor min(m, n).

4 Affine maximizers become affine minimizers in scheduling.

Our contribution. 1. We identify a so far unknown monotone allocation rule generalizing affine minimizers, that we call player-grouping minimizer. A player-grouping minimizer partitions the set of players, and always allocates all tasks within one subset of the partition (called group) by some affine minimizer. Between any two groups of players, preferences are decided by minimizing arbitrary fixed increasing functions of the objective values of the groups:

Definition 2 (player-grouping minimizer). Let {Ng}rg=1 be a partition of the set of players into r groups, with at least two players in each group. For each 1 ≤ g ≤ r let Φg : (-∞, Cg) → R be an increasing continuous bijection 5 and Ag be an affine minimizer over the players of group g. Within each group the affine minimizer Ag decides, which players (would) receive the tasks in that group. For given bids ti of the players in group g, let Optg denote the objective value of Ag.6 Group s receives all the tasks, allocated according to As, if Φs(Opts) = ming Φg(Optg) (assuming some consistent tie-breaking rule).

Example 1. The allocation for n = 4 and m = 2, that gives the tasks to the players who provide the minimum of the expressions t11+t12, t11+5t22, 5t21+t12, 5t21+5t22, and (t31 + t32 + 3)3 , (t31 + t42)3 , (t41 + t32 - 1)3 , (t41 + t42)3 is a grouping minimizer. (If ties are broken by a fixed order of these eight possible allocations, then it is an SMON grouping minimizer.) Note that here players 1 and 2 form group N1, in the respective affine minimizer λ2 = 5 and the additive constants ca are zero; the Φ1 function for this group is the identity function Φ1(x) = x. Another group N2 consists of players 3 and 4. The corresponding affine minimizer has multiplicative constants λ = 1, and additive constants 3, 0, -1 and 0 depending on the allocation within these two players; moreover, Φ2(x) = x3 .

2. We characterize SMON mechanisms for two tasks or items as either task-independent mechanisms or player-grouping minimizers:

Theorem 1. Every continuous decisive SMON mechanism for allocating two tasks or items, with additive bidder valuations and tij ∈ R, is either a task-independent mechanism, or a grouping minimizer (if the grouping minimizer is onto 7 , then it is an affine minimizer).

Since monotone allocations for two players are essentially SMON (with an appropriate tie-breaking rule), for two tasks our result generalizes the 2-player characterization in [Christodoulou et al., 2008]. Moreover, grouping minimizers are very similar to virtual utility maximizers for a single item [Mishra and Quadir, 2012].

3. We derive a key lemma (Lemma 2) that turns out to be of 'universal' use for the SMON problem. For fixed bids t-i, of all other players, the allocations to a single player i depending on his own 2-dimensional bid vector ti, partition the bid-space according to one of the shapes in Figure 1 (due to the WMON property). The positions of the boundary lines in these figures correspond to the (differences of the) payments to player i for the different allocations. We investigate these boundary positions (i.e. the truthful payments), as functions of the other players' bids. 8 For SMON mechanisms, Lemma 2 implies the linearity of these payment functions in 'most' cases. We prove that linearity of all boundary functions results in the mechanism being an affine minimizer. The only exceptions where linearity needs not hold, imply either a task independent mechanism or a boundary between different player-groups in a grouping minimizer (see Figures 2 and 3).

5 The Cg ∈ R ∪ {+∞} with Cg being +∞ for at least one g; this is needed for the tasks to be always allocated.

6Optg = minag ∑i ∑j λitijagij + cag , where allocations ag give all tasks to group g.

7 I.e. every allocation occurs for at least one input t.

Our technical assumptions are decisiveness, continuity of the payment functions, and that the costs tij can take arbitrary real values. 9 For a discussion on these, and some examples of degenerate allocation rules, see the full version 10 .

Preliminaries. The following notation and observations apply to any number of tasks. Since we treat the two-tasks case in the paper, we will illustrate these notions for m = 2. For a more detailed treatment see, e.g., [Christodoulou et al., 2008; Vidali, 2009].

An allocation matrix is a = (a1, a2, . . . , an), where ak is the binary allocation vector of player k. We also use α, α′ . . . etc. to denote m-dimensional allocation vectors (for two tasks, α, ak ∈ {(00), (01), (10), (11)}). For two tasks, aik denotes the allocation giving the first task to player i and the second to player k (mind the difference to aij , which is a single bit). The bid matrix of all players except for player k, is denoted by t-k, whereas t-ik denotes the bid matrix of all players except for players i and k. For fixed t-k, the allocation regions Rkα = {tk | ak(tk, t-k) = α} ⊂ Rm for all possible α, partition the bid space Rm of player k in 2m parts.

Definition 3. An allocation function A satisfies SMON (WMON) if A(tk, t-k) = a, and A(t′k , t-k) = a′ , where a ̸= a′ , imply (ak - a′k )(tk - t′k ) < 0 (≤ 0).

For WMON allocations the allocation regions of any player must have a special geometric shape: the boundary between any two regions Rkα and Rkα′ (if it exists) is part of the hyperplane (α-α′ ) · tk = f k α:α′ , where the functions f k α:α′ , that determine these boundary positions are defined as follows: In a truthful mechanism, the payment of player k depends on t-k and on ak. Let pkak (t-k) denote this payment. Then

8 Truthful normalized payments are uniquely determined by the allocation function and by t-i.

9 Note that similar assumptions are made in [Dobzinski and Nisan, 2011; Dobzinski and Sundararajan, 2008; Christodoulou et al., 2008; Mishra and Quadir, 2012].

10 Full version of the paper: https://infotomb.com//eeevx

In general, for some t-k some of the allocation areas Rα might be empty. We make the assumption that the allocation figures are complete (all the 2m regions are always nonempty), i.e., the allocation is decisive:

Definition 4. An allocation function A is decisive, if every player k, for every fixed bids t-k of the other players and every particular allocation α ∈ {0, 1}m has bids tk so that A allocates him exactly the items in α.

Thus, for WMON allocations of two tasks, the allocation of player k as a function of (tk1, tk2) has a geometrical representation of one of three possible shapes (see Figure 1). For given fixed t-k, we call this geometric representation the (allocation) figure of player k.

In Section 2.1 we investigate how the positions f k α:α′ of a player's boundaries change as a function of t-k. We will show that this change is linear in t-k with only a few exceptions. For fixed t-ik the boundary f k α:α′ is a function of the bid ti. We assume the continuity of f k α:α′(ti) for any fixed t-ik. Most of the time, w.l.o.g. we consider the figure and boundaries of the first player. In this case, for k = 1, we omit the superscript in f k ,Rk , etc.

In the rest of the section we summarize further implications of the SMON property, the strict version of WMON. See the full version for omitted proofs. If an allocation rule A(t) is SMON, then the allocation of all players is constant in the interior of any region Rkα (otherwise, changing tk would result in changing a to a′ , with ak = a′k , contradicting SMON). We denote by f k a:a′(t-k) the boundary between allocations a, a′ (these describe the allocation of all players, not just of player k) for every t-k for which such a boundary exists in the figure of player k. Next we state a crucial elementary property of continuous SMON mechanisms:

(⋆) For fixed bids of the other players, the boundary f k a:a′ in the allocation figure of player k, considered as a function of the bids ti of any particular player i ̸= k depends only on (a′i - ai) · ti (= ∑mj=1 (a′ij - aij)tij), by some strictly increasing continuous function. If a′i = ai then the boundary position is independent of ti.

For example, let a = (11, 00, 00), and a′ = (01, 10, 00), and t3 be fixed; then fa:a′(t2) = ϕ(t21), for a nondecreasing real function ϕ. Similarly, if a = (10, 01, 00) and a′ = (01, 10, 00), then fa:a′ = ψ(t21 - t22) for some nondecreasing function ψ. The property (⋆) is implied by Lemma 1, and Observation 1 below:

Lemma 1. [increasing boundaries] Let t-1i be fixed, and G ⊂ Rm a connected set. Assume that the boundary fa:a′ exists for all ti ∈ G. For every ti, ti ∈ G it holds that if (a′i - ai) · ti < (a′i - ai) · ti, then fa:a′ (ti) ≤ fa:a′ (ti).

Corollary 1. Let S be a subset of the tasks. If aij = a′ij for all j ∈ S, then fa:a′ (ti) = fa:a′ (ti) whenever ti and ti differ only on tasks in S.

For example, let a = (11, 00, 00), and a′ = (01, 10, 00). By the lemma (for i = 2), f11:01 is increasing in t21. The corollary says, that f11:01 is a function of only t21. S consists of task j = 2, because the allocation of this task to player 2 remains the same a22 = a′22 = 0. Consider t2 and t2 bids such that t21 = t21. If f11:01(t2) < f11:01(t′2 ) were the case, then by the lemma, f11:01 would have a jump of at least f11:01(t′2 ) - f11:01(t′2 ) in t21. However, f11:01(t21) is continuous by assumption. We conclude the subsection with a couple of simple observations that hold in the case of continuous boundary functions.

Observation 1. (a) [boundary points] Let t-1 = (ti, t-1i). If t1 is a point on the boundary fa:a′(t-1), where the allocations ai and a′i are different, then for t-i = (t1, t-1i) the bid ti is a point on the boundary f ia:a′ (t-i).

• (b) [inverse boundaries] Let t-1i be fixed. If for some monotone continuous univariate function fa:a′(ti) = ϕ((a′i - ai) · ti), then f ia′ :a (t1) = ϕ-1 ((a1 - a′1 ) · t1).
• (c) [strictly increasing boundaries] Let t-1i be fixed, and G ⊂ Rm a connected set. Assume that the boundary fa:a′ exists for all ti ∈ G. The function fa:a′(ti) is strictly increasing in (a′i - ai) · ti over ti ∈ G.

2 Characterization

In this section we sketch the proof of Theorem 1. The full version contains the detailed proofs. Figures 2 and 3 show the possible allocation figures of player 1, w.r.t. the dependence of boundaries on other players' bids. The player indices marking the four regions indicate the players who get the tasks in the respective region. As an example, consider Figure 2 (1). Here player i gets task 1 in regions R01 and R00; and player j gets task 2 in R00 and R10. By property (⋆), the position f11:01 of the boundary between R11 and R01 is given by an increasing function of ti1, that we denote by F(ti1). Similarly, the horizontal boundary position is determined by an increasing function G(tj2). If the figure has a shape like in Figure 2 (2), then the slanted boundary has the equation t11 - t12 = F (ti1) - G(tj2).

In general, in every allocation figure, task 1 is either given to the same player in R01 and in R00, or to two different players, and similarly for task 2. Accordingly, the boundaries where task 1 changes owner are either only the vertical boundaries (like in types (1) to (6)), or the vertical boundaries and f01:00 where two other players exchange the task among each other. Combining all possibilities for both tasks, we obtain the depicted cases.

Definition 5. We call the allocations in an allocation figure quasi-independent, if the same player receives task 1 in R01 and in R00, and the same (possibly other) player receives task 2 in R10 and in R00.

Figures 2 and 3 show all possible quasi-independent and non quasi-independent allocations, respectively, up to symmetry. Observe that for a particular boundary the (⋆) property only implies that it(s position) is a multivariate function, monotone in each variable. (E.g., in case (6) in Figure 3 f10:00 is some function f(ti1, tj2, tk2).) However, whenever different other boundaries depend on these different variables, it must be the case that the multivariate function is a so called additively separable function as appears in the figure. For instance, in (6), if only ti1 is increased (locally), then only the two vertical boundaries move, and f() as a function of ti1 is necessarily of the form F(ti1) + C(tj2, tk2) for some function F; by similar considerations, G and H functions exist s.t. f = F(ti1) -G(tj2) +H(tk2) +C.

2.1 Local linearity results

The main theorems of this subsection show the linearity of different boundary functions fα:α′(ti). Since taskindependent allocations, that are in general nonlinear, have "crossing" figures (see Figure 1 (b)), it will be important to distinguish two types of allocation figures:

Definition 6. For fixed t-k, the allocation figure of k is crossing, if f k 11:01 = f k 10:00 , and f k 11:10 = f k 01:00 . Otherwise we call the figure non-crossing.

Mechanisms with only crossing allocation figures are taskindependent. The boundary functions fα:α′ of such mechanisms need not be linear, as they indicate the critical values for getting the task in arbitrary monotone single-task allocations. In what follows, we show that if the mechanism is onto, the converse also holds: if the mechanism has an allocation figure (for some k and t-k) that is non-crossing, then all boundary functions of the mechanism must be linear. However, if the mechanism is not onto, that is, certain allocations aij never occur, then even complete (decisive) non-crossing allocation figures might change by non-linear functions. The resulting mechanisms, which we named (player) grouping minimizers, constitute a generalization of affine minimizers. The main reason for enforced linearity of the boundaries is given in the following basic lemma. Namely, whenever these boundaries are additive separable functions of at least two variables, and so are their inverse boundaries (on another player's figure), we encounter a situation that fulfils the conditions of the lemma. For an illustration see Figure 4: α and ϕ are (roughly) inverse functions. The conditions of the lemma imply that if the functions β and ψ are monotone, then for any small enough ∆, the second curve is a parallel translation of the first one both in vertical and in horizontal direction. This is possible only if the curve is a straight line (α and ϕ are linear).

Lemma 2. Assume that for strictly monotone continuous real functions α, β, ϕ, and ψ, for every (x, y, z) ∈ G for an open set G ⊆ R3 , it holds that (y = α(x) + β(z)) ⇔ (x = ϕ(y) + ψ(z).) Moreover, we assume that an open neighborhood of (x, z) pairs exists for which (x, α(x) + β(z), z) ∈ G. Then

• (a) α and ϕ are linear functions;
• (b) α and ϕ are both increasing or both decreasing, and exactly one of β and ψ is increasing;
• (c) if β and ψ are also linear functions with slopes λβ and λψ, then the slopes λa of α and λϕ of ϕ satisfy λα = - λβ λψ , and λϕ = - λψ λβ .

We call a real function ϕ : R → R locally linear in point x, if a δ > 0 exists such that ϕ is linear in the interval (x-δ, x+δ); ϕ is locally non-linear in x, if ϕ is not a linear function in any open neighborhood of x. With the help of Lemma 2, in Theorems 2 and 3 we show the local linearity of the boundary functions of region R11 (F and G) and also of R00 (H) in most cases. The exceptional cases, when linearity in general does not hold, are case (1) for functions F and G, which is the allocation of a task-independent mechanism, and cases (8) and (9) for H which are typical allocations of grouping minimizers. Notice that (8), (9) are exactly the allocation types, where in region R00 the tasks are given only to players who do not get a job in any other region.

Theorem2. If an allocation figure of player 1 is constant (i.e. the allocations of all players in each region are constant) for some connected open set G ⊂ R(n-1)×2 of t-1 values, then the function F (resp. G) is locally linear in every point ti1 (resp. ti2 or tj2) in the projection of G, or case (1) of Figure 2 holds over G.

Proof. We assume an open rectangle T ⊂ G where the conditions hold. Then the result extends to an arbitrary open set G. As an illustration we give a detailed proof of the theorem in case (2) of Figure 2 as example for how to apply Lemma 2 for the linearity of boundary functions.

In case (2), the line of the (slanted) boundary f10:01 is given by the equation t11-t12 = F(ti1)-G(tj2), and it is a boundary between allocations a1j and ai1 . If we fix a boundary point t1, then for this t1 the figure of player i has a boundary f i10:00 = f iai1 :a1j , and ti is a point of this boundary by Observation 1 (b). Moreover, the boundary position for i is a function of the form ti1 = -Gi (t12)+Hi (t11, tj2), for some monotone increasing functions Gi and Hi . For fixed ¯ tj2 holds

and this is valid in some neighborhood of (t11, t12, ti1), since it is valid on t-1 ∈ T .

We set y := t12, x := ti1, z := t11 and choose the strictly monotone, continuous functions -F(x), z + G(¯ tj2), -Gi (y), and Hi (z, ¯ tj2), as α(), β(), ϕ(), and ψ(z), respectively. Applying the lemma yields that F is locally linear. For proving the linearity of G we must fix ti1 instead of tj2.

Theorem 3. If an allocation figure of player 1 is constant for some connected open set G ⊂ R(n-1)×2 of t-1 values, then the function H() (when defined) is locally linear in each variable of H, in every point in the corresponding projection of G, or else one of the cases (8) or (9) in Figure 3 holds.

2.2 Global linearity results

Next, we focus on the functions F and G. We prove that local linearity extends to global linearity of these functions. More precisely, the functions F(ti1) for all i ̸= 1 are uniquely determined with domain R (unless the allocation ai1 does not occur at all), and the same holds for G(ti2). Moreover, they prove to be linear, unless the mechanism is task-independent. It turns out that the requirement of Theorem 2 to have constant allocations in all the four regions is not necessary, concerning the functions F and G. The next observation extends Corollary 1 to the case when other players' bids are not fixed.

Observation 2. Let t-1 = (t2, t3, . . . , tn) and t′-1 = (t′2 , t′3 , . . . , t′n ), so that ti1 = t′i1 . If both boundaries fa11 :ai1(t-1) and fa11 :ai1(t′-1 ) exist, then they are equal.

From now on, we can use F 1 i (ti1) and G1i (ti2) (in general F k i (ti1) and Gki (ti2)) to denote the over their whole domain uniquely determined boundary functions of a mechanism. We will omit the superscript 1 whenever we consider the allocation of player 1. We omit the subscript i, when it is clear from the argument ti1 or ti2. We prove that if the mechanism is not task-independent, these functions are linear and have domain R or ∅. The proof uses the following lemmas:

Lemma 3. If all allocation figures of a single player are crossing, then all allocation figures of all players are crossing, and therefore the mechanism is task-independent.

Lemma 4. Let ti1 be an interior point of the domain of F(ti1). If F is locally non-linear in ti1, then the mechanism is task-independent.

Theorem 4. If the SMON mechanism is not taskindependent, then in the allocation figures of player 1,

• (a) every Fi and every Gi function is linear (when defined);
• (b) for any fixed t-1 the boundaries of the region R11 are f11:01 = mini̸=1 Fi(ti1) and f11:10 = mini̸=1 Gi(ti2);
• (c) the domain of every Fi and every Gi is R or ∅;
• (d) if ai1 exists then for any fixed t-1, the tj1 values of the players j ̸= 1, i can be increased so that in R01 the allocation becomes ai1 ; in turn, for any fixed t-1, the ti1 can be decreased so that in R01 the allocation becomes ai1 (and similarly for ti2).

The same holds for the allocation figures of every player k.

2.3 Non task-independent mechanisms

This subsection completes the characterization. We define the slopes of different boundary functions and settle the connection between them. For ease of exposition, henceforth we assume that the SMON mechanism we consider is not taskindependent (more precisely, not threshold), and therefore has at least one non-crossing allocation figure by Lemma 4. By Theorem 4, the F k i (ti1) and Gki (ti2) functions are linear over the whole real domain. We introduce the notation λki,horiz and λki,vert , respectively, for their slopes:

Notation 1. If the allocation aik ever occurs in the mechanism, then we denote the slope of the linear function F k i (ti1) by λki,horiz ; if the allocation aki occurs, we denote the slope of the function Gki (ti2) by λki,vert .

Later we will prove that for non task-independent allocations λki,horiz = λki,vert must hold. Before showing this, it will be useful to first elaborate on the H functions (see Figure 3). These will turn out to be linear, unless the players are partitioned into isolated groups that never share the jobs (in particular, H is always linear in cases (4)-(7), but not necessarily in cases (8) and (9)). Note also that such H functions never occur in task-independent allocations. We treat the allocation figures of player 1, and first examine the dependence of H functions on the bids of players i, with whom player 1 sometimes shares the jobs, i.e., either of ai1 or a1i occurs as allocation. This case also serves as the base case of the induction proof of Theorem 6.

Theorem 5. Assume that the allocation ai1 occurs in the mechanism. Then whenever a boundary function H() of the region R00 depends on ti1, or ti2, or on ti1 + ti2, this dependence is linear with slope λ1i,horiz . Analogously, if the allocation a1i exists, then for any of these arguments the function has slope λ1i,vert .

Corollary 2. If for some open set of t-k values, the allocation to player k is of type (4)-(9) so that H depends on ti1 or ti2 or on ti1+ti2, then λki,horiz = λki,vert (if both are defined).

Lemma 5. For any SMON allocation λki,horiz = λki,vert (when defined), unless the allocation is task-independent.

Next we define a partition of the players, such that restricted to any set of the partition, the mechanism is an affine minimizer.

Definition 7. We define the player-graph with the set of players [n] as vertices: let players i and j be connected by an edge if the allocation aij occurs in the mechanism. The players of the same connected component are called a group.

For neighboring players i and k in the player-graph by Lemma 5 we can define λki = λki,horiz = λki,vert . Observe that for these λki values λki = 1/λik is obvious by Observation 1 (b).

Lemma 6. Assume that the mechanism is not taskindependent and i, j, k is a triangle in the player-graph. Then λki = λkj · λji .

The next theorem shows that the constant slopes λki can be defined for any pair of players within the same group.

Theorem 6. Assume that the mechanism is not taskindependent. For any two players i and k of the same group there exist constants λki = 1/λik such that in every allocation figure of player k where the functions F k i , Gki appear or H depends on ti, they depend linearly on ti with slope λki .

Observation 3. If the mechanism is not task-independent, then for an arbitrary path i0, i1, i2, . . . , it in the player-graph it holds that λi0 it = λi0 i1 · λi1 i2 · . . . · λit-1 it .

Corollary 3. For any three players i, j, k of the same group, λki = λkj · λji .

Due to the uniqueness and transitivity of the λ values in non task-independent allocations, we can choose λi = λ1i to be the multiplicative weight of a player i in the group of player 1. (We can choose a representative player in each group to play the role of player 1.) In order to determine the affine minimizer within a connected group of players completely, we need additive constants for each allocation to these players, which we define next.

Lemma 7. Consider w.l.o.g. the connected group of player 1. There exist constants cii and cij for arbitrary members i and j of the group, such that within this group the mechanism allocates according to an affine minimizer with multiplicative constants λ1i and additive constants cii and cij (given that this group of players receives the tasks).

Clearly, for every connected group g we can choose a representative player kg, and determine the multiplicative and additive constants λkg i , cij and cii accordingly. We assume that k1 = 1. It remains to elaborate on the rules of the allocation between two different groups of players. Let Optg be the optimum value of group g, that is Optg = mini,j∈g(λkg i ti1+ λkg j tj2+cij ). The characterization result (Theorem 1) is now

• an immediate corollary of Lemma 8.

Lemma 8. For every connected group g of players, there exists an increasing continuous function Φg with domain (-∞,Cg) and lim-∞Φg = -∞ s.t. (optimal players of) group g with minimum value of Φg(Optg) receive the tasks.

3 Discussion

The most immediate open question is, whether our result extends to SMON mechanisms with many tasks. The characterization can be generalized if we make the following strong assumption: for any two tasks u and v, if two players (ever) share these tasks in the 2-dimensional projection allocation obtained by fixing the bids for every other task to some t-uv matrix, then they also share the tasks given any other fixed values t′-uv . This property holds for all the mechanisms that we know, but it is not clear why it can be assumed right away. We conjecture that every continuous decisive SMON mechanism for allocating m items, with additive bidder valuations and tij ∈ R, is the product of grouping minimizers and a task-independent mechanism.

Another question is, if Lemma 2 can in any way be helpful to gain insight into the nature of WMON allocations. The lemma suggests the intuition, that in order to obtain new types of WMON allocation rules, we need to find ones where the boundary functions are not additive separable functions of the relevant variables. 11