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!

Designing LSA spectrum auctions: mechanism properties and challenges

Shared Access (LSA) is a complementary solution allowing Mobile Network Operators (MNOs) to access to another incumbent's frequency spectrum after obtaining a proper license from the regulator. This license contains all conditions of sharing, which ensures a certain quality of service for MNOs. In this context, using auctions to allocate those LSA-type licenses is a natural approach toward an efficient use of spectrum. In this paper, we review the existing mechanisms taking into account radio interference, and propose new ones. We also investigate extensions of those mechanisms, when the management of interference among base stations is more subtle than partitioning base stations into groups, and when several base stations are controlled by a common entity. For those extended contexts, we show that we can maximize social welfare and preserve the truthfulness by properly applying Vickrey-Clarke-Grove auction scheme.

INTRODUCTION

Accommodating exploding mobile data traffic is among the great challenges for the fifth generation (5G) networks [1]. Dealing with that traffic indeed requires an optimal utilization of spectrum, but currently some holders of a licensed spectrum (e.g., militaries, satellites, some commercial users) do not always use all their frequencies-usage varies with time and geographical location-, hence there is some room for improvement, which has given rise to the proposal of the concept of dynamic spectrum access (DSA) [START_REF] Amraoui | Accès Dynamique au Spectre dans le Contexte de la Radio Cognitive[END_REF].

DSA refers to the situation in which a primary user, who has an exclusive right to use the band, shares his bandwidth with a secondary user. Secondary users must allow the primary user to use his spectrum without disrupting it. For this, these systems use cognitive radio [START_REF] Amraoui | Accès Dynamique au Spectre dans le Contexte de la Radio Cognitive[END_REF]: secondary users-Mobile Networks Operators (MNOs) in our contextcan intelligently detect communication channels that are in use and those that are not, and move to unused channels. However, for MNOs this approach is risky because neither the access to spectrum nor the quality of service (protection from interference) are guaranteed.

In November 2011, the Radio Spectrum Policy group (RSPG) has proposed a new sharing concept called Licensed Shared Access (LSA) [START_REF]ECC Report 205[END_REF]. That concept involves three stakeholders: the incumbent user, the secondary user which is called LSA licensee, and the regulator [START_REF] Matinmikko | Spectrum sharing using licensed shared access: the concept and its workflow for LTE-advanced networks[END_REF]. Contrary to DSA, under the LSA approach, the secondary user needs to obtain a license from the regulator before accessing the spectrum of the incumbent. The license includes the conditions of sharing, in particular in terms of time, frequency and geographic region. The LSA concept guarantees to the incumbent and the LSA licensee a certain level of QoS specified in the LSA license [START_REF] Matinmikko | Spectrum sharing using licensed shared access: the concept and its workflow for LTE-advanced networks[END_REF].

Deploying an LSA system requires the introduction of two new architectural building blocks [START_REF] Frascolla | Dynamic licensed shared access-a new architecture and spectrum allocation techniques[END_REF], as shown in Fig. 1: the LSA repository and the LSA controller. The LSA repos-Fig. 1: Overview of the LSA concept (taken from [START_REF] Matinmikko | Spectrum sharing using licensed shared access: the concept and its workflow for LTE-advanced networks[END_REF]) itory is a database which contains information about LSA spectrum bands together with their conditions of sharing. It is controlled by the regulator and the incumbent, and is required to deliver the information on spectrum availability based on the incumbent spectrum use and associated conditions for sharing. The LSA controller resides in the network operator's domain and controls the access to the incumbent's spectrum by following the instructions received from the LSA repository. Each MNO has to have his own LSA controller. Several trials of the LSA approach have taken place in Europe [6]-[8], and have shown its applicability. LSA is now under the final stages of standardization and field validation [START_REF] Yrjølå | Licensed shared access evolution enables early access to 5g spectrum and novel use cases[END_REF].

A key objective for LSA is to allocate the spectrum in the most efficient way, i.e., so as to maximize the resulting value to the market. Since the LSA ecosystem involves several actors (incumbent and MNOs) with nonaligned objectives, one needs to define allocation and pricing schemes that are robust to manipulation; hence the focus on auctions for that task [START_REF] Wang | Spectrum Sharing Based on Truthful Auction in Licensed Shared Access Systems[END_REF].

This paper aims at analyzing and comparing auction schemes introduced in the literature ( [START_REF] Wang | Spectrum Sharing Based on Truthful Auction in Licensed Shared Access Systems[END_REF]- [START_REF] Zhou | Trust: A general framework for truthful double spectrum access[END_REF]) for the specific LSA context under different scenarios (as will be detailed in Sections 4 and 5), as well as benefiting from more general results on auctions ( [START_REF] Myerson | Optimal auction design[END_REF], [START_REF] Krishna | Auction Theory[END_REF]) to propose alternative mechanisms. To compare mechanisms, we apply the commonly used efficiency and fairness measures ( [START_REF] Krishna | Auction Theory[END_REF], [START_REF] Jain | A quantitative measure of fairness and discrimination for resource allocation in shared computer systems[END_REF]), in addition to the fulfillment of properties such as incentive compatibility and individual rationality.

