Marcel Morales
email: marcel.morales@ujf-grenoble.fr

Dung Thai Nguyen

Nguyen Thi

Gröbner basis, a "pseudo-polynomial" algorithm for computing the Frobenius number

published or not. The documents may come

Gröbner basis. a "pseudo-polynomial" algorithm for computing the Frobenius number

Introduction

In the sequel we shall use the following notations. Let K be a field, A be a set of n natural numbers A = {a 1 , . . . , a n } ⊂ N. S the numerical semigroup generated by a 1 , . . . , a n , that is S = {k 1 a 1 + . . . k n a n |k i ∈ N}. We consider the one-dimensional toric affine ring

A = K[t a 1 , . . . , t an ] ⊂ K[t], that is A = K[t k |k ∈ S] := K[S].
The ring A = K[t a 1 , . . . , t an ] ⊂ K[t] has a presentation as a quotient of the polynomial ring K[x 1 , . . . , x n ], as follows: Let ϕ : K[x 1 , . . . , x n ] → K[t a 1 , . . . , t an ] defined by

x 1 → t a 1
. . .

x n → t an

Let I(S) be the kernel of ϕ, that is the ideal ideal formed by all polynomials of K[x 1 , . . . , x n ] such that P (t a 1 , . . . , t an ) = 0. The ideal I(S) has a system of generators formed by binomials which are differences of two monomials with coefficient 1. Note that if we grade the polynomial ring K[x 1 , . . . , x n ] by setting deg(x i ) = a i , the morphism ϕ is homogeneous, and the ideal I(S) is homogeneous.

The following theorem is well known, we give here a short proof for the commodity of the reader.

Theorem 0.1. Suppose that a 1 , . . . , a n are relatively prime numbers then any large integer belongs to S.

Proof. Suppose that n = 2, By Bézout'theorem there exist relative integer numbers s 1 , s 2 such that s 1 a 1 + s 2 a 2 = 1. We can assume that s 1 > 0, s 2 < 0. Let k > 0 big enough we can write k = qa 2 +r with 0 ≤ r < a 2 , which implies k = qa 2 +r(s 1 a 1 +s 2 a 2 ) = rs 1 a 1 +(q+rs 2 )a 2 . Since k is large enough (q + rs 2 ) > 0, hence k ∈ S.

A similar argument works for n > 2.

Definition 0.2. Suppose that a 1 , . . . , a n are relatively prime numbers, the biggest integer number in N \ S is called the Frobenius number, we denote it by g(S). More generally if gcd(a 1 , . . . , a n ) = λ then the biggest integer in λN \ S is called the Frobenius number, we denote it by g(S).

Suppose that gcd(a 1 , . . . , a n ) = λ, let S be the semigroup generated by a 1 λ , . . . , an λ . We have that g(S) = λg( S). The problem of computing the Frobenius number is open since the end of 19th Century, for n = 2 there is a formula (see section 1), for n = 3 a formula using Euclide's algorithm for gcd was given in [START_REF] Rodseth | On a linear Diophantine problem of Frobenius[END_REF]. In 1987, in [START_REF] Morales | Syzygies of monomial curves and a linear diophantine problem of Frobenius[END_REF] the first author translate for the first time the Frobenius problem into an algebraic setting, showing that the Frobenius number is the degree of the Hilbert-Poincaré series written as a rational fraction, moreover By using [START_REF] Rodseth | On a linear Diophantine problem of Frobenius[END_REF], in the case n = 3 the Hilbert-Poincaré series is completely described by an algorithm using only Euclide's algorithm for gcd, that is of complexity ln(a). An implementation in Pascal was done by the first author to compute a system of generators of the affine monomial curve K[t a , t b , t c ] and its projective closure, which computed the Frobenius number for three natural numbers. In recent works [START_REF] Einstein | Frobenius numbers by lattice point enumeration[END_REF] and [START_REF] Roune | Solving Thousand Digit Frobenius Problems Using Grobner Bases[END_REF], the computation of Frobenius number, is related to the computation of the Hilbert-Poincaré series. More precisely, in [START_REF] Roune | Solving Thousand Digit Frobenius Problems Using Grobner Bases[END_REF] the author deduces the Frobenius number from a Gröbner basis of the ideal I(S). We recall that the computation of a Gröbner basis is double exponential complexity by using the Buchberger algorithm.

In this paper we study the Frobenius problem from algebraic point of view, this allows us to give a conceptual frame to our algorithm. As a consequence of our study we get a very fast and simple algorithm to compute the Frobenius number, determine completely the semigroup S and solve the knapsack integer problem, that is to decide if an integer number belong to S. We have implemented for n ≤ 17. We need to solve the "multiplicative" integer knapsack problem: Find all positive integer solutions (k 1 , . . . , k n ) of the inequality n i=2 (k i + 1) ≤ a 1 + 1. Moreover let G(S) be a Gröbner basis for the degree reverse lexicographic order to x n , . . . , x 1 . ≺ revlex and in(I(S)) be its initial ideal. As an extension we find several algorithms :

1. The set of monomials {x k 2 2 . . . x kn n / ∈ in(I(S))}.

2. The system of monomial generators of in (I).

3. The Gröbner basis G(S) of I, without using Buchberger's algorithm.

They are extensions of the previous work and algorithm by the first author in [START_REF] Morales | Syzygies of monomial curves and a linear diophantine problem of Frobenius[END_REF], [START_REF] Morales | Équations des variétés monomiales en codimension deux[END_REF]. The algorithm presented here is implemented and can be downloaded in https://wwwfourier.ujf-grenoble.fr/ morales/. Note that because of the limitation of the Compiler for the moment the software works only for numbers less than 10000, but an implementation in Mathematica should allow to compute with any number of digits.

In the first section we introduce the Apéry set and we prove some known results.

In the second section we present the connection between Hilbert-Poincaré series and the Frobenius number. This connection was established by the first author for the first time in [START_REF] Morales | Syzygies of monomial curves and a linear diophantine problem of Frobenius[END_REF].

In the third section we introduce Noether normalization and we prove the connection between Apéry sets and Noether normalization.

In the last section we develop our algorithm.

In our work in progress, we will extend the above algorithm to compute Gröbner basis of any simplicial monomial ideal.

Frobenius number, Apéry set

For a survey on the Frobenius number we refer to [START_REF] Ramírez Alfonsín | The Diophantine Frobenius Problem[END_REF].

Definition 1.1. Suppose that a 1 is the smallest among a 1 , . . . , a n . The Apéry set Ap(S, a 1 ) of the semigroup S with respect to a 1 is the set Ap(S, a 1 ) := {s ∈ S|sa 1 / ∈ S}.

Remark 1.2. The definition of Apéry set makes sense even if the numbers a 1 , . . . , a n are not relatively prime numbers. Suppose that gcd(a 1 , . . . , a n ) = λ, let S be the semigroup generated by a 1 λ , . . . , an λ . We have that Ap(S, a 1 ) is obtained from Ap( S, a 1 λ ) by multiplication by λ.

Theorem 1.3. (Apéry [START_REF] Apéry | Sur les branches superlinéaires des courbes algébriques[END_REF])Suppose that a 1 , . . . , a n are natural numbers such that gcd(a 1 , . . . , a n ) = λ.

1. Ap(S, a 1 ) := {λw 0 , . . . , λw a 1 λ -1 }, where w i is the smallest element is S congruent to i mod a 1 λ . 2. g(S) = max {sa 1 |s ∈ Ap(S, a 1 )}.

Proof.

1. We can assume that a 1 , . . . , a n are relatively prime numbers. First we prove that for all i = 0, . . . , a 1 -1, w i belongs to Ap(S, a 1 ). Suppose that it is not true, that is w ia 1 ∈ S for some i = 0, . . . , a 1 -1. It follows that w ia 1 < w i and both w ia 1 , w i ∈ S are congruent to i mod a 1 . This is a contradiction with the definition of w i . As a consequence Ap(S, a 1 ) has at least a 1 elements in order to prove the claim it will be enough to show that Ap(S, a 1 ) has exactly a 1 elements. Suppose that card(Ap(S, a 1 )) > a 1 , then there exists two elements s 1 < s 2 in Ap(S, a 1 ) such that both s 1 < s 2 are congruent to i mod a 1 for some i = 0, . . . , a 1 -1, that is s 2 = s 1 + ka 1 with k > 0 a natural integer, hence s 2 ∈ Ap(S, a 1 ), a contradiction.

2. Let h ∈ N such that h > max {sa 1 |s ∈ Ap(S, a 1 )}, since h is congruent to i mod a 1 for some i = 0, . . . , a 1 -1, we can write h = w i + αa 1 , with α ∈ Z, hence h = (w ia 1 ) + (α + 1)a 1 , since h > (w ia 1 ) we have (α + 1) > 0, hence α ≥ 0, which implies that h ∈ S.

Corollary 1.4. Let n = 2 suppose that a 1 , a 2 are relatively prime numbers then g(S) = (a 1 -1)(a 2 -1) -1.

Proof. We give a combinatorial proof using Apéry sets. Since a 1 , a 2 are relatively prime numbers, we have Ap(S, a 1 ) := {0, a 2 , . . . , (a 1 -1)a 2 },

hence g(S) = (a 1 -1)(a 2 ) -a 1 = (a 1 -1)(a 2 -1) -1
For n = 2, we will give an algebraic proof later.

Corollary 1.5. For i = 0, . . . , a 1 -1 let S i = {s ∈ S|s ≡ i mod a 1 }. Then S is the disjoint union of S 0 , . . . S a 1 -1 .

2 Frobenius number and Hilbert-Poincaré series

