Hiba Abdallah

Quentin Mérigot

Quentin M Érigot

On the reconstruction of convex sets from random normal measurements

We study the problem of reconstructing a convex body using only a finite number of measurements of outer normal vectors. More precisely, we suppose that the normal vectors are measured at independent random locations uniformly distributed along the boundary of our convex set. Given a desired Hausdorff error η, we provide an upper bounds on the number of probes that one has to perform in order to obtain an η-approximation of this convex set with high probability. Our result rely on the stability theory related to Minkowski's theorem.

Introduction

Surface reconstruction is now a classical and rather well-understood topic in computational geometry. The input of this problem is a finite set of points P measured on (or close to) an underlying unknown surface S, and the goal is to reconstruct a Hausdorff approximation of this surface. In this article, we deal with a surface reconstruction question. However, our input is not a set of points, but a set of (unit outer) normal vectors measured at various unknown locations on S. This question stemmed from a collaboration with CEA-Leti, which has developed sensors that embed an accelerometer and a magnetometer, and can return their own orientation, but not their position. Since these sensors are small and rather inexpensive it is possible to use many of them to monitor the deformations of a known surface [START_REF] Sprynski | Surface reconstruction via geodesic interpolation[END_REF]. Can such sensors be used for surface reconstruction ? One cannot expect to be able to reconstruct a surface from a finite number of normal measurements, without assumptions on the surface or on the distribution of the points. Here, we study the case where the underlying surface is convex, and where the normals are measured at random and uniformly distributed locations.

Related work. Minkowski's theorem asserts that a convex set is uniquely determined, up to translation, by the distribution of its normals on the sphere. In the case of polyhedron, the precise statement is as follows: given a set of normal vectors n 1 , . . . , n N in the unit sphere, and a set of positive numbers a 1 , . . . , a N such that (i) N i=1 a i n i = 0 and (ii) the set of normals spans R d , there exists a convex polytope with exactly N faces and such that the area of the face with normal n i is a i [START_REF] Minkowski | Volumen und oberfläche[END_REF]. Moreover, this polytope is unique up to translation. The computational aspects related to Minkowski's theorem have been studied using variational techniques on the primal problem [START_REF] Little | Extended gaussian images, mixed volumes, shape reconstruction[END_REF] or on the dual problem [START_REF] Carlier | On a theorem of alexandrov[END_REF][START_REF] Lachand-Robert | Minimizing within convex bodies using a convex hull method[END_REF], but also from the viewpoint of complexity theory [START_REF] Gritzmann | On the algorithmic complexity of Minkowski's reconstruction theorem[END_REF].

Minkowski theorem can be interpreted as a reconstruction result, and such a result comes with a corresponding stability question: if the distribution of normals of two convex bodies are close to each other (in a sense to be made precise), are the corresponding bodies also close in the Hausdorff sense up to translation ? This question has been studied extensively in the convex geometry literature, using the theory surrounding the Brunn-Minkowski inequality, starting from two articles by Diskant [START_REF] Diskant | Bounds for the discrepancy between convex bodies in terms of the isoperimetric difference[END_REF][START_REF] Diskant | Bounds for the discrepancy between convex bodies in terms of the isoperimetric difference[END_REF][START_REF] Schneider | Convex bodies: the Brunn-Minkowski theory[END_REF][START_REF] Hug | Stability results involving surface area measures of convex bodies[END_REF]. Our probabilistic convergence theorem bears some resemblance with [START_REF] Gardner | Convergence of algorithms for reconstructing convex bodies and directional measures[END_REF], which studies a different inverse problem in convex geometry, namely reconstructing a convex set from its brightness function.

Contributions. In the present paper, we suppose the existence of an underlying convex body K, which is not necessarily a polytope, and from which a probing device measures unit outer normals. Our input data is a set of N unit normals (n i ) 1≤i≤N , which have been measured at N locations on the boundary ∂K of K. These locations have been chosen randomly and independently, and are uniformly distributed with respect to the surface area on ∂K. Note that from now on, we assume that only the measured normals are known to us, and not the locations they were measured at. The question we consider is the following: given η > 0, what is the minimum number of such measurements needed so as to be able to reconstruct with high probability a convex set L N which is η Hausdorff-close to K up to translation? Denoting d H the Hausdorff distance, we prove the following theorem:

Theorem (Theorem 4.1). Let K be a bounded convex set with non-empty interior and whose boundary has (d -1)-area one. Given p ∈ (0, 1) and η > 0, and

N ≥ const (K, d) • η d(1-d) 2 -2d log(1/p)
random normal measurements, it is possible to construct a convex body L N such that

P min x∈R d d H (x + K, L N ) ≤ η ≥ 1 -p.
In the course of proving this theorem, we introduce a very weak notion of distance between measures on the unit sphere, which we call the "convex-dual distance". This distance is weaker than usual distances between measures, such as the bounded-Lipschitz1 or the total variation distances. Surprisingly, it is nonetheless sufficiently strong to control the Hausdorff distance between two convex bodies in term of the convex-dual distances between their distribution of normals, as shown in Theorem 3.1. This theorem weakens the hypothesis in the stability results of Diskant [START_REF] Diskant | Bounds for the discrepancy between convex bodies in terms of the isoperimetric difference[END_REF][START_REF] Diskant | Bounds for the discrepancy between convex bodies in terms of the isoperimetric difference[END_REF] and Hug-Schneider [START_REF] Hug | Stability results involving surface area measures of convex bodies[END_REF].

Notation. The Euclidean norm and scalar product on R d are denoted . and . • . respectively. The unit sphere of R d is denoted S d-1 , and B(x, r) is the ball centered at a point x with radius r. We call convex body a compact convex subsets of the Euclidean space R d with non-empty interior. The boundary of a convex body K is denoted ∂K. Also, we denote H d (A) the volume of a set A, and H d-1 (B) the (d -1)-Hausdorff measure of B. These notions coincide with the intuitive notions of volume and surface area in dimension three. A (non-negative) measure µ over a metric space X associates to any (Borel) subset B a non-negative number µ(B). It should enjoy also the following additivity property: if (B i ) is a countable family of disjoint subsets, then µ(∪ i B i ) = i µ(B i ). We call µ(X) the total mass of µ. The measure µ on X is a probability measure if µ(X) = 1. The unit Dirac mass at a point x of X is the probability measure δ x defined by δ x (B) = 1 if x belongs to B and δ x (B) = 0 if not.

Minkowski problem and the convex-dual distance

The problem originally posed by Minkowski concerns the reconstruction of a convex polyhedron P from its facet areas (a i ) 1≤i≤N and unit outer normals (n i ) 1≤i≤N . This data can be summarized by a measure on the unit sphere, and more precisely by a linear combination of Dirac masses: µ P = 1≤i≤N a i δ x i . Minkowski's problem has been generalized to more general convex bodies by Alexandrov using the notion of surface area measure.

Recall that given a convex body K and a point x on its boundary, a unit vector v is a unit outer normal if for every point y in K, (xy) • v ≥ 0. For H d-1 -almost every point in ∂K, there is a single outer unit normal, which we denote n K (x). The Gauss map of K is the map n K : ∂K → S d-1 .

Definition 2.1. The surface area measure of K is a measure µ K on the unit sphere. The measure µ K (B) of a (Borel) subset B of the sphere S d-1 is the (d -1)-area of the subset of ∂K whose normals lie in B. In other words, [START_REF] Alexandrov | On the theory of mixed volumes of convex bodies[END_REF] µ

K (B) := H d-1 ({x ∈ ∂K; n K (x) ∈ B}) = H d-1 (n -1 K (B))
. By definition, the total mass µ K (S d-1 ) of the surface area measure is equal to the (d-1)-volume of the boundary ∂K. In particular, the surface area of K is a probability measure if and only if K has unit surface area, i.e. H d-1 (∂K) = 1.

For instance, if P is a convex polyhedron with k d-dimensional facets F 1 , . . . , F k , the unit exterior normal n P (x) is well defined at any point x that lies on the relative interior of one of these facets. As noted earlier, the surface area measure of the polyhedron P can then be written as a finite weighted sum of Dirac masses, µ P = N i=1 H d-1 (F i )δ n F i , where the unit normal to the ith face is denoted n F i .