The rest of this paper is organized as follows: in Section 2 we define what an auction mechanism is and describe some of its desirable properties, while the system model we consider is introduced in Section 3. Section 4 contains the main contributions of this paper: under the assumptions made in the literature, we review the proposed mechanisms, adapting one to ensure truthfulness. We adapt them to include a per-buyer reserve price set by the auctioneer while maintaining incentive properties, and compare those mechanisms in terms of efficiency, revenue, and fairness. Section 5 investigates the relaxation of some key assumptions in the model: while the mechanisms partition the base stations into separate groups and allocate spectrum among groups, we consider allowing overlapping groups (groups still covering all base stations, but not necessarily in a partition); also, several base station bids being coordinated by a common entity (an MNO) is investigated. Finally, we provide some concluding remarks and suggest some perspective for future work in Section 6.

AUCTION MECHANISMS AND DESIRABLE PROP-

ERTIES

In this section, we provide the definition of an auction mechanism, and of possible properties (goals) that a regulator may want the mechanism to satisfy. Note that each designer of an auction mechanism may be interested in a particular subset of properties.

Auction mechanisms

We consider N strategic agents ("players", or "bidders") wishing to acquire some-possibly divisible-goods.

An auction mechanism takes some bids b = (b 1 , .., b N ) submitted by the players under a predetermined format, and based on those bids, returns:

• an allocation of the good(s) among the bidders,

• a payment vector p = (p 1 , .., p N ), where p i is the (possibly negative) price that player i is charged. In this paper, we limit ourselves to direct auction mechanisms, i.e., mechanisms where the bid format contains all the information to build the bidder's utility function. This is actually without loss of generality, due to the Revelation Principle [START_REF] Myerson | Optimal auction design[END_REF], and for our model will translate into bidders declaring the price they are willing to pay per unit of spectrum.

The objective of each player i is to maximize his own objective function, which we call his utility and denote by u i [START_REF] Osborne | A Course in Game Theory[END_REF]. Since that utility depends on allocations and prices (computed based on bids), it is reasonable to assume that players will try to bid strategically to maximize their utility, hence the need for the mechanism to take that behavior into account.

Desirable properties for an auction scheme

