Ayman Chouayakh
email: ayman.chouayakh@orange.com

Aurélien Bechler
email: aurelien.bechler@orange.com

Isabel Amigo
email: isabel.amigo@imt-atlantique.fr!

Loutfi Nuaymi
email: loutfi.nuaymi@imt-atlantique.fr!

Patrick Maillé
email: patrick.maille@imt-atlantique.fr!

Aur Élien Bechler

Patrick Maill

Multi-Block Ascending Auctions for Effective 5G Licensed Shared Access

Keywords: Shared Access, Spectrum Sharing, Auctions

INTRODUCTION

For fifth generation (5G) wireless networks, dealing with mobile data traffic is challenging, traffic volumes being expected to explode. At the same time, some licensed frequency bands held by governmental agencies are underutilized, leading to the emergence of the Licensed Shared Access (LSA) idea [START_REF] Khun-Jush | Licensed shared access as complementary approach to meet spectrum demands: Benefits for next generation cellular systems[END_REF], [START_REF] Matinmikko | Spectrum sharing using licensed shared access: the concept and its workflow for LTEadvanced networks[END_REF].

LSA is a new concept, proposed by the Radio Spectrum Policy group (RSPG) in November 2011, which aims to optimize the use of spectrum, allowing the incumbents or the owners of the 2.3-2.4 GHz frequency band to temporarily share their spectrum with Mobile Network Operators (MNOs). Contrary to the traditional concept of sharing in which secondary users (MNOs in the LSA context) have no guarantee for accessing the incumbent's spectrum, under LSA the duration and conditions of sharing are precisely defined beforehand by the regulator via a license. Deploying an LSA system requires the introduction of two new architectural blocks called the LSA repository-basically a database containing information about the LSA band such as conditions of sharing and duration-and the LSA controller which controls the access to the LSA bandwidth [START_REF] Matinmikko | Spectrum sharing using licensed shared access: the concept and its workflow for LTEadvanced networks[END_REF].

Several trials have been carried out to show the applicability of the LSA concept 1 .

Since the objective of LSA is to optimize spectrum usage, spatial reusability (MNOs who do not interfere should be able to use the same spectrum bands simultaneously) should also be leveraged. Spectrum reusability has been addressed in spectrum markets in the last decade [START_REF] Chen | Tames: A truthful auction mechanism for heterogeneous spectrum allocation[END_REF]- [START_REF] Chouayakh | PAM: A Fair and Truthful Mechanism for 5G Dynamic Spectrum Allocation[END_REF]; we will in particular consider a scenario in which multiple Base Stations (BSs) of different operators compete for LSA spectrum at a defined period of time in a particular geographical area (in this paper we use the terms bidder, player and base station interchangeably).