Alexandrov's theorem [START_REF] Alexandrov | On the theory of mixed volumes of convex bodies[END_REF] generalizes the reconstruction theorem of Minkowski mentioned in the introduction. It shows that a convex body is uniquely determined, up to translation, by its surface area measure. It also gives a characterization of the measures on the sphere that can occur as surface area measures of convex bodies. Definition 2.2. Given a measure µ on the unit sphere S d-1 , (i) the mean of µ is the point of R d defined by mean(µ) := S d-1 xdµ K (x). The measure µ has zero mean if this point lies at the origin. (ii) we say that the measure µ has non-degenerate support if for every hyperplane H ⊆ R d , the inequality µ K (S d-1 \ H) > 0 holds. Equivalently, µ has nondegenerate support if and only its mass is not entirely contained on a single great circle of the sphere.

Theorem (Alexandrov). Given any measure µ on S d-1 with zero mean and nondegenerate support, there exists a convex body K whose surface area measure µ K coincides with µ. Moreover, this convex body is unique up to translation.

2.1. Convex-dual distance. One of our goals in this article is to refine existing quantitative estimates of uniqueness in Alexandrov's theorem. In other words, we want to be able to express the fact that if the surface area measures µ K and µ L are close to each other, then the convex bodies K and L are also close to each other. For this purpose, we introduce the convex-dual distance, a very weak notion of distance between measures on the unit sphere.

The support function of a convex body K ⊆ R d is a function h K : S d-1 → R on the unit sphere defined by the formula h K (u) := max x∈K x • u. We will use the following known fact of convex geometry, whose proof is included for convenience.

Lemma 2.3. If K ⊆ B(0, r), the support function h K is r-Lipschitz and |h K | ≤ r.
Proof. Consider u in the unit sphere, and x in K such that h K (u) = u • x. For any vector v in the unit sphere,

h K (v) = max y∈K v • y ≥ v • x = u • x + (v -u) • x ≥ h K (u) -u -v x ≥ h K (u) -r u -v .
Swapping u and v gives the Lipschitz bound. Moreover, for v in S d-1 , we get by the Cauchy-Schwartz inequality

|h K (v)| = max y∈K |v • y| ≤ v max y∈Y y ≤ r Definition 2.4. Given two measures µ, ν on S d-1 , their convex-dual distance is defined by: (2) d C (µ, ν) = max K⊆B(0,1) S d-1 h K dµ - S d-1 h K dν ,
where the maximum is taken over the set of convex bodies included in the unit ball.

The function d C defined this way is non-negative and symmetric, and it is easily seen to satisfy the triangle inequality on the space of measures on the sphere S d-1 . However, nothing forbids a priori that for general measures the distance d C (µ, ν) vanishes while µ = ν. The restriction of d C to the space of surface area measures of convex sets satisfies the third axiom of a distance, i.e. given two convex bodies K and L, the distance d C (µ K , µ L ) vanishes if and only if µ K = µ L . The proof of this fact needs additional tools from convex geometry and is postponed to Lemma 3.5.

Comparison with other distances.

There are many notions of distances on spaces of measures. In this paragraph, we compare the convex-dual distance with two of them. The total variation distance between two measures µ and ν on S d-1 is defined by d TV (µ, ν) = sup

B⊆S d-1 |µ(B) -ν(B)| ,
where the supremum is taken on all Borel subsets. The bounded-Lipschitz distance defined by the following supremum, where BL 1 denotes the set of functions on the unit sphere that are 1-Lipschitz and whose absolute value is bounded by one:

d bL (µ, ν) = sup f ∈BL 1 S d-1 f dµ - S d-1
f dν .

Lemma 2.5 shows that the convex-dual distance is the weakest of these three distances. This implies that a stability result with respect to this distance is stronger than a stability result with respect to d TV or d bL . The main advantage for using the convexdual distance over the bounded-Lipschitz distance comes from the fact that the set of support functions of convex sets included in B(0, 1) is much smaller than the set BL 1 . We will show in Section 4 the implications of this fact on the speed of convergence of random sampling.

Lemma 2.5. Given two measures µ, ν on

S d-1 , d C (µ, ν) ≤ d bL (µ, ν) ≤ const(d)d TV (µ, ν).
Proof. By Lemma 2.3, the support function h K of a convex set K contained in the ball B(0, 1) is 1-Lipschitz and |h K | is bounded by one. This implies that h K lies in BL 1 , and therefore

S d-1 h K d µ - S d-1 h K d ν ≤ d bL (µ, ν).
Taking the maximum over all such support functions gives d C (µ, ν) ≤ d bL (µ, ν). The second inequality follows from e.g. [START_REF] Dudley | Real analysis and probability[END_REF], Theorem 6.15.

Stability in Minkowski Problem

In this section, we refine existing stability results for Minkowski's problem so as to obtain a stability result with respect to the convex-dual distance between surface area measures. We rely and improve upon existing stability results due to Diskant and Hug-Schneider, using our definition of convex-dual distance and using a C 0 regularity estimate for Minkowski's problem due to Cheng and Yau.

The following stability theorem is Theorem 3.1 in [START_REF] Hug | Stability results involving surface area measures of convex bodies[END_REF], and is deduced from earlier results of Diskant [START_REF] Diskant | Bounds for the discrepancy between convex bodies in terms of the isoperimetric difference[END_REF][START_REF] Diskant | Bounds for the discrepancy between convex bodies in terms of the isoperimetric difference[END_REF], see also [START_REF] Schneider | Convex bodies: the Brunn-Minkowski theory[END_REF]. The inradius of a convex body K is the maximum radius of a ball contained in K and the circumradius is the minimum radius of a ball containing K.

Theorem (Diskant, Hug-Schneider; Theorem 3.1 in [START_REF] Hug | Stability results involving surface area measures of convex bodies[END_REF]). Let K and L be convex bodies with inradius at least r > 0 and circumradius at most R < +∞. Then, [START_REF] Carlier | On a theorem of alexandrov[END_REF] min

x∈R d d H (K + x, L) ≤ const(r, R, d)d 1/d bL (µ K , µ L ).
The main drawback for applying this theorem in the setting of geometric inference is that one makes an assumption regarding the inradius and circumradius of the underlying set K but also a similar assumption on the reconstructed set L. The second drawback is that the right-hand side involves the bounded-Lipschitz distance d bL instead of the weaker convex-dual distance d C . Our improvements to the previous stability results can be summarized as the the following theorem that obtains the same conclusions with weaker hypothesis: Theorem 3.1. Given a convex body K in R d , and for any measure µ on S d-1 with zero mean and such that d C (µ K , µ) ≤ ǫ 0 , there is a convex set L whose surface area measure coincides with µ and (4) min

x∈R d d H (K + x, L) ≤ cd 1/d C (µ K , µ),
where c and ǫ 0 are two positive constants depending on d and K only.

As we will see later, the constants in the theorem above depend on the dimension, on the weak rotundity of the surface area measure µ K , defined in the next paragraph, and on the area H d-1 (∂K). The exponent in the right-hand side of ( 4) is very likely not optimal, but the optimal exponent is bounded from below by 1 d-1 , as noted in [START_REF] Hug | Stability results involving surface area measures of convex bodies[END_REF]. The remainder of this section is organised as follows. We introduce in §3.1 the notion of weak rotundity of the surface area measure of K, and show how the lower and upper bounds on the inradius and circumradius in Diskant's theorems can be replaced by a lower bound on the weak rotundity using a lemma of Cheng and Yau. Then, we recall some known facts from the theory of stability in Minkowski's theorem in §3.2. Finally, we combine these results in §3.3 to get a proof of Theorem 3.1 3.1. Weak rotundity. In this paragraph, we use a lemma of Cheng and Yau in order to remove the assumption on the inradius and circumradius of one of the two convex sets. We call weak rotundity of a measure µ on the unit sphere the following quantity rotund(µ) := min

y∈S d-1 S d-1 max(y • v, 0)dµ(v)
Note that the positivity of rotund(µ) is equivalent to the hypothesis that µ has nondegenerate support.

Lemma 3.2. Given a measure on the sphere S d-1 , rotund(µ) > 0 if and only if for any hyperplane H ⊆ R d one has µ(S d-1 \ H) > 0.

Proof. If there was a hyperplane H = {y} ⊥ such that the support of µ is included in

S d-1 ∩ H, one would have rotund(µ) ≤ S d-1 max(x, y•, 0)dµ(x) = S d-1 ∩H max(x, y•, 0)dµ(x) = 0.
Therefore, if rotund(µ) > 0, the measure µ must have non-degenerate support.

