Rachael Colley
email: rachael.colley@irit.fr

Umberto Grandi
email: umberto.grandi@irit.fr

Arianna Novaro
email: arianna.novaro@irit.fr

Smart Voting

We propose a generalisation of liquid democracy in which a voter can either vote directly on the issues at stake, delegate her vote to another voter, or express complex delegations to a set of trusted voters. By requiring a ranking of desirable delegations and a backup vote from each voter, we are able to put forward and compare four algorithms to solve delegation cycles and obtain a final collective decision.

Introduction

Advances in information technology are opening up avenues for the improvement of democratic practices and collective decision-making processes (see, e.g., [START_REF] Brill | Interactive democracy[END_REF]). One of the most popular ideas is to explore the space between direct democracy-often infeasible due to the limited amount of resources decision-makers can invest in each direct vote-and representative democracy, by allowing for transitive delegations to take place among agents. This method is named liquid democracy, in contrast to proxy voting in which delegations are not transitive [START_REF] Miller | [END_REF]. Liquid democracy has been the subject of numerous recent investigations in AI, ranging from analysing its truth-tracking power [START_REF] Cohensius | [END_REF][START_REF] Bloembergen | [END_REF][START_REF] Kahng | [END_REF] to its adaptation for multiple issues and alternatives [START_REF] Christoff | [END_REF][START_REF] Brill | Pairwise liquid democracy[END_REF]. In its simplest form, liquid democracy works as follows: a collective decision needs to be taken on a binary issue; agents can either vote directly or delegate their vote to a single other agent; direct votes are then weighted by the number of transitive delegations received, and a final decision is taken using a standard voting rule.

In this paper we propose to push forward the idea of liquid democracy under two aspects. First, while most implementations of liquid democracy [see, e.g., [START_REF] Behrens | [END_REF] introduce a platform for the elicitation of voters' delegations, we aim at a decentralised voting system in which voters' ballots and delegations can remain private. Thus, we define a language for voters to express a direct vote, or a delegation to a single other agent, or a combination of the votes of multiple other agents. Second, to tackle the issue of delegation cycles we allow voters to express a number of prioritized delegations, with a final backup vote with the lowest priority. An example of what we call a smart ballot can be seen on the right-hand side of Figure 1. Two possible practical implementations can be envisaged for smart voting. The first is a fully decentralised version that might make use of smart contract technology (hence the title of this paper), where a smart ballot would be a piece of self-executable and publicly available code included in a blockchain, with full transparency and accountability of the election procedure. 1 The second, in applications where vote secrecy is crucial, is a more standard method of votes being collected by a trusted central authority-raising interesting computational questions on providing a certificate to each voter that their ballot has been taken into account. Our contribution. We define a script language for voters to express ranked, possibly complex, delegations in collective decisions with multiple issues (Section 2). The intended application is voting in a purely preferential setting (deciding on food is a perfect example [see, e.g., Hardt and Lopes, 2015]), and delegations are seen as a way to elicit trust or influence relations among voters. To transform profiles of smart ballots into direct votes for alternatives we propose four unravelling procedures (Section 2), and we show that they terminate in polynomial time (Section 3). The final objective of smart voting is that of obtaining a collective decision from the agents' ballots, and we assume here that a standard voting rule is applied on the outcome of the proposed unravelling procedures. We investigate further algorithmic properties of our setting in Section 3, and we conclude with a study of ranked delegations to single voters and participation axioms (Section 4). Some proofs are sketched or omitted due to space constraints. Related work. Recent papers have analysed the efficacy of liquid democracy and proxy voting as a truth-tracking mechanism, mostly for a binary decision [Green-Armytage, 2015;[START_REF] Cohensius | [END_REF][START_REF] Kahng | [END_REF][START_REF] Caragiannis | Ioannis Caragiannis and Evi Micha. A contribution to the critique of liquid democracy[END_REF][START_REF] Bloembergen | [END_REF]. We do not study truth-tracking here, and rather propose a method to elicit mutual influence from voters and infer a collective decision.

This work takes inspiration from papers trying to solve the issue of delegation cycles. As in the work of [START_REF] Kotsialou | Grammateia Kotsialou and Luke Riley. Incentivising participation in liquid democracy with breadth-first delegation[END_REF] and [START_REF] Escoffier | [END_REF]2020], we let voters express a ranking of possible delegates, to break potential cycles of delegations. 2 We also draw inspiration from Degrave [2014] and [START_REF] Abramowitz | Flexible representative democracy: An introduction with binary issues[END_REF] in allowing a delegation to be spread to multiple voters. However, we keep the transitivity of delegations and stick to the principle of "one person, one vote" in not splitting the voting power of any individual. We also borrow from [START_REF] Christoff | [END_REF] the requirement that voters must specify a default value (i.e., a backup vote) on each issue.

Generalisations of liquid democracy have been studied by [START_REF] Christoff | [END_REF] on multiple logically connected issues, and by [START_REF] Brill | Pairwise liquid democracy[END_REF], who consider delegations on pairwise preferences on alternatives. We assume here votes on multiple independent issues, and we also do not consider aspects of strategic voting or analysis of voters power, as done by [START_REF] Escoffier | [END_REF] and [START_REF] Gölz | [END_REF].

