Omer Biran

Core stable bidding rings in independent private value auctions with externalities

Keywords: Auctions, collusion, externalities, Bayesian games, core, partition function game, mechanism design. JEL classification: C71, C72, D44

We consider a second price auction between bidders with independently and identically distributed valuations, where a losing bidder suffers a negative direct externality. Considering ex-ante commitments to form bidding rings we study the question of core stability of the grand coalition, namely: is there a subset of bidders that prefers forming a small bidding ring rather than participating in the grand cartel? We show that in the presence of direct externalities between bidders the grand coalition is not necessarily core stable, as opposed to the zero externality case, where the stability of the grand coalition is a known result. Finally, we study collusion in auctions as a mechanism design problem, insisting on the difficulty to compare ex-ante and interim commitments. In particular, we show that there are situations in which bidders prefer colluding before privately learning their types.

Introduction

The question of collusion in auctions receives great attention in the auction theory literature. From an empirical point of view, there is clear evidence 1 of collusion in real life auctions and auction-like situations, although strictly prohibited in many countries. From a theoretical point of view, collusion in auctions provides a great challenge as the formation of bidding rings violates the symmetry between bidders, which is a common assumption in auction theory.

We address the question of collusion in auctions in the presence of direct externalities between bidders, focusing on the grand coalition, i.e., a bidding ring that includes all bidders. We examine the core stability of the grand coalition, as early as in the ex-ante stage, namely, before bidders learn their types. Our main goal is to answer the question: Is the grand coalition plausible in the presence of externalities, in the sense that no group of bidders prefers seceding?

A 3-player art auction example

The following example demonstrates the motivation to our work. Consider three art collectors who wish to acquire a valuable piece of art in a future auction. We assume that the object receives a restricted attention in the market, and that the three art collectors are the only possible potential bidders, a fact which is common knowledge. For the time being the auction house publishes a catalog with some details about the art object, however, the object itself is not yet available for close examination by the interested potential bidders or experts on their behalf. As such an examination is necessary in order to determine the true value of such a valuable object (e.g., to determine how well preserved it is), the three collectors can only have a rough estimation regarding their valuations in the planned auction. We, therefore, interpret this stage as the ex-ante stage.

As art collectors extremely vary in their personal preferences (e.g., personal taste), the value that they assign to the good (once it is finally accessible for a close inspection) is considered private.

A losing bidder in this example suffers a negative utility (i.e., direct externality). For instance, if the auctioned object is part of a collection, losing the auction may result in a decrease of value of other works of art that the losing collector already owns from the same collection. 1The formation of a bidding ring prior to the auction can be profitable. For instance, full cooperation between the three collectors will eliminate com-pletely the competition in the auction (bid rigging), allowing them to win the object for a low price. Note, however, that in such a case the collector who will eventually own the good will most probably need to compensate the other ring members for their expected loss (i.e., externality). The presence of externalities may therefore interfere with cooperation.

We wish to see to which extent, in the presence of externalities, an ex-ante commitment of the grand coalition is plausible, in the sense that no group of players wishes to secede. In example 5.1 we demonstrate a market where a player, anticipating that the two other players will continue cooperating if he secedes, finds it profitable to deviate in the presence of externalities. 2 In such a setup, the grand coalition is said to be "instable".

Related Literature

Empirical evidence of collusion, and in particular of partial collusion, i.e., bidding rings which do not include all bidders, can be found in the work of [START_REF] Porter | Ohio school milk markets: an analysis of bidding[END_REF] who find proof of bid rigging in school milk procurement in Ohio, as well as in [START_REF] Porter | Detection of bid rigging in procurement auctions[END_REF] who study Long-Island highway construction contracts. [START_REF] Bajari | Deciding between competition and collusion[END_REF] study collusion in Midwest seal coats contracts. In particular, these studies provide some interesting links between observed bidders' behavior and theoretical notions. For example, [START_REF] Porter | Detection of bid rigging in procurement auctions[END_REF] describe bidding rings that participate in several auctions, which can be interpreted as an ex-ante commitment, as ring members commit to cooperate in several auctions before learning the considered auctions' details, and in particular, before learning their private types.

With the help of mechanism design tools, the question of collusion in private value auctions without externalities was studied in, e.g., [START_REF] Mcafee | Bidding rings[END_REF] who consider first price auctions, Mailath and Zemsky (1991), and [START_REF] Graham | Collusive bidder behavior at single-object second-price and English auctions[END_REF] who study collusion in second price auctions, and [START_REF] Marshall | Bidder collusion[END_REF] and [START_REF] Robinson | Collusion and the choice of auction[END_REF] who compare between first and second price auctions in order to find which is more vulnerable to bidder collusion.

We follow the model of markets with direct externalities between players, which was studied by [START_REF] Caillaud | Collusion in auctions with externalities[END_REF] and [START_REF] Jehiel | Multidimensional mechanism design for auctions with externalities[END_REF] in incomplete information setups, as well as by Jehiel andMoldovanu (1996, 1999) and [START_REF] Jehiel | How (not) to sell nuclear weapons[END_REF] in complete information. [START_REF] Caillaud | Collusion in auctions with externalities[END_REF] study collusion in identically distributed independent private value second price auctions with direct externalities, however, they do not consider the seceding of coalitions but of individuals only. The question of partial collusion, i.e., the formation of bidding rings smaller than the grand coalition, in complete information auctions with direct externalities was studied by [START_REF] Biran | Strategic partial collusion in auctions with externalities[END_REF].

The property of core-stability, to which we refer in this paper, was presented by [START_REF] Biran | Core-stable rings in auctions with independent private values[END_REF], who develop tools to study the plausibility of coalitions in Bayesian games. They propose an application of core-stability of bidding rings in independent private value (first and second price) auctions. They also consider examples of instability in the presence of direct externalities with complete information. One of the key notions in their work, which naturally plays an important role in the current paper as well, is coalitional equilibrium in games with incomplete information, extending the work of [START_REF] Ray | Equilibrium binding agreements[END_REF] and [START_REF] Ray | A game-theoretic perspective on coalition formation[END_REF]. When discussing core stability we rely on two basic core notions, the core with merging expectations introduced by [START_REF] Maskin | Bargaining, coalitions and externalities[END_REF], and the core with singleton expectations introduced by [START_REF] Hafalir | Efficiency in coalition games with externalities[END_REF].

Following [START_REF] Biran | Core-stable rings in auctions with independent private values[END_REF] we focus on core-stability in the exante stage. The literature which deals with ring formation in the ex-ante stage includes, e.g., [START_REF] Bajari | Comparing competition and collusion: a numerical approach[END_REF], [START_REF] Waehrer | Asymmetric auctions with application to joint bidding and mergers[END_REF], and [START_REF] Marshall | Numerical analysis of asymmetric first price auctions[END_REF]. The question of ex-ante commitment to an incentive compatible (I.C.) mechanism was addressed by, e.g., [START_REF] Forges | The ex ante incentive compatible core in the absence of wealth effects[END_REF] and [START_REF] Forges | A note on the incentive compatible core[END_REF].

Core-stability

As in the model of [START_REF] Caillaud | Collusion in auctions with externalities[END_REF], we consider a second price auction with a reserve price organized between a set of bidders with independent private values which are identically distributed. A losing bidder suffers a deterministic negative externality which is not identity dependent and hence assumed to be of common knowledge.

As we wish to study bidder collusion, given a partition of bidders, we define an auxiliary auction game in which the players are bidding rings, namely, cells in the considered partition.

Consider the existence of a Nash equilibrium in every auxiliary game, with respect to ex-ante expected utilities. In other words, for every bidder partition assume the existence of a coalitional equilibrium of a second price auction held between the bidding rings in this partition. Such a mapping of bidder partitions to coalitional equilibria, defines a partition form game (see, e.g., [START_REF] Lucas | n-person games in partition function form[END_REF]), in which the value of a coalition (given a partition in which it is a cell) is its ex-ante expected utility in a Nash equilibrium of the corresponding auxiliary game. [START_REF] Biran | Core-stable rings in auctions with independent private values[END_REF] prove that with appropriate transfer payments between coalition members a coalitional equilibrium can be made I.C. More precisely, the latter results from their proposition 1 where they show that for any coalition S, given a strategy of the others and a best response for S, there exists a mechanism for S, composed of an exactly balanced transfer scheme between the members of S and the best response strategy of S, such that this mechanism is I.C. We therefore assume, thus WLOG, that types are common knowledge inside a coalition. In particular, the type of a bidding ring in the auxiliary game is the highest valuation of its members (net of their externalities).