In this paper, we will consider the following properties that a mechanism may satisfy, which are the most used in the literature [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 any multi-constraint problem, it is not possible to jointly satisfy all properties, hence the auction designer has to set a trade-off between them.

Revenue maximization

the revenue of the regulator, Rev, is the sum of payments of all players:

Rev = N i=1 p i .
A mechanism maximizing that metric is desirable from the seller's point of view; such mechanisms are studied in particular in [START_REF] Myerson | Optimal auction design[END_REF].

Efficiency

Social Welfare SW is defined as the sum of the utilities of all stakeholders, i.e., the utilities of all bidders and the utility of the seller, which is given by his revenue. That metric can be interpreted as the overall value of the allocation. A mechanism is said to be efficient if it maximizes social welfare.

Truthfulness

A mechanism is truthful or incentive compatible if and only if for each player i, declaring truthfully one's preferences maximizes one's utility, whatever the other players do.

Individual rationality

That property means that a player has a bidding strategy that ensures him to get a non-negative utility, hence he is always better off participating in the auction than staying out of the mechanism.

Fairness of the allocation

There exist several measures of fairness [START_REF] Maillé | Telecommunication network Economics[END_REF]. In this paper, we will use Jain's index which is given by:

J(α) = ( N i=1 α i ) 2 N N i=1 α 2 i ,
with α i the quantity of good allocated to player i. 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 and equal to 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.

No price discrimination

A pricing scheme that charges buyers different prices for identical good(s) is said to perform price discrimination [START_REF] Carroll | Issues in price discrimination: Reply[END_REF], which may seem unfair from the point of view of buyers and should therefore be avoided.

Truthfulness and minimal price

Truthfulness is very important because it reduces the complexity of the game for players, since the strategies to play are very simple (just declare one's preferences). In particular, that property induces some fairness in participation, in the sense that wealthier players cannot get an edge over competitors by implementing costly measures to optimize their bidding strategy. Also, that property is desirable from the auctioneer point of view: if one objective is efficiency, it is simpler to base the allocation optimization on real utilities rather than unfaithful ones.

Luckily, when bidders' allocation is one-dimensional, that property can be guaranteed in a quite general setting: Myerson indeed showed in a lemma [START_REF] Myerson | Optimal auction design[END_REF] that an allocation rule α i (b 1 , ..., b N ) is implementable (there is a truthful payment rule that can be associated to it) if and only if it is monotone. An allocation rule is monotone if for each player i,

α i (b i , b -i ) is monotone in b i , where b -i = (b 1 , .., b i-1 , b i+1 , .., b N ).
In addition, if we add the constraint that a zero bid implies a zero payment, the payment rule is unique.

Roughgarden details that payment rule in a case that is particularly relevant for us [START_REF] Roughgarden | Myerson's Lemma[END_REF]: given a piecewise constant monotone allocation curve as shown in Fig. 2a, each player i should pay a price as a function of the corresponding breaking points (points at which i's allocation changes) in the range [0, b i ]. Specifically, if there are X breaking points (z j ) then the payment is given by:

p i (b i , b -i ) = X j=1 z j • (jump in α(., b -i ) at z j ) . (1)
This price corresponds to the greyed surface in Fig. 2a (X = 3). In particular, if there is one and only one indivisible item, i.e., the allocation is either 1 or 0 as shown in Fig. 2b then there is one and only one breaking point for each player, that is his minimum bid to win the auction. As an example, in the second-price auction the breaking point for each player is the maximum bid of the other players.

In addition, without losing truthfulness and in order to protect himself from low revenues, the auctioneer may introduce a "reserve price per bidder", imposing in the allocation rule that bids strictly below that price be allocated no resource [START_REF] Chouayakh | Auction mechanisms for Licensed Shared Access: reserve prices and revenue-fairness tradeoffs[END_REF]. By applying Myerson's result above (since the allocation is still monotone), this involves that the perunit revenue from each player is at least that reserve price: any bid strictly below it leading to a null allocation, the breaking point(s) for each winning player must at least equal that reserve price.

SYSTEM MODEL FOR LSA AUCTIONS

In this section, we instanciate the general auction framework to the specific context of LSA auctions. More specifically, we describe our model for bidders (here, operators) preferences, and explain how the interference among coverage areas is managed, through the definition of groups of base stations. We then describe the general working of an LSA auction scheme in that context.

b i α i (b i ) z 1 z 2 z 3 z 4 bi α 1 α 2 α 3 α 4 1 (a) Divisible item 0 1 b i α i (b i ) bi (b) Indivisible item

Preferences of operators

We consider N base stations in competition to obtain spectrum under the LSA scheme. A given quantity of available spectrum is auctioned, which we normalize to 1 w.l.o.g., and which we assume can be arbitrarily split among base stations. We suppose that each base station i = 1, ..., N has a quasi-linear utility function, with a constant marginal valuation v i for spectrum: if it obtains a fraction α i > 0 of the available bandwidth and pays p i , his utility is:

u i (b i , b -i , v i ) = α i (b i , b -i )v i -p i (b i , b -i ).
Otherwise his utility is zero. Notice that we have assumed indistinguishable channel properties [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], i.e., base stations are only sensitive to the amount of bandwidth-and not to the specific bands-they can use.

Under those assumptions, the preferences of base station i are completely characterized by the value v i , hence if each base station is controlled by a different player (operator), a direct auction mechanism would simply ask each one to declare one's v i . The truthfulness property would then translate into players not being able to do better than proposing a bid b i = v i , i.e.,

u i (v i , b -i , v i ) ≥ u i (b i , b -i , v i ) ∀ b -i , b i ,
Also, the social welfare measure SW is given by:

SW = N i=1 (α i v i -p i ) + N i=1 p i = N i=1 α i v i .

Grouping operators before the auction

Two base stations can use the same bandwidth simultaneously if they do not interfere with each other. This can be captured in a model by using an interference graph. Fig. 3 shows an example of an interference graph: base stations are represented by vertices, an edge between two vertices means that those base stations interfere. For example, in Fig. 3 base stations {3,5} can use the same fraction of bandwidth simultaneously. The competition between the N base stations is transformed into a competition between M groups in such a way that two base stations in the same group k (the set of base stations in that group is denoted by g k ) do not interfere, hence the spectrum allocated to a group is used by all the members of the group. The group creation is performed by the auctioneer from the interference graph before the actual auction takes place. An example of group constitution for the interference graph of Fig. 3 is: g 1 = {1, 2, 4, 6} and g 2 = {3, 5}. Another possible configuration is g 1 = {1, 2, 4, 6}, g 2 = {1, 2, 5, 6} and g 3 = {3, 5, 6}.

While the group formation has a non-negligible impact, in this paper (as in [START_REF] Wang | Spectrum Sharing Based on Truthful Auction in Licensed Shared Access Systems[END_REF]- [START_REF] Zhou | Trust: A general framework for truthful double spectrum access[END_REF], [START_REF] Chouayakh | PAM: A Fair and Truthful Mechanism for 5G Dynamic Spectrum Allocation[END_REF] that also relies on groups) we assume that the groups are formed by the auctioneer, and advertised to bidders, before any bids are submitted. We indeed focus here on how to allocate the resource among groups, based on the submitted bids. Fig. 3: Some base stations with their coverage areas (left), the corresponding interference graph (center), and two possible group configurations (right).

Steps of the auction

The main steps of all the auction schemes considered in this paper are the same, and summarized as follows.

1) Group construction: from the interference graph, the regulator constructs groups under the constraint "two base stations in the same group do not interfere with each other"; 2) Bid collection: bidders are asked to declare their valuation; 3) Allocation: each base station is allocated some fraction α i of the available spectrum (specific to the mechanism used); 4) Payment: each player i is charged a price p i (specific to the mechanism).

AUCTIONING FOR LSA SPECTRUM AMONG BASE

STATIONS

Different auction mechanisms have been proposed as candidates in the LSA context. We start by reviewing those in the literature, then we present our recently proposed PAM mechanism [START_REF] Chouayakh | PAM: A Fair and Truthful Mechanism for 5G Dynamic Spectrum Allocation[END_REF], and we propose two new mechanisms derived from LSAA [START_REF] Wang | Spectrum Sharing Based on Truthful Auction in Licensed Shared Access Systems[END_REF], one of the reviewed mechanisms. Note that in this section, we make two key assumptions, initially introduced by the schemes proposed in the literature. Those assumptions are the following: Assumption A. The grouping is made such that each base station belongs to one and only one group.

