Damien Besancenot
email: besancenot.damien@univ-paris13.fr

Delphine Dubart
email: dubart@essec.fr

Radu Vranceanu
email: vranceanu@essec.fr

THE VALUE OF LIES IN AN ULTIMATUM GAME WITH IMPERFECT INFORMATION

Keywords: Ultimatum game, Asymmetric information, Lying costs, Strategic lies, Deception, Welfare loss. JEL Classification: C91, D82, D83

Humans often lie strategically. We study this problem in an ultimatum game involving informed proposers and uninformed responders, where the former can send an unverifiable statement about their endowment. If there are some intrinsically honest proposers, a simple message game shows that the rest of them are likely to declare a lower-than-actual endowment to the responders. In the second part of the paper, we report on an experiment testing this game. On average, 88.5% of the proposers understate the actual endowment by 20.5%. Regression analysis shows that a one-dollar gap between the actual and declared amounts prompts proposers to reduce their offer by 19 cents. However, responders appear not to take such claims seriously, and thus the frequency of rejections should increase. The consequence is a net welfare loss, that is specific to such a "free-to-lie" environment.

Introduction

Humans sometimes resort to lies as a tool for leveraging on negotiation power (e.g., [START_REF] Lewicki | Lying and deception: A behavioral model[END_REF][START_REF] Anton | Drawing the line: An exploratory test of ethical behavior in negotiations[END_REF][START_REF] Shapiro | Threats, bluffs, and disclaimers in negotiations[END_REF]. As noted by Lewicki and Stark (1996, p.77), in a negotiation context, "lies misinform the opponent, eliminate or obscure the opponent choice alternatives, or manipulate the perceived costs and benefits of particular choice options open to the opponent". Clearly, in a world entirely populated by liars, messages would not be taken seriously by their recipients. 1 The ability of these less ethical people to manipulate the beliefs of others is therefore grounded in the existence of at least some individuals who have a significant aversion to lying [START_REF] Kartik | Credulity, lies, and costly talk[END_REF][START_REF] Chen | Selecting cheap talk equilibria[END_REF][START_REF] Kartik | Strategic communication with lying costs[END_REF].

There is a growing body of experimental economics literature on lying and deception that focuses on what motivates individuals to resort to such questionable communication methods. In this context, players are generally referred to as the Sender (of the message) and the Receiver. [START_REF] Gneezy | Deception: The role of consequences[END_REF] submits an interesting typology of lies with respect to players' payoffs. If the lie, defined as a misrepresentation of reality, brings about an improvement in both players' well-being, we have a "Pareto white lie"; if the sender is worse-off but the receiver is better-off, we have "an altruistic white lie". If the sender is better-off while the receiver is worse-off, this is the typical "selfish lie", which [START_REF] Gneezy | Deception: The role of consequences[END_REF] acknowledges to be the most relevant category for many economic events. Taking stock from a two-person interaction experiment, he shows that a non-negligible number of subjects lie in order to reap some benefit, even if this involves a loss for their partner in the game; subjects' inclination to lie increases the more they have to gain from the lie, and decreases the more the others will lose from it.

One important finding of these empirical studies is that humans inherently present some form of aversion to lying, although its extent can vary greatly from one individual to another. [START_REF] Lundquist | The aversion to lying[END_REF] find that aversion to lying increases with the size of the lie. [START_REF] Erat | White lies, Forthcoming[END_REF] show that a majority of people are reluctant to tell even Pareto white lies, which suggests that lie aversion is independent of any social preference over outcomes. Hurkens and Kartick (2009) argue that some people might never lie and others would lie whenever they prefer the outcome of lying to the outcome of telling the truth (irrespective of the consequences of the lie). [START_REF] Sánchez-Pagés | An experimental study of truth-telling in a senderreceiver game[END_REF] analyzes a truth-telling game where senders and receivers have conflicting goals, and observes that some subjects reject material incentives to misbehave. There is an open debate on the inner nature of lying costs, some scholars claiming that people have an inner aversion to telling lies [START_REF] Vanberg | Why do people keep their promises? An experimental test of two explanations[END_REF], and others suggesting that people refrain from lying because they do not like to deceive others [START_REF] Charness | Promises and partnership[END_REF]2010). [START_REF] Hao | Honest lies[END_REF] provide experimental evidence to support the hypothesis that the only reason many people refrain from lying is to preserve their image of an honest person, but they willingly turn to lying when their action is hidden. However, in their experiment too, about 44% of the subjects exhibit an intrinsic preference for honesty even under secrecy.

In this paper, we aim to study the inner mechanism of misleading communication in the negotiation context specific to the ultimatum game [START_REF] Güth | An experimental analysis of the ultimatum bargaining[END_REF]). In the standard experimental setup, the two players are often referred to as the Proposer and the Responder.

The Proposer is endowed with an amount of money and must make an offer as how to divide this sum between them. The Responder can accept the offer, in which case the endowment is divided as proposed, or reject it, in which case both players receive nothing. The subgame perfect Nash equilibrium with pure self-interest predicts that responders should accept any positive amount, and, knowing this, proposers should make close-to-zero offers. This result has been invalidated by an impressive number of tests (Roth, 1995). As documented by [START_REF] Oosterbeek | Cultural differences in ultimatum game experiments: Evidence from a meta-analysis[END_REF] in a meta-analysis covering 37 papers, on average proposers offer about 40% of the "pie"; also, about 16% of the offers are rejected. 2 These results have been interpreted as evidence of an inherent concern for fairness concern specific to human beings [START_REF] Camerer | Behavioral Game Theory[END_REF].

In order to allow the proposer to send misleading messages, we make sure that the responder has only imperfect information about the proposer's endowment. 3 The proposer is then asked to send a message indicating the amount of money received at the outset of the game; this is unverifiable information for the responder. The proposer's strategic advantage over the responder is thus twofold: he makes the first move and has full information about his position in the game. The responder's negotiation power stems from his ability to turn down the offer submitted by the proposer, at a cost for himself. We expect the responder to reject "unfair" offers; knowing this, the proposer should make offers that the former is likely to accept.

In the first part of the paper, we develop a simple message model in this ultimatum framework, building on the theoretical literature on strategic communication with lying costs [START_REF] Kartik | Credulity, lies, and costly talk[END_REF][START_REF] Chen | Selecting cheap talk equilibria[END_REF][START_REF] Kartik | Strategic communication with lying costs[END_REF]. If there are some intrinsically honest proposers, we show that the others will claim that they received a smaller endowment simply to push down responders' expectations about this endowment and hence submit lower acceptable offers. The trade-off between lying costs and lying benefits is thus at the heart of the paper. In the second part of the paper, we implement an experiment where anonymous 2 See [START_REF] Bearden | Ultimatum bargaining experiments: The state of the art[END_REF] for an almost exhaustive survey of the literature on this game.

