Olivier Bailleux
email: olivier.bailleux@u-bourgogne.fr

DPLL with restarts linearly simulates CDCL

If we give DPLL the ability to make restarts and to learn clauses representing the explored search space, it can linearly simulate CDCL solvers.

Introduction

Second generation SAT solvers, such as DPLL, and third generation SAT solvers, known as CDCL, have several common features. They produce sequences of assumptions (often called decisions) and unitary propagations that lead either to the discovery of a model or to a contradiction, also called conflict. In the following, such a sequence will be called AUPsequence, for Assumption and Unit Propagation Sequence, and inconsistent AUP-sequence when it leads to a conflict (an example is given in figure 1). But the two types of solvers do not exploit the contradictory AUP-sequences in the same way. Third-generation solvers analyze the sequence backwards, from the end, to seek an explanation of the conflict in the form of a clause that will be learned [START_REF] Hadi Katebi | Empirical study of the anatomy of modern sat solvers[END_REF], and then perform a non-chronological backtrack to the stage in the sequence where the learned clause becomes assertive (allows a deduction by unit resolution). Instead, the second generation solvers simply perform a chronological backtrack, which amounts to implicitly learn the clause representing the negation of the assumptions. In addition, third generation solvers perform restarts while keeping all or part of the learned clauses. In practice, restarts are crucial for the effectiveness of these solvers. They have also been used with second-generation SAT solvers [START_REF] Gomes | Boosting combinatorial search through randomization[END_REF] [SI09], but, until further notice, without preserving any information about the search space explored in previous sessions.

Let us define a UP-nogood of a formula Σ as any set E of literals such that the conjunction of Σ and the literals of E allows unit propagation to produce the empty clause, namely Σ ∧ w∈E w U P ⊥.

The two types of solvers generally do not learn the same clauses. DPLL solvers implicitly use ad absurdum reasoning and implicitly produce the UP-nogood consisting of the assumptions of the current contradictory AUP-sequence, and then implicitly learn the clause corresponding to the negation of this nogood. In addition, the assumptions are stated in an order imposed by chronological backtracking. In the case of CDCL solvers, the UP-nogood is produced from the current contradictory AUP-sequence by starting from the negation of the clause that became empty, and by iteratively replacing a literal w of this nogood by the literals that allowed to deduce w. In most CDCL solvers, this process stops when exactly one of the literals in the current nogood have been fixed at the last assumption level. This learning scheme is known as first-UIP for First Unit Implication Point. For more details, see for example [START_REF] Hadi Katebi | Empirical study of the anatomy of modern sat solvers[END_REF]. CDCL solvers are known to have the same deductive power as General Resolution in the sense that they can produce refutations whose size is polynomially related to that of the shortest refutations that can be produced by Resolution [START_REF] Pipatsrisawat | On the power of clause-learning sat solvers as resolution engines[END_REF]. This is not the case with DPLL solvers, which can refute only in exponential time some formulae that can be refutable in polynomial time and space by Resolution, and therefore by CDCL solvers, subject to an appropriate choice of assumptions [START_REF] Ben-Sasson | Near optimal separation of tree-like and general resolution[END_REF]. This applies in particular to Pebbling formulas, which encode the possibility of performing a set of tasks subject to precedence constraints.

The common feature of second and third generation solvers is that when they deal with inconsistent formulae, they implicitly produce refutations of these formulae in a particular form called RUP for "Reverse Unit Propagation" [START_REF] Goldberg | Verification of proofs of unsatisfiability for cnf formulas[END_REF]. An RUP of a CNF formula Σ is a sequence q 1 , ..., q m of clauses such that for any i ∈ 1...m, Σ ∧ q 1 ∧ ... ∧ q i-1 ∧ ¬q i can be refuted by unit propagation (formally, Σ ∧ q 1 ∧ ... ∧ q i-1 ∧ ¬q i U P ⊥), from which it follows that each clause q i is a logical consequence of Σ. Each clause of an RUP is therefore a key to produce, thanks to unitary propagation, a step of a proof establishing that the last clause of the sequence is a logical consequence of the formula. See [START_REF] Heule | Proofs for satisfiability problems. All about Proofs[END_REF], for a detailed presentation of the concept of RUP and other variants of clausal proofs.

For example,

q 1 = (b ∨ c), q 2 = (b), q 3 = ⊥ is a RUP of the formula Σ = (a ∨ ¬b)(b ∨ c ∨ ¬d)(b ∨ c ∨ d)(b ∨ ¬c ∨ e)(b ∨ ¬c ∨ ¬e)(¬b ∨ e)(a ∨ ¬b ∨ e)(¬a ∨ ¬b ∨ ¬e) (1)
because

¬q 1 ∧ Σ U P ⊥, ¬q 2 ∧ q 1 ∧ Σ U P ⊥, ¬q 3 ∧ q 2 ∧ q 1 ∧ Σ U P ⊥
The concept of RUP is essentially used for the verification of refutations produced by SAT solvers when they deal with inconsistent formulas, particularly during competitions, where the concerned solvers must produce RUP refutations that are checked by an independent application. Actually, DPLL and CDCL solvers can be considered as machines for producing RUPs. By adopting such a point of view, CDCL's strength is to produce, with certain formulas, RUPs that are much smaller than the smallest RUPs that can be produced by DPLL solvers.

The purpose of this paper is to present a version of the DPLL with restart that learns, before each restart, a set of clauses representing the knowledge accumulated during the previous search session. We will call such a program DPLL+R (for DPLL + Restart) or 2.5 th generation solver. With a sufficient number of restarts, and by choosing the assumptions appropriately, such a solver can produce exactly the same RUPs as CDCL solvers. In practice, this does not guarantee that such DPLL+R solvers are as effective as CDCL solvers, but it can be argued that the difference in efficiency depends only on the restart policy and the heuristic of assumption selection. This opens some perspectives for exploring the research field between second generation and third generation solvers. In addition, this approach has already been successfully tested in the field of constraint programming [GBL + 17].

DPLL + Restarts

Applied to a formula Σ, DPLL explores the space of all possible assignments of the variables involved in this formula. To do this, it produces a series of contradictory AUP-sequences under a constrained order of assumptions. More precisely, the state of the solver at the time of a conflict occurring after m assumptions is characterized by a list (h 1 , p 1 ), ..., (h m , p m ) where h i denotes an assumption represented by a literal, and p i ∈ {1, 2} represents the phase of this assumption in the current sequence. The successive solver states and associated sequences are subject to the following constraints, which reflects the notion of chronological backtracking:

The conflicting state following any conflicting state (h 1 , p 1 ), ..., (h i-1 , p i-1 ), (h i , 1), (h i+1 , 2), ..., (h m , 2) must be (h 1 , p 1 ), ..., (h i-1 , p i-1 ), (¬h i , 2), (h i+1 , 1), ..., (h m , 1), i.e., the last assumption in phase 1 must be complemented, then switched in phase 2 and followed, if applicable, by assumptions in phase 1.

Each conflicting state e of the solver characterize a set C e of counter-models of the interpretation space of the formula Σ. Clearly, if e = (h 1 , p 1 ), ..., (h m , p m ), then C e = C(e) where C is the function defined as follows:

       C((h , 1)) = h C((h , 2)) = C((h 1 , 1), (h 2 , p 2 ), ..., (h m , p m )) = h 1 ∧ C((h 2 , p 2 ), ..., (h m , p m )), m > 1 C((h 1 , 2), (h 2 , p 2 ), ..., (h m , p m )) = ¬h 1 ∨ C((h 2 , p 2 ), ..., (h m , p m )), m > 1 (2)
For example, with a lexicographic order of assumptions, DPLL refutes the previously introduced formula Σ (1) as shown figure 3. At the time of the conflict ending the sequence highlighted in yellow, the solver is in the state e = (a, 2), (¬b, 1), (¬c, 1). The interpretations already eliminated at this stage, as defined by the formula (2), are the models of the formula C e = ¬a ∨ (¬b ∧ ¬c). These interpretations are counter-models of Σ, and represent the knowledge deduced by the solver. This knowledge can be represented by the clauses (¬a) and (b ∨ c).