In this scenario, a mechanism for attributing licenses needs to be adopted. A common approach is to design an auction mechanism, due to the need for information revealed by potential bidders to find an allocation maximizing the extracted value. Designing an auction mechanism here raises two major challenges: it should take spectrum reusability into account, and should be truthful (strategy-proof) i.e., each player should be incentivized to sincerely reveal their willingness-to-pay for the good (LSA spectrum in our context) independently of the other bidders' behavior. Indeed, in general, players are expected to try to manipulate the mechanism in order to maximize their profit, which may hurt other players' (including the auctioneer's) interests.

The LSA concept involves two major differences with regard to the allocation of 3G or 4G spectrum to operators. First, the allocation needs to work at a faster time scale, since the availability of LSA spectrum will be changed by the incumbent, possibly several times per hour, and the regulator has to allocate the LSA spectrum via an auction mechanism for potential LSA licensees as soon as the incumbent releases its spectrum in order to improve the use of the spectrum. Second, spatial reusability (MNOs who do not interfere can use the same spectrum bands simultaneously), should be leveraged. Indeed, due to possibly overlapping coverage areas, there are limited possibilities for allocating the same spectrum to several MNOs. We manage interference among coverage areas through groups. A group is a set of base stations of different MNOs such that two base stations in the same group do not interfere, hence the spectrum allocated to a group can be used by all the members of the group.

Related work

Several mechanisms have been proposed for the LSA context. In [START_REF] Chen | Tames: A truthful auction mechanism for heterogeneous spectrum allocation[END_REF], [START_REF] Zhou | Trust: A general framework for truthful double spectrum access[END_REF], [START_REF] Wang | Spectrum Sharing Based on Truthful Auction in Licensed Shared Access Systems[END_REF], auction mechanisms are proposed for the case where there is only one spectrum block to allocate. LSAA [START_REF] Wang | Spectrum Sharing Based on Truthful Auction in Licensed Shared Access Systems[END_REF] is the first auction mechanism which was proposed as a candidate for the LSA context, it performs well in terms of social welfare assuming truthtelling by bidders, but sincere bidding is not an optimal strategy for bidders. In [START_REF] Chouayakh | Licensed shared access for 5g: Which auction mechanism to choose?[END_REF], we modified the payment rule of LSAA to make it truthful. For those works there are two limitations:

• First, they are all-or-nothing schemes, i.e., all the available quantity of LSA spectrum is considered as an indivisible block and allocated to one and only one group. A question which may arise is: can we improve the performance of those auctions by splitting spectrum into blocks and adapting those mechanisms? Splitting spectrum may increase the outcome of the auction with respect to any metric, as an example it can increase fairness of the allocation since spectrum will not be necessarily allocated to one and only one group. On the other hand, it may complicate the auction design and analysis since the set of possible allocations increases.

• Second, they are one-shot auctions. A one-shot auction mechanism is composed of a single round so bidders have only one chance to submit bids to the auctioneer. In general, bidders prefer "ascending auctions" where information is revealed by bidders during some convergence phase. Compared with one-shot auctions, ascending auctions have several advantages: they preserve the privacy of the winning bidder(s) which do(es) not reveal its valuation(s). Also, they are more transparent because each bidder sees the evolution of the auction.

Contributions of the paper

Our contributions can be summarized as follows.

First, we study the impact of splitting spectrum into K identical blocks, and show how to adapt the payment rule for each existing one-block auction mechanism in order to maintain its incentive properties (truthful bidding). We show by simulations that this modification (splitting spectrum and converting those mechanisms to the multi-block scenario) increases the performance metrics of the auction.

We then show, using the "clinching" approach initially proposed by Ausubel [START_REF] Ausubel | An efficient ascending-bid auction for multiple objects[END_REF], how to convert oneshot multi-block auction mechanisms into equivalent ascending multi-block auction mechanisms, where the equivalence means that the one-shot and the ascending version generate the same allocations and payments. We propose two methods for that conversion. The first method is by introducing a representative party per group to act on behalf of the members of each group. Since bidders do not see the evolution of the auction which may be undesirable, in the second method, we show how to implement an ascending version while removing representatives, so that the auction is run directly between bidders and the auctioneer, leading to more transparency. We show that when bid values are discretized, the convergence rate -the number of rounds-of the algorithm is upper-bounded by the K + 1-highest groupbid (expressed in discretized units).

This paper extends and improves the state-of-the-art auctions for the LSA context as well as our previous work [START_REF] Chouayakh | Auction mechanisms for licensed shared access: reserve prices and revenue-fairness trade offs[END_REF]. In [START_REF] Chouayakh | Auction mechanisms for licensed shared access: reserve prices and revenue-fairness trade offs[END_REF], following the assumptions made in the literature (only one block allocated for one group via a one-shot auction), we have shown how to ameliorate the revenue of the auctions proposed in the literature for the LSA context by introducing a reserve price per bidder. However, for multi-block scenarios, we cannot run the auction proposed in [START_REF] Chouayakh | Auction mechanisms for licensed shared access: reserve prices and revenue-fairness trade offs[END_REF] directly for multiple rounds because we will lose truthfulness. The first part of this paper can be interpreted as a modification or extension of [START_REF] Chouayakh | Auction mechanisms for licensed shared access: reserve prices and revenue-fairness trade offs[END_REF] because by using the approach proposed in this paper, we can run the auction mechanisms proposed in [START_REF] Chouayakh | Auction mechanisms for licensed shared access: reserve prices and revenue-fairness trade offs[END_REF] (such as TLSAA and TLSAA2) for the multi-blocks scenario.

AUCTION MECHANISMS AND DESIRABLE

PROPERTIES

In this section we provide the definition of an auction mechanism and the most desirable properties.

Auctions

An auction mechanism is an allocation mechanism used in order to assign some item(s) (LSA spectrum in our context) for bidders. An auction mechanism (MEC) takes some bids submitted by N bidders under a predetermined format and returns two components [START_REF] Hartline | Optimal mechanism design and money burning[END_REF]:

• an allocation of the goods among the bidders,

α MEC = (α MEC 1 , .., α MEC N ), where α MEC i , (0 ≤ α MEC i ≤ 1)
, is the fraction allocated to bidder i. Note that in the ascending auction, the auctioneer (the regulator) may collect bids over multiple rounds.

In the following section, we describe the most desirable properties from the point of view of the regulator.

Properties

In this section, we list the properties that a mechanism may satisfy [START_REF] Li | Designing truthful spectrum auctions for multi-hop secondary networks[END_REF], [START_REF] Kash | Enabling spectrum sharing in secondary market auctions[END_REF]. As for most multi-constraint problems, it is not possible to jointly satisfy all properties, hence the auction designer will have to set a tradeoff between them. For a bidder i, we denote by v i its valuation function for the spectrum, (i.e., how much spectrum is worth to him), by u i its utility function (valuation minus price paid), and by b i its bid function.

In this paper we focus on auction schemes where bids are in monetary units, and interpreted by the auctioneer as the bidder's willingness-to-pay for the allocation(s).

Truthfulness, or Incentive Compatibility

A mechanism is truthful or incentive compatible if and only if for each player i, declaring truthfully one's preferences maximizes one's utility function given any fixed bids of the other players.

Individual rationality

This property means that a player has a bidding strategy (a function that transforms valuation into a bid) that ensures it to get a non-negative utility, hence it is always better off participating in the auction than staying out of the mechanism.

Fairness of the allocation

We refer to fairness as the quality of treating bidders equally. Given N bidders, there exist several measures of fairness such as max-min fairness, proportional fairness and Jain's index [START_REF] Maillé | Telecommunication network Economics[END_REF]. A detailed description of those measures is given in [START_REF] Ahmad | Fairness issues and measures in wireless networks: A survey[END_REF]. We will use Jain's index which is given by:

J(α MEC ) = ( N i=1 α MEC i ) 2 N N i=1 (α MEC i ) 2 .
This index is a continuous function of the allocations, with values in [ 1 N , 1]: it achieves its maximum 1 if all players obtain the same amount, and is minimum 1 N if one and only one player obtains some good. As another reference, a situation in which a% of users receive equal allocation and the remaining (100-a)% receive zero [START_REF] Jain | A quantitative measure of fairness and discrimination[END_REF] gives a Jain index of a/100. Motivated by those features we will use this index to measure the fairness of a mechanism's allocation.

Efficiency

Efficiency E MEC , of a given mechanism MEC, is defined as the sum of the valuations served [START_REF] Roughgarden | Is efficiency expensive[END_REF]:

E MEC = N i=1 v i (α MEC i ). (1)
This means that the social valuation of the good being sold equals the maximum of the potential bidders' individual valuations [START_REF] Maskin | Auctions and Efficiency[END_REF]. Since valuations are private (so they are unknown to the auctioneer), one may wonder how set α to maximize efficiency. When bidders are asked to reveal their valuations in their bids and the auction is truthful, maximizing efficiency can then be done based on bids (which can be assumed to correspond to valuations).

In the following section, we present the system model and bidder preferences. Table 1 summarizes the notations used in this paper.

SYSTEM MODEL AND BIDDER PREFERENCES

In this section, we present the grouping model and the preferences of bidders. This can be captured in a model by using an interference graph. As the manager of the auction, the regulator is assumed to be able to build that interference graph. The regulator is indeed responsible for interconnection dispute resolution and guaranteeing access conditions to networks, and can sanction operators for not meeting legal or regulatory requirements [START_REF] France | Regulatory reform in the telecommunications sector[END_REF]. In particular, the regulator knows the transmission range of base stations, some information necessary to build the graph. Fig. 1 shows an example of such an interference graph: BSs are represented by vertices, an edge between two vertices means that those BSs interfere (their coverage areas overlap). The graph shows for instance that BSs {1, 3, 5} can use the same frequencies simultaneously. By putting in the same group BSs that do not interfere, the competition between N BSs is transformed into a competition between M groups, with the spectrum allocated to a group being then used by the members of the group. An example of group constitution for the interference graph of Fig. 1 is: g 1 = {1, 3, 5} and g 2 = {2, 4}.

In this paper we consider that groups are formed and their composition is sent to bidders before the auction takes place. Note that in some other works [START_REF] Wang | Spectrum Sharing Based on Truthful Auction in Licensed Shared Access Systems[END_REF], [START_REF] Zhou | eBay in the sky: Strategy-proof wireless spectrum auctions[END_REF], grouping is done after bids are received. But bidders could then try to manipulate their bids to change the groups formed so we may loose some properties of the auction.

There are different methods for group formation. In [START_REF] Shao | Lyric: Local recall-based dynamic double spectrum auction mechanism with heterogeneous-demand secondary users[END_REF], the authors form groups by extracting all maximum independent sets; however finding the maximum independent sets in a graph is an NP-Hard problem. In [START_REF] Chouayakh | A truthful auction mechanism for dynamic allocation of LSA spectrum blocks for 5G[END_REF], we have proposed a heuristic for group construction which is easy and fast (quasi-linear complexity with the number of base stations), first sorting BSs in an ascending order of their degree of interference, and treating them in that order while grouping them together as much as possible. The intuition behind this is to create large groups to get closer to the maximum independent sets. Simulations show that the efficiency of that heuristic grouping method is at least 60 % of that of maximum independent sets. In this paper, we suppose groups are given, and we focus on the allocations and payments.

Figure 1: Some base stations with their coverage areas (left), the corresponding interference graph (center), and some possible group configuration (right).

Bidder preferences

In this paper, we assume a quasi-linear utility model for bidders, as commonly done in the literature [START_REF] Lehmann | Combinatorial auctions with decreasing marginal utilities[END_REF], [START_REF] Enderle | User satisfaction models and scheduling algorithms for packet-switched services in umts[END_REF]: the utility of a bidder is the difference between its valuation for the allocated resource and the price it is charged.

We suppose that spectrum in the 2.3 -2.4 GHz is homogeneous i.e., MNOs are only sensitive to the quantity of obtained spectrum and not to the specific allocated spectrum bands.

Finally, we assume that each bidder i's valuation function v i (•) for spectrum is nondecreasing and concave.

In the next section, we present the auction mechanisms which have been proposed as candidates to allocate LSA spectrum. Note that all those mechanisms are one-shot auctions.

CANDIDATE ONE-SHOT MECHANISMS FOR SINGLE-BLOCK LSA SPECTRUM

In this section we consider the case where a unique (indivisible) block of LSA spectrum has to be allocated. In particular, this is the case where the available quantity of LSA spectrum is small. The valuation function v i of a bidder i then comes down to a unique value, that is the valuation for being allocated the block.

In this setting, each bidder i with valuation v i submits a bid b i representing the willingness to pay for all the available LSA spectrum. After receiving bids from bidders, the auctioneer computes a (mechanismspecific) "group-bid" for each group and attributes the bandwidth to the group with the highest group-bid.

Definition 1. The group-bid B MEC

h of a mechanism MEC is a positive real obtained from the bids of a group h (which contains m h bidders) via a function

f MEC h . f MEC h : R m h → R + (b 1 , .., b m h ) → B MEC h = f MEC h (b 1 , .., b m h ) (2)
A necessarily condition to ensure truthfulness, i.e., for there to exist a truthful payment rule [START_REF] Myerson | Optimal auction design[END_REF] is that f MEC h be non-decreasing with respect to each variable.

In the following we present the auction mechanisms from the literature that have been considered for this LSA setting.

TRUST

TRUST [START_REF] Zhou | Trust: A general framework for truthful double spectrum auctions[END_REF] computes the group-bid B TRUST h of each group g h as:

B TRUST h = f TRUST h (b 1 , .., b m h ) = m h inf i∈g h b i .
All the players of the group with the highest group-bid are then winners (i.e., they can use the spectrum), and each has to pay a proportion 1/m h of the second-highest group-bid.

TRUST is truthful and individual rational. However, it computes the group-bid based on the player with the lowest bid of the group. From the point of view of bidders, this mechanism is unfair because the bidder with the lowest bid decides for all the members of its group, i.e., if that bidder has a very low bid then other bidders of its group cannot do anything to change the outcome (from losing to winning). Contrary to TRUST, in LSAA [START_REF] Wang | Spectrum Sharing Based on Truthful Auction in Licensed Shared Access Systems[END_REF] each bidder of the group is involved in the definition of the group-bid.

TLSAA and TLSAA2

In LSAA [START_REF] Wang | Spectrum Sharing Based on Truthful Auction in Licensed Shared Access Systems[END_REF], bids in each group are sorted in a nonascending order. The group-bid of a group g h is computed as:

B LSAA h = max i∈g h rank(b i )b i ,
where rank(b i ) is the rank of player i's bid in the group. This group-bid can be interpreted as follows: it represents the maximum total price that a subset of g h can share equitably. The authors define an index c such that:

c = max rank(b l ), l ∈ arg max i∈g h (rank(b i )b i ) . (3)
If g h is the winning group, then only players with rank below or equal to c are winners. Winners pay the second highest group-bid equally.

Authors of LSAA claim that LSAA is truthful. However, it is not the case as we have shown in [START_REF] Chouayakh | PAM: A Fair and Truthful Mechanism for 5G Dynamic Spectrum Allocation[END_REF], and in [START_REF] Chouayakh | Licensed shared access for 5g: Which auction mechanism to choose?[END_REF] we have proposed two variants that are truthful: TLSAA and TLSAA2. Both mechanisms compute the group-bid of each group in the same way as LSAA, however TLSAA is more efficient than LSAA, with a lower revenue. On the other hand TLSAA2 has the same revenue as LSAA and is more efficient (but less than TLSAA). More specifics are given below.

• TLSAA: all the bidders of the winning group (the one with the highest group-bid) can use the bandwidth, and each bidder i in that group is charged a price

p TLSAA i = inf{ bi s.t. α LSAA i ( bi ) = 1}, (4)
where α LSAA i ( bi ) is the allocation that bidder i would get by bidding bi instead of b i , all other bids remaining unchanged.

• TLSAA2: The allocation rule is defined as follows: a winning player which belongs to the group g w should not only belong to the winning group but also bid at least as high as player c where c is defined as follows:

c = max rank(b i ), i ∈ g w and rank(b i )b i ≥ B LSAA second , (5)
where B LSAA second is the second highest group-bid. In turn, the payment rule is defined as follows: each winning player pays an amount equal to

B LSAA second c .

VCG

The general principle of VCG (Vickrey-Clarke-Groves) auctions [START_REF] Vickrey | Counterspeculation, auctions, and competitive sealed tenders[END_REF]- [START_REF] Groves | Incentives in teams[END_REF] is to allocate resources to maximize the "declared" efficiency (since computed based on submitted bids) and charge each bidder the loss of declared efficiency its presence causes to the others. We denote by E -i a the efficiency when bidder i is absent, and by E -i p the efficiency when bidder i is present but without counting it. The payment rule is therefore:

p VCG i = E -i a -E -i p .
VCG is known to be the unique mechanism which is jointly truthful, individually rational and maximizes efficiency.

The implementation of VCG for the LSA context can be done by defining the group-bid of a group g h as

B VCG h = i∈g h b i .
For the payment we proceed as follows: if a player belongs to a losing group it pays 0 because whether it is present or not the winning group is the same. If a player belongs to the winning group g win with groupbid B VCG win then we can distinguish two cases: if its presence does not change the outcome, i.e., B VCG win

-i ≥ B VCG
second (with B VCG second the second-highest group-bid and B VCG win -i the group-bid of the winning group when player i is absent) then it pays 0, otherwise it pays B VCG second -B VCG win -i . To summarize:

p VCG i = [B VCG second -B VCG win -i ] + , (6)
with the notation [x] + = max(x, 0). Note that some bidders having to pay 0 does not impact economic efficiency, since it is defined only in terms of valuations for the allocation (not prices paid). Economic efficiency may on the other hand be affected if some bidders submit bids under multiple identifiers (false-name bidding), as has been pointed out in [START_REF] Alkalay-Houlihan | False-name bidding and economic efficiency in combinatorial auctions[END_REF]. However, for the LSA context this cannot be the case because each base station is well-defined by its location and can submit only one bid).