3 Many authors have studied ultimatum games with imperfect information, be it uncertainty or ambiguity (inter alia, [START_REF] Mitzkewitz | Experimental results on ultimatum games with imperfect information[END_REF][START_REF] Straub | An experimental investigation of ultimatum games: Information, fairness, expectations, and lowest acceptable offers[END_REF][START_REF] Kagel | Fairness in ultimatum games with asymmetric information and asymmetric payoffs[END_REF][START_REF] Güth | Two-level ultimatum game with incomplete information: An experimental study[END_REF][START_REF] Amnon | Ultimatums in two-persons bargaining with one-sided uncertainity: Offer games[END_REF][START_REF] Croson | Information in ultimatum games: An experimental study[END_REF]. A standard result is that proposers make substantially lower absolute offers as compared to the perfect information case. pairs of subjects were asked to play the game described above four times. At the outset of a given round, the computer chooses the proposer's endowment from a uniform distribution; responders know this distribution. The proposers make an offer and send their message. The empirical results corroborate the theoretical model's predictions of proposers' behavior; the proposers understate the actual amount in 88.5% of messages (by 19% on average). However, the empirical evidence on responders' behavior challenges the theoretical model. On average, they base their accept/reject decision on the offer alone ignoring the message. As a result, the frequency of rejections, bringing about losses for both parties, is higher than in a truth-telling context. Probably one important contribution of this paper is to point out that, at least in this simple interaction, the "free-to-lie environment" is socially inefficient.

Our experiment -combining an ultimatum game with imperfect information and a message game -can be seen as an extension of the empirical study by Croson et al. (2003). 4 In their paper, pairs of subjects play, four times, an ultimatum game with an outside option for responders if they reject the proposers' offer, under various information treatments.

In one treatment, proposers know the size of the pie (actually one of four possible values), while responders know that it can be anything between two given bounds (responders are thus subject to decision ambiguity). [START_REF] Croson | Cheap talk in bargaining experiments: Lying and threats in ultimatum games[END_REF] also allow for players to exchange messages and use a dummy variable to record a misleading/true message. In contrast to their study, in our experiment responders know the statistical distribution of the proposers' endowment; these amounts are drawn from an almost continuous distribution, an approach adopted by [START_REF] Amnon | Ultimatums in two-persons bargaining with one-sided uncertainity: Offer games[END_REF]. Proposers' lies are measured by the difference between the declared and the actual amount, not by a dummy variable. We can therefore estimate the "subjective value" of a one-dollar lie, i.e. by how much on average a proposer reduces his offer each time he understates his endowment by one dollar.

The paper is organized as follows. The next section presents a theoretical analysis of the lying strategy in an ultimatum game with imperfect information. Section 3 introduces the experiment. The last section presents the conclusion.

2 Theory: the "message game"

Main assumptions

In this section we aim at analyzing the communication strategy of a Proposer in an ultimatum game with one-side imperfect information. We consider a pair of players taken at random from a large population of individuals. Within a basic pair the two players will be referred to as the Proposer and the Responder. To keep the analysis as simple as possible, we assume that individuals are identical in everything but their aversion to lying.

At the outset of the game, the proposer gets a cash endowment Y randomly chosen in the range [0, A] according to an uniform distribution. The responder does not observe this endowment, but know the statistical distribution. Then the proposer must make two decisions. He must send a message M to the responder about the value of Y and must make a cash offer Z, with Z < Y. The message can be true (M = Y ) or false (M 6 = Y ). The responder cannot verify it. At the last stage, the responder who gets the offer Z and the message M must decide whether to accept or to reject the offer. If he accepts the offer, the proposer gets (Y -Z) and the responder gets Z; if he rejects the offer, both players get nothing.

Players aim to maximize their expected utility given their set of feasible strategies. In this simple model, we assume that -all things equal -players prefer more money to less, have fairness concerns, and present an aversion to lying, i.e. they dislike misrepresenting reality.

For an individual k, lying aversion is represented by a cost C k that the individual incurs whenever he tells a lie; following [START_REF] Lundquist | The aversion to lying[END_REF], we admit that this cost is proportional to the "size of the lie", i.e. the gap between the declared and the true value of the variable of interest; we can write the total cost as

C k = c k |Y -M | , where c k > 0
is the marginal cost of one-dollar lie. There are two types players with respect to the lying cost.5 Following the experimental evidence brought by Hurkens and Kartick (2009), [START_REF] Hao | Honest lies[END_REF] or [START_REF] Erat | White lies, Forthcoming[END_REF], we admit that a share α of the population is made of intrinsically honest individuals or "H-type players". For those players, the lying cost always exceeds the reward they can get from a false message M (in other words, c H is large enough). All other (1α) individuals have a marginal cost c L = c, with c small enough; they might consider the trade-off between bearing the cost of a lie (M < Y ) and the gain from making a lower offer Z. 6 We refer to these would-be liars as the "L-type players". [START_REF] Fehr | A theory of fairness, competition, and cooperation[END_REF] argued that individuals in a position to compare their own gain with that of a reference group incurs an utility loss if their gain is below the average income of the group, what they call "disadvantageous inequality aversion", and can also bear an utility loss if they have a gain higher than the reference group, what they call "advantageous inequality aversion". They argue that an individual's sensibility to advantageous inequality aversion should be lower than the sensibility to disadvantageous inequality aversion. For the sake of simplicity, in this paper we assume that the two players in our ultimatum game are not sensible to advantageous inequality, i.e. they do not suffer an utility loss if they earn more than the other. We also admit that all subjects present the same aversion to disadvantageous inequality.

The ultimatum game is a two-player interaction. If we use the index k and -k to denote the two persons, and denote their payoffs by respectively x k and x -k , the utility function of individual k can be written as:

U k (x k ) = x k -1 (x k <x -k ) v(x -k -x k ) -1 lie C k , (1)
where

1 (x k <x -k
) is a dummy variable that takes the value 1 if x k < x -k and 0 if else, parameter v (with v > 0) captures the utility loss related to "disadvantageous inequality" of individual k and 1 lie takes the value 1 if M 6 = Y (lie) and 0 in the opposite case (truth).7

For any given

x -k , if x k < x -k it turns out that ∂U k (x k )/∂x k = (1 + v); if x k > x -k we have ∂U k (x k )/∂x k = 1.
In both cases, the utility is an increasing function in a player's own gain.

Strategies

For sure, for any player k, the game is acceptable if and only if U k (x k ) ≥ 0 :

U k (x k ) ≥ 0 ⇔ x k ≥ vx -k + 1 lie C k 1 + v (2)
Notice that in our setup only the proposer can issue a wrong message. Since the responder is not subject to the lie/tell-the-truth choice, the participation constraint for the responder can be written as:

x k ≥ µ v 1 + v ¶ x -k .
Denoting by Y the total sum to be shared between the two players, with Y = x k + x -k , the responder's participation constraint can be interpreted as a fairness constraint: he will accept any offer x k providing him with a "fair share" of the pie:

x k ≥ ΦY, with Φ = µ v 1 + 2v ¶ ∈]0; 0.5[ and dΦ/dv > 0. (3)
Given that the responder does not know Y, his decision to accept or not the allocation will be based on his expected value of Y contingent upon the signal M issued by the proposer,

denoted by E[Y |M ].
For a given strategy (M, Z) played by the proposer, the responder's optimal "pie-sharing strategy" will be:

Responder pie-sharing strategy

⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ Accept the offer Z if: Z ≥ ΦE[Y |M ] Refuse the offer Z if: Z < ΦE[Y |M ] . (4)
A proposer who aims at maximizing an utility function such as defined in Eq. ( 1) will make the smallest offer Z that the responder accepts, to get the largest gain (Y -Z). The best "pie sharing" strategy for the proposer is thus to offer the lowest acceptable amount by the responder:

Proposer pie-sharing strategy:

Z = ΦE[Y |M ]. (5)
Given that E[Y |M ] ≤ Y and Φ < 0.5, it turns out that Z < (Y -Z) : the proposer is not subject to adverse inequality. The utility of a proposer utility who receives Y and plays his best pie-sharing is:

U (Y, Z, M) = Y -Z -c |Y -M | = Y -ΦE[Y |M ] -c |Y -M | . (6)
A proposer who aims to maximize his utility must decide on the message M that he sends to the responder, depending on his endowment Y and his type (honest or liar). A honest proposer will always declare the true amount (M = Y ) and a liar will declare a false amount

(M 6 = Y ).
We admit that the optimal false message can be written as a (lying) function in Y , denoted by g(Y ) :

Proposers' communication strategy:

⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ M = Y if proposer is H-type M = g(Y ) if proposer is L-type . ( 7
)
The lying function presents the following properties:

-g(0) = 0: if the endowment is zero, the message can be only zero (the proposer has no choice but to tell the truth);

-for Y > 0, g(Y ) < Y : since the message aims to push down the expected value of Y , and lies are costly, the proposer has no incentive to declare an endowment higher than the actual one;8 -g admits a reciprocal function g -1 on the interval [0, A].

Equilibrium

Let us denote by f (M |L) (respectively f (M |H)) the conditional distribution of the signal M given that the proposer is a liar (and respectively a honest person). By application of Bayes' theorem for continuous distribution functions, the probability for the responder to be matched with a L-type proposer who issues a message M is:

Pr[L|M ] = f (M |L) Pr[L] f (M |L) Pr[L] + f (M |H) Pr[H] . (8)
In equilibrium, the responder should know the lying function g(M ); he can infer from the message M the conditional expectation of Y. If M exceeds g(A), this signal can only be true (it was sent by a H-type proposer). In the opposite case, if M ≤ g(A), the expected value of

Y given M is : E[Y |M ] = Pr[L|M ]g -1 (M ) + {1 -Pr[L|M ]} M = f (M |L) Pr[L]g -1 (M ) + f (M |H) Pr[H]M f (M |L) Pr[L] + f (M |H) Pr[H] . ( 9
)
an expression that acknowledges that M can be sent either by a honest player (then

Y = M ),
or by a liar (then Y = g -1 (M )). Furthermore, in equilibrium a responder can infer from the message of a liar the true value of Y , hence in the former expression we can substitute

g -1 (M ) by Y . Moreover, as Y Ã U (0, A), it turns out that f (M |H) = 1/A and f (M |L) = ¯g-10 (M ) ¯/A.
As Pr[H] = α, we get the final expression for the expected Y given M :

E[Y |M ] = ¯g-10 (M ) ¯(1 -α) Y + αM |g -10 (M )| (1 -α) + α (10)
Thus the utility of the L-type proposer (Eq. 6) can be written as:

U (Y, Z, M) = Y -Φ ¯g-10 (M ) ¯(1 -α) Y + αM |g -10 (M )| (1 -α) + α -c(Y -M ). (11)
The optimal announcement strategy for a L-type proposer is to choose the message M that maximizes utility U (Y, Z, M).

This problem probably presents several equilibria, depending on responders' beliefs. In this paper we limit the analysis to the simplest (and also intuitively appealing) case where responders present linear beliefs:

Responders' beliefs: g(Y ) = µY, with µ ∈ [0, 1]. (12)
Then g -10 (M ) = 1/µ and proposer's utility becomes:

U (Y, Z, M) = Y -Φ Y µ (1 -α) + αM 1 µ (1 -α) + α -c(Y -M ) (13) = Y -Φ Y 2 M (1 -α) + αM Y M (1 -α) + α -c(Y -M ) (14) = Y -Φ (1 -α)Y + α M 2 Y (1 -α) + α M Y -c(Y -M ). (15)
The first order optimality condition:

∂U ∂M = -Φ £ (1 -α) + α M Y ¤ 2α M Y -α Y h (1 -α)Y + α M 2 Y i £ (1 -α) + α M Y ¤ 2 + c = 0. ( 16
)
leads to the optimal value, M .9

The latter is a linear function of the endowment Y , consistent with responders' beliefs:

M = 1 α ⎧ ⎨ ⎩ " (1 -α) ¡ 1 -c Φ ¢ # 1/2 -(1 -α) ⎫ ⎬ ⎭ Y. ( 17
)
Notice that, in equilibrium there is a single value of µ consistent with responders' beliefs, defined by:

µ = 1 α ( • Φ(1 -α) Φ -c ¸1/2 -(1 -α) ) . ( 18
)
This value exists iif c < Φ (existence condition). We can remark that µ = M/Y is increasing with c : the smaller the marginal lying cost and the higher the size of the lie.

Furthermore, the equilibrium requires: 0 < µ < 1 :

µ > 0 ⇐⇒ Φ Φ -c > (1 -α) is always true (19) µ < 1 ⇐⇒ c < αΦ (20)
If this last condition is verified, the existence condition (c < Φ) is also fulfilled; thus the necessary and sufficient condition for this equilibrium to exist is:

NSC : c < c = αΦ. (21)
The equilibrium with lies requires that the (1α) liars present a marginal cost of lying below the critical value c. Notice that the solution also holds in the special case where liars present no lying aversion (c = 0). Individuals with a marginal lying cost above c actually belong to the group of H-type proposers; such a person has no incentive to deviate from the truth-telling strategy, since the cost of lying would exceed its benefit from making a lower offer.

We recall that in this theoretical model agents differ only with respect to the (marginal) lying cost. We have shown that if there are at least some honest persons and for all the others lying costs are small enough (c < c), in equilibrium the latter will systematically understate Y, i.e. they declare M < Y. Responders adjust their beliefs in keeping with the message; in equilibrium they accept all offers. 10 Thus, compared with a no-lie (or a perfect information) environment, honest proposers who get Y < g(A) are worse-off since they must make higher offers, while liars are better-off, since they can make lower offers.

3 The Experiment

Experimental Design

In this section, we report on an experiment where we asked flesh and blood subjects to play an ultimatum game combined with a message game. The only difference with the theoretical model is that we set now a positive lower bound on the amount that can be provided by the computer. The main steps are listed below (see Appendix for instructions):

Step Step 3. He makes an offer Z (with Z ∈ [0; Y ]).

Step 4. Responder gets the message M and the offer Z. He must decide whether to accept or reject the offer. If he accepts, the amounts are due; if else, both players get nothing.

The whole procedure was common knowledge. We run three sessions. [START_REF] Fischbacher | z-Tree: Zurich toolbox for ready-made economic experiments[END_REF]. Each subject was assigned at random with a PC terminal.

We make sure that no subject has participated more than once in this experiment. A short introductory questionnaire allows to make sure that students understand well the problem.

The roles (proposer/responder) were assigned one for all at the outset of the game, but players were not informed of their role before each round started. Each proposer played the game four times against changing anonymous partners (Mitzkewitz and Nagel, 1993); we gathered a total of 148 observations (37 independent per round).

We randomly chose one of the four rounds to be paid for real money, at an exchange rate of 10 euro for 100 experimental currency units. 11 The test has lasted for 18 minutes on average, and players earned 4.80 euros (including a 2 euro fixed participation amount).12

Results: Proposer behavior

Lying by understating the actual endowment Y appears to be the systematic behavior.

Proposers adopted this strategy in 88.5% of the overall 148 decisions. They told the truth in 8.8% of the cases, and the number did not vary much from one round to another. Subjects overstated the actual endowment in a very small number of cases (2.7%); this strategy does not fit well in our theoretical framework. Some misunderstanding of the problem might explain them, an assumption that seems to be vindicated by the declining number over the four rounds (from to 2 to 0). (Standard deviation between brackets)

Table 3 presents three interesting ratios (in percent), taking into account only the strategic lies (i.e., messages that understate the actual endowment, M < Y ). The second line shows the average ratio between the claimed and the actual endowment: proposers tend to discount the actual endowment by 20.5%. 13 The third line is the average ratio between the offer and the actual endowment: on average offers represent 36% of the endowment, in line with other experiments surveyed by [START_REF] Oosterbeek | Cultural differences in ultimatum game experiments: Evidence from a meta-analysis[END_REF]. The fourth line shows that on average offers represent 45% of the claimed amount (Z/M ).