More interestingly, Cheng and Yau [START_REF] Cheng | On the regularity of the solution of the n-dimensional Minkowski problem[END_REF] established a quantitative lower bound on the inradius and an upper bound on the circumradius of K in term of weak rotundity of the surface area measure of K. Note that in their statement, the boundary ∂K is assumed to be of class C 4 , but their proof does not use this fact and can be extended verbatim to the non-smooth case. A simpler proof of these bounds using John's ellipsoid is presented in [11, §1.1]. Proposition 3.3 (Cheng-Yau lemma). Let K be a convex body of R d . Then, the inradius r and circumradius R of K satisfy the inequalities:

R ≤ const(d) µ K (S d-1 ) d d-1 rotund(µ K ) -1 , r ≥ const(d) µ K (S d-1 ) -d rotund(µ K ) d .
The advantage of the weak rotundity of µ K over the inradius and circumradius of K is that this quantity is stable with respect to the convex-dual distance between measures on the sphere. Lemma 3.4. Let µ, ν be two measures on the unit sphere. Then,

|rotund(µ) -rotund(ν)| ≤ d C (µ, ν), (5)
µ(S d-1 ) -ν(S d-1 ) ≤ d C (µ, ν). ( 6
)
Proof. We prove Eq. ( 5) first. Given a point y on the unit sphere, let S y denote the line segment joining the origin to y. Then,

h Sy (v) = max x∈Sy v • x = max(v • y, v • 0) = max(v • y, 0). Define f µ (y) := S d-1 max(y • v, 0)dµ(v)
and define f ν similarly. As a consequence of the definition of the convex-dual distance, we obtain

|f µ (y) -f ν (y)| = S d-1 max(y • v, 0)dµ(v) - S d-1 max(y • v, 0)dµ(v) = S d-1 h Sy (v)dµ(v) - S d-1 h Sy (v)dµ(v) ≤ d C (µ, ν).
We have just shown that the uniform distance between the functions f µ and f ν is bounded by d C (µ, ν). In particular, the difference between the minimum of those functions is bounded by the same quantity, i.e. |rotund(µ)rotund(ν)| ≤ d C (µ, ν). Inequality ( 6) is obtained simply by plugging the support function of the unit ball, h B(0,1) = 1, in the definition of the convex-dual distance:

µ(S d-1 ) -ν(S d-1 ) = S d-1 h B(0,1) d(µ -ν) ≤ d C (µ, ν)
3.2. Background on stability theory. We need to introduce some tools from convex geometry in order to prove Theorem 3.1. We make use of the following representations for the volume V (K) of a convex body K and the first mixed volume V 1 (K, L) of K with another convex body L. The reader can consider these formulas as definitions. More details on mixed volumes can be found in e.g. [START_REF] Schneider | Convex bodies: the Brunn-Minkowski theory[END_REF]Chapter 5].

V(K) = 1 d S d-1 h K (u)dµ K (u) V 1 (K, L) = 1 d S d-1 h L (u)dµ K (u).
The following inequality is called Minkowski's isoperimetric inequality:

(7) V d 1 (K, L) ≥ V d-1 (K)V(L).
Equality holds in [START_REF] Diskant | Bounds for the discrepancy between convex bodies in terms of the isoperimetric difference[END_REF] if and only if the convex sets K and L are equal up to homothety and translation. With L equal to the unit ball, one recovers the usual isoperimetric inequality since then, V 1 (K, L) = 1 d H d-1 (∂K). Minkowski's inequality implies that the convex-dual distance introduced in Section 2 is indeed a distance between surface area measures.

Lemma 3.5. d C (µ K , µ L ) = 0 if and only if µ K = µ L .
Proof. The hypothesis d C (µ K , µ L ) = 0 implies that for any compact convex set M contained in the unit ball, one has (8)

S d-1 h M dµ K = S d-1 h M dµ L .
If one replaces M by λM , with λ > 0, the two sides of this equality are multiplied by λ. Thus, Eq. ( 8) holds for any convex body M , regardless of the assumption that M is contained in B(0, 1). Taking M = L in Eq. ( 8) we get

(9) V 1 (K, L) = 1 d S d-1 h L (u)dµ K (u) = 1 d S d-1 h L (u)dµ L (u) = V(L).
Combining this with Minkowski's inequality implies

(10) V(L) d = V d 1 (K, L) ≥ V d-1 (K)V(L)
. Exchanging the role of K and L, we see that the volumes of K and L agree, and the inequality (10) becomes an equality. Using the equality case in Minkowski's inequality, this implies that K and L are equal up to homothety and translation. Using again the equality of volumes of K and L, we see that the factor of the homothety has to be one. Consequently, K and L are translate of each other, and the surface area measures µ K and µ L are equal.

Minkowski's isoperimetric inequality is at the heart of Diskant's stability results. Instead of using Diskant's theorems directly, we will use the following consequence [START_REF] Schneider | Convex bodies: the Brunn-Minkowski theory[END_REF]Theorem 7.2.2]. Theorem 3.6 (Diskant, Schneider). Given two positive numbers r < R, there exists a positive constant c = const(r, R, d) such that for any pair of convex bodies K, L with inradii at least r and circumradii at most R, and

(11) ǫ := max(|V (K) -V 1 (K, L)| , |V (L) -V 1 (L, K)|),
the following inequality holds:

(12) min x∈R d d H (K, x + L) ≤ cǫ 1 d .
Note that there is one difference between the statement of Theorem 7.2.2 there and the statement given in Theorem 3.6 here however. We replace the strong assumption that the surface area measures of K and L are close in the total variation sense by a consequence of this fact, namely Eq. (7.2.6) there and Eq. ( 11) here. This weaker assumption is sufficient for the proof to work, as noted by Hug and Schneider in [12, Theorem 3.1].

Proof of Theorem

3.1. Assume that d C (µ K , µ) ≤ ǫ 0 := min( 1 2 rotund(µ K ), 1 2 µ K (S d-1 )).
Then, the stability results of Lemma 3.4 imply

0 < 1 2 rotund(µ K ) ≤ rotund(µ) ≤ 2rotund(µ K ), (13) 0 < 1 2 µ K (S d-1 ) ≤ µ(S d-1 ) ≤ 2µ K (S d-1
). ( 14)

In particular, by Lemma 3.4, the measure µ has non-degenerate support. Applying Alexandrov's theorem, there exists a convex body L such that µ = µ L . Cheng and Yau's lemma and Equations ( 13) and ( 14) imply that the inradii r K and r L of K and L are bounded from below by a constant r. Similarly, the circumradii R K and R L are bounded by a constant R. These constants r and R depend only on rotund(µ K ) and H d-1 (∂K). Now, by definition of the mixed volumes,

|V(K) -V 1 (K, L)| = S d-1 (h K -h L )dµ K ≤ S d-1 h K d(µ K -µ L ) + h L d(µ K -µ L ) . ( 15
)
Since the stability theorem we are proving is up to translations, we can translate K and L if necessary. The circumradii R K and R L are bounded by R, and we therefore assume that K and L are included in the ball B(0, R). This means that the bodies K ′ = 1 R K and L ′ = 1 R L are included in the unit ball. Note also that h L ′ = Rh L . Putting the definition of the convex-dual distance into Eq. ( 15), this gives

|V(K) -V 1 (K, L)| ≤ R S d-1 h K ′ d(µ K -µ L ) +R h L ′ d(µ K -µ L ) ≤ 2Rd C (µ K , µ L ).
The same inequality where L and K have been exchanged also holds, and this allows us to apply Theorem 3.6 with ǫ = 2Rd C (µ K , µ L ). Note that the constant that occurs in Eq. ( 12) depends on quantities that depend on rotund(K), µ K (S d-1 ) = H d (∂K) and d.

Random sampling

Let K be a convex body and µ K its surface area measure. Note that by measuring normals only, one cannot determine the area of ∂K. Therefore, we assume that K has unit surface area, i.e. µ K is a probability measure. We call random normal measurements a family of unit vectors (n i ) 1≤i≤N that are obtained by measuring the unit outer normal at N random independent locations on ∂K, whose distribution is given by the surface area on ∂K. Equivalently, the vectors (n i ) 1≤i≤N are obtained by i.i.d. sampling from the probability measure µ K . The empirical measure associated to µ K is therefore defined by the formula µ K,N := 1 N N i=1 δ n i . The main result of the article is the following theorem. Theorem 4.1. Let K be a convex body with unit surface area. Given a desired probability p ∈ (0, 1), a desired error η > 0, and given

