domain: math qfin

text:
Benjamin Heymann

Alejandro Jofr

MECHANISM DESIGN AND ALLOCATION ALGORITHMS FOR NETWORK MARKETS WITH PIECE-WISE LINEAR COSTS AND EXTERNALITIES

Keywords: Auctions, mechanism design, allocation algorithm, electricity markets, fixed point AMS subject classifications. 91B26, 90C35, 90C15, 90B15, 91B44, 91B51, 91B52, 91A43, 91B26, 91B24, 68W15, 05B85

 for simplified markets of two agents with linear production cost functions. In standard procurement auctions, the market power resulting from the quadratic transmission losses allow the producers to bid above their true value (i.e. production cost). The mechanism proposed in the previous paper reduces the producers margin to the society benefit. We extend those results to a more general market made of a finite number of agents with piecewise linear cost functions, which make the problem more difficult, but at the same time more realistic. We show that the methodology works for a large class of externalities. We also provide two algorithms to solve the principal allocation problem.

1. Introduction. Our purpose is to show how monopolistic behaviors in network markets can be opposed using mechanism design. We point out that the optimal mechanism we obtain has a surprisingly simple expression. We complete this work with algorithmic tools for the computation of this mechanism. Following a model proposal already discussed in [START_REF] Juan | Monopolistic competition in electricity networks with resistance losses[END_REF][START_REF] Juan | Equilibrium analysis of electricity auctions[END_REF][START_REF] Figueroa | Cost-minimizing regulations for a wholesale electricity market[END_REF], we consider a geographically extended market where a divisible good is traded. Each market participant is located on a node of a graph, and the nodes are connected by edges. The good can travel from one node to another through those edges at the cost of a quadratic loss. We will use the word principal to designate what could also be called in the literature a central operator, or in the context of electricity markets, an ISO. This principal, who aggregates the (inelastic) demand side, has to match locally -i.e. at each node -production and demand at the lowest expense through a procurement auction. As argued in [START_REF] Figueroa | Cost-minimizing regulations for a wholesale electricity market[END_REF] this setting is relevant to describe some real electricity markets, but it could also be used in other markets where a good is transported. There is a clear antagonism between the market participants: the operator wants to minimize its expected cost while the producers want to maximize their expected profit. So there is a transaction and a commitment between each agent and the principal, and at the same time, there is a competition among the agents. In a standard procurement auction, the market power resulting from the quadratic line losses allow the producers to bid above their true value (i.e. production cost) [START_REF] Juan | Monopolistic competition in electricity networks with resistance losses[END_REF]. The mechanism reduces the producers margin and decrease the social cost represented in this case by the optimal value of the principal. The optimal auction design was introduced by Myerson in 1981 [START_REF] Roger B Myerson | Optimal auction design[END_REF]. We build on an electricity market model introduced by the second author in two previous papers [START_REF] Juan | Equilibrium analysis of electricity auctions[END_REF] and [START_REF] Juan | Monopolistic competition in electricity networks with resistance losses[END_REF]. The authors wrote a brief presentation of this model in [START_REF] Heymann | Mechanism design and auctions for electricity network[END_REF]. Other models were proposed for example in [START_REF] Aussel | Electricity spot market with transmission losses[END_REF], [START_REF] Edward J Anderson | Mixed strategies in discriminatory divisible-good auctions[END_REF], and [START_REF] Hu | Using epecs to model bilevel games in restructured electricity markets with locational prices[END_REF], with a focus on the existence of a market equilibrium. Concerning the techniques we use in this paper the reader can refer to [START_REF] Laffont | The theory of incentives: the principal-agent model[END_REF], [START_REF] Nisan | Introduction to mechanism design (for computer scientists)[END_REF], [START_REF] Robert | Handbook of game theory with economic applications[END_REF] chapter 45 and [START_REF] Donald | Supermodularity and complementarity[END_REF] for general introductions on principal agent theory, mechanism design, game theory and lattices theory respectively.

We consider -similarly to [START_REF] Figueroa | Cost-minimizing regulations for a wholesale electricity market[END_REF]-that everybody knows the demand at each node before the interactions start and that the production cost of each agent is private information. In a standard setting the agents first bid their cost and then the principal, knowing the bids, a posteriori minimizes its cost. So in a standard setting the principal is a bid taker. The producers know they influence the allocation and compete with each other to maximize their individual profit. Since the demand is known by everyone, everyone can guess the principal reaction once the bids have been announced: we can virtually remove the principal from the interaction in the standard setting and consider that the agents are the players of a game with incomplete information (since the agents do not know their fellow agents preferences). This equivalence is true provided that the agents are not communicating with each others. The mechanism design consists in changing the payoff function of this game -subject to constraints we detail in this article-so as to minimize a priori (i.e. before the bids are announced) the principal cost. Allowing the principal to strike first by revealing a committing rule gives him a strategic advantage in the negotiation.

We restrict our discussion to determinist demand, but the reasoning extends naturally to random demand as long as any possible realization of the demand satisfies the model assumptions. Indeed since the optimal mechanism constructed in this article is incentive compatible, then a random version (where the demand is revealed after the producers bidding phase, as in [START_REF] Juan | Equilibrium analysis of electricity auctions[END_REF]) would be realization-wise incentive compatible, and so incentive compatible. Observe the mechanism we propose in the following could be adapted to elastic, piecewise linear demand.

Our first main result is the mechanism design characterization. Interestingly the allocation procedures for the optimal and the standard mechanism are the same (one just needs to modify the input of the allocation procedure of the standard mechanism to get the allocation of the optimal mechanism). Our second main result is a principal allocation algorithm based on a fixed point. The fixed point could be interpreted as cooperating agents trying to minimize a global criteria by sharing relevant information. Our implementation of the algorithm gives good results against standard methods. We point out that the numerical computation of Nash equilibrium for the procurement auction (important to compare the optimal mechanism and the standard auction setting) requires an efficient algorithm to compute the allocation. Some other additional facts are presented within the paper: the smoothness of the allocation functions (q and Q), a decreasing rate estimation for the fixed point iterations, some results of numerical experiments with the fixed point algorithm, and a specific algorithm for the two-agent case.

We describe the market in the next section. In §3 we introduce and solve the mechanism design problem. In §4, we study the standard allocation problem and propose an algorithm to solve it. In §5 we propose a different algorithm for the 2agent standard allocation problem. In §6 we sum up and comment the main results and propose some continuations for this work. A reader only interested in mechanism design could read §2, §3 and §4 only, whereas readers interested only in allocation algorithms could concentrate on §4 and §5.

2. Market description. The production cost of each agent is assumed to be piecewise linear, non decreasing and convex in the quantity produced. This class of functions is sufficiently rich to represent real life problems and sufficiently simple for theoretical study. In this work we need to assume that the production levels at which there is a slope change are known in advance and exogenous (i.e. the agents cannot choose them). Then without loss of generality we assume that there is a quantity q such that the changes of slope only occur at the multiples of q. Thus, the authors find it practical to write the production cost functions in the form

(2.1) C c (q) = N j=1 c j min((q -(j -1)q) + , q),
where N ∈ N and the c j are some slopes coefficients specific to the agent, while q is the quantity produced. We will sometimes refer to the vector of the c j as the cost vector (of the agent). If we denote by q j i the quantity produced by agent i at marginal cost c j i , then q j i = min((q i -(j -1)q) + , q), where q i is the total quantity produced by this agent. Let

c * < c * ∈ R * + and C a set of non-decreasing N -tuples of [c * , c * ].
To each element c of C we associate the piecewise linear cost function q → C c (q). Throughout the paper we set, for any c ∈ C, c N +1 = c * to simplify notations in some proofs. Note that in practice a capacity constraint of the type q ≤ j q for a given agent can be implemented by setting its (j + 1) th slope c j+1 equal to a big positive number. If an agent of cost vector c produces a quantity q and receives a transfer x, then its profit is (2.2)

u i = x -C c (q).
There are n agents numbered from 1 to n in the market. We denote I = [1 . . . n] and use generically the letter i to refer to a specific agent, and -i to refer to I\{i}. We denote J = [1 . . . N ] and we will use generically j for the cost coefficients of the jth segment (starting from 1). The agents are dispatched on the n nodes of a graph. At each node i we find the corresponding agent i and a local demand d i . The nodes are connected by undirected edges. We write V (i) the set of nodes different from i connected to i.

Obviously if i 1 ∈ V (i 2 ) then i 2 ∈ V (i 1 ). We denote E = {(i 1 , i 2 ) : i 1 ∈ V (i 2 )
} the set of undirected edges. For each (i 1 , i 2 ) ∈ E, we introduce a quadratic loss coefficient r i1,i2 such that r i1,i2 = r i2,i1 . In the context of electricity market, this quadratic coefficient corresponds to the Joule effect within the lines. We make the non restricting assumption that N is big enough so that in what follows production at each node is smaller than qN .

We assume that both the agents and the principal are risk neutral: they maximize their expected profit. If the principal proposes to pay a price x i to agent i to make her produce a quantity q i -this agent being free to accept or decline the offer-and if the agent i has a production cost defined by c i , then she accepts the offer if

(2.3) x i -C ci (q i ) ≥ 0.
So for agent i, either x i ≥ C ci (q i ) or q i = 0. Thus, if the principal knew the cost vectors c i , he would solve an allocation problem with those c i , and then bid to the agents the quantity and the payments corresponding to the solution of the allocation problem. But the principal does not know the cost vectors, so instead what happens is that the agents tell her some values for the c i (not necessary their real cost vectors), and then the principal decides based on those values. In this case, previous works [START_REF] Juan | Monopolistic competition in electricity networks with resistance losses[END_REF] showed that the agents can get non-zero profits and bid above their production costs.

The question we adress is how to reduce their margins.

To do so, we need to consider an intermediate scenario between the one in which the agent knows nothing (and is a price taker), and the one in which he knows everything (and optimizes directly the whole system as a global optimizer). Each agent is characterized by an element f i , which is a probability density of support included in C and an element c i of C drawn according to f i . Only agent i knows c i , which is private information. The other agents and the principal only know the probability f i with which it was drawn. The density f i corresponds to the public knowledge on agent i production costs so the principal won't accept any bid c i that is not in the support of f i . We assume that the cost slopes are not correlated for a given agent and between agents, i.e. their laws f j i are independent. In particular f i (c i ) = j∈J f j i (c j i ). In such situation, it makes sense to define (2.4)