Assumption B.

Each base station is controlled by a different player, i.e., we assume non-coordination among bids submitted by base stations.

In Section 5, we investigate the consequences of relaxing those assumptions.

State of the art

In the following, we present some auction mechanisms that have been proposed for LSA. In each case the allocation to each group is based on its "groupbid", which is a mechanism-specific quantity. All the notations used throughout the paper are given in Table 1. Note that for all the mechanisms in this subsection, the bandwidth is allocated to one and only one group: for each player i, α i is either 1 (if i is a winning player) or 0.

B k 1 i∈g k ) -n i b i B -i
Tot sum of the total bids of all groups except i's bid.

B -i Tot = ( M k=1 B k ) -n i b i

LSAA

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 groupbid of a group g k is computed as: max i∈g k rank(b i )b i , where rank(b i ) is the rank of player i's bid in the group. The authors define an index j such that:

j = max rank(b l ), l ∈ arg max i∈g k (rank(b i )b i ) . (2)
If g k is the winning group, then only players with rank below or equal to j are winners. Winners pay the second highest groupbid equally.

For TAMES and TRUST, the allocation is based on the bidder with the lowest bid. This can extremely harm the social welfare and the revenue. For LSAA, we have shown in [START_REF] Chouayakh | PAM: A Fair and Truthful Mechanism for 5G Dynamic Spectrum Allocation[END_REF] that this mechanism is not always truthful, we therefore adapt it in two different fashions in the next subsection.

Proposed mechanisms

This subsection introduces several alternative mechanisms that we suggest could be applied to auction LSA spectrum.

VCG

In [START_REF] Chouayakh | Auction mechanisms for Licensed Shared Access: reserve prices and revenue-fairness tradeoffs[END_REF], we propose to adapt the Vickrey-Clarke-Groves (VCG) ([28]- [START_REF] Groves | Incentives in teams[END_REF]) mechanism to the LSA context. The principle of VCG is to allocate resources to maximize the "declared" social welfare (since computed based on submitted bids) and charge each bidder the loss of declared welfare his presence causes to the others. A way to implement VCG would be to compute the groupbid of a group g k as i∈g k b i ; the winning group is then the group with the highest groupbid. If a player belongs to a losing group he pays 0 because whether he is present or not the winning group is the same. If a player belongs to the winning group g win with group bid B win then we can distinguish two cases: if his presence does not change the outcome, i.e., B -i win ≥ B second (with B second the second-highest groupbid) then he pays 0 otherwise he pays B second -B -i win . To summarize:

p V CG i = [B second -B -i win ] + . ( 3
)
That mechanism is known to be efficient, individually rational, and truthful [START_REF] Krishna | Auction Theory[END_REF].

Proportional Allocation Mechanism (PAM)

In [START_REF] Chouayakh | PAM: A Fair and Truthful Mechanism for 5G Dynamic Spectrum Allocation[END_REF] we proposed PAM, which allocates to each group k a fraction α k of the bandwidth in proportion to the bids submitted by players belonging to that group i.e.,

γ k = i∈g k bi BTot .
Each player i pays an amount computed to ensure truthfulness, given by:

p PAM i = b i + B -i g b i + B -i Tot R + B -i Tot -B -i g ln b i + B -i Tot R + B -i Tot + R + B -i Tot b i + B -i Tot -1 , (4)
where R is a reserve price per bidder set by the auctioneer, that ensures that the per-unit price paid by each bidder is at least R.

In [START_REF] Chouayakh | Auction mechanisms for Licensed Shared Access: reserve prices and revenue-fairness tradeoffs[END_REF], we have extended all the aforementioned mechanisms by introducing a reserve price R per bidder; the general method is detailed in Proposition 3.

TLSAA and TLSAA2 (extensions to LSAA)

As pointed out previously, the initial design of LSAA was not truthful. We propose here two variants that are truthful, and that can also be extended by adding a reserve price, when seeking to optimize auctioneer's revenue. 4.2.3.1 TLSAA: we preserve LSAA's method of groupbid computation, but propose a new payment rule which ensures a truthful bidding: since the allocation rule is monotone, we can implement the truthful payment rule given in (1). This gives

p i = min{b i s.t. α i (b i ) = 1}. (5)
We illustrate that rule with an example: suppose we have two groups with bids respectively {20, 10, 9, 6, 3} and {20, 8, 7}. The first group wins the auction since it has the highest groupbid (with value 27). Let us compute the payment of the first player (the one with bid 20): by proposing a bid lower than 5.25 player 1 would be a losing player because the groupbid of his group would then be below the second groupbid 21, and by proposing a bid higher than 5.25 group 1 wins the auction. So Player 1 should pay 5.25. Note that for the second and the third player the same reasoning can be made and each one should pay 5.25, however the fourth player should pay 0 because his group is a winning group whether he is present or not (there is no breakpoint for him).

In LSAA, the revenue is given by the second highest groupbid. A question which may arise regards the revenue of this modified version of LSAA. We show below that truthfulness comes at a cost, since revenue may decrease with respect to the initial version (assuming truthful bidding).