N ≥ const (K, d) • η d(1-d) 2 -2d log(1/p)
random normal measurements it is possible to construct a convex body L N such that

P min x∈R d d H (x + K, L N ) ≤ η ≥ 1 -p.
The exponents that we obtain are N = Ω(η -5 ) in dimension two and N = Ω(η -9 ) in dimension three, and are most likely not optimal.

4.1. Zero-mean assumption. Note that even if the mean of the the empirical measure µ K,N will be close to zero with high probability, it will usually not be exactly zero. However, this is a necessary condition for the existence of a convex polytope L such that µ L = µ K,N . The following proposition shows that this equality can be enforced without perturbing µ N too much in the sense of the convex-dual distance d C . Proposition 4.2. Given any convex body K with unit surface area, and any probability measure ν on S d-1 , there exists a probability measure ν on S d-1 with zero mean such that Proof. We only deal with the case of a probability measure on a finite set ν = 1 N 1≤i≤N δ x i . The general case can be obtained using the density of these measures in the space of probability measures. Let m denote the mean of ν, i.e. m = 1 N 1≤i≤N x i . By convexity of B(0, 1), the point m always lies inside the ball B(0, 1). Moreover, by strict strict convexity of the ball, m = 1 occurs only when ν = δ m . In this case, one can check that if ν is the uniform probability measure on S d-1 then d C (ν, ν) ≤ 2. We will assume from now on that m < 1 and set ν = 1 N 1≤i≤N λa i • δ m i , where

d C (ν, µ K ) ≤ 3d C (ν, µ K ).
m i = x i -m x i -m , a i = x i -m , λ =   1 N 1≤i≤N a i   -1
.

By construction, the measure ν is a probability measure; and it has zero mean:

1 N 1≤i≤N λa i m i = 1 N 1≤i≤N λa i x i -m a i =   1 N λ 1≤i≤N x i   -λm = 0.
Second, we want to bound the convex-dual distance between ν and ν. For that purpose, we consider a convex set M included in the unit ball B(0, 1) and h M its support function. We let M be the extension of the support function to R d by the same formula M (x) = sup p∈M x • p. This function is positively homogeneous, i.e. for λ > 0, M (λv) = λ M (v). We have:

(16)

S d-1 h M (v)d(ν -ν)(v) = 1 N 1≤i≤N h M (x i ) - 1≤i≤N λa i h M x i -m a i ≤ 1 N 1≤i≤N M (x i ) -λa i M x i -m a i ≤ 1 N 1≤i≤N | M (x i ) -λ M (x i -m)|
From the first to the second line we used the triangle inequality, and from the second to the third line we used the homogeneity of . Finally, since M is contained in the unit ball, the function M is 1-Lipschitz (this follows from the same proof as in Lemma 2.3).

Combining with M (0) = 0, we get:

| M (x i ) -λ M (x i -m)| ≤ | M (x i ) -M (x i -m)| + |(1 -λ) M (x i -m)| ≤ m + |1 -λ| x i -m
Summing these inequalities, and using the definition of λ gives us [START_REF] Sprynski | Surface reconstruction via geodesic interpolation[END_REF] 1

N 1≤i≤N | M (x i ) -λ M (x i -m)| ≤ m + |1 -λ| 1 N N i=1 x i -m = m + 1 - 1 N N i=1 x i -m ≤ 2 m
We conclude using the definition of the convex-dual distance and Eqs ( 16)- [START_REF] Sprynski | Surface reconstruction via geodesic interpolation[END_REF].

Proof of Proposition 4.2. We need to show that the mean m of the measure ν is not too far from zero. Given any point x on S d-1 and K x = {x} the convex set consisting of only x, one has h Kx (v) := max z∈Kx z • v = x • v. Therefore, using the definition of the convex-dual distance and the fact that µ K has zero mean we obtain

d C (µ K , ν) ≥ S d-1 x • vdµ K (v) - S d-1 x • vdν(v)) = S d-1 x • vdν(v) = |m • v| .
Taking x = m/ m in this inequality proves that m is bounded by d C (µ K , ν). We can then apply Lemma 4.3 to construct ν. Using the triangle inequality for d C and d C (ν, ν) ≤ 2 m , we get.

d C (ν, µ K ) ≤ d C (ν, ν) + d C (ν, µ K ) ≤ 2 m + d C (ν, µ K ) ≤ 3d C (ν, µ K ).
4.2. Convergence of the empirical measure. We consider a probability measure µ on the unit sphere, and we denote by µ N the empirical measure constructed from µ, i.e. µ N = 1 N 1≤i≤N δ X i where X i are i.i.d random vectors with distribution µ. The following probabilistic statement determines the speed of convergence of µ N to µ for the convex-dual distance.

Proposition 4.4. Let µ be a probability measure on S d-1 , and µ N the corresponding empirical measure. Then, µ N converges to µ for the convex dual distance with high probability. More precisely, for any positive ǫ ≤ const(d) and any N , the following inequality holds:

(18) P [d C (µ N , µ K ) ≤ ǫ] ≥ 1 -2 exp const(d)ǫ 1-d 2 -N ǫ 2 /2 .
The proof of this proposition relies on the combination of a Theorem of Bronshtein [2, Theorem 5] with Chernoff's bound. Recall that the ǫ-covering number N (X, ǫ) of a metric space X is the minimal number of closed balls of radius ǫ needed to cover X. Let C 1 be the set of convex bodies contained in the unit ball R d , endowed with the Hausdorff distance.

Theorem (Bronshtein). Assuming ǫ ≤ ǫ d := 10 -12 /(d -1), the following bound holds:

log 2 (N (C 1 , ǫ)) ≤ const(d)ǫ 1-d 2 .
Proof of Proposition 4.4. By the theorem of Bronshtein, given any positive number ǫ smaller than ǫ d , there exists n and n convex body K 1 , . . . , K n included in the unit ball such that for any convex body M ⊆ B(0, 1) one has min 1≤i≤n d H (K i , M ) ≤ ǫ. Moreover, the number n can be chosen smaller than

(19) n = N (C 1 , ǫ) ≤ exp const(d)ǫ 1-d 2
.

We consider N i.i.d. random points X 1 , . . . , X N on the unit sphere whose distribution is given by the measure µ. For a fixed i, the support function h K i is bounded by one by Lemma 2.3, and one can apply Hoeffding's inequality to the random variables (h K i (X k )) 1≤k≤N . By definition of the empirical measure µ N , this gives (20)

P S d-1 h K i (x)dµ N (x) - S d-1 h K i dµ ≥ ǫ ≤ 2 exp(-2N ǫ 2 ).
Taking the union bound, we get

(21) P max 1≤i≤n S d-1 h K i (x)d(µ N -µ)(x) ≥ ǫ ≤ 2n exp(-2N ǫ 2 )
Now, given any convex body M included in the unit ball, there exists i in {1, . . . , n} such that the distance h Mh K i = d H (M, K i ) is at most ǫ. Thus, for any probability measure ν on the sphere,

S d-1 h K i (x)dν(x) - S d-1 h M dν ≤ S d-1 h K i -h M ∞ dν ≤ ǫ,
and as a consequence,

S d-1 h M (x)d(µ N -µ)(x) ≤ max 1≤i≤n S d-1 h K i (x)d(µ N -µ)(x) + 2ǫ. (22)
The combination of inequalities (21) and (22) imply that (23)

P(d C (µ N , µ) ≥ 3ǫ) ≤ 2 exp(log(n) -2N ǫ 2 )
Using the upper bound on n from Eq. ( 19) concludes the proof.

4.3.

Proof of Theorem 4.1. We assume first that d C (µ K , µ K,N ) is small enough, and more precisely that d C (µ K , µ K,N ) ≤ 1 3 ǫ 0 , where ǫ 0 is the constant given by Theorem 3.1. By Proposition 4.2 we can construct a probability measure µ K,N with zero mean such that d C (µ K , µ K,N ) ≤ 3d C (µ K , µ K,N ) ≤ ǫ 0 . This allows us to apply Theorem 3.1 to the measure µ K,N . There exists a convex body L N whose surface area measure µ L N coincides with µ K,N and moreover, min

x∈R d d H (x + K, L N ) ≤ cd C (µ K , µ L N ) 1 d = 3 1 d cd C (µ K , µ K,N ) 1 d .
Therefore, using Proposition 4.4, and assuming ǫ ≤ 1 3 ǫ 0 , we have