More generally, the knowledge C e capitalized by a DPLL session that has reached a conflicting state e can be very easily represented by a set of clauses, i.e., the negation of C e . Note that the cardinal of this set is linearly related to the number of assumptions in phase 2. The algorithm DPLL+R consists in repeating the following actions until either a model is found or a conflicting state with all the assumptions in phase 2 is reached.

1. Run a DPLL search session that can be stopped (according to a criterion to be defined) at any conflict state.

2. Produce the clauses encoding the knowledge capitalized by the search session using the formula (2).

Deduction power of DPLL+R

In this section, we will show that if DPLL+R had a way to choose the assumptions appropriately, it could produce any RUP that could be produced by any CDCL solver, and therefore it could solve any SAT instance as effectively as any CDCL solver. To the best of our knowledge, this result, although quite obvious, has not yet been explicitly mentioned in the literature. It is based on the idea of using an RUP produced by a CDCL solver as an oracle to choose the assumptions of a DPLL solver performing a restart at each conflict (i.e. at the first conflict of each research session).

We will call AUP-nogood of a formula Σ any list n 1 , ..., n t of literals that, when used as assumptions, produce a contradictory AUP-sequence, meaning that all the possible propagations from Σ do not produce any w such that ¬w ∈ {n 1 , ..., n t }, all the possible propagations from Σ ∧ n 1 ∧ ... ∧ n i , i ∈ 1..t -1 do not produce any w such that ¬w ∈ {n i+1 , ..., n t }, and, the empty clause is propagated from Σ ∧ n 1 ∧ ... ∧ n t .

Clearly, the set of the literals of any AUP-nogood of a formula Σ is a UP-nogood of Σ. This is a direct consequence of the confluence theorem of domain consistency in constraint programming [START_REF] Krzysztof | Principles of constraint programming[END_REF]. But the reverse is not true. Some UP-nogoods are not AUP-nogoods, first of all, the negation of a clause of Σ. For example, if (a ∨ b ∨ c) is a clause of Σ, and {¬a, ¬b} is not a UP-nogood of Σ, then < a, b, c > is not a AUP-nogood because ¬a ∧ ¬b will propagate c, and therefore ¬c cannot be used as the next assumption.

In the following, we will show that any UP-nogood produced by a CDCL solver, when sorted appropriately, is an AUPnogoods. As a result, DPLL+R can simulate CDCL by using as assumptions, in the appropriate order, the literals of this UP-nogood.

For example, the figure 4 shows again the contradictory sequence S 1 from the figure 2 produced from the example formula Σ (1). From this sequence, a CDCL solver produces the AUP-nogood ¬b, ¬c from which the clause (b ∨ c) will be learned. This clause will appear in the RUP generated by the CDCL solver. Not all the literals of this AUP-nogood correspond to assumptions in the contradictory sequence from which it was produced. But if we use these literals as assumptions, we produce a contradictory sequence S 1 .

Figure 4: A contradictory AUP-sequence S 1 produced from the formula (1), the AUP-nogood produced by analysis of this sequence by a CDCL solver, and the contradictory sequence S 1 obtained by using the literals of the nogood as assumptions.

Let us define a consistent Σ-AUP-sequence s as a sequence s 1 , ..., s k of segments, where each segment s i consists of a literal h i called assumption and a sequence L i of literals verifying the following properties:

1. Neither h i nor ¬h i can be deduced by unit propagation from Σ and the assumptions of the previous segments.

2. Each literal of L i can be deduced by one unit resolution from one or more previous literals of s and a clause of Σ.

Any literal that can be deduced by unit propagation from

Σ ∧ h 1 ∧ ... ∧ h i is in one of the segments L 1 to L i .

The empty clause cannot be deducted from

Σ ∧ h 1 ∧ ... ∧ h k by unit propagation.
Let us define a contradictory Σ-AUP-sequence s as a sequence s 1 , ..., s k , c of segments such as s 1 , ..., s k is a consistent Σ-AUP-sequence and c is a segment consisting of a literal h c and a sequence L c of literals verifying the following properties:

1. Neither h c nor ¬h c can be deducted by unit propagation from the assumptions of the previous segments and Σ.

2. Each literal of L c can be deduced by one unit resolution from one or more previous literals of s and a clause of Σ.

3. The empty clause can be deduced by one unit resolution from the last literal of L c , one or more previous literals of s and a clause of Σ.

We will only write AUP-sequence when there is no ambiguity about the formula used for deductions. The figure 5 illustrates the composition of a AUP-contradictory sequence.

Figure 5: A contradictory AUP-sequence.

Please note that the fact that a Σ-AUP-sequence s 1 , ..., s k is consistent does not tell us that the empty clause is not a logical consequence of Σ ∧ h 1 ∧ ... ∧ h k but tells us that the empty clause cannot be deduced from this formula by unit resolution. On the other hand, if a Σ-AUP-sequence s 1 , ..., s k , c is contradictory, then

Σ ∧ s 1 ∧ ... ∧ s k ∧ c is inconsistent, so the clause ¬h 1 ∨ ... ∨ ¬h k ∨ ¬h c is a logical consequence of Σ.
We will call the list h 1 , ..., h k (, h c ) of assumptions the key of the AUP-sequence s 1 , ..., s k (, c). The sequences that can be generated from the same key can differ in the order of the propagations done in each segment when several unit resolutions are possible. The key of a contradictory AUP-sequence is clearly a AUP-nogood. Now, we will show that the nogoods produced by CDCL solvers are indeed AUP-nogoods, and therefore can allow DPLL+R to refute a formula as quickly as CDCL if (1) it makes a restart after each AUP-sequence and (2) it uses as assumptions the literals of the nogoods produced by CDCL, in the appropriate order.

Let us recall how CDCL solvers produce their nogoods from a contradictory AUP-sequence s = s 1 , ..., s k , c from a so called conflict clause q c which was become empty at the end of segment c. The production of a nogoods is done in several steps. Each step replaces the current nogood, which is initially the negation of the conflict clause, with a new nogood, until a stopping criterion is verified. Whatever the learning scheme used, at the time of stopping the process there is always exactly one literal of the current nogood in the last segment c of s. In the case of the 1-UIP learning scheme, the most common one, the stop occurs as soon as this condition is fulfilled. Here is the detailed algorithm.

Data: a contradictory AUP-sequence s Result: a nogood N E ← {¬w, w ∈ q c }, where q c is the conflict clause of s; while the stopping criterion is false do let r be the literal of E that has the highest rank (closest to the end) among the literals of E that are not in the key of s (i.e. among those that have been deducted by unit propagation); let q be the clause that was used to produce r; E ← E\{r} ∪ {¬w, w ∈ q\{r}} ; end N ← the elements of E sorted according to their ranks in s;

Algorithm 1: Production of a sorted nogood. Now, let us introduce the following property.

Proposition 3.1. Let Σ be a CNF formula, s = s 1 , ..., s k , c be a Σ-AUP-sequence, and N = n 1 , ..., n t be a nogood produced from s using algorithm 1, where n 1 , ..., n t are sorted according to their positions in s. For each i ∈ 2..t -1, ¬n i cannot be propagated from n 1 , ..., n i-1 , namely, Σ ∧ n 1 ∧ ... ∧ n i-1 U P ¬n i .

Proof. Let n i , i ∈ 1..t be a literal of N . We know that n i is in s. The tree following cases can occur :

1. n i is an assumption of s. In this case, if ¬n i could have been propagated from the previous literals of N , which represent a subset of the literals located before n i in s, then ¬n i would have been propagated in s, (because, by construction of s, all possible propagations are achieved before each assumption), and then n i could not be an assumption of s. The property holds.

