Francesca Fossati
email: francesca.fossati@sorbonne-universite.fr

Member, IEEE Sahar Hoteit
email: sahar.hoteit@u-psud.fr

Stefano Moretti
email: stefano.moretti@lamsade.dauphine.fr.

Senior, IEEE Stefano Secci
email: seccis@cnam.fr

Fair Resource Allocation in Systems with Complete Information Sharing

Keywords:

In networking and computing, resource allocation is typically addressed using classical resource allocation protocols as the proportional rule, the max-min fair allocation, or solutions inspired by cooperative game theory. In this paper, we argue that, under awareness about the available resource and other users demands, a cooperative setting has to be considered in order to revisit and adapt the concept of fairness. Such a complete information sharing setting is expected to happen in 5G environments, where resource sharing among tenants (slices) needs to be made acceptable by users and applications, which therefore need to be better informed about the system status via ad-hoc (northbound) interfaces than in legacy environments. We identify in the individual satisfaction rate the key aspect of the challenge of defining a new notion of fairness in systems with complete information sharing and, consequently, a more appropriate resource allocation algorithm. We generalize the concept of user satisfaction considering the set of admissible solutions for bankruptcy games and we adapt to it the fairness indices. Accordingly, we propose a new allocation rule we call Mood Value: for each user, it equalizes our novel game-theoretic definition of user satisfaction with respect to a distribution of the resource. We test the mood value and a new fairness index through extensive simulations about the cellular frequency scheduling use-case, showing how they better support the fairness analysis. We complete the paper with further analysis on the behavior of the mood value in the presence of multiple competing providers and with cheating users.

I. INTRODUCTION

In communication networks and computing systems, resource allocation (in some contexts also referred to as resource scheduling, pooling, or sharing) is a phase, in a network protocol or system management stack, when a group of individual users or clients have to receive a portion of the resource in order to provide a service. Resource allocation becomes a challenging problem when the available resource is limited and not enough to fully satisfy users' demand. In such situations, resource allocation algorithms need to ensure a form of fairness. Such situations emerge in a variety of contexts, such as wireless access [START_REF] Saad | Coalitional games for distributed collaborative spectrum sensing in cognitive radio networks[END_REF], [START_REF] Ghimire | Revisiting scheduling in heterogeneous networks when the backhaul is limited[END_REF], competitive routing [START_REF] Orda | Competitive routing in multiuser communication networks[END_REF], traffic transport control [START_REF] Sy. Yun | Distributed Proportional Fair Load Balancing in Heterogenous Systems[END_REF].

The common methodology adopted in the literature is to determine, on the one hand, the allocation rules that satisfy desirable properties [START_REF] Thomson | Axiomatic and game-theoretic analysis of bankruptcy and taxation problems: an update[END_REF], and to analyze, on the other hand, Fig. 1: A representation of strategic network setting without and with complete information sharing. The amount c i is the resource demand of user i ∈ {1, 2, 3}; E is the amount of shared resource available. the fairness of a given allocation through indices, the most commonly used being the Jain's index [START_REF] Jain | A quantitative measure of fairness and discrimination for resource allocation in shared computer system[END_REF]. Allocation rules and indices of fairness are commonly justified by some fairness criteria. For instance, among two equivalent users demanding the same amount of resource, it makes sense not to discriminate and to give to each of them the same portion of the resource. In some cases, it can be desirable to guarantee at least a minimum amount of the resource so that the maximum number of users can be served.

In the networking literature, the resource allocation problem is historically solved as a single-decision maker problem in which users are possibly not aware of the other users' demands and of the total amount of available resource. It follows that the most natural and intuitive way to quantify the user satisfaction is through the proportion of the demand that is satisfied by an allocation. Large literature exists indeed in the networking area on proportional resource allocations for many practical situations, from wireless networks to transport connection management [START_REF] Ghimire | Revisiting scheduling in heterogeneous networks when the backhaul is limited[END_REF], [START_REF] Orda | Competitive routing in multiuser communication networks[END_REF], [START_REF] Sy. Yun | Distributed Proportional Fair Load Balancing in Heterogenous Systems[END_REF].

Instead, in this paper, we are particularly interested in novel networking contexts such that users can be aware of other users' demands and the available amount, as depicted in Fig. 1: in legacy resource allocation models, users' interaction with the system only implies issuing a resource request and receiving a resource allocation, therefore with an assessment of user's satisfaction only based on this information; in systems with demand and available amount awareness, users are made more conscious about the system setting with a signaling channel from the system to the users providing information about resource availability and other users' demands. As such, rational users shall compute their satisfaction also based on the presence of other users and the system resource availability.

In fact, such networking contexts with demand and resource availability awareness are making surface in wired and wireless network environments with an increasing level of programmability, i.e., using software-defined radio and virtualized network platforms on top of a shared infrastructure, as predicated with 5G. Sharing an infrastructure logically implies regular and possibly real-time auditability of the system, to ensure that various tenants esteem they are fairly treated by the infrastructure provider [START_REF] Zhu | Virtualization of 5G cellular networks as a hierarchical combinatorial auction[END_REF]. In fact, users in such scenarios can be prone to change providers if their satisfaction can improve with another provider. In existing SND/NFV systems, using north-bound Application Programming Interfaces (API) tenant applications and policy manager applications can already gather resource information and share data stores with each-other. Besides forthcoming 5G systems, methods allowing raising end-user awareness exist in current systems such as those supporting spectrum sharing; for such systems, a large number of auctions mechanisms are proposed in the literature [START_REF] Zhu | Virtualization of 5G cellular networks as a hierarchical combinatorial auction[END_REF], [START_REF] Huang | Auction-Based Spectrum Sharing[END_REF], [START_REF] Zhou | TRUST: A general framework for truthful double spectrum auctions[END_REF], assuming either a signaling channel or a sensing solution allowing demand (bid) and available resource awareness.

Our main motivation is reasoning toward a new notion of user satisfaction for such resource allocation situations with demand and resource awareness. Let us briefly clarify our motivation with a basic allocation example. A user i asks a quantity of resource that is bigger than the resource itself (as B in Fig. 1). Classical fairness indices [START_REF] Jain | A quantitative measure of fairness and discrimination for resource allocation in shared computer system[END_REF], [START_REF] Ab | On the measurement of inequality[END_REF], [START_REF] Mo | Fair end-to-end window-based congestion control[END_REF] tend to qualify the user satisfaction as maximum when i obtains exactly what it asks. In the case where i asks more than the available amount, it cannot reach the maximum satisfaction due to the fact that its demand exceeds the available resource. Instead, under complete information sharing, it would be more reasonable that its satisfaction is maximum when it obtains all the available resource. Furthermore, if all the other users together ask a quantity of good inferior to the resource, a minimum portion of it, equal to the difference between the resource and the sum of the demands of all the others, is guaranteed to i. Under a dual reasoning, it also appears more acceptable that the minimum satisfaction of a user is reached when it receives the minimum portion of the available resource, instead of when it receives zero. If users are in complete information context the classical approach can lead to unreasonable outcomes.

In this perspective, in order to better describe the user satisfaction as a function of the available resource, and to capture the interactions due to the networking context (e.g., networked users may be aware of respective demands, may ally in the formulation of their demands, etc.), we propose to model the resource allocation problem as a cooperative game. Accordingly, we define a new satisfaction rate for users, able to adapt to various configurations of the demands. Furthermore, we define a new resource allocation rule, called the 'Mood Value', based on the idea that the fairest allocation is the one that equalizes the satisfaction of each player. Indeed, regardless of the level of satisfaction, each player is not discriminated if its satisfaction is equal to that of other players. Choosing this allocation, users, who have the chance to recover information about the other users and the available resource, have the feeling to receive a fair portion of the resource. We also provide an interpretation of this approach positioning it with respect to classical traffic theory [START_REF] Fp | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF].

The paper is organized as follows. Section II presents the state of the art. In Section III a new satisfaction rate is proposed. In Section IV the mood value and new fairness indices are described. In Section V we provide an interpretation of the mood value with respect to conventional traffic theory. Section VI presents some numerical examples. Section VII further investigates dynamics in multi-provider situations. Finally, in Section VIII we analyze the cases where users can cheat. Section IX concludes the paper.

