Ioannis Z Emiris
email: emiris@di.uoa.gr

Vasilis Margonis
email: basilis.math@gmail.com

Ioannis Psarros
email: ipsarros@uni-bonn.de

Near-Neighbor Preserving Dimension Reduction via Coverings for Doubling Subsets of � 1

Keywords: Approximate Nearest Neighbor, Manhattan metric, doubling dimension, randomized embedding, dimensionality reduction, Cauchy distribution, covering point set

Nearest neighbor-preserving embeddings exist for � 2 (Euclidean) and � 1 (Manhattan) metrics, as well as doubling subsets of � 2 , where doubling dimension is today the most effective way of capturing input structure. These randomized embeddings bound the distortion only for distances between the query point and a point-set. Motivated by the study of fast Approximate Nearest Neighbor search in � 1 , this paper settles the missing case of doubling subsets of � 1 .

In particular, we introduce a randomized dimensionality reduction by means of a near neighbor-preserving embedding; the latter is related to the decisionwith-witness problem. The input set gets represented via appropriate covering point-sets. For this, we leverage either approximate r-nets or randomly shifted grids, with different tradeoffs between preprocessing time and target dimension. We exploit Cauchy random variables, and derive a concentration bound of independent interest.

Introduction

Proximity search is a key computational question with a wide variety of applications. The corresponding problems in metric spaces of low dimension have been usually handled by space tessellation. Such solutions are affected by the curse of dimensionality, which makes them too costly in high dimensions. In the past two decades, the increasing need for manipulating high-dimensional data has led to randomized and approximation algorithms with polynomial dependence on the dimension, since the latter cannot be assumed as fixed but is part of the input parameters. Approximate Nearest Neighbor search, which is an optimization problem, constitutes a cornerstone question in this area. Existing reductions (see, e.g. [START_REF] Har-Peled | Approximate nearest neighbor: Towards removing the curse of dimensionality[END_REF]), which incur a polylogarithmic time overhead, reduce this search to the following decision problem with witness, namely the (c, R)-Approximate Near Neighbor question:

Definition 1 (Approximate Near Neighbor). Let (X, d X ) be a metric space.

Given P ⊆ X and reals R > 0, c ≥ 1, construct a data structure S which, given a query point q ∈ X, performs as follows:

• If the nearest neighbor of q lies within distance at most R, then S is allowed to report any point p * ∈ P , such that d X (q, p * ) ≤ cR.

• If all points lie at distance more than cR from q, then S returns ⊥.

The data structure S always returns either a point at distance ≤ cR or ⊥, even when none of the above two cases occurs.

We shall now suppose that R = 1, because this can always be achieved by re-scaling the input point set, and we refer to this problem as c-ANN, or simply ANN. We focus on subsets of � d 1 , in other words, the input dataset consists of n vectors in R d endowed with the standard � 1 distance function, also known as Manhattan metric, whose norm is denoted by � • � 1 . Note that all logarithms are base 2.

Previous work. Major landmarks in the study of data structures for highdimensional normed spaces are the different variants, proofs, and applications of the celebrated Johnson-Lindenstrauss Lemma (e.g. [START_REF] Achlioptas | Database-friendly random projections: Johnson-Lindenstrauss with binary coins[END_REF][START_REF] Ailon | The fast Johnson-Lindenstrauss transform and approximate nearest neighbors[END_REF][START_REF] Anagnostopoulos | Randomized embeddings with slack and high-dimensional approximate nearest neighbor[END_REF]), sketches based on p-stable distributions [START_REF] Indyk | Stable distributions, pseudorandom generators, embeddings, and data stream computation[END_REF], and Locality Sensitive Hashing (e.g. [START_REF] Andoni | Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions[END_REF][START_REF] Andoni | Optimal hashing-based time-space trade-offs for approximate near neighbors[END_REF][START_REF] Indyk | Approximate nearest neighbors: Towards removing the curse of dimensionality[END_REF]). In the core of most high-dimensional solutions, lies the fact that for certain metric spaces, e.g. � p for p ∈ [START_REF] Har-Peled | Approximate nearest neighbor: Towards removing the curse of dimensionality[END_REF][START_REF] Achlioptas | Database-friendly random projections: Johnson-Lindenstrauss with binary coins[END_REF], the distance can be efficiently sketched. Spaces which are considered to be harder in this context, such as � ∞ , can also be treated [START_REF] Indyk | On approximate nearest neighbors under l infinity norm[END_REF], and are quite interesting since they can be used as host spaces for various norms [START_REF] Andoni | Approximate near neighbors for general symmetric norms[END_REF].