2. n i is propagated in the last segment of s. In this case, i = t and all the literals n j , j ∈ 1..t -1 of N are in the consistent part of s. If these literals had allowed the propagation of ¬n i , this propagation would have been done in the consistent part of s and n i would therefore not have been propagated in the last segment. The property holds.

3. n i is propagated in a segment s j of the consistent part of s. The literals before n i in N are located in s either in the segments before s j , or in s j . But if these literals had been able to propagate ¬n i , they would have done no latter than in the segment s j , and the propagation of n i would have produced the empty clause in the segment s j . This is in contradiction with the fact that s j is in the coherent part of s. The property holds.

As a corollary, the UP-nogoods produced by CDCL, if sorted in the appropriate order, are AUP-nogoods. It follows that DPLL+R can linearly simulate any refutation of a formula performed by a CDCL solver, at the cost of a restart after each contradictory AUP-sequence, and subject to the choice of the appropriate assumptions (decision variables).

Conclusion

Giving a DPLL solver the ability to restart and learn clauses representing the knowledge acquired since the last restart gives it the same deductive power as a CDCL solver. This does not necessarily imply that in practice there are heuristics of assumptions choice that allow DPLL+R to be as effective as CDCL with 1-UIP learning scheme, but it tells us that the difference in efficiency between the two, if applicable, is heuristic in nature. More specifically, the combination of the 1-UIP learning scheme and non-chronological backtracking is not in itself a fundamentally more powerful proof system than the learning of the negation of decision literals (which we have preferred to call assumptions in this article). Rather, it is an effective heuristic for producing refutations by inverse unit propagation (RUP). The question that remains open is the existence of assumption choice heuristics that would allow DPLL+R solvers to produce RUP refutations as short as those produced by the best CDCL solvers.

Although we have exploited, for the purpose of proving the deductive power of DPLL+R, the properties of the borderline case where the solver restarts after each conflict, we think it would be very interesting to experiment with this type of solver with a less drastic restart regime, seeking a good compromise between the theoretical deductive power and the growth of the number of clauses learned, so as to exploit the ability of chronological backtracking to represent in a very concise way the explored part of the interpretation space. The potential of this approach is based on the existence of heuristics of assumption choice that can exploit the theoretical potential of the underlying proof system.

Figure 1 :

 1 Figure 1: An example of a contradictory AUP-sequence. Circles refer to assumptions and squares to propagations.

Figure 2 :

 2 Figure 2: On this example of a contradictory AUP-sequence, DPLL implicitly produces the clause a ∨ c, while CDCL explicitly produces the clause b ∨ c .

Figure 3 :

 3 Figure 3: The search tree of DPLL on the formula (1).


Artem Melnyk

Vladimir Borysenko

Patrick Henaff

Analysis of synchrony of a handshake between humans

come



Abstract-Physical and social interaction between humans and robots are important for humanoid robotics. In this article the characteristics of a handshake between humans are physically examined aiming at future experiments with a handshake between a human and a robot. A special pair of data gloves has been designed to measure quantitative characteristics of a handshake ritual such as duration, strength of the grip, and frequency of the rhythmic movements. Experiment results show that handshaking consists of four phases. After a physical contact, a mutual synchrony appears between the two persons. A statistical analysis shows that the frequency of this synchronization is around 4 Hz and average strength of the grip is 2.5 N.

I. INTRODUCTION

Usually, robots are used for a special set of tasks. The parameters of their environment are known and constrained and they do not perform any unexpected interaction until they are reprogrammed. The priorities of a large number of robots which work in industry are their accuracy and speed.

Advances in artificial intelligence and robotics are now looking to challenges in non-constrained robot environments [START_REF] Alami | Safe and dependable physical Human-Robot interaction in anthropic domains: State of the art and challenges[END_REF], [START_REF] Santis | An atlas of physical human robot interaction[END_REF]. More flexible and intelligent control systems are designed to create adaptive robots able to perform new tasks, interact or work with humans. Robots will become adaptable, acquire learning abilities and exhibit new behavior corresponding to any change in their environment [START_REF] Kahn | What is a human? -toward psychological benchmarks in the field of Human-Robot interaction[END_REF]- [START_REF] Huber | Humanrobot interaction in handing-over tasks[END_REF].

In the near future, the humanoid robot will appear in the human environment as a companion to help or to work with the humans. This raises the relevant question of interaction between a human and robot in a human -friendly behavior. The social robot is a focus of attention of researchers in robotics, psychology, neuroscience and sociology. There are works about security [START_REF] De Rengerve | Online learning and planning in a pick-and-place task demonstrated through body manipulation[END_REF] and a real role of a robot [START_REF] Dautenhahn | What is a robot companion -friend, assistant or butler?[END_REF]- [START_REF] Haddadin | The role of the robot mass and velocity in physical human-robot interaction -part i: Non-constrained blunt impacts[END_REF] in the human environment. A great number of researches have been carried out in the field of physical Human-Robot Interaction (pHRI) wherein handshaking is an important subject [START_REF] Jindai | Development of a handshake request motion model based on analysis of handshake motion between humans[END_REF]- [START_REF] Vanello | Neural correlates of humanrobot handshaking[END_REF]. Human-robot interaction has been studied through the handshaking action [START_REF] Kawarazaki | Communication robot system based on the handshaking action[END_REF]. In [START_REF] Zeng | Human-robot handshaking: A hybrid deliberate/reactive model[END_REF] the authors propose a hybrid deliberate/reactive model to achieve natural handshaking between a human and a robot and they compare the trajectory and interaction force during the human-human and human-robot handshaking. investigations in human psychology are giving rise to comprehensive study of this social phenomenon. Handshaking has an important social function of regulating and maintaining human interactions [START_REF] Schiffrin | Handwork as Ceremony: The Case of the Handshake[END_REF], [START_REF] Bernieri | The influence of handshakes on first impression accuracy[END_REF], and it is a universally accepted pattern of behavior in societies that initiates and constitutes social interaction [START_REF] Hall | The handshake as interaction[END_REF]. Some works show that there seems to be a strong association between poor handshaking skills and autistic psychopathology [START_REF] Golubchik | Handshaking as a measure of social responsiveness in patients with autistic spectrum disorder[END_REF].

According to [START_REF] Astr | Greeting behaviour and psychogenic need: interviews on experiences of therapists, clergymen, and car salesmen[END_REF] a handshake provides the information about the person character. Several studies show that specific handshake manners may depend on personality traits [START_REF] Astrom | Introductory greeting behaviour: a laboratory investigation of approaching and closing salutation phases[END_REF]. In [START_REF] Chaplin | Handshaking, gender, personality, and first impressions[END_REF] it is shown that handshake characteristics like completeness of grip (forces), strength, duration, vigor (frequency) and others are related to particular orthogonal factors of personality. The authors define a set of qualitative characteristics related to impressions of the experiment participants. Thus, one can imagine that in future a humanoid robot will be able to handshake with humans like humans and why not with different personality characteristics. This paper aims to better understand a handshake between humans. Experiments are carried out aiming at a quantitative analysis of a handshake, especially the synchrony phenomenon that appears when the hands of two humans interact. Coupling energy of interaction between oscillating systems causes synchronization and it is defined as an adjustment of frequency of one or both of the coupling objects (mutual adjustment) [START_REF] Pikovsky | Synchronization: a universal concept in nonlinear sciences[END_REF]. This nonlinear phenomenon is well-known in biological and physical systems where various oscillating systems interact and start to behave synchronously by adjusting their own frequencies. For example, two people walk synchronously after a few tens of steps, the choristers heart rhythms are synchronized while singing, the breathing of a baby synchronizes with the breathing of its pregnant mother. Moreover, an interesting aspect of the phenomenon of synchronization in human interactions is its unintentional nature.

