John D Clemens

AND Dominique Lecomte

Benjamin D Miller

DICHOTOMY THEOREMS FOR FAMILIES OF NON-COFINAL ESSENTIAL COMPLEXITY

Keywords: 2010 Mathematics Subject Classification. Primary 03E15; secondary 28A05 Complexity, dichotomy, equivalence relation, smooth

We prove that for every Borel equivalence relation E, either E is Borel reducible to E 0 , or the family of Borel equivalence relations incompatible with E has cofinal essential complexity. It follows that if F is a Borel equivalence relation and F is a family of Borel equivalence relations of non-cofinal essential complexity which together satisfy the dichotomy that for every Borel equivalence relation E, either E ∈ F or F is Borel reducible to E, then F consists solely of smooth equivalence relations, thus the dichotomy is equivalent to a known theorem.

Introduction

A reduction of an equivalence relation E on a set X to an equivalence relation F on a set Y is a function π : X → Y with the property that ∀x 1 , x 2 ∈ X (x 1 E x 2 ⇐⇒ π(x 1 ) F π(x 2 )). A topological space is Polish if it is second countable and completely metrizable, a subset of such a space is Borel if it is in the σ-algebra generated by the underlying topology, and a function between such spaces is Borel if pre-images of open sets are Borel. Over the last few decades, the study of Borel reducibility of Borel equivalence relations on Polish spaces has emerged as a central theme in descriptive set theory.

The early development of this area was dominated by dichotomy theorems. There are several trivial ones, such as the fact that if n is a natural number, then for every Borel equivalence relation E on a Polish space, either E is Borel reducible to equality on n, or equality on n + 1 is Borel reducible to E. Similarly, either there is a natural number n for which E is Borel reducible to equality on n, or equality on N is Borel reducible to E.

There are also non-trivial results of this form. By [START_REF] Silver | Counting the number of equivalence classes of Borel and coanalytic equivalence relations[END_REF], either E is Borel reducible to equality on N, or equality on 2 N is Borel reducible to E. And by [HKL90, Theorem 1.1], either E is Borel reducible to equality on 2 N , or E 0 is Borel reducible to E, where E 0 is the relation on 2 N given by x E 0 y ⇐⇒ ∃n ∈ N∀m ≥ n x(m) = y(m).

Whereas the results we have mentioned thus far concern the global structure of the Borel reducibility hierarchy, [KL97, Theorem 1] yields a local dichotomy of this form. Namely, that for every Borel equivalence relation E on a Polish space which is Borel reducible to E 1 , either E is Borel reducible to E 0 , or E 1 is Borel reducible to E, where E 1 is the relation on (2 N ) N given by x E 1 y ⇐⇒ ∃n ∈ N∀m ≥ n x(m) = y(m).

At first glance, one might hope the assumption that E is Borel reducible to E 1 could be eliminated, thereby yielding a new global dichotomy theorem. Unfortunately, [KL97, Theorem 2] ensures that if E is not Borel reducible to E 0 , then there is a Borel equivalence relation with which it is incomparable under Borel reducibility. It follows that only the pairs (F, F ′ ) discussed thus far (up to Borel bi-reducibility) satisfy both (1) there is a Borel reduction of F to F ′ but not vice versa, and (2) for every Borel equivalence relation E on a Polish space, either E is Borel reducible to F , or F ′ is Borel reducible to E.

As the latter result rules out further global dichotomies of the sort discussed thus far, it is interesting to note that its proof hinges upon the previously mentioned local dichotomy, as well as Harrington's unpublished theorem that the family of orbit equivalence relations induced by Borel actions of Polish groups on Polish spaces is unbounded in the Borel reducibility hierarchy. Here we utilize strengthenings of these results to provide a substantially stronger anti-dichotomy theorem.

Given a property P of Borel equivalence relations, we say that a Borel equivalence relation is essentially P if it is Borel reducible to a Borel equivalence relation on a Polish space with the given property. A Wadge reduction of a set A ⊆ X to a set B ⊆ Y is a continuous function π : X → Y such that ∀x ∈ X (x ∈ A ⇐⇒ π(x) ∈ B). We say that a Borel equivalence relation E has essential complexity at least the complexity of a set B ⊆ 2 N if B is Wadge reducible to every Borel equivalence relation to which E is Borel reducible. We say that a family F of Borel equivalence relations has cofinal essential complexity if for every Borel set B ⊆ 2 N , there is a Borel equivalence relation E ∈ F with essential complexity at least the complexity of B.

Much as in [START_REF] Kechris | The classification of hypersmooth Borel equivalence relations[END_REF], we obtain our anti-dichotomy theorem as a consequence of a result yielding the existence of incomparable Borel equivalence relations, albeit one considerably stronger than that given there.

Theorem 1. Suppose that X is a Polish space and E is a Borel equivalence relation on X. Then exactly one of the following holds:

(1) The relation E is Borel reducible to E 0 .

(2) The family of Borel equivalence relations on Polish spaces which are incomparable with E under Borel reducibility has cofinal essential complexity.

We say that a family F of Borel equivalence relations on Polish spaces is dichotomical if there is a minimum Borel equivalence relation F on a Polish space which is not in F , meaning that whenever E is a Borel equivalence relation on a Polish space, either E ∈ F or there is a Borel reduction of F to E. The following consequence of Theorem 1 implies that the only such families are those associated with the dichotomies mentioned earlier.

Theorem 2. Suppose that F is a dichotomical class of Borel equivalence relations on Polish spaces of non-cofinal essential complexity. Then every equivalence relation in F is smooth.

In §1, we briefly review the preliminaries needed throughout the paper. In §2, we introduce a property of graphs G ensuring that if a Borel equivalence relation E on a Polish space, whose classes are all countable, is Borel reducible to the equivalence relation generated by G, then it is Borel reducible to E 0 . In §3, we introduce a family of ideals on N × N, and show that they are cofinal under Wadge reducibility. In §4, we introduce a family of trees on N × N, and show that the graphs determined by their branches interact nicely with equivalence relations induced by ideals. In §5, we consider a subfamily of these trees satisfying an appropriate density condition, and show that the graphs determined by their branches interact particularly nicely with equivalence relations induced by the ideals introduced earlier. And in §6, we establish our primary results.

Preliminaries

Two sets M, N ⊆ N are almost disjoint if |M ∩ N| < ℵ 0 .
Proposition 1.1. There is a continuous injection π : 2 N → P(N) into a family of pairwise almost disjoint infinite sets.

Proof. It is sufficient to observe that the function π : 2 N → P(2 <N ), given by π(c) = {c ↾ n | n ∈ N}, is a continuous injection into a family of pairwise almost disjoint infinite sets.

A set is comeager if it contains an intersection of countably many dense open sets.

Proposition 1.2. Suppose that X and Y are Polish spaces and the map π : X → Y is Borel. Then there is a comeager set C ⊆ X on which π is continuous.

Proof. See, for example, [START_REF] Kechris | Classical descriptive set theory[END_REF]Theorem 8.38].

A subset of a Polish space is analytic if it is the continuous image of a Borel subset of a Polish space. A subset of a Polish space is co-analytic if its complement is analytic.

Theorem 1.3 (Souslin). Suppose that X is a Polish space and B ⊆ X. Then B is Borel if and only if B is both analytic and co-analytic.

Proof. See, for example, [START_REF] Kechris | Classical descriptive set theory[END_REF]Theorem 14.11].

The projection from X × Y to X is given by proj

X (x, y) = x. A partial uniformization of a set R ⊆ X × Y is a function whose graph is contained in R. A uniformization of a set R ⊆ X × Y is a partial uniformization of R whose domain is proj X (R).
Theorem 1.4 (Lusin-Novikov). Suppose that X and Y are Polish spaces and R ⊆ X × Y is a Borel set whose vertical sections are all countable. Then proj X (R) is Borel, and R is a countable union of Borel uniformizations.

Proof. See, for example, [Kec95, Theorem 18.10].

For each x ∈ X, the x th vertical section of a set R ⊆ X ×Y is given by A graph on a set X is an irreflexive, symmetric set G ⊆ X ×X. Such a graph is locally countable if its vertical sections are countable. An edge

R x = {y ∈ Y | x R y}. The set of unicity of R is {x ∈ X | |R x | = 1}.
N-coloring of G is a map c : G → N with ∀(x, y) ∈ G c(x, y) = c(y, x) and ∀(x, y), (x, z) ∈ G (y = z =⇒ c(x, y) = c(x, z)).
Theorem 1.6 (Feldman-Moore). Suppose that X is a Polish space and G is a locally countable Borel graph on X. Then there is a Borel edge N-coloring of G.

Proof. This follows from the proof of [FM77, Theorem 1].

We say that a Borel equivalence relation is smooth if it is Borel reducible to equality on 2 N . An embedding is an injective reduction.

Theorem 1.7 (Harrington-Kechris-Louveau). Suppose that X is a Polish space and E is a Borel equivalence relation on X. Then exactly one of the following holds:

(1) The relation E is smooth.

(2) There is a continuous embedding of E 0 into E.

Proof. See [HKL90, Theorem 1.1].

A partial transversal of an equivalence relation E on X is a set B ⊆ X intersecting every equivalence class of E in at most one point. A transversal of an equivalence relation E on X is a set B ⊆ X intersecting every equivalence class of E in exactly one point.