f -i (c -i ) = i ∈I\i f i (c i ) and f (c 1 , .., c n ) = i∈I f i (c i ),
and E (respectively E c-i ) the mean operator with respect to f (respectively f -i ). The density f (resp. f -i ) represents the uncertainty from the principal (resp. agent i) perspective. To simplify notations we will use the symbole C n to denote the product of the supports of the f i . We denote by Q the set of allocation functions -which are the applications from C n to R n + , by X the set of payments functions -which are the applications from C n to R n , and by H the set of flow functions -which are the applications from C n to R E . A direct mechanism is a triple (q, x, h) ∈ (Q, X , H). Let (q, x) ∈ (Q, X ). For this payment function and this allocation function, the expected profit of agent i of type c i and bid c i is

(2.5) U i (c i , c i ) = E -i u i = X i (c i ) - j∈J c j i Q j i (c i ).
where the capitalized quantities

(2.6) Q j i (c i ) = E -i min((q i (c i , c -i ) -(j -1)q) + , q) and X i (c i ) = E -i x i (c i , c -i )
correspond to the average of their non capitalized counterpart. We also denote by

(2.7) V i (c i ) = U i (c i , c i ).
the expected profit of agent i if she is of type c i and bids her true production cost.

In this work we make five assumptions.

• First, the non overlapping working zones assumption is that if we denote by C i the support of f i , then C i should be of the form:

(2.8)

C i = [c 1- i , c 1+ i ] × . . . × [c N - i , c N + i ] with c 1- i < c 1+ i < . . . < c N - i < c N + i
. We could interprete each segments over which the agent has a constant marginal cost as a working zone with identified productive assets. The expertise of the market participants should allow them to, based on the working zone, assess the marginal cost of the agent. This makes senses for instance if the setting is repeated over time. This estimation need to be precise enough so that there is no chance that it corresponds to another working zone. We use this item in particular in the proof of lemma 3.6.

• For i ∈ I, j ∈ J and c i ∈ C i let (2.9)

K j i (c i ) = c j i c j- i f i (c -j i , s)ds f i (c i )
.

We point out that by independence of the laws of the c j i ,

K j i (c i ) = c j i c j- i f j i (s)ds/ f j i (c j i ) = K j i (c j i ).
So K j i is simply the ratio of the cumulative distribution and the probability density for c j i . The second assumption is the discernability assumption. For all i ∈ I and c i ∈ C i , the virtual cost J i,j (c j i ) = c j i + K j i (c j i ) is increasing in j. As demonstrated in the next section, the virtual cost could be interpreted as the real marginal cost augmented by a marginal information rent. The item imposes the marginal information rent to be such that for any bid, the virtual marginal prices are increasing, i.e. the virtual production cost function is convex. The item is necessary to show the independence property of the reformulation in Lemmas 3.8 and 3.9.

• Third, in the following we assume that, for all j ∈ J, i ∈ I and c i ∈ C i , (2.10)

c j i → c j i + K i j (c j i )
is increasing in c j i . This is the piecewise linear adaptation of the classic monotone likelihood ratio property assumption encountered in mechanism design [START_REF] Roger B Myerson | Optimal auction design[END_REF][START_REF] José | On the planners loss due to lack of information in bayesian mechanism design[END_REF]. It is true in particular for log-concave functions. The assumption ensures that the pointwise allocation resulting from the mechanism design problem reformulation is decreasing in the bids. We refer to this assumption in the proof of Theorem 3.11.

• Fourth, for §3 and §4 only, we assume that (2.11)

d i - i ∈V (i) 1 2r i,i
< 0, and

d i + i ∈V (i) 3 2r i,i > N q,
i.e. we require the r i,j to be small enough. Note that the bigger the demand, the smaller the r should be, which is a limit to the generality of the approach. This assumption ensures that, for any agent i and working zone k, no matter what the other agents are doing, it is still possible to find a (virtual) marginal price that would ensure a production of exactly k q in an optimal allocation. If the loss rates r ii are all too big for a given agent i, then the line losses can be bigger than the flow through the lines: the lines of agent i can be all saturated. This hypothesis is necessary to ensure the existence of one of the building block of the fixed point operator presented in §4. We point out that this is the multidimensional version of the assumption 1 -2rd ≥ 0 in [START_REF] Figueroa | Cost-minimizing regulations for a wholesale electricity market[END_REF]. • Fifth, for regularity issues we make the non restrictive assumption that it is not possible to produce a multiple of q at each node and satisfy exactly the nodal constraints. This is non restrictive because if this was the case we could perturb the demand to ensure the condition is satisfied. This hypothesis will be important in the proof of the regularity of q (in lemma 4.4), from which the regularity of Q follows. To finish with the market presentation, we introduce the products of the type sets

C n = i∈I C i and C -i = i ∈I\{i} C i .
3. Mechanism Design. We start with the revelation principle as expressed in [START_REF] Gibbons | Game theory for applied economists[END_REF].

Theorem 3.1 (Revelation Principle). To any Bayesian Nash equilibrium of a game of incomplete information, there exists a payoff-equivalent direct revelation mechanism that has an equilibrium where the players truthfully report their types. According to the revelation principle, we can look for direct truthful mechanisms.

There is a priori no reason why the agents should willingly report their types. So we need to add a constraint on the design to enforce truthfulness. This means that the profit of any agent i of type c i should be maximal when agent i bids her true type c i i.e. for all (c i , c i )

(3.1) U i (c i , c i ) ≥ U i (c i , c i ). (IC)
This is the incentive compatibility (IC) constraint. In addition, since we want all agents to participate in the market, we need the participation constraint imposing that for all c i

(3.2) U i (c i , c i ) ≥ 0. (P C)
Without this constraint, the principal would optimize as if the agents would accept any deal (even deals where they would make a negative profit). The last constraint is that the supply should be at least equal to the demand at every node. The supply available at a given node is equal to the production augmented by the imports minus the exports and the line losses. As explained earlier, there is a loss when some quantity h i,i of the divisible good is sent from one node i to another i . This loss is equal to r i,i h 2 i,i , where r i,i is a multiplicative constant. In order to obtain symmetric expressions, we will proceed as if half of this quantity was lost by the sender, and the other half by the receiver (see for instance [START_REF] Juan | Monopolistic competition in electricity networks with resistance losses[END_REF]). Note that we could have equivalently used signed flows, but we would have lost some symmetry in the formulation. Then the supply and demand constraint writes, for all i ∈ I and c ∈ C n , (3.3)

q i (c) + i ∈V (i) h i ,i (c) -h i,i (c) - h 2 i,i (c) + h 2 i ,i (c) 2 r i,i ≥ d i . (SD)
We point out that for an optimal allocation (see §4) , h i,i h i ,i = 0. The principal decision is a triple (q, x, h) ∈ (Q, X , H). This decision is made under the constraints (IC), (PC) and (SD). Since we assume that the principal is risk neutral, his goal is to minimize his average cost, i.e. mathematically his criterion is equal to the average of the sum of the payments. Finally the optimal mechanism is the solution of Problem 1.

minimize (q,x,h)∈(Q,X ,H) i∈I Ex i (c) subject to ∀c ∈ C n , ∀i ∈ I : q i (c) + i ∈V (i) h i ,i (c) -h i,i (c) - h 2 i,i (c) + h 2 i ,i (c) 2 r i,i ≥ d i (SD) ∀c ∈ C n , ∀(i, i ) ∈ E : h i,i (c) ≥ 0 ∀i ∈ I, ∀(c i , c i ) ∈ C 2 i : U i (c i , c i ) ≥ U i (c i , c i ) (IC) ∀i ∈ I, ∀c i ∈ C i : U i (c i , c i ) ≥ 0 (P C).
We now proceed to solve the optimal mechanism design problem, which is a functional optimization problem with an infinity of constraints, some of which are expressed with integrals. The essential observation is that this complicated problem is equivalent to a much simpler one. The proof relies on the comparison with two intermediate problems:

Problem 2. minimize (q,x,h)∈(Q,X ,H) i∈I Ex i (c) subject to. ∀c ∈ C n , ∀i ∈ I : q i (c) + i ∈V (i) h i ,i (c) -h i,i (c) - h 2 i,i (c) + h 2 i ,i (c) 2 r i,i ≥ d i (SD) ∀c ∈ C n , ∀(i, i ) ∈ E : h i,i (c) ≥ 0 ∀i ∈ I, ∀j ∈ J, (c -j , t 1 , t 2 ), (c 1 , . . . , t k , . . . , c N ) ∈ C i , : V i (c 1 , .., c j-1 , t 1 , c j+1 .., c N ) -V i (c 1 , .., c j-1 , t 2 , c j+1 .., c N ) = t2 t1 Q j i (c 1 , .., c j-1 , s, c j+1 .., c N )ds (H1) ∀i ∈ I, ∀(c, c ) ∈ c 2 : (c -c ).(Q i (c) -Q i (c )) ≤ 0, (H2) ∀i ∈ I, ∀c i ∈ C i : V i (c i ) ≥ 0 (P C),
and Problem 3.

minimize (q,h)∈(Q,H) E i∈I j∈J q j i (c)(c j i + K j i (c j i )) subject to ∀(c, i) ∈ C n × I : q i (c) + i ∈V (i) h i ,i (c) -h i,i (c) - h 2 i,i (c) + h 2 i ,i (c) 2 r i,i ≥ d i (SD) ∀c ∈ C n , ∀(i, i ) ∈ E : h i,i (c) ≥ 0. ∀c ∈ C i , ∀i ∈ I : x i (c) = j∈J q j i (c)c j i + c j+ i c j i q j i (c 1 i . . . c j-1 i , t, c (j+1)+ 1 . . . c N + i ; c -i )dt.
The inequality on the scalar product in (H2) is the piecewise linear equivalent of a monotonicity condition already encountered in [START_REF] Figueroa | Cost-minimizing regulations for a wholesale electricity market[END_REF]. The first two problems are very similar, but (IC) has been replaced by (H1) and (H2) and (PC) is expressed in terms of V instead of U . This replacement is a trick introduced by Myerson in his 1981 paper. We will show later on how we can compare Problems 2 and 3, but note that Problem 3 is really simpler, as the optimization part can be solved pointwise (and x can be deduced from this pointwise optimization). The main result of this paper is that the three problems have the same solution.