Significant amount of work has been undertaken for point sets of low doubling dimension, since it is today one of the primary paradigms for capturing input structure (formal definitions in the next section). For any finite metric space X of doubling dimension dim(X), there exists a data structure [START_REF] Cole | Searching dynamic point sets in spaces with bounded doubling dimension[END_REF][START_REF] Har-Peled | Fast construction of nets in low dimensional metrics, and their applications[END_REF] with expected preprocessing time O(2 dim(X) n log n), space usage O(2 dim(X) n) (or even O(n)) and query time O(2 dim(X) log n + ε -O(dim(X) ).

Indyk and Naor [START_REF] Indyk | Nearest-neighbor-preserving embeddings[END_REF] introduced the notion of nearest-neighbor preserving embeddings, which are randomized embeddings between two metric spaces with guaranteed bounded distortion only for the distances between a query point and a point set. They achieved a dimension reduction for doubling subsets of � 2 , with the target dimension depending only on the input dataset's doubling dimension.

Even before, Indyk [START_REF] Indyk | Stable distributions, pseudorandom generators, embeddings, and data stream computation[END_REF] had introduced a randomized embedding for dimension reduction in � 1 , which is suitable for proximity search purposes, and it achieves target dimension polylogarithmic in the size of the point set. Naturally, such approaches can be easily combined with any known data structure to be used in the projection space. Randomized embeddings have been recently used in the ANN context [START_REF] Bartal | Approximate nearest neighbor search for � pspaces (2 < p < ∞) via embeddings[END_REF], for doubling subsets of � p , 2 < p < ∞.

Dimensionality reduction in � 1 cannot be achieved in the same generality as in � 2 , even by assuming that the point set is of low doubling dimension [START_REF] Lee | Metric structures in L 1 : dimension, snowflakes, and average distortion[END_REF]: There are arbitrarily large n-point subsets P ⊆ � 1 which are doubling with constant 6, such that every embedding with distortion

D of P into � k 1 requires k = n Ω(1/D 2 )
. Aiming at more restrictive guarantees, e.g. preserving distances within some pre-defined range, is a relevant workaround. Then, dimension reduction techniques for doubling subsets of � p , p ∈ [1, 2], have been proposed in [START_REF] Bartal | Dimension reduction techniques for � p[END_REF], but they rely on partition algorithms which require the whole point set to be known in advance. Hence, applicability of such techniques is very limited and, specifically, they do not seem amenable to an online setting where query points are not known in advance.

Our results. A new dimensionality reduction scheme is proposed, by means of a near neighbor-preserving embedding for doubling subsets of � 1 , thus settling a case that remained open. Our definition is essentially a modified version of the nearest neighbor preserving embedding of [START_REF] Indyk | Nearest-neighbor-preserving embeddings[END_REF]: the required guarantees are weaker, since we consider the decision version of the problem, therefore the embedding depends on some range parameter R > 0.

Definition 2 (Near-neighbor preserving embedding). Let (Y, d Y ), (Z, d Z ) be metric spaces and X ⊆ Y . A distribution over mappings f : Y → Z is a near-neighbor preserving embedding with range R > 0, distortion D ≥ 1 and probability of correctness P ∈ [0, 1] if for every α ≥ D and any q ∈ Y , if x ∈ X is such that d Y (x, q) ≤ R, then with probability at least P,

• d Z (f (x), f (q)) ≤ D • R, • ∀p ∈ X : d Y (p, q) > D • α • R =⇒ d Z (f (p), f (q)) > α • R.
Considering a point set P ⊂ � d 1 of cardinality n, our results concern � k 1 as the target space, where k depends on the doubling dimension of P . We assume that R = 1, since we can re-scale the given point set. More specifically:

1. In Theorem 10, we prove that for every ε ∈ (0, 1/2) and c ≥ 1, there is a randomized mapping h : � d 1 → � k 1 that can be computed in time Õ(dn 1+1/Ω(c) ) and is near neighbor-preserving for P with distortion 1+6ε and probability of correctness Ω(ε), where

k = (log λ P • log(c/ε)) Θ(1/ε) /ζ(ε),
for a function ζ(ε) > 0 depending only on ε. Although the mapping h depends on the point set, the parameter c is user-defined and therefore provides a trade-off between preprocessing time and target dimension.

2. In Theorem 13, we show that for every ε ∈ (0, 1/2), there is a randomized mapping h � : � d 1 → � k 1 that can be computed in time O(dkn), and is near neighbor-preserving for P with distortion 1+6ε and probability of correctness Ω(ε), where

k = (log λ P • log(d/ε)) Θ(1/ε) /ζ(ε),
for a function ζ(ε) > 0 depending only on ε. In this case, the function h � is oblivious to P and well-defined over the whole space, but the target dimension depends on d.

On the low-preprocessing-time extreme, one can embed the dataset in nearlinear time, but the target dimension is polynomial in log log n. This is to be juxtaposed to the analogous result in [START_REF] Indyk | Stable distributions, pseudorandom generators, embeddings, and data stream computation[END_REF], which achieves target dimension polynomial in log n, without any assumption on the doubling dimension of the dataset. On the other hand, it is possible to obtain a preprocessing time of dn 1+δ for any constant δ > 0, and target dimension which depends solely on the doubling dimension.

Methodology. Both of the aforementioned embeddings h, h � consist of two basic components. First, we represent the point set P with an ε-covering set, and then we apply a random linear projection à la Indyk [START_REF] Indyk | Stable distributions, pseudorandom generators, embeddings, and data stream computation[END_REF] to that set, using Cauchy variables.

The role of the covering set is to exploit the doubling dimension of P . In the analogous result for � 2 in [START_REF] Indyk | Nearest-neighbor-preserving embeddings[END_REF], no representative sets were used; the mapping was just a random linear projection of P . In the case of � 1 however, a similar analysis of a linear projection with Cauchy variables without these representative sets seems to be impossible, since the Cauchy distribution is heavy tailed.

In Theorem 10, we consider c-approximate r-nets as a covering set. Inspired by the algorithm of [START_REF] Eppstein | Approximate greedy clustering and distance selection for graph metrics[END_REF] for � 2 , we design an algorithm that computes a capproximate r-net in � 1 in subquadratic, but superlinear, time. On the other hand, Theorem 13 relies on randomly shifted grids, which can be computed in linear time, but are inferior to r-nets in terms of capturing the doubling dimension of the point set, hence inferior in terms of the target dimension.

To bound the distortion incurred by the randomized projection, we exploit the 1-stability property of the Cauchy distribution. To this end, we establish a new concentration bound for sums of independent Cauchy variables, which should be of interest beyond the scope of this paper. To overcome the technical difficulties associated with the heavy tails of the Cauchy distribution, we study sums of square roots of Cauchy variables, whereas in [START_REF] Indyk | Stable distributions, pseudorandom generators, embeddings, and data stream computation[END_REF], Indyk considers sums of truncated Cauchy variables instead. Although our concentration bound is rather weak, it is sufficient for our purposes and its analysis is much simpler compared to that in [START_REF] Indyk | Stable distributions, pseudorandom generators, embeddings, and data stream computation[END_REF].

Algorithmic implications. Our results show that efficient dimension reduction for doubling subsets of � 1 is possible, in the context of ANN. In particular, these results imply efficient sketches, meaning that one can solve ANN with minimal storage per point. Dimensionality reduction also serves as a problem reduction from a high-dimensional hard instance to a low-dimensional easy instance. Since the algorithms presented in this paper are quite simple, they should also be of practical interest: they easily extend the scope of any implementation which has been optimized to solve the problem in low dimension, so that it may handle high-dimensional data.

Our embedding can be combined with the bucketing method in [START_REF] Har-Peled | Approximate nearest neighbor: Towards removing the curse of dimensionality[END_REF] for the

(1+ε)-ANN problem in � d 1 .
For instance, setting c = log n in Theorem 10, yields preprocessing time dn 1+o (1) , space n 1+o (1) and query time O(d)•(log λ P • log log n) O(1/ε) assuming that the doubling dimension is a fixed constant. This improves upon existing results: the query time of [START_REF] Krauthgamer | Navigating nets: Simple algorithms for proximity search[END_REF] depends on the aspect ratio of the dataset, while the data structures of [START_REF] Cole | Searching dynamic point sets in spaces with bounded doubling dimension[END_REF][START_REF] Har-Peled | Fast construction of nets in low dimensional metrics, and their applications[END_REF] support queries with time complexity which depends exponentially on the doubling dimension. However, it is worth noting that one could potentially improve the results of [START_REF] Cole | Searching dynamic point sets in spaces with bounded doubling dimension[END_REF][START_REF] Har-Peled | Fast construction of nets in low dimensional metrics, and their applications[END_REF][START_REF] Krauthgamer | Navigating nets: Simple algorithms for proximity search[END_REF] in the special case of � 1 , by employing ANN data structures with fast query time, in order to accelerate the traversal of the net-tree. Hence, while our result gives a simple framework for exploiting the intrinsic dimension of doubling subsets of � 1 , it is unlikely that it shall improve upon simple variants of previous results in terms of complexity bounds. This paper is the complete and final version of our results that appeared in preliminary form in [START_REF] Emiris | Near-neighbor preserving dimension reduction for doubling subsets of � 1[END_REF].

Paper structure. The next section introduces basic concepts and some relevant existing results. Section 3 establishes a new concentration bound on sums of independent Cauchy variables. Section 4 achieves dimensionality reduction by means of representing the point set by a carefully chosen net, while Section 5 employs randomly shifted grids for the same task. We conclude with a discussion of our results, and of potential improvements.

Preliminaries

In this section, we define basic notions about doubling metrics and present some relevant existing results.

Definition 3. Consider any metric space (X, d X ) and let B(p, r) = {x ∈ X | d X (x, p) ≤ r}.
The doubling constant of X, denoted λ X , is the smallest integer λ X such that for any p ∈ X and r > 0, the ball B(p, r) can be covered by λ X balls of radius r/2 centered at points in X.

The doubling dimension of (X, d X ) is defined as log λ X . Nets play an important role in the study of embeddings, as well as in designing efficient data structures for doubling metrics. Proof. We employ some standard ideas from [START_REF] Har-Peled | Approximate nearest neighbor: Towards removing the curse of dimensionality[END_REF]. An analogous result for � 2 can be found in [START_REF] Eppstein | Approximate greedy clustering and distance selection for graph metrics[END_REF]. Let us first suppose that r = 1, since we are able to re-scale the point set. Let us now consider a randomly shifted grid with side-length 2.

The probability that two points p, q ∈ P fall into the same grid cell is at least 1 -�p -q� 1 /2. For each non-empty grid cell, we snap points to a grid: each coordinate is rounded to the nearest multiple of δ = 1/10dc. Then, coordinates are multiplied by 1/δ and each point x = (x 1 , . . . , x d ) ∈ [2δ] d is mapped to {0, 1} 2d/δ by a function G as follows: G(x) = (g(x 1 ), . . . , g(x d )), where g(z) is a binary string of z ones followed by 2/δz zeros. For any two points p, q in the same grid cell, let f (p),f (q) be the two binary strings obtained by the above mapping. Notice that,

�f (p) -f (q)� 1 ∈ (2/δ) • �p -q� 1 ± 1. Hence, �p -q� 1 ≤ 1 =⇒ �f (p) -f (q)� 1 ≤ (2/δ) + 1, �p -q� 1 ≥ c =⇒ �f (p) -f (q)� 1 ≥ (2/δ) • c -1.
Let us now employ the LSH family of [START_REF] Har-Peled | Approximate nearest neighbor: Towards removing the curse of dimensionality[END_REF], for the Hamming space. After standard concatenation, we may assume that the family is (ρ, c � ρ, n -1/c � , n -1 )sensitive, where ρ = (2/δ) + 1 and c � = Ω(c). Let α = n -1/c � and β = n -1 .

Notice that for the above two-level hashing table, we obtain the following guarantees: Any two points p, q ∈ P , such that �p -q� 1 ≤ 1, fall into the same bucket with probability ≥ α/2. Any two points p, q ∈ P , such that �p -q� 1 ≥ c, fall into the same bucket with probability ≤ β.

Finally, we independently build k = Θ(n 1/c � log n) hashtables as above, where the random hash function is defined as a concatenation of the function which maps points to their grid cell id and one LSH function. We pick an arbitrary ordering p 1 , . . . , p n ∈ P . We follow a greedy strategy in order to compute the approximate net. We start with point p 1 , and we add it to the net. We mark all (unmarked) points which fall at the same bucket with p 1 , in one of the k hashtables, and are at distance ≤ cr. Then, we proceed with point p 2 .

If p 2 is unmarked, then we repeat the above. Otherwise, we proceed with p 3 .

The above iteration stops when all points have been marked. Throughout the procedure, we are able to store one pointer for each point, indicating the center which covered it.

Correctness. The probability that a good pair p, q does not fall into the same bucket for any of the k hashtables is

≤ (1 -α/2) k ≤ n -10
. Hence, with high probability, the packing property holds, and the covering property holds because the above algorithm stops when all points are marked.

Running time. The time to build the k hashtables is k

• n = Õ(n 1+1/c � ).
Then, at most n queries are performed: for each query, we investigate k buckets and the expected number of false positives is

≤ k • n 2 • β = Õ(n 1+1/c � ).
Hence, if we stop after having seen a sufficient amount of false positives, we obtain time complexity Õ(n 1+1/c � ) and the covering property holds with constant probability. We can repeat the above procedure O(log n) times to obtain high probability of success.

The main result in the context of randomized embeddings for dimension reduction in � d 1 is the following theorem, which exploits the 1-stability property of Cauchy random variables and provides with an asymmetric guarantee: The probability of non-contraction is high, but the probability of non-expansion is constant. Nevertheless, this asymmetric property is sufficient for proximity search.

Theorem 6 (Thm 5, [START_REF] Indyk | Stable distributions, pseudorandom generators, embeddings, and data stream computation[END_REF]). For any ε ≤ 1/2, δ > 0, ε > γ > 0 there is a probability space over linear mappings f :

� d 1 → � k 1 ,
where k = (ln (1/δ)) 1/(ε-γ) /ζ(γ), for a function ζ(γ) > 0 depending only on γ, such that for any pair of points p, q ∈ � d 1 :

Pr � �f (p) -f (q)� 1 ≤ (1 -ε) �p -q� 1 � ≤ δ, Pr � �f (p) -f (q)� 1 ≥ (1 + ε) �p -q� 1 � ≤ 1 + γ 1 + ε .
Note that the embedding is defined as f (u) = Au/T , where A is a k×d matrix with each element being an i.i.d. Cauchy random variable. In addition,

T is a scaling factor defined as the expectation of a sum of truncated Cauchy variables, such that T = Θ(k log (k/ε)), see [START_REF] Indyk | Stable distributions, pseudorandom generators, embeddings, and data stream computation[END_REF]Lem. 5].