P B (u) = l∈Z H B (l)u l .
We recall the following Theorem from [START_REF] Morales | Syzygies of monomial curves and a linear diophantine problem of Frobenius[END_REF] Theorem 2.1. Let R := K[x 1 , . . . , x n ] be the polynomial ring graded by the weights deg

x 1 = a 1 , . . . , deg x n = a n , I ⊂ K[x 1 , . . . ,
x n ] be a graded ideal and B := R/I. Then 1. The Hilbert-Poincaré series of B is a rational function:

P B (u) = Q B (u) (1 -u a 1 )(1 -u a 2 ) . . . (1 -u an )
,

where Q B (u) is a polynomial on u.

2.

There exists h polynomials with integer coefficients Φ H B ,0 (l), . . . , Φ H B ,h (l) such that H B (lh + i) = Φ H B ,i (l) for 0 ≤ i ≤ h -1 and l large enough. We recall that the index of regularity of the Hilbert function is the biggest integer l such that H B (l) = Φ H B ,i (l), for any i.

3. The index of regularity of the Hilbert function equals the degree of the rational fraction defining the Poincaré series.

Corollary 2.2. [START_REF] Morales | Fonctions de Hilbert, genre géométrique d'une singularité quasihomogène Cohen-Macaulay[END_REF] Let S be the semigroup generated by a 1 , . . . , a n , and

A = K[t a 1 , . . . , t an ] ⊂ K[t]
. The Frobenius number g(S) coincides with the degree of the rational fraction defining the Poincaré series P A (u) by the theorem 2.1.

Proof. The Hilbert function of A is given by

H A (l) = 1 if l ∈ S 0 if l / ∈ S.
In particular if a 1 , . . . , a n are relatively prime, H A (l) = 1 for l large enough, and the Frobenius number coincides with the index of regularity of the Hilbert function H A (l), so it is the degree of the rational fraction defining the Poincaré series P A (u).

Gröbner basis

Let a 1 , . . . , a n be natural numbers, λ = gcd(a 1 , . . . , a n ). We denote by S (resp. S) the semigroup generated by a 1 , . . . , a n (resp. by a 1 /λ, . . . , a n /λ). Note that the semigroup rings K[S], K[ S] are isomorphic. Let R := K[x 1 , . . . , x n ] be the polynomial ring graded by the weights deg x 1 = a 1 , . . . , deg x n = a n . We consider ≺ degrevlex the degree reverse lexicographical order with x n , . . . , x 1 , but all results are valuable for any monomial order such that the variable x 1 never appears in a minimal system of generators of the initial ideal in(I(S)). The first statement of the following theorem is an extension to the quasi-homogeneous case of [START_REF]Effectivité des calculs polynomiaux, Courd de DEA 1984-1985[END_REF].

Theorem 3.1. Let A := K[t a 1 , . . . , t an ] ≃ R/I(S).

1. The polynomial ring K[x 1 ] ⊂ A is a Noether normalization. Moreover let G(S) be a Gröbner basis for ≺ revlex and in(I(S)) be the initial ideal then

A ≃ ⊕ x k 2 2 ...x kn n / ∈in(I(S)) K[t a 1 ][t k 2 a 2 +...+knan ].
2. The Hilbert-Poincaré series is given by: 1. We have that for any i = 2, . . . , n, (t a i ) a 1 -(t a 1 ) a i = 0, so K[t a 1 , . . . , t an ] is integral over K[t a 1 ], both rings have dimension one so K[t a 1 ] ⊂ K[t a 1 , . . . , t an ] is a Noether normalization, also both rings are Cohen-Macaulay. By the Auslander-Buschsbaum formula we get that K[t a 1 , . . . , t an ] is a free K[t a 1 ]-module. This is the same to say that R/I(S) is a free K[x 1 ]-module. Since R/I(S) is a graded K[x 1 ]module, we can use Nakayama's lemma, hence any K-basis of R/(I(S), x 1 ) gives us a basis of R/I(S) as a free K[x 1 ]-module. Let G(S) be a Gröbner basis for ≺ revlex and in(I(S)) be the initial ideal, by definition of ≺ degrevlex , x 1 does not divides any of the elements in in(I(S)). On the other hand Macaulay's theorem [START_REF] Eisenbud | Commutative algebra with a view toward algebraic geometry[END_REF][Theorem 15.3]says us that the set of monomials not in in(I(S)) is a basis of R/I(S) as a free K[x 1 ]-module.

P A (t) = x k 2 2 ...x kn n / ∈in(I(S)) t k 2 a 2 +...+knan 1 -t a 1

It is clear that the

Hilbert-Poincaré series of K[t a 1 ] is 1 1-t a 1
, the Hilbert-Poincaré series is an additive function, hence we have the formula for the Hilbert-Poincaré series of A.

By 2.1

The Frobenius number of S is the degree of the Hilbert-Poincaré series of A.

We have the following consequence which will be important for our algorithm: Corollary 3.2. We have that

s i ∈ H, l ∈ N such that s -a 1 = s i + la 1 that is s = s i + (l + 1
)a 1 a contradiction to the direct sum decomposition. Reciprocally, let s ∈ Ap(S, a 1 ), then there exists unique

s i ∈ H, l ∈ N such that s = s i + la 1 , if l > 0 then s -a 1 ∈ S a contradiction , hence s = s i ∈ H. 2. If s = l 2 a 2 + . . . + l n a n with (k 1 , . . . , k n ) = (l 1 , . . . , l n ) and x l 2 2 . . . x ln n ≺ revlex x k 2 2 . . . x kn n then x k 2 2 .
. . x kn n ∈ in(I(S)), a contradiction.

Example 3.3. Let n = 2, and a 1 , a 2 be natural numbers, λ = gcd(a 1 , a 2 ), we have that

K[t a 1 , t a 2 ] ≃ K[x 1 , x 2 ]/(x a 1 /λ 2 -x a 2 /λ 1
) it is clear that that x

a 1 /λ 2 -x a 2 /λ 1
is a Gröbner basis of the ideal (x

a 1 /λ 2 -x a 2 /λ 1
) for ≺ revlex . We have in(x

a 1 /λ 2 -x a 2 /λ 1 ) = (x a 1 /λ 2 ), hence K[t a 1 , t a 2 ] =≃ ⊕ a 1 /λ-1 k=0 K[t a 1 ][t ka 2 ]
, the Poincaré series is given by: P A (t) =

a 1 /λ-1 k=0 t ka 2 1 -t a 1 .
if a 1 , a 2 are coprime then the Frobenius number is (a

1 -1)a 2 -a 1 = (a 1 -1)(a 2 -1) -1.
4 Frobenius number, Hilbert-Poincaré series, the case n = 3

This section is a short version of [START_REF] Morales | Syzygies of monomial curves and a linear diophantine problem of Frobenius[END_REF] and [START_REF] Morales | Équations des variétés monomiales en codimension deux[END_REF].

Let consider three natural numbers a, b, c and S be the semigroup generated by a, b, c. First, remark that any solution α := (u, v, w) of the Diophantine equation ua + vb + wc = 0 gives rise to a binomial in the ideal I(S) in the following way: we write the vector α = α +α -, where the components of both α + , α -are nonnegative then x α +x α -∈ I(S), where

x α + = x α + 1 1 x α + 2 2 x α + 3 3
. Reciprocally if x αx β ∈ I(S) and x α , x β have not common factors then (u, v, w) := αβ is a solution of the equation ua + vb + wc = 0. Second, it is clear that find solutions (u, v, w) of the Diophantine equation ua + vb + wc = 0 is equivalent to find solutions (s, p, r) of the Diophantine equation sbpc = ra. Let s 0 be the smallest natural number such that (s 0 , 0, r 0 ) is solution of the equation sb-pc = ra. We set p 0 = 0. Let p 1 be the smallest natural number such that (s 1 , p 1 , r 1 ) is solution of the equation sbpc = ra, with 0 ≤ s 1 < s 0 . Note that s 0 = a gcd(a,b) and p 1 = gcd (a,b) gcd(a,b,c) . The numbers s 1 can be got from the extended Euclide's algorithm for the computation of the greatest common divisor of a, b.

Let consider the Euclides' algorithm with negative rest:

           s 0 = q 2 s 1 -s 2 s 1 = q 3 s 2 -s 3 . . . = . . . s m-1 = q m+1 s m s m+1 = 0 q i ≥ 2 , s i ≥ 0 ∀i.
Let define the sequences: p i , r i (0 ≤ i ≤ m + 1) , by:

p i+1 = p i q i+1 -p i-1 , r i+1 = r i q i+1 -r i-1 , (1 ≤ i ≤ m).
Note that from [START_REF] Morales | Équations des variétés monomiales en codimension deux[END_REF] we have for i = 0, . . . , m that s i p i+1s i+1 p i = s 0 p 1 = a gcd(a,b,c) . Let µ the unique integer such that r µ > 0 ≥ r µ+1 . Theorem 4.1. ( [START_REF] Morales | Fonctions de Hilbert, genre géométrique d'une singularité quasihomogène Cohen-Macaulay[END_REF], [START_REF] Morales | Syzygies of monomial curves and a linear diophantine problem of Frobenius[END_REF] and [START_REF] Morales | Équations des variétés monomiales en codimension deux[END_REF]) The set

x sµ 2 -x rµ 1 x pµ 3 , x p µ+1 3 -x -r µ+1 1 x s µ+1 2 , x sµ-s µ+1 2 x p µ+1 -pµ 3 -x rµ-r µ+1 1
is a Gröbner basis of I(S) for ≺ revlex with x 3 , x 2 , x 1 . In particular in(I(S) = (x sµ 2 , x

p µ+1 3 , x sµ-s µ+1 2 x p µ+1 3
), and

N 2 \ exp(in(I(S)) = {(k, l) ∈ N 2 |0 ≤ k < s µ -s µ+1 , 0 ≤ l < p µ+1 }∪ {(k, l) ∈ N 2 |s µ -s µ+1 ≤ k < s µ , 0 ≤ l < p µ+1 -p µ }. K[t a , t b , t c ] ≃ ⊕ (k,l)∈N 2 \exp(in(I(S)) K[t a ][t kb+lc ].
In particular the Poincaré series is given by:

P A (t) = (k,l)∈N 2 \exp(in(I(S)) t kb+lc 1 -t a
and if the numbers a, b, c are relatively prime the Frobenius number is

g(S) = max {kb + lc|(k, l) ∈ N 2 \ exp(in(I(S))} -a 1 .
Proof. we can give a new and shorter proof than the one given in the general case in [START_REF] Morales | Équations des variétés monomiales en codimension deux[END_REF]. We can assume that the numbers a, b, c are relatively prime. Let consider the three elements of I(S):

x sµ 2 -x rµ 1 x pµ 3 , x p µ+1 3 -x -r µ+1 1 x s µ+1 2 , x sµ-s µ+1 2 x p µ+1 -pµ 3 -x rµ-r µ+1 1
. It then follows that

J := (x sµ 2 , x p µ+1 3 , x sµ-s µ+1 2 x p µ+1 3
) ⊂ in(I(S). Now we count the numbers of monomial not in J,

card(N 2 \ exp(J)) = (s µ -s µ+1 )p µ+1 + s µ+1 (p µ+1 -p µ ) = s µ p µ+1 -s µ+1 p µ = a.
On the other hand by Corollary 3.2, card(N 2 \ exp(in(I(S))) = a this implies in(I(S) = J, hence the set

x sµ 2 -x rµ 1 x pµ 3 , x p µ+1 3 -x -r µ+1 1 x s µ+1 2 , x sµ-s µ+1 2 x p µ+1 -pµ 3 -x rµ-r µ+1 1
is a Gröbner basis of I(S) for ≺ revlex with x 3 , x 2 , x 1 . The other claims follows from the Theorem 3.1 5 Algorithm for the case n ≥ 4

For n = 3, we have seen that the algorithm use only Euclide's algorithm. Let n ≥ 4. Let a 1 , . . . , a n be relatively prime natural numbers, S the semigroup generated by a 1 , . . . , a n . Let R := K[x 1 , . . . , x n ] be the polynomial ring graded by the weights deg x 1 = a 1 , . . . , deg x n = a n . We consider ≺ degrevlex the degree reverse lexicographical order with x n , . . . , x 1 , A = K[t a 1 , . . . , t an ] ≃ R/I(S). 2 . . . x kn n . that is we have (k 2 + 1) × . . . × (k n + 1) -1 monomials not in in(I(S), hence (k 2 + 1) × . . . × (k n + 1) -1 ≤ a 1 , which implies S n-1 + S n-2 + . . . + S 2 + S 1 ≤ a 1 , where S i is the symmetric polynomial of degree i in the variables k 2 , . . . , k n . In particular k 2 + . . . + k n ≤ a 1 .

We have the following algorithm for the Frobenius number: End (of the algorithm).

In the following example we compute the Gröbner basis by my software and by Cocoa, it runs in above 7 seconds in both softwares. The Gröbner basis has 571 generators. If we compute only the Apéry number our algorithm is much faster than Cocoa. In this example the Apéry number is 5145.

  Let R := K[x 1 , . . . , x n ] be the polynomial ring graded by the weights deg x 1 = a 1 , . . . , deg x n = a n , and I ⊂ K[x 1 , . . . , x n ] be a graded ideal. Let B = R/I, the Hilbert-function of B is defined by H B (l) = dim K B l , for all l ∈ Z, and the Hilbert-Poincaré series of B:

3 .

 3 The Frobenius number g( S) = max {k 2 a 2 +...+knan|x

Remark 5 . 1 .

 51 If x k 2 2 . . . x kn n ∈ in(I(S) is part of a minimal generating system of in(I(S), then all the monomials with exponents in the cube [0; k 2 ] × . . . × [0; k n ] are not in in(I(S) except x k 2

Algorithm 5 . 2 .

 52 Frobenius MM-DD: Input: a 1 , . . . , a n Ouput: the Apéry set of S with respect to a 1 . The Frobenius number of S. Begin 1. sum = 1; test=false,testsum=false, Ap = {0}, Apmod = {0}. 2. while (sum ≤ a 1 ) and (testsum=false) do (a) for each monomial x k 2 2 . . . x kn n with k 2 + . . . + k n = sum

Example 5 . 5 .

 55 (a 1 = 1030, a 2 = 1031, a 3 =, 1034, a 4 = 1039, a 5 = 1046, a 6 = 1055, a 7 = 1066, a 8 = 1079, a 9 = 1094, a 10 = 1111, a 11 = 1130, a 12 = 1151, a 13 = 1373, a 14 = 1393, a 15 = 1423, a 16 = 1433, a 17 = 1493).

1 .

 1 Ap(S, a 1 ) = {k 2 a 2 + . . . + k n a n |x k 2 Ap(S, a 1 ), such that s = k 2 a 2 + . . . + k n a n and x k 2 2 . . . x kn n / ∈ in(I(S)). Suppose that s = l 2 a 2 + . . . + l n a n for some natural numbers l 2 , . . . , l n , then x k 2 2 . . . x kn n ≺ revlex x l 2 2 . . . x ln n .

	2 . . . x kn n / ∈ in(I(S))}. In particular
	card{x k 2 2 . . . x kn n / ∈ in(I(S))} =	a 1 gcd(a 1 , . . . , a n )	.
	2. Let s ∈

Proof. We can assume that gcd(a 1 , . . . , a n ) = 1.

1. By the above theorem

K[t a 1 , . . . , t an ] ≃ ⊕ s i ∈H K[t a 1 ][t s i ] where H = {k 2 a 2 + . . . + k n a n |x k 2 2 . . . x kn n /

∈ in(I(S))}, now we prove that H = Ap(S, a 1 ). Let s ∈ H suppose that s / ∈ Ap(S, a 1 ), hence sa 1 ∈ S, by the above decomposition there exists unique

(b) if n i=2 (k i + 1) ≤ a 1 + 1 then i. compute qsum := k 2 a 2 + . . . + k n a n and the congruence class mod a 1 , that is k 2 a 2 + . . . + k n a n mod a 1 ii. If qsum mod a 1 doesn't belongs to Apmod then Ap = Ap∪{qsum}, Apmod = Apmod ∪ {qsum mod a 1 }. iii. If qsum mod a 1 belongs to Apmod, let h ∈ Ap such that h = qsum mod a

. . x kn n with k 2 + . . . + k n = sum, we have that test=true then testsum=true.

(e) Otherwise testsum=false. sum = sum + 1.

f rob

End (of the algorithm).

The knapsack integer problem: Let b ∈ N, in order to know if b ∈ S we run the above algorithm, let h ∈ Ap such that b = h mod a 1 ,then b ∈ S if and only if b ≥ h.

Algorithm 5.3. Frobenius NoINI MM-DD:

Input: a 1 , . . . , a n Ouput: the Apéry set of S with respect to a 1 . The Frobenius number of S. The set of monomials in the variables x 2 , ..., x n not in the ideal in(I(S). Sumnoini the least upper bound for the usual degree of a minimal system of monomial generators of the ideal in(I(S) Begin

2. while (sum ≤ a 1 ) and (testsum=false) do (a) for each monomial x k 2 2 . . . x kn n with k 2 + . . .


Z Basrak
email: basrak@irb.hr

P Eudes
email: eudes@subatech.in2p3.fr

V De La Mota

F Sébille

G Royer

Scientific Workshop on Nuclear Fission dynamics and the Emission of Prompt Neutrons and Gamma Rays, THEORY-3 Impact of reaction cross section on the unified description of fusion excitation function

Keywords: Heavy-ion reactions, Intermediate energies, Fusion excitation function, Vanishing of fusion, Reaction cross sections

A systematics of over 300 complete and incomplete fusion cross section data points covering energies beyond the barrier for fusion is presented. Owing to a usual reduction of the fusion cross sections by the total reaction cross sections and an original scaling of energy, a fusion excitation function common to all the data points is established. A universal description of the fusion excitation function relying on basic nuclear concepts is proposed and its dependence on the reaction cross section used for the cross section normalization is discussed. The pioneering empirical model proposed by Bass in 1974 to describe the complete fusion cross sections is rather successful for the incomplete fusion too and provides cross section predictions in satisfactory agreement with the observed universality of the fusion excitation function. The sophisticated microscopic transport DYWAN model not only reproduces the data but also predicts that fusion reaction mechanism disappears due to weakened nuclear stopping power around the Fermi energy.

Introduction

The complex interplay between the one body (nuclear mean field) and the two-body (elementary nucleon-nucleon (NN) collisions) degrees of freedom governs the rich zoo of nuclear reaction mechanisms observed in the transition Fermi-energy region. Understanding the role of these two origins of energy dissipation in the course of heavy-ion reactions (HIR) is a long standing challenge put to nuclear models. Study of the fusion excitation function, both complete (CF) and incomplete (IF), and in particular shedding some light onto conditions of fusion disappearance, may be a useful tool to constrain the ingredients entering theoretical models used to describe HIR in this energy range. The modern dynamical models such as Sky3D by Maruhn et al. (2014), TDHF3D by Simenel (2012) Fig. 1. Raw fusion cross sections σ f plotted as a function of E inc . The inventoried systems are distinguished among them by symbols and a color code. The same symbols and the color code are used in Eudes et al. (2014-a) where an interested reader may find detailed information on energies, σ values, and references to original works. The dashed line and the dashed curve are intended to guide the eye only. Sébille et al. (2007) offer the promising theoretical frameworks to resolve above questions especially in selecting the most appropriate effective interaction, see e.g. Dutra et al. (2012), and an improved modeling of the NN collisions.

In two recent papers we have presented a systematic study of both CF and IF fusion cross sections σ f in the incident energy E inc = E lab /nucleon range of ∼3A -155A MeV, see Eudes et al. (2013Eudes et al. ( , 2014-a)-a). In total, from the literature published during the past 40 years, we have collected 382 CF and CF+IF σ f data points belonging to 81 reaction systems with a vast variety of projectile-target pairs, system mass asymmetry, system isospin content as well as in the large range of covered system masses A sys = 26 -278 nucleons.

Scaling of fusion cross sections

Discarding those σ f data points for which we have strong indication that the σ f value suffers from a non-fusion contribution, cf. in Eudes et al. (2013Eudes et al. ( , 2014-a)-a), or that other reaction mechanism has been erroneously identified as fusion, Eudes et al. (2014-b), one ends with 76 systems and 316 CF+IF σ f data points. These data, as a function of E inc , are displayed in figure 1. Clearly, most of these raw σ f data points gather in a narrow domain of the σ f vs E inc plane although the lighter systems (blue, cyan, and green symbols) gather along an arclike structure (see the dashed curve) while the heavier ones (pink, red, and orange symbols) follow a line which sharply rises with E inc (see the dashed line). The fact that systems of low and high mass A sys do not fall together is expected due to the known dependence of the fusion cross section on the system size. To remediate it, one normalizes σ f by the (total) reaction cross section σ r at the same E inc . The obtained σ f /σ r = σ n , as suggested by Lautesse et al. (2006), is in figure 2 plotted as a function of center-of-mass energy E c.m. = (E lab /A p ) (A p A t /A sys ), where A sys = A p +A t and A p (A t ) stands for projectile (target) mass. By the applied normalization, the huge difference between the lighter and the heavy systems in their dependence of the fusion σ f as a function of increasing energy of figure 1 is completely washed out: All the systems display a similar arclike dependence on energy although it seems that arcs are shifted along abscissae as a function of the increasing A sys . However, a scrutiny scan of the data reveals the true cause of this observed behavior. Systems of distinct arcs do not differ by their A sys but rather by their A p vs A t asymmetry. Defining abscissa in units of the so-called system available energy E av = E c.m. /A sys one does express the mass asymmetric systems on the same footing with those which are mass symmetric. The normalized σ n as a function of E av is displayed in figures 3 and 4. Disregarding for a while discussion of the different panels of these figures, one may draw a general conclusion: By properly reducing σ f values with σ r and by applying an original energy scaling, the fusion excitation function, irrespectively of the details of a given reaction system, follows a simple universal law. et al. (1996), and c) the Mixed approach (see text for details), respectively. The full red curve in each panel is due to a fit with the homographic function of Eq. ( 2), whereas the dashed black curve is due to the fit of panel c).

Reaction cross section

Besides on experimental uncertainties of σ f the exact parameter values of the observed universal fusion excitation function are somewhat dependent on the σ r -values used for the σ f normalization. In this contribution, we focus on Fig. 5. Ratios of experimental σ r and theoretical predictions for five models as a function of E av . Panels display σ r ratios with the models of a) [START_REF] Bass | Nuclear Reactions with Heavy Ions[END_REF], b) Gupta and Kailas (1984), c) Kox et al. (1987), d) Shen et al. (1989), and e) Tripathi et al. (1996). An interested reader may find detailed information on experimental σ r and references to original works in Eudes et al. (2014-a).

the data normalization problem and the impact of the implemented σ r . Accurate measurement of the total σ r is rather hard so that these data are scarce and it would be inappropriate to apply them to the ensemble of the collected σ f data. Therefore, one commonly resorts to phenomenological approaches to calculate σ r , a solution which suffers for its own uncertainties and ambiguities. Thus, the uncertainty arising from the use of a particular parameterization of σ r has to be investigated. Among a number of phenomenological parameterizations of σ r we have investigated five of them due to [START_REF] Bass | Nuclear Reactions with Heavy Ions[END_REF]; Gupta and Kailas (1984); Kox et al. (1987); Shen et al. (1989); Tripathi et al. (1996), i.e. in this study we have included the pioneer one due to [START_REF] Bass | Nuclear Reactions with Heavy Ions[END_REF] and the most recent one by Tripathi et al. (1996). All these approaches rely on the strong absorption picture of nuclear processes and differ among themselves in the way the basic relation

σ(E) = π R 2 (1 - V E ) (1)
is parameterized. In Eq. ( 1), the cross section depends on the inverse of energy E while the radius R and the potential depth V may be, in a first approximation, considered as a constant for a given system. Various models differ in the treatment of R and V by introducing or not a certain dependence on energy and/or on some other system properties, usually A p or A sys , to the one or both of them. In order to infer reliability of each of the models, in figure 5 we compare them with 134 experimental σ r measured for 46 systems.

From figure 5, one may infer that some of the models, on the average, overpredict σ r . This conclusion is made plausible by projecting the σ r -ratio values onto the ordinate of each of the panels. The resulting histograms are shown in figure 6. The hollow histograms display the projections of the full σ r data set, i.e. at all E av . The yellow and the hashed histograms refer to the projections of the σ r -ratio values above and below E av = 2 MeV/nucleon, respectively. Clearly, the Bass approach strongly and the Kox one moderately overpredict the measured σ r at all E av , whereas parameterizations of Eq. ( 1) by Shen et al. (1989) and by Tripathi et al. (1996) moderately overpredict σ r for E av 2 MeV/nucleon and the one by Gupta and Kailas (1984) at energies E av 2 MeV/nucleon. By investigating the projection histograms in some detail, we heuristically define the most appropriate combination of model predictions. So, the Mixed σ r is defined as follows

σ r (Mixed) = ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ σ r (T ripathi), f or E av < 2 MeV/nucleon, A sys < 86 σ r (Gupta), f or E av < 2 MeV/nucleon, A sys ≥ 86 1 2 [σ r (T ripathi) + σ r (S hen)],
f or E av ≥ 2 MeV/nucleon, all A sys . With no doubt, from figure 6, one infers that the heuristic Mixed choice for the normalization σ r reproduces on the best manner the experimental σ r -values regarding both the centroid and the width of the distribution histogram, see panel f) of figure 6.

Let us discuss figures 3 and 4 in some detail. In figure 3 shown are normalizations with σ r of Bass, Gupta, and Kox, respectively and in figure 4 those with σ r of Shen and that of Tripathi as well as the one labeled Mixed obtained by a heuristic approach. These plots corroborate the conclusion that the Mixed σ r is the best choice for the normalization of fusion σ f . It is interesting to note that in figures 3 two of the models violate the normalization condition. In fact, out of the 316 data points in the case of Gupta and that of Kox (panels b) and c) in figures 3, respectively) 2 and 41 points, respectively violate the physically allowed range for the normalized cross section values σ n = σ f /σ r , namely between 0 and 1. All these points are due to σ n overflow that occurs at low energies.

Fitting the universal fusion excitation function

Assuming the applicability of the strong absorption concept, in the first approximation both σ f and σ r may be expressed by the same functional form given by Eq. ( 1). Consequently, for the reduced cross section one gets a simple homographic law

σ n (E) = σ f (E) σ r (E) = a + b c + E , ( 2
)
where a, b, and c are free parameters and E is taken as E av , cf. in Eudes et al. (2013Eudes et al. ( , 2014-a)-a). The σ n data points of each panel of figures 3 and 4 have been fitted with the three-parameters homographic function of Eq. ( 2). The obtained best fit result is displayed by the red full curve for each σ n . Interestingly enough, independently of the σ r chosen for the normalization procedure, the best fit curve gives for the energy of disappearance of the CF+IF fusion process the same value: E av = 12.98 ± 0.06 MeV/nucleon. Also, at low energy, all the best fit curves overlap. The fit results of different normalization cases disagree by at most about 5 % of σ n and this occurs at intermediate values of E av . That may be easily inferred by the dashed black curve that is drawn in each panel of figures 3 and 4 and which represents the best fit result in the case of the heuristic (Mixed) σ r . Although the best fit result does not depend strongly on the details of the σ r parameterization, this subject is open to further investigation. However, the homographic functional law of Eq. ( 2) seems to be established without any doubt.

Predicted fusion cross sections

Theoretical approaches suitable to predict the fusion cross sections well above the fusion barrier are rather scarce. Among the approaches in closed empirical form which is well adjusted for the massive calculation of σ f we have investigated two models, those by Bass (1974Bass ( , 1977) ) and by Matsuse et al. (1982). It has to be mentioned that these models, and in particular the one by Matsuse et al. (1982), have not been tested on a large number of HIR and especially not for the rather vast span of reaction characteristics that the present collection of σ f data points covers. Anyway, in figures 7 and 8 are presented the σ f -values predicted by these two models when for the normalization are taken the σ r -values calculated according to [START_REF] Bass | Nuclear Reactions with Heavy Ions[END_REF], Kox et al. (1987) and Tripathi et al. (1996). The predictions of Bass (1974Bass ( , 1977) ) rather well reproduce the general trend of the excitation function although the σ n -values for each of the normalizations used overpredict data for E av > 8 MeV/nucleon, cf. in figure 7. Generally speaking, these normalized cross sections split into two more or less distinct branches that overlap at the extreme values of E av . In the calculation of σ r , the friction parameter of the Bass model has been fixed to the recommended value, i.e. to 5/7. By varying the value of this parameter and/or by introducing an additional degree of liberty into the model one may hope to bring the model prediction to the full homographic universality of the experimental data. In the case of σ f by Matsuse et al. (1982) the normalized σ n is almost constant for E av > 3 MeV/nucleon and amounts between 20 % and 27 % of the total reaction σ r at the highest energy considered, cf. in figure 8. Such a result suggests that the fusion reaction mechanism would be present at any E inc . We mention that with σ f of Bass (1974Bass ( , 1977) ) the normalization condition 0 ≤ σ n ≤ 1 is violated at 9 of 316 points in the case of σ r by Kox et al. (1987), whereas for σ f of Matsuse et al. (1982) the normalization is always violated -for 8, 29 and 16 points when σ r is calculated by [START_REF] Bass | Nuclear Reactions with Heavy Ions[END_REF], Kox et al. (1987) and Tripathi et al. (1996), respectively.

Another possible way in reproducing fusion excitation function offer various dynamical simulations of HIR. This approach is, however, extremely demanding in the CPU time because the simulation has to be carried out at a number of the reaction impact parameters in fine step and at each energy under study. That is why these models have essentially been used to qualitatively study the phenomenon of heavy-ion fusion while the rare example of the published quantitative studies of fusion excitation function by microscopic transport theories are with the BUU model by Xu et al. (1990), the Landau-Vlasov (LV) model by Eudes et al. (2013), the SMF model by Shvedov et al. (2010) and the DYWAN model by Eudes et al. (2013). The BUU and LV models completely fails in reproducing both absolute values and trends of our universal fusion excitation function given by the homographic law of Eq. ( 2), cf. in Eudes Bass (1974Bass ( , 1977) ) model for the data points of figures 1 and which are normalized by σ r calculated with a) [START_REF] Bass | Nuclear Reactions with Heavy Ions[END_REF], b) Kox et al. (1987) and c) Tripathi et al. (1996) 2). The light-violet background band around the best fit curve is due to the errors on the fit parameters. The full red curve in the main panel is due to the same kind of fit to CF+IF data of the Mixed σ n , in fact, the best fit curve of panel c) of figure 4. The dashed blue curve is the difference of both fusion excitation functions. The open symbols refer to the 14 systems studied experimentally. An interested reader may find detailed information on energies, σ f -values, and references to original works in Eudes et al. (2014-a). The black filled symbols are result of σ f as predicted by the DYWAN model of Sébille et al. (2007). The inset displays the ratio of CF and CF+IF best-fit excitation functions as a function of E av .