Following the standard abuse of language, we say that an equivalence relation is countable if all of its equivalence classes are countable.

Proposition 1.8. Suppose that X is a Polish space and E is a countable Borel equivalence relation on X. Then E is smooth if and only if X is the union of countably many Borel partial transversals of E.

Proof. This is a straightforward consequence of Theorem 1.4.

Again following the standard abuse of language, we say that an equivalence relation is finite if all of its equivalence classes are finite.

Proposition 1.9. Suppose that X is a Polish space and E is a finite Borel equivalence relation on X. Then E is smooth.

Proof. This is also a straightforward consequence of Theorem 1.4.

We say that a Borel equivalence relation is hyperfinite if it is the union of an increasing sequence (F n ) n∈N of finite Borel subequivalence relations. By [

Y is Π 1 1 1 1 1 1 -on-Σ 1 1 1 1 1 1 if whenever X is a Po- lish space and R ⊆ X × Y is an analytic set, the corresponding set {x ∈ X | R x satisfies P } is co-analytic. Theorem 1.12. Suppose that X is a Polish space, Φ is a Π 1 1 1 1 1 1 -on-Σ 1 1 1 1 1 1
property of subsets of X, and A ⊆ X is an analytic set on which Φ holds. Then there is a Borel set B ⊇ A on which Φ holds.

Proof. See, for example, [Kec95, Theorem 35.10].

A path through a graph G is a sequence (x i ) i≤n with the property that ∀i < n x i G x i+1 . Such a path is a cycle if n > 2, (x i ) i<n is injective, and

x 0 = x n . A graph is acyclic if it has no cycles.
The equivalence relation generated by a graph G on a set X is the smallest equivalence relation E G on X containing it. A graphing of an equivalence relation is a graph generating it. We say that a Borel equivalence relation is treeable if it has an acyclic Borel graphing.

Theorem 1.13 (Hjorth). Suppose that X is a Polish space and E is a treeable Borel equivalence relation on X. Then the following are equivalent:

(1) The relation E is essentially countable.

(2) There is a Borel set B ⊆ X whose intersection with each equivalence class of E is countable and non-empty.

Proof. See [Hjo08, Theorem 6].

Theorem 1.14. Suppose that X is a Polish space and E is a Borel equivalence relation on X essentially generated by a Borel subgraph of an acyclic compact graph. Then exactly one of the following holds:

(1) The relation E is essentially countable.

(2) There is a continuous embedding of E 1 into E.

Proof

Partition stratifications

Suppose that X is a Polish space, E is a Borel equivalence relation on X, and G is a Borel graph on X. We use G E to denote the graph on X/E given by

G E = {(C, D) ∈ (X/E) × (X/E) | C = D and (C × D) ∩ G = ∅}.
We say that G has faithful cycles over E if among all G-paths (x i ) i≤k , only G-cycles have the property that ([

x i ] E ) i≤k is a G E -cycle.
A partition stratification of G is a sequence of the form (E n , G n ) n∈N , where (E n ) n∈N is a decreasing sequence of equivalence relations on X, each of which having only countably many classes, whose intersection is the diagonal, (G n ) n∈N is an increasing sequence of Borel graphs whose union is G, and G n has faithful cycles on E n .

Proposition 2.1. Suppose that X is a Polish space, E is a countable Borel equivalence relation on X, and G is a Borel graphing of E. Then E is hyperfinite if and only if there is a partition stratification of G.

Proof. Suppose first that E is hyperfinite, and fix an increasing sequence (F n ) n∈N of finite Borel subequivalence relations whose union is E. As Propositions 1.8 and 1.9 ensure that spaces underlying finite Borel equivalence relations are countable unions of Borel partial transversals, it follows that there is a decreasing sequence (E n ) n∈N of Borel equivalence relations such that every E n has only countably many classes, each of which is a partial transversal of F n of diameter at most 1/n. For each n ∈ N, set G n = F n ∩ G, and note that if

(x i ) i≤k is a G n -path for which ([x i ] En ) i≤k is a (G n ) En -cycle, then x 0 (E n ∩ F n ) x k , so x 0 = x k , thus (x i ) i≤k is a G n -cycle. It follows that each G n has faithful cycles on E n , so (E n , G n ) n∈N is a partition stratification of G.
Conversely, suppose that (E n , G n ) n∈N is a partition stratification of G. By Theorem 1.6, there is a Borel edge N-coloring c of G. Let H n denote the subgraph of G n consisting of all (x, y) ∈ G n \ E n for which c(x, y) is minimal both among natural numbers of the form c(x ′ , y) where x E n x ′ G y, and those of the form c(x, y ′ ) where x G y ′ E n y. Then (H n ) n∈N is an increasing sequence of Borel graphs whose union is G. By Theorem 1.11, to see that E G is hyperfinite, we need only check that the relations F n = E Hn are smooth. By Proposition 1.8, it is sufficient to show that for all n ∈ N, every equivalence class of E n is a partial transversal of F n .

Suppose, towards a contradiction, that k ∈ N is least for which there is an injective H n -path (x i ) i≤k beginning and ending at distinct E n -related points. The definition of partition stratification ensures that ([x i ] En ) i≤k is not a (G n ) En -cycle, so there exists 0 < i < k for which x i-1 E n x i+1 . Set x = x i-1 , y = x i , and x ′ = x i+1 . Then c(x, y) = c(x ′ , y), so the definition of H n ensures that ¬x H n y or ¬x ′ H n y, the desired contradiction.

We say that properties P and Q of Borel equivalence relations coincide below a given Borel equivalence relation F if the family of Borel equivalence relations on Polish spaces which are Borel reducible to F and satisfy P is the same as the family of Borel equivalence relations on Polish spaces which are Borel reducible to F and satisfy Q.

Proposition 2.2. Suppose that X is a Polish space, E is a Borel equivalence relation on X, and G is a Borel graphing of E which admits a partition stratification. Then countability and hyperfiniteness coincide below E.

Proof. Fix a partition stratification (E n , G n ) n∈N of G.
Lemma 2.3. There are only countably many injective G-paths between any two points.

Proof. Suppose, towards a contradiction, that k ∈ N is the least natural number for which there exist x, y ∈ X between which there are uncountably many injective G-paths (z i ) i≤k from x to y. Then for n ∈ N sufficiently large, there are uncountably many injective G npaths (z i ) i≤k from x to y with the further property that ([z i ] En ) i≤k is an injective (G n ) En -path. Fix such an injective G n -path (z i ) i≤k from x to y for which there are uncountably many injective G n -paths (z ′ i ) i≤k from x to y inducing the same injective (G n ) En -path as (z i ) i≤k . The minimality of k then ensures that there are uncountably many injective G n -paths (z ′ i ) i≤k from x to y inducing the same injective (G n ) En -path as (z i ) i≤k but avoiding {z i | 0 < i < k}. Then for n ′ ∈ N sufficiently large, there are uncountably many injective G n -paths (z ′ i ) i≤k from x to y inducing the same injective (G n ) En -path as (z i ) i≤k but for which the corresponding injective (

G n ) E n ′ -path avoids {[z i ] E n ′ | 0 < i < k}.
It follows that there is such an injective G n -path (z ′ i ) i≤k from x to y for which there are uncountably many such injective G n -paths (z ′′ i ) i≤k inducing the same injective (G n ) E n ′ -path as (z ′ i ) i≤k . By one more appeal to the minimality of k, there are uncountably many such injective

G n - paths (z ′′ i ) i≤k inducing the same injective (G n ) E n ′ -path as (z ′ i ) i≤k but avoiding {z ′ i | 0 < i < k}. Fix any such injective G n -path (z ′′ i ) i≤k , and observe that (z ′ 1 , . . . , z ′ k = z k , . . . , z 0 = z ′′ 0 , z ′′ 1 ) is an injective G n -path inducing a (G n ) E n ′ -cycle, contradicting the fact that G n ′ has faithful cycles on E n ′ .
By Theorem 1.4 and Proposition 1.10, it is sufficient to show that E is hyperfinite on every Borel set B ⊆ X on which it is countable. Towards this end, let C denote the convex closure of B with respect to G, that is, the set of points lying along an injective G-path between two points of B. As Theorem 1.4 and Lemma 2.3 ensure that C is also a Borel set on which E is countable, Proposition 2.1 implies that E is hyperfinite on C, thus hyperfinite on B.

In the treeable case, we can say even more.

Proposition 2.4. Suppose that X is a Polish space, E is a treeable Borel equivalence relation on X, and countability and hyperfiniteness coincide below E. Then essential countability and essential hyperfiniteness also coincide below E.

Proof. Suppose that Y is a Polish space and F is an essentially countable Borel equivalence relation on Y which admits a Borel reduction φ : Y → X to E. Fix a Polish space Y ′ and a countable Borel equivalence relation F ′ on Y ′ for which there is a Borel reduction ψ :

Y → Y ′ of F to F ′ . Then the set R 0 = {(x, ψ(y)) | φ(y) = x} induces a partial injection of X/E into Y ′ /F ′ , in the sense that x 1 E x 2 ⇐⇒ y ′ 1 F ′ y ′ 2 , for all (x 1 , y ′ 1 ), (x 2 , y ′ 2 ) ∈ R 0 . The product of the equivalence relations E and F ′ is the relation on X × Y ′ given by (x 1 , y ′ 1 ) (E × F ′ ) (x 2 , y ′ 2 ) ⇐⇒ (x 1 E x 2 and y ′ 1 F y ′ 2 ). Lemma 2.5. There is an (E×F ′ )-invariant Borel set R ⊇ R 0 inducing a partial injection of X/E into Y ′ /F ′ .
Proof. As the property of inducing a partial injection of X/E into Y ′ /F ′ is Π 1 1 1 1 1 1 -on-Σ 1 1 1 1 1 1 and closed under (E ×F ′ )-saturation, by repeatedly applying Theorem 1.12, we obtain Borel sets

R n+1 ⊇ [R n ] E×F ′ inducing Borel partial injections of X/E into Y ′ /F ′ . Define R = n∈N R n .
As F ′ is countable, Theorem 1.4 ensures that the set C = proj X (R) is Borel, and that there is a Borel uniformization π : C → Y ′ of R. As any such function is necessarily a reduction of E to F ′ on C, it follows that E is essentially countable on C. An application of Theorem 1.13 then yields a Borel set D ⊆ C, whose E-saturation is C, on which E is countable. As countability and hyperfiniteness coincide below E, it follows that E is hyperfinite on D, and one more application of Theorem 1.4 yields a Borel reduction of E ↾ C to E ↾ D, so E is essentially hyperfinite on C, thus F is essentially hyperfinite.

Ideals

We say that a family K of subsets of N × N is determined by cardinalities on vertical sections if

A ∈ K ⇐⇒ B ∈ K, whenever ∀n ∈ N |A n | = |B n |.
For each family N ⊆ P(N) of subsets of the natural numbers, we use cl(N ) to denote the closure of N under finite unions, and we define K N = N ∈cl(N ) K N , where

K N = {A ⊆ N × N | ∀n ∈ N (|A n | = ℵ 0 =⇒ n ∈ N)}.
Note that every such family is both determined by cardinalities on vertical sections and an ideal, in the sense that it is closed under containment and finite unions.

Proposition 3.1. Suppose that N ⊆ P(N) is a family of pairwise almost disjoint infinite subsets of N. Then there is a continuous function π :

N → P(N × N) Wadge reducing M to K M , for all M ⊆ N . Proof. Define π(N) = N × N. Given M ⊆ N , observe first that if M ∈ M , then π(M) ∈ K M ⊆ K M . Conversely, if N ∈ N and π(N) ∈ K M , then there exist n ∈ N and M 1 , . . . , M n ∈ M such that π(N) ∈ K M 1 ∪•••∪Mn , in which case N ⊆ M 1 ∪ • • • ∪ M n . As N consists of pairwise almost disjoint infinite sets, it follows that N = M i , for some 1 ≤ i ≤ n, thus N ∈ M .
A weak converse to this result is provided by the following. Proposition 3.2. Suppose that N ⊆ P(N) is a Borel family of pairwise almost disjoint infinite subsets of N. Then K N is also Borel.

Proof. Clearly K N is analytic, so by Theorem 1.3, it is sufficient to show that it is co-analytic. But this follows from Theorem 1.5 and the fact that a set A is in K N if and only if there exist k ∈ N and a unique subfamily F of N of cardinality k for which there is a finite subset F of a set in cl(N ) such that ∀n ∈ N

(|A n | = ℵ 0 =⇒ n ∈ F ∪ F ).

Trees

Suppose that t i,n ∈ 2 n , for all i < 2 and n ∈ N. Associated with (t i,n ) i<2,n∈N are the graphs T n on 2 n obtained recursively by letting T n+1 be the union of the graph {(s

(i), t (i)) | i < 2 and (s, t) ∈ T n } with the singleton edge {(t i,n (i), t 1-i,n (1 -i)) | i < 2}, as well as the set T = {(∅, ∅)} ∪ n∈N T n .
A straightforward induction shows that each T n is a tree on 2 n . It follows that if the set T is closed under initial segments, then the set

[T ] = {(x, y) ∈ 2 N × 2 N | ∀n ∈ N (x ↾ n, y ↾ n) ∈ T n }
of branches through T is an acyclic compact graph admitting a partition stratification, thus all of its Borel subgraphs admit partition stratifications as well. As equivalence relations induced by acyclic Borel graphs are themselves Borel (by Theorems 1.3 and 1.5), Propositions 2.2 and 2.4 therefore imply that essential countability and essential hyperfiniteness coincide below equivalence relations generated by such subgraphs.

The support of a sequence c ∈ 2 N is given by supp(c) = c -1 (1). Proposition 4.2. Suppose that t i,n ∈ 2 n for all i < 2 and n ∈ N, the corresponding set T is closed under initial segments, and I is an ideal on N containing all finite subsets of N.

Then E I ∩ [T ] is a graphing of E I ∩ E [T ] .
Proof. It is sufficient to show that if n ∈ N, (c i ) i≤n is an injective [T ]path, and c 0 E I c n , then (c i ) i≤n is an (E I ∩ [T ])-path. Towards this end, appeal to Proposition 4.1 repeatedly to obtain a finite set F ⊆ N containing (supp(c i ) △ supp(c i+1 )) ∩ (supp(c j ) △ supp(c j+1 )), for all i < j < n. Then supp(c 0 ) △ supp(c n ) and i<n supp(c i ) △ supp(c i+1 ) agree off of F , so supp(c i ) △ supp(c i+1 ) ⊆ F ∪ (supp(c 0 ) △ supp(c n )), and is therefore in I, for all i < n.

Density

Suppose that t i,n ∈ 2 n , for all i < 2 and n ∈ N, and the corresponding set T is closed under initial segments. Then for each n ∈ N, there exist k ∈ {0, . . . , n} and s ∈ 2 n-k with t i,n+1 = t i,k (i) s. Conversely, if k n ∈ {0, . . . , n} and s n ∈ 2 n-kn for all n ∈ N, then the set T associated with (t i,n ) i<2,n∈N , where t i,0 = ∅ and t i,n+1 = t i,kn (i) s n for i < 2 and n ∈ N, is closed under initial segments. We say that (k n , s n ) n∈N is suitable if k n ∈ {0, . . . , n} and s n ∈ 2 n-kn , for all n ∈ N.

Fix an injective enumeration (i n , j n ) n∈N of N × N with i 0 = 0, and let e denote its inverse. We say that (k n , s n ) n∈N is dense (with respect to Theorem 5.2. The family of treeable Borel equivalence relations below which essential hyperfiniteness and the inexistence of a continuous embedding of E 1 coincide has cofinal essential complexity.

Proof. By appealing to Proposition 1.1, we obtain a continuous injection π : 2 N → P(N) into a family of pairwise almost disjoint infinite sets. Given a Borel set B ⊆ 2 N , set N = π(B). Proposition 3.1 then ensures that B is Wadge reducible to K N , and Proposition 3.2 implies that the latter is Borel, thus the same holds of the ideal I = e * K N .

Fix a dense suitable sequence (k n , s n ) n∈N , and let T be the associated set. Proposition 4.2 then ensures that the equivalence relation E on 2 N given by E = E I ∩ E [T ] is generated by a Borel subgraph of an acyclic compact graph, and since it is clearly Borel, by Theorem 1.14 we need only check that its essential complexity is at least the complexity of B.

Towards this end, suppose that Y is a Polish space, and F is a Borel equivalence relation on Y for which there is a Borel reduction φ : X → Y of E to F . Proposition 1.2 then yields a comeager Borel set C ⊆ X on which φ is continuous. By Proposition 5.1, there is a Wadge reduction ψ : P(N) → [T ] ↾ C of I to E, and it follows that (φ × φ) • ψ is a Wadge reduction of I to F , so B is Wadge reducible to F , thus the essential complexity of E is at least the complexity of B.

Anti-basis results

We say that a family F of Borel equivalence relations on Polish spaces is unbounded if for every Borel equivalence relation E on a Polish space, there is a Borel equivalence relation F ∈ F which is not Borel reducible to E.

We say that the non-linearity of Borel reducibility is captured off of a family F of Borel equivalence relations if every non-essentiallyhyperfinite Borel equivalence relation is incompatible with a Borel equivalence relation outside of F . Theorem 6.1. Suppose that F is a class of Borel equivalence relations whose complement contains unboundedly many Borel equivalence relations below which essential hyperfiniteness and the inexistence of a Borel reduction of E 1 coincide, as well as unboundedly many Borel equivalence relations to which E 1 does not admit a Borel reduction. Then the non-linearity of Borel reducibility is captured off of F . Proof. Suppose that E is a Borel equivalence relation compatible with every Borel equivalence relation outside of F . Fix a Borel equivalence relation E ′ , outside of F and not Borel reducible to E, below which essential hyperfiniteness and the inexistence of a Borel reduction of E 1 coincide. In addition, fix a Borel equivalence relation E ′′ , outside of F and not Borel reducible to E, to which E 1 does not admit a Borel reduction. As E is Borel reducible to E ′′ , it follows that E 1 is not Borel reducible to E. As E is Borel reducible to E ′ , it therefore follows that E is essentially hyperfinite.

The following corollary strengthens [KL97, Theorem 2]. Theorem 6.2. Suppose that X is a Polish space and E is a Borel equivalence relation on X. Then the following are equivalent:

(1) The relation E is not essentially hyperfinite.

(2) There is a Borel equivalence relation on a Polish space which is incompatible with E.

(3) The family of Borel equivalence relations on Polish spaces which are incompatible with E under Borel reducibility has cofinal essential complexity.

Proof. As (3) =⇒ (2) is trivial and (2) =⇒ (1) is a consequence of Theorem 1.7, it is sufficient to show (1) =⇒ (3). Towards this end, note that Theorem 5.2 ensures that the family of Borel equivalence relations on Polish spaces below which essential hyperfiniteness and the inexistence of a Borel reduction of E 1 coincide has cofinal essential complexity, and Theorems 1.15 and 1.16 imply that the family of Borel equivalence relations on Polish spaces to which E 1 does not Borel reduce has cofinal essential complexity. So, by Theorem 6.1, the family of Borel equivalence relations on Polish spaces which are incompatible with E under Borel reducibility has cofinal essential complexity.

We can now establish our primary result.

Theorem 6.3. Suppose that F is a dichotomical class of Borel equivalence relations on Polish spaces of bounded essential complexity. Then every equivalence relation in F is smooth.

Proof. Fix a Borel equivalence relation F witnessing that F is dichotomical. Then F is necessarily essentially hyperfinite, since otherwise Theorem 6.2 would yield a Borel equivalence relation outside of F and incompatible with F . But Theorem 1.7 then implies that every relation in F is smooth.

  Theorem 1.5 (Lusin). Suppose that X and Y are Polish spaces and R ⊆ X × Y is Borel. Then the set of unicity of R is co-analytic.Proof. See, for example,[START_REF] Kechris | Classical descriptive set theory[END_REF] Theorem 18.11].

Proposition 4. 1 .

 1 Suppose that t i,n ∈ 2 n for all i < 2 and n ∈ N, the corresponding set T is closed under initial segments, (a, b), (c, d) ∈ [T ], and {a, b} = {c, d}. Then (supp(a) △ supp(b)) ∩ (supp(c) △ supp(d)) is finite.Proof. For each n ∈ N, let T n denote the tree on 2 n associated with (t i,n ) i<2,n∈N , and note that if n ∈ supp(a) △ supp(b), then the pair of restrictions (a↾ (n + 1), b ↾ (n + 1)) is in T n+1 , from which it follows that {a ↾ (n + 1), b ↾ (n + 1)} = {t i,n (i) | i < 2}, and therefore that {a ↾ n, b ↾ n} = {t i,n | i < 2}. In particular, if n ∈ N is sufficiently large that {a ↾ n, b ↾ n} = {c ↾ n, d ↾ n}, then n is not in (supp(a) △ supp(b)) ∩ (supp(c) △ supp(d)).Given a family I of subsets of N, let E I denote the binary relation on 2 N given by c E I d ⇐⇒ supp(c) △ supp(d) ∈ I.

  DJK94, Theorem 1], a countable Borel equivalence relation is hyperfinite if and only if it is Borel reducible to E 0 . Borel equivalence relation is hypersmooth if it is the union of an increasing sequence (F n ) n∈N of smooth Borel subequivalence relations. By [KL97, Propositions 1.1 and 1.3], a Borel equivalence relation is hypersmooth if and only if it is Borel reducible to E 1 . Theorem 1.11 (Dougherty-Jackson-Kechris). Suppose that X is a Polish space and E is a Borel equivalence relation on X. Then E is hyperfinite if and only if E is both countable and hypersmooth.

	A property P of subsets of
	Proof. See [DJK94, Proposition 5.2].
	We say that a Proof. See, for example, [DJK94, Theorem 5.1].

