Anna Bogomolnaia
email: anna.bogomolnaia@glasgow.ac.uk

Ron Holzman
email: holzman@technion.ac.il

Hervé Moulin
email: herve.moulin@glasgow.ac.uk

Worst Case in Voting and Bargaining

Keywords: worst case, guarantees, voting by veto, random dictator JEL classi…cation: D 63, D71

The guarantee of an anonymous mechanism is the worst case welfare an agent can secure against unanimously adversarial others. How high can such a guarantee be, and what type of mechanism achieves it?

We address the worst case design question in the n-person probabilistic voting/bargaining model with p deterministic outcomes. If n p the uniform lottery is the only maximal (unimprovable) guarantee; there are many more if p > n, in particular the ones inspired by the random dictator mechanism and by voting by veto.

If n = 2 the maximal set M(n; p) is a simple polytope where each vertex combines a round of vetoes with one of random dictatorship. For p > n 3, writing d = b p 1 n c, we show that the dual veto and random dictator guarantees, together with the uniform one, are the building blocks of 2 d simplices of dimension d in M(n; p). Their vertices are guarantees easy to interpret and implement. The set M(n; p) may contain other guarantees as well; what we can say in full generality is that it is a …nite union of polytopes, all sharing the uniform guarantee.

Guarantees and protocols

Worst case analysis is a simple mechanism design question. Fix an arbitrary collective decision problem by its feasible outcomes -allocation of resources, public decision making, etc.. -, the domain of individual preferences and the number n of relevant agents. We evaluate a mechanism (game form) solving this problem by the guarantee it o¤ers to the participants. This is the welfare level each one can secure in this game form without any prior knowledge of how others will play their part: the worst case assumption is that their moves are collectively adversarial (what I know or believe about their preferences, what I expect about their behaviour is irrelevant). My guarantee is the value of the two-person zero-sum game pitting me against the rest of the world.

Given the decision problem, what guarantees can any mechanism o¤er, and which mechanisms implement such guarantees? We are particularly interested in the maximal guarantees, those that cannot be improved: a higher guarantee is a better default option if I am clueless about other participants or unwilling to engage in risky strategic moves; it encourages acceptance of and participation in the mechanism.

These questions were …rst addressed by the cake-cutting literature ( [32], [START_REF] Dubins | How to cut a cake fairly[END_REF], [START_REF] Kuhn | On games of fair division, Essays in Mathematical Economics in Honour of Oskar Morgenstern[END_REF]). Two agents divide a cake over which their utilities are additive and non atomic. In the Divide and Choose mechanism (D&C for short) they each can guarantee a share worth 1=2 of the whole cake: the Divider must cut the cake in two parts of equal worth, any other move is at her own risk. This guarantee is not only maximal but also optimal (higher than any other feasible guarantee): when the two agents have identical preferences, their common guarantee cannot be worth more than 1=2 of the cake.

Contrast D&C with the simple Nash demand game: each agent claims a share of the cake, demands are met if they are compatible, otherwise nobody gets any cake. Against an adversarial player I will not get anything: this mechanism o¤ers no guarantee at all. The appeal of D&C is that I cannot be tricked to accept a share worth less than 1=2.

Worst case analysis is related to the familiar implementation methodology in mechanism design, but only loosely. We speak of a mechanism implementing a certain guarantee -mapping my preferences to a certain welfare level -but we do not postulate that each agent behaves under the worst case assumption, nor do we ask what social choice function will then be realised, as some papers reviewed in section 2 did. Instead the guarantee of a game form is just one of its features, an important one for two reasons: an agent using a best reply to the other agents'strategies gets at least her guaranteed welfare (because she has a safe strategy achieving that level no matter what); so any Nash equilibrium of the game delivers at least the guaranteed welfare to everyone, if an agent plays the mechanism repeatedly with changing sets of participants, the safe strategy is always available when she happens to be clueless about the other agents'behaviour, Many di¤erent mechanisms can implement the same guarantee, as the example below makes clear. 1 We call the whole class of game forms sharing a certain guarantee the protocol implementing it. The two concepts of guarantee and protocol and their relation is the object of worst case analysis.

We initiate this approach in the probabilistic voting model, where the protocols we identify can be interpreted as the guidelines for a partially informal bargaining process. There are …nitely many pure (deterministic) outcomes and we must choose a convex compromise (probabilistic or otherwise) between these. For tractability, we maintain a symmetric treatment of agents (Anonymity) and of outcomes (Neutrality). We …nd that, depending on the number n of agents and p of pure outcomes the set of maximal guarantees and their protocols can be either very simple and dull (when n p, see below) or dauntingly complex.

A good starting point is the simple case of deterministic voting over p outcomes with ordinal preferences. An anonymous and neutral guarantee is a rank k from 1 to p (where rank 1 is the worst): it is feasible if for any preference pro…le there is at least one outcome ranked k or above by each voter. Suppose …rst n p: at a pro…le where each outcome is the worst for some agent, the rank k must be 1, so the guarantee idea has no bite. Now if n < p we can give to each voter the right to veto up to d = b p 1 n c outcomes: this is feasible because nd < p, so the rank k = d + 1 is a feasible guarantee, clearly the best possible one. Worst case analysis'simple advice to a committee smaller than the number of outcomes it chooses from, is to distribute d veto rights to its members, not at all what a standard voting rule à la Condorcet or Borda does. However the corresponding protocol contains, inter alia, the following mechanisms: ask everyone to pick independently d outcomes to veto, then use any voting rule to pick among the remaining free outcomes, often more than p nd of them.

We allow compromises between the pure outcomes, interpreted as lotteries, time shares, or the division of a budget. Distributing veto tokens is a natural way to achieve a high guarantee, but there are others. The familiar random dictator2 mechanism ( [START_REF] Gibbard | Manipulation of schemes that mix voting with chance[END_REF]) with two voters implements the guarantee putting a 1=2 probability on both my …rst and worst ranks. And the uniform lottery over all ranks is yet another guarantee implemented by any mechanism where each participant has the right, at some stage of the game that could depend upon the agent, the play of the game etc.., to force the decision by ‡ipping a fair coin between all outcomes.

Example: three agents, six outcomes The uniform guarantee U N I( 6) is the lottery uni = ( ), where each rank is equally probable. Distributing one veto token to each agent implements 1 = (0; 1; 0; 0; 0; 0) (recall the …rst coordinate is the worst rank), as in the deterministic case. But 1 is not maximal: it is improved by making the protocol a bit more precise. After the veto tokens have been used, we can pick one of the remaining outcomes uniformly, or give the option to force this random choice to each agent. Then the rank distribution cannot be worse for anyone than vt = (0; 1 3 ; 1 3 ; 1 3 ; 0; 0), because my worst case after the vetoing phase is that the two other agents killed my two best outcomes. And vt stochastically dominates 1 . We will use the notation V T (3; 6) instead of vt when it is important to specify n and p.

The random dictator mechanism between our three agents delivers the guarantee 2 = ( 2 3 ; 0; 0; 0; 0; 1 3 ): my worst case is that the two other agents pick my worst outcome. Again 2 is not maximal, and improved by the following protocol: agents report (one of) their top outcome(s); if they all agree on a we choose a; if they each choose a di¤erent outcome, we pick one of them with uniform probability; but if the choices are a; a; b we randomize uniformly between a; b and an arbitrary third outcome c. This implements the correct random dictator guarantee RD(3; 6) : rd = ( 1 3 ; 1 3 ; 0; 0; 0; 1 3 ), that stochastically dominates 2 .