3.1. Necessary conditions for Problem 1. We derive some necessary conditions for a solution of Problem 1. In fact, we only use constraint (IC) to deduce the two next results. The first lemma indicates that any solution of the first problem should be such that Q is monotonous. This is a classic result already introduced for instance in [START_REF] Roger B Myerson | Optimal auction design[END_REF] and [START_REF] Figueroa | Cost-minimizing regulations for a wholesale electricity market[END_REF]. The novelty here is that in the context of piecewise linear production cost functions, this monotonicity result is expressed in a vectorial sense.

Lemma 3.2 (Q monotonicity). If (q, x, h) is admissible for Problem 1, then for all agent i ∈ I and all

(c i , c i ) ∈ C 2 i (3.4) (c i -c i ).(Q i (c i ) -Q i (c i )) ≤ 0
where . is the scalar product in R N .

Mechanism design and allocation algorithms for network markets

Proof. We omit the i in the proof, as it plays no role. First, let (c, c ) ∈ C 2 i by the (IC) constraint,

(3.5) U (c, c) ≥ U (c, c ) and U (c , c ) ≥ U (c , c)
i.e.

(3.6)

X(c) - j∈J c j Q j (c) ≥ X(c ) - j∈J c j Q j (c ) X(c ) - j∈J c j Q j (c ) ≥ X(c) - j∈J c j Q j (c).
We get the lemma after summation of the two inequalities and simplification. Lemma 3.2 indicates that an agent should be producing less on average in her ith working zone if she is biding a higher marginal cost for this working zone.

Lemma 3.3. If (q, x, h) is admissible for Problem 1 then for any agent (omitting i) for any c, t 1 and t 2 (3.7)

V (c 1 , . . . , c j-1 , t 1 , c j+1 , . . . , c N ) =V (c 1 , . . . , c j-1 , t 2 , c j+1 , . . . , c N ) - t1 t2 Q j (c 1 , . . . , c j-1 , s, c j+1 , . . . , c N )ds Proof. The inequality U (c, c) ≤ U (c, c ) implies that c → U (c, c ) is maximal at c for any c ∈ C i . Moreover, (3.8) t → U ((c 1 , .., c j-1 , t, c j+1 .., c N ), c) = X(c) - k∈J\{j} c k Q k (c) -tQ j (c)
is absolutely continuous, differentiable with respect to t for all c, and its derivative is -Q j (c). By definition of q j , Q j ≤ q. So applying the envelope theorem we get the result.

Necessary conditions for Problem 2.

We derive some necessary conditions for a solution of Problem 2.

Lemma 3.4. If (q, x, h) is an optimal solution of Problem 2 then (omitting i) for all c ∈ C i (3.9)

V (c) = j∈J c j+ c j Q j (c 1 . . . c j-1 , t, c (j+1)+ , . . . , c N + )dt.
Proof. According to (H1)

j∈J c j+ cj Q j (c 1 . . . c j-1 , t, c (j+1)+ , . . . , c N + )dt = j∈J V (c 1 , .., c j-1 , c j , c (j+1)+ , . . . , c N + ) -V (c 1 , .., c j-1 , c (j)+ , . . . , c N + ) = V (c) -V (c 1+ , . . . , c N + ).
This is an expression for V (c) as a sum of a positive function of c and a constant V (c 1+ , . . . , c N + ). It is clear that to optimize the criteria, this constant should be as small as possible. The participation contraint (PC) imposes that V (c 1+ , . . . , c N + ) ≥ 0, therefore V (c 1+ , . . . , c N + ) = 0. A consequence of this is: Corollary 3.5. If (q, x, h) is an optimal solution of Problem 2 then for all i ∈ I,

(3.10) V i (c 1+ i , . . . , c N + i ) = 0.
Proof. See the proof of Lemma 3.4. Corollary 3.5 means that if an agent bids a production cost functions that is the maximum of what he could bid, he should not make any profit, and so he should be paid exactly his production cost. We see with this lemma that if the public information is inaccurate and the real cost of an agent is higher than what could be expected, then there is a risk that the participation constraint is not satisfied. On the other hand, it should not be surprising that an agent can have a zero profit: remember that in the extreme case in which the principal knows everything (discussed in §2), the agents do not make any profit.

Another consequence of lemma 3.4 is Lemma 3.6. If (q, x, h) is an optimal solution of Problem 2, the expected profit of agent i (over his type) is

(3.11) EV i (c) = j∈J (c1..cn)∈Ci Q j i (c 1 , . . . , c j , c (j+1)+ , . . . c N + )K j i (c)f i (c)dc.
Proof. By Lemma 3.4 and Fubini's lemma, EV i (c) is equal to

E j∈J c j+ c j Q j i (c 1 , . . . , c j-1 , t, c (j+1)+ , . . . c N + )dt = j∈J c -j ∈C -j c j+ c j =c j- c j+ t=c j Q j i (c 1 , . . . , c j-1 , t, c (j+1)+ i , . . . c N + i )f i (c)dtdc j dc -j .
Our task is now to compute the inner term. Applying again Fubini's lemma, this term is equal to

c j+ c j =c j- c j+ t=c j Q j i (c 1 , . . . , c j-1 , t, c (j+1)+ , . . . c N + )f i (c)dtdc j = c j+ t=c j- t c j =c j- Q j i (c 1 , . . . , c j-1 , t, c (j+1)+ , . . . c N + )f i (c)dc j dt = c j+ t=c j- Q j i (c 1 , . . . , c j-1 , t, c (j+1)+ , . . . c N + )( t c j =c j- f i (c)dc j )dt = c j+ t=c j- Q j i (c 1 , . . . , c j-1 , t, c (j+1)+ , . . . c N + )( t c j =c j- f i (c) f i (c -j , t) dc j )f i (c -j , t)dt = c j+ t=c j- Q j i (c 1 , . . . , c j-1 , t, c (j+1)+ , . . . c N + )K j i (t)f i (c -j , t)dt = c j+ c j =c j- Q j i (c 1 , . . . , c j-1 , c j , c (j+1)+ , . . . c N + )K j i (c j )f i (c i )dc j
We get the lemma by summing all the inner terms. Lemma 3.7. If (H1) is satisfied, then for any (a, b) ∈ C 2 i (omitting i)

(3.12) X(a) -X(b) = j∈J [a j Q j (a) -b j Q j (b) + b j a j Q j (b 1 . . . b j-1 , t, a j+1 . . . a N )dt]
Proof. Because of its length the proof is detailled in Appendix A Lemma 3.8. If (q, x, h) verifies (H1) and (H2) and

Q j i is independent of c j i for j > j, then for all (c, c) ∈ C 2 (3.13) U (c, c) ≥ U (c, c).
Proof. Since (H1) is satisfied, equation (3.12) of Lemma 3.7 applies. We combine this relation with the definition of the expected profit U from (2.5). We obtain:

U (c, c) -U (c, c) = j∈J c j Q j (c) -cj Q j (c)+ cj c j Q j (c 1 , ..., cj-1 , t, c j+1 , ...c N )dt + c j Q j (c) -c j Q j (c) = j∈J (c j -cj )Q j (c 1 , ..., cj-1 , cj )) + cj c j Q j (c 1 , ..., cj-1 , t)dt = j∈J cj c j Q j (c 1 , ..., cj-1 , t) -Q j (c 1 , ..., cj-1 , cj )dt,
where we used the independence hypothesis for the second equality. By (H2), which implies the decreasingness of Q j with respect to c j i when all other quantities are fixed, if c j < cj then for any t ∈ [c j , cj ], Q j (t) -Q j (c j ) ≥ 0. Otherwise, we use the formula ,c) is non negative.