II. BACKGROUND

A resource allocation problem can be characterized by a pair (c, E), in which c is the vector of demands (claims) from n users (claimants) and E is the resource (estate) that should be shared between them. The set of users is N ={1, ..., n}. The resource allocation is a challenging problem when E is not enough to satisfy all the demands (

n i=1 c i ≥ E). An allocation
x ∈ R n is a solution vector that satisfies three basic properties:

• Non-negativity: each user should receive at least zero.

• Demands boundedness: each user cannot receive more than its demand. • Efficiency: the sum of all allocations should be E. An allocation rule is a function that associates a unique allocation vector x to each (c, E).

A. Classical resource allocation rules

Many resource allocation rules are proposed in the literature and each of them is characterized by a set of properties that justify the use of the given rule in order to find a solution of the allocation problem [START_REF] Thomson | Axiomatic and game-theoretic analysis of bankruptcy and taxation problems: an update[END_REF]. In computer networks, the most well-known rules are: the proportional rule and the weighted proportional rule [START_REF] Fp | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF], the max-min fair allocation (MMF) [START_REF] Dp | Data networks[END_REF], [START_REF] Ogryczak | Fair optimization and networks: A survey[END_REF] , and the α-fair allocation [START_REF] Mo | Fair end-to-end window-based congestion control[END_REF]. Each of these allocation rules, result of an optimization problem and/or an iterative algorithm, follows a fairness criterion.

The weighted proportional allocation rule is based on the idea that a logarithmic utility function captures well the individual evaluation of the worth of the resource [START_REF] Fp | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF]. One way to compute it is via the maximization of n i=1 w i log x i subject to demand boundness and efficiency constraints. When w i is equal to 1 the resulting allocation is called simply proportional and when w i is equal to c i we obtain the allocation that actually produces allocations proportional to the demands; hence in the following, we refer to the latter rule as 'proportional' instead of the previous one with w i equal to 1.

The max-min fairness (MMF) allocation rule is the only feasible allocation such that, if the allocation of some users is increased, the allocation of some other users with smaller or equal amount is decreased [START_REF] Dp | Data networks[END_REF], [START_REF] Ogryczak | Fair optimization and networks: A survey[END_REF]. If we order the claimants according to their increasing demand, i.e., c 1 ≤ c 2 ≤ • • • ≤ c n , then MMF allocation for user i is given by:

M M F i ( c, E) = min c i , E - i-1 j=1 M M F j ( c, E) n -i + 1 .
Intuitively, MMF gives the lowest claimant (assuming min i c i ≤ E n ) its total demand and evenly distributes unused resources to the others. More generally, it is possible to obtain a family of allocation rules maximizing a parametric utility function. The α-fair utility function is defined as [START_REF] Mo | Fair end-to-end window-based congestion control[END_REF]. If α → 1 the solution of the optimization problem coincides with the weighted proportional allocation with w i equal to 1, if α = 2 with the minimum delay potential allocation, that is the allocation obtained minimizing the total potential delay n i=1

n i=1 x (1-α) i 1-α
( 1 xi ) [START_REF] Massoulié | Bandwidth sharing: objectives and algorithms[END_REF], and if α → ∞ with the max-min fair allocation.

The common point about classical resource allocation rule is that a single decision-maker, typically the network operator, takes a decision taking into consideration all users' demand and available resource, but users are not made aware of other users' resource and/or the available resource, and hence they measure their satisfaction based only on their demand and the received allocation by the decision-maker.

The evaluation of the fairness of the allocations, used as an important system performance metric especially in networking, can be useful to discriminate among allocation rules and to evaluate the level of 'justice' in the resource sharing. The axiomatic theory of fairness proposed in [START_REF] Lan | An axiomatic theory of fairness in network resource allocation[END_REF] shows that it exists a unique family of fairness measures, satisfying a set of reasonable axioms, which includes well-known measures as the Jain's index, the Atkinson's index, the maximum or minimum ratio and the α-fair utility. More details on general measures of fairness are in Appendix A.

B. Allocation rules with complete information sharing

Among the various techniques adopted when addressing resource allocation with complete information sharing, we can identify cooperative game theoretical approaches and auctionbased approaches.

Game theory has been largely applied to communication systems in order to model network interactions. In resource allocation, for example, in [START_REF] Rj | A game-theoretic look at the Gaussian multiaccess channel[END_REF] a cooperative game model is proposed to select a fair allocation of the transmission rate in multiple access channels and in [START_REF] Mathur | Coalitions in cooperative wireless networks[END_REF] the authors studied, using coalitional game theory, the cooperation between rational users in wireless networks. Generally, a conventional game theoretical model works under hypothesis of complete information, i.e., decision-makers (e.g., users) are aware of others' utility functions as a function of their strategies. This stands for non-cooperative approaches, which can however be simply dependent on own utility function when seeking simple best-reply behaviors. This stands as well as for cooperative game approaches, where the value of subcoalitions is supposed to be a shared information.

Auction models for divisible goods exist as well [Wang, Zender, 2002]; except sealed-bid auctions, in other auction models bidders are made explicitly or implicitly aware of other users' bids [START_REF] Zhu | Virtualization of 5G cellular networks as a hierarchical combinatorial auction[END_REF], [START_REF] Huang | Auction-Based Spectrum Sharing[END_REF], [START_REF] Zhou | TRUST: A general framework for truthful double spectrum auctions[END_REF], and the outcome of an auction can be driven toward resource sharing [START_REF] Lazar | Auctions for network resource sharing[END_REF], hence going beyond simple good bidding. Recent studies, namely [START_REF] Zhu | Virtualization of 5G cellular networks as a hierarchical combinatorial auction[END_REF], propose the adoption of hierarchical auctions for virtualized network resource allocation. A major impediment of auction-based frameworks is that signaling is needed between users and system, which implies a certain latency in the decision making, which could not be acceptable for real-time allocation such as spectrum or computing resource scheduling.

On the other hand, adopting a cooperative game approach, a resource allocation situation with complete information sharing can be modeled and solved at a single decision-making point, while taking into consideration users' perspective and the fact that users are aware of all the problem inputs. A resource allocation problem can be defined as a Transferable Utility (TU) game [START_REF] Owen | Game Theory[END_REF], [START_REF] Mc | Bankruptcy-based radio resource management for multimedia mobile networks[END_REF], [START_REF] Hoteit | A nucleolus-based approach for resource allocation in OFDMA wireless mesh networks[END_REF], [START_REF] Hoteit | On fair network cache allocation to content providers[END_REF]. The game is a pair (N, v) where N ={1, . . . , n} denotes the set of players and v : 2 N → R is the characteristic function, (by convention, v(∅)=0). Bankruptcy games [START_REF] Thomson | Axiomatic and game-theoretic analysis of bankruptcy and taxation problems: an update[END_REF], in particular, deal with situations where the number of claimed resource exceeds that available. A Bankruptcy game is a TU-game (N, v) in which the value of each coalition S of players is given by:

v(S) = max{E - i∈N \S c i , 0}
where E ≥ 0 represents the estate to be divided and c ∈ R N + is a vector of claims satisfying the condition i∈N c i > E [START_REF] Owen | Game Theory[END_REF], [START_REF] Rj. Aumann | Game theoretic analysis of a bankruptcy problem from the Talmud[END_REF]. The bankruptcy game is superadditive, that is:

v(S ∪ T ) ≥ v(S) + v(T ), ∀S, T ⊆ N |S ∩ T = ∅
it is also supermodular (or, equivalently, convex), that is:

v(S ∪ T ) + v(S ∩ T ) ≥ v(S) + v(T ) ∀S, T ⊆ N
A classical set-value solution for a TU-game is the core C(v), which is defined as the set of allocation vectors x ∈ R N for which no coalition has an incentive to leave the grand coalition N , that is the one formed by all the players, i.e.:

C(v) = {x ∈ R N : i∈N x i = v(N ), i∈S x i ≥ v(S) ∀S ⊂ N }.
A one-point solution (or simply a solution) for a class C N of TU games with N as set of players is a function ψ : C N → R N that assigns a payoff vector ψ(v) ∈ R N to every TU game in the class. A well-known solution for TU-games is the Shapley value [START_REF] Ls | A value for n-person games[END_REF] φ(v) of a game (N, v), defined as the weighted mean of the players' marginal contributions over all possible coalitions and computed as follows:

φ i (v) = S⊆N :i∈S w i (S)(v(S) -v(S \ {i})), with w i (S) = (s-1)!(n-s)! n!
where s denotes the cardinality of S ⊆ N . Another well studied solution for TU-games is the nucleolus, based on the idea of minimizing the maximum discontent [START_REF] Schmeidler | The nucleolus of a characteristic function game[END_REF]. Given a TU-game (N, v) and an allocation x ∈ R N , let e(S, x)= v(S)-i∈S x i be the excess of coalition S over the allocation x, and let ≤ L be the lexicographic order on R. Given an imputation x, θ(x) is the vector that arranges in decreasing order the excess of the 2 n -1 non-empty coalitions over the imputation x. The nucleolus ν(v) is defined as the imputation x (i.e., i∈N x i =v(N ) and x i ≥ v({i}) for each i ∈ N ) such that θ(x) ≤ L θ(y) for all y imputations of the game v. As compromise between the utopia and the disagreement points, a third important solution for quasibalanced games is the tau-value. It is defined by

τ (v) = αm(v) + (1 -α)M (v) (1)
where α ∈ [0, 1] is uniquely determined so that the solution is efficient, M (v) is the utopia payoff, and m(v) is the minimum right payoff 1 . Given a bankruptcy game, many other solutions can be proposed [START_REF] Thomson | Axiomatic and game-theoretic analysis of bankruptcy and taxation problems: an update[END_REF]. As already introduced in the previous section, the proportional allocation assigns to player i an allocation

equal to E • c i / n i=1 c i . The Constrained Equal Loss (CEL)
allocation divides equally the difference between the sum of the demands and E, under the constraint that no player receives a negative amount. The CEA allocation gives equal awards to all agents subject to no one receiving more than its claim and it coincides with the MMF allocation rule.

The following example shows some of the most important allocation rules and fairness indices. We describe classical methods to evaluate the satisfaction of a user for an allocation, and propose a new definition of user satisfaction for scenarios with complete information sharing.

A. User satisfaction rate

A crucial issue in resource allocation is to jointly:

• find the best solution in terms of a certain goal;

• evaluate its fairness by referring to a fairness index. With this purpose, it is important to evaluate the individual satisfaction rates and to summarize the information given by each of them with a global fairness index.

A natural way to quantify the satisfaction of a user, as proposed by Jain, is through the proportion of the demand that is satisfied by an allocation [START_REF] Jain | A quantitative measure of fairness and discrimination for resource allocation in shared computer system[END_REF].

Definition 1 (Demand Fraction Satisfaction rate). Given the user i with demand c i and an allocation x i , the Demand Fraction Satisfaction (DFS) rate of i is:

DF S i = x i c i .
This rate takes a value between 0 and 1 since it represents the percentage of the demand that is satisfied.

Measuring the fairness of a system where user demands are bounded and differ among users, and using as satisfaction rate the DFS rate, implies replacing x i with DF S i in ( 5)- [START_REF] Jain | A quantitative measure of fairness and discrimination for resource allocation in shared computer system[END_REF].

Unavoidably, this way to quantify the user satisfaction makes the weighted proportional allocation the fairest one 1 Efficiency is defined as n i=1 x i = E. The utopia payoff is the marginal contribution of player i to the grand coalition N that utopistically could be assigned to i. The minimum right payoff is max S:i∈S R(S, i), where R(S, i) is the remainder (the amount which remain for player i when coalition S forms and all the other player in S obtain their utopia payoff).

since it allocates proportionally to the demand. There are, however, situations in which the common sense does not suggest to allocate in a proportional way; e.g., if there is a big gap between the demands, in order to protect the 'weaker' users and guarantee them a minimum portion of the estate. For such cases, the MMF allocation can be preferable. Furthermore, as mentioned in the introduction, the presence of other users, aware of other users' demand and of the available resource, should rationally be considered not to distort the evaluation of each user satisfaction.

For these reasons, we aim at defining an alternative satisfaction rate that satisfies the following two properties we name demand relativeness and relative null satisfaction:

• Demand relativeness: a user is fully satisfied when it receives its maximal right, based on the available resource; • Relative null satisfaction: a user has null satisfaction when it receives exactly its minimal right, based on other users' demands and the available resource.

The minimal right for a player is the difference between the available amount and the sum of the demands of the other users (i.e., taking a worst-case assumption that the others get the totality of their demand), and the maximal right is equal to the maximum available resource, i.e., c i if c i < E, or it is equal to E otherwise. Remembering the definition of the characteristic function of a bankruptcy game we have that:

• the minimal right for player i is v(i) • the maximal right for player i is v(N ) -v(N \ i)
Thus we introduce the 'player satisfaction (PS) rate', which satisfies the above two properties by considering the value of the bankruptcy game associated to the allocation problem.

Definition 2 (Player Satisfaction Rate). Given a bankruptcy game such that n i=1 c i > E and an allocation x i , the Player Satisfaction (PS) rate 2 for i is:

P S i = x i -min i max i -min i ,
where: [START_REF] Fossati | A Mood Value for Fair Resource Allocations[END_REF] if the allocation belongs to the core (see Theorem 1). Moreover it 'corrects' DF S i since it replaces the interval of possible values [0, c i ] for x i with the interval [min i , max i ]. Consequently, if for the DFS rate the maximum satisfaction for i is measured when it gets c i and the minimum when it gets 0, with PS, i is measured to be totally satisfied when it gets max i (i.e., c i if available, otherwise E), and totally unsatisfied when it gets min i (i.e., max{E -j∈N \{i} c j , 0}). In both cases the PS rate shows that player 2 is less satisfied 2 it is possible to generalize the PS measure of fairness for all the quasibalanced game (i.e. if m(v) ≤ M (v) and

min i = v(i), max i = v(N )-v(N \i). If n i=1 c i = E the player satisfaction rate is P S i = 1, ∀i ∈ N . P S i ∈ [0,
n i=1 m i (v) ≤ v(N ) ≤ n i=1 M i (v)), considering as minimum the minimum right payoff m i (v) and as maximum the utopia payoff M i (v).
than what expected with the DFS rate. This is due to the fact that the game guarantees player 2 to get at least 5.

Let us show some interesting properties of the PS rate.

Theorem 1. If the allocation x belongs to the core of the bankruptcy game, P S i ∈ [0, 1] ∀i ∈ N .

Proof. If a solution x belongs to a core it holds:

x i ≥ v(i) and x i ≤ v(N )-v(N \ i). Thus v(i) and v(N )-v(N \ i) are
the minimum and the maximum value that an allocation in the core can take. If

x i =v(i)=min i then P S i =0, if x i =v(N )- v(N \ i)=max i then P S i =1.
Proposition 1. It is possible to summarize the bankruptcy regimes of the P S rate in four possible cases as in Table II.

c i < E c i ≥ E PS case PS case v(i) = 0 x i c i GM x i E GG v(i) = 0 x i -v(i) c i -v(i) MM x i -v(i) E-v(i)

MG

TABLE II: Value of PS in the four possible cases.

Proof. Let us treat each possible cases of Table II:

• Case GM: v(i) = 0, c i < E. Using the definition of bankruptcy game, it holds: v(N ) -v(N \ i) = E - max{0, E -c i } = E -E + c i . It follows P S i = x i /c i . • Case GG: v(i) = 0, c i ≥ E. Using the definition of bankruptcy game, it holds: v(N ) -v(N \ i) = E - max{0, E -c i } = E. It follows P S i = x i /E. • Case MM: v(i) = 0, c i < E. As in case MG, v(N ) - v(N \ i) = E -max{0, E -c i } = c i . It follows P S i = (x i -v(i))/(c i -v(i)). • Case MG: v(i) = 0, c i ≥ E. As in case GG , v(N ) - v(N \ i) = E -max{0, E -c i } = E. It follows P S i = (x i -v(i))/(E -v(i)).
Case terminology: the PS rate differentiates four possible cases we name GM, GG, MM, MG. If a player asks less than E we call it moderate player (M) while if it asks more than E it is a greedy player (G). In similar way, if the sum of the demand of a group of n -1 players exceeds E, that means v(i) = 0, the group is a group of greedy players (G) otherwise if v(i) = 0 we have a group of moderate players (M). In the terminology we have used, the first character refers to the group of players while the second refers to the player itself. Proposition 1 highlights that not only there is a relation between the DFS rate and the PS rate, but that the satisfaction of a user should be modified when it is considered as a player inside a cooperative game. In particular, we can notice that for case GM the PS rate coincides with the DFS one, i.e., P S i = DF S i ; for case GG, the user satisfaction measured with the PS rate is higher than when it is measured with the DFS rate, i.e., P S i ≥ DF S i ; in the MM case, we have instead that DF S i ≥ P S i . We can also notice that the denominator of the PS rate is always different than zero. In cases GM and GG this is obviously true, in case MM the denominator is zero when n i=1 c i = E but in this case we set P S i = 1 and in case MG the denominator is zero when j∈N,j =i c j = 0 that is impossible. Furthermore, from Proposition 1 it follows that if an allocation, i.e., a solution of an allocation problem that satisfies efficiency, non-negativity and demand boundedness, is an imputation, then P S i ∈ [0, 1] for all the users. This holds due to the fact that for an allocation, in each of the four cases presented above, it is always verified that v(N ) -v(N \ i) is an upper bound for x i .

Looking at the possible combinations of scenarios it is possible to characterize the players of an allocation problem, and hence how they measure their satisfaction, as follows.

Proposition 2. Given an allocation problem with n = 2 users, the following combinations are possible:

• GG: All the players are in scenario GG.

• MM: All the players are in scenario MM.

• GM-MG: One player is in scenario MG and the others are in scenario GM. If n ≥ 3, 3 combinations are added to the previous ones:

• GM: All the players are in scenario GM.

• GM-GG: Two groups of players: some players are in scenario GM and the others in scenario GG. • GM-MM: Two groups of players: some players are in scenario GM and the others in scenario MM.

Proof. In case of three users, example 3 validates the existence of the six scenarios listed above. We prove that all the other combinations of scenarios, i.e. MG, GG-MM, GG-MG, MM-MG, are impossible.

• MG: all the user has a demand c i ≥ E. This implies that for all user i it holds j =i c j > E, but this is in contradiction with the fact that v(i) = 0. • GG-MM: for each user i of type MM it holds j =i c j < E but it exists at least one user of type GG such that c i ≥ E. This implies that j =i c j > E that is in contradiction with the fact that v(i) = 0. • GG-MG: all the users has a demand bigger or equal to E but it exists at least one user i in configuration MG such that j =i c j < E. This is impossible due to the fact that each demand exceeds E. • MM-MG: for each user i it holds j =i c j < E but it exists at least one user such that c i ≥ E. This produces a contradiction. In case GM-MG, if there exists two users i, j of type MG, it holds that c i > E and c j > E and

k =i c k < E and k =j c k < E. This produces a contradiction because c i > E implies k =j c k > E and c i > E implies k =j c k > E.
In case of two users, also the following scenarios are impossible:

• GM: both the users have a demand inferior to

E (c 1 < E, c 2 < E). It follows v(1) = E -c 2 > E and v(2) = E -c 1 > E that contradicts v(1) = v(2) = 0. • GM-GG the user 1 of type GM hasc 1 < E so v(2) = E -c 1 > 0.
This implies that 2 can not be of type GG. • GM-MM: as in case GM both users have a demand inferior to E.

It follows v(1) = E -c 2 > E and v(2) = E -c 1 > E,

B. Game-theoretical interpretation

To support and justify the use of the new satisfaction rate, we show an interesting game-theoretic interpretation.

Gately [START_REF] Gately | Sharing the gains from regional cooperation: A game theoretic application to planning investment in electric power[END_REF] introduced the concept of propensity to disrupt in order to remove the less fair imputations from the core. The idea was to investigate the gain of the player from the cooperation or, instead, its propensity to leave the cooperation, and to eliminate the imputation for which the propensity to leave the coalition for some players is excessively high. The formal definition of the propensity to disrupt is given in [START_REF] Sc | The propensity to disrupt and the disruption nucleolus of a characteristic function game[END_REF].

Definition 3 (Propensity to disrupt). For any allocation vector x, the propensity to disrupt d(x, S) of a coalition S ⊂ N (S = ∅, N ) is the ratio of the loss incurred by the complementary coalition N \ S to the loss incurred by the coalition S itself if the payoff vector is abandoned. That is:

d(x, S) = x(N \ S) -v(N \ S) x(S) -v(S) .
An equivalent definition of d(x, S) is:

d(x, S) = x(S) -v(S) x(S) -v(S) - 1
where:

x(S) = v(N ) -v(N \ S) [29].
The propensity to disrupt of a coalition S quantifies its desire to leave the coalition. When x(S) = v(S) the propensity to disrupt of S is infinite and the desire of S to leave the coalition is maximum; when x(S) > v(S) but x(S) -v(S) is small, the value of d(x, S) is very high and again S does not like the agreement; when x(S) = v(N ) -v(N \ S) the propensity to disrupt is zero and S has the propensity not to destroy the coalition; when x(S) > v(N ) -v(N \ S) the index is negative and there is an hyper-enthusiasm for such an agreement. It holds an interesting relationship between the propensity to disrupt and the player satisfaction rate.

Theorem 2. The relationship between the player satisfaction rate and the propensity to disrupt is:

P S i = (d(x, i) + 1) -1 .
Proof. Using the alternative definition of d(x, i) we have

d(x, i) = v(N )-v(N \i)-v(i) xi-v(i) -1 but v(N )-v(N \i)-v(i) xi-v(i) is equal to 1 P Si so d(x, i) = 1 P Si -1.
It is worth noting that if d(x, i) goes to infinity, then P S i goes to 0 and if d(x, i) = 0 then P S i = 1. This gives another interpretation of the PS rate. The higher the satisfaction is, the bigger the enthusiasm of i, for being in the coalition, is. On the contrary, the closer to zero the user satisfaction is, the higher the propensity of user i to leave the coalition is.

IV. THE MOOD VALUE AND THE PLAYER FAIRNESS INDEX

In this section, we define a new resource allocation rule that we call the Mood Value. The fairness idea behind this rule is the same of the one behind the Jain's index. A repartition of a resource is fair when all the users have the same satisfaction. Furthermore, we propose novel fairness indices as a modification of the classical fairness ones.

A. The Mood Value

Using the proposed PS rate, we can define the mood value.

Definition 4 (Mood Value). Given an allocation problem characterized by (c, E), the allocation x such that P S i = P S j ∀i, j ∈ N is called mood value.

Due to the relation between the propensity to disrupt and the player satisfaction, the fairest solution corresponds to the one in which every player has the same propensity to leave the coalition. Equalizing the propensity to disrupt of the users, this allocation equalizes the mood of each player. In particular, given a game, it exists a unique mood such that the satisfaction of each user is the same. The closer to zero the mood is, the more unsatisfied user i is; the closer to one the mood is, the more enthusiast the user i is.

Theorem 3. Let (c, E) characterize an allocation problem.

There exists a unique mood m such that P S i = m ∀i ∈ N :

m = E -min max -min (2)
where:

min = n i=1 v(i) = n i=1 min i , max = n i=1 [E - v(N \ i)] = n i=1 max i . The mood value is: x m i = min i + m(max i -min i ). (3)
Proof. Let P S i = m ∀i ∈ N . It follows:

x i = m(E -v(N \ i)) + (1 -m)v(i).
(4) Due to the efficiency property it holds:

n i=1 [m(E -v(N \ i)) + (1 -m)v(i)] = E. Thus (2). Since x i is the mood value iff P S i = m ∀i ∈ N : x i -v(i) E -v(N \ i) -v(i) = m
∀i ∈ N and (3) remains proved.

From (2) we can notice that the mood depends only on the game setting, thus, given a bankruptcy game, we can know a priori the value of the mood that produces a fair allocation. Knowing m, on can easily calculate the mood value x m i . The formula [START_REF] Ghimire | Revisiting scheduling in heterogeneous networks when the backhaul is limited[END_REF] shows that each user receives the minimum possible allocation v(i) plus a portion m of the quantity max i -min i . The nearer to 1 the mood m is, the greater the happiness of each user is, and the closer to the maximum the allocation is. In fact, when m is equal to 1, the player receives exactly E -v(N \ i), that is the maximum portion of resource that it can get, being inside a bankruptcy game. Depending only on the value of the minimum and the maximum payoff, the mood value coincides with the τvalue solution for bankruptcy games, also called adjusted proportional rules (AP-Rule) [START_REF] Curiel | Bankruptcy games[END_REF]. Before detailing this relationship, let us mention that in the bankruptcy games the core is [START_REF] Curiel | Bankruptcy games[END_REF]. Moreover, the core cover CC(v) is defined as the set of x ∈ R N such that Proof. The τ -value is the linear combination of the minimal and the utopia payoff (1) and, given the alternative definition of the mood value (4), we have to simply prove that the utopia payoff for each player is given by E-v(N \i) and the minimal one by v(i). α multiplies the minimal payoff in (1) while m the utopia one in (4), so trivially α = 1-m. As already argued in [START_REF] Curiel | Bankruptcy games[END_REF], the core C(v) coincides with the core cover CC(v). It follows that m

C(v) = {x ∈ R N : i∈N x i = v(N ), v(i) ≤ x i ≤ v(N ) -v(N \ i) ∀i ⊂ N }
i∈N x i = v(N ) and m(v) ≤ x ≤ M (v).
i (v) = v(i) and M i (v) = v(N ) -v(N \ i).
The mood value owns some interesting properties. It is an allocation thus it satisfies non-negativity, demand boundedness and efficiency property; it is stable, that means it belongs to the core of the game (prop. 5) and it guarantees more than minimal right to each player (x m i > v(i)). Furthermore, it satisfies the following property: if v(i) = v(j) and v(N \ i) = v(N \ j) then x m i = x m j . This implies the equal treatment of equals (c i = c j ⇒ x m i = x m j ) and equal treatment of greedy claimants (given a bankruptcy game, let G be the set of greedy players, i.e. such that c i > E: if |G| ≥ 2 then x m i = x m j ∀i, j ∈ G). This last property guarantees that even if a user has a cheating behavior, its demand is bounded by the available amount of resource E. Furthermore, the mood value is a strategy-proof allocation because a user has no advantages in splitting his demand and Curiel et al. in [START_REF] Curiel | Bankruptcy games[END_REF] prove that the τ -value solution for bankruptcy games can be characterized by (i) minimal right property, (ii) equal treatments of equals and (iii) strategy proofness property.

Theorem 5. The mood value belongs to the core of (N, v).

Proof. We should prove that x m S ≥ v(S), ∀S ⊆ N . If v(S) = 0 the condition holds due to the fact that x m i < 0, ∀i ∈ N . Now consider the case v(S) > 0. Suppose that x m S < v(S) = E -i∈N \S c i . For the efficiency property it holds E = x m S + x m N \S , implying x m N \S > i∈N \S c i , which yields a contradiction with the fact that, according to the mood value solution, each user receives at most its demand.

In case of two players, it holds the following proposition. Proposition 3. In a game with two players, the mood value coincides with the Shapley value and the mood is equal to 0.5.

Proof. Using ( 2) and (3) we have m = 0.5 and

x m i = 1 2 v(i) + 1 2 (E -v(N \ i)) for i = {1, 2}.
The Shapley solution for a game with two players is:

φ(1) = 1 2 v(1) + 1 2 (E -v(2)), φ(2) = 1 2 v(2) + 1 2 (E -v(1)
) and it coincides with x m . When the number of players is bigger than two, the mood value does not coincide any longer with the Shapley value as it is shown in the following example. It is important to note that the mood value solution for a resource allocation problem produces an interesting solution also in the case in which the sum of the demands is inferior to the resource. This is a desirable property with an application perspective to systems in which bankruptcy situations can dynamically alternate with situations that are not bankruptcy situations. In such cases, each user receives the demand c i and the excess E -n i=1 c i is divided equally between them. Proposition 4. Let (c, E) such that n i=1 c i ≤ E. The mood value solution for user i is

x i = c i + E - n i=1 c i n .
Proof. In order to calculate x i , it is necessary the value of v(i) and v(N \ i). It holds:

v(i) = E -j =i c i , v(N \ i) = E -c i .
Using the formula ( 2) and ( 3), we have m = (n -1)/n and

x i = E -j =i c i + n-1 n n i=1 c i -E = c i + E-n i=1 ci n .
Mood Value Computation Complexity: Differently from the other allocation solutions inspired by game theory, in order to calculate this new allocation, only the value of 2n coalitions, i.e., the ones formed by the single players and the ones containing n -1 players, is needed. The time complexity of mood value computation is dominated by the complexity of computing v(i) that is O(n). In dynamic situations, i.e., when the value of each of the n coalitions has to be updated at each slot of time, the complexity is therefore O(n 2 ), but it can be reduced to O(n) when v(i) pre-computation is possible. This makes the mood value the best allocation rule in terms of time complexity together with the proportional allocation: the Shapley value has a time complexity of O(n!), while iterative algorithms for the computation of MMF and CEL allocations have a O(n 2 log n) time complexity; the Nucleolus computation that in general is a NP-hard problem, in case of bankruptcy games can reduced to O(n log n) [START_REF] Fleiner | The nucleolus of the bankruptcy problem by hydraulic rationing[END_REF], [START_REF] Sziklai | On the Computation of the Nucleolus of Cooperative Tramsferable Utility Games[END_REF].

In terms of spatial complexity, the mood value, proportional, MMF and CEL allocations can be considered as equivalent and in the order of O(n). Instead, the Shapley value and the Nucleolus computations have a spatial complexity of O(2 n ).

B. The Player Fairness Index

In our next analysis, we consider the Jain's index and its modification we called Player fairness index. Definition 5. Given an allocation problem (c, E) and an allocation x, the Jain's fairness index is:

J = n i=1 x i c i 2 n n i=1 x i c i 2
The Jain's index is bounded between 1 n and 1 [START_REF] Jain | A quantitative measure of fairness and discrimination for resource allocation in shared computer system[END_REF]. The maximum fairness is measured when all the users obtain the same fraction of demand and the minimum fairness is measured when it exists only one user that receives all the resource. The Jain's index has the following good properties:

• Population size independence: applicable to any user set, finite or infinite. • Scale and metric independence: not affected by the scale.

• Boundedness: can be expressed as a percentage.

• Continuity: able to capture any change in the allocation. As we argued in the previous section, the appropriate metric to rationally measure the satisfaction of the users, in complete information sharing settings, is the PS rate. Consequently, we replace in the Jain's index the DFS rate with the PS rate and we obtain a new measure of fairness, we call players fairness index.

Definition 6 (Players fairness index). Given a problem (c, E) and an allocation x, the players fairness index is:

J p = n i=1 P S i 2 n n i=1 P S i 2
The resulting new fairness index we propose takes value 1 when all the users have the same satisfaction, i.e., when the allocation is the mood value. Theorem 6. The players fairness index takes value in the interval [ 1 n , 1] when the allocation belongs to the core. Proof. From Theorem 1 follows that P S i belongs to [0, 1] and that n i=1 P S i is always not negative. The maximum fairness is measured when all the users have the same PS rate, i.e.:

n i=1 P S i 2 = nP S i 2 ⇒ n n i=1 P S i 2 = nn P S i 2 .
Thus J p = 1. The minimum fairness is measured when ∃!k s.t. P S k = 0 and P S j = 0 ∀j = k. In this case:

n i=1 P S i 2 = P S k 2 ⇒ n n i=1 P S i 2 = n P S k 2 ⇒ J p = 1 n
For core allocations, J p takes value in the same interval of J making possible a comparison between the two indices. Furthermore, this index maintains all the good properties of the Jain's index: the population size independence, the scale and metric independence, the boundedness and the continuity.

It is worth mentioning that our proposed fairness index, as well as other indices from the literature that we recall in the paper, are used in the context of resource allocation frameworks where the satisfaction rate of the users is not boolean (either satisfied or unsatisfied) and there are no strict service level agreements to be fully satisfied.

V. INTERPRETATION WITH RESPECT TO TRAFFIC THEORY

In the already cited seminal works about the definition of proportional and weighted proportional allocations in network communications, network optimization models are defined using as goal the maximization of a utility function. A typical application is the bandwidth sharing between elastic applications [START_REF] Fp | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF], i.e., protocols able to adapt the transmission rate upon detection of packet loss. In this context, we show how it is possible to revisit the mood value as a value resulting of the sum of the minimum allocation and the result of a weighted proportional allocation formulation where the weights are not the original demands, but new demands re-scaled accordingly to the maximum possible allocation knowing the available resource, and the minimum allocation under complete information sharing. More precisely, it holds the following proposition: Proposition 5. The mood value can be computed as the result of the following 4-step algorithm.