Proposition 1.10 (Dougherty-Jackson-Kechris). Suppose that X and Y are Polish spaces, E and F are countable Borel equivalence relations on X and Y , E is Borel reducible to F , and F is hyperfinite. Then E is hyperfinite.

  Suppose that X is a Polish space and E is the orbit equivalence relation induced by a Borel action of a Polish group on a Polish space. Then E 1 is not Borel reducible to E.

	Proof. See [KL97, Theorem 4.2].

. See [CLM14, Theorem 6.3 and Proposition 6.4].

A topological group is Polish if it is Polish as a topological space. Theorem 1.15 (Hjorth-Kechris-Louveau). The family of orbit equivalence relations induced by Borel actions of Polish groups on Polish spaces has cofinal essential complexity. Proof. See [HKL98, Theorem 4.1]. Theorem 1.16 (Kechris-Louveau).

Acknowledgments. We would like to express our gratitude to Renaud Bonnafoux and Jean-Marc Tomczyk, who took over Dominique Lecomte's teaching while he spent a semester in Münster, during which the bulk of this work was completed. We would also like to thank Alain Louveau and Gabriel Debs for their remarks on our work.

The authors were supported in part by SFB Grant 878.

our fixed enumeration) if for all i, k ∈ N and all s ∈ 2 <N , there exists n ∈ N such that i = i n+1 , k = k n , and s ⊑ s n .