Proposition 1. The revenue of TLSAA cannot be higher than the second-highest groupbid.

Proof. We denote by g w the winning group. Let us define j such that:

j = max {rank(b i ), i ∈ g w and rank(b i )b i ≥ B second } . (6)
Consider a player i in the winning group:

• if rank(b i ) is strictly above j then that player pays 0, because his group always wins whatever his bid (there is no breaking point for him);

• if rank(b i ) is below j then we can distinguish two cases:
1) if his group remains the winning group without i's bid, that player pays 0. 2) if his group is a loosing group if i is not there (winning group only with his presence), his breaking point is exactly B second j .

Hence the maximum revenue is B second j

• j = B second .
One may then wonder whether we can find an allocation rule that ensures the same revenue as TLSAA. To reach that goal, we propose TLSAA2, in which the bidgroup is defined as in LSAA, but we modify the allocation rule and still apply the payment rule ensuring truthful bidding, given in (1). 4.2.3.2 TLSAA2: The proposed rules are as follows.

Allocation: A winning player should not only belong to the winning group but also bid at least as high as player j (see (6)). Payment: Each winning player pays

p i = B second j . (7)
Proposition 2. TLSAA2 is truthful with revenue equal to B second .

Proof. For the revenue, it is clear that it is equal to B second j j = B second . This payment rule ensures a truthful bidding because the allocation rule is monotone (the allocation rule of TLSAA2 is just the allocation rule of TLSAA with constraint given by ( 6)), and the payment rule corresponds to Equation (1). 2. Note that, in order to increase VCG's revenue, authors in [START_REF] Fu | Vcg auctions with reserve prices: Lazy or eager[END_REF] have introduced a reserve price per bidder. In our work in [START_REF] Chouayakh | Auction mechanisms for Licensed Shared Access: reserve prices and revenue-fairness tradeoffs[END_REF], we have extended that approach for other mechanisms. In the following proposition, we generalize [START_REF] Chouayakh | Auction mechanisms for Licensed Shared Access: reserve prices and revenue-fairness tradeoffs[END_REF] for any mechanism with a monotone and all-or-nothingallocation rule. Proposition 3. Consider a mechanism denoted by MEC with a monotone and all-or-nothing-allocation rule (α i is either 0 or 1 for each player i). We denote by p the corresponding truthful payment rule. For any nonnegative value R, the mechanism MEC defined as follows is truthful:

• the allocation rule α is simply the rule α, ignoring all bids strictly below R;

• the payment rule consists in charging player i a price

p i (b i ) := max{R, p R i (b i )}, if α i = 1 0, if α i = 0, (8)
with p R i (b i ) the price given by the original mechanism rule where bids strictly below R are ignored.

Additionally, that modification ensures that the per-unit price paid by players is at least R.

Proof. The allocation rule α is still monotone, therefore there must exist a payment rule p which renders the mechanism truthful.

Let us fix a player i with valuation v i . If v i < R, bidding truthfully ensures a utility equal to 0 otherwise he obtains either a negative utility or a utility equal to 0. We distinguish two cases for a winning player with v i > R:

• p R i (v i ) ≥ R:
this situation corresponds to the original mechanism facing only bidders with valuations above R, hence proposing a bid b i = v i maximizes his utility.

• 0 ≤ p R i (v i ) < R:
bidding truthfully generates a utility v i -R, any other bid b i leads to a lower utility since the bidder would either get no resource (hence utility 0), or still be a winner and pay at least R.

For a losing player, the outcome corresponds to the original mechanism MEC (now facing only bidders with valuations above R). Since MEC is truthful, and MEC' only has larger payments than MEC, bidding truthfully-and losingremains a best strategy.

Hence, we can introduce to TLSAA and TLSAA2 a reserve price per bidder and the payment rule for each mechanism is given by (8).

Performance evaluation

This section compares the performance of the previous mechanisms. The performance evaluation is based on simulations. We are particularly interested in average social welfare and fairness metrics, as well as in the average revenue of the auctioneer.

Simulation settings

For those simulations, we have fixed two groups from the interference graph of Fig. 3: g 1 = {1, 2, 4, 6} and g 2 = {3, 5}. The marginal valuations of base stations are drawn from the uniform distribution over the interval [0,100]. For each extended mechanism and for each reserve price R, we have computed the average (with respect to each metric) over 10.000 draws.

Results

The objectives of those simulations is to help the regulator to choose a particular mechanism given a fixed configuration of groups: simulation results (Fig. 4) show that PAM outperforms the other schemes in terms of fairness. In terms of revenue, Fig. 5 shows that TRUST could offer the highest revenue by playing on the reserve price. In terms of social welfare, VCG is efficient by construction. Note that the regulator could trade-off the allocation fairness, the auction In TLSAA2, TAMES and TRUST each winning player pays the same amount so there is no price discrimination, however for the other mechanisms we do not have any guarantees.

EXTENSIONS WHEN RELAXING ASSUMPTIONS

In this section, we consider relaxing the key assumptions made previously.

In Subsection 5.1, we relax Assumption A, by treating the case when the base station (BS) grouping allows a base station to belong to several groups, which should improve the social welfare of the allocation but complicates the mechanism analysis (ensuring truthfulness becomes harder).