Allocating the available quantity of spectrum as a unique block makes sense if that quantity is small. However, if the available LSA spectrum is large, then the auctioneer may decide to split it to allocate some spectrum to more bidders. We assume that in that case, the spectrum will be split into several blocks of the same size [START_REF] Hou | Optimal spectrum sharing for multi-hop software defined radio networks[END_REF]. Splitting spectrum may increase the outcome of the auction with respect to any metric, as an example it can increase fairness of the allocation since spectrum will not be necessarily allocated to one and only one group, but it may complicate the auction analysis. In the following we treat the case where the auctioneer has K blocks to allocate.

FROM SINGLE-BLOCK TO MULTI-BLOCK AUC-TION MECHANISMS

We will take into account the concavity of valuations. We suppose that spectrum is split into K identical blocks 1 , identical meaning that BSs do not have preferences over blocks [START_REF] Zhou | eBay in the sky: Strategy-proof wireless spectrum auctions[END_REF], [START_REF] Wang | Designing truthful spectrum double auctions with local markets[END_REF].

Each BS i has a private valuation vector v i composed of K elements: the first element v i,1 represents the valuation for being allocated one block, and the n th element v i,n (n > 1) represents the extra valuation for BS i for an n th extra block given that it has already n -1 blocks. The valuation of a block, for a BS, decreases with the number of blocks already obtained. This corresponds to a discretization of concave valuation functions for spectrum [START_REF] Enderle | User satisfaction models and scheduling algorithms for packet-switched services in umts[END_REF], as illustrated in Fig. 2. Recall that we adopted a quasi-linear utility model, so that if a BS i obtains n b i blocks and pays p i , its utility is then:

u i = n b i n=1 v i,n -p i .
In addition, an operator obtaining no block gets a utility equal to zero.

Valuation

Obtained spectrum (MHz)

v i,1 v i,2 v i,3 v i,4 v i,5 v i,6 Block size

Converting all-or-nothing schemes to multiblock allocation schemes

With the spectrum to allocated being divided into K blocks of equal size, the bid format and the notion of group-bid need to be extended, both will now be vectors.

Following our convention for valuations, each BS submits to the auctioneer a bid vector b i composed of K elements in a non-increasing order, which will be interpreted as willingness-to-pay for extra blocks: b i,n represents the bid of BS i for an n th extra block given that it has already n -1 blocks.

We denote by B MEC h the group-bid vector of g h , which is also composed of K elements and is interpreted similarly: the n th element of B MEC h represents 1 In this paper, we suppose that spectrum (the 2.3-2.4 GHz bandwidth) is homogeneous. If spectrum is heterogeneous or if blocks are not identical, we can apply other approaches from the literature [START_REF] Shao | Lyric: Local recall-based dynamic double spectrum auction mechanism with heterogeneous-demand secondary users[END_REF], however the allocation problem in such a situation (when bidders have decreasing marginal utilities) is in general an NP-hard problem [START_REF] Lehmann | Combinatorial auctions with decreasing marginal utilities[END_REF] which is undesirable for the LSA context because the auction must run as fast as possible. In addition we cannot make a sub-optimal allocation while preserving truthful bidding, since in that situation there is no payment rule which guarantees truthful bidding [START_REF] Lehmann | Combinatorial auctions with decreasing marginal utilities[END_REF].

the bid of g h for an n th extra block given that it has already n -1 blocks.

In the mechanisms we study, each n th component of the group-bid vector will depend only on the n th component of the group members' bid. Formally, for each n = 1, ..., K,