field and a still insufficient stopping efficiency of NN collisions, cf. in Eudes et al. (2013). The phenomenon of the nuclear (pseudo)transparency has been predicted for HIR in the Fermi-energy range a long time ago, see Eudes et al. (1997); Basrak (2004); Novosel et al. (2005), but it received only recently an experimental confirmation, see Lehaut et al. (2010).

Complete and incomplete fusion cross section

Only twelve experiments have explicitly been designed to measure both complete and incomplete fusion components, cf. in Eudes et al. (2013Eudes et al. ( , 2014-a)-a). These 57 CF σ n data points belonging to the 14 reaction systems and obtained with the heuristic σ r discussed above are displayed in figure 9 as a function of E av . The same homographic law of Eq. ( 2) used in fitting the CF+IF data is here used to obtain the best fit result to the CF data. It is shown by the full violet curve. The used fitting code by James and Roos (1975) provides an uncertainty on the fit parameters a, b, and c. These uncertainties define the light-violet background drawn around the best fit curve. Owing to the rather large experimental error bars and the relatively small number of data points the energy of CF disappearance is not very accurately defined. It reads E av = 6.2 +1.3 -1.1 MeV/nucleon. Similarly, CF data display a stronger dependence on the normalization σ r used. However, the deduced energy of CF disappearance for each of the σ r used lays well within the above stated uncertainty limits.