One key observation here is that, given a point set P in a space of bounded aspect ratio Φ, one can directly employ Theorem 6. The number of points can be upper bounded by a function of λ P and Φ, and hence the new dimension k depends only on these parameters. Here, we establish better bounds than those in Theorem 6 for doubling subsets of � d 1 , without any assumption on the aspect ratio.

Concentration bounds for Cauchy variables

In this section, we prove some basic properties of the Cauchy distribution, which serves as our main embedding tool.

Let C D denote the Cauchy distribution with density c(x) = (1/π)/(1 + x 2 ).

One key property of the Cauchy distribution is the so-called 1-stability property:

Let v = (v 1 , . . . , v k ) ∈ R k and X 1 , . . . , X k be i.i.d. random variables following C D , then � k j=1 X i v i is distributed as X•�v� 1 , where X ∼ C D .
The Cauchy distribution has undefined mean. However, for 0 < q < 1, the mean of the q-th power of a Cauchy random variable can be defined. More specifically, for some X ∼ C D we have

E � |X| 1/2 � = 2 π � ∞ 0 √ x 1 + x 2 dx = 2 π π √ 2 = √ 2.
The following lemma provides a bound for the moment-generating function

of |X| 1/2 . Lemma 7. Let X ∼ C D .
Then for any β > 1:

E � exp (-β|X| 1/2 ) � ≤ 2 β .
Proof. For any constant β,

� 1 0 e -βx 1/2 dx = 2 β 2 � 1 - β + 1 e β � .
Then, for any β > 1,

E � exp (-β|X| 1/2 ) � = � ∞ -∞ e -β|x| 1/2 • c(x) dx = 2 π � ∞ 0 e -βx 1/2 • 1 1 + x 2 dx = 2 π � 1 0 e -βx 1/2 • 1 1 + x 2 dx + 2 π � ∞ 1 e -βx 1/2 • 1 1 + x 2 dx ≤ 2 π � 1 0 e -βx 1/2 dx + 2 π � ∞ 1 e -β • 1 1 + x 2 dx = 2 π • 2 β 2 � 1 - β + 1 e β � + 1 2e β ≤ 4 πβ 2 + 1 2e β ≤ 2 β . Let S := � k j=1 |X j |
where each X j is an i.i.d. Cauchy variable. To prove concentration bounds for S, we study the sum S :=

� k j=1 |X j | 1/2
. By Hölder's Inequality, for any x ∈ R d and p > q > 0,

�x� p ≤ �x� q ≤ d 1/q-1/p �x� p .
Consequently, for x = (X 1 , . . . , X k ) ∈ R k , p = 1 and q = 1/2 we have that

S ≤ S2 ≤ k • S, hence for any t > 0, Pr[S ≤ t] ≤ Pr[ S ≤ √ tk]. (1)
type concentration bound for S, which by Eq. ( 1) translates into a concentration bound for S.

Lemma 8. For every D > 1,

Pr � S ≤ E[ S] D � ≤ � 10 D � k .
Proof. Since X j 's are independent, E[ S] = √ 2k. Then, by Lemma 7 and Markov's inequality, for any β > 1, it follows that

Pr � S ≤ E[ S] D � = Pr � exp(-β S) ≥ exp � -β • E[ S] D �� ≤ E[exp(-β S)] exp(-β E[ S]/D) = E[exp(-β|X j | 1/2 )] k exp(-β √ 2k/D) ≤ � 2 β � k • e √ 2βk/D .
Setting β = D completes the proof.

Net-based dimension reduction

This section describes the dimension reduction mapping for � 1 via r-nets.

Let P ⊂ � d 1 be a set of n points with doubling constant λ P . For some point x ∈ R d and r > 0, we denote by B 1 (x, r) the � 1 -ball of radius r around x. The embedding is non-linear and is carried out in two steps.

First, let us compute a c-approximate (ε/c)-net N of P with the algorithm of Theorem 5. Moreover, the algorithm assigns each point of P to the point of N which covered it. Let g : P → N be this assignment. In the second step, for every s ∈ N and any query point q ∈ � d 1 , we apply the linear map of Theorem 6. That is, f (s) = As/T , where A is a k×d matrix with each element being an i.i.d. Cauchy random variable. Recall that value T satisfies

T = Θ(k log (k/ε)).
By the 1-stability property of the Cauchy distribution, f (s) is distributed as

�s� 1 •(Y 1 , . . . , Y k ), where each Y j is i.i.d. and Y j ∼ C D . Hence, �f (s)� 1 = �s� 1 •S
where S := � j |Y j |. We now define the embedding to be h = f • g. We apply h to every point in P , and f to any query point q. It is clear from the properties of the net that g incurs an additive error of ±ε on the distance between q and any point in P , so it is sufficient to consider the distortion of f . Our analysis consists of studying separately the following disjoint subsets of N : Points that lie at distance at most D 0 from the query and points that lie at distance at least D 0 , for some D 0 > 1 chosen appropriately. For the former set, we directly apply Theorem 6, since it has bounded diameter.

The next lemma guarantees the low distortion for points of the latter set, namely those that are sufficiently far from the query. We consider the sum of the square roots of each |Y j |, i.e., S = � j |Y j | 1/2 , in order to employ the tools of Section 3. Lemma 9. Fix a query point q ∈ � d 1 . For any ε ≤ 1/2, c ≥ 1, δ ∈ (0, 1), there exists

D 0 = O(log(k/ε)) such that for k = Θ � log 2 λ P • log(c/ε) + log(1/δ) � ,
with probability at least 1δ,

∀s ∈ N : �s -q� 1 ≥ D 0 =⇒ �f (s) -f (q))� 1 ≥ 4.
Proof. Assume wlog that the query point is the origin (0, . . . , 0). For some D 0 > 1, we define the following subsets of N :

N i := {s ∈ N | D i ≤ �s� 1 < D i+1 }, D i = 2 2i D 0 , i = 0, 1, 2, . . .
By the definition of doubling constant and the fact that two points of N lie at distance at least ε,

|N i | ≤ λ �log(4cDi+1/ε)� P ≤ λ 4 log(cDi+1/ε) P . 13
Therefore, by the union bound, and Eq. ( 1):

Pr � ∃i∃s ∈ N i : �f (s)� 1 ≤ 4 �s� 1 D i � = Pr � ∃i∃s ∈ N i : S ≤ 4T D i � ≤ ∞ � i=0 |N i | Pr � S ≤ √ 4kT √ D i � = ∞ � i=0 |N i | Pr � S ≤ E[ S] • � 2T k2 2i D 0 � . By Lemma 8, for D 0 =�800T /k�=Θ(log(k/ε)) and k > 4• log λ P • log(cD 0 /ε) + 2 log(2λ P /δ): ∞ � i=0 |N i | Pr � S ≤ E[ S] 10 • 2 i+1 � ≤ ∞ � i=0 λ 4 log (cDi+1/ε) P � 1 2 i+1 � k = ∞ � i=0 2 log(λP )(4 log (cD0/ε)+2i+2) 2 k(i+1) ≤ ∞ � i=0 2 log(λP )•4 log (cD0/ε) • 2 2 log(λP )(i+1) 2 (4•log λP •log(cD0/ε))(i+1) • 2 2 log(2λP /δ))(i+1) ≤ ∞ � i=0 2 -2 log(2/δ))(i+1) = ∞ � i=0 � δ 2 4 � i -1 = δ 2 4 -δ 2 ≤ δ.
Finally, for some large enough constant C, we demand that