Round An examination of the data change from one round to another suggests that the learning effect is limited, if any. Except the decline in the almost very small number of "irrational lies" (Table 1), there is no clear trend in the absolute or relative data. More intuition about

Z it = c + θ t + aY it + bLIE it + u i + it ( 22
)
where i indexes the player, with i ∈ [1, 37], and t indexes the round, with t ∈ {1, 2, 3, 4}.

Parameter a captures the relationship between offers and endowment when controlling for the lie, the parameter b indicates the variation in the offer for a one-dollar lie. Denoting the common constant by c, the parameter θ t denotes a round-specific intercept and would capture any group learning effect over the rounds; to avoid colinearity, one round must be dropped (we choose the first one as the benchmark). The individual specific effect u i captures individual unobserved heterogeneity, and it is an indiosyncratic error. In a fixed effect (FE) specification u i are treated as constants over time, in a random effect (RE) model the u i are treated as random variables rather than fixed constants (furthermore, in the RE approach, u i and it are assumed to be independent). It is difficult to say which of the two methods fits best to our model; the RE specification is appealing since the individuals in our test are a small sample of a much larger population (of student subjects), the FE is interesting, since it is not clear why individual effects should be uncorrelated with the other regressors. We therefore provide in Table 4 an estimate of Eq. ( 22 (*** stands for significant at 1%, ** stands for significant at 5%, ns for non significant)

The two models (FE and RE) provide similar qualitative results. A Hausman test confirms that individual disturbance terms u i are uncorrelated with the regressors (Chi2(5)=3.18;

p-value = 0.6726), which recommends the RE method. 14The estimated coefficients indicate that, all things equal, for every additional dollar in endowment, proposers increase their offer by 33 cents; a one-dollar lie would contribute to reduce the offer by 19 cents.

These findings are consistent with the theoretical model, according to which L-type proposers (i.e., those characterized by a relatively small marginal lying cost) would declare a smaller than actual endowment, just in order to prompt responders to reduce the expected endowment (of proposers) and make lower offers. Our results also match those put forward by [START_REF] Croson | Cheap talk in bargaining experiments: Lying and threats in ultimatum games[END_REF] who showed that in presence of imperfect information and lies, for every additional dollar endowment, proposers raise their offer by 39 cents. They also report that a lie (as measured by a dummy variable) would reduce the offer by 1.5 dollars. 15Round specific effects are not statistically significant, suggesting that over a small number of repeated interactions the proposers' learning effect is limited.

Results: Responder behavior

Table 5 indicates the basic statistics pertaining to the responder's decision. On average, the rejection rate at 24% is slightly higher than usual, but not excessive [START_REF] Oosterbeek | Cultural differences in ultimatum game experiments: Evidence from a meta-analysis[END_REF] refer to a rejection rate of 16% on average).

Over the total of 148 observations, the average amount of the accepted offers (29.04) is higher than the average amount of the rejected offers (21.88). A Mann-Whitney U-test for independent observations shows that the difference between the average of accepted offers and the average of rejected offers is significant at 5% in rounds 1, 3 and 4 (it is not significant in round 2).

The same test shows that the average declared endowment (Av. M ) in rejected offers is not statistically different from the average declared endowment in accepted offers in any of the four rounds.

Round We also perform a regression of the decision dummy ARD (which takes the value 1 when the offer is accepted, 0 when rejected) on the offer Z and the declared endowment M :

ARD jt = c + θ t + qZ jt + rM jt + u j + jt ( 23
)
where the index j corresponds to a Responder, and t indexes the round. As in the former regression, θ t denotes the round specific effect (to avoid colinearity we omit the first round), u j captures the individual heterogeneity and jt is the idiosyncratic error. Given the binomial nature of ARD we implement a probit and logit model, both of them with a random effect (RE) specification. The output is presented in Like in the Proposer equation, round specific effects are not statistically significant. Results here too are consistent with findings by [START_REF] Croson | Cheap talk in bargaining experiments: Lying and threats in ultimatum games[END_REF]: while the offer Z has a statistically significant impact on the probability to accept an offer, the message M has not.

The estimate of the marginal effects shows that around the average offer, chances to have an offer accepted increase by 3 percentage points for one-dollar increase in the offer Z.

In order to bring some additional intuition to these results, let us perform some rule-ofthumb calculations. We know that on average a six dollar lie reduces proposers' offer by one dollar (Table 4), but this rises the probability of having the offer rejected by responders by 3 percentage points (Table 5). We consider now a L-type proposer with a zero marginal cost of lying. Let us assume that he gets 75 dollars (the expected value of the uniform distribution over [50,100]), tells the truth and makes an offer Z = 0.33 * 75 = 25.17 Given the average rejection rate, his expected payoff is (75 -25) * 0.76 = 38. Now, if he tells a six dollar lie, he will reduce his offer by one dollar, from 25 to 24 dollars. For sure, if the probability of having the offer accepted does not vary, he would make a profit. But since for a smaller offer the probability to have it accepted declines by 3 percentage points, the expected gain will be (75 -24) * 0.73 = 37.23. It turns out that in the neiborghood of these average values, a onedollar lie brings about an ex post dollar loss to the "unethical" proposer (without counting any would-be lying cost on top of it). These numbers suggest that in this game proposers are subject to a form of overconfidence bias: they tend to believe that responders will take for granted their message, but this does not happen.

Conclusion

In this paper, we studied an ultimatum game with uninformed responders and proposers who can communicate strategically about their endowment, knowing that the responders will not be able to verify their claim. The theoretical analysis presented in the first section suggests that while there are at least some honest people in this world, it is worth lying for the others.

More precisely, proposers willing to lie can be expected to understate the actual endowment and make lower offers.

The empirical findings corroborate the predictions of the theoretical model as far as the proposers are concerned. In 88.5% of the messages, proposers discount their endowment by 20.5% on average. These lies are systematically associated with lower offers; for every one-dollar lie, proposers reduce their offer by 19 cents. However, the experiment challenges the theoretical analysis as far as responders' are concerned since they do not react as the proposers expect: the endowments declared by proposers have little impact on their decision whether to accept/reject the offer. They behave as if the received message is genuine "cheap talk". Only the amount of the offer itself matters in their decision whether to accept/reject it: a one-dollar reduction in the offer reduces the acceptance rate by 3 percentage points.

If proposers reduce their offers because they "believe in their own lies", but responders are skeptical, the final outcome is a net welfare loss, since the frequency of rejected offers (bringing zero gains for both players) will be higher than in a lie-free environment. In this simple experiment, attempts to manipulate through lying are detrimental not only to those who receive the wrong message, but also to those who deliver it. Despite this, the people in a position to÷ lie do lie; they are probably victims of a self-confidence bias concerning their ability to cheat.

It is difficult to extend the insights from this simple game to any other form of selfish lies. However, if further research can show that lying systematically brings about a socially inefficient outcome, then the emergence of a social norm banning lying would appear as a natural outcome.

5 Annex. Instructions Screen 1. General information Good Morning, Thank you for participating to this study.

It presents an interaction between two individuals on how to share a sum of money, denominated in ECU (for Experimental Currency Units) Individuals play in pairs, under complete anonymicity, behind the computer screen. Pairs are rematched at every round. You never play twice with the same player. Identities of the persons will never be revealed.

At the beginning of the game, one of the two players gets an endowment. He must then make an offer to the other on how to divide this amount between them. For instance, if he receives 100 ecus, he can make an offer 10, that is a division 90:10. Then the other player can either accept this offer or reject it. If accepted, the first player who made the offer keeps the 90 ecus and the second player who accepted the offer keeps the 10 ecus; if rejected, both players get nothing. Thus by giving up his own gain, the second player can inflict a loss to the former.

In this game, the player who receive the offer (Player 2), will never learn the exact amount received by the first player (Player1). He only knows that the amount is chosen by the computer, with equal chances, among the integers in the set [50,100].

Before making his offer, Player 1 must sent a message to Player 2, indicating the amount he got at that round. Player 2 cannot verify this information (and Player 1 knows this).

Screen 2. Some clarification questions

These questions aim at helping you to better understand the rule of the game, by means of some fictitious examples. Step 1. Player 1 offers to Player 2 an amount Z between 0 and Y . He also sends a message to Player 2, where he makes a statement about his endowment Y .

Step 3. Player 2 learns the offer Z and the message about Y , and decides whether to accept/reject this offer. If he accepts, he gets Z and Player 1 gets Y -Z, if he rejects this offer, both players get nothing. Player 2 will not be able to verify the information about the actual amount received by Player 1.

You will play this game four times in a row. One round chosen at random will be remunerated in cash, at the exchange rate 100 ECU = 10 euros.

Screen 4a. The decision

  1. Proposer gets Y experimental currency units. The endowment Y is picked by the computer with even chances among integers in the interval [50; 100]. Step 2. He sends a message M to the responder, informing him about the amount Y, with M ∈ [50; 100]. If M = Y, he tells the truth, if M 6 = Y, he lies.

Figure 1 :Figure 2 :

 12 Figure 1: Actual and declared endowment

1.

  You are the person who receives the offer (your are therefore Player 2). Assuming that you know that Player 1 got 100 ecus, if he offer you 25 ecu (75:25), would you accept this offer ? (Yes/No) Assuming that you know that Player 1 got 50 ecus, if he offer you 25 ecu (25:25), would you accept this offer ? (Yes/No) 2. You are the person who makes the offer (you are therefore Player 1) Assuming that you receive 90 ecus, but Player 2 only knows that you get a sum in the interval [50, 100], -What amount would you claim to have obtained ? [...] -How much money would you offer him ? [...] Screen 3. The rule of the gameStep 0: At the beginning of the game, Player 1 receives an amount Y draw at random by the computer in the interval[50, 100]. Every integer has equal chances to be chosen. Player 2 will never learn this amount, but knows that it is draw from the interval [50, 100] with equal chances.

Table 1

 1

	indicates the distribution of messages per round,

Table 1 .

 1 The distribution of proposer messages

11

See

[START_REF] Laury | Pay one of pay all. Random selection of one choice for payment[END_REF]

for the validity of this approach.

Table 2

 2 indicates the average endowment (Y ), the average declared endowment (M ) and the average offer (Z) per round and over the four rounds.

		Round 1	Round 2	Round 3	Round 4	All rounds
	Av. Y	74.70 (14.19) 78.30 (12.53) 71.84 (14.08) 74.19 (16.19) 74.76 (14.35)
	Av. M 60.16 (9.37)	61.78 (9.59)	59.59 (11.76) 60.00 (10.57) 60.39 (10.29)
	Av. Z 26.68 (7.38)	28.68 (6.64)	26.11 (9.48)	27.91 (7.45)	27.34 (7.79)

Table 2 .

 2 Average actual and declared endowment, average offer.

Table 4 .

 4 ) using both methods. Proposer offer equation: Estimation output.

		FE	RE
	Y	0.317*** 0.334***
	LIE	-0.140** -0.188***
	c	5.029 ns	4.407 ns
	θ 2	1.137 ns	1.168 ns
	θ 3	0.017 ns	0.041 ns
	θ 4	1.356 ns	1.348 ns
	Nb. obs	148	148
	R 2 -overall	0.22	0.22
	σ u	4.91	3.84
	ρ	0.42	0.31
	Proba all u i = 0 0.00	-