In figure 9 by the full red curve is shown the best fit result with the heuristic (Mixed) σ r of panel c) of figure 4. Making difference of the violet CF and the red CF+IF best fit homographic functions allows to infer the main proper-ties of the incomplete fusion excitation function: IF process opens around E av ≈ 1.5 MeV/nucleon, reaches maximal value at the energy of CF disappearance (E av ≈ 6 MeV/nucleon), and vanishes at E av ≈ 13 MeV/nucleon. An inset displays how the best-fit CF excitation function decreases relatively to the CF+IF one, an observable which has been investigated a long time ago by Morgenstern et al. (1984) who have concluded that the mass asymmetry has a strong influence on the onset of incomplete fusion and on the limiting energy of complete fusion.

Conclusions

To summarize, the scrutiny of the existing fusion cross sections well above the reaction barrier allowed us to establish a universal dependence of these data on energy. The established homographic functional description of both the complete and the complete plus incomplete fusion excitation functions is rather stable and the inferred global features of these excitation functions quite weakly depend on the details of the reaction cross section used for data normalization. Nevertheless, the normalization may be improved if additional high quality measurements on both fusion and reaction cross section would be available. The universality of the obtained fusion excitation functions offers an easily applicable check on the reliability of nuclear models. It comes out that the old and rather simple empirical model developed by Bass (1974) which is relying on the concepts of the strong nuclear absorption quite well reproduces the CF+IF fusion excitation function, although the model has been developed to describe the CF only. Most of the much more sophisticated dynamical models fails to reproduce the observed features of fusion. Among these approaches, so far, only the DYWAN model of Sébille et al. (2007) has been able to provide a convincing result in interpreting fusion cross sections.

Fig. 2 .

 2 Fig. 2. Normalized fusion cross sections σ n plotted as a function of E c.m. .

Fig. 3 .

 3 Fig.3. Normalized fusion cross sections σ n plotted as a function of E av . The σ r used for normalization is due to a)[START_REF] Bass | Nuclear Reactions with Heavy Ions[END_REF], b)Gupta and Kailas (1984), and c)Kox et al. (1987), respectively. The full red curve in each panel is due to a fit with the homographic function of Eq. (2), whereas the dashed black curve is due to the same kind of fit of panel c) in figure4.

Fig. 4 .

 4 Fig. 4. Normalized fusion cross sections σ n plotted as a function of E av . The σ r used for the normalization is due to a) Shen et al. (1989), b) Tripathiet al. (1996), and c) the Mixed approach (see text for details), respectively. The full red curve in each panel is due to a fit with the homographic function of Eq. (2), whereas the dashed black curve is due to the fit of panel c).

Fig. 6 .

 6 Fig.6. Histograms of the ratios between the experimental σ r and the σ r -values calculated by the models of a)[START_REF] Bass | Nuclear Reactions with Heavy Ions[END_REF], b)Gupta and Kailas (1984), c)Kox et al. (1987), d)Shen et al. (1989), e)Tripathi et al. (1996) and the Mixed one. The yellow and the hashed histograms refer to the projections of the σ r -ratio values above and below E av = 2 MeV/nucleon, respectively.

Fig. 7 .

 7 Fig.7. The predicted σ f by theBass (1974Bass ( , 1977) ) model for the data points of figures 1 and which are normalized by σ r calculated with a)[START_REF] Bass | Nuclear Reactions with Heavy Ions[END_REF], b)Kox et al. (1987) and c)Tripathi et al. (1996) models. To guide the eye in each panel is plotted the best fit curve of panel c) of figure 4.

Fig. 8 .Fig. 9 .

 89 Fig.7. The predicted σ f by theBass (1974Bass ( , 1977) ) model for the data points of figures 1 and which are normalized by σ r calculated with a)[START_REF] Bass | Nuclear Reactions with Heavy Ions[END_REF], b)Kox et al. (1987) and c)Tripathi et al. (1996) models. To guide the eye in each panel is plotted the best fit curve of panel c) of figure 4.

AVAILABLE ENERGY (MeV/nucleon) Bass Kox Tripathi a) b) c) 14N+12C 20Ne+16O 24Mg+12C 12C+27Al 16O+24Mg 20Ne+20Ne 28Si+12C 16O+26Mg 18O+24Mg 16O+27Al 32S+12C 20Ne+26Mg 20Ne+27Al 20Ne+27Al 35Cl+12C 16O+32S 16O+40Ca 28Si+28Si 28Si+28Si 32S+24Mg 19F+40Ca 32S+27Al 35Cl+24Mg 12C+48Ti 23Na+40Ca 16O+48Ti 40Ar+27Al 28Si+40Ca 12C+58Ni 36Ar+KCl 12C+63Cu 40Ar+40Ca 40Ca+40Ca 58Ni+27Al 24Mg+63Cu 48Ti+45Sc 36Ar+58Ni 16O+92Mo 32S+76Ge 40Ar+68Zn 52Cr+56Fe 19F+93Nb 64Zn+48Ti 58Ni+58Ni 18O+100Mo 78Kr+40Ca 82Kr+40Ca 12C+124Sn 14N+124Sn 20Ne+124Sn 40Ar+109Ag 84Kr+65Cu 40Ar+116Sn 40Ar+121Sb 16O+146Nd 132Xe+30Si 40Ar+124Sn 14N+154Sm 14N+159Tb 16O+159Tb 20Ne+159Tb 58Ni+124Sn 20Ne+169Tm 12C+182W 19F+175Lu 40Ar+154Sm 14N+181Ta 16O+181Ta 40Ar+164Dy 24Mg+181Ta 40Ar+165Ho 12C+197Au 14N+197Au 16O+197Au 16O+197Au 20Ne+197Au 40Ar+197Au 14N+232Th 40Ar+238U