t ∈ [c j , c j ] verifies Q j (t) -Q j (c j ) ≤ 0. So U (c, c) -U (c

Necessary conditions for Problem 3.

We derive some properties for Problem 3.

Lemma 3.9. There is an optimal solution (q, x, h) for Problem 3 such that q j i (and

Q j i ) is independent of c k i for k = j. Proof.
First note that x is not taking any role in the optimization problem: it is defined afterward. The only real optimization variables are then q and h. Remember that q j i is defined as a function of q by q j i = min((q i -(j -1)q) + , q). The constraints are defined for each c ∈ C n and the integral criterion is in fact a sum of independent criteria depending on q(c) for c ∈ C n . Therefore we can solve Problem 3 with a pointwise optimization. By the discernability assumption, for any c ∈ C n and i ∈ I,

c j i + K j i (c j i ) is increasing in j. So for all c ∈ C n , i ∈ I, j∈J q j i (c)(c j i + K j i (c j i )
) is a convex criteria in q i and so the pointwise problem corresponds to Problem 4 of §4. In particular, we can apply Lemma 4.3 from the next section. So q j i only depends on c j i and c -i . This property is preserved by integration over the c -i : Q j i only depends on c j i .

We point out that, since the pointwise problem has a unique solution, the pointwise optimal solution introduced in the proof is uniquely defined. Theorem 3.10. If (q, x, h) is the pointwise optimal solution of Problem 3 and

K j i is smooth in c j i for (i, j) ∈ I × J and c ∈ C i , then for all i ∈ I, Q i is C ∞ over C i .
Proof. We will use some results and notations from 4.2. Remember that c j i → c j i + K j i (c j i ) is increasing, so by composition with smooth bijection, we can do the reasoning as if the costs involved were c j i instead of c j i + K j i (c j i ). First according to Lemma 4.4, q i is continuous. Since q i is bounded, we can apply the dominated convergence theorem to show that Q i is continuous. Then we proceed by mathematical induction. Assume that

Q i is C l , then take c 0 i ∈ C i and c k i a sequence in C i that converges to c 0 i . Since Ŝ = ∪ k∈N S(c k i
) is a countable union of null measured set (by Lemma B.5), its measure is zero. So without changing the results, we can compute the integrals on C -i \ Ŝ instead of C -i . Since q i and its derivatives are bounded, we can apply the dominated convergence theorem to compute the limit of

Q (l) i (c 0 i )-Q (l) i (c k i ) c 0 i -c k i
as k goes to +∞ as the integral of a limit. Since we removed the point over which this limit was not defined, we get that

Q (l) i (c 0 i )-Q (l) i (c k i ) c 0 i -c k i
has a limit, and this limit does not depend on the sequence c k i . So Q i is l + 1 times derivable at c i , for all c i . We conclude by induction.

3.4. Resolution of the mechanism design problem. Last but not least, we state the main result of the Section. Theorem 3.11. Let (q j i , h) be defined such that for any c ∈ C n , (q j i (c j i , c -i ), h(c)) solves minimize q j i ,x,h i∈I j∈J

q j i (c j i , c -i )(c j i + K j i (c j i ))
subject to

0 ≤ q j i ≤ q j∈J q i i (c j i , c -i ) + i ∈V (i) h i ,i (c) -h i,i (c) - h 2 i,i (c) + h 2 i ,i (c) 2 r i,i ≥ d i h i,i (c) ≥ 0,
and set

(3.14) q i (c) = j∈J q j i (c j i , c -i ) and x i (c) = j∈J q j i (c j i , c -i )c j i + c j+ i c j i q j i (t, c -i )dt,
then (q, h, x) solves the optimal mechanism design problem (Problem 1).

Proof.

• First note that (q, h, x) is the pointwise solution of Problem 3 so it is optimal for Problem 3, moreover, by construction (q, h, x) satisfies (SD) and h ≥ 0. • Then note that by Lemma 3.6, (q, h, x) solves a relaxation of Problem 2, but is it admissible for Problem 2 ?

• By definition of V (omitting i),

V (c 1 . . . a j . . . c N ) -V (c 1 . . . b j . . . c N ) = Ex(c 1 . . . a j . . . c N ) -x(c 1 . . . a j . . . c N ) -[Q j (a j )a j -Q j (b j )b j ] = Eq j i (a j , c -i )a j + c j+ i a j q j i (t, c -i )dt -Eq j i (b j , c -i )b j - c j+ i b j q j i (t, c -i )dt -[Q j (a j )a j -Q j (b j )b j ] = E b j a j q j i (t, c -i )dt = b j a j Q j i (t)dt
where we used the definition of x, the definition of Q and Fubini lemma's for the second, third and fourth equalities. So (q, h, x) satisfies (H1). • By construction, q j i is non-increasing in c j i + K j i (c j i ) then using the third assumption, q j i is non-increasing in c j i so for any (a, b,

c -i ) ∈ C 2 × C -i , (a j i -b j i )(q j i (a j i , c -i ) -q j i (b j i , c -i )) ≤ 0, so by integration with respect to c -i , (a j i -b j i )(Q j i (a j i ) -Q j i (b j i ) ≤ 0 and then by summation over j, (c -c ).(Q i (c) - Q i (c )) ≤ 0, i.e. (H2) is satisfied. • Since (H1) is satisfied, V i (c i ) ≥ V i (c + i ).
Moreover, V i (c + i ) = 0 by construction of x. So the participation constraint (PC) is satisfied.

• Therefore (q, h, x) is admissible for Problem 2. So it solves Problem 2.

• Since (q, h, x) solves Problem 2, by Lemma 3.8 the incentive compatibility constraint (IC) is satisfied. Moreover, by Lemma 3.4, (PC) is satisfied. So (q, h, x) is admissible for Problem 1, but is it optimal ? • By Lemmas 3.2 and 3.3, any optimal solution of Problem 1 should be admissible for Problem 2. Since the criteria are the same, we conclude that (q, h, x) is an optimal solution of Problem 1.

3.5. Comments. In the optimal mechanism, the agents are paid at a marginal price that is equal to their bid augmented by an information rent. This information rent depends on the problem structure by the fact that it is built from a collection of allocation problems, and it depends on the available information by the fact that, in these optimization problems, the marginal prices are replaced by the virtual marginal prices c j i + K j i (c j i ). We point out that, as already noted for instance in [START_REF] José | On the planners loss due to lack of information in bayesian mechanism design[END_REF], the computation of such rent may pose a practical difficulty for large problems.

Notice that, by construction, the optimal mechanism is incentive compatible no matter K as (H1) is verified anyway as long as the hypothesis are satisfied. If this market is repeated over time, the principal can dynamically enhance his probabilities.

The model extends to the more realistic case when some nodes do not have a producer and for some others, the demand is null. In particular, we can consider the buyer/suppliers setting where there is demand only at one node.

One may argue that one limit of the current result is that it does not take into account any network constraints. Nonetheless, the structure of the proof makes it clear that we exploited only some properties of the allocation problem. Therefore, the optimal mechanism construction is valid for any market for which the allocation problem satisfies these properties. We discuss more on this point in §3. [START_REF] Aussel | Electricity spot market with transmission losses[END_REF].

In addition, the optimal mechanism construction is valid for limiting case with r = 0 at some edges. In this case, one needs to specify the definition of q of as the solution of the allocation problem may not be a singleton. If all the agents are identical and r = 0 for all edges, this corresponds to a second best auction.

We have not tried any ironing techniques to get rid of the monotone likelihood ratio assumption ; this is probably something to look at.

3.6. Generalization. The study of this subsection could be postponed to a second reading. We extend Theorem 3.11 to a more general network market. In this subsection we use specific notations. The letter e is used generically to refer to a line. The network flow is now subject to a constraint of the form N (h) ∈ R m -, where N (h) is a convex and smooth function from R E to R m , where m ∈ N. We call this constraint the network constraint. To model the piecewise linear prices, we use positive variables q j i ≤ qj i . Thus, the working zones are not assumed to be of equal sizes anymore. The marginal rates c j i are assumed to be increasing in j. The criterion is still J(q) = i∈I j∈J q j i c j i . We write K 1 the set of decisions (q j i , h e ) such that N (h) ∈ R m -and 0 ≤ q j i ≤ qj i . We assume that K 1 is non-empty. The nodal constraints are replaced by constraints of the form (for all i ∈ I) j q j i + g i (h) ≥ 0 where the g i are smooth strictly concave functions from (R + ) E to R. We introduce the set K 2 = {(q j i , h e ) ∈ K 1 ; ∀i ∈ Ij q j i -g i (h) ≤ 0}. Then the allocation problem corresponds to the following optimization program:

(3.15) minimize (q j i ,h) J(q) subject to (q j i , h e ) ∈ K 2 .
It is clear that q j i is non-increasing in c j i . We point out that at optimality, the nodal constraint should be binding. Moreover, by the strict concavity of the g i the solution of problem (3.15) is unique.1 Note that J is smooth and its gradient at (c j i , h e ) is (c 1 1 , . . . c N 1 , . . . c N n , 0, . . . , 0), where the last |E| null coordinates correspond to the variable h. We denote by N K1 (q j i , h e ) and N K2 (q j i , h e ) the normal cones to K 1 and K 2 at (q j i , h e ). Applying Theorem 10 from [START_REF] Rockafellar | Fundamental of optimization[END_REF] (we can check that the constraint qualification is satisfied if q is not identically equal to zero), we can express N K2 (q j i , h e ) as (3.16)

{ i∈I λ i ∇f i (q j i , h e ) + z; (λ 1 , . . . , λ n ) ∈ (R + ) n , z ∈ N K1 (q j i , h e )}
where f i (q, h) =j q j i -g i (h). Applying Theorem 9 from [START_REF] Rockafellar | Fundamental of optimization[END_REF], the solution of (3.15) should satisfy (3.17) -∇J(q j i , h e ) ∈ N K2 (q j i , h e ). Observe that since the problem is convex and the solution unique, this is in fact a necessary and sufficient condition for the unique solution of the problem. The N first rows of this relation gives:

(3.18) (-c 1 1 , . . . , -c N 1 ) = λ 1 (-1, . . . , -1) + (z 1 , . . . , z N ). where λ 1 ≥ 0 and (3.19) z j      ≥ 0 if q j i = qj i ≤ 0 if q j i = 0 0 else
Note that if z j = 0 then c j i = λ 1 , and since the c j i are increasing in j, there is at most one j such that z j = 0. Moreover, by 3.18 for all j we have z j = λ 1 -c j 1 . So the z j are strictly decreasing in j. From the product structure of K 1 we deduce the product structure of its normal cone. We can then write with obvious notations: N K1 (q, h) = N K1 (q) × N K1 (h) From the rows corresponding to h in the first order condition we derive the relation:

(3.20) i∈I λ i ∇g i (h) ∈ N K1 (h).
Lemma 3.12 is a generalization of Lemma 4.3.

Lemma 3.12. Let (q(c), h(c)) be a solution of Problem 3.15. Assume q i continuous with respect to c i , then for any i ∈ I, j ∈ J, q j i (c) does not depend on c l i for l = j.

Proof.

Take (c i , c -i ) ∈ C n . If q j i (c i , c -i ) ∈]0, qj i [, then λ i = c j i and c k i (k = j)
does not intervene the first order conditions (3.19) and (3.20), so that the solution does not depends on it. So without loss of generality we assume q j i (c i , c -i ) = 0 (the case q j i (c i , c -i ) = qj i could be treated in the same manner). By the continuity assumption we can restrict even more to the case where q j-1 i = qj-1 i and q j i (c i , c -i ) = 0. Then by the first order condition,

λ i ∈ [c j-1 i , c j i ].
Using the same the first order condition argument we used at the beginning of this proof, we see that the solution only depends on c j-1 i and c j i . If c j-1 i increases, then q i decrease so that q j i stays equal to zero. If c j-1 i decreases, then the first order condition λ i ∈ [c j-1 i , c j i ] stays true for the current λ i , the whole first order condition is still satisfied. Therefore the solution does not change. The lemma follows.

Notice that we can write q i as a strictly convex function of h q i = -g i (h), and then the cost associated with q i is the composition of an increasing convex function of R and a convex function from R |E| to R, therefore it is convex with respect to h, then we can rewrite the problem with only h as a decision variable, the problem would be defined on a convex set and with a strictly convex cost, and parametrized by c ∈ C. Then we can apply Berge maximum principle (see Theorem 9.17 in [START_REF] Rangarajan | A first course in optimization theory[END_REF]) in a convex setting to get the continuity of q. From Lemma 3.12 and the monotony of q, we conclude that we can extend Theorem 3.11 to a more general setting.

3.7.

Examples with log-concave functions. We point out that a sufficient condition to check the monotone likelihood ratio property is that F/f is increasing. If F is a smooth cumulative distribution function with f the corresponding smooth and positive density, then F/f is increasing iff f /F is decreasing iff ln F is decreasing iff ln F is concave. A function f is said to be log-concave if ln f is concave. Many density functions encountered in the economic and engineering literature are log-concave: the uniform, the normal, the exponential, the power function and the Laplace distribution have log-concave density function. We refer to [START_REF] Bagnoli | Log-concave probability and its applications[END_REF] for the results we use on this class of functions. The class of log-concave is stable by monotonic transformation and truncation. Moreover, it happens that if a probability density distribution is logconcave, then the corresponding cumulative distribution is log-concave. In mechanism design theory, it is standard to assume F to be log-concave [START_REF] Laffont | The dynamics of incentive contracts[END_REF].

We want to see the implication of the discernability assumption. This assumption imposes a gap ∆ equals to K j i (c j+ i ) between c j+ i and c

(j+1)i

. We compute this gap for some standard cases. To simplify the notations and the computation, we assume without loss of generality that c j-= 0 and write c j+ = c + . We get the following table :  Table 1: The gap ∆ for some standard probabilities

Name ∝ f (x) ∝ F (x) K(x) ∆ Uniform 1 x x c + Power Function λ( x c + ) λ-1 c + ( x c + ) λ x λ c + λ Weibull λ( x c + ) λ-1 e (-x c + ) λ c + (1 -e -( x c + ) λ ) c + λ ( c + x ) λ-1 (e ( x c + ) λ -1) c + e-1 λ Laplace 1 2 e -λ|x-c + 2 | x > c + 2 , 2-e -λ c + 2 e -λ(x-c + 2 ) 2λ 2 λ (e c + 2 λ -1) Exponential (reversed) λe -(c + -x)λ
e -c + λ (e xλ -1)

1-e -xλ λ

1-e -c + λ λ

We truncate the probabilities so that they have support in [0, c + ]. The symbole ∝ means that we express f and F modulo the multiplication by a common constant (due to the truncation) and λ is a positive parameter that should be greater than 1 for the Power function and the Weibull probability. For the uniform distribution, we see that the interval should be of non-decreasing sizes. For instance, one could take

c 1 ∈ [c, 2c], c 2 ∈ [3c, 4c], c 3 ∈ [5c,
6c], etc. For the Power function, the Weibull function and the exponential, we see that the gap could be made smaller. We do not address in this work the question of the practical implementation of an optimal mechanism. The discernability assumption raises an additional practical issue.

Study of the allocation problem.

4.1. The standard auction problem. The previous section motivates the study of the allocation problem for different reasons. First, as we have seen in the proofs, the results of §3 rely on some properties of the solution of the standard allocation problem. In addition to those properties, we derive in this section two algorithms to compute the solution of the standard allocation problem. According to 3.11, those algorithms can be used for both the original auction problem and the optimal mechanism design. To benchmark the mechanism design equilibrium against an equilibrium of the Bayesian game related to the standard auction, numerical efficiency is pivotal: indeed the Bayesian equilibrium requires a lot of allocations computations.

Let us first introduce the standard allocation problem. In a standard mechanism, the principal solves an allocation problem based on the bids he receives. Those bids will be denoted by c j i , where as before i ∈ I corresponds to the ith agent and j ∈ J corresponds to the jth working zone with constant marginal price. To model the fact that the production costs are piecewise linear, we use some positive variables q j i so that q j i ≤ q, for any i ∈ I, the quantity produced by agent i is q i = j∈J q j i and the related production cost is j∈J c j i q j i . As before, an allocation should satisfy the constraint that production exceeds demand. We end up with Problem 4: Problem 4.

(4.1) minimize (q,h) i∈I j∈J

q j i c j i subject to ∀i ∈ I : j∈J q j i + i ∈V (i) h i ,i -h i,i - h 2 i,i + h 2 i ,i 2 r i,i ≥ d i (λ i ) ∀(i, i ) ∈ E : h i,i ≥ 0 (γ i,i ) ∀(i, j) ∈ I × J : q j i ≥ 0 (µ i,j ) ∀(i, j) ∈ I × J : q j i ≤ q (ν i,j ).
The notations for the dual the variables associated with each constraint are indicated in parentheses. Those variables are in R + .

For any node i ∈ I, we define the function

F i for λ ∈ [min i c 1 i , max i c N i ] n (4.2) F i (λ i , λ -i ) = d i + i ∈V (i) λ i -λ i r i,i (λ i + λ i ) + (λ i -λ i ) 2 2r i,i (λ i + λ i ) 2 .
We will justify later that this function could be interpreted as the production of agent i when the multipliers are λ i and λ -i . Its partial derivative with respect to λ i is

(4.3) ∂ λi F i (λ i , λ -i ) = - i ∈V (i) 4 r i,i λ 2 i (λ i + λ i ) 3 < 0.
The derivative is negative: when i increases its price it is assigned smaller production quantities. The partial derivative of

F i for i ∈ I\{i} is (4.4) ∂ λ i F i (λ i , λ -i ) = 4 r i,i λ i λi (λi+λ i ) 3 > 0 if i ∈ V (i) 0 else.
When another agent becomes less competitive, i is assigned more production. Let k ∈ J ∪ {0}. The limit at +∞ and 0 of

F i (x, λ -i ) -k q are (4.5) lim x→+∞ F i (x, λ -i ) -k q = d i -k q - j∈V (i) 1 2r i,j and (4.6) lim x→+∞ F i (x, λ -i ) -k q = d i -k q + j∈V (i) 3 2r i,j
.

Using the hypotheses (2.11), the first term is strictly negative and the second strictly positive, so by the intermediate value theorem, F i -k q has a zero. Since F i -k q is decreasing in λ i , this solution is unique. Now we define for i ∈ I and k ∈ J ∪ {0}, g k i as the function that associates any λ -i ∈ [min i c 1 i , max i c N i ] n-1 with the unique x such that and F i (x, λ -i ) = k q and x > 0:

(4.7) F i (g k i (λ -i ), λ -i ) = k q g k i (λ -i ) > 0. Lemma 4.1. For any i ∈ I, k ∈ J ∪{0}, λ -i ∈ [min i c 1 i , max i c N i ] n-1 and i ∈ V (i) (4.8) ∂ λ i g k i (λ -i ) > 0.
In particular, g k i is increasing in λ i for i ∈ V (i). Proof. According to the implicit function theorem (4.9)

∂g k i (λ -i ) ∂λ i = - ∂F i ∂λ i / ∂F i ∂λ i , It is clear that g k i (λ -i ) is decreasing in k.
We proceed with the computation of the dual of Problem 4. If a strong duality theorem applies, then we should have min q,h max λ,γ,ν,µ i∈I,j∈J

q j i c j i + i∈I λ i {d i -( j∈J q j i + i ∈V (i) h i ,i -h i,i - h 2 i,i + h 2 i ,i 2 r i,i )} - i∈I,j∈J γ i,j h i,j + i∈I,j∈J ν i,j (q j i -q) -µ i,j q j i = max λ,γ,νµ min q,h i∈I λ i d i - i∈I,j∈J ν i,j q + q j i (c j i + ν i,j -λ i -µ i,j ) + (i,i )∈E h i,i {λ i -λ i -γ i,j } + h 2 i,i r i,i λ i + λ i 2 ,
so that for any (i, i ) ∈ E, by necessary and sufficient first order condition

h i,i = γ i,i + λ i -λ i r i,i (λ i + λ i ) . (4.10)
By replacing h by its expression in the dual variables we get something equivalent to

(4.11) maximize (λ,γ,µ,ν) i∈I {λ i d i - j∈J ν i,k q - i ∈V (i) (λ i -λ i -γ i,j ) 2 2r i,i (λ i + λ i ) } subject to ∀(i, j) ∈ I × J c j i + ν i,j ≥ λ i + µ i,j .
The expression of γ with respect to λ follows. For any (i, i ) ∈ E (4.12)

γ i,i = 0 if λ i ≤ λ i λ i -λ i else so the dual problem is equivalent to (4.13) maximize (λ,µ,ν) i∈I {λ i d i - j∈J ν i,j q - i ∈V (i) (λ i -λ i ) 2 4r i,i (λ i + λ i ) } subject to ∀(i, j) ∈ I × J c j i + ν i,j ≥ λ i + µ i,j
, because µ does not play any role in the admissibility of the other variables nor in the objective, this is equivalent to

(4.14) maximize (λ,ν) i∈I {λ i d i - j∈J ν i,j q - i ∈V (i) (λ i -λ i ) 2 4r i,i (λ i + λ i ) } subject to ∀(i, j) ∈ I × J c j i + ν i,j ≥ λ i ,
The expression of ν follows. For any (i, j) ∈ I × J (4.15)

ν i,j = 0 if λ i ≤ c j i λ i -c j i else.
So we can a posteriori justify that we have strong duality: the operator is continuous, convex-concave and the dual variables are restricted to be in a bounded set. So the dual of the allocation problem writes:

(4.16) maximize λ≥0 i∈I {λ i d i -q j∈J (λ i -c j i )δ λi≥c j i - i ∈V (i) (λ i -λ i ) 2 4r i,i (λ i + λ i ) },
where (4.17)

δ x≥y = 1 if x ≥ y 0 else.
For i ∈ I we maximize the criteria

(4.18) λ i d i -q j∈J (λ i -c j i )δ λi≥c j i - i ∈V (i) (λ i -λ i ) 2 4r i,i (λ i + λ i ) ,
which is strictly concave for any λ -i (sum of concave and strictly concave functions). We denote by Λ i (λ -i ) its maximizer. The first order necessary and sufficient condition on Λ i is:

(4.19) 0 ∈ F i (Λ i , λ -i ) -K i (Λ i ),
where (4.20)

K i (λ i ) =          0 if λ i < c 1 i [j -1, j]q if λ i = c j i j q if λ i ∈]c j i , c j+1 i [, j = N N q if λ i ∈ λ i ∈]c N i , c[,
We conclude Lemma 4.2. For any i ∈ I and any

λ -i ∈ [min i c 1 i , max i c N i ] n-1 , Λ i (λ -i ) is the unique solution of F i (Λ i , λ -i ) ∈ K i (Λ i ). (4.21)
We point out that the primal (and dual) solution unicity is a desirable property that is not systematic for the allocation problems of centralized market models. The expression of h with respect to λ (4.10) and the fact the supply constraint should be binding at optimality justify the interpretation of F i proposed at the beginning of this subsection. In the following we use this property many times. 4.2. Some properties of the solution. If r and d are set, we can see the solution of Problem 4 as a function of the vector c ∈ C n . We denote by q(c) the solution of Problem 4 with the cost vector c. Similarly, we define q i (c), q j i (c), λ(c) and λ i (c). We give here two properties of the allocation problem solution. By integration, we showed in the previous section that the solution of the mechanism design inherits those properties.

Lemma 4.3. Let (q(c), h(c)) be a solution of Problem 4, then q j i (c) does not depend on c l i for l = j:

(4.22) q j i (c 1 , . . . c j-1 , c j , c j+1 . . . , c N ; c -i ) = q j i (s 1 , . . . s j-1 , c j , s j+1 . . . , s N ; c -i ) Proof. Let i ∈ I, j ∈ J, c -i ∈ C n-1 , c = (c 1 , .
. . , c N ) ∈ C and s = (s 1 , . . . , s N ) ∈ C such that s j = c j . We shall prove that q j i (s, c -i ) = q j i (c, c -i ). We denote by λ c (resp. λ s ) the dual variables associated with the nodal contraints for the allocation problem parametrized with c (resp. s). First if (4.23) q j i (c, c -i ) ∈]0, q[, then by lemma 4.2 λ c i = c j i and so using Lemma 4.2 again, λ s i = c j i . Therefore λ s = λ c , from which we deduce that q j i (c, c -i ) = q j i (s, c -i ). So without loss of generality, we can assume that (4.24) q j i (c, c -i ) = q and q j i (s, c -i ) = 0.

Then using Lemma 4.2 we get (4.25)

λ c i ≥ c k and λ s i ≤ c k , so that λ c i ≥ λ s i . If λ c i > λ s i , then λ c -i ≥ λ s -i by non-decreasingness of Λ i , i ∈ I\{i} (explained in §4.
3) Therefore all the other agents are producing less, which is absurd since i is already producing less.

We extend the notations by setting for all i ∈ I, c 0 i = c * . We consider the subset S of C for which at some nodes i, the multiplicator λ i is equal to the marginal cost and the production is a multiple of q (i.e. stuck in an angle): (4.26) S = {c ∈ C n , q i (c) = j q and λ i (c) = c j i for some i ∈ I, j ∈ J ∪ {0}, j ∈ {j, j + 1}}.

The set S corresponds to the points of transition between the two possibilities defined by the first order condition (4.19). Because of the angle, it is natural to think that this is where irregularities may happen (see the proof of the next lemma). We introduce this set to show some regularity properties of q and Q. We detail the proof in the Appendix. The approach consists in showing that S is a finit union of sets of zero measure. This is also true for the projection of S on the {c i } × C -i . Then we observe that on C\S, the relations between the primal and dual variables are smooth. Lemma 4.4. The function q is C ∞ on C n \S and C 0 on C n . Proof. We postpone the proof to Appendix B 4.3. Fixed point. In this subsection we show that the solution of the dual problem is the unique fixed point of a monotone operator. We define

(4.27) Λ(λ 1 , ..., λ n ) = (Λ 1 (λ -1 ), ..., Λ n (λ -n )).
Lemma 4.5. For any i ∈ I, Λ i is non-decreasing. Proof. Let λ -i < λ -i and the corresponding Λ i and Λ i . Assume Λ i > Λ i . Since F i is decreasing in the first variable and increasing in the second (4.28)

F i (Λ i , λ -i ) < F i (Λ i , λ -i )
Moreover for any x ∈ K(Λ i ) and y ∈ K(Λ i ), x ≤ y and

F i (Λ i , λ -i ) ∈ K(Λ i ), F i (Λ i , λ -i ) ∈ K(Λ i ). Therefore F i (Λ i , λ -i ) ≤ F i (Λ i , λ -i
) which is absurd. We will use the following classical result (see [START_REF] Donald | Supermodularity and complementarity[END_REF] for a proof and definition of complete lattice). Theorem 4.6 (Knaster-Tarski fixed point). Let L be a complete lattice and let f an application from L to L and order preserving. Then the set of fixed points of f in L is a complete lattice.

In particular, the set of fixed points is non empty. Since Λ is order preserving and [c * , c * ] n is a lattice when we consider the natural order, there is a fixed point, and the set of fixed points is a lattice.

Lemma 4.7. λ is optimal for the dual ⇔ λ is a fixed point of Λ.

Proof.

• If λ is optimal for the dual, then each component i maximizes the criteria (4.18), so λ is a fixed point of Λ. • If λ is a fixed point of Λ, then by definition, each component i maximizes the criteria (4.18). So since the problem is (strictly) concave, λ is optimal.

A consequence of the previous lemma is that Lemma 4.8. The set of fixed points of Λ is a singleton. Definition 4.9 (Continuous for monotone sequence). We consider the natural partial order on R n . We say that a function G is continuous for monotone (resp. increasing, decreasing) sequences if for any monotone (resp. increasing, decreasing) sequence x n converging to a point x in the domain of G, G(x n ) goes to G(x) as n goes to infinity.

Obviously, a function is continuous for monotone sequences if and only if it is continuous for increasing and decreasing sequences.

Lemma 4.10. The operator Λ is continuous for monotone sequences.

The intuition of the proof is that we can use the monotony of the sequence and Lemma 4.2 to characterize the behaviour of Λ on the neighborhood. We find that Λ is either constant or characterized by the implicit function theorem.

Proof. Let λ-i , j ∈ [1 . . . N ], we first deal with the 'nice' case, that corresponds to

F i (Λ( λ-i ), λ-i ) ∈]j -1, j[q • If Λ i ( λ-i ) ∈]c j i , c j+1 i
[ (we do not treat the case j = N , which is very similar to what follows) then since F i is C ∞ and of invertible derivative (non zero) in λ i , the implicit function theorem tells us that the solution ψ of F i (ψ( λ-i ), λ-i ) = j q is continous in a neighborhood B of λ-i . So we can take B small enough so that for λ -i ∈ B, ψ(λ -i ) ∈]c j i , c j+1 i [. On this neighborhood, ψ satisfies the first order conditions and so by unicity of the solution of the optimization problem, since those conditions are sufficient, ψ = Λ i on B. So Λ i is continous at λ-i .

• If Λ i ( λ-i ) = c j i (as before, we do not treat the case j = N ), then by Lemma 4.2

F i (Λ i ( λ-i ), λ-i ) = [j -1, j]q, if F i ∈]j -1, j[q (we
deal with the border case in the next point) then since F i is continuous, there is a neighborhood B of λ-i such that F i (Λ i ( λ-i ), λ -i ) ∈]j -1, j[q, so on B Λ i is constant so continuous.

• We proceed with the borders. If F i (Λ i ( λ-i ), λ-i ) = (j -1)q and Λ i ( λ-i ) = c j i . -Decreasing case: Let us take ∈ R n-1 + such that F i (Λ i ( λ-i ), λ-i + ) ∈ [j -1, j]q (F i is continuous and increasing in λ -i ). Then Λ i ( λ-i + ) = Λ i ( λ-i ) checks the first order condition so Λ is constant, so we get the continuity for decreasing sequences. -Increasing case: F i (Λ i ( λ-i ), λ-i ) = (j -1)q and so there exists a ball B such that the implicit function theorem applies and there exists ψ such that F i (ψ( λ-i -), λ-i -) = (j -1)q and ψ( λ-i ) = Λ i ( λ-i ) = c j i (remember that Λ i ( λ-i ) = c j i by hypothesis) . Since F i is increasing in the second variable and decreasing in the first, ψ is increasing. For of positive components and sufficiently small, ψ( λ-i -) ∈]c j-1 i , c j i [ (since ψ( λ-i ) = Λ i ( λ-i ) = c j i ) and so check the first order condition. So for of positive components and sufficiently small, ψ = Λ i by uniqueness of the solution. So Λ i is continuous for increasing sequence.

• We do the same analysis if F i (Λ i ( λ-i ), λ-i ) = j q and Λ i ( λ-i ) = c j i . The conclusion follows.

We could have alternatively used Berge Maximum theorem for strictly concave criterion to get the continuity of Λ. Yet, we choose to present this proof for pedagogical reasons since it contains some key ideas we will use later (see appendix).

Theorem 4.11. The sequence (Λ k (c N 1 ...c N n )) k∈N converges to the solution of the dual.

Proof.

Since Λ(c N 1 ...c N n ) ≤ (c N 1 ...c N n )
, and since Λ is order preserving, the sequence Λ k (c N 1 ...c N n ) = λ k is non increasing and bounded, so converge to a point x. Since Λ is continuous for monotone sequence, x is a fixed point.

Theorem 4.12. For any i ∈ I, λ -i ∈ [c * , c * ] n-1 , Λ i (λ -i ) has the following explicite expression:

(4.29) Λ i (λ -i ) = min{c N i , min j∈J {c j i 1 Fi(c j i ,λ-i)<j q }, min k∈[0..N -1] {g k i (λ -i )1 g k i (λ-i)∈[c k i ,c k+1 i ] }}
Proof. We denote by G i the RHS of (4.29) and show that for any i

F i (G i (λ -i ), λ -i ) ∈ K(G(λ -i )), (4.30)
and then we conclude with a uniqueness argument.

If there is j ∈ J such that G i (λ -i ) = c j i , then either F i (c j i , λ -i ) < j q or g j i (λ -i ) = c j i . This last possibility implies by definition of g j i that F i (c j i , λ -i ) = j q. So anyway F i (c j i , λ -i ) ≤ j q. Remember that K(G(λ -i )) = [j -1, j]q. So we need to prove that F i (c j i , λ -i ) ≥ (j -1)q. Suppose the contrary, i.e. F i (c j i , λ -i ) < (j -1)q. Then since G i (λ -i ) = c j i , F (c j i , λ -i ) < (j -1)q, which in turn implies that (4.31)

g j i (λ -i ) < c j i . Now observe that since G i (λ -i ) = c j i , F (c j-1 i , λ -i ) > (j -1)q, which implies that (4.32) g j i (λ -i ) > c j-1 i .
Combining (4.31) and (4.32) with the definition of G, we see that G(λ -i ) ≤ g j i (λ -i ). But G(λ -i ) = c j i and g j i (λ -i ) < c j i , so this is absurd. Therefore F i (c j i , λ -i ) ≥ (j -1)q. Else let us assume that there is not such j. Then there is k ∈

[0 . . . N -1] such that G i (λ -i ) = g k i (λ -i ). By definition of g k i , F i (G i (λ -i ), λ -i )) = k q and by definition of G, G i (λ -i ) ∈ [c k i , c k+1 i ]. So again F i (G i (λ -i ), λ -i )) ∈ K(G i (λ -i ))
. We can now conclude that Λ = G.