Table 5 .

 5 Basic statistics for the responder decision

			1 Round 2 Round 3 Round 4 All rounds
	Acceptance rate	0.84	0.76	0.70	0.76	0.76
	Av. Z, accepted offers	28.32	29.61	28.96	29.32	29.04
	Av. Z, rejected offers	18.17	25.78	19.36	23.56	21.88
	Av. M , accepted offers	60.48	62.39	59.54	61.18	60.91
	Av. M , rejected offers	58.50	59.89	59.73	56.33	58.69
	Av. Z/Y , accepted offers 0.47	0.48	0.49	0.48	0.48
	Av. Z/Y , rejected offers 0.31	0.43	0.35	0.41	0.38

Table 6

 6

	, where, for each method, a

Pioneering studies in the analysis of strategic information manipulation were submitted by[START_REF] Crawford | Strategic information transmission[END_REF] and[START_REF] Sobel | A theory of credibility[END_REF]. In these papers agents can send misleading messages without a direct cost, i.e. they can undertake "cheap talk". In equilibrium, the messages do no alter the action of the receiver.

See also the companion paper[START_REF] Boles | Deception and retribution in repeated ultimatum bargaining[END_REF].

This is the only differentiating characteristic of individuals in this model.

The threshold c separating a honest person from a liar is engodeneous; we will determine it latter on.

This linear form was introduced by[START_REF] Fehr | A theory of fairness, competition, and cooperation[END_REF].

A quick look to the Bayesian revision of expectations (Eq. 10) shows that an overestimated message (M > Y ) pushes up the expected income, thus rises the value of the minimum acceptable offer.

Wa can check that ∂ 2 U/∂M 2 < 0, ∀M.

In real interactions, responders might have a different aversion to inequality, unknown to the proposer. If the latter makes his offer according to his expected aversion to inequality of responders, then some offers can be rejected.

Total compensation was higher, since they participated in two other experiments of a different nature.

If we consider all the messages (including true ones and overstatements), the average discount is 17.64%.

The Breusch-Pagan Lagrange multiplier test suggests that the RE specification is to be preferred to a simple OLS regression.

In a companion paper[START_REF] Besancenot | The value of lies in a power-to-take game with imperfect information[END_REF], we study a power-to-take (or demand ultimatum) game coupled with a similar message game and found that the message senders (responders in that game) also lie strategically: when they lie, they make less advantageous offers.

A FE logit model provides similar qualitative results.

Here 0.33 is the average share offered by a honest person according to the estimated offer equation (Table4).

Your gain for this round is [Y-Z]/0.


Matthieu Calvez
email: matthieu.calvez@univ-rennes1.fr

IRMAR Bert Wiest
email: bertold.wiest@univ-rennes1.fr

A FAST SOLUTION TO THE CONJUGACY PROBLEM IN THE 4-STRAND BRAID GROUP

We present an algorithm for solving the conjugacy search problem in the four strand braid group. The computational complexity is cubic with respect to the braid length.

Introduction

The conjugacy problem is one of the three famous decision problems in groups first formulated by Dehn in the early 20th century. The aim is to decide whether two given elements x and y of a group G are conjugate in G, i.e. if there exists an element z in G such that x = z -1 yz (which we shall denote x = y z ). If so, then an additional problem is to actually search for such a conjugating element z. These two problems are called CDP (conjugacy decision problem) and CSP (conjugacy search problem).

We know since Garside [START_REF] Garside | The braid groups and other groups[END_REF] that CDP and CSP are solvable for the braid groups B n , meaning that there exists an algorithm for solving these two problems in B n , n 1. In fact, the properties of braid groups discovered in [START_REF] Garside | The braid groups and other groups[END_REF] are now known to hold for a large class of groups, called Garside groups [START_REF] Dehornoy | Groupes de Garside[END_REF]; this class of groups contains for instance all Artin-Tits groups of spherical type [START_REF] Brieskorn | Artin-Gruppen und Coxeter-Gruppen[END_REF].

A Garside group of finite type G is equipped with a partial order relation , called the prefix order, which is invariant under left multiplication and which induces on G a lattice structure (i.e. every pair of elements has a largest common divisor and a least common multiple). Moreover, the positive cone of this relation

P = {x ∈ G | 1
x} contains a special element ∆, called the Garside element, with the following properties: firstly, conjugation by ∆ stabilizes P , and secondly, the set of positive divisors of ∆ with respect to (also called the set of simple elements) is finite and generates G. An important property of Garside groups is the existence of a left normal form [START_REF] Dehornoy | Groupes de Garside[END_REF]. This means that for any element x of the group there exists a unique decomposition of the form x = ∆ p x 1 . . . x r , where p ∈ Z, r ∈ N, and the factors x i are simple elements. In this factorization, the quantity ℓ(x) = r is called the canonical length of x.

The braid groups admit in fact two distinct Garside structures (i.e. two distinct pairs ( , ∆)). We shall use both structures. On the one hand, the classical Garside structure, stemming from Garside's original article [START_REF] Garside | The braid groups and other groups[END_REF]: for x, y ∈ B n , x y if and only if x -1 y can be written as a product of Artin generators σ i , all with positive powers; the Garside element is ∆ = (σ 1 . . . σ n-1 ) . . . (σ 1 σ 2 )σ 1 . On the other hand, the dual (or BKL) structure, introduced by Birman, Ko and Lee in [START_REF] Birman | A new approach to the word and conjugacy problems in the braid groups[END_REF], which we shall describe in detail in Section 2.

Since Garside, several more and more powerful algorithms for solving CDP and CSP have been proposed [START_REF] Elrifai | Algorithms for positive braids[END_REF][START_REF] Gebhardt | A new approach to the conjugacy problem in Garside groups[END_REF][START_REF] Gebhardt | The cyclic sliding operation in Garside groups[END_REF]. We briefly recall that each of the algorithms [START_REF] Elrifai | Algorithms for positive braids[END_REF][START_REF] Gebhardt | A new approach to the conjugacy problem in Garside groups[END_REF][START_REF] Gebhardt | The cyclic sliding operation in Garside groups[END_REF] for solving CDP and CSP in a Garside group G is based on the calculation, for any given x ∈ G, of a finite non-empty subset E x of the conjugacy class of x, satisfying E x = E y if and only if x and y are conjugate. The Super Summit Sets (SSS) [START_REF] Elrifai | Algorithms for positive braids[END_REF], the Ultra Summit Sets (U SS) [START_REF] Gebhardt | A new approach to the conjugacy problem in Garside groups[END_REF] and the sets of sliding circuits (SC) [START_REF] Gebhardt | The cyclic sliding operation in Garside groups[END_REF] are three examples of such characteristic subsets. Unfortunately, despite the very high speed (in practice) of the most recent algorithms, the existence of a polynomial bound on the algorithmic complexity (with respect to the length of the input) is still an open problem, even in the case of the braid groups.

The main result of the current article is the following theorem: Theorem 1.1. There exists an algorithm which solves CDP and CSP in the braid group B 4 and whose algorithmic complexity is cubic with respect to the length of the input braid words.

We are not able to prove Theorem 1.1 using only the tools of Garside theory. We shall also use a geometric point of view on braids. It is known (see e.g. [START_REF] Birman | Braids, Links and Mapping Class Groups[END_REF]) that the braid group B n (n 1) can be identified with the mapping class group of the ntimes punctured disk D n . In this context, braids can be classified according to their dynamical properties, in the following trichotomy (Nielsen-Thurston classification) [START_REF] Casson | Automorphisms of surfaces after Nielsen and Thurston[END_REF][START_REF] Fathi | Travaux de Thurston sur les surfaces[END_REF]: a braid x is

• periodic, if there exists an integer m such that x m ∈ ZB n = ∆ 2 ,
• reducible, if there exists a non-empty family F (called the canonical reduction system) of isotopy classes of nondegenerate disjoint simple closed curves in D n (non-degenerate means not null-homotopic, not homotopic into a puncture and not boundary-parallel) such that the x-action leaves F invariant, -F does not intersect any other isotopy class of simple closed curve in D n which is invariant under some power of x • pseudo-Anosov (pA) otherwise.

We remark that the definition of "reducible" most frequently found in the literature also encompasses certain periodic elements. In this paper we only apply the word "reducible" to the braids which would usually be called "reducible non-periodic".

The paper [START_REF] Birman | Conjugacy in Garside Groups I: Cycling, Powers and Rigidity[END_REF] proposes a program, based both on the Nielsen-Thurston classification and on Garside theory, for solving CDP and CSP in the braid groups in polynomial time with respect to both the length of the input braid words and their number of strands. A first step in this program is the construction of a polynomial time algorithm for deciding the dynamical type of any given braid (Open question 1 in [START_REF] Birman | Conjugacy in Garside Groups I: Cycling, Powers and Rigidity[END_REF]).

In [START_REF] Calvez | Fast algorithmic Nielsen-Thurston classification of four-strand braids[END_REF], the authors answered this question in the case of the group B 4 : they produced an algorithm of complexity O(ℓ 2 ) to decide the Nielsen-Thurston type of any given 4-strand braid of length ℓ. Thus in the group B 4 , in order to solve CDP and CSP it is sufficient to solve these problems for pairs of elements which are known to be of the same dynamical type (as pairs of braids of different dynamical type are never conjugate).

The algorithm given in [START_REF] Calvez | Fast algorithmic Nielsen-Thurston classification of four-strand braids[END_REF] also implies a solution to CDP and CSP for reducible four-strand braids of length at most ℓ in time O(ℓ 2 ). The main lemma here is that for braids with at most 3 strands and of length at most ℓ, the problems CDP and CSP are solvable in time O(ℓ 2 ), see [START_REF] Calvez | Fast algorithmic Nielsen-Thurston classification of four-strand braids[END_REF].

The case of periodic braids is treated in [START_REF] Birman | Conjugacy in Garside groups III: Periodic braids[END_REF], where an algorithm of complexity O(ℓ 3 n 2 log n) for solving CDP and CSP for periodic braids with n strands of canonical length at most ℓ is presented.

In order to prove Theorem 1.1, we thus have to produce an algorithm of complexity at most O(ℓ 3 ) capable of solving CDP and CSP for pseudo-Anosov four-strand braids of length at most ℓ. Technically, our main contribution is the following result, which gives a partial affirmative answer (in the special case of pseudo-Anosov 4-strand braids) to the Open Question 2 in [START_REF] Birman | Conjugacy in Garside Groups I: Cycling, Powers and Rigidity[END_REF]: using the vocabulary of [START_REF] Gebhardt | The cyclic sliding operation in Garside groups[END_REF], if a 4strand pseudo-Anosov braid is rigid (meaning, roughly speaking, that the normal form is as simple as possible), then its set of sliding circuits (and also its Ultra Summit Set) is "small": Theorem 1.2. For every braid x in B 4 which is pseudo-Anosov and rigid with respect to the dual Garside structure, the cardinality of SC(x) for the dual structure is bounded above by O(ℓ(x) 2 ). This result implies that the algorithm given in [START_REF] Gebhardt | Solving the conjugacy problem in Garside groups by cyclic sliding[END_REF] for solving CDP and CSP has complexity O(ℓ 3 ) when applied to two 4-strand braids which are of length at most ℓ, pseudo-Anosov and rigid in the dual structure.