domain: math spi stat

text:
Giacomo Bacci
email: gbacci@mbigroup.it

Luca Sanguinetti
email: luca.sanguinetti@unipi.it

Marco Luise
email: marco.luise@unipi.it

Understanding Game Theory via Wireless Power Control

In this lecture note, we introduce the basic concepts of game theory (GT), a branch of mathematics traditionally studied and applied in the areas of economics, political science, and biology, which has emerged in the last fifteen years as an effective framework for communications, networking, and signal processing (SP). The real catalyzer has been the blooming of all issues related to distributed networks, in which the nodes can be modeled as players in a game competing for system resources. Some relevant notions of GT are introduced by elaborating on a simple application in the context of wireless communications, notably the power control in an interference channel (IC) with two transmitters and two receivers.

RELEVANCE

 have attracted a significant interest by the wireless communications and SP engineering communities [2, Part II], due to the need for designing autonomous, distributed, and flexible systems, in which the available resources are allocated through low-complexity and scalable procedures. Games are appealing, owing to some characteristics that are not common in classical optimization: as an example, GT can handle interactive situations in which each player can only have a partial control over the optimization variables, while using its own performance metric. It is true that commonalities can be found with other disciplines, such as multi-objective optimization [3], convex optimization [4], and learning theory [5], but GT possesses many distinguishing features that make it essential for the standard current toolbox of communication as well as SP engineers.

PREREQUISITES

The readers require basic knowledge in linear algebra and wireless communication theory.

WHAT IS A GAME?

To take advantage of GT and its associated theoretical tools, the first step is to model the problem at hand as a game. In doing so, three ingredients must be identified:

• the players, that represent the main actors in the problem, having conflicting interests and affecting the performance of everyone else in the game;

• a set of strategies available to each player, that determines what each player can do;

• a utility function for each player, that measures its degree of satisfaction as a function of the combination of all player's choices.

This description may encompass a large number of situations: to mention a few examples, players in a game can be base stations (BSs) allocating the resources in a cellular network to increase the system throughput, or watermarking devices choosing algorithms to face potential attackers.

The objective of the modeling effort is to describe the game using its strategic-form representation: a triplet ⟨K, {S k } k∈K , {u k } k∈K ⟩, where: K = {1, . . . , K} is the set of players, where K is the number of players; S k is the set of strategies for each player k; and u k (s) is the utility function (also known as reward or payoff ) associated to player k for a combination of choices s = [s 1 , . . . , s K ] = [s k , s \k ], where s \k = [s 1 , . . . , s k-1 , s k+1 , . . . , s K ] denotes the strategies taken by all other players except player k (the opponents).

In general, the game outcome u k (s) for player k depends on all players' choices through s, that stems out from the interaction of the players with possibly conflicting interests. This brings forth a couple of distinguishing features of GT:

• each player k can have a different performance metric; this feature is captured by a per-player specific function u k (s), that accounts for the player's nature;

• each player k has partial control (s k ∈ S k only) over the optimization variables.

The first property is strictly tied with multi-objective optimization [START_REF] Björnson | Multi-objective signal processing optimization: The way to balance conflicting metrics in 5G systems[END_REF], although a clear difference exists in the scope of the optimization variables, as in multi-objective optimization we have full control over the variables. The second property is tightly related to the framework of distributed optimization [START_REF] Scutari | Convex optimization, game theory, and variational inequality theory[END_REF], with which it shares many intersections, although there are specific differences: one of the most important is that, while in distributed optimization the agents follow some common given rules, in GT the players act as independent decision-makers.

THE NEAR-FAR EFFECT (NFE) GAME

To picture out the meaning of the strategic-form representation, let us consider an example taken from a very common wireless communications scenario: the IC, represented in Fig. 1a, in which the two transmitters interfere with each other in the attempt to reach their own receiver. This simple scheme encompasses many scenarios: it can be used to model i) a multicellular system, with red and blue nodes belonging to two different cells; ii) a heterogeneous network, where the red and blue nodes belong to a macro cell and a small cell, resp.; iii) a cognitive radio system, where the red and blue nodes are primary users (PUs) and secondary users (SUs), resp.; and iv) a device-to-device system, where the receivers are also network nodes.

Using GT, we can i) model the problem at hand in a suitable manner, and ii) provide the theoretical tools to solve it. In this case, solving means devising the optimal transmission strategy to be selected by the two wireless terminals of Fig. 1a. In particular, we assume that the two nodes are allowed either to transmit at a certain power level p, or to stay idle. This situation can be modeled as a game, with K = 2 players, and strategy sets S k = {0, p} for k ∈ K = {1, 2}. For simplicity, we also assume that the two terminals choose their strategies simultaneously (i.e., without being informed of the other's choice) once and for all (i.e., they cannot make any change after observing the outcome of the game) -in GT parlance, we consider a static game. Finally, since players and strategy sets are both countable, the game is finite.

As depicted in Fig. 1a, player 1 (the far terminal) is located much farther away from both receivers than player 2 (the near terminal). To describe this situation in a mathematical fashion, we introduce the power gains h jk ∈ R + experienced by terminal k's signal when propagating to receiver j. For simplicity, let us assume h jk = h k for j = 1, 2 with h 1 /h 2 ≪ 1 (we will better quantify this ratio later on), thereby giving rise to the so-called near-far problem.

We need now to define a utility function, and to do so we consider that each terminal achieves a degree of satisfaction that depends both on the success of its transmission and on the energy spent to transmit at power s k . Mathematically, this translates here into a (dimensionless) utility u k (s) = t k (s)c k (s), where t k (s) accounts for the outcome of the transmission, and c k (s) measures the cost associated to using s k .

We assume that the cost scales linearly with the transmit power, and that it is independent of the other terminal's strategy: c k (s) = cs k /p. Measuring t k (s) is more complicated, as it has to capture the interaction between the players as a function of the selected strategies s 1 and s 2 . In practice, successful reception of a signal in a multiple-access scenario (such as the one considered here), be it in the time, frequency, space, or code domain, depends on the signal-to-interference-plus-noise ratio (SINR) γ k , which measures the ratio of the useful received signal power to the amount of undesired power collected at the receiver. Under the assumption of additive white Gaussian noise (AWGN) with power σ 2 , we get

γ k (s) = Γh k s k σ 2 + h \k s \k = µ k (s \k )s k ≥ 0, (1)
where

\k = 2 if k = 1, \k = 1 if k = 2,
and Γ ≥ 1 is the processing gain, that depends on the multiple access technology and on the receiver processing. For the time being, let us assume the transmission to be successful if and only if γ k ≥ γ req , where the minimum SINR γ req depends on some system parameters.

So, when γ k < γ req , the transmitted message cannot be decoded at receiver k, and t k (s) = 0. On the contrary, when γ k ≥ γ req , receiver k can correctly receive the information associated to user k's signal, and

t k (s) = t,
where t is a dimensionless parameter that accounts for the throughput achieved at destination.

To properly capture the cost-benefit analysis that regulates any practical wireless system, it makes sense to assume t ≫ c.

A profitable way to investigate finite static games in their strategic form, such as our NFE game, is through the so-called payoff matrix (Fig. 1b) in which player 1's strategies are identified by the rows, player 2's strategies by the columns, and the entries of the matrix (the pair of numbers in the box) represent the utilities (u 1 (s) , u 2 (s)) achieved by the players. Under the assumptions that p = σ 2 h1Γ γ req and h1 h2 < 1 1+γreq/Γ (see [START_REF] Bacci | How to use a strategic game to optimize the performance of CDMA wireless network synchronization[END_REF] for further details), it is easy to fill out each box of the matrix based on the hypotheses listed above.

Once the game is in its strategic form, we have to solve it, i.e., to predict its outcome. In the NFE game, we assume that both players: i) are rational; ii) control their own strategies only; and iii) know each other's payoff. The first assumption means that each player is a utility-maximizer decision maker. The second hypothesis casts this problem as a noncooperative game, in which the players compete to unilaterally maximize u k (s). Finally, the third hypothesis involves the concept of complete information that each player has about the game. By inspecting the payoff matrix in Fig. 1b, it is apparent that player 2's best strategy is represented by s ⋆ 2 = p whatever s 1 is, since tc > 0 under the assumption t ≫ c. For this reason, the player 1

player 2 0 0 p p 0, 0 0, t -c t -c, 0 -c, -c u 1 (s), u 2 (s)
Fig. 2: Payoff matrix of the IC game.

strategy s 2 = 0 is said to be strictly dominated by

s 2 = p, as u 2 ([s 1 , 0]) < u 2 ([s 1 , p]) ∀s 1 ∈ S 1
. This is known to player 1 as well, that rationally chooses to play s ⋆ 1 = 0. As a conclusion, the predictable outcome of the NFE game is

s ⋆ = [s ⋆ 1 , s ⋆ 2 ] = [0, p],
as highlighted by the shaded box in Fig. 1b. In GT parlance, this game has been solved by applying the iterated elimination of dominated strategies, or iterated dominance

for short [1, Ch. 1].

THE IC GAME