It is easy to check directly that U N I( 6), V T (3; 6) and RD(3; 6) are all maximal. For instance this follows for rd and vt by inspecting respectively the left or right pro…le of strict ordinal preferences (where agent 1's worst is a and best is c). At the left pro…le, to give a 1 3 chance of their best outcome to all agents a protocol implementing rd must pick a; b or c, each with probability 1 3 : then each agent experiences exactly the distribution rd over her ranked outcomes, and no other lottery stochastically dominating rd is a feasible guarantee at this pro…le. Similarly at the right pro…le, implementing vt implies zero probability on a; b; c, and at most (hence exactly) 1 3 on each of x; y and z. The symmetry of these two arguments is not a coincidence: a critical duality relation connects vt and rd (section 4). What other guarantees are maximal for n = 3; p = 6? Convex combinations preserve feasibility but not maximality: for instance an equal chance of the protocols implementing V T (3; 6) and RD(3; 6) delivers the feasible guarantee

1 2 rd + 1 2 vt = ( 1 6 ; 1 3 ; 1 6 ; 1 6 ; 0; 1 6
) which is dominated by uni . But lotteries between U N I(6) and V T (3; 6), or between U N I(6) and RD(3; 6) are in fact maximal. Moreover for this choice of n and p, the maximal guarantees cover exactly the two intervals [ uni ; vt ] and [ uni ; rd ] (Theorem 1 in section 5).

The choice facing the worst case designer in this example is sharp, and its resolution is context dependent: the veto guarantee is a good …t when bargaining is about choosing an expensive infrastructure project, or a person to hold a position for life; the random dictator approach makes sense if we are dividing time between di¤erent activities, or choosing a pair of roman consuls; the uniform guarantee stands out if we value a disagreement outcome revealing no information about individual preferences.

Critical to their practical application, the protocols implementing U N I; V T and RD above rely on ordinal preferences only, as do the agents'safe action when they report which outcome(s) they veto, or which ones they prefer among those still in play.

The punchline Our results cast a new light on two familiar collective decison mechanisms, random dictator and voting by veto. Together and in combination with the uniform guarantee, they generate all maximal guarantees if n = 2, and essentially all of them again if 3 n < p 2n. In the general case they can be sequentially combined to produce a very large subset of maximal guarantees.

Contents of the paper

After a review of the literature in section 2 we de…ne in section 3 the concept of guarantee in three related models. In the …rst one, agents have ordinal preferences over the pure outcomes, and incomplete preferences over lotteries by stochastic dominance. In the second they have von Neuman Morgenstern (vNM) utilities over lotteries. In the third they have quasi-linear utilities over outcomes and money, and lotteries are replaced by cash compensations. A guarantee is a convex combination of the ranks 1 to p where rank 1 is the worst. It is feasible if at each pro…le of preferences, there is a lottery over pure outcomes, or a pure outcome and a balanced set of cash compensations in the quasi-linear model, that everyone weakly prefers to her guaranteed utility.

Lemma 1 shows that the three de…nitions are equivalent and that feasible guarantees cover a canonical polytope G(n; p) in the simplex with p ranked vertices. Its Corollary gives a compact though abstract characterisation of G(n; p).

Section 4 focuses on the subset M(n; p) of maximal guarantees, starting with a complete characterisation in two easy cases (section 4.1):

If n p the unique maximal guarantee is U N I(p), dominating every other feasible guarantee (Proposition 1), so the worst case viewpoint tells us to allow each agent to force this canonical anonymous and neutral disagreement outcome. In every other case there are many more options.

If n = 2 < p a guarantee is maximal if and only if it is symmetric with respect to the middle rank (Proposition 2). For instance M(2; 6) is the convex hull of rd = ( 1 2 ; 0; 0; 0; 0; 1 2 ) (RD(2; 6)), mix = (0; 1 2 ; 0; 0; 1 2 ; 0), and vt = (0; 0; 1 2 ; 1 2 ; 0; 0) (two veto tokens per person). Here is the protocol for mix : the agents veto one outcome each, then choose randomly a dictator (equivalently, we randomly give one veto token to one agent and four tokens to the other). Note that U N I(p) is the center of the polytope M(2; p). When 3 n < p, the structure of M(n; p) is much more complicated. Section 4.2 describes a critical duality property inside M(n; p), relating V T (n; p) and RD(n; p), while U N I(p) is self-dual: Proposition 3. We de…ne in section 4.3 the large set C(n; p) of canonical guarantees: for three or more agents they are a rich family of vertices of M(n; p). Their protocols combine up to d successive rounds (recall d = b p 1 n c) of either veto (one token each) or a (partial) random dictator.

Our …rst main result Theorem 1 in section 5.1, gives a fairly complete picture of all maximal guarantees with three or more agents and at most twice as many pure outcomes (p 2n () d = 1). As long as p 6 = 2n 1 and (n; p) 6 = (4; 8); (5; 10), they cover exactly the two intervals [U N I(p); V T (n; p)] and [U N I(p); RD(n; p)], as in the numerical example above. There are additional maximal guarantees when p = 2n 1 or (n; p) = (4; 8); (5; 10), some of them described after the Theorem (Proposi-tion 4).

In section 5.2 we turn to the general case 3 n < p with no restrictions on d. The set M(n; p) is a union of polytopes (faces of G(n; p)), of which U N I(p) is always a vertex. Theorem 2 uses the canonical guarantees in C(n; p) to construct 2 d simplices of dimension d, one for each sequence of length d in fV T; RDg: the vertices of such a simplex are lotteries in C(n; p) obtained from the d initial subsequences of , plus U N I(p). For instance the sequence = (V T; RD) gives the triangle in C(3; 7) with vertices U N I(p), V T (3; 7), and = (0; 1 3 ; 1 3 ; 0; 1 3 ; 0; 0) denoted V T RD; the latter is implemented by a …rst round of one veto each, followed by RD(3; q) over the remaining q outcomes (four or more). This construction does not cover the entire set M(n; p) but delivers a large subset built from simple combinations of veto and random dictator steps.

Section 6 gathers some open questions and potential research directions. Several proofs are gathered in the Appendix, section 7.

Related literature

The optimal design of a mechanism under the risk averse assumption that other agents are adversarial is discussed by the early literature on implementation in several slightly di¤erent formulations: implementation in maximin ( [START_REF] Thomson | Maximin strategies and elicitation of preferences[END_REF], [START_REF] Dasgupta | The Implementation of Social Choice Rules: Some General Results on Incentive Compatibility[END_REF]), prudent ( [START_REF] Moulin | Prudence versus sophistication in voting strategy[END_REF]) or protective strategies ( [START_REF] Barbera | Implementability via protective equilibria[END_REF]). As explained in section 1 our protocols do not de…ne complete game forms, and our guarantees are compatible with a wide range of strategic behaviours.

Steinhaus' seminal papers ( [32], see also [START_REF] Dubins | How to cut a cake fairly[END_REF], [START_REF] Kuhn | On games of fair division, Essays in Mathematical Economics in Honour of Oskar Morgenstern[END_REF]) invented the worst case approach for cutting a cake fairly among any number of agents. His simple protocol generalises Divide and Choose and guarantees to each agent a fair share: one that is worth at least 1 n of the whole cake. The main focus of the subsequent literature is envy free divisions: how to achieve one by simple cuts and queries ( [START_REF] Brams | An envy-free cake division protocol[END_REF], [START_REF] Robertson | Cake Cutting Algorithms: Be Fair If You Can[END_REF], [START_REF] Aziz | A Discrete and Bounded Envy-free Cake Cutting Protocol for Any Number of Agents[END_REF]) and proving its existence under preferences more general than additive utilities ( [START_REF] Stromquist | How to cut a cake fairly[END_REF], [START_REF] Woodall | Dividing a cake fairly[END_REF]). An exception is the recent paper ( [START_REF] Bogomolnaia | Guarantees in fair division: geberal or monotone preferences[END_REF]) returning to the worst case approach under very general preferences and identifying the MinMaxShare (my best share in the worst partition of the cake I can be o¤ered) as a feasible guarantee, though not a maximal one.

The last decade saw an explosion of research to de…ne and compute a fair allocation of indivisible items, proposing in particular a new de…nition of the fair share as the MaxMinShare ( [START_REF] Budish | The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes[END_REF]): my worst share in the best partition of the objects I can propose. This guarantee may not be feasible ( [START_REF] Procaccia | Fair Enough: Guaranteeing Approximate Maximin Shares[END_REF]) but this happens very rarely ( [START_REF] Kurokawa | When can the maximin share guarantee be guaranteed?[END_REF]); the real concern is that the protocols approximating this guarantee are all but simple.

Other early instances of the worst case approach are in production economies ( [START_REF] Moulin | All Sorry to Disagree: a General Principle for the Provision of Non-rival Goods[END_REF], [START_REF] Moulin | Welfare Bounds in the Cooperative Production Problem[END_REF]) and in the minimal cost spanning tree problem ( [START_REF] Hougaard | Decentralized pricing in minimum cost spanning trees[END_REF]).

The random dictator mechanism is a staple of probabilistic social choice ( [START_REF] Gibbard | Manipulation of schemes that mix voting with chance[END_REF], [START_REF] Sen | The Gibbard random dictatorship theorem: a generalization and a new proof[END_REF]). In axiomatic bargaining it inspires the Rai¤a solution ( [START_REF] Rai¤a | Arbitration schemes for generalized two-person games[END_REF]) and the mid-point domination axiom ( [START_REF] Sobel | Distortion of utilities and the bargaining problem[END_REF], [START_REF] Thomson | A class of solutions to bargaining problem[END_REF]) satis…ed by both the Nash and Kalai-Smorodinsky solutions.

Voting by veto is another early idea introduced by Mueller ( [START_REF] Mueller | Voting by veto[END_REF]) to incentivise agents toward compromising o¤ers: each agent makes one o¤er, which together with the status quo outcome makes p = n + 1 outcomes, after which they take turns to veto one outcome each (in our model the natural status quo is the uniform lottery over outcomes). This procedure is generalised in ( [START_REF] Moulin | Prudence versus sophistication in voting strategy[END_REF]). The area monotonic bargaining solution ([2], [START_REF] Anbarci | Noncooperative foundations of the area monotonic solution[END_REF]) is a direct application of voting by veto between two parties, similar to distributing b p 1 2 c veto tokens to each agent in our model. A handful of recent papers discuss variants of voting by veto in the classic implementation context: ([9]), ( [START_REF] Barbera | Balancing the power to appoint o¢ cers[END_REF]),( [START_REF] Laslier | A solution to the two-person implementation problem[END_REF]). All three papers implement maximal guarantees. Closer to home section 4 in ( [START_REF] Kirneva | On coordination in selection committees[END_REF]) explains the strategic properties of a veto mechanism implementing arbitrary compositions of our guarantee V T (n; p).

We mention …nally the small literature on bargaining with cash compensations and quasi-linear utilities ( [START_REF] Moulin | Egalitarianism and utilitarianism in quasi-linear bargaining[END_REF], [START_REF] Chun | The solidarity axiom for quasi-linear social choice problems[END_REF]) where only the uniform guarantee is discussed, while our results unveil many more possibilities.

Feasible guarantees

Anonymity and Neutrality (symmetric treatment of agents and outcomes, respectively) are hard wired in the model so a guarantee is well de…ned once we …x the number n of agents and p of deterministic outcomes. It is an element of (p), the simplex of lotteries over the ranks in [p] = f1;

; pg. Here 1 is the probability of the worst rank and p that of the best rank. We give three equivalent de…nitions of the same concept of feasibility, after which when we speak of a guaranteee we always mean that it is feasible.

Notation. For lotteries 2 (p), and only for those, we write

[ ] k 2 k 1 instead of the sum P k 2 k 1 t
. The symmetric of w.r.t. the middle rank is e :

e k = p+1 k for all k 2 [p].
The stochastic dominance relation (dominance for short) in (p) plays a central role throughout. We write ` and say that dominates if the following three equivalent properties hold

8k 2 [p] : [ ] k 1 [ ] k 1 8k 2 [p] : [ ] p k [ ] p k 8z 2 R p : fz 1 z 2 z p g =) z z
The set of deterministic outcomes is A, with generic element a, and (A), with generic element `, is that of lotteries over A. We keep in mind the alternative interpretations of (A) as time sharing or division of a budget between the "pure" outcomes in A.

The set of agents is [n], with generic element i. An agent i's ordinal preference over A (a complete, re ‡exive and transitive relation) is written

% i . A k-tail of the preference % i is a subset T of A with cardinality k such that b % i a whenever a 2 T; b 2 A T . Indi¤erences in % i may produce several k-tails.
Given % i and `2 (A) the rank-ordered rearrangement of `is the following lottery

` i in (p) 8k 2 [p] : [` i ] k 1 = minf X a2T `ajT is a k-tail of % i g (1)
De…nition 1 (ordinal preferences): Given n and p, the lottery 2 (p) is a guarantee at n; p if for any n-pro…le of preferences = (% i ) n i=1 on A there exists a lottery `2 (A) s.t. ` i ` for all i 2 [n]. Then we say that the lottery `implements at pro…le .

An agent i's vNM utility over A is a vector u i in R A and u i `= P a2A u ia `a is her utility at lottery `. We write u i 2 R p the rank-ordered rearrangement (aka order statistics) of u i :

8k 2 [p] : k X t=1 u it = minf X a2T u ia jT A, jT j = kg
De…nition 2 (vNM utilities):Given n and p, the lottery 2 (p) is a guarantee at n; p if for any n-pro…le of utilities (u i ) n i=1 on A there exists a lottery `2 (A) s.t. ` u i u i for all i 2 [n]. The ordinal de…nition is agnostic w.r.t. the risk attitude of the agents. The cardinal one speci…es it completely.

In the third model the agents have quasi-linear utilities over the pure outcomes in A: in lieu of randomisation (or any convex combinations) compromises are achieved by cash compensations between the agents. Agent i's utility is still any u i 2 R A and an outcome is a pair (a; t) where a 2 A and t = (t i ) n i=1 is a balanced set of transfers between agents, P n 1 t i = 0; the corresponding utilities are u ia + t i .

De…nition 3 (quasi-linear utilities): Given n and p, the convex combination 2 (p) is a guarantee at n; p if for any n-pro…le (u i ) n i=1 of utilities on A, there exists an outcome a 2 A and a balanced set of transfers

(t i ) n i=1 such that u ia + t i u i for all i 2 [n].
Lemma 1 These three de…nitions are equivalent. We write G(n; p) for the set of all guarantees at n; p: it is a polytope in (p).

Proof De…nition 1 =) De…nition 2
The identity ` u i = ` i u i for all `2 (A); u i 2 R A is easily checked. Now assume meets De…nition 1 and …x an arbitrary pro…le (u i ) n i=1 of vNM utilities, with associated ordinal preferences

(% i ) n i=1 . If `implements at (% i ) n
i=1 the relation ` i ` and the identity give ` u i u i as desired.

De…nition 2 =) De…nition 3 De…nition 3 says that is a guarantee if and only if for all

(u i ) n i=1 2 (R A ) n we have: n X i=1 u i max a2A n X i=1 u ia (2)
Fix (u i ) n i=1 and choose `implementing as in De…nition 2: the inequalities

` u i u i and n X i=1 ` u i max a2A n X i=1 u ia
together imply [START_REF] Anbarci | The area monotonic solution to the cooperative bargaining problem[END_REF].

De…nition 3 =) De…nition 1. Fix as in De…nition 3 and a preference pro…le

(% i ) n i=1 . Call S i the set of utilities v i 2 R A representing % i (a % i b () v ia v ib
for all a; b) and such that v ia 2 [0; 1] for all a. By property (2) for any pro…le (v i ) n i=1 2 n i=1 S i there exists a 2 A such that