k > C (log λ P • log(c log k/ε) + log(1/δ)) > 4 • log λ P • log(cD 0 /ε) + 2 log(2λ P /δ) which is satisfied for k = Θ � log 2 λ P • log(c/ε) + log(1/δ) � .
Theorem 10. Let P ⊂ � d 1 such that |P | = n. For any ε ∈ (0, 1/2) and c ≥ 1, there is a non-linear randomized embedding h = f • g :

� d 1 → � k 1 ,
where

k = (log λ P • log(c/ε)) Θ(1/ε) /ζ(ε),
for a function ζ(ε) > 0 depending only on ε, such that, for any q ∈ � d 1 , if there exists p * ∈ P such that �p * -q� 1 ≤ 1, then, with probability Ω(ε):

�h(p * ) -f (q)� 1 ≤ 1 + 3ε, ∀p ∈ P : �p -q� 1 > 1 + 9ε =⇒ �h(p) -f (q)� 1 > 1 + 3ε.
Set P can be embedded in time Õ(dn 1+1/Ω(c) ), and any query q ∈ � d 1 can be embedded in time O(dk).

Proof. Let f, g be the mappings defined in the beginning of the section and D 0 = Θ(log(k/ε)). Assume wlog for simplicity that q = 0 d . Then, by Lemma 9

for k = Θ � log 2 λ P • log(c/ε) �
, with probability at least 1ε/5, we have:

∀p ∈ P : �p -q� 1 ≥ D 0 + ε =⇒ �h(p) -f (q)� 1 ≥ 4.
By Theorem 6, for γ = ε/10 and δ = ε/(5λ 8 log (cD0/ε) P

), with probability at least 1ε/5, we get:

∀p ∈ P : �p-q� 1 ∈ (1+9ε, D 0 +ε) =⇒ �h(p) -f (q)� 1 > (1+8ε)(1-ε) ≥ 1+3ε.
Moreover,

Pr � �h(p * ) -f (q)� 1 ≤ 1 + 3ε � ≥ 1 - 1 + ε/10 1 + ε ≥ 1 -(1 -ε/2).
Then, the target dimension needs to satisfy the following inequality:

k ≥ � ln (5λ 8 log (cD0/ε) P /ε) � 2/ε ζ(ε) = � Θ(log log k • log λ P + log λ P • ln(c/ε)) � 2/ε ζ(ε) .
Hence, for k = (log λ P • log(c/ε)) Θ(1/ε) /ζ(ε), we achieve a total probability of success in Ω(ε), which completes the proof.

Dimension reduction based on randomly shifted grids

In this section, we explore some properties of randomly shifted grids, and we present a simplified embedding which consists of a first step of snapping points to a grid, and a second step of randomly projecting grid points. for t 1 , . . . , t d independent uniform random variables in the interval [0, w], induces a randomly shifted grid in R d . For a set X ⊆ R d , we denote by g w (X), the image of X on the randomly shifted grid points defined by g w . For some x ∈ R d and r > 0, the number of grid cells of g w (� d 1 ) that B 1 (x, r) intersects per axis is independent, and in expectation is 1+2r/w. Then, the expected total number of grid cells that B 1 (x, r) intersects is at most (1+2r/w) d . Now let P ⊂ � d 1 be a set of n points with doubling constant λ P and q ∈ � d 1 a query point. For w = ε/d, the � 1 -diameter of each cell is ε and therefore g w (P ) is an ε-covering set of P . The next lemma shows that, with constant probability, the growth on the number of representatives, as we move away from q, is bounded.

Lemma 12. Let {D i } i∈N be a sequence of radii such that, for any i, D i+1 = 4D i . Let A i be the points of g w (P ) within distance D i+1 = 2 2(i+1) D 0 from q.

Then, with probability at least 1/3,

∀i ∈ {-1, 0, . . .} : |A i | ≤ 4 i+3 λ 2 log(dDi+1/ε) P . Proof. By Lemma 11, E[|A i |] ≤ 8λ
2 log(dDi+1/ε) P

for every i ∈ {-1, 0, . . .}. Then, a union bound followed by Markov's inequality yields

Pr � ∃i ∈ {0, 1, . . .} : |A i | ≥ 4 i+1 E[|A i |] � ≤ 1/3.
In addition,

Pr � |A -1 | ≥ 4 E[|A i |] � ≤ 1/4. Theorem 13. Let P ⊂ � d 1 such that |P | = n. For any ε ∈ (0, 1/2), there is a non-linear randomized embedding h � : � d 1 → � k 1 , where k = (log λ P • log(d/ε)) Θ(1/ε) /ζ(ε),
for a function ζ(ε) > 0 depending only on ε, such that for any q ∈ � d 1 , if there exists p * ∈ P such that �p * -q� 1 ≤ 1, then with probability Ω(ε),

�h � (p * ) -f (q)� 1 ≤ 1 + 3ε, ∀p ∈ P : �p -q� 1 > 1 + 9ε =⇒ �h � (p) -f (q)� 1 > 1 + 3ε.

Any point can be embedded in time O(dk).

Proof. We follow the same reasoning as in the proof of Theorem 10. The embed-

ding is h � = f • g ε/d
, where f is the randomized linear map defined in Section 4.

As before, we apply h � to every point in P , and only f to queries. The randomly shifted grid incurs an additive error of ε in the distances between q and P .

Assume wlog that q = 0 d and let A i be the points of g ε/d (P ) within distance D i+1 = 2 2(i+1) D 0 from q. Hence, by Lemma 12, ), with probability at least 1ε/5, it holds:

Pr � ∃i∃s ∈ A i : �f (s)� 1 ≤ 4 �s� 1 D i � ≤ ∞ � i=0 |A i | Pr � S ≤ 4T D i � ≤ ∞ � i=0 4
∀p ∈ P : �p -q� 1 ∈ (1 + 9ε, D 0 + ε) =⇒ �h � (p)f (q)� 1 > 1 + 3ε.

Moreover, with probability at least ε/2, we obtain:

�h � (p * ) -f (q)� 1 ≤ 1 + 3ε.
As in Theorem 10, the target dimension needs to satisfy the following: Hence, for k = (log λ P • log(d/ε)) Θ(1/ε) /ζ(ε) we achieve total probability of success Ω(ε).

Conclusion

We have filled in a gap in the spectrum of randomized embeddings with bounded distortion only for distances between the query and a point set: such embeddings existed for � 2 and � 1 and for doubling subsets of � 2 . Here we settle the case of doubling subsets of � 1 with a near neighbor-preserving embedding.

In the meantime, we obtain a concentration bound on sums of independent Cauchy variables. Our algorithms are quite simple, therefore they should also be of practical interest.

We rely on approximate r-nets or randomly shifted grids. For the former, Theorem 10 provides with a trade-off between the preprocessing time required and the target dimension. On the other hand, Theorem 13 has the advantage of fast preprocessing: any point is embedded in O(dk) time, and the embedding is oblivious to the point set. In regards to the near-linear preprocessing time, the two results are comparable, since the dimension in Theorem 13 can be substituted by the target dimension of Theorem 6.

Let us underline that any potential improvements to Theorem 6 should lead to improvements to Theorems 10 and 13. The target dimension in these theorems follows from a direct application of Theorem 6 to the representative data points which lie inside a bounding ball centered at the query.

Definition 4 .

 4 For c ≥ 1, r > 0 and metric space (V, d V ), a c-approximate r-net of V is a subset N ⊆ V such that no two points of N are within distance r of each other, and every point of V lies within distance at most c•r from some point of N .Theorem 5. Let P ⊂ � d 1 such that |P | = n.Then, for any c > 0, r > 0, one can compute a c-approximate r-net of P in time Õ(dn 1+1/c � ), where c � = Ω(c). The result is correct with high probability. The algorithm also returns the assignment of each point of P to the point of the net which covers it.

Let w > 0

 0 and t be chosen uniformly at random from the interval [0, w]. The function h w,t (x) = w • � xt w � induces a random partition of the real line into segments of length w. Hence, the function g w (x) = (h w,t1 (x 1 ), ..., h w,t d (x d )),

Lemma 11 .

 11 Let R > 1 and P � := B 1 (q, R) ∩ P . Then, for w = ε/d E � |g w (P � )| � ≤ 8λ 2 log(dR/ε) P . Proof. By the doubling constant definition, there exists a set of balls of radius ε/d 2 centered at points in P � , of cardinality at most λ 2 log(dR/ε) P which covers P � . For each ball of radius ε/d 2 , the expected number of intersecting grid cells is (1+2/d) d ≤ e 2 . The lemma follows by linearity of expectation.