The rest of the proof of Theorem 1.1 thus has to consist of a reduction to the rigid case. A key result in this direction is Theorem 3.37 in [START_REF] Birman | Conjugacy in Garside Groups I: Cycling, Powers and Rigidity[END_REF], which states that for any braid x (with arbitrarily many strands) there exists a strictly positive integer m such that x m is conjugate to a rigid braid. Moreover, for any fixed number of strands, this integer m is bounded by a constant which does not depend on x (see Theorem 4.1). The next step in the reduction to the rigid case is provided by the result from [START_REF] González-Meneses | The nth root of a braid is unique up to conjugacy[END_REF] that for any m ∈ N, any pseudo-Anosov braid has at most one mth root. Therefore, for any two pseudo-Anosov braids x, y ∈ B n , for any positive integer m, and for any braid z ∈ B n , the relations x = y z and x m = (y m ) z are equivalent. Thus the only remaining problem is the following: for any pair x, y of pseudo-Anosov braids we have to produce (in polynomial time) a suitable power s and rigid conjugates x of x s and ȳ of y s (together with conjugating elements).

The existence of a polynomial time algorithm which, for any given pseudo-Anosov braid, constructs a rigid conjugate (if one exists), together with a conjugating element, is proved in [START_REF] Calvez | Fast Nielsen-Thurston classification of braids[END_REF] (see Proposition 4.2 below). This algorithm is based on the linear conjugator bound for pseudo-Anosov elements in mapping class groups due to Masur and Minsky [START_REF] Masur | Geometry of the complex of curves. II. Hierarchical structure[END_REF]. We deduce the following algorithm: Theorem 1.3. There is an algorithm with the following propoerties:

• as input, it takes two pseudo-Anosov braids x, y ∈ B n of canonical length at most ℓ, • as output, it yields an integer s and n-strand braids x, ȳ, z 1 and z 2 such that x and ȳ are rigid and satisfy x = (x s ) z1 and ȳ = (y s ) z2 , • for any fixed n, the complexity is O(ℓ 2 ).

We can now describe the algorithm promised by Theorem 1.1:

ALGORITHM:

INPUT: x and y two elements of the four-strand braid group. OUTPUT: whether or not x and y are conjugate, and if they are, an element z ∈ B 4 so that x = y z .

(1) Determine the dynamical types of x and y, using [START_REF] Calvez | Fast algorithmic Nielsen-Thurston classification of four-strand braids[END_REF]. If they are not the same, answer "x and y are not conjugate" and STOP. (2) If x and y are periodic use [START_REF] Birman | Conjugacy in Garside groups III: Periodic braids[END_REF] and STOP.

(3) If x and y are reducible, use [START_REF] Calvez | Fast algorithmic Nielsen-Thurston classification of four-strand braids[END_REF] and STOP. (4) If x and y are pseudo-Anosov, use the algorithm of Theorem 1.3 in order to produce s, x, ȳ, z 1 , z 2 with the required properties. (5) Apply Algorithm 3 of [START_REF] Gebhardt | Solving the conjugacy problem in Garside groups by cyclic sliding[END_REF] to x and ȳ. If x and ȳ are conjugate, then this algorithm produces c ∈ B 4 such that x = ȳc . In this case answer "x is conjugate to y by z 2 cz -1 1 ." and STOP. (6) Answer "x and y are not conjugate". This paper is organized as follows. In Section 2 we recall some prerequisites from Garside theory. In Section 3 we prove Theorem 1.2 bounding the size of the sets of sliding circuits. In Section 4 we prove Theorem 1.3 and finally Theorem 1.1.

Acknowledgements. The authors are grateful to Juan González-Meneses for suggesting a simplification in the proof of Theorem 1.2. The first-named author was partially supported by a grant from Région Bretagne, by MTM2010-19355 and FEDER.

Prerequisites from Garside theory

In this section we first recall some general facts which apply to all Garside groups. Then we turn our attention to rigid elements and describe in detail the structure of the sets of sliding circuits in this particular case. Finally, we recall briefly the dual Garside structure on the 4-strand braid group. Note that none of the results in this section are new; however, we shall introduce in the second and third part some non-standard notation which will be useful for the rest of the paper.

2.1. Reminders on Garside theory. Throughout this subsection, G denotes a Garside group. Its partial order relation is denoted , and the associated positive cone is P . The order is a lattice: the greatest common divisor of two elements x, y of G is denoted x ∧ y. The set of divisors of the Garside element ∆ which lie in P is finite and generates G; its elements are called the simple elements. We denote τ the interior automorphism associated to ∆; it preserves P and the relation . In particular, the automorphism τ induces a permutation of the (finite) set of simple elements, and since these elements generate G, the interior automorphism τ is of finite order.

We also recall that every simple element s possesses a right complement ∂(s) defined by the formula ∂(s) = s -1 ∆. This notion allows us to define: Definition 2.1. Let s 1 and s 2 be two simple elements of G. We say the pair

s 1 s 2 is left-weighted if ∂(s 1 ) ∧ s 2 = 1, in other words if s 1 is the greatest simple divisor of s 1 s 2 .
Proposition 2.2. [START_REF] Dehornoy | Groupes de Garside[END_REF][START_REF] Elrifai | Algorithms for positive braids[END_REF] Let x ∈ G. There exists a unique decomposition x = ∆ p x 1 . . . x r , where r is a non-negative integer, p is the greatest integer satisfying ∆ p x, the x i are simple elements with x r = 1, and (if r 2) the pair x i x i+1 is left-weighted for i = 1, . . . , r -1.

In the previous proposition, the decomposition x = ∆ p x 1 . . . x r is called the (left) normal form of x; the integers p and r are called the infimum and the canonical length of x, and they are denoted inf(x) and ℓ(x). The supremum sup(x) is the quantity p + r. For every element x of G, sup(x) = min{k ∈ Z, x ∆ k }. We observe that the elements of canonical length zero are precisely the powers of ∆; these elements are as simple as possible within their conjugacy class.

Remark 2.3. The set of simple elements, taken as a generating set of G, induces a length function on G: the length |x| of an element x of G is by definition the smallest possible length of a word representing x whose letters are simple elements or their inverses. We note that always ℓ(x)

|x|. We also have the following relations, for any x satisfying inf(x) = p and ℓ(x) = r [START_REF] Dehornoy | Groupes de Garside[END_REF][START_REF] Charney | The language of geodesics for Garside groups[END_REF]:

|x| =      p + r if p 0, r if p < 0 and |p| r, |p| if p < 0 and |p| > r.
Definition 2.4. Let x ∈ G, and let x = ∆ p x 1 . . . x r be the normal form of x. Suppose r 1. We call

• initial factor of x the simple element ι(x) = τ -p (x 1 ), • final factor of x the simple element ϕ(x) = x r .
We recall that G is equipped with different operations which are defined in terms of normal forms, each corresponding to a particular conjugation.

Definition 2.5. [15] Let x ∈ G with normal form x = ∆ p x 1 . . . x r . Suppose r 1.
We define:

• the cycling c(x) = x ι(x) = ∆ p x 2 . . . x r τ -p (x 1 ), • the decycling d(x) = x ϕ(x) -1 = ∆ p τ p (x r )x 1 . . . x r-1 . If ℓ(x) = 0, we also define c(x) = d(x) = x.
Note that cycling and decycling commute with the automorphism τ . These two operations make it possible to "simplify" elements of G within their conjugacy class:

Proposition 2.6. [15] Let x ∈ G.
(i) The subset of the conjugacy class of x consisiting of all elements with minimal canonical length is finite and non-empty. Its elements have simultaneously maximal infimum and minimal supremum. This subset is called the Super Summit Set of x, and denoted SSS(x). (ii) There exist k 0 , l 0 ∈ N such that for every k k 0 and l l 0 , c k (d l (x)) ∈ SSS(x).

More recently, Gebhardt and González-Meneses introduced a new type of conjugation which combines cycling and decycling into a single, conceptually simpler, operation:

Definition 2.7. [19] Let x ∈ G with normal form x = ∆ p x 1 . . . x r . Suppose r 1.
We define the preferred prefix of x by the formula p(x) = ι(x) ∧ ∂(ϕ(x)). Cyclic sliding is the operation s defined by

s(x) = x p(x) . If ℓ(x) = 0 then we also define s(x) = x.
Now the analogue of Proposition 2.6 (ii), also proved in [START_REF] Gebhardt | The cyclic sliding operation in Garside groups[END_REF], states that for every x ∈ G, there exists an integer k 0 such that s k (x) ∈ SSS(x) whenever k k 0 . Moreover, the observation that s preserves SSS(x) implies that the set of periodic points of s in the conjugacy class of x is a (finite) nonempty subset of SSS(x); this is another conjugacy invariant: Definition 2.8. Let x ∈ G. The set of sliding circuits of x is the set of all conjugates of x which are periodic points of the cyclic sliding operation. That is,

SC(x) = {y ∈ x G | ∃k ∈ N, s k (y) = y}.
An important example of fixed points of s are the so-called rigid elements: Definition 2.9. Let x ∈ G with normal form x = ∆ p x 1 . . . x r . Suppose r 1. We say x is rigid if the pair ϕ(x)ι(x) is left-weighted.

In particular, an element of canonical length 0 is not rigid.

One very useful quality of the Super Summit Set is that it can quickly be reached by iterated cyclic sliding: Theorem 2.10. [START_REF] Birman | The Infimum, Supremum and Geodesic Length of a Braid Conjugacy Class[END_REF][START_REF] Gebhardt | The cyclic sliding operation in Garside groups[END_REF] Let G be a Garside group. Then there exists a constant α, which depends only on the group G and its Garside structure, such that for every x ∈ G, s ℓ(x)•α (x) ∈ SSS(x).

For instance in the case of the classical Garside structure on B n we have α = n(n-1)

2

, and α = n -1 for the dual structure. This result has a very important algorithmic application: it yields an algorithm of complexity O(ℓ 2 ) for calculating an element y ∈ SSS(x) for any given x ∈ B n in normal form of canonical length ℓ(x) = ℓ. The algorithm can even output an explicit conjugating element between x and y.

For the rest of the paper, we shall mostly be dealing with braids which lie in their own Super Summit Set (because pushing braids into their own SSS only costs O(ℓ 2 ), as we have just seen).

In order to prove Theorem 1.2, we need to study the structure of the set of rigid conjugates of any element x ∈ G. This is the object of the next subsection.

2.2. Ultra Summit Sets and rigid elements. Our aim in this subsection is to describe the structure of the set of all rigid conjugates of an element of a Garside group. We use the same notation as in the previous subsection. Our study is based mainly on the following proposition from [START_REF] Gebhardt | The cyclic sliding operation in Garside groups[END_REF]: Proposition 2.11. [START_REF] Gebhardt | The cyclic sliding operation in Garside groups[END_REF] Let x ∈ G. Suppose that x has a rigid conjugate. Then SC(x) is precisely the set of all rigid conjugates of x.

The following results are also proven in [START_REF] Gebhardt | The cyclic sliding operation in Garside groups[END_REF] (independently of the existence of a rigid conjugate): Definition 2.12. [START_REF] Gebhardt | The cyclic sliding operation in Garside groups[END_REF] Let x ∈ G and y ∈ SC(x). A simple, non-trivial element s of G is said to be a minimal arrow for y if y s ∈ SC(x) and if the only positive prefixes t of s with y t ∈ SC(x) are t = 1 and t = s. (i) The set SC(x) is stable under conjugation by ∆, by cycling, and by decycling. (ii) (See also [START_REF] Birman | Conjugacy in Garside Groups II: Structure of the ultra summit set[END_REF]). For every y ∈ SC(x), the minimal arrows for y are prefixes of ι(y) or of ∂(ϕ(y)).