Then in Subsection 5.2, we assume that several base stations can be controlled by a common entity (an MNO), thereby relaxing Assumption B. Again, one has to be careful to maintain the schemes' properties.

A player is a base station which can belong to more than one group

The assumption of allowing each BS to be a member of only one group may appear to be restrictive because by removing this assumption, i.e. allowing a base station to belong to more than one group, we increase social welfare: suppose that there is a base station which is not causing interference to any other base station, clearly this base station should belong to all groups. In the following, we investigate the truthfulness of the previous mechanisms when removing this restriction, by addressing the following question: given the allocation rule and the hypothesis that a player (BS) can belong to more than one group, is there a payment rule such that those mechanisms are still truthful? We add a star to the original mechanism to denote the new version. Note that the difference between Mechanism and Mechanism* (if it exists) resides only in the payment rule.

Candidate mechanisms are not all adaptable

We show in the following that we can adapt all previous mechanisms except TAMES and TLSAA2. Before that, let us introduce the following proposition.

Proposition 4. Given a monotone allocation rule, if a player belongs to all groups then he pays 0.

Proof. Direct application of Myerson's lemma (there is no breaking point for this player because he is always a winning player).

•

TAMES:

Under TAMES, all players of the group with the highest groupbid are winners except the player with the lowest bid. With the assumption that a player can belong to more than one group, the allocation rule is non-monotone. Indeed, consider a player with valuation equal to 15, belonging to two groups with bids respectively {15, 20, 25} and {8,9,15, 20}. Bidding truthfully leads to a utility equal to 0 because he is a loosing player. However, any bid lower than 12 leads to a higher utility because in that situation this player is a winning player. Since the allocation rule is not monotone anymore, we cannot find a truthful payment rule.

• TRUST* Under TRUST* all players of the group with the highest group bid are winners. Clearly, the allocation rule is monotone. Thus we can find a truthful payment rule. The breakpoint for player i is given by the minimum bid that allows i to win the auction: for each group k which i belongs to, we compute the minimum bid, if it exists, which allows him to win the auction.

Example: consider four groups with bids respectively {2, 3, 4, 8},{0.5, 8} {5, 3, 8} and {4}. The payment of player i with valuation 8 in bold is min{1, 4 3 } = 1. Indeed, by proposing a bid b i = 1, the first group wins the auction. For the second group, player i cannot change the outcome (there is no breaking point), for the third group, the breaking point is given by b i = 4 3 . Thus the payment of player i is min{1, 4 3 } = 1.

•

VCG*:

We propose to adapt VCG in this context. The winning group is the group with the highest groupbid. We denote by B -i max the highest groupbid of groups to which i does not belong. If the player belongs to the winning group g win with groupbid B win then we can distinguish two cases: if i's presence does not change the outcome i.e., B -i win ≥ B -i max then he pays 0 otherwise he pays B -i max -B -i win . To summarize:

p V CG * i = [B -i max -B -i win ] + . (9)
• PAM*: we denote by n i the number of groups which i belongs to. The initial version of PAM in [START_REF] Chouayakh | PAM: A Fair and Truthful Mechanism for 5G Dynamic Spectrum Allocation[END_REF] was actually designed under this assumption. The payment rule is given by:

p i = n i b i + B -i g n i b i + B -i Tot R + B -i Tot -B -i g n i ln n i b i + B -i Tot n i R + B -i Tot + n i R + B -i Tot n i b i + B -i Tot -1 . (10)
• TLSAA*: Under TLSAA* all players of the group with the highest group bid are winners. Clearly, the allocation rule is monotone. Thus we can find a truthful payment rule. The breakpoint for player i is given by the minimum bid that allows i to win the auction: for each group k which i belongs to, we compute the minimum bid, if it exists, which allows him to win the auction.

• TLSAA2:

We cannot find a truthful payment rule since the allocation rule is non-monotone, which can be seen on the following example, with two groups with bids respectively {15, 5, 3} and {7, 5, 4}. Clearly the player with the bid in bold ( 5) is a losing player (the first group wins the auction and only the first player is a winning player and he pays 12). However, if player i proposed b i = 2.5 instead of 5 then he would be a winning player because in this situation all players of the first group would be winners and pay 2.

In the following we evaluate the impact of Assumption A. we compare Mech and Mech* (without considering TAMES and TLSAA2 since as we have shown they can not be extended) preserving truthfulness.

Performance Evaluation

We have done the following simulations: we have fixed two possible group configurations from the interference graph of Fig. 3: In the first configuration C 1 , we have two groups g 1 = {1, 2, 4, 6} and g 2 = {3, 5}. For the second configuration C 2 we have three groups g 1 = {1, 2, 4, 6}, g 2 = {1, 2, 5} and g 3 = {3, 5, 6}. The marginal valuations of base stations are drawn from the uniform distribution over the interval [0,100]. For each mechanism and for each reserve price R, we have computed the average (with respect to each metric) over 10000 draws. Results are shown on Fig. 7 to [START_REF] Wang | Spectrum Sharing Based on Truthful Auction in Licensed Shared Access Systems[END_REF] The objective of those simulations is to help the regulator to choose group configurations: if his objective is to maximize his revenue, then C 1 is better than C 2 in terms of revenue. In the other hand, if his objectives are to maximize social welfare and the fairness of the allocation then by choosing C 2 , he can get a higher social welfare and improve fairness.