Step 1: We assign to each user the minimal right v(i).

Step 2: We set the new value of the estate E = E -min = E -n i=1 v(i) and the new demands c i = max i -min i .

Step 3: We solve the following optimization problem maximize

x n i=1 c i log x i subject to x i ≤ c i , i = 1, . . . , n x i ≥ 0, i = 1, . . . , n n i=1 x i = E
Step 4 The mood value coincides with the sum of the minimal right and the allocation given by step 3:

x m i = v(i) + x i . Proof.
We should prove that the result of the optimization problem is

x i = mc i . The lagrangian of the problem is L(x, µ, λ) = n i=1 c i log x i -µ T (C -Ax)-λ(E - n i=1 x i )
where the vector µ and λ are the lagrangian multipliers (or shadow prices), C is the vector of the demands [c 1 , ...c n ] and A is the identity matrix of dimension n. Then, ∂L ∂xi =

c i xi - µ i -λ. The optimum is given by x i = c i µi+λ when µ ≥ 0, Ay ≤ C, n i=1 x i = E and µ T (C -Ax) = 0.
This coincides with the case in which µ T = 0 and λ = 0. In fact, we have

n i=1 c i λ = 1 λ n i=1 c i = E . It follows that λ = 1 E n i=1 c i is greater or equal to 1 and x i = c i
λ is less or equal to c i , that is an admissible solution. We can now notice that λ =