.2

  As in Lemma 9, for D 0 = �800T /k� = Θ(log(k/ε)), k ≥ 20 log λ P • log � dD0 2i+6+2 log λP [log(dD0/ε)+2(i+1)] 2 k(i+1) ≤ ε/5. Hence, for k = Ω � (log 2 λ P • log(d/ε) �, with probability at least 1-ε/5, we have:∀p ∈ P : �p -q� 1 ≥ D 0 + ε =⇒ �h � (p)f (q)� 1 ≥ 4.Now, we are able to use Theorem 6 for points which are at distance at most D 0 + ε from q, and the near neighbor. By Lemma 12, with constant probability, the number of grid points at distance ≤ D 0 +ε, is at most 32•λ 4 log(dD0/ε) P . Hence, by Theorem 6, for γ = ε/10 and δ = ε/(160λ 4 log (dD0/ε) P

Acknowledgements

IZE is member of team AROMATH, joint between INRIA Sophia-Antipolis (France) and NKUA. IP thanks Robert Krauthgamer for useful discussions on the topic.

Partially supported by the European Union's H2020 research and innovation programme under grant agreement No. 734242 (LAMBDA). Funding: this research has been co-financed by Greece and the European Union (European Social Fund) through the Operational Programme "Human Resources Development, Education and Lifelong Learning" in the context of the project "Strengthening Human Resources Research Potential via Doctorate Research" (MIS-5000432), implemented by the State Scholarships Foundation (IKY) of Greece.


Mantiaba Coulibaly

Loïc Sauvee
email: loic.sauvee@lasalle-beauvais.fr

Mantiaba COULIBALY and Loïc SAUVEE Conceptualization of value creation process in brand alliances: Static and dynamic view

In this communication, we conceptualize the value creation process in brand alliances through an approach both static and dynamic. We analyse this process in the food market. We show that some components explain the value creation process in brand alliances: context, actors, objectives, behaviors, resources, governance mechanisms. The impact of these components depends on the nature of organizations and the market.

Introduction

To present a static approach of the value creation process, we mobilize literature on brand alliances as well as strategic alliances. We identify some components which influence value for the consumers and the organizations in brand alliances: context, actors (their objectives and behaviors), resources and governance mechanisms. Also, we show that these components can have negatives impacts on brand alliances. We also present a dynamic approach of value creation in brand alliances. We show that the evolution of some organizational factors impact value creation in brand alliances: internal factors such as objectives and resources of actors, internal tensions [START_REF] Das | Instabilities of Strategic Alliances: An Internal Tensions Perspective[END_REF] and governance mechanisms. With a qualitative methodology, we use case studies [START_REF] Yin | Case Study Research[END_REF][START_REF] Eisenhardt | THEORY BUILDING FROM CASES: OPPORTUNITIES AND CHALLENGES[END_REF] to apply the value creation process to two types of alliances in the food market: the alliance between a private certification brand and a private brand of banana, and the alliance between an ingredient food brand and a dietary food supplement brand. Firstly, we analyse the value creation process in brand alliances with a static approach. Secondly, we explain a dynamic view of value creation in brand alliances. Finally, we apply the static and dynamic approach to the case studies and we compare the results.

A Static approach of value creation in brand alliances

We use research on brand alliances and strategic alliances to identify components which can explain value creation in brand alliances.

-Context of brand alliances The context of alliances represents an external and internal environment of the alliances [START_REF] Kumar | Differential Learning and Interaction in Alliance Dynamics: A process and Outcome Discrepancy Model[END_REF]). An external environment explains the economical, social and legal situation of alliance. An internal environment concerns for example communication on a product or strategy of commercialization adopted by organizations in alliance. According to Kumar and Nti (1998: 364), the internal and external environment can involve negative impacts on the relationship between organizations in alliance.

-Actors in brand alliances Actors in brand alliances represent organizations which combine their brands and partners of these organizations [START_REF] Golan | Do Food Labels Make a Difference[END_REF]. In the food market owners of brands exchange with their direct partners (producers, distributors, organization of control) and their indirect partners (government, public and private institutions). They note that all the organizations in brand alliances exchange activities and resources (Håkansson and Senhota, 1995) to create value for consumers and finally for organizations.

-Actors'objectives, their resources and behaviors in brand alliances In brand alliances, actors (organizations) develop different (individual) objectives and/or common objectives. The objectives can be strategic: to realize benefit, to have legitimacy, and to reduce costs [START_REF] Abratt | Managing co-branding strategies: global brands into local markets[END_REF][START_REF] Prince | Examining the longevite of new agency accounts: A comparative study of U.S. advertising experiences[END_REF]. The objectives can concern the brand image and the price of the product which represents the brands (Leuthesser and al. 2003). In addition, organizations combine tangible resources such as cash flow, raw material, etc. and intangible resources for example brand, reputation, knowledge, etc. [START_REF] Williamson | A comparison of alternative approaches to economic organization[END_REF][START_REF] Gilbert | Strategies to Outpace the Competition[END_REF]. So resources permit to create value for consumers (quality of product toward the brand) and organizations (reputation, benefit).

But, retention of resources involves dependence between organizations (Pfeffer et Salancik, 1978). And some organizations develop opportunistic behaviors because they want to improve rapidly their profit without other partners in the alliance [START_REF] Williamson | A comparison of alternative approaches to economic organization[END_REF][START_REF] Williamson | The Theory of the Firm as a Governance Structure: From Choice to Contract[END_REF].

-Using governance mechanisms in brand alliances Previous research on inter organizational relationship (IOR) and strategic alliances show that we can have formal and informal governance mechanisms in alliances. We have formal mechanisms such as contracts between actors in alliance [START_REF] Williamson | A comparison of alternative approaches to economic organization[END_REF], social and environmental norms, shared knowledge [START_REF] Doz | the evolution of cooperation in strategic alliances: initial conditions or learning processes?[END_REF] and coordination of activities [START_REF] Mintzberg | The structuring of organizations[END_REF]. We have informal mechanisms such as trust and informal agreement between organizations. All these mechanisms allow value creation for consumers (best image of product which represents the brands of alliance) and organizations (good relationship, development of activities and sales). However, governance mechanisms involve some negative impacts in alliance: costs to negotiate contracts, difficulties to respect norms, to collaborate, etc. From these studies, we show that the context of alliance, the actors (organizations) which combine their brands in alliance and their partners), the objectives, the behaviors and resources of actors, and the governance mechanisms facilitate value creation in brand alliances. These components create value for consumers toward quality of product and trust of the brand. Then the components create value for organizations which combine their brands and their partners: they can increase benefit, allow access to new resources, improve trust with partners, have new knowledge, competitive advantage. However, organizations must support costs of contracts, management of relationship, respect of rules, etc.

A dynamic approach of value creation in brand alliances

We consider works on evolution of strategic alliances [START_REF] Ring | Developmental processes of cooperative interorganizational relationships[END_REF][START_REF] Das | Instabilities of Strategic Alliances: An Internal Tensions Perspective[END_REF][START_REF] Doz | the evolution of cooperation in strategic alliances: initial conditions or learning processes?[END_REF] to explain value creation in brand alliances on the long term. Ring and Van de Ven (1994: 97) inform us on the steps of the evolution process of the relationship between organizations in alliance: negotiations (formal and informal negotiations), commitments (formal and informal contracts), and assessments and execution of commitments. According to Doz (1996: 55), evolution of an alliance is impacted by initial conditions such as task definition, partners' routines, expectations of performance and behavior, etc. Other researches give us information on the existence of contradictory elements during the evolution of an alliance. Indeed, Das and Teng (2000: 84-88) show that in alliances application of some decisions and activities cause modification of flexibility to rigidity. Then cooperation can be opposed to competition and in strategic orientation, short term can be opposed to long term. From these researches we note importance of governance mechanisms (formal and informal), internal conditions (such as resources, objectives, their behavior) and internal tensions (degree of flexibility, degree of cooperation and strategic orientation) in the evolution of brand alliances. All of these organizational factors can impact positively or negatively on the value created in brand alliances. Finally interaction between actors in the long term can modify governance relationship in a market [START_REF] Ritter | A framework for analyzing relationship governance[END_REF].

Application of the value creation process to case studies in a food market