Base stations' bids coordinated by a single entity (operator)

In this section, we define a player as an operator who coordinates several base stations and we investigate the applicability (truthfulness) of the previous mechanisms.

Assumption

In the literature and in our previous work, we define a player as a base station. In this section, we redefine a player as an operator who coordinates several base stations. We suppose that each base station can belong to only one group and the utility U I of an operator I which has N I base stations is:

U I = N I i=1 α i v i -p I ,
where α i is the fraction of spectrum allocated to base station i of operator I and v i its valuation. Note that we will not change the system model, i.e. the regulator collects a bid from each base station. The question which may arise is: under the new definition of a player, do the previous mechanisms preserve truthfulness?

In this new definition of players, truthfulness means that for each operator I who has N I base stations, proposing a bid vector equal to the valuation vector, i.e., proposing (b 1 , .., b N I ) = (v 1 , .., v N I ) maximizes his utility.

Before discussing the applicability of the previous mechanisms in this context let us introduce the following proposition (note that this holds only when a player is an operator). Proposition 5. If a mechanism is truthful with the additional constraint that a base station must belong to one and only one group then, given the allocation rule, there also exists a truthful payment rule without that constraint i.e., each base station can belong to more than one group.

Proof. Let us fix an operator I with N I base stations with a vector of valuations V I = (v 1 , .., v N I ) under the assumption that a base station can belong to more than one group. The utility of the operator is given by

U I = N I i=1 α i (B I )v i -P I (B I )
where B I = (b 1 , .., b N I ) is the bid vector. Our objective is to find P I (B I ) which elicits truth telling. If we consider each base station i which belongs to n i groups as n i different base stations with the same bid and the same valuation as base station i then we obtain the same allocation for groups (in total we have N * I = N I i n i base stations). We denote by B * I and V * I the bid and valuation vectors of those N * I base stations. We have:

N I i=1 α i (B I )v i = N * I i=1 α i (B * I )v i (11)
By assumption, we can find the payment rule P * I which ensures truthful bidding (B * I = V * I ). Then, by construction P I (B I ) = P * I (B * I ) must ensure a truth telling. Indeed:

U I = N I i=1 α i (B I )v i -P * I (B * I ) = N I * i=1 α i (B * I )v i -P * I (B * I )
meaning that U i is maximized for B * I = V * I , by setting B I = V I we obtain that maximum utility.

Most candidate mechanisms are not truthful

In the following proposition, we show that all the previous mechanisms, except VCG, could not applied. Proposition 6. For all the previous mechanisms except VCG, there is no payment rule ensuring truthful bidding.

Proof. We show the non-existence for each of the other schemes.

• TRUST: consider two groups, and suppose that operator I has two base stations with valuations in bold and which are in two groups with valuations respectively {30, 3} and {5, 4}. By bidding truthfully the second group wins the auction so the utility of the operator I is 5 -p I , however if that operator proposes a bid vector {30,0} then we are back to the situation where a base station is a player (since each operator has one and only one base station): group one wins the auction and in this situation the utility of the operator i is 30-2 = 28 which is strictly better than the previous one.

• PAM: consider an operator I with two base stations in two different groups. The first group is composed by two base stations of different operators and the second contains only one base station. We denote by v I,1 the valuation of the first base station and by v I,2 the valuation of the second. Suppose that v I,1 > v I,2 and the reserve price per bidder is zero. The utility of the operator is given by:

U I = α 1 v I,1 + (1 -α 1 )v I,2 -p I . (12)
But proposing any bid b I = (b I,1 , 0) ensures a maximum utility which is equal to v I,1 because in this situation, a player is a base station and we have only one group thus the payment is zero (see [START_REF] Chouayakh | PAM: A Fair and Truthful Mechanism for 5G Dynamic Spectrum Allocation[END_REF]).

• TLSAA: we consider two groups with bids respectively {16, 20} and {15, 30}. By bidding truthfully, operator I gets a utility lower than 16. However, if he reports only his bid for the second base station then he obtains a utility 30 -10 = 20.

As illustrated in Table 3, when an operator is considered as a player, only VCG can be applied.

A truthful mechanism

We apply the VCG mechanism in our context and under the assumption that a player is an operator, we denote by VCG** the implementation of VCG in this context. The bandwith is allocated to the group with the highest groupbid. The payment of a player I is given by

SW -I -(SW I - N I i=1 b i α i ),
where SW -I is the social welfare when operator I is absent, SW I is the social welfare when the operator I is present.

Example: Consider two groups with bids respectively {5, 30} and {12, 8, 25}. The payment of operator I (which has base stations with bold-written bids) is:

30 -(45 -(12 + 8)) = 5
As we have shown before, VCG can be applied when an operator is considered as a player. In the following we focus on the revenue. In particular we analyse two different ways of implementing a reserve price in this particular scenario. 5.2.3.1 Revenue investigation for VCG**: VCG** can yield very small revenue, even no revenue in some situations. To avoid this situation, we have introduced in a previous work [START_REF] Chouayakh | Auction mechanisms for Licensed Shared Access: reserve prices and revenue-fairness tradeoffs[END_REF] a reserve price per base station: each base station has to bid above that reserve price and will pay at least that amount if he is a winning player. In this section we investigate the applicability of what we have proposed before i.e., do we preserve the truthfulness when applying a reserve price per base station, when several base stations are assumed to be coordinated by a single entity (operator)?