P min x∈R d d H (x + K, L N ) ≤ 3 1 d cǫ 1 d ≥ P [d C (µ K , µ K,N ) ≤ ǫ] ≥ 1 -2 exp const(d)ǫ 1-d 2 -N ǫ 2 /2 .
Finally, we set η = 3

1 d cǫ 1 d , we get P min x∈R d d H (x + K, L N ) ≤ η ≥ 1 -2 exp C • η d(1-d) 2 -N η 2d .
for some constant C that only depends on d and K, thus concluding the proof.

Special case: polyhedra

When the underlying convex body is a convex polyhedron, one can get much better probabilistic bounds on the speed of convergence. This model is quite simplistic, however, because of the assumptions that each of the measured normals must coincide with the one of normals of the underlying polyhedron. In particular, one cannot hope to extend this result to handle noise. The proof of this proposition relies on Theorem 2.1 of [START_REF] Hug | Stability results involving surface area measures of convex bodies[END_REF] and on a lemma of Devroye. Proof of Proposition 5.1. The surface area measure of K can be written as µ K = 1≤i≤k a i δ n i where the areas (a i ) sum to one. It is well-known that the empirical measure µ K,N constructed from a finitely support probability measures such as µ K converges to the probability measure µ K in the total variation distance with high probability. For instance, using Lemma 3 in [START_REF] Devroye | The equivalence of weak, strong and complete convergence in l1 for kernel density estimates[END_REF] we get (24) P(d TV (µ K , µ K,N ) ≥ ǫ) ≤ 3 exp(-N ǫ 2 /25), assuming ǫ ≥ 20k/N . Now, let ν be an instance of µ K,N such that d TV (µ K , ν) ≤ ǫ. The measure ν can be written as ν = 1≤i≤k b i δ n i , and the assumption that the total variation distance between µ K and ν is at most ǫ can be rewritten as 1≤i≤k |a ib i | ≤ ǫ. The measure Using Lemma 3.4, this inequality ensures that rotund(ν) ≥ rotund(µ K )/2 > 0. By Alexandrov's theorem, there exists a convex set L N whose surface area measure µ L N coincides with ν, and whose inradius and circumradius can be bounded in term of the weak rotundity rotund(µ K ). This allows us to apply Theorem 2.1 of [START_REF] Hug | Stability results involving surface area measures of convex bodies[END_REF] to the sets K and L N to show that (25) min where c depends on d and rotund(µ K )). This probability becomes lower than p, and the assumption in Eq (24) is satisfied, as soon as N ≥ const(d, rotund(µ K ), k) • η -2(d-1) log(1/p).

Lemma 4 . 3 .

 43 Given any probability measure ν on S d-1 with mean m, there exists a probability measure ν on S d-1 with zero mean such that d C (ν, ν) ≤ 2 m .

Proposition 5 . 1 .

 51 Let K be a convex polyhedron of R d with k facets, non-empty interior and whose surface area H d-1 (∂K) equals one. Then one can construct a convex polyhedron L N such that P( minx∈R d d H (x + K, L N ) ≤ η) ≥ 1p from N random normal measurements with N ≥ const(d, rotund(µ K ), k)•η -2(d-1) log(1/p).

Figure 1 .

 1 Figure1. Reconstruction of a unit cube from 300 random normal measurements with a uniform noise of radius 0.05. The reconstruction is obtained using the variational approach proposed in[START_REF] Lachand-Robert | Minimizing within convex bodies using a convex hull method[END_REF].

- 1

 1 x∈R d d H (K + x, L N ) ≤ const(d, rotund(µ K ))ǫ 1 dCombining Eqs (24) and (25), we getP min x∈R d d H (K + x, L N ) ≥ η ≤ P(d TV (µ K , µ K,N ) ≥ c • η d-1 ) ≤ exp(-c • N η 2(d-1) )

The bounded-Lipschitz distance coincides with the Wasserstein (or Earthmover) distance with exponent one when the two measures have the same total mass.

Acknowledgements. The authors would like to acknowledge the support of a grant from Université de Grenoble (MSTIC GEONOR) and a grant from the French ANR (Optiform, ANR-12-BS01-0007). The authors would also like to thank the members of the associated team ECR Géométrie et Capteurs CEA/UJF between LJK-UJF and CEA-LETI bringing up this problem to their attention.

Discussion

In this article, we introduced the convex-dual distance between surface area measures. This distance is weaker than the bounded-Lipschitz distance and is yet sufficient to control the Hausdorff distance between convex bodies in term of the distance between their surface area measures. This stability result has then been used to deduce probabilistic reconstruction results (Theorem 4.1). The main open problem consists in improving the exponent in the lower bound on the number of samples in this theorem.

What would happen if we would have used the bounded-Lipschitz distance in the probabilistic part of the proof of Theorem 4.1 instead of the convex-dual distance? The lower bound on the number N of necessary normal measurements to get a Hausdorff error of ǫ in the reconstruction would increase substantially:

In particular, the exponents would become N = Ω(η -6 ) in dimension two and N = Ω(η -12 ) in dimension three, compared to N = Ω(η -5 ) and N = Ω(η -9 ) with our analysis. This difference is due to the fact that the space BL 1 of functions on S d-1 that are 1-Lipschitz and bounded by one is much larger than the space C 1 of support function of convex sets included in the unit ball. More precisely,

where the constants in the Θ(.) notation only depend on the ambient dimension. It is therefore tempting to pursue in this direction, and to try to consider a weaker dual distance between surface area measures, i.e. defined with an even smaller space of functions. This idea is not hopeless, as if one looks closely at the proofs of Theorem 3.1, Lemma 3.4 and Proposition 4.2, there are only a handful of probing functions that are used to control the Hausdorff distance between two convex bodies K and L as a function of their surface area measures µ K and µ L , and more precisely,

where s u : x → u • x. This set of function is exponentially much smaller than the set of support functions of convex bodies included in the unit ball:

However, turning this remark into an improvement of the probabilistic analysis seems quite challenging, because in the probabilistic setting, the second convex body L N is reconstructed from random normal measurements and is itself random.


Flavio Pressacco

Giacomo Plazzotta

Laura Ziani

Twin relationships in Parsimonious Games: some results

Keywords: incidence matrices, twin relationships, minimal winning quota, balanced lottery

come

Introduction

In this paper we present some results concerning twin relationships in Parsimonious games (henceforth P games). P games are the subset of constant sum homogeneous weighted majority games characterized by the parsimony property to have, for any given number n (> 3) 1 of non dummy players in the game, the smallest number, i.e. exactly n, of minimal winning coalitions. P games have been defined and studied by Isbell in a vintage paper ( [START_REF] Isbel | A class of majority games[END_REF], 1956) where the special properties of this class of games are described. Among other things Isbell introduced a twin relationship on P games, but without deepening the point, which at the best of our knowledge did not receive any further attention in the relevant literature.

To understand the twin relationship it is convenient to recall that its premise is the existence of a general rule that drives the one to one correspondence that obviously exists between the set of players and the set of minimal winning coalitions of any P game. In turn this correspondence comes out from the following idea: keeping account of the minimal homogeneous representation of a given P game, divide the players in h groups (2 ≤ h ≤ n -2) so as all members of the same group (of the same type) share the same individual weight. Order players j = 1, . . . , n and types t = 1, . . . , h according to a non decreasing (for players) or a strictly increasing (for types) weight convention. In particular, players of the group with minimum weight (type 1) may be called "peones", those of type h -1 "vice-top" and the player (of group h) with greatest weight "top player". In any P game there are lower bounds on the number of peones and of vice top and a binding constraint on the top class: indeed there is just one top player.

Let us shortly call odd (respectively even) players, those whose type is odd (even). After that, the one to one correspondence is described by the following rules: to any non top player there is associated the minimal winning coalition made by that player and all players of alternative parity and greater weight, whereas the coalition made by all odd players (which may include or not the top player) is associated to the top player. Note that, in this way, also the set of minimal winning coalitions is divided in h groups and, matching the type order of players and associated coalitions, that the numerousness x t of type t players is equal to the one of type t minimal winning coalitions. All these results imply a special structure of the incidence matrix upon minimal winning coalitions of a P game, i.e. the square n dimensional binary matrix A whose elements a ij are 1 if column player j belongs to the row minimal winning coalition i (or S i ), and 0 otherwise. In particular the square submatrix M , obtained from A by deleting the last row and column, is block diagonal upper triangular. The diagonal blocks of M are x t dimensional diagonal square matrices, rectangular blocks over the diagonal alternate matrices with all elements equal to one to null matrices, while by definition all the entries under the diagonal blocks are zero.