Let us now slightly modify the scenario represented in Fig. 1a. Assume for example to move player 1 closer to its receiver, such that the distance between player 1 and both receivers becomes the same as the distance between player 2 and both receivers. For simplicity, let us also suppose h jk = h for j, k = 1, 2. By using p = σ 2 hΓ γ req , following the same considerations taken for the NFE game, it is easy to obtain the payoff matrix reported in Fig. 2. As an exercise, we can verify that no strictly dominated strategies exist, and thus we cannot apply the iterated dominance procedure used to solve the NFE game.

To get out of this impasse, we introduce the concept of best response (BR) b k (s \k ), which is mathematically defined as:

b k (s \k ) = arg max sk∈Sk u k [s k , s \k ] , (2)
i.e., the best that we can get out of the game once we know the opponents' moves s \k . Since player 1 chooses rows, we can compute its BR by examining the columns that can be possibly selected by player 2.

When

s 2 = 0, b 1 (s 2 = 0) = p. Conversely, when s 2 = p, b 1 (s 2 = p) = 0.
The same can be obtained for player 2, and we end up with the players' BRs, underlining the relevant payoffs in Fig. 2. We find two boxes (shaded background) containing the BRs of both players, representing two stable states, where "stable" here means that such states are attained by some multiple agents with conflicting interests that compete through self-optimization, and eventually reach a point where none of them has any incentive to unilaterally deviate from.

A point that possesses such properties is termed a Nash equilibrium (NE) of the game, defined as a

strategy profile s ⋆ = [s ⋆ k , s ⋆ \k ] such that, for all k ∈ K, u k [s ⋆ k , s ⋆ \k ] ≥ u k [s k , s ⋆ \k ] ∀s k ∈ S k , (3)
or, equivalently, s ⋆ k ∈ b k (s ⋆ \k ). As an exercise, check that s ⋆ = [0, p] is the unique NE of the NFE game. The notion of NE encompasses many interpretations of GT, not discussed here for brevity, that the interested readers can find in many textbooks (e.g., [START_REF] Lasaulce | Game Theory and Learning for Wireless Networks: Fundamentals and Applications[END_REF]Ch. 1]). Modeling the players as self-optimizing decision-makers finds a suitable application especially in the context of SP, in which the devices can be programmed to do so. Since each player has only a partial control of the game, the concept of NE is tightly coupled with the application of distributed algorithms and machine learning techniques [START_REF] Lasaulce | Game Theory and Learning for Wireless Networks: Fundamentals and Applications[END_REF]Part II].

For brevity, we will not discuss here theorems on equilibrium existence [1, Ch. 1], that establish the existence of the NE in particular classes of games, and on equilibrium uniqueness

INTRODUCING CONTINUOUS POWERS

The solutions of NFE and IC games, in which at most one terminal can successfully transmit, directly stem out of choosing a binary strategy set S k = {0, p} for both players. Let us see what happens if any power level in the continuous interval [0, p] can be selected. This amounts to setting S k = {s k ∈ R : 0 ≤ s k ≤ p}. Within this setting, the power control problem can be studied as a continuous game [7, Ch. 2]. In our attempt of getting closer to a realistic scenario, let us also modify the utilities to better model how real data networks work in practice. A good approximation for the effective throughput in a packet-

oriented transmission is t k (s) = t (1 -exp{-γ k (s)}) L [8]
, whose behavior is depicted (red line, left axis) in Fig. 3. In our expression, L denotes the number of information bits per packet (here, L = 20), and t is the communication rate (in b/s). To properly capture the tradeoff between obtaining a satisfactory throughput and saving transmit power -similarly to what considered for the NFE and IC games -, we will adopt a "green" approach, based on improving each player's energy efficiency [START_REF] Meshkati | Energy-efficient resource allocation in wireless networks[END_REF]. This can be done by defining player k's utility as the ratio between throughput and power expenditure, thus accounting for the number of bits correctly delivered per joule of energy consumed:

u k (s) = t k (s)/s k [b/J], (4)
whose normalized behavior is reported (blue line, right axis) in Fig. 3, with µ k (s \k ) defined as in [START_REF] Fudenberg | Game Theory[END_REF].

Using straightforward manipulation, player k's BR (2) turns out to be b k (s \k ) = min{p, γ ⋆ k /µ k (s \k )}, where γ ⋆ k is the "optimal" SINR such that ∂t k (s)/∂γ k (s [START_REF] Meshkati | Energy-efficient resource allocation in wireless networks[END_REF]. For instance, when L = 20, we get γ ⋆ k 4.5 = 6.5 dB for k = 1, 2 (see Fig. 3). Based on such BR, the continuous IC game presents a unique NE, represented by the fixed point s ⋆ k = b k (s ⋆ \k ) for k = 1, 2 [START_REF] Meshkati | Energy-efficient resource allocation in wireless networks[END_REF]. How can the NE be "visualized"? Let us consider a particular realization of the network sketched in Fig. 1a, with the following parameters:1 h 11 = 0.75, h 21 = 0.25, h 12 = 0.5, h 22 = 1; Γ = 4; p/σ 2 = 5;

)| γk(s)=γ ⋆ k = 1 γ ⋆ k t k (s)| γk(s)=γ ⋆ k
and L = 20. The solution of this game is given by the NE s ⋆ /σ 2 = [2.99, 1.97], yielding normalized utilities

σ 2
t u 1 (s ⋆ ) = 0.269 and σ 2 t u 2 (s ⋆ ) = 0.407. We display in Fig. 4 the (normalized) utilities at the NE (green diamond) on the bidimensional normalized utility plane, given by all achievable utility pairs (u 1 (s), u 2 (s)) (shaded region), for any strategy profile s ∈ S 1 × S 2 (the utility plan can be found via a numerical search using [START_REF] Bacci | MATLAB code[END_REF]). Note that s ⋆ 1 > s ⋆ 2 , and u 1 (s ⋆ ) < u 2 (s ⋆ ): this is due to the better channel conditions experienced by player 2 (both in the direct and the interference links), that make it achieve the optimal SINR γ ⋆ 2 with a lower power consumption than player 1. However, unlike the finite version of the NFE game, where s ⋆ 1 = 0 (and thus t 1 (s ⋆ ) = 0), now player 1 can successfully connect to its receiver, getting a throughput t 1 (s ⋆ ) 0.8t (the same as t 2 (s ⋆ )), at the cost of a slightly higher power consumption (s ⋆ 1 /s ⋆ 2 1.52), and thus with a lower energy efficiency.

IS THE NE EFFICIENT?

A natural question that arises regards the actual efficiency, or, the performance, if you wish, of the NE.

To address this question, we first need to agree upon our performance metric. In GT, a convenient way to assess how desirable a solution is involves the concept of efficiency, evaluated in terms of Pareto optimality.

A profile s is Pareto-optimal (PO) if there exists no other s such that i) u k (s) ≥ u k (s) for all k ∈ K, and ii) u k (s) > u k (s) for some k ∈ K. In our continuous IC game, the performance achieved by the PO profile set is represented by the contour of the shaded area of Fig. 4, which is called the Pareto frontier. Clearly, if we increase u 1 (s) (i.e., if we move rightward along x), then u 2 (s) decreases, and the same happens if we increase u 2 (s) (by moving upward along y). Still, Pareto optimality does not qualify as our performance metric.

We have to further introduce the notion of social welfare (SW), that is often used as a convenient measure for the efficiency of a strategy vector [START_REF] Lasaulce | Game Theory and Learning for Wireless Networks: Fundamentals and Applications[END_REF]Ch. 2]. Formally, the social-optimal (SO) profile š is the PO profile that maximizes the SW, defined as the weighted sum-utility k∈K w k u k (s), where the weights {w k } k∈K , k∈K w k = 1, allow us to account for different classes of service: as an example, unequal weights can be useful to model PUs (higher w k 's) and SUs (lower w k 's) in a cognitive network. In our two-player game, we can identify š as the tangent point between the Pareto frontier and a line with slope -w 1 /w 2 . As an example,

REPEATING THE GAME

The inefficiency of the NE is mainly due to the selfish behavior (in the sense of self-optimization) of the players. An effective method to induce cooperation -while maintaining the noncooperative nature of the interaction -is forcing the players to interact more than once. A typical example of this approach is a repeated game, in which a static game is repeated N times. For instance, assume that the two transmitters of Fig. 1a interact a number N of times, each time selecting their optimal transmit powers s k (n), where n is the time index [START_REF] Treust | A repeated game formulation of energy-efficient decentralized power control[END_REF]. When introducing the notion of time, each strategy set S k becomes a complete plan of actions, that depends on the unfolding of the game through time.

Similarly, the utility functions must account for i) the partial utilities

u k (s(n)) = t k (s(n))/s k (n) received
at each stage n of the game, with s(n) denoting the profile selected by the players at time n; and ii) how much past utilities should be weighted (i.e., decay) compared to present ones. A simple example is the exponential decay, where the utility at time n is weighted by the factor δ n , 0 ≤ δ ≤ 1, and the total utility after N repetitions of the game is u N k (s) = N n=0 δ n u k (s(n)). By letting N → ∞, we further define a normalized utility u δ k (s) = (1-δ) +∞ n=0 δ n u k (s(n)) [START_REF] Treust | A repeated game formulation of energy-efficient decentralized power control[END_REF]. The parameter δ is the so-called discount factor, and its meaning is borrowed from micro-economics: a payoff received at the present time n is larger by a factor 1/δ than the payoff of the next stage, and smaller by a factor δ than that of the previous one. This means that, if players are patient (in the SP and communications context, delay-tolerant), δ is typically close to 1. Conversely, if players are impatient (i.e., delay-sensitive), δ is typically close to 0.