We can interpret the fixed point algorithm as if some benevolent agents situated at each node of the network were exchanging information. They collectively try to minimize the total cost and, to do so, they communicate their current marginal costs. This marginal cost is the minimum of their local marginal cost and the marginal cost of importation from the adjacent nodes. At each iteration, the agents compute how much they are going to produce based on their current marginal cost. Then they update their marginal cost based on the information they just received and transmit this marginal cost to the adjacent nodes. We point out that the information used by each agent is local. 4.4. Decreasing Rate. We derive in this section an estimate for the decreasing rate. We denote α = max (e,e )∈E 2 r e /r e . We have the following bound: Lemma 4.13. For any

(i, i , k, λ -i ) ∈ E × [0, N ] × [c * , c * ] n-1 , (4.33) ∂ λi g k i (λ -i ) ≥ 1 N α ( c * c * ) 5 .
Proof. We combine (4.9) with (4.3) and (4.4). Lemma 4.14. Since (λ k i ) k∈N is non-increasing for all i ∈ I, there is a finite number of k for which at least one coordinate λ k i satisfies

(4.34) λ k i > c q i and λ k+1 i ≤ c q i or (4.35) λ k i = c q i and λ k+1 i < c q i . We denote by K this set. Let (k 1 , k 2 ) ∈ N 2 such that [k 1 -1, k 2 + 1] ∩ K = ∅. Then for k ∈ [k 1 , k 2 ] and i ∈ I such that λ k-1 i = λ k i λ k i -λ k+1 i ≥ 1 N α ( c * c * ) 5 max i ∈V (i) (λ k-1 i -λ k i ) (4.36) Proof. By definition of λ k , λ k i -λ k+1 i = Λ i (λ k-1 -i ) -Λ i (λ k -i ). By construction, there exists j ∈ [0, N -1] such that Λ i (λ k-1 -i ) = g j i (λ k-1 -i ) and Λ i (λ k -i ) = g j i (λ k -i ). Then by monotony of g, g j i (λ k -i ) -g j i (λ k-1 -i ) is lower bounded by (4.37) |∂ λ i g j i | ∞ (λ k-1 i -λ k i ), for i ∈ V (i).
We then take the i ∈ V (i) that maximizes (λ k-1 i -λ k i ) and use the previous lemma to get the result. 4.5. Algorithm Implementation. We implemented this algorithm in Matlab. We use a dichotomy to compute the g k i . Note that for linear cost the analysis is similar. We define g i (λ -i ) as the unique x such that f i (x, λ -i ) = 0 and x ≥ 0 and define Λ such that