1 E n i=1 c i = max-min E-min = 1 m . It follows x i = mc i . Example 5. Let (c, E) be the allocation problem Example 1.
Following the algorithm we have:

Step 1: v(i) = [0, 0, 5].
Step 2:

E = 5, c i = [3, 2, 5]. Step 3: x = [1.5, 1, 2.5]
Step 4:

x m i = [1.5, 1, 7.5].
The algorithm shows that the mood value firstly assigns the minimal right (step 1) and secondly, considering the new allocation problem resulting after the first assignment (step 2), it allocates in a proportional way the resources (step 3). Then the proportion of allocated resource is the mood.

We provide two ways to compute the mood value: (3) and the 4-step algorithm of Section V. It is clear that the computation of the mood value through the formula (3) is less complex than the one using the 4-step algorithm.

VI. NUMERICAL EXAMPLES A. OFDMA scheduling use-case

In this section, we want to test the mood value and the new fairness index and to compare them with the classical allocations and the Jain's index. We run numerical simulations of the cellular OFDMA (Orthogonal Frequency-Division Multiple Access) spectrum scheduling problem.

In OFDMA scheduling, a base station unit or controller dynamically receives new users and decides which spectrum portion to allocate to which users, as a function of (i) their signal power and interference levels (aspects that characterize their demands), (ii) the other users to manage concurrently (i.e., users that arrive together during a OFDMA frame time or still in the scheduler queue) and (iii) the spectrum already allocated to existing users. The number of users to manage concurrently is basically limited to few (up to a dozen), except in high mobility environments. It is worth mentioning that in OFDMA, the unit of spectrum for the allocation is the Resource Block (RB). We suppose that the maximum number of available resource blocks is equal to 100; this coincides, in LTE standard, with the number of resource blocks for a bandwidth of 20 MHz. Furthermore, we consider a range for demand generation between 0 and 100 RBs using two different distributions: (i) a uniform distribution between 0 and 100, and (ii) a Zipf's distribution

f (k, s, N ) = 1 k s / N i=1
1 n s where the parameters k and s are equal to 100 and 0.4, respectively. We choose these values for the two parameters of the Zipf's distribution because as shown in [START_REF] Fossati | A Mood Value for Fair Resource Allocations[END_REF], they permit to fit well a realistic demand distribution. As a matter of fact, we show in [START_REF] Fossati | A Mood Value for Fair Resource Allocations[END_REF] that the continuous extension of OFDMA demand generation process leads to a distribution that well fits a Weibull distribution 3 .

We run different instances varying the available resource (i.e., E) from 5 to 95, with the interpretation of being the available number of resource blocks at the instant the OFDMA scheduling problem is faced. We simulate 300 bankruptcy games with 3 and 10 users in the scheduler. Fig. 2, 3, 4 and 5 show the results of the simulations. We consider the six allocations discussed before: Proportional, Shapley, Nucleolus, Mood Value, MMF and CEL. We calculate the Jain's fairness index and the players fairness index 3 The Zipf's distribution can be seen as a discrete variation of the Pareto distribution, that belongs to the same distributions family of the Weibull one. and we plot, for each value of E and each index, the mean value in between the first and third quartile lines.

In the 3-user cases (Fig. 2 and Fig. 4) the fairest allocation accordingly to the Jain's index is the proportional rule, and accordingly to the players' fairness index is the mood value. For both allocations, the value of the respective fairness index is equal to 1 for almost all the values of the available resource; only when the resource is scarce the value decreases due to the fact that the solutions are rounded. We can also notice that the mood value allocation has a behavior similar to the Shapley value and to the nucleolus and that it is close to the proportional allocation when the resource is between 50 and 80, and to the MMF allocation when the resource is scarce. For this last allocation the PF index has high value when the available resource is small (high congestion), i.e., when there are many greedy users. In fact, the MMF allocation and the mood value are close: in such cases, both have the property of treating equally the greedy claimant, giving them the same portion of resource, independently of their demands.

In the 10-user cases (Fig. 3 and Fig. 5), we can observe a similar trend for the two indices, but their values decreases, in particular in case of scarce resource, due to the discretization of the solution. Again, the mood value has a behavior similar to the Shapley value, but it is no more close to the nucleolus.

For each scenario, we can notice that the mood value solu- tion gives a better performance in term of fairness, measured with both indices, with respect to the MMF allocation, that is the one mostly used in this type of problems. In particular, the difference in term of fairness between the two allocations increases when the number of users in the system increases.

B. Continuous allocation example

Differently from the previous analysis around the OFDMA scheduling use-case where to a user can be given a discrete and limited number of RBs, we now consider divisible resources as caches or link bandwidths (i.e., a quasi-continuum situation with the bit granularity but with millions of bits for a single allocation). In the supplementary materials, we provide the same type of results than the previous section comparing rules and fairness indices, which lead to similar conclusions.