Definition 2.14. [START_REF] Gebhardt | The cyclic sliding operation in Garside groups[END_REF] To every element x of G we associate a connected, oriented graph SCG(x) describing the set SC(x) as follows:

• the graph has one vertex for every element of SC(x),

• for every element y of SC(x) and every minimal arrow s for y, the graph SCG(x) has an oriented edge from the vertex y to the vertex y s . This edge is labelled s.

When x has a rigid conjugate, the graph SCG(x) has a particularly elegant structure, which we describe now. For the rest of this subsection we shall always suppose that x is rigid.

Definition 2.15. Let x ∈ G be a rigid element, and let y ∈ SC(x). The orbit of y is the set

O y = {τ k c l (y) | k, l ∈ N}.
Lemma 2.16. Let x ∈ G be a rigid element, and let y ∈ SC(x). Denote p = inf(x) and r = ℓ(x).

(i) The orbit O y is a subset of SC(x).

(ii) The orbit O y is stable under cycling, decycling, and τ ; in particular, for every

z ∈ O y , z ι(z) and z ∂(ϕ(z)) are element of O y . (iii) Let y 1 , y 2 ∈ SC(x). Then O y1 = O y2 if and only if O y1 ∩ O y2 = ∅. (iv) The cardinality of the orbit O y is bounded above by f • ℓ(y), where f is the order of τ ).
The results of Lemma 2.16 are well-known to the experts. For the sake of completeness, we nevertheless give a proof.

Proof. (i) This is a consecquence of Proposition 2.13 (i).

(ii) The stability of O y under cycling and conjugation by ∆ follows immediately from the definition (since c and τ commute). Let us now prove that d(z) ∈ O y whenever z ∈ O y . Let ∆ p z 1 . . . z r be the normal form of z. Then d(z) = ∆ p τ p (z r )z 1 . . . z r-1 , and this expression is in normal form since z was rigid. Moreover, we observe that d(z) = τ p (c r-1 (z)) (still due to the rigidity), and this last element belongs to O y by definition. For the second part of the statement, we only need to recall that z ι(z) = c(z) and that z ∂(ϕ(z)) = τ (d(z)).

Remark. Let f be the order of the automorphism τ . For any m ∈ N and any z ∈ SC(x) we now observe that c rm (z) = τ -pm (z), and in particular Then due to the above remark we have

c rf m (z) = z.
c rf j-l (τ k(f -1) (z)) = y so y ∈ O z .
Finally by (ii), O y ⊂ O z , as desired.

(iv) We consider the r first successive cyclings of the f elements y, τ (y), . . . , τ f -1 (y). This yields at most rf elements of O y . We claim that it yields all elements of O y . Indeed, let z = τ k (c l (y)). Let m ∈ N be such that rm l < r(m + 1). Then lrm ∈ [0, . . . , r -1], and

z = τ k (c rm (c l-rm (y))) = τ k-pm (c l-rm (y))
where the second equality follows from the above remark. Thus z occurs as one of the first r cyclings of one of y, τ (y), . . . , τ f -1 (y).

We have proven that the relation ∼, defined by x ∼ y if and only if O x = O y , is an equivalence relation on SC(x), and SC(x) is the disjoint union of the different orbits O y . We denote SC(x) the quotient set SC(x)/∼. We now associate a "quotient graph" SCG(x) to SC(x) in the same way as SCG(x) is associated to SC(x). In order to do this rigorously, we need the following definition: Definition 2.17. Let y ∈ SC(x) be rigid, and let s be a minimal arrow for y. We say s is a minimal useful arrow if y s / ∈ O y .

Remark 2.18. According to Proposition 2.13 (ii) and Lemma 2.16 (ii), the minimal useful arrows for y are strict prefixes of ι(y) or of ∂(ϕ(y)).

We recall the notion, due to Gebhardt [START_REF] Gebhardt | A new approach to the conjugacy problem in Garside groups[END_REF], of the transport under cycling of an arrow: if y, s ∈ G, we define the transport under cycling of s at y by the formula s

y = ι(y) -1 sι(y s ). It is known ( [START_REF] Gebhardt | A new approach to the conjugacy problem in Garside groups[END_REF], Corollary 2.7) that the transport induces a bijection between the set of minimal arrows for y ∈ SC(x) and the set of minimal arrows for c(y). Similarly, conjugation by ∆ induces a bijection between the minimal arrows for y and the minimal arrows for τ (y). In particular, if s is a minimal useful arrow between y and y s , then s

(1) y is a minimal useful arrow between c(y) and c(y s ), and τ (s) is a minimal useful arrow between τ (y) and τ (y s ). Thus we can define the desired quotient graph without any ambiguity (i.e. the arbitrary choices made in the following definition do not matter): Definition 2.19. To every rigid element x of G we associate a connected, oriented graph SCG(x) as follows:

• The vertices of the graph correspond to elements of SC(x),

• For every element O y ∈ SC(x), we arbitrarily choose a representative y ′ of O y . Now to any minimal useful arrow s for y ′ , from y ′ ∈ O y to z ′ ∈ O z , we associate an edge of the graph, oriented from O y to O z .

In order to bound the size of SC(x), it suffices to bound the number of vertices of SCG(x): if SCG(x) has k vertices, then the cardinality of SC(x) is at most

k • f • ℓ(x) (due to Lemma 2.16 (iv)).
2.3. The dual structure of B 4 . A detailed account of the dual Garside structure on braid groups can be found in the original article [START_REF] Birman | A new approach to the word and conjugacy problems in the braid groups[END_REF], and an introduction in Chapter VIII of [START_REF] Dehornoy | Ordering Braids[END_REF]. We restrict ourselves here to a brief description of this structure in the case of the four-strand braid group B 4 . We consider the sub-monoid BKL + 4 of B 4 generated by the braids a p,q , 1 p < q 4, where a p,p+1 = σ p for p = 1, . . . , 3,

a 1,3 = σ -1 2 σ 1 σ 2 , a 2,4 = σ -1 3 σ 2 σ 3 , a 1,4 = σ -1 3 σ -1 2 σ 1 σ 2 σ 3 .
The notation BKL is derived from the names of the discoverers of this structure: Birman, Ko and Lee. The monoid BKL + 4 induces a partial order relation on B 4 : x y if and only if x -1 y ∈ BKL + 4 . Taking as Garside element the braid δ = σ 1 σ 2 σ 3 , these data give rise to a new Garside structure, which we denote BKL 4 . For instance, we shall write x ∈ BKL 4 in order to say that x is a four-strand braid seen in the structure BKL 4 , and given as a product of the generators a i,j .

We now introduce some notation concerning the BKL 4 -structure which we shall be using for the rest of the article. We recall that B 4 can be seen as the mapping class group of the four times punctured disk D 4 . In the context of the BKL 4 -structure it is practical to parametrize D 4 as the unit disk in C with punctures P j = 1 2 e -i(2j-1)π 4 , for j = 1, . . . , 4. The braid a p,q then corresponds to the counterclockwise half Dehntwist along the arc (P p , P q ). Pictorially, we will represent the braid a p,q by the segment (P p , P q ); for instance, a 2,4 is denoted ( ), a 1,4 is written ( ), and so on. Similarly, the braid which cyclically exchanges P 3 , P 2 and P 1 by a counterclockwise movement is denoted ( ). With this notation, the generators a p,q are subject to the following relations:

( )( ) = ( )( ) = ( ), ( )( ) = ( )( ) = ( ), ( )( ) = ( )( ) = ( )( ) = ( ), ( )( ) = ( )( ) = ( )( ) = ( ), ( )( ) = ( )( ) = ( )( ) = ( ), ( )( ) = ( )( ) = ( )( ) = ( ).
The Garside element is δ = ( ). Conjugation by δ corresponds to a one-quarter counterclockwise turn, and τ is an automorphism of order 4 of B 4 . Therefore, Lemma 2.16(iv), applied to the BKL 4 -structure, states that the orbit of a rigid braid x contains at most 4 • ℓ(x) elements.

Our proof of Theorem 1.2 is based on the simplicity of the lattice of simple elements of BKL 4 . It has only 14 elements: 1, ( ), ( ), ( ), ( ), ( ), ( ), ( ), ( ), ( ), ( ), ( ), ( ), δ.

The relations listed above are length-preserving. This allows us to define a morphism λ : B 4 -→ Z by sending every braid a p,q to 1. For any braid x, we call λ(x) the weight of x. As already remarked in [START_REF] Birman | The Infimum, Supremum and Geodesic Length of a Braid Conjugacy Class[END_REF], λ(δ) = 3 and for any other simple nontrivial element s we have λ(s) = 1 or 2. This observation yields a new quantity, in addition to canonical length, supremum and infimum, which is constant inside the Super Summit Set: Lemma 2.20. Let x ∈ BKL 4 , and let y ∈ SSS(x). For every z ∈ SSS(x), the normal form of z contains as many factors of weight 2 and as many factors of weight 1 as the normal form of y.

Proof. For every braid x ∈ BKL 4 , if k 1 is the number of factors of weight 1 and k 2 the number of factors of weight 2 in the normal form of x, then ℓ(x) = k 1 + k 2 and λ(x) = 3 inf(x) + 2k 2 + k 1 . Thus k 1 and k 2 are constant in the Super Summit Set, since canonical length, weight, and infimum are constant there.

The following very simple remark will turn out to be very useful: Remark 2.21. Let a and b be two simple elements for BKL 4 . If a is of weight 2 and δ does not divide the product ab, then a.b is in normal form.

We finally claim that in the BKL 4 structure, the existence of a minimal useful arrow s from y ′ ∈ O y to z ′ ∈ O z is equivalent to the existence of a minimal useful arrow from z ′ ∈ O z to some element of O y . (In other words, every edge in SCG(x), for G = BKL 4 , is oriented both ways.) Let us prove this claim. According to Remark 2.18, such a minimal arrow s is a strict prefix either of ι(y ′ ) or of ∂(ϕ(y ′ )). In particular, λ(s) = 1. Now there is an arrow, which is of weight 1 and thus minimal, given in the first case by s -1 ι(y ′ ) from z ′ to c(y ′ ), and in the second case by s -1 ∂(ϕ(y ′ )), from z ′ to τ d(y ′ ).

Proof of Theorem 1.2

Throughout this section, we use the dual Garside structure on B 4 . Our aim is to prove Theorem 1.2, so we consider a rigid pseudo-Anosov braid x, and we try to bound the size of SC(x). The hypothesis that x is pseudo-Anosov implies that the canonical length of x is strictly larger than 1 (this can be proven by analysing all braids with canonical length 1).

We shall see that it suffices to prove Theorem 1.2 separately in three special cases, which are defined in terms of the simple factors occurring in x (see Section 2.3). We will consider successively the following three cases:

• The normal form of x contains at least one factor of weight 1 and one factor of weight 2 -this case is solved in Proposition 3.1. (Notice that all other elements of SC(x) will have the same property, by Lemma 2.20).

• There exists an element y of SC(x) such that all the factors other than δ occurring in the normal form of y belong to {( ), ( ), ( ), ( )} -this case is solved in Proposition 3.4. • For every element y of SC(x), all the factors other than δ occurring in the normal form of y are of weight 1, and at least one of them is ( ) or ( )this case is solved in Proposition 3.13.

In the first two cases, the hypothesis that x should be pseudo-Anosov is in fact unnecessary. In these cases, we even construct a linear bound on #SC(x). The third case requires much more sophisticated techniques, and gives rise to an example showing that the quadratic bound is optimal.