Several researches in psychology take into account the concept of synchrony for its important role in early development, language learning and social interaction. As humanoid robot actions will occur in a social context, the phenomenon of synchrony is now being studied in such fields as social signal processing, machine learning and robotics [START_REF] Schmidt | Dynamics of interpersonal coordination[END_REF]. In [START_REF] Hasnain | A synchrony-based perspective for partner selection and attentional mechanism in humanrobot interaction[END_REF], the authors describe the mechanism of Human-Robot Interaction which is initiated by synchrony detection. In [START_REF] Shen | The impact of participants' beliefs on motor interference and motor coordination in Human-Humanoid interactions[END_REF], human motor coordination responses indicate that the participants tend to synchronize with agents with better overall perception. Based on the results of this experimental study, the authors suggest that a humanoid robot with good overall perception as a "social entity" may facilitate "engaging" interactions with a human. In [START_REF] Ronsse | Human-Robot synchrony: Flexible assistance using adaptive oscillators[END_REF], [START_REF] Melnyk | Physical Human-Robot Interaction in the handshaking case: Learning of rhythmicity using oscillators neuron[END_REF], the authors show that the synchrony between a human and a robot arm when they interact in a handshaking situation can be learnt using adaptive oscillators or central pattern generators (CPG).

Analysis of Synchrony of a Handshake Between Humans

A. A. Melnyk , V. Ph. Borysenko and P. Hénaff

In this paper, the characteristics of a handshake between humans are physically examined aiming at future experiments with handshakes between a human and a robot. A special pair of data gloves has been designed to measure quantitative characteristics of a handshake ritual such as duration, strength of the grip, and frequency of the rhythmic movements.

After this introduction, the second part of this paper describes the proposed materials and methods to measure handshake synchrony. The third part presents the experiments. Analysis of the synchrony during several handshakes between various couples of humans is carried out. Finally, the conclusion and perspectives are given in the fourth part.

II. MATERIALS AND METHODS

A. Materials

To measure human handshake characteristics, a customized wearable experimental setup has been designed (see [START_REF] Melnyk | Sensor network architecture to measure characteristics of a handshake between humans[END_REF] for more details). It consists of a set of several sensors (accelerometers, gyroscopes and force sensitive resistors) attached to a glove, and of a microcontroller for signal acquisition and conditioning. Our system allows reproducible experiments to quantify handshake characteristics such as duration and strength of the grip, vigor and rhythmicity of a handshake. Compared to the commercially existing systems (which are not available in Ukraine) our system is cheaper and it allows measuring hand grip force simultaneously with acceleration. The glove equipped with six degrees of freedom (6 DoF) inertial measurement unit (IMU) and six force sensitive resistors (FSR) transduces hand movement parameters and interaction force values. The FSR are glued on the palm region of the glove to get the data about the fullness of the grip of two interacting hands (Fig. 1a). The 6 DoF IMU is attached to each glove on the back of the palm (opisthenar). It provides three linear accelerations and three angular velocities. Accelerations allow measuring vigor of a handshake and angular velocities allow reconstructing the motion of the hand for other experiments not presented in this paper. Fig. 1b and Fig. 1c present the sensing axes of the 6 DoF IMU. Position of the FSR on the hand allows measuring the distribution of the forces during the grip and then how each person grips the hand of the other person.

The characteristics of the sensors are given in Table 1. The current values of accelerations are processed in real time with a sampling time of 20 ms by a 16 MHz microcontroller ATmega2560 and sent asynchronously via USB port to the remote computer after filtering and transformations of coordinate systems.

B. Methods

The dynamics of interaction between two hands during a handshake is investigated to examine the phenomenon of synchrony. The Phase Locking Value index (PLV) is used to compute the phase difference between the accelerations of the two human hands. PLV is a method presented by Lachaux et al. for detecting EEG synchrony in a band of frequencies [START_REF] Lachaux | Measuring phase synchrony in brain signals[END_REF]. The PLV is obtained after having applied filtering and a convolution with a complex Gabor wavelet on the two signals (see [START_REF] Lachaux | Measuring phase synchrony in brain signals[END_REF] for more details). The PLV value is close to 1 for synchronized signals and approaches 0 otherwise. In our experiments, the PLV is defined by: where are the phases of the accelerations measured on person I and II. is the phase difference between the two signals and N is the number of samples. The parameters of the PLV process are fixed for analysis of natural arm movements in accordance with the work presented in [START_REF] Lachaux | Measuring phase synchrony in brain signals[END_REF].

III. EXPERIMENTAL RESULTS OF HANDSHAKING

A. Experimental setup

Two persons were equipped with our system of sensors and were proposed to start a casual handshake. The persons were allowed looking and speaking to each other for more natural experimental conditions. They stood at arm length, so they did not have to do any additional movements except handshaking (Fig. 1). Before starting handshaking, a twostage calibration procedure was applied to obtain adequate measurements from the sensors. During the first stage the subjects did not move, they were in their natural standing position with arms lowered down. During the second stage the subjects were asked to produce, with their hands in front of them, several elementary movements (pronation, supination, flexion, extension, ulnar, radial deviations). A set of five successive handshakes is presented in Fig. 2 for the subject I and subject II. The first subfigure shows the acceleration from the x axis of accelerometer (sagittal plan), the second and third subfigures depict accelerations on y (sagittal plan) and z-axis respectively (frontal plan). The fourth subfigure depicts mean forces on the data glove of two persons (upper-side f 1 , f 2 , f 3 and lower-side f 4 , f 5 , f 6 sensors of the data glove). The average duration of a handshake is 2.67 seconds (with a standard deviation 0.86 s) and a pause (an interval between two handshakes) is 3.57 s (with s standard deviation 0.69 s). The maximum acceleration does not exceed 4.1 g. In this part of the work the average of the forces are only used to determine the physical contact. The average grip force f m is around 3.5 N. The subject I seems to be stronger than the subject II. This characteristic will be utilized in other experiments to classify the personality of subjects.

B. Handshake analysis of one pair of persons

On the Fig. 3 the analysis focuses on the third handshake of Fig. 2 those (from 14s to 20 s). The accelerations measured on the hands show that handshaking is a phenomenon that can be decomposed into four phases. In phase 1, a visual contact is established, and the persons bring their hands to start the shake (start of handshake: SoH). In phase 2, a physical contact (PhC) is established, and the participants are in the first phase of the interaction, unconsciously synchronizing their movements. In phase 3, movements are mutually synchronized (MS), and handshake continues. Phase 4 corresponds to the end of the handshake (EoH), physical connection is broken, and hands freely move back to after 0.5 s (before the interaction, the PLV value is low) and is maintained until the end of the handshake The accelerations also show that the main movement occurs in the sagittal plane. Indeed, the acceleration values on x and z axes must be modified taking into account the rotation of the hands during the movement (this rotation is not currently corrected). In fact, x and z accelerations are smaller compared to the acceleration on y axis. Thus only y axis data are considered for analysis. The angular velocities are depicted in Fig. 4. In the phase of MS, the maximum is 200 /s, while at the beginning of the transition phase PhC velocity its attenuation. 1). The PLV is computed on accelerations. The pX (respictevely: pY and pZ) is PLV result of aX (respictevely: aY and aZ) using eq.( 1). The forces are averaged on the six sensors of two persons. The PLV applied to these signals shows that synchronization seems to start 0.5 s later than when it is computed based on acceleration values. As the linear acceleration expresses better the vigor and the dynamics of the handshake, the PLV will be computed on accelerations ay in the rest of the paper. The PhC phase is defined in the interval of time from the first contact measured with the force sensors till the PLV becomes equal to 1 (Fig. 3). The MS phase is defined in the time interval where PLV is maintained at 1.0.

The fig. 5 shows a frequency analysis during the handshake. A fast Fourier transformation (FFT) is applied to the acceleration signals during PhC and MS phases. For the two subjects, in the PhC phase, the main values of the frequencies are approximately distributed in the large lobes [1Hz -6 Hz] and [6Hz -10 Hz]. For the MS phase the main frequency appears around 4Hz with a narrow bandwidth of 1.5Hz. This difference means that, during the handshake, there is a shift of the frequency of the movement from an unsynchronized rhythmic movement to a stable synchronized rhythmic movement. This phenomenon is statically analyzed in the next subsection.