We use a qualitative approach applying case study protocol [START_REF] Yin | Case Study Research[END_REF][START_REF] Eisenhardt | THEORY BUILDING FROM CASES: OPPORTUNITIES AND CHALLENGES[END_REF] to present a static and dynamic approach of the value creation process in brand alliances in the food market. We worked on types of brand alliances in two markets during three years [START_REF] Coulibaly | Brand alliances and value creation: a network approach, An analytical framework tested on the food market, Fruit and Vegetable Summit[END_REF][START_REF] Sauvée | The Interorganizational Dynamics of Brand Alliances[END_REF]. The first case study on a fair trade market concerns an alliance between a private certification brand: "Fairtrade" of Max Havelaar association and a private brand of banana: "Oké" of Agrofair's company. The second alliance on dietary food supplements market relies on an alliance between a private ingredient brand "Svétol" of Berkem's company and a private dietary food supplement brand "ADIP'LIGHT" of Lierac's company. To collect data, we conducted 26 semi-directive face to face interviews (14 in the fair trade market and 12 in the dietary food supplements market) with executive managers, sales directors of the organizations which join their brand and their partners. We sent 6 written questionnaires for additional details. We completed these data with annual reports, secondary data on markets and firms. We analysed data with the help of "QSR Nvivo 8.0"software.

Case study 1

Case study 2

We present in table 1 and table 2 data collected in a static approach and a dynamic approach.

Table 1: Static approach of value creation process in food market

Case study 1: alliance between a certification brand and private brand of banana

Case study 2 : alliance between a ingredient brand and a dietary food supplement brand External environment

Fair trade market: -Regulated market to reduce inequality between producers in developing countries and industrial in developed countries.

-A high consumption of fair trade banana.

Internal environment

Promotion of two types of brand :"Fairtrade" and "Oké" on fair trade bananas "oké fairtrade".

External environment

Dietary food supplements market: -Regulated market to control and preserve health of consumers.

-Increasing of dietary food supplement particularly for thinness.

Internal environment

Promotion of two types of brand: "Svétol" and " ADIP'LIGHT " on dietary food supplements "ADIP'LIGHT".

Owners of brand

Company Agrofair: importer of bananas. Company Max Havelaar : association which promote marketing of fair-trade products.

Direct partners of Agrofair and Max Havelaar

Producers, Ripeners, distributors, certification. organization (FLO : Fairtrade Labelling Organization), consumers Indirect partners of Agrofair and Max Havelaar Voluntary, government.

Owners of brand

Company Berkem: industry of food ingredients. Company Lierac: industry of dietary food supplements.

Direct partners of Berkem and Lierac

Suppliers of raw material to produce ingredients, distributors of ingredients.

Indirect partners of Berkem and Lierac

Research center, hospitals.

Common objectives of organizations in the alliance:

-To ensure equality between organizations which exchange in a fair-trade market to sell bananas labeling "oké fair-trade".

-To reduce problem of producers who produce bananas.

-To protect environment. Behavior Opportunism of organizations in exchange.

Common objectives of organizations in alliance

-To permit women to lose weight using a dietary food supplement "ADIP'LIGHT" containing ingredient "Svétol".

-Increasing of benefit. Behavior Opportunism of organizations in exchange.

Resources

Value creation in brand alliances Consumer value:

-Quality of fair trade banana "Oké-fairtrade": respect of environment rules, security, guaranty.

Financial value:

-Decrease of production costs, increase of benefit, investment in socials projects in developing countries. Competitive value -Notoriety, reputation, brand image of fair trade.

-Qualified producers: they know process of production.

-Communication around a fair trade concept.

-Improvement of live conditions of producers. Negative consequences in brand alliances -Negotiation costs of contracts, constraints to respect social and environment rules.

Value creation in brand alliances Consumer value:

-Quality of dietary food supplement "ADIP'LIGHT " : The product contains a thinness ingredient "Svétol", respects environment rules.

Conclusion

From the case studies in the food market, we confirm contribution of the literature on brand alliances and strategic alliances concerning impact of context of alliance, common objectives of actors, resources, behaviors and governance mechanisms on value creation in brand alliances. We note also existing of difficulties when organizations join their brands. However, we note difference between objectives in the two case studies. Indeed in a fair trade market the main objective is to promote an equal trade of banana between developing countries and developed countries. In a dietary food supplement market, the main objective is to produce financial result. We note also the difference between governance mechanisms and modifications in resources, internal tensions, mechanisms during evolution of the alliance: in the case study 2, we don't identify informal mechanisms and modification We conclude that value creation in brand alliances depend of factors such as nature of organization (commercial or non commercial) and the aspect of market (rules). These factors influence objectives, behavior of actors, exploitation of resources and governance mechanisms and finally value for the consumers and organizations. So we advice managers to anticipate partners' behaviors in an alliance, to follow the evolution of environmental norms, to work and to exchange strategic information with the marketing board of the partners. We also note two main limits in this communication. Firstly we apply a process of value creation only in two case studies and on the food market. Secondly we study dynamics on brand alliances only during three years. We think that in future researches, it is possible to compare the value creation process in brand alliances in the food market and the industrial market.

-

  Financial resources (subsidies). -Notoriety of "Fairtrade" brand. -Strategy of communication, schedule of conditions. Governance mechanisms in alliance Formal mechanism -Contracts between Agrofair and Max Havelaar : Max Havelaar give to Agrofair its agreement to put a fair-trade brand on the banana and Agrofair pay royalty to Max Havelaar. -FLO verify respect of standard in fair trade market by all the actors: socials and environment norms. -Cooperation et negotiation between organizations in applying standard and produce knowledge. Informal mechanism -Trust between Agrofair and Max Havelaar. Resources -Clinical studies. -Communication in scientific journal on the food market. Governance mechanisms in alliance Formal mechanism -Confidential agreement. -Respect of socials and environment norms in a dietary food supplements market. -Exchange of Knowledge concerning specification of final product (dietary food supplement).

  Financial value: -Benefit of Berkem and Lierac increase. Competitive value -Scientific team work in Berkem and Lierac: doctors, engineers. Negatives consequences in brand alliances -Negotiation costs of contracts, constraints to respect social and environment rules.-The cycle of life of ingredients and dietary food supplements is short in this market.

Table 2 : Dynamic approach of value creation process in food market Case study 1: alliance between a certification brand and private brand of banana Case study 2 : alliance between an ingredient brand and a dietary food supplement brand

 2

	Modifications	Resources	-Common communication of Agrofair	-To renew clinical studies and
	in internal		and Max Havelaar to justify the price of	communication in scientific review
	factors		« oké fairtrade » banana to the final
			consumer: write actions conducting by
			organizations to improve producers
			conditions, distribution of benefit
			between actors;
			-Augmentation des subventions
		Actors'	-Max Havelaar encourage companies to	No information
		objectives and	invest in a fair trade market
		behaviors	-Common objectives : maintain alliance
			during a long time
	Modifications	Degree of	Certification of Agrofair by the control	No information
	on internal	flexibility :	organization / control of the Agrofair's
	tensions	flexibility	activities by certification organization,
		versus	payment of royalty by Agrofair.
		Degree of	Common communication to promote	Common communication on an
		cooperation:	banana "Oké faitrade" / potential	ingredient "Svétol " in a dietary food
		Cooperation	competitors on the fair trade market to	supplement "ADIP'LIGHT " /
		versus	sell banana	communicate on others ingredients
		competition		included in "ADIP'LIGHT"
		Strategic	Respect of producers's conditions,	Using an ingredient "Svétol" to produce
		orientation:	equality in the distribution of benefit	a dietary food supplement
		short term	between actors / Respect of the price of	" ADIPT'LIGHT" /to replace a "Svétol"
		versus long	banana in the fair trade market	by other ingredient
		term
	Modifications in	Formal	-Reinforcement of standards, rules and	No information
	governance mechanisms	mechanisms	norms -Increasing of appointments and
			exchanges between actors
			-Participation of producers at the
			decisions in fair trade market
		Informal	-Reinforcement of trust between actors	No information
		mechanisms

th Conference on Business Market Management,Copenhagen, 18-20 March 2009


Loïc Sauvée
email: loic.sauvee@isab.fr

COLLECTIVE BRAND GOVERNANCE AND THE DESIGN OF INTERORGANIZATIONAL RELATIONSHIPS

Keywords: interfirm relationships, collective brands, governance, authority 1-Introduction

The development of joint actions in marketing challenges the theory, mainly because it shifts research objectives towards the design of organizational relationships. Focused on one type of joint actions, the collective brand, we summarize the main findings of researchers in the field of transaction-cost analysis. Considering that a collective brand is the result of an interorganizational strategy, we propose an analytical framework helping to understand the design of interorganizational relationships. We identify the endogeneous variables determining the organizational choices. Then we propose a two-step model focused on the allocation of decision rights and on governance mechanisms.