(4.38) Λ i (λ) = min(c i , g i (λ -i ))
We perform some numerical comparisons with CVX, a package for specifying and solving convex programs [START_REF] Grant | Graph implementations for nonsmooth convex programs[END_REF][START_REF] Grant | CVX: Matlab software for disciplined convex programming[END_REF] for both linear and piecewise linear production cost functions. We generate a graph with 100 nodes connected randomly. To generate the graph, we use a Barabasi-Albert model [START_REF] Barabási | Emergence of scaling in random networks[END_REF] to ensure some scaling properties. The experiment is performed on a personal laptop (OSX, 4 Go,1.3 GHz Intel Core i5). The networks randomly generated to test the implementations are displayed in Figures 1a and1b, and the results are summarized in Both CVX and the fixed point algorithm find the optimal value. The linear version of the fixed point algorithm is about ten times faster than the CVX resolution. Note that the algorithm could be distributed, since at each iteration, the computation at each node only depends on the values of the previous iteration. In addition, instead of computing the iterates of Λ at each step, we could use intermediate steps were we follow a decreasing direction Λ(λ k ) -λ k and choose h > 0 such that λ

k h = h(Λ(λ k ) - λ k ) + λ k satisfies Λ(λ k h ) ≤ λ k h
, which is easier to check than computing the g i . This makes the algorithm similar to more standard descent based approaches (see [START_REF] Bertsekas | Convex optimization algorithms[END_REF]).