Consider a mapping which determines the conjecture of every coalition on the behavior (i.e., partitioning) of the others if it decides to deviate and secede from the grand coalition. Namely, to every coalition we assign a partition in which it is a cell. With respect to this mapping the previously described partition form game reduces to a characteristic form game. The grand coalition is said to be core-stable if the core of this characteristic form game is not empty. The interpretation is that the grand coalition is plausible as no subset of bidders has an interest to deviate.

In order to examine the question of the stability of the grand coalition in auctions with externalities, we start by proving the existence of a coalitional equilibrium for any given bidder partition. Note that as opposed to the non-collusive auction game in which bidders are symmetric, in an auxiliary auction game the "bidders" (i.e., bidding rings) are asymmetric. Symmetry between bidders is violated in two senses in the auxiliary auction game. First, while bidders' valuations are distributed identically in the non-collusive auction, in the auxiliary auction each bidding ring has a different distribution which depends on its size. That is as the type of a bidding ring is the maximal valuation of its members.

Second, in the non-collusive auction externalities on a losing bidder are not identity dependent. A losing bidder suffers the same externality regardless of his (or the winner's) identity. In an auxiliary auction it is no longer true. The externality of a losing ring is cumulative and is a function of its size, as every member of the ring suffers a personal externality due to a loss. These two aspects of asymmetry introduce significant complications in the equilibrium analysis.

In this model Caillaud and Jehiel (1998) already identified an equilibrium in symmetric auctions with externalities where all bidders act individually (i.e., no bidding rings are allowed). They proved that bidding the difference between one's type and the externality term whenever the type exceeds the reservation price (and making an irrelevant bid otherwise) is in equilibrium. The reservation price therefore serves as a participation threshold for bidders. This equilibrium, however, depends crucially on the fact that bidders have identical distribution functions, and does not extend to asymmetric setups, where bidding rings (with nonidentical distribution functions) are considered.

In order to prove the existence of equilibrium in asymmetric collusive auctions (i.e., the auxiliary auction game), where each participating bidding ring has a different distribution function, we borrow the idea of participation thresholds. We prove that for any collusion scheme (i.e., bidder partition) there exist in the corresponding (asymmetric) auxiliary auction game participation thresholds which constitute an equilibrium. Specifically, given a strategy of the others, a ring has a threshold type between the reservation price and the sum of the reservation price and the ring's negative externality, such that if the ring's type is higher than its threshold type its best response is to bid the difference between its type and its externality, and whenever its type is lower than the threshold type its best response is to make an irrelevant bid.

We then rely on two specific mappings defining the conjecture of a seceding coalition regarding the partitioning of the others, starting with [START_REF] Maskin | Bargaining, coalitions and externalities[END_REF] merging expectations (see also, [START_REF] Hafalir | Efficiency in coalition games with externalities[END_REF]). With merging expectations a seceding coalition expects the others to form the complementary coalition. Such an assumption yields an auxiliary auction game with two (usually asymmetric) bidders. Afterwards we consider the case where due to the secession of a coalition cooperation breaks down completely, as a result of which bidders outside the seceding coalition act individually. [START_REF] Hafalir | Efficiency in coalition games with externalities[END_REF] refers to such a scenario as singleton expectations. It yields an auction game in which a "strong" bidder competes with "weak" bidders (see also, e.g., [START_REF] Maskin | Asymmetric auctions[END_REF]). We compute explicitly the participation thresholds of the coalitions in these two cases.

Once the equilibrium analysis is completed and the question of stability is to be addressed, for the sake of simplicity, we restrict our attention to an auction with three bidders. 3 As opposed to the case without externalities in which the grand coalition is stable (see, e.g., [START_REF] Mailath | Collusion in second price auctions with heterogeneous bidders[END_REF]), we demonstrate that in the presence of externalities a bidder with merging expectations may prefer acting individually rather than participating in the all-bidders cartel. We therefore conclude that externalities may lead to the instability of the grand coalition.

As a last part of the paper we study collusion in auctions with externalities as a mechanism design problem, insisting on the differences between exante and interim collusion. More specifically, we look at collusive ex-post efficient mechanisms which are budget-balanced and incentive compatible and compare interim individual rationality with ex-ante group participation constraints.

As a benchmark we refer to the results of [START_REF] Mailath | Collusion in second price auctions with heterogeneous bidders[END_REF] in second price auctions without direct externalities. They prove the existence of such collusive mechanisms with ex-ante group participation constraints. In the presence of direct externalities Caillaud and Jehiel (1998) identify a necessary and sufficient condition for the existence of an ex-post efficient mechanism for the grand coalition which is budget-balanced, incentive compatible and satisfies interim individual rationality. Translating our results as described above, (obtained in a model similar to the one of Caillaud and Jehiel (1998)), to the language of mechanism design, the grand coalition being core-stable means the existence of an ex-post efficient mechanism for the grand coalition which is budget-balanced, incentive compatible and satisfies ex-ante group participation constraints.

In order to show that the ex-ante and interim approaches are not logically comparable we give two examples. In the first the grand coalition has an ex-post efficient mechanism, which is budget balanced, incentive compatible and satisfies interim individual participation constraints but not ex-ante group participation constraints. In the second example the grand coalition has an ex-post efficient mechanism which is budget-balanced, incentive compatible and satisfies ex-ante group participation constraints but is not interim individually rational.

We insist that although interim individual rationality is stronger than ex-ante individual rationality, comparing ex-ante and interim commitments is difficult. [START_REF] Biran | Core-stable rings in auctions with independent private values[END_REF] explain this difficulty by saying that the decision of a coalition to block in the interim stage is a function of its conditional expected utility given the types of its members, and therefore one cannot use a straight forward transfer scheme for the grand coalition in order to ensure that no coalition would block interim (as opposed to ex-ante blocking). Finally, we conclude from this discussion that there are situations in which the grand coalition would try to collude in the ex-ante stage (given that such a stage can be identified), rather than letting the players learn their types before asking them to commit. Our paper takes the following form: Section 2 presents the model. In section 3 we prove the existence of coalitional equilibrium in auctions with asymmetric bidders for any given bidder partition. In section 4 we compute the participation thresholds of bidding rings with merging and singleton expectation, which are used in section 5 to demonstrate the instability of the grand coalition in the presence of externalities. In section 6 we study collusion in auctions with externalities as a mechanism design problem, and section 7 concludes. In appendix A we bring the proof of coalitional equilibrium with singleton expectations, and appendix B presents simulations of core stability of the grand coalition with singleton expectations.

Model

Second price auction with externalities

As in Caillaud and Jehiel (1998) we consider a single indivisible object second price auction Γ with a reserve price R > 0, held in a market with a set of bidders N = {1, 2, ..., n}. Bidder i assigns a valuation t i to the object, which is the utility he derives from the object if winning it. The valuation, or type, of i is private, and is identically and independently distributed with respect to a common continuous density f > 0 in [t, t], with distribution F .

Additionally, symmetric direct external effects are considered. Specifically, a losing bidder suffers a negative externality e < 0. The externality term is not identity dependent. Namely, every losing bidder gets a utility equals to e regardless of his or the winner's identity. The externality is, therefore, assumed to be of common knowledge. For the sake of simplicity we assume that the parameters maintain t < R + e as well as R < t. The interpretation is that a highest type bidder is expected to participate in the auction, whereas a lowest type is not. 4Let b ∈ R n + be a bidding vector. If no bidder makes a relevant bid, i.e., max j∈N b j < R then the seller keeps the good and all bidders get a utility normalized to zero. Otherwise, the good is allocated to the bidder who makes the highest bid, i, for the second highest relevant price: p = max{R, max j =i {b j }}. Considering quasi-linear utilities, i gets t i -p, while every other bidder suffers the externality e. In case of a tie we assume that each of the bidders who placed the highest bid wins with equal probability.

The auxiliary collusion game

We extend now the auction game to consider bidding rings. Note P a partition of N , where the interpretation is that S ∈ P is a bidding ring. We note t S the valuation of such a ring, defined by t S = max i∈S t i + (s -1)e, where s = |S|, as a bidding ring wishes to maximize its profit.

Clearly, when defining the valuation of a coalition in this way we assume full revelation of information between coalition members. This assumption is WLOG as [START_REF] Biran | Core-stable rings in auctions with independent private values[END_REF] show that a given coalitional equilibrium can be made I.C. with appropriate transfers within each coalition. 5 Types are therefore common knowledge inside a coalition. Hence, the distribution of a coalition's type in terms of the original distribution F is:

F S (t) = (F (t -(s -1)e)) s (2.1)
for all t ∈ [t+(s-1)e, t+(s-1)e]. Additionally, if S does not win the auction it suffers an externality e S = se. Note, that the formation of coalitions clearly violates the symmetry in the market in two different senses. First, valuations of "bidders", i.e., bidding rings, in a collusive auction are not identically distributed, as F S depends on the size of S. Second, the externality of a losing ring depends on its identity as e S is a function of |S|.

Given a partition P we can therefore consider the auxiliary auction game Γ(P ) where players are coalitions in P . Let b ∈ R |P | + be a bidding vector in Γ(P ), where the interpretation is that in every coalition the highest valuation ring member makes a relevant bid, while the other members of the coalition make irrelevant bids (below the reservation price) which can be conveniently ignored. Once again, WLOG we may assume full revelation of information within a coalition, hence, such a definition of a bidding vector in Γ(P ) is justified.

As before, if there is no relevant bid, i.e., max S∈P b S < R then the seller keeps the good and all coalitions get a null utility. Otherwise, the good is allocated to the coalition S that made the highest bid, for the second highest relevant price: p = max{R, max T =S {b T }}. S derives therefore a utility of t S -p, while every other coalition suffers the (identity dependent) externality e S . In case of a tie we assume that each of the coalitions that placed the highest bid wins with equal probability.

Core-stability of the grand coalition

Following Biran and Forges (2011) we address the question of the stability of the grand coalition, applied to the considered second price auction. Roughly speaking, they say that the grand coalition is core-stable if the core of the underlying cooperative game is non-empty.

As a first step in defining the underlying characteristic function, they consider for every coalition S ⊂ N , a partition B(S) such that S ∈ B(S). B(S) is interpreted as the conjecture of S on the partitioning of the rest of the players, N \ S, if S secedes.

Assume the existence of a coalitional equilibrium mapping σ (see, e.g., [START_REF] Ray | A game-theoretic perspective on coalition formation[END_REF]). Namely, for every partition P of N , σ(P ) is a Nash equilibrium of Γ(P ). With respect to σ, Biran and Forges (2011) derive a characteristic function, w B σ , which assigns to every coalition S its (ex-ante) expected utility in the equilibrium σ(B(S)) of the auxiliary game Γ(B(S)).

Finally, as mentioned above, they say that with respect to the mappings σ and B the grand coalition is core-stable if the core of w B σ is non-empty. In order to examine the stability of the grand coalition in auctions with externalities, we start by proving the existence of a coalitional equilibrium mapping σ (see, section 3). We then compute the coalitional equilibria given two specific examples of (symmetric) mappings B (see, section 4). 6 Finally, we compute the corresponding characteristic functions w B σ (see, sections 5). As the grand coalition may win the auction by offering the reserve price, or alternatively get a zero utility if not participating (no trade), it participates in equilibrium if and only if the highest valuation of its members net of the reserve price is greater than the externalities of the other two members. The value of the grand coalition is therefore:

w B σ (N ) = w(N ) = E((max i ti + (n -1)e -R)I(max i ti + (n -1)e > R)) (2.
2) where, ti is a random variable with distribution F , and I is the indicator function. Obviously, the value of the grand coalition does not depend on the mappings σ and B (see also, e.g., [START_REF] Biran | Core-stable rings in auctions with independent private values[END_REF]). If the core of the underlying cooperative game is not empty, then by symmetry, the allocation in which every agent gets an equal share of the value of the grand coalition is in the core. More precisely, the core is not empty if and only if it contains the following payment vector:

w B σ (N ) n n i=1 (2.3)
Hence, in order to prove the instability of the grand coalition, it suffices to identify a coalition S, such that:

w B σ (N ) n < w B σ (S) |S| (2.4)
Example 5.1 demonstrates a case where (2.4) holds for a singleton (i.e., |S| = 1) in a 3-bidder auction, illustrating the instability of the grand coalition in the presence of externalities. 73 Coalitional equilibrium [START_REF] Caillaud | Collusion in auctions with externalities[END_REF] prove that in a symmetric market, if no bidding rings are considered, then for every distribution F there exists an equilibrium in the auction, where a bidder bids his valuation augmented by the externality term if his valuation is greater than the reserve price, and 0 otherwise. We refer to such a strategy as a participation threshold bidding strategy with a threshold R:

σ i (t i ) = t i -e If t i > R 0 Otherwise (3.1)
We revise their analysis to establish the existence of equilibrium in threshold strategies in collusive auctions. Fix a partition P of N and a coalition S ∈ P . For all types t S of S and bids b ∈ R

|P |

+ of the participants in the auxiliary game Γ(P ), we denote u S (t S ; b) the utility of S of type t S in Γ(P ) when b is played, as defined in section 2.2. Conveniently, we denote b -S the bidding vector of all the participants but S. Consider the following lemmas: The proofs of the lemmas are analogous to Caillaud and Jehiel (1998) and are therefore omitted. Loosely speaking, we conclude from the lemmas that in a collusive auction every bidding ring S has a "dominant" strategy (except for the interval [R + se, R], where a "monotonous" behavior maintains).

Lemma 3.1. ∀b -S , ∀t S < R + se, ∀b S ≥ R u S (t S ; (0, b -S )) ≥ u S (t S ; (b S , b -S )) Lemma 3.2. ∀b -S , ∀t S ≥ R + se, ∀b S ≥ R u S (t S ; (t S -e S , b -S )) ≥ u S (t S ; (b S , b -S )) Lemma 3.3. ∀b -S , ∀t S > R, ∀b S < R u S (t S ; (t S -e S , b -S )) ≥ u S (t S ; (b S , b -S )) Lemma 3.4. ∀b -S , ∀(t S , t S ), t S > t S ≥ R + se, if u S (t S ; (t S -e S , b -S )) ≥ u S (
Specifically, if the type of S is lower than R + se its "best response" is not to participate regardless of the actions of the others as by winning it gets a utility lower than its externality (lemma 3.1). If its type is higher than the reserve price it should participate by bidding its type augmented by its externality (lemmas 3.2 and 3.3). Finally, if an intermediate type in the interval [R + se, R] prefers participating then any higher type prefers participating as well (lemma 3.4). It follows that given any strategy of the others there exist a participation threshold strategy which is a best response. The existence of the following tractable equilibrium in threshold strategies follows.

Proposition 3.5. Let P be a partition of N . Then for all S ∈ P there exists t * S ∈ [R + e S , R] such that the following (σ S ) S∈P is an equilibrium of Γ(P ):

σ S (t S ) = t S -e S If t S > t * S 0 Otherwise (3.2)
We refer to t * S as the participation threshold of S in the equilibrium σ. An immediate implication of the proposition is that for a given valuation, the bigger a coalition is, the higher it is likely to bid if participating. The intuition is quite clear, as a big coalition suffers a greater externality if losing.

Finally, proposition 3.5 provides the coalitional equilibrium mapping σ which will be used to demonstrate the instability of the grand coalition in the presence of externalities (see, example 5.1).

Participation threshold

We wish to compute the coalitional equilibrium (namely, the participation threshold of a coalition) identified in the previous section in two specific cases. We start with the case where the complementary of a seceding coalition forms due to a secession. Then, we go on with the case where cooperation breaks down completely due to the secession of a coalition, namely, all players outside the seceding coalition act individually. The first case corresponds to the core with merging expectation (m-core) introduced by Maskin (2003), while the second case corresponds to the core with singleton expectations (s-core) introduced by Hafalir (2007).

Merging expectations -The two cartels case

Let us start with an analysis of the participation threshold of a coalition which expects its complementary to act cooperatively if seceding, i.e., ∀S ⊂ N, B(S) = {S, N \ S}. Suppose, thus WLOG, that |S| > |N \ S|. 8 We first claim (proposition 4.1) that there exists an equilibrium in threshold strategies where the participation threshold of the smaller coalition is simply the reserve price, while that of the bigger one is in the interval [R -e N \S + e S , R]. We then derive an explicit expression of the latter. Proof. Suppose first that N \S follows a bidding strategy with a participation threshold equals to R. From the preceding analysis we conclude that there exists a best response strategy for S with a threshold t * S ∈ [R + e S , R]. Let us compute the interim utility of S of type t S ≥ R + e S if it chooses to participate in the auction and if it chooses not to participate. If S makes an irrelevant bid, then it gets 0 if N \ S does not participate as well, and e S otherwise, which yields:

seP ( tN\S > R) (4.1)
where, |S| = s and tN\S denotes a random variable with distribution F N \S .

If on the other hand S chooses to participate, we distinguish between 3 cases. Either, N \ S does not participate in which case S wins the good for the reserve price. Or, N \ S participates and wins, in which case S gets its externality. Or, finally, both coalitions participate and S wins, paying the bid of N \ S. Note that as we consider threshold strategies, if a coalition chooses to participate it bids the difference between its type and its externality (see, (3.2)). The interim utility of S if participating is therefore: where, |N \ S| = n -s and I is the indicator function. As we consider continuous distribution, ties occur with zero probability with respect to threshold strategies.

(t S -
As the interim utility functions of S if participating, (4.2), or not participating, (4.1), are continuous with respect to the type of S, we conclude that in equilibrium, S of threshold type t * S is indifferent between participating or not. Namely, replacing t S with t * S in (4.1) and (4.2) yields an equality: In order to compute the participation threshold of the bigger coalition, we derive from (4.3):

seP ( tN\S > R) = (t * S -R)P ( tN\S ≤ R) + seP ( tN\S >
9 0 = -se(1 -(F (R -(n -s -1)e)) n-s ) + (t * S -R)(F (R -(n -s -1)e)) n-s + se(1 -(F (t * S -(s -1)e)) n-s ) + t * S +(n-2s)e R (t * S -t + (n -s)e)(n -s) (F (t -(n -s -1)e)) n-s-1 f (t -(n -s -1)e) dt (4.6)
which, by integration in parts, gives a characterization of t * S in the considered case:

0 = -(n -2s)e(F (R -(n -s -1)e)) n-s + t * S -(s-1)e R-(n-s-1)e (F (t)) n-s dt (4.7)
Note, that there exists a unique threshold satisfying (4.7) as the function

h(τ ) = -(n -2s)e(F (R -(n -s -1)e)) n-s + τ -(s-1)e R-(n-s-1)e (F (t)) n-s dt, τ ∈ [R -(n -2s)e, R]
, is strictly increasing and maintains h(R -(n -2s)e) ≤ 0 and h(R) ≥ 0.

Singleton expectations -The cartel vs. individuals case

We repeat the previous analysis in a market where due to the secession of a coalition, cooperation breaks down completely. As a result of which, all players outside the seceding coalition act individually, namely, ∀S ⊂ N, B(S) = {S, {i} i / ∈S }. We prove in a similar way (see, appendix A) that each individual participates if his type is greater than the reserve price while the coalition participates if its valuation exceeds some t Finally, as in the previous section we derive the following characterization of t * S in the considered case:

0 = (s -1)e(F (R)) n-s + t * S -(s-1)e R (F (t)) n-s dt (4.8)
As before, there exists a unique threshold satisfying (4.8).

Stability in a 3-player market with externalities

We consider a symmetric market with 3 players, as it is the smallest market in which the instability of the grand coalition can be demonstrated. 10 Mailath and Zemsky (1991) prove that in a standard second price auction, without direct externalities, the grand coalition is core-stable, namely, no subset of bidders has a profitable deviation. We wish to go further and examine the stability of the grand coalition in the presence of externalities.

Coalitions' values

In order to verify (2.4), namely, to compare the per-capita utility of a seceding coalition with the per-capita utility in the grand coalition, we compute the values of the different coalitions. Let us start with the value of the grand coalition. Consider, therefore, the auxiliary game Γ({1, 2, 3}). Recalling (2.2), the value (or, ex-ante utility) of the grand coalition is,

v = E((max i ti + 2e -R)I(max i ti + 2e > R)) (5.1)
Consider now a seceding coalition of two, denoted S. Note, that its value, denoted y, does not depend on the considered mapping B. Consider, therefore, the auxiliary game Γ({{i}, S}). We refer to the threshold equilibrium constructed in proposition 4.1, namely, the individual i participates if and only if his valuation is greater than the reserve price, offering his valuation augmented by the externality term, while the coalition S acts similarly with respect to the participation threshold t * given by (4.7). 11In a similar way to the analysis in the previous section, as a first step in computing y we compute the interim utility function of S. If the type of S is lower than its participation threshold, t S ≤ t * , it gets: e S if the individual participates (i.e., if t i > R), and 0 otherwise. Its interim utility in this case is therefore,

e S P ( ti > R) (5.2)
If, alternatively, t S > t * , i.e., S participates, we distinguish between 3 cases. If the individual does not participate, S wins the good for the reserve price R. If the individual participates (offering his valuation augmented by the externality term) and the coalition overbids him (offering its valuation augmented by its externality) the coalition gets the good paying the offer of the individual. Finally, if the individual overbids the coalition, then the latter gets its externality. Hence, if participating, the coalition gets the following interim utility:

(t S -R)P ( ti ≤ R) + E[(t S -( ti -e))I( ti > R and t S -e S > ti -e)]
+ e S P ( ti > R and t S -e S < ti -e) (5.3)

By taking expectations on (5.2) and ( 5.3), recalling (2.1), and by integrating in parts, we get the value (or, ex-ante utility) of a coalition of two:

y = 2e(1 -F (R)) + t t * -e (F (t) -F (t) 3 ) dt (5.4)
with a (unique) participation threshold t * (see, (4.7)) given by:

0 = eF (R) + t * -e R F (t) dt (5.5)
Finally, we need to compute the value of a seceding single player. We need to distinguish between two cases. With merging expectations the value of a seceding individual is his ex-ante utility with respect to the equilibrium σ({{i}, S}), denoted z. With singleton expectations his value is his ex-ante utility w.r.t σ({{1}, {2}, {3}}), denoted x.

In a similar way to the computation of the term y above we get:

z = F (t * -e) 2 (t * -2e -R) + e -F (t * -e) 2 t * -e R F (t) dt + t t * -e (F (t) 2 -F (t) 3 ) dt (5.6)
In order to compute x, recall that the participation threshold of any individual in this case is the reserve price R. If t 1 ≤ R, 1 gets e if any of the others participates and 0 otherwise, which yields his interim utility if not participating:

eP (max{ t2 , t3 } > R) (5.7)
If t 1 > R, the interim utility of 1 is:

(t 1 -R)P (max{ t2 , t3 } ≤ R)+E[(t 1 -(max{ t2 , t3 }-e))I(max{ t2 , t3 } > R and t 1 -e > max{ t2 , t3 }-e)]+eP (max{ t2 , t3 } > R and t 1 -e < max{ t2 , t3 }-e) (5.8)
The distribution of max{ t2 , t3 } being F 2 , we conclude by taking expectations on the interim utilities and integrating in parts that the ex-ante utility of an individual facing two other individuals is: 3 ) dt (5.9)

x = e(1 -F (R) 2 ) + t R (F (t) 2 -F (t)

Emptiness of the core

As stated above in order to examine the stability of the grand coalition we need to verify whether a coalition of two players or an individual can gain more by not cooperating. By symmetry, a coalition of two players secedes if

y 2 > v 3 .
However, if an individual secedes, there are two possible partitions for the remaining two agents. To demonstrate the instability of the grand coalition in the presence of externalities we focus on merging expectations (m-core), namely, a seceding individual expects the others to form the complementary cartel. Therefore, by symmetry, an individual profitably secedes if z > v 3 . 12 We conclude that the grand coalition is m-core-stable, (i.e., the m-core is non-empty), if and only if:

13 z ≤ v 3 and y 2 ≤ v 3 (5.10)
Consider first, as a benchmark, a market without externalities. We know that in such a market offering one's valuation, as long as it is higher than the reserve price, constitutes an equilibrium in weakly dominant strategies. Recalling that the valuation of a coalition is equal to the maximal type of its members, [START_REF] Biran | Core-stable rings in auctions with independent private values[END_REF] prove that the partition function reduces in this case to a characteristic function. In other words, in the absence of externalities the value of a coalition does not depend on the mapping B. In particular, the s-core and the m-core coincide, and x = z. Furthermore, they 12 Note that an individual with singleton expectations will not deviate as by grand coalition superadditivity x ≤ v 3 . 13 As for the core with singleton expectations (s-core), it is non-empty if and only if:

y 2 ≤ v 3 (5.11)
It follows that the s-core contains the m-core in a 3-player market.

prove that without externalities all rings are core-stable (see also [START_REF] Mailath | Collusion in second price auctions with heterogeneous bidders[END_REF] and [START_REF] Barbar | Collusion dans les enchères: quelques apports des jeux coopératifs[END_REF]). 14 Introducing direct externalities between agents interferes severely with cooperation. While as collusion reduces competition which leads to potential greater profits due to price reduction, agents find it more difficult to collude in the presence of externalities as in large coalitions the cumulating effect of negative externalities decreases dramatically the coalition's net profit.

In the following example an individual facing a cartel of two gains more than if he chooses to join the cartel in order to form the grand coalition. We therefore conclude that the grand coalition is not stable with merging expectations.

Example 5.1. Consider a 3-agent symmetric market where the valuation each agent assigns to the good is distributed uniformly in the unit interval, F ∼ U [0, 1]. A second price auction is held in this market with a reserve price R = 9 10 . The externality on a non-winning agent is e = -1 4 . Note that as 1 + 2e < R, if the grand coalition forms it profitably chooses not to participate in the auction. Hence, v = 0. By (5.6) it is readily verified that z > 0, hence an individual expecting the others to act cooperatively in case he secedes from the grand coalition, will profitably act independently. The grand coalition is therefore instable with merging expectation.

Note, that considering "merging expectations" in the example is easily justified. Once a player secedes from the grand coalition the remaining two players can either cooperate and get y 2 each, or further split up gaining x each. From (5.4) and (5.9) we learn that y 2 > x in the example, hence, the remaining two players will profitably cooperate.

The individual's behavior in the example can also be interpreted as "freeriding". If he forms a coalition with the two other agents he gets a null payoff. By letting the two others form a coalition he gains a higher payoff, z > 0.

Let us note that stability is violated in the presence of externalities also when externalities are close to zero. One should not expect some sort of continuity, in the sense that for a small enough externality term all coalitions remain stable. This discontinuity may be explained, for instance, by the fact that for any negative externality the utility of a coalition depends on the 14 The stability of a coalition of two players may also be recovered from [START_REF] Waehrer | Asymmetric auctions with application to joint bidding and mergers[END_REF]. He proves that in the absence of externalities the per capita share in a second price auction increases with the size of the coalition. Specifically, y 2 ≥ z = x.

partition of the others. In particular, we can consider an externality term as small as we wish, for a large enough reserve price, the instability with merging expectations demonstrated in the example maintains. As a concluding remark for this section we recall a property proved by [START_REF] Waehrer | Asymmetric auctions with application to joint bidding and mergers[END_REF]: the per capita share in a second price auction increases with the size of the coalition. As the example shows, the property does not extend to markets with direct externalities. Specifically, we obtain in the example y 2 < z.

Collusive mechanisms

The question of collusion in auctions is frequently addressed in the literature as a mechanism design problem. Loosely speaking, a collusive mechanism for the grand coalition determines the bidding profile of the players, as well as transfer payments between them in order to share the coalition's gain. When studying collusion in auctions with the means of mechanism design, we try to establish which properties the collusive mechanism may possess.

Consider a second price auction with independent private value (IPV) without direct externalities between bidders. Mailath and Zemsky (1991) construct a collusive mechanism for the grand coalition (with heterogeneous bidders) which is ex-post efficient, incentive compatible (IC), interim individually rational (IR) and budget-balanced (BB). 15 As is well known, IPV second price auctions have an equilibrium in weakly dominant strategies, where every bidder bids his type, or valuation. Full revelation within bidding rings yields an analogous result in collusive auctions, namely, a ring submits in equilibrium a bid equals to the highest valuation of its members (see, e.g., [START_REF] Biran | Core-stable rings in auctions with independent private values[END_REF]). In particular a ring conveys no strategic externality upon players outside the ring, since the ring's highest type member would make the same bid if the ring did not collude. This allows [START_REF] Mailath | Collusion in second price auctions with heterogeneous bidders[END_REF] to prove the "coalitional stability" of the grand coalition, namely, the existence of a mechanism for the grand coalition which is ex-post efficient, IC, BB and satisfies ex-ante group participation constraints. 16Caillaud and Jehiel (1998) study collusion in auctions with direct externalities where individual bidders decide whether to participate in the grand coalition at the interim stage. They mainly assume that bidders have veto power, namely, the refusal of a bidder to participate in the grand coalition leads to an auction where all bidders act individually. 17 They prove that the following condition is necessary and sufficient for the existence of a mechanism for the grand coalition which is ex-post efficient, BB, IC and interim IR:

e + t R+e F (t) n-1 dt ≤ 1 n v + t t t max{τ,R-(n-1)e} F (t) n-1 dt f (τ ) dτ (6.1)
whenever R ≤ t + (n -1)e. In the complementary case, namely, when the grand coalition has absolutely no interest in participating in the auction, whatever its valuation is, the necessary and sufficient condition for the existence of a mechanism for the grand coalition which is ex-post efficient, BB, IC and interim IR is:

e + t R+e F (t) n-1 dt ≤ 0 (6.2)
It can be verified that in the case without direct externalities (e = 0) the necessary and sufficient condition identified by Caillaud and Jehiel (1998) holds, which in turn revalidates the result of [START_REF] Mailath | Collusion in second price auctions with heterogeneous bidders[END_REF] regarding the existence of an ex-post efficient mechanism for the grand coalition which is IC, BB and interim IR. Specifically, as e = 0 it holds that R ≤ t + (n -1)e and we should therefore look at condition (6.1). Changing the order of integration in the RHS of (6.1) replacing v = E((max i ti + (n -1)e -R)I(max i ti + (n -1)e > R)) (see, (2.2)) and setting e = 0 yields, Bondareva-Shapley theorem (see, e.g., [START_REF] Shapley | On balanced sets and cores[END_REF]). In particular, no constructive proof is available, as opposed to the case with interim individual participation constraints, as mentioned above. 17 Caillaud and Jehiel (1998) state that one can assume veto power to bidders without loss of generality. Since they define the individual rationality level of i as his minmax payoff, it indeed does not depend on the partitioning of N \ {i}. Nevertheless, in our model individual rationality levels are calculated in equilibrium and do depend on the partitioning of the others, as demonstrated by example 5.1.

t R F (t) n-1 dt ≤ t R (t -R)F (t) n-1 f (t) dt + t R F (t) n dt (6.3)
Integrating in parts the first integral in the RHS of (6.3) yields the following equivalent inequality:

t R F (t) n-1 dt ≤ t R 1 n (1 + (n -1)F (t) n ) dt (6.4)
which can be verified by looking at the difference between the integrand in the RHS of (6.4) and the integrand in the LHS of (6.4) as a function of the type in the interval [t, t]. This function is non-increasing and is equal to 0 in t.

With respect to Caillaud and Jehiel (1998)'s condition, consider example 5.1. In terms of mechanism design, the coalitional equilibrium considered in the example yields a mechanism for the grand coalition which is ex-post efficient, BB and IC. 18 The fact that a single player (with merging expectations) prefers seceding at the ex-ante stage in this example means that the mechanism fails to be ex-ante IR.

As ex-ante IR is a weaker property than interim IR, such a mechanism would also fail to be interim IR given that an individual has merging expectations, in particular, without veto power. Nevertheless, it can be readily verified that condition (6.2) does hold in this example, which means that the grand coalition has an ex-post efficient, BB, IC and interim IR mechanism if individuals have veto power. We conclude that the veto power assumption is strong.

To complete the discussion we propose another example, where the grand coalition is core-stable while as the necessary and sufficient condition of Caillaud and Jehiel (1998) does not hold. The interpretation is that there exists an ex-post efficient mechanism for the grand coalition which is BB, IC and satisfies ex-ante group participation constraints (for groups with either merging or singleton expectations, i.e., veto power or not), yet a mechanism for the grand coalition which is ex-post efficient, BB and IC, fails to be interim IR.

Example 6.1. Consider a 3-player symmetric market where the valuation that each player assigns to the good is distributed uniformly in the unit interval, F ∼ U [0, 1]. A second price auction is held in this market with a reserve price R = 3 5 . The externality on a non-winning agent is e = -1 4 . Note that as 1 + 2e < R if the grand coalition forms it profitably chooses not to participate in the auction. 19 It is readily verified that the LHS of (6.2) is positive, therefore, condition (6.2) does not hold.

Once again, as 1 + 2e < R, the grand coalition is not expected to participate in the auction, namely v = 0. It can be readily verified that y, z < 0 (see, (5.4) and (5.6)), hence, the m-core of this game is non-empty (see, (5.10)), which in turn yields that the s-core is not empty as well (see, footnote 13). Hence the grand coalition is ex-ante core stable with both merging or singleton expectations.

The latter example demonstrates the existence of an ex-post efficient, IC and BB mechanism which satisfies ex-ante group participation constraints while interim IR fails to be maintained. We find this result important for two reasons. First, the context of the mechanism design problem might be so that agents have to commit ex-ante, the interim stage being too late for collusion. Consider, for instance, the example of an art auction previously mentioned (see, e.g., section 1.1) where waiting for the art object to be available at the auction house for close examination by experts on behalf of the art collectors (i.e., interim stage) might be too adjacent to the auction, leaving no time for coalition formation negotiations. Another example, Porter and Zona (1999) study collusion in school milk procurements in Ohio where local diaries formed a bidding ring which repeatedly participated in the yearly school milk procurement. Forming a ring with the intention to participate in future auctions explicitly assumes the ability and willing of players to commit exante. That is since the auction details are not yet published while collusion takes place, and therefore the players cannot calculate their cost if winning, and in particular they cannot calculate their valuations or types.

A second reason relates to the point of view of the colluding ring. As proved by Biran and Forges (2011) a coalition can strive to achieve a "first best" solution at the ex-ante stage, namely, a collusive mechanism which is ex-post efficient, and satisfies group participation constraints, which can be made IC by implementing an appropriate balanced transfer scheme, as introduced, for instance, by [START_REF] Groves | Incentives in teams[END_REF]. It is well known that a transfer scheme of that kind usually fails from being IR at the interim stage, leaving the coalition with a "second best" solution.

Moreover, as already explained by [START_REF] Biran | Core-stable rings in auctions with independent private values[END_REF], defining group participation constraints in the interim stage is difficult. The decision of a coalition to secede in the interim stage is a function of its "type". But what is the "type" of a coalition? How, and to what extent, do coalition members share their information, if at all? 20 Moreover, formulating interim blocking as a function of the conditional expected utility of a coalition given its "type" raises another difficulty. As opposed to the ex-ante blocking case, one can no longer use straight forward transfer payments between the members of the grand coalition in order to avoid all coalitions from blocking. Nevertheless, in example 6.1 an individual is blocking in the interim stage. Therefore, even if we could define group participation constraints in the interim stage, the grand coalition would be interim blocked, although, as demonstrated above, it would not be blocked in the ex-ante stage by both individuals and groups. We conclude that in this example the grand coalition would prefer colluding in the ex-ante stage.

Conclusion

We considered a second price auction in the presence of externalities, studying the question of the core stability of the grand coalition. We derived an auxiliary auction game between coalitions, or bidding rings, from the original non-collusive auction game, defining the valuation of a coalition as the highest valuation of its members net of the externalities of the coalition's members. We then proved the existence of a Nash equilibrium in the auxiliary game for any given partition of the bidders, computing it specifically in two concrete cases. The merging expectations case, where a seceding coalition conjectures that the others will form a complementary coalition. And the singleton expectations case, where a seceding coalition conjectures that the others will act individually.

Given these results, we showed that as opposed to the case without externalities where the grand coalition is always stable, the presence of external-ities makes cooperation harder. In particular, we demonstrated an auction with three bidders, where a singleton with merging expectations prefers acting individually than joining the grand coalition, as early as in the ex-ante stage. It follows that the grand coalition is not necessarily stable in the presence of externalities.

Finally, we studied collusion in auctions using mechanism design tools. We showed that ex-ante and interim commitments are not logically dependent, insisting on the difficulty to define interim group participation constraints, and demonstrating an auction where the grand coalition would prefer to collude as early as in the ex-ante stage.

A Appendix: Participation threshold of a coalition facing individuals

seP (max i / ∈S ti > R) (A.1)
where ti denotes a random variable with distribution F . If on the other hand S chooses to participate, we distinguish between three cases. Either all i / ∈ S do not participate, in which case S wins the good for the reserve price. Either there is some i / ∈ S who participates and wins, in which case S gets its externality. Or finally there is some i / ∈ S who participates, however S wins paying the second highest bid max B Appendix: Simulations of core stability of the grand coalition with singleton expectations

We consider in this appendix singleton expectations, namely, a deviating coalition expects the others to act individually. We present several simulations of markets with three agents, showing that the grand coalition is core stable with singleton expectations, i.e., the s-core is non-empty. We note, however, that given example 5.1 where the grand coalition was proved to be unstable with merging expectation, the question of the stability of the grand coalition in a given market depends strongly on the conjecture of a seceding coalition on the partitioning of the remaining bidders.

We first recall, with respect to the notations in section 5, that the s-core is non-empty if and only if y 2 ≤ v 3 . Namely, the per capita utility in a coalition of two if seceding is lower than the per capita utility in the grand coalition (see, (5.11)).

We consider symmetric markets where the valuation that each player assigns to the good is distributed uniformly in the unit interval, F ∼ U [0, 1]. According to the parameters of the market, (i.e., the reservation price, R, and the externality term, e), we distinguish between two market types . The first market type maintains R < 1 + 2e, namely, a maximal type grand coalition participates in the auction as it can gain a positive utility by bidding the reserve price.

The second type maintains R > 1 + 2e, which means that for any type realization, the grand coalition, if it forms, does not participate in the auction. Nevertheless, we also demand R < 1 + e to avoid a degenerated case, where a coalition of two players does not participate as well. 21We executed the following MATLAB simulation using the Symbolic Math Toolbox in order to calculate: v, y, z, x. (Correspondingly, the payoff of: The grand coalition; Coalition of two; Singleton facing a coalition of two; Singleton facing two individuals.) 22syms t; v = @(e,R) int((t+2*e-R)*3*t^2,R-2*e,1); % tstar is the participation threshold of a coalition of two tstar = @(e,R) e+sqrt(R^2-2*e*R); y = @(e,R) 2*e*(1-R)+int(t-t^3,tstar(e,R)-e,1); z = @(e,R) (tstar(e,R)-e)^2*(tstar(e,R)-2*e-R)+e-(tstar(e,R)-e)^2*int(t,R,tstar(e,R)-e)+ int(t^2-t^3,tstar(e,R)-e,1); x = @(e,R) e*(1-R^2)+int(t^2-t^3,R,1);

The following table presents the simulation results in markets of the first type (i.e., the grand coalition may participate): R e v y z x 0.01 -0.005 0.73 0.24 0.078 0.078 0.99 -0.001 9.5 • 10 -5 6 • 10 -5 3.1 • 10 -5 2.9 • 10 -5 0.33 -0.32 0.001 -0.31 -0.13 -0.21 0.5 -0.2 0.014 -0.124 -0.045 -0.093

It can be readily verified that all simulations maintain y 2 ≤ v 3 , namely, the grand coalition is core stable with singleton expectations.

Simulation results of markets of the second type, i.e., the grand coalition does not participate, are presented in the following table: R e v y z x 0.34 -0.33 0 -0.33 -0.13 -0.22 0.99 -0.007 0 -1.3 • 10 -4 7.4 • 10 -6 -9 • 10 -5 0.5 -0.49 0 -0.47 -0.03 -0.31 0.9 -0.25 0 -0.03 0.07 -0.04

Here also, all simulations maintain y 2 ≤ v 3 . Note, that the last simulation corresponds to the market from example 5.1, where the grand coalition was not core stable with merging expectations.

  t S ; (b S , b -S )) for any b S < R, then u S (t S ; (t S -e S , b -S )) ≥ u S (t S ; (b S , b -S )) for any b S < R

Proposition 4 . 1 .

 41 Let P = {S, N \ S} where |S| > |N \ S|. Then there exists t * S ∈ [R -e N \S + e S , R], such that t * S and t * N \S = R constitute an equilibrium of Γ(P ) in threshold strategies.

  R)P ( tN\S ≤ R) + seP ( tN\S > R and tN\S -(n -s)e > t S -se) + E((t S -( tN\S -(n -s)e))I( tN\S > R and tN\S -(n -s)e < t S -se)) (4.2)

  -e N \S + e S , R]. There exists a best response strategy for N \ S with thresholds t * N \S ∈ [R + e N \S , R].Following the same analysis we conclude that in equilibrium:

	Suppose by way of contradiction that t * S < R -e N \S + e S . Then R = max{R, t * S + (n -2s)e} and I( tN\S > R and tN\S -(n -s)e < t * S -se) = 0, ∀ tN\S . Hence, (4.3) reduces to:
	0 = (t * S -R)P ( tN\S ≤ R)	(4.4)
	or equivalently, as f > 0, t * S = R, which is a contradiction.
	Suppose now that S is following a bidding strategy with a participation
	threshold t * S ∈ [R
	and tN\S -(n -s)e < t * S -se))
		(4.3)