B MEC h,n = f MEC h ({b i,n , i ∈ g h }). (7
}, in group 3: {(13, 10, , therefore the third group obtains three blocks.

Payments

We denote by p MEC i the payment vector of bidder i when the mechanism MEC is applied: p MEC i,n will be the payment of bidder i for its n th block. We suggest to apply the payment rule that will ensure a truthful bidding (as we will also show next): following the principles in [START_REF] Roughgarden | Ascending and ex post incentive compatible mechanisms[END_REF], the payment of player i (in group h) for its n th block with then be defined as:

p MEC i,n = inf r : f MEC h ({b j,n , j ∈ g h \i} ∪ {r}) ≥ C MEC h,n (9)
This payment can be interpreted as follows: for its n th block, bidder i pays the minimum amount r that allows it to obtain that block i.e., the minimum amount such that B MEC h,n ≥ C MEC h,n . Example 2. Let us take Example 1 and compute the payments of the first player of the third group. The payment rule of VCG using (8) is:

p VCG i,n = inf{r : r + j∈g h \i b j,n ≥ C VCG h,n } =   C VCG h,n - j∈g h \i b j,n   + .
The third group obtains three blocks, the payment of the first player is then:

[10 -(11 + 9)] + + [17 -(8 + 8)] + + [19 -(6 + 5)] + = 9.
This payment can be interpreted as follows:

p VCG i,n
is zero when the presence of bidder i does not change the outcome (i.e., there is no damage for other bidders).

p VCG i,n
is strictly positive only if the presence of bidder i causes damage to other bidders, i.e., when its presence makes that block be allocated to g h instead of to another group (the one whose bids led to the value C VCG h,n ). In that situation, the damage caused to other bidders is C VCG h,n , but its presence is beneficial to the members of its group (the gain from its presence is j∈g h \i b j,n ). The difference between those two quantities is then (C VCG h,n -j∈g h \i b j,n ). We now prove that the proposed mechanism with allocation given in [START_REF] Chouayakh | Licensed shared access for 5g: Which auction mechanism to choose?[END_REF] and payment given in ( 9) is truthful. Let us first introduce the two following lemmas. Lemma 1. Payments for blocks can only increase i.e., if player i pays p MEC i,n for its n th block then it pays p MEC i,n+1 ≥ p MEC i,n for its (n + 1) th block.

Proof. This is a consequence from the payment rule:

p MEC i,n = inf r : f MEC h {r} ∪ {bj,n, j ∈ g h \i} ≥ C MEC h,n ≤ inf r : f MEC h {r} ∪ {bj,n, j ∈ g h \i} ≥ C MEC h,n+1 ≤ inf r : f MEC h {r} ∪ {bj,n+1, j ∈ g h \i} ≥ C MEC h,n+1 = p MEC i,n+1
For the first inequality we have used the fact that

C MEC h,n+1 ≥ C MEC h,n .
For the second inequality we have used the fact that for any bidder j, bj,n ≥ bj,n+1 and the fact that f MEC h is a non-decreasing function.

In the following, we call a component b i,n of the bid vector of player i a winning component if b i,n ≥ p MEC i,n and a losing component if b i,n < p MEC i,n . Lemma 2. If a player gets n blocks, then the winning components of its bid vector are exactly its first n components.

Proof. Assume that there is a situation in which b i,n is a losing bid and b i,n+1 is a winning bid: b i,n being a losing bid means that b i,n < p MEC i,n with p MEC i,n the price that it would have pay for the n th block, and b i,n+1 being a winning bid means that b i,n+1

≥ MEC i,n+1 , hence from Lemma 1, b i,n+1 ≥ p MEC i,n
and then b i,n+1 > b i,n , a contradiction.

We can now establish the main result of this section. Proposition 1. For the proposed mechanism with allocation rule in [START_REF] Chouayakh | Licensed shared access for 5g: Which auction mechanism to choose?[END_REF] and payment rule in [START_REF] Ausubel | An efficient ascending-bid auction for multiple objects[END_REF], truthful bidding, is a dominant strategy i.e., for each bidder i, proposing (b i,1 , .., b i,K ) = (v i,n , .., v i,K ) maximizes its utility.

Proof. Suppose that by bidding truthfully, player i (which belongs to group h) gets n blocks. From lemma 2 its winning bids are the first n bids. For its first n bids, player i cannot do better than proposing its true valuations: lowering the corresponding bids could make it lose blocks that are charged below its valuation for them, and increasing those bids would have no impact because it pays the same amount. Player i does not obtain an (n + 1) th block, so we have

B MEC h,n+1 = f MEC h ({b j,n+1 , j ∈ g h \i} ∪ {v i,n+1 }) < C MEC h,n+1 . If player i wants an (n+1) th block then it has to propose a bid b i,n+1 such that B MEC h,n+1 ≥ C MEC h,n+1
, however this leads to a lower utility: in this situation, player i pays an amount r higher than

v i,n+1 because f MEC h ({b j,n+1 , j ∈ g h \i} ∪ {v i,n+1 }) ≤ C MEC h,n+1 , f MEC h ({b j,n+1 , j ∈ g h \i} ∪ {r}) ≥ C MEC h,n+1 and f MEC h is an increasing function.
After showing how to convert one-shot single block auction mechanism to one-shot multi-block auction mechanism, a natural question is how to set the number of blocks.

How to set the number of blocks for a given quantity of spectrum?

Choosing the number of blocks is very important because it may impact the outcome of the auction especially in terms of revenue as we show in the following example.

Example 3. We suppose that the auctioneer has a quantity of spectrum that could be split into two blocks so it can allocate that quantity as a single block or two blocks. There are three groups, with each group composed of one bidder. We consider two different cases.

• Assume that the valuation vectors of bidders for two blocks are: {30, 1}, {25, 3} and {4, 2}. The valuation of bidders for the whole spectrum as a single block are then 31, 28 and 6, respectively. If the auctioneer allocates spectrum as a single block, then the first bidder obtains that block and pays 28, while if the auctioneer allocates the spectrum as two blocks then bidder one and bidder two obtain one block each one and each bidder pays 4, yielding a revenue 8.

• Now assume that the bidders' valuation vectors for two blocks are: {10, 5}, {10, 1} and {9, 0}, hence valuations for the whole spectrum as a single block 15, 11 and 9. If the auctioneer allocates spectrum as one block then the first bidder obtains that block and pays 11, while selling the spectrum as two blocks would yield a revenue 18, bidder one and bidder two obtaining one block and paying 9 each. Therefore, splitting spectrum will impact the outcome of the auction. We further evaluate the impact of the number of blocks on the different metrics by simulations. We are particularly interested in average efficiency and fairness metrics, as well as in the average revenue of the auctioneer.

Simulation settings

In the simulations we perform, we suppose that the available quantity of LSA spectrum can be split into 10, 5 or 2 blocks (or it can be allocated as a unique block). For each metric, the average valuation is computed over 1000 draws. For each draw, we generate the number of groups uniformly between 2 and 10. The number of bidders in each group is also chosen from the discrete uniform distribution, over [START_REF] Khun-Jush | Licensed shared access as complementary approach to meet spectrum demands: Benefits for next generation cellular systems[END_REF][START_REF] Zhou | eBay in the sky: Strategy-proof wireless spectrum auctions[END_REF]. Bidder valuations are drawn from the uniform distribution U(0, 100) (and we repeat the same process when valuations are drawn from the exponential distribution with mean 50). For each bidder, we generate 10 bids then we sort those bids in a non-increasing order. The first bid represents the bid for the first block and the last bid represents the bid for the 10 th block. We create the bid vector from those bids with respect to the number of blocks. For example, if the available spectrum will be allocated as a one block then we add up all those components to create one bid.

Results

In terms of efficiency, Table 2 and Table 3 show that as we increase the number of blocks we increase the efficiency of the allocation (valuation functions being concave, one can extract more value by sharing the resource among groups than by allocating it to only one group).

In terms of fairness, Table 4 and Table 5 show that as we increase the number of blocks, fairness increases. This seems to be natural since as we increase the number of blocks there are more chances that each group will be served which leads to increasing Jain's index.

In terms of revenue, Table 6 and Table 7 show that the optimal number of blocks depends on the valuations' distribution. The regulator can maximize its revenue by choosing TLSAA2 and setting K = 10 for the uniform distribution and K = 5 for the exponential distribution.

In order to set the optimal number of blocks, we have to define the utility function of the regulator, which we assume will depend on the revenue and the allocation's fairness and efficiency. A possible way to do that is to consider a weighted sum of those three metric, with a nonnegative weight vector β = (β 1 , β 2 , β 3 ) such that β 1 is the weight for revenue, β 2 for fairness and β 3 for efficiency. According to β we can select the mechanism and the number of blocks maximizing that utility, just by computing the weighted sums of the corresponding metric values from the tables. As an example, if β 1 = 0 (the regulator is not sensitive to revenue) and bids are drawn from the exponential distribution, then by setting K = 10, and applying VCG, the regulator can maximize its utility (see Table 2 andTable 4 ).

Those results illustrate how one can select the most appropriate settings (number of blocks and mechanism) depending on the auctioneer's priorities. However, as pointed out earlier one may prefer mechanisms that do not involve bidders (especially winners) revealing their whole preferences. Hence in the following, we focus on transforming those one-shot auctions into "ascending auctions", where information is revealed by bidders during some convergence phase.

K 10 5

FROM ONE-SHOT TO ASCENDING AUCTION

MECHANISMS

In this section we show how to convert the previously studied one-shot schemes into ascending schemes. We start by presenting the clinching auction [START_REF] Ausubel | An efficient ascending-bid auction for multiple objects[END_REF], then show how to adapt it if to the LSA context.

Background: the clinching auction

The clinching auction is an ascending auction for K homogeneous goods, where bidders have decreasing marginal valuations as presented in Section 5. At each round t, the auctioneer declares a unit price p t and bidders respond by asking for a quantity (at each round the demanded quantity cannot exceed the demanded quantity in the previous round) at that price, the price increasing (in general we can increment by > 0 but here with discretized valuations we take p t+1 = p t + 1) until demand is no greater than supply K. Bidders' payments are computed during the auction: an active bidder clinches (obtains) an item at price p if the demand of the other players at that price falls below the supply.

To compute allocations and prices, the seller uses two quantities, namely cumulative clinch and current clinch, defined as follows. The cumulative clinch Cl t i of player i at round t is defined as:

Cl t i = max{0, K - j =i d t j }, (10)
with d t j the demand of player j at round t. The increment of the obtained blocks is called the current clinch at round t of player i, and denoted by cl t i :

cl t i = Cl t i -Cl t-1 i . (11)
When the auction ends, each bidder i obtains a quantity equal to its cumulative clinch, and its payment p i is:

p i = T t=0 p t cl t i . (12)
Ausubel proved [START_REF] Ausubel | An efficient ascending-bid auction for multiple objects[END_REF] that the clinching auction achieves the outcome of VCG i.e., it ensures an efficient allocation, charges each player with its Vickrey payment and bidding truthfully is an ex post Nash equilibrium: bidding truthfully is a best strategy if all other players also bid truthfully, without knowing the other players' valuations [START_REF] Roughgarden | Ascending and ex post incentive compatible mechanisms[END_REF]. Here, bidding truthfully means that each player reports its demand with respect to its valuations: d t i (p) = max{n such that v i,n > p t }, for a given declared price p t . Example 4. An illustrative example is provided in Table 8, with three items and three players with respective marginal valuations (6, 4, 0), (5, 3, 2), (2, 1, 0). We assume that players are not willing to pay a price per block equal to the valuation of that block, as an example if player one gets one block for a price p t = 6 then its utility is zero, hence we will suppose that for p t = 6 player one will not demand any block i.e., its demand is zero.

For p t = 2, the sum of demands of player two and three is equal to 2, hence, cl 2 1 = 1 -0 = 1, player one clinches its first block at price 2. Similarly, player two clinches its block at the same price. At p t = 3, cl 3 1 = 2 -1 = 1, thus player one clinches its second block. Finally the auction concludes at price p t = 3 (d 1 + d 2 + d 3 = 3), player one obtains two blocks and pays 2 + 3 = 5 and player two obtains one block and pays 2.

Round 0 1 2 3 Price 0 1 2 3 Total demand 7 6 4 3 = K d 1 2 2 2 2 Cl t 1 0 0 1 2 cl t 1 0 0 1 1 p 1 0 0 2 2+3 d 2 3 3 2 1 Cl t 2 0 0 1 1 cl t 2 0 0 1 0 p 2 0 0 2 2 d 3 2 1 0 0 Cl t 3 0 0 0 0 cl t 3 0 0 0 0 p 3 0 0 0 0 Table 8: A auction example for K = 3 items
Remark: We denote by c i the highest K valuations of other players facing player i. If a player obtains its n th block at a unit price p t then p t is the minimum amount such that the sum of demands of all other players is K -n, clearly p t corresponds to c i,n .

Adapting the clinching approach to LSA

We propose two equivalent (in terms of allocations and payments) ascending versions of a one-shot auction mechanism with a function f MEC h , based on the clinching approach: in the first version we introduce a representative per group, that will act as an intermediary between bidders and the auctioneer. In the second version, we remove those representatives so that the auction will be between the auctioneer and bidders. This is an extension of our work in [START_REF] Chouayakh | Licensed shared access for 5g: Which auction mechanism to choose?[END_REF].

Implementation with representatives

In this version, a representative per group will act on behalf of members of that group, as an interface between BSs and the auctioneer. There is no direct communication between BSs and the auctioneer (see Figure 3), the auction will be between the M group representatives and the auctioneer.

Before the auction takes place, each BS i transmits to the representative of its group its bids vector b i , which can be different from v i , then each representative h constructs the group-bid vector based on the received bids

(B MEC h,n = f MEC h ({b j,n , j ∈ g h })
). As in the initial clinching auction, the auctioneer broadcasts a per-block price P t starting with P = 0, which to simplify notation we write P instead of P t . Each representative h then responds with its demand D t h (P ), that is, a number of blocks the group is willing to buy at round t at that price:

D t h (P ) = max{n, B MEC h,n > P }. (13)
The auctioneer keeps increasing P by one unit until the sum of demands of all representatives is equal to or below K (see Fig ( 5)). To perform clinching (i.e., decide on block allocations), we use the same model as before but adapt it to groups (representatives): the cumulative clinch Cl t h of representative h is then defined as:

Cl t h (P ) := max{0, K - j =h D t j (P )}. (14)
Figure 3: The approach with a representative per group As in the original scheme, the current clinch at time t for representative h is the increment of Cl t h .

cl t h (P ) = Cl t h -Cl t-1 h . ( 15
)
After obtaining a block at price P , each representative charges each BS i of its group as follows:

p h i,n = min{r : f MEC h ({r} ∪ {b j,n , j ∈ g h \i}) ≥ P } (16)
Summarizing, the ascending auction we propose would follow the following steps: 1) Each BS reports to the corresponding representative its bids vector.

2) The representative of each group constructs its vector of valuations.