C. Statistical analysis of a handshake

Aiming to prepare for future experiments with a large number of persons, preliminary experiments to analyze frequencies and durations of the handshake were carried out for six couples of persons (men from 20 to 45 years old) four handshakes per couple, i.e. 24 mixed handshakes. The goal of these experiments was unknown for the participants.

A statistical analysis of frequency shows the average of spectrums for the two phases in Fig. 6. For the PhC phase, frequencies are distributed around 3.2 Hz but with a wide band of 3 Hz. In the MS phase, the main frequency of 4.2 Hz with a narrow band of 1 Hz appears again. Amplitudes are approximately the same in the two phases. Thus, during the handshake, the movement synchronizes and accelerates to reach the frequency around 4 Hz and the two human upper limbs are coupled in a stable cycle limit. This seems to mean When the synchronization appears at the common frequency, people seem to communicate physically.

The frequency around 4Hz suggests that the subjects shake their hand rather fast. This surprising result must be confirmed by other future additional experiments. Indeed, the frequency of handshaking may depend on the psychological state of one of the persons. But in all cases, a humanoid robot must be able to reproduce the motion of this frequency in secure conditions if it handshakes with a human. The fig. 7 shows the average duration of the two phases for all the couples of persons. The MS phase is almost three times wider than the PhC phase. The PhC phase is almost the same for all the handshakes. Notice that the average strength force measured during the handshake is around 2.5N.

IV. CONCLUSION

The synchrony is a natural behavioral property of people. In this paper, we have shown that a handshake has four main phases. During the rhythmic physical interaction, in the first phase, the movements occur asynchronously, in the other phase they are phase-locked. Experiments have shown that a phenomenon of physical synchronization occurs during the handshake. Statistical analysis shows that the fundamental frequency of the movement in the synchronization phase is around 4 Hz and the average strength force is about 2.5 N for all the subjects. This frequency of 4 Hz is a surprising result.

In future works, we will investigate a large number of handshaking experiments with a large pool of human subjects including several coded social behavior for subjects. The results will provide behavior models that we could implement in a compliant robotic arm in order to reproduce handshaking between a human and robots. Moreover, it will be necessary to model and simulate personalities, and to investigate how perception (eye contact, temperature and humidity of the hand) can influence on the handshaking.

Figure 1 .

 1 Figure 1. Two interacting subjects carrying the prototype system. a) the data gloves (subjects I and II); b) the six force sensitive resistors (above sensors position on the hand is shown); c) local coordinate system (CS) for accelerometers; d) local coordinate system for gyroscopes.

Figure 2 .

 2 Figure 2.Accelerations and average forces measured on the two human arms during five handshakes.

.

Figure 3 .

 3 Figure 3. Acceleration measured in the coordinate frame of the IMU during a handshake and PLV. Axes z of the two subjetcs are opposed (see Fig.1). The PLV is computed on accelerations. The pX (respictevely: pY and pZ) is PLV result of aX (respictevely: aY and aZ) using eq.(1). The forces are averaged on the six sensors of two persons.

Figure 4 .

 4 Figure 4. Angular velocities measured in the coordinate frame of the IMU during a handshake and PLV. Axis z for velocity corresponds to axis y for accelerations (see Fig. 1).

Figure 5 .

 5 Figure 5. Superposed views of 5 handshakes of one pair of subjects (PhC Phase in blue, MS phase in red). The frequency equal to zero corresponds to the constant values in the signals at the beginning and end of hanshakes.

Figure 6 .

 6 Figure 6. Average of spectrums (FFT) for PhC-phase (blue) and MSphase (red) obtained for 24 handshakes.

Figure 7 .

 7 Figure 7. Duration analysis of PhC-phase (left) and MS-phase (right) for the six human couples.

TABLE I

 I

	.	APPLIED INERTIAL UNITS
	Measured value	Sensor	Range	Analog input
	Acceleration, aX, aY, aZ	ADXL335
	Velocities, wX, wY	PR530	300 s -1
	Velocity, wZ	LY530	300 s -1	ADC 5
	Force, fi	FSR	10 kg

ACKNOWLEDGMENT Thanks to Dr. Viacheslav Khomenko for his help in inertial sensors calibration and data acquisition. Thanks also to Olga Kuksina for linguistic editing of the article. This work is partially supported by the French Embassy in Ukraine and by the INTERACT French project referenced ANR-09-CORD-014.


Sara Hofmann
email: sara.hofmann@uni-bremen.de

Øystein Saebø
email: oystein.sabo@uia.no

Stefano Za

Alessio Maria Braccini
email: abraccini@unitus.it

Exploring Public Sector's Roles in Collaborative Consumption -A Research Agenda

Keywords: collaborative consumption, public services, public sector, government, research agenda

Motivated by the growing significance of sharing economy within our society, we here discuss which role the public sector may have within collaborative consumption (CC). CC refers to a business model grounded on peer-to-peer based sharing of goods and services through community-based online services. While public sector to a large extent has transformed from formalised bureaucratic structures into more hybrid organisations, focusing on the co-creation between public and private stakeholders, public sector's role within the sharing economy is still in need for further investigation. We reflect on the need for studying how public sector could benefit from a more active role within CC for public service provision in the e-government area. Based on current literature on CC, we argue that the public sector can take on three main roles in CC: the customers, the service providers, and the platform providers. We further develop suggestions for a research agenda in this area and raise questions for a further discussion on the role of public sector within CC.

Introduction

The way public sector provides services changed during the past 30 years, from rigid and bureaucratic structures [START_REF] Rainey | Comparing Public and Private Organizations: Empirical Research and the Power of the A Priori[END_REF], into decentralised forms of co-ordination, leveraging on the concept of competition rather than control, and favouring markets more than hierarchies for ensuring efficient allocations of scarce public resources [START_REF] Hoggett | New Modes Of Control In The Public Service[END_REF]. Confronted by progressive reductions of budgets and increased pressure on the efficiency of public expenditures, new hybrid forms of public-private collaborations emerge [START_REF] Lampropoulou | Theoretical models of public administration and patterns of state reform in Greece[END_REF], allowing for co-production of services including both public bodies and citizens [START_REF] Nabatchi | Varieties of Participation in Public Services: The Who, When, and What of Coproduction[END_REF]. In the current global climate of austerity and in the aftermath of the recent world financial crisis [START_REF] Fotaki | Co-Production Under the Financial Crisis and Austerity[END_REF][START_REF] Martin | Lean in a cold fiscal climate: the public sector in an age of reduced resources[END_REF][START_REF] Voorberg | A Systematic Review of Co-Creation and Co-Production: Embarking on the social innovation journey[END_REF], the importance of co-operation between the public, private, and the citizens for service deliveries will most probably increase [START_REF] Alford | The Multiple Facets of Co-Production: Building on the work of Elinor Ostrom[END_REF]. Meanwhile, new forms of goods and service consumption emerge [START_REF] Belk | You are what you can access: Sharing and collaborative consumption online[END_REF], based on the principles of sharing individual resources, temporary ownership, and access to digital platforms. These new business models, often referred to by the umbrella concept of sharing economy, leverage on forms of co-operation among different actorsincluding the customerthrough digital platforms [START_REF] Torre | Empowering Organizations: Enabling Platforms and Artefacts[END_REF]. Sharing economy applications evolve on separate trajectories from that of public services [START_REF] Hamari | The sharing economy: Why people participate in collaborative consumption[END_REF]. However, they are increasingly creating tensions with services regulated by the public sector, exemplified by the prominent conflict between the Uber company and the public taxi transportation service in cities all around the world, or Airbnb influencing the traditional hotel industry. Thus, in CC the public sector currently takes a role that is mainly limited to regulatory aspects.