This special structure inspired Isbell in recognizing that the transposed A T of the incidence matrix A of any "primal" game G should still be the incidence matrix of a P game G to be called twin (dual in Isbell terminology) of G. In other words a couple of P games are twins if and only if each incidence matrix of the couple is obtained by transposition of the incidence matrix of the twin2 .

Our contribution in this paper is embedded in a couple of theorems regarding twins. The first result says that twins have the same minimal winning quota, and is a straightforward corollary of a theorem regarding the determinant of the incidence matrix of any P game. The theorem states that the absolute value of the determinant is the minimal winning quota of the game.

The second theorem regards the connection between the balanced lottery on minimal winning coalitions of a P game and the individual weights of its twin. To understand the point suppose that the following three-stage mechanism is adopted to fix a fair and stable result for a P game, avoiding lengthy and may be unsatisfying negotiations between players. In the first stage the probabilities driving a lottery on the set of minimal winning coalitions are fixed. In the second stage the lottery mechanism makes the choice of one minimal winning coalition and in the third the (normalized to one) global reward of the game is divided within players of the chosen minimal winning coalition. In order to grant ex post fairness, in this stage individual rewards are proportional to individual weights.

We define balanced 3 a lottery that gives to all players the same (ex ante) probability to be a member of the chosen minimal winning coalition. Clearly a balanced lottery adds ex ante to ex post fairness: indeed it is easy to check that (given the ex post mechanism of reward) only under a balanced lottery the expected gain of each player is exactly his (normalized) individual weight. A question immediately arises: any P game admits (may be just one) balanced lotteries? The answer is positive: our second fundamental theorem shows that for any P game there exists just one balanced lottery which is given by the normalized and properly reordered set of individual weights of its twin. Precisely the balanced probabilities of type t coalitions in the game G are, for any t but the top one, the normalized weights of type h -t players in the twin G, while the probability of the coalition associated to the top player is just the normalized weight of the top player in G. The transposition properties of incidence matrices play a decisive role also in the proof of this result. The plan of the paper is as follows. In section 2 a short recall of the basics of constant sum homogeneous weighted majority games is offered; section 3, divided in three subsections (one to one correspondence between players and minimal winning coalitions; the special structure of the incidence matrix of a P game; the transposition approach to the twin relationships in P games) resumes fundamental results on P games 4 . Section 4 (minimal winning quota in twin games) and 5 (balanced lotteries and twin games) give proofs of our main theorems on twin games. Some examples are offered in section 6. Conclusions follow in the final section 7.

Basics on homogeneous weighted majority games

Let us recall some well known basic definitions.

As usual N = {1, . . . , n} denotes the set of all (non dummy) players. A coalition S is a subset of the set N . A game G in coalitional function form is defined by the coalitional function of the game, that is the real function v : P(N ) → R.

A game in coalitional function form is simple if its v function has values in {0, 1}. A coalition S is winning if v(S) = 1, losing if v(S) = 0.

A simple game is constant sum if, for any S ∈ P(N ), v(S) + v( S) = 1.

A coalition S is said to be minimal winning if v(S) = 1 and, for any T S, v(T ) = 0. The set of minimal winning coalitions is denoted by W M . A player j who does not belong to any minimal winning coalition is said dummy; at the other extreme, it is a dictator if it is v(j) = 1. We will consider games free of dictator and dummies.

A simple, weighted majority game is described by a representation (q; w) where w is a vector (w 1 , w 2 , . . . , w n ) of positive weights, q > 1 2 • w(N ) = 1 2 • j∈N w j is the winning quota and v(S) = 1 ⇔ w(S) = j∈S w j ≥ q.

A representation (q; w) of a weighted majority game is homogeneous if w(S) = q for any S of W M . Homogeneous weighted majority games are games for which (at least) a homogeneous representation exists.

Consider now the class of all simple, constant sum n person homogeneous weighted majority games 5 .

ization, a balanced lottery on a P game has the property to balance the set of minimal winning coalitions of the game. 4 Such results may be found in Isbell paper or are straightforward consequences of his work. 5 At the origins of game theory, homogeneous weighted majority games (h.w.m.g.) have been introduced in [START_REF] Neumann | Theory of games and economic behaviour[END_REF] by Von Neumann-Morgenstern and have been studied mainly under the constant sum condition. Subsequent treatments in the absence of the constant sum condition (with deadlocks) may be found e.g. in [START_REF] Ostmann | On the minimal representation of homogeneous games[END_REF] by Ostmann, who gave the proof that any h.w.m.g. (including non constant sum ones) has a unique minimal homogeneous representation, and in [START_REF] Rosenmüller | Homogeneous games: recursive structure and Mathematics of Operations Research[END_REF]. Generally speaking, the homogeneous minimal representation is to be thought in a broader sense but hereafter the restrictive application concerning the constant sum case is used.

Proposition 2.1. All games of such a class admit a minimal homogeneous representation, that is a (homogeneous) representation (q; w) such that all weights are integers, there are players with (minimum) weight 1 and q = 1+w(N )

2

, which implies for any S ∈ W M , w(S) -w( S) = 1.

Hereafter we will suppose that in such a representation the vector w is ordered according to the convention w 1 = 1, w j ≤ w j+1 for any j.

Proposition 2.2. The cardinality of the W M set of our class may be either greater or equal (but not lower) than n. See [START_REF] Isbel | A class of majority games[END_REF], p. 185. Definition 2.1. We call Parsimonious games (hereafter P games) the subset of constant sum homogeneous weighted majority games characterized by the parsimony property to have for any given number n of non dummy players in the game the smallest number, i.e. exactly n, of minimal winning coalitions.

As said before, general properties of P games have been studied by Isbell. A recall of such properties is given in the next section divided in three subsections devoted respectively to:

a The one to one correspondence between players and minimal winning coalitions b The incidence matrix upon winning minimal coalitions of a P game c The transposition approach to the twin relationship in P games 3 Main results on Parsimonious games

One to one correspondence between players and minimal winning coalitions

Let us recall that in any n person P game there are h (2 ≤ h ≤ n -2) types; players of type t share, in the minimal homogeneous representation, a type weight w t and the ordering of types satisfies w t < w t+1 . As said in the introduction, odd (even) players are those of type t odd (even). Let us denote by x t the numerousness of players of type t and give the following: Definition 3.1. Let G be a P game with h types; the type representation of G is the vector x = (x 1 , . . . , x t , . . . , x h ), while the free type representation f x = (x 1 , . . . , x t , . . . , x h-1 ) is the one obtained by deleting its last component x h .

The main Isbell result ([3], p. 185, penultimate indent) was that Proposition 3.1. In all P games the one to one correspondence between players and minimal winning coalitions is described by a unique general rule. Precisely, to any non top player (of type t < h) there corresponds the coalition made by that player and all players of alternative parity and greater weight; to the top player the coalition made by all odd players (which may or not include the top player).

Keeping account that all minimal winning coalitions share the same minimal winning quota and hence the same sum of individual weights, the following consequences of the general rule are straightforward for the sequence of type weights:

w 1 = 1 initial condition (3.1a) w 2 = x 1 • w 1 = x 1 (3.1b) w t = x t-1 • w t-1 + w t-2 , t = 3, . . . , h -1 (3.1c) w h = (x h-1 -1) • w h-1 + w h-2 (3.1d) Hence Proposition 3.2.
In any P game with h types the weights of all types are unequivocally given as the recursive implicit function (3.1) of the free type representation f x = (x 1 , . . . , x t , . . . , x h-1 ).

Moreover

Proposition 3.3. To preserve strict monotony of the sequence of type weights, the type representation needs to satisfy, in addition to the binding constraint x h = 1, the lower bounds:

x 1 > 1 (otherwise w 2 = w 1 = 1) and x h-1 > 1 (otherwise w h = w h-2 ).
No other constraints hold ([3], p. 185).

In the next section we will exploit also the following relations ([3], p. 186, first indent) between type weights of the players: for t odd:

w t = 1 + s even<t x s • w s (3.2a)
for t even:

w t = s odd<t x s • w s (3.2b)
Formula (3.2a) comes from the minimal winning character of the coalitions made by one of the peones and all even players and, respectively, by one player of type t (odd) and all even players of greater weight; formula (3.2b) from the minimal winning character of the coalitions made by all odd players and, respectively, by one player of type t even and all odd players of greater weight. Hence Proposition 3.4.

