WPCa% 2 BPZ Courier 10cpi#|xx  @87X@HP LaserJet IIIHPLASIII.PRSx  @,\,A]X@2< ZLu+#|xHP LaserJet IIIHPLASIII.PRSx6X@8;,\,A]X@11-17-95 10:35a moulin strategy paper   #Courier 10cpiCourier 10cpi (Bold)Courier 12cpiCourier 12cpi (Bold)CG Times (Scalable)CG Times Italic (Scalable)2Z[ v>"Sh ^!.22YN!!!2Y!!!!2222222222!!dYd,YH?EJ?;HJ!'F?[JH9HC6?JH^HHA!!!22!,2,2,!222N2222%'22H22,,2,d2$22T2222!!!!,222222222H,H,H,H,H,YCE,?,?,?,?,!!!!J2H2H2H2H2J2J2J2J2H2H,JH2H2H2J292H2H2H2E2E2E2E2J2?2?2?2?2H2H2H2H2H2H2J222222$2I822F2?2?2?2??J2J;J2J2H2H2YHC2C2C2626'6262?2?2J2J2J2J2J2J2^HH2A2A,!222!!/ddddddddddddddddddddddddddddddddddddddddddddddddNHHH222!,))22X222YY2#2222Y#!2442Ydd22==Ld2d2H2;SS88Y2!4^x#"ddddHHddd2Hdd4HHYYddd2YYddd 2Y2!!dddddH=dYHHHHHHHHHH!d2H282YdHdC2!2H,29HNEddHHHHHHHHHHddddd0dHHHHdddddddddddddddddddHHdddddWC=NdHddd+;HHHHdddddHHH2HHdHHdddHHH,HHHH,HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH!HHH!HHH!HHH!HHHHHHHHHHHHHH=?8=8C,?'A,J,H,!F,C8[8J,C2H,H=92=22?,H,C=H8N===H?J!2HHH=,====!!2222HJ222HHH=!=2,!f22xxx,x  @87X@2xxx,x  `B7X6}*ddd,#d  @87@&}*ddd,1d  `J72H<!,F ,< P7,P>I;!,Z,;&_ x$&7,X{K< ,Kx'3 g. ,  g"Sh ^!022YN!!!2Y!!!!2222222222!!dYd2Y==CH=9HH!,C8SCH=H=28H=S=88!!!22!22,2,22,H2222''2,C,,',2,d2$22T2222!!!!2222222222=2=2=2=2=2YCC,=,=,=,=,!!!!C2H2H2H2H2H2H2H2H28,=2HH2H28,H2=2=2=2=2C2C2C2C2H2=2=2=2=2H2H2H2H2H2H2H222222$2Q222C282828288C2C=C2C2H2H2^C=2=2=2222'22228282H2H2H2H2H2H2SC82828'!222!!/ddddddddddddddddddddddddddddddddddddddddddddddddNHHH222!2..22W222YY2#2222Y#!2222Ydd22==Ld2d2H26LL22Y2!2Yz#"ddddHHddd2Hdd2HHYYddd2YYddd 2Y2!!dddddH=dYHHHHHHHHHH!d2=282YdHdC2!2H,29HNEddHHHHHHHHHHddddd0dHHHHdddddddddddddddddddHHdddddWC=NdHddd+;HHHHdddddHHH2HHdHHdddHHH,HHHH,HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH!HHH!HHH!HHH!HHHHHHHHHHHHH===8=8C,='8,H,H,!C,C8S8C,C2H,H==2=228,8,C==8N=====H!2H88=,====!!2222=H222888=!=2,!f2a8DocumentgDocument Style StyleXX` `  ` 2pkVk,a4DocumentgDocument Style Style . a6DocumentgDocument Style Style GX  a5DocumentgDocument Style Style }X(# a2DocumentgDocument Style Style<o   ?  A.  2*vty a7DocumentgDocument Style StyleyXX` ` (#` BibliogrphyBibliography:X (# a1Right ParRight-Aligned Paragraph Numbers:`S@ I.  X(# a2Right ParRight-Aligned Paragraph Numbers C @` A. ` ` (#` 2# \   da3DocumentgDocument Style Style B b  ?  1.  a3Right ParRight-Aligned Paragraph Numbers L! ` ` @P 1. ` `  (# a4Right ParRight-Aligned Paragraph Numbers Uj` `  @ a. ` (# a5Right ParRight-Aligned Paragraph Numbers _o` `  @h(1)  hh#(#h 2Ua6Right ParRight-Aligned Paragraph Numbersh` `  hh#@$(a) hh#((# a7Right ParRight-Aligned Paragraph NumberspfJ` `  hh#(@*i) (h-(# a8Right ParRight-Aligned Paragraph NumbersyW"3!` `  hh#(-@p/a) -pp2(#p a1DocumentgDocument Style StyleXqq   l ^) I. ׃  2+vDoc InitInitialize Document Style  0*0*  I. A. 1. a.(1)(a) i) a) I. 1. A. a.(1)(a) i) a)DocumentgTech InitInitialize Technical Style. k I. A. 1. a.(1)(a) i) a) 1 .1 .1 .1 .1 .1 .1 .1 Technicala5TechnicalTechnical Document Style)WD (1) . a6TechnicalTechnical Document Style)D (a) . 2/*a2TechnicalTechnical Document Style<6  ?  A.   a3TechnicalTechnical Document Style9Wg  2  1.   a4TechnicalTechnical Document Style8bv{ 2  a.   a1TechnicalTechnical Document StyleF!<  ?  I.   2-%  *!F`a7TechnicalTechnical Document Style(@D i) . a8TechnicalTechnical Document Style(D a) . PleadingHeader for numbered pleading paperP@n   $] X X` hp x (#%'0*,.8135@8:! #xdddddlddxstack {alignl x_1(q_1,q_2)= 1 over 2 (C(q_1,q_2)+C(q_1,0)C(0,q_2)) # ~ # alignl x_2(q_1,q_2)=1 over 2 (C(q_1,q_2)+C(0,q_2)C(q_1,0))~for~all~q_1,q_2 epsilon \{0,1\}}x  @87X@x  @87X@x  @87X@xRqqCqq C q( CqxRqqCqq Cp q( Cqforallqq1(1, 2Z)11T20( (1`,P2) ( 1H , 08 ) (0,2)H)2(1, 2Z)1720( (1`,P2) ( 0 , 28 ) (1,X0)H)1`,P2{y0,i1}    2h2h >Consider the cost function 0'0*(('# !0Ԍ$(#(#(#(#8!!'#$|A#xW ddddd ddxC(1,0)=C(0,1)=10~;~C(1,1)=30x  @87X@x  @87X@x  @87X@8CZ8C8C8(81z8,80j8)8(J808,:818)8108;2 8( 81" 8, 81 8) 8308*8 8|$(#(#8(#(#!A'#$and assume that both agents are willing to pay $13 for one unit of "their" good (recall that agent i is only interested in good i). The corresponding demand game is as follows (entries represent net utility gain from the initial  _ allocation h0__dd<< q_i=0~x_i=0x  @87X@x  @87X@x  @87X@_q+i*_x+i__Z_0r_0h)    Y ddx !ddxe @ Y  m    _  !0__dd  q_2=1x  @87X@x  @87X@x  @87X@_q+2R_1_!   3  2m e   agent 2   0  2m     _i  !0__dd  q_2=0x  @87X@x  @87X@x  @87X@_q+2R_0_!^  0^  0m O  } }  0  3O^ _  !0__ddq_1=0x  @87X@x  @87X@x  @87X@_q+1R_0_! !!05__ddq_1=1x  @87X@x  @87X@x  @87X@_q+1R_1_!    agent 1 This game has the familiar Battle of the Sexes configuration, whereby none of the  _ two Nash equilibria A0u __udd<</((q_1=0, q_2=1)x  @87X@x  @87X@x  @87X@_(_(z+1B_0_,+2r_1_)_q2_q__/߬ and a0u__udd<<.(q_1=1,q_2=0))x  @87X@x  @87X@x  @87X@_(+1_1B_,2+2_0r_)_)_q_qR__.߫ can be refined away. It is the epitome of a game with poor strategic properties (in particular it is not dominance solvable). Contrast the above method with the elementary incremental cost method where agent 1 is first  _(  *0fG__fdd<<7Sx_1(q_1,q_2)=C(q_1,0);~x_2(q_1,q_2)=C(q_1,q_2)C(q_1,0)~all~q_1,q_2 epsilon \{0,1\}x  @87X@x  @87X@x  @87X@_xR_q_qJ_C:_q:_xz _q _qr _Cb _q_qZ_CJ_q_all_q_q+1_(+1_, +2Z_)_(+1_,z_0_)j_;+2 _( +1B _,2 +2 _) _( +1*_,+2j_)_(+1_,_0_) +1Z_,J+2_{s_0_,c_1_}_ ___ 7ߴڃ For any preference profile (not even necessarily convex) the demand game has clean strategic properties: agent 1 has a dominant strategy (his utility unaffected by agent 2's choice) and the game is dominancesolvable. There is a unique Nash equilibrium unless player 1 is indifferent between consuming good 1  _` or not (and if she is, her altruistic choice !0D!__dd<<q_1=0x  @87X@x  @87X@x  @87X@_q+1R_0_! picks the strong equilibrium, given increasing marginal costs). In the example, this equilibrium is (1,0). Consider the elementary incremental cost formula among any number of agents ordered as 1,2,...,n: ha#x%ddd}[ddx9GJ 2  (1)  2X  ix_i=C(q_1,....,q_i,0,...,0)C(q_1,...,q_{i1}, 0,...,0) ~ # ~# alignl for~all~i,~all~q_i epsilon [0,Q_i]x  @87X@x  @87X@x  @87X@xiZCJqqbib CR qrqi^for^all^i^all^q*i3 ^Q *i :(1,..z..j,,*0,.. . , 0r ) ( 1 , . ..,1,R0,B..2.,"0) ^,^[C^0^, ^]j^ h$(#(#(#(#!a'#$Clearly the corresponding demand game has equally nice equilibrium properties as in the two person case: the game is dominance solvable (player 1 has a dominant strategy; once player 1's demand is selected, player 2 has a dominant strategy and so on) and, barring indifferences, has a unique Nash equilibrium (also a strong equilibrium). Also, the social choice function eliciting individual preferences and implementing the non cooperative equilibrium of the reported game is non manipulable (by individual agents or coalitions). P(0*((1'# !W '#P A%'#t)aPԌ _ When each agent wants to consume at most one unit 0%__%dd<<(Q_i=1~for~all~i)x  @87X@x  @87X@x  @87X@_(_1_)_Q +i_forb_all"_iZ_߁ the n! elementary incremental cost formulas (1) are not the only cost sharing methods of which the corresponding demand game is always dominancesolvable, or has a unique Nash equilibrium for almost all preference profiles. However the corresponding n! social choice functions are essentially the only scfs meeting  }= the property of coalition strategyproofness (Theorems 3 and 4).5 These findings are disappointing (they can be read as an impossibility result) because they do not leave much flexibility to the mechanism designer. The hierarchy of the players must be chosen once and for all, and the higher players in the hierarchy are at a clear advantage over the lower players (given increasing marginal costs).  _ Turning now to the general case where the capacities 0__dd<<Q_ix  @87X@x  @87X@x  @87X@_Q+i are arbitrary, our results have a more positive flavour. In fact, the flexibility of the mechanism designer increases dramatically. For sure the n! elementary methods like (1) remain in the set of "good" methods (of which the demand game has an unambiguous non cooperative equilibrium), but many new methods enter this set as well. Even though these methods always keep some degree of inequity among players (formally, none of them is anonymous), this bias may become vanishingly small as the individual capacities become very large (as the goods become more and more divisible): see the discussion in Section 12. We give an example of a simple incremental cost method in the case of three  _W agents with capacities 0= v__=dd<<RQ_1=4,Q_2=3,Q_3=2x  @87X@x  @87X@x  @87X@_QB_Qr_Q+1R_4_,+2_3_,+3_2_ _:_R. Any such method is identified by a  }*L sequence in {1,2,3} where player 1 appears four times, player 2 appears three  }= times and player 3 appears twice.6 For instance #xdddmm]ddxG# 2 `^ (2) ă)1~~~~2~~~~1~~~~3~~~~2~~~~1~~~~2~~~~3~~~~1x  @87X@x  @87X@x  @87X@81828183r82J 81" 82 8381߷$(#(#(#(#!'#$The corresponding method works as follows. Consider the demand profile  _ 4!0 __ dd<<q=(q_1,q_2,q_3)=(2,2,1)x  @87X@x  @87X@x  @87X@_qz_q_q_q_:__(+1B_,2+2_,r+3_)_(*_2_,_2_, _1_)4. We follow the sequence (2), assigning one unit of good i to agent i each time agent i is called, and charging her the corresponding incremental cost. Thus we build a monotone path of demand profiles from 0 to q:    Y !ddxe @ Addx`  Y OO ^  demand )  incremental )  charged O   profileH  costH  to/ )  0,0,0w  0w  / / H  1,0,0 C(1,0,0)0  agent 1/ / w  1,1,0 C(1,1,0)C(1,0,0)  agent 2/ /   2,1,0 C(2,1,0)C(1,1,0)  agent 1/ /   2,1,13! C(2,1,1)C(2,1,0)3!  agent 3/ _     2,2,1" C(2,2,1)C(2,1,1)"  agent 2_  3!   This determines completely the cost sharing of C(2,2,1). In a way, the choice of q=(2,2,1) was lucky because we reached q while following the sequence (2). What about the demand profile q'=(1,2,2)? This time we fulfill the demand of agent 1 at once , so we simply erase agent 1 in the remaining sequence and proceed. After four steps, the demand of agent 2 is fulfilled so we erase him also and charge the remain incremental cost to agent 3:0'0*(('#0Ԍ   T Addx`  addx` ` ` T _  O 3!  demand O  incrementalO  chargedO   profilen  costn  to/ O  1,0,0  C(1,0,0)  agent 1/ / n  1,1,0  C(1,1,0)C(1,0,0)  agent 2/ /   1,1,1  C(1,1,1)C(1,1,0)  agent 3/ /   1,2,1*  C(1,2,1)C(1,1,1)*  agent 2/ _    1,2,2  C(1,2,2)C(1,2,1)  agent 3_  *   To show that this method yields a dominance solvable demand game at every profile of convex preferences we will use the assumption of increasing marginal  _~ costs \A0-__-dd<<(partial _i C(q)x  @87X@x  @87X@x  @87X@_(_(_)_,+i:_C*_q\ increases in a0__dd<<q_ix  @87X@x  @87X@x  @87X@_q+i and in 0__dd<<q_jx  @87X@x  @87X@x  @87X@_q+j for all 0;88dd<<j != ix  @87X@x  @87X@x  @87X@8j8i8c). Consider player 1: if he demands 0 or 1 unit, he pays the Stand Alone cost no matter what other players are demanding. Therefore (barring indifferences)  _h either his strategy !0 __dd<<q_1=0x  @87X@x  @87X@x  @87X@_q+1R_0_! dominates !0__dd<<q_1=1x  @87X@x  @87X@x  @87X@_q+1R_1_! or vice versa. Suppose the former:  _] we claim that !0( __dd<<q_1=0x  @87X@x  @87X@x  @87X@_q+1R_0_! dominates every other strategy !0 *|__ *dd<<)q_1', 1  q_1' 4x  @87X@x  @87X@x  @87X@_qB_q_ _:1_,R_1:1_4)ߦ. Indeed for all  _ A0*__*dd<<q_1'x  @87X@x  @87X@x  @87X@_q:1:  _ #xdddddddx(stack {alignl x_1(q_1',0,0)=C(q_1',0,0) # ~ # alignl x_1(q_1',q_2,q_3) C(q_1',0,0)~for~all~q_2,q_3,0  q_2  3, 0  q_3  2}x  @87X@x  @87X@x  @87X@xRqCq^xR^q^q^q^Cz^q ^for ^allr ^q^q^q^q1(1,0 ,0)b(R1,0, 0)*1^(91^, *2Z^,J*3^)^(91B^,^02^,^0" ^) *2:^,**3z^,^0Z*2"^3^,^0z*3B^2UrkU^ j^^^^(ߥ$(#(#(#(#!'#$(the inequality follows from increasing marginal costs). As a05*a__5*dd<<  C(q_1',0,0)x  @87X@x  @87X@x  @87X@_C_q_(z:1_,B_0_,2_0_) ߇ is  _l convex in 0*__*dd<<q_1'x  @87X@x  @87X@x  @87X@_q:1, and agent 1's preferences are convex, his preferences are single _ peaked over the graph 0*H __*dd<<a(q_1',C(q_1',0,0)x  @87X@x  @87X@x  @87X@_(:1R_,B_(2:1_,_0r_,_0b_)_q_C_qKa). As his preferences decrease when we  _ move from 05*__5*dd<<$q_1'=0~\to~q_1'=1x  @87X@x  @87X@x  @87X@_q"_toj_q_2_:1R_0:1_1$ߡ, they keep decreasing all the way so player 1 prefers 0I#__dd<< (q_1=0,x_1=0)x  @87X@x  @87X@x  @87X@_(+1_0B_,2+1_0r_)_q_xR__ߚ  _ to any allocation 0* __*dd<<(q_1',x_1(q_1',q_2,q_3)x  @87X@x  @87X@x  @87X@_(:1R_,B+1_(:1_,+2_,+3R_)_q_x _qJ_q_q), as claimed.  _ Thus if !!0( !__dd<<q_1=0x  @87X@x  @87X@x  @87X@_q+1R_0_! dominates !A0Q!__dd<<q_1=1x  @87X@x  @87X@x  @87X@_q+1R_1_! all but one of player 1's strategies are  _ eliminated. If, on the other hand, !a0"__dd<<q_1=1x  @87X@x  @87X@x  @87X@_q+1R_1_! dominates !0"__dd<<q_1=0x  @87X@x  @87X@x  @87X@_q+1R_0_!, player 1's strategy set shrinks to [1,2,3,4]. In both cases the iterated elimination of dominated strategies continues: a similar argument shows that player 2 either eliminates  _ !0%__dd<<q_2=0x  @87X@x  @87X@x  @87X@_q+2R_0_! or e0%__dd<< q_2=1,2,3x  @87X@x  @87X@x  @87X@_q+2R_1_,B_2_,2_3_e. And so on. In general, we establish (Lemma 6) that the demand game associated with any incremental cost method is dominancesolvable, strictly so if indifferences are barred. Our Theorems 1 and 2 prove the converse property: only an incremental cost method can give rise to a dominance solvable demand game at every preference profile (Theorem 1) or to a demand game with a unique Nash equilibrium for almost every preference profile (Theorem 2). Theorems 3 and 4 are the main results of this paper. They are written in the context of social choice functions satisfying the two mild requirements called Consumer Sovereignty (an agent can always guarantee that a certain demand of output will be met) and No Exploitation (an agent consuming no output does not pay anything). Theorem 3 characterizes the set of coalition strategyproof social choice functions as those scfs derived from an incremental cost method satisfying Cross Monotonicity (agent j's cost0'0*(('#0 shares does not fall when agent i's demand rises). Adding a requirement of continuity (w.r.t the cost function), Theorem 4 characterizes the subset of simple incremental cost mechanisms defined by a single sequence such as (2).  }*C  3. StrategyProof Allocation of Private Goods This section repeats known arguments making strategyproof and coalition strategyproof mechanisms worthy of our interest and analytical efforts; it also relates our results to the existing literature on strategyproof allocation of private goods. A strategyproof social choice function elicits truthful report of individual preferences in an environment where information about these preferences is private (to the agent holding these preferences) and where agents' actions are decentralized (in particular, agents are unable to form coalitions and coordinate strategically their messages). Two decades after the invention of strategyproofness (Hurwicz [1972], Gibbard [1973]) the vast literature on implementation has shown that in such environment, only a strategyproof social choice function can be implemented (see e.g. Barbera and Jackson [1993], Barbera [1994]). A strategyproof mechanism is appealing because it gives straightforward incentives to each individual participant whether or not this particular agent knows anything more than his own preferences: any information about other participants' preferences is useless to him, as long as he cannot coordinate his actions with that of any other agent. However, many interesting strategyproof mechanisms are vulnerable to strategic manipulations if a subset of the participants happen to be mutually informed of their preferences and are able to coordinate the messages elicited by the mechanism. A paramount example of this situation is the pivotal mechanism for public decision making (Clarke [1971]) as well as the whole class of mechanisms generalizing the pivotal (Groves [1973], Green and Laffont [1979]). Typically these mechanisms collect more taxes than necessary to cover the cost of the selected public project and are therefore manipulable by the (grand) coalition of all participants.  }*| A coalition strategyproof social choice function is one that cannot be manipulated either by individual agents misreporting their own preference (hence the social choice function is strategyproof in the ordinary sense) or by any coalition of agents jointly misreporting. The corresponding mechanism can be implemented whether or not the information about individual preferences is private, and whether or not individual actions are decentralized. Thus I submit that when the only variable parameter of our environment is the profile of individual preferences, a coalitionstrategyproof social choice function is the only form of allocation mechanism that is a sustainable "constitutional" design over the full gamut of informational assumptions (including in particular the case where information about individual preferences is strictly private, the case where it is common knowledge and all intermediate cases). Of course, we must assume that the mechanism designer has the commitment power to enforce the allocation computed by the mechanism (in our case he can enforce the payment of individual cost shares). The formal discussion of coalition strategyproof social choice functions has been mostly confined to the allocation of pure public goods (the voting context), following the initial observation that in an environment where preferences are single peaked over a line of possible outcomes, the majority (Condorcet) winner defines a coalition strategyproof mechanism (Barbera [1994] offers a good survey of the literature on strategyproof voting). In the context of allocation of private goods, however, the results are few and far between. For exchange economies (and/or the fair division of unproduced commodities), Barbera and Jackson [1993] recently characterized all strategy'0*((ԫproof mechanisms (under the additional assumptions of anonymity and individual rationality; they are able to drop those assumptions in the two agents case). It turns out that just like in the case of voting with singlepeaked preferences, a strategyproof mechanism is coalition strategyproof as well. For production economies (with private goods only), the literature on strategyproofness consists, so far, of two papers, both related to the current work. Satterthwaite and Sonnenschein [1981] established that all strategyproof mechanisms exhibit the local property of "acyclicity" (the analog for the context with divisible outputs of the property stated in Definition 4); Shenker [1992] (expanding on the strategic analysis of Moulin and Shenker [1992]) is able to deduce the global structure of coalition strategyproof mechanisms (under the additional assumption of anonymity). Note that both of these papers rely heavily on regularity (in particular smoothness) assumptions on the social choice function itself. Such assumptions are technically compelling yet they are hardly defensible normatively. A remarkable feature of Barbera and Jackson [1993] is to dispense with regularity assumptions (including continuity) altogether. This paper offers a complete characterization of coalition strategyproof cost sharing methods that uses no regularity and no anonymity assumption. Our model is considerably simpler than in Satterthwaite and Sonnenschein [1981] or Shenker [1992], in that the output goods are produced in indivisible units and each agent consumes (several units of) exactly one output good. The key insight of Satterthwaite and Sonnenschein [1981] is that strategyproofness of a resource allocation leads to a local hierarchy of dictators: that is, agent 1 who is first in the hierarchy gets an allocation based on his own message (without any influence of other agents' messages); agent 2's allocation depends of her own as well as agent 1's message (but not on messages by agents 3 to n), and so on. The hierarchy is local in the sense that it may depend upon the preference profile. This pattern is especially clear in the case of the elementary incremental cost sharing methods (1): there the hierarchy is the same at every preference profile. However, in every other method of our general family of incremental costsharing methods (e.g. (2)), the hierarchy varies with the profile. Thus the mechanism may be globally (almost) equitable if it is not locally equitable. This important point is already demonstrated (in the model with divisible goods) by Moulin and Shenker [1992] and by Shenker [1992].  }*q  4. The Model; Definition of Cost Sharing Methods  The technology produces n different goods. The set N of goods in fixed  8f once for all _0 !88dd <<( line N line =n)x  @87X@x  @87X@x  @87X@8(8)8 R8 88N8n_. Each good comes in indivisible units; the capacity of  _4 good i is denoted 0 S"__dd <<Q_i x  @87X@x  @87X@x  @87X@_Q+i so .!0=S"__dd <<Q_i epsilon  x  @87X@x  @87X@x  @87X@_Q+i_ C_ױ., where A0BS"88dd <<T =\{0,1,2,...\})x  @87X@x  @87X@x  @87X@888{80 8,818,q828,a8.8.Q8.8}A8)T. The capacity profile  _) is denoted Q (so .a0T H#88dd <<Q epsilon  ^Nx  @87X@x  @87X@x  @87X@8QzzN8 8ױ. with ith coordinate 0d#__dd <<Q_ix  @87X@x  @87X@x  @87X@_Q+i) To each good i corresponds a different agent (agent i) who is only interested in consuming good i (she does not consume any of the other goods, nor does she care about what other agents consume of the other goods or pay). We  _ denote by 0&__dd <<q_ix  @87X@x  @87X@x  @87X@_q+i agent i's consumption of good i (0&__dd <<q_ix  @87X@x  @87X@x  @87X@_q+i is an integer and \0-6&__-dd <<0q_iQ_ix  @87X@x  @87X@x  @87X@_0___q+iJ_Q+i\)  _! and by 0l'88dd <<oqx  @87X@x  @87X@x  @87X@8qo the consumption profile. We speak indifferently of !0'__dd <<q_ix  @87X@x  @87X@x  @87X@_q+i as agent i's demand or consumption and of q as the demand profile. Thus q varies in the  8g# rectangle [0, Q] of A0 )88dd << ^Nx  @87X@x  @87X@x  @87X@8zN.  _$ We denote by a0 3+__dd <<e_ix  @87X@x  @87X@x  @87X@_e+i the ith coordinate vector of 0-+88dd << ^Nx  @87X@x  @87X@x  @87X@8zN and for all coalition   & S, %0],88dd << S  N,x  @87X@x  @87X@x  @87X@8S8N8z8,% by 0q ],__dd <<e_Sx  @87X@x  @87X@x  @87X@_e+S the vector %0XJ/,XJdd << sum_S e_ix  @87X@x  @87X@x  @87X@9I+SueRi%. Given |0VA,88dd <<q epsilon  ^N, i epsilon Nx  @87X@x  @87X@x  @87X@8qzzNB8i8N8 8 88,| and @!0*(,__*dd <<q_i' epsilon  x  @87X@x  @87X@x  @87X@_q:iC__ @, we denote  _Z' nA0*y-__*dd <<( q line ^i q_i')x  @87X@x  @87X@x  @87X@_(r_)_qRi_q":i_ 3n the vector with ith coordinate a0*y-__*dd <<q_i'x  @87X@x  @87X@x  @87X@_q:i and jth coordinate 0-__dd <<q_jx  @87X@x  @87X@x  @87X@_q+j for all jci. Z' 0*(( The cost of producing the demand profile q is C(q), that must be shared among the n agents/goods. We always assume that the cost function C is strictly increasing in each individual demand and that there is no fixed cost. Thus the basic space of cost functions  _  t  tXt o# $Xddddddd xt (Q)=\{C:[`0,Q`]   ~line~C(0)=0~\and~ partial _i C(q) > 0 ~ for~all~i epsilon N,~all~q~s.t. q_i < Q_i\}x  @87X@x  @87X@x  @87X@__c___ @ _H _,_(_)w_{g_:_[m_0_,_]_(P _0 _) _0p_(`_)_>P_0_,_._._<I_}_Q_C]_Q`_C _and +i _C_q _for_all_iy_N_all_qQ_sA_t1_q+iy_Q+i_ o$XXd&d&XXd&d&!Xc&$ XtX  X (with the notation =0%  W __% dd <<partial _i C(q)=C(q+e_i)C(q))x  @87X@x  @87X@x  @87X@_,__B_r+i_C_q_C _q_ez+i_C_q:_(*_)_(_)2_("_)_)=. The whole strategic analysis (starting with Section 9) and several important non strategic properties of cost sharing methods (see sections 58)  8" take place in the subset of $0A88dd << (Q)x  @87X@x  @87X@x  @87X@88(8)8Q$ exhibiting increasing marginal costs and cost complementarity. Denote the second derivative of C at q with respect to i,j as  _ y#xddddddd x4partial_{ij}C(q)=C(q+e_i+e_j)C(q+e_i)C(q+e_j)+C(q)x  @87X@x  @87X@x  @87X@_,____ _z _Z __r+ij_C_qj_CZ_qJ_e+i_e+jR_CB _q2 _e +i _C _q _eR+j_C_q_(z_)_(b_)_( _)j _(_) _(_)y$(#(# (#(#!'#$Note that this formula makes sense only if |0|R__dd <<qQe_ie_jx  @87X@x  @87X@x  @87X@_q_Q_er+i:_e+j_z__|. The space of imc (increasing marginal cost) functions is now defined  #xdddddidd xW6# 2 `@ (3) ăo _{imc} (Q)=\{C epsilon  (Q) line for~all~i,~j epsilon N,~all~q  Qe_ie_j:partial _{ij} C(q) > 0\}x  @87X@x  @87X@x  @87X@____ __N__,+imc_Q_C_Q_for_allu _i _j _N _all_q_Q~_e+i_eF+jn+ij_C_q_(w_)g_{=_(-_) _, _,_:_(v_)_>f_0_}W_ 5 _  $(#(# (#(#!'#$In definition (3), we allow for i=j, thus the marginal cost of good i is strictly increasing w.r.t each good. Note that a cost function in C is in particular strictly supermodular: !#xdddddJdd xW6# 2 `O (4) ăCfor~all~q,q' epsilon [`0,Q`]: C(q)+C(q') < C(q or q') + C(q and q')x  @87X@x  @87X@x  @87X@8for8all8q8q8Q8C 8q 8C 8q 8C8qs8q 8C8q8q 8,8[.808,8]$8: 8( 8)l 8( 8) 8< 8(08)8(8)z| 8u zz8z?8 88߾$(#(#`(#(#!!'#$(where  and  are respectively the coordinatewise supremum and infimum).  }*J  Definition 1   8 Fix a capacity profile . 088dd <<Q epsilon  ^Nx  @87X@x  @87X@x  @87X@8QzzN8 8ױ. and a cost function O! 088dd <<C epsilon  (Q)x  @87X@x  @87X@x  @87X@8C8Q8 8p8(`8)O. A cost sharing  _ method (csm) is a mapping A 088dd <<qxix  @87X@x  @87X@x  @87X@8q from [0,Q] into a 0*__*dd <<  _+^Nx  @87X@x  @87X@x  @87X@_:N, associating with each demand profile q a profile of cost shares x(q) and satisfying three properties:  S i) Budget balance:  0J r Jdd <<1sum_N x_i(q)=C(q)x  @87X@x  @87X@x  @87X@9I+NuxRiq%CqE(5)()1߮ (for all q)  _ ii) No Exploitation: if ! 0t!__dd <<q_i=0x  @87X@x  @87X@x  @87X@_q+i_Z_0! then T 0M!__Mdd <<x_i(q)=0x  @87X@x  @87X@x  @87X@_x+iZ_q_(_)_0J_T (for all q,i)  _ iii) Strict Demand Monotonicity:  0%"__%dd <<(5partial _i x_i(q) > 0 (for~ all~ q,i~ s.t. q_i < Q_i)x  @87X@x  @87X@x  @87X@_,r+i_xB+i _qb_for"_all_q_i _s _t _q +i _QJ +i_(_)_>r_0_(Z_, _. _.R _< _)(ߥ  8 We denote by F 0 #88dd <<  (Q,C)x  @87X@x  @87X@x  @87X@88(8,r8) 8Q8CF the set of cost sharing methods thus defined. The No Exploitation property is a compelling normative requirement in the absence of fixed costs. Demand Monotonicity has a dual normative or incentivedriven interpretation (as noted in Moulin [1994], where it plays a central role in the axiomatic analysis). In the analysis of social choice functions in Section 11, it will be a consequence of incentivecompatibility. By Definition 1, there is a single cost sharing method whenever only one  8# agent i is active, that is to say whenever every agent j, ! 0X)88dd <<j != ix  @87X@x  @87X@x  @87X@8j8i8c, has zero capacity  _[$ CA 0z*__dd <<(Q_j=0)x  @87X@x  @87X@x  @87X@_(_0J_)_Q +jZ_C: agent i must pay the full cost a 0-iz*__-dd << (x_i(q)=C(q)x  @87X@x  @87X@x  @87X@_(Z_(J_)_(_)_x +i_q:_C*_q_ߘ) and others pay nothing. Thus an interesting cost sharing problem must have at least two active agents. We define now two projection operators playing a crucial role throughout  8E' the paper. We call a precost sharing method (precsm) a mapping  0xd-88dd <<qxix  @87X@x  @87X@x  @87X@8q from [0,Q]`E' 0*((AXc& '# '# '#! `  8 into  088dd << ^Nx  @87X@x  @87X@x  @87X@8zN satisfying BudgetBalance (but not necessarily properties ii) and iii)  _ in Definition 1). We denote by W 0M0 __Mdd << _0(Q,C)x  @87X@x  @87X@x  @87X@_+0_(_,_)Z_QJ_CW the set of precsms (a superset of  _ E 088dd << (Q,C)x  @87X@x  @87X@x  @87X@88(8,r8) 8Q8CE). Given q 0 88dd <<Q,C epsilon  (Q)x  @87X@x  @87X@x  @87X@8Q8C8Q8,`8(P8)z8 8q and an agent i such that "! 0__dd <<q_i > 0x  @87X@x  @87X@x  @87X@_q+i_>Z_0", we define two cost  8 functions FA 088dd << C^{i},C^ix  @87X@x  @87X@x  @87X@8Czi8CmzizC8,F as follows:  _ 4A#x5 dddddmdd xstack {alignl C^{i} epsilon  ((Q line^i 0)):~~C^{i} (q)=C(q) # ~ # alignl C^i epsilon  ((Q line^i Q_i1)): C^i(q)=C(q+e_i)C(e_i)}x  @87X@x  @87X@x  @87X@CiQiCijq C q_Ci_Qi_Q+i*_Ci_q _C _q _el +i _C_e+i RZ u_b_ _ _t _4 _C _ )((10)!):()J (: )_(r_(J_1_):_)_:,_( _) _( _)$_(l_)4$(#(#(#(#!A'#$Next we define two operators a 0' 88'dd <<r^ix  @87X@x  @87X@x  @87X@8rzi and  0V 88Vdd <<r^{i}x  @87X@x  @87X@x  @87X@8rziz on W 0M __Mdd << _0(Q,C)x  @87X@x  @87X@x  @87X@_+0_(_,_)Z_QJ_CW. For all  0 __dd <<xi epsilon _0(Q,C)x  @87X@x  @87X@x  @87X@__ _c+0_(_,_)+_Q_C߄ (with corresponding cost share profile x(q)):  _`  XX a#(#[Xddddd[dd xs# 2 `7 (5) ă2stack {alignl r^{i} (xi) epsilon  _0((Q line^i 0), C^{i}):~for~all~q epsilon [`0,(Q line ^i 0)], x^{i} (q)=x(q) # ~ # alignl r^i (xi) epsilon _0((Q line^i Q_i 1), C^i):~for~all~q epsilon [`0,(Q line^i Q_i 1)],~x^i(q)=x(q+e_i)x(e_i)}x  @87X@x  @87X@x  @87X@r#iQ#iDC%#i for} all= q Q#ix#iqxq^ri^Q]i^Q-*i]^C i ^forg ^all'^q^Qi^Q*i^x@i^qp^x`^qP^e*i^x^e*i#< # #^ ^ }^n^ ^^^^C(+)0(L(0T),u):[0,($0)],5(%)(})^(^)U*0^(^(^1m^)^,_ ^) ^:^[^0^,~^(V^1^)F^]^,^(^)^( ^)^(^)   ^t^ ^ 2$XX%%` XX%%!aX%$ XX Interpret G 0i88dd << r^{i}(xi)x  @87X@x  @87X@x  @87X@8rzizC8(+8)8G as the restriction of  0J88dd <<qxix  @87X@x  @87X@x  @87X@8q when we set !! 0__dd <<q_i=0x  @87X@x  @87X@x  @87X@_q+i_Z_0! and 3A 0i88dd <<r^i(xi)x  @87X@x  @87X@x  @87X@8rzi8(8)83 as the  _[ restriction of a 0 z88dd <<qxix  @87X@x  @87X@x  @87X@8q when we set & 05z__dd << q_i  1x  @87X@x  @87X@x  @87X@_q+i_Z_1&. The budget balance property holds for  8P G 0o88dd << r^{i}(xi)x  @87X@x  @87X@x  @87X@8rzizC8(+8)8G and 3 0Z o88dd <<r^i(xi)x  @87X@x  @87X@x  @87X@8rzi8(8)83. Suppose now  is a cost sharing method according to Definition 1  _ (satisfying properties ii and iii; in particular & 0__dd << x_i  0x  @87X@x  @87X@x  @87X@_x+i_Z_0& for all i). Then H 0%!88dd << r^{i}( xi)x  @87X@x  @87X@x  @87X@8rzizC8(+8)8H  8 also satisfies properties ii and iii, so ! 0V88Vdd <<r^{i}x  @87X@x  @87X@x  @87X@8rziz projects EA 088dd << (Q,C)x  @87X@x  @87X@x  @87X@88(8,r8) 8Q8CE onto  8 a 088dd <<K((Q line ^i 0),C^{i})x  @87X@x  @87X@x  @87X@88 z8( 8(808)8,38)8QJzi8CziK. On the other hand 3 088dd <<r^i(xi)x  @87X@x  @87X@x  @87X@8rzi8(8)83 satisfies Demand Monotonicity (property iii) but typically fails No Exploitation (property ii). In fact  8 W 0388dd <<r^i (xi) satisfies x  @87X@x  @87X@x  @87X@8rzit8 satisfies8(8)8W No Exploitation (and therefore, is a fullfledged csm) if and only if  _ /#xddddddd xA# 2 ` (6) ă9for~all~q epsilon [`0,Q`]: \{q_i=1\} => \{x_i(q)=C(e_i)\}x  @87X@x  @87X@x  @87X@_for_all_q_Q_q_+i _x +i _q/_C_e+i _ k_[_0q_,w_]_:g_{' _1 _} _> _{O _(? _)_(_)g_}_ _ _/$(#(#(#(#!'#$(Indeed No Exploitation for  implies  0E`__Edd <<rx(e_i)=C(e_i).e_i).x  @87X@x  @87X@x  @87X@_x_e+i_C_e2+ir_e+i_(_):_(_)_.B_)_.J_r The class of incremental cost sharing methods (the object of this paper) hinges upon this property, as seen in our next definition.  }*  5. Defining the Incremental Cost Sharing Methods We give three equivalent but formally different definitions: one inductive definition (Def. 2), one constructive definition based on a family of game trees (Def. 3) and one functional definition by means of the acyclicity property (Def. 4). All three definitions are central to the subsequent strategic analysis.  c! The size of a capacity profile . 0$'88dd <<Q epsilon  ^Nx  @87X@x  @87X@x  @87X@8QzzN8 8ױ. is defined as 0J'Jdd <<sigma (Q)=sum_N Q_ix  @87X@x  @87X@x  @87X@%() QM+NQTRiq9I߁. In the  8" following definition the induction bears on $!0 (88 dd <<sigma(Q)x  @87X@x  @87X@x  @87X@8%8(8) 8Q$.  }*"$  Definition 2 Inductive Definition  8p% Fix A0+88dd <<2Q,s.t. sigma(Q) > 0x  @87X@x  @87X@x  @87X@8Q8s8t8Q8,z8.j8.a8(Q8)8>A808%2߯ and Oa0X+88dd <<C epsilon  (Q)x  @87X@x  @87X@x  @87X@8C8Q8 8p8(`8)O. Define (inductively on 50k+88dd << sigma(Q))x  @87X@x  @87X@x  @87X@8%8(8)8) 8Q5 the set IC(Q,C) of incremental cost sharing methods as follows: h #x?ddddd=wdd x# 2 `n (7) ăstack {alignl xi epsilon IC(Q,C) < \{ xi epsilon (Q,C);~ yi epsilon N: Q_i > 0~ \and~~~~~~~~~~~~~ # ~ #~~~~~~~~~~~~ r^{i} (xi) epsilon IC ((Q line ^i 0) C^{i})~\and~r^i (xi) epsilon IC ((Q line^i Q_i 1), C^i)\}}x  @87X@x  @87X@x  @87X@ <   ^^ G^/^ ICKQ;CQC- i N Qv iand2^ri$^IC ^Q i ^C i ^and^ri^ICp^Q8i^Q*i8^Ci(,){(},m);~ : >> 0c^(K^)^(^( ^0 ^)= ^)^(^)^(^(^1H^)^,:^)^}+<  y| ^  ^ X^h`' 0*((A '#u A X%=a '# '#  `Ԍ 8 $(#(#(#(#!'#$Recall that (Q,C) contains a single method if G0  88dd << sigma(Q)=1x  @87X@x  @87X@x  @87X@8%8(8)q81 8Q8G, therefore the above induction is well defined (although it could lead to an empty set IC(Q,C) for some Q).  _ Notice that if for all 0F 88Fdd <<i,j epsilon N, i!= jx  @87X@x  @87X@x  @87X@8i8j8N8i8j8,S8,z8 C8c߁, we have s02 __dd <<partial _{ij}C(0) !=0x  @87X@x  @87X@x  @87X@_,_cr+ij_C_(_0z_)j_0s, then the agent i whose existence is stated by (7) must be unique as well. For this agent i must satisfy property (6) and if two agents i,j satisfy (6) we get  _ #xdddddudd xCJx_i(e_{ij})=C(e_i); x_j(e_{ij}) = C(e_j);~for~all~k != i,j~x_k(e_{ij}) = 0x  @87X@x  @87X@x  @87X@_x+iZ_e+ijb_CR_e+i_x+jZ_e+ijb _CR _e +jj _for*_all_k_i_j_x+k_eZ+ij_(r_)_("_)_;_(r_) _(" _) _;R_,j_(_)_0__b_cr_C$(#(#(#(#!'#$Hence Budgetbalance gives 0<__dd <<C(e_{ij})=C(e_i)+C(e_j)x  @87X@x  @87X@x  @87X@_C_ez+ij _C_ez+i_C_e*+j_(_)_(_)2_(z_)_B_, which we assumed to be impossible. This observation is important for Lemma 2 below. We turn to the constructive definition of the incremental csms. A few preliminary definitions are in order. A binary game tree is a finite tree with a distinguished node called the origin of the tree and denoted 0, such that every non terminal node has exactly two successors denoted left, right, and such that to every non terminal node is attached a player (in N) who has the move (chooses either the left or the right  =` successor).7 Given a binary game tree !088dd <<utheta x  @87X@x  @87X@x  @87X@8u we denote by A088dd <<oWx  @87X@x  @87X@x  @87X@8Wo the set of terminal  _3 nodes and by a0 R__dd <<V_ix  @87X@x  @87X@x  @87X@_V+i the set of non terminal nodes where player i has the move. For  t any node v (terminal or not) we write the path from the origin to v as  _  tt  tXt 5# $XdddddH dd xSP(v)=\{0=v', v^2,...,v^K=v\}~where~v^{k+1} ~is~a~successor~of~v^k, ~all~k=0,..,K1.x  @87X@x  @87X@x  @87X@8P8v8v8v@8vzK 8v 8where 8vCzk8is8a8 successor38of{8v-zkM8all 8kU8K8(z8)j8{808,z28,`8.8.P8.8,2 8}z1}8,80u8,8.e8.8,E818.8Z8czB 8z885$XXd&d&XXd&d&!Xc&$ Xt Finally, for any node v (terminal or not) we write 0__dd <<CV_i(v)=V_i CAP P(v)x  @87X@x  @87X@x  @87X@_V+iZ_v_VB+i_P_v_(_)~_(n_)J__>C to be the set  _` of nodes preceding v where agent i has the move. We call the node of 10]l __]dd <<V_i(v)x  @87X@x  @87X@x  @87X@_V+iZ_v_(_)1  _U farthest away from 0 (on the path P(w)) the last node of 10]t__]dd <<V_i(v)x  @87X@x  @87X@x  @87X@_V+iZ_v_(_)1.  }*  Definition 3 The Family of Trees T(Q)    8? We fix a capacity profile .00^"88dd <<Q epsilon  ^Nx  @87X@x  @87X@x  @87X@8QzzN8 8ױ. and define the set T(Q) of binary game  8) trees 0H#88dd <<tthetax  @87X@x  @87X@x  @87X@8t by the following properties. For all !0vH#88vdd << w epsilon Wx  @87X@x  @87X@x  @87X@8w8W8  the path  8 7A0y $88y dd <<P(w)=\{0=v^1, v^2,..,v^K\}x  @87X@x  @87X@x  @87X@8P8w8v+8v8vzK8(z8)j8{80cz18,z2 8,8.8.t8,8}8Z87 satisfies:  _ i. for all i: a0 %__dd <<IQ_i >0 => V_i(w) != Hx  @87X@x  @87X@x  @87X@_Q+i_VB+i _w_>Z_0J_>_(_)__cr_HI  _ ii. for all i and k=0,...,K1: if <0X\%__Xdd << v^k epsilon V_ix  @87X@x  @87X@x  @87X@_vku_V+i_ < and #0%88dd <<v^{k+1}x  @87X@x  @87X@x  @87X@8vzkzCz1# is the left successor of 0'v"%88'dd <<v^kx  @87X@x  @87X@x  @87X@8vzk,  _ then 0''88'dd <<v^kx  @87X@x  @87X@x  @87X@8vzk is the last node in 10]"'__]dd <<V_i(w)x  @87X@x  @87X@x  @87X@_V+iZ_w_(_)1.  _! iii. for all i: if for all k such that ;!0XP(__Xdd <<v^k epsilon V_ix  @87X@x  @87X@x  @87X@_vku_V+i_ ;, #A0p(88dd <<v^{k+1}x  @87X@x  @87X@x  @87X@8vzkzCz1# is the right successor of a0'#(88'dd <<v^kx  @87X@x  @87X@x  @87X@8vzk  _ # then 10]()__]dd <<V_i(w)x  @87X@x  @87X@x  @87X@_V+iZ_w_(_)1 has exactly 0()__dd <<Q_ix  @87X@x  @87X@x  @87X@_Q+i elements.  _$ This definition implies in particular that for all active agent B0 *__dd <<(Q_i>0)x  @87X@x  @87X@x  @87X@_(Z_>_0J_)_Q +iB  _% and all terminal node w, 10]t+__]dd <<V_i(w)x  @87X@x  @87X@x  @87X@_V+iZ_w_(_)1 must contain at least one and at most 0 +__dd <<Q_ix  @87X@x  @87X@x  @87X@_Q+i nodes;  _& moreover if "!0` ,__dd <<Q_i=0 x  @87X@x  @87X@x  @87X@_Q+i_Z_0" then 1A0] ,__]dd <<V_i(w)x  @87X@x  @87X@x  @87X@_V+iZ_w_(_)1 is empty. P' 0*((1'#  '#/ Xc& PԌWe give a few examples of trees in T(Q). If only one agent is active, say  _ Ua0-__-dd << Q=Q_i.e_ix  @87X@x  @87X@x  @87X@_Q_Q+iJ_e+i__.U, then T(Q) contains a single tree given in Figure 1: player i selects  _ a demand 04__dd <<q_ix  @87X@x  @87X@x  @87X@_q+i by first moving right 0%__dd <<q_ix  @87X@x  @87X@x  @87X@_q+i times then moving left to a terminal node. Figures 2 and 3 give two binary trees in T(Q) respectively for Q=(3,3) and Q=(2,2,2). Figure 2 corresponds (in the bijection described below) to the incremental cost method described by the sequence (211212) and Figure 3 corresponds to the sequence (122313). The reader may find useful to follow the constructions of the next paragraphs (up to Lemma 1) on these Figures.  8{ Now we associate with an arbitrary tree O0 88dd <<theta epsilon T(Q)x  @87X@x  @87X@x  @87X@8~8 8T8QW8(G8)O an incremental cost method  8I . Throughout the construction, a certain cost function P0h 88dd <<C epsilon  (Q) x  @87X@x  @87X@x  @87X@8C8Q8 8p8(`8)P is given. We  8 start with an arbitrary terminal node w of . Consider a non terminal node 0'"688'dd <<v^kx  @87X@x  @87X@x  @87X@8vzk  _ on P(w) where agent i has the move K!0\<__dd <<(v epsilon V_i)x  @87X@x  @87X@x  @87X@_(3_)_vc_V+i_ K. We interpret the fact that #A06! 88dd <<v^{k+1}x  @87X@x  @87X@x  @87X@8vzkzCz1#  8 is the right successor of a0'188'dd <<v^kx  @87X@x  @87X@x  @87X@8vzk as meaning that agent i wants one more unit of good  8 i than what he already accumulated and the fact that #0d88dd <<v^{k+1}x  @87X@x  @87X@x  @87X@8vzkzCz1# is the left successor  8 of 0'88'dd <<v^kx  @87X@x  @87X@x  @87X@8vzk as meaning that he has enough. In this fashion we build a monotonic  8 sequence of demand profiles in [0,Q]. Formally let j0 d88 dd <<P(w)=\{0=v^1,v^2,...,v^K=w\}x  @87X@x  @87X@x  @87X@8P8w8v+8vd8v zK 8w8(z8)j8{80cz18,z2 8,8.8.t8.8,V 8}8Z8f 8j and define inductively  _a #xdddddKdd xA# 2 `> (8) ăAstack {alignl .q^1 =0~\and~for~all~k=1,...,K1: # ~ # alignl .q^{k+1} =q^k + e_i~if~v^k epsilon V_i~\and~v^{k+1}~is~the~\right~successor~of~v^k # ~ # ~~~~~~=q^k~~~~~~~if~v^k epsilon V_i~\and~v^{k+1} ~is~the~\left~successor~of~v^k # ~ # alignl .q^K = q}x  @87X@x  @87X@x  @87X@.101[ , .K . .; , 1 :=.1 1 17.qandsfor3allk K=qk=q5k=e} i%=ifm=vk=VP i=and =vI k =is =the=rightI= successor=of!=vkqLkifLvkV/ i and v( kp isthexleft successor@ofv:k7q<yK7qkk+ k == "x 7o= N A$(#(#a(#(#!'#$Clearly 0E__Edd <<line V_i(w) line  Q_ix  @87X@x  @87X@x  @87X@_ _ _b_V+i_wb_Q+i2_("_)ߗ implies 80=__=dd << q_i  Q_ix  @87X@x  @87X@x  @87X@_q+iZ_Q+i_8 therefore we have just constructed a mapping from W into [0,Q]. In fact this mapping is a bijection with the following  8 inverse mapping. Pick an arbitrary profile [!0V88Vdd <<q epsilon [0,Q]x  @87X@x  @87X@x  @87X@8qS8Q8 8[c808,8][ and construct inductively a path from the origin of the tree to a terminal node  8 ^!#xddddddd xA# 2 `j (9) ăstack {alignl .v^1=0 ~\and~for~all~k=1,...,K1: # ~ # alignl .v^{k+1}~is~the~\right~successor~of~v^k~if~v^k~epsilon V_i~\and~line V_i(v^k) line  q_i # ~ # alignl .v^{k+1}~is~the~\left~successor~of~v^k~if~v^k epsilon V_i~\and~ line V_i (v^k) line  q_i + 1}x  @87X@x  @87X@x  @87X@=.1=0=1[ =, =.K =. =.; =, =1 =:.#1X()^.1^(^)^1=v=ands=for3=all=k =Kv#kcisthekright successor of v#kMifvG#kPVixandViv#kqi^vkc^is^thek^left^ successor3 ^of{ ^v-k^if^vk^V*i^and^V8*i^vkB^q*ik=k=+ =k#8 J kh^ z^ ^^ ^ ^$(#(#(#(#8!!'#$(where A0=lO#88=dd << line A linex  @87X@x  @87X@x  @87X@8 8 b8A denotes the cardinality of A)  8 The above algorithm must stop at a terminal node a0v$88vdd << w epsilon Wx  @87X@x  @87X@x  @87X@8w8W8  (as long as v is non terminal, the algorithm finds a successor to v), hence it defines a mapping from [0,Q] into W. To see that this mapping is precisely the inverse of the mapping from W to [0,Q] defined by (8), one must show first that when q is deduced from w by (8) and/or when w is deduced from q by (9) we have A#x'dddddE dd xA$ 2 ` (10) ă.for~all~i: line V_i(w) line = min (q_i+1, Q_i)x  @87X@x  @87X@x  @87X@_for_all_i_VR+i_w _q2 +i _Qj +i _:_(_)_min: _( _1r _, _)_  _ Z_ _ߗ$(#(#h!(#(#!A'#$We omit the straightforward details.  }*$  Lemma 1 Incremental csm associated with a Tree in T(Q)  8% Given are 0 ,88dd <<oQx  @87X@x  @87X@x  @87X@8Qo, O0U ,88dd <<C epsilon  (Q)x  @87X@x  @87X@x  @87X@8C8Q8 8p8(`8)O and a binary game tree O0,88dd <<theta epsilon T(Q)x  @87X@x  @87X@x  @87X@8~8 8T8QW8(G8)O.  To an arbitrary  8& demand profile [0V -88Vdd <<q epsilon [0,Q]x  @87X@x  @87X@x  @87X@8qS8Q8 8[c808,8][ associate the path 0,88dd <<\{0=v^1,v^2,...,v^K=w\}x  @87X@x  @87X@x  @87X@8{80 z1[8,dz28,,8.8.8.8,8}88z8v8v 8vzK8w by algorithm P' 0*((1'# '#1#! ''#)A PԌ 8     #d6X@8;@#(9) and construct the monotone path !088dd<<%0=q^1  q^2  ...  q^K = q x  @87X@x  @87X@x  @87X@80z1z28.,8.8.88<8888q[8q8qFzK8q by algorithm (8). The cost share of agent i is computed as:  8 _a#xmdddddddxA$ 2 `*  (11) ăstack {alignl x_i (q)= sum from {k=1} to {K1} (C(q^{k+1})C(q^k)).(q_i^{k+1} q_i^k)= sum from {K(i)} C(q^{k+1})C(q^k) # ~ # alignl where~K(i)=\{k line v^k epsilon V_i\}}x  @87X@x  @87X@x  @87X@ax-iZaq5KkaaCQaqkaCaqd k aq% k <i aq?k <iKiaCaqwkWaCGaqk^where^K^i^kZ^v k^V=*ia(a)b51b1a(a(1a):a( a), a) a. a( 1a)(o)na(1ga)a(Ia):^(*^)^{^}Ja52Jau  aaa^ ^ II\^ _$(#(#(#(#8!a'#$This defines a csm pA0 88dd<<xi = psi(theta,C)x  @87X@x  @87X@x  @87X@881888(p8,`8)8Cp in IC(Q,C) (Definition 2). Observe that formula (11) justifies the incremental cost terminology: agent i  _ pays those incremental costs along the path a0*__*dd<<0q_,^1 q_,^2...,q^Kx  @87X@x  @87X@x  @87X@_q_q_qfK1:,2k:,_.L_._.<_,0߭ that are caused by an increase of her demand.  8]  Proof of Lemma 1 Check first that  is in E0D|88dd<< (Q,C)x  @87X@x  @87X@x  @87X@88(8,r8) 8Q8CE. Budget balance is clear  _+ from (11) and so is No Exploitation (if !0P__dd<<q_i=0x  @87X@x  @87X@x  @87X@_q+i_Z_0! then 30*J__*dd<<q_i^k=0x  @87X@x  @87X@x  @87X@_qk:i__03 for all k). Demand  8U Monotonicity for a certain agent i follows from comparing the sequence  0l t88dd<<(q^k)x  @87X@x  @87X@x  @87X@8(8)8q<zk   _? deduced from q by (8) and N0'^88'dd<<( q tilde ^{k'} )x  @87X@x  @87X@x  @87X@8(8)88qzkdd{N deduced from !!0w__dd<<q+e_ix  @87X@x  @87X@x  @87X@_q_e+i_! by (8) and checking that they  _l coincide up to the index k after which A0'*__'*dd<<q_i^kx  @87X@x  @87X@x  @87X@_qk:i remains constant. To show that  is an incremental csm, we use an induction on the length of  _ the tree . Let i be the agent starting  (namely )a0__dd<< 0 epsilon V_ix  @87X@x  @87X@x  @87X@_0_ _Vk+i)). To every demand  _ profile q such that !0 __dd<<q_i=1x  @87X@x  @87X@x  @87X@_q+i_Z_1!, algorithm (8) associates a sequence  0=88dd<<(q^k)x  @87X@x  @87X@x  @87X@8(8)8q<zk  such that 0#__dd<<q^1=0, q^2= e_ix  @87X@x  @87X@x  @87X@_q[_q_e4+i1k_0_,2_<_ߌ  _ and formula (11) yields 0e%__edd<<.x_i(e_i)=C(e_i)x  @87X@x  @87X@x  @87X@_x+iZ_e+i_C _e+i_(*_)_(_)_.߫. Therefore I0 88dd<< r^{i}()x  @87X@x  @87X@x  @87X@8rzizC8(+8)8I and 5!0 88dd<< r^i()x  @87X@x  @87X@x  @87X@8rzi8(8)85 are both  8 in (Q,C) because property (6) holds true. Next denote by A01881dd<< theta^{i}x  @87X@x  @87X@x  @87X@8~zzi and a088dd<<theta^ix  @87X@x  @87X@x  @87X@8~zi the two binary subtrees of  starting respectively after the left move and after the right move from the origin:  _3 #x1Rddddd5iddxA$ 2 `z Z  (12) ă}[stack {alignl ~~~~~~~~~~i # ~ # alignl theta: # ~ # alignl ~~~(theta^{i})~~~~ (theta^i)}x  @87X@x  @87X@x  @87X@iNyiZyi77~:7(7)v7(7)y}$(#(#3(#(#8!'#$One checks easily that 0z "88zdd<<U#theta^{i} epsilon T((Q line ^i 0))x  @87X@x  @87X@x  @87X@88 ~z_8 zi8T8Qzi8(o8(80w8)8)U and 0r"__rdd<<w%theta^i epsilon T((Q line ^i Q_i 1))x  @87X@x  @87X@x  @87X@__ ~i/_T_Q_i_Q/+i_(_(_1o_)_)_ _w and moreover  8| #x #ddddd# EddxA$ 2 `c (13) ăstack {alignl r^{i} (xi)=r^{i}( psi (theta,C))=psi (theta^{i} ,C) # ~ # alignl r^i (xi) = r^i(psi(theta,C))= psi (theta^i,C)}x  @87X@x  @87X@x  @87X@ririCX i C7ryi7ryiT7C yir 7C t77C(+)L(V(:,*))$ ( , )7(7)7(7(7,7)D7)7( 7, 7)11 7f71p7471> 7$(#(#|(#(#!'#$The inductive assumption guarantees that O0'88dd<<psi (theta^{i}) x  @87X@x  @87X@x  @87X@8188((8)zziO and 90c['88cdd<< psi(theta^i)x  @87X@x  @87X@x  @87X@8188(8)zi9 are in ICj0'88dd<<((Q line^i 0))x  @87X@x  @87X@x  @87X@8(8(808) 8)8Qziz8 j  _P" and IC!0o(__dd<<#((Q line^i Q_i 1))x  @87X@x  @87X@x  @87X@_(_(b_1_)R_)_Qi_Q+iz_ _#ߠ respectively (because they are shorter in length than ) and  }*a# the proof of Lemma 1 is complete. QED  8$ We show next that for a fixed function C, DA0p*88dd<<psi(.,C)x  @87X@x  @87X@x  @87X@818(8.8,8) 8CD is actually a bijection from T(Q) into IC(Q,C). To do this we construct its inverse image. To an  8$& incremental cost method  we associate a binary game tree $a0XC,88dd<<phi(xi)x  @87X@x  @87X@x  @87X@8-88(w8)$ by repeatedly applying property (7). So the definition of the game tree is, once again,  8' inductive with the induction bearing on $0 P-88 dd<<sigma(Q)x  @87X@x  @87X@x  @87X@8%8(8) 8Q$.P'0*((1'# aR'#!#'# 'PԌ _ ԙFormally, we assume t0__dd<<partial_{ij} C(q) != 0x  @87X@x  @87X@x  @87X@_,_cr+ij_C_q_(z_)j_0t for all V0mQ88mdd<< i,j, i!= jx  @87X@x  @87X@x  @87X@8i8j8i8j8,z8,j8cV and all M0B__dd<<q  Qe_{ij}x  @87X@x  @87X@x  @87X@_q_Q_ej+ij_z_M. We fix  8 an incremental csm  0. 88.dd<<( xi epsilon IC(Q,C))x  @87X@x  @87X@x  @87X@8(K8(;8,+8)8)88 [8IC8Q8Cߓ and we note that property (7) defines a unique agent i (see the discussion after Definition 2). Now we  8j construct the binary game tree $!088dd<<phi(xi)x  @87X@x  @87X@x  @87X@8-88(w8)$ as follows:  88 n#xW ddddd ddxA$ 2 `  (14) ăJstack {alignl ~~~~~~~~~~~~~i # ~ # ~ # phi (r^{i} (xi))~~~~~phi(r^i(xi))}x  @87X@x  @87X@x  @87X@!i8rzi8rozi8-88-788(88( 8)8)E8(8(8) 8)zn$(#(#8(#(#!'#$By property (7) and the induction assumption, }A0#A 88#dd<<phi(r^{i}(xi))x  @87X@x  @87X@x  @87X@8-88(88( 8)8)8rziz} is in {a0 A 88 dd<<T((Q line^i 0))x  @87X@x  @87X@x  @87X@8Tz8QBzi8(8(80 8)8)8 { and  _  i0+88dd<< phi(r^i(xi))x  @87X@x  @87X@x  @87X@8-88( 8(8)i8)8rzii is in 0U` +__Udd<<4T((Q line^i Q_i 1))x  @87X@x  @87X@x  @87X@_Tz_QBi_Q+i_(_(_1R_)_)_ b_4߱. In particular, note that f0H+__Hdd<<partial _{jj'} C^i != 0x  @87X@x  @87X@x  @87X@_,dd"YE_cr+jjC_Ci_0f and z0w +__wdd<<partial _{jj'} C^{i} != 0x  @87X@x  @87X@x  @87X@_,dd"Yt_cr+jjC_C$i_0z  _ both follow from our assumption T00<__dd<<partial _{jj'} C != 0x  @87X@x  @87X@x  @87X@_,dd"Y_cr+jjC_C3_0T. One checks easily, then, that the composition (14) yields a tree in T(q) (check successively the three properties in Definition 3: we omit the details) and this completes the (inductive)  8` definition of $!0( 88dd<<phi(xi)x  @87X@x  @87X@x  @87X@8-88(w8)$.  }*  Lemma 2   8# Fix qA0B88dd<<Q,C epsilon  (Q)x  @87X@x  @87X@x  @87X@8Q8C8Q8,`8(P8)z8 8q, satisfying the following non singularity assumption  8 &#xdddddmddxB$ 2 ` (15) ăHfor~all~i,j, i!= j,~\and~all~q, q Qe_{ij}: partial _{ij} C(q) != 0x  @87X@x  @87X@x  @87X@_for_all_i_jr_ib_j_andj _all* _q _q _Q _er+ij+ij_Cz_q _,_,_, _,_:_(_)_0_c _ __,j_c&$(#(#(#(#!'#$Then a088dd<<rphix  @87X@x  @87X@x  @87X@8-r and D0: 88dd<<psi(.,C)x  @87X@x  @87X@x  @87X@818(8.8,8) 8CD are inverse bijections from IC(Q,C) into T(Q) and back: :#xzdddddm ddxA$ 2 ` (16) ăstack {alignl for~all~ xi epsilon IC(Q,C): psi(phi(xi),C)=xi # ~ # alignl for~all~ theta epsilon T (Q): phi (psi (theta, C))=theta}x  @87X@x  @87X@x  @87X@wforwallcwICwQwC wC7for7all_7TO7Q 7Cww #w1- w-" w w77 7-717z 7Sw(Cw,3w)w:w( w( w) w, w)7(7)?7:47(>7(" 7, 7) 7)r w 7:$(#(#[(#(#C!'#$   8E Proof  ` ` Both statements are proven by induction on $0 ,d88 dd<<sigma(Q)x  @87X@x  @87X@x  @87X@8%8(8) 8Q$. Throughout the  8 proof C is fixed and we write simply (0$288dd<< psi (theta)x  @87X@x  @87X@x  @87X@8188(8)( instead of I0288dd<< psi(theta,C)x  @87X@x  @87X@x  @87X@8188(8,x8)8CI. We must prove  8 that 088dd<< psi 0 phix  @87X@x  @87X@x  @87X@818-80 and !0D 88dd<< phi 0 psix  @87X@x  @87X@x  @87X@8-8180 are the identity mapping for IC(Q,C) and T(Q) respectively.  8 Show first A088dd<< psi 0 phix  @87X@x  @87X@x  @87X@818-80 is the identity mapping. Pick an arbitrary  in IC(Q,C) and  8} denote La0l88dd<< phi(xi)=thetax  @87X@x  @87X@x  @87X@8-8g88(w8)8L. Denote by i the (unique) agent satisfying (7). By construction  8K of 0j 88dd<<rphix  @87X@x  @87X@x  @87X@8-r, the tree  is given by the composition (14), or equivalently  8 !#x8!ddddd ddx/7theta^{i} = phi(r^{i} (xi))~;~theta^i = phi(r^i (xi))x  @87X@x  @87X@x  @87X@88-4888-_ 8~z8zx8zi8rlzi(zi8r zi8(8(8)8)8;m8( 8( 8)G 8)/߬$(#(#(#(#!!'#$(where Q0el#88edd<<theta^{i}, theta^ix  @87X@x  @87X@x  @87X@88~zzizi8,Q are defined by (12)). Applying 0#88dd<<spsi x  @87X@x  @87X@x  @87X@81s to both sides of these equations, and taking into account the right hand side equations in (13) (note that the left hand side equations of (13) are not proven at this point) we get: A#x  &dddddEddx@stack {alignl r^{i} (psi (theta))= psi(theta^{i})=psi 0 phi (r^{i} (xi)) = r^{i} (xi) # ~ # alignl r^i(psi (theta))= psi (theta^i)= psi 0 phi (r^i (xi)) = r^i (xi)}x  @87X@x  @87X@x  @87X@ri_i r i ri7ryiyi 7r yiq 7r# yi!'/   77 7C(M(1))+()10& ( ( )/ )P(8)7(7(7)z7)7(07)707(! 7( 7) 7)s 7([7)111-G 717j71t7 71*7- 7 7@߽$(#(#(#(#!A'#$where the righthand equalities follow by the induction assumption. Observe that  8~$ a csm  is entirely characterized by the pair 0*88dd<<7r^{i} ( xi), r^i (xi)x  @87X@x  @87X@x  @87X@8rzi8rzizC8(+8)8,8(8)887ߴ and conclude  8h% M0+88dd<<psi(theta)= xix  @87X@x  @87X@x  @87X@818x88(8)8M as desired.  8& To check !0 ,88dd<< phi 0 psix  @87X@x  @87X@x  @87X@8-8180 is the identity of T(Q), pick an arbitrary tree A0\,88dd<<tthetax  @87X@x  @87X@x  @87X@8t in T(Q)  8' and set La0-88dd<< psi(theta)=xix  @87X@x  @87X@x  @87X@818x88(8)8L. Denote by i the agent who has the move at the origin of  (sop'0*((QW '#9 '#0z'#8!'#M#! &'#|)Ap  is given by (12). By (13) we have  8 a#xddddd ddx17r^{i}(xi)= psi (theta^{i})~\and~r^i(xi)=psi (theta^i)x  @87X@x  @87X@x  @87X@8rzizi8and8rszi ziz8z# 8C8(+8)8(18)8( 8)- 8(a 8)881%8; 8 81 81߮$(#(#(#(#!a'#$Apply 0b 88dd<<rphix  @87X@x  @87X@x  @87X@8-r on both sides of these equations and use the induction assumption to get #x0 ddddd ddx6<phi(r^{i} (xi)) = theta^{i}~\and~ phi (r^i (xi)) = theta^ix  @87X@x  @87X@x  @87X@8-888- 8 88(88( 8)8))8( 8( 8) 8)8rziDzi8and8rS zi_ ziz8z{ 86߳$(#(#(#(#!'#$Notice that agent i is the unique agent satisfying (6) (by assumption (15)).  8T Hence the tree %0 s 88dd<<phi (xi)x  @87X@x  @87X@x  @87X@8-88(w8)% is given by (14). On the other hand  is given by (12).  8" We conclude L0` A88dd<< phi(xi)=thetax  @87X@x  @87X@x  @87X@8-8g88(w8)8L as desired. QED  _  Remark 1  Lemma 2 does not hold if O0$__dd<<partial _{ij} C(q)x  @87X@x  @87X@x  @87X@_,r+ij_C_q_(z_)O can be zero, because several  8 distinct trees in T(Q) may yield the same csm: the mapping 0 88dd<<rpsix  @87X@x  @87X@x  @87X@81r is not onetoone  8Z anymore and !0` y88dd<< phi 0 psix  @87X@x  @87X@x  @87X@8-8180 cannot be the identity of T(Q). An example with N={1,2}, Q=(1,1) follows: x#xddddd ddxC(0,1)=C(1,0)=1~;~C(1,1)=2x  @87X@x  @87X@x  @87X@8CZ8CB8C8(80z8,81j8)8(J818,:808)81r8;8(2 81 8," 81 8) 828*8 8x$(#(# (#(#!'#$The two trees in T(Q) are 1 2 2 2 and 1 1  8 They both correspond (via the mapping A088dd<<rpsix  @87X@x  @87X@x  @87X@81r) to the same csm: #xddddd ddxx_i (q)=q_i~for~i=1,2, ~all~q x  @87X@x  @87X@x  @87X@_x+iZ_q_qB+i_for_i_all _q_(_)_1_,_2_,J_"_$(#(#(#(#!'#$We conclude this section with a third definition of IC(Q,C) based on the property of acyclicity of a csm, analog in our framework with indivisible units of output to the acyclicity condition introduced by Satterthwaite and Sonnenschein [1981] and playing a key role in the discussion of cost sharing with divisible input and output by Moulin and Shenker [1992] and Shenker [1993]. One piece of notation will be useful. Given the capacity profile Q and a  _ vector ]a0l"88dd<<q epsilon [`0,Q`]x  @87X@x  @87X@x  @87X@8qi8Q8 8[y808,8]], we denote 0N"__Ndd<<!B(q)=\{i epsilon N \\ q_i < Q_i\}x  @87X@x  @87X@x  @87X@_B_q_i_N_q++i_Qs+i_(z_)j_{3_\{_<_}_Z_ .  Definition 4 Acyclic Cost Sharing Methods  8 Given are 0 %88dd<<oQx  @87X@x  @87X@x  @87X@8Qo, O0U %88dd<<C epsilon  (Q)x  @87X@x  @87X@x  @87X@8C8Q8 8p8(`8)O and a csm r0%88dd<<xi epsilon (Q,C)x  @87X@x  @87X@x  @87X@88 8c8(S8,C8)8Q8Cr. For any demand profile q in [0,Q], we say that  is acyclic at q if we have  8  t  t\t #%\'dddddddxx$ 2 `Z: (17) ăudforall S, S  B (q)~y i epsilon S; x_i ~is~constant~on [q,q+e_{S\\i}] ~ \and~on~[q+e_i,q+e_S`]x  @87X@x  @87X@x  @87X@_z__y;____Sz_Sj_BZ_q_i_S_xc+i _isS _constantk _on_q_q_e++S+i_and_onk_q[_e+i_q_e+S_,_(_)k_;[_[K_,{+\_]_[+_,y_]_ u$\\d&d& \\d&d&!\c&$ \t We say that  is acyclic if it is acyclic for all ]08)88dd<<q epsilon [`0,Q`]x  @87X@x  @87X@x  @87X@8qi8Q8 8[y808,8]].  8% Acyclicity at q means that (for all i!0-+88dd<< (S  B(q))x  @87X@x  @87X@x  @87X@8(8(8)Z8)8Sz8Bj8q8i there is an agent i such that in  _% the interval gA0 +__dd<< [`q,q+e_S`]x  @87X@x  @87X@x  @87X@_[_,f_]_q_q_e+S_g, a0}+__dd<<x_ix  @87X@x  @87X@x  @87X@_x+iis independent of 0z+__dd<<x_jx  @87X@x  @87X@x  @87X@_x+j for all :0f+88fdd<<j epsilon S\\ix  @87X@x  @87X@x  @87X@8j8S8i8 c8\:. px'0*((Q'#a0 '#E '#'# \'c&<)pԌ }*  Lemma 3   _N Given Q and i0 m__dd<<C epsilon  _{imc} (Q) x  @87X@x  @87X@x  @87X@_Cp+imc_Q_ _`_(P_)i (property (3)), for all csm  in E0m88dd<< (Q,C)x  @87X@x  @87X@x  @87X@88(8,r8) 8Q8CE we have #x ddddd ddxS)~is~acyclic~ < ~xi epsilon IC(Q,C)x  @87X@x  @87X@x  @87X@88#8 8is"8acyclic8IC8Q 8C8<t8(d 8,T 8)S$(#(#(#(#!'#$The proof is in the Appendix. Thus acyclicity is a local condition (analog to the cancellation of certain high order derivatives) characterizing the incremental cost methods. It will be key to our first strategic characterization (Theorem 1).  }* 6. Simple Incremental Cost Sharing Methods  On Figure 4 are two typical incremental cost methods with N={1,2,3] and Q=(1,1,1). The method in Figure 4a, is the incremental cost method (1). In the method on Figure 4.b agent 1 still pays his stand alone cost no matter what; yet what happens after agent 1 makes his choice depends upon agent 1's actual demand:  _ if !0__dd<<q_1=0x  @87X@x  @87X@x  @87X@_q+1R_0_!, agent 2 pays her Stand Alone cost; if !!0Y__dd<<q_1=1x  @87X@x  @87X@x  @87X@_q+1R_1_!, agent 3 pays his Stand Alone cost. Intuitively, the csm in Figure 4b is less simple than in Figure 4a because in the latter the acyclicity pattern (whose cost share depends on whose choice) is fixed once and for all, and in the former it is not. This suggests to look at the subset of incremental cost methods where the acyclicity pattern does not vary at all (of which Figures 2 and 3 give two more examples). Given a capacity profile Q, we denote by s a sequence in N with K elements:  8 A0!88!dd<<cs=\{i^1,i^2,..,i^K\}x  @87X@x  @87X@x  @87X@8sz8i8i8iFzK88{ z1[8,dz28,,8.8.8,8}c. The set S(Q) contains those sequences of length $a0 88 dd<<sigma(Q)x  @87X@x  @87X@x  @87X@8%8(8) 8Q$ such  _q that agent i appears exactly 0__dd<<Q_ix  @87X@x  @87X@x  @87X@_Q+i times  8f !#xdddddddxHK=sigma(Q)~\and~for~all~i~ line \{k, 1kK line i^k=i\} line = Q_ix  @87X@x  @87X@x  @87X@_K_QA_and_for_all_i _k _k _K _ick+_i_Qc+i_Q _  _q _a _ __ k__%_(q_) _{ _, _1_}$(#(#f(#(#!!'#$A sequence K0!88dd<<s epsilon S (Q)x  @87X@x  @87X@x  @87X@8s8S8Q8 c8(S8)K can be alternatively described by a monotone path from 0 to   Q, 0'88'dd<<%0=q^1  q^2  .... `q^K = Qx  @87X@x  @87X@x  @87X@80z1z28.,8.8.8.88<88$88q[8q"8qzK8Q with the property [0zQozQdd<<sum_N q_i^k =kx  @87X@x  @87X@x  @87X@9I+Nuq'kaikw[ for all k (the bijection  _! from the set S(Q) into the set of such sequences in given by:  0=@ __=dd<<8q^{k+1}=q^k + e_{i^ k})x  @87X@x  @87X@x  @87X@_qk _qk_e+iddvYk_ _C1_)8ߵ.  }*  Definition 5 Simple Binary Game Trees  8' The subset ST(Q) of T(Q) (Definition 3) is defined by induction on $! 0 4!F#88 dd<<sigma(Q)x  @87X@x  @87X@x  @87X@8%8(8) 8Q$.  _ For any A 0I$88dd<<ts=\{i^1,i^2,...,i^K\}x  @87X@x  @87X@x  @87X@8sz8i8i 8izK88{ z1[8,dz28,,8.8.8.8,8}t in S(Q), denote Ba 0F $__Fdd<<!s^*=\{i_*^1, i_*^2,..,i_*^{K_*}\}x  @87X@x  @87X@x  @87X@_s_i<_i_iK_[::ddu:k_{t1_,2_,_. _._,_}B the subsequence  _; of s obtained by deleting from s all occurrences of agent  0XZ%__dd<<i_1x  @87X@x  @87X@x  @87X@_i+1.  Therefore  80  0OO&88Odd<<<s^* epsilon S((Q line^i 0))x  @87X@x  @87X@x  @87X@8sT8S8Qziz48 8 8(D8(80L8)8)<߹. Denote  0 O&88dd<<is hat = \{i^2,....,i^K\} x  @87X@x  @87X@x  @87X@688sz8i+8izK88{ z2[8,8.K8.8.;8.8,-8}i the subsequence of s obtained by  _! deleting the first term  0U'__dd<<i_1x  @87X@x  @87X@x  @87X@_i+1. Thus !0.9'__.dd<<u#s hat epsilon S((Q line ^i Q_i 1))x  @87X@x  @87X@x  @87X@6__s_SS_Qik_Q+i_ c_(_(_1+_)_)_ ;_u. We define the simple binary game tree (s) associated with s as follows:@+"0*((! '# '#!@Ԍ 8 uA#xdddddddxB$ 2 `  (18) ăastack {alignl ~~~~~~~~~~~~i_1 # ~ # alignl theta(s): # ~ # ~ # ~~~~~theta(s^*)~~~~~theta (s hat)}x  @87X@x  @87X@x  @87X@2i s7s7sS1~ (n ) :67(7)+7(7) 77?y7u$(#(#(#(#!A'#$In the above induction, the initial condition is clear: if G!!0x 88dd<< sigma(Q)=1x  @87X@x  @87X@x  @87X@8%8(8)q81 8Q8G, then ST(Q)=T(Q). Of course the latter equality holds whenever Q contains only one active agent (because T(Q) is then a singleton). Actually, the equality of ST(Q) and T(Q) extends to all "twoperson" trees, namely to all Q where at most two agents are active. To establish this claim,  _ consider a profile Q such that A!0E__Edd<<WQ_1 > 0, Q_2 > 0, Q_i=0 x  @87X@x  @87X@x  @87X@_QB_Qr_Q+i+1_>R_0_,+2 _>_0_,_0B_W for all i3 and take an arbitrary tree  in T(Q). Call w the terminal node of the path where both agents  8 always move right. By Definition 3 the path ka!0 D88 dd<<P(w)=\{0=v^1, v^2,...,v^K=w\}x  @87X@x  @87X@x  @87X@8P8w8v+8vd8v zK 8w8(z8)j8{80cz18,z2 8,8.8.t8.8,V 8}8Z8f 8k  _v contains exactly !0T __dd<<Q_1x  @87X@x  @87X@x  @87X@_Q+1 nodes in !0)__dd<<V_1x  @87X@x  @87X@x  @87X@_V+1 and !0 __dd<<Q_2x  @87X@x  @87X@x  @87X@_Q+2 nodes in !0__dd<<V_2x  @87X@x  @87X@x  @87X@_V+2 (and no other non terminal  _k node: so y"0 __ dd<< K=Q_1+Q_2+1x  @87X@x  @87X@x  @87X@_K_QB_Q__ _z+1+2_1y). The corresponding sequence !"0G88Gdd<<Ts=\{i^1,..,i^{K1}\}x  @87X@x  @87X@x  @87X@8sz8i;8izK8z8{ z1[8,8.K8.8,lz18}T (defined by  _| OA"0__dd<<v^k epsilon V_{i^k}x  @87X@x  @87X@x  @87X@_vku_V+iddfYk_ O) is in S(Q). Check now that La"088dd<<theta=theta(s)x  @87X@x  @87X@x  @87X@88~8b8(R8)8sL. Without loss of generality,  8 assume !"0l88dd<<i^1=1x  @87X@x  @87X@x  @87X@8iz1k818!. The subtree of  starting after the left move from the origin  _w belongs to u"05__5dd<< T((0,Q_2))x  @87X@x  @87X@x  @87X@_Tj_Q_(_(z_0_,+22_)_)u (see (12)) therefore must coincide with 7"0b588bdd<< theta(s^*)x  @87X@x  @87X@x  @87X@8~8(8)8sz7 (because u"05#__5dd<< T((0,Q_2))x  @87X@x  @87X@x  @87X@_Tj_Q_(_(z_0_,+22_)_)u  8  contains only one tree). Repeat the argument for the node #0 88dd<<v^2x  @87X@x  @87X@x  @87X@8vz2 obtaining after  8r a right move from the origin: the subtree starting after the left move from !#0"88dd<<v^2x  @87X@x  @87X@x  @87X@8vz2 is unambiguous. And so on, until the whole tree  is unambiguously determined. Figure 2 illustrates this construction. Figures 4a 4b show that ST(Q) is a strict subset of T(Q) as soon as three  _ or more agents are active. If each capacity A#0D__dd<<Q_ix  @87X@x  @87X@x  @87X@_Q+i is one, a tree in ST(Q) is characterized by an ordering of N (thus there are n! simple trees) whereas the set T(Q) contains many more trees when n3 (see Remark 2 for a precise count). For any capacity profile Q and any sequence s in S(Q), the construction of  8 the binary game tree $a#0 88dd<<theta(s)x  @87X@x  @87X@x  @87X@8~8(n8)8s$ is similar to that given two paragraphs above: the  8W path #0v 88dd<<\{0=v^1,v^2,...,v^{K+1}\}x  @87X@x  @87X@x  @87X@8{80 z1[8,dz28,,8.8.8.8,=z18}8zz8v8v 8vzK where all agents always move right follows the  _A sequence s in the sense that O#0`!__dd<<v^k epsilon V_{i^k}x  @87X@x  @87X@x  @87X@_vku_V+iddfYk_ O for all k=1,..,K. The inductive property  8R (18) allows to complete the construction of $#0q"88dd<<theta(s)x  @87X@x  @87X@x  @87X@8~8(n8)8s$. Figure 3 provides an illustration. In the subsequent strategic analysis, the subset of incremental cost sharing methods associated with a simple binary game tree plays an important role. We call it the set of simple incremental methods and denote it SIC (Q,C):  8c thus #0' &88' dd<<xSIC(Q,C)=psi(ST(Q),C)x  @87X@x  @87X@x  @87X@8SIC8Q8CT8ST8Q$8Cz8(j8,Z8)8(D8(48)8,8)8J81x (for any given cost function C). In those methods the pattern of acyclicity (Definition 4) is especially simple. Fix a sequence  _! $0h *'__h *dd<<s=\{i_,^1...,i^K\} \in~ ST(Q)x  @87X@x  @87X@x  @87X@_sz_i;_iK_in_STe_Q__{ 1:,[_._.K_._,=_}_(_) and let  the corresponding csm in SIC(Q,C)  8# !$0C!)88Cdd<<H(xi = psi(theta(s),C))x  @87X@x  @87X@x  @87X@8(8(8(8)P8,@8)8)8r81|88`8s8CH. Given an arbitrary demand profile q, compute for all i the  _# index k(i) at which the demand A$0)__dd<<q_ix  @87X@x  @87X@x  @87X@_q+i is met: k(i) is defined by the two properties  _$ a#x*ddddd ddxkDi^{k(i)} = i~\and~line \{k line k  k(i), i^k = i\} line  q_ix  @87X@x  @87X@x  @87X@_ikCi[_i+_and_k{_kk_k[_i _iu k= _i _qu +i();_{_(_)K _, _}__ +_ _ _- _ } _k$(#(#$(#(#!a'#$(the inequality is strict if !a$0-__dd<<q_i=0x  @87X@x  @87X@x  @87X@_q+i_Z_0!). Then in any coalition i$0-88dd<< S,S  B(q)x  @87X@x  @87X@x  @87X@8S8S8B8q8,j8(Z8)z8i, the agent@a'0*((!'#g A*'# -a@ i with the smallest index k(i) satisfies property (17). We call the cost sharing method (1) an elementary incremental method (there are n! such methods obtained by varying the ordering of the agents). It is the simple incremental method corresponding to the sequence 1,..,1,2,..,2,3,.. where  _C the first $0b __dd<<Q_1x  @87X@x  @87X@x  @87X@_Q+1 terms are agent 1, the next $0b __dd<<Q_2x  @87X@x  @87X@x  @87X@_Q+2 terms are agent 2 and so on. As soon as at least one agent has a capacity of at least two, not all simple incremental methods are elementary (Remark 2 shows the difference in the cardinality of these two sets). Clearly the pattern of acyclicity is constant (over all q) for an elementary incremental method. In fact this property characterizes the set of elementary methods among all simple incremental methods, and even among all incremental methods (we omit the straightforward proof).  }*  Remark 2 Counting incremental methods and simple incremental methods  The cardinality of ST(Q) (and of SIC(Q,C), provided C is non singular: assumption (15)) is given by a simple formula:  8e $#xddddd NddxAline ST(Q) line = mu (Q)= {(sum_N Q_i)!} over {Q_1 ! Q_2!...Q_n!}x  @87X@x  @87X@x  @87X@!  }qSTQQY/NQ` Vi;_Q{_Q# _Q +na(Q)()( )( !+1_!+2C_!_.3 _. _. _! }=I$$(#(#e (#(#!'#$The cardinality &$0 n88dd<< lambda (Q)x  @87X@x  @87X@x  @87X@88(}8)8Q& of T(Q) follows a recursive formula deduced from (12):  _ &#xkddddd- ddxRlambda(Q)= sum from {i epsilon N} lambda((Q line^i 0)). lambda ((Q line^i Q_i 1))x  @87X@x  @87X@x  @87X@+ (})(w(0))o.b(( 1* ) )Qm+i+NQ!iR Q !ij Q ig   : oI&$(#(#(#(#C!'#$with the initial condition ~%0 <__ dd<<lambda(Q_i e_i)=1x  @87X@x  @87X@x  @87X@__(_)_1_Q+i_eU+i_~. This gives easily !%0l88ldd<<lambda(Q)= mu (Q)x  @87X@x  @87X@x  @87X@8m88(}8)8(8)8Qi8Q8 whenever at most two agents are active. However, with three or more active agents, the  8 number %A%0l88dd<< lambda(Q)x  @87X@x  @87X@x  @87X@88(}8)8Q% grows astronomically faster than !a%088dd<<mu(Q)x  @87X@x  @87X@x  @87X@88(8)8Q!. For instance compare: (1,1,1)=12 (1,1,1)=6 (1,1,1,1)=576 (1,1,1,1)=24 (1,1,1,1,1)=1,658,880 (1,1,1,1,1)=120 (footnote 9) (2,2,2)=5,184 (2,2,2)=90 (2,2,1,1)=1 191,024 (2,2,1,1)=180  =  (2,2,2,2)%0  88dd<<uSIMEQ x  @87X@x  @87X@x  @87X@8su2.1013 (2,2,2,2)=2,520  }*  7. Cross Monotonicity Given a cost function C with increasing marginal costs (property (3)), we say that a certain csm is cross monotonic if agent i's cost share is non  8 decreasing in agent j's demand. For any r%0$88dd<<xi epsilon (Q,C)x  @87X@x  @87X@x  @87X@88 8c8(S8,C8)8Q8Cr this is the property: #x%dddddmddxg$ 2 ` (19) ăy@for~all~i,j, i!= j, ~all~q,q Qe_j: partial_j x_i (q)  0x  @87X@x  @87X@x  @87X@_for_all_i_jr_ib_j_allj _qZ _qJ _Q: _e +j +j2_x+iz_q _,_,_, _, _:_(_)_0_c _ _ _,j_y$(#(#(#(#!'#$This expresses a burden sharing requirement: the cost increase when agent  _" j's consumption raises from %0(__dd<<q_jx  @87X@x  @87X@x  @87X@_q+j to "%0%(__dd<<q_j +1x  @87X@x  @87X@x  @87X@_q+j_Z_1" can be attributed in part to agent i's  _# consumption, because &0 )__dd<<VDELTA =C(q+e_j)C(q)x  @87X@x  @87X@x  @87X@___K_#_C_q_e+j_C_q_(_);_(+_)V increases in !&0)__dd<<q_ix  @87X@x  @87X@x  @87X@_q+i (property (3)). Cross Monotoncity requires agent i to bear a (non negative) share of : that is to  _S% say, it does not allow agent i to benefit when A&0 r+__dd<<q_jx  @87X@x  @87X@x  @87X@_q+j increases. The CM property is key to the existence of a strong equilibrium of the demand game (Lemma 7).  _'  Lemma 4  Given are Q and a&0<-__dd<<C IN  _{imc} (Q,C)x  @87X@x  @87X@x  @87X@_C+imc_Q_C__w_(g_,W_)߅. All simple incremental methods (allP'0*((1'#'#%'#'P  in SIC(Q,C)) satisfy Cross Monotonicity. An incremental method that is not simple (namely, a csm  in IC(QC)\SIC(Q,C)) may or may not meet Cross Mononicity. Lemma 4 implies in particular that when at most two agents are active all incremental methods are cross monotonic (indeed, SIC(Q,C)=IC(Q,C) in that case).  }*C  Proof  ` ` Fix an arbitrary element  in SIC(Q,C), two agents i,j and a demand  _ profile k&0% __dd<<q,q  Qe_jx  @87X@x  @87X@x  @87X@_q_q_Q_eb+j_,z_j_k. Use (9) and (8) to construct the monotone path r&0 88dd<<q^k , 1  k  Kx  @87X@x  @87X@x  @87X@8qzk|8kl8K8,8188r  _ from 0 to q and the monotone path &0< 88<dd<<q tilde^k , 1  k  K'x  @87X@x  @87X@x  @87X@688qzk|8kl8K8,8188zߛ from 0 to !&06 __dd<<q+e_jx  @87X@x  @87X@x  @87X@_q_e+j_!. Note that K'=K+1  _  unless V'0-l+ __-dd<< q_j=Q_j1x  @87X@x  @87X@x  @87X@_q+jZ_Q+j_*__1V in which case K'=K (by formula (10)). Let k be the last index  _ in K(j) (for the profile q): thus the node !'0' 88'dd<<v^kx  @87X@x  @87X@x  @87X@8vzk associated with A'0' 88'dd<<q^kx  @87X@x  @87X@x  @87X@8qzk is in a'0!< __dd<<V_jx  @87X@x  @87X@x  @87X@_V+j and  8 #'0188dd<<v^{k+1}x  @87X@x  @87X@x  @87X@8vzkzCz1# is left of '0' 188'dd<<v^kx  @87X@x  @87X@x  @87X@8vzk, and X'0 188 dd<< q^{k+1}=q^kx  @87X@x  @87X@x  @87X@8qzk 8qzkz8Cz1X. The path '0'U188'dd<< q tilde ^kx  @87X@x  @87X@x  @87X@688qzk coincides with (0'188'dd<<q^kx  @87X@x  @87X@x  @87X@8qzk up to k and differs thereafter #xddddd-ddxO]q tilde ^{k+1} = q^k + e_j~;~q tilde^k' = q^k' + e_j~\or~q^{k'1} + e_j ~ for~all~k'  k+1x  @87X@x  @87X@x  @87X@6___qk _qk_e+j}_q/k(_qk_eS +j _orC _q km _e +j_forU_all_kJ_k_ _dd_dd:[_dd4 U  ___C1_; 1:_1O$(#(# (#(#!'#$Indeed the order in which all agents in N\j are called upon to move is exactly  _ the same at q and at !!(0 __dd<<q+e_jx  @87X@x  @87X@x  @87X@_q_e+j_! (it is given by the reference sequence JA(0i88dd<<s epsilon S(Q)x  @87X@x  @87X@x  @87X@8s8S8Q8 c8(S8)J from  _ which  is derived). Notice that in the path a(088dd<<v tildex  @87X@x  @87X@x  @87X@688v associated with !(0__dd<<q+e_jx  @87X@x  @87X@x  @87X@_q_e+j_!, agent j  _ has the move once more after k (unless g(0__dd<< q_j=Q_j1)x  @87X@x  @87X@x  @87X@_q+jZ_Q+j_*__1_)g and goes left (after which we  _ have (0B-__B-dd<<aq tilde ^k' = q^{k'1} + e_j)x  @87X@x  @87X@x  @87X@6__qk_qNk_eg+jdd$E_ddo_1_)a.  _ Comparing the two summations (11) giving respectively 1(0] __]dd<<x_i(q)x  @87X@x  @87X@x  @87X@_x+iZ_q_(_)1 and  _ f)0__dd<< x_i(q+e_j)x  @87X@x  @87X@x  @87X@_x+iZ_qJ_e+j_(_)_f, we can compute their difference as  _ /#xdddddddxx_i(q+e_j)x_i(q)= sum from {k' epsilon K(i),k'>k} \{(C(q tilde ^{k'+1}) C(q tilde ^k' )) (C(q tilde ^{k'+1} e_j)C(q tilde ^k'e_j))\}x  @87X@x  @87X@x  @87X@xiZqJej xiRq+k{+K+i +k +kS CC q =kCq=kCqi=kejCqd=k]ej()()+(k+)+, +>c { ( ( =1 )]())p(`(:=1):(-))}BddYddk Ydd4 kU =mddkddk=JddkI;+ g /$(#(#(#(#C!'#$Thus the assumption of increasing marginal costs guarantees !)0 __dd<<partial_j x_i(q) 0x  @87X@x  @87X@x  @87X@_,_r+j_xB+i _q_(_)r_0߃. Note  8 that the summation can be empty (if K(i) is contained in EA)088dd<< [`1,k^*`]x  @87X@x  @87X@x  @87X@8[818,8]8k!zE) in which case  _ a)0__dd<<partial_j x_i (q)=0x  @87X@x  @87X@x  @87X@_,_r+j_xB+i _q_(_)r_0߀. This proves the first statement of Lemma 4. To prove the second statement, the example in Figure 4.b will be enough. We have N={1,2,3}, Q=(1,1,1) and  is given by:  _  !#xY!dddddeddxstack {alignl x_1(q)=C(q_1,0,0) # ~ # alignl x_2 (q) = C(0, q_2,0)~~~~~~~~~~~~~~~~if~ q_1=0 # ~ # ~~~~~~=C(1,q_2,q_3)C(1,0,q_3)~~if~q_1=1 # ~ # alignl x_3(q)=C(0,q_2,q_3)C(0,q_2,0) ~~if~q_1=0 # ~ #~~~~~~ =C(1,0, q_3)C(1,0,0)~~~~if~q_1=1}x  @87X@x  @87X@x  @87X@xRqCqxRqCqJ if q-C-q-q-CR -qB -if -qxRqCqqCr qR if q_Cr_q*_CJ _if _q1()2("1r,0b,0R)`2()2(0",`2b,0R) `10"-(-1-,2R-,B3-)-(r-1-,b -0 -, 3 -)1-13()2(0",2b,R3) (0, 2: , 0* )10_(_1 _,_0_,+3:_)_(_1_, _0 _, _0r _) +1_1BBZ2- -R-Bb*__Z_ $(#(#(#(#!!'#$One checks easily that M)0 )__dd<<partial _i x_1=0x  @87X@x  @87X@x  @87X@_,_r+i_x:+1_0M for 1)0}-)88}dd<<i=2,3x  @87X@x  @87X@x  @87X@8i882z8,831, that P)0f)__dd<<partial_i x_2 0x  @87X@x  @87X@x  @87X@_,_r+i_x:+2_0P for i=1,3 and that  _X$ R)0w*__dd<<partial _2 x_3  0x  @87X@x  @87X@x  @87X@_,_r+2:+3_0_xR. Moreover the inequality *0w*__dd<<partial_1 x_3 (q)  0x  @87X@x  @87X@x  @87X@_,_r+1:+3_(z_)j_0_x_q߅ holds, except perhaps at q=(0,1,1):PX$0*((1'#'#!'#j)!PԌ _  A#xdddddddx9partial _1 x_3(0,1,1)=C(1,0,1)+C(0,1,0)C(0,1,1)C(1,0,0)x  @87X@x  @87X@x  @87X@_,_ _B _z_r+1:+3_(_0z_,_1j_,_1Z_)_(:_1_,*_0_,_1_) _(r _0 _,b _1 _,R _0 _)2_(_0"_,_1_,_1_)j_(_1Z_,_0J_,_0:_)_xJ_C _C _C_C $(#(#(#(#!A'#$ t Clearly when C varies in !*0t__dd<< _{imc} (1,1,1)x  @87X@x  @87X@x  @87X@_+imc_(_1w_,_1g_,_1W_)߁ this quantity may be positive or negative. QED.  t   }*8  Remark 3   _ For any csm  in IC(Q,C), any A*0v 88vdd j epsilon Nx  @87X@x  @87X@x  @87X@8j8N8  and any na*0 __ddq, q  Q e_jx  @87X@x  @87X@x  @87X@_q_q_Q_eb+j_,z_j_n, the following property holds true  }* a#x6dddddudd!A$ 2 ` (20) ăNg\{ yi epsilon N\\j: partial _j x_i (q) < 0 \} => \{ y i' epsilon N\\j: partial_j x_{i'} (q) > 0\}x  @87X@x  @87X@x  @87X@_{S_\C_:;_(+_)_<_0_}_>_{ _\q _:_(_)_>r_0_}_y_, _s _y|  _,ddqY_i_N_j+jk_x+i_q _i _N _jI +j _x+i _qz_  _ N$(#(# (#(#!a'#$ This property is used in the proof of Lemma 7. To prove (20) consider the  8Z monotone path *0'( y88'dd<<q^kx  @87X@x  @87X@x  @87X@8qzk, k=1,...,K corresponding to the demand profile q. The effect  _D on *0__dd<<x_jx  @87X@x  @87X@x  @87X@_x+j of increasing his demand to !*0%__dd<<q_j+1x  @87X@x  @87X@x  @87X@_q+j_Z_1! is to add the term *0c__dd<<SC(q^k + e_j)C(q^k)x  @87X@x  @87X@x  @87X@_C_qk|_e+j<_C,_qk_(L_)_(._)__S in the summation (11), where k is the last index in K(j) (for the profile q). Therefore, increasing marginal costs imply: :#xdddddJddxUpartial_j x_j (q)=C(q^k+e_j)C(q^k)  C (q+e_j)C(e_j)= partial_j (sum _N x_i) (q)x  @87X@x  @87X@x  @87X@,d$   V,rRjxBRj qrCbqke\RjCq> k~ Cn q^ e RjCeRj.Rj+NYxRiq()()( ) (. )()~())()9I:$(#(#(#(#!'#$Property (20) follows at once.  }*4 8. Variable Cost Functions and Continuity One of our characterization results (Theorem 4) uses a property of continuity of the cost shares with respect to the cost function itself. Formally, this requires to expand the set of objects under scrutiny.  }*  Definition 6   _l Fix a capacity profile Q in +088dd<< ^N x  @87X@x  @87X@x  @87X@8zN and a subset 6!+0bt__bdd<<  _0(Q)x  @87X@x  @87X@x  @87X@_+0_(_)__Q6 of $A+0f88dd<< (Q)x  @87X@x  @87X@x  @87X@88(8)8Q$. A cost  _} sharing mechanism (csm) is a mapping  from a+0^ __^dd<<#[`0,Q`] .  _0(Q)x  @87X@x  @87X@x  @87X@_[_0_,_]_.+0_(_)_Q[_Q_#ߠ into +0* __*dd<<  _+^Nx  @87X@x  @87X@x  @87X@_:N associating  8 with each cost function C a cost sharing method !+0p!88dd<<xi(C)x  @87X@x  @87X@x  @87X@88(r8)8C! in E+0!88dd<< (Q,C)x  @87X@x  @87X@x  @87X@88(8,r8) 8Q8CE (Definition 1).  _u We denote the corresponding cost shares as S+0M|"__Mdd<<x_i(q;C)x  @87X@x  @87X@x  @87X@_x+iZ_qJ_C_(_;_)S. The space of all cost  _j sharing mechanisms is denoted 6,0]h#__]dd<< _0 (Q)x  @87X@x  @87X@x  @87X@_+0_(_)Z_Q6. We abuse notations when we use the same letter  and the same abbreviation csm to speak of cost sharing methods (Definition 1) or mechanisms (Definition 6). This will not lead to confusion, however. The following property is normatively compelling. It rules out the possibility that microscopic variations of the cost function have a macroscopic effect on cost shares.  _>$ Continuity: the csm c!,0. ]*__.dd<<xi epsilon _0 (Q)x  @87X@x  @87X@x  @87X@__ _c+0_(_)+_Qc is continuous if for all i, all q, SA,0M"]*__Mdd<<x_i(q,C)x  @87X@x  @87X@x  @87X@_x+iZ_qJ_C_(_,_)S is  _3% continuous in aa,0;( R+__;dd<<C epsilon  _0(Q)x  @87X@x  @87X@x  @87X@_C8_Q_ _p+0_(_)a. Notice that C varies in a vector space of finite  _(& dimension, therefore the topology of ,0$G,__dd<< _0x  @87X@x  @87X@x  @87X@_+0 is unambiguous.  _' Consider a csm  such that for all C in 6,0b-__bdd<<  _0(Q)x  @87X@x  @87X@x  @87X@_+0_(_)__Q6, (C) is an incrementalP'0*((1'#?A6'#ra'#7P  8 method, ,088dd<<&xi(C) epsilon IC(Q,C)x  @87X@x  @87X@x  @87X@88 8(r8);8(+8,8)8CK8IC8Q8C&ߣ. If (C) is derived from the same tree  in T(Q) for all  8 ,088dd<<oCx  @87X@x  @87X@x  @87X@8Co (namely -0S88Sdd<<'xi (C)= psi (theta,C)x  @87X@x  @87X@x  @87X@8b81l88(r8)8(8,8)8CP8C8'ߤ for all C), then  is surely continuous in C: in the  8 summation (11), the monotone path !-0'88'dd<<q^kx  @87X@x  @87X@x  @87X@8qzk depends on  and on q but not on C,  _ therefore SA-0M__Mdd<<x_i(q,C)x  @87X@x  @87X@x  @87X@_x+iZ_qJ_C_(_,_)S is actually linear in C.9 Lemma 5 below shows the converse property: only those incremental methods derived from a fixed tree (the same for all cost functions) are continuous (provided we assume increasing marginal costs).  }*  Definition 7   _e Given Q and a subset 6a-0b< __bdd<<  _0(Q)x  @87X@x  @87X@x  @87X@_+0_(_)__Q6 of $-0. 88dd<< (Q)x  @87X@x  @87X@x  @87X@88(8)8Q$, an incremental mechanism on 6-0b\! __bdd<<  _0(Q)x  @87X@x  @87X@x  @87X@_+0_(_)__Q6  _Z is a cost sharing mechanism b-0.y__.dd<<xi epsilon _0(Q)x  @87X@x  @87X@x  @87X@__ _c+0_(_)+_Qb (Definition 6) that is derived from a  8O certain binary game tree O-0tn88dd<<theta epsilon T(Q)x  @87X@x  @87X@x  @87X@8~8 8T8QW8(G8)O #x<ddddd ddxA$ 2 ` (21) ă7for~all~C epsilon  _0 (Q)~~~ xi (C)= psi (theta, C)x  @87X@x  @87X@x  @87X@_for_all_C_Q_C _C _ _ _1 _k_ _+0@_(0_) _( _) _(v _,f _)߀$(#(# (#(#!'#$We say that  is a simple incremental mechanism if, moreover,  is a simple tree,  8` Q.0J88Jdd<<theta epsilon ST(Q)x  @87X@x  @87X@x  @87X@8~8 8STG8Q8(8)Q. We write IC(Q) (resp. SIC(Q)) for the set of incremental mechanisms (resp. simple mechanisms). Thus equation (21) defines a bijection from T(Q) into IC(Q) (and from ST(Q) into SIC(Q)).  }*#  Lemma 5   _q Fix Q, assume the cost function varies in =!.0p__dd<< _{imc} (Q)x  @87X@x  @87X@x  @87X@_+imc_Q_(w_)= and consider a cost  _f  t sharing mechanism iA.0 __dd<<xi epsilon _{imc} (Q)x  @87X@x  @87X@x  @87X@__ _c+imc_QS_(C_)i. We have:  tXX 2#(#9Xzddd""ddxq.i 2  (22)  2   2  Lu\{xi epsilon IC(Q)\} < \{ xi~is~continuous~\and (forall C epsilon  _{imc} (Q): xi(C) epsilon IC(Q,C))\}]x  @87X@x  @87X@x  @87X@_{K_(;_)_}_{ _(_(_)b_:J_(:_)_(_,_)[_)_}K_]__ <_$_ __ [_IC_Q_isL_ continuousT _and_C +imcr_Q_C_IC{_Qk_C+_<4_z_L2$XX%%[XX%%!X%$ XX #xddddmm ddxB$ 2 `d (23) ă*T\{ xi epsilon SIC (Q)\} < \{ xi epsilon IC(Q) \and~ xi~is~cross~monotonic\}x  @87X@x  @87X@x  @87X@8{8(8)+8}<8{u8(e8)8}88 8$8  8[8SIC;8Q8IC8Q8ande 8is 8cross]8 monotonic8<*$(#(#E(#(#!'#$(where " is CM" means "(C) is CM for all C")   }*/ Proof of Property (22)   _} Fix  continuous and such that for all C in <a.08"__dd<< _{imc}(Q)x  @87X@x  @87X@x  @87X@_+imc_Q_(w_)<, .0S"88Sdd<<&xi(C)= psi(theta, C)x  @87X@x  @87X@x  @87X@8b81l88(r8)8(8,8)8CP8C8&ߣ for  8r some .0#88dd<<tthetax  @87X@x  @87X@x  @87X@8t in T(Q). We must show that  is independent of C. Suppose it is not.  8@ Denote ).0l_$88dd<< Gamma(theta)x  @87X@x  @87X@x  @87X@888(g8)) the subset of cost functions corresponding to the tree .0>_$88dd<<tthetax  @87X@x  @87X@x  @87X@8t. Since  _ T(Q) is finite and =/0 -%__dd<< _{imc} (Q)x  @87X@x  @87X@x  @87X@_+imc_Q_(w_)= is connected, one of the sets )!/0:-%88dd<< Gamma(theta)x  @87X@x  @87X@x  @87X@888(g8)) is not closed.  _ That is to say, there exists a sequence A/0P"&__dd<<C_tx  @87X@x  @87X@x  @87X@_C+t in  a/0"&__dd<<  _{imc}x  @87X@x  @87X@x  @87X@_+imc , t=1,2,... converging to /0""&__dd<< C_infinityx  @87X@x  @87X@x  @87X@_C+  _ (also in  /043'__dd<<  _{imc}x  @87X@x  @87X@x  @87X@_+imc ) and two different trees ,/0'88dd<<theta, theta^*x  @87X@x  @87X@x  @87X@88~8,bz, in T(Q) such that:  8 " #x((dddddyddx%Ufor~all~t=1,2,.. xi(C_t)= psi(theta^*,C_t)~\and~xi(C_infinity)=psi(theta, C_infinity)x  @87X@x  @87X@x  @87X@_for_all_t:_C+t8 _C +t _and_C&_C _ _p +_+_1_,r_2_,b_._._( _) _( _, _)_(H_)_(_,_)R_ _1 __8_1B_%ߢ$(#(# "(#(#!'#$Denote by /0*88dd<<xi^*x  @87X@x  @87X@x  @87X@8z the incremental mechanism associated with 00I*88dd<<theta^*x  @87X@x  @87X@x  @87X@8~z (for all C,  _% !00+88dd<<Mxi^* (C)= psi(theta^*, C)x  @87X@x  @87X@x  @87X@8818z:8(z8(8)D8(x8,h8)J8C8CM). Because  and A00+88dd<<theta^*x  @87X@x  @87X@x  @87X@8~z differ, Lemma 2 implies that ;a00MD+__Mdd<<xi(C_infinity)x  @87X@x  @87X@x  @87X@__(_)_Cr+; and  _& N00,__dd<<xi^*(C_infinity)x  @87X@x  @87X@x  @87X@_+_(_)J_CN are two different csms in IC(Q,C). Thus there exist an agent i and a demand profile q such that`'0*((A<'#\Xz%d'#o(('#d*`Ԍ _ +!#xddddd*ddx,x_i (q, C_infinity) != x_i^* (q, C_infinity)x  @87X@x  @87X@x  @87X@_x+iZ_qJ_C_x:i[_qK_C_(_,_)_(_,_)+_c++$(#(#(#(#!!'#$Because 0088dd<<xi^*x  @87X@x  @87X@x  @87X@8z is continuous, and because 00M__Mdd<<4xi^*(C_t)= xi(C_t)x  @87X@x  @87X@x  @87X@_ ___(_)z_(_)J_C+t_Cr+t4߱ for all t, we have: /A#xK ddddd/ddxKx_i^* (q,C_infinity)={lim from t}~ x_i^* (q,C_t)={lim from t} ~x_i (q,C_t)x  @87X@x  @87X@x  @87X@xikq[C+txSi,qCth +t x i q CTtdd (,#)lim(,) liml (\ ,)/$(#(#(#(#C!A'#$Hence a contradiction of the continuity of . This concludes the proof of statement <= in property (22). The statement => has been checked before Definition 7.  }*  Proof of Property (23) Statement => follows from Lemma 4. To prove statement <= we fix  in IC(Q)  8 derived from a certain tree O0088dd<<theta epsilon T(Q)x  @87X@x  @87X@x  @87X@8~8 8T8QW8(G8)O and we assume that  is not simple (Definition 5): then we show that  is not cross monotonic.  _ As usual we use an induction on $10 88 dd<<sigma(Q)x  @87X@x  @87X@x  @87X@8%8(8) 8Q$. Without loss of generality, assume )!10l$__dd<< 0 epsilon V_1x  @87X@x  @87X@x  @87X@_0c+1_ _V)  8 (player 1 has the first move in A10088dd<<tthetax  @87X@x  @87X@x  @87X@8t). If one of the trees a101!881dd<< theta^{1}x  @87X@x  @87X@x  @87X@8~zz1 or 1088dd<<theta^1x  @87X@x  @87X@x  @87X@8~z1 (given by  8| (12)) is not simple, then by the inductive assumption the corresponding csm 105"885dd<<xi^{1}x  @87X@x  @87X@x  @87X@8zz1  8f or 1088dd<<xi^1x  @87X@x  @87X@x  @87X@8z1 is not cross monotonic and we are done (we omit the straightforward  8P details). Assume now that both 1010o881dd<< theta ^{1}x  @87X@x  @87X@x  @87X@8~zz1 and 20Uo88dd<<theta^1x  @87X@x  @87X@x  @87X@8~z1 are simple. They are described by  _: two sequences s and s', respectively in |!20 PY88 dd<<S((Q line ^1 0))x  @87X@x  @87X@x  @87X@8Sz8Q8(8(Bz180 8)8)8 | and A20MQY__Mdd<<5S((Q line ^1 Q_1 1))x  @87X@x  @87X@x  @87X@_Sz_Q_Q_(_(B1 +1_1J_)_)_ Z_5߲. Of course  _K s' contains Ca20` j__dd<<(Q_11)x  @87X@x  @87X@x  @87X@_(+1_1B_)_QR_C more elements than s (corresponding to the occurrences of agent 1). Let s" obtain from s' by deleting all occurrences of agent 1, so that  8 20W88Wdd<<>s" epsilon S((Q line ^1 0))x  @87X@x  @87X@x  @87X@8s\8S8Qz<8 8 8(L8(z180T8)8)>߻. If s"=s then the tree  is simple so we must have s"20"88dd<<q!=x  @87X@x  @87X@x  @87X@8cqs: we call k the first index where they differ  _x (a#xdddddddxstack {alignl s=(i^1, i^2,....,i^{k1}, j,...) # ~ # alignl s"=(i^1, i^2,..., i^{k1}, i,...) ~with~i,j,1~all~different # ~ # alignl we~set~ q = sum from {t=1} to {k1} e_{i^ t}}x  @87X@x  @87X@x  @87X@)sz)i)i)ikk})jsiDi}ikvi with ijallF differentweZsetq k +t1eidd"t)ek^ZZ+)( k1[),dk2),,).).).). ),k1),),m ). ).] ). ))s(|1,2%,...,1,,f . .V . )N,>,11+1I($(#(#x(#(#!a'#$We notice that O20 #__dd<<q  Q e_{ij}x  @87X@x  @87X@x  @87X@_q_Q_ej+ij_z_O and we compute from formula (11):  _ #x$dddddddxA$ 2 `r (24) ă0x_i(q+e_i+e_j;C)=x_i(q; C)+C(q+e_j+e_i)C(q+e_j)x  @87X@x  @87X@x  @87X@_x+iZ_qJ_e+i_e+j_CB_x+i_qz_C _C _q _eB +j _e +i_C_q_e*+j_(b_;R_)_(_;_)Z _( _)B_(z_)___j _J _ _R_2_߷$(#(#(#(#!'#$(indeed the monotone path 20'&88'dd<<q^tx  @87X@x  @87X@x  @87X@8qzt associated with V30-&__-dd<< q+e_j+e_ix  @87X@x  @87X@x  @87X@_q_e+jJ_e+i__V by (9), (8) goes through  _! q and !!30'__dd<<q+e_jx  @87X@x  @87X@x  @87X@_q_e+j_!). Similarly we compute  _"  #x(ddddduddx$ 2 `Z: (25) ă7x_i(e_1+q+e_j+e_i;C)=x_i(q+e_1;C)+C(q+e_1+e_i)C(q+e_1)x  @87X@x  @87X@x  @87X@_x+iZ_e_q_e +j_eR+i_C_x+i_q _e _Cb _CR _qB_e_e+iB_C2_q"_e_(+1_;_)R_(2 +1 _;r _) _(+1R_)_(+1_)"__Z_ _B _ _ _ ___ $(#(#"(#(#!'#$(indeed the corresponding path A30'P+88'dd<< q tilde^tx  @87X@x  @87X@x  @87X@688qzt goes through !a30kl+__dd<<q+e_1x  @87X@x  @87X@x  @87X@_q_e_z+1! and V30%<l+__%dd<< q+e_1+e_ix  @87X@x  @87X@x  @87X@_q_eB_e+i__z+1V). Now we  8B& construct a cost function 30a,88dd<<C tildex  @87X@x  @87X@x  @87X@DV8C for which the csm '30,88dd<< psi(theta)x  @87X@x  @87X@x  @87X@8188(8)' violates cross monotonicity  _.' because 30M-__dd<<npartial_1 x_i (q+e_j+e_i) < 0x  @87X@x  @87X@x  @87X@_,__r+1_(_)_<_0_xB+i _q_ez+jB_e+in. Fix an arbitrary function 40M-88dd<<oCx  @87X@x  @87X@x  @87X@8Co in  !40M-__dd<< _{imc} x  @87X@x  @87X@x  @87X@_+imc , a positivep.'0*((Q'#t! '#z A'#"a$'#2&('#*p  8 number a, and construct A4088dd<<C tildex  @87X@x  @87X@x  @87X@DV8C as follows:  8 #x9 dddddqddxstack {for~all~q'~ s.t. q+e_i+e_j  q'  Q:~C tilde(q')=C(q)+a # ~ # alignl for~all~other~q'~in~[`0,Q`]:~~~C tilde(q')=C(q)}x  @87X@x  @87X@x  @87X@forallqstqweie? j q< Q Ct q!Cqya8for8all8otherB8q 8Q+ 8C 8q8C8q#G   zW8 zP8.. : (1)()'8[80- 8,3 8] 8: 8( 8)@8(08) ] V$(#(#(#(#!'#$Checking that a40( 88dd<<C tildex  @87X@x  @87X@x  @87X@DV8C has increasing marginal cost ((3)) is straightforward. Observe  8 than upon replacing C by 40t 88dd<<C tildex  @87X@x  @87X@x  @87X@DV8C in (24), the cost share of agent i increases by a, whereas the same replacement in (25) leaves her cost share unchanged. Therefore  }*U  t the desired violation of cross monotonicity follows when a is large enough. QED  t   }*  Remark 4  Lemma 5 does not hold if the cost function varies in the whole space  8 $4088dd<< (Q)x  @87X@x  @87X@x  @87X@88(8)8Q$. A counterexample is easily constructed with 40-88-dd<<aN=\{1,2\},Q=(1,1)x  @87X@x  @87X@x  @87X@8N8Q8J88{z818,j828}Z8,8(:818,*818)a. Recall  _ that IC((1,1),C) contains only two cost sharing methods, denoted 40__dd<<xi_1x  @87X@x  @87X@x  @87X@_+1 and 50 __dd<<xi_2x  @87X@x  @87X@x  @87X@_+2,  8 where i is the agent paying his stand alone cost. Define the mechanism !50 88dd<<qxix  @87X@x  @87X@x  @87X@8q as follows:  _ #x#=ddddd [ddx"stack {forall C epsilon  (Q)~~ xi(C)= xi_1~if~ partial _{12} C(0)  0 # ~ # ~~~~~~~~~~~~~~~~~=xi _2~if~ partial_{12} C(0) < 0}x  @87X@x  @87X@x  @87X@zl, ^^,CiQCqif Cz^if ^C   Yb^()y(i)1 121 ( 0! ) 0*2" *12: ^( ^0* ^) ^< ^0"ߟ$(#(#(#(#!'#$Continuity holds because the two methods A50'__dd<<xi_1x  @87X@x  @87X@x  @87X@_+1 and a50'__dd<<xi_2x  @87X@x  @87X@x  @87X@_+2 coincide whenever q50'__dd<<partial _{12}C(0)=0x  @87X@x  @87X@x  @87X@_,_r+12_(_0z_)j_0_Cq.  _ Obviously IC((1,1)) contains only two mechanisms (use 50__dd<<xi_1x  @87X@x  @87X@x  @87X@_+1 for all C, or use 50}"__dd<<xi_2x  @87X@x  @87X@x  @87X@_+2  8 for all C) and 50 88dd<<qxix  @87X@x  @87X@x  @87X@8q is not one of them. @0*((! '# ='#@  }*  #d6X@8;@#    9. The Demand Game of a Marginal Contribution Method Agent i is now endowed with individual preferences over his consumption of  _ good i and his cost share. We denote by 60__dd<<R_ix  @87X@x  @87X@x  @87X@_R+i a complete preordering on  _ !60N __Ndd<<[`0,Q_i`]x  _+x  @87X@x  @87X@x  @87X@_[_0_,v_]_Q+i_xf_+ (where the interval DA602 __dd<< [`0,Q_i`]x  @87X@x  @87X@x  @87X@_[_0_,v_]_Q+iD is in a60 88dd<<t x  @87X@x  @87X@x  @87X@8t) and the associated  _ indifference relation by 60t __dd<<I_ix  @87X@x  @87X@x  @87X@_I+i and strict preference relation by 60 __dd<<P_ix  @87X@x  @87X@x  @87X@_P+i. We always assume the following properties.  ."  @60MA .Mdd<<stack {alignl.R_i~is~strictly~increasing ~\in~q_i~\and~strictly ~decreasing~ \in~x_i # ~# alignl .R_i~is~continuous~(its~upper~\and~lower~contour~sets~are~closed) # ~ # alignl .R_i~is~convex: For~all~q_i epsilon`[`0,Q_i 2`],~all~x_i,x_i', x_i" epsilon  _+}x  @87X@x  @87X@x  @87X@a..()^.^: ^[ ^0 ^, ^2]^]^,5^,}^,aR -iaisastrictlya increasing ainb aq -iaandJastrictlyba decreasingjainax2-iR iis continuouszits: upper andlowerZcontoursets2areclosed^R *i^is^convexB^For^all ^qB *i ^Q *i^alle^x*i^x-9i^xu9i ^ ^ W ^>?^*@  _ #x8dddddg*ddxB$ 2 `mM (26) ăR\{(q_i, x_i) I_i (q_i+1,x_i') I_i (q_i+2,x_i")\} => \{x_i" x_i' x_i' x_i\}x  @87X@x  @87X@x  @87X@_{_(_,_)b_("_1_,_)* _( _2b _, _); _}+_>_{_}_q+iJ_x+i_I+i_qZ+i_x:iZ_I+i _q" +i _xZ :i_x:i|_x:i_xD:i _x+i_r _k  __ L_U_ߐ$(#(# (#(#!'#$We denote by 60 __dd<<Delta_ix  @87X@x  @87X@x  @87X@_+i the domain of individual preferences thus defined. The notation 70$__dd<<Delta_Nx  @87X@x  @87X@x  @87X@_+N  _ stands for the cartesian product of !70F__Fdd<<!Delta_i, i=1,...nx  @87X@x  @87X@x  @87X@_+is_i_n_,c_1_,S_._.C_._!ߞ namely the set of preference  _ profiles where @A70? __?dd<<R_i epsilon Delta_ix  @87X@x  @87X@x  @87X@_R+i+i_ C_@ for all i.  }*;  Remark 5  Notice that there is no loss of generality in assuming that agent i has unbounded reserves of the private good: if agent i's endowment of money is  _ bounded by a70__dd<<omega_ix  @87X@x  @87X@x  @87X@_3+i then the preference 70B__dd<<R_ix  @87X@x  @87X@x  @87X@_R+i strictly prefers (0,0) to any consumption T70-$__-dd<< (q_i,x_i)x  @87X@x  @87X@x  @87X@_(Z_,_)_q +i_xR+iT  _ such that 970Z__Zdd<< x_i > omega_ix  @87X@x  @87X@x  @87X@_x+i+i_>Z_39. As agent i can guarantee (0,0) by demanding !70N__dd<<q_i=0x  @87X@x  @87X@x  @87X@_q+i_Z_0! (by No Exploitation) an equilibrium of the demand game never involves an unfeasible consumption.  8 Given a o80( 88dd<<Q,C~ \in~  (Q)x  @87X@x  @87X@x  @87X@8Q8C8in8Q8,8(8)8o and a csm  in F!8088dd<<  (Q,C)x  @87X@x  @87X@x  @87X@88(8,r8) 8Q8CF, and a preference profile  _ *A80&__&dd<< R~\in~Delta_Nx  @87X@x  @87X@x  @87X@_R_in+N*_*, the demand game (R,) is the normal form game with strategy set  _y Ea80__dd<< [`0, Q_i`]x  @87X@x  @87X@x  @87X@_[_0_,v_]_Q+iE for agent i and where agent i evaluates the strategy profile ]80M 88dd<<q epsilon [`0,Q`]x  @87X@x  @87X@x  @87X@8qi8Q8 8[y808,8]]  _n by applying 80` __dd<<R_ix  @87X@x  @87X@x  @87X@_R+i to his consumption vector (g80E__dd<< q_i, x_i (q)x  @87X@x  @87X@x  @87X@_q+iZ_x+i_q_,*_(_)g).  8  In the particular case where  is an incremental csm, p80> )!88>dd<<xi epsilon IC(Q,C)x  @87X@x  @87X@x  @87X@88 8ICK8Q;8C8(8,8)p, the  8 sequential game F90 !88dd<< (R, xi)^*x  @87X@x  @87X@x  @87X@8(8,8)8Rz8bzF is the extensive form game with perfect information  8 played on the binary game tree $!90"88dd<<phi(xi)x  @87X@x  @87X@x  @87X@8-88(w8)$. The key to the extraordinary strategic features of this game (and of the corresponding demand game) is to consider a certain set of paths constructed on the tree  with the help of the preference profile.  }*,  Definition 8   _z! Given are Q, C in <A90'__dd<< _{imc}(Q)x  @87X@x  @87X@x  @87X@_+imc_Q_(w_)<, an incremental csm , Pa90r'88dd<<xi epsilon IC(QC)x  @87X@x  @87X@x  @87X@88 8ICK8QC8(;8)P, and a  _o" preference profile R in 90(__dd<<Delta_Nx  @87X@x  @87X@x  @87X@_+N. We say that a path m90 (88 dd<<P(w)=\{0=v^1, v^2,...,v^K = w\}x  @87X@x  @87X@x  @87X@8P8w8v+8vd8v zK 8w8(z8)j8{80cz18,z2 8,8.8.t8.8,V 8}8Z8f 8m from 0 to the terminal node w is an equilibrium path of the sequential game if we have for all k=0,1,..,K1: 0j'0*((8'#0Ԍ 8 !#xEddddd.}ddxA$ 2 ` (27) ăstack {alignl if~v^k epsilon V_i~\and~(q_i^k ,x_i(q^k))P_i(q_i^k + 1, x_i(q^k + e_i)) # ~ # alignl then~v^{k+1}~is~the~\left~successor~of~v^k # ~ # alignl if~v^k epsilon V_i~\and~(q_i^k+1, x_i(q^k + e_i))`P_i(q_i^k, x_i (q^k)) # ~ # alignl then~v^{k+1}~is~the~\right~successor~of~v^k}x  @87X@x  @87X@x  @87X@ifZv kV=~iandq kix~iq k PQ ~i q k ix~iq}kEe~i/thenJ/vqk#/isk/the+/leftc / successor /of;/vqkifZv kV=iandqkix i q kI e i P igqkixai)qk7thenJ7vyk#7isk7the+7right 7 successork7of7veyk\ \ (,g( )Y ) ( 1 ,S()){q1(1,W ( ) ) (i,(+)){y1 +q +yߎ$(#(#(#(#-!!'#$where 90'L 88'dd<<q^kx  @87X@x  @87X@x  @87X@8qzk is the demand path constructed by (9). We denote by V90VGL 88Vdd<< E^*(R,xi)x  @87X@x  @87X@x  @87X@8Ek8Rz8(8,8)[8V the set of terminal nodes w reached by all equilibrium paths of the game (R,) and by  8 E(R,), E(R,):0( 88dd<<t x  @87X@x  @87X@x  @87X@8t[0,Q] the set of corresponding demand profiles (in the bijection from W into [0,Q] given by (8) (9)).  }*  Lemma 6  Same assumptions as in Definition 8. The set E(R,) is the set of Nash  }= equilibrium outcomes of the demand game (R,). This game is dominance solvable10 and E(R,) is the corresponding set of sophisticated equilibrium profiles. The  }=0 set E*(R,) is the set of subgame perfect equilibrium outcomes of the sequential  8 game G!:0 88dd<< (R, xi )^*x  @87X@x  @87X@x  @87X@8(8,8)8Rz8bzG.  }*{  Proof   _ We fix A:0 __dd<<Q, C epsilon  _{imc} (Q)x  @87X@x  @87X@x  @87X@_Q_C`+imc_Q_,P_(@_)z_ _ߋ, pa:0>W88>dd<<xi epsilon IC(Q,C)x  @87X@x  @87X@x  @87X@88 8ICK8Q;8C8(8,8)p and .:0__dd<<R epsilon Delta_Nx  @87X@x  @87X@x  @87X@_R+N_ _.. Step 1 A demand profile q in E(R,) results from the iterated elimination of equivalent or strictly dominated strategies, and is a subgame perfect equilibrium outcome as well.  8 Fix o:0@88dd<<q epsilon E(R, xi)x  @87X@x  @87X@x  @87X@8q8E8R8 8c8(S8,;8)o and denote by :0'88'dd<<v^kx  @87X@x  @87X@x  @87X@8vzk and :0O88Odd<<>q^k, k=1,...,K,x  @87X@x  @87X@x  @87X@8qzk8kL8K8,|818,l8.8.\8.8,8,8>߻ the paths in ;088dd<<tthetax  @87X@x  @87X@x  @87X@8t and [0,Q] given by (9) and (8) respectively. We define a decreasing sequence of strategy sets converging to q:  _  A#xa dddddOddx cstack {alignl .for~all~i:~~Y_i^1=[0,Q_i] # ~ # alignl .if~O epsilon V_i: Y_i^2= \{0\}~if~q_i=0;~Y_i^2= [1, Q_i]~if~q_i > 0 # ~ # Y_j^2=Y_j^1~for~all~j != i~~~~~~~~~~~~~~~~~~~ # ~ # alignl .if~q^k epsilon V_i: Y_i^{k+1} = \{q_i^k\} ~if~ q^{k+1}=q^k; Y_i ^{k+1} = [`q_i^{k+1} , Q_i`]~if~ q^{k+1}=q^k + e_i # ~ # Y_j^{k+1} = Y_j~for~all~j != i~~~~~~~~~~~~~~}x  @87X@x  @87X@x  @87X@.:;)1[{0,; ]2.{2:2L2{20<2} 20 2;u 2= 2[ 21- 2,u2]]2>20721.:U1v{}9 <1 ;U1t[3U1,]*<1k1forJall iY*ikQi2if2O2V+i2Ys i 2ifT2qi 2Yd i 2Q%iE2if2q iY&qjYqj8for all j iifq<k5Vi}YUkiqUkniif q <k q <k{ Y Uk iqUkiQ{iifq<kq<klei:^Yk9j3^Y*j[ ^for ^all ^j ^i2$ 2 20 c^U < \UU<z^S ^cJ2   ߅ $(#(#(#(#" !A'#$We check that in the game with strategy sets !;0_*D,&___*dd<<.Y_i^k, i=1,..,nx  @87X@x  @87X@x  @87X@_Yk:i_i_n_,|_1_,l_._.\_,_.߫ the strategies in  _7! }A;0 *V'__ *dd<<Y_i^k\\Y_i^ {k+1}x  @87X@x  @87X@x  @87X@_Yk:i_Yk :i_\1m} are either strictly dominated or equivalent to some strategy in 6a;0*4!V'__*dd<< Y_i ^{k+1}x  @87X@x  @87X@x  @87X@_Yk:iC16. This crucial argument is given first for k=1, then repeated for an arbitrary k.  _# Say );0@')__dd<< O epsilon V_ix  @87X@x  @87X@x  @87X@_O_Vk+i_ ) and assume !;0 ')__dd<<q_i=0x  @87X@x  @87X@x  @87X@_q+i_Z_0!. By definition of E(R,) we have  8# a#x*dddddeddxA$ 2 `  (28) ăq(0,0) R_i(1,C(e_i))x  @87X@x  @87X@x  @87X@_(_0_,z_0_):_(_1*_,_(b_)_)j_R+i_C_e+iq$(#(##(#(#!a'#$We claim that this implies for all profile ;0|,88dd<<q tildex  @87X@x  @87X@x  @87X@688q Pg'0*((1'# ! '#%A*'#<,aPԌ _ #xddddd ddxK9(0, x_i(q tilde line^i 0)) R_i(q tilde _i, x_i(q tilde ))x  @87X@x  @87X@x  @87X@_(_0_,J_(_0R_)_)_(Z_,_( _) _)z_x+i_qiB_R+i_q +i_xR+i _q__> _:_ K$(#(#(#(#!'#$in other words !;0 __dd<<q_i=0x  @87X@x  @87X@x  @87X@_q+i_Z_0! is a dominant strategy of player i. Notice that formula (11) implies  88 #xW ddddd ddxKx_i ( q tilde) = sum from {K tilde (i)} C( q tilde ^t + e_i)C( q tilde ^t)x  @87X@x  @87X@x  @87X@xiZq+Kb+i9C)q5te#icCS q 5t()+(+)(s)(U )~?Mw J+I$(#(#8(#(#C!'#$where <0' 88'dd<< q tilde ^tx  @87X@x  @87X@x  @87X@688qzt is the monotone path corresponding to !<0k 88dd<<q tildex  @87X@x  @87X@x  @87X@688q. Say that A<0' 88'dd<< q tilde ^tx  @87X@x  @87X@x  @87X@688qzt is the rth  8e element of 7a<088dd<< K tilde (i)x  @87X@x  @87X@x  @87X@DV8K8i8(z8)7; by construction of this path and increasing marginal cost we have:  _ #xdddddddxw\{C(q tilde ^t + e_i)C(q tilde ^t)  C((r e_i)C((r1) e_i) for~all~t\} => \{ x_i (q tilde)  C(q tilde_i e_i)\}x  @87X@x  @87X@x  @87X@_{_(_),_(_)_(_(F _) _(& _( _1_)N_)_}_>&_{n_(^_)_(_)V_}_Cz_q,t_et+i_C_qVt_C_rv _e +i6 _C _r~_e+i_for_allF_t_x+i_qN_C>_q+i_e+i__ _b_|_<__ _ _6__$(#(# (#(#!'#$As the mapping <0 __dd<<q_i``C(q_i e_i) x  @87X@x  @87X@x  @87X@_q+i_Cv_q+iF_e+i__(_)ߑ is strictly convex (by increasing marginal costs) and  _ <0__dd<<R_ix  @87X@x  @87X@x  @87X@_R+i is convex, agent i's preferences over the set Q<0__dd<<2(q tilde _i, C(q tilde _i e_i)), q tilde _i  0x  @87X@x  @87X@x  @87X@_(Z_,J_(b_)_)R_,_0____q +i_C_qB+i_e+i_qJ+i_Q are singlepeaked (reaching their peak for at most two demands). Thus (28) implies that his  _% preferences peak at (0,0), with possibly another peak at v<0=D__=dd<< (1,C(e_i ))x  @87X@x  @87X@x  @87X@_(_1_,_(:_)_)z_Cj_e+iv. If the  _ relation (28) is strict and/or >=09__dd<<q tilde _i  2x  @87X@x  @87X@x  @87X@6__q+i_Z_2>, then strategy 0 of agent i strictly  _ dominates strategy !=0 .__dd<< q tilde _ix  @87X@x  @87X@x  @87X@6__q+i.  _ Assume next !A=0 __dd<<q_i=1x  @87X@x  @87X@x  @87X@_q+i_Z_1!, so that  _ #xdddddeddxA$ 2 `  (29) ăp(1,C(e_i))R_i(0,0)x  @87X@x  @87X@x  @87X@_(_1_,_(:_)_)_(r_0_,b_0_)z_Cj_e+i*_R+ip$(#(#(#(#!'#$Now we observe that Da=0u  [__u dd<<1x_i( q tilde line ^i 1) = C(e_i)~for~all~q tilde x  @87X@x  @87X@x  @87X@_x+iZ_q"i_C_eJ+ij_for*_all _q_(r_1_)R_(_)~_ __ b_D, implying that strategy 0 is weakly dominated by strategy 1 for player i. It is strictly dominated by (resp. equivalent to) strategy 1 if the preference relation (29) is strict (resp. is an indifference).  _ We fix next an arbitrary index k where i has the move ]=0H  __Hdd<<(v^k epsilon V_i)x  @87X@x  @87X@x  @87X@_(_)_v<k_Vm+i_ ] and check  _ that 5=0*!__*dd<< Y_i^{k+1}x  @87X@x  @87X@x  @87X@_Yk:iC15 obtains from =0'* !__'*dd<<Y_i^kx  @87X@x  @87X@x  @87X@_Yk:i by deleting some strictly dominated or equivalent  8$ strategies. Assume first X=0 C"88 dd<< q^{k+1}=q^kx  @87X@x  @87X@x  @87X@8qzk 8qzkz8Cz1X so that by definition of D>0 _"88dd<<E(R, xi)x  @87X@x  @87X@x  @87X@8E8R8(z8,b8)8D we must have:  8  #x#ddddd *ddxA$ 2 ` (30) ă/(q_i^k, x_i(q^k)) R_i(q_i^k +1, x_i(q^k + e_i))x  @87X@x  @87X@x  @87X@_(_,_(N_)_)_(_1x_, _( _) _)_q<k :i_x+iL_qk>_R+i_q8k:i_xp +i8 _q k _e2 +i_: _ $(#(#(#(#!'#$Consider another demand profile !>00p&88dd<<q tildex  @87X@x  @87X@x  @87X@688q such that ^!#x>'ddddd *ddx;q tilde _i > q_i^k;~q tilde _j epsilon Y_j^k~for~all~j != ix  @87X@x  @87X@x  @87X@6_P__q+iZ_q k:i,_q+j]_Yk:j_forw_all7 _j' _i_>\_;_  _c^$(#(#!(#(#!!'#$We claim that  _b$ A#x*ddddd *ddxA$ 2 `]=  (31) ă//(q_i^k, x_i(q^k)) R_i(q tilde_i, x_i (q tilde))x  @87X@x  @87X@x  @87X@_(_,_(N_)_)_(V_,_( _) _)_q<k :i_x+iL_qk>_R+i_q+i_xN+i _q_: _/$(#(#b$(#(#!A'#$with a strict preference if (30) is strict and/or A>0_*8-___*dd<<q tilde_i  q_i^k+2x  @87X@x  @87X@x  @87X@6__q+iZ_q k:i_\__2߄.&0*((q'#[W '#9 '#S'##'#)&>''#)!*'#,AԌCompute from (11):  8  a#xddddduddxA$ 2 `vV (32) ă,x_i(q^k + e_i)= x_i(q^k)+C(q^k + e_i)C(q^k)x  @87X@x  @87X@x  @87X@_x+iZ_q k_eT+i_x+i_qk_C_qp k8 _e +i _C _q k_(_)d_(_)F_( _)p _( _)\__V_ _ _ $(#(#(#(#!a'#$Now if a>0'lb 88'dd<< q tilde ^tx  @87X@x  @87X@x  @87X@688qzt is the monotone path associated with the profile >0~ 88dd<<q tildex  @87X@x  @87X@x  @87X@688q (by (9), (8)), it  _- coincides with that of q up to k >0i e 88i dd<<(q tilde ^t = q^t~for~t=1,..,k)x  @87X@x  @87X@x  @87X@8(818,8.v8.8,8)88q<zt8qzt^8for8tf8k88 because the sets >0'*i"L __'*dd<<Y_j^kx  @87X@x  @87X@x  @87X@_Yk:j  8W determine completely the sequence >0'v 88'dd<<q^tx  @87X@x  @87X@x  @87X@8qzt up to t=k. Hence by formula (11):  8A  #x` dddddddxex_i(q tilde) = x_i(q^k)+ sum from {tk+1,t epsilon K tilde (i)} C(q tilde ^t + e_i) C(q tilde ^t)x  @87X@x  @87X@x  @87X@xiZqxBi q5k+t+k+tl+K +i C q 5tM e i Cq5t()( )<+1+,+(\ +)[ ( )()~? !JL++  fI,+  $(#(#A(#(#C!'#$Say that ?0'488'dd<< q tilde^tx  @87X@x  @87X@x  @87X@688qzt is the rth element of 6!?088dd<< K tilde(i)x  @87X@x  @87X@x  @87X@DV8K8i8(z8)6 after A?0'|88'dd<<q^kx  @87X@x  @87X@x  @87X@8qzk; then increasing marginal costs imply: #x6dddddddx<lC(q tilde^t + e_i) C(q tilde^t)  C(q^k+re_i)C(q^k + (r1) e_i) ~for~all~tk+1,~t epsilon K tilde(i)x  @87X@x  @87X@x  @87X@_C_qt|_e+i<_C,_qt_C_qk _re +i _C _qb k_r_e+i"_for_all_t_k_t_K_i_(L_)_(._)_( _)8 _(*_(_1 _)R_)_1_,_( _)&_P_}___ _H _ ___ _B_ <߹$(#(# (#(#!'#$Summing up:  _Z #xyddddd*ddx|Tx_i(q tilde)  x_i(q^k)+C(q^k + (q tilde_iq_i^k) e_i)C(q^k)= lambda (q tilde_i)x  @87X@x  @87X@x  @87X@_x+iZ_q_xB+i _qk_C_qk_q^ +i& _q k :i _e +i` _CP_qk5_q+i_(_)_( _)t_(f_(( _)p _) _(R_)_(_)~_ _Y_J___ _ __B_|$(#(#Z(#(#!'#$The term Na?0`4__`dd<<lambda(q tilde_i)x  @87X@x  @87X@x  @87X@__(_))__q+iN is strictly convex w.r.t. ?0 __dd<<q_ix  @87X@x  @87X@x  @87X@_q+i therefore the claim (31) follows  _ by single peakedness of agent i's preferences over ?0  __ dd<</(q tilde _i, lambda(q tilde_i)x  @87X@x  @87X@x  @87X@_(Z_,M_(_)___q +i_qE+i_/߬.  _ In particular, the relation (31) is strict if (30) is strict and/or r?0-@__-dd<<q tilde_i  q_i+2x  @87X@x  @87X@x  @87X@6__q+iZ_q+i_*__2r.  _ It is an indifference if (30) is an indifference and n?0-d__-dd<<q tilde _i=q_i+1x  @87X@x  @87X@x  @87X@6__q+iZ_q+i_*__1n.  _ Assume finally @0h __hdd<<q^{k+1} = q^k + e_ix  @87X@x  @87X@x  @87X@_qk _qk_e+i_ _C1ߑ, so by definition of D!@088dd<<E(R, xi)x  @87X@x  @87X@x  @87X@8E8R8(z8,b8)8D we must have  _ !#xddddd *ddxA$ 2 ` (33) ă0(q_i^{k+1}, x_i(q^k + e_i)) R_i(q_i^k, x_i(q^k))x  @87X@x  @87X@x  @87X@_(1 _,S_(_)_)_(O _, _( _) _)_qk :i_x+i_q}kE_e+i_R+iM_qk:i _xG +i _q kk_!$(#(#(#(#!'#$Then for all A@0 88dd<<q tildex  @87X@x  @87X@x  @87X@688q such that da@0X*__X*dd<<q tilde_j epsilon Y_j^kx  @87X@x  @87X@x  @87X@6__q+jC_Yk:j_ d for all j @0Q88dd<<q!=x  @87X@x  @87X@x  @87X@8cq i, we have  8  #xdddddU*ddxYSx_i(q tilde line^i q_i^k)=x_i(q^k),~x_i(q tilde line^i q_i^k + 1) = x_i (q^k + e_i)x  @87X@x  @87X@x  @87X@_x+iZ_q"ir_q$k:id_x+i_q^k_xv+i> _q iV _q k :i8 _x +i_q2k_ez+i_(t_)4_(_)&_,_( _1H _)_(_)~_b __ _ _ X _ __Y$(#(#(#(#! '#$(because the first k terms of the monotone path associated with @0\"88dd<<q tildex  @87X@x  @87X@x  @87X@688q  _  coincide with e@0( C#88dd<< q^1,..,q^kx  @87X@x  @87X@x  @87X@8q8qzkz18,k8.8.[8,e). Therefore strategy V@0* *#__*dd<< (q_i^k +1)x  @87X@x  @87X@x  @87X@_(_1|_)_q<k :i_V strictly dominates (resp.  _5 is equivalent to) strategy A0'*<T$__'*dd<<q_i^kx  @87X@x  @87X@x  @87X@_qk:i if the preference (33) is strict (resp. is an indifference). To conclude the proof of Step 1 we must show that q is a subgame perfect equilibrium outcome. In the sequential game, we construct a subgame perfect equilibrium by exactly the same technique applied to an arbitrary node v of the  8" tree. If the path of demands !A0h(88dd<<q tilde^1,..,q tilde^kx  @87X@x  @87X@x  @87X@6888q8qzkz18,k8.8.[8,ߓ is associated with the path P(v), and player i has the move at v, we select his move at v as follows: v'0*((a'# a` '#B6'#ty'#'#O'#" ԌN! #xdddddd ddxA `stack {alignl if~q tilde^k=q^k:~q tilde ^{k+1} = q^{k+1} # ~ # alignl if~q tilde ^k != q^k:~q tilde ^{k+1}=q tilde ^k~~~if~(q tilde _i ^k,x_i(q tilde^k)) R_i( q tilde _i^k +1, x_i (q tilde ^k + e_i)) # ~ # q tilde ^{k+1} = q tilde ^k +e_i~~otherwise~~~~~~~~~~~~~}x  @87X@x  @87X@x  @87X@WifZWq kWqkWq7kWq0kifZq $kq$kq7$kqQ$kifi q =k i xc i+ q $kRieq=kixOiq$kei_qqk_qkS_e+i _ otherwise~WW~ O ;__\W'W\c$'ga__W:11:$1 (k , (-))(1W,(a))1N$(#(#(#(#8!! '#$This defines a s.p.e. of the sequential game. We omit the details.  8  Step 2 If q is a Nash Equilibrium of the Demand Game (AA0 88dd<<R, xix  @87X@x  @87X@x  @87X@8R8,8) then paA0 88dd<<q epsilon E(R, xi) x  @87X@x  @87X@x  @87X@8q8E8R8 8c8(S8,;8)p.  8 Fix a demand profile q with associated path A0 88dd<<\{0=q^1,q^2,..,q^K=q\}. x  @87X@x  @87X@x  @87X@8{80 z1[8,dz28,,8.8.8,8}8.88z8q8q8qFzK8q Assume  8 mA0 88dd<<q NOTIN E(R, xi)x  @87X@x  @87X@x  @87X@8q8E8R8z8(j8,R8)8m. For some k such that player i has the move at A0' 88'dd<<v^kx  @87X@x  @87X@x  @87X@8vzk, one of the two following statements is true A #xGddddd*ddxA$ 2 ` (34) ăLGq^{k+1} = q^k + e_i~\and~(q_i^k, x_i (q^k)) P_i(q_i^k +1, x_i(q^k+e_i))x  @87X@x  @87X@x  @87X@_qk _qk_e+i_and_qke:i__x+i _qY k _P +i _q ka :iK_x+i_qEk _e+i_ _ __C1m_(_,/ _( _)! _)i _([_1_,_(_)U_)L$(#(#( (#(#!A '#$a #xddddd*ddxA$ 2 ` (35) ăCq^{k+1} = q^k~~\and~(q_i^k +1, x_i(q^k + e_i)) P_i(q_i^k, x_i(q^k))x  @87X@x  @87X@x  @87X@_qk _qk_and_qku:i__x+i _qY k! _e +i _Pa +i)_qk:i_x#+i_qk__ _C1}_(o_1_,/ _( _)i _) _(+_,s_(_)e_)߸$(#(# (#(#!a '#$Suppose (34) holds. Then, just like in Step 1, we deduce from increasing marginal costs and (11)  #xdddddIddx>stack {alignl x_i(q line ^i q_i^k)= x_i (q^k) # ~ # alignl x_i(q^k + e_i) = x_i(q^k)+C(q^k+e_i)C(q^k) # ~ # alignl x_i(q)~>~ x_i(q^k)+C(q^k+(q_iq_i^k) e_i)C(q^k)}x  @87X@x  @87X@x  @87X@~xJiZ~q"ir~q$kYid~xJi~q^kxiZq =keTixiq=kCqp =k8 e i C q =k_x+iZ_qr_x+i_qlk_C_qNk _q +i _q kV :iP _e +i_C_qk~(t~)4~(~)()d()F( )p ( )_(_)_>B_(_)$_( _( _) _)_(_)~ ~\V  4__^ _ _>߻$(#(#(#(#! '#$Therefore (34) and convexity of preferences imply  #xSddddd *ddxL-(q_i^k, x_i(q line^i q_i^k))~P_i(q_i, x_i(q))x  @87X@x  @87X@x  @87X@_(_,_(f_)_)~_(_, _( _)v _)_q<k :i_x+iL_qid_qk:i_P.+i_qv+i> _x +i _q_ L$(#(#4(#(#! '#$So q is not a Nash equilibrium. Similarly if (35) hold, we have  _w  #xddddd*ddxFBq_i=q_i^k; x_i(q)=x_i(q^k); x_i(q line^i q_i^k + 1)= x_i(q^k +e_i)x  @87X@x  @87X@x  @87X@_q+iZ_q k:i_xT+i_q_x+i_q~k_x> +i _q i _q k :i_x+iH_qk_eB+i_ _~ _  _ _J_\_;_(_)T_(_)F_; _( _1 _)_(_)F$(#(#w(#(#! '#$so that player i benefits by switching to 3A0*2"__*dd<<q_i^k+1x  @87X@x  @87X@x  @87X@_qk:i__13 and q is not a Nash equilibrium.  }*  Step 3 End of the Proof Denoting by S0(R,) and Na(R,) respectively the set of sophisticated  8 equilibria and of Nash equilibria of (R,) we have shown B0%88dd<<GE(R,xi)  S0(R,xi)x  @87X@x  @87X@x  @87X@8E8RR8S08R8(z8,b8)B8(28,8)888G in  8 Step 1 and Na(R,)[!B0 &88dd<< E(R, xi)~x  @87X@x  @87X@x  @87X@88Ez8R8(8,8)j8[ in Step 2. On the other hand, the inclusion  8u! S0(R,)AB0l'88dd<<t x  @87X@x  @87X@x  @87X@8tNa(R,) is true in any normal form game. Concerning the set SPE(R,)  8C" of subgame perfect equilibrium outcomes, Step 1 showed +aB0,b(88dd<< E^*  SPEx  @87X@x  @87X@x  @87X@8Ek8SPEz8+ and an easy  8-# variation of Step 2 shows +B0L)88dd<< SPE  E^*x  @87X@x  @87X@x  @87X@8SPE8Ez8z+. QED.  }*$  Remark 6  If the preference profile R is such that for all player i, and all  _e% demand profile q, [B0- +__-dd<<q_i  Q_i1x  @87X@x  @87X@x  @87X@_q+iZ_Q+i_*__1[, we have: '0*((a'#S ! G'#A '#8a '#A S'# '#! Ԍd #xddddd}ddxA$ 2 `V6 (36) ăE(q_i,x_i(q))~is~n\ot~indifferent~\to~(q_i +1 , x_i(q line ^i q_i +1))x  @87X@x  @87X@x  @87X@_(Z_,_(_) _)_(j_1_,*_(_1z_)_)_q +i_xR+i_q_is"_n_ot_ indifferentb _to"_q+iZ_x+i_qji_q:+i__ _d$(#(#(#(#! '#$then the property (27) determines a unique equilibrium path and the equilibrium set E(R,) contains a single demand profile q. This outcome is the unique Nash equilibrium of (R,) and the unique subgame perfect equilibrium outcome of  8 EB0 88dd<<(R,xi)^*x  @87X@x  @87X@x  @87X@8(8,8)8Rz8bzE. Moreover, (R,) is strictly dominance solvable. Finally, the noncooperative equilibrium is also the Stackelberg equilibrium for any ordering of the players. This remark will play an important role in the proof of the characterization theorems (Sections 10,11), because the set of conditions (36) (for all q, all i) defines a dense subdomain of preference profiles.  }= We turn now to the strong equilibrium11 of the demand game (R,). Here the property of Cross Monotonicity ((19)) plays a key role. We refine the algorithm (27): when the player who has the move is  _m indifferent between demanding B0__dd<<q_ix  @87X@x  @87X@x  @87X@_q+i or "C0Q__dd<<q_i +1x  @87X@x  @87X@x  @87X@_q+i_Z_1", she always chooses to demand !C0R!__dd<<q_ix  @87X@x  @87X@x  @87X@_q+i. In other words ties are always resolved by the lowest demand. Thus  8 AC0(88dd<<\{0=v^1, v^2,..,v^K=w\}x  @87X@x  @87X@x  @87X@8{80 z1[8,dz28,,8.8.8,8}88z8v8v8vFzK8w is called the canonical equilibrium path: O #xEddddd}ddxA$ 2 `4 (37) ă stack {alignl v^{k+1}~\left~successor~of~v^k~if # ~ # alignl \{v^k epsilon V_i~\and (q_i^k ,x_i(q^k)) R_i(q_i^k +1, x_i(q^k + e_i))\} # ~ # alignl v^{k+1}~\right~successor~of~v^k~if~ # ~ # \{v^k epsilon V_i~\and ~(q_i^k + 1, x_i (q^k +e_i)) P_i(q_i^k, x_i(q^k))\}}x  @87X@x  @87X@x  @87X@v kleft# successorof v kU ifVv<kVVm"iVandVqku1ioVx"iVqik VR) "i Vq kq 1i[ Vx "iVqUkVe"ivkright successor+ ofs v% k if^v<k^Vm*i^andM^qk9i^x7*i^q ky ^e *i9 ^P *i ^q3k9i^x{*iC^qk  VVO^ ^C 1V{}V(V,?V(V)1 V)y V(k V1 V,+V(V)eV)V}C1^{^(^1?^,^(I ^) ^) ^(^,^(E^)^)5^}V ^ O$(#(# (#(#-! '#$We call canonical equilibrium and denote by e(,R) the demand profile resulting from this path.  }*  Lemma 7    _c Given are aC0 88dd<<oQx  @87X@x  @87X@x  @87X@8QoEC0 __dd<<,C epsilon  _{imc}x  @87X@x  @87X@x  @87X@_,_C+imc_ c_E(C088dd<<oQx  @87X@x  @87X@x  @87X@8Qo) and ,C0^88^dd<<xi epsilon IC(x  @87X@x  @87X@x  @87X@88 8IC8(,C0/88dd<<oQx  @87X@x  @87X@x  @87X@8QoD088dd<<,C)x  @87X@x  @87X@x  @87X@8,8)8C. i) If the incremental cost sharing method  is cross monotonic ((19)), then for  _ all .!D0@ __dd<<R epsilon Delta_Nx  @87X@x  @87X@x  @87X@_R+N_ _. the canonical equilibrium hAD0 88dd<< e(R,)=qx  @87X@x  @87X@x  @87X@8e8RR8q8(z8,b8)88h is a strong equilibrium of  8 4aD0u!88udd<<(R,)x  @87X@x  @87X@x  @87X@8(8,8)8Rz84. Moreover either q is the only strong equilibrium, or there is only one other strong equilibrium q' that is welfare indifferent to q and that only differs from q in one unit for a single player:  ht ! #$h/#dddddJ*ddxŵ$ 2 ` (38) ăf \{yi~q_i'=q_i +1~\and~q_j'=q_j~for~all~j != i\} ~\and~ \{forall i (q_i,x_i(q)) I_i (q_i',x_i(q')\}x  @87X@x  @87X@x  @87X@_{b_1J_}_{B_(_,_(_):_)_(_,_(G_)_}_yc___Z _cR_z_i_qR:i_q+i2_and_qr:j:_q+jb _for" _all _j _i_and_i_q:+i_x+iJ_q_I2+i_qz:iB_x+i_q߷$hhd&d&hhd&d&!! hc&$ ht ii) If the incremental cost sharing method  is not cross monotonic, then there  _S exists a preference profile R in D0r&__dd<<Delta_Nx  @87X@x  @87X@x  @87X@_+N such that the demand game (R, ) has no strong equilibrium.  _"  Proof of Statement i  We fix R in D0\(__dd<<Delta_Nx  @87X@x  @87X@x  @87X@_+N and set hD0(88dd<< q=e(R,)x  @87X@x  @87X@x  @87X@8q8e8R8z8(j8,R8)8h. First we show by contraposition that q is a strong equilibrium. Suppose coalition S objects to 11  82$ D0Q*88dd<<oqx  @87X@x  @87X@x  @87X@8qo by E0Q*88dd<<q tildex  @87X@x  @87X@x  @87X@688q: P'0*((1'#[ '# h/#c&%! PԌ 8  XX A #(#Xddddd5ddx-$ 2 ` (39) ă7stack {alignl for~all~j NOTIN S:~q tilde_j=q_j;~ for~all~i epsilon S:~(q tilde_i, x_i(q tilde)) R_i (q_i, x_i(q)) # ~ # alignl with~at~least~one~strict~inequality}x  @87X@x  @87X@x  @87X@foralljSqJkjqkjforr all2 i SqKkixki[qRCki qkiSxkiq8withJ8at8leastB8one8strict* 8 inequality :; :S(,()K)(,#())  7$XX%%XX%%!A X%$ XX   Compare the monotone paths !E0'< 88'dd<<q^kx  @87X@x  @87X@x  @87X@8qzk and AE0'W 88'dd<< q tilde ^kx  @87X@x  @87X@x  @87X@688qzk constructed by (8),(9). Let k be the first index after which they differ, and i the player who moves differently in  8{ the qpath and in the aE0H 88dd<<q tildex  @87X@x  @87X@x  @87X@688qکpath. By (38) player i belongs to S:  _I a #xh dddddddxRq^k=q tilde ^k,~player~i~moves~at~v^k=v tilde ^k,~ \and~ q^{k+1} != q tilde ^{k+1}x  @87X@x  @87X@x  @87X@8qzk8q>zk^8player8iV8moves 8atN 8v zk 8vz zk8andZ8qzkS8qzk8P 8;z8c4z8 8w88, 8,z1z1$(#(#I(#(#!a '#$Suppose player i moves right at E0'088'dd<<q^kx  @87X@x  @87X@x  @87X@8qzk in the qpath E0X3__Xdd<<6(q^{k+1} = q^k + e_i)x  @87X@x  @87X@x  @87X@_(1_)_qk_q5k_e}+ik __6߳ and left in the  _ E0J88dd<<q tildex  @87X@x  @87X@x  @87X@688qکpath. Then ^E0o*a __o*dd<<q tilde _i= q_i^kx  @87X@x  @87X@x  @87X@6__q+iZ_q k:i_^ and  t  #!?ddddd*ddx[g(q tilde_i,x_i(q tilde ))=(q_i^k, x_i(q line ^i q_i^k)) \because~q^t~\and~q tilde ^t~coincide~up~\to~kx  @87X@x  @87X@x  @87X@_(Z_,_(_) _)_(t_,_(N _) _)_>___q +i_xR+i_qr_q$k:i_xl+i4_qiL _q k :i> _because_qt8_and_qtR_coincidej_up_to_k__ [$d&d& d&d&! c&$ t Moreover (37) implies  #xddddd]*ddxB(q_i^k +1, x_i (q line^i q_i^k +1)) P_i(q_i^k,x_i(q line^i q_i^k))x  @87X@x  @87X@x  @87X@_(_1|_,_(_1F_)_) _( _, _(Z_)_)_q<k :i_xt+i<_qiT_qk:i6_P+i~ _q0 k :i _xx +i@ _q iX _q k :i__ V_ _ ߁$(#(#c(#(#! '#$and finally the Nash equilibrium property of q yields  #xddddd *ddx5(q_i, x_i(q)) R_i(q_i^k + 1, x_i(q line^i q_i^k + 1))x  @87X@x  @87X@x  @87X@_(Z_,_(_) _)R_(D_1_, _( _1 _) _)_q +i_xR+i_q_R+i_q|kJ:i4_x+i| _qD i _qF k :i_ _  _$(#(#(#(#! '#$Combining the three above properties we obtain a contradiction of (38). Therefore we have shown:  _  #xddddd *ddxA$ 2 `!  (40) ă2q^{k+1}=q^k, q_i=q_i^k~\and~q tilde _i  q_i +1x  @87X@x  @87X@x  @87X@_qk _qk_q+i_qkM:i'_and_qg+i/ _q +i_U__ _C1 _,w _1 _ߩ$(#(#(#(#! '#$Just like in Step 1 of the proof of Lemma 6, we note that F0XK__dd<<R_ix  @87X@x  @87X@x  @87X@_R+i is single peaked  _! on the graph  !F0* @__*dd<<(q_i', x_i (q^k line ^i q_i'))x  @87X@x  @87X@x  @87X@_(Z_,_(_)_)_q :i_xR+i_qkli_q<:i_ M  and (because AF0>u88>dd<<q epsilon E(xi, R))x  @87X@x  @87X@x  @87X@8q8E8R8 8c8(K8,;8)8)߀ that it reaches its  _K maximum at aF0j __dd<<q_ix  @87X@x  @87X@x  @87X@_q+i, hence:  8@   #x_!ddddd ddxA$ 2 ` (41) ăl;(q_i, x_i (q)) R_i (q tilde _i, x_i (q^k line^i q tilde_i))x  @87X@x  @87X@x  @87X@_(Z_,_(_) _)R_(_,_( _)D _)_q +i_xR+i_q_R+i_qJ+i_x+iZ_q k i _q| +i_ _\ _ l $(#(#@(#(#! '#$On the other hand, =F0 #88dd<<q tilde  q^kx  @87X@x  @87X@x  @87X@688q8qzk8= and cross monotonicity imply  _ 7! #x$ddddd ddxA$ 2 ` (42) ăC(q tilde_i, x_i(q^k line^i q tilde_i))R_i(q tilde_i, x_i (q tilde))x  @87X@x  @87X@x  @87X@_(Z_,_(_)_)L_(_, _( _)D _)___x __q +i_xR+i_qkli_q<+i|_R+i_qD+i _x +iT _q_ 7$(#(#(#(#!! '#$Combining (41) (42) and (39) we get F0'__dd<<( q tilde_i=q_i +1x  @87X@x  @87X@x  @87X@_(_1__q +i_qR+iZ__߀ and):  _W" A #xv(ddddd ddxA$ 2 `  (43) ă +(q_i, x_i(q))I_i (q tilde_i, x_i (q tilde))x  @87X@x  @87X@x  @87X@_(Z_,_(_) _)R_(_,_(_)J _)_q +i_xR+i_q_I+i_qJ+i_x+iZ_q_~_ ߬$(#(#W"(#(#!A '#$Now consider F02 +__2dd<<)q'=(q tilde line^i q_i)x  @87X@x  @87X@x  @87X@_q_qi_qW+i_7_ G_(_)_)ߦ. By cross monotonicity it is an objection of coalition  8& S\i to q: in view of the fact that player i is indifferent between F0#,88dd<<oqx  @87X@x  @87X@x  @87X@8qo and G0m!#,88dd<<q tildex  @87X@x  @87X@x  @87X@688q, at  8& least one player j in S\i strictly prefers !G0|,88dd<<q tildex  @87X@x  @87X@x  @87X@688q to AG0,88dd<<oqx  @87X@x  @87X@x  @87X@8qo, and this preference is  8' preserved when we shift to aG0<-88dd<<q'x  @87X@x  @87X@x  @87X@8qz (by cross monotonicity again). Repeating the'0*(( X% A h '#}a ?c& '# '# '# _!'## $'#!'! v('#*A  argument brings an objection by coalition smaller and smaller until we reach a contradiction. We show next the (almost) uniqueness of the strong equilibrium. Let  8 fG088dd << q=e(R,xi)x  @87X@x  @87X@x  @87X@8q8e8R8z8(j8,R8)8f and let G0 88dd <<q tildex  @87X@x  @87X@x  @87X@688q be another strong equilibrium of (R,). As above we pick  8j the first index k from which the two sequences G0'  88'dd <<q^kx  @87X@x  @87X@x  @87X@8qzk and G0'' 88'dd << q tilde^kx  @87X@x  @87X@x  @87X@688qzk differ. We note that  8T player i cannot move right at H0'hs 88'dd <<q^kx  @87X@x  @87X@x  @87X@8qzk in the !H0 88dd <<oqx  @87X@x  @87X@x  @87X@8qoکpath and left in the AH0 88dd <<q tildex  @87X@x  @87X@x  @87X@688qکpath, for  8> this would contradict the Nash equilibrium property of aH0,] 88dd <<q tildex  @87X@x  @87X@x  @87X@688q (in view of (37) player  _  i would gain strictly in the shift from \H0o*P+ __o*dd <<q tilde_i=q_i^kx  @87X@x  @87X@x  @87X@6__q+iZ_q k:i_\ to 4H0*O+ __*dd <<q_i^k +1x  @87X@x  @87X@x  @87X@_qk:i__14). Therefore we are in the configuration (40), and properties (41) (42) follow as above. Combining  _ these with H0} __}dd <<!x_i(q tilde line ^i q_i) = x_i(q)x  @87X@x  @87X@x  @87X@_x+iZ_q"ir_q+i2_x+iz_q_(B_)_(_)~__ _ (a consequence of =H0 88dd <<q tilde  q^kx  @87X@x  @87X@x  @87X@688q8qzk8=) we get  8 a #x dddddE dd xp>(q_i, x_i (q tilde line^i q_i)) R_i (q tilde_i, x_i (q tilde))x  @87X@x  @87X@x  @87X@_(Z_,_(_)z_)_( _,R _(B _) _)_q +i_xR+i_qi2_q+i_Rr+i:_q+i_x +i _q>_^_ __ p$(#(#(#(#!a '#$The reverse preference holds as well, because I088dd <<q tildex  @87X@x  @87X@x  @87X@688q is a Nash equilibrium. Therefore we have  _  #xdddddedd xA$ 2 `nN (44) ăTq tilde_i=q_i +1~\and~(q_i, x_i (q tilde line^i q_i)) I_i (q tilde_i, x_i (q tilde))x  @87X@x  @87X@x  @87X@6_^_~ ___q+iZ_q+ir_and_q*+i_xr+i:_q iR _q +i _I +iZ _q +i _x"+i_q_*__ _12_(z_,_(" _) _) _(* _,r_(b_)_)߼$(#(# (#(#! '#$Now we compare I!I0] __]dd << x_j(q tilde) x  @87X@x  @87X@x  @87X@_x+jZ_q_(_)~_I and AI0__dd <<x_j(q tilde line^i q_i)x  @87X@x  @87X@x  @87X@_x+jZ_q"ir_q+i_(B_)~__ ߔ for an agent 4aI0}"88}dd <<j,j != ix  @87X@x  @87X@x  @87X@8j8j8i8,z8c4. By cross monotonicity  _ and LI0=@__=dd <<q_i < q tilde _ix  @87X@x  @87X@x  @87X@_q+iZ_q+i_<~_L we have I0} __}dd <<+x_j(q tilde line ^i q_i)  x_j (q tilde)x  @87X@x  @87X@x  @87X@_x+jZ_q"ir_q+i2_x+jz_q_(B_)_(_)~___ _. If this inequality is strict, player j  _ strictly prefers the demand profile qI0__dd <<(q tilde line^i q_i)x  @87X@x  @87X@x  @87X@_(r_)__qRi_q"+i_ q to I0M88dd <<q tildex  @87X@x  @87X@x  @87X@688q: in view of (44), coalition  8 (ij) has an objection to J0t88dd <<q tildex  @87X@x  @87X@x  @87X@688q, and the latter cannot be a strong equilibrium. Therefore  _C x #xbddddd dd x4x_j(q tilde line ^i q_i)=x_j(q tilde)~for~all~j != ix  @87X@x  @87X@x  @87X@_x+jZ_q"ir_q+i2_x+jz_q_for_allB _j2 _i_(B_)_(_)~___ _ _cx$(#(#C(#(#! '#$This implies that !J0* __*dd <<e q tilde_j=q_j^k~for~all~j,j != ix  @87X@x  @87X@x  @87X@6__q+jZ_q k:j_fort_all4_j$_j_i__c_,e. Otherwise increasing marginal costs and formula (11) yield:  _   #xddddd dd x9x_j(q tilde line ^i q_i)x_j(q^k) < x_j(q tilde)x_j(q^k)x  @87X@x  @87X@x  @87X@_x+jZ_q"ir_q+i2_x+jz_q,kl_x+j_q _x +jd _q k_(B_)_(|_)_<<_(, _) _(f _)~___ _ _ $(#(#(#(#! '#$Therefore all players j, jAJ0!88dd <<s != x  @87X@x  @87X@x  @87X@8csi move left after aJ0'}k!88'dd <<q^kx  @87X@x  @87X@x  @87X@8qzk in the J0!88dd <<q tildex  @87X@x  @87X@x  @87X@688q path and oJ0_Ik!___dd <<q tilde=q^k + e_ix  @87X@x  @87X@x  @87X@6__q_qk|_e+i__o.  8] Now we show that !J0T |"88dd <<q=q^kx  @87X@x  @87X@x  @87X@8q8qzk8!. Suppose not, and let j be the first player to move  8G right in the J0 #88dd <<oqx  @87X@x  @87X@x  @87X@8qoکpath following K0'f#88'dd <<q^kx  @87X@x  @87X@x  @87X@8qzk. By (37) we have:  _1  #xP$ddddd *dd x|,(q_j^k+1, x_j(q^k+e_j)) P_j(q_j^k, x_j(q^k))x  @87X@x  @87X@x  @87X@_(_1|_,_(_)_)F_( _, _( _) _)_q<k :j_xt+j<_qk_e6+jv_P+j_qp k> :j8 _x +j _q2 k_>_|$(#(#1(#(#! '#$Now \!K0o*@&__o*dd <<q_j^k=q tilde_jx  @87X@x  @87X@x  @87X@_qk:j_q +j__\ and AK0 '__dd <<Ex_j(q^k)=x_j(q tilde)x  @87X@x  @87X@x  @87X@_x+jZ_q kL_x+j_q_(\_)_( _)__E: setting kaK0"'__dd << q^*=q^k + e_jx  @87X@x  @87X@x  @87X@_qk_qk_ee+j_m_k, the above relation says that  8! j strictly benefits in the move from K0$2(88dd <<q tilde x  @87X@x  @87X@x  @87X@688q to K0Q(88dd <<q^*x  @87X@x  @87X@x  @87X@8qz; on the other hand player i is indifferent to this move (by (44)), so we have an objection by coalition (ij) to  8# K0)88dd <<q tildex  @87X@x  @87X@x  @87X@688q, contradicting its strong equilibrium property. This concludes the proof of  _V$ [K0u*__dd << q tilde=q+e_ix  @87X@x  @87X@x  @87X@6__q_q_er+i_z_[ and of statement i.  }*%  Proof of Statement ii  Assume that the method  is not cross monotonic. Then by property (20) we can find three players denoted 1,2,3 and a demand profile q such that p' 0*((Q '#Ia '#Z b'# '# ! P$'#& pԌ _  X R # ddddddd!x]partial _1 x_2 (q)= x_2(q+e_1)x_2 (q) < 0 ~\and~ partial _1 x_3 (q) = x_3 (q+e_1)x_3(q) > 0x  @87X@x  @87X@x  @87X@_,_"__ _,j__R_r+1:+2_(z_)+22_(+1b_)+2_( _) _< _0 +1 +3_(_)Z+3_(+1_)B+3_(_)_>r_0_x_qj_x_q_eR_x_q _and: _xz_q_x"_q_e_x _qR$%%%%! %$ X Choose a preference L0 __dd!<<R_1x  @87X@x  @87X@x  @87X@_R+1 such that player 1 is indifferent between consuming !L0"__dd!<<q_1x  @87X@x  @87X@x  @87X@_q+1  _ or #AL0 __dd!<<q_1 + 1x  @87X@x  @87X@x  @87X@_q+1R_1_# and these two strategies strictly dominate every other strategy:  _ aL0  __ dd!<<5%(q_1, x_1 (q)) I_1(q_1+1, x_1(q+e_1))x  @87X@x  @87X@x  @87X@_(+1R_,B+1_(_)_)+1:_(*+1_1j_,Z+1_( +1 _)R _)_q_x _qr_I_q_x" _q _ez_ _5߲ and L0 __dd!<<[R_1 epsilon D_1(q_1,q_1 +1)x  @87X@x  @87X@x  @87X@_R;_D{_q_q+1+1_(+1C_,3+1_1s_)_ _[ (the notation L0[ __dd!<<D_1x  @87X@x  @87X@x  @87X@_D+1 is defined  _{ by (47)). Next choose IL0 __dd!<< R_i, i  2x  @87X@x  @87X@x  @87X@_R+iZ_i_,J_2_I such that strategy L0Q __dd!<<q_ix  @87X@x  @87X@x  @87X@_q+i strictly dominates every  _p other strategy: M0T __dd!<<R_i epsilon D_i(q_i)x  @87X@x  @87X@x  @87X@_R+iC_D+i_q +i_ _([_)߀ (this notation is defined immediately after (47).  _e At this profile, the Nash equilibrium demands are q and !!M0 __dd!<<q+e_1x  @87X@x  @87X@x  @87X@_q_e_z+1! but neither one is  _Z a strong equilibrium: coalition (12) objects at AM0y88dd!oqx  @87X@x  @87X@x  @87X@8qo by !aM0y__dd!<<q+e_1x  @87X@x  @87X@x  @87X@_q_e_z+1! and coalition (13)  _O objects at !M0n__dd!<<q+e_1x  @87X@x  @87X@x  @87X@_q_e_z+1! by M0i n88dd!oqx  @87X@x  @87X@x  @87X@8qo. QED  }*D   8  Remark 7  In the twoplayer case (;M0- 88-dd!<< line N line=2x  @87X@x  @87X@x  @87X@8 8 *8b8N82;), all incremental cost sharing methods are cross monotonic (see Lemma 4). Moreover it is easily checked that the canonical equilibrium is also the Pareto superior Nash equilibrium: the demand  8 profile CM0&88dd!<<e(R,xi)x  @87X@x  @87X@x  @87X@8e8R8(z8,b8)8C is Pareto superior or indifferent to every other outcome in  8 CN088dd!<<E(R,xi)x  @87X@x  @87X@x  @87X@8E8R8(z8,b8)8C. This property, however, does not hold true with three or more players, even for an elementary incremental method. An example follows. Consider the elementary method of Figure 4a with three agents ordered as  _ 1,2,3. Let Q=(1,1,1) and }!N0M __M dd!<<C(q_1,q_2,q_3)=(q_1+2q_2+q_3)^2x  @87X@x  @87X@x  @87X@_C_qB_q_q_qj_q_q_(z+1_,+2 _,+3J_):_(*+1_2+2" +3r _) 2_z_2_}. Let agent 1 be willing to pay $1 for one unit of good 1 (thus he is indifferent between demanding it or not), agent 2 be willing to pay $6 and agent 3 be willing to pay $6. We have two Nash equilibria namely q=(0,1,1) and q'=(1,0,1) with respective net utilities  8 (0,2,1) and (0.0,3): they are not Pareto comparable. Note that fAN088dd!<< e(R,xi)=qx  @87X@x  @87X@x  @87X@8e8RR8q8(z8,b8)88f is a  8l strong equilibrium but aN0 88dd!<<q'x  @87X@x  @87X@x  @87X@8qz is not (because of an objection by coalition (12)).  }*  10. Characterization Results Among Cost Sharing Methods (or Mechanisms)  The results of this section are necessary steps toward the proof of our main theorems in the next section. They are also interesting in their own right. We start with the definitions of two sets of "generic' cost functions and of the set of "generic" preferences for a given csm.  }*5  Definition 9 Generic Cost Functions   Given Q, consider the two following properties of a cost function C:  8*  X ! # qI#ddd)dd!xY 2  (45)  2  `w ă^forall i ~forall q, q' epsilon [`0,Q`]~\{ q != q'\} => \{ partial_i C(q) != partial_i C(q')\}x  @87X@x  @87X@x  @87X@_zZ_zS_cY _ _,Q _c _,_i_q_q^_Q4_q$_q! +iq _Ca _q)+iy_Ci_qJ_,_[n_0_,_]_{_} _>I _{ _( _)_(&_)_}_ $%%*%%C!! %$ X In the next property, N0'H &88'dd!<<q^tx  @87X@x  @87X@x  @87X@8qzt and N0'c&88'dd!<<p^tx  @87X@x  @87X@x  @87X@8pzt, t=0,...,T, denote two increasing (that is  8W! N03v'883dd!<<x$q^t  q^{t+1}~\and~q^t != q^{t+1}x  @87X@x  @87X@x  @87X@8qzt8qzte8and%8qzt8q0zt8mz'8czz1z1x) sequences of [0,Q]. We call these two sequences disjoint  8A" if IN0`(88dd!<< q^t != p^t' x  @87X@x  @87X@x  @87X@8qzt8p>zt8cddI for all  O02 |(88dd!<<t,t'x  @87X@x  @87X@x  @87X@8t8t8,z  A #xf)dddddKdd!xB$ 2 `e (46) ăstack {alignl forall i~forall T epsilon [`0, Q_i 1`]~ forall q^t, p^t, t=1,..,~T~~ \{q^t~ \and~p^t'~disjoint~ # ~ # alignl \and~ q_i^t=p_i^t = t~for~all~t\} => \{ sum_t partial _i C(q^t) != sum_t partial_i C(p^t)\}}x  @87X@x  @87X@x  @87X@!zZ!z!!z !ddN  ,c,!i!T)!QiG!qct!ps ct; !t !T{!q-ct!and!pGct !disjointandqtR`iLpt`itforVall tJ *t1 Qi Cqq#t?*t&QivCfptJ! ![9!0!,q!1!]I!, !,+ !1 !, !. !. !,!{ }~ > { (s)(h)}n 8Ic8I߇$(#(#G#(#(#!A '#$P'!0*((1%? !I#%&! !f)'#-A !PԌ _ ԙWe denote by P!O0* __*dd"<< _{imc}^* (Q)x  @87X@x  @87X@x  @87X@_:imc_Q_(w_)P (resp. tAO0z*__z*dd"<< _{imc}^{**}(Q))x  @87X@x  @87X@x  @87X@_:imc_Q_(w_)_)t the subset of <aO0<T__dd"<< _{imc}(Q)x  @87X@x  @87X@x  @87X@_+imc_Q_(w_)< defined by (45) (resp. (46)).  8 Clearly O0J88Jdd"<<  ^{**} x  @87X@x  @87X@x  @87X@8zz is an open dense subset of O0  88dd"<<t x  @87X@x  @87X@x  @87X@8t (and so is its superset O0x88dd"<< ^*x  @87X@x  @87X@x  @87X@8z) for the  8 standard topology of the finite dimensional vector space KO0V88Vdd"<< ^{[`0,Q`]}x  @87X@x  @87X@x  @87X@8z[z0Ez,z]zQK.  }*L  Definition 10 Generic Preferences  8 Given Q, a cost function OP0 88dd"<<C epsilon  (Q)x  @87X@x  @87X@x  @87X@8C8Q8 8p8(`8)O an agent i and a cost sharing method  _h r!P0 88dd"<<xi epsilon (Q,C)x  @87X@x  @87X@x  @87X@88 8c8(S8,C8)8Q8Cr, we denote by 8AP0nZ __ndd"<< Delta_i(xi)x  @87X@x  @87X@x  @87X@_s_+i_(_)8 the subdomain of aP0 __dd"<<Delta_ix  @87X@x  @87X@x  @87X@_+i defined by the property:  _]  t a #!| ddddddd"xJbfor~all~q,p epsilon [`0,Q`]~\{(q_i, x_i (q)) I_i(p_i, x_i(p))\} => \{q_i=p_i ~\and~x_i(q)=x_i(p)\}x  @87X@x  @87X@x  @87X@_for_all_q_p_Q' _q +io _x +i _q _I +ig_p+i_x/+i_p?_q+i_p+i_ando_x+i_q_x+ig_p _,[_[_0a_,g_]7_{_( _,? _(/ _) _) _(7_,_(o_)_)__}O_>_{?_(/_)_(_)W_}_ ___J$d&d&]d&d&!a c&$ t Clearly 8P0n__ndd"<< Delta_i(xi)x  @87X@x  @87X@x  @87X@_s_+i_(_)8 is an open dense subset of P0.__dd"<<Delta_ix  @87X@x  @87X@x  @87X@_+i for the standard topology on individual preferences (using the Hausdorf metric between the graphs of these preferences: see Hildenbrand [1974]). Our first theorem uses neither a generic cost function nor the domain of generic preferences.  }*  Theorem 1 DominanceSolvability   _& Given Q and gP0 E__dd"<<C epsilon  _{imc}(Q)x  @87X@x  @87X@x  @87X@_Cp+imc_Q_ _`_(P_)g and tP0E88dd"<< epsilon (Q,C)x  @87X@x  @87X@x  @87X@88 8c8(S8,C8)8Q8Ct, the two following statements are equivalent:  8 i. pQ0>88>dd"<<xi epsilon IC(Q,C)x  @87X@x  @87X@x  @87X@88 8ICK8Q;8C8(8,8)p:!Q0F 88dd"<<qxix  @87X@x  @87X@x  @87X@8q is an incremental cost sharing method.  _7 ii. for all .AQ0 V__dd"<<R epsilon Delta_Nx  @87X@x  @87X@x  @87X@_R+N_ _. the game 3aQ0uV88udd"<<(R, xi)x  @87X@x  @87X@x  @87X@8(8,8)8Rz83 is dominance solvable. Our second theorem uses generic preferences and, if N contains three or more players, generic cost functions.  }*  Theorem 2 Unique Nash or Strong Equilibrium for Generic Preferences   _ Given Q, hQ0 5__dd"<<C epsilon  _{imc} (Q)x  @87X@x  @87X@x  @87X@_Cp+imc_Q_ _`_(P_)h and rQ0[588dd"<<xi epsilon (Q,C)x  @87X@x  @87X@x  @87X@88 8c8(S8,C8)8Q8Cr, consider the three statements:  8 i) pQ0>88>dd"<<xi epsilon IC(Q,C)x  @87X@x  @87X@x  @87X@88 8ICK8Q;8C8(8,8)p: Q0 88dd"<<qxix  @87X@x  @87X@x  @87X@8q is a marginal contribution method.  _' ii) for all cR0G F!__Gdd"<<R epsilon Delta_N(xi)x  @87X@x  @87X@x  @87X@_R+N_ _L__(_)c the game 3!R0uF!88udd"<<(R, xi)x  @87X@x  @87X@x  @87X@8(8,8)8Rz83 has a unique Nash equilibrium.  _ iii) for all cAR0G "__Gdd"<<R epsilon Delta_N(xi)x  @87X@x  @87X@x  @87X@_R+N_ _L__(_)c the game 3aR0u"88udd"<<(R, xi)x  @87X@x  @87X@x  @87X@8(8,8)8Rz83 has a unique strong equilibrium.  8_ If <R0-~$88-dd"<<line N line =2x  @87X@x  @87X@x  @87X@8 8 *8b8N82< (or if at most two agents are active in Q) properties i, ii, and iii are equivalent.  _{ If AR0-&88-dd"<<line N line  3 x  @87X@x  @87X@x  @87X@8 8 *8b8N83A and if zR0*) &__*dd"<<C epsilon _{imc}^* (Q)x  @87X@x  @87X@x  @87X@_Cp:imc_Q_ _p`_(P_)z properties i and ii are equivalent.  _L" If AR0-(88-dd"<<line N line  3 x  @87X@x  @87X@x  @87X@8 8 *8b8N83A and if S0*) k(__*dd"<<C epsilon  _{imc}^{**} (Q)x  @87X@x  @87X@x  @87X@_Cp:imc_Q_ _p`_(P_)ߏ, properties i and iii are equivalent as well.   The rest of Section 10 is devoted to the proof of Theorem 1. The longer proof of Theorem 2 is relegated to the Appendix.  8& The following definition will be useful. Given 3!S0u1,88udd"<<Q,C, xix  @87X@x  @87X@x  @87X@8Q8C8,z8,83 in CAS0m1,88mdd"<<IC(Q,C)x  @87X@x  @87X@x  @87X@8ICz8Qj8C8(8,8)C, and  _& an agent i, we denote by aS0t,88dd"<<y varepsilonx  @87X@x  @87X@x  @87X@8=y an upper bound of \S0 s,__ dd"<<partial_i x_i(q)x  @87X@x  @87X@x  @87X@_,r+i_xB+i _q_(_)\ for all S0,__dd"<<q epsilon [`0,Qe_i`]x  @87X@x  @87X@x  @87X@_qi_QY_e+i_ _[y_0_,?_]_ߒ. We0&"0*((| c&a "0  _ say that agent i's preference relation S0P__dd#<<R_ix  @87X@x  @87X@x  @87X@_R+i is focused on {S0!__dd#<<\{q_i, q_i +1\}x  @87X@x  @87X@x  @87X@_{Z_,_1_}_q +i_qR+i_{ if we have  _  \t  #%\dddddadd#xx$ 2 ` (47) ă9lfor~all~x_i epsilon  _+:~(q_i, x_i+C(Q)) P_i(q_i 1, x_i) ~ \and~(q_i+1,x_i) P_i (q_i+2,x_i+ varepsilon)x  @87X@x  @87X@x  @87X@_for_all_x+i_q`+i(_x+ip _C` _Q _PH +i _q +iH_x+i_and _q+iX_x+i_P +i_qh+i _x+ib_ h_=_H+_ _____:h_(_, _( _)P _) _(X_1_,_)_(h_1_,(_)p_(0_2_,_)9$\\d&d&\\d&d&! \c&$ \t We denote by T0 __dd#<<D_i(q_i,q_i +1)x  @87X@x  @87X@x  @87X@_D+iZ_q+i_q"+i_(*_,_1b_)r_ߛ the subset of !T0 __dd#<<Delta_ix  @87X@x  @87X@x  @87X@_+i defined by (47). For these preferences, agent i is willing to pay any cost share requested by the csm to  _- consume AT0L __dd#<<q_ix  @87X@x  @87X@x  @87X@_q+i or "aT0U L __dd#<<q_i +1x  @87X@x  @87X@x  @87X@_q+i_Z_1" units of good i; he is not willing to pay what the csm  _" demands to consume !T0 A __dd#<<q_i+2x  @87X@x  @87X@x  @87X@_q+i_Z_2! or more. Therefore every strategy smaller (resp.  _ greater) than T0( 6 __dd#<<q_ix  @87X@x  @87X@x  @87X@_q+i (resp. !T0=6 __dd#<<q_i+1x  @87X@x  @87X@x  @87X@_q+i_Z_1!) is strictly dominated by T06 __dd#<<q_i x  @87X@x  @87X@x  @87X@_q+i (resp. by "U06 __dd#<<q_i +1x  @87X@x  @87X@x  @87X@_q+i_Z_1").  _ Similarly we say that !U0__dd#<<R_ix  @87X@x  @87X@x  @87X@_R+i is focused on AU0q__dd#<<q_ix  @87X@x  @87X@x  @87X@_q+i if agent i is willing to pay  _ C(Q) to increase his demand from #aU0__dd#<<q_i 1 x  @87X@x  @87X@x  @87X@_q+i_Z_1# to U0 __dd#<<q_ix  @87X@x  @87X@x  @87X@_q+i and is not willing to pay U0 88dd#<<y varepsilonx  @87X@x  @87X@x  @87X@8=y to go  _ from U0__dd#<<q_ix  @87X@x  @87X@x  @87X@_q+i to !U0) __dd#<<q_i+1x  @87X@x  @87X@x  @87X@_q+i_Z_1! (thus strategy V0N__dd#<<q_ix  @87X@x  @87X@x  @87X@_q+i is strictly dominant). We denote by C!V0!__dd#<<D_i(q_i)x  @87X@x  @87X@x  @87X@_D+iZ_q+i_(*_)C  _ the corresponding subset of AV0__dd#<<Delta_ix  @87X@x  @87X@x  @87X@_+i.  }*.  Proof of Theorem 1 By Lemma 6 we only need to show ii => i. We fix a csm  satisfying ii: by Lemma 3 it will be enough to show that  is acyclic. Take a profile q and a  8 coalition jaV088dd#<<S, S  B(q)x  @87X@x  @87X@x  @87X@8S8S8B8q8,j8(Z8)z8j, as in the premises of property (17). We fix the  _ preferences of any agent j outside S as V0P__dd#<<R_jx  @87X@x  @87X@x  @87X@_R+j in CV0__dd#<<D_j(q_j)x  @87X@x  @87X@x  @87X@_D+jZ_q+j_(*_)C whereas the preferences  _ of any agent i inside S will be chosen in V0__dd#<<D_i(q_i,q_i +1)x  @87X@x  @87X@x  @87X@_D+iZ_q+i_q"+i_(*_,_1b_)r_ߛ. Thus the elimination  _ of strictly dominated strategies shrinks the strategy set of player 7V0}@88}dd#<< j,j NOTIN Sx  @87X@x  @87X@x  @87X@8j8j8S8,z8Ѻ7 to "W0M#__dd#<<\{q_j\}x  @87X@x  @87X@x  @87X@_{Z_}_q +j"  _w and that of player :!W0f 88fdd#<<i, i epsilon Sx  @87X@x  @87X@x  @87X@8i8i8S8,z8 : to |AW0__dd#<<\{q_i, q_i + 1\}x  @87X@x  @87X@x  @87X@_{Z_,_1_}_q +i_qR+i_|. After one round of elimination, we are  _l left with the strategy set gaW0<__dd#<< [`q,q+e_S`]x  @87X@x  @87X@x  @87X@_[_,f_]_q_q_e+S_g. Next we assume that property (17) does not hold and we construct the  _ preferences KW0` __dd#<<R_i,i epsilon Sx  @87X@x  @87X@x  @87X@_R+iZ_i3_S_,_ K, in such a way that no further elimination of dominated or  _ equivalent strategies is possible. Suppose agent i is such that W0__dd#<<x_ix  @87X@x  @87X@x  @87X@_x+i is not  _ constant on W0y` __ydd#<<3A= [`q,q+e_{S\\i}`]x  @87X@x  @87X@x  @87X@_A_q_qp_e+S+i___[_,8+\_]3߰. There exists 3W0_88_dd#<<q^1, q^2x  @87X@x  @87X@x  @87X@8qk8qz18,z23 in A such that X0__dd#<<Bx_i(q^1) < x_i (q^2)x  @87X@x  @87X@x  @87X@_x+iZ_q+_x+is_q_(1;_)_<_(2T_)B߿.  _ Then we can choose !X0 __dd#<<R_ix  @87X@x  @87X@x  @87X@_R+i in AX0__dd#<<D_i(q_i,q_i+1)x  @87X@x  @87X@x  @87X@_D+iZ_q+i_q"+i_(*_,_1b_)r_ߚ such that:  _  #x ddddddd#xq](q_i, x_i(q^1)) q_i (q_i+1, x_i(q^1 + e_1))~\and~(q_i+1, x_i(q^2 + e_1)) P_i (q_i, x_i (q^2))x  @87X@x  @87X@x  @87X@_(Z_,_(1_)s_)_({_1_,; _(D 1 +1 _)L _)_(_1_,\_(e2+1_)m_)_(_,E_(N2_)_)_q +i_xR+i_q_qk+i3_q+ik_x+i _q _e _andT_q+i_x +i_q-_e_Pe+i-_q+iu_x+i_q_ _$__q$(#(#(#(#! '#$(see Figure 5a, noticing that aX0 hZ#__ dd#<<%x_i(q^1) < x_i(q^2) < x_i(q^2 + e_i))x  @87X@x  @87X@x  @87X@_x+iZ_q+_x+is_qD_x+i_q_ee +i_(1;_)_<_(2T_)_<_(2 _)- _)m_߁. Therefore agent i has no dominated or equivalent strategy in the restriction of the demand game to  _ gX0%__dd#<< [`q,q+e_S`]x  @87X@x  @87X@x  @87X@_[_,f_]_q_q_e+S_g. Similarly, suppose agent i is such that X0m%__dd#<<x_ix  @87X@x  @87X@x  @87X@_x+i is not constant on  _ X09#&__9dd#<< [`q+e_i, q+e_S`]x  @87X@x  @87X@x  @87X@_[`_,_]_q_e+i_q_eH+S_P_ ߝ. There exists 2X0_)&88_dd#<<q^1,q^2x  @87X@x  @87X@x  @87X@8qk8qz18,z22 in A such that 9Y0&__dd#<<x_i(q^1+e_i) < x_i(q^2+e_i).x  @87X@x  @87X@x  @87X@_x+iZ_q_e3+is_x+i_q_e+i_(1_)_<C_(L2_)\_.;__9 Then  _ we can choose !Y0( '__dd#<<R_ix  @87X@x  @87X@x  @87X@_R+i in AY0 '__dd#<<D_i(q_i,q_i+1)x  @87X@x  @87X@x  @87X@_D+iZ_q+i_q"+i_(*_,_1b_)r_ߚ so that  #x (dddddQdd#xUQ(q_i+1,x_i(q^1+e_1)) P_i (q_i,x_i(q^1))~\and~(q_i,x_i(q^2)) P_i(q_i+1,x_i(q^2+1))x  @87X@x  @87X@x  @87X@_(_1J_,_(1+1+_)_)_(3 _,{ _( 1 _)L _)_($_,l_(u2_)=_)_(E_1_,_(2_1N_)_)_q +i_xB+i _qc_e_P+ic_q+i _x+ +i _q _andT_q+i_x+i_q_P5+i_q}+i5_x+i}_qZ___^_U$(#(#!(#(#! '#$(see Figure 5.b). Again, agent i cannot eliminate any strategy in the  _1% restriction of the demand game to gaY0P+__dd#<< [`q,q+e_S`]x  @87X@x  @87X@x  @87X@_[_,f_]_q_q_e+S_g. Thus we constructed a profile R  8&& such that the game 4Y0u E,88udd#<<(R, xi) x  @87X@x  @87X@x  @87X@8(8,8)8Rz84 is not dominance solvable. QED. P'#0*((1\c&4 # '#" # ('#I* #PԌ }*  ""   #d6X@8;@#  Remark 8 The restriction to a generic cost function in the statement of  8 Theorem 2 for the case @Y0- 88-dd$<<line N line  3x  @87X@x  @87X@x  @87X@8 8 *8b8N83@ cannot be dispensed with. A counterexample can be given for the smallest conceivable capacity profile namely N={123} ,  _ Y0;__dd$<<EQ_i=1~for~i=1,2,3. x  @87X@x  @87X@x  @87X@_Q+i*_for_i_b_Z_1_1R_,_2B_,_32_.E Choose a cost function C in =Y0%;__dd$<< _{imc} (Q)x  @87X@x  @87X@x  @87X@_+imc_Q_(w_)= and such that  _ TZ0} L __} dd$<<&partial_3C(1,0,0)= partial _3 C(0,1,0)x  @87X@x  @87X@x  @87X@_,__,r+3:_(_1*_,_0_,_0 _)Z+3"_(_0_,_1_,z_0_)_C_CT (for instance !Z0M  0 __M dd$<<!C(q_1, q_2, q_3)=(q_1+q_2+q_3)^2)x  @87X@x  @87X@x  @87X@_C_qB_q_q_q_q2_q_(z+1_,+2 _,+3J_):_(*+1j+2+3_)r 2 _)_z__. Then define the csm  by No Exploitation and as follows:  X  #  ddddd)dd$x\-stack {alignl x_1(1,q_2,q_3)=C(1,0,0)~if~(q_2,q_3) != (1,1);~x_1(1,1,1)=C(1,1,1)C(0,1,1) # ~ # alignl x_2(q_1,1,q_3)=C(0,1,0)~if~(q_1,q_3)!= (1,0); x_2(1,1,0)=C(1,1,0)C(1,0,0) # ~ # alignl x_3 (q_1,q_2,1)=C(0,1,1)C(0,1,0)=C(1,0,1)C(1,0,0)~if~(q_1,q_2) != (0,0); # ~ # alignl x_3(0,0,1)=C(0,0,1)}x  @87X@x  @87X@x  @87X@xBqq:CR if qR q2xCC,xR,q,q:,CR ,if ,qR ,q,xb,C,CxRqq:Cr C CCifqq^x^C_1(R1,_2 ,_3J)(*1,0, 0) ( _2 , _3 ) (1,r1)b;_1(r1,b1,R1)2(1",1,1)j(0Z,1J,1:)2,(1,,,1 ,,3J,),(*,0,,,1,, ,0,) ,( 1 ,, 3 ,) ,(,1,,r,0,)b,;R2,(,1,, ,1,,,0r,),(R,1,,B,1,,2,0,),(,1,,z,0,,j,0,)3(1, 2Z,1J)(*0,1, 1) (b 0 ,R 1 ,B 0 )"(1,0,z1)Z(1J,0:,0*)B(21,r2)(*0,0) ;*3^(R^0^,B^0^,2^1^)^(^0^,z^0^,j^1^) cBz, ,c,",2 j:c"^\$%%%%! %$ XX  X One checks easily budget balance and demand monotonicity. Clearly  is not an incremental cost sharing method. On the other hand, at all generic preference profiles, the demand game has a unique Nash equilibrium. This follows by direct inspection if the best reply of at least one agent is constant (check that in the remaining 2 agents games the acyclicity property (17) holds, hence one player always has a dominant strategy). On the other hand each player has only one possible non constant best reply, namely  _  #xddddddd$xstack {alignl br_1(1,1)=0~~br_1(q_2,q_3)=1~if~(q_2,q_3) != (1,1) # ~ # alignl br_2(1,0)=0~~br_2(q_1,q_3)=1~if~(q_1,q_3) != (1,0) # ~ # alignl br_3(0,0)=1~~br_3(q_1,q_2)=0~if~(q_1,q_2) != (0,0)}x  @87X@x  @87X@x  @87X@-brJ-br-qB-q -if -q -qbrJbrqBq if q q_brJ_br_qB_q _if _q _q1R-(-1B-,-12-)"-0:1-(z2-,3 -) -1 -( 2R -,B3-)-(-1r-,-1b-)2R(1B,02)"0:2(z1,3 ) 1 ( 1R ,B3)(1r,0b)+3R_(_0B_,_02_)"_1:+3_(z+1_,+2 _) _0 _( +1R _,B+2_)_(_0r_,_0b_)- - -c  c_ _ _c$(#(#(#(#8! '#$(for instance C(1,1,1)C(0,1,1)>C (1,0,0) rules out KAZ0M d7__M dd$<<br_1(1,1)=1, br_1(q_2,q_3)=0x  @87X@x  @87X@x  @87X@_br_br_q _q+1R_(_1B_,_12_)"_1_,+1R_(B+2_,+3_) _0_J _K otherwise). At this configuration, (1,0,0) is the unique Nash equilibrium.  }*[  Remark 9  Theorem 2 is reminiscent of the main theorem in Moulin and Shenker [1992]. There the main property in the characterization of the serial cost sharing method is existence and uniqueness of Nash equilibrium of the demand game (that holds at every profile of convex preferences). However, the assumption of  _ anonymity (if 3aZ0=  __=dd$<<Q_i=Q_jx  @87X@x  @87X@x  @87X@_Q+iZ_Q+j_3 and 3Z0= __=dd$<<q_i=q_jx  @87X@x  @87X@x  @87X@_q+iZ_q+j_3 then 3Z0=R __=dd$<<x_i=x_jx  @87X@x  @87X@x  @87X@_x+iZ_x+j_3) plays a key role in that result whereas it is absent in Theorem 2 (in our model with indivisible units of output, we cannot require anonymity: none of the incremental methods is anonymous). Another important assumption in that result is the differentiability of the cost  _ share Z0#__dd$<<x_ix  @87X@x  @87X@x  @87X@_x+i with respect to Z0#__dd$<<q_ix  @87X@x  @87X@x  @87X@_q+i. Thus Theorem 2 is a more compelling characterization result that relies only on the "unique Nash equilibrium" property.  }*  Remark 10  By analogy with the next two results (Theorems 3 and 4) it is easy to enounce variants of Theorem 2 by imposing either one or both of the two following requirements: a) the demand game should have at least one strong equilibrium at every profile  _# in [0-)__dd$<<Delta_Nx  @87X@x  @87X@x  @87X@_+N; b) the cost shares S![0M-)__Mdd$<<x_i(q,C)x  @87X@x  @87X@x  @87X@_x+iZ_qJ_C_(_,_)S should depend continuously on the cost function C. By combining property ii (or iii) in Theorem 2 and property a above, we characterize the set of incremental methods satisfying Cross Monotonicity. By combining property ii (or iii) and property b above, we characterize the cost sharing mechanisms in IC(Q) (Definition 7). By combining property ii (or iii), property a and property b, we characterize the simple mechanisms of SIC(Q) (Definition 7). @'$0*((! %< $'# $@Ԍ }* ԙ 11. Coalition StrategyProof Social Choice Functions  }*N  Definition 11 Social Choice Functions   _ Given are Q and OA[0H 88dd%<<c epsilon  (Q)x  @87X@x  @87X@x  @87X@8c8Q8 8p8(`8)O. A social choice function is a mapping F from a[0W#__dd%<<Delta_Nx  @87X@x  @87X@x  @87X@_+N  8 into the set of feasible allocations [0$ 88dd%<<t x  @87X@x  @87X@x  @87X@8t:  __  XX V! #(#X~ ddddd/Qdd%x{  =\{(q,x) epsilon [`0,Q`] x  _+^N ~line~ sum_N x_i=C(q)\}~ \and~R epsilon Delta_N ~ ~ F(R)=(q,x) epsilon  x  @87X@x  @87X@x  @87X@ta | ~._G{(,)x[0~,]l (\ ) }()(,)7q'xQxN% +N x, Ri C qanddRRNNF>Rqx  = I 9IV$XX%%_XX%%!! X%$ XX We denote agent i's allocation at R by [0 __dd%<<?F_i(R)=(q_i,x_i)x  @87X@x  @87X@x  @87X@_F+iZ_R:_q+i_x+i_(_)_( _,R_)J_?߼.  }*  Definition 12  We say that the social choice function F is strategyproof on the domain  _ [0__dd%<<Delta_Nx  @87X@x  @87X@x  @87X@_+N if we have  _ A #xddddd"dd%xB$ 2 `  (48) ăoforall R epsilon Delta_N~forall i epsilon N~~ forall R hat _i epsilon Delta_i~~F_i(R) R_i F_i(R line^i R hat_i)x  @87X@x  @87X@x  @87X@_z_z_z' _ _R+N_i_N_R+i_+i__F+i _R _R +ig _F +i _Rw i _RG+i_ c__ e_ _} }/ _( _)7 _(_)߉$(#(# (#(#!A '#$(if (48) is violated, we say that i manipulates at [0Z88dd%<<oRx  @87X@x  @87X@x  @87X@8Ro by \0<__dd%<<R hat_ix  @87X@x  @87X@x  @87X@D}_R+i).  80 We say that F is coalition strategyproof if for all coalition !\0LO88dd%<<oSx  @87X@x  @87X@x  @87X@8So, A\0O88dd%<<S  Nx  @87X@x  @87X@x  @87X@8S8N8, and any  8 two preference profiles a\0;88dd%<<oRx  @87X@x  @87X@x  @87X@8Ro and \088dd%<<R hatx  @87X@x  @87X@x  @87X@DV8R we have  8  Xt a # $X ddddd5dd%x{q$ 2 `P0 (49) ă\{forall j NOTIN S~R_j=R hat_j~\and~forall i epsilon S~F_i (R hat) R_i`F_i(R) \} => \{ forall i epsilon S~ F_i(R hat) I_i F_i(R)\}x  @87X@x  @87X@x  @87X@_{ _( _) _( _)i_}Y_>_{:_(*_)B_(2_)_}_zz___z_I_z_j_S_RB+j _R+j2_andj_iC_S _F +i[ _RK _R +i1 _F +iy _R_i_Sj_F+i_R_I"+ir_F+i_R<} }}_ 9_ ߾$XXd&d&XXd&d&!a Xc&$ Xt (if (49) is violated, we say that S manipulates at \088dd%<<oRx  @87X@x  @87X@x  @87X@8Ro by \088dd%<<R hatx  @87X@x  @87X@x  @87X@DV8R).  }*   Lemma 8   _g Given \0` 88dd%<<oQx  @87X@x  @87X@x  @87X@8Qo, g]0 __dd%<<C epsilon  _{imc}(Q)x  @87X@x  @87X@x  @87X@_Cp+imc_Q_ _`_(P_)g, and an incremental cost sharing method !]0>88>dd%<<xi epsilon I C (Q, C)x  @87X@x  @87X@x  @87X@88 8I[8CK8Q;8C8(8,8)߂, the canonical equilibrium (property (37)) of  defines a social choice function F: F(R)=e(R,) for all R.  _Q i) This social choice function is strategyproof in the domain A]0xp__dd%<<Delta_Nx  @87X@x  @87X@x  @87X@_+N.  _ ii) It is coalitionstrategyproof on the domain 9a]0n !__ndd%<< Delta_N (xi)x  @87X@x  @87X@x  @87X@_s_+N_(_)9. iii)  If  is cross monotonic (property (19)) it is coalition strategyproof on  _0 the domain ]0O#__dd%<<Delta_Nx  @87X@x  @87X@x  @87X@_+N.  _  Proof of Statement i Fix a profile R, an agent i, and a misreport ]0$__dd%<<R hat_ix  @87X@x  @87X@x  @87X@D}_R+i by agent  _ i. Set F(R)=(q,x) and ]0E %__Edd%<<#F(R line ^i R hat_i)=(q hat, x hat)x  @87X@x  @87X@x  @87X@_F_Ri_R+iR_qB_x_(_)_(_,_)z_ b_L}v_f_. Assume ']0&88dd%<< q != q hatx  @87X@x  @87X@x  @87X@8q8q8c&8' (otherwise property (48)  8 is obvious) and that the two sequences ^0''88'dd%<<q^k x  @87X@x  @87X@x  @87X@8qzk and !^0''88'dd%<<q hat ^kx  @87X@x  @87X@x  @87X@688qzk (constructed by (37) and (8))  8! differ for the first time at k+1. Then at node A^0'p'88'dd%<<v^kx  @87X@x  @87X@x  @87X@8vzk, player i must have the move.  8" If #a^0(88dd%<<v^{k+1}x  @87X@x  @87X@x  @87X@8vzkzCz1# is right of ^0' (88'dd%<<v^kx  @87X@x  @87X@x  @87X@8vzk and 9^0(88dd%<< v hat ^{k+1}x  @87X@x  @87X@x  @87X@688vzkzCz19 is left, we have by (37)  8#  #x)ddddd*dd%x=Z(q_i,x_i(q)) R_i(q_i^k + 1, x_i (q^k + e_i)) P_i (q_i^k, x_i(q^k))=(q hat _i, x_i (q hat))x  @87X@x  @87X@x  @87X@_(Z_,_(_) _)R_(D_1_, _( _)> _) _(_,H_(_):_)*_(r_,_(_)"_)_q +i_xR+i_q_R+i_q|kJ:i4_x+i| _q. k _ev +i _P6 +i _qk~:ix_x+i_qrk_q"+i_xj+i2_q_~ ___V_=ߺ$(#(##(#(#! '#$hence agent i strictly loses by misreporting. If #^08k,88dd%<<v^{k+1}x  @87X@x  @87X@x  @87X@8vzkzCz1# is left of ^0'k,88'dd%<<v^kx  @87X@x  @87X@x  @87X@8vzk and 9_0!k,88dd%<< v hat ^{k+1}x  @87X@x  @87X@x  @87X@688vzkzCz19 is right, the analysis in Step 1 of the proof of Lemma 6 shows that `'%0*((AX~ % ! %'#A %X c&Ga %)'#$, %`Ԍ 8  #xdddddjdd&xstack {alignl (q_i, x_i(q))=(q_i^k, x_i(q^k)) R_i (q tilde_i, x_i (q tilde )) # ~ # alignl for~all~ q tilde~s.t. q tilde_i > q_i^k~\and~q tilde _j epsilon Y_j^k~all~j!= i}x  @87X@x  @87X@x  @87X@(Z,() )(t,(6 ) ) (> , (v))^.^.^>q ixRiqrq$Ukixli4q<k& R in q i x6 i q^for^all^qb^sR^tB^q*i^q<k 9i^and ^q$ *j ^Y kU 9j/ ^all^j^ig^c "^f^ ^t ^ ߖ$(#(#(#(#! '#$  (see relation (31)). As '!_07t 887dd&<< q hat^{k'}x  @87X@x  @87X@x  @87X@688qzkdd' coincides with A_0X 88Xdd&<<q^k'x  @87X@x  @87X@x  @87X@8qzkdd$ up to k, the above preference  8 relation holds for a_0 88dd&<<q hatx  @87X@x  @87X@x  @87X@688q and the proof is complete.   }*  Proof of Statement ii  Fix a profile R with F(R)=q, a coalition S, and a  8 misreport _0 88dd&<<R hatx  @87X@x  @87X@x  @87X@DV8R by S with n_0 88dd&<<F(R hat) = q hatx  @87X@x  @87X@x  @87X@8F8Rj8q8(z8)4V88n. Again, consider the first index k after which  8 the two sequences _0' 88'dd&<<q^kx  @87X@x  @87X@x  @87X@8qzk and _0'88'dd&<<q hat ^kx  @87X@x  @87X@x  @87X@688qzk (associated with `088dd&<<F(R)x  @87X@x  @87X@x  @87X@8F8R8(z8) and 5!`088dd&<< F (R hat)x  @87X@x  @87X@x  @87X@8F8R8(z8)4V5 respectively)  8 differ. The player i who has the move at HA`088dd&<< v^k=v hat^kx  @87X@x  @87X@x  @87X@8vzk8v>zk88H must be a member of S (otherwise the two sequences still coincide at k+1). Because the profile R is  _ generic a`07W__7dd&<< (R epsilon Delta_N (xi))x  @87X@x  @87X@x  @87X@_(L_(4_)_)_R+N_ c__ ߆, player i strictly prefers `0 ;__ dd&<<$(q^{k+1}, x_i(q^{k+1}))= (q,x_i (q))x  @87X@x  @87X@x  @87X@_(1 _,S_(1L_)_)_(_,_( _)T _)_qk_x+i_q\k,_q_x+id _qk<_ߒ to  _- (`0L__dd&<<c!q hat ^ {k+1}, x_i (q hat ^ {k+1}x  @87X@x  @87X@x  @87X@6_w__qk _x+iS_qk4C1_,_(1c)). Hence, the analysis in Step 1 of the proof of Lemma 6 implies  _> that player i strictly prefers v`0=]__=dd&<< (q,x_i(q)) x  @87X@x  @87X@x  @87X@_(_,J_(:_)_)_qz_x+i_qv to `0]__dd&<<(q hat, x_i (q hat)x  @87X@x  @87X@x  @87X@_(_,J_(:_)___qz_x+i_qߐ).  }*  Proof of Statement iii  The proof is similar to that of statement ii. Using the same assumption and notation as above, we suppose that every player in S  _( weakly benefits in the misreport a0G88dd&<<R hatx  @87X@x  @87X@x  @87X@DV8R !a0G__dd&<<V(F_i( R hat) R_i F_i(R)x  @87X@x  @87X@x  @87X@_(Z_(J_)b_(R_)_F +i_R_RB+i_F+i_R}V all Aa0vfe88vdd&<< i epsilon Sx  @87X@x  @87X@x  @87X@8i8S8 ) and we show that  _; none of them strictly benefit aa0hZ__dd&<<U(F_i(R hat) I_i F_i(R)x  @87X@x  @87X@x  @87X@_(Z_(J_)b_(R_)_F +i_R_IB+i_F+i_R}U). We copy the proof of statement  8N i in Lemma 7. If k is the first index after which a0'm88'dd&<<q^kx  @87X@x  @87X@x  @87X@8qzk and a0'm88'dd&<< q hat ^kx  @87X@x  @87X@x  @87X@688qzk differ we note  88 that agent i who has the move at a0'W88'dd&<<v^kx  @87X@x  @87X@x  @87X@8vzk (and is a member of S) must be indifferent  _" between 1a0]___]dd&<<F_i(R)x  @87X@x  @87X@x  @87X@_F+iZ_R_(_)1 and Gb0]! A__]dd&<< F_i( R hat)x  @87X@x  @87X@x  @87X@_F+iZ_R_(_)}G !b0___dd&<<(q hat _i = q_i+1x  @87X@x  @87X@x  @87X@_(_1__q +i_qR+iZ__ and property (43) where Ab0K_88dd&<<q hatx  @87X@x  @87X@x  @87X@688q replaces ab0 _88dd&<<q tildex  @87X@x  @87X@x  @87X@688q).  85 Moreover, by cross monotonicity, no player 4b0}|T88}dd&<<j, j!= ix  @87X@x  @87X@x  @87X@8j8j8i8,z8c4, suffers when player switches  _ from b0"__dd&<<R hat _ix  @87X@x  @87X@x  @87X@D}_R+i to b0) @__dd&<<R_ix  @87X@x  @87X@x  @87X@_R+i:  _ u #x5ddddd] dd&x4F_j(R hat line^i R_i) R_j F_j (R hat )~~~all~ j~!= ix  @87X@x  @87X@x  @87X@_F+jZ_R"ir_R+i_R:+j_F +j_R_all _j _i_(B_)Z_(J_)}}_ Z _cu$(#(#(#(#! '#$Therefore rb0__dd&<<( R hat line ^i R_i) x  @87X@x  @87X@x  @87X@_(r_)}_RRi_R"+i_ r is a misreport by coalition S\i where all agents in S\i weakly benefit (and one of them strictly benefits) and we can proceed (as in the proof  }*l of Lemma 7) by induction on the size of S. QED  }*  Remark 11  A slightly stronger equilibrium statement holds true for the social choice functions associated with an incremental csm. If preferences are generic, then all Nash equilibrium profiles of the direct revelation game (where player i's strategy is any generic preference profile and the outcome is computed by the social choice function itself) yield the truthful outcome (i.e. the canonical equilibrium for the true preferences). If the incremental method is cross monotonic, then all strong equilibrium profiles of the direct revelation game yield almost the truthful outcome (where property (38) gives the meaning of "almost"). Our final characterization theorems use two additional properties of social choice functions.  _$ Consumer Sovereignty:  for all c0v*88vdd&<< i epsilon Nx  @87X@x  @87X@x  @87X@8i8N8 , all !c0C*b*__C*dd&<<q_i^* epsilon [`0,Q_i`]x  @87X@x  @87X@x  @87X@_q:i_QR+i_ T_[_0Z_,_]ߔ there exists a preference SAc0P*1$*__P*dd&<<R_i^* epsilon Delta_ix  @87X@x  @87X@x  @87X@_R:i+i_ T_S  _% such that: ac0X*+__X*dd&<<H% forall R epsilon Delta_N~\{R_i=R_i^*x  @87X@x  @87X@x  @87X@_z__R+N_R+id_R:i_ c__{H and ^c0n *H+__n *dd&<<F_i(R)=(q_i,x_i)\} => q_i=q_i^*x  @87X@x  @87X@x  @87X@_F+iZ_R:_q+i_x+i2_q+iz_q:i_(_)_( _,R_)_}_>J_B__ ^. This is reminiscent of the condition of citizen sovereignty in classical@'&0*((!'# &5'#s &@ social choice. For a social choice function derived from an incremental method,  _ agent i is guaranteed to consume c0__dd'<<q_ix  @87X@x  @87X@x  @87X@_q+i by reporting a preference focusing on c0!__dd'<<q_ix  @87X@x  @87X@x  @87X@_q+i (as defined immediately after property (45)): indeed for such a preference, her  _C strategy c04b__dd'<<q_ix  @87X@x  @87X@x  @87X@_q+i strictly dominates every other strategy in the demand game. No Exploitation:  #x ddddd^dd'x%Xfor~all~i epsilon N, ~all~ R epsilon Delta_N:~\{F_i(R)= (q_i,x_i)~\and~q_i=0\} => `x_i=0x  @87X@x  @87X@x  @87X@_for_all_ik_N_alls_R+N} _F +i _R _q%+i_xm+i_andM_q+i_x +i _ _ L__,5 _: _{M _(= _)- _(u_,_)_0 _}_>_0 ___[_%ߢ$(#(#(#(#! '#$Theorems 3 and 4 (the two main results of the paper) characterize the social choice functions associated with incremental cost sharing methods respectively in the context of a fixed cost function and of a variable cost function. In the former case we must assume that the cost function is generic  8 (unless <d0-88-dd'<<line N line =2x  @87X@x  @87X@x  @87X@8 8 *8b8N82<) and in the latter case we don't, however we add a requirement of continuity.  Theorem 3 Fixed Cost Function  _( Given Q, h!d0 __dd'<<C epsilon  _{imc} (Q)x  @87X@x  @87X@x  @87X@_Cp+imc_Q_ _`_(P_)h and a social choice function HAd0]G88]dd'<<F epsilon  ^{Delta _N}x  @87X@x  @87X@x  @87X@8FddtN8 8H, consider the two statements  8 i) There is a cross monotonic incremental cost sharing method pad0>L88>dd'<<xi epsilon IC(Q,C)x  @87X@x  @87X@x  @87X@88 8ICK8Q;8C8(8,8)p such that F is welfare equivalent to the associated social choice function: t#x#ddddd[dd'xstack {alignl forall R epsilon Delta_N~F(R)~is~a~strong~equilibrium ~ of~(R, xi): # ~ # alignl F(R)=e(R, xi ) ~\or~e(R, xi)+e_i~(see(38))} x  @87X@x  @87X@x  @87X@z^ ^RNFRis$astrong  equilibriumof\R^F^Rj^eZ^R^or^e^R ^e *i ^see cLJ^^( )(,)4:^(z^)^(^,^)J^(:^," ^): ^( ^( ^38^)^)t$(#(#q(#(#!'#$ Xt  Xt ii) The scf F satisfies Consumer Sovereignty, No Exploitation and is coalitionstrategyproof.  8P If <d0-o88-dd'<<line N line =2x  @87X@x  @87X@x  @87X@8 8 *8b8N82< (or if at most two agents are active in Q) properties i and ii are  _ equivalent. If @d0- r88-dd'<<line N line  3x  @87X@x  @87X@x  @87X@8 8 *8b8N83@ and if \d0s*==__s*dd'<<C epsilon  _{imc} ^{**}x  @87X@x  @87X@x  @87X@_Cp:imc_ _p\ (d0xr88dd'<<oQx  @87X@x  @87X@x  @87X@8Qo) properties i and ii are equivalent as well. Note that at any generic preference profile R, an incremental method has a unique strong equilibrium, hence in statement i the social choice function F  8 picks exactly the canonical equilibrium Ce0P!88dd'<<e(R,xi)x  @87X@x  @87X@x  @87X@8e8R8(z8,b8)8C.  _Y When the cost function varies in <!e0x"__dd'<< _{imc}(Q)x  @87X@x  @87X@x  @87X@_+imc_Q_(w_)<, we write our social choice functions as F(R,C) (this abuse of notation does not create any confusion). We say that the scf F is continuous for all C and for almost all profiles, if it is  8 a continuous mapping with respect to C, when $Ae0D$88dd'<< (Q)x  @87X@x  @87X@x  @87X@88(8)8Q$ and ae0J$88dd'<<t x  @87X@x  @87X@x  @87X@8t are equipped with their natural topologies. (See Definition 13 in Appendix 3 for details).  }*  Theorem 4 Variable Cost Function   _" Given Q and a social choice function F (a mapping from e0%(__dd'<<Delta_Nx  @87X@x  @87X@x  @87X@_+N . <e0%(__dd'<< _{imc}(Q)x  @87X@x  @87X@x  @87X@_+imc_Q_(w_)< into  8" e0)88dd'<<t x  @87X@x  @87X@x  @87X@8t) the two following statements are equivalent:  8# i) There exists a simple incremental cost sharing method  ]e0V)88Vdd'<<epsilon S I C (Q)x  @87X@x  @87X@x  @87X@8 s8S8Ic8CS8Q8(8)] such that F is the associated social choice function:  X !#x]+ddddddd'xNforall R epsilon Delta_N~ forall C epsilon  _{imc} (Q)~F(R,C)=e(R, xi (C))x  @87X@x  @87X@x  @87X@_z_z_ __R+N_Cz+imc_Q*_F_R _Cr _eb _R: _C_ c__ R _j_(Z_)_(_, _) _( _, _( _)*_)$(#(#>%(#(#!!'#$ii) The scf F satisfies Consumer Sovereignty, No Exploitation and is coalitionP''0*((1 '# ''#']+'#}-!'P strategyproof and continuous.  }*  12. Concluding Comments  Many questions are left open within our strategic model of cost sharing with indivisible units of output. First of all how robust are the characterization results to the weakening of certain assumptions? What family of cost sharing methods are characterized if we weaken coalition strategyproofness into strategyproofness in Theorems 3 and 4? If we drop Consumer Sovereignty in Theorems 3 and 4? What about the variant of Theorem 2 where we look for the larger family of csms guaranteeing the existence of a  _{ Nash equilibrium (resp. of a strong equilibrium) at every profile in f0__dd(<<Delta_Nx  @87X@x  @87X@x  @87X@_+N? What becomes of Theorems 2 and 3 when the cost function is not generic? Another direction that should be explored relates the current model to the more familiar model with divisible outputs of the (mostly axiomatic) literature  _ on cost sharing. In the case of unit capacities, !!f08+__dd(<<Q_i=1x  @87X@x  @87X@x  @87X@_Q+i_Z_1! for all i (the standard TU cooperative games model), Theorems 3 and 4 characterize the sets of elementary incremental cost sharing methods (given by (1)). There the only choice left to the discretion of the mechanism designer is the ordering of the agents. When capacities grow large, on the other hand, there are many more methods to choose from. The divisible output model appears more amenable to axiomatic selection among of incremental cost sharing methods. To derive the model with divisible goods as the limit of the current indivisible goods model, we could use a standard replication technique. Start  8 from a capacity profile Q and a cost function C in $Af088dd(<< (Q)x  @87X@x  @87X@x  @87X@88(8)8Q$. In the kreplication  _ of 1af0}88}dd(<<(Q, C)x  @87X@x  @87X@x  @87X@8(8,8)8Qz8C1 a demand by agent i such as Tf0-__-dd(<< (q_i,k_i)x  @87X@x  @87X@x  @87X@_(Z_,_)_q +i_kR+iT, where of0__dd(<<0k_i  k1x  @87X@x  @87X@x  @87X@_0:_1____k+iJ_ko, represent f0"__dd(<<q_ix  @87X@x  @87X@x  @87X@_q+i  _ big units and a fraction  f0t__dd(<<k_i/kx  @87X@x  @87X@x  @87X@_k+iZ_k_/  of the next unit (thus the new demand interval has  _ cardinality !g0` __dd(<<k. Q_ix  @87X@x  @87X@x  @87X@_k_Q+i_.!); the cost function is then extended by linear interpolation  8 to the new grid T!g0 88dd(<< [`0,k.Q`]x  @87X@x  @87X@x  @87X@8[808,8.8]8k8QT (we omit the details). Here is one example of a csm that is the limit of a sequence of simple incremental methods in the indivisible goods models. Suppose the simple incremental methods in each replication are described by a path ((8)) appproximating the straight line from 0 to k.Q. Then in the limit, a certain generalization of serial cost sharing (Moulin and Shenker [1992]) obtains. Given  _E ]Ag0d!88dd(<<q epsilon [`0,Q`]x  @87X@x  @87X@x  @87X@8qi8Q8 8[y808,8]], set gag0 d!__dd(<< r_i=q_i/Q_ix  @87X@x  @87X@x  @87X@_r+iZ_q+i_Q"+i_*_/g and order the agents so that g0Ud!__Udd(<<:r_1 r_2...r_nx  @87X@x  @87X@x  @87X@_rR_rr_r+n+1+2_. _._.___:߷. Then compute individual cost shares as follows: +A#x#dddddkdd(xstack {alignl x_1 = Q_1 . INT _0^{r_1} partial _1 C(tQ)dt~;~x_2=Q_2. \{ int _0^{r_1} partial _2C(tQ)dt+ int _{r_1}^{r_2} partial _2 C(tQ line ^1 q_1) dt\} # ~ # alignl x_n=Q_n. \{` int _ 0^{r_1} partial_n C(tQ)dt+...+ int_{r_{n1}}^r_n partial _n C(q line ^n t_n Q_n) dt\}} x  @87X@x  @87X@x  @87X@xRQ(rdCTtQdtx Qb r CtQdtr|r0C tQqdtxnZQnSrnCtQZdtY Srdd 1n Frdd= $nQ n C qY nt)nyQndt11.ddxg1|01(D);L 2 2 .T {dd g1 |0N 2(~)ddDg2ddZ12(`A1(1x)}*.{dd11{F0z().: . .dd $1 (I)},  ,, R,J* ddy $ ,  L L^L0TL TL+$(#(#(#(#8!A'#$This formula is very different from the AumannShapley pricing formula (see Taumann [1988]), if only because the latter fails Demand Monotonicity (Moulin [1994]). Maybe the replication argument will shed some light on the connection between this model and the results on strategyproofness in Shenker [1992]. 0&(,++#'#$(A(0  }*  XX *& FOOTNOTES ă 1. The huge literature on values of cooperative games starts with Shapley [1953]. For a discussion of its applications see Young [1985]. 2. From Billera and Heath [1982] to the recent surveys of Taumann [1988] and Young [1994], attention has been focused on a particular formula known as the AumannShapley pricing method. Other methods have been recently discussed as well: McLean and Sharkey [1994], Moulin [1994]. 3. See the differentiability assumption on the cost sharing method in Moulin and Shenker [1992] and the smoothness assumptions on the social choice functions in Shenker [1992], or Satterthwaite and Sonnenschein [1981]. 4. Their arithmetic average is the Shapley value. Their convex hull is the set of probabilistic values (Weber [1988]). A TU cooperative game is concave if and only if every vector is in the core (Ichiishi [1981]). 5. The characterization is exact if we add a requirement of continuity w.r.t. the cost function (Theorem 4). Otherwise, there exist a few more coalition strategyproof methods quite similar to the above, except that the ordering in which players 2,...,n are called upon may depend upon the actual demand of player 1. See Theorem 3. On the other hand, there are many more methods of which the demand game is always dominancesolvable or has a unique Nash equilibrium at almost all preference profile: see Theorems 1 and 2 and the discussion in the last paragraph of this section. 6. We have 1,260 such methods, of which 6 are the elementary incremental formulas. For instance, the method (1) corresponds to the sequence 111122233. 7. A tree is a connected graph with no cycle. There is a unique path from the origin to any given node of the tree. A node v is non terminal if there is another node w such that the unique path from 0 to w goes through v. We say that  8. node g0M88dd)<<v'x  @87X@x  @87X@x  @87X@8vz is a successor of node v if the unique path from 0 to g0M88dd)<<v'x  @87X@x  @87X@x  @87X@8vz reaches v  8 immediately before reaching g0788dd)<<v'x  @87X@x  @87X@x  @87X@8vz; then we also say that v precedes h0.788dd)<<v'x  @87X@x  @87X@x  @87X@8vz.  _ 8. For any n and !!h0 __dd)<<Q_i=1x  @87X@x  @87X@x  @87X@_Q+i_Z_1! for all i, compute a#xdddddldd)x9mu (Q)=n!~;lambda (Q)= n.(n1)^2.(n2)^2^2 ...(2)^2^{n2}x  @87X@x  @87X@x  @87X@8688(8)8!8;8(8) 8.8(81a 8) z2) 8. 8( 82 8) z2ddI 2 8. 8.u8.8(e828)Uz2dd28Qv8n)8Q8n8n 8nddn88q8 8ddߋ$(#(#(#(#!a'#$9. Most cost sharing methods discussed so far by the axiomatic literature (in the model with variable demands) are additive: the AumannShapley pricing rule, the ShapleyShubik method as well as the serial method discussed in Moulin [1994]. 10. Here we call a game dominancesolvable if there is an iterated elimination of weakly dominated or equivalent strategies converging to a single strategy profile: this profile is called a sophisticated equilibrium. This definition is less demanding than the original one (Moulin [1979]) where only weakly dominated strategies can be eliminated. As usual, we call a game strictly dominancesolvable if the iterated elimination of strictly dominated strategies converges to a singleton. 11. A strategy profile q is a strong equilibrium if there is no coalition S,  8\% Ah0+88dd)<<S  Nx  @87X@x  @87X@x  @87X@8S8N8, objecting to q by the profile ah0{+88dd)<<q'x  @87X@x  @87X@x  @87X@8qz. We say that S objects to q by h0 {+88dd)<<q'x  @87X@x  @87X@x  @87X@8qz if  _F& Eh0=*e,__=*dd)<<q_j=q_j'x  @87X@x  @87X@x  @87X@_q+jZ_q:j_E for all h0q ,88dd)<< j NOTIN Sx  @87X@x  @87X@x  @87X@8j8S8ј, no player in S strictly prefers q to h0:~,88dd)<<q'x  @87X@x  @87X@x  @87X@8qz and at least one  8p'  X player in S strictly prefers i0-88dd)<<q'x  @87X@x  @87X@x  @87X@8qz to q. 0Z(),++'#!a)0  }*  ((   #d6X@8;@#B APPENDIX 1: PROOF OF LEMMA 3 ă  _ We fix !i0 __dd*<< Q,C epsilon  _{imc} (Q)x  @87X@x  @87X@x  @87X@_Q_C`+imc_Q_,P_(@_)z_ _ ߊ and sAi088dd*<<xi epsilon  (Q,C)x  @87X@x  @87X@x  @87X@88 8c8(S8,C8)8Q8Cs.  8  Step 1 If ai0 88dd*<<qxix  @87X@x  @87X@x  @87X@8q is in IC(Q,C) then i0a 88dd*<<qxix  @87X@x  @87X@x  @87X@8q is acyclic . Set Hi0 88dd*<< T=phi (xi)x  @87X@x  @87X@x  @87X@8T88-88(g8)H and fix a demand  8_ profile q, and a coalition S contained in i0 88dd*<<B(q)x  @87X@x  @87X@x  @87X@8B8q8(z8). Let i0~ 88dd*<< \{v^1,..,v^K\}x  @87X@x  @87X@x  @87X@8{z1k8,8.[8.8,M8}8vK8vzK ߉ be the path associated with q by (q) and let k be the first index at which a member of S has the move and goes left:  _  zj0 __dd*<<Iv^k epsilon V_i~for~some~ i epsilon S~\and~v^{K+1}~\left~successor~of~v^kx  @87X@x  @87X@x  @87X@_vku_V+i_for]_some_in_S>_and _v K _left_ successor_of_vk_  _  / 1z  _ Note that if no such index exists then 3!j0= __=dd*<<q_i=Q_ix  @87X@x  @87X@x  @87X@_q+iZ_Q+i_3 contradicting the construction of  8 S. Obviously agent i satisfies (17): indeed for all q', MAj0X88dd*<<q q'  Qx  @87X@x  @87X@x  @87X@8q8q78Q8z8M property (11)  _ implies ^aj0J *__J *dd*<<\{q_i'=q_i => x_i(q')=x_i(q)\}x  @87X@x  @87X@x  @87X@_{_>b_(_)W_(G_)_}_q :i_qR+i_x+i_q_x+i_qZ__k_^ and j0 *__ *dd*<<9$\{q_i'=q_i+1 => x_i(q')=x_i(q+e_i)\}x  @87X@x  @87X@x  @87X@_{_1 _>R_(_)G_( _) _}_q :i_qR+i_x+i_qw_x+i_q _e/ +iZ___[_7 _9߶.  8X  Step 2 If j0w88dd*<<qxix  @87X@x  @87X@x  @87X@8q is acyclic, the following property holds:  _  j0K__Kdd*<<XEXISTS i epsilon N~Q_i >0~\and~ FORALL q epsilon [`0,q`]~\{q_i=1\} => \{x_i(q)=C(e_i\}x  @87X@x  @87X@x  @87X@_y _z _ ___ic_N3_Q+iK_and_q_q _q0 +iP_x+i_q_C_ep+i_ _ _>{_0\_[_0b_,h _]8 _{ _1p _}` _> _{ _(_)x_(_}ߌ (50) When property (17) holds at q, S for agent i we write AC(q,S,i). In order to prove (50) we can obviously ignore all inactive players, so we now assume,  _ without loss of generality, that all players are active j0%__%dd*<<(Q_i >0 ~for~all~i)x  @87X@x  @87X@x  @87X@_(Z_>_0_)_Q +i_forb_all"_i߂.  8S By acyclicity of k0 r88dd*<<qxix  @87X@x  @87X@x  @87X@8q at 0 for n (as B(0)=N), there is an agent (necessarily  _! unique; see above?) say agent 1, such that AC(0N,1). We show that !k0@@__dd*<< x_1(q)=C(e_1)x  @87X@x  @87X@x  @87X@_xR_q