3) At each round, each representative h reports its demand D t h (P ) to the auctioneer. 4) The auctioneer computes the cumulative clinch Cl t h of each representative h at round t which is defined as Cl t h = max{0, Kj =i D t j }, with D t j the demand of other representative j at round t. the current clinch at round t of the group h is denoted by cl t h :

cl t h = Cl t h -Cl t-1 h . (17)
5) If a representative clinches a block at a price P then it charges each BS i of its group a price given in [START_REF] Jain | A quantitative measure of fairness and discrimination[END_REF] and sends that amount to the auctioneer. 6) If the demands of all representatives is higher than K, then the auctioneer increases P at the next round and we go back to step 3, otherwise the auction ends. Table 9 shows the evolution of the auction i.e., the demand of each group at each round. The auction stops 9: Demand and price evolution of the clinching auction with representatives taking VCG as the elementary mechanism at P = 14 (when the sum of demands equals 4):

• The first group clinches its first block at P = 10. Each bidder of that group pays zero.

• At P = 13 the first group clinches its second block. The first bidder pays 13 -(7 + 3) = 3, the second bidder pays also 3 and the third bidder pays [13 -14] + = 0.

• At P = 14, the second and the third group clinch their first block. The first bidder of the second group pays 14 -9 = 5. The second bidder of the second group pays 14 -7 = 7. The bidder of the third group pays 14.

An important question which may arise regards convergence rate of the algorithm. We denote by S MEC the vector composed of all the groupbid vectors sorted in a non-increasing order. The size of S MEC is M × K. In Example 5, S VCG = [START_REF] Chouayakh | A truthful auction mechanism for dynamic allocation of LSA spectrum blocks for 5G[END_REF][START_REF] Roughgarden | Is efficiency expensive[END_REF][START_REF] Jain | A quantitative measure of fairness and discrimination[END_REF][START_REF] Ahmad | Fairness issues and measures in wireless networks: A survey[END_REF][START_REF] Maillé | Telecommunication network Economics[END_REF][START_REF] Kash | Enabling spectrum sharing in secondary market auctions[END_REF][START_REF] Chouayakh | Auction mechanisms for licensed shared access: reserve prices and revenue-fairness trade offs[END_REF][START_REF] Ausubel | An efficient ascending-bid auction for multiple objects[END_REF][START_REF] Ausubel | An efficient ascending-bid auction for multiple objects[END_REF][START_REF] Zhu | Stamp: A strategy-proof approximation auction mechanism for spatially reusable items in wireless networks[END_REF][START_REF] Chen | Tames: A truthful auction mechanism for heterogeneous spectrum allocation[END_REF][START_REF] Khun-Jush | Licensed shared access as complementary approach to meet spectrum demands: Benefits for next generation cellular systems[END_REF]. In the following we provide the convergence rate of the auction.

Proposition 2. The auction concludes after S MEC

K+1 rounds, where S MEC K+1 is the K th component of S MEC .

Proof. At each price P the demand of each representative corresponds to the number of components in the group-bid vector that are higher than P . In particular if P = S MEC K+1 then the sum of demands of all representatives is exactly K, also S MEC K+1 is the minimum price at which the sum of demands is exactly K, for P = S MEC K+1 -1 the sum of demands is K + 1. Therefore, the auction ends after S MEC K+1 rounds.

In the following, we investigate the truthfulness of the proposed mechanism. Proposition 3. From the point of view of a BS, proposing a bid b i to the representative is the same as proposing a bid to the auctioneer in the one-shot version: both auctions will generate the same outcome (allocations and payments).

Proof. After receiving bids from BSs, each representative of g h computes the group-bid vector of g h , (before that step is made by the auctioneer). A representative obtains its n th block at price P means that the demand of other groups at that price is K -n and at P -1 is K + 1 -n, therefore P must be equal to C MEC h,n . Thus the auction with representatives leads to the some allocation as the one-shot version. Now, for its n th block i.e., when P = C MEC h,n , player i will be charged, by the representative. That amount is the same as before (see [START_REF] Ausubel | An efficient ascending-bid auction for multiple objects[END_REF]). Therefore both auction lead to the same allocations and payments. Proposition 4. After introducing representatives, for each bidder i, reporting its true valuation vector to the corresponding representative is a dominant strategy.

Proof. Since in the one-shot version bidding truthfully is a dominant strategy, then here also bidding truthfully is a dominant strategy.