The continuous allocation allows us to better stress the situations different users fall in, as discussed in Prop. 1 and 2, and that as a function of the congestion level computed as the global demand over the available resource. Due to its noninformative nature, we consider a uniform distribution of the demands between 0 and 100 units of resource (e.g., Megabytes or Mega-bit/s) and we run different instances with a ratio of E (available resource) ranging from 5% to 95% of the global demand. We simulate 300 bankruptcy games with 3 and 10 users in the system waiting for an allocation. Fig. 6 shows the users configuration as a function of the available resource. With 3 users (Fig. 6a), for low value of E almost all are greedy players (GG case) due to the fact that the resource is small; increasing E the number of moderate players (GM) increases but also some users in configuration MG appear. In fact, increasing E, some greedy players become moderate while the others remain greedy; some of them are greedy inside a group of greedy users (GG), while some others greedy inside a group of moderate ones (MG). When the available resource is higher than half of the global demand, greedy players GG disappear and the number of moderate players increases. In particular, users MM appear and they become the majority when the resource is large. With 10 users (Fig. 6b), we find a similar trend than with 3 users in the number of moderate players that increases increasing E. However, MG users disappear; in fact, it holds that it can exist at most one MG user in a game (see Prop. 2) and, due to the higher number of users in the system, it is very unlikely that there exists only a player MG in the system such that the sum of the demands of the other n -1 players exceeds E.

To support the analysis of the user cases distribution, we plot the ratio of the four user types increasing the number of users from 3 to 15 and setting the demands in a uniform way between 0 and 100 (Fig. 7). As we already noticed, the number of MG users is small and it becomes negligible starting from a number of users higher than 5 (Fig. 7d). Furthermore, increasing the number of users, the range of available resource in which all the users are of type GM increases. In fact, if in 3-users scenarios a user can be of each possible type, in 15user scenarios we find users different from type GG only if the ratio of the available resource is less than 0.2 or higher than 0.8. When users are of type GG, their satisfaction is measured in the classical way with the DFS rate; it follows that with a sufficiently high number of users, the new proposed approach gives different results from the classical one only in case of high congestion or in case of low congestion. In order to capture all the possible scenarios, we choose a low number of users for the simulations. Summarizing, the simulations show how the proposed Mood Value produces different results with respect to the classical approach; in particular, in case of few users or, if the number of users is sufficiently high, in case of high or low congestion. The Mood Value is able to nicely weight the nature (greedy or moderate) of users; in particular, it is close to the MMF allocation when the resource is scarce and to the proportional allocation when the resource is close to the global demand. Furthermore, it is worth noticing that with respect the Shapley value, the results show that the Mood Value has a similar good behavior in terms of fairness, with the key advantage of having a much lower computation time complexity.

VII. DYNAMICS IN MULTI-PROVIDER CONTEXTS

We test the behavior of the different resource allocation rules in a strategic context with multiple competing providers. We run this analysis to (i) study the global system efficiency under the different allocation rules, and to (ii) qualify the motivation in adopting the mood value for a network provider.

A. Impact on system efficiency

For the first analysis we consider two providers, provider 1 and provider 2, providing the same service on a competitive market. Each of them has its own capacity (E1, E2) and its own way to allocate resources. We consider only the MMF, the mood value and the proportional allocation rules. Users are selfish and they have no binding agreements with the provider thus they can move from one provider to the other in order to reach a better satisfaction with respect of their allocation. The satisfaction is calculated using the demand fraction satisfaction rate (DFS rate) with the consequence that users prefer to move if their allocation is strictly bigger.

We set up a simulation in order to investigate the equilibrium configuration of the user to provider choices. We are particularly interested in the percentage of time in which the simulation produces 'agglomerated' configurations, i.e., when the equilibrium configuration coincides in having all the users served by only one provider. This is the worst configuration in terms of efficiency: the equilibrium is globally inefficient because the entire resource of one operator gets wasted.

In order to find the equilibrium configuration we randomly choose one of the two providers and we calculate the solution when all the users are served by this provider. Having the initial state, we calculate, for each player, the gain in moving to the other provider: if the gain is positive, it has propensity to move to the other provider, otherwise it prefers to stay in the currently provider. We choose randomly one user between the users that have positive gain and we move it in the other provider. We repeat the algorithm until we reach an equilibrium configuration.

For our simulations we generate E1 randomly between 0 and 20 units and we consider fixed ratios between E1 and E2 (E2= 1 10 E1, E2= 2 10 E1, ..., E2=E1, ..., E2=10E1). For each scenario, we generate 200 resource allocation problem instances with 3 users, choosing the demands uniformly between 0 and E1 + E2 (CASE 1). We repeat the simulations adding the constraints that both E1 and E2 are bigger than the smaller demand, i.e., we avoid situations in which all the demands are bigger than the estate (CASE 2). This second case makes more sense in some configurations and it follows the trivial idea that usually a provider owns enough resource to completely satisfy at least the user with the smallest demand.

For both cases, we plot the results in three scenarios:

• MMF-MOOD: the first provider allocates the resource using the MMF rule and the second with the mood value. • MMF-PROP: the first provider allocates using the MMF rule and the second with the proportional rule. • MOOD-PROP: the first provider allocates using the mood value rule and the second with the proportional rule. Fig. 8 and Fig. 9 show the result of the analysis. In CASE 1 (Fig. 8) we can notice that in each scenario the percentage of agglomerated equilibria is high when the gap between the quantity of available resource in the two providers is considerable; for instance, if one provider's resource is four times higher than that of the other provider. In these cases, there is a high probability that all the users, including the one with the smaller demand, reach a better allocation choosing the provider with the widest resource. In this case, the percentage of agglomerated equilibria slightly differs from one allocation to the other and in particular it is slightly higher when the provider allocates using the MMF rule; differently, in CASE 2 (Fig. 9) the percentage of agglomerated equilibria differs a lot with respect to the allocation that the providers adopt. In particular, we can notice that the number of agglomerated equilibria produced by the MMF allocation slightly decreases with respect to CASE 1, while the number of the ones produced by the proportional and mood value solution drastically decreases. We can report that in this case there is a resource waste that goes up to 26% (case E2= 3 10 E1) of the global resource with the MMF allocation, and it does not exceed 1,7% (case E2= 2 10 E1) with the mood value allocation.

B. Impact on user retention

In a second analysis, we aim to assess which type of users are attracted by which allocation rule. In this case we consider that operators have equal resources to avoid the presence of inefficient equilibria and we set two scenarios; we randomly generate 200 times E1 equal to E2 and 10 users such that in average the level of congestion in first scenario is 10% and in second is 90%.

Fig. 10 and Fig. 11 show the distribution of the four types of users previously discussed, for the three different pairs of allocation rules among the two providers, and for the two congestion scenarios 4 . We can notice that in case of high congestion there are only GM and GG users, while without congestion there are GM and MM users. In the former case, the mood value and the proportional allocation attract the users with high demand when the allocation of the other provider is MMF, while in the MOOD-PROP case there is a symmetric distribution in the users' type. We can also notice that in the MMF-MOOD case the mood value gives a median number of users 20% higher than with the MMF allocation. Moreover, in the high congestion scenario (Fig. 11), the MMF mostly attracts MM users, i.e., users with a demand lower than the available resource and such that the sum of other users demands is less than E; this means that if one of them leaves the provider, there is no more congestion on that provider and there is an excess of resource that gets wasted. Therefore, the mood value and the proportional allocation have a similar impact on user retention from a provider perspective: they appear better than the MMF allocation in a multi-provider strategic context because they can better use the resource of the providers, avoid resource waste. In particular, the gain of using these two allocations is conspicuous when we avoid (unlikely) situations in which all the users ask more than the resource available in one provider. Furthermore, in case of high congestion, the mood value attracts more users and users of higher demands, with respect to the MMF; in case of low congestion, similarly to the proportional allocation, it reduces the resource waste due to provider change.

VIII. ANALYSIS OF CHEATING BEHAVIORS

Let us investigate the consequences of users' cheating behaviors and in particular the relationship with the mood value, which, while it allows cheating behaviors, limits the gain of the cheating user 5 . Figure 12 shows the proportional allocation and the mood value when users cheat on their demands. The figure refers to an allocation problem where the available resource is 10 and the real demands of the users are 6 and 8. For the proportional allocation, the value of each allocation is the intersection between the black line, that is the Paretoefficient frontier, and the line with angular coefficient given by the ratio between the demand of user 2 and the demand of user 1; for the mood value, the value is the intersection between the frontier and the line connecting the minimum and the maximum allocation of the two users. We can notice that, with the proportional allocation, a user is stimulated in asking more in order to obtain a bigger allocation. The mood value does not avoid cheating behavior as well: asking more, users can receive more if their real demand is smaller than the available resource; nevertheless, when the demand goes beyond the available resource E, the mood value limits it at the available resource amount so that users have no incentive in asking more than E. In our example the first user can increase at most its allocation from 4 to 6 and the second one from 6 to 7. We formalize this aspect as follows: Proposition 6. A user has no incentive in asking more than the available resource if the allocation rule is the Mood value.