In this paper we explore the roles public sector may play within these new business models, beyond their traditional regulatory role [START_REF] Rut | Sharing Economy: All of Us in Wonderland[END_REF][START_REF] Thoreson | The Sharing Economy. Pondering the possibilities for local government[END_REF]. We introduce the concept of collaborative consumption (CC), a specific business model within the sharing economy [START_REF] Benoit | A triadic framework for collaborative consumption (CC): Motives, activities and resources & capabilities of actors[END_REF], as a framework for studying the role of the public sector within the sharing economy. While several sharing examples are based on the co-ownership of resources between two or more individuals, CC focuses on triadic relationships between customers, peer service providers, and platform providers [START_REF] Benoit | A triadic framework for collaborative consumption (CC): Motives, activities and resources & capabilities of actors[END_REF]. Hence, we argue for CC to be a suitable framework for studying the partnering models where public sector, citizens, and private companies act together in various constellations for creating innovative ways of delivering public services and consuming goods and services.

Our aim is to initiate a discussion within the e-government community on the roles of public sector in the sharing economy, and to present a systematisation of avenues for research within the field. To address this, we follow [START_REF] Boell | A Hermeneutic Approach for Conducting Literature Reviews and Literature Searches Communications of the Association for Information Systems[END_REF]'s hermeneutic approach for reviewing the literature on CC and public sector. We argue how public sector can assume the three roles in CCcustomer, service provider, and platform providerdiscuss implications, and identify research gaps, which we summarise in a research agenda.

Method: Conceptual Framework and Hermeneutic Cycle

Our review is based on a hermeneutic literature review process [START_REF] Boell | A Hermeneutic Approach for Conducting Literature Reviews and Literature Searches Communications of the Association for Information Systems[END_REF], which is a common approach especially in conceptual papers in the field of Information Systems and egovernment (cf. e.g. [START_REF] Lindgren | Electronic services in the public sector. A conceptual framework[END_REF]). In contrast to structured literature reviews, this approach acknowledges literature reviews as subjective and interpretative processes in which the researcher gains a deeper understanding of a subject over time by iteratively identifying relevant literature, thus digging deeper into the body of knowledge. The hermeneutic approach consists of two intertwined circles, the search and acquisition and the analysis and interpretation circle (cf. Error! Reference source not found.).

Searching for literature on the concept of CC in the public sector, we found that research in this field is scarce with most articles ascribing a passive, regulative role to governments (see Section 3.2). Thus, we identified the need of deriving a research agenda for CC in the public sector in order to advance this field in a structured way. Therefore, we searched for literature on CC in general and finally decided for [START_REF] Benoit | A triadic framework for collaborative consumption (CC): Motives, activities and resources & capabilities of actors[END_REF]'s framework as the basis for our analysis since they provide a clear distinction of the different actors in CC, consisting of a triadic relationship between a customer, a service provider, and a platform provider. We iteratively searched for relevant literature for discussing these three roles within the public sector. Based on our identified research gaps, we derived a research agenda for thoroughly analysing public sector's role in CC.

Fig. 1.

Hermeneutic framework for literature reviews by [START_REF] Boell | A Hermeneutic Approach for Conducting Literature Reviews and Literature Searches Communications of the Association for Information Systems[END_REF] 3 Related Work

Public Sector Responsibilities

In order to discuss the role of the public sector in CC, we need to understand the main responsibilities of public sector within the society. Interestingly, this is rarely discussed within the e-government field; the reason why public sector exists is more or less taken for granted. Anderson [START_REF] Anderson | Government and the Economy: What is Fundamental?[END_REF] introduces seven main areas governments have within societies. While a thorough discussion of these is beyond the scope of this paper, we introduce them here to inform the discourse of CC within public sector, by reflecting on how public sector roles within the sharing economy could influence on the main responsibilities public sector has within the societies (in section four below).

The government provides an economic infrastructure, with institutions, rules and arrangements needed within a society [START_REF] Hughes | Public Management and Administration. An Introduction[END_REF]. This includes the definition and protection of property rights, enforcements of contracts, tariff systems and currencies. Rules for the economic infrastructure are provided by the political systems, explicated by regulations, and protected by sanctions. The government also provides various goods and services valuable, accessible, and broadly used by everyone, while being difficult to pay for by their individual use. Such goods include the national defense, roads, crisis response management, and other public infrastructures, representing the public goods within societies. Furthermore, the government is responsible for the resolution and adjustment of conflicts, to pursue justice, order and stability, including the protection of weaker groups, the provision of laws and sanctions to avoid exploitation of children, and regulations to secure a minimum wage for workers.

Competition within the society needs to be maintained to avoid cartels, price-fixing, and companies restricting access to their products for groups of citizens, by providing rules and regulations to avoid one or few actors to dominate the market, to maintain a healthy competition to secure the best possible quality at the right cost for the benefit of the society and their members. Moreover, the government also acts in the protection of natural resources for defending the nature against degradations, to maintain the interests of future generations. Governments are also responsible for securing all members of the society a minimum access to goods and services of the economy, for instance by adjusting potentially socially unacceptable consequences of the market economy on members of the society, such as poverty and malnutrition. People may be excluded from access to the market economy due to illness, old age and illiteracy, in which case governments are expected to intervene to provide a minimum level of assistance. Finally, since there will always be fluctuations within the economy with booms being followed by regressions, an important role for government is to stabilize the economy, through budgets, monetary policy, and control over prices and the state finances [START_REF] Hughes | Public Management and Administration. An Introduction[END_REF].

Collaborative Consumption

CC are "peer-to-peer based activities of obtaining, giving, or sharing access to goods and services, coordinated through community-based online services" [START_REF] Hamari | The sharing economy: Why people participate in collaborative consumption[END_REF]. CC underpins a form of coordination among the consumption behaviour of individuals who agree on their consumption actions, or on the acquisition and distribution of resources for a compensation [START_REF] Belk | You are what you can access: Sharing and collaborative consumption online[END_REF]. CC applications are favoured by the diffusion of digital platformslike social mediaand digital eco-systems [START_REF] Carillo | An investigation of the role of dependency in predicting continuance intention to use ubiquitous media systems: Combining a media sytem perspective with expectation-confirmation theories[END_REF][START_REF] Owyang | The Collaborative Economy[END_REF], which facilitate communication and coordination among different actors cooperating for a common goal [START_REF] Ren | Building Member Attachment in Online Communities: Applying Theories of Group Identity and Interpersonal Bonds[END_REF][START_REF] Shirky | Here comes everybody: The power of organizing without organizations[END_REF]. CC holds a potential venue to stimulate sustainable consumption practices [START_REF] Heinrichs | Sharing Economy: A Potential New Pathway to Sustainability[END_REF], to promote a cultural shift from ownership to access and sharing of resources [START_REF] Botsman | What's Mine Is Yours: The Rise of Collaborative Consumption[END_REF]. The behaviour of individuals in a CC context is guided by information sharing, collective coordination and decision making, and individual and communal rational behaviour. On the one side, the used digital platforms reduce the transaction costs for creating connections among unacquainted members and for sharing information among them [START_REF] Hamari | The sharing economy: Why people participate in collaborative consumption[END_REF][START_REF] Martin | The sharing economy: A pathway to sustainability or a nightmarish form of neoliberal capitalism?[END_REF][START_REF] Olson | The logic of collective action[END_REF]. While on the other side, people act in these settings on the basis of rational reasoning, seeking the maximisation of utility and the minimisation of costs [START_REF] Möhlmann | Collaborative consumption: determinants of satisfaction and the likelihood of using a sharing economy option again[END_REF].