P n i=1 v ia P n i=1 v i , which implies min (v i ) n i=1 2 n i=1 S i max a2A n X i=1 (v ia v i ) 0
The summation is a linear function of the variable (v i ) n i=1 varying in a convex compact, and of a. By the minimax theorem there exists `2 (A) such that

P n i=1 ` v i P n i=1 v i for all (v i ) n i=1 2 n i=1 S i . Taking v i = 0 for all i 2 gives ` v 1 v 1 for all v 1 2 S 1 . Equivalently ` 1 v 1 v 1
for any weakly increasing sequence v 1 in [0; 1] p : the desired property ` 1 ` follows, and the argument is the same for each i 2.

G(n; p) is a polytope. De…nition 1 implies that the set G(n; p) is a polytope in (p) (the convex hull of a …nite set, and the intersection of …nitely many half-spaces) for any n; p. Indeed feasibility of at some …xed ordinal pro…le means that a system of linear inequalities in `of the form M ` has a solution `, where the matrix M is independent of and depends a¢ nely on : by the Farkas Lemma this is equivalent to …nitely many linear inequalities on , and there are only …nitely many ordinal pro…les.

Corollary to Lemma 1 The lottery 2 (p) is in G(n; p) if and only if for any n-pro…le

(u i ) n i=1 in (R A ) n we have n X i=1 u i = 0 =) n X i=1 u i 0 (3)
"Only if"holds because (3) is a special case of the characteristic property (2).

For "if" we pick an arbitrary pro…le (u i ) n i=1 and set z = max a2A P n i=1 u ia . Writing 1 the vector with all coordinates equal to 1, we pick a pro…le (v i ) n i=1 such that u i v i for all i and P n i=1 v ia = z for all a, then we can apply (3) to (w i ) n i=1 : w i = v i z n 1. This gives P n i=1 v i z and the claim.

If n = 2 property (3) is easy to interpret, after checking the following identity (recall e is the symmetric of w.r.t. the middle rank):

8u 2 R A : ( u) = e u (4)
Property (3) means u e u for all u, equivalently e ` . Therefore

2 G(2; p) () [ ] k 1 [ ] p p+1 k for all k = 1; ; b p 2 c (5)
But for n 3 it is much harder to discover a set of such inequalities representing G(n; p), or the set of its extreme points.

Remark. We downplay the quasi-linear interpretation because the corresponding protocols, though quite straightforward to construct, are less palatable. They require to report the willingness to pay for di¤ erent outcomes, and thus essentially rely on the entire cardinal utility pro…le.

From the welfare point of view, the guarantees of interest are those that cannot be improved, the maximal ones.

De…nition 4

The guarantee 2 G(n; p) is maximal if

8 2 G(n; p) : ` =) =
The set of maximal guarantees is M(n; p) G(n; p). p for all k 2 [p], has the following properties: i) It is maximal for all n; p. ii) If n p it dominates every other feasible guarantee:

M(n; p) = f uni g. iii) If n 3 it is a vertex of G(n; p), hence of M(n; p) too.

Proof.

Statement i).The equality uni u i = uni u i for all u i implies for any pro…le

(u i ) n i=1 n X i=1 u i = 0 =) uni ( n X i=1 u i ) = 0 (6)
Suppose some 2 G(n; p) dominates uni and consider a pro…le of the form (u 1 ; u 1 ; 0;

; 0) where u 1 is arbitrary. Summing up the inequalities u 1 uni u 1 , ( u 1 ) uni ( u 1 ) gives u 1 + ( u 1 ) 0. Because meets property (3) both inequalities are equalities, and we conclude = uni .

Statement ii). Assume n p and pick an arbitrary guarantee in G(n; p), and a cyclical permutation of A: the latter maps utility u to u : u a = u (a) . We pick any u and consider the pro…le (u; u ; u 2 ; ; u p 1 ; 0; ; 0)

with n p null utilities. Clearly P p 1 k=0 u k = 1 for = P a2A u a , so we can apply property (3) to the pro…le (u p 1; u p 1; ; u p 1 p 1; 0; ; 0).

Together with (u k ) = u for all k, this gives

0 p 1 X k=0 ( (u k ) p ) = p( u ) =) u p = uni u as desired.
Statement iii). Suppose uni is a convex combination of two distinct 1 ; 2 in G(n; p). For any pro…le s. t.

P n i=1 u i = 0, property (3) implies P n i=1 s u i 0 for s = 1; 2. But by ( 6) the relevant convex combination of these inequalities is an equality, therefore they both are equalities.

For n 3, a lottery meeting (6) must be uni . Indeed, de…ne k = [ ] p p+1 k for k 2 [p] and 0 = 0, then pick any three nonnegative integers k; l; m summing to p. Consider a pro…le of 0; 1 utilities where u 1 ; u 2 ; u 3 are equal to 1 precisely on three sets of respective sizes k; l; m partitioning A, while other utilities, if any, are identically zero. Applying [START_REF] Bogomolnaia | Guarantees in fair division: geberal or monotone preferences[END_REF]

k = p+1 k for 1 k b p 2 c (7)
The extreme points of the polytope M(2; p) are the following guarantees t :

t t = t p+1 t = 1 2 for t = 1; ; b p 2 c ; and p+1 2 p+1 2 = 1 if p is odd
We see that for n = 2 the uniform guarantee U N I(p) is the center of the polytope M(2; p), contrasting sharply with the case n 3, p > n where U N I(p) is an extreme point of the non convex set M(n; p): Theorem 2.

Proof . Fix 2 G(2; p) and symmetric. Rewrite [START_REF] Brams | An envy-free cake division protocol[END_REF] as u = e u for all u , which by the identity (4) means u = ( u) for all u . The latter is property [START_REF] Bogomolnaia | Guarantees in fair division: geberal or monotone preferences[END_REF] for n = 2, so the maximality of follows as in the above proof of statement i) Proposition 1.

To prove the converse statement pick 2 G(2; p), which means e ` (see property [START_REF] Barbera | Implementability via protective equilibria[END_REF] in the previous section). As the dominance relation is preserved by convex combinations we have 1 2 ( e + ) ` where 1 2 ( e + ) is symmetric: thus is dominated if it is not symmetric.

The protocols implementing the vertices of M(2; p) combine in a simple way the veto and random dictator ideas explained in section 1. Asking one randomly chosen agent to select a pure outcome implements 1 = ( 1 2 ; 0; ; 0; 1 2 ), which we call the random dictator guarantee and denote RD(2; p). The guarantee V T (2; p) is = (0; 1 p 2 ; ; 1 p 2 ; 0) implemented by giving one veto token per person, then selecting one of the remaining 13 Documents de travail du Centre d'Economie de la Sorbonne -2021.12 outcomes with uniform probability (as in the example of section 1). It is maximal, though not a vertex of M(2; p) except if p = 3 or 4.

To implement 2 = (0; 1 2 ; 0; ; 0; 1 2 ; 0) we ask …rst each agent to veto one outcome, after which we pick a random dictator between the remaining (p 2 or p 1) outcomes: we write this guarantee as V T RD(2; p). And so on: V T t 1 RD(2; p) is the guarantee t : let each agent veto t 1 pure outcomes, then pick a random dictator for the remaining ones. If p is odd the guarantee

p+1 2 denoted V T p 1
2 (2; p) simply gives p 1 2 veto tokens to each agent.

A duality operation preserving M(n; p)

Although the results in this subsection apply for all n; p, they are only useful if 3 n < p, the only case not covered by Propositions 1 and 2: we maintain this assumption from now on. Besides the uniform rule U N I(p) the two most basic guarantees come from one round of veto or of random dictator:

V T (n; p) ! (0; 1 p n ; ; 1 p n ; n 1 z }| { 0; ; 0) RD(n; p) ! ( n 1 z }| { 1 n ; ; 1 n ; 0; ; 0; 1 n )
Given a lottery in (p) di¤erent from uni , the radius to is the interval of the half-line from uni toward contained in (p) (its other end is on the boundary @ (p)), i. e. all lotteries of the form uni + ( uni ) for some 0. The anti-radius from e is the interval in (p) of the half-line from uni away from e , i. e., the set of all lotteries of the form uni + ( uni e ) for some 0. If is a boundary lottery its dual F is the end point of the anti-radius from e

F = (1 + ) uni e where = 1 p max 1 k p k 1 (8)
(where max 1 k p k > 1 p because 2 @ (p)). Keeping in mind that min 1 k p k = 0 it is easy to check the identity ( F ) F = . For non boundary lotteries we extend this de…nition linearly on the radius to f 2 @ (p) and = uni + ( 1) g =) F = uni + (1 ) F : so that ! F is a proper duality in (p).

The uniform lottery is the only self-dual one, while V T (n; p) and RD(n; p) are dual of each other.

Proposition 3 i) If 6 =
uni is a maximal guarantee, the radius to and the antiradius from e (the symmetric of w.r.t. the middle rank) are contained in M(n; p). ii) The duality operation ! F in (p) preserves maximal lotteries:

[M(n; p)] F = M(n; p)
Note that the statement in Proposition 3 holds if we replace M(n; p) by G(n; p): the radius to a feasible guarantee, and the anti-radius from its symmetric are feasible as well; duality preserves feasibility. This follows at once from the Corollary to Lemma 1, the identity (4) and the de…nition [START_REF] Budish | The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes[END_REF].

The proof for M(n; p) is much harder: we need a technical result characterising M(n; p) in G(n; p) by its position w. r. t. the polar cone of G(n; p). Notation: we write G for the polar cone of G R p : G = fz 2 R p j8y 2 G : z y 0g.

Lemma 2

The guarantee 2 G(n; p) is maximal if and only if there exists a vector z 2 G(n; p) s. t.

P p k=1 z k = 0, z 1 < z 2 < < z p and z = 0.

Proof of "if". Fix in G(n; p) and z in G(n; p) as in the statement, and suppose is dominated by . As the coordinates of z increase strictly, ` and 6 = imply z < z. Now feasibility of and z 2 G(n; p) give z 0. This contradicts the assumption z = 0.

Note that the condition P p k=1 z k = 0 was not used, therefore Lemma 2 remains valid without this condition. But the condition makes the "only if" part stronger. The long proof of this direction is given in the Appendix.

Proof of Proposition 3. Statement i)

We …x 2 M(n; p) and z 2 G(n; p) as in Lemma 2. Consider …rst a lottery = uni + ( uni ) in the radius to . That is feasible as well ( 2 G(n; p)) is clear by checking property (3) in section 3. For maximality we use P p k=1 z k = 0 and z = 0 to compute z = (1 ) uni z + z = 0 and conclude 2 M(n; p) by Lemma 2 again.

Still …xing 2 M(n; p) and z, we pick next a lottery = uni + ( uni e ) in the anti radius from e . For feasibility we check property (3) at an arbitrary pro…le (u i ) n i=1 s. t.

P n 1 u i = 0. Compute n X 1 u i = (1 + ) n X 1 uni u i n X 1 e u i = n X 1 ( u i ) 0
where the last equality is the identity (4), and the inequality is from property (3) for .

The argument just made shows that for any 2 G(n; p) the lottery

(1 + ) uni
e is feasible as well, in particular

0 ((1 + ) uni e ) z = e z
where the equality uses P p k=1 z k = 0. Writing w = ( z p ; z p 1 ; : : : ; z 1 ) and using the identity (4), we conclude that w 0. Thus w is in G(n; p) too, and it satis…es the requirements in Lemma 2 with respect to : w = e w = z = 0, which proves the maximality of . Statement ii) follows from statement i) and the de…nition of the duality operation.

Canonical guarantees

We write the largest coordinate of a lottery as + = max 1 k p k . We see from [START_REF] Budish | The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes[END_REF] that the dual F of the boundary lottery is