In our context, applying an homogeneous reserve price R per base station could consist, as before, in ignoring bid below R, and having each winning base station pay at least R. In other words, each operator would pay at least α i R}. However, this leads to loosing truthfulness, as exemplified here: consider two groups and two operators, the first group with a base station of the first operator and the second group with two base stations of the second operator. Suppose that the valuations of base stations are {7} and {6, 3}. If the reserve price is 4, then by bidding truthfully, the second operator looses the auction (since his second base station will be excluded as the groupbid of the second group is 6 < 7). However by proposing a bid vector {6, 5}, he would win the auction and get a utility 9 -max{7, 8} = 1.

Another alternative to adapt a reserve price could be to apply a reserve price R * per operator, i.e., if an operator is a winning player then he should pay at least that amount. The final payment therefore [START_REF] Fu | Vcg auctions with reserve prices: Lazy or eager[END_REF] is max{R * , p VCG * * I }.

Since each operator may have only a set of winning base stations (base stations of the winning group), a question that may arise is how to apply that reserve price. A natural approach can be to apply a reserve price per group: if an operator has some base stations in a group then the sum of bids of those base stations must be greater than R * . Unfortunately this also leads to loose the truthfulness: consider an operator with two base stations with valuations {4,7} on two groups: {8, 4} and {3, 7}. Suppose R * = 3, then by bidding truthfully the utility of the operator is 4 -max{3, 0} = 1. However if he proposes (0,7) then its utility is 7 -max{3, 5} = 2.

Both our attempts to improve the revenue using reserve prices (per base station, or per operator) lead to losing truthfulness, hence we do not recommend using the associated methods. Finding other ways to introduce reserve prices while maintaining truthfulness, when a player controls several base stations, is an interesting direction for future works.

CONCLUSION

In this paper, we have designed new truthful auction mechanisms aimed at allocating spectrum in the context of LSA. Those mechanisms have different properties so the regulator can choose one with respect to his preferences. We have also studied the impact of the hypothesis "each base station must belong to one and only one group" on truthfulness and we have extended previous studied mechanisms to this scenario by finding the corresponding payment rule (if it exists) eliciting truthful bidding. We have also defined a player as an operator who coordinates several base stations, and shown that under this assumption, only VCG can be applied and elicit truthful bidding.

In this paper we have focused on sealed auctions i.e., all bidders simultaneously submit sealed bids. In future works, we will focus on ascendant open auctions and we will study the case in which the regulator has more than one block to allocate which complicates the auction analysis.

Fig. 2 :

 2 Fig.2: Some piecewise constant monotone allocation curves (solid curves). The grey area represents the price paid when the bid b i has value bi .

R

  minimum per bidder price set by the auctioneer M number of groups N number of base stations v i true valuation of base station i per bandwidth unit b i bid of base station i b -i bids of all base stations except i g k group k (a set of base station indices) α i fraction of spectrum allocated to a base station i B k sum of bids of g k B k = i∈g k b i B Tot sum of the total bids of all groups, of groups which i belongs to except i's bid, B -i g = ( M k=1

Fig. 4 :Fig. 5 :

 45 Fig. 4: Average fairness as a function of the reserve price R

Fig. 6 :

 6 Fig. 6: Average social welfare as a function of the reserve price R

Fig. 7 :Fig. 8 :

 78 Fig. 7: Average revenue (left), fairness (center) and social welfare as a function of the reserve price.

Fig. 9 :Fig. 10 :

 910 Fig. 9: Average revenue (left), fairness (center) and social welfare (right) as a function of the reserve price.

α

  i R. A possible way to adapt the same idea to this scenario is to modify the final payment of each operator as max{p VCG * * I ,

TABLE 1 :

 1 All players of the highest-groupbid group are winners, except the one with the lowest bid of that group. Each winning player pays the same price, that is the lowest bid in their group.

	4.1.2 TRUST
	TRUST [12] works quite similarly to TAMES. It computes
	the groupbid as: |g

notations 4.1.1 TAMES TAMES

[START_REF] Chen | Tames: A truthful auction mechanism for heterogeneous spectrum allocation[END_REF]

computes the groupbid of each group k as

(|g k |-1) min i∈g k b i , where |g k | is the cardinal of group k. k | min i∈g k b i .

All players of the group with the highest groupbid are winners. Winners pay equitably the second-highest groupbid (each winner pays a proportion 1/|g k | of it).

TABLE 2 :

 2 Illustration of truthful mechanismsAll candidate mechanisms are summarized in Table

TABLE 3 :

 3 Candidate truthful mechanisms depending on the assumptions made.

	Scenario	Candidate truthful mecha-
		nisms
	A player is a base station, that	TAMES, TRUST, TLSAA,
	belongs to one and only one group	TLSAA2, VCG, PAM
	(Assumptions A and B)
	A player is a base station which	TRUST*, TLSAA*, VCG*,
	can belong to more than one group	PAM
	(Assumption B)
	A player is an operator that coor-	VCG**
	dinates several base stations