3.1. A simple special case. We now describe a simple special case where Theorem 1.2 can be proved by elementary arguments. The proof of this proposition is based on the following lemma:

Lemma 3.2. Let x ∈ BKL 4 be a rigid braid whose normal form contains at least one factor of weight 1 and at least one factor of weight 2. Let y ∈ SC(x). Then there is no strict prefix of ι(y) or of ∂(ϕ(y)) which is a minimal arrow for y.

Proof. By Lemma 2.20, the normal form of every element of SSS(x) (and thus of SC(x)) contains at least one factor of weight 1 and at least one factor of weight 2. Therefore, if δ p y 1 . . . y r is the normal form of y, then there exist k, l with 1 k, l r such that λ(y k ) = 1 et λ(y l ) = 2. Let t be a simple nontrivial braid such that t ≺ τ -p (y 1 ) or t ≺ ∂(y r ) and y t ∈ SSS(x). We shall prove that y t cannot be rigid. Up to replacing y by its inverse, which is rigid with ι(y -1 ) = ∂(φ(y)), we can suppose that t ≺ τ -p (y 1 ).

Necessarily, λ(t) = 1 and λ(y 1 ) = 2 (because a factor y 1 with λ(y 1 ) = 1 cannot have any strict prefix), so we can take l = 1. Let us choose k as the smallest index of a simple factor of weight 1. Thus for 1 j < k we have λ(y j ) = 2. Let us study the element y t = t -1 δ p y 1 . . . y r t.

Since y was rigid, the pair y r .t is in normal form. Next, we are going to prove that ϕ(y t ) = t. Writing t 1 = τ p (t), the calculation of the normal form of y t can be performed using k -1 successive local slidings:

(t -1 j y j )y j+1 = (t -1 j y j t j+1 )(t -1 j+1 y j+1 ) = y ′ j (t -1 j+1 y j+1 ) for j = 1, . . . , k -1, where t j+1 = ∂(t -1 j y j ) ∧ y j+1
. For all j = 1, . . . , k -1, we have t j = 1 (i.e. the pair (t -1 j y j )y j+1 is not in normal form as written) because otherwise we'd obtain sup(y t ) > sup(y). Moreover, δ is not a prefix of t -1 1 y 1 . . . y r t. Therefore, λ(t j ) = 1 for j = 1, . . . , k -1. Since λ(y k ) = 1, we also have t k = y k , and y ′ k-1 is of weight 2. Now by Remark 2.21, the pair y ′ k-1 • y k+1 (with y k+1 = t if k = r) is in normal form. This completes the proof of our claim that ϕ(y t ) = t.

We can now prove that y t is not rigid. Indeed,

ι(y t ) ∧ ∂(ϕ(y t )) = τ -p (t -1 1 y 1 t 2 ) ∧ ∂(t) = t -1 ι(y)τ -p (t 2 ) ∧ ∂(t)
. Thus t -1 ι(y) is a nontrivial common prefix of ι(y t ) and ∂(ϕ(y t )), so the pair ϕ(y t )ι(y t ) is not left-weighted. In summary, the braid y t is not rigid and t was not a minimal arrow for y. Now, the proof of Proposition 3.1 is an immediate consequence of the preceding lemma and of Lemma 2.16(iv). Now, in order to prove Theorem 1.2, we have to find a quadratic bound on the size of SC(x) for any rigid pseudo-Anosov braid x ∈ BKL 4 . By Proposition 3.1, we can restrict our attention to braids whose normal form has all its factors (other than δ) of the same weight (1 or 2). Up to considering inverses, we can restrict ourselves to the case of weight 1 (see [START_REF] Birman | Conjugacy in Garside Groups II: Structure of the ultra summit set[END_REF], Corollary 3.10).

So for the rest of the proof of Theorem 1.2, we can suppose that x is a rigid pseudo-Anosov braid whose normal form has only factors of weight 1 (i.e. ( ), ( ), ( ), ( ), ( ), ( )), and δ ±1 By Lemma 2.20, all elements of SSS(x) have the same property. Moreover, using Remark 2.18, we see that for every y ∈ SC(x), all possible minimal useful arrows for y are strict prefixes of ∂(ϕ(y)) (there is no strict non-trivial prefix of ι(y) because λ(ι(y)) = 1). In particular, all vertices of SCG(x) have valence at most 3.

We make one more simple, but very useful general observation: Lemma 3.3. Suppose that the normal form of the rigid braid y ∈ SC(x) has only factors of weight 1 (and δ ±1 ), with at least one factor equal to ( ) or to ( ). Then the vertex O y of SCG(x) is at most bivalent.

Proof. Up to replacing y by y ′ ∈ O y , we can suppose that ϕ(y) = ( ). But ∂(( )) = ( ), and this simple element has only two strict positive prefixes.

We split the rest of our argument into two parts. In Subsection 3.2, we study the case where SC(x) contains an element that does not satisfy the hypotheses of Lemma 3.3, i.e. an element whose normal form contains, apart from δ ±1 , only the letters from {( ), ( ), ( ), ( )}; we shall denote the latter set E. By contrast, Subsection 3.3 deals with the case where all elements of SC(x) satisfy the hypotheses of Lemma 3.3.

3.2. Some element of SC(x) has all its factors in E. We recall the notation E = {( ), ( ), ( ), ( )}. Our aim in this subsection is to prove the following result, whose proof is elementary but involves a lot of careful case-checking: Proposition 3.4. Let x ∈ BKL 4 be a rigid braid. Let us suppose that SC(x) contains some element y whose normal form has all of its factors (apart from δ ±1 ) belonging to E. Then the graph SCG(x) has at most six vertices. Moreover, #SC(x) 24 • ℓ(x).

The last sentence of Proposition 3.4 follows immediately from the preceding one, together with Lemma 2.16 (iv).

First we note that in order to prove Proposition 3.4, it suffices to prove that for some non-zero integer m ∈ N the graph SCG(x m ) has at most 6 vertices. Indeed, since all braids in SC(x) are rigid, there is an injection from SC(x) to SC(x m ), sending an orbit O y to an orbit O y m . So possibly after replacing x by x 4 , we can suppose that inf(x) is a multiple of 4. In fact, since for any integer m, multiplication by δ 4m induces an isomorphism between SC(x) and SC(δ 4m x), we can even suppose that inf(x) = 0 (and thus that the infimum of any element of SSS(x) is zero).

So for the rest of the proof of Proposition 3.4, we shall assume that for y (and hence for all elements of O y ) the normal form has all letters belonging to E. Remark 3.5. Conjugation by δ induces a permutation of E. Moreover, for all s, t ∈ E, the product st is in normal if and only if t ∈ {s, τ (s)}. Remark 3.5 allows us to give a precise description of the normal form of y: Lemma 3.6. Let y ∈ BKL 4 be a rigid braid with inf(y) = 0, all of whose factors belong to E. Then, possibly after replacing y by another element of O y , the normal form of y is of the form

y = r j=1 τ -r+j ( ) kj ,
where the k j , j = 1, . . . , r are strictly positive integers, and r = 1 or r ≡ 0 (mod 4).

Proof. Up to conjugating y by a power of δ, we can suppose that ϕ(y) = ( ). By Remark 3.5 and our hypothesis on y, the normal form of y is indeed a product of the form y = τ -(r-1) ( ) k1 . . . ( ) kr for integers r and k 1 , . . . , k r all strictly positive. Then, due to rigidity and Remark 3.5, we have ι(y) = ϕ(y) or ι(y) = τ (ϕ(y)). Let us suppose that r > 1. Up to cycling, we can suppose ι(y) = τ (ϕ(y)), which means that τ -r+1 (( )) = τ (( )). This implies that r ≡ 0 (mod 4).

Lemma 3.7. If r = 1 in Lemma 3.6, then #SC(x) = 6.

Proof. If r = 1 then SC(x) = {( ) k1 , ( ) k1 , ( ) k1 , ( ) k1 , ( ) k1 , ( ) k1 }.

Lemma 3.8. Suppose that r > 1 in Lemma 3.6. Then there exists a minimal arrow for y if and only if r ≡ 0 (mod 3). If this is the case, then y admits in fact three minimal (but not necessarily useful) arrows. If not, then the graph SCG(x) has a single vertex.

Proof. According to Lemma 3.6, we have r ≡ 0 (mod 4), and we can rewrite

y = m j=1 ( ) kj,1 ( ) kj,2 ( ) kj,3 ( ) kj,4 := m j=1 α j ,
with m := r 4 and k j,i > 0 for all j, i with 1 j m and 1 i 4. The minimal useful arrows for y, if they exist, are all strict prefixes of ∂(( )), so they are ( ), ( ) or ( ).

Proof. Up to cycling or conjugating by δ we can suppose that the last factor of z is ( ), and that l m 3 > 1. There are at most two minimal arrows for z, namely ( ) and ( ). A calculation of the normal form of z( ) shows that ( ) ⊀ z( ), which implies that z ( ) / ∈ SSS(x), and hence the lemma.

In order to perform this calculation, we make three observations. Firstly,

( ) lν -1 ( ) = ( )( )( ) lν -2 .
Secondly, for arbitrary integers a, b > 0,

( ) a ( )( ) b ( ) = ( ) ( ) a ( )( )( ) b-1
and the first factor on the right hand side is independant of the powers a and b.

Thirdly, the pair ( )( ) is in normal form. Now the previous calculation can be pushed towards the left along the normal form of z, getting twisted by a conjugation by ∆ at each step, until it hits, possibly, a factor ( ) or ( ), where it gets stuck.

This shows that the multiplication of z by ( ) on the right can only modify the beginning of the normal form of z if ( )

l m 3
-1 is the only occurrence of ( ) or ( ) in z. Moreover, if this is the case, then the initial factor of z( ) is ( ). This completes the proof.

Lemma 3.10. Suppose that the normal form of z does not contain any factor ( ) or ( ). Then Proof. According to our hypothesis, we can further rewrite the formulae from the proof of Lemma 3.8:

y = m 3 ν=1 ( ) aν ( ) bν ( )( ) dν ( ) eν ( )( ) gν ( ) hν ( )( ) jν ( ) kν ( ) and z = m 3 ν=1 ( ) aν ( )( ) bν ( ) dν ( )( ) eν ( ) gν ( )( ) hν ( ) jν ( )( ) kν .
(i) According to Lemma 3.8, z admits three minimal (not necessarily useful) arrows.

(ii) Let v be a minimal useful arrow for z such that z v contains no factor ( ) or ( ). We first mention that at least one such an arrow exists, because O y = O z . We know that v ∈ {( ), ( ), ( )}. Thus it is sufficient to prove that v = ( ) and v = ( ). We are going to apply the formulae from the proof of Lemma 3.8, now with z playing the rôle previously played by y.

If v = ( ), then the formulae from the proof of Lemma 3.8, together with the restriction that z v must not contain any factors ( ) ni ( ), imply the equalities b ν = e ν = h ν = k ν = 1. But then z = z ( ) , contradicting the usefulness of v. Thus v = ( ).

We remark that the length function used in the statement of ([7], Proposition 7) is the length associated to the alphabet of divisors of ∆, i.e. the set of simple braids in the classical Garside structure. However, the length functions associated to different finite generating sets in a group are in bilipschitz correspondence. More explicitely, our two length functions on B 4 are related, with the obvious notations, by the formula:

|x| BKL4 2 • |x| classical 6 • |x| BKL4 .
In order to complete the proof of Theorem 1.2, it is now sufficient to prove the following result (where the constant c is the one promised by Theorem 3.12). Question 3.14. Open question 2 in [START_REF] Birman | Conjugacy in Garside Groups I: Cycling, Powers and Rigidity[END_REF] concerns the existence of a polynomial bound in n and ℓ on the size of the set of sliding circuits of a rigid (pseudo-Anosov) braid with n strands and of canonical length at most ℓ. Prasolov gave a negative answer, by exhibiting a family of rigid pseudo-Anosov braids for which the size of the SC grows exponentially as a function of n (for both structures, dual and classical). On the other hand, if we fix n then no such counter-example is known, and indeed in the special case n = 4 our Theorem 1.2 gives an affirmative answer. So we formulate the following question: for any fixed integer n, does there exist a polynomial P n such that the cardinality of the (classical or dual) SC of a rigid pseudo-Anosov braid with n strands is bounded above by P n (ℓ(x))? Question 3.15. Is the size of the (classical or dual) SSS of a rigid pseudo-Anosov 4-braid x bounded above by P (ℓ(x)), for some polynomial P ? We know from [START_REF] Caruso | On the size of Super Summit Sets of pseudo-Anosov braids[END_REF] that for braids with five or more strands, the size of the classical SSS can increase exponentially with the length of the braid.

Proofs of Theorems 1.3 and 1.1

In this section we will prove Theorems 1.3 and 1.1. The plan is to prove Theorem 1.3 first, and then to prove the validity of the algorithm described in the Introduction and to analyse its complexity.

First we recall one of the main results of [START_REF] Birman | Conjugacy in Garside Groups I: Cycling, Powers and Rigidity[END_REF]: Theorem 4.1. [START_REF] Birman | Conjugacy in Garside Groups I: Cycling, Powers and Rigidity[END_REF]. Let x ∈ B n be a pseudo-Anosov braid. Then there exists an integer m such that x m is conjugate to a rigid braid. Moreover, the integer m can be bounded independently of the length of x: m < ( n(n-1)

2

) 3 for the classical Garside structure and m < (n -1) 3 for the dual structure.

We are going to use a second time the Masur-Minsky linear conjugacy bound, by invoking the following result from [START_REF] Calvez | Fast Nielsen-Thurston classification of braids[END_REF] whose proof relies on this bound. (Recall that s denotes the cyclic sliding operation -see Definition 2.7).

Proposition 4.2. ([7], Theorem 2)

. There exists a constant C, depending only on n and on the chosen Garside structure, with the following property: if x ∈ B n is a pseudo-Anosov braid lying in its own Super Summit Set, and if x possesses some rigid conjugate, then the conjugate s C|x| (x) is rigid. This proposition yields a quadratic time algorithm for finding a rigid conjugate y of any given pseudo-Anosov braid x satisfying x ∈ SSS(x), and also for finding a conjugating element, provided a rigid conjugate exists at all.

We are now ready to prove Theorem 1.3.

Proof of Theorem 1.3. Let us denote β(n) the upper bound on m in the statement of Theorem 4.1. Let x, y ∈ B n be pseudo-Anosov braids. Our aim is to algorithmically find rigid conjugates of x s and y s for some s ∈ N.

Due to Theorem 4.1, there exist two integers i x and i y , both smaller than β(n), such that x ix and y iy are conjugate to rigid braids. For all i = 1, . . . , β(n) -1 simultaneously, our algorithm iterates the operation s starting from x i , until a rigid braid is found. The corresponding power i x and a braid z x such that (x ix ) zx is rigid are memorized. We denote x this rigid conjugate of x ix The same procedure, applied to y, yields an integer i y and braids z y and ỹ with the corresponding properties.

Note that the algorithm so far is doable in time O(ℓ 2 ), where ℓ is the maximum of the canonical lengths of x and y. In order to prove this, we remark that the canonical length of all the braids x i and y i , for i = 1, . . . , β(n) -1, is bounded above by β(n)ℓ. By Theorem 2.10 and Proposition 4.2, the number of iterations needed in order to find x is linearly bounded with respect to this length β(n)ℓ. Finally, each iteration of the operation s on a braid of canonical length ℓ takes time O(ℓ)(see [START_REF] Gebhardt | Solving the conjugacy problem in Garside groups by cyclic sliding[END_REF]). Let s = lcm(i x , i y ). Since powers of rigid braids are again rigid, x s and y s are conjugate to rigid braids. So all our algorithm has to do now is to calculate s, and output x = x s ix , ȳ = ỹ s iy , and z 1 = z x , z 2 = z y . This satisfies the requirements of Theorem 1.3.

Proof of Theorem 1.1. We have to prove that the algorithm described in the introduction is valid and of complexity O(ℓ(x) 3 ). All the necessary ingredients are already at our disposal. Steps (1) and (3) are of complexity O(ℓ 2 ), as was shown in [START_REF] Calvez | Fast algorithmic Nielsen-Thurston classification of four-strand braids[END_REF]. Step (2) is of complexity O(ℓ 3 ) (see Theorem 1 dans [START_REF] Birman | Conjugacy in Garside groups III: Periodic braids[END_REF]). Step (4) is of complexity O(ℓ 2 ), by Theorem 1.3. Finally, Theorem 4.11 of [START_REF] Gebhardt | Solving the conjugacy problem in Garside groups by cyclic sliding[END_REF] assures us that Algorithm 3 in [START_REF] Gebhardt | Solving the conjugacy problem in Garside groups by cyclic sliding[END_REF] correctly solves CDP and CSP for rigid braids of length at most ℓ in time O(ℓ • κ), where κ denotes the cardinality of the SC of the input braids. Our Theorem 1.2 now implies that step (5) of our algorithm has complexity O(ℓ 3 ). Moreover, step [START_REF] Birman | A new approach to the word and conjugacy problems in the braid groups[END_REF] gives the correct answer, because by [START_REF] González-Meneses | The nth root of a braid is unique up to conjugacy[END_REF], the relation x = ȳc for a braid c (i.e. (x s ) z1 = ((y s ) z2 ) c ) is equivalent to the relation x z1 = y z2c , which is in turn equivalent to x being conjugate to y by z 2 cz -1

1 .

Proposition 2 .

 2 13. [19] Let x ∈ G.

(

  iii) It suffices to prove that for every y ∈ SC(x) and every z ∈ O y , O z = O y . The inclusion O z ⊂ O y holds by part (ii). Conversely, let k, l ∈ N such that z = τ k c l (y); we shall prove that y ∈ O z . Let j be the smallest positive integer satisfying rf j > l.

Proposition 3 . 1 .

 31 Let x ∈ BKL 4 be a rigid braid whose normal form contains at least one factor of weight 1 and at least one factor of weight 2. Then the set SC(x) consists only of O x and in particular #SC(x) 4 • ℓ(x).

( i )

 i the three strict prefixes of ∂(ϕ(z)) are minimal arrows for z, (ii) if v is a minimal useful arrow for z conjugating z to another rigid braid whose normal form contains no factor ( ) or ( ), then z v ∈ O y and v = ( ).

  So let O a and O b be two distinct vertices of SCG(x), and let z a and z b be representatives of these two orbits. Due to Theorem 3.12, there exists a braid w satisfying z w a = b b , and such that |w| 2 • c • |x| 4 • c • ℓ(x). Up to changing the representative z a we can suppose that inf(w) = 0. Then λ(w) 2 • |w|, as every factor of the normal form of w contributes at most 2 to the weight of w. Thus w is the product of at most 2 • |w| minimal arrows, which yields a path of length at most 2 • |w| between O a and O b in the graph SCG(x).

  Proposition 3.13. Let x ∈ BKL 4 be a rigid pseudo-Anosov braid. Suppose that all elements of SC(x) have at least one factor of their normal form equal to ( ) or ( ).Then the graph SCG(x) has at most 16•c•ℓ(x) vertices. Thus, #SC(x) 64•c•ℓ(x) 2 .Proof. First we can suppose that |x| 2 • ℓ(x). In order to see this, we notice that multiplying x by any power m of the central element δ 4 induces an isomorphism between the graphs SCG(x) and SCG(δ 4m x). In this way, we can suppose that inf(x) ∈ {-3, -2, -1, 0}. Then from Remark 2.3 we obtain |x| 2 • ℓ(x) (recalling that ℓ(x) 2, since x is pseudo-Anosov).

According to Lemma 3.3, every vertex of the graph SCG(x) is at most bivalent, so topologically the graph is either a compact line segment or a circle. We claim that any two distinct vertices O a , O b in the graph SCG(x) can be connected in the graph by a path of length at most 8 • c • ℓ(x). Before proving this claim, we observe that the claim, together with Lemma 2.16 (iv), implies Proposition 3.13 (the factor 2 comes from the possibility that the graph might form a circle).

The proof of the lemma essentially comes down to the following calculations, where the right hand sides of the equations (except for their first factor) are always in normal form; in other words, A j , B j and C j are normal forms, independently of the powers occurring in the formulae (this calculation uses the notation α j defined in the previous paragraph):

We remark that, independently of j and of the powers occurring, the "pairs" A • C, B • A and C • B are in normal form. On the one hand, if r ≡ 1 or r ≡ 2 (mod 3), then this shows that for every u with u ≺ ∂(( )) we have u ⊀ yu, and in particular y u / ∈ SSS(x). On the other hand, if m ≡ 0 (mod 3), then this shows that the three braids

are rigid.

We suppose from now on that r ≡ 0 (mod 3) (this is always satisfied up to replacing x by x 3 ). Let u be such that u ≺ ∂(( )). Then it follows from our proof of Lemma 3.8 that we can always find, up to cyclic permutation of the factors, an element z of O y u of the form

by making an appropriate choice of indices and powers inside the factors.

We can then rewrite y in the form

with strictly positive integers a ν , b ν , . . . , l ν for all ν = 1, . . . , m 3 , and then z becomes

Lemma 3.9. If the normal form of z contains a factor ( ) or ( ), then z admits a unique minimal useful arrow, i.e. the vertex O z of the graph SCG(x) is extremal.

Analogously, if v = ( ), then due to the formulae from the proof of Lemma 3.8 we obtain a ν = d ν = g ν = j ν = 1. But then

We obtain c(z ( ) ) = τ (z), contradicting the usefulness of v. Thus v = ( ).

Lemma 3.10 shows that the graph SCG(x) cannot contain a chain of 3 vertices whose elements contain no factor ( ) or ( ). By Lemma 3.9 any vertex which does contains at least one factor ( ) or ( ), but which is adjacent to a vertex which doesn't, is monovalent. Since the graph SCG(x) is connected, this implies that it has at most 6 vertices. This completes the proof of Proposition 3.4.

3.3.

All elements of SC(x) have at least one factor not belonging to E.

In this subsection we suppose that all elements of SC(x) have at least one factor in their normal form equal to ( ) ou ( ). According to Lemma 3.3, the graph SCG(x) is then a (possibly closed) line. In order to prove Theorem 1.2, we need to bound the length of this line. This task seems much more difficult than in the previous subsections, we have currently no elementary proof of Theorem 1.2 under the above hypotheses. In order to illustrate the difficulty, we show first that the quadratic bound of Theorem 1.2 is optimal. The following example was obtained with the help of the program GAP [START_REF] Schönert | GAP -Groups[END_REF]:

Example 3.11. For all k ∈ N, the braid β k = ( )( )( )( )( )( ) 3k ( ) -3k , whose normal form is