The push-forward of a family K of subsets of N × N through e is given by e * K = {e(A) | A ∈ K}.

Proposition 5.1. Suppose that (k n , s n ) n∈N is dense and suitable, T is the corresponding set, C ⊆ 2 N is comeager, K is a family of subsets of N × N which is determined by cardinalities on vertical sections and invariant under finite alterations of the leftmost column, and I = e * K. Then there is a Wadge reduction π :

Proof. Fix dense open sets U n ⊆ 2 N whose intersection is contained in C, and let t i,n denote the sequences associated with (k n , s n ) n∈N . We will recursively construct natural numbers ℓ n > 0, in addition to natural numbers n u < ℓ n and sequences t u ∈ 2 ℓn-nu-1 for u ∈ 2 n , from which we define π i,n : 2 n → 2 ℓn by π i,n (u) = t i,nu (i) t u , for i < 2 and u ∈ 2 n . We will ensure that the following conditions hold:

(1) ∀i,

= (supp(π 0,n (u)) △ supp(π 1,n (u))) ∪ {n u (1) }. We begin by setting ℓ 0 = 1, n ∅ = 0, and t ∅ = ∅.

Suppose now that n ∈ N and we have already found ℓ n , n u , and t u , for u ∈ 2 n . For each u ∈ 2 n , set n u (0) = n u , and fix t ′ u ∈ 2 <N with the property that N π i,n (u) t ′ u ⊆ U n for all i < 2. By density, there exists n u (1) > 0 with i n = i n u (1) , n u = k n u (1) -1 , and t u t ′ u ⊑ s n u (1) -1 . Define ℓ n+1 = max u∈2 n n u (1) + 1, and for each u ∈ 2 n , fix an extension t u (0) ∈ 2 ℓ n+1 -nu-1 of t u t ′ u , as well as t u (1) ∈ 2 ℓ n+1 -n u (1) -1 . By condition (1), the function π : P(N) → 2 N × 2 N which is given by π(A) = (π 0 (χ A ), π 1 (χ A )), where π i (c) = n∈N π i,n (c ↾ n) for all i < 2, is well-defined and continuous. Condition (2) then ensures that π i (2 N ) ⊆ C for all i < 2, so π(P(N)) ⊆ C × C, thus condition (3) implies that π(P(N)) ⊆ [T ] ↾ C. And conditions (4) -(6) ensure that for all N ⊆ N, the cardinalities of all but the leftmost vertical sections of e -1 (supp(π 0 (χ N )) △ supp(π 1 (χ N ))) and e -1 (N) agree, whereas the cardinalities of their leftmost vertical sections differ by at most one, thus N ∈ I if and only if π(N) ∈ E I .

As a consequence, we obtain the following.


domain: info math spi

text:
Giacomo Bacci

E Veronica Belmega

Panayotis Mertikopoulos

Luca Sanguinetti

Energy-Aware Competitive Link Adaptation in Small-Cell Networks (Invited Paper)