F k = 1 p + 1 ( + e k ) for 1 k p (9)
(where e k = p+1 k ) De…nition 5 Composition by V T and RD For any 2 (p) the lottery V T 2 (p + n) obtains by inserting between one zero in rank 1 and n 1 zeros after rank p + 1:

V T = (0; ; n 1 z }| { 0; ; 0) (10)
If 2 @ (p) the lottery RD 2 @ (p + n) obtains by …lling uniformly n 1 ranks before and one after as follows: For any 2 (p) the lottery RD

RD = ( n 1 z }| { + n + + 1 ; ; + n + + 1 ; 1 n + + 1 ; + n + + 1 ) (11)
2 (p + n) is given by RD = [V T F ] F (12)
If 2 @ (p) we must check that the two de…nitions ( 11) and ( 12) coincide. Write for the boundary lottery on the right-hand side of equation [START_REF] Dasgupta | The Implementation of Social Choice Rules: Some General Results on Incentive Compatibility[END_REF]: applying ( 9) and + = + n + +1 we get

F = 1 (p + n) + n + +1
1 ( For the proof we need a second characterisation of maximal guarantees; the proof, much easier than that of Lemma 2, is also in the Appendix.

+ n + + 1 1 e ) = 1 p + 1 ( + 1 ( + ; e ;

Lemma 4

The guarantee 2 G(n; p) is maximal if and only if for all k 2 [p 1] there exists a preference pro…le such that, for any lottery ìmplementing at (De…nition 1) we have

max i2[n] [` i ] k 1 = [ ] k 1 ( 13
)
Proof of Lemma 3 Statement i) The proof that V T (n; p) is maximal, done in section 1 for n = 3; p = 6, is an application of Lemma 4. Its generalisation is straightforward. Then its dual RD(n; p) is maximal by Proposition 3. Statement ii) Fixing 2 G(n; p) we implement V T as follows: ask agents to report their worst outcome, eliminate n outcomes containing all the reported ones, then implement over the remaining p outcomes. The latter are ranked weakly higher than 2;

; p + 1 for each agent, so we conclude that V T is feasible. If now 2 M(n; p), we …x an index k 2 [p 1] and an (n; p)-pro…le ensuring property [START_REF] Gibbard | Manipulation of schemes that mix voting with chance[END_REF] as in the premises of Lemma 4. We construct the following (n; p + n) pro…le

1 a 1 p z}|{ a 2 a n n a n a 1 a n 1 (14)
where the initial pro…le on p outcomes occupies the ranks 2 to p + 1, while the preferences over the n other outcomes are cyclical. If a lottery ìmplements V T at it can put no weight on any a i outcome because (V T ) 1 = 0, therefore the restriction of `to the outcomes of implements at , so property (13) holds for ranks 2 to p + 1 as well as for the …rst one and the last n 1 ones.

That RD is feasible, resp. maximal if is follows from the duality relation [START_REF] Dubins | How to cut a cake fairly[END_REF] and the fact that duality respects maximality and feasibility (Proposition 3). Here is for completeness the protocol implementing RD if is a boundary feasible lottery: agents report their best outcome, then we pick n outcomes containing all reports; with probability n + n + +1 we choose one of those uniformly, and with probability 1 n + +1 we implement among the remaining p outcomes.

De…nition 6 Canonical guarantees Fix n; p; 3 n < p, s. t. d = b p 1 n c and p = dn + q for some q = 1;

; n. Each sequence = ( t ) h t=1 in fV T; RDg of length h; h d, de…nes a canonical guarantee 1 2 h by iterating the composition operation, i.e.,

1 2 h = 1 ( 2 ( h ) )
where h acts on (d h + 1)n + q outcomes, h 1 h acts on (d h + 2)n + q outcomes, etc. We write their set as C(n; p), of cardinality 2 d+1 2.

By Lemma 3 and the fact that the composition by each t adds n outcomes to the previous ones, all canonical lotteries are maximal. By duality [START_REF] Dubins | How to cut a cake fairly[END_REF], canonical lotteries come in dual pairs: exchanging V T and RD in each term of the sequence produces the dual lottery.

An important observation is that each 2 C(n; p) is uniform on its support, therefore determined by this non full support. This implies that it Statement i). Assume p = 2n 1. At any pro…le we can choose a set of n 1 outcomes meeting (containing at least one of) the top two outcomes of each agent. A uniform lottery over these outcomes guarantees to every agent a probability of at least 1 n 1 for his top two outcomes. Hence there must be a maximal guarantee that does that, but neither U N I(p); V T (n; p) nor RD(n; p) does this, hence neither does a convex combination of these.

For (4; 8) one checks easily that we can always choose a triple of outcomes meeting the top three outcomes of each agent in at most one element. A uniform lottery over the complement of triple guarantees to every agent at least 2 5 for his top three outcomes, and the argument is completed as above. For (5; 10), a simple case check shows that we can choose a triple of outcomes meeting the top three outcomes of each agent. A uniform lottery over them guarantees to every agent at least 1 3 for his top three outcomes, and the argument is completed as above.

Statements ii) and iii). The protocols implementing and F in each case follow the same logic as above. For we can always pick two outcomes x; y meeting the top two (when (n; p) = (3; 5)) or three (when (n; p) = (4; 7)) of any agent, then we draw x and y each with probability 1 2 . For F we can always pick two outcomes x; y such that the worst two (when (n; p) = (3; 5)) or three (when (n; p) = (4; 7)) of any agent contain at least one of them, then we randomise uniformly over the remaining outcomes.

We omit for brevity the tedious arguments, available upon request from the authors, showing that these guarantees, as well as and F are maximal, and generate the entire sets M(3; 5) and M(4; 7).

Note that, in particular, Theorem 1 and Proposition 4 give a full description of maximal guarantees whenever 3 n < p n + 3.

Maximal guarantees for 3 n < p

For higher values of d = b p 1 n c we know only a few general facts about the structure of M(n; p). Lemma 2 in Proposition 3 provides our best clue. For any z 2 G(n; p) such that G(n; p) intersects the hyperplane H = fyjz y = 0g, the intersection H \ G(n; p) is a face of G(n; p), in particular a polytope. The Lemma tells us that such a face de…ned by a vector z with increasing coordinates is a subset of M(n; p), and that all maximal guarantees obtain for some z. This proves the following. can we evaluate the number of such components?

The early voting by veto literature stresses the guarantees it o¤ers to coalitions of like-minded voters ( [START_REF] Mueller | Voting by veto[END_REF]). We could similarly de…ne, given n and p, a guarantee for each size of a coalition, and try to link our modeling approach to the design of voting rules where the strategic formation of coalitions promotes stability ( [START_REF] Moulin | The Proportional Veto Principle[END_REF], [START_REF] Moulin | The Strategy of Social Choice[END_REF], [START_REF] Peleg | Game theoretic analysis of voting in committees[END_REF]).

Even for the individual guarantees discussed here, it may be possible to connect a maximal guarantee with the "best" game form(s) to implement it, where best may refer to simplicity, or to strategic or normative properties.

Appendix

Proof of Lemma 2

We prove the only if statement: for any 2 M(n; p) we can …nd a vector z as in Lemma 2.

Consider the following cone W in R p :

= fz = n X i=1 u i j for some U = (u i ) n i=1 s.t. n X i=1 u i = 0g (16)
By its characteristic property (3) G(n; p) is the intersection of W with (p), therefore G(n; p) is the Minkowski sum of ! W and R p , where ! W is the convex hull of W . Moreover the identity

P (i;k)2[n] [p] u ik = P (i;a)2[n] A u ia implies P p k=1 z k = 0 in W , therefore ! W = G(n; p) \ fzj P p k=1 z k = 0g.
We …x now a maximal guarantee and de…ne the sub-cone Z of ! W :

Z = fz 2 G(n; p) j p X k=1 z k = 0 and z = 0g
This cone is convex, and every element of Z satis…es z 1 z 2 z p , because these inequalities hold in W . To prove that Z contains some z s. t. z 1 < z 2 < < z p , we choose in Z one b z in which the number of equalities between consecutive coordinates of b z is as small as possible. If there is no equality we are done. Otherwise, assume that the …rst equality is b z k = b z k+1 . We will show the existence of some z 2 W s. t. z k < z k+1 and z = 0:

[` i ] k 1 1 [` i ] k 1 [ ] k 1 " = [ ] k 1 1 "
so that if k 1 is positive we can apply the previous argument. If k 1 = 0 again, we repeat this observation until we …nd some positive t , t k 2, whose existence is assured by [START_REF] Moulin | Prudence versus sophistication in voting strategy[END_REF].

Proof of Theorem 1

Step Assume …rst that p 2n 2 and 2 k b p 2 c. If k divides p the lemma is obvious (take a partition of [p]). Suppose p = tk+r where 1 r k 1. Let S i = f(i 1)k + 1; : : : ; ikg for i = 1; : : : ; t. Also, let S i = C i [ ftk + 1; : : : ; pg for i = t + 1; : : : ; t + k, where the sets C i are of size k r and form the k cyclic intervals in a cyclic arrangement of S t . Let 1 = = t 1 = 1; t = r k ; t+1 = = t+k = 1 k . These weights make S 1 ; : : : ; S t+k a balanced family, and it remains to check that t + k n.

We have t + k < p k + k maxf p x + x : x 2 [2; p 2 ]g = p+4 2 . If p 2n 2 this gives t + k < n + 1 as desired.

Assume next p = 2n and 2 k n. When k divides p a partition works, so we may assume that 3 k n 1 and thus n 4. We further exclude the exceptional cases n = 4; 5 and assume n 6. If k n 2 we still have p k + k n + 1 as in the original proof. Thus we may assume that k = n 1. We provide two variants of the construction of the balanced family, depending on parity. where jSj = k and the other sets are pairs. Take S with weight 1, and for each P i , the union of all P j , j 6 = i, with weight 2 k . This gives a balanced family of size k 2 + 2 < n. where jSj = k, jT j = 3 and the other sets are pairs. Take S with weight 1, for each P i take the union of T and all P j , j 6 = i, with weight 2 k , and for each element a of T take the union of fag and all the P i with weight 1 k . This gives a balanced family of size k 1 2 + 4 n.

Step 2. Assume (n; p) are as in Lemma 5 and let 2 k p 2. Then for any 2 G(n; p) we have [ ] k 1 k p . By duality, it su¢ ces to show this for 2 k b p 2 c. Let S 1 ; : : : ; S m with weights 1 ; : : : ; m be a balanced family as in the lemma. Consider a pro…le of preferences in which fa j : j 2 S i g is the k-tail of the preferences of agent i, i = 1; : : : ; m. Let `be a lottery that implements at this pro…le. Then 1 = P a2A `a = P m i=1 i P j2S i `aj

P m i=1 i [ ] k 1 = p k [ ] k
1 , implying the desired inequality.

Step 3. We know from Proposition 3 and the maximality of vt ; rd that M(n; p) contains the union of the two intervals in the statement. Conversely we …x 2 G(n; p), where (n; p) are as in Lemma 5, and show that it is dominated by a guarantee in those two intervals. We distinguish three cases.

Case 1. p 1 p . Set p = x and keep in mind that feasibility implies x 1 n . We will show that is dominated (weakly) by the guarantee 2 [ uni ; rd ] s. t. p = x : that is k = x for 1 k n 1 and k = y for n k p 1, with nx + (p n)y = 1.

Set p = n+q and partition A as fa 1 ; ; a n g[fb 1 ; ; b q g then consider a pro…le of preferences where for everyone: the a-s occupy the ranks 1 to n 1 and p and each a appears exactly once in rank p; the b-s occupy the ranks n to p 1 and the pattern of the b-s is cyclical for the …rst q agents. Pick a lottery `implementing at this pro…le. Then `a x for each a implying [ ] k x + ry for 1 r q 1. Indeed by summing the implementation constraints for the top r + 1 outcomes of the …rst q agents, we get (denoting the top outcome of agent i by a i ):

q[ ] p p r q X i=1 `ai + r q X i=1 `bi = ( q X i=1 `ai + q X i=1 `bi ) + (r 1) q X i=1 `bi
(1 (n q)x) + (r 1)(1 nx) = q(x + ry) Case 2. 1 1 p . Set 1 = x and p = n + q. We show similarly that is dominated (weakly) by the guarantee 2 [ uni ; vt ] s. t. 1 = x : that is k = x for p n + 2 k p and k = y for 2 k q + 1, with nx + qy = 1.

We consider a pro…le of preferences over the outcomes in fa 1 ; ; a n g [ fb 1 ;

; b q g where: the a-s occupy the ranks 1 and p n + 2 to p and each a appears exactly once in rank 1;

1 a b x y z c 2

 2 b c y z x a 3 c a z x y b 1 a x y z b c 2 b y z x c a 3 c z x y a b

4. 1 2 Proposition 1

 121 Two easy cases: n p and n = The uniform guarantee U N I(p), uni k = 1

16

  Documents de travail du Centre d'Economie de la Sorbonne -2021.12

n 1 z

 1 }| { + ; : : : ; + )) = V T F as desired. Note that De…nition 5 implies in particular V T U N I(p) = V T (n; n+p) and RD U N I(p) = RD(n; n + p).

  The guarantees V T (n; p) and RD(n; p) are maximal.ii) The composition of guarantees by V T and RD respects their feasibility and maximality. For any 2 (p)2 M(n; p) =) V T ; RD 2 M(n; p + n)and the same statement holds by replacing M(n; p) by G(n; p) and M(n; p+ n) by G(n; p + n):