A collective brand is a brand which property and/or use is shared between several legally autonomous actors. Therefore a collective brand will systematically imply coordination among partners. This specific context places the design of interorganizational relationships at the core of the marketing strategy. Indeed these actors will have to create, sustain and guarantee the brand's reputation, both at individual and interfirm level. Several marketing theorists, mainly influenced by transaction-cost analysis (hereafter TCA) developed conceptual framework to understand the design of interorganizational relationships when there is a joint marketing action (cf for example [START_REF] Achrol | Changes in the Theory of Interorganizational Relations in Marketing: Toward a Network Paradigm[END_REF][START_REF] Anderson | Transaction Cost Analysis and Marketing[END_REF][START_REF] Bergen | Agency Relationships in Marketing: A Review of the Implications and Applications of Agency and Related Theories[END_REF][START_REF] Carson | Understanding Institutional Designs Within Marketing Value Systems[END_REF][START_REF] Rindfleisch | Transaction Cost Analysis: Past, Present and Future Applications[END_REF]. In a first part we summarize their main findings. Then we propose a conceptual framework to understand the design of interorganizational relationships between actors engaged in a collective brand. We show that two aspects are crucial in this design : (i) the allocation of decision rights leading to the definition of a collective authority, and (ii) the set up of governance mechanisms which purpose will be to mitigate all forms of contractual hazards found between agents.

2-Managing a collective brand: implications for the design of interorganizational relationships.

When creating a collective brand, actors will face two types of problems. First, when a collective brand is a source of value, it is also a potential source of conflicts. Each actor has an incentive to take over a wide part of the created value to the detriment of others, through opportunist behavior. For example each producer is incitated to free ride with regard to the collective reputation by not following the rules allowing to obtain the expected quality. Consequently the producers are placed in a situation of interdependence. Second, the agents cannot forsee all the contingencies which may arise during the progress of the cooperation, in particular when uncertainty is important. Therefore a complete contract to govern the relations is not a feasible alternative. These two problems emphasize the role of ex post and ex ante brand governance mechanisms. This situation is still enhanced because a collective brand, to be credible for consumers, must homogeneize in time and space all the individual marketing strategies.

Stemming from the TCA literature, the core principle for the choice of a governance form is the alignment principle : "Transactions, which differ in their attributes, are aligned with governance structures, which differ in their competences, in a discriminating way" [START_REF] Williamson | The Mechanisms of Governance[END_REF]. This alignment principle can be extended: the choice of a governance form has to be matched with the "nature of the situation at hand and the features of the selected governance mechanisms" (Heide 1994:83).

The basic assumption of TCA is that "the study of governance is concerned with the identification, explanation and mitigation of all forms of contractual hazards" (Williamson, 1996:5). Contractual hazards may be of various nature: a network of firms developping a collective brand is expected to face mutilateral dependencies and adptation problems. According to [START_REF] Ghosh | Governance Value Analysis and Marketing Strategy[END_REF], this general argument, for marketing decisions, turns into:

-Securing specific investments. This is the main prediction of transaction-cost economics. As long as agents cooperate in a strategy with an objective of value creation, they must provide safeguards in the exchange process. These safeguard clauses are a set of mechanisms implement to reduce contractual hazards between agents. This sends back to the type of co-investments made between the partners and to the contractual provisions of their interfirm relationships.

-Facilitating adaptation to external and internal uncertainty. In relational governance, because of the existence of long-term relationships without discretionary power (as in the hierarchical forms), governance mechanisms must allow adaptations. This situation is particularly frequent in marketing decisions, with the need to adapt to unforseeable situations such as evolution of markets, change in consumer needs, competitors' new marketing strategies...

-Acommodating performance measurement difficulties. The cost of effort measurement between the parties in the network also determines the way the value sustaining and claiming problem is managed. Usually, there is an equilibrium between the control (outcome-or behavior-based controls) and the monitoring designs [START_REF] Heide | Interorganizational Governance in Marketing Channels[END_REF]Stump 1996, Brown, Dev and[START_REF] Brown | Managing Marketing Channel Opportunism: The Efficacy of Alternative Governance Mechanisms[END_REF]. This statement will help us, in the following paragraph, to formalize a framework for the design of interorganizational relationships, in considering that multigovernance structures such as networks are a combination of these dimensions. Each of these dimensions will have a specific role in the management of the collective brand.

3-Collective brand governance : an analytical framework

A collective brand is the result of an interorganizational strategy. As suggested by Zaheer and Venkatraman (1995:375), relational governance has two main dimensions : the process (how the strategic decisions are made) and the structure (the result of these decisions). In our example the process deals with the variables, both exogeneous and endogeneous, that influences the organizational choices and the design of governance structures per se. Exogeneous variables deal with environment constraints. There are two types of constraints. The first one concerns sector and market characteristics, such as market size, concentration ratio, existing marketing strategies. These are the competitive environment constraints that are not managable by the incumbent firm. The second one is the institutional environment. Indeed, the set of existing rules is going to influence the relative costs of implementing alternative modes of governance forms, or event prevent some of them to be set up.

In our framework we will clearly focus on endogeneous variables. The owners and users of a collective brand have to arbitrate on two types of variables: the choice of a specific configuration (allocation) of decision rights regarding this brand, and the choice of governance mechanisms.

3-1 Collective brand and authority: the allocation of decision rights Following [START_REF] Stinchcombe | Information and Organizations[END_REF], Heide shows that, in relational governance situations, authority "can be achieved between firms by means of contractual provisions" (Heide 1994:74). As developed previously, we saw that ex post governance mechanisms are necessary to fill the gap of contract incompleteness. Authority, and consequently the allocation of decision rights, is central to the question of collective brand governance. This idea that authority can be achieved by other means than hierarchical governance but also by uni-or multilateral contractual provisions is central to the analysis of collective brand governance [START_REF] Bucklin | Organizing Successful Co-Marketing Alliances[END_REF].

The allocation of decision rights defines who takes decisions and the nature of these decisions. Such an allocation of decision rights determines the roles and mutual obligations of the parts. As showned by [START_REF] Raynaud | The Contractual Design of Governance Structure to Manage Shared Brand Name, 3rd conference of the ISNIE[END_REF], one must clearly distinguish between the design of the institutional arrangement in itself (its internal structure) and the interorganizational architecture, defined as the way the set of multilateral arrangements is organized. An ongoing research on collective brands [START_REF] Sauvée | Managing a Brand in the Tomato Sector: Authority and Enforcement Mechanisms in a Collective Organization[END_REF] showed that this interorganizational architecture leads to a central party, which role is to monitor the network. This central party will possess a certain number of rights: for example the right to control partners, to exclude or to coopt them.

As long as the allocation of decision rights coincides with property rights (i.e an independant firm responsible for its decisions) this identification is trivial. But, as authors like Ménard showed, in networks, there exists inevitably a specific decision mechanism in charge of some collective decisions, called authority. This concept of authority is defined as a "delegation by legally autonomous actors of decision power on a sub class of their actions". (Ménard 1997:746). Then a central party, which can be a firm, a third party or a negotiation structure, will be tailored to deal with some decisions.

In some cases, an assembly of co-owners will be in charge of marketing decisions such as promotional expenses. In a sense the franchisees create their own franchisor. In other cases, there is a negotiation structure which owns the brand, like in cooperatives. Through a delegation of individual rights, this negotiation structure will decide the strategic orientations of the brand. The partners in the network can also co-invest in a specialized company, in charge of the monitoring of the brand. Doing so the partners create a type of marketing jointventure. Formally, this 'central party' may take different forms. But its role is always to create a private order within a group of legally autonomous firms or actors.

3-2 Governance mechanisms for marketing decisions

The interorganizational architecture being defined, let us turn to the governance mechanisms themselves. For [START_REF] Brousseau | Incomplete Contracts and Governance Structures : Are Incomplete Contract Theory and New Institutional Economics Substitutes or Complements?[END_REF], there are three generic governance mechanisms: supervision, control and incentive, and litigation mechanisms. All of them may be seen as decision procedures to fill the gap of contract incompleteness and to enforce the contractual promises.

(i) Supervision mechanism. In a situation of relational governance, an entity (for example the franchisor in franchise system) has the formal right to make decisions about internal functioning and the evolution of the cooperation. It could be a modification of a brand's list of specification, investments in products promotion, launch of a new product. These decisions will be made in many cases by the central party. But, when the network is large and complex, this supervision mechanism can be divided in two parts: on the one hand the strategic decisions (for example the marketing strategy) and on the other hand more operational decisions (that are delegated to the partners) [START_REF] Sauvée | Managing a Brand in the Tomato Sector: Authority and Enforcement Mechanisms in a Collective Organization[END_REF].