Extending the concept of NE to repeated games [1, Ch. 5], we can show that the optimal strategy s δ = {s δ (n)} +∞ n=0 is for both players to select s δ k (n) = šk if s δ k (n -1) = šk and s δ \k (n -1) = š\k , and s δ k (n) = s ⋆ k otherwise, with s δ k (0) = šk , and š and s ⋆ being the SO and NE points, respectively, provided that δ ≥ δ (i.e., if they are delay-tolerant enough), where δ is a function of the network parameters [START_REF] Treust | A repeated game formulation of energy-efficient decentralized power control[END_REF]. In other words, in the repeated IC game, cooperation is enforced by letting the players interact an indefinite number of times: this is successful due to threatening future punishments for the player(s) who defect.

The effectiveness of this approach is apparent in Fig. 4, where the performance of s δ , represented by the black asterisk, coincides with the SW, under the assumption δ ≥ δ. As a drawback, players must have knowledge of š: this only occurs if each player k knows all channel gains {h jk } j,k∈K , which might not be viable for all scenarios (e.g., in a cognitive network). Repeated games are a subclass of dynamic games, that are often used in SP problems to account for time evolution (see [START_REF] Lasaulce | Game Theory and Learning for Wireless Networks: Fundamentals and Applications[END_REF]Ch. 3] for more details).

INTRODUCING COOPERATION AMONG THE PLAYERS

In the techniques considered so far, we have focused on improving the efficiency of the solution, without considering any fairness issue. In the example above, the SW is obtained by favoring player 2 to the detriment of player 1's performance, as is apparent in the inset of Fig. 4, where the SW is far away from the projection of the NE over the Pareto frontier -obtained intersecting it with the "fair" line with slope 1 and passing through (u 1 (s ⋆ ), u 2 (s ⋆ )). We can balance efficiency and fairness by explicitly introducing cooperation among the players, assuming some explicit exchange of information. The fundamental difference of a cooperative approach is that, while in the games assumed so far cooperation can only be induced as the result of matching it with self-optimization (i.e., unilateral deviations are not beneficial anyway), now the players are willing to cooperate, as they know that they can mutually benefit from reaching an agreement.

In GT parlance, this is called a bargaining problem [2, Ch. 7], whose analytical tools are tightly related to SP techniques, such as consensus algorithms [START_REF] Olfati-Saber | Consensus and cooperation in networked multi-agent systems[END_REF].

Consider again the continuous IC game, and assume that the players can collaborate to select a satisfactory profile ṡ ∈ S 1 ×S 2 . In case they fail to reach an agreement, each player k gets u k (s ⋆ ), where s ⋆ is the NE of the noncooperative game studied before. On the contrary, the players now strive to attain the Nash bargaining solution (NBS), i.e., the (unique) PO profile that satisfies ṡ = arg max s∈S 2 k=1 (u k (s)u k (s ⋆ )), where the subset S ⊆ S 1 × S 2 is such that u k (s) ≥ u k (s ⋆ ) for all k ∈ K and s ∈ S. Interestingly, the NBS has close analogies with proportional fair allocation mechanisms, as discussed in [START_REF] Han | Game Theory in Wireless and Communication Networks: Theory, Models and Applications[END_REF]Ch. 7]. As is apparent, the NBS tries to increase as much as possible the utilities of the players with respect to the NE in a fair manner.

The graphical interpretation of the NBS is shown in Fig. 4: the NBS ṡ corresponds to the profile such that (u 1 (ṡ), u 2 (ṡ)) is the point of tangency between the Pareto frontier and the hyperbola with vertex in x = u 1 (s ⋆ ) and y = u 2 (s ⋆ ). Hence, the point of tangency lies by definition in the Pareto improvement region, as illustrated in Fig. 4 using a blue dot. In our usual network configuration, ṡ/σ 2 = [2.26, 1.52], yielding σ 2 t u 1 (ṡ) = 0.288 and σ 2 t u 2 (ṡ) = 0.434. The performance of ṡ lies in between the SW and the maximum-fairness projection of the NE performance, thus trading off efficiency and fairness. The reason why the NBS is unbalanced towards player 2 lies again in its better channel condition, which makes it stronger in negotiation [START_REF] Han | Game Theory in Wireless and Communication Networks: Theory, Models and Applications[END_REF]Ch. 7].

For more than two players, we can also consider a more general cooperative framework, namely coalitional GT [START_REF] Saad | Coalitional game theory for communication networks[END_REF], that provides the theoretical tools to investigate situations in which subsets of players can bind agreements to work together, aiming at improving their joint utility. This approach is particularly useful in many areas of SP, such as spectrum sensing for cognitive systems (see [START_REF] Han | Game Theory in Wireless and Communication Networks: Theory, Models and Applications[END_REF]Ch. 13] for further details).

CONCLUDING REMARKS

In this lecture note, we introduced the very basic notions of GT, using a power control problem for a wireless interference channel as the leitmotiv: by further detailing and adding features to this "toy example," we presented, among the others, the concepts of players, strategies, utilities, NE, Pareto and social optimality. The interested readers that want to deepen their knowledge of GT are invited to target specific textbooks, such as general ones (e.g., [START_REF] Fudenberg | Game Theory[END_REF]), and those specifically tailored to an SP audience (e.g., [START_REF] Han | Game Theory in Wireless and Communication Networks: Theory, Models and Applications[END_REF], [START_REF] Lasaulce | Game Theory and Learning for Wireless Networks: Fundamentals and Applications[END_REF]).

REPRODUCIBLE RESEARCH

This lecture note has supplementary, downloadable material available in [START_REF] Bacci | MATLAB code[END_REF], provided by the authors.

The material includes MATLAB code that can reproduce all the simulation results.

Fig. 1 :

 1 Fig. 1: Representation of the NFE game.

[ 2 ,

 2 Ch. 3]. When uniqueness cannot be ensured, like in the case of the IC game, we face the problem of equilibrium selection. One solution to this issue is the concept of correlated equilibrium (CE) [1, Ch. 2], a generalization of the NE, where an arbitrator helps the players to correlate their strategies, so as to favor a decision process in the interplay -e.g., letting them adopt s ⋆ = [p, 0].

Fig. 3 :

 3 Fig. 3: Throughput (red) and utility (blue) as functions of the SINR (continuous NFE game).

Fig. 4 :

 4 Fig. 4: Normalized utility plan (continuous-power NFE game).

The MATLAB code for all examples presented in this note is available for download in[START_REF] Bacci | MATLAB code[END_REF].

The research leading to these results has received funding from the European Union's FP7 under REA Grant agreements no.

PIOF-GA-2011-302520 GRAND-CRU and PIEF-GA-2012-330731 Dense4Green, and is also supported by the European Union's FP7 NEWCOM# (Grant agreement no. 318306).

if we consider w 1 = w 2 = 0.5 (i.e., if the two players have the same priority), š/σ 2 = [2.20, 1.55], yielding σ 2 t u 1 (š) = 0.278 and σ 2 t u 2 (š) = 0.446 (Fig. 4). We have zoomed a section of Fig. 4 (see the inset box) to show that the NE s ⋆ is socially inefficient, since its performance is distinct from (more specifically, poorer than) that achieved by š. In general, š cannot be achieved by distributed algorithms, rather, it is the result of a global optimization, and in our case it turns out to be unbalanced towards player 2 (the one with better channel conditions): this is reminiscent of the waterfilling policy [START_REF] Scutari | Convex optimization, game theory, and variational inequality theory[END_REF], that allocates most resources to the users that can achieve higher throughputs. More importantly, the magnification in Fig. 4 shows that there are a multitude of profiles that provide utilities lying in the Pareto improvement region, in which u k (s) ≥ u k (s ⋆ ) for all k ∈ K (shaded region in the inset).

Consequently, the next question is: how can we improve the efficiency of the NE? In this lecture note, we will focus on three popular methods, namely: i) modifying the utility functions; ii) letting the players interact more than once; and iii) letting the players cooperate.

PRICING THE STRATEGIES

The simplest method to improve the efficiency of the NE while maintaining the game structure is by modifying the utility function. This can be done for instance by introducing some form of externality. This approach is in spirit close to mechanism design [START_REF] Fudenberg | Game Theory[END_REF]Ch. 7]. For the power control games studied so far, one might think of charging the players for the powers they consume, by introducing a pricing factor α (in b/J • W -1 ): ũk (s) = u k (s)αs k = t k (s)/s kαs k [START_REF] Saraydar | Efficient power control via pricing in wireless data networks[END_REF]. The rationale behind this approach is the following: if each transmitter is discouraged from being aggressive (due to power taxation), the multiple access interference (MAI) experienced by the other is reduced, and both SINRs at the equilibrium stay as close as possible to γ ⋆ k (provided that the AWGN power σ 2 is not dominant -a condition which always holds in multiple-access systems).

To evaluate the benefits of this method, we compute the NE s⋆ of the modified game, using the BR approach (see [START_REF] Bacci | MATLAB code[END_REF]). The cyan cross marker in Fig. 4 represents the performance σ 2 t u 1 (s ⋆ ), σ 2 t u 2 (s ⋆ ) of the original utility function (4) (which is the one we are actually interested in), using α = 0.12t/σ 4 , that yields s⋆ /σ 2 = [2.17, 1.57]. As can be seen, the performance of s⋆ is very close to the Pareto frontier, further favoring player 2's performance compared to the SW. We have thus improved the efficiency of the game solution, while maintaining the noncooperative nature of the interplay (with all its desirable properties).

The main drawback is that this improvement can only be achieved after a proper tuning of α (that highly depends on system parameters). As an exercise, one could evaluate the performance of s⋆ as a function of α (see [START_REF] Bacci | MATLAB code[END_REF]).