This work proposes a distributed power allocation scheme for maximizing the energy efficiency in the uplink of noncooperative small-cell networks based on orthogonal frequencydivision multiple-access technology. This is achieved by modeling users as rational agents that engage in a non-cooperative game in which every user selects the power loading so as to maximize his own utility (the user's throughput per Watt of transmit power) while satisfying minimum rate constraints. In this framework, we prove the existence of a Debreu equilibrium (also known as generalized Nash equilibrium) and we characterize the structure of the corresponding power allocation profile using techniques drawn from fractional programming. To attain this equilibrium in a distributed fashion, we also propose a method based on an iterative water-filling best response process. Numerical simulations are then used to assess the method's convergence and the performance of its end-state as a function of the system parameters.

I. INTRODUCTION

Small-cell networks are nowadays considered as one of the most promising solutions to address the seemingly contradictory future requirements of the Information and Communication Technology industry: more cellular network capacity and less energy consumption [START_REF] Hoydis | Green small-cell networks[END_REF]. In a nutshell, the smallcell network concept amounts to a very dense deployment of operator-installed low-cost and low-power base stations equipped with advanced self-organization capabilities. This paradigm shift from carefully planned cellular networks to irregularly deployed self-optimizing base stations with different coverage makes the cellular architecture increasingly complex and heterogeneous, and poses many challenging issues to efficient network operation.

One of the key technical challenges in the deployment of small-cell networks is the involved network interference. A promising solution to this problem is commonly referred to as distributed cooperation [START_REF] Hoydis | Green small-cell networks[END_REF], and aims at finding algorithmic solutions that approach the ideal cooperative gains while exploiting mostly local information and requiring limited interactions.

The research leading to these results has received funding from the People Programme (Marie Curie Actions) of the European Union's FP7 under REA Grant agreements no. PIOF-GA-2011-302520 GRAND-CRU and PIEF-GA-2012-330731 Dense4Green, from the European Commission in the framework of the FP7 Network of Excellence in Wireless COMmunications NEWCOM# (Grant agreement no. 318306), and from the French National Research Agency (ANR) research grant NETLEARN (contract no. ANR-13-INFR-004).

Motivated by all this, in this paper, we analyze the uplink component of an orthogonal frequency-division multipleaccess (OFDMA)-based small cell network. In particular, we propose a game-theoretic framework to examine the optimal power allocation over the available sub-carriers at each transmitter, designed to maximize each link's individual energyaware utility. Specifically, the utility of each transmitter is defined as the achieved throughput per unit of power, accounting for both the power required for data transmission and that required by the circuit components of the wireless device (such as amplifiers, mixer, oscillator, and filters) [START_REF] Björnson | Designing multi-user MIMO for energy efficiency: When is massive MIMO the answer?[END_REF]- [START_REF] Isheden | Framework for link-level energy efficiency optimization with informed transmitter[END_REF]. In addition to the above, if the users also have a minimum rate requirement that must be achieved, the resulting game departs from the classical framework put forth by Nash [START_REF] Nash | Non-cooperative games[END_REF], and becomes a Debreu-type game in which the actions available to each user depend on the power profile of other users [START_REF] Debreu | A social equilibrium existence theorem[END_REF]. In this setting, the relevant solution concept is that of a Debreu equilibrium (which is also commonly known as a generalized Nash equilibrium); the existence of this state is then proved by suitably extending the results of [START_REF] Debreu | A social equilibrium existence theorem[END_REF] to a setting with non-compact action sets, and its structure is characterized using techniques from fractional programming [START_REF] Boyd | Convex Optimization[END_REF]. As we shall see, Debreu equilibria correspond to the fixed points of a water-filling best response operator where the water level is a function of the minimum rate constraints and each user's power envelope [START_REF] Isheden | Framework for link-level energy efficiency optimization with informed transmitter[END_REF]. The theoretical analysis is then adopted to derive an iterative and distributed power allocation algorithm whose convergence and performance are assessed by means of numerical results.

The most relevant works in the above context are [START_REF] Miao | Distributed interferenceaware energy-efficient power optimization[END_REF] and [START_REF] Bacci | Distributed energyefficient power and subcarrier allocation for OFDMA-based small cells[END_REF]. In [START_REF] Miao | Distributed interferenceaware energy-efficient power optimization[END_REF], the authors examine a similar distributed energy-aware resource allocation problem but the users are not assumed to have any hard minimum rate requirements, so the resulting non-cooperative game is a classical Nash game with continuous action sets. The added quality-of-service (QoS) requirement complicates the analysis of the game considerably: to prove the equilibrium existence, one must go beyond standard Nash equilibrium results, since a user's admissible power allocation profile depends on the power profile of all other users; also, the question of the uniqueness of an equilibrium, in our case, seems to be a very difficult issue, which is left as a future work. Much closer in spirit is the very recent companion paper [START_REF] Bacci | Distributed energyefficient power and subcarrier allocation for OFDMA-based small cells[END_REF], whose system model is essentially equivalent to the one that we study in this paper (including the minimum QoS constraint at the user level). That said, by taking an approach based on fractional programming, we are able to chart out here the convergence properties of the proposed water-filling best response algorithm, and we are also able to provide a rigorous proof of the existence of a Debreu equilibrium by extending the results of [START_REF] Debreu | A social equilibrium existence theorem[END_REF] to a non-compact setting (by contrast, in [START_REF] Bacci | Distributed energyefficient power and subcarrier allocation for OFDMA-based small cells[END_REF] this result is announced but not proven).

Paper outline: In Sect. II, we introduce the small-cell network model, which is then formulated as a Nash/Debreu energy-aware power allocation game in Sect. III (where we prove the existence of a Debreu equilibrium and characterize its structure). In Sect. IV, we propose a distributed algorithm, which allows the users to converge to the game's equilibrium in a distributed fashion. The convergence of the proposed distributed algorithm and the energy-efficiency of the algorithm's end state are then evaluated via numerical simulations in Sect. V.

Notational conventions: Matrices and vectors are denoted by bold letters, I L , 0 L , and 1 L are the L × L identity matrix, the L × 1 all-zero column vector, and the L × 1 allone column vector, respectively, and • 2 , (•) T and (•) H denote Euclidean norm of the enclosed vector, transposition and Hermitian transposition respectively. The notation (x) + stands for max(0, x) whereas W (•) denotes the Lambert W function [START_REF] Corless | On the Lambert W function[END_REF], defined to be the multivalued inverse of the function z = W (z) e W(z) for any z ∈ C. Finally, if A k , k = 1, . . . , K is a finite family of sets, and a k ∈ A k , we will use the notation (a k ; a -k ) ∈ k A k as shorthand for the profile (a 1 , . . . , a k , . . . , a K ).

II. SYSTEM MODEL AND PROBLEM FORMULATION

We consider the uplink of a network composed by S small cells operating in an OFDMA-based open-access licensed spectrum. The sth small cell uses a set of orthogonal subcarriers to serve the K s user equipments (UEs) falling within its coverage radius ρ s . For simplicity, we assume that the same set of subcarriers N = {1, . . . , N } is used by all small cells. The latter is assigned by the macrocell network and does not represent a parameter of our problem. To exploit the frequency diversity, we assume that the subcarrier spacing is larger than the coherence bandwidth B c experienced by each user. Each small-cell access point (SAP) is equipped with M receiving antennas while a single antenna is employed at the UEs to keep the complexity of the front-end limited.

Let h kj,n ∈ C M×1 denote the uplink channel vector whose entries [h kj,n ] m represent the (frequency) channel gains over subcarrier n from the jth UE to the mth receive antenna of user kth serving SAP, i.e., the sth SAP whose distance from user k is smaller than ρ s with k, j ∈ K = {1, . . . , K} and K = S s=1 K s . The vector x k,n ∈ C M×1 collecting the samples received at the UE k's serving SAP over the nth subcarrier can be written as

x k,n = K j=1 h kj,n √ p j,n z j,n + w k,n (1)
where w k,n ∈ C M×1 is a Gaussian vector with zero mean and covariance matrix σ 2 I M accounting for background noise, whereas p j,n and z j,n denote UE j's transmit power and data symbol over subcarrier n, respectively. To keep the complexity of the SAP at a tolerable level, a simple linear detection scheme is employed for data detection. This means that the entries of x k,n are linearly combined to form y k,n = g H k,n x k,n , where g k,n is the vector employed for recovering the data transmitted by user k over subcarrier n. The signal-to-interference-plusnoise ratio (SINR) achieved by user k at its serving SAP over subcarrier n takes the form

γ k,n = µ k,n (p -k,n )p k,n (2)
with

µ k,n (p -k,n ) = g H k,n h kk,n 2 g k,n 2 σ 2 + j =k g H k,n h kj,n 2 p j,n (3)
where we have explicitly reported the dependence on p -k,n = [p 1,n , . . . , p k-1,n , p k+1,n , . . . , p K,n ] T , which is the vector collecting all powers transmitted over subcarrier n except user k's one. Using (2), the achievable rate (normalized to the subcarrier bandwidth, and thus measured in b/s/Hz) of the kth user is given by

r k (p) = N n=1 log 2 (1 + γ k,n /Γ) ( 4
)
where Γ is the SINR gap with respect to the Shannon capacity [START_REF] Cioffi | A multicarrier primer[END_REF], and p = [p T 1 , . . . , p T K ] T ∈ R K×N + collects the transmit powers by all users over all subcarriers, where the (row) vector p k = [p k,1 , . . . , p k,N ] T denotes user k's powers over all subcarriers, with p k,n ≥ 0 (if p k,n = 0, user k is not transmitting over subcarrier n). Note that user k's multiple access interference (MAI), measured by the summation at the denominator of (3), comes from both intra-cell interference (generated by other UEs being served by the same SAP) and inter-cell interference (from UEs served by all other S -1 SAPs), whereas macro-cell users are assumed to be orthogonal thanks to a proper frequency resource planning operated by the macro-cell network (if needed, macro-cell interference can be included into σ 2 ). To simplify notations, the dependence of µ k,n and r k is not made explicit from now on.

As mentioned in Sect. I, an energy-efficient design of the network, which is of primary importance when dealing with mobile, battery-power UEs, must properly take into account the energy consumption incurred by each UE. To this aim, it is worth noting that, beside the radiative powers p k at the output of the radio-frequency front-end, each terminal k also incurs circuit power consumption during transmission, mostly due to the power dissipated in the power amplifier [START_REF] Björnson | Designing multi-user MIMO for energy efficiency: When is massive MIMO the answer?[END_REF], [START_REF] Isheden | Framework for link-level energy efficiency optimization with informed transmitter[END_REF]. The overall power consumption P T,k of the kth UE is thus given by

P T,k = p c + P k = p c + N n=1 p k,n (5)
where N n=1 p k,n = p T k 1 N is the radiative power consumed by user k over the whole spectrum, and p c represents the average current power consumed by the device electronics, which is assumed to be independent of the transmission state and equal for all UEs. Following [START_REF] Isheden | Framework for link-level energy efficiency optimization with informed transmitter[END_REF], [START_REF] Miao | Energy-efficient link adaptation in frequency-selective channels[END_REF], the energy efficiency of the link can be measured (in b/J/Hz) by the utility function

u k (p) = r k P T,k = N n=1 log 2 (1 + µ k,n p k,n /Γ) p c + N n=1 p k,n (6)
where the dependence of all others' transmit powers over all subcarriers is collected by the gains {µ k,n } N n=1 . Observe that, in data-oriented wireless networks, users are usually required to satisfy QoS requirements in terms of minimum achieved rates θ k ≥ 0, i.e., r k ≥ θ k .

To summarize, the design of an energy-efficient resource allocation scheme, that encompasses both subcarrier allocation and power control (by setting, for each UE k, p k,n = 0 on unused subcarriers, and p k,n > 0 on used subcarriers), requires to solve, for each UE k, the following optimization problem:

p ⋆ k = arg max p k ∈R N + N n=1 log 2 (1 + µ k,n p k,n /Γ) p c + N n=1 p k,n (7)
subject to p k,n ≥ 0 ∀n = 1, . . . , N (8)
N n=1 log 2 (1 + µ k,n p k,n /Γ) ≥ θ k (9)
where the constraint (8) ensures each transmit power to be positive, whereas [START_REF] Bacci | Distributed energyefficient power and subcarrier allocation for OFDMA-based small cells[END_REF] forces each user to fulfill a requirement on the minimum normalized rate θ k . Note that, unlike other formulations in the field of OFDMA resource allocation (see for example [START_REF] Wong | Multiuser OFDM with adaptive subcarrier, bit, and power allocation[END_REF], [START_REF] Tabassum | Sum rate maximization in the uplink of multi-cell OFDMA networks[END_REF]), here the subcarrier selection and power loading problems are tackled in a joint manner. Furthermore, the interplay among the UEs in K makes (7) a multidimensional optimization problem in which each UE k ∈ K aims at unilaterally choosing its own transmit power allocations p k so as to optimize its own link energy efficiency u k (p). In doing this, each UE affect the choice of all other UEs as well.

III. GAME-THEORETIC RESOURCE ALLOCATION

A natural framework for studying the strategic inter-user interactions that arise from the system model of the previous section is offered by the theory of non-cooperative games with continuous (and action-dependent) action sets. Following Debreu [START_REF] Debreu | A social equilibrium existence theorem[END_REF] (see also [START_REF] Facchinei | Generalized Nash equilibrium problems[END_REF]), we will thus consider a noncooperative game G ≡ G(K, P , u) defined as follows:

a) The players of G will comprise the set K of UEs. b) The total action set of player k representing all transmit power profiles (including possibly unfeasible ones) will be:

P nc k = {p k ∈ R N : p k,n ≥ 0 for all n = 1, . . . , N }. ( 10
) Otherwise, in the presence of the rate constraints (9), the feasible action set of player k given a power allocation profile p -k ∈ P nc -k ≡ ℓ =k P nc ℓ of other users will be:

P k (p -k ) = {p k ∈ P nc k : r k (p) ≥ θ k } . ( 11
)
c) The utility function of player k will be given by [START_REF] Debreu | A social equilibrium existence theorem[END_REF].

A first question that arises is whether this game is feasible in the sense that there exists a power allocation profile p = (p 1 , . . . , p K )

∈ k P nc k such that p k ∈ P k (p -k ) for all k ∈ K. ( 12
)
The feasibility of the game depends non-trivially on the users' channels and rate constraints [START_REF] Bacci | Distributed energyefficient power and subcarrier allocation for OFDMA-based small cells[END_REF], and it is easy to construct examples where there are no feasible profiles with finite power. 1 Albeit important in its own right, this feasibility 1 From a mathematical viewpoint, a compactification argument can be used to show that the game always admits a feasible point if infinite powers and finite rates are allowed, but, of course, this has little practical relevance. question will not be addressed here; instead, assuming that the problem is feasible, we will focus on power allocation profiles that are unilaterally stable for all users -and thus provide a sense of system-wide stability as well.

In this framework, the most widely used solution concept is a generalization of the notion of Nash equilibrium, known as Debreu equilibrium [START_REF] Debreu | A social equilibrium existence theorem[END_REF] (and sometimes also referred to as a generalized Nash equilibrium [START_REF] Facchinei | Generalized Nash equilibrium problems[END_REF]). Formally:

Definition 1: A transmit power profile p ⋆ is a Debreu equilibrium of G(K, P, u) if, for all players k ∈ K, we have p ⋆ k ∈ P k (p ⋆ -k ) and u k (p ⋆ ) ≥ u k (p k ; p ⋆ -k ) (13)
for all

p k ∈ P k (p ⋆ -k ).
Debreu equilibria are of particular interest in the context of distributed systems because they offer a stable solution of the game in which every player (in this case, the small-cell UE) is satisfied with its action choices and does not wish to deviate from (and thus destabilize the system) if other players stick to their chosen actions. Accordingly, in the rest of this section, we will treat the problem of equilibrium existence in the power allocation game G, leaving the question of convergence to such state to Sect. IV.

Debreu's original paper [START_REF] Debreu | A social equilibrium existence theorem[END_REF] provides a general existence result for games of this kind under the assumptions that:

1) the players' constrained action sets P k (p -k ) are compact, convex and nonempty for all p -k ∈ P -k ; 2) P k (p -k ) varies continuously with p -k (in the sense that the graph of the set-valued correspondence p -k → P k (p -k ) is closed); and 3) each player's utility function is quasi-concave over the player's individual actions.

In our setting, the Shannon rate function r k (p k ; p -k ) (4) is concave in p k and unbounded from above, so P k (p -k ) is convex and nonempty for all p -k ∈ P nc -k ; moreover, P k (p -k ) varies continuously with p -k since constraints [START_REF] Bacci | Distributed energyefficient power and subcarrier allocation for OFDMA-based small cells[END_REF] are themselves continuous in p -k . Finally, it can be easily shown that

u k (p k ; p -k ) is quasi-concave in p k since, for any ξ ∈ R, u k (p k ; p -k ) ≥ ξ if and only if r k (p k ; p -k ) -ξ p c + N n=1 p k,n ≥ 0, (14)
and since the set defined by this inequality is convex for every

p -k ∈ P -k (recall that r k (p k ; p -k ) is concave in p k ), our claim follows.
Unfortunately however, the sets P k (p -k ) are not compact, so Debreu's equilibrium existence result does not apply. Nonetheless, an extension of the reasoning of [START_REF] Debreu | A social equilibrium existence theorem[END_REF] leads to the following result (see Appendix A for the proof).

Proposition 1: If the game G ≡ G(K, P, u) is feasible, then it admits a Debreu equilibrium.

Having established the existence of a Debreu equilibrium, we now turn to investigate its structure. Denoting by

α k = 1 N p c - N n=1 Γ/µ k,n (15)
β k = 1 N N n=1 ln (µ k,n /Γ) (16)
the following result is proved in Appendix B using the fractional programming paradigm.

Proposition 2: At the Debreu equilibrium of G, the elements p ⋆ k,n of the optimal transmit power profile p ⋆ are the solutions to the following fixed-point system of equations:

p ⋆ k,n = 1 λ ⋆ k - Γ µ k,n + ( 17
)
where

λ ⋆ k = min λ k , λ k (18)
with

λ k = e (β k -1)-W (αk•e β k -1 ) (19)
being the water level of the water-filling operator [START_REF] Dinkelbach | On nonlinear fractional programming[END_REF] when the problem ( 7) is solved without the minimum-rate constraints (9) (or equivalently, θ k = 0 ∀k), where W (•) denotes the Lambert W function [START_REF] Corless | On the Lambert W function[END_REF], and2

λ k = 1 Γ N 1 2 θ k N n=1 µ k,n (20)
is the water level of ( 17) when all minimum-rate constraints (9) are simultaneously met with equality (i.e., [START_REF] Boyd | Convex Optimization[END_REF] reduces to a power minimization given rate constraints r k = θ k ).

IV. DISTRIBUTED IMPLEMENTATION

To derive a practical criterion to let each small-cell UE k ∈ K reach the Debreu equilibrium of G in a distributed fashion, we start by assuming that the UEs with indices j = k have already chosen their optimal transmit powers (i.e., in an asynchronous resource allocation scenario). This amounts to assuming p -k = p ⋆ -k . Hence, from (3), we have that the gains µ k,n (p ⋆ -k,n ) needed to implement (17) can be obtained by