5. Two-agent allocation problem. We propose another algorithm for the piecewise linear allocation problem when the network is limited to two agents. This section is motivated by the need for efficient (both in speed and precision) allocation algorithms to numerically compute Bayesian Nash equilibria of the standard setting. Indeed, the natural next step of this work would be to proceed with numerical benchmarks, by comparing the Bayesian Nash equilibrium of the standard setting and the solution of the optimal mechanism. In general the numerical search of such equilibrium requires to solve the allocation problems many times. A second motivation to present this piece of work here is the complementary insight it gives on the structure of the allocation problem.

5.1. First order condition. The allocation problem with two agents of slopes c j i and demand vector d i is ] and h = q -1 2 (j 2 q).

We then use the fact that g is idempotent: g(u) = x ⇔ g(x) = u. We obtain:

(5.12) 0 ∈ ∂C(h) ⇔

          
∃j 1 , j 2 h ∈ q -1 i (](j i -1), j i [q) and h = g( ), g(

c j 1 1 c j 2 (h) 2
)] and h = q -1 1 (j 1 q) ∃j 2 , rh ∈ [g(

c j 1 (h) 1 c j 2 2
), g(

c j 1 (h) 1 c j 2 +1 2
)] and h = q -1 2 (j 2 q). We denote, for (i, j) ∈ I × J and (j 1 , j 2 ) ∈ J 2 :

a j i = q -1 i (j q) and b j1,j2 = g(c j1 1 /c j2 2 )/r. (5.13) Those two quantities only depend on the problem data. We point out that a j i corresponds to the value of h when we set q i = j q and b j1,j2 corresponds to the optimal value of h when q i ∈](j i -1), j i [q. We sum up with the following Lemma: Lemma 5.1. There exist (j 1 , j 2 ) ∈ J 2 such that one of those propositions is true:

F i (λ I A , λ I B (λ I A )) = qk i . Moreover, since F i is C ∞ on [c * , c * ] n , λ I B is C ∞ on V .
Then if c ∈ V , (c, λ I B (c)) checks the first order condition so by uniqueness c I A , λ I B (c) is the dual solution, and so, q i = F i (λ I B (c), c) for all i ∈ I on V , so q i is C ∞ at c. This concludes the proof of the first part of the lemma. The continuity of q comes from Berge maximum principle (see Theorem 9.17 in [START_REF] Rangarajan | A first course in optimization theory[END_REF]) in a convex setting.

The next lemma is an important component for the proof of Theorem 3. • i ∈ I A then as explained in the proof of Lemma B.3, S(I A , I B , I C , j, j ) is locally a surface parametrized by c i so by projection over an hyperplane of the type c i = x it also a surface in C -i . • i ∈ I B \I C locally, q is independant of c i so if S(I A , I B , I C , j, j ) ∩ (c i , S i (c i )) is of strictly positive measure, then S(I A , I B , I C , j, j ) has also a strictly positive measure in C n , since this is not true, S(I A , I B , I C , j, j ) ∩ (c i , S i (c i )) is of zero measure in the neighborhood. • Else i ∈ I C , which is the tricky part. First by definition of I C , for any element c of S(I A , I B , I C , j, j ), q i (c) = j i q and λ i (c) = c j i i . Without loss of generality, we assume j i = j i , the other case can be treated similarly. Then we make the observation that we do not modify the c -i of S(I A , I B , I C , j, j ) if we set c j+1 i = c j i . Since we are interested in S(I A , I B , I C , j, j ) ∩ (c i , S i (c i )), we can assume without loss of generality that c j+1 i = c j i . Then we have reduced to the case i ∈ I A . We conclude as in the proof of Lemma B.3.

  the fact that any

( a )

 a The network generated to test the linear implementation of the algorithm (b) The network generated to test the generic implementation of the algorithm

2 ∈( 5 . 16 )Q

 2516 [b j1(a j 2 2 ),j2 , b j1(a j 2 2 ),j2+1 ].Then the optimal value of h is respectively b j1,j2 , a j1 1 and a j2 2 .Proof. By definitionX(a 1 . . . a k-1 , b, a k+1 . . . a N ) -X(a 1 . . . a k-1 , c, a k+1 . . . a N ) = V (a 1 . . . b . . . a N ) -V (a 1 . . . c . . . a N ) + j =k a j [Q j (a 1 . . . b . . . a N ) -Q j (a 1 . . . c . . . a N )] +bQ k (a 1 . . . b . . . a N ) -cQ k (a 1 . . . c . . . a N ) = c b Q k (a 1 . . . s . . . a N )ds + j =k a j [Q j (a 1 . . . b . . . a N ) -Q j (a 1 . . . c . . . a N )] +bQ k (a 1 . . . b . . . a N ) -cQ k (a 1 . . . c . . . a N ).We use (H1) for the last equality. Then we apply a telescopic formulaX(a) -X(b) = X(a 1 . . . a N ) -X(b 1 , a 2 . . . a N ) + X(b 1 , a 2 . . . a N ) -X(b 1 , b 2 . . . a N ) + . . . +X(b 1 . . . b N 1 , a N ) -X(b 1 . . . b N ) k (b 1 . . . s . . . a N )ds) + N k=1 j<k b j [Q j (b 1 . . . b k-1 , a k , a k+1 . . . a N ) -Q j (b 1 . . . b k-1 , b k , a k+1 . . . a N )] + N k=1 j>k a j [Q j (b 1 . . . b k-1 , a k , a k+1 . . . a N ) -Q j (b 1 . . . b k-1 , b k , a k+1 . . . a N )] + N k=1 a k Q k (b 1 . . . b k-1 , a k , a k+1 . . . a N ) -b k Q k (b 1 . . . b k-1 . . . b k , a k+1 . . . a N )Reordering the last three terms, we getN j=1 k>j b j [Q j (b 1 . . . b k-1 , a k , a k+1 . . . a N ) -Q j (b 1 . . . b k-1 , b k , a k+1 . . . a N )] + N j=1 k<j a j [Q j (b 1 . . . b k-1 , a k , a k+1 . . . a N ) -Q j (b 1 . . . b k-1 , b k , a k+1 . . . a N )] + N j=1 a j Q j (b 1 . . . b j -1, a j , a j+1 . . . a N ) -b j Q j (b 1 . . . b j-1 . . . b j , a j+1 . . . a N ) (b 1 . . . b k-1 , a k , a k+1 . . . a N ) -Q j (b 1 . . . b k-1 , b k , a k+1 . . . a N )] +a j Q j (b 1 . . . b j-1 , a j , a j+1 . . . a N ) -b j Q j (b 1 . . . b j-1 . . . b j , a j+1 . . . a N ) +a j k<j [Q j (b 1 . . . b k-1 , a k , a k+1 . . . a N ) -Q j (b 1 . . . b k-1 , b k , a k+1 . . . a N )]} = N j a j Q j (a 1 . . . a N ) -b j Q j (b 1 . . . b N )