The exchange of goods and services among members of the community can be based on direct or indirect reciprocity. In the former case, there is often a high level of uncertainty since participants rely on the norm of reciprocity (comparable benefits) instead of explicit agreements (negotiation). In the latter, participants provide valued resources to others without any expectation directly from the same person [START_REF] Yamagishi | Generalized Exchange and Social Dilemmas[END_REF]. In social exchange terminology, this is called 'generalised exchange' where people give benefits in response to needs or to demonstrate a general concern for the other person [START_REF] Clark | The Difference between Communal and Exchange Relationships: What it is and is Not[END_REF]. These settings are prone to free riding and opportunistic behaviour, and may determine failures where CC instead of being a way of sustainably coordinating resources usage, leads to the tragedy of the overexploitation of the commons [START_REF] Hardin | The Tragedy of the Commons -The population problem has no technical solution; it requires a fundamental extension in morality[END_REF].

Three main characteristics delineate CC from traditional forms of exchange [START_REF] Benoit | A triadic framework for collaborative consumption (CC): Motives, activities and resources & capabilities of actors[END_REF]: the number and type of actors, the nature of the exchange, and the directness of the exchange (cf. Table 1). First, CC represents a triadic connection, including a) a platform provider enabling the exchange, b) customers who request access to the assets, and c) a peer service provider who grants such access, resulting in two different providers serving the customer. Second, in CC, there is no transfer of ownership, rather, the peer service provider grants temporary property rights to customers. Third, CC is mediated through market mechanisms, unlike related phenomena such as sharing, which relies more on social mechanisms. Consequently, CC include actors who have economic motives (among others) for participating in the triadic connections with others.

Table 1. Main characteristics of CC (adopted and extracted from [START_REF] Benoit | A triadic framework for collaborative consumption (CC): Motives, activities and resources & capabilities of actors[END_REF]).

Collaborative Consumption Number and type of actors

Triadic, between a platform provider, a peer service provider and a customer

Nature of exchange

No ownership transfer, shorter periods of agreed consumption time of underutilized assets from the peer service provider, sequential use Directness of exchange Mediated through market mechanisms

Existing Studies of CC in the Public Sector

Academic literature on collaborative consumption mostly refers to the public sector taking a regulative role in private sector initiatives [START_REF] Posen | Ridesharing in the Sharing Economy: Should Regulators Impose Über Regulations on Uber?[END_REF][START_REF] Katz | Regulating the sharing economy[END_REF]. Articles that discuss the application or implications of CC in public sector organisations are few.

From an empirical perspective, CC is mainly discussed in the context of smart cities with the aim of providing better transportation and housing infrastructures. Experts call for municipality-driven alternatives to private-sector business models such as Uber and Airbnb [START_REF] Almirall | Smart Cities at the Crossroads[END_REF]. In 2012, for example, the Seoul Metropolitan Government started the Sharing City Initiative for facilitating access to services such as transportation and public libraries. Evaluations in this context show that CC does not necessarily have to be a purely private sector related business model but can be driven by governments as well, thus pursuing societal and economic goals [START_REF] Moon | Government-driven Sharing Economy: Lessons from the Sharing City Initiative of the Seoul Metropolitan Government[END_REF]. Such initiatives can create more transparency and accountability when governments provide open data about their activities.

The literature discusses various challenges for the public sector when engaging in CC. Governments need to adjust the legal framework, removing potential obstacles to CC activities [START_REF] Moon | Government-driven Sharing Economy: Lessons from the Sharing City Initiative of the Seoul Metropolitan Government[END_REF][START_REF] Chasin | Taking Peer-to-Peer Sharing and Collaborative Consumption onto the Next Level -New Opportunities and Challenges for E-Government[END_REF] and need to cooperate with external stakeholder including private companies, NGOs, citizens, and other public sector organisations [START_REF] Moon | Government-driven Sharing Economy: Lessons from the Sharing City Initiative of the Seoul Metropolitan Government[END_REF]. Relying on third parties requires governments to give up their monopoly of the provision of services and makes them more dependent on the behaviour of actors that are out of their control. Thus, adopting CC in the public sector requires a cultural shift for governments as they need to deal with the idea of decreasing ownership [START_REF] Almirall | Smart Cities at the Crossroads[END_REF], which might lead to a changing role of the public sector as perceived by the public [START_REF] Chasin | Taking Peer-to-Peer Sharing and Collaborative Consumption onto the Next Level -New Opportunities and Challenges for E-Government[END_REF]. Furthermore, especially in the context of smart cities, governments would need to access raw data from various sources as citizen platforms, Internet of Things, sensors and open city level data, which they are currently lacking [START_REF] Almirall | Smart Cities at the Crossroads[END_REF] and would have to provide initial funding for promoting CC projects [START_REF] Moon | Government-driven Sharing Economy: Lessons from the Sharing City Initiative of the Seoul Metropolitan Government[END_REF].

In addition to the rather passive regulative part in CC, the discourse on the more active roles that governments can play is limited within the current body of knowledge. While [START_REF] Chasin | Taking Peer-to-Peer Sharing and Collaborative Consumption onto the Next Level -New Opportunities and Challenges for E-Government[END_REF], for instance, review several e-government models according to their suitability for CC purposes, they narrow their perspective on governments serving as the platform provider in CC. However, "[g]overnment and regulators do more than set policy. They can also be active participants in the collaborative economy by supporting, encouraging or promoting collaborative economic activities that enable more efficient provision of public services. […] How can governments at all levels get the most benefit from the collaborative economy?" [START_REF] Stokes | Making Sense of the Uk Collaborative Economy[END_REF]. We believe that in order for public sector to benefit the most from CC, it is worthwhile to discuss if and how they can take on the three roles as discussed above: customer, service provider, and platform provider. However, such a perspective is currently under-researched by the literature.

Public Sector's Roles in CC

Public Sector as a Customer