(ii) Incentive and control/coercion mechanism. These mechanisms are designed to "incite the agents to follow the behavior required, or, on the contrary, to dissuade them from adopting behavior that are opposed to their commitments" (Brousseau and Fares 2000:411). To understand fully these mechanisms, we must consider that control and incentive are complementary. Control mechanisms are a necessary condition to protect the value of the collective brand. In order to limit the cost of control, there is a trade off between behaviorbased and outcome-based mechanisms (cf for example [START_REF] Stump | Controlling Supplier Opportunism in Industrial Relationship[END_REF]. This trade off will depend upon the information characteristics of the brand's value. But this necessary condition is not sufficient to fully understand the design of interorganizational relationships. The creation and the distribution of a stream of rents connected to the brand will create incentives, for the partners, to maintain the high value of the brand and its reputation. This may be done through the price system (for example a price premium for product quality) or by the threat of termination of the relationships.

(iii) Litigation mechanism. Behaviors of firms, in networks, may result in conflicts. These conflicts find their sources in voluntary or even involuntary opportunist behaviors. In any case, it is necessary to design a mechanism to deal with such situations: exact extent of rights and duties of the parties, formal and informal arbitration processes, designation of arbitrators. Many other means, such as relational norms or corporate identity, may be used to limit conflicts. But the existence of litigation mechanisms is also a way to indirectly limit opportunist behavior through a fear of exclusion from the network.

In spite of the wide variety and diversity of devices inside each type of mechanism, ongoing research in that field showed that these three generic mechanisms are found in every network situations. It plays the role of invariant schemes in front of universal contractual hazards: adverse selection, moral hazards, free riding. But the ability to protect in the long run the value of the collective brand is determining for the success of the cooperation [START_REF] Madhok | Resources, Transactions and Rents: Managing Value Through Interfirm Collaborative Relationships[END_REF].

4-Concluding comments

Drawing from the existing literature on relational governance and from empirical researches, we suggest that the governance of collective brands must adress clearly the design of interorganizational relationships on two aspects: first, in the recognition of an authority principle to fill the gap of joint action incompleteness; second, in the set up of governance mechanisms which rationale is to be find in the mitigation of contractual hazards. The contractual hazards linked to the common ownership and use of a collective brand are mainly network externalities. Therefore the design of interorganizational relationshisps will be the result of choices made to guarantee the flexibility for enforcing decisions in a changing environment while securing the network's partners in the value of their collective brand. In that perspective, the challenge of future research is to understand more completely how firms engaged in a collective brand strategy try to optimize the institutional design of their relationships under efficiency principle.

5-References


est destinée au dépôt

Conditions d'émergence des filières innovantes : propositions pour un agenda de recherche sur les bioraffineries végétales

Ion Lucian Ceapraz, Gaëlle Kotbi, Loïc Sauvée, Frédéric Huet, Pascal Jollivet,

Yann Moulier Boutang

To cite this version:

  Induit par cette nouvelle révolution industrielle associant les démarches de l'écologie industrielle et de l'économie de proximité dans un contexte de rupture avec le modèle des économies post industrielles basées sur les énergies fossiles, l'émergence des bioraffineries végétales suppose de repenser la façon dont se constituent les filières de production lorsqu'il y a raréfaction des ressources énergétique à bas prix et essor des technologies de la communication. Il devient notamment nécessaire de repenser la création de valeur des biens agricoles et agroindustriels produits en fonction de leur place dans des modes de valorisation et dans les cycles de vie bioénergétiques globaux L'approche éco systémique ainsi considéré permet l'internalisation et la valorisation d'externalités (tant négatives que positives) ainsi que Ed.) (2011) Rethinking business models. Lessons from entrepreneurial projects. On line at http://halshs.archives-ouvertes.fr/docs/00/58/35/95/PDF/RethinkBusinessModelsforInnovationV2.pdf LANGEVELD J.W.A, SANDERS J.P.M. 2010. The biobased bioeconomy: biofuels, materials and chemicals in the post-oil era. London: Earthscan.

	interorganisationnels à l'oeuvre quand se mettent en placent ces modes d'organisations
	« Industrie, villes et régions dans une économie mondialisée » d'activités économiques radicalement nouvelles.
	9, 10 et 11juillet 2012
	4. Résultats attendus
	Belfort La communication explore les voies de recherches et les questions programmatiques à
	UMR ThéMA, l'interface de ces axes, et notamment : modes d'organisation des activités productives et
	Conditions d'émergence des filières innovantes : propositions pour un insertion dans des écosystèmes locaux, interactions et apprentissages multi locaux (à l'échelle
	agenda de recherche sur les bioraffineries végétales de l'entreprise, du bassin de production, de la filière), dimensions locales de l'organisation
	économique et phénomènes d'apprentissage. Le positionnement de la recherche, positive
	la valorisation d'actifs intangibles associés (confiance, coopération, innovativité, labels et et/ou normative dans une démarche constructiviste, sera également précisé. La méthode
	Lucian CEAPRAZ , Gaëlle KOTBI, Loïc SAUVEE (PICAR-T, LaSalle Beauvais) marque) employée est essentiellement exploratoire et qualitative, conduite à partir d'une revue de la
	Frédéric HUET, Pascal JOLLIVET, Yann MOULIER BOUTANG (COSTECH, UTC) littérature à mobiliser.
	3. La discussion
	objectif de valoriser la plante entière à partir du concept de bioraffinerie végétale. Les équipes
	de recherche PICAR-T (LaSalle Beauvais) et COSTECH (UTC) participent au module de
	travail intitulé «Bio raffinerie : vers un métabolisme industriel». Dans ce module, est explorée
	la question de la faisabilité économique, institutionnelle et organisationnelle de ces nouvelles
	filières, en lien avec les modes d'organisation de la production agricole, de l'agrofourniture,
	de la collecte et de la première transformation. Les conditions de la constitution d'un
	écosystème agroindustriel minimisant l'impact énergétique et environnemental associant Références bibliographiques
	BIOREFINERY OVERVIEW, 2009. Report on the different concepts of existing European
	biorefineries.
	CHANAL V. (
	Le deuxième axe d'approche s'interroge sur les conditions d'émergence et de pérennité
	d'écosystèmes locaux/régionaux associant acteurs du monde économique, de la recherche et
	du monde institutionnel. Pour concilier les enjeux d'environnement global et de
	développement local, il est nécessaire d'intégrer les deux approches dans les politiques,
	qu'elles soient forestières, environnementales ou agri-territoriales. Le troisième axe
	d'approche prend pour objet l'analyse les phénomènes d'apprentissage interindividuels et

Ion Lucian Ceapraz, Gaëlle Kotbi, Loïc Sauvée, Frédéric Huet, Pascal Jollivet, et al.. Conditions d'émergence des filières innovantes : propositions pour un agenda de recherche sur les bioraffineries végétales. 49ème colloque ASRDLF 2012 " Industrie, villes et régions dans une économie mondialisée ", UMR ThéMA, Jul 2012, Belfort, France. hal-04313165 Objectif de la communication Dans le cadre des IEED (Instituts d'Excellence en Energies Décarbonées) le projet PIVERT-GENESYS (Picardie Innovation Végétale Enseignement Recherche et Technologie) a pour l'agriculture et les activités de recherche et développement sont au centre de l'analyse. Cela suppose que soient élaborées de grilles d'analyse en rupture avec les schémas traditionnels de l'économie basés sur le modèle agroindustriel centralisé et dispendieux en consommation d'énergie. Dans un nouveau mode coopératif et distribué, des notions telles que la proximité, l'apprentissage, l'économie contributive, l'organisation en réseaux, l'interaction et la qualité de vie des individus, se trouvent au centre des approches. Dans ce contexte l'objectif de la communication est de préciser les jalons pour un agenda de recherche dans ce domaine. 2. Originalité du sujet La discussion est organisée en articulant les trois axes d'approche du module de travail. La communication se propose dans un premier temps de développer ses trois axes de manière spécifique, en lien avec les travaux déjà existants et leurs applications dans les secteurs de la bioraffinerie végétale. Le premier axe d'approche interroge les modes de gouvernance de nouveaux systèmes de cultures dédiées aux bioraffineries. La concurrence/complémentarité des productions alimentaires et agroindustrielles supposent en effet que soit développées des structures de gouvernance intégrant des modes de pilotage, de contrôle et d'incitation spécifiques. Il s'agit ici de prendre notamment en compte la gouvernance organisationnelle de l'approvisionnement de la bioraffinerie vue comme un ensemble d'entreprises (gouvernance de filière) associée à sa traduction territorialisée. Il s'agit d'un processus fondé sur la mobilisation progressive des acteurs et sur l'émergence de leaders et de porteurs de projets, ce qui conduit à une interdépendance entre les pouvoirs et les institutions associées à l'action collective. Ses progrès et sa pertinence constituent une réponse politique aux défis écologiques et à ceux du développement économique qui en dépend. Les résultats attendus consistent en l'élaboration d'un agenda de recherche original susceptible d'explorer toutes les facettes de nouveaux écosystèmes agroindustriels en émergence autour des bioraffineries. Outre l'intérêt de la perspective syncrétique de la démarche, la recherche peut constituer un premier pas vers la constitution de cadres d'analyse intégratifs susceptibles de mieux comprendre les conditions d'émergence socio économique et organisationnelle de ces filières innovantes. Mots clés : bioraffinerie végétale, écosystème, apprentissage, proximités, agriculture Star COLIBRI. 2010. Background information and biorefinery status; potential and sustainability.