In allowing voters to express complex delegations combining the votes of other agents, we follow the vast literature on social influence and opinion diffusion on networks [see, e.g., [START_REF] Easley | [END_REF], and most notably, research studying the use of aggregation functions such as majority in binary opinion diffusion [START_REF] Grandi | [END_REF][START_REF] Bredereck | Manipulating opinion diffusion in social networks[END_REF][START_REF] Auletta | [END_REF].

Formal Framework

We define here the components of our model for smart voting.

Smart Ballots

In smart voting we have a set N of n agents (or voters) who decide on a set I of m issues. The alternative values, or simply alternatives, for each issue i ∈ I range over a non-empty finite domain D(i), which can also include abstention.

An agent a expresses her opinion over an issue i ∈ I by submitting a (valid) smart ballot B ai defined as follows: Definition 1 (Smart Ballot). A smart ballot of agent a for an issue i ∈ I is an ordering

((S 1 , F 1 ) > • • • > (S k , F k ) > x)
where k ≥ 0 and for 1 ≤ h ≤ k we have that S h ⊆ N is a set of agents, F h : D(i) S h → D(i) is a resolute aggregation function and x ∈ D(i) is an alternative.

Thus, a smart ballot can be seen as a preference ordering over the agent's desired delegations, ending with a direct backup vote for an alternative in the issue's domain. Definition 2 (Valid Smart Ballot). A valid smart ballot of agent a for an issue i ∈ I is a smart ballot such that, for all 1 ≤ s = t ≤ k, (i) if S s ∩ S t = ∅ then F s is not equivalent to F t , and (ii) a / ∈ S s .

The two validity requirements ensure that agents are not manipulating the election by submitting many equivalent versions of the same delegation function, and that they are not generating delegation loops by including themselves in the set of delegates. The following example shows the expressiveness of smart ballots: Example 1. Alice, Bob, Carl, and Diana, wonder whether to try a new restaurant (1) or stay in (0). Alice knows that her friends are real foodies, and she is too tired to check online reviews. She would like to state this complex delegation: "I vote to go if and only if Bob, and at least one of Carl or Diana, think it's worth it.3 If that creates a delegation cycle, I will copy Bob's vote. If that also creates a cycle, I will vote to go". She submits the following smart ballot:

• (({B, C, D}, B ∧ (C ∨ D)) > ({B}, B) > 1).
The next ballot represents Alice wanting to delegate to Bob, then Carl, then Diana, and as a last resort voting to go:

• (({B}, B) > ({C}, C) > ({D}, D) > 1).
This last ballot expresses Alice wanting to vote with the majority opinion of her friends, and otherwise voting to go:

• (({B, C, D}, Maj) > 1). Let B h
ai denote the h th preference level given by agent a on issue i in her smart ballot B ai -thus, B h ai = (S h ai , F h ai ) or B h ai = x with x ∈ D(i). For instance, in Example 1 we have in the second case that B 2 Ai = (S 2 Ai , F 2 Ai ) = ({C}, C). Given n smart ballots for an issue i ∈ I from each agent in N , a (smart) profile for this issue i, is a vector B i = (B 1i , . . . , B ni ). A valid (smart) profile is a smart profile where each smart ballot is valid (as per Definition 2).

Unravelling Procedures

In this section we propose four procedures that transform a valid smart profile into a profile of direct votes, i.e., votes supporting a single alternative in the issue's domain, D(i). Definition 3 (Unravelling Procedure). An unravelling procedure U for issue i ∈ I and agents in N is any function

U : (B 1i × • • • × B ni ) → D(i) n .
Due to possible delegation cycles, it may be unclear how to assign direct votes to agents. We follow two principles in our definitions: use the highest preference level of voters when breaking delegation cycles (cf. Definition 4), and keep the unravelling process polynomial (cf. Section 3). Algorithm 1 outlines our general unravelling procedure UNRAVEL.

The input of UNRAVEL is a smart profile B i . A vector X is initialised with placeholders ∆ at each position x a for a ∈ N Algorithm 1 General unravelling procedure UNRAVEL 1: X := (∆, . . . , ∆) empty vector for direct votes 2: while X / ∈ D(i) n do 3:

lev := 1 reset preference level counter to 1 4:

Y := X a copy of X to compute changes 5:

while X = Y do 6:

procedure UPDATE({U, RU, DU, DRU})

7:

lev := lev + 1 8: return X output vector of direct votes and it is returned when a vote in D(i) is found for all agents.

Counter lev is set at the first preference level of the agents and an additional vector Y is added to help computation. In line 6 a subroutine with one update procedure is executed. 4We give four update procedures, defined by the presence or absence of two properties. Namely, direct vote priority (D), prioritising direct votes over those that can be computed from the current vector Y of votes; and random voter selection (R), randomly choosing an agent whose vote is added (or computed) next. The four procedures are thus: basic update (U), update with direct vote priority (DU), update with random voter selection (RU), update with direct vote priority and random voter selection (DRU).

Unless otherwise specified, if the condition in an if statement fails, the program skips to the next step. Moreover, Y S denotes the restriction of vector Y to the elements in set S.

Algorithm 2 UPDATE(U) 1: for a ∈ N such that x a = ∆ do 2: if B lev ai ∈ D(i) then
a has a direct vote at lev 3:

x a := B lev ai 4:

else if F lev ai (Y S lev ai ) ∈ D(i) then 5:
x a := F lev ai (Y S lev ai ) add a's computable vote UPDATE(U) checks for each agent without a direct vote at lev (line 1): if their preference at lev is either a direct vote (line 3) or can be computed from the current values in Y (line 5), then vector X is updated with the new direct votes.

Algorithm 3 UPDATE(DU) 1: for a ∈ N such that x a = ∆ do 2: if B lev ai ∈ D(i) then add direct votes 3: x a := B lev ai 4: if Y = X then if no direct vote added to X 5: for a ∈ N such that x a = ∆ do 6: if F lev ai (Y S lev ai ) ∈ D(i) then find computables 7:
x a := F lev ai (Y S lev ai ) UPDATE(DU) first tries to add directs votes to X (line 2); if there are none (line 4) it tries with votes computable at lev.

At line 1 of UPDATE(RU) an empty set P is initialised to hold agents with either a direct vote or a computable vote at Algorithm 4 UPDATE(RU)

1: P := ∅ initialise an empty set 2: for a ∈ N such that x a = ∆ do 3: if B lev ai ∈ D(i) or F lev ai (Y S lev ai ) ∈ D(i)
x b := B lev bi 9: else if F lev bi (Y S lev bi ) ∈ D(i) then 10: x b := F lev bi (Y S lev bi )
lev (line 3); if P is non-empty, one agent will be randomly chosen and her direct/computable vote is added to X.

Algorithm 5 UPDATE(DRU)

1: P, P := ∅ initialise an empty set 2: for a ∈ N such that x a = ∆ do x

b := F lev bi (Y S lev bi )
UPDATE(DRU) first selects agents with a direct vote at level lev (line 3) and chooses one randomly to update X (line 9). If not, UPDATE(DRU) will repeat this process, but it will now look for computable votes at level lev.

The following example shows how UPDATE(U) works: Example 2. Consider a binary issue i with D(i) = {0, 1} and agents N = {A, . . . , E}. Their valid ballots in B i , stating their preferences for delegations or direct votes, are shown schematically in the table below and in Figure 2.

1 st 2 nd 3 rd A ({B, C}, B ∧ C) ({D}, D) 1 B 1 - - C ({D}, D) 0 - D ({E}, E) 1 - E ({A}, A) ({B}, B) 0
We spell out here the unravelling UNRAVEL(U) on B i :

• Starting at lev = 1, the direct vote of B is stored in X = (∆, 1, ∆, ∆, ∆).
• As there are no direct or computable votes at lev = 1 (using Y ), the level counter is increased to lev = 2. • The procedure adds the direct votes of C and D, and computes the vote of E from the current Y by copying the vote of B, obtaining X = (∆, 1, 0, 1, 1).

A 1 • The preference level is set back to lev = 1.

B ∧ C C 0 B 1 D 0 E 1
• A's vote can be computed from her first preference level, and vector X = (0, 1, 0, 1, 1) is thus returned.

An important clarification is that in all our procedures, when checking if an agent's vote can be computed from a partial profile of other agents' votes, we test the existence of a necessary winner [START_REF] Konczak | [END_REF]. Formally, F lev ai (X S lev ai ) has a necessary winner y ∈ D(i) if for all a ∈ S lev ai such that x a = ∆, for all z ∈ D(i) such that x a = z we have that F lev ai (X S lev ai ) = y.5 We conclude with two further definitions. The notion of vote certificate can explain to an agent which part of their ballot was used to compute the unravelled profile, without revealing the full profile: Definition 4 (Certificates). An agent a's certificate of an un-

ravelled profile U(B i ) is Cert U (B i , a) = (k, X S k ai ),
where k is a preference level and X S k ai is the partial profile of direct votes used by U to compute a's vote.

We can then define the set of voters influenced by a voter a: Definition 5 (Influence). The set of voters influenced by voter a in profile B i using unravelling procedure U is

I U (B i , a) = {b | a ∈ S k bi for Cert U (B i , b) = (k, X S k bi )}. Let I U * (B i , a)=I U (B i , a)∪{c|c∈I U (B i , b)∧b∈I U (B i , a)} ∪.
. . be the voters b indirectly influenced by a. In Example 2, we have that Cert U (B i , C) = (2, ∅) and I U (B i , C) = {A}.

Restricting the Language of Smart Ballots

In this section, we define useful restrictions to the language of smart ballots. Firstly, we focus on binary Boolean functions compactly expressed as contingent (i.e., neither a contradiction, nor a tautology) propositional formulas in DNF: Definition 6 (BOOL Ballots). A smart ballot B ai for agent a and binary issue i belongs to language BOOL if every F h ai in B ai is a contingent propositional formula in DNF.

Therefore, BOOL ballots can only contain Boolean functions-as, for instance, all the delegating ballots in Example 2. Atomic boolean functions are equivalent to the identity function, i.e., copying another agent's vote. The requirement for a contingent formula is to prevent agents from overriding the delegation structure by giving a direct vote for 1 or 0 in disguise at multiple preference levels. When using language BOOL, we will write ϕ lev ai instead of F lev ai . Next, we define a restriction for smart ballots where all of the (possibly many) delegations must be to single agents: Definition 7 (LIQUID Ballots). Smart ballot B ai for agent a and issue i belongs to LIQUID if every delegating B h ai in B ai is of the form ({b}, id) for b ∈ N \ {a} and id the identity function, and if h > 1 the final vote of a is abstention ( * ).

Finally, for a given language L we write L k to indicate smart ballots in L having at most k delegations in their ordering. For instance, in Example 2 the smart ballots of all agents belong to the language BOOL 2 .

Voting Rules

The final step of smart voting aggregates the vector of direct votes into an outcome. For the remainder of the paper, we will use the following rules (for a domain with abstentions * ): the majority rule (Maj) returns the alternative in the domain having more than n /2 votes, and * otherwise; the relative majority rule (RMaj) returns the plurality outcome among D(i) \ { * }, and if there is a tie it returns * .

Algorithmic Analysis

We here analyse the unravelling procedures introduced in Section 2.2. For simplicity, in the rest of the paper we assume that I contains a single issue (thus, we drop the subscript i).

Properties of Unravelling

Given the four update procedures, our first result shows that for any valid smart profile the general unravelling procedure UNRAVEL always terminates: Proposition 1. Algorithms UNRAVEL(U), UNRAVEL(DU), UNRAVEL(RU) and UNRAVEL(DRU) always terminate on a valid smart profile B.

Proof (sketch). The proof (omitted in the interest of space) rests on the fact that the two while loops in UNRAVEL cannot be in an infinite cycle due to each B a having a finite number of preference levels,6 the final preference being a direct vote, and each procedure updating at least one agent's direct vote in X at each iteration (and removing none).

In the next proposition we prove that the four update procedures actually give different results. Proposition 2. There exists a valid smart profile B for which UNRAVEL(U), UNRAVEL(DU), UNRAVEL(RU), and UNRAVEL(DRU) give different outputs.

Proof. Consider the smart profile of Example 2: the outcomes of the four unravelling procedures are shown in Table 1. It is clear that procedures U and DU lead to different outcomes than the others. Although procedures RU and DRU give the same profiles of direct votes, these outcomes occur at different rates. 1,1,1,1,1) D