q = 1 + s even x s • w s = s odd x s • w s (3.3) w(N ) = 1 + 2 • s even x s • w s = 2 • s odd x s • w s -1 (3.4)
3.2 The structure of the incidence matrix of a P game

The incidence matrix A upon minimal winning coalitions of a P game is the square binary n × n matrix obtained through an association of players to columns (in order of non decreasing weights), and of minimal winning coalitions to rows (in the order induced by the one to one correspondence explained in the previous subsection) and putting a ij = 1 if player j is a member of the minimal winning coalition i (or S i associated to player i), and a ij = 0 otherwise. The square submatrix M obtained from A by deleting the last row and the last column turns out to be a matrix with a special structure.

Denoting by B r,c , with r, c = 1, . . . , h -1 the block (dimension x r × x c ) associated to coalitions of type r and players of type c, it turns out that: Proposition 3.5. Diagonal blocks (r = c) are square identity matrices; Proposition 3.6. Those with c < r < h, i.e. under the diagonal, are rectangular null matrices; Proposition 3.7. Those with r < c < h are rectangular with elements identically equal to 1(0) if (r + c) is odd (even).

Moreover keeping in consideration also the last row and column of A there are other blocks with one or both r, c equal to h: Proposition 3.8. For c = h the elements of the blocks are still identically equal to 1 (0) if (r + c) is odd (even); Proposition 3.9. For r = h the elements are identically equal to 1 (0) for c odd (even).

As we shall see in next sections, the incidence matrix is a helpful tool to study a P game and in particular the connections between twin P games.

Twin relationships in P games

The special structure of the incidence matrices of P games inspired Isbell ([3], p. 185, last indent) in recognizing an important property embedded in the following: Proposition 3.10. The transposed A T of the incidence matrix of any (primal) P game G is still the incidence matrix of a P game G, to be seen as the twin (dual in Isbell terminology) of G.

Remark 3.1. It is important to underline that in A T the association of all non top players to columns and of the corresponding minimal winning coalitions to rows holds just in the reverse order (from the last but most powerful in the game to the least powerful) than the standard one (which goes from the least powerful to the last but most powerful). In more detail in A T for any t = 1, . . . , h -1 and r < h the block indexed B r,t is associated to the set of players of type h -t and to coalitions of type h -r in G; only the last column still remains associated to the top player (for r < h B r,h concerns coalitions of type h -r and the top player in G) and the last row to the coalition corresponding to the top player (for r < h B h,r concerns players of type h -r and the coalition of type h in G). Remark 3.2. For all t < h the number of players (and of the associated coalitions) of type t in G is the number of players (and of the associated coalitions) of type h -t in G.

Hence, more formally: Proposition 3.11. M T , the transposed matrix of the submatrix M (of A), should be the incidence submatrix M of another P game G, but now with M block diagonal lower triangular with ordering of coalitions and players inverted (i.e. non increasing) with respect to that of M . To obtain A complete the transposition of the last row and column.

If we now wish to recover the standard ordering in A, we should transform A T in the following way to obtain a modified transposed A τ : at first rewrite all rows of A T inverting the order of all but the last entry in each row, then rewrite all columns inverting the order of all but the last entry in each column. It turns out that:

Result 3.1. a T i,j = a τ n-i,n-j for any i, j < n a T i,j = a τ n-i,n for any i < n a T n,j = a τ n,n-j for any j < n a T n,n = a τ n,n (3.5)
After these modifications A τ turns out to be the incidence matrix A of G coherent with the standard ordering convention of players and coalitions. To understand the point see also the examples in section 6.

We signal that an alternative, easier and more immediate understanding of the connection between a couple of twin P games, is given6 through their free type representations and is resumed by: Proposition 3.12. For any t = 1, . . . , h -1,

x t = x h-t .
The proposition says that a couple of twins share the same value of n and h and that their free type representation vectors are each other symmetric. [START_REF] Montero | Proportional payoffs in majority games[END_REF] The minimal winning quota in twin P games

In this section we will show that: Theorem 4.1. Let G, G be any couple of twin P games and q and q their minimal winning quotas; then q = q. Theorem 4.1 is a straightforward corollary of the following theorem linking the minimal winning quota and the determinant of the incidence matrix of any P game: Theorem 4.2. The incidence matrix A of any P game G with h types and minimal winning quota q is non singular and its determinant is |A| = (q) • (-1) h+1 .

Proof. Let us denote by a i , i = 1, . . . , n the row vectors of A. Recalling that the submatrix M is upper triangular, we wish to transform A in a triangular matrix T (A) with elements t ij by adding to its last row a proper linear combination i=1,...,n-1 z i a i of the rows of M . This would clearly imply that:

Proposition 4.1. |T (A)| = |A| = t nn
We prove now:

Proposition 4.2. The coefficients of such a linear combination are given by

z i = (-1) t • w i if the coalition i (of type t) is associated to a player i of type t.
To check that Prop. 4.2 holds we must verify that the elements of the last row of T satisfy:

t nj = i=1,...,n-1
(-1) t w i • a ij + a nj = 0 for any j = 1, . . . , n -1 (4.1a)

t nn = i=1,...,n-1 (-1) t w i • a in + a nn = (q) • (-1) h+1 for j = n (4.1b)
We now give the proof of equation (4.1a).

Proof. As a consequence of Propositions 3.5, 3.6, 3.7, 3.9 of section 3.2, a null vector for the first n -1 components of the row vector t n is obtained if and only if the following relations hold: 0<s even<t

x s • z s + z t + 1 = 0 for columns of type t < h odd (4.2a) 0<s odd<t

x s • z s + z t + 0 = 0 for columns of type t < h even (4.2b)

Then, starting from t = 1, recursively:

z 1 = -1 = -w 1 by (3.1a)
for t = 2:

x 1 • z 1 + z 2 = 0; z 2 = x 1 • w 1 = w 2 by (3.1b)
for t = 3:

x 2 • z 2 + z 3 + 1 = 0; z 3 = -(1 + x 2 • w 2 ) = -w 3 by (3.2a)
for t = 4:

x 1 • z 1 + x 3 • z 3 + z 4 = 0; z 4 = (x 1 • w 1 + x 3 • w 3 ) = w 4 by (3.1b)
and, by immediate induction on t, z t = -w t for t odd and z t = w t for t even.

We give now the proof of equation (4.1b).

Proof. Suppose (4.1a) holds and consider at first an even h; then (by Proposition 3.8) a in = 1 for all coalitions i of odd type (odd t) and 0 for all coalitions of even type, while (by Proposition 3.9) a nn = 0, and we have

t nn = i=1,...,n-1 (-1) t w i • a in + a nn = -(x 1 • w 1 + x 3 • w 3 + . . . + x h-1 • w h-1 ) (4.3)
Formula (4.3) gives t nn as the opposite of the sum of the weights of all odd players, which is the total weight q of the minimal winning coalition associated to the top player.

Hence t nn = -q = (q) • (-1) h+1 . On the other side, if h is odd a nn = 1 and a in = 1 for all even t and we have:

t nn = i=1,...,n-1 (-1) t • w i • a in + a nn == (x 2 • w 2 + x 4 • w 4 + . . . + x h-1 • w h-1 ) + 1 (4.4)
Then (4.4) gives t nn as the sum of the weights of all even players and one of the players with minimum weight, which is the total weight q of a minimal winning coalition associated to one peone. Hence t nn = q = (q) • (-1) h+1 and the proof of Theorem 4.2 has been completed.

After that Theorem 4.1 follows immediately from the chain:

(q) • (-1) h+1 = |A| = |A T | = |A| = (q) • (-1) h+1
5 Balanced lotteries and twin relationships in P games Definition 5.1. A lottery on a n person P game G is a probability distribution on the minimal winning coalitions of G, i.e. a column vector p = (p 1 , . . . , p j , . . . , p n ) with p j the probability assigned to the minimal winning coalition S j .

Definition 5.2. A balanced lottery on G is a lottery p which assigns to all players the same probability π to be a member of the minimal winning coalition selected by the lottery. Hence and more formally a balanced lottery should satisfy:

p T • A = π • 1 T
The following results connect balanced lotteries and twin relationships in P games.

Theorem 5.1. Let G and G be a couple of twin games. There exists just one balanced lottery p on G; its probabilities are given by the normalized individual weights of the twin G according to the following rule:

p j = w n-j /w(N ) for j = 1, . . . , n -1 (5.1a)
p n = w n /w(N ) (5.1b) while π = q/w(N ) = q/w(N ) (5.2)
Proof. By definition 5.2 a balanced lottery p on G must satisfy

p T • A = π • 1 T (5.3)
while by Prop. 3.10:

Aw = A T w = q1 (5.4)
Exploiting non singularity and hence invertibility of A, multiply (5.3) and (5.4) respectively by A -1 and (A T ) -1 to obtain:

p T = π1 T A -1 or p = π(A -1 ) T 1 (5.5) w = q(A T ) -1 1 (5.6) Being (A -1 ) T = (A T ) -1 it is: π -1 p = q -1 w (5.7) so as: p = π q w (5.8)
Premultiplying both sides of (5.8) by 1 T we obtain

1 T p = 1 = π q 1 T w = π q w(N ) (5.9) or π q = 1 w(N ) (5.10)
and finally, by Theorem 4.1

π = q w(N ) = q w(N ) (5.11)
which proves (5.2) and p = 1 w(N ) w (5.12) which gives the probability vector of the balanced lottery, which is unique thanks to the non singularity of A.

To understand the behaviour of the first n -1 components of the vector p, given in Theorem 5.1, recall that by Prop. 3.11 the ordering of coalitions and players in A T (in G) is, except for the coalition associated to the top player, reversed respect to the one in A (in G); this implies that, for such coalitions, the probability assigned to a coalition of type t (in G) is the (normalized) weight of a player of type h -t in G.

We conclude this section with:

Proposition 5.1. If the division of payoffs among members of a minimal winning coalition is proportional to their individual weights (in such a coalition), the balanced lottery gives to each player in the game G an expected payoff proportional to her individual weight in G (and not in G!).

We wish to underline here that the rationality of the formation of a minimal winning coalition, with division of payoff among its members proportional to their individual weights, goes back to the early stage of n person game theory in coalitional form; in particular, for P games the set of n "imputations" generated by this logic are a stable set solution a la Von Neumann-Morgenstern of the P game G 7 .

The proof of the Prop. 5.1 is immediate as the expected reward E(j) for any player j is given, keeping account of (5.10), by: E(j) = (w j /q)π = (w j /q)(q/w(N )) = (w j /w(N )) (5.13) In this way both expected payoffs and actual payoff division are proportional to the weights of the minimal homogeneous representation of the game. We could say that ex ante and ex post fairness are reconciled. We recall that this result is similar to the one proposed by Montero [START_REF] Montero | Proportional payoffs in majority games[END_REF] and Montero-Vidal Puga [START_REF] Montero | Demand bargaining and proportional payoffs in majority games[END_REF] as the outcome of a more sophisticated model of bargaining.

Some examples

Ex. 1 Let G be the nine person P game with minimal homogeneous representation given by: 26; 1, 1, 1, 3, 4, 4, 11, 11, 15 7 As well known [START_REF] Neumann | Theory of games and economic behaviour[END_REF] a stable set solution is a set V of imputations such that: there is no dominance among imputations of V , and any imputation not in V is dominated by at least one imputation of V .

The incidence matrix A of G is then:

A =                    
1 0 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1

1 1 1 0 1 1 0 0 1                    
The transposition of A gives the following incidence matrix A of the game G, the twin of G, whose minimal homogeneous representation is 26; 1, 1, 2, 2, 5, 7, 7, 7, 19,

A = A T =                    
1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 1 0 0 1

1 1 1 0 1 1 1 0 0 1 1 1 0 1 1 0 1 0 0 0 0 1 0 0 1 1 1                    
Note that in this matrix the ordering of all players, but the top, on columns and of the corresponding coalitions on rows is reversed with respect to the standard one; for example, the first block of three rows corresponds to the three coalitions of type t = 4 in the game G; such coalitions are formed by a vice top player of type 4 and by the top player.

If we wish to have A in the form coherent with the standard ordering of players and coalitions we modify A T into the modified transposed A τ :

A = A τ =                     1 0 1 1 0 1 1 1 0 0 1 1 1 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1                    
It is immediate to check that G and G have the same minimal winning quota q = q = 26. The balanced lottery on G is given, according to (5.1a) and (5.1b) by the vector: (7/51, 7/51, 7/51, 5/51, 2/51, 2/51, 1/51, 1/51, 19/51) Then, for example, the balanced lottery gives probability 7/51 to the coalition formed by one of the peones, the player with weight 3 and both the last but top players.

Conversely, the balanced lottery on G is given by ( Ex. 2 Let G be the nine person P game with minimal homogeneous representation given by: 25; 1, 1, 1, 3, 4, 7, 7, 7, 18

The incidence matrix A of G is then:

A =                     1 0 0 1 0 1 1 1 0 0 1 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 1                    
The transposition of A gives the following incidence matrix A of the game G, the twin of G, whose minimal homogeneous representation is still 25; 1, 1, 1, 3, 4, 7, 7, 7, 18:

A T =                     1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 0 1 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 1 1 1 1                    
Note that G and G have the same minimal homogeneous representation, which reveals that they are the same game, even if, at first sight, it seems different from A. Really the difference is not substantial as it comes merely from the reversion of the order of non top players and associated coalitions.

The identity between G and G is recovered once we compute A τ .

A τ =                     1 0 0 1 0 1 1 1 0 0 1 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 1                    
It is immediately checked that the A τ version of A is equal to A, which confirms that G = G, as revealed also by the bilateral symmetry of the representation vector f x or by the coincidence of f x and f x both equal to (3,1,1,3).

To resume we could say that Proposition 6.1. G and G are coincident (are the same game) if there is equality between: a) A and the A τ version of A or b) between the free type representations f x and f x or c) between the minimal homogeneous representations (q, w) and (q; w).

On the contrary, the formal equality between A and the A T version of A is not a necessary condition for the coincidence between G and G, except for games G with only two types (h = 2).

Concerning this point the following result holds: Proposition 6.2. The incidence matrix A of any P game G with h = 2 types of players satisfies A = A T = A τ . Hence for such games surely G = G.

The proof is immediate keeping account that no reversion of the order of non top players (and associated coalitions) is possible when h -1 = 1, while all but the last entries of the last row and the last column are 1; the same information comes from the bilateral symmetry of f x which implies equality of f x and f x.

Finally the balanced lotteries on both G and G are given by :

Conclusions

In his smart treatment of Parsimonious games, going back to the early stage of game theory development, Isbell introduced a twin relationship, which at least at our knowledge, did not find any further investigation in relevant literature.

Looking carefully at the properties of twin games and signalling preliminarily that twins have free type representation vectors which are each other symmetric, we show in this paper that a) twin games have the same minimal winning quota and b) any P game has just one balanced lottery, given by the (properly normalized and reordered) vector of individual weights of its twin.

Our paper is purely theoretical and we do not discuss here any application of our results; yet we feel confident that, keeping account of the prominent role played by symmetry in the design of the universe, applications of symmetric properties in hard as well as in social sciences may be found so that this could be a promising road for future research 8 .

7/25, 7 /

 7 25, 7/25, 4/25, 3/25, 1/25, 1/25, 1/25, 18/25 More generally it is obvious that: Proposition 6.3. A pair G and G of identical twin games have the same balanced lottery, while not identical twins G and G have the same minimal winning quota but different balanced lotteries.

  Note the extreme low probability (1/51) given in both games to the coalitions formed by the top and by one of the last but top players.

	11/51, 11/51, 4/51, 4/51, 3/51, 1/51, 1/51, 1/51, 15/51)

As we shall see later (Prop.

3.12) an alternative fully equivalent definition of twins could be based on the symmetry of the free type representations of twin games.[START_REF] Isbel | A class of majority games[END_REF] Generally speaking, a given set of m coalitions S = (S1, . . . , Si, . . . , Sm) is balanced if there exists a positive m-dimensional vector d such that for any (non dummy) player j it is i:j∈S i di = 1. Then, except for a normal-

As suggested by a rather cryptic sentence in[START_REF] Isbel | A class of majority games[END_REF], last row, p. 185, on the point see also[START_REF] Pressacco | Bilateral symmetry and modified Pascal triangles in Parsimonious games[END_REF], sect. 3, p.

Acknowledgements

We acknowledge financial support of MedioCredito Friuli Venezia Friuli through the "Bonaldo Stringher" Laboratory of Finance, Department of Finance, University of Udine.