Proof. If a user i has a demand c i > E then the interval of value considered to calculate the mood value is [min i , E]: increasing the demand the interval does not change because min i depends only on E and on the demands of the other users. So it trivially follows that the mood value allocation for the user is not increasing. We test now the gain of users in cheating for a 2-user allocation problem in which both users have a demand, expressing their real need, inferior to the available resource (c=(6, 8), E=10). In order to obtain a better allocation users can declare a need superior than how much they really need; in particular in our example from 10% to 400% more than the demand c i .

Fig. 13 shows the heat map of the users gain as a function of the percentage of cheating of both users; we use the DFS satisfaction and the gain for user i is calculated as

G i = x c i -x r i x r i
, where x c i is i's allocation when there is cheating and x r i is the allocation when both users declare the true needs. Being c 1 and c 2 bigger than E 2 , the MMF allocation is always equal to E 2 for both users thus cheating brings no gain to users, otherwise a proportional or a mood value allocation allow users to gain or to lose. We can notice that with a proportional allocation the gain or the loss of user can be very high (see Table IV), depending on the percentage (importance) of cheating, while the mood value allocation limits the gain or the loss. This follows from the property of equal treatment of greedy claimants, and from the fact that the mood value solution coincides with the MMF fair allocation when the resource is scarce with respect to the demands of the users.

IX. CONCLUSION

We proposed a game-theoretical approach to analyze and solve resource allocation problems, going beyond classical approaches that do not explore the setting where users can be aware of other users' demand and the available resource.

In particular, we proposed a new way of quantifying the user satisfaction taking into account the deeper knowledge of the users with respect to the resource allocation problem, and a new fairness index as enhancement of the family of fairness measures, describing and comparing their mathematical properties in detail. According to these new concepts, we propose a new resource allocation rule called the 'Mood Value' that meets the goal of providing the fairest resource allocation and we position it with respect to game theory metrics as well the common theory of fair allocation in networks.

Finally, we test our ideas via numerical simulations of representative demand distributions and we provide two further analysis showing the advantages of the mood value allocation in a strategic multi-provider context and in the presence of cheating users. Besides the properties we analytically prove, the results of our simulations can be summarized as follows:

• the mood value allocation is able to take into account the nature of the users and the level of congestion of the system and consequently to choose the fairest solution; • in case of high congestion, the mood value allocates the resources in way similar to the MMF allocation, while in case of low congestion similarly to the proportional allocation; this implies that if users cheat on their demand, they have a limited gain because the mood value converges to a MMF allocation under high congestion; • the mood value has lower computational complexity than other game theoretical solutions as the Shapley value; • in case of strategic contest, the mood value guarantees the efficiency of the equilibrium, except, with a low percentage, in case of strong resource imbalance between the two providers and it attracts more users and with higher demands in case of high system congestion.

APPENDIX A FAIRNESS INDICES

The axiomatic theory of fairness proposed in [START_REF] Lan | An axiomatic theory of fairness in network resource allocation[END_REF] shows that it exists an unique family of fairness measures given by:

F β,λ (x) = f (x) i x i 1 λ (5)
where x is the allocation, 1 λ and β are parameters belonging to R and f (x) is a symmetric fairness measure as f β (x) or an asymmetric one as f β (x, q):

f β (x) = sign(1 -β) n i=1 x i j x j 1-β 1 β (6) f β (x, q) = sign(-r(1 + rβ)) n i=1 q i x i j x j -rβ 1 β ( 7
)
where q i is user i specific weight and r ∈ R is a constant exponent. This family of measures unifies different fairness indices belonging to different fields as networking, economy and political philosophy. The most common fairness indices are described with their (5)- [START_REF] Jain | A quantitative measure of fairness and discrimination for resource allocation in shared computer system[END_REF] α-fair f β (x, q) β ∈ (0, 1) 1

1-β β 1 -1 β sign(1 -β) n i=1 (x i ) 1-β 1 β [0, +∞) (β = α) β ∈ (1, ∞)
Atkinson-1 f β (x, q) 1 -, ∈ [0, 1]

1 n 0 -1 -1 n n i=1 (x i ) 1- 1 1-/ n i=1 (x i ) n [0, 1]
TABLE V: Common fairness indices and their parameters using ( 5)-( 7) -NA = Not Available.

Example 1 .

 1 Let (c, E) be the situation of Fig.1with c=(3, 2, 13) and E=10.

Example 2 .

 2 Consider (c, E) of Example 1 (see Fig.1) and the corresponding bankruptcy game model. It holds: Proportional allocation: DF S 2 = 0.555 and P S 2 = 0.444 MMF allocation: DF S 2 = 0.3846 and P S 2 = 0.

Theorem 4 .

 4 The mood value coincides with the τ -value solution for bankruptcy games, where the α value of the τvalue coincides with 1 -m.

Example 4 .

 4 Let c i = [6, 2, 5] and let E = 10. The mood value is x m = [4.875, 1.25, 3.875] and the Shapley value is x s = [4.833, 1.333, 3.833].

Fig. 2 :Fig. 3 :

 23 Fig. 2: Fairness w.r.t. the available resource (3 users, uniform)

Fig. 4 :Fig. 5 :

 45 Fig. 4: Fairness w.r.t. the available resource (3 users, Zipf)

Fig. 6 :

 6 Fig. 6: User cases distribution

Fig. 7 :

 7 Fig. 7: Ratio of users as function of the users number

Fig. 8 :Fig. 9 :

 89 Fig. 8: Percentage of agglomerated equilibria in CASE 1.

Fig. 10 :

 10 Fig. 10: Distribution of the four type of users -average level of congestion = 10%

Fig. 12 :

 12 Fig. 12: Variation of the proportional and mood value allocations as function of the cheating. c:(6,8), E:10

(a) User 1 :

 1 Fig. 13: Users' gain in cheating environment (E=10, c=(6,8)).

  Table I shows the value of the Jain's index and the Atkinson's index of fairness.

	User demands	Prop.	MMF	Shapley	Nucleolus	CEL
	A: 3	1.67	3	1.5	1.5	0
	B: 2	1.11	2	1	1	0
	C: 13	7.22	5	7.5	7.5	10

TABLE I

 I

	: Allocation rules comparison (E=10, cf. Fig. 1)
	III. MEASUREMENT OF USER SATISFACTION

TABLE III :

 III Allocation problems with three players.

TABLE IV :

 IV Maximum gain and lost: comparison

  parameters in TableV.

	Index name	f (x)	β	q i	1 λ	r	F β,λ (x)		Value range
	n*Jain	f β (x)	-1	NA	0	NA	n i=1 (x i )	2 /	n i=1 (x i ) 2	[0, n]
	Max-Ratio	f β (x)	β → ∞	NA	0	NA	-max i	n i=1 x i x i	(-∞, 0]
	Min-Ratio	f β (x)	β → -∞	NA	0	NA	min i	n i=1 x i x i	[0, +∞)
	Proportional	f β (x)	β → 1	NA	0	NA	n i=1 log(x i )	(0, +∞)

e.g., in Fig.10athe first provider uses the MMF rule and the user distribution is given by the first four boxplots, the fifth one giving the sum; the remaining boxplots give the same numbers for the second provider. Each boxplot reports, from bottom to top, the minimum, first quartile, median, third quartile, and maximum.

It is worth mentioning that, in order to introduce mechanisms to guarantee truthful demands, a pricing scheme like the one proposed in[START_REF] Hoteit | On fair network cache allocation to content providers[END_REF] can be applied. Such a pricing scheme encourages the users to declare their truthful demands by maximizing their utilities for real declarations.

This work was partially funded by the FED4PMR project.