max{R, t * S + (n -2s)e}) + E((t * S -( tN\S -(n -s)e))I( tN\S > R (n -s)eP ( tS > t * S ) = (t * N \S -R)P ( tS ≤ t * S ) + (n -s)eP ( tS > max{t * S , t * N \S -(n -2s)e}) + E((t

* N \S -( tS -se))I( tS > t * S and tS -se < t * N \S -(n -s)e)) (4.5) where, tS is a random variable with distribution F S . As t * N \S ≤ R ≤ t * S + e N \S -e S it holds that t * S = max{t * S , t * N \S -(n-2s)e} and I( tS > t * S and tSse < t * N \S -(n -s)e) = 0, ∀ tS . It follows that t * N \S = R, which concludes the proof.

  Proof of proposition 4.2. Suppose first that all i / ∈ S follow a bidding strategy with a participation threshold equals to R. Then S has a best response strategy with a threshold t * S ∈ [R + e S , R]. Let us compute the interim utility of S of type t * S if it chooses to participate in the auction and if it chooses not to participate. If S makes an irrelevant bid, then it gets 0 if all i / ∈ S do not participate as well, and e S otherwise, which yields:

  In equilibrium S of type t * S is indifferent between participating or not. Suppose by way of contradiction that t * S < R + (s -1)e. Then R = max{R, t * S -(s -1)e} and I(max S = R, which is a contradiction. Suppose now WLOG that 1 / ∈ S and that S is following a bidding strategy with a participation threshold t * S ∈ [R + (s -1)e, R], while all the individuals but 1 follow a strategy with a threshold R. There exists a best response strategy for 1 with threshold t * 1 ∈ [R + e, R]. Following the same analysis we conclude that in equilibrium:

				i / ∈S	ti > R and max i / ∈S	ti -e < t * S -se) =
	0, ∀( ti ) i / ∈S . Hence,
	seP (max i / ∈S	ti > R) = (t * S -R)P (max i / ∈S	i / ∈S ti ≤ R) + seP (max	ti > R)	(A.3)
	or equivalently, t eP ( max i / ∈S∪{1} ti > R or tS > t * S ) = (t * 1 -R)P ( max i / ∈S∪{1}	ti ≤ R and tS ≤ t * S )
						+ eP ( max i / ∈S∪{1}	ti > max{R, t * 1 }
						or tS > max{t * S , t * 1 + (s -1)e})
						+ E((t * 1 -max{ max i / ∈S∪{1}
						ti -e. The
						i / ∈S
	interim utility of S is therefore:
	(t * S -R)P (max i / ∈S	ti ≤ R) + seP (max i / ∈S	ti > R and max i / ∈S	ti -e > t * S -se)
	+ E((t * S -(max i / ∈S	ti -e))I(max i / ∈S	ti > R and max i / ∈S	ti -e < t * S -se)) (A.2)

*

ti -e, tS -se})

I( max i / ∈S∪{1} ti ∈ (R, t * 1 ] or tS ∈ (t * S , t * 1 + (s -1)e]) (A.4)

It follows that t * 1 = R.

As opposed to art dealers, art collectors do not buy in order to resell.

For the sake of simplicity we demonstrate the secession of a single player rather than of a group of players. In order to demonstrate the secession of a group of players one needs to consider a larger market which significantly complicates the computations.

This is the smallest auction in which the instability of the grand coalition can be demonstrated. Examples exist for the general n-bidder case, n > 3. However, the grand coalition is always stable in a 2-bidder auction due to symmetry and the super-additivity of the grand coalition (see, section 5).

Our results may be recovered without this assumption.

See Biran and Forges (2011)'s corollary of proposition 1.

For instance, singleton expectations yield a symmetric mapping, as every seceding coalition conjectures that the others will partition themselves in the same way, to singletons. Merging expectations is another example for a symmetric mapping.

This is for the sake of simplicity as demonstrating the secession of a group of players requires more bidders which significantly complicates the computations. See also, footnote 2.

In case of an equality the collusive auction is symmetric and the equilibrium reduces to the one identified by Caillaud and Jehiel (1998). Namely, both coalitions have a participation threshold equals to the reservation price R (see, section 3).

For the sake of simplicity we assume here t + (n -2)e > R, otherwise S might have a participation threshold which never allows it to participate in the auction. The analysis can be repeated in the complementary case.

Due to symmetry and grand coalition superadditivity (see, e.g.,[START_REF] Biran | Core-stable rings in auctions with independent private values[END_REF]) the grand coalition is always stable in a 2-player market with externalities. The instability of the grand coalition in the presence of externalities can be demonstrated also in the general n-player case, n ≥ 3.

As in the computation of (4.7) we assume here t + e > R. See also footnote 9.

Allowing agreements which involve the seller as well,[START_REF] Myerson | Efficient mechanisms for bilateral trading[END_REF] prove an impossibility theorem regarding the existence of an ex-post efficient, BB, IC, interim IR mechanism. This indicates that in this result, the seller takes an important part with respect to the (in)stability of collusive agreements.

[START_REF] Mailath | Collusion in second price auctions with heterogeneous bidders[END_REF] prove the existence of such a mechanism using the famous

While we follow an ex-ante approach, we achieve ex-ante incentive efficiency in the grand coalition by constructing an ex-post efficient mechanism which is also incentive compatible (see also, e.g.,[START_REF] Holmstrom | Efficient and durable decision rules with incomplete information[END_REF],[START_REF] Mas-Colell | Microeconomic theory[END_REF]).

and e = -1 5 for which the grand coalition does participate in the auction.

[START_REF] Biran | Core-stable rings in auctions with independent private values[END_REF] propose looking at the incentive compatible coarse-core (see, e.g.,[START_REF] Vohra | Incomplete information, incentive compatibility and the core[END_REF]), where coalitions block on the basis of common knowledge events, i.e., communication between coalition members is reduced to a minimal level.

Simulations ran in the complementary case, 1 + 2e > R > 1 + e, also find the grand coalition core stable with singleton expectations.

In the second market type, as the grand coalition does not participate, we simply set: v = 0;


Ouannas Moussa
email: mouannas@hotmail.com

Distribution of Prime Numbers

In this paper I present the distribution of prime numbers which was treated in many researches by studying the function of Riemann; because it has a remarkable property; its non trivial zeros are prime numbers; but in this work I will show that we can find the distribution of prime numbers on remaining in natural numbers only.

1.Introduction :

The bone Ishango discovered there are nearly 20000 years and yet, it seems that we are only at starting point of understanding the prime numbers; we ignore how they are distributed, how they behave among themselves or in set of natural numbers. However, you will see in this studying that there is a mean to clarify the distribution on using natural numbers only. I think all the formulas and technics to run anything in this world already exist but only hidden, simply wait for the « moment » to remove the membrane that blind us according to some special characteristics. The resolution of the Riemann zeta function (ξ(s) = 0) means knowing all non trivial zeros of the function; we previously thought that they are prime numbers but according to the study done by Harry k.Kahn: arXiv: 0801.4049 v1; these zeros are also numbers that are the product of two primes, he has spoken that there are two lines: the first contains the multiples of seven (7) and the other multiples of eleven (11), whereas in my study I do not found only multiples of (7 and 11) but those of 13, 17,19,23,29,31,37, ... ................... Moreover, under Article arXiv: 0810.0095 of Shi Huang; as it seems "some mathematicians Have Suspected Link Between a premium numbers and secrets of creation". A remark which led me to admire our surroundings and daily life and to whom we rarely pay attention. In the world of bees, the natural sciences have taught us that when a bee wants to Inform its congeners that it has found a field of flowers, it begins to dance in eight (8), on the other hand there is no evidence that the human body needs eight (8) hours for rest: this is not a coded message ... ... ... .. the distribution of prime numbers is tangible proof. This distribution already exists but only hidden, so whatever our understanding of phenomena and things; it is seemed that we are at starting point.

2.Spliting up of the natural integers :

I established a table where the first line start from 1 until 19 and the second from 20 to 38 …. in Fig I .  After coloring the prime numbers in blue and the non-prime in red; it appears that they are adjusted (from left to right and from top to bottom) according to two (02) oblique lines of the following formulas:

 19(5+6a) + 18 k / n = 5+6a et n = 1+6a avec n et a € N 19(1+6a) + 18k k € N 0≤ k ≤18
It appears also that they are adjusted (from left to right and from bottom to top) according to four (04) oblique lines of the following formula: 19n -20k / n and k € N 0≤ k ≤18 with n ≠5b / b € N I noticed that the two (02) lines and the four (04) intersect in 08 points so we obtain groups of 08 numbers. But the 08 numbers are not all prime numbers; those which are non-prime are a product of two prime numbers from 7 to infinity or the power of some prime numbers, « 8 is the rank of 19 in set of prime numbers » ; is it here a coincidence ? It appears clearly that the prime numbers are distributed in groups of 08 numbers which can be obtained with the following formula: 2x3x5 n +2k+3 / n an k € N and k= {2, 4, 5, 7,8, 10, 13,14} Thus , the numbers 2k+3 which are 7,11,13,17,19,23,29,31 constitute the basis not only for the obtention of the prime numbers but to determine their rank(rate) and also for eliminating the non-prime numbers. Additive:

The periods of the power of : 2x3x5n+2k+3=X+2k+3=Y

Test of primality:

However, these numbers non prime are the basis of the algorithm for primality testing on writing n in the form n=α+ (30n+2k+3) β according to the

Conclusion:

As a conclusion to this studying, I think that I clarified the distribution of prime numbers and found a mean to calculate them by splitting up the natural integers on using 19 and we can obtain this result only with 19 and 11. On the other hand, it is not necessary to look for the density of prime numbers since we can talk about ranks. In fact I have not found this distribution by coincidence, but just remove the membrane which blinds us, on extracting from the Quran. In addition to that, I want to tell that I have found other mysterious secrets of prime numbers which I cannot disclose now. All what I can say therefore that the primes are the cause of many phenomena that I shall reveal in my upcoming articles.

FIG

  FIG 1 :

I

  Fig 2:

  1 :

	The eight (8) numbers (prime and non prime) which belong to the Distribution can be written
	932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 in this form:
	913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931
	894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 X=30n+2k+3 with 2k+3= {7, 11, 13, 17, 19, 23, 29, 31}
	856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874
	837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855
	818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836
	799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817
	780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798
	761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779
	742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760
	723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741
	704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722
	685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703
	666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684
	647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665
	628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646
	609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 19n-20b
	590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608
	571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 19n-20b
	552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570
	533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 19n-20b
	514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532
	495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 19n-20b
	476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494
	457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475
	438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456
	419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437
	400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418
	381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399
	362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380
	343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361
	324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342
	305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323
	286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304
	267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285
	248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266
	229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247
	210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228
	191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209
	172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190
	153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171
	134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152
	115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 19(1+6a) +18k
	96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114
	77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 19(5+6a) +18k
	58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
	39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
	20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
	1	2	3	4	5	6	7	8	9 10 11 12 13 14 15 16 17 18 19
			prime number			non prime number	2x3x5 n

  Table of: -Primality testing -Periods of non-prime numbers (np) in Pk

	n	Pk n	Pk n	Pk n	Pk n	Pk n	Pk n	Pk n	Pk
	1	8	2	7	2	11	3	10	4	6	5	5	6	9	7	4
	2	7	3	11	4	9	6	4	6	10	8	6	10	8	11	5
	2	11	4	9	5	8	7	5	8	4	9	10	12	7	13	6
	3	10	6	4	7	5	9	8	10	9	12	11	16	6	17	7
	4	6	6	10	8	4	10	9	11	11	14	7	18	5	19	8
	5	5	8	6	9	10	12	11	14	7	16	8	22	4	23	9
	6	9	10	8	12	7	16	6	18	5	22	4	27	11	29	10
	7	4	11	5	13	6	17	7	19	8	23	9	29	10	31	11

  X+7 Pk X+11 Pk X+13 Pk X+17 Pk X+19 Pk X+23 Pk X+29 Pk X+31 Pk

	Y 2 Y 3	8 6	Y 2 Y 3	11 5	Y 2 Y 3	8 4	Y 2 Y 3	8 9	Y 2 Y 3	11 8	Y 2 Y 3	8 7	Y 2 Y 3	10 11	Y n	11
	Y 4	11			Y 4	11	Y 4	11			Y 4	11
	Y 5	4			Y 5	6	Y 5	7			Y 5	9
	To better understand the table; it suffice to say that all numbers that are not primes but the
	product of two primes belonging to the distribution : 30n +7; 30n +11, 30n +13, 30n +17,
	30n+ 19, 30n+ 23, 30n+ 29 and 30n+ 31 have a period depending on the positioning table.

table of FIG 3.

  If it is so, X is a prime number. b/ if X is verified with 7 we do not need to verify with 17, if not we make the same process with 17.In this formula the only obstacle is the number of non-prime (np) which I will disclose in my next articles.

	FIG 4:	P 4
	P 7	P 8
		P 11
	P 10
		P 6
	P 5
	P 9
	We choose X a natural number, if its last digit number is 7, 9, 1 or 3 it may be prime, so to
	know if it belongs to the group of 8 , we must do a subtraction.
	If its digit number is 7 we retrench 7 or 17:
	a/ if X-7 is not divisible by 2x3x5 i.e. 30, X is not prime and if it is divisible we obtain n;
	since X belongs to the group of 8; so we verify if it is not non-prime in the table on writing n
	in the forms:
	n=α+ (30n+2k+3) β according to the table of FIG 3

Thus:

If the last digit number of X is 9 we retrench 29 or 19 If the last digit number of X is 1 we retrench 31 or 11 If the last digit number of X is 3 we retrench 23 or 13 and we proceed as previously.

Examples: X=917 * X-7= 910/30 =30,333 not divisible by 30, it does not belong to the distribution. * X-17 = 900/30 = 30 =n divisible by 30, so X belongs to the distribution and its position is P7, now we give the forms of n=30: n=2+7k →np in P7 and in P11 n=11+19k→ np in P11 n= 4+13k→ np in P9 Since X is in the position P7 so it is not prime.

NB:

We can also form prime numbers as great as possible Examples:

We choose n = 1600, so the eight (8) numbers are: In

Determination of the rank:

Rn = 8 n + Pk -np * Rn is the rank * Pk is the position of the prime number with {4,5, 6, 7, 8, 9, 10, and 11} * np the number of the non-prime numbers belong to the distribution before this prime number.