The implementation with representatives may introduce "the black box effect": from the point of view of players, they cannot see the evolution of the auction (they are just asked to pay an amount for an obtained block). For the auctioneer, it cannot see how each BS is charged. Therefore in the following we propose an ascending implementation without representatives.

Implementation without representatives

In this scenario, the auction will be between the regulator and BSs. Similarly to what was presented before, the auctioneer fixes a unit price P and keeps increasing P until demand of groups is no higher than supply. The question here is how to compute the demand of groups?

We propose to introduce a unit price p h per group and proceed as follows: for each price P , the auctioneer keeps increasing p h and asks each player of group h its demand d i (p h ), until it can compute the demand of group h D h (P ) i.e., demands of groups will be computed from demands of players as shown in [START_REF] Maskin | Auctions and Efficiency[END_REF] (to simplify we write D h (P ) instead of D t h (P )). D h (P ) = max{n :

∃ ({r h 1 , ..., r h m h ) ∈ R |m h | s.t. d i (r h i ) = n ∀ i ∈ g h and f MEC h (r h 1 , ..., r h m h ) > P } (18)
Note that bidder i reporting its demand truthfully means that d i (p h ) = max{n, v i,n > p h }.

We now show that this demand is the same as the one presented before (with representatives). Proposition 5. The demand of a group h given in ( 18) is equivalent to the demand given in [START_REF] Kash | Enabling spectrum sharing in secondary market auctions[END_REF].

Proof. In order to prove the equivalence we show the following equivalence:

B MEC h,n > P ⇐⇒ ∃ (r h 1 , ..., r h m h ) ∈ R |m h | s.t. d i (r h i ) = n and f MEC h (r h 1 , ..., r h m h ) > P ⇒. Assume B MEC h,n > P : then f MEC h (b 1,n , ..., b m h ,n ) > P , since f MEC h is a continuous function. Thus we can find ( i , .., m h ) such that f MEC h (b 1,n -1 , ..., b m h ,n - m h ) > P . By setting r h i = b i,n -i we obtain f VCG h (r h 1 , .., r h m h ) > P and d i (r h i ) = n. ⇐. Assume ∃ (r h 1 , ..., r h m h ) ∈ R |m h | s.t. d i (r h i ) = n andf MEC h (r h 1 , ..., r h m h ) > P : this means that b i,n > r h i ∀i (because d i (b i,n ) = n-1) since f MEC h (r h 1 , .., r h m h ) > P , then f MEC h (b 1,n , .., b m h ,n ) > P .
The auctioneer keeps increasing p h until it can compute the demand of group h at price P (see Fig. 4). Remark: Preserving valuations of players is one of the most desirable properties of multi-round auctions, however the auctioneer may have an idea about valuations of some players. As an example, in the English auction, if a player drops out at a price, then that price corresponds exactly to its valuation. Similarly here, when introducing prices per group, the auctioneer can have some idea about valuations of some players: if

d i (p h ) = n and d i (p h + 1) = n -1 then b i,n = p h + 1.
To determine how to charge each player, we will use the same logic as before: Let us fix the first bidder of g h . If g h can clinch an n th block without the participation of that bidder, then the first bidder pays zero. Otherwise group h cannot clinch that block therefore we can compute the maximum amount that it can pay for that block i.e., from demand of players we can compute B MEC h,n -1 and therefore player 1 pays P -B MEC h,n -1 . Example 6. Take the same configuration as example 5. Let us compute the demand of the first group. To compute D 1 (P ) for P = 1, we start with p 1 = 1 and ask players of group one their demand at 1 . All players are willing to buy 4 blocks at that price, hence we know that D 1 (P ) = 4 as long as P ≤ 3, each player is willing to pay a unit price r 1 1 = r 1 2 = r 1 3 = P 3 . For P = 4 we need to ask individual demands at p 1 = 2. Truthful answers give d 1 (2) = 4 and d 2 (2) = d 3 (2) = 3, so we know that D 1 (P ) = 4 as long as P ≤ 5.

For P = 6, we know from the responses for p 1 = 2 that D 1 (P ) ≥ 3. We increase p 1 (p 1 = 3). Since player one is willing to buy 4 blocks at a unit price 3, then D 1 (P ) = 4, (r 1 1 = 3, r 1 2 = r 1 3 = 1.5). Following that process, we derive the group demands. D 1 (P ) = 4 for P < 9, D 1 (P ) = 3 for 9 ≤ P ≤ 13 and D 1 (P ) = 2 for P = 14.

At each P , we compute the demand of all groups as shown for the first group, until total demand gets equal to or lower than K. We conclude that the auction stops at P = 14 (when the sum of demands equals 4). The outcome is the following: • The first group clinches its first block at P = 10. Each player of that group pays zero because when it is absent the other players of group one could obtain that block.

• At P = 13 the first group clinches its second block. The first bidder pays 13 -(7 + 3) = 3, because from p 1 = 8 we can see that bidder two can pay a maximum amount of 7 for a second block and the third bidder can pay a maximum amount of 3. The second bidder pays 3 and the third bidder pays 0.

• At P = 14, the second and the third group clinch their first block. The first bidder of the second group pays 14 -9 = 5 (p 2 was incremented till 9 which corresponds to the maximum amount that bidder two of that group can pay in order to obtain one block). The second bidder pays 14 -7 = 7. The bidder of the third group pays 14.

Can we compute the demand of group h at price P ?

P = P + 1
Each player of group h reports its demand for p h Compute the current clinch of each group [START_REF] Roughgarden | Is efficiency expensive[END_REF]. end while Proposition 6. In the ascending implementation of MEC without representative, truthful telling is an ex post-Nash equilibrium.

Proof. Let us fix a player i, suppose that all other BSs report their demand truthfully during the auction. By reporting its true demand, player i will obtain the same utility as in the auction with the representatives since both auctions have the same allocations (same demands) and payments (by construction). We denote by u 1 that utility. Now we have to show that any other strategy of demanding for player i will reduce its utility.Suppose that that strategy generates a strictly higher utility: player i could obtain that same utility in the first implementation (with representatives) by proposing a bid vector with respect to those reported demands i.e., if d i (p h ) = n -1 and d i (p h -1) = n then it fixes b i,n = p h . This is a contradiction because in the first implementation, proposing the valuation is a dominant strategy.

Note that in this section, there is no need for performance evaluation since we already know the performance of the equivalent one-shot versions. If the regulator is satisfied by the performance of a one-shot auction, then it can implement its equivalent ascending version and add privacy and transparency.

CONCLUSION

In this paper, we have studied frequency allocation in the context of 5G LSA. Under LSA the owner of the 2.3 -2.4 GHz bandwidth can share its bandwidth with MNOs. Sharing is done after obtaining a license from the regulator. Such attribution of licenses is made via an auction mechanism.

Potential candidate auction mechanisms for the LSA context are truthful one-shot auctions. A one-shot auction mechanism is composed of a single round so bidders have only one chance to submit bids for the auctioneer. In addition, those mechanisms of the literature attribute all the available spectrum as a one block.

In this paper, we have investigated the above mentioned considerations through these questions: can we improve the outcome of the auction by splitting the available spectrum ? In that case, how to convert all-ornothing auction mechanisms into multi-block auction mechanisms? Can we develop equivalent ascending versions of those mechanisms?

We have supposed that the LSA spectrum can be split into several blocks, and shown how to convert a single-block auction mechanism into a multi-block auction mechanism. The choice of the number of blocks can increase efficiency or fairness but also decrease revenue, hence a trade-off for the auctioneer.

We have considered ascending auctions, that are more transparent than one-shot auctions (bidders see the auction evolution), and preserve privacy (bidders do not necessarily need to reveal all their valuations). We have shown, by using the "clinching" approach, how to convert one-shot multi-block auction mechanisms into ascending auction mechanisms with comparable properties.

This paper can be extended in several directions. First, studying LSA auctions as a repeated game [START_REF] Osborne | An introduction to game theory[END_REF] can be of interest, since the auction may be run many times per day in some configurations. Repeated games have a larger strategy space: bidders may decide to cooperate, which can be sustained by punishing deviating players over future iterations. Other interesting directions for future works include the treatment of the case of non-homogeneous (non-identical) spectrum blocks: computing efficient allocations then becomes an NP-hard problem, hence heuristics must be used which then affect the incentive-compatibility properties of the mechanism. Therefore, more intricate definitions of those properties would be needed, e.g., involving beliefs about the other players and their bids, and/or considerations of the computational cost for a bidder to optimize its bid (versus the expected gain in utility).

•

  a payment vector p MEC = (p MEC 1 , .., p MEC N ),where p MEC i is the price that player i is charged.

Figure 2 :

 2 Figure 2: An example of a concave valuation function of obtained spectrum

1 = 2 = 3 = 3 , 1 = 2 = 3 = 1 ( 25 > 2 ( 21 >VCG 3 ( 33 >

 1233123125221333 }. Let us apply VCG, i.e. B VCG h,n = j∈g h b i,n . The group-bids are then B VCG {25, 19, 10, 8, 2}, B VCG {21, 17, 7, 5, 3}, B VCG {33, 26, 20, 16, 9}. Now let us compute the allocations. The five highest group-bids are {33, 26, 25, 21, 20}; three of those components (33, 26, 20) are in B VCG therefore the third group obtains three blocks. One component (21) is in B VCG 2 then the second group obtains one block and one component (25) is in B VCG 1 then the first group obtains one block. We can also perform allocations based on group-bid vectors and facing-bid vectors as follows. Let us first introduce facing-bids: C VCG {17, 20, 21, 26, 33}, C VCG {19, 20, 25, 26, 33}, and C VCG {10, 17, 19, 21, 25} The allocation can be performed as follows: B VCG 1 defeats only one element of C VCG 17), therefore the first group obtains one block. B VCG 2 defeats only one element of C VCG 19), therefore the second group obtains one block. B VCG 3 defeats three elements of C 10, 26 > 17, 20 > 19)