µ k,n (p ⋆ -k,n ) = γ k,n p k,n (21)
for all n ∈ N . This means that the only information that is not locally available at the kth UE to compute the optimal powers {p ⋆ k,n } is the set of SINRs {γ k,n } measured at UE k's serving SAP, that can be fed back with a modest feedback rate requirement on the return channel (a discussion on the impact of a limited feedback can be adapted to this specific scenario from [START_REF] Bacci | Energy-efficient power control for contention-based synchronization in OFDMA systems with discrete powers and limited feedback[END_REF]).

Based on the above considerations, we can derive an iterative and fully decentralized algorithm to be adopted by each UE k at each time step t to solve the fixed-point Algorithm 1 Iterative algorithm to solve problem [START_REF] Boyd | Convex Optimization[END_REF].

set t = 0. initialize p k [t] = 0 N for all users k ∈ K repeat for k = 1 to K do {loop over the users} receive {γ k,n [t]} N n=1 from the serving SAP compute λ k using Algorithm 2 compute λ k using inverse water-filling

set λ ⋆ k = min λ k , λ k for n = 1 to N do {loop over the carriers} update p k,n [t + 1] = max 0, 1 λ ⋆ k - Γ•p k,n [t] γ k,n [t]
end for end for update

t = t + 1 until p k [t] = p k [t -1] for all k ∈ K
Algorithm 2 Iterative algorithm to compute λ k as in [START_REF] Verdú | On channel capacity per unit cost[END_REF].

set a tolerance ε ≪ 1 {initialization of the Dinkelbach method} repeat select a random λ k ∈ R for n = 1 to N do set p k,n = (1/λ k -Γ/µ k,n ) + end for compute ϕ(p k ) using (25) compute χ(p k ) using (26) set Φ(λ k ) = ϕ(p k ) -λ k • χ(p k ) until Φ(λ k ) ≥ 0 {Dinkelbach method} while Φ(λ k ) ≥ ε do set λ k = ϕ(p k )/χ(p k ) for n = 1 to N do set p k,n = (1/λ k -Γ/µ k,n ) + end for update ϕ(p k ) using (25) update χ(p k ) using (26) set Φ(λ k ) = ϕ(p k ) -λ k • χ(p k ) end while
system of equations ( 17) with a low-complexity, scalable and adaptive procedure. The pseudo-code for the whole network is summarized in Algorithm 1. Note that, in practice, each UE k needs only to implement the steps enclosed in the inner cycle, and this algorithm is thus suitable for a dynamic network configuration, since each UE only requires the SINRs fed back by the serving SAP, without any further information on the network and/or small-cell status.

For the sake of clarity, the algorithm to compute λ k as in [START_REF] Verdú | On channel capacity per unit cost[END_REF] is reported in Algorithm 2, whereas λ k can easily be computed using standard water-filling algorithms (e.g., see [START_REF] Boyd | Convex Optimization[END_REF]). Note that, although [START_REF] Verdú | On channel capacity per unit cost[END_REF] is derived analytically in a closed form, it is attractive to use the iterative method outlined in Algorithm 2, that takes advantage of the Dinkelbach method [START_REF] Dinkelbach | On nonlinear fractional programming[END_REF], a numerical method based on the application of Newton's method that significantly reduces the computational complexity compared to the evaluation of the Lambert W function. For the sake of brevity, Algorithm 2 makes use of some functions introduced in Appendix B. Throughout the simulations reported in Sect. V, the tolerance is set to ε = 10 -5 .

The convergence of Algorithm 1 to the equilibrium point is assessed numerically in the next section by means of extensive simulations. A formal proof of the convergence is beyond the scope of this work, and it is currently under investigation. A possible solution in this direction comes from the observation that the power allocation p k,n [t + 1] in Algorithm 1 is updated according to a water-filling strategy, in which the water level λ ⋆ k is computed as λ ⋆ k = min λ k , λ k . Studying the contraction properties of this water-filling operator is likely to represent the right way to prove the convergence towards the equilibrium (e.g., see [START_REF] Scutari | Optimal linear precoding strategies for wideband non-cooperative systems based on game theory -Part II: Algorithms[END_REF] for more details).

V. SIMULATION RESULTS

In this section, we propose some numerical results to evaluate the performance of the proposed algorithm for different working conditions. Throughout the simulations, we adopt the following parameters (see [START_REF] Björnson | Designing multi-user MIMO for energy efficiency: When is massive MIMO the answer?[END_REF] and references therein). We consider a 200 m × 200 m area populated by S = 8 randomly distributed small cells, each having a radius ρ s = ρ = 20 m and a forbidden area with radius 0.2 m. The set of available subcarriers is composed by N = 32 subcarriers, each having a bandwidth B ≅ 11 kHz and spaced by 350 kHz, whereas each UEs coherence bandwidth is assumed to be B c ≅ 90 kHz, using a 24-tap channel model to reproduce multipath effects. To include the effects of fading and shadowing into our model, we use a path-loss exponent equal to ς = 4. For simplicity, we assume perfect channel estimation at the receiver side, and we consider the maximum ratio combining (MRC) technique, which amounts to setting g k,n = h kk,n for all k ∈ K and n ∈ N . We also assume an SINR gap equal to Γ = 1 = 0 dB and an AWGN per-subcarrier power equal to σ 2 = 0.137 fW. Without loss of generality, we will measure the performance for a specific user (say user 1) within a small cell, by averaging over all possible positions of the users, uniformly randomizing their minimum-rate constraints θ k in [0, 20] [b/s/Hz] for k = 1. Unless otherwise specified, we assume each SAP s to be equipped with M = 2 received antennas, the number of users per small cell to be K s = 8, the nonradiative power to be p c = 100 mW, and the rate constraint for the user of interest to be θ 1 = 10 b/s/Hz.

Figs. 1 and 2 depict the average total transmit powers and the achievable (normalized) rates at the equilibrium as functions of the (normalized) distance between the observed user and its SAP, respectively, averaged over 10, 000 independent network realizations. Red lines represent the case without rate constraints θ 1 = 0 b/s/Hz, whereas blue and green lines report the cases θ 1 = 10 b/s/Hz and θ 1 = 20 b/s/Hz, respectively. As can be seen, when the UE is close to the serving SAP d 1 /ρ ≤ 0.3, the equilibrium point in the three cases is exactly the same, as the energy-efficient formulation lets the user achieve an equilibrium rate which is significantly larger than the minimum one. When on the contrary the reference user is close to the cell edge (say d 1 /ρ ≥ 0.8), the MAI becomes significant, and thus the equilibrium rate given by the energy efficient formulation approaches the minimum one. This is particularly apparent in Fig. 1, and is reflected in the average total power consumption reported in Fig. 2. This behavior, although dependent from the particular network settings, is true in general. Note that the critical normalized distance, at which r 1 (p ⋆ ) ≅ θ 1 , decreases as either the constraint θ 1 increases, or the degrees of freedom N • M , that is directly connected to the number of available resources in the network, decreases with respect to the number of users K = s N s = 64.3 Interestingly, as confirmed by numerical results not reported here for the sake of brevity, which are also in line with the simulations reported in [START_REF] Bacci | Distributed energyefficient power and subcarrier allocation for OFDMA-based small cells[END_REF], the energy efficiency (in terms of the utility (6) achieved at the equilibrium) is weakly dependent on the constraint θ 1 : although it decreases as θ 1 increases, the variation is negligible, thus introducing fairness into the network. To evaluate the impact of the circuit power p c on the energy efficiency of the system, in Figs. 3 and4 we report the performance of the proposed algorithm as a function of p c , averaged over 100, 000 independent network realizations. Note that, for all selected nonradiative powers p c ∈ [1, 100] mW, the hypothesis p c ≫ σ 2 holds, which is in line with the state of the art for radio-frequency and baseband transceiver modeling [START_REF] Björnson | Designing multi-user MIMO for energy efficiency: When is massive MIMO the answer?[END_REF]. As can be seen in Fig. 3, the total power consumption at the equilibrium P 1 (p ⋆ ) is directly proportional to p c . Otherwise stated, the energy-efficient equilibrium point is highly impacted by the nonradiative power, and bit-per-Joule metric tells us to use a radiative power which is comparable with the nonradiative one. Interestingly, the (normalized) achievable rates at the equilibrium point are r 1 (p ⋆ ) ≅ 20 b/s/Hz irrespectively of p c . This justifies the behavior of the achieved utilities at the equilibrium, reported in Fig. 4, and confirms a result which is well-known in the literature (e.g., see [START_REF] Isheden | Framework for link-level energy efficiency optimization with informed transmitter[END_REF], [START_REF] Verdú | On channel capacity per unit cost[END_REF]):

M = 1 M = 2 M = 3
Fig. 6. Average utility at the equilibrium as a function of the number of users per small cell.

the energy efficiency increases as the circuit (nonradiative) power decreases. Hence, reducing p c can achieve a two-fold goal, thus further boosting the research in this field: not only is it expedient to reduce the constant power consumption (from an electronics point of view), but also it leads energyaware terminals to reduce their radiative power when they aim at maximizing their bit-per-Joule performance (from an information-theoretic and resource-allocation perspective).