10 . Lemma B. 5 .

 105 Let i ∈ I and c i ∈ C i , then the Lebesgue measure of the set(B.10) S i (c i ) = {c -i ∈ C -i , (c i , c -i ) ∈ S} is zero. Proof. Using Lemma B.1, S i (c i ) ⊆ {c -i ∈ C -i , (c i , c -i ) ∈ ∪S(I A , I B , I C , j, j )}. So let c -i ∈ S i (c i ), I A , I B apartition of I, and I C ⊆ I B not empty, and j, j such that (c i , c -i ) ∈ S(I A , I B , I C , j, j ). There are three possible cases:

Table 2 .

 2

		Fixed Point CVX		Fixed Point CVX
	cost	83.2	83.195	cost	4971.4	4971.4
	time (s) 2.03	30.23	time (s) 28.39	35.23

Table 2 :

 2 Results for a linear (a) and piecewise linear (b) instances of the problem solved with the fixed point algorithm and CVX.

Take two optimal solutions, then check that the solution build with the average of the two flow vectors is admissible by convexity of the problem and strictly better by concavity of g.

Problem 5.

(5.1) minimize q j i ,h j∈J c j 1 q j 1 + c j 2 q j 2 subject to

We assume that N is big enough so that each agent could supply the whole amount without producing more than qN . This is not a restrictive assumption as we could put very high marginal cost to model some capacity constraints. We denote for h ∈ R and j ∈ J

(5.3) φ j i (h) = min((q i (h) -(j -1)q) + , q). In order to reduce to an unconstrained problem, we assume that the constraints on the positiveness of the production are not bounding (else we can already conclude). This can be checked numerically by computing the gradients at q i (h) = 0. Since the nodal constraints are bounding, we reformulate the problem:

By definition of φ for (i, j, h) ∈ I × J × R,

(5.5)

So we can express the derivative of φ j i :

(5.6)

The function C is convex, the expression of its subdifferential ∂C(h) follows from (5.6):

By the fifth assumption, we eliminate the last possibility. We denote (5.7)

] if q 1 (h) ∈]j 1 -1, j 1 [q and q 2 (h) = j 2 q

We denote (5.9)

and

(5.10)

By (5.8), 0 ∈ ∂C(h) is equivalent to one of those propositions being true:

(5.11)

Mechanism design and allocation algorithms for network markets 5.2. Algorithm. We denote by c - i the copy of the vector c i with the first coordinate removed, and q i the total production of agent i. We denote by q 1 (d, c 1 , c 2 ) and q 2 (d, c 1 , c 2 ) the optimal production allocation when the demand is d at both node and the cost vectors are c 1 and c 2 .

Lemma 5.2.

Proof. Fix q 1 i = q, the resulting optimization problem is equivalent to

which is the 2-agent equivalent of F i . We already know that if (λ 1 , λ 2 ) are the solution of the dual, then q 1 = F (λ 1 , λ 2 ) and q 2 = F (λ 2 , λ 1 ). The main result of this part is:

and the second and third propositions of Lemma 5.1 are not satisfied, then let k be the smallest element of J ∩ {0} such that

2 ) and q 2 = F (c 1 2 , c k 1 ) Proof. If (B), then we show that q 2 ≥ q. Indeed, if we assume q 2 < q, then since we have eliminated the corner solution cases λ 2 = c 1 2 . If we assume in addition that

2 ) > (k -1)q because of the definition of k, which is absurd. So if q 2 < q then necessarily q 1 > (k -1)q (The case q 1 = (k -1)q is a corner solution case that has been eliminated by hypothesis). So λ 1 > c k 1 so by (B) q 2 = F (λ 2 , λ 1 ) > F (c 1 2 , c k 1 ) > q which is in contradiction with the assumption. So if (B), then q 2 > q, and since c 1 1 < c 1 2 , q 1 > q. Else, by definition, (A) is true. Note that q 1 = F (c k 1 , c 1 2 ) and q 2 = F (c 1 2 , c k 1 ) solve the linear problem with c 1 = c k 1 and c 2 = c 1 2 and it is admissible. So by convexity, this is the solution.

Combining this result with the previous subsection, we can build an algorithm that first checks that we do not have a corner solution, and then recursively computes the solution.

Conclusion.

We have shown how to characterize and compute the mechanism design. In addition, the allocation problem for the optimal and the standard mechanism are the same. We have proposed an algorithm based on a fixed point to solve the allocation problem. This work raises some questions. Can we weaken the Assumptions used in this work? Can we estimate the social benefit of using such mechanism? How to build numerical benchmarks to compare the optimal mechanism and the standard setting? How to implement the optimal mechanism in practice? Which real markets enter in the framework described in §3.6? Appendix A. Proof of Lemma 3.7.

We end up with (

Appendix B. On S and the regularity of q. Remember that the set S corresponds to the points of transition between the two possibilities defined by the first order condition (4.19): (B.1) S = {c ∈ C n , q i (c) = j q and λ i (c) = c j for some i ∈ I, j ∈ J, j ∈ {j, j + 1}}.

Our first goal is to show that S is a finite union of sets of zero measure (Lemmas B.1 and B.3). To do so, we apply the implicit functions theorem. From this we deduce the regularity of q (proof of Lemma 4.4). For any I A , I B partition of I, and I C ⊂ I B not empty, j ∈ J I and j ∈ J I such that for all i, j ∈ {j i , j i + 1}, we denote by S(I A , I B , I C , j, j ) the set

.

For an element c of such set, we denote by M the matrix

.

We need to study the invertibility of M to apply the implicit functions theorem (Lemma B.2). Note that the function S is defined on a finite set. We use the image of S to show that the measure of S with respect to the Lebesgue measure is zero. We first show in the next lemma that S is included in the finite union of the S(I A , I B , I C , j, j ) family. Then we will show that each element of this family has a measure equal to zero. Lemma B.1. S ⊆ ∪S(I A , I B , I C , j, j ) Proof. Take c ∈ S, then by definition of S, there exist i ∈ I, j ∈ J and j ∈ {j, j + 1} such that q i (c) = j q and λ i (c) = c j , so I C is not empty. By Lemma 4.2, for all i ∈ I, i is in I A or I B . So we have a set S(I A , I B , I C , j, j ) such that c is in this set, so S is included in the union of those sets.

Lemma B.2. For any c ∈ C n the matrix M (c) is invertible. Proof. Assume that there are some coefficients α i such that i α i M i = 0 where M i is the ith column of M . Then by (4.3) and (4.4), the ith row of this relation writes:

We denote b i,j = λ 2 j λi ri,j (λi+λj ) 3 and a i = αi λi . Then (B.4) is equivalent to

Considering the biggest a i , we get that all a i are equal by convexity, and so either all are equal to zero or (B.6)

which is not the case since I A is not empty by the fifth assumption. Next we show that S(I A , I B , I C , j, j ) has a zero Lebesgue measure.

Lemma B.3. For any I A , I B partition of I, and I C ⊂ I B not empty, j ∈ J I and j ∈ J I such that for all i, j ∈ {j, j + 1}, the measure of the set S(I A , I B , I C , j, j ) is zero.

Proof. We assume in the market description that it is not possible to produce a multiple q at each node and satisfy exactly the nodal constraints (fifth assumption). Therefore it is not possible that I B = I, so I A is not empty. By definition of S I A ,I B ,I C ,j,j , for all i ∈ I B , (B.7)

which is a system of equations in λ I B parametrized by c j I A . Let c ∈ C such that the system is satisfied, by Lemma B.2, we can apply the implicit function theorem, so there is a ball around c in which S(I A , I B , I C , j, j ) is included in a smooth surface. By compacity of C, we can choose a sequence dense in S(I A , I B , I C , j, j ). We apply the result to each element of this sequence. By density, S(I A , I B , I C , j, j ) is a countable union of smooth surfaces. Therefore the measure of S(I A , I B , I C , j, j ) is zero.

A direct consequence of Lemma B.