Proposition 5

 5 For 3 n < p, the set M(n; p) is a …nite union of faces of the polytope G(n; p), each having U N I(p) as a vertex. Our second main result identi…es a large subset of M(n; p) constructed what is the maximal dimension of a simplicial component of M(n; p)? We conjecture it is d = b p 1 n c.

Case 1 .

 1 k = n 1 is even. Partition [p] = [2k + 2] into S; P 1 ; : : : ; P k 2 +1

Case 2 .

 2 k = n 1 is odd. Partition [p] = [2k + 2] into S; T; P 1 ; : : : ; P k 1 2

1 kx for 1 k n 1 ;

 11 moreover p = x by assumption. It remains to show that [ ] p p r

  to this pro…le yields k + l + m = 1. It is easy to check that this simple integer version of the Cauchy equation implies k = k p for all k. Proposition 2 Maximal guarantees for n = 2 If n = 2 < p the lottery 2 (p) is a maximal guarantee if and only if it is symmetric:

  1. Recall the following notion from the Shapley-Bondareva theorem. A family S 1 ; : : : ; S m of subsets of [p] is balanced if there exist positive weights Then there exists a balanced family S 1 ; : : : ; S m of subsets of [p] of size k each, such that m n.

	Lemma 5 Assume that p 2 k b p 2 c.	2n 2, or p = 2n but n 6 = 4; 5 and let

1 ; : : : ; m such that

P i:j2S i i = 1 for every j 2 [p].

Similarly we can implement the optimal "one half of the whole cake" guarantee by D&C or by any one of Dubins and Spanier'moving knife procedures ([12]) 3 Documents de travail du Centre d'Economie de la Sorbonne -2021.12

Each agent has an equal chance to choose the …nal outcome. 4 Documents de travail du Centre d'Economie de la Sorbonne -2021.12

Documents de travail du Centre d'Economie de la Sorbonne -2021.12

Documents de travail du Centre d'Economie de la Sorbonne -2021.12

I. e., the guarantees 1 ; 1 2 ; 1

, etc..

Documents de travail du Centre d'Economie de la Sorbonne -2021.12

Acknowledgement 1 We are grateful for the comments of seminar participants in the University Paris 1, Lancaster, Oxford and Ashoka Universities. Moulin's research was supported by a Blaise Pascal Chair of the Region Ile-de-France, 2020-21.

is a vertex of G(n; p) (the proof mimicks that of statement iii) in Proposition 1), hence also a vertex of M(n; p).

We give some examples. If d = 1 (p 2n) V T (n; p) and RD(n; p) are the only canonical guarantees.

Constant sequences: the composition of h veto steps, or of h random dictator steps, gives dual lotteries of a similar shape: their support is at the extreme ranks or in the center: A simple protocol for the former gives h veto tokens to each agent, then randomises uniformly between the remaining outcomes, even if there are more than p nh of those (which will only improve the guaranteed welfare).

To implement the latter we elicit from each agent her h top outcomes, then randomise uniformly between any nh outcomes containing all reported tops, adding arbitrary outcomes if the reported ones are fewer than nh. The last instruction is important: ignoring it could result in giving too much weight to someone's worst outcomes (as illustrated in the example of section 1).

For d = 2 we have six canonical guarantees, four from the constant sequences and a dual pair from (V T; RD) and (RD; V T ). For instance in C(3; 7):

The protocol for RD V T selects three outcomes containing the top ones of each agent; then with probability 3=4 it picks one of those uniformly, and with probability 1=4 plays V T (3; 4) among the remaining outcomes.

Our …nal example is in C(3; 11) where d = 3 and we have three pairs of non constant sequences of length three, for instance: n < p let vt ; rd ; uni be the guarantees from V T (n; p); RD(n; p) and U N I(p). Then

ii) This is an equality if p 2n 2 and if p = 2n except when (n; p) = (4; 8) or (5; 10).

The proof is in the Appendix. Our next result explains why additional maximal guarantees appear in the cases excluded by statement ii) above and describes the full set M(n; p) in two such cases. ; 0; 0; 1 2 ; 0)

The set M(3; 5) is the union of the four intervals joining U N I(5) to these guarantees.

iii) For n = 4; p = 7 there are three dual pairs of maximal guarantees on the boundary of (7): V T (4; 7); RD(4; 7) and the two pairs = ( 1 2 ; 0; 0; 0; 1 2 ; 0; 0) The proof is in the Appendix.

The simplest example not covered in Theorem 1 is n = 3; p = 7, so d = 2. Theorem 2 describes four triangles of maximal guarantees coming in dual pairs. The uniform lottery is always a vertex and the other two vertices are canonical guarantees:

) where the dual pairs are the top two and the bottom two rows. In addition to these four triangles, the maximal set M(3; 7) also contains two intervals, joining U N I(7) to each of the following two dual non canonical guarantees:

In general, we keep in mind that many more guarantees than the ones described in Theorem 2 are maximal. Pick any non canonical guarantee in M(n; p) \ @ (p), for instance those described in Proposition 4 or in the previous paragraph: by Lemma 3 successive compositions of with V T and/or RD generate, for any h 1, 2 h non canonical maximal guarantees in M(n; p + hn) \ @ (p + hn).

Concluding comments

The set M(n; p) remains simple if n = 2 and/or p 2n (Proposition 2 and Theorem 1), but its combinatorial/geometric structure becomes complicated, perhaps severely, as

The corresponding vector z = P n i=1 u i is in W therefore u s i converges to zero. By taking subsequences, we can make sure that for each i, the way each u s i orders the outcomes in A does not depend on s (but depends on i). Then for each i there is a lottery i on A, its coordinates a permutation of those of , s.t.

;a2A de…ned by three sets of conditions: in each row i the entries are ordered the same way as in every u s i P n i=1 x a i = 0 in each column a x 1a = 0; x 1b = 1 where a and b are the outcomes ranked k and k + 1 by each u s 1 Note that Q is non empty because it contains each matrix U s . By construction each X in Q de…nes a pro…le in and

x i = 0, it cannot contain points arbitrarily close to H. Thus there is some positive " s.t. for any pro…le U in we have P n i=1 u i < ", and we can now conclude the proof in Case 1. These inequalities imply for any pro…le U :

Indeed if u 1;k+1 u 1k = 1 the pro…le (u 1 u 1k 1; u 2 + u 1k 1; u 3 ;

; u n ) is in , and rescaling our pro…le by

Note that in [START_REF] Laslier | A solution to the two-person implementation problem[END_REF] we can replace coordinate 1 by any coordinate i. Therefore we have

Because k > 0, the lottery obtained from by shifting " n or k , whichever is less, from k to k+1 dominates , and property [START_REF] Moulin | Egalitarianism and utilitarianism in quasi-linear bargaining[END_REF] implies it is feasible.

Case 2 k = 0 In this case, because b z 2 ! W it is a sum of m elements z j 2 W; j 2 [m], each z j de…ned by n utilities (u j i ) n i=1 as in [START_REF] Kuhn | On games of fair division, Essays in Mathematical Economics in Honour of Oskar Morgenstern[END_REF]. Note that if k > 1 then u j 0 i 0 ;k 1 < u j 0 i 0 ;k for some i 0 ; j 0 . Pick such i 0 and j 0 (or arbitrary ones if k = 1). Let a 2 A be s. t. u j 0 i 0 ;k = u j 0 i 0 ;a . For some small " > 0, modify (u

i=1 by letting u i 0 ;a = u j 0 i 0 ;a ", u i 1 ;a = u j 0 i 1 ;a + " for some i 1 6 = i 0 , and leaving all other utilities unchanged. Because k = 0 and by our choice of i 0 ,j 0 , for small enough " we have

As is feasible, this must be an equality, and therefore z = P n i=1 u i 2 Z and satis…es z k < z k+1 by construction.

Proof of Lemma 4

Statement If. Pick two guarantees ; in G(n; p), such that meets the property above while ` . Pick k 2 [p 1] and a pro…le as in the statement. Choose a lottery `implementing at and an agent i reaching the maximum in (13): we have

As k was arbitrary in [p 1] we conclude = therefore is maximal. Statement Only If. Suppose now that 2 G(n; p) fails the property in the Lemma: there is some k and some " > 0 s. t. at any pro…le there is some lottery `implementing at and such that

We must show that is not maximal. Suppose …rst k > 0 and construct 0 dominating by shifting a weight , smaller than " and k , from k to k+1 (and no other change). The lottery 0 is still in G(n; p): at a pro…le the lottery `implementing and meeting (20) implements 0 as well. Suppose next k = 0. Then we have for all i the b-s occupy the ranks 2 to q + 1 and the pattern of the b-s is cyclical for the …rst q agents.

Then the proof mimicks that in case 1 by showing …rst that a lottery implementing at this pro…le has [ ] p p k+1 kx for 1 k n 1, then focusing attention on the …rst q + 1 ranks to show [ ] r+1 1 x + ry for 1 r q 1. We omit the details.

Combining these inequalities with those in step 2 we see that is strictly dominated by uni .

Proof of Theorem 2

We …x 1 q n such that p = dn + q and prove the statement by induction on d. It is clear for d = 1 as fV T g and fRDg are the only two sequences and the intervals [U N I(p); V T (n; p)], [U N I(p); RD(n; p)] are in M(n; p).

Fix d 2 and consider a sequence 2 fV T; RDg d starting with 1 = V T . By its de…nition [START_REF] Chun | The solidarity axiom for quasi-linear social choice problems[END_REF] the composition by V T commutes with convex combinations of 2 ; 2 3 ; . Using the notation V EX[ ] for such combinations we have

where by the inductive assumption the second convex combination of canonical guarantees in C(n; p n) and of U N I(p n) is a maximal guarantee. By Lemma 3 so is the left-hand convex combination , and by Proposition 3 so is a convex combination of U N I(p) and .

The proof of the inductive step for a sequence starting from RD is more involded, because RD does not commute with convex combinations, even of boundary lotteries: therefore property [START_REF] Moulin | All Sorry to Disagree: a General Principle for the Provision of Non-rival Goods[END_REF] where RD replaces V T can only be true if the two sides use di¤erent convex combinations.