Example 5 . 1 =

 51 Consider M = 3 groups and K = 4 blocks, with the following valuation vectors: • in group 1 (3 players): (9, 7, 6, 5), (7, 7, 5, 2), (6, 3, 3, 2); • in group 2 (2 players): (7, 6, 4, 3), (9, 7, 5, 2); • in group 3 (1 player): (15, 10, 3, 1).The group-bids are then B VCG

p h = p h + 1 Figure 5 :Algorithm 1

 151 Figure 5: Applying the clinching approach to LSA.

Table 1 : Notations 3.1 Grouping BSs before the auction

 1

	K	number of blocks
	M	number of groups
	m h	number of players in group h
	α	allocation vector
	v i	valuation function of bidder i
	b i	bid function of bidder i
	B MEC h p MEC i C MEC h Cl t i Cl t h d t i D t h cl t i cl t h	group-bid of group h with mechanism MEC payment of bidder i with mechanism MEC vector of competing bids facing group h cumulative clinch of bidder i at round t cumulative clinch of group h at round t demand of player i at round t demand of group h at round t current clinch of bidder i at round t current clinch of group h at round t
	P	unit price per group
	p h	unit price per bidder for group h
	Most LSA auction mechanisms which involve spectrum
	re-usability act as follows: they consider a scenario in
	which multiple BSs of different operators compete for
	LSA spectrum at a defined period of time in a particular
	geographical area; two BSs can use the same bandwidth
	simultaneously if they do not interfere with each other.

  )5.1.1 AllocationOnce group-bid vectors are computed from players' bids, the regulator obtains M × K values in total (M group-bid vectors with K elements each).Blocks are then allocated to the highest K "bids" among those M × K, as if they were independent. In practice, we denote by C MEC h the vector of competing bids facing group h, i.e. C MEC h is composed of the highest K bids from the other M -1 groups. C MEC h is sorted in an ascending order, with its components being denoted by C MEC h,n , n = 1, ..., K. The number of blocks that a group wins is then the number of competing bids it defeats:

if B MEC h,n > C MEC h,n then g h obtains an n th block. (8) Example 1. Suppose we have five blocks to allocate to three groups which are composed of one, two and three players respectively, with players' bids: in group 1: {(25, 19, 10, 8, 2)}, in group 2: {(10, 9,

Table 2 :

 2 Average efficiency vs number of blocks (bids drawn from uniform distribution U(0, 100))

				2	1
	VCG		13129.0	12406.25	9269.4
	TLSAA	13304.88	13048.3	12346.1	9104.45
	TLSAA2	13150.2	12926.8	12149.3	8873.5
	TRUST	13073.1	12893.78	12124.7	8971.9
	K	10	5	2	1
	VCG	19213.3	18061.5	14682.6	9396.88
	TLSAA	19085.6	17946	14510.4	9262.2
	TLSAA2	18548.78	17426.9	13949.9	8802.6
	TRUST	18322.7	17309.18	14011	8867.6

Table 3 :

 3 Average efficiency vs number of blocks (bids drawn from exponential distribution Exp(1/50))

	K	10	5	2	1
	VCG	0.57	0.57	0.39	0.21
	TLSAA	0.62	0.61	0.39	0.2
	TLSAA2	0.61	0.6	0.38	0.21
	TRUST	0.64	0.62	0.37	0.21

Table 4 :

 4 Average fairness vs number of blocks (bids drawn from uniform distribution U(0, 100)

	K	10	5	2	1
	VCG	0.74	0.63	0.38	0.19
	TLSAA	0.73	0.63	0.37	0.19
	TLSAA2	0.708	0.6	0.36	0.18
	TRUST	0.702	0.62	0.38	0.18

Table 5 :

 5 Average fairness vs number of blocks (bids drawn from exponential distribution Exp(1/50))

	K	10	5	2	1
	VCG	1356.6	1285.9	2602	2413.6
	TLSAA	1948.7	2001.1	3013.2	3397.3
	TLSAA2	8061.9	7942.1	8003.7	6093.6
	TRUST	7323.3	7278.4	7520.5	5566.4

Table 6 :

 6 Average revenue vs number of blocks (bids drawn from uniform distribution U(0, 100))

	K	10	5	2	1
	VCG	1061.1	960.4	2045.3	2693
	TLSAA	2082.1	2253.9	2978.8	2570
	TLSAA2	7897.1	8199.7	7664.5	5416.3
	TRUST	6072.8	6464.8	6249.7	4537.4

Table 7 :

 7 Average revenue vs number of blocks (bids drawn from exponential distribution Exp(1/50))

See, e.g., https://www.cept.org/ecc/topics/ lsa-implementation