By taking the customer role, public sector organisations can use goods and services that are provided by other parties, e.g. by other public sector organisations, citizens, or companies. This might be a cost-efficient alternative to owning resources that are a) needed only occasionally or b) very urgently and that cannot be provided by public sector organisations themselves. An example for public sector organisations acting as customers is the online platform MuniRent (https://www.munirent.co/) where organisations can use idle equipment such as heavy machinery provided by other parties. In doing so, public sector organisations do not need to own specialised equipment which they seldom use. For a monthly fee, MuniRent offers public sector organisations to list, reserve, and loan their surplus equipment. Another example of public sector acting as customers in CC is renting resources in urgent cases from public and private sector organisations.

In emergency situations such as floods, hurricanes, or wars, the public sector needs housing for many people which they may not provide themselves. Thus, they can use online platforms to rent idle housing spaces from citizens and organisations (such as flats or sport halls). During the hurricane Sandy, governments cooperated with private actors like Airbnb, to find housing for the homeless people [START_REF] Newcombe | Shared Housing Offers Disaster Relief for Cities[END_REF].

Acting as a customer in such a CC environment inevitably means involving other stakeholders such as citizens and organisations in the process of public service delivery by using the goods and services they provide. The customer role may change the selfunderstanding and role of governments in relation to the public. Furthermore, this raises the question if CC could lead to the long-desired idea of co-creation and participation.

Both research and practice have long since discussed the theoretical potentials of including citizens in public sector service delivery and creation. However, up to now, success stories about participation are rather few [START_REF] Federici | Gentlemen, all aboard!' ICT and party politics: Reflections from a Mass-eParticipation experience[END_REF]. From an economic point of view, being the customer in CC hypothetically promises costs savings since governments do not need to own all resources they use. However, it could also be prone to negative externalities against the intended governmental aims of stabilising economy and giving equal access right if for instance we think of the tensions that cases in the private sector like Foodora are creating in the labour market in some countries. Anyhow, this comes with a change in governments' business models, which currently rely on long-term contracts with certain providers and call for tenders. It is unclear how the quality of public services changes through CC [START_REF] Stokes | Making Sense of the Uk Collaborative Economy[END_REF]. A key challenge is to ensure the quality of the consumed goods and services if their creation is out of control for governments. Governments need to rely on the availability of critical resources (e.g. in crisis situations). As such the public sector role as a customer might lead to a conflict with certain government responsibilities such as the resolution and adjustment of conflicts, to pursue justice, order and stability.

Public Sector as Peer Service Provider

Public sector organisations can share idle resources with other public-sector organisations, citizens and companies via online community platforms. Public sector organisations possess equipment which is seldom in use, such as dump trucks, excavators and guardrail cleaners, and can thus be offered to others while another example refers to online libraries which lends books to citizens. Local governments provide the resources (books), which in most cases are managed via an electronic catalogue. Citizens can borrow these resources either offline or online and typically pay a monthly or yearly fee. Governments can even serve as the platform provider if they are the ones running the electronic library catalogue. A further case of the public sector acting as the peer service provider is the sharing of publicly owned cares via car sharing apps. The city of Offenbach, for example, shares government-owned vehicles on weekends with citizens when they are not needed otherwise [START_REF] Almirall | Smart Cities at the Crossroads[END_REF].

The service provider role may influence citizens' trust in governments if the public sector participates more actively in people's life by sharing goods and services with them. In the best case, this might lead to more transparency on government actions, thus creating more credibility. Sharing goods and services can help governments to ensure their responsible for securing all members of the society a minimum access to goods and services of the economy, which can, for example, be achieved by sharing resources especially with people in need. As governments would act as a new competitor in the market by sharing goods and services, this will have an effect on their responsibility of stabilizing the economy. For the public sector as such, the service provider role may, one the one hand, lead to financial income, while, on the other, also enhancing and creating new tasks concerning for instance questions of liability. At the same time, considering inequality in the access to digital technologies, this could also reduce the societal and economic cohesion within a country, and create potential competitive tensions with the private sector.

Public Sector as Platform Provider

Public sector organisations can offer online platforms where other stakeholders such as citizens, non-government organisations, and companies can share (public service related) resources [START_REF] Chasin | Taking Peer-to-Peer Sharing and Collaborative Consumption onto the Next Level -New Opportunities and Challenges for E-Government[END_REF]. This can include all kinds of goods and services, like the sharing of resources in crisis situations, ride sharing in order to reduce transport, or offering fellow citizens support in coping with government services. However, this could theoretically go as far as governments outsourcing government services to service providers. Moreover, the public sector could also offer an online-based community for internal resource sharing where to allocate personnel and equipment when needed.

It needs to be identified if it is economically sensible for the public sector to act as the platform provider since this could increase the workload for governments. From a consumer point of view, public sector serving as intermediaries between the customer and the service provider might increase the trust in the goods and services shared via the CC platform, and could avoid the tensions that private managed platforms are creating on the market. This aspect touches upon governments' responsibility of providing an economic infrastructure for its citizens. Again, this changing role of the public sector in society would possibly influence the trust in government.

Research Agenda

We argued that CC can challenge the current organisation of the public sector and deserves more attention from the research community. Based on discussing the different roles that governments can take in CC, we would like to draw the attention now to several arising questions that should be addressed by research in the near future.

Tasks and Services in the Public Sector that are Suitable for CC

The public sector fulfils an abundance of different tasks and, as explained above, has to cover various areas of responsibilities. It seems obvious that not all of them are suitable to be delivered or consumed via CC. Future research should therefore identify assess the feasibility of CC projects within different parts of the public sector:

 How does CC relate to the different areas of responsibilities within public sector?  What kind of public sector responsibilities could benefit from including CC business models, and what responsibilities should better not be exposed to such logics?  Which public sector services are suitable for being offered or consumed via CC?

Implications of CC in the Public Sector

Taking part in CC activities challenges public sector's traditional way of working. Public sector could, for example, become more strongly dependent on the provision of goods and services by other parties. While potentially reducing their own effort, CC activities create new tasks for the public sector, which need to be managed. This raises a number of issues to be clarified:

 What are societal and legal implications of CC in the public sector?  Which economic and societal negative externalities are raised by a CC strategy for the public sector?  Which new competences are needed to manage this change in the public sector?  How does the business model of the public sector (has to) change?

CC-Driven Change in Relationship between the Public Sector and the Public

When engaging in CC activities, the role of the public sector within society changes since citizens and private sector organisations become more strongly involved in the provision of services. This could lead to the desired paradigm shift that was proclaimed in the e-participation context. At the same time new forms of self-organization might reduce the need for traditional political and democratic institutions through which public services and public services policies are traditionally organized. In order to predict the changing relationship, future research should analyse:

 How does the (self-) understanding of public sector change by taking on roles in CC?  How does the public sectorcitizens relationship, and the perceived trust, change?  Could CC be a way for increasing the level of participation or engagement in the public discourse by the citizens?  How does CC initiatives affect economic viability and social vitality, as well as political validity and viability?

Theories for Analysing CC in the Public Sector

As already argued, CC in general and especially in the public sector is undertheorized. It becomes obvious that transferring this business model to the public sector touches upon various disciplines such as public administration, politics, law, economics, organisation management, e-government, and information systems, to name a few. In order to provide a comprehensive theoretical picture, we need to answer:

 Which disciplines, apart from e-government, should be considered when conducting research on CC in the public sector?  Which theories do we need to incorporate in future research?

Methodological Considerations

Given the emphasis on understanding the phenomena investigated within their real-life context through a rich description of particular instances [START_REF] Yin | Case Study Research: Design and Methods, Fourth Edi[END_REF], it is appropriate to adopt an explorative case study approach [START_REF] Kirsch | The enactments and consequences of token, shared, and compliant participation in information systems development[END_REF]. Exploratory case studies typically address how and why questions [START_REF] Yin | Case Study Research: Design and Methods, Fourth Edi[END_REF] concerning the dynamics present within a particular contextual setting [START_REF] Eisenhardt | Theory Building From Cases : Opportunities and Challenges[END_REF], with the objective of developing initial understandings, which is clearly needed within a new research area of interests.

However, since real-life examples of CC in the public sector are few, which makes it difficult to run case studies or quantitative studies, we believe simulation to be a viable method for investigating the research issue. Simulation studies are considered particularly useful for building a place in which it is easy to explore new concepts, ideas, boundaries and limitations [START_REF] Casti | Would-Be Worlds: How Simulation is Changing the Frontiers of Science[END_REF]. For this reason, we plan to investigate our proposal of studying public service provision in a CC scenario through simulation studies, which are methods for using computer software to model the operation of real world processes, systems, or events. For their nature, simulations work as virtual experiments [START_REF] Za | Exploring Foundations for Using Simulations in IS Research[END_REF]. Based on insights from both empirical studies and simulation experiments we will perform in the next steps of the research project, we believe that there will be the need to strengthen the theoretical underpinning of CC in the public sector. Thus, we also argue for the need of further conceptual studies in this area.

Conclusive Remarks

In this paper we have argued that in addition to acting as a regulative body in CC, governments can take the three different roles of customer, service provider and platform provider. We discussed the implications that might go along with the new roles for the public sector and subsequently derived a research agenda to serve as a roadmap for future research on CC in the e-government field. Thus, we contribute to the current body of knowledge by providing a systemised overview of research gaps that need to be addressed. As for the practice we are initiating a discussion on CC in the public sector that moves beyond the yet prevailing notion of governments being an outsider in the triadic relationship that constitutes CC. We argue that it is worthwhile for the public sector to take new and thus more active roles in CC. Finally, regarding the relationships between the public sector and citizens, since CC is built on community-based activities, it is interesting to explore the issues concerning economic viability (sustainability) and social vitality (reciprocal relations for satisfying social needs), as well as political validity and viability (power mobilization and distribution in making decisions). Our research is naturally limited in various ways. Being among the first ones to systematically address the possible roles of the public sector in CC we struggled with identifying relevant theoretical literature. In addition, actual applications of CC in the public sector are scarce, thus limiting the empirical evidence. We do not claim completeness for our research agenda and suggest integrating further literature from disciplines related to CC or the public sector such as public administration or political sciences. What is more, we have left out the role of governments as regulatory entities in the CC process, which might also raise points for future research. Nevertheless, we believe that our work provides a helpful point of departure for discussing CC in the public sector.