Observe …rst that if the boundary lottery is maximal,

] is in M(n; p) \ @ (p) as well. That is on the boundary is clear. By [START_REF] Dasgupta | The Implementation of Social Choice Rules: Some General Results on Incentive Compatibility[END_REF] takes the form ) ; n )

Consider a pro…le similar to [START_REF] Hougaard | Decentralized pricing in minimum cost spanning trees[END_REF] in the proof of Lemma 3, where by maxi-mality of we choose ensuring property [START_REF] Gibbard | Manipulation of schemes that mix voting with chance[END_REF] in Lemma 4:

If the lottery `implements at this pro…le we have `ai = n therefore its weight on the remaining p n outcomes in is (1 ) and the claim follows by Lemma 4 again.

We …x now an arbitrary convex combination

in G(n; p) and claim that it takes the form RD where is some other convex combination

This claim allows us to complete the induction step as follows. By the induction hypothesis, is in M(n; p n), and it is easy to see (and explained in detail below) that it is on the boundary. By what we just observed, any V EX[RD(n; p);RD ] is also maximal; by the claim this means that any convex combination of the guarantees corresponding to the initial subsequences of starting with RD is maximal. Finally, Proposition 3 handles the addition of the uniform guarantee.

Proof of the claim. Recall that canonical guarantees are uniform on their support, which we now describe for the canonical guarantees in our sequence. We partition the ranks 1;

