WPC 2 BJ ZCourierCourier 10cpix6X@KX@HP LaserJet Series IIHPLASEII.PRSx6X@8;,t0J`X@#|x2<vp k|CourierCourier BoldHPLASIIP.PRSx6X@8;,8t0tX@a8DocumentgDocument Style StyleXX` `  ` a4DocumentgDocument Style Style . a6DocumentgDocument Style Style GX  2kv)ta5DocumentgDocument Style Style }X(# a2DocumentgDocument Style Style<o   ?  A.  a7DocumentgDocument Style StyleyXX` ` (#` BibliogrphyBibliography:X (# 2E   )a1Right ParRight-Aligned Paragraph Numbers:`S@ I.  X(# a2Right ParRight-Aligned Paragraph Numbers C @` A. ` ` (#` a3DocumentgDocument Style Style B b  ?  1.  a3Right ParRight-Aligned Paragraph Numbers L! ` ` @P 1. ` `  (# 2  { C a4Right ParRight-Aligned Paragraph Numbers Uj` `  @ a. ` (# a5Right ParRight-Aligned Paragraph Numbers _o` `  @h(1)  hh#(#h a6Right ParRight-Aligned Paragraph Numbersh` `  hh#@$(a) hh#((# a7Right ParRight-Aligned Paragraph NumberspfJ` `  hh#(@*i) (h-(# 2E  + a8Right ParRight-Aligned Paragraph NumbersyW"3!` `  hh#(-@p/a) -pp2(#p a1DocumentgDocument Style StyleXqq   l ^) I. ׃  Doc 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 Technical2GUa5TechnicalTechnical Document Style)WD (1) . a6TechnicalTechnical Document Style)D (a) . a2TechnicalTechnical Document Style<6  ?  A.   a3TechnicalTechnical Document Style9Wg  2  1.   2PDa4TechnicalTechnical Document Style8bv{ 2  a.   a1TechnicalTechnical Document StyleF!<  ?  I.   a7TechnicalTechnical Document Style(@D i) . a8TechnicalTechnical Document Style(D a) . 2!7!EQPleadingHeader for numbered pleading paperP@n   $] X X` hp x (#%'0*,.8135@8:__dd<< q_1,...q_nx6X@8;X@x6X@8;X@x6X@8;X@_q_q:+n+1_,R_._.B_.e we write Ja0HJHJdd<< q= sum _i q_ix6X@8;X@x6X@8;X@x6X@8;X@q+ieqRi9IJ. In average  _ cost pricing, agent i pays 0uX__udd<<Qx_i=(q_i/q) . C(q)x6X@8;X@x6X@8;X@x6X@8;X@_x+i_qR+i_q_Cr_q_Z_(_/_) _._(_)Q. In marginal cost  _ pricing, 0__dd<<Gx_i=q_i . C'(q)+alphax6X@8;X@x6X@8;X@x6X@8;X@_x+iZ_q+i_C_q_3_*_.__(O_)?_G, where the "fixed fee" 088dd<<talphax6X@8;X@x6X@8;X@x6X@8;X@8t is the same for all agents (and is determined by budget balance). In the Shapley  _[ Shubik mechanism, 0 __dd<<x_ix6X@8;X@x6X@8;X@x6X@8;X@_x+i is the Shapley value of agent i in the cooperative game (with transferable utility) associating to each   coalition S its Stand Alone cost 0J(Jdd<<3V(S)=C( sum _S q_i)x6X@8;X@x6X@8;X@x6X@8;X@VSjC6+Sq=Ri(z)()Z9I3߰ (Shubik [1962],  _ Young [1985]). In serial costsharing, the cost share !0x__dd<<x_ix6X@8;X@x6X@8;X@x6X@8;X@_x+i is given by formula (1); an alternative characterization is the property  _> that A0~__dd<<x_ix6X@8;X@x6X@8;X@x6X@8;X@_x+i does not depend upon those demands a0~__dd<<q_jx6X@8;X@x6X@8;X@x6X@8;X@_q+j (by other agents)  _( that are bounded below by 0h __dd<<q_ix6X@8;X@x6X@8;X@x6X@8;X@_q+i (as explained at the beginning of Section 7: see property (13) and the discussion thereafter).  ?  Given a cost sharing mechanism and a particular preference profile, we postulate in standard game theoretic fashion, that the non cooperative behavior of the participants will result in a  _R" choice of demands 0 (__dd<<=q_i,i=1,2...,nx6X@8;X@x6X@8;X@x6X@8;X@_q+iZ_i_n_,J_1_,:_2_.*_._._,_=ߺ forming a Nash equilibrium of the corresponding strategic game, if such equilibrium exists at all. We invoke the usual evolutive stories to explain how decentralized behavior by agents mutually ignorant about each other's\'0*((@@ preferences, converges toward a Nash equilibrium (see the comments at the end of Section 5). So if no Nash equilibrium exists at some preference profile (a very real possibility, as well shall soon see), we interpret it as a fundamental difficulty of the  ?@ decentralized play of our mechanism at this particular profile.2 Thus the first and foremost question about a mechanism is to determine on what domain of preferences it guarantees the existence of at least one Nash equilibrium. This question conceptually precedes any discussion of fairness and/or efficiency of equilibrium outcomes. Our first critique of average cost pricing (and of marginal cost pricing, as defined above) is that this mechanism fails to have any Nash equilibrium at all for some very well behaved profile of preferences (in fact, for preferences represented by quasilinear  _ utility functions of the form 0u __udd <<  u_i(q_i)x_i)x6X@8;X@x6X@8;X@x6X@8;X@_u+iZ_q+i_x+i_(*_)_)_ ߉: see Lemma 1. On the other hand Theorem 1 uncovers a reasonably rich family of simple mechanisms (containing serial cost sharing, the ShapleyShubik cost sharing mechanism, and more) where at least one Nash equilibrium exists on a reasonably rich domain of preferences (namely monotonic, convex and such that both goods are normal). This result is based on the fixed point techniques in lattices (more precisely the single crossing property discussed by Milgrom and Shannon [1991]). By contrast in the decreasing returns case (when the cost function C is convex) the familiar fixed point techniques in convex sets (Nash's theorem) show that many simple mechanisms (among them average cost pricing) guarantee at least one Nashj' 0*((@@  ? equilibrium on the domain of monotonic and convex preferences.3 On this domain I conjecture that, under increasing returns, there is  ?  no simple mechanism guaranteeing at least one Nash equilibrium. Next we turn to the normative properties of the equilibrium outcomes. We know that such outcomes will be inefficient in all  ? but exceptional cases.4 We focus on three familiar fairness tests that feed the discussion of first best solutions. The first one is the Stand Alone test (Faulhaber [1975], Sharkey [1982]) requiring that no agent (or coalition of agents) be asked to pay more than the cost of serving this agent (or coalition) alone:   0 J Jdd <<[Fx_iC(q_i)~(\or~sum_{i epsilon S} x_i C(sum_{i epsilon S} q_i))x6X@8;X@x6X@8;X@x6X@8;X@xRiZCJqRibor+i+SxRiC +iA +S qH Rim()(] ( ) )9I 9I+  + [. If each agent or coalition has access to the technology, this test has a positive interpretation as part of a core stability property (or equivalently, as a contestability argument: if the test fails for a certain coalition then it would be profitable for a firm to enter and serve this coalition). If the Stand Alone test is the central normative property of the natural monopoly literature, our second test, the No Envy property, is the most popular property of the distributive justice literature, where it conveys the idea of equal opportunity of consumption. A remarkably versatile concept, (see the survey by Thomson and Varian [1985]) it means in our context that no agent i  _d# strictly prefers another agent's net trade U0-)__-dd << (x_j, q_j)x6X@8;X@x6X@8;X@x6X@8;X@_(Z_,_)_x +j_qR+jU over her own net  _N% trade T!0-+__-dd << (x_i,q_i)x6X@8;X@x6X@8;X@x6X@8;X@_(Z_,_)_x +i_qR+iT.5 And finally, the Unanimity test (the less familiar of the tree tests, see Moulin [1990 a,b]), rules out the8' 0*((@@ possibility that an agent i benefits from the difference between his preferences and other agents' preferences. In our context,  _  this amounts to the inequality A0 8` __ dd <<x_i  {C(nq_i)}/ nx6X@8;X@x6X@8;X@x6X@8;X@_x+iZ_CJ_nqB+i_n__(_) _/ߒ: my cost share is at least what my fair share would be if every other agent had the same demand as my own. For first best (efficient) solutions of the natural monopoly problem, the Stand Alone and No Envy tests are generally incompatible. This is easily checked even in the simplest  ? configuration of demands.6 But the equilibrium outcomes of our simple mechanisms are inefficient, hence requiring them to pass all three tests at once may not be asking for too much. As it turns out, all Nash equilibrium outcomes of serial cost sharing pass all three tests. On the other hand the more familiar average cost pricing and ShapleyShubik mechanisms pass the Stand Alone test but fail No Envy (and Unanimity). I submit that this is a severe normative defect of those mechanisms: even though they offer the same strategic opportunities to all agents ex ante (the game form is anonymous), their equilibrium outcome may not offer the same consumption opportunities to all agents ex post (the No Envy test may fail). Other mechanisms pass the No Envy and/or Unanimity tests, but fail Stand Alone: an example is marginal cost pricing, charging the fixed fee to all agents, even those who consume no output. The general model is defined in Section 3. In Section 4 three numerical examples illustrate some of the main differences between the four basic mechanisms. Section 5 discusses the existence of aj' 0*((@@ Nash equilibrium outcome in simple mechanisms. The three equity tests are formally introduced in Section 6 and a related characterization of serial cost sharing is the subject of Section 7. Some concluding comments are gathered in Section 8.  ?@  3 THE MODEL Throughout the paper we are given a (one output) cost function C with the following properties:  ? C is concave, increasing, C(0)=0 and limC(q)=+a0088dd <<winfinityx6X@8;X@x6X@8;X@x6X@8;X@8wڃ  _ A cost sharing mechanism among n agents is a mapping 088dd <<tzeta x6X@8;X@x6X@8;X@x6X@8;X@8 t from 0'*c!__'*dd <<R_+^nx6X@8;X@x6X@8;X@x6X@8;X@_Rn:  _Y into 0'*__'*dd <<R_+^nx6X@8;X@x6X@8;X@x6X@8;X@_Rn:, associating to each profile of demands  _ 0X__dd <<q=(q_1,...,q_n),~0q_ix6X@8;X@x6X@8;X@x6X@8;X@_qz_q_q+n_q"+i_*__(+1B_,_.2_._."_,j_)_,_0, a profile of non negative costs 0%X__dd <<>x=(x_1,...,x_n)x6X@8;X@x6X@8;X@x6X@8;X@_xz_x_x+n__(+1B_,_.2_._."_,j_)>߻, and satisfying budget balance:  ? !#xdddddkJdd x7sum_i x_i=C(sum_i q_i)x6X@8;X@x6X@8;X@x6X@8;X@9I9I+iuxRiC+iqRiE5()7ߴ$(#(#(#(# !!'#$A simple mechanism is a cost sharing mechanism satisfying the anonymity property, namely for all i,j=1,...,n:  _  X CA# 3ddddd*dd xr\{q_i=q_j', q_j=q_i',q_k=q_k' ~all~k !=i,j\} => \{zeta_i(q)= zeta_j (q)~\and~zeta_k(q)= zeta_k\(q')~all~k != i,j\}x6X@8;X@x6X@8;X@x6X@8;X@_{_,2_,B _,2 _}" _> _{_(_)n_(^_)_(_)J_(_)w_,g_}_q +i_qR:j_q+jb_q:i_q*+k_qr:k_all _k _i _j+iH_q+j_q._and\+k$_q+k_qO_all_k_i_jZ_c_z_R _c _8__S_c_ _ _ _ C$%%%%X!A%$Each agent is endowed with preferences over !0*P!__*dd <<R_+^2x6X@8;X@x6X@8;X@x6X@8;X@_R2:. We consider two possible domains of preferences, namely  _ .A0($88dd <<ti x6X@8;X@x6X@8;X@x6X@8;X@8it: preferences non increasing in a0P$__dd <<x_ix6X@8;X@x6X@8;X@x6X@8;X@_x+i, non decreasing in 0$__dd <<q_ix6X@8;X@x6X@8;X@x6X@8;X@_q+i, non locally satiated, and decreasing on (C(q),q) for q large enough; moreover convex and continuous.  _# .0()__dd <<i _*x6X@8;X@x6X@8;X@x6X@8;X@_i+: the subdomain of D containing binormal preferences (namely both goods are normal):  _' If z is in the demand set on a given budget line 0^-__dd <<p_1 x+p_2 q  bx6X@8;X@x6X@8;X@x6X@8;X@____pR_xB_p _q_b+1+2ߑ,@' 0*((@@!'#h! 3%!A @Ԍ _  and if  0P @88dd <<b'>bx6X@8;X@x6X@8;X@x6X@8;X@8bG8bz8> , then the demand set on the budget line 0Z@__dd <<%p_1x+p_2 q  b'x6X@8;X@x6X@8;X@x6X@8;X@____pR_xB_p _q_b+1+2%ߢ  ?  contains at least a point z' such that !0P88dd << x'x ~\and~q'qx6X@8;X@x6X@8;X@x6X@8;X@8xG8x8and8q 8qz8hz8 ߆. For preferences represented by a differentiable utility function u, the normality property simply means that the  ? MRS A0 88dd <<}+(partial u/partial x)/(partial u/partial q)x6X@8;X@x6X@8;X@x6X@8;X@8(b8/8)*8/8(8/B8)8,8,8,j8,8u:8xz8u8q} (i.e. the slope Ta0mU 88mdd << (d q/d x)x6X@8;X@x6X@8;X@x6X@8;X@8(z8/8)8d8q8dj8xT of the indifference contour) is non decreasing in x and in q. For instance an additively separable  ? utility function 0 88dd <<pu(x,q)=a(q)b(x)x6X@8;X@x6X@8;X@x6X@8;X@8u8x8qZ8aJ8q8b8x8(z8,j8)8(8)*8(8)8:8p (with a concave, b convex and both  _ increasing) represents a preference in 0__dd <<i _*x6X@8;X@x6X@8;X@x6X@8;X@_i+. Next we define four basic mechanisms.  ? Mechanism 1: Average cost pricing (ACP)  ? a# ddddddd xGKfor~any~q_1,...,q_n:~x_i=zeta_i(q)=q_i over q_N.C(q_N), where~q_N=sum_j q_jx6X@8;X@x6X@8;X@x6X@8;X@!foranyqqAnaxi i q cq /i _q +N CqmNwhere]qNjqj1i,.Y..I,:g (W ) .u()5,1  -  e IG$%%%%!a%$Mechanism 2: Marginal cost pricing (MCP) Denote by C'(q) the right hand derivative of C:  ? d# sddddd{dd xMfor~all~q_1,...,q_n:x_i= zeta_i(q)=q_i.C'(q_N)+ 1 over n (C(q_N)q_N.C'(q_N))x6X@8;X@x6X@8;X@x6X@8;X@!forallqqAn xi i q qo i7 ClqNr8nCzqN:qNCq7N1i,.Y..I,: ( ) . (<)r1((J) .?())w  Q  2Jd$%%%% !%$Note that the deficit 0 88dd <<  C(q)qC'(q)x6X@8;X@x6X@8;X@x6X@8;X@8C8qj8qC8q8(z8)8(8)8sz ߉ is non negative so that the above cost shares are non negative, too. The MCP mechanism divides equally the deficit among all agents. Other divisions of the deficit are discussed in the literature (see e.g. the alternative cost avoided method in Young [1985]). The corresponding mechanisms do not have better strategic properties than MCP.  ?c$ Mechanism 3: the ShapleyShubik mechanism (SS) Given a profile of demands q (and a cost function C'), consider the  ' cooperative game (with sidepayments): 0Jp_-Jdd <<1V(S)=C(sum_S q_i)x6X@8;X@x6X@8;X@x6X@8;X@VSjC6+Sq=Ri(z)()Z9I1߮. The SS cost@' 0*((@@!%a % @ sharing rule is the Shapley value of this game, or # ddddd ddx&x_i=zeta_i (q)=E[V(S` CUP \{i\})V(S)]x6X@8;X@x6X@8;X@x6X@8;X@_x+i+i_q_E_V_SR_i2 _V" _S___Z_ _(_)p_[`_(_{_}B_) _( _) _]f_=ߖ$%%%%X!%$where the expectation bears on all orderings of {1,...,n} and S is the (possibly empty) coalition of agents preceding i in a random ordering.  ? Mechanism 4: Serial cost sharing (SER) The formula is given for a profile of demands q such that  _( 0Uh__Udd<<:q_1 q_2...q_nx6X@8;X@x6X@8;X@x6X@8;X@_qR_qr_q+n+1+2_. _._.___:߷. The other cases follow by anonymity. Denote  ? P# RdddddddxVq^1=nq_1, q^2=(n1) q_2+q_1 ,..., q^i=(ni+1) q_i+q_{i1}+...+q_1,..., q^n=q_n+...+q_1x6X@8;X@x6X@8;X@x6X@8;X@_qk_nq#_q_n_q_q4 _q i& _n_i_qv+i>_q+i_q_qn_q+n_q1[+1_,2|_(_1\_)L+2+1_,T _. _.D _. _, _(_1~_)V+1_._._.v+1_,>_._.._._,_.X_._.8+1__l__6 _ ___+__ _h_H_P$%% %%X!%$ XX  X  8t #,%8ddddd'ddx^ ?  (1) stack {alignl zeta_1={C(q^1)} over n; zeta_2= {C(q^2)} over {n1} {C(q^1)} over {n(n1)}; zeta_i(q)={C(q^i)} over {ni+1} {C(q^{i1})} over {(ni+2)(ni+1)} ... {C(q^1)} over {n(n1)}}x6X@8;X@x6X@8;X@x6X@8;X@ w   1(W1_);2k(tW2)S81 ( W16 ) 8( 81z 8) ;P (@)(h)_81(W1 )8(828)8(f818).n..(W10)8(81t8)58d 888jW8888~^8xfxkN- kC~qv8nCqc8ne CU q" 8n 8n i qvCfqWi8no8iCqWi>8n.8i8nv8i_COq8n 8n߮$88d&d&j88d&d& !8c&$ 8t   Remark   _ At a demand profile such that !0Z__dd<<q_1x6X@8;X@x6X@8;X@x6X@8;X@_q+1 is the smallest demand and A0 Z__dd<<q_nx6X@8;X@x6X@8;X@x6X@8;X@_q+n the largest one, we have the following inequalities:  ` a0-[`-[dd<<csstack {alignl x_1(ACP)  x_1 (SER)  x_1 (MCP) # ~# alignl x_n(MCP)  x_n(ACP); x_n (SER)  x_n (ACP)}x6X@8;X@x6X@8;X@x6X@8;X@xRACPxSERBxMCP^x*nZ^MCP^x2*n^ACPR^x*n^SER ^xr *n: ^ACP1()"1r(R)1 ( )^(^)^(b^)^;"^( ^) ^( ^)2:^z ^c  ? 4 Numerical Examples We fix the following piecewiselinear cost function throughout this section:  ?h #xs$dddddddx@*# ? `:  (1) ăC(q)=min\{2q, q over 2+15\}x6X@8;X@x6X@8;X@x6X@8;X@!Cqqq()ymin{Y2I,8215}2$(#(#h(#(# !'#$Marginal cost equals 2 up to $0nH'88ndd<<q^*=10x6X@8;X@x6X@8;X@x6X@8;X@8qz8k810$ and falls to 1/2 afterwards. In all numerical examples, we have two agents with quasilinear  _$ utilities of the form 0E:+__Edd<<0u_i=u_i(q_i)x_ix6X@8;X@x6X@8;X@x6X@8;X@_u+iZ_u+i_q"+ib_x+i__*_(r_)0߭ (in particular, agents have unbounded reserves of the transferable input called money). In the`&0*((@@A% R%8c&$'#~'`  ? MCP mechanism, the jump in marginal cost at $0nP@88ndd<<q^*=10x6X@8;X@x6X@8;X@x6X@8;X@8qz8k810$ yields a  _ discontinuous cost share. Say !08"__dd<<q_1=2x6X@8;X@x6X@8;X@x6X@8;X@_q+1R_2_!. Then player 2's cost share is  _ D0 __dd<<x_2=2q_2x6X@8;X@x6X@8;X@x6X@8;X@_x_q+2R_2B+2_D as long as  !0 __dd<<q_2<8x6X@8;X@x6X@8;X@x6X@8;X@_q+2_<R_8  but jumps down to A0 __dd<<?x_2=7.5+(q_2/2)x6X@8;X@x6X@8;X@x6X@8;X@_x_q+2R_7_.B_52_("+2r_/_2b_)__?߼ when $a0 __dd<<q_28x6X@8;X@x6X@8;X@x6X@8;X@_q+2R_8_$  _ (note that if !0@ __dd<<q_1=8x6X@8;X@x6X@8;X@x6X@8;X@_q+1R_8_!, then 0e __dd<<x_2x6X@8;X@x6X@8;X@x6X@8;X@_x+2 jumps up at !0j __dd<<q_2=2x6X@8;X@x6X@8;X@x6X@8;X@_q+2R_2_!). Consider the following utility functions:  _0 !#xpdddddddxistack {alignl u_1 (q_1)=min\{q_1, {q_1} over 4} + 3 over 2\}, ~~u_2(q_2)=min\{3q_2, {2q_2} over 7 + 19\}x6X@8;X@x6X@8;X@x6X@8;X@0upqq<q| u qq<q1(18)(min{1,184<3<82}T , 2D (4 2 )t min{T3D2,R<2B287219"}~ f2*$(#(#0 (#(# !!'#$Efficiency requires to produce x0 8__ dd<< q_1=0,q_2=7x6X@8;X@x6X@8;X@x6X@8;X@_qB_q+1R_0_,+2_7_ _x (obtained by maximizing  _: k0 z__ dd<<u_1(q_1)+u_2(q_2)C(q_1+q_2))x6X@8;X@x6X@8;X@x6X@8;X@_uR_q _uJ_q_C_q2_q+1_(+1_)+2_(+2_)z_(j+1+2_)r _)___k. This pair is also the unique equilibrium demand profile in all three mechanisms ACP, SS and SER. In all three mechanisms, agent 2 covers all costs. Yet (0,7) is not an equilibrium profile of the MCP mechanism, because player 2 wishes  _ to raise his demand to F!0*x__*dd<<q_2'=10:x6X@8;X@x6X@8;X@x6X@8;X@_q_:2R_10B_:F at that level he pays  _ (A0E*__E*dd<<x_2' =(q_2'/2)+7.5=12.5x6X@8;X@x6X@8;X@x6X@8;X@_x_q_[__:2R_(B:2_/ _2_)r_7_.b_5R_12B_._5( (because player 1 must pick up half of the fixed  _R cost 15) as opposed to #a0Ux__Udd<<x_2=14x6X@8;X@x6X@8;X@x6X@8;X@_x+2R_14_# if he demands !0__dd<<q_2=7x6X@8;X@x6X@8;X@x6X@8;X@_q+2R_7_!. Once player 2  _< demands 50U*p| __U*dd<<q_2'=10x6X@8;X@x6X@8;X@x6X@8;X@_q_:2R_105, however, player 1 wishes to raise his demand to 30*5"| __*dd<<q_1'=2x6X@8;X@x6X@8;X@x6X@8;X@_q_:1R_23  _ (he ends up with a utility loss }0 *"__ *dd<<u_1(2)((q_1'/2)+7.5)= 6.5 x6X@8;X@x6X@8;X@x6X@8;X@_u_q+1_(R_2_)_(2_(":1r_/_2b_)R_7_.B_5_)" _6 _. _5B_;_2__} anyway).  _ Now given 3 0*` $%__*dd<<q_1'=2x6X@8;X@x6X@8;X@x6X@8;X@_q_:1R_23, player 2 wishes to demand only 3! 0*$%__*dd<<q_2'=8x6X@8;X@x6X@8;X@x6X@8;X@_q_:2R_83 (he only wishes to make sure that player 1 picks half of the fixed cost), to which  _" player 1's best reply is 3A 0*h)__*dd<<q_1'=0x6X@8;X@x6X@8;X@x6X@8;X@_q_:1R_03 (whereby he has nothing to pay!) and so on. It turns out that the demand game generated by the MCP mechanism has no Nash equilibrium whatsoever: the best reply0&0*((@@p'#m!0 functions are )A#x#ddddd [ddxmstack {alignl br_1(q_2)=0~if~q_2<10;=2~if~q_210 # ~ # alignl br_2(q_1)=10q_1~if~q_13;=7~if~q_13}x6X@8;X@x6X@8;X@x6X@8;X@brqRifq if q^br^q^q ^ifR^q ^if ^q1R(B2)02b<10;2J 2 10*2R^(B*1^)^10b*1*1^3 ^; ^7 *1R ^3 B  ^r^^ ^ ^)$(#(#(#(#!A'#$In the next numerical examples, we illustrate the differences between the three mechanisms ACP, SS and SER. Consider first a unanimous utility profile:  _ a#xdddddddxu_i(q_i)=5 sqrt {q_i}, i=1,2x6X@8;X@x6X@8;X@x6X@8;X@_u+iZ_q+i_q+iI_i_(*_)_5_,9_1_,)_2__)O$(#(# (#(#X!a'#$Efficiency requires to produce Xa 08\__dd<< q_1=q_2=25x6X@8;X@x6X@8;X@x6X@8;X@_qR_q+1+2_25__X. The demand profile (25,25) is a Nash equilibrium of both the SER and SS mechanisms: indeed given that the other player demands 25, a player faces the actual marginal cost 1/2 whenever he/she demands 10 or more. Note that there is another Nash equilibrium (for both mechanisms) at  _ z 0@__dd<< q_1=q_2=1.56x6X@8;X@x6X@8;X@x6X@8;X@_qR_q+1+2_1 _._56__z (computed by x 0* __*dd<< u_i'(q_i)=2x6X@8;X@x6X@8;X@x6X@8;X@_u:iZ_q+i__(*_)_2x; note that given " 0@__dd<<q_j < 5x6X@8;X@x6X@8;X@x6X@8;X@_q+j_<Z_5", player i  _ faces the marginal cost 2 for K 0__dd<<0 q_i5x6X@8;X@x6X@8;X@x6X@8;X@_0J_5___q+iK) and this equilibrium is Pareto inferior to (25,25): on Figure 1 are drawn the opportunity  _ sets in all three mechanisms SER, SS and ACP given # 0]D__]dd<<q_j=25x6X@8;X@x6X@8;X@x6X@8;X@_q+j_Z_25# or  _ E! 0M.!__Mdd<<q_j=1.56x6X@8;X@x6X@8;X@x6X@8;X@_q+j_Z_1_.J_56E. In the ACP mechanism, only the inferior equilibrium  _ (1.56,1.56) survives: there is no equilibrium TA 0#__dd<< (q_1,q_2)x6X@8;X@x6X@8;X@x6X@8;X@_(+1R_,B+2_)_q_qT with  _ la 0 %__ dd<<q_1+q_210.x6X@8;X@x6X@8;X@x6X@8;X@_qR_q+1+2_10_.__l7 Our next example is one where only the serial equilibrium  _<" outcome is efficient. The functions  0|(__dd<<u_ix6X@8;X@x6X@8;X@x6X@8;X@_u+i are concave and satisfy: #x)dddddddxK~stack {alignl u_1'(3)=2;~u_1' (8)=1 over 2;~u_1(8)u_1(3)>5.5 # ~ # alignl u_2'(2)=2;~u_2'(16)= 1 over 2;~u_2(16)u_2(2)>11.5}x6X@8;X@x6X@8;X@x6X@8;X@uu`u uuuu u/B/2 B 1(R3)22;z1(B8)11T2;1( ( 8 ) 1 (H 3 )8 > 5(.52(R2)22;z2(B162)h1h72;P 2 ( 16 )p 2 (8 2 )(>11.522@K$(#(##(#(#U!'#$P0*((@@1'#V A'#Na)'#.PԒ _ See Figure 2. The efficient demand profile is z 0@__dd<< q_1=8,q_2=16x6X@8;X@x6X@8;X@x6X@8;X@_qB_q+1R_8_,+2_16_ _z; it is an  _ equilibrium of the serial mechanism (another equilibrium of SER is  0 *$*__ *dd<< q_1'=3,q_2'=2x6X@8;X@x6X@8;X@x6X@8;X@_qB_q_ _:1R_3_,:2_2ߜ  _> but the choice of 2 0- ~ __-dd<<u_1,u_2x6X@8;X@x6X@8;X@x6X@8;X@_uR_u+1_,+22 makes this equilibrium Pareto inferior).  _( Indeed given # 0U h __Udd<<q_2=16x6X@8;X@x6X@8;X@x6X@8;X@_q+2R_16_#, agent 1's cost share is ! 0Mh __dd<< x_1=C(2q_1)/2x6X@8;X@x6X@8;X@x6X@8;X@_xR_C_q+1_(B_22+1_)_/r_2_ߙ for any A 0"h __dd<<q_1x6X@8;X@x6X@8;X@x6X@8;X@_q+1  _ (including &a 0U R__Udd<< q_116x6X@8;X@x6X@8;X@x6X@8;X@_q+1R_16_& because  0=R__=dd<<s,C(2q_1)/2+C(2.32)/2=C(q_1+32) for~ all~ q_1)x6X@8;X@x6X@8;X@x6X@8;X@_Cz_q"_C_C _qj _for*_all_q_(_2+1B_)_/2_2_(_2_._32_)j_/_2J _(: +1 _32 _)b+1_)_Z_ _s  _ hence agent 1 faces the marginal cost 1/2 whenever $ 0<__dd<<5q_1x6X@8;X@x6X@8;X@x6X@8;X@_5z+1__q$. On the other hand (8,16) is not an equilibrium of SS: given  _v # 0U__Udd<<q_2=16x6X@8;X@x6X@8;X@x6X@8;X@_q+2R_16_#, agent 1's cost share is  05__dd<<  x_1=(5/4)q_1x6X@8;X@x6X@8;X@x6X@8;X@_x_q+1R_(_5B_/_42_)"+1_ ߈ for L 0E__Edd<<0q_110x6X@8;X@x6X@8;X@x6X@8;X@_0z+1B_10___qL. Hence the  _ equilibrium of SS is W! 0^*%__^*dd<< (q_1^*,16)x6X@8;X@x6X@8;X@x6X@8;X@_(:1k_,_16_)_qW where A 0*.%__*dd<<q_1^*x6X@8;X@x6X@8;X@x6X@8;X@_q:1 is defined by a 0*<%__*dd<<0u_1'(q_1^*)=5/4x6X@8;X@x6X@8;X@x6X@8;X@_uR_q_:1_(:13_)#_5_/_40߭ and it falls short of efficiency. The equilibrium (or equilibria) of the ACP mechanism are also inefficient in this example. And finally we check that even SER may yield an inefficient equilibrium outcome with a cost function like (1). Take  _ ;#x$ddddd;ddxdstack {alignl u_1(q_1)=4 sqrt {q_1} # ~ # alignl u_2'(2)=2;u_2' (16)= 1 over 2; u_2(16)u_2(2)>17.5}x6X@8;X@x6X@8;X@x6X@8;X@{uR{q{quu(uH uG1{(G1{) {4iG12(R2)22;"2r(16)172;2(h 16X ) 2 ( 2 )x > 17.X5{B;R ..O2;$(#(#(#(#!'#$Then the unique equilibrium of SER is z 0!__dd<< q_1=1,q_2=16x6X@8;X@x6X@8;X@x6X@8;X@_qB_q+1R_1_,+2_16_ _z. Indeed ! 0- !__dd<<q_1=1x6X@8;X@x6X@8;X@x6X@8;X@_q+1R_1_!  _~ reaches the maximum of  0x#__dd<<u_1(q_1)(C(2q_1)/2)x6X@8;X@x6X@8;X@x6X@8;X@_uR_q_C_q+1_(+1_) _(_(r_2b+1_)*_/_2_)_.8 Moreover, given  _h { 0 %__ dd<<q_1=1,q_21x6X@8;X@x6X@8;X@x6X@8;X@_qB_q+1R_1_,+2_1_ _{, agent 2's utility function is  0%__dd<<u_2(q_2)(C(q_2+1)2)x6X@8;X@x6X@8;X@x6X@8;X@_uR_q_Cr_q+2_(+2_) _(_(+2_1*_)_2_)_:__; the  _R! latter has two local maxima at 2 and 16 but our choice of ! 0X '__dd<<u_2x6X@8;X@x6X@8;X@x6X@8;X@_u+2  _<# guarantees that #A 0U0 |)__Udd<<q_2=16x6X@8;X@x6X@8;X@x6X@8;X@_q+2R_16_# is the global maximum. The SER equilbrium is not efficient, however, since the marginal utilities are 2 and 1/2 respectively. Of course, in this example, the SS and ACP0&0*((@@$'#!0 mechanisms have inefficient equilibria as well. In general, pick a continuous cost function consisting of two linear pieces (and decreasing marginal cost). Then for any profile of convex preferences, if can be shown that i) SER has at least one Nash equilibrium, ii) SER has (at least) one strong equilibrium and this equilibrium is also Pareto superior to all other Nash equilibria. The strong equilibrium is unique if preferences are strictly convex. We omit the straightforward proof of these claims. In view of Lemma 2 below, statement i does not hold for an arbitrary concave cost function; the same is true of statement ii.  ?0  5 EXISTENCE OF A NASH EQUILIBRIUM If the cost function C is convex (decreasing returns to scale)  ?P all three9 mechanisms ACP,SS and SER have at least one Nash  ? equilibrium outcome for every preference profile in a 0 88dd<<ti x6X@8;X@x6X@8;X@x6X@8;X@8it.10 By contrast, under increasing returns, the ACP mechanism may not have  ? any equilibrium at all, even for a profile in  0@Z88dd<<ti x6X@8;X@x6X@8;X@x6X@8;X@8it*.  ?  Lemma 1  ?T i) There exists a concave cost function C made of two linear pieces (like the function (1)) and a (two person) preference  _t profile in  0 %__dd<<i _*x6X@8;X@x6X@8;X@x6X@8;X@_i+ (in fact a profile of quasilinear utilities) such that the ACP mechanism has no Nash equilibrium. The same statement holds true for the MCP mechanism. ii) If C is differentiable and the function C'AC is non increasing  ?& over L 0 N,88 dd<<[`0,+ infinity)x6X@8;X@x6X@8;X@x6X@8;X@8[808,8)88L, then the ACP mechanism has at least one Nash equilibrium for every preference profile (with an arbitrary number'0*((@@  _ of players) in  0 @__dd<<i _*x6X@8;X@x6X@8;X@x6X@8;X@_i+.  ?  Proof  ?z  Statement i) The first example in Section 4 shows the claim for the MCP mechanism. To prove the claim for the ACP mechanism, we use the cost function C given by (2). We have two players. For a given  { 0__dd<<q_2x6X@8;X@x6X@8;X@x6X@8;X@_q+2, we denote by !01 {{1dd<<O_q_2x6X@8;X@x6X@8;X@x6X@8;X@{OGqdd%2 the opportunity set of player 1 namely the curve  {l #xdddddAddxgP(q_1,x_1) epsilon O_q_2~ < x_1= q_1 over {q_1+q_2} C(q_1+q_2)=q_1.AC(q_1+q_2)x6X@8;X@x6X@8;X@x6X@8;X@!(1a,Q1)ddJ21/1u+1+2 ( 1 2% ) 1 .E(51u2)qxzOqwxcq_q=_q- C q] q qUACqq <?_  g$(#(#l (#(#!'#$On the curve A01 {{1dd<<O_q_2x6X@8;X@x6X@8;X@x6X@8;X@{OGqdd%2 we consider the two points  _v oa0=__=dd<<6E(q_2)=(12,12AC(12+q_2))~\and~F(q_2)=(16,16AC(16+q_2))x6X@8;X@x6X@8;X@x6X@8;X@_E_q_ACZ_qj _and* _F _q_ACr_q_(z+2_)_(2_12"_,_12z_(_12+2" _) _) _( +2 _)_(J_16:_,_16_( _16+2:_)_)B__Z__o. Then we choose  _` the (quasilinear) utility of player 1, x0p__dd<< u_1(q_1)x_1x6X@8;X@x6X@8;X@x6X@8;X@_uR_q _x+1_(+1_)+1_x, in such a way that one of its indifference contours contains the interval [E(14), F(14)], a vertical halfline starting at F(14) and an almost horizontal halfline starting at E(14): See Figure 3. By quasilinearity, all other indifference contours are deduced by an horizontal translation.  _ By construction the best reply of player 1 at #0UZ%__Udd<<q_2=14x6X@8;X@x6X@8;X@x6X@8;X@_q+2R_14_# contains  _! 12 and 16. Indeed [E(14),F(14)] is a chord of 0=D'__=dd<<O_{14}x6X@8;X@x6X@8;X@x6X@8;X@_O+14: see Figure 3.  _" We claim that the rest of the function 0e.)__edd<<br_1x6X@8;X@x6X@8;X@x6X@8;X@_br+1 is as follows:  _$ W#x+ddddd ddx# ? `n (3) ă;br_1(q_2)=16~if~q_2<14~;=12~if~14[`A(q_2),B(q_2)]x6X@8;X@x6X@8;X@x6X@8;X@_[_(+2X_)_,_(+2_)x_]_A_qH_B8_q>߻ (expressed as a@0'0*((@@!'#+'#8-@  ? ratio <!0@88dd<<Delta x/Delta qx6X@8;X@x6X@8;X@x6X@8;X@888x48q#8/<) is worth #xddddd ddxQ4sigma(q_2)= {16AC(16+q_2)12AC(12+q_2)} over {1612}x6X@8;X@x6X@8;X@x6X@8;X@!%(2)<16<(n<16N2<)<12n <( <12 2 <)&816812q<AC<q~ <ACN <qX^<< <86Q$(#(#(#(# !'#$therefore ^!#x dddddddx\sigma'(q_2)=1 over 4 ({16} over {16+q_2} (C'AC)(16+q_2){12} over {12+q_2} (C'AC)(12+q_2))x6X@8;X@x6X@8;X@x6X@8;X@?%!_!K K _j!(2*)`<1`_4(^<16_16+2( )+ ( 16 2 )<12 _12+2a()v(122))bq&_qCAC qq_qCACVq28KK ^$(#(#Z(#(# !!'#$For t10, we have (C'AC)(t)= 15/t,so that:  { A#xJdddddiddxS sigma'(q_2) > 0~ < ~q_2 < 192x6X@8;X@x6X@8;X@x6X@8;X@_%_<_(+2_)u_>_0&+2v_<_1925_q_qS$(#(# (#(#X!A'#$Therefore as A0 __dd<<q_2x6X@8;X@x6X@8;X@x6X@8;X@_q+2 increases, the curve a01{{1dd<<O_q_2x6X@8;X@x6X@8;X@x6X@8;X@{OGqdd%2 moves leftward and the  _ slope of 0__dd<<>(E(q_2), F(q_2))x6X@8;X@x6X@8;X@x6X@8;X@_(_(+2B_)_,_(+2_)b_)_Ez_q2_F"_q>߻ increases: this yields the best reply function (3) for player 1: see Figure 3. To complete the proof of Statement i, it remains to choose a (quasilinear) utility function for player 2 guaranteeing  _ a#x^dddddM ddx/# ? `f (4) ărbr_2(12)<14~\and~br_2(16)>14x6X@8;X@x6X@8;X@x6X@8;X@_br_and_br+2R_(_12_)2_<_14+2_(j_16Z _) _>J _14r$(#(#(#(#X!a'#$This easy construction (for instance we can take Z0__dd<< br_2(12)=12x6X@8;X@x6X@8;X@x6X@8;X@_br+2R_(_12_)_122_Z and  _` k0% __%dd<< br_2(16)=16)x6X@8;X@x6X@8;X@x6X@8;X@_br+2R_(_16_)_16_)2_k is omitted. Together, the two best reply functions (3), (4) preclude the existence of a Nash equilibrium to the ACP mechanism. The proof of statement ii in Lemma 1 is given immediately  ? after the proof of Lemma 2. Q.E.D. A general result about the existence of Nash equilibria in simple mechanisms cannot use the fixed point theorems from convex analysis because the best reply correspondences are not convex  _:' valued. For a given choice 0=z-__=dd<<q_{i}x6X@8;X@x6X@8;X@x6X@8;X@_q+i+ of strategies by the agents other`:'0*((@@A'#  '#!J'#A^'#~a`  _ than i, the opportunity set 0# @__# dd<<O-\{(x_i,q_i)/x_i=zeta_i(q_i,q_{i}),q_i0\}x6X@8;X@x6X@8;X@x6X@8;X@_{_(_,_)_/_(X_,_)` _, _0 _}_x+iJ_q+i _x+i+i_q+i_q+i _qX +i_H+ _R_ O is typically  _ the graph of a concave function (with variable !0*__dd<<q_ix6X@8;X@x6X@8;X@x6X@8;X@_q+i and value A0 *__dd<<x_ix6X@8;X@x6X@8;X@x6X@8;X@_x+i),  _ hence even a preference in a0X __dd<<i _*x6X@8;X@x6X@8;X@x6X@8;X@_i+ may reach its maximum over this opportunity set in two or more distinct points. However, the fixed point theorems from lattice theory (the descendants of Tarski's theorem) can be fruitfully applied to our problem. We introduce some notations. A n player normal form game  _ where player i's strategy is 0H__dd<<q_ix6X@8;X@x6X@8;X@x6X@8;X@_q+i, 0=-__=dd<< 0q_iQ<+infinityx6X@8;X@x6X@8;X@x6X@8;X@_0_<__:___q+iJ_Q ߆ will be denoted  _x 0__dd<<(pi_1,..,pi_n)x6X@8;X@x6X@8;X@x6X@8;X@_(+1__,_.O_._,_)_!?_!+nߋ with 0 __dd<<@pi_i(q_1,...,q_n)x6X@8;X@x6X@8;X@x6X@8;X@_!+i__q_q+n_(+1'_,_._._._,O_)@߽ interpreted as the payoff to player  _b i whenever the strategic profile is 0__dd<<>q=(q_1,...,q_n)x6X@8;X@x6X@8;X@x6X@8;X@_qz_q_q+n__(+1B_,_.2_._."_,j_)>߻. The notation  _L \!0__dd<<(q line ^i q_i )x6X@8;X@x6X@8;X@x6X@8;X@_(r_)_qRi_q"+i_ \ represents the demand profile with ith coordinate A0* __*dd<<q_i'x6X@8;X@x6X@8;X@x6X@8;X@_q:i and  _ jth coordinate a00 __dd<<q_jx6X@8;X@x6X@8;X@x6X@8;X@_q+j for all 0]88dd<<j != ix6X@8;X@x6X@8;X@x6X@8;X@8j8i8c. Thus the strategic profile q is  _ a Nash equilibrium if we have 0*8__*dd<<!pi_i(q)  pi_i(q line ^i q_i')x6X@8;X@x6X@8;X@x6X@8;X@_!_!+i__qL+i_qi,_q:i_(_)_(_)O__  for all i and all 0*"__*dd<<q_i'x6X@8;X@x6X@8;X@x6X@8;X@_q:i. We say that the normal form game has the single crossing  ?n property if we have for all i and all profiles 10J!88Jdd<<q,q':x6X@8;X@x6X@8;X@x6X@8;X@8q8q8,8:z1  _P *f0*#__*dd<<g\{q_iq_i'~for~all~i~\and~pi_i(q)pi_i(q line ^i q_i')\}=> \{pi_i(q' line^i q_i)  pi_i (q')\}x6X@8;X@x6X@8;X@x6X@8;X@_{ _( _) _(_)l_}\_>_{!_(_)_(_)8_}_q +i_qR:i_for_allz_iJ_and +iW _qD +i _q i$_q:i+i_qi_qv+i;+i_qZ_cG _ _ _*V_ >_ _! _!L_!_!f à  ?  and  _4! *`!0*t'__*dd<<c\{q_iq_i'~for~all~i~\and~pi_i(q) < pi_i(q line ^i q_i')\} => \{pi_i(q' line^i q_i) < pi_i(q')\}x6X@8;X@x6X@8;X@x6X@8;X@_{ _( _)G _< _(_)l_}\_>_{!_(_)>_<_(_)8_}_q +i_qR:i_for_allz_iJ_and +iW _qD +i _q i$_q:i+i_qi_qv+i;+i_qZ_c _ _*V_  _! _!L_!_!`ڃ  ?#  Theorem (Milgrom and Shannon [1991], Theorem 15)  _% Let a normal form game A0xX+__dd<<(pi_1,...,pi_n)x6X@8;X@x6X@8;X@x6X@8;X@_(+1__,_.O_._.?_,_)_!_!<+nߜ be given such that for all  _' i=1,..,n, i) the payoff function a0(B-__dd<<pi_ix6X@8;X@x6X@8;X@x6X@8;X@_!+i is continuous in q and ii) 0B"B-__dd<<pi_ix6X@8;X@x6X@8;X@x6X@8;X@_!+i'0*((@@ satisfies the single crossing property. Then the game possesses a  ? largest Nash equilibrium 0h88dd<<q^*x6X@8;X@x6X@8;X@x6X@8;X@8qz and a smallest Nash equilibrium  _r 0F __Fdd<<q_* (so~q_*q^*)x6X@8;X@x6X@8;X@x6X@8;X@_qR_so_q_q++b_k_(_)ߓ. Moreover the strategies `06* __6*dd<<q_i^*~\and~q_{*i}x6X@8;X@x6X@8;X@x6X@8;X@_q:iK_and _q+i+` are respectively the largest and the smallest serially undominated strategies of  ?V player i. Note that in the above statement the strategy sets of all players must be bounded.  ?  Theorem 1   ? Consider a simple mechanism 0(88dd<<szetax6X@8;X@x6X@8;X@x6X@8;X@8 s among n agents satisfying  ?@ a) !088dd<<szetax6X@8;X@x6X@8;X@x6X@8;X@8 s is continuous in q  _ b) Cross monotonicity : for all i,j, iA0*88dd<<r!= x6X@8;X@x6X@8;X@x6X@8;X@8crj,5a0K *__Kdd<< zeta_i(q)x6X@8;X@x6X@8;X@x6X@8;X@_ +iH_q_(_)5 is non increasing  _ in 0__dd<<q_jx6X@8;X@x6X@8;X@x6X@8;X@_q+j. Note: this property implies that 0e__dd<<zeta_ix6X@8;X@x6X@8;X@x6X@8;X@_ +i is increasing in 0!__dd<<q_ix6X@8;X@x6X@8;X@x6X@8;X@_q+i.  _ c) Complementarity : for all U0m88mdd<< i,j,i!= jx6X@8;X@x6X@8;X@x6X@8;X@8i8j8i8j8,z8,j8cU the increment of 0__dd<<zeta_ix6X@8;X@x6X@8;X@x6X@8;X@_ +i when !0"__dd<<q_ix6X@8;X@x6X@8;X@x6X@8;X@_q+i  _ increases is non increasing in A08__dd<<q_jx6X@8;X@x6X@8;X@x6X@8;X@_q+j. Formally, for all q,q':  _  *a0,* __,*dd<<>Qqq' => zeta_i(q line^i q_i') zeta_i(q)  zeta_i(q')zeta_i(q' line^i q_i)x6X@8;X@x6X@8;X@x6X@8;X@_q_q+i_qi_q}:i++i_q +i _q +it _qi_qQ+i__]_ E__"  _1_ 7_>m_(_){_(k_) _(N _) _(_)_ _ [ _ > _ >߻ă  _ Then for any preference profile in 0&!__dd<<i _*x6X@8;X@x6X@8;X@x6X@8;X@_i+, the corresponding demand game satisfies the assumptions of the above Theorem. Its largest  ?` Nash equilibrium is also Pareto superior among all Nash equilibria.  ? When 0` 0&88dd<<szetax6X@8;X@x6X@8;X@x6X@8;X@8 s is twice differentiable (as the ACP,SS, and SER mechanisms are if C itself is twice differentiable), the properties of Cross Monotonicity and Complementarity mean respectively  _$ 0) *__) dd<<0Wpartial zeta_i/partial q_j  0~\and~ partial^2 zeta_i/partial q_i partial q_j  0x6X@8;X@x6X@8;X@x6X@8;X@_,_,__,_,_,& _r_ _ +i_q+j _and+i&_q+iV _q +j0_/P_0@2N_/ _00߭. &0*((@@Ԍ ?  Proof of Theorem 1  _ Let u be a utility function representing a preference in 0!__dd<<i_*x6X@8;X@x6X@8;X@x6X@8;X@_i+.  _z Binormality implies the following property. Fix 90-*  __-*dd<<q_1,q_1', x_1,x_1',y_1,y_1'x6X@8;X@x6X@8;X@x6X@8;X@_qR_q_x_x_yR_y+1_,:1_, +1Z_,J:1_,+1_,:1c9 such that:  _^ #x ddddd*ddx+# ? `~ (5) ăMq_1 < q_1',x_1'y_1';u(x_1,q_1)=u(x_1',q_1')~\and~u(y_1,q_1)=u(y_1', q_1')x6X@8;X@x6X@8;X@x6X@8;X@_qR_q_x_y_u_xB_q_u _x* _q _and_ur_y_qj_uZ_y_q+1_<:1_, :1J:1_;_(z+1_,+1 _)r _(b :1 _, :1 _)_(+1:_,*+1z_)_(:1"_,:1b_)#Z_c_{  _+߷$(#(#^(#(#X!'#$Then we must have !0* __*dd<<Gy_1x_1y_1'x_1'x6X@8;X@x6X@8;X@x6X@8;X@_yR_x_y_x+1+1 :1J:1__#Z_cG.  _ Indeed, the TA0P J__dd<< (x_1,q_1)x6X@8;X@x6X@8;X@x6X@8;X@_(+1R_,B+1_)_x_qT indifference contour has equation x=f(q) and  _ the Ta04__dd<< (y_1,q_1)x6X@8;X@x6X@8;X@x6X@8;X@_(+1R_,B+1_)_y_qT indifference contour has equation x=g(q), with f,g  _ concave and increasing on f0*__*dd<< [q_1,q_1']x6X@8;X@x6X@8;X@x6X@8;X@_[+1R_,B:1_]_q_q[f. Binormality implies 0*=__*dd<<Fg_'(q) f_+'(q)x6X@8;X@x6X@8;X@x6X@8;X@_gR_q_f_q:B_K2:_(_)_(r_)F  _2 for all q (where 0* r__*dd<<g_'x6X@8;X@x6X@8;X@x6X@8;X@_g: is the left derivative and 0*r__*dd<<f_+'x6X@8;X@x6X@8;X@x6X@8;X@_f: the right  _ derivative) hence 0M * __M *dd<< g(q_1')g(q_1)f(q_1')f(q_1)x6X@8;X@x6X@8;X@x6X@8;X@_g_q_g_qb_fR_q _f_q_(z:1_)2_("+1r_)_(:1_)_(r +1 _)B___ߐ as desired.  ? We check the single crossing property. For all |!0088dd<<q,q', qq' x6X@8;X@x6X@8;X@x6X@8;X@8q8q78q'8q8,8,z8z| we must  _ show: {A0*__*dd<<ru_i(zeta_i(q line^i q_i'), q_i')u_i(zeta_i(q),q_i)=> u_i(zeta_i(q'),q_i')  u_i(zeta_i(q' line^i q_i),q_i).x6X@8;X@x6X@8;X@x6X@8;X@_u+i+i_qXi_q(:ih_q:i(_u+i+i _q _q +iF _u +i+i_qq_q:i1_u+i+i_qi _q+i_qL+i_(_(x_)_,8_)_(. _( _) _, _) _>_(L_(_)_,A_)_(7_(_)T_,_)_.Z_ p_ _ y_ _ 9_V _U_@l_ {  _ Fix i=1 for convenience and the vectors qq' with Da0-* P!__-*dd<<q_1_q, _q+1+1_(_)^+1_(1:1_)d+1_( _)_x__ ~_ R_ _ _ 7ߴ$(#(#(#(#X!'#$Invoke Complementarity: the above inequality implies a08x( __8dd<<Nx_1zeta_1(q' line^1 q_1)x6X@8;X@x6X@8;X@x6X@8;X@_x_q_q+1+1_(1]+1_)_E_ R_ N therefore #x ddddd`*ddx?u_1(x_1',q_1')=u_1 (x_1,q_1) u_1(zeta_1(q' line^1 q_1),q_1)x6X@8;X@x6X@8;X@x6X@8;X@_uR_x_qJ_u_x_q_u _qU _q _q+1_(:1_, :1Z_)+1_(+1R_,B+1_)+1J _(0 +1 _( 1 +1 _) _,+1_)#_ _  _  _ ߑ$(#(#(#(#X!'#$The other inequality of the SC property (involving strict inequalities) is proven by a similar argument. In order to apply the MilgromShannon theorem, we cut a bounded set of strategies for  ? every player. This can be done because in the domain 088dd<<ti x6X@8;X@x6X@8;X@x6X@8;X@8it, utilities are decreasing on (q,C(q)) for q large enough. We omit the  ? details. Q.E.D.  ?l  Lemma 2 Both the SS and SER mechanisms meet the properties of Cross Monotonicity and Complementarity. Hence the corresponding games have a largest and Pareto superior Nash equilibrium for all profile  _ in 0__dd<<i_*x6X@8;X@x6X@8;X@x6X@8;X@_i+. However both mechanisms may fail to have a Nash equilibrium  ? for some (two person) profiles in 0!88dd<<ti x6X@8;X@x6X@8;X@x6X@8;X@8it.  ?@  Proof of Lemma 2 a) The mechanism SS meets the assumptions of Theorem 1. Continuity is clear. Cross Monotonicity and Complementarity of each term  ?! 0O0(88Odd<<DV(S` cup \{i\})V(S)x6X@8;X@x6X@8;X@x6X@8;X@8V8S|8i\8VL8S8(8{8}l8)8(8)8=8D follow at once from the concavity of C; and they are both preserved by linear combinations. b) The mechanism SER meets the assumptions of Theorem 1.  _& Continuity follows upon noticing that the formulas yield a0,__dd<<zeta_i=zeta_{i+1} x6X@8;X@x6X@8;X@x6X@8;X@_ H_ +i+i_+V+1a@&0*((@@!'#%  '#/@  _ whenever X!0@__dd<< q_i=q_{i+1}x6X@8;X@x6X@8;X@x6X@8;X@_q+iZ_q+i_"+r+1X. To check the last two properties observe that  _ A0*__dd<<|)partial zeta_i/partial q_j = 0~if~q_i+i <C@<q~k2<Cg<q~k _n_k>1<(B<)<( ~1 <)_1 ߊ$(#(#(#(#!'#$where each term in the summation is non positive because 0'h88'dd<<q^kx6X@8;X@x6X@8;X@x6X@8;X@8qzk is non decreasing in k and C' is non increasing. This proves Cross Monotonicity. Taking derivatives one more time yields c!#xdddddLddx>{partial^2 zeta_i} over {partial q_i`partial q_j}=C"(q^i)0x6X@8;X@x6X@8;X@x6X@8;X@?c,g_,_,!XK2f()0c  /i_qG+i _q+j}Cq!ic$(#(#(#(#!!'#$The conscientious reader will complete the argument for the case where C is not differentiable everywhere (or will consult Moulin and Shenker [1992]).  ?v c) On the domain 0 88dd<<ti x6X@8;X@x6X@8;X@x6X@8;X@8it, both SS and SER may have no Nash equilibrium at all. We prove the claim for n=2 and the SS mechanism. Adapting our example to SER and n3 is straightforward. We fix a strictly  _@ concave function C and construct a profile T0#__dd<< (u_1,u_2)x6X@8;X@x6X@8;X@x6X@8;X@_(+1R_,B+2_)_u_uT with the following best reply functions: @&0*((@@!4 '#'#^!@ԌA#x@ddddd+/ddxw/P ?  (7)  ?  &stack {alignl br_1(q_2)`=[3,4]~~~~~~~~~~~~~~~if~q_2<2 # ~ # alignl~~~~~~~~~ = [ 1 over 2,1]`cup [3,4]~~~~~if~q_2=2 # ~ # alignl ~~~~~~~~~=[`1 over 2,1]~~~~~~~~~~~~~if~q_2>2}x6X@8;X@x6X@8;X@x6X@8;X@brq if` q ifJ q if> qe1R(Be2)[3,4x] e2( < 2[`21`U2,x1][j3,Z4] 2 2[v1v82,1] 2 >~ 2 * *28~=2N&$(#(#(#(#!A'#$and  { a#xddddd /ddx/# ? `? (8) ă$stack {alignl br_2(q_1) `= [`1 over 2,1]~~~~~~~~~~~~if~q_1<2 # ~ # alignl ~~~~~~~~~=[`1 over 2,1] cup`[3,4]~~~if~q_1=2 # ~ # alignl ~~~~~~~~~= [`3,4]~~~~~~~~~~~~~if~q_1>2}x6X@8;X@x6X@8;X@x6X@8;X@<br<q <if <qh if q _if _q2R<(B1<)<[l1l2 <,<1<]T 1 << <2[v|1v2,1][3,p4]( 1 2_[0_3_, _4_]H +1 _> _2 <*x *_2De2NH~=$$(#(#(#(#!a'#$The construction of 0__dd<<u_1x6X@8;X@x6X@8;X@x6X@8;X@_u+1 takes place in two steps. Denote by 0 {{dd<< zeta_{q_2}x6X@8;X@x6X@8;X@x6X@8;X@{ Gqdd%2 the  _ costshare of player 1 for a given choice !0`__dd<<q_2x6X@8;X@x6X@8;X@x6X@8;X@_q+2 by player 2:  { #xddddd ddx+zeta_q_2(q_1)=q_1 over {q_1+q_2}.C(q_1+q_2)x6X@8;X@x6X@8;X@x6X@8;X@! qq1cq_q_q9C)qiqdd2( 1[)/1 +1I+2.(121 )Y_iߛ$(#(#(#(#!'#$Note that the graphs of A0{{dd<<zeta_q_2x6X@8;X@x6X@8;X@x6X@8;X@{ Gqdd%2 are all concave and do not overlap (see  ? Figure 4). We call a088dd<<tdeltax6X@8;X@x6X@8;X@x6X@8;X@8 t a lower bound on the derivative of  ?` 0!88dd<< AC(q)=C(q)/q x6X@8;X@x6X@8;X@x6X@8;X@8ACz8q8C8q:8q8(8)Z8(J8)8/j8ߚ on [0,4]. This bound can be taken positive by the strict concavity of C. We define first the parametrized functions  { 05${{5dd<< alpha_q_2x6X@8;X@x6X@8;X@x6X@8;X@{Gqdd%2 as follows  8t   #,% 8@ddddd dd,% ystack {alignl alpha_q_2(q_1)=zeta_q_2 ( 1 over 2)(1 over 2 q_1).AC(0)~~~if~0q_1 1 over 2 # ~ # alignl ~~~~~~~~=zeta_q_2(q_1)~~~~~~~if~1 over 2q_11 # ~ # alignl ~~~~~~~~=(zeta_q_2(3)zeta_q_2(1). {(q_11)} over 2 + zeta_q_2(1))~~if~ 1q_13 # ~ # alignl ~~~~~~~~=zeta _q_2 (q_1)~~~~~~if~3q_14 # ~ # alignl ~~~~~~~~=zeta_q_2 (4)~~~~~~~if~4q_1}x6X@8;X@x6X@8;X@x6X@8;X@R J     J Jz qqqpq( AC ifqqqdif q0q q4 Aqr qifqqq ifD qFqzifL zqdd2"(1b)dd2L( {1 2)(X{1X218 ) . ( 0 )081F{1F2dd2D(41) ^1 2 1J 1J(ddg2(43)ddZg2(1). A( 1t A1 A) =2dd g2 (v1)f)1>13dd2D(41)T 3 1 4dd$2Dz(z44z)\ z4 F1"H  $ A N  z z2G20G2G2 *#    `&0*((@@A@'# A'#2a'#8@c&|`Ԍ$88d&d&88d&d& !8c&$  $88d&d&88d&d& !8c&$ԙ 8t Thus 05{{5dd<< alpha_q_2x6X@8;X@x6X@8;X@x6X@8;X@{Gqdd%2 coincides with 0{{dd<<zeta_q_2x6X@8;X@x6X@8;X@x6X@8;X@{ Gqdd%2 in the two intervals X0,0dd<< [1 over 2,1]x6X@8;X@x6X@8;X@x6X@8;X@![182,1o]2X and [3,4] and is linear on each of the other three intervals. Therefore  { d!0@{{dd<<alpha_q_2 zeta_q_2x6X@8;X@x6X@8;X@x6X@8;X@{{ GqGqdd%2ddX%2"{d and A05 @{{5dd<< alpha_q_2x6X@8;X@x6X@8;X@x6X@8;X@{Gqdd%2 is concave, for all a0@__dd<<q_2x6X@8;X@x6X@8;X@x6X@8;X@_q+2. Moreover for any given 0!@__dd<<q_1x6X@8;X@x6X@8;X@x6X@8;X@_q+1,  {" the term Z0b{{dd<<alpha_q_2(q_1)x6X@8;X@x6X@8;X@x6X@8;X@{Gq{qdd%2"{(G1b{)Z is continuous and strictly decreasing in 0b__dd<<q_2x6X@8;X@x6X@8;X@x6X@8;X@_q+2. Hence  {D the family of the graphs of 05{{5dd<< alpha_q_2x6X@8;X@x6X@8;X@x6X@8;X@{Gqdd%2 forms the indifference contours of  _f a preference 0 __dd<<u_0x6X@8;X@x6X@8;X@x6X@8;X@_u+0 in !0 88dd<<ti x6X@8;X@x6X@8;X@x6X@8;X@8it (of course after chopping off this part of the  {P graph where ZA0P {{dd<<alpha_q_2(q_1)x6X@8;X@x6X@8;X@x6X@8;X@{Gq{qdd%2"{(G1b{)Z is negative: see Figure 4).  {r Now we define two modifications of a05p{{5dd<< alpha_q_2x6X@8;X@x6X@8;X@x6X@8;X@{Gqdd%2, denoted 05U{{5dd<<beta_q_2x6X@8;X@x6X@8;X@x6X@8;X@{Gqdd%2 and 0( {{(dd<< gamma_q_2x6X@8;X@x6X@8;X@x6X@8;X@{Gqdd%2,  _ yielding respectively the indifference contours of 0!__dd<<u_1x6X@8;X@x6X@8;X@x6X@8;X@_u+1 and 0!__dd<<u_2x6X@8;X@x6X@8;X@x6X@8;X@_u+2.  _~ #x#dddddddx7stack {alignl if~q_22~~~beta_q_2(q_1)=alpha_q_2(q_1) delta over 9 (2q_2).(3q_1)_+~~~for~all~q_1 # ~ # alignl if~q_22~~~beta_q_2(q_1)=alpha_q_2(q_1) delta over 9 theta (q_2)(q_11)_+~~~~~if~0q_14 # ~ # alignl ~~~~~~~~~~~~~~~~~~~~=alpha_q_2(4) delta over 3~~~~~~~~~~~~~~~~~~~~~~if~4q_1}x6X@8;X@x6X@8;X@x6X@8;X@ifZqqqqq q qforcall#qifZqqqqqg qqifqqif q22dd2*(1j)dd.2j(Z 1 ) r9 ( 2c 2 )+.(31)122dd2*(1j)dd.2j(Z 1 ) U9 ( 2/ )(11O)01G4dd>b2z(4j ) 8341"" s K""  _ Z O Z 2  j  7 7 7x ߗ$(#(#~(#(#!'#$where 0+__dd<<"(x)_+=max\{x,0\}x6X@8;X@x6X@8;X@x6X@8;X@_(_)B_max_{_,_0_}_x"_xz+_"ߟ and !0+88dd<<tthetax6X@8;X@x6X@8;X@x6X@8;X@8t is the function A0av+__add<<theta(x)= min \{(x2)_+ , 1\}x6X@8;X@x6X@8;X@x6X@8;X@_~_(n_)^_min_{>_(_2_)_,^_1_}_x_x_._+  {8' One checks at once that a05x-{{5dd<<beta_q_2x6X@8;X@x6X@8;X@x6X@8;X@{Gqdd%2 is concave and increasing w.r.t. 0!x-__dd<<q_1x6X@8;X@x6X@8;X@x6X@8;X@_q+1@8'0*((@@!8@c&|#'#*@  { (the latter because 0 @{{ dd<<Gd/dq_1 [alpha_q_2(q_1)]x6X@8;X@x6X@8;X@x6X@8;X@{d{dq>GqB{q{/G1B{[dd%2{(G1 {){]{G is bounded below by 0@88dd<<delta/2x6X@8;X@x6X@8;X@x6X@8;X@8 8/82) and that  {" Y0b{{dd<< beta_q_2(q_1)x6X@8;X@x6X@8;X@x6X@8;X@{Gq{qdd%2"{(G1b{)Y is continuous and strictly decreasing in 0Mb__dd<<q_2x6X@8;X@x6X@8;X@x6X@8;X@_q+2 (the latter  {D because !0 p {{ dd<<Gd/dq_2 [alpha_q_2(q_1)]x6X@8;X@x6X@8;X@x6X@8;X@{d{dq>GqB{q{/G2B{[dd%2{(G1 {){]{G is bounded below by A0U 88dd<<delta/2x6X@8;X@x6X@8;X@x6X@8;X@8 8/82). Thus the family  {f of the graphs of a05 {{5dd<<beta_q_2x6X@8;X@x6X@8;X@x6X@8;X@{Gqdd%2 forms the indifference contours of a  { preference 0 __dd<<u_1x6X@8;X@x6X@8;X@x6X@8;X@_u+1 in 0 88dd<<ti x6X@8;X@x6X@8;X@x6X@8;X@8it. Note that 0/m{{/dd<<4!beta_q_2alpha_q_2zeta_q_2x6X@8;X@x6X@8;X@x6X@8;X@{{"{ GqGqGqdd%2ddn%2dd%2"{{4߱ for all 0__dd<<q_1x6X@8;X@x6X@8;X@x6X@8;X@_q+1. If $0__dd<<q_22x6X@8;X@x6X@8;X@x6X@8;X@_q+2R_2_$,  _ these inequalities are equalities only if !0`__dd<<93q_14;~if~q_2=2x6X@8;X@x6X@8;X@x6X@8;X@_3z+1B_4_;J+2_2____q_if_q9߶, these are  _ equalities for ^A0M __M dd<<,1/2q_11~\and~3q_14;~if~q_2>2x6X@8;X@x6X@8;X@x6X@8;X@_1_/_2j+12_1_3*+1_4j_; +2J _> _2z__:_z__q_and_q: _if _q^ they are equalities for  { la0C__dd<<1/2q_11x6X@8;X@x6X@8;X@x6X@8;X@_1_/_2j+12_1z___ql (see Figure 4). This shows (7). The functions 0(eC{{(dd<< gamma_q_1x6X@8;X@x6X@8;X@x6X@8;X@{Gqdd%1 are defined next:  { #xdddddddx?stack {alignl if~q_12~~~gamma_q_1(q_2)=alpha_q_1(q_2)delta over 9 (2q_1).(q_21)_+~~~~~if~0q_24 # ~ # alignl ~~~~~~~~~~~~~~~~~~~=alpha_q_1(4)delta over 3 (2q_1)~~~~~~~~~~~~~~~~~if~4q_2 # ~ # alignl if~q_1_`2~~~ gamma_q_1(q_2)=alpha_q_1(q_2) delta over 9 theta (q_1).(3q_2)_+~~~~~~~for~all~q_2}x6X@8;X@x6X@8;X@x6X@8;X@ifZqqqqq qqFif~qqS qkifqifZqqqqqe qq}for=allq12dd1( 2])dd!1](M 2 ) r9v ( 2V 1 ).(2N1)024dd1"(4 )I U3 (c 2 1 )4212ddb1((2h)dd,b1h(X 2 ) 89 ( 1- ) .(32M)u2" f >F  +-  M O H 2 %X   7 7 7 $(#(#(#(#!'#$The functions Z0@ {{dd<<gamma_q_1(q_2)x6X@8;X@x6X@8;X@x6X@8;X@{Gq{qdd%1{(G2U{)Z are similarly concave and increasing in 0X!__dd<<q_2x6X@8;X@x6X@8;X@x6X@8;X@_q+2 and  _ continuous and decreasing in 0H!__dd<<q_1x6X@8;X@x6X@8;X@x6X@8;X@_q+1. They represent a preference 0!!__dd<<u_2x6X@8;X@x6X@8;X@x6X@8;X@_u+2  ?    t in !0#88dd<<ti x6X@8;X@x6X@8;X@x6X@8;X@8it for which the best reply correspondence is given by (8). Q.E.D.  ?;  t  Proof of Statement ii of Lemma 1 : The mechanism ACP meets all assumptions of Theorem 1 except perhaps Complementarity. However, Complementarity holds if  ?# EA0:+*88:dd<<(C'AC)x6X@8;X@x6X@8;X@x6X@8;X@8(8)8C8ACzG8E is non increasing (we omit the straightforward  ?% computations). An example is any cost function Ya0f0 ,88fdd<< C(y)=y^alphax6X@8;X@x6X@8;X@x6X@8;X@8C8yj8y8(z8)8zY, where the  ?' coefficient 0P -88dd<<talphax6X@8;X@x6X@8;X@x6X@8;X@8t is in ]0,1[. 0'0*((@@'#0ԌThe two results (Theorem 1 and Lemma 2) reveal an important difference between our two domains of individual preferences. If  _  the domain is 0@ ` __dd<<i _*x6X@8;X@x6X@8;X@x6X@8;X@_i+, we have many simple mechanisms where Nash equilibrium behavior, although not unambiguous (because at some profiles we may have several equilibrium outcomes), has a Pareto superior selection (and where Cournot tatonnement starting from "very high" demands is sure to converge: see Milgrom and Roberts  ?J [1991]). If the domain is 0X88dd<<ti x6X@8;X@x6X@8;X@x6X@8;X@8it (Giffen goods are possible), then I do not know of any simple mechanism guaranteeing the existence of  ? at least one Nash equilibrium.11  ?  6THREE EQUITY TESTS (IN EQUILIBRIUM) The Stand Alone test is the most familiar equity property of the natural monopoly literature (e.g. Sharkey [1982]). The test says that an agent (or coalition of agents) should not pay more than the cost of serving his or her own demand.  ? b#x$dddddKJddxbStand~Alone~test:~for~all~S E \{1,...,n\}~~~sum_{i epsilon S} x_i  C(sum_{i epsilon S} q_i)x6X@8;X@x6X@8;X@x6X@8;X@StandAlonertest"for all Sn+i>+SxERi C+ii+SqpRiR: { 1 , .r..b,R}() E9I9I+ )+ b$(#(#(#(# !'#$ Lemma 3  ? If a simple mechanism 0X"88dd<<szetax6X@8;X@x6X@8;X@x6X@8;X@8 s satisfies Cross Monotonicity (see  _> Theorem 1) then every allocation  0e(~$__edd<<q(x_i,q_i)i=1,...,nx6X@8;X@x6X@8;X@x6X@8;X@_(Z_,_) _1_,_.r_._.b_,_x +i_qR+i_i_n_q passes the Stand Alone test.  ?!  Proof  ?H# Let ! 0)88dd<<szetax6X@8;X@x6X@8;X@x6X@8;X@8 s be a cross monotonic mechanism. Then we have for all q: !#x2+ddddd ddx+# ? `  (9) ă(FORALL i=1,...,n~~~~q_i=0~=>~zeta_i(q)=0x6X@8;X@x6X@8;X@x6X@8;X@_z__:_ __iJ_n"_q+i +i _qz_1_,j_._.Z_._,j_0_>@ _(0 _) _0 _ ߜ$(#(#$(#(#X!!'#$@J'0*((@@!$'# 2+'#R-!@Ԍ _ Indeed if !A 0` @__dd<<q_i=0x6X@8;X@x6X@8;X@x6X@8;X@_q+i_Z_0!, Cross Monotonicity implies a 0@__dd<<Jzeta_i(q)zeta_i(0)=0x6X@8;X@x6X@8;X@x6X@8;X@_ _ +iH_q+i_(_)n_(_0^_)N_08__J. Hence  _ property (9) because  0*__dd<<zeta_ix6X@8;X@x6X@8;X@x6X@8;X@_ +i is nonnegative. Next fix an arbitrary q  _ and a coalition S. Define q* by F 0N* __N*dd<< q_i^*=q_ix6X@8;X@x6X@8;X@x6X@8;X@_q:ik_q+i_F if  0vI 88vdd<< i epsilon Sx6X@8;X@x6X@8;X@x6X@8;X@8i8S8  and  0V* __V*dd<<q_i^*=0~if~i~ NOTIN Sx6X@8;X@x6X@8;X@x6X@8;X@_q:i;_if_i_S_S_k_0߄.  ( Property (9) and budget balance imply: X!0J Jph J Jdd<<6sum_{i epsilon S} zeta_i(q^*)=C(sum_{i epsilon S} q_i)x6X@8;X@x6X@8;X@x6X@8;X@9I9I+i~+SsRi;q C+ih+SqoRi>+  (+ ()()X. On  _ the other hand, Cross Monotonicity yields !!!0{ `__{ dd<<-zeta_i(q) zeta_i(q^*)~for~all~i epsilon Sx6X@8;X@x6X@8;X@x6X@8;X@_ _  _ +iH_q+i_q_forW_all _i _S_(_)n_(_)8_w!,  ? whence the conclusion by summing up these inequalities over A!0v 88vdd<< i epsilon Sx6X@8;X@x6X@8;X@x6X@8;X@8i8S8 .  ?  Q.E.D.  ?  Remark I. At every Nash equilibrium q of a cross monotonic mechanism, a stronger version of the Stand Alone test holds true, namely: A#xddddd ddx+$ ? `? (10) ăA.u_i(zeta_i(q),q_i)max_{q0} u_i(C(q),q)x6X@8;X@x6X@8;X@x6X@8;X@_u+i+i_q_qx+i +q_u+iX _CH _q _q_(_(_)_,_)_max+0_( _( _)8 _,( _)Z_ @_p+A$(#(#(#(#X!A'#$This says that no agent can improve his welfare by being the sole user of the technology. But the corresponding coalitional version of inequality (10) (defining the familiar Stand Alone Core, see Scarf [1986]) does not hold. Recall that out of the four mechanisms introduced in Section 4, only MCP fails Cross Monotonicity. As the example in Section 3 shows, MCP fails even the (weak) property (9). Our second test is the No Envy property, perhaps the single most important concept of the microeconomic literature on distributive justice. In the cooperative production model presently discussed, it can take two forms depending on whether agents compare their input.output trade via the mechanism, or0P&0*((@@'#(A0 compare their net consumption of these two goods (endowment minus input.output trade). See the discussion of these two variants in Thomson and Varian [1985] and Vohra [1992]. We retain the first interpretation because we study the fairness of the mechanism without any concern for the inequality of initial endowments (just like bargaining theory seeks a fair division of the surplus without questioning the fairness of the disagreement point). ^a#x0dddddeddx9No~Envy:~for~all~i,j=1,...,n:u_i(x_i,q_i)u_i(x_j,q_j)x6X@8;X@x6X@8;X@x6X@8;X@_NoZ_Envy _for_all_iz_j: _n* _u +ir_x+i_q:+iz_u+i_xB+j _q+j:_:_,j _1 _,Z _. _.J _. _, _: _(B_,_)J_(_,_)__^$(#(# (#(#X!a'#$The No Envy test interprets common ownership as equal opportunity: every agent gets the best of all the actual allocations (the actual opportunities at this particular equilibrium). Any allocation resulting from a non linear pricing scheme (see e.g. Guesnerie [1975], Vohra [1990]) must be envyfree. And vice versa: an envyfree outcome can be interpreted as a non linear pricing equilibrium, provided the non linear price is chosen  ?8 after we learn of our particular outcome.12 Our third (and last) equity test is the following: #x!dddddddx-$ ? ` (11) ă*9Unanimity~test:~for~all~i=1,..,n:x_i~{C(nq_i)} over nx6X@8;X@x6X@8;X@x6X@8;X@! Unanimitytestafor! all i)nxi<C<nqi8n: 1I , .9 . ,:w<(7<)Y 1*$(#(#X(#(# !'#$Thus an agent must pay at least his fair share in the hypothetical situation where all individual demands coincide with his. This inequality is compatible with budget balance because C is concave. The Unanimity test has been proposed (Moulin [1990b] [1992]) as a normative consequence of the fact that differences in individual demands should not bear differently on different agents@'0*((@@!0'#Pa!'#$@   (whereas if ba!0 P @ dd <<1x_i> {C(nq_i)} over n~\and~x_j < {C(nq_j)} over nx6X@8;X@x6X@8;X@x6X@8;X@0xi<C<nqi8nandx.j<<C, <nq$ jX 8n>6<(<)~<<(t <)11b, agent i suffers and agent j benefits from the fact that other agents' demands are different from his own).  ? The next Lemma states a property of a mechanism !0 88dd <<szetax6X@8;X@x6X@8;X@x6X@8;X@8 s, guaranteeing that all Nash equilibrium outcomes pass the No Envy and the Unanimity tests. Figure 5 provides the intuition for the Lemma, by showing four configurations of the opportunity sets in a two person mechanism. In three of these configurations a Nash equilibrium outcome with envy is depicted. The only configuration  _U without envy is that where !0) X__) dd <<'3x_1zeta_2(q_1,q_1)~\and~x_2 zeta_1(q_2,q_2)x6X@8;X@x6X@8;X@x6X@8;X@_x_q_q`_and _x _q _q+1+2_(+1P_,@+1_)+2+1 _( +2^ _,N +2 _)__R_ `_ 'ߤ.  ??  Lemma 4  ? Let !088dd <<szetax6X@8;X@x6X@8;X@x6X@8;X@8 s be a simple mechanism such that  ?y #xddddddd x-$ ? ` (12) ă6for~all~q,~all~i,j~~zeta_i(q) zeta_i(q line^j q_i)x6X@8;X@x6X@8;X@x6X@8;X@_for_all_q_all_i_j +i _q +i _qN j _q+i _,_,p _(` _) _(n_)_ P _  _ _ ߯$(#(#y(#(#X!'#$Then every Nash equilibrium (at an arbitrary profile in !088dd <<ti x6X@8;X@x6X@8;X@x6X@8;X@8it) is envyfree. Moreover the Unanimity test holds true at every demand profile.  ?  Proof  ?+ Fix a profile u in "0k#88dd <<ti x6X@8;X@x6X@8;X@x6X@8;X@8it and a Nash equilibrium q. Fix also two agents i,j. The equilibrium property, and property (12) yield: #x[&dddddEdd xAstack {alignl u_j(zeta_j(q),q_j) u_j(zeta_j(q line^j q_i), q_i) # ~ # alignl zeta_j (q line ^i q_i)=zeta_i( q line ^j q_i)  zeta_j(q)}~~~~ =>~~~~~ u_j(zeta_j(q),q_j) u_j(zeta_i(q),q_i)x6X@8;X@x6X@8;X@x6X@8;X@ujjqqxju8jnj6q#jN q i q i*jH^qi`^q*i*iV^qjn^q*i*jd ^q^ujjqDqjujiqqji((),)(( ) , )^(0^)^(>^)^( ^).>.(d(T),)( ()r,)Z  ^  ^ .^  L @ ^ ^^ ^ A߾$(#(#e (#(#!'#$which says that agent j does not envy agent i. On the other hand, inequality (11) follows from repeated  ?m' applications of anonymity and property (12). Q.E.D. @m' 0*((@@!'# &'#c* @ԌWhich simple mechanisms do meet property (12)? Marginal cost pricing (MCP) meets (12) for two person problems (n=2). There (12) amounts to: #xs ddddddd!x7A1 over 2 [C(q_1+q_2)+(q_1q_2).C'(q_1+q_2)]  1 over 2 C(2q_1)x6X@8;X@x6X@8;X@x6X@8;X@2N2 v1v82[(162)v(f12)n. ( 1 2# ) ] 1 82(a2Q1)C~qqq.qC q[ qqCqFw   7ߴ$(#(#(#(# !'#$which is a consequence of the concavity of C. A similar computation shows that MCP fails (12) if n3 (and an example of Nash equilibrium with envy is easily constructed). On the other hand, MCP passes the Unanimity test for all n (as inequality (11)  _ reduces to !"0  P__ dd!<<9%C(q_N)C(nq_i)(nq_iq_N).C'(q_N))x6X@8;X@x6X@8;X@x6X@8;X@_C_q+N_C_nq+ib_nqZ+i"_q+N _C _q +N_(_):_(_)_(_)j _. _( _)_ _)J_r__s 9߶. The serial mechanism (SER) satisfies (12) for any n. Consider  _ a demand profile q such that ~A"0H__dd!<<q_1...q_nx6X@8;X@x6X@8;X@x6X@8;X@_q2_q+n+1R_._.B_.__~ and two agents i,j. If 6a"0="__=dd!<< q_iq_jx6X@8;X@x6X@8;X@x6X@8;X@_q+iZ_q+j_6  _ notice that "0P __dd!<<q_jx6X@8;X@x6X@8;X@x6X@8;X@_q+j does not enter formula (1): therefore 5"0K__Kdd!<< zeta_i(q)x6X@8;X@x6X@8;X@x6X@8;X@_ +iH_q_(_)5 remains  _ unchanged if "0 __dd!<<q_1x6X@8;X@x6X@8;X@x6X@8;X@_q+1 changes in arbitrary fashion as long as it remains  _ bounded below by "0 __dd!<<q_ix6X@8;X@x6X@8;X@x6X@8;X@_q+i. This implies inequality (12) when  _j #0m__mdd!<<:q_iq_j.~If~q_jq_ix6X@8;X@x6X@8;X@x6X@8;X@_q+iZ_q+j_IfB_q+j_q +i__*_.:߷, then Cross Monotonicity implies (12). On the other hand, both ACP and SS fail the Unanimity test and have envious equilibrium outcomes for any n2. The second statement follows from Figure 5 and the observation that the opportunity sets of both mechanisms do not cross (they are "strictly" cross monotonic). The first statement is true for any demand profile of distinct demands provided C is strictly concave. SER is not the only example of a simple mechanism satisfying  ?D& property (12). Another such mechanism is the decreasing serial  ?' mechanism (de Frutos [1992])defined by the same formulas (1) at a0'!0*((@@ '# !0  _ demand profile such that !#0Uh@__Udd"<<9q_1q_2...q_nx6X@8;X@x6X@8;X@x6X@8;X@_qR_qr_q+n+1+2_. _._.___9߶. Equivalently this is the only simple mechanism where agent i's cost share does not depend  _z upon A#0 __dd"<<q_jx6X@8;X@x6X@8;X@x6X@8;X@_q+j as long as a#0 __dd"<<q_jx6X@8;X@x6X@8;X@x6X@8;X@_q+j remains bounded above by #0 __dd"<<q_ix6X@8;X@x6X@8;X@x6X@8;X@_q+i. Thus for n=2   this mechanism is defined by #0H) dd"<< Ex_1= {C(2q_1)} over 2, x_2=C(q_1+q_2) {C(2q_1)} over 2~if~q_1q_2x6X@8;X@x6X@8;X@x6X@8;X@0x<C<qx>C.qnql <C <q ifqq1.<(<21<)82,v2(126 ) <(\ <2L 1 <) 82T12 ##D  ߈. Checking property (12) for n=2 is immediate, and the general case is hardly more difficult (we omit the details). Notice that the decreasing serial mechanism is disqualified for the same normative reason as MCP, namely the fact that an agent demanding no output must pay a positive share of the cost incurred by the other agents' demand (namely, a violation of property (9)). With n=2 and  _ W#0D__dd"<< q_2=0 < q_1x6X@8;X@x6X@8;X@x6X@8;X@_qB_q+2R_0_<+1_W, agent 2 must pay #0eD__edd"<<RC(q_1) C(2q_1)/ 2x6X@8;X@x6X@8;X@x6X@8;X@_C_q_C"_q_(z+1_)2_(_2+1_)b_/_2B_R. The following table summarizes the equity propertie of (the equilibrium allocations of) our four mechanisms:  ^ ddx !ddx"` ((( ^ @@   ACP  MCP  SS  SER@P  Stand Alone Test#  Y#  N#  Y#  YP   No Envy Tests  Ns  n=2:Y n3:N;  N;  Y   # Unanimity Test  N  Y  N  Y  ;  ?K 7 A CHARACTERIZATION OF SERIAL COSTSHARING Our three equity tests are at the heart of the normative discussion of (first best) solutions of the cooperative production problem (all three properties generalize to technologies with multiple inputs and/or multiple outputs). An important observation is that, in general, there is no first best solution passing both  ?& the Stand Alone and the No Envy test.13 Therefore it is quite&"0*((@@ remarkable that one simple mechanism, namely serial cost sharing, always produces equilibrium outcomes passing all three tests (and  ?  of course, inefficient).14 Is serial cost sharing the only simple mechanism, of which the  ?@ equilibrium outcomes always (that is, for all profiles in $0 88dd#<<ti x6X@8;X@x6X@8;X@x6X@8;X@8it) meet our three tests? Surely it is the only such mechanism satisfying Cross Monotonicity and property (12). For the combination of these two properties implies at once  _ P#xddddddd#x-$ ? ` (13) ăE\{q_iq_j~=>~zeta_i(q)=zeta_i(q line ^j q_i)\}~~for~all~q,~all~i,jx6X@8;X@x6X@8;X@x6X@8;X@_{r_>_(_)_( _)v _}_,_,_q +i_qR+j+ix_qN+i_qj. _q +i _for^ _all_qf_all&_i_jZ__h__ B_ _ P$(#(# (#(#X!'#$This says that !$0 2__dd#<<zeta_i x6X@8;X@x6X@8;X@x6X@8;X@_ +i does not depend on A$02__dd#<<q_jx6X@8;X@x6X@8;X@x6X@8;X@_q+j as long as a$02__dd#<<q_j x6X@8;X@x6X@8;X@x6X@8;X@_q+j remains  _ bounded below by $0 __dd#<<q_ix6X@8;X@x6X@8;X@x6X@8;X@_q+i. Combined with anonymity and budget balance,  _ this forces serial cost sharing. Indeed suppose $0U__Udd#<<9q_1q_2...q_nx6X@8;X@x6X@8;X@x6X@8;X@_qR_qr_q+n+1+2_. _._.___9߶ and consider agent 1. Repeated applications of (13) give c!#xddddddd#xnext~~~~~ stack {alignl zeta_1(q)=zeta_1(q_1,q_1,...,q_1)=` {C(nq_1)} over n # ~ # alignl zeta_2(q)=zeta_2(q_1,q_2,...,q_2)=` {C(q_1+(n1)q_2)zeta_1(q)} over {n1}}x6X@8;X@x6X@8;X@x6X@8;X@nextq~qq q Cnq {nq~qq q ;C;q;nz;qh;qq7n H  H 2; 1h(X)1(1F,6 1 , .v . .f ,V 1 )j(K1")2h(X)2(1F,6 2 , .v . .f ,V 2 )j;(Z1";(;1;)2B;)1;(;)a71  ;;;7# ${ c$(#(#@(#(#x!!'#$and so on, until we get inductively the whole formula (1). Yet this is not a satisfactory characterization result because property (12) has no clear ethical justification. We want a result using directly the No Envy test. Note that Cross Monotonicity, a stronger requirement than Stand Alone, does have ethical meaning: when one agent raises her demand, thereby lowering both average and marginal costs, no one else should be hurt; more utilization of the technology can only produce positive externalities.@&#0*((@@!'##'#!!#@Ԍ ?  Theorem 2  ? a) Serial cost sharing is the only continuous, cross monotonic, simple mechanism of which all Nash equilibrium outcomes, for all  _ profiles in $0P __dd$<<i _*x6X@8;X@x6X@8;X@x6X@8;X@_i+, pass the No Envy test. b) There are other continuous simple mechanisms of which all Nash  _* equilibrium outcomes, for all profiles in $0`j88dd$<<{ i x6X@8;X@x6X@8;X@x6X@8;X@8i{ (and not just in %0!j__dd$<<i _*x6X@8;X@x6X@8;X@x6X@8;X@_i+), pass the No Envy test, as well as the Stand Alone and the Unanimity  ? test.  ?4  Proof of Statement a By the argument preceding Theorem 2 it is enough to show that a simple mechanism satisfying Cross Monotonicity and No Envy in equilibrium, must satisfy property (12) as well. Take a cross  ?t monotonic mechanism !%088dd$<<szetax6X@8;X@x6X@8;X@x6X@8;X@8 s and suppose there is a demand profile A%0 88dd$<<q barx6X@8;X@x6X@8;X@x6X@8;X@688q and  ? two agents i,j,ia%00 ^88dd$<<q!=x6X@8;X@x6X@8;X@x6X@8;X@8cqj, such that `A#xddddddd$xTq bar_i < q bar_j~\and~zeta_i(q bar) < zeta_i(q^*)~where~q^* =(q bar line^j q bar_i)x6X@8;X@x6X@8;X@x6X@8;X@6_~__l___q+iZ_q+j_and+ix_qN+i_q _wherew _qH_qj`_q+i_<_(_)h_<_(_) _(0_)B_ _  X __ `$(#(#(#(#X!A'#$Cross Monotonicity and budget balance imply:    t for all %0Jp Jdd$Sq_jq bar_i\{for~all~k!= j: zeta_k(q bar line ^j q_j)  zeta_k(q^*)\}~=>~\{zeta_j(q bar line ^j q_j) C(q_j+q bar _{N\\j})sum_{k!=j} zeta_k(q^*)\}x6X@8;X@x6X@8;X@x6X@8;X@qRjZqRiforball"kjpRk8 q jP q Rj~ RkF qRjeq-j}qRj=C-qRjuqRNRj+kI+j>Rkqc    o U+c~\ *{:( ) (')}>{(M)(=R\)()_}   /  9IS  {D  t This says that on q%0M #__Mdd$<<[q bar_i,+infinity)x6X@8;X@x6X@8;X@x6X@8;X@_[Z_,_)__q +i_J_q, the opportunity set >%0e#{{edd$<<O_{ q bar _{j}} x6X@8;X@x6X@8;X@x6X@8;X@{OGqdd%jGdd%> stays to the right of the graph of the concave increasing function   t%0G J6'G Jdd$<<2C(q_j+q bar _{N\\j} ) sum _{k != j} zeta_k (q^*)x6X@8;X@x6X@8;X@x6X@8;X@CqRjJqRNbRj~+k+jRkq(R\)c()*+cln9I t. Moreover, the set =&0ed'{{edd$<<O_{ q bar _{j}}x6X@8;X@x6X@8;X@x6X@8;X@{OGqdd%jGdd%= stays to the left of the graph of C (by Stand Alone): see Figure 6. Therefore we can  _u$ find a number !&0@ *__dd$<<q_j,q_j q bar_jx6X@8;X@x6X@8;X@x6X@8;X@_q+jZ_q+j_q"+j_,*__߀ and a preference A&05*__dd$<<u_jx6X@8;X@x6X@8;X@x6X@8;X@_u+j in a&0 *__dd$<<i _*x6X@8;X@x6X@8;X@x6X@8;X@_i+ of which the lower  {_& contour at &0 ,__dd$<<o(zeta_j(q bar line^j q_j),q_j)x6X@8;X@x6X@8;X@x6X@8;X@_(H_(_) _,h_)_ +j_qj_qX+j_q+j_8_ o contains <&0e{,{{edd$<<O_ {q bar_{j}}x6X@8;X@x6X@8;X@x6X@8;X@{OGqdd%jGdd%< but does not contain0_&$0*((@@'#DA$0  { &0\__dd%<<9(zeta_i(q bar), q bar_i)x6X@8;X@x6X@8;X@x6X@8;X@_(H_(8_)_,_)_ +i_q(_q+i_L_9߶ (remember &0[@__dd%<<6(zeta_i(q^*),q bar_i)x6X@8;X@x6X@8;X@x6X@8;X@_(H_(_)_,a_)_ +i_q_q+iQ_6߳ is in ;'0e\{{edd%<<O_{q bar_{j}}x6X@8;X@x6X@8;X@x6X@8;X@{OGqdd%jGdd%;). By Cross Monotonicity this implies  _ a#x* ddddddd%x ru_j(zeta_i(q bar line ^j q_j), q bar _i)  u_j(zeta_i( q bar), q bar_i) > u_j(zeta_j ( q bar line ^j q_j), q_j)x6X@8;X@x6X@8;X@x6X@8;X@_u+j+i_qXj_q(+jh_q+i(_u+j+i _q _q +i _uN +j+jL_qjd_q+j$_q+j_(_(x_)_,8_)_(. _( _) _, _)V _> _(_(4_)_,_)Z_ p_ _ __ _2 _p__ __ ߈$(#(#(#(#X!a'#$Figure 6 shows a possible construction of !'0` __dd%<<u_jx6X@8;X@x6X@8;X@x6X@8;X@_u+j using continuity of  _, A'0__dd%<<zeta_jx6X@8;X@x6X@8;X@x6X@8;X@_ +j. It remains to complete the profile u (in a'0*3l__*dd%<< i _*^nx6X@8;X@x6X@8;X@x6X@8;X@_i:n) by utilities  _ F'0__dd%<< u_k,k != jx6X@8;X@x6X@8;X@x6X@8;X@_u+kZ_kJ_j_,_cF, such that '0% __dd%<<%(zeta_k (q bar line ^j q_j), q bar_k)x6X@8;X@x6X@8;X@x6X@8;X@_(H_(_) _,h_)_ +k_qj_qX+j_q+k__8_  maximizes '0@__dd%<<u_kx6X@8;X@x6X@8;X@x6X@8;X@_u+k on agent k's  _ opportunity set at o'0 __dd%<<(q bar line^j q_j)x6X@8;X@x6X@8;X@x6X@8;X@_(r_)__qRj_q"+j_ o (using an indifference contour with a rightangle at that point). In this way we construct a profile  _T with an equilibrium at p(0x__dd%<<(q bar line ^j q_j)x6X@8;X@x6X@8;X@x6X@8;X@_(r_)__qRj_q"+j_ p where agent j envies agent i.  ?v  Proof of statement b In the case of two agents (n=2), we construct another simple mechanism meeting all three tests in equilibrium. In the case of two agents, the Unanimity test and property (12) coincide,  ? therefore all we have to do is to find a simple mechanism !(088dd%<<szetax6X@8;X@x6X@8;X@x6X@8;X@8 s such that "#x0"ddddddd%x-$ ? `  (14) ă<{C(2q_i)} over 2  zeta_i(q_1,q_2)  C(q_i)~~for~i=1,2x6X@8;X@x6X@8;X@x6X@8;X@1?g<C<qOi%iq-qCqU i for i<(W<2<)82u(e1,2)]( )} 1 ,m2?m  "$(#(#(#(# !'#$There are many such mechanisms, even under the additional  _ requirement that A(0 &__dd%<<zeta_ix6X@8;X@x6X@8;X@x6X@8;X@_ +i should increase with a(0&__dd%<<q_ix6X@8;X@x6X@8;X@x6X@8;X@_q+i. The following mechanism can be checked to be the best mechanism for the agent  _$ with the largest demand among those satisfying (14). For all $(0!Z*__dd%<<q_20x6X@8;X@x6X@8;X@x6X@8;X@_q+2R_0_$,  _& define (0jD,__jdd%<<:alpha(q_2) epsilon [0,q_2]x6X@8;X@x6X@8;X@x6X@8;X@_N_ _(+2_)_['_0_,+2_]_q_q:߷ as the smallest solution of the equation:@&%0*((@@!* '#f a%0"'#-%%@Ԍ`#xs@ddddd dd&x!C(q_2 + x)C(x)= 1 over 2 C(2q_2)x6X@8;X@x6X@8;X@x6X@8;X@!CqQxCxC_q(2)1(!)W1W82o(22' )A2/`$(#(#(#(# !'#$This is well defined because the lefthand side is non increasing  ? in x, and (0` 88dd&<<2{C(2q)}/ 2 C(q)x6X@8;X@x6X@8;X@x6X@8;X@8Cz8q8C8q8(828)j8/82J8(:8)Z82߯. Then define our mechanism as follows for  _ all q such that 6(0-0 / __-dd&<< q_1q_2x6X@8;X@x6X@8;X@x6X@8;X@_qR_q+1+2_6 (use anonymity to define it for 6)0-/ __-dd&<< q_2q_1x6X@8;X@x6X@8;X@x6X@8;X@_qR_q+2+1_6):  ? #x7dddddodd&xqif~0q_1 alpha(q_2): ~~~ stack {alignl zeta_1=C(q_1) # ~ # alignl zeta_2=C(q_1+q_2)C(q_1)} # ~ # ~ # alignl~~ if~ alpha(q_2)q_1q_2:~~~stack {alignl zeta_1=C(q_1+q_2) {C(2q_2)} over 2 # ~ # alignl zeta_2={C(2q_2)} over 2}x6X@8;X@x6X@8;X@x6X@8;X@if=qyqo C_ qo rC_ rq rqW rCGrqifqqq| Cl q q Cq ;C* ;qM01(2A):1 ( 1' )>2 r( >1 >2g r) r(>1r)(~2)61v2:1 ( 1$ 2t )"(2K2){22: ;( ;2 2 ;) 72r' r rF 4   }9 9r  F F # $# q$(#(#(#(#` !'#$Check that !)0 y88dd&<<szetax6X@8;X@x6X@8;X@x6X@8;X@8 s is well defined (check for q such that  _ A)0i#__idd&<<nq_1= alpha(q_2) \or~q_1=q_2)x6X@8;X@x6X@8;X@x6X@8;X@_qN_q_or_q_q+1_(+2_)N+1+2_)__R_n and continuous; moreover a)0I#88dd&<<talphax6X@8;X@x6X@8;X@x6X@8;X@8t is non decreasing and  _ )0 __dd&<<zeta_ix6X@8;X@x6X@8;X@x6X@8;X@_ +i is non decreasing in )0 __dd&<<q_ix6X@8;X@x6X@8;X@x6X@8;X@_q+i; and finally )0h 88dd&<<szetax6X@8;X@x6X@8;X@x6X@8;X@8 s satisfies (14). Q.E.D.  ?   9 CONCLUDING COMMENTS Two earlier characterizations of serial cost sharing can be compared to Theorem 2. The first one uses the fact that it has a unique Nash equilibrium when the cost function is convex  ? (decreasing returns to scale), and for any preference profile in )0(#7#88dd&<<ti x6X@8;X@x6X@8;X@x6X@8;X@8it: Moulin and Shenker [1992]. See also de Frutos [1992] for a similar characterization involving both the increasing and decreasing versions of serial cost sharing (defined in the last paragraph of Section 6). The second one is purely axiomatic and relies on the linearity of formula (1) w.r.t. the cost function C: Moulin and Shenker [1993]. The present result uses normative properties of@q&&0*((@@!@'# &'#&@ the equilibrium outcomes (the No Envy test) as well as normative properties of the cost sharing formula itself (Cross Monotonicity). In the cooperative production problem, the dual of the cost sharing approach is surplus sharing: each agent sends an input  @ contribution *0 __dd'<<x_ix6X@8;X@x6X@8;X@x6X@8;X@_x+i and the total output i!*08J  8Jdd'<< (F(sum_i x_i)x6X@8;X@x6X@8;X@x6X@8;X@(()FV+ix]Riz9Ii, where F is the production function) is divided according to a certain formula (e.g. Israelsen [1980]). Most cost sharing mechanisms are unambiguously transformed into surplus sharing mechanisms: out of our four mechanisms (ACP,MCP,SS and SER) only MCP is hard to  ?o transform.15 The characterization result (Theorem 2) is easily adapted to the surplus sharing context: we only need to reverse the Cross  _ Monotonicity axiom (agent i's output share A*0___dd'<<q_ix6X@8;X@x6X@8;X@x6X@8;X@_q+i is non decreasing in  _  agent j's input contribution Fa*0HI__dd'<< x_j,j != ix6X@8;X@x6X@8;X@x6X@8;X@_x+jZ_jJ_i_,_cF). But Theorem 1, on the other hand, has no obvious counterpart in the surplus sharing context: the combination of Cross Monotonicity and of (the reverse of)  _ Complementarity (namely *0S __dd'<<r0{partial^2 q_i}/{partial x_i partial x_j} 0)x6X@8;X@x6X@8;X@x6X@8;X@_, _,:_,j_r2_/_0Z_)_qB+ij_x+i_x+jr does not imply that the  _5 corresponding games have strategic complementarities on *0u"__dd'<<i _*x6X@8;X@x6X@8;X@x6X@8;X@_i+. A more satisfactory characterization result would not make use of the CM axiom. I conjecture that statement a of Theorem 2 still holds if we replace CM by the property that the mechanism has at  _" least one Nash equilibrium for all profiles in *0)__dd'<<i _*x6X@8;X@x6X@8;X@x6X@8;X@_i+"'0*((@@  ? & FOOTNOTES ă  _  1. We must interpret the allocation T*0-` __-dd(<< (x_i,q_i)x6X@8;X@x6X@8;X@x6X@8;X@_(Z_,_)_x +i_qR+iT as the actual consumption of agent i: no further trading of input and/or output between the agents is allowed. This may require close monitoring of the allocation as in the photocopying example. 2. Existence of an equilibrium in mixed strategies is of no help here for i) a mixed strategy is an immensely more complicated object when pure strategies vary in the real line, and ii) no satisfactory evolutive story can be invoked for mixed strategies. 3. And one mechanism, serial cost sharing, is essentially characterized by the property that the Nash equilibrium is unique at all such preference profiles: Moulin and Shenker [1992]. 4. The argument on p 1023 of Moulin and Shenker [1992] is equally valid under increasing returns. 5. We do not want agents to compare their net consumptions i.e.  _Z input endowment minus +0__dd(<<x_ix6X@8;X@x6X@8;X@x6X@8;X@_x+i because this would entail an ethical judgment over the initial distribution of endowments. We choose instead to incorporate those endowments in the preference profile and view the differences in individual preferences as ethically neutral. '(0*((@@Ԍ6. Say that a large number of agents each demand one unit of the good, and that their reservation price generate the usual downward sloping demand curve. Call p the "competitive" price namely the lowest price equal to the marginal cost of the corresponding demand (i.e. the lowest intersection of the demand and marginal costs curve). Then efficiency requires to serve all agents with a reservation price above p and only those (call them active agents). No Envy requires that every active agent pay the same price p'. Because of increasing returns, p' must exceed p. By applying No Envy to an agent with reservation price immediately above p and to one immediately below p, we see that this inactive agent (hence all inactive agents, by No Envy again) must pay p'p. This contradicts  _ the Stand Alone test for the inactive agents (who, consuming !!+0H!__dd)<<q_i=0x6X@8;X@x6X@8;X@x6X@8;X@_q+i_Z_0!,  _ should pay nothing: A+0__dd)<<x_iC(0)=0)x6X@8;X@x6X@8;X@x6X@8;X@_x+iZ_C_:__(J_0_)_0*_)ߋ.  _ 7. Whenever Ya+0P __dd)<< q_1=q_25x6X@8;X@x6X@8;X@x6X@8;X@_qR_q+1+2_5__Y, we have w+0*__*dd)<< u_i'(q_i)<1x6X@8;X@x6X@8;X@x6X@8;X@_u:iZ_q+i_(*_)_<_1w and X+0 __dd)<< dx_i/dq_i>1x6X@8;X@x6X@8;X@x6X@8;X@_dx +i_dq+iZ_/_>_1X.  _ 8. Note that we have two local maxima, at !+0`]__dd)<<q_1=1x6X@8;X@x6X@8;X@x6X@8;X@_q+1R_1_! and 5+0U* (__U*dd)<<q_1'=16x6X@8;X@x6X@8;X@x6X@8;X@_q_:1R_165 respectively. 9. Note that MCP is not defined in that case because the term  ?\ ,0 $88 dd)<<. (C(q)qC'(q))x6X@8;X@x6X@8;X@x6X@8;X@8(8(8)8(8)8)8Cz8q8qC8qj8z.߫ is negative.  ?> 10. The equilibrium of SER is unique for every profile in !,0~&88dd)<<ti x6X@8;X@x6X@8;X@x6X@8;X@8it (Moulin and Shenker [1992]; that of ACP is unique (utilitywise) for every  _x# profile in A,0 )__dd)<<i _*x6X@8;X@x6X@8;X@x6X@8;X@_i+ (Watts [1992]). &)0*((@@Ԍ11. And I conjecture that none exists: should we drop the anonymity requirement in the definition of a simple mechanism, a dictarorial mechanism would do. 12. Of course the simple mechanism that we call marginal cost pricing does not necessarily result in a non linear pricing equilibrium (because the opportunity set faced by one agent is determined by the strategic choice of the other agents). Still, the Nash equilibrium outcomes of the MCP mechanism are always envyfree with only two agents (as explained below).  _ 13. This is true for preference profiles in a,0PP__dd*<<i _*x6X@8;X@x6X@8;X@x6X@8;X@_i+ک or even quasilinear preferences: see footnote 7 and Moulin [1990 a]. See also Vohra  _ [1992] showing a twoperson example with preferences in ,0__dd*<<i _*x6X@8;X@x6X@8;X@x6X@8;X@_i+ where no efficient and envyfree outcome exists. 14. Notice that this holds true even with continuous, monotonic, but not necessarily convex preferences.  $ 15. Because the formula ,0 d dd*<<.q_i=x_i.F'(x_N)+ 1 over n (F(x_N)x_N.F'(x_N))x6X@8;X@x6X@8;X@x6X@8;X@!qiixiFxfN8nFxtN x4 N F1 x NB.<  9.n()1(|() . ( )y )2 may yield a negative output share. *0*((@@  ? % REFERENCES ă  ?X 1. Baumol W., Panzar J. and Willig R., 1982 Contestable Markets  ? and the Theory of Industry Sturcture, New York: Harcourt Brace Jovanovitch. 2. Brown D., Heller W. and Starr R., 1991 TwoPart Marginal Cost  ? Pricing Equilibria: Existence and Efficiency, forthcoming, Journal  ?( of Economic Theory. 3. Faulhaber G., 1975 "Cross Subsidization: Pricing in Public  ?H Enterprises," American Economic Review, 65, 96677. 4. Fleurbaey M. and F. Maniquet, 1993 Cooperative Production: a Comparison of Individual Rationality Constraints, mimeo, University of Namur. 5. deFrutos M.A., 1992 Decreasing Serial CostSharing Under Economies of Scale, mimeo, Universitat Autonoma de Barcelona. 6. Guesnerie R., 1975 Pareto Optimality in Non Convex Economies,  ?8 Econometrica, 43, 129. 7. Israelsen D., 1980 "Collectives, Communes and Incentives,"  ?X Journal of Comparative Economics 4, 99124. 8. Maniquet F., 1993 Allocation Rules for a Commonly Owned Technology: the Average Cost Lower Bound, Ph.D. thesis, University of Namur. 9. MasColell, A., 1980 Remarks on the GameTheoretic Analysis  ?(# of a Simple Distribution of Surplus Problem, International Journal  ?$ of Game Theory, 9, 125140. '+0*((@@Ԍ10. Milgrom P. and Roberts J., 1991 Adaptive and Sophisticated  ? Learning in Normal Form Games, Games and Economic Behavior, 3, 82100. 11. Milgrom P. and Shannon C., 1991 Monotone Comparative Statics, mimeo, Stanford. 12. Moore, J., 1992 Implementation in Environments with Complete  ?` Information, in Advances in Economic Theory, ed. J.J. Laffont, Cambridge University Press. 13. Moulin H., 1987 A Core Selection for Pricing a Single Output  ? Monopoly, Rand Journal of Economics, Autumn 18,3,397407 14. Moulin H., 1990a Joint Ownership of a Convex Technology:  ?0 Comparison of Three Solutions, Review of Economic Studies, 57, 439452. 15. Moulin H., 1990b Uniform Externalities: Two Axioms for Fair  ? Allocation, Journal of Public Economics, 43, 305326. 16. Moulin H., 1992 Welfare Bounds in the Cooperative Production  ? Problem, Games and Economic Behavior, 4, 373401. 17. Moulin H. and Shenker S., 1992 Serial Cost Sharing,  ?  Econometrica, 60,5, 10091037. 18. Moulin H. and Shenker S., 1993 Average Cost Pricing Versus  ?@ Serial Cost Sharing, forthcoming, Journal of Economic Theory.  ? 19. Myerson R., 1991 Game Theory: Analysis of Conflict, Harvard University Press. 20. Palfrey T., 1992 Implementation in Bayesian Equilibrium: the  ?% Multiple Equilibrium Problem in Mechanism Design, in Advances in  ?' Economic Theory. ed. J.J. Laffont, Cambridge University Press.',0*((@@Ԍ21. Scarf H., 1986 "Notes on the Core of a Productive Economy,"  ? in Contributions to Mathematical Economics in Honor of Gerard  ?  Debreu, W. Hildenbrand and A MasColell, Editors, NOrthHolland, Amsterdam. 22. Sharkey W., 1982 The Theory of Natural Monopoly, Cambridge: Cambridge University Press. 21. Shubik, M., 1962 Incentives, Decentralized Control, the  ? Assignment of Joint Costs and Internal Pricing, Management Science, 32543. 23. Thomson W. and Varian H., 1985 Theories of Justice Based on  ? Symmetry, in Social Goals and Social Organizations, L. Hurwicz, D. Schmeidler and H. Sonnenschein editors, Cambridge, Cambridge University Press. 24. Vohra R., 1990 On the Inefficiency of TwoPart Tariffs,  ? Review of Economic Studies, 57, 3, 415438. 25. Vohra R., 1992 Equity and Efficiency in NonConvex Economies, Social Choice and Welfare, 9, 3, 185202. 26. Watts A., 1992 On the Uniqueness of Equilibrium in the Cournot Oligopoly and Other Games, forthcoming, Games and Economic  ? Behavior.  ?@ 27. Young H.P., 1985 Cost Allocation: Methods, Principles,  ? Applications. North Holland.