UNRAVEL Output X ∈ D(i) n Random voter U (0, 1, 0, 1, 1) - DU (0, 1, 0, 1, 0) - RU (0, 1, 0, 0, 0) C (1, 1, 1, 1, 1) D (1, 1, 1, 1, 1) E DRU (0, 1, 0, 0, 0) C (
Table 1: The last column indicates, for procedures RU and DRU, which voters have been picked (only one random choice here).

Observe that the proof above implies that the collective decision can be different depending on the unravelling used, and on the randomly chosen voter. The majority outcome would be 1 in two thirds of the cases with procedure RU, whereas only in half of the cases when using procedure DRU.

Computational Complexity

The first problem we study is how hard it is to verify that a smart ballot is valid with respect to language L. The VALIDB(L) problem takes as input a smart ballot B a in L and agents N , and it asks if B a is valid for L.

Theorem 1. VALIDB(BOOL k ) is NP-complete, for k ≥ 1.
Proof. For membership, observe that for B a to be a valid BOOL k ballot, it needs to verify the following properties (for 1 ≤ h, ≤ k), that can either be checked in polynomial time by reading B a , or require a (polynomial) certificate. The properties are: there are ≤ k top preferences of the form (S h a , ϕ h a ); there is one direct vote in {0, 1} as final preference; each ϕ h a is in DNF; each S h a is such that a / ∈ S h a ; and each ϕ h a is such that V ar(ϕ h a ) ⊆ S h a ⊆ N . For the final three properties, we have to guess certificates: at most k to check that each ϕ h a is not a tautology (¬ϕ h a is satisfiable); at most k to check that each ϕ h a is not a contradiction (ϕ h a is satisfiable); at most k 2 (k -1) to check that for all ϕ h a and ϕ a such that h = , ϕ h a and ϕ a are not logically equivalent (i.e., ¬(ϕ h a ↔ ϕ a ) is satisfiable). All this requires at most k 2 (k + 3) certificates for constant k. Thus, VALIDB(BOOL k ) is in NP.

For hardness, we reduce from the NP-complete problem DNF-FALSIFIABLE,7 whose input is a formula ϕ in DNF. We create an instance of VALIDB(BOOL k ) where N = V ar(ϕ) ∪ {a, b}, for fresh variables a and b, D(i) = {0, 1} and B a = ((N \{a}, ϕ ∨ b) > 1). We now show that DNF-FALSIFIABLE has a positive answer if and only if the answer to VALIDB(BOOL k ) on our instance is also positive.

Assume that ϕ is falsifiable. By construction of B a , we only need to check that ϕ ∨ b is neither a contradiction nor a tautology: this follows from ϕ being falsifiable and b being a fresh variable. Assume that ϕ is not falsifiable, i.e., ϕ is a tautology. Thus, agent a provides a function ϕ ∨ b which is a tautology, and hence B a is not valid. Therefore, VALIDB(BOOL k ) is NP-complete.

Although checking if a BOOL k smart ballot is valid is not a tractable problem, it is as hard as the SAT problem for propositional formulas, for which efficient solvers exist.

Next, we show that our unravelling procedures terminate in polynomial time given BOOL ballots. We refer to this problem as UNRAVEL(#) L for # ∈ {U, DU, RU, DRU}. Observe that the size of the input for UNRAVEL(#) BOOL is in O(max p (B) • n • max ϕ (B)), where max p (B) is the highest preference level of any ballot in B and max ϕ (B) is the maximum length of any formula from an agent in B. Proposition 3. UNRAVEL(#) BOOL terminates in at most O(n 2 • max p (B) • 2 max ϕ (B)) time steps, for # ∈ {U, DU, RU, DRU}.

Proof. The while loop from line 2 in UNRAVEL can be repeated at most n times (in case just one direct vote is added to X at each iteration). Moreover, the while loop from line 5 can be repeated at most max p (B) times, in case all smart ballots are of the same length and no vote is computable in the first max p (B) -1 positions for any agent.

The following is executed at most n • max p (B) times: UP-DATE(#) checks that for each agent a such that x a = ∆ (at most n) either B lev a ∈ D(i) or ϕ lev a has a necessary winner (depending on the # used). As each ϕ lev a is in DNF, i.e., a disjunction of conjunctions of literals (called cubes), to verify if it has a necessary winner we check if either:

1. all literals of a cube of ϕ lev a are made true by X S lev a , 2. one literal in each cube is made false by X S lev a , returning a direct vote of 1 or 0, respectively. The use of UPDATE(#) takes at most O(n • 2 max ϕ (B)) steps. Hence, in O(n 2 • max p (B) • 2 max ϕ (B)) time steps a profile X of direct votes is output by UNRAVEL(#) BOOL .

Ranked Singleton Delegations

In this section we focus on the language LIQUID k from Definition 7. Agents are restricted to express either a direct vote or a (partial) ranking of single-agent delegations.

Liquid Democracy

We begin by showing that our unravelling procedures yield the same result on the language LIQUID 1 , corresponding to the simplest setting of liquid democracy: Proposition 4. If B ∈ LIQUID 1 then UNRAVEL(#) outputs the same result for # ∈ {U, DU, RU, DRU}.

Proof (sketch). At the first iteration step, all direct votes are added to the vector X. Each unravelling procedure then computes the votes of those agents who are delegating but are not in a delegation cycle (possibly not in the same order, but with the same result). Cycles are broken by looking at backup votes of possibly different agents, which are all abstentions by the definition of LIQUID 1 . Now, consider an example of liquid democracy. By creating a profile of smart ballots with B a = (({b}, id) > * ) if agent a was delegating her decision to agent b ∈ N \{a} and B a = (x) with x = * if agent a was voting directly, we obtain the following result:

Proposition 5. Liquid Democracy can be translated into a smart voting election with LIQUID 1 ballots and UNRAVEL(#) for # ∈ {U, DU, RU, DRU}.

The proof of Proposition 5 is omitted for lack of space.

Participation Axioms

In this section we study two properties of unravelling procedures, focussing on a binary domain (with abstentions). The first, proposed by [START_REF] Kotsialou | Grammateia Kotsialou and Luke Riley. Incentivising participation in liquid democracy with breadth-first delegation[END_REF], was inspired by the classical participation axiom from social choice [Moulin, 1988]. Both properties focus on a voter's incentive to participate in the election, either by voting directly or by delegating. Thus, we assume that an agent a expressing a direct vote for alternative x ∈ {0, 1} prefers x over 1 -x, denoted by x > a 1 -x, and that a prefers x over abstention, x > a * . Definition 8 (Cast-Participation). A voting rule r and unravelling procedure U satisfy cast-participation if for all valid smart profiles B and agents

a ∈ N such that B a ∈ D(i)\{ * } r(U(B)) ≥ a r(U(B -a , B a ))
for all B a = B a , and B -a is equal to B without a's ballot.

Cast-participation implies that agents who vote directly have an incentive to do so, rather than to express any other ballot (recall our restriction to ranked singleton delegations).

A voting rule r on the domain {0, 1, * } N satisfies monotonicity if for any profile X, if r(X) = x with x ∈ {0, 1} then r(X +x ) = x, where profile X +x is obtained from X by having one voter switch from an initial vote of 1 -x to x or * , or from an initial vote of * to x. Observe that all rules introduced in Section 2.4 satisfy this property. Due to this definition we can now show the following: Theorem 2. Any monotonic rule r with unravelling procedure UNRAVEL(#) for # ∈ {U, DU, RU, DRU} satisfies cast-participation for LIQUID.

Proof (sketch). Without loss of generality, assume that for agent a ∈ N we have B a = (1); thus for a it is the case that 1> a 0. To falsify cast-participation, we need to construct a profile B such that r(UNRAVEL(#)(B))=0 or * , and a smart ballot B a such that r(UNRAVEL(#)(B -a , B a ))=1.

If a now delegates to an agent with a direct vote for 1, the outcome does not change. Therefore, all voters c ∈ I # * (a, B) vote for 1 in B, but vote for either 0 or * in B (i.e., the final votes of B can be obtained from those of B by switching 1s to 0s or * s). Moreover, all c ∈ I # * (a, B) do not change their vote from B to B . Thus, this contradicts the monotonicity assumption of voting rule r.

The theorem above does not hold for non-singleton delegations-we omit the proof in the interest of space.

We now focus on the incentive that a voter has to receive and accept delegations. Recall that I # * (B, a) is the set of agents who are directly or indirectly influenced by a's vote. Definition 9 (Guru-participation). A voting rule r and unravelling procedure U satisfy the guru-participation property if and only if for all profiles B and all agents a ∈ N such that B a = (x) with x ∈ D(i) \ { * } we have that The outcomes of the four procedures are shown here:

# B B U/ DU X 1 = (1, 1, 0, 0, 1, 0) X 2 = (1, * , * , * , 1, 0) RU/ X 3 = (1, 1, 1, 1, 1, 0) DRU X 4 = (1, 0, 0, 0, 1, 0)

X 5 = (1, 0, 0, 0, 1, 0)

By applying unravelling procedures U and DU, agent a prefers the outcome from B to B, since RMaj(X 1 ) = * and RMaj(X 2 ) = 1. For procedures RU and DRU, the outcome on B is RMaj(X 2 ) = 1. However, their outcome on B can be either RMaj(X 4 ) = RMaj(X 5 ) = 0 or RMaj(X 3 ) = 1. Agent a strictly prefers the outcome from B , which is certainly 1, over profile B which leads to an outcome of 0 for two thirds of the cases.

Observe that the profile in the above proof shows that our unravelling procedures differ from those of [START_REF] Kotsialou | Grammateia Kotsialou and Luke Riley. Incentivising participation in liquid democracy with breadth-first delegation[END_REF], as their depth-first procedure on B would output (1, 0, 1, 0, 1, 0), while their breadth-first procedure on B would give (1, * , 0, 0, 1, 0). The breadth-first procedure does satisfy guru-participation, but at the price of using delegations that are quite low in the voters' rankings.

Conclusion

In this paper we propose and study an extension of liquid democracy that accounts for ranked and multi-voter delegations. We introduce four unravelling procedures to transform voters' ballots into profiles of direct votes, on which a collective decision is taken using a standard voting rule. Our procedures are polynomial, and aim at making use of the highestranked delegations when breaking delegation cycles.

With our proposal we want to put forward a general framework to study delegative voting, with notable examples being the classical settings of liquid democracy. Future work will include the investigation of further axiomatic properties for unravelling procedures and delegative voting, in line with the participation axioms, and a more fine-grained analysis of restricted languages for smart ballots.

Figure 1 :

 1 Figure1: A profile of binary votes in liquid democracy on the left: voter A delegates her vote to B, who in turn delegates to C, who casts a direct vote in favour, unlike D who casts a direct vote against. On the right, a profile of smart ballots: voter A wants her vote to coincide with the majority of B, C, and D's votes, and in case this leads to a delegation cycle she gives a single delegation to B. Voter B delegates to D, who casts a direct vote against, while C votes in favour. Voters A and B abstain (*) as their final backup option.

  ai ∈ D(i) then add agents with direct vote to P 4: P := P ∪ {a} 5: else if F lev ai (Y S lev ai ) ∈ D(i) then 6: P := P ∪ {a} 7: if P = ∅ then there are agents with direct votes 8: select b from P uniformly at random 9: x b := B lev bi 10: else if P = ∅ then there are computable votes 11: select b from P uniformly at random 12:

Figure 2 :

 2 Figure 2: A network representation of Bi from Example 2. Solid lines represent first preferences and dashed lines second preferences.The final preference for a direct vote is next to the agent's name.

  r(U(B)) ≥ a r(U(B -b , ( * ))) for any b ∈ I # * (B, a), and B -b is B without b's ballot. We now show that all four unravelling procedures we propose do not satisfy this property for a specific rule r: Theorem 3. RMaj and UNRAVEL(#) do not satisfy guruparticipation for # ∈ {U, DU, RU, DRU} for LIQUID. Proof. Consider a smart profile B with B a = (1), B b = (({c}, id)>({a}, id)> * ), B c = (({d}, id)>({f }, id)> * ), B d = (({b}, id) > ({f }, id) > * ), B e = (1) and B f = (0) and profile B = (B -b , ( * )) obtained from B by switching b's vote to B b = ( * ).

  then

	4:	P := P ∪ {a}
	5: if P = ∅ then	there are direct/computable votes
	6:	select b from P uniformly at random
	7:	if B lev bi ∈ D(i) then
	8:

Recent work by[START_REF] Dhillon | [END_REF] conducts a detailed analysis of smart contracts for electronic voting and liquid democracy. See also the reports of[START_REF] Kotsialou | Using distributed ledger technology for shareholder rights management[END_REF] and[START_REF] Riley | Deploying a shareholder rights management system onto a distributed ledger[END_REF].

We note in passing that ranked delegations for collective decisions were also experimented by Google[Hardt and Lopes, 2015].

This can be expressed by propositional formula B ∧ (C ∨ D).

In what follows, we simply write UNRAVEL(#) to indicate the UNRAVEL algorithm using UPDATE procedure #.

In Example 2, in case xB = 0 then necessarily B ∧ C will be false, and thus xA = 0 (even if xC = ∆).

Recall that since D(i) and the possible sets of delegates are finite, and since all functions given in an agent's valid ballot must differ, the possible number of functions must also be finite.

Since SAT-CNF is NP-hard, by the duality principle DNF-FALSIFIABLE is also NP-hard; for membership in NP it suffices to verify a falsifying truth assignment in polynomial time.

Acknowledgments

The authors acknowledge the support of the ANR JCJC project SCONE (ANR 18-CE23-0009-01). This paper developed from ideas discussed at the Dagstuhl Seminar 19381 (Application-Oriented Computational Social Choice), 2019.


Olivier Lai

Mark Chun

Fatima Abdurrahman

Jessica Lu

Max Service

Dora Fohring

Doug Toomey

Deconstructing Turbulence and optimizing GLAO using imaka telemetry

Keywords: optical turbulence, ground layer adaptive optics, dome seeing, tomography, turbulence profiling

By analyzing global covariance matrices from the imaka GLAO system at the UH 2.2m telescope, it is possible to reconstruct ground layer strength, the integrated turbulence strength as well as the vertical turbulence profile. These are compared to simultaneous profiles obtained by the Maunakea facility MASS/DIMM. A method has been developed to directly compute the phase structure function from the covariances of the slopes, obtained from the telemetry data. The phase structure function allows to test the validity of the Kolmogorov (or van Karman) model and the spatial frequency content of the turbulence: Dome and telescope tube seeing are expected to have an excess of high spatial frequencies, which is detrimental to the PSF by amplifying the halo, and which the AO system cannot correct.

The telescope, the dome and their interaction with the ground layer produce a complex environment for the turbulence. We are therefore developing a small, portable optical turbulence sensor which we will be able to use to scan the dome and telescope tube to quantify the local presence of turbulence. This is the AIR-FLOW (Airborne Interferometric Recombiner -Fluctuations of Light at Optical Wavelengths) project. With imaka and AIR-FLOW we hope to generate a coherent and quantitative account of the turbulence type and strength present in the telescope beam and to accurately match this detailed phase information to the focal plane images. Such a level of detail is required to understand and eventually be able to control the local environment for optimized image quality. We foresee this expertise will be especially valuable for ELTs, where the halo around the PSF will act like an extra source of background.

INTRODUCTION

Imaka is a ground layer adaptive optics (GLAO) prototype/demonstrator installed at the University of Hawaii 88" telescope on Maunakea [START_REF] Lai | IMAKA: imaging from Mauna KeA with an atmosphere corrected 1 square degree optical imager[END_REF][START_REF] Chun | imaka: a ground layer adaptive optics system on Mauna Kea[END_REF]. The goal of this project is to analyze and optimize GLAO performance over large fields; indeed, the patrol field of the wavefront sensors is on the order of 0.4˚ (24' x 18') and the science field of view is on the order of 12'. Up to 5 Shack Hartman wavefront sensors can be positioned on guide stars; these have 8 x 8 subapertures of 12x12 pixels measuring 0.4" providing a relatively large 5" field, necessary for open loop and GLAO operation. The correction is provided by a 36-electrode bimorph mirror manufactured by CILAS, on loan from Subaru Telescope (it was the DM used in their first-generation facility AO system). Imaka was installed of the UH88" telescope in October 2016 and had its GLAO first light in November 2016. Observing runs took place in January, February and May 2017 (as well as March 2018 but data is not included in present analysis). A detailed description of the instrument can be found in [START_REF] Chun | [END_REF] and of its performance in [START_REF] Abdurrahman | Improved Image Quality over 10' fields with the `Imaka ground layer adaptive optics experiment[END_REF]. Here, we focus on the very useful tool of having 5 simultaneous wavefront sensors pointing in different directions to analyze the turbulence through its properties and its profile. This information can be also used to generate tomographic filters, such as a learn-and-apply method adapted from MOAO to GLAO applications. The measurements used were obtained in open loop, although the methods developed herein will be adapted to closed loop operation (by reconstructing pseudo-open loop measurements from the commands to the deformable mirror), where the sensitivity to altitude turbulence may be improved, but the detailed structure of the turbulence near the ground may be harder to extract as the ground conjugate but tilted DM will have a variable height of correction as a function of position in the pupil.

The analysis of the turbulence profile follows a method somewhat similar to that developed in [START_REF] Martin | William Herschel Telescope site characterization using the MOAO pathfinder CANARY on-sky data[END_REF] and used on the CANARY MOAO instrument on the William Herschell Telescope. Telemetry streams are recorded, containing all relevant real time AO variables of interest. These are usually of a length between 1024 and 2048 samples (sometimes multiple telemetry buffers were recorded sequentially, allowing to concatenate the circular buffers); as the sampling frequency is on the order of 180Hz, the buffers sample between 5.5 and 11 seconds of turbulence which may not be sufficient to properly sample the turbulence statistics. Nonetheless, we extract the centroids and compute the slopes covariance matrices: Cslopes = <m.m T >. We call the covariances of each wavefront sensor with itself the auto-covariance and the covariances of the wavefront sensors with each other the cross-covariances. The former contain the integrated the turbulence and the latter contain information on the ground layer and up to the altitude where the meta-pupil starts to become discontinuous (in practice, the highest levels are only poorly sampled as fewer subapertures are available for their measurement.

SLOPE COVARIANCE MATRIX MODEL

The analysis depends on being able to interpret the covariance matrices. To do so, we need a model against which to compare our data. Consider two subapertures of size d and a distance r apart. By virtue of Green's Theorem, we can write the slope vector s as:

(1)

The contour integral ∮ ϕx dy is the sum (i.e. normalized to the subaperture size, the average value) of the phase along the left edge of the subaperture ϕ<y>(x) minus the sum of the phase along the right edge, ϕ<y>(x + d). By virtue of the mean theorem, of the phase along the left edge can be approximated as the value of the phase halfway along the edge, point A for subaperture 1, point C for subaperture 2; similarly, the average value of the phase on the right side of the subaperture is approximated as the phase halfway along the subaperture, point B for subaperture 1, point D for subaperture 2, so we can write ∮ϕx dy ~ ϕy=A(x) -ϕy=B(x + d). To alleviate the notation, we write the x-slope of subaperture 1 as sx1 = ϕ(B) -ϕ(A) and the x-slope of subaperture 2 as sx2 = ϕ(D) -ϕ(C). We can then write the covariance matrix of the x-slopes as:

(2)

Recall that the phase structure function Dϕ is defined as: Similarly, we can compute the y-slope covariances <sy1 sy2> and the x-y covariances, although these contain less information at small separation. For the phase structure function, we can use either the Kolmogorov or the von Karman models, both of which have relatively straightforward analytical expressions. We can thus generate covariance matrices for layers at any altitude, simply by maintaining the proper geometrical relationship of the subapertures within each beam, through the distance r at the given altitude.

Direct inversion

It is possible to construct a large altitude-covariance matrix, where each column is the covariance matrix for a layer at a single altitude, unfolded into a vector. Such a matrix A would be of size [Nheight, (2 x Nsubaper x Nwfs) 2 ] for which a generalized inverse of the form A † = (A T .A) -1 A T can be found. In theory, it ought to be possible to multiply a measured covariance matrix-vector by this generalized inverse and obtain a vector containing the strength of each layer at each altitude of the model. Unfortunately, this method is limited both because the noise in the measurements propagates in the reconstruction, but also because the outer scale L0 varies with altitude. Specifically, it can lead to negative values of the turbulence strength when the off-diagonal response for an altitude layer is too narrow due to a small outer scale. One possible solution is to filter the tip-tilt from the measurements and compute a model covariance matrix with a van Karman spectrum and a small outer-scale, on the order of the telescope diameter, although this still does not prevent the turbulence strength to be negative at times. A disadvantage of filtering the tip-tilt is that information on the outer scale is essentially lost, although in the presence of vibrations, it usually required to filter it to reconstruct the turbulence profile. An advantage of this method is that once the model covariance matrices at altitude are calculated, extracting the profile from the measurements requires a simple matrix multiplication.

Covariance map fitting

The covariance matrices contain a lot of redundant information and the signal can be increased over the noise by averaging all the matrix elements that represent the same subaperture separation on the pupil. This is simply a reordering and averaging of the matrices but allows to reduce the size of the maps from (2 x Nsubaper x Nwfs) 2 to (2 x Nxsub x Nwfs) 2 , with Nsubaper = Nxsub 2 .

We first extract integrated properties of the turbulence, by using only the auto-covariance maps. We average the autocovariance maps of all the wavefront sensors under the assumption that the free atmosphere turbulence is independent of the direction of the guide star. We use a simplex algorithm to find the phase structure function that produces the best fit to the measured covariance maps, as given by equation 4. To simplify and constrain the phase structure function, we parametrize using the von Karman model, which has been shown to be representative of many different types of turbulence, indoors or outdoors [START_REF] Ziad | Lotuce: a new monitor for turbulence characterization inside telescope's dome[END_REF][START_REF] Chabé | The INdoor TurbulENce SEnsor (INTENSE) instrument[END_REF]. We use the formula given by Kellerer [START_REF] Kellerer | A Cookbook of Structure Functions[END_REF]: [START_REF] Martin | William Herschel Telescope site characterization using the MOAO pathfinder CANARY on-sky data[END_REF] with k=6.88. We then average the cross-covariances and the central peak of the covariance map will be due to the ground layer only. We use the same simplex algorithm to obtain the r0 and L0 of the ground turbulence. Once we have found the best fit to the ground layer covariance peak, we subtract it from the integrated covariance peak and estimate the free atmosphere turbulence strength and outer scale. Please verify that (1) all pages are present, (2) all figures are correct, (3) all fonts and special characters are correct, and (4) all text and figures fit within the red margin lines shown on this review document. Complete formatting information is available at http://SPIE.org/manuscripts Return to the Manage Active Submissions page at http://spie.org/submissions/tasks.aspx and approve or disapprove this submission. Your manuscript will not be published without this approval. Please contact author_help@spie.org with any questions or concerns. Single layers of turbulence at altitude will produce a decentered covariance peak. Using cross-covariance maps from which we have subtracted the ground layer and free atmosphere components, we try to estimate the turbulence profile by fitting our decentered altitude-dependent model covariance maps to these residuals. We use a priori information of the direction in which the secondary peaks are located for each pair of guide star, to increase the sensitivity, but the signal is usually quite tenuous, and it is therefore challenging to extract the outer scale at altitude. Increasing the number of samples in our circular buffers and obtaining very clean covariance maps could alleviate this issue. Note however, that since most of the data from the UH88" telescope is tainted by vibrations the accuracy of the methods only work reliably when tip-tilt is filtered, but L0 is consequently severely underestimated.

It should be possible to remove the vibrations and jitter of the circular buffers from their temporal properties; unfortunately, the temporal power spectrum of tip-tilt shows only a broad peak which is difficult to filter. Also, tip-tilt translates into a constant on the covariance maps, so subtracting a constant should correct this bias, although it is unclear how to estimate the contribution of the turbulence versus the vibrations, and this depends on both r0 and L0. If this could be done to any level of accuracy, then it would also be easy to simply estimate the strength of the turbulence from the modal variance spectrum, which it is not, unless using higher orders, where the effects of the outer scale become negligible.

Running a simplex optimization of r0 and L0 for each altitude is CPU intensive and probably not ideal to implement as a real time tool, although probably provides the best estimates of the turbulence profile (see e.g. Figure 5). Guesalaga et al. [START_REF] Guesalaga | Online estimation of the wavefront outer scale profile from adaptive optics telemetry[END_REF] have implemented a method where they compute covariance matrices at each altitude for various r0 and L0 and apply a sort of CLEAN peak finding algorithm. We have not implemented such a method but instead, for real time pruposes, we use predetermined outer scales for different altitudes. This method is obviously much faster but will generally overestimate the amount of turbulence near the ground.

It will be important to obtain good profiles, for example to examine the PSF variability as a function of the thickness of the ground layer. Also, in its current implementation, the learn and apply tomographic filter does require a profile to be optimized, as we use a simulated atmosphere to generate the tomographic filter.

Figure 4: Turbulence profile obtained from Simple fitting of the covariance maps with model covariance maps. We show the results for a Kolmogorov Spectrum on the top row, without (left) and with (right) filtering the tip tilt. The lower row shows the fit of a von Karman phase structure function for L0=20m (left) and 2m (right).

In the line plots, the full line is the integrated turbulence, the dashed line is the ground layer and the dotted line is the free atmosphere.

TURBULENCE PROFILING

In this section we present some of the turbulence profiles obtained with imaka during the February (for profiles) and May (for spatial properties of the turbulence) observing runs. No statistical study of the profiles has been performed and the data set is not very homogeneous (the three observing runs had very different atmospheric conditions, as well as different guide star constellations, and wavefront sensor orientations). The long-term goal is to have an automated tool that can reconstruct the profiles and populate an archive for statistical analysis and correlation with image plane data.

For comparison purposes, we include the measurements from MASS/DIMM obtained for the night of February 16 th for which we show the profile analysis. That nigh had strong ground layer turbulence and a free atmosphere seeing between 0.1 and 0.4".

Please verify that (1) all pages are present, (2) all figures are correct, (3) all fonts and special characters are correct, and (4) all text and figures fit within the red margin lines shown on this review document. Complete formatting information is available at http://SPIE.org/manuscripts Return to the Manage Active Submissions page at http://spie.org/submissions/tasks.aspx and approve or disapprove this submission. Your manuscript will not be published without this approval. Please contact author_help@spie.org with any questions or concerns.

10703 -229 V. 10 (p.5 of 14) / Color: No / Format: Letter / Date: 6/4/2018 11:21:14 AM SPIE USE: ____ DB Check, ____ Prod Check, Notes:

Comparison of methods for night of UT20170216

First, we show the profile obtained by direct inversion of the covariance matrix in Figure 3. We have a choice for the model to use and whether to filter the tip tilt or not. Note that filtering tip-tilt means that it is filtered from the covariance matrices in the fitting process, but not from results, so the estimated seeing contains the full turbulence. We find that a hybrid model with a von Karman phase structure function with L0=4m for altitudes below 700m and a Kolmogorov phase structure function above seems to minimize the artefacts, and the filtering of the tip tilt does not alter the results substantially, so this is encouraging. However, the layer at altitude 800m as well as the lack of free atmosphere turbulence (the highest layer represents the free atmosphere and is arbitrarily set to an altitude 3 times higher than the highest reconstructed layer). Next in Figure 4, we show the results of our model fitting algorithm (where we set the outer scale to a set value for the model). The main features of Figure 3 are still apparent but the profile is much cleaner, with less noise. Filtering tip-tilt increases the sensitivity to mid-altitude layers, because the off-centered peak become sharper and easier to fit. Reducing the outer scale also seems to increase the sensitivity to mid-altitude layers, for similar reasons. In the same figure we show a plot of seeing (integrated, full line; ground layer, dashed line and free atmosphere, dotted line) because these are each estimated independently of the actual profile. Estimates of these parameters are rather insensitive to which model is being used.

Please verify that (1) all pages are present, (2) all figures are correct, (3) all fonts and special characters are correct, and (4) all text and figures fit within the red margin lines shown on this review document. Complete formatting information is available at http://SPIE.org/manuscripts Return to the Manage Active Submissions page at http://spie.org/submissions/tasks.aspx and approve or disapprove this submission. Your manuscript will not be published without this approval. Please contact author_help@spie.org with any questions or concerns. Finally, we ran the Simplex fitting on the von Karman Model where both r0 and L0 were free parameters shown in Figure 5. Tip-tilt filtering is very time consuming because the covariance maps have to be converted into covariance matrices, for which we can build a tip-tilt filtering matrix. We then have to convert the covariance matrices back into a covariance maps, which prevents this method from being useful in real time. However, for a posteriori analysis, it is the most accurate and most useful as it provides not only the profile of r0 but also that of L0 (Figure 6), and we can start looking for systematic effects that one might expect, such as a smaller outer scale at low altitude.

-229

Seeing is formally defined as the FWHM at 500nm for a Kolmogorov PSF with given r0. However, a finite outer scale modifies (reduces) the FWHM obtained at the focus of the telescope. Since we have access to L0, we can correct for the effect of outer scale on seeing to predict the Image Quality (IQ), to compare directly to the FWHM of focal plane images. [START_REF] Ziad | Lotuce: a new monitor for turbulence characterization inside telescope's dome[END_REF] This correction factor was established by Martinez et al. [START_REF] Martinez | Atmospheric blur with finite outer scale or partial adaptive optics correction[END_REF] and is valid for L0/r0 > 20. However, we show in Figure 6 the actual r0 and L0 obtained as a function of time for both the covariance maps including tip-tilt and those with tip-tilt filtered. A few comments are needed to explain those profiles. The r0 profiles are shown clipped to below 1m; indeed, for r0 much larger than that, the signal of such a weak layer is effectively lost in the noise. Also, when r0 is large, the value of L0 is not very meaningful, since there is no peak in the covariance map to fit. The r0 profiles are qualitatively comparable to the seeing profiles obtained by direct inversion or fixed-model fitting, though we note that the resolution on the ground layer is improved when filtering tip-tilt (as would be expected) but also that the free atmosphere is better estimated when tip-tilt is filtered. The L0 profiles are interesting but rather speculative, as the SNR on the covariance maps obtained with 2048 samples is marginal to fit secondary off-axis peaks. When tip-tilt is included, there are times when the noise is too strong, and the fit is poor for the entire profile (e.g. at UT 6.5, 8.6 and 8.9). However, when filtering tip-tilt the values of L0 are consistently smaller than 20m. It is surprising that the L0 estimates show no correlation to the r0 profiles, as one would expect the noise on L0 to be larger when r0 is large.

The L0 profile is difficult to interpret. However, one thing appears clearly in the bottom left panel of Figure 6: The outer scale of the ground layer is large, quite opposite to what one might have expected. However, tip-tilt adds a constant pedestal to covariance maps, and the apparent large outer scale may be an artefact of the Simplex algorithm trying to fit this pedestal due to vibrations with a von Karman Structure Function, and the one that extends out furthest (effectively acting as a constant in the wings of the covariance maps) is for L0 ↝∞. Please verify that (1) all pages are present, (2) all figures are correct, (3) all fonts and special characters are correct, and (4) all text and figures fit within the red margin lines shown on this review document. Complete formatting information is available at http://SPIE.org/manuscripts Return to the Manage Active Submissions page at http://spie.org/submissions/tasks.aspx and approve or disapprove this submission. Your manuscript will not be published without this approval. Please contact author_help@spie.org with any questions or concerns.

10703

SPATIAL PROPERTIES OF THE TURBULENCE

To further characterize the turbulence, we want to infer its spatial properties, and this is best represented by the phase structure function. A von Karman phase structure function is able to represent most cases of turbulence by varying the outer scale, from ∞ for fully developed, Kolmogorov turbulence to L0~D for random walk, diffusive turbulence. However, since we have a model that allows to get the covariance from the phase structure function, we wanted to see if we could obtain the phase structure function empirically from the covariance maps, in other words, can we solve for Dϕ(r) in terms of <sx1 sx2> from equation 4? For r=0, we can write:

From which we deduce the following discrete sum:

We can then infer the phase structure function without having to parametrize it. This method however tends to amplify noise at long separations as it effectively performs an integration by linking up the variances of points B, C to get from A to D on Figure 1. Also, whereas we try to reconstruct the entire covariance map using our phase structure function-based model, this method only uses a one-dimensional cut through the covariance map to reconstruct the radial phase structure function, it is not trivial to generalize in two dimensions.

W reconstructed the phase structure function using the covariance matrix for the entire night of 2017/02/16, but instead of separating the ground layer and the free atmosphere from the cross-covariances and the difference between the autocovariance and the cross-covariance respectively, we tried to use a cleaner method whereby we obtained the integrated seeing from the auto-covariances as previously, but for the free atmosphere we subtracted the pairwise measurements of WFSn to those of WFSn+1: both contain the contribution of the ground layer which should subtract out perfectly, leaving a circular buffer with twice the variance of the free atmosphere. For the ground layer, we concatenated the various wavefront sensors into a single circular buffer and computed the covariance by matching different wavefront sensors:

Using such covariances, we reconstructed the phase structure function non parametrically from equation 8 and tried fitting it with either a variable exponent power law (of the form (r/r0) 𝛼 , with variable r0 and 𝛼) or with a von Karman spectrum with a finite outer scale. It was not possible to discriminate between these two models, especially given the coarse sampling of the phase structure function (equal to the number of subapertures, 8 in the case of imaka, and limited baseline imposed by the telescope diameter). In the following we report only on open loop von Karman fit values to alleviate the discussion.

In the case of a von Karman fit, it is also possible to fit covariance maps on the profile using our simplex algorithm. We can filter the tip-tilt from the data and from the model covariance maps and we can obtain estimates of r0 and L0 only from higher orders. We expect L0 to be smaller than in the case of the data with vibrations present in the tip-tilt signal. In theory it should be possible to compute the covariance map for a power law with tip-tilt subtracted but we did not pursue this, especially as GLAO PSFs seem to be very well fitted by a von Karman phase structure function with a small outer scale. In Table 1 and Figure 7 we compare the estimates of r0 and L0 obtained by fitting the tip-tilt-filtered covariance maps with a tip-tilt-filtered von Karman phase structure function to the r0 and L0 computed from fitting the one-dimensional empirical structure function obtained with equation 8. The presence of vibrations makes the interpretation of these curves difficult as it prevents a direct comparison of the tiptilt filtering as well as between x and y. This tool may become useful for systems with a greater number of subapertures, as it will improve the resolution of the reconstructed phase structure function. However, the noise reconstruction of the phase structure function will also increase due to the integration of noisy covariance maps. The phase structure function of tip tilt is a parabola (this is easy to see from first principles since D𝜙 2 (r) = <| 𝜙(𝜌)-𝜙(𝜌+r)| 2 >, but 𝜙(𝜌+r) = 𝜙(𝜌) + bx (with b=constant) for pure tip along x-axis, so D𝜙 2 (r) = <|bx| 2 > = b 2 x 2 and the same for tilt with y).

Unfortunately, it is difficult to separate which part of the tip-tilt comes from vibrations and which is part of the atmosphere. To try to circumvent that, we can also attempt to compute and fit the empirical phase structure function from covariance maps from which we have removed tip-tilt and compare it to fitting the tip-tilt filtered covariance map with a theoretical von Karman covariance map model from which we have not filtered tip tilt. This will certainly introduce a bias in the estimation of the outer scale, but we can at least check for agreement in r0 and between x and y. These results are presented in Figure 8 and Table 2.

Please verify that (1) all pages are present, (2) all figures are correct, (3) all fonts and special characters are correct, and ( 4) all text and figures fit within the red margin lines shown on this review document. Complete formatting information is available at http://SPIE.org/manuscripts

Return to the Manage Active Submissions page at http://spie.org/submissions/tasks.aspx and approve or disapprove this submission. Your manuscript will not be published without this approval. Please contact author_help@spie.org with any questions or concerns.

10703 -229 V. 8, and the dotted lines are von Karman fits with values reported in Table 2. The dashed lines are von Karman fits on the covariance maps directly, without reconstructing the phase structure functions. Left: free atmosphere, middle: ground layer and right, sum of left and middle panels. On the right panel, green and blue are integrated tip and tilt (respectively) from auto-covariances. The agreement between x and y is much better, indicating the impact of the jitter on the estimation of the phase structure functions.

This work will be greatly improved if we can reduce the telescope vibrations at the source, especially as the jitter is not restricted to a narrow frequency but is spread over a rather band and may even have a low frequency component that is most likely not well sampled given the length of our circular buffers. This jitter also affects the image plane analysis presented in the next section, which, if it were corrected at the source, would allow us to match the telemetry data with the delivered images at the focal plane.

Unfortunately, in the case of GLAO (or seeing limited), the MTF does not extend out to the cut-off frequency of the telescope, and the large separations on the phase structure function are dominated by numerical errors by taking the logarithm of an exceedingly small number. However, the small separations on the pupil are adequately estimated, as shown in Figure 9.

Please verify that (1) all pages are present, (2) all figures are correct, (3) all fonts and special characters are correct, and (4) all text and figures fit within the red margin lines shown on this review document. Complete formatting information is available at http://SPIE.org/manuscripts Return to the Manage Active Submissions page at http://spie.org/submissions/tasks.aspx and approve or disapprove this submission. Your manuscript will not be published without this approval. Please contact author_help@spie.org with any questions or concerns. It is more robust to try to fit the phase structure function in image plane using the Fourier Transform of equation 9. We then have to revert to a parametric phase structure function. In Figure 10, we show the r0 and L0 estimated for the run of May 2017 from image plane data (note that these images are elongated due to jitter and the analysis is only carried out on the narrow axis of the PSF). The range of r0 remains more or less unchanged between open and closed loop, but the outer scale is systematically reduced when the loop is closed (Figure 10, right). This suggests that the GLAO PSF may be well parametrized with a von Karman phase structure function with a small outer scale. Please verify that (1) all pages are present, (2) all figures are correct, (3) all fonts and special characters are correct, and (4) all text and figures fit within the red margin lines shown on this review document. Complete formatting information is available at http://SPIE.org/manuscripts Return to the Manage Active Submissions page at http://spie.org/submissions/tasks.aspx and approve or disapprove this submission. Your manuscript will not be published without this approval. Please contact author_help@spie.org with any questions or concerns. Since the fit in the image plane is more robust, we can also try to fit the PSF with a von Karman phase structure function to which we add a parabolic component in one dimension, representative of the broadening of the PSF due to vibrations. We let the amplitude and the angle of the parabola vary as free parameters of the fit and obtain the results shown inFigure 11. A major difference with the results obtained using the narrow axis of the PSF is that the r0 is smaller on average, for both open and closed loop images. The open loop L0 is also smaller, which makes the effect of the GLAO correction as a reduction of the outer scale less visible but compared toFigure 11, it is the estimated closed loop outer scale that remains relatively unchanged, while the open loop outer scale show more variation (indicating that some of the residual tip-tilt from the narrow axis PSF contributes to overestimating L0.

TAMING TURBULENCE

The reason why it is important to determine the turbulence profile and the spatial properties of the turbulence is to understand the physical properties of the turbulence, to determine whether the GLAO correction will be useful given the conditions but also to be able to produce optimal tomographic filters and understand which ones will perform better. We currently only consider implementing on two types of tomographic filters (described below), but the goal is to use the imaka prototype as a testbench for different algorithms.

Tomographic filters

We are developing two approaches to improve GLAO correction by attempting to reject the free atmosphere from the measurements. To do better than simple averaging, we need to include some a priori information, which helps to identify (and reject) turbulence not associated with the ground layer. Turbulence profiles and temporal filtering are such examples.

The learn and apply method, developed by Vidal etal, [START_REF] Martinez | Atmospheric blur with finite outer scale or partial adaptive optics correction[END_REF] is conceptually very simple: What is the matrix M which will produce the optimal measurements in the center (or any other part) of the field, given a set of measurements on the periphery (or anywhere else): mfield =MLA mWFS. We can multiply both side by mWFS T and take a time average to find: MLA = < mfield • mWFS > < mWFS • mWFS > -1 . The latter term is the inverse of the covariance matrix, which we have access to (though not always well conditioned), but the former term is harder to obtain. For MOAO applications, a truth sensor can be used at the location of the science target, but in GLAO, it is the average of the field, therefore only the measurements from the ground that we are interested in. We can try to average the measurements of the different WFS to obtain an estimate of the ground layer measurements, but these will still include the partially averaged FA from each direction. We propose to estimate mfield by open loop simulations, for which we need to know the thickness (and profile) of the ground layer. Knowing the outer scale is also useful. We draw many realizations of the phase screens maintaining the proper geometrical relationships between guide stars and layer height and can compute learn and apply tomographic filters in this way. We have tried this algorithm on the sky during the May 2017 run, but the results are not conclusive, as too much time had elapsed between obtaining measurements and producing the tomographic matrix.

Another promising method to improve GLAO correction is to use the spatio-temporal covariance maps to identify layers traveling at different speeds and generate a filtering matrix from these covariance maps. Such a filter should allow to isolate layers and their relative speed and only combine measurements from the current and N previous frames that contribute to the signal of these selected layers. We can observe these peaks in spatio-temporal covariance maps and work is ongoing to isolate them automatically and transform them into an optimal filter.

AIR-FLOW

GLAO performance will be strongly dependent on controlling the wings of the PSF to reduce the NEA as much as possible. The telescope, the dome and their interaction with the ground layer produce a complex environment for the turbulence and it is difficult to interpret data which can intermittently be very different from simple models. The wings of the PSF occur when there is an excess of high spatial frequencies with respect to low ones. This can occur if the outer scale of the turbulence is small, if the turbulence is not fully developed or in the case of diffusive turbulence. All these phenomena occur in the vicinity of or inside the dome, and this is a part of the environment we can control. To better understand the self-generated turbulence, we have developed a portable turbulence sensor, named AIR-FLOW [START_REF] Vidal | Tomography reconstruction using the learn and apply algorithm[END_REF]. Such a sensor will also be useful to control the dome vents of telescopes such as CFHT and Gemini, as well as to optimize the airflow in the domes of ELTs.

Airborne Interferometric Recombiner -Fluctuations of Light at Optical Wavelength is a turbulence sensor based on a nonredundant mask. Because the baselines are small, the induced turbulence phase perturbations are small. The variance of the phase of each frequency of the Fourier transform of the complex fringe pattern in the focal plane provides an estimate of the variance of the phase (within the linear range) at different separations and allows to measure the phase structure function directly. First tests using a small heat source show promising results (Figure 12). The instrument will be ruggedized and tested simultaneously with INTENSE/LOTUCE [START_REF] Ziad | Lotuce: a new monitor for turbulence characterization inside telescope's dome[END_REF][START_REF] Chabé | The INdoor TurbulENce SEnsor (INTENSE) instrument[END_REF] at Plateau de Calern before attempting to measure turbulence at the UH88" concurrently with imaka. Please verify that (1) all pages are present, (2) all figures are correct, (3) all fonts and special characters are correct, and (4) all text and figures fit within the red margin lines shown on this review document. Complete formatting information is available at http://SPIE.org/manuscripts Return to the Manage Active Submissions page at http://spie.org/submissions/tasks.aspx and approve or disapprove this submission. Your manuscript will not be published without this approval. Please contact author_help@spie.org with any questions or concerns.

CONCLUSION

We have presented ongoing work to use wavefront sensor telemetry from imaka to try to reconstruct the optical turbulence seen during our observations, both in its vertical profile as well as its spatial properties. We have presented three different methods to reconstruct the profile using an analytical model of the phase structure function (direct inversion, Simplex with fixed model, Simplex with variable r0 and L0). We have also presented the state of affairs of the estimation of the phase structure function both empirically and with a von Karman parametrization. Work is ongoing to separate the contribution of jitter using Moffat parametrization. We have also tried to estimate the phase structure function from image plane data and found that we cannot access it directly. We can however use a simplex fit to estimate r0 and L0 from the difference between the data and a theoretical PSF computed using a von Karman phase structure function. Because of the presence of vibrations, we can either use the narrow axis of the PSF or try to add a parabolic component to the phase structure function (the amplitude and angle of which are free parameters in the fit). The results of these algorithms are in the process of being integrated to a tomographic filter for GLAO. Finally, we report on the first measurements obtained with our AIRFLOW prototype, the goal of which is to chase down the turbulence inside the telescope dome and tube, and especially attempt to determine its physical properties.

With imaka and AIR-FLOW we hope to generate a coherent and quantitative account of the turbulence type and strength present in the telescope beam and to accurately match this detailed phase information to the focal plane images. Such a level of detail is required to understand and eventually be able to control the local environment for optimized image quality. We foresee this expertise will be especially valuable for ELTs, where the halo around the PSF will act like an extra source of background.

( 3 )

 3 By writing < ϕ(B) ϕ(D)> as 1/2 Dϕ(BD) -𝜎𝜙 2 , we can replace the covariances of equation 2 by the phase structure functions and all the variances cancel out:[START_REF] Abdurrahman | Improved Image Quality over 10' fields with the `Imaka ground layer adaptive optics experiment[END_REF]

Figure 1 :

 1 Figure 1: Two subapertures of side d and a distance r apart.

Figure 2 :

 2 Figure 2: MKAM Mass/DIMM measurement of the turbulence on the night of UT February 16 th 2017. The yellow box shows the time span during which we observed. The blue dots show the free atmosphere seeing, below 0.2" on average but with spikes up to 0.4". The red dots show the ground layer seeing, with two large spikes shortly after 06:00UT (20:00HST) and around 8:00UT (22:00HST).

  10703 -229 V. 10 (p.3 of 14) / Color: No / Format: Letter / Date: 6/4/2018 11:21:14 AM SPIE USE: ____ DB Check, ____ Prod Check, Notes:

Figure 3 :

 3 Figure 3: Turbulence profiles for the night of UT20170216, obtained from direct covariance matrix inversion. On the top row from left to right, Kolmogorov, von Karman with L0=20m and L0=4m. The middle row shows the same turbulence models but with tip-tilt filtered. Both have systematic residual seen as horizontal and vertical persistent lines where the method simply fails. The bottom two panels show a hybrid model with a von Karman phase structure function with L0=4m for altitudes below 700m and a Kolmogorov phase structure function above.

Figure 5 :

 5 Figure 5: Turbulence profiles obtained by fitting the covariance maps to a von Karman Phase Structure function by Simplex, with r0 and L0 as free parameters at each altitude (top row, with tip-tilt, bottom row, tip-tilt filtered from covariance maps). On the right, we show the actual IQ, which differs from seeing.

Figure 6 :

 6 Figure 6: r0 (top) and L0 (bottom) profiles with tip tilt (left) and filtered (right). The color scale for r0 is clipped from 0 (black) to 1m (white) even though some values of r0 are estimated up to 20m. The color scale for L0 goes from 0 to 1000m (left) and from 2 to 10m (right).

  -229 V. 10 (p.7 of 14) / Color: No / Format: Letter / Date: 6/4/2018 11:21:14 AM SPIE USE: ____ DB Check, ____ Prod Check, Notes:

( 6 )

 6 as Dϕ(d) = Dϕ(-d) and Dϕ(0)=0. Similarly, for r=d, For r=2d, Etc…

Figure 7 :

 7 Figure 7: Phase structure functions. In all cases, full line is the phase structure function reconstructed from Equation8, dotted is the associated von Karman fit while dashed line is the tip-tilt filtered von Karman model fitted to the tip-tilt filtered covariance maps. The red and black curves show x and y for the free atmosphere (left), the ground layer (middle) and the integrated seeing (right); on this last panel green and blue are the integrated seeing (auto-covariances) and black and red are the sum of the left and middle panels. The fact that the red and blue curves, as well as the green and black curves almost overlap means that the integrated seeing matches well the sum of the ground layer and free atmosphere.

Figure 8 :

 8 Figure8: Tip-tilt filtered phase structure functions. As in Figure8, black is tip (x) and red is tilt (y). Thin full lines are the empirical reconstructed phase structure functions from Equation8, and the dotted lines are von Karman fits with values reported in Table2. The dashed lines are von Karman fits on the covariance maps directly, without reconstructing the phase structure functions. Left: free atmosphere, middle: ground layer and right, sum of left and middle panels. On the right panel, green and blue are integrated tip and tilt (respectively) from auto-covariances. The agreement between x and y is much better, indicating the impact of the jitter on the estimation of the phase structure functions.

1

 1 Phase structure function from image plane data To compare the wavefront sensor reconstructed phase structure function, we can try to obtain the phase structure function from focal plane image data. If we call the Optical Transfer Function (OTF) the autocorrelation of the pupil function and the Modulation Transfer Function (MTF) the Fourier transform of the PSF, then the following relations hold:

  10703 -229 V. 10 (p.10 of 14) / Color: No / Format: Letter / Date: 6/4/2018 11:21:14 AM SPIE USE: ____ DB Check, ____ Prod Check, Notes:

Figure 9 :

 9 Figure 9: (left) Phase structure function obtained from image plane data on the night of My 18th 2017. Decreasing SNR from cyan to yellow, we can see the saturation of the phase structure function due to numerical errors of the logarithm of small numbers. The small separation regime is well fit by a Kolmogorov phase structure function with r0 of 0.25m.

Figure 10 :

 10 Figure 10: (Left) r0 and L0 obtained from fitting the narrow axis of image plane data for the entire May 2017 run; different colors indicate different nights. Stars are open loop and triangles are closed loop. (Right) r0 and L0 versus time from image data during the May 2017 run (same color coding). The open (star) and closed (triangle) loop r0 (bottom panel) are almost identical, but the outer scale (top panel: log scale showing some outliers, middle panel: linear scale) is systematically smaller when GLAO correction is turned on.

  10703 -229 V. 10 (p.11 of 14) / Color: No / Format: Letter / Date: 6/4/2018 11:21:14 AM SPIE USE: ____ DB Check, ____ Prod Check, Notes:

Figure 11 ,

 11 Figure 11, left: r0 vs L0 and right: r0 (bottom) and L0 (middle and top) vs. time allowing for PSF broadening in one axis in the phase structure function by including a parabolic component, the amplitude and angle of which are free parameters of the fit.

  10703 -229 V. 10 (p.12 of 14) / Color: No / Format: Letter / Date: 6/4/2018 11:21:14 AM SPIE USE: ____ DB Check, ____ Prod Check, Notes:

Figure 12 :

 12 Figure 12: First results of the AIRFLOW prototype. A point source is reimaged through a non-redundant mask (lower right inset) and produces the fringe pattern shown on the inset at the top left of the plot. A heat source was placed in the test area and produced the data shown on the right. The red line is a Kolmogorov spectrum.

  10703 -229 V. 10 (p.13 of 14) / Color: No / Format: Letter / Date: 6/4/2018 11:21:14 AM SPIE USE: ____ DB Check, ____ Prod Check, Notes:

  Please verify that[START_REF] Lai | IMAKA: imaging from Mauna KeA with an atmosphere corrected 1 square degree optical imager[END_REF] all pages are present, (2) all figures are correct, (3) all fonts and special characters are correct, and (4) all text and figures fit within the red margin lines shown on this review document. Complete formatting information is available at http://SPIE.org/manuscripts

Return to the Manage Active Submissions page at http://spie.org/submissions/tasks.aspx and approve or disapprove this submission. Your manuscript will not be published without this approval. Please contact author_help@spie.org with any questions or concerns. 10703 -229 V. 10 (p.8 of 14) / Color: No / Format: Letter / Date: 6/4/2018 11:21:14 AM SPIE USE: ____ DB Check, ____ Prod Check, Notes:

Table 1 :

 1 Average values of r0 and L0 for the night of UT February 16

	20170216	Integrated x	Integrated y	Ground Layer x	Ground Layer y	Free atmosphere x	Free atmosphere y
	r0 (m)	0.186	0.186	0.239	0.284	0.256	0.255
	L0 (m)	196.0	25.8	2.4 x10 5	58.7	13.1	10.6
	r0_noTT (m)	0.152	0.224	0.223	0.345	0.178	0.171
	L0_noTT (m) 5.1	10.1	6.3	57.3	2.7	2.3

th , 0217, obtained from fitting the reconstructed phase structure function from covariance maps by a von Karman phase structure function. It is worth noting that the vibrations were mostly in x, which may explain the large outer scale for the ground layer along that axis. It is maybe surprising that the outer scale of the free atmosphere is so small.

Table 2 :

 2 r0 and L0 estimated with tip-tilt filtered from circular buffers but not from model, leading to a bias in outer scale.

	20170216	Integrated x Integrated y Ground Layer x	Ground Layer y	Free atmosphere x	Free atmosphere y
	Tip-tilt filtered
	r0 (m)	0.117	0.131	0.197	0.196	0.175	0.189
	L0 (m)	3.5	4.0	3.9	3.9	3.5	3.9
	r0_noTT (m)	0.133	0.174	0.201	0.242	0.201	0.242
	L0_noTT (m)