Finally, Figs. 5 and 6 report the performance of the proposed resource allocation scheme as a function of the number of users per cell K s for three different receive architectures: M = 1 (red lines), M = 2 (blue lines), and M = 3 (green lines) antennas, respectively. As can easily be guessed, the degrees of freedom N •M impact on the occurrence of feasible scenarios: as confirmed by simulations, when the total number of users K = 8N s is larger than N • M = 32M , the resources available in the network are scarce to accommodate all the rate requests θ k . To provide significant performance results, we plot only network configurations that yield feasible scenarios with an occurrence larger than 70% of the times. This is the reason why only K s ≤ 5 is reported for the case M = 1, whereas M = {2, 3} are able to accommodate a larger population of users without impacting on the required minimum performance θ k . As can be seen in Fig. 5, increasing the number of users K s increases the contribution from both intra-cell and inter-cell MAI, which in turn decreases the average normalized achievable rate at the equilibrium. However, note that increasing M yields a larger r 1 (p ⋆ ), since the SAP can better separate the users due to a larger space diversity given by the singleinput-multiple-output (SIMO) configuration (and thus a larger number of degrees of freedom). This behavior is confirmed by Fig. 6, that measured the utility (6) as a function of the same parameters. As expected, in all network configurations increasing K s decreases u 1 (p ⋆ ), due to increasing the MAI. However, note that the difference is not significant for all receiver configurations. This means that, if the only concern is the energy efficiency of the system, then increasing the number of antennas does not yield significant advantages. On the contrary, if also the spectral efficiency is critical (i.e., if larger θ k 's are needed), then increasing M is a viable solution to achieve a proper resource allocation, as witnessed by larger achievable rates at the equilibrium (see Fig. 5). It is worth noting that these considerations hold true due to adopting a MRC technique, which is suboptimal for a proper MAI management. Other schemes, such as zero-forcing (ZF) or minimum mean-square error (MMSE) approaches, which are out-of-scope of the present contribution, might lead to exploiting better the spatial diversity of the MISO configurations, and thus larger differences in the achieved energy efficiency.

VI. CONCLUSIONS AND PERSPECTIVES

In this paper, we proposed a distributed power allocation scheme for energy-aware, non-cooperative wireless users with minimum rate constraints in an uplink multicarrier smallcell network. By modeling this scenario as a non-cooperative game in the sense of Debreu, we proved the existence of an equilibrium state and we characterized it as the fixed point of a water-filling operator using techniques borrowed from fractional programming. To attain this equilibrium in a distributed fashion, we also proposed an iterative solution method based on an iterative water-filling best response process, whose convergence and performance was assessed by numerical simulations. Performance results show that reducing the nonradiative power consumed by the user device electronics is particularly critical to improve the performance of mobile terminals in terms of energy efficiency, which is also highly impacted by the receiver configuration. Further work is needed: i) to assess the feasibility of the problem given a particular network realization; ii) to analytically prove the convergence of the iterative algorithm to the equilibrium point; iii) to assess its complexity as a function of the system parameters; and iv) to evaluate the impact of different receiver architectures on the spectral and energy efficiency of the network.

APPENDIX A PROOF OF PROPOSITION 1

Fix some power vector p k ∈ P nc -k , and let P ⋆ k (p -k ) ≡ arg max{u k (p k ; p -k ) : p k ∈ P k (p -k )} be the best response set of player k to the power profile p -k of the other players. By the quasi-concavity of u k and Lemma 1 below, it follows that P ⋆ k is compact; as a result, letting M k (p -k ) denote the maximum value of u k over P k (p -k ), it follows that the set

P ′ k (p -k ) ≡ {p k ∈ P nc k : u k (p k ; p -k ) ≥ (1 -ε)M k (p -k )} (
22) will also be compact if ε is chosen sufficiently small. Define now the restricted game G ′ ≡ G ′ (K, P ′ , u) with the same data as G except for the fact that the players' constrained action sets are now given by ( 22). Seeing as the sets P ′ k (p -k ) are compact (by construction) and vary continuously with p -k (simply note that all the functions involved in the definition of P ′ k (p -k ) are themselves continuous),4 G ′ will admit a Debreu equilibrium by Theorem 1 in [START_REF] Debreu | A social equilibrium existence theorem[END_REF]. On the other hand, given that the best response set P ⋆ k (p -k ) of player k against p -k in G is contained in P ′ k (p -k ) for all p -k ∈ P nc -k and for all k ∈ K, it follows that any equilibrium of the restricted game G ′ will also be an equilibrium of G, and our proof is complete. Proof: If the maximum set Ω f of f is not compact, there will exist an unbounded sequence p m ∈ Ω f , so, by descending to a subsequence of p m if necessary, we may assume that p n,m → ∞ for some n. However, since lim p→∞ log(1 + ap)/p = 0 for all a > 0, this implies that the maximum value of f will be 0, a contradiction.

APPENDIX B PROOF OF PROPOSITION 2

The constrained optimization [START_REF] Boyd | Convex Optimization[END_REF] can be cast into the paradigm of fractional programs, which are nonlinear programs where the objective function is a ratio of two real-valued functions. In particular, (7) can be rewritten as

p ⋆ k = arg max p k ∈P k (p -k ) ϕ(p k ) χ(p k ) (24)
where P k (p -k ) is defined as in [START_REF] Cioffi | A multicarrier primer[END_REF], and

Hence, considering p ⋆ k,n ≥ 0, the optimal power allocation becomes the waterfilling criterion [START_REF] Dinkelbach | On nonlinear fractional programming[END_REF], in which the water level λ ⋆ k is replaced by λ k . By plugging (29) back into (27), we can finally compute the optimal power level λ k :

-ln λ k + (β k -1) = α k λ k ( 30
)
where the functions α k and β k are defined as in ( 15) and ( 16), respectively. To provide a better insight on (30), let us try to write it in a closed form. To this aim, let us define

ν k = -ln λ k + (β k -1) (31)
so that (30) can be rewritten as

ν k • e ν k = α k • e β k -1 . (32)
Using the Lambert function W (•), and inverting (31), after straightforward manipulation we get λ k as in [START_REF] Verdú | On channel capacity per unit cost[END_REF].

When introducing back the constraint (9), we are placing a lower bound on ϕ(p k ): ϕ(p k ) ≥ θ k . Following [START_REF] Isheden | Framework for link-level energy efficiency optimization with informed transmitter[END_REF], this is equivalent to placing an upper bound λ k on λ k , that comes out of the inverse waterfilling criterion that minimizes χ(p k ) given ϕ(p k ) = θ k , and is equal to (20). Hence, the solution to [START_REF] Boyd | Convex Optimization[END_REF] is given by [START_REF] Dinkelbach | On nonlinear fractional programming[END_REF], with λ ⋆ k computed as in [START_REF] Scutari | Optimal linear precoding strategies for wideband non-cooperative systems based on game theory -Part II: Algorithms[END_REF].

  Fig. 1. Average normalized rate at the equilibrium as a function of the normalized distance from the SAP.

θ 1

 1 Fig. 2. Average transmit power at the equilibrium as a function of the normalized distance from the SAP.

Fig. 3 .

 3 Fig. 3. Average transmit power at the equilibrium as a function of the circuit power.

Fig. 4 .

 4 Fig.[START_REF] Isheden | Framework for link-level energy efficiency optimization with informed transmitter[END_REF]. Average utility at the equilibrium as a function of the circuit power.

Fig. 5 .

 5 Fig. 5. Average normalized rate at the equilibrium as a function of the number of users per small cell.

Lemma 1 :

 1 Let a n > 0, n = 1, . . . , N , be positive constants, and let b > 0. Then, the solution set of the problem maximize f (p) = N n=1 log (1 + a n p n )

ϕ(p k ) = N n=1 ln( 1 +

 n=11 µ k,n p k,n /Γ), (25)χ(p k ) = p c + N n=1 p k,n .(26)Using [4, Sect. II.A] we can see that solving problem (24) is equivalent to finding the root of the following nonlinear function:Φ(λ k ) = max p k ∈P k (p -k ) ϕ(p k )λ k χ(p k )(27)where λ k ∈ R. To compute the solution of (24), let us first use (25) -(26), but without the constraint (9), so that p k ∈ R N + (i.e., only nonnegative powers are considered). The stationarity condition given by∂ϕ(p k ) ∂p k,n p k,n =p ⋆ k,n λ k ∂χ(p k ) ∂p k,n p k,n =p ⋆ n = 1, . . . , N using (25) -(26) becomes µ k,n /Γ 1 + µ k,n p ⋆ k,n /Γ λ k = 0 n = 1, . . . , N.

The closed-form expressions[START_REF] Verdú | On channel capacity per unit cost[END_REF] and (20) apply only when all subcarriers n are active, i.e., p k,n > 0. Please refer to Sect. IV for a practical method to compute λ k and λ k in the general case p k,n ≥ 0.

A rule of thumb to properly drive the network is to have N • M ≥ K. In this case, we have on purpose reported a borderline scenario, in which N = 32, M = 2, and K = 64 = N • M .

Importantly, given that the arg max operator is not continuous, this continuity property might fail if we had taken P ′ k (p -k ) ≡ P ⋆ k (p -k ). By artificially enlarging the players' best-response set, continuity is guaranteed.