; p into subsets S 1 ; ; S d+1 each of size n except for the last one of size q. The set S 1 is the support of RD(n; p) (the ranks 1 to n 1 and p). If 2 = RD then S 2 has the ranks n to 2n 2 and p 1, and the support of RD 2 is S 1 [ S 2 . If 2 = V T then S 2 has the rank n and those from p n + 1 to p 1, and the support of

(the complement of S 2 ). Continuing in this fashion, each j de…nes a new set S j that is added to its support if j = RD, while if j = V T we add S j+1 [ [ S d+1 to the support. We keep track of this construction by entering a one for sets in the support and a zero for those outside it: with the notation " 2 f0; 1g and " 0 = 1 " our sequence in C(n; p) 29 Documents de travail du Centre d'Economie de la Sorbonne -2021.12 is described by a table as follows

k is 1 k on its own support. Clearly, but critically, there is a column with only zeroes: this holds if " 2 = 0 ( 2 = V T ), or if " 2 = 1 but " 3 = 0, etc.., until, if " j = 1 for all j, the last column is null. A symmetric argument shows that in addition to the …rst column, there is another column full of ones. The …rst remark implies that and are respectively in @ (p) and @ (p n); the second that the maximal coordinate of is + = P d j=2 j j . Now we select the coe¢ cients j such that for this choice of . Because 2 @ (p n) the lottery RD is given by [START_REF] Dasgupta | The Implementation of Social Choice Rules: Some General Results on Incentive Compatibility[END_REF]: in particular it is constant on each set S k , just like . We see in the table that RD equals

in S 1 , while is worth P d j=2 j j +n so they coincide. Each entry in another column S k at row j adds " 1 n + +1 j j to RD and " j j +n to , where " is the coe¢ cient of that particular entry, so the desired equality follows.


E Rosenzweig

N Q Khanh

H A Tran

N T Ngo

S B Nguyen

NOTES ON THE 1 st DRAFT OF VIETNAM'S POWER DEVELOPMENT PLAN VIII

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Executive Summary

In February 2021, Vietnam's Ministry of Industry and Trade released the draft Power Development Plan VIII (draft PDP8), which outlines how the country will produce its electricity for the next ten years.

The draft focuses on developing gas-fired power. It reuses a renewable energy development strategy elaborated six years ago, ambitious then but now outdated by the solar and wind boom. Over the next ten years, it would more than double the sector's CO2 and PM2.5 emissions.

The bias towards gas-fired power generation is more the symptom of a problem in the planning process than the outcome of well-informed political choices. In recent years, Vietnam's Power Development Plan 7 turned into a record-keeping list of authorized energy projects. That broke the logic of planning.

The function of a masterplan is to think forward five to ten years. The future may be unpredictable; there will always be surprises like the COVID crisis. This is why a plan should identify no-regret investments, which remain relevant for a wide range of scenarios.

Policymakers need a coherent strategy about rooftop PV, floating PV, offshore wind, electricity storage, grid expansion financing, production capacity procurement with auctions, transport electrification, and long-term climate policy options. The current draft PDP8 study is short on these questions. Beyond the socio-economic plan, the PDP should coordinate with the marine and transportation plans.

There is an opportunity to address these topics by revising the draft to finalize the PDP8. Furthermore, the planning process must become more agile to keep up with the accelerated changes in the energy landscape. The draft PDP8 proposes a Law on Renewable Energy, and new regulatory institutions working on a shorter than quinquenal cycle. These changes are necessary to restore the planning process function as an useful decision support mechanism in the de-centralized energy systems era. b. Economists forecast how much electricity will be needed. This is about 9% more per year until 2025, with the Northern region growing faster than the Central or Southern parts.

c. The Government authorizes as many projects as needed according to its priorities.

d. Knowing how the load and sources will expand in each province gives a roadmap for grid engineers to build the necessary transmission network. See the Map 1 at the end of this document.

e. This reveals the amount of investment to be financed: a lot. According to the draft PDP8, over the next ten years, the power sector requires USD9.5bn per year for generation and USD3.3bn per year for transmission.

The total investment required is more than half the Vietnam trade surplus, which was 20 billion USD in 2020. and "To prioritize to gas-fired power development and suitable roadmap to reduce the share of coal-fired power." The focus on natural gas and renewable energy sources makes a change compared to the past strategy since the previous plan (PDP7) focused on developing a fleet of coal-fired power plants to meet the growth of electricity needs.

Since Resolution 55 defines both renewable energies and gas-fired power as priorities, there is a balance to be found. Coal and LNG supporters said that the new focus on renewable energy was excessive: solar and wind would never cover the country's energy consumption and require too much capital. On the other side, energy transition supporters [START_REF] Brown | Vietnam's PDP8 Should Be a Catalyst for Innovation, Not a Barrier to Change. Some Technology Choices Carry Substantially Higher Risks Than Others[END_REF] noted that the draft PDP8 focused too much on coal and gas, which failed to deliver according to the previous plans. Compromises are always criticized from both sides, but being attacked from both sides is not proof that the plan found a just balance. Does it? We will find the answer discussing Table 1, which compares the key 2030 targets of the draft PDP8 with the present situation and trends.

Image by Johannes Plenio from Pexels We can compare the Past and Present columns in the table with the previous plan -PDP7A, the 2016 revision of the PDP7-to understand the planning exercise's nature better.

The PDP7A forecasted the 2020 national commercial power output to be between 228 TWh and 245 TWh. The actual level was 216.8 TWh in 2019, with a pre-COVID power output growth rate of 9.7% per year (and a 2019-2020 growth rate of about zero). At that rate, the power output would have been within the range of the forecast. The demand estimate was overestimated, although not by much. The over-estimation of the economic growth rate forecasts used to prepare the PDP7A explains well this error.

PDP7A planned to have 26 GW of coal-fired generation capacity, 9 GW of gas-fired capacity, 18 GW of hydro, 0.85 GW of solar power, and 0.8 GW of wind power in 2020.

In reality, coal-fired generation capacity increased only to 20.4 GW in 2020. While EVN delivered projects mostly as planned, projects under the responsibility of other state-owned enterprises and foreign investors were delayed. Gas-fired generation capacity was 7.2 GW in 2020, as the domestic offshore fields were not put in production as planned.

The PDP8 planned to have 4.6 GW of nuclear power capacity operational by 2030. The National Assembly officially stopped the Ninh Thuan nuclear project in November 2016, eight months after the PDP7A was published. As the plant was planned to start in 2028, keeping or abandonning it had no influence on the electricity supply for the next ten years.

Facing the risk of electricity shortages as early as 2020-2021, the Government increased the price at which EVN buys solar and wind power. While it takes at least five years to build a coal power plant, it takes only one year to set up a solar farm. Between 2018 and 2020, photovoltaics reached 25% of Vietnam power generation capacity: 7.9 GW for rooftop PV, 8.6 GW for ground-mounted PV. Now Vietnam has more solar power than the UK or South Korea. About 11 GW of wind power capacity are currently under construction, with 4.43 GW on track to have COD before 31/10/2021 according to EVN (letter 1380/EVN-TTĐ on 22/03/2021).

The transmission network did not anticipate such a significant deviation from the plan. Consequently, in 2020 and 2021, we waste a sizable fraction of the electricity produced by solar and wind farms because it cannot be transmitted to the users. Considering the delay in 2 What the recent past reminds about the best-laid plans grid investment, it takes two to three years to solve these issues, assuming there are no difficulties acquiring the land use authorizations for substations and transmission lines.

Reality always derails plans. As the proverb says, "The best-laid plans of mice and men oft go astray." Since a gap between well prepared rational plan and the course of events is unavoidable, timely adaptation deviating from the initial plan is always necessary to achieve desired outcomes. Here, the Government changed the policies to add generation capacity and alleviate the supply security issue.

The renewable energy boom has demonstrated that a 5-year planning update cycle does not match the timescale of today's changes in the energy system. Solar PV gained a 25% share in the capacity mix in two years. We can expect more rapid advances in decentralized energy production. The draft PDP8 proposes to give additional responsibilities to the National Steering Committee for Electricity Development in Implementation of the PDP 8 (conclusion 19.11) and to allow power planning on a one or two years cycle as a basis to organize bidding and choose investors for power projects (conclusion 19.12). These recommendations about regulatory changes are more critical than long term forecasts.

Da Mi floating solar. Image by VIET.

Before we go back to Table 1 to see how the draft PDP8 balances the 'prioritize renewable energy and 'prioritize gas-fired power', let us discuss how these numbers were obtained.

As the introduction said, the hard choices in the planning process are to select projects meeting the demand that best fit with the policy goals. The draft PDP8 conducted a very comprehensive study to that end. It explored a set of 11 scenarios using models with detailed technological, spatial and temporal resolutions. It then performed a multicriteria ranking of these scenarios Further sensitivity analysis of this scenario examined how it performs when under perturbed conditions: different load, a dry year, different primary fuel prices, different cost of offshore wind technology, different CO2 prices. We want to offer these academic comments on the way the scenario was selected and analyzed:

Having only one 'vision for 2045' is a scientific shortcoming. A robust planning exercise should instead aim to find "no regret solutions", that is, investments in the short term that will still be useful in a long time for a broad range of plausible futures. There is no need to discuss the plan's post-2030 targets. These numbers have little forecast value; authorities will revise the strategy many times before.

This sensitivity analysis severely underestimated the variability of future fossil fuel prices. The draft PDP8 considers an uncertainty range for LNG price in 2025 of 10.6 -11.0 USD/MMBTU and coal 81 -88 USD/ton (page 402). Fossil fuel prices variability is much greater than that. For example, LNG's spot price in Asia (Platts Japan-Korea 3 Comments on how the PDP8 scenario was defined Marker) was around 2 USD/MMBTU mid-summer 2020, before it hit a record high of around 20 USD/MMBTU in January. While long-term supply prices are not as volatile as the spot price, most are indexed on uncertain oil prices. The PDP8 draft fails to provide an adequately calibrated analysis of the economy's exposure to fossil fuel price risks.

The draft PDP8 scenarios analysis explore only a tiny part of the space of feasible scenarios (see page 387, for example). The plan is an official document; it legally has to be based on projects already signed. But following old policy documents is not a legal constraint. On the contrary, the new plan has legitimacy to account for recent development and propose a new vision. Thus going beyond the 2015 renewable energy development strategy is allowed. For the low carbon scenarios KB4_CO2, it could have been remembered that Vietnam belongs to a club of countries vulnerable to climate change, which publicly and officially subscribed to the goal of carbon neutrality by 2050.

The five dimensions used in the multicriteria ranking miss some of the system's most desirable qualities: flexibility and finance availability. Finance availability is about the appetite of investors for different technologies. It is crucial as far as the private sector will fund most of the new infrastructure. System flexibility is the speed at which the power system responds to operation decisions for ensuring supply-demand balance.

It is crucial to the stable and secure operation of a system that integrates significant shares of intermittent energy sources, and this is already the case. It is urgent to study the role of energy storage in much more detail.

The draft PDP8 coordinates vertically with the socio-economic masterplan. It should also link horizontally with the Transport plan. The PDP8 is an opportunity to anticipate how road transport electrification will change the load curve and infrastructure requirements. Link with the Marine plan is also necessary to harmonize the location and capacity of future seaports necessary for importing fuels and for the offshore wind industry.

Within these limits, we admire the study's quality and comprehensiveness, which is totally in line with the planning logic and laws. Including external environmental costs in the calculation was an important step forward. The publication of the modelling assumptions as a technology catalogue (Jakob [START_REF] Lundsager | Vietnam Technology Catalogue -Technology data input for power system modelling in Viet Nam[END_REF] and a more open dialogue with the community of experts and stakeholders certainly improved the results' transparency and quality.

Finally, let us look at the 2025 and 2030 objectives in Table 1.

The table's top shows a 200% to 250% growth in system size, greenhouse gases and dust pollution over the next ten years. Sadly, these numbers remind us that much more change is needed to put the electricity sector on a sustainable development trajectory. The draft PDP8 points out correctly that it achieves reduction below the baseline according to the current national targets. At some point these targets will become more ambitious and switch to stabilizing CO2 emissions, before moving to carbon neutrality. This target switch may well happen before 2045, that is within the PDP8 planning horizon. Instead of reduction below a counter-factual baseline, showing the absolute numbers of environmental damage could motivate more strongly key and non-key energy users to improve energy efficiency.

Resource potential constrains hydroelectricity and biomass; they do not weigh much in the match between gas and other renewables. The case of biomass illustrates an essential point about state-owned vs private ownership of generation assets. In the Renewable Energy Development Strategy, the Government planned to create for State-owned utilities a Renewable Portfolio Standards system (RPS). The RPS system would mandate operators to source a fraction of their energy from renewable sourcesdirectly or by buying certificates from other operators who have excess renewable energy capacity. In many countries, utilities fulfilled their RPS mandate by co-firing biomass along with coal in their thermal plants.

Such constraints are more difficult to legally impose on private operators, who have been given the protection of a power purchase agreement before their Build-Operate-Transfer investment.

For coal, the PDP8 adds no new coal-fired thermal power other than those already under construction. Yet, the pipeline of projects is enough to add 9 GW between 2020 and 2025. This figure raises concerns about a strong dependence on imported primary fuels when the domestic coal and gas production remain the same or decline. According to the General Department of Customs, Vietnam imported approximately 55 million tons of coal in 2020, mainly for electricity generation. In the last five years, many coal plants projects faced difficulties and delays. It is not clear from our reading of the draft PDP8 if and how these problems will be solved. Most financial institutions, banks and insurers in the world have stopped funding new construction projects of this type in an attempt to show their commitment to the Paris Agreement 2015 to fight against climate change. The next 5-years power development plan of China, to be published later in 2021, maybe the turning point for this primary energy source.

A look at the 2025 and 2030 targets

The draft PDP8 sets to develop 18 GW of imported LNG generation capacity over the next ten years. This technology has complementarity with intermittent renewables, as gas turbines can ramp production up and down quickly. It is also possible to have long term flexibility by renting instead of building: floating regasification, storage and even generation units can be returned or moved where necessary. Analysts might have considered this real-option dimension more in the planning: LNG is not only for traditional existing power centres. The analysis also did not weigh in its multicriteria analysis the risks of macroeconomic costs and energy security issues of importing large amounts of LNG, which are essential to inform policy. Finally, the PDP8 also inherits a pipeline of delayed projects from the previous plan, mainly those using domestic gas.

It is not clear that their issues are resolved.

The draft PDP8 goals for solar power are severely outdated. The plan follows a renewable energy development strategy defined six years ago. It was ambitious at that time but needs rethinking now after the solar and wind boom. The draft PDP8 imposes that the share of renewable energy sources used to produce electricity decreases from 38% to 32% between 2020 and 2030. While the country succeeded in installing 16GW in two years, the draft restricts the sector by adding 120 MW per year until 2025. Floating solar technology technologies has not started to give their potential. Auctions can be conducted to benefit from lower prices and control the geographic location of the development -the Northern provinces are lagging when it comes to solar. And there are still millions of rooftops available.

Installed wind power capacity was about 630 MW in 2020, and the draft PDP8 aims for 11.3 GW in 2025. This is going to be outdated fast. The 2025 target is to build all projects already added in the previous masterplan, for which the deadline is the end of October this year, 2021. At the end of the year, we are likely to be in the same situation as for solar PV:

the plan objectives are achieved, now what? The 2030 target adds onshore projects currently registered but not approved, plus 2 GW of offshore wind power out of 44.6 GW of identified projects.

The bottom rows of Table 1 are about imports and storage. Both capacities are essential in the long run. The interconnects' sizes are politically determined. They are not a control variable in the PDP8. Trading electricity is not just trading kWh; it also contributes to grid stability. Connecting to a grid rich in dispatchable hydro, like Laos, will be an asset for a grid rich in must-run intermittent renewable, like Vietnam. Storage is also a requirement to integrate a high share of solar and wind. It is logical for the Power Development Plan to reconsider the storage strategy at the same time as the solar and wind targets.

In introduction, we asked if the draft PDP8 found a balance between two priorities. The answer is negative. The draft envisions gas-fired power as the backbone of the system development for the next 10 years. It practically ignores the offshore wind option, which could be a game-changer.

There is a problem with the solar and wind targets, which are outdated compared to the recent developments. Since 1975, the Vietnam energy system has followed a constant line: develop the domestic energy sources [START_REF] Hà | Seven insights for Vietnam's power sector energy transition[END_REF]. The first twenty years the focus was on hydroelectricity, then it went to domestic natural gas for ten years, and then to domestically produced coal for ten years. The solar and wind boom since 2018 is in line with this constant need to ensure energy independence. Thus, relying on importing fossil fuels goes against the long-term historical trends as much as against short term recent development.

This is more a symptom of a problem in the planning system than the outcome of well-informed political choices. The planning was not agile enough to catch up with the renewable energy boom of the last three years.

Planning is always a challenging exercise, but the conditions are the moment are unstable if not chaotic. In 2019, the new planning Law became effective in January, its application Decree was issued in May (Nguyễn Xuân Phúc, 2019), and the Prime Minister's decision on PDP8 contents was issued in October. Some technological costs are falling fast, upheaving the merit order of different options. The grid's nature changes from centralized to decentralized.

Power development accelerated. Nowadays it encompasses herding hundreds of small projects, not only planning GW-scale power plants to open years from now. The position of the State is ambiguous, as in a general move towards a market-oriented economy, the energy system remains as a national security asset with many natural monopolies. Instead of command and control, the State has to rely on indirect instruments, and the private sector is agile and fast to move when the incentives are there. Not to mention the global health and economic crisis, on top of climate change redefining energy policy.

Rational decision making remains crucial to continue the success story of the Vietnam energy system. The planning logic exposed in the introduction must evolve to new conditions. The more uncertain environment justifies the PDP8 draft's proposition to have a shorter planning cycle. Under the necessary new supervisory institutions, short term no-regrets investment could receive more attention. At the same time, the long-term strategy function of

Conclusion

the PDP should be restored. In the last years, PDP7 has not been used as a planning document but devolved as an administrative list of authorized projects. The draft PDP8 proposes a Law on Renewable Energy. This could be a venue to update the renewable energy development strategy from 2015, and update the PDP accordingly. There is a need to plan the continuous expansion of the solar PV and wind sectors, including offshore.

Image by Nikolay Shulga from Pexels

In

  February 2021, Vietnam's Ministry of Industry and Trade released the draft Power Development Plan VIII (Institute of Energy, 2021) (draft PDP8), which outlines how the country will produce its electricity for the next ten years. Under Article 12 of the Planning Law, effective 01 January 2019, regarding the public participation in the planning activities, the draft has been open for comments. This text shares a few thoughts regarding this vital discussion about keeping the lights on with high reliability at an affordable financial, social and environmental cost.This Power Development Plan, like all others, is the outcome of a rational decision analysis process. The planning logic, visible in the outline of the draft PDP8, is as follows: a. Public and private investors propose electricity production projects. Currently, about 162GW of projects is registered, disproportionally in the Central region.

  using five dimensions: Fit with current policy goals, System cost, CO2 emissions, New grid needs, Diversification. The winning candidate KB1B_CLNLTT is defined as follows (p.383-384):This scenario adopts the 2015 Renewable Energy Development Strategy goals (Nguyễn Tấn Dũng, 2015) (Decision 2068). Accordingly, the proportion of electricity produced from renewable sources (including large hydro) reaches 38% by2020, 32% in 2030 and 43% in 2050. […] This strategy is also suitable with Resolution 55(Vietnam's Politburo, 2020, 55), which stipulates the rate renewable energy sources in the total primary energy supply reach 15-20% by 2030 and 25-30% by 2045, corresponding to the proportion of electricity of renewable energy in the total electricity National production capacity of about 30% in2030 and 40% in 2045.[…] External costs of emissions are included in the cost minimization.

Figure 1 :

 1 Figure 1: Blueprint to develop the electricity system in Vietnam, PDP8 draft 3.

Table 1 : PDP8 objectives in the base case, compared to past and present trends Past Present PDP8 draft 2010 2019 2020 2025 2030 Electricity used (TWh)

 1

		85.4	210.5	216.8	335	491
	Total installed capacity (GW)	20.4*	55.9*	69.3	102.1	137.7
	CO2 emissions (Mt)			118	186	246
	PM2.5 emissions (kt)			9.450	21.312	31.707

Installed capacity by technology and energy source (GW) Hydroelectricity 8.575 20.632 20.685 24.497 25.992

	Large hydro >30 MW	17.085	19.697	19.792
	Small hydro <30 MW	3.600	4.800	5.000

Coal-fired power plants 3.941 20.267 20.431 29.523 37.323

	Domestic coal	14.281	16.841	16.941
	Imported coal	6.150	12.682	20.362

Gas/oil-fired power plants 7.846 9.070 9.030 14.055 28.871

	Domestic gas			7.097	9.054	10.636
	Imported LNG			0	4.103	18.097
	Oil			1.933	0.898	0.138
	Solar PV	0	4.696	16.640	17.240	18.640
	Wind power	0	0.377	0.630	11.320	18.010
	Onshore and nearshore			0.630	11.320	16.010
	Offshore			0	0	2.000
	Biomass & other renewable	0.049	0.325	0.570	2.050	3.150
	Imports	0	0.570	1.272	3.508	5.677
	From Laos	0	0.570	0.572	2.808	4.977
	From China	n/a	n/a	0.700	0.700	0.700
	Storage**			0	0	1.200
	Sources: PDP8 draft 3 chapter 1, chapter 6 p. 239, chapter 9 pp. 352, 354.

Notes: *Excluding import capacity from China. **Includes pumped hydro and batteries.

Định hướng phát triển đi ện gió ngoài k hơi


Siyuan Niu
email: siyuan.niu@lirmm.fr

Adrien Suau

Gabriel Staffelbach

Aida Todri-Sanial

A Hardware-aware Heuristic for the Qubit Mapping Problem in the NISQ Era

•Hardware-Aware (HA) mapping transition algorithm. •Hardware-aware Simulated Annealing (HSA) initial mapping.

•Hardware-aware get_neighbor method.

=

•Initial mapping

•{𝑞 0 → 𝑄 0 , 𝑞 1 → 𝑄 1 , 𝑞 2 → 𝑄 2 , 𝑞 3 → 𝑄 3 , 𝑞 4 → 𝑄 4 }
•SWAP candidates:

• 𝑞 1 , 𝑞 2 and 𝑞 1 , 𝑞 3 •NISQ devices.

•Connectivity constraint: Nearest-neighbor connections.

•Different physical qubits: various calibration data.

•Qubit mapping problem: Adapting a quantum program to given hardware connectivity.

•Map the most used qubit of the mapped circuit to the most connected physical qubit.

•Apply CNOT gates on qubits that are directly connected and with reliable interconnects.

•If a CNOT cannot be applied on two neighbor qubits, apply on two qubits whose distance is two. Fidelity improved by 23%.

Introduction Acknowledgement

• Comparison of number of additional gates and fidelity on IBM Q 20 Almaden (small benchmarks).

  . 𝑞 1 𝜋 𝑔. 𝑞 2 + 𝑊 × 1 𝐸 𝑔ϵ𝐸 𝐷 𝜋 𝑔. 𝑞 1 [𝜋 𝑔. 𝑞 2 ] •Distance matrix 𝐷 = α 1 × 𝑆 + 𝛼 2 × 𝜀 + 𝛼 3 × 𝑇 • S: SWAP matrix, ε: SWAP error matrix, T: SWAP execution time matrix •Selection between SWAP and Bridge gate.

  This work was supported in part by the Region of Occitanie, Direction de la Recherche, du Transfert Technologique et de l'Enseignment Superieur, France, under the Grant "Quantum CAD", in part by a Research Collaboration Grant between TOTAL, LIRMM, and CERFACS, and in part by the QuantUM Initiative of the Region Occitanie, University of Montpellier, and IBM Montpellier.

  𝑞 1 , 𝑞 2 because of the lower error rate. •Final mapping •{𝑞 0 → 𝑄 0 , 𝑞 1 → 𝑄 2 , 𝑞 2 → 𝑄 1 , 𝑞 3 → 𝑄 3 , 𝑞 4 → 𝑄 4 } Number of additional gates improved by 30%. • Comparison of number of additional gates on IBM Q 20 Almaden (large benchmarks). Number of additional gates improved by 32%.


Michiel Postema

Ayache Bouakaz

Chien Ting

Nico De Jong

REAL-TIME OPTICAL IMAGING OF INDIVIDUAL MICROBUBBLES IN AN ULTRASONIC FIELD

In this study we analyze the behavior of individual experimental ultrasonic contrast bubbles, insonofied by 500 kHz ultrasound, at acoustic pressures between 0.06 and 0.66 MPa. The oscillations were observed under a microscope with a fast framing camera. It is concluded that apparently identical bubbles can expand to different maximal diameters.

I. INTRODUCTION

We investigated an experimental ultrasonic contrast agent (UCA), supplied by Bracco Research SA, Geneva, Switzerland. It consists of phospholipidencapsulated sulfur hexafluoride gas bubbles ranging in diameter from 1 to 6 µm with a median of 2 µm. The acoustic behavior of the contrast agent was modeled and described by [1]. In this study we did optical observations, recorded with a fast framing camera, of UCA bubbles insonofied by 500 kHz ultrasound at peak negative acoustic pressures between 0.06 and 0.66 MPa. The observations were done with a two-dimensional fast framing camera, as described by [2].

II. OPTICAL CONSIDERATIONS

The optical observations show oscillating contrast bubbles. The oscillating behavior was studied by measuring bubble sizes from the optical images. The optical system was studied, to determine the relation between the observed bubble size and the true bubble size.

An image observed through a microscope is the convolution of the true object image and the pointspread function of the optical imaging system. Our optical system had an objective lens with a focal length of 0.8 mm and an aperture of 1.5 mm. Its point-spread function was computed using the Rayleigh integral[3], for a wavelength of 500 nm. The theoretical threshold to be used in automatic bubble segmentation for size measurements is 50% of the intensity value between foreground (bubble) and background. This was validated for bubbles larger than 0.4 µm by measurements on simulated images, obtained by convolving the point-spread function with different shapes. The intensity gradient between foreground and background is steepest (the contrast between foreground and background is highest) when in focus, as was expected from forward modeling. Lateral distance (µm) 8-bit gray-value cross-section

III. SETUP

The contrast bubbles were insonofied using a singleelement transducer, spherically focused at 75 mm, transmitting 10 cycles of 500 kHz. The amplitude of the signal was adjusted by attenuators and a linear power amplifier. Acoustic pressures applied were measured with a calibrated hydrophone at the site of interest.

The transducer was mounted in a Perspex container at an angle of 45º relative to the top of the container, as shown in figure 2. This container was filled with water. Into the container a Ø 200 µm capillary fiber was placed in the focus of the transducer. Contrast fluid (5ml of a 0.9% NaCl dilution added to a 25 mg vial) was inserted through this capillary fiber.

Figure 2: Front-side view of container

The Perspex container was positioned beneath a microscope with a 100´ objective lens. On top of the microscope a 100 MHz fast framing CCD camera was placed.

The camera was computer controlled. The first frame was taken a few microseconds before ultrasound arrival. The other seven frames were taken during ultrasound insonofication, with 330 ns interframe time for 500 kHz ultrasound, spanning a full ultrasound cycle. Frame exposure times ranged from 10 ns to 70 ns.

IV. SEGMENTATION AND ERROR CALCULATION

Bubble diameters were measured with a semiautomated segmentation program, using the 50% threshold between foreground and background described in the previous section.

From each binary-segmented image, the size of an enclosed area representing a bubble was measured.

From this area the bubble diameter was calculated.

The dependence of bubble diameter measurement on light intensity, choice of region of interest, channel and multi channel plate amplification, was calculated by measuring UCA bubble diameters from image sequences without ultrasound insonofication and by measuring 1.069±0.008 µm polystyrene latex calibration spheres, using different light intensities and selecting different regions of interest. The standard deviation determined in diameters was 0.16 µm.

Based on the measurements with two-dimensional grids, we assume that diameters from bubbles that were slightly out of focus could be correctly measured with the threshold used. Bubbles that were clearly out of focus were not taken into account in this study.

V. RESULTS

In this study, 583 insonofied bubbles were subjected to an extensive analysis. Peak negative acoustic pressures applied to these bubbles ranged from 63 kPa to 856 kPa. The maximal diameters measured were normalized by the initial bubble diameters:

(dmax/dinitial)-1, indicating diameter growth.

Data from events at relatively low pressures are presented in figure 3. Relative diameter growth is plotted as a function of initial bubble diameter. The figure shows that bubbles of the same size appear to have different maxima by factors over 10.

This phenomenon was separately investigated at high peak negative pressures of 659 kPa. An example is demonstrated in figure 4, where three apparently identical UCA bubbles were selected. The initial bubble diameters as shown in the first frame are 4.11 µm, 4.12 µm and 4.26 µm, respectively. The measured amplitudes in frame 3 are 9.14 µm, 10.0 µm and 10.7 µm, respectively. The difference in maximal excursion between bubble 1 and bubble 3 is therefore roughly 30% against a 3.6% difference in initial diameters. The random errors caused by our optical system and segmentation process are within 8% of the initial bubble sizes measured for the median UCA bubble diameter of 2 µm.

We checked the representativity of the bubbles analyzed for the whole agent, by comparing the initial size distribution with a SonoVue™ distribution measured with a Coulter instrument [4]. The median diameter of 2 µm is confirmed by these measurements, but bubbles over 4 µm are hardly observed in the optical data. We conclude that our optical observations are representative in the diameter range 1 µm to 4 µm. Because the image exposure times are low relative to the interframe times, the measured maxima do not have to correspond to the true maximal bubble expansions. In worst case, if the bubble expands according to a sine, the maximal growth measured can be off the true value by half an interframing interval, which equals a twelfth expansion cycle, i.e. cos(2p/12)×100%=87% of the true excursion. Since the bubbles in the experiments shown in figure 5are closer to each other than 1% of the acoustic wavelength, acoustic differences due to location are negligible in this situation.

From the above results it is concluded that identical bubbles can have different oscillating behavior. The differences in the oscillation maxima observed can be explained by differences in shell properties of individual bubbles. Asymmetric oscillations were regularly observed at high acoustic pressures.

Mean bubble growth is plotted as a function of acoustic pressure in figure 6, from 134 bubbles with

Figure 3 :

 3 Figure 3: Relative bubble growth at three different peak negative acoustic pressures

Figure 4 :

 4 Figure 4: Optical image of 659 kPa insonofied contrast-frame 1 taken before ultrasound arrival

Figure 5 :

 5 Figure 5: Relative bubble growth at 659 kPa, where identical markers indicate bubbles from the same image sequence

  diameters between 1.8 µm and 2.2 µm. The plotted theoretical curves were calculated numerically from the models by De Jong[5] and Morgan[6] for a Ø 2 µm bubble and based on the parameters of the constant thickness model[1]. Although there is no clear fit, the Morgan model describes the maximal growth better. Jensen and N.B. Svendsen, "Calculation of pressure fields from arbitrarily shaped, apodized, and excited ultrasound transducers," IEEE Trans Ultrason Ferroelec Freq Contr, vol. 39, pp. 262-267, 1992. [4] M. Schneider, M. Arditi, M.-B. Barrau et al., "SonoVue™: A new ultrasonographic contrast agent based on sulfur hexafluoride-filled microbubbles," Invest Radiol, vol. 30, pp. 451-457, 1995. [5] N. de Jong, R. Cornet and C.T. Lancée, "Higher harmonics of vibrating gas filled microspheres: Part one: simulations," Ultrasonics, vol. 32, pp. 447-453, 1994. [6] K.E. Morgan, J.S. Allen, P.A. Dayton et al., "Experimental and theoretical evaluation of microbubble behavior: Effect of transmitted phase and bubble size," IEEE Trans UltrasonFerroelec Freq Contr, vol.47, pp. 1494-1509, 2000.

	Relative growth (dimensionless)	[3] J.A. 0.01 0.1 1 10 100
		10		100		1000
		Acoustic peak negative pressure (kPa)
	Figure 6: Mean relative growth as a function of
	acoustic pressure applied, for bubbles with diameters
	ranging from 1.8 µm to 2.2 µm, compared to Morgan
		model (--) and De Jong model (-)
		VII. ACKNOWLEDGMENTS
	We thank Leo Bekkering for making the capillary
	fibers and doing the mounting adjustments.
	This work has been supported by the Technology
	Foundation STW (RKG.5104) and the Interuniversity
	Cardiology Institute of the Netherlands.
			VIII. LITERATURE
	[1] J.-M. Gorce, M. Arditi and M. Schneider,
	"Influence of bubble size distribution on the
	echogenicity of ultrasound contrast agents: A
	study of SonoVue™," Invest Radiol, vol. 35,
	pp. 661-671, 2000.
	[2] N. de Jong, P. Frinking, A. Bouakaz et al.,
	"Optical	imaging	of	contrast	agent
	microbubbles in an ultrasound field with a 100
	MHz camera," Ultrasound in Med & Biol, vol.
	26, pp. 487-492, 2000.

*Michiel Postema e-mail: postema@tch.fgg.eur.nl