Patrick Maillé

Gwen Maudet

Mathieu Simon

Bruno Tuffin

Are Search Engines Biased? Detecting and Reducing Bias using Meta Search Engines

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

When we want to reach some content, information or tool on our smartphone, tablet or laptop, and do not know exactly what to look for and where to get it, we usually use a search engine (SE), that responds to typed-in keywords with a ranked list of links to the supposed most relevant corresponding places. Google is the most used SE worldwide, but many others exist such as Bing, Yahoo, Duckduckgo, Qwant, or Startpage. For a more comprehensive list, see for example https://en.wikipedia.org/wiki/List_of_search_engines. Search engines propositions have a huge influence on our daily life, since users have a tendency to click on one of the first proposed links, and search engines are extensively used: Google alone registers in a year about 2 trillions searches all over the world 1 .

But SEs are accused of voluntarily lowering some links in their rankings, hence reducing the visibility, access, and revenue of the corresponding actors, or of boosting other links the SEs are closely or financially related to 2 . While SEs are making money thanks to sponsored links, that are displayed links clearly presented as advertisements corresponding to the search keywords and sold through auctions [START_REF] Maillé | An overview of research on sponsored search auctions[END_REF][START_REF] Maillé | Telecommunication Network Economics: From Theory to Applications[END_REF], we are talking here about organic links, representing the considered most relevant responses to the dialed keywords. This issue of biasing the results was brought in 2009 by Adam Raff, co-founder of the price-comparison company Foundem, saying that Google was voluntarily penalizing his company in rankings with respect to Google's own services. Any SE could indeed in theory choose which company to promote or to demote with financial motivations; such an optimal strategy was computed in [START_REF] L'ecuyer | Revenue-maximizing rankings for online platforms with quality-sensitive consumers[END_REF], as a trade-off between short-term and long-term revenues; other models can be found in [START_REF] Pollock | Is google the next microsoft: Competition, welfare and regulation in online search[END_REF].

This has led to the so-called and still vivid search neutrality debate, asking whether SEs should be neutral in their organic rankings-i.e., base their rankings on relevance only-and if so, how that can be monitored [START_REF] Grimmelmann | Some skepticism about search neutrality[END_REF][START_REF] Lewandowski | Is google responsible for providing fair and unbiased results?[END_REF][START_REF] Manne | If search neutrality is the answer, what's the question[END_REF]28]. The issue is related to the sensitive Net neutrality debate [START_REF] Coucheney | Network neutrality debate and ISP inter-relations: Traffic exchange, revenue sharing, and disconnection threat[END_REF][START_REF]Net Neutrality or Net Neutering: Should Broadband Internet Services be Regulated[END_REF][START_REF] Maillé | Toward a net neutrality debate that conforms to the 2010s[END_REF][START_REF] Odlyzko | Network neutrality, search neutrality, and the never-ending conflict between efficiency and fairness in markets[END_REF][START_REF] Wu | Network neutrality, broadband discrimination[END_REF], active for almost 20 years, asking whether Internet Service Providers (ISPs) should be allowed to differentiate service at the packet level within the network to get some return on their infrastructure investment. A higher quality of service would be paid by content providers, but this raised concerns regarding the impact on innovation, freedom of speech (if some content can be blocked), etc. The basic definition of Net neutrality, even if it depends on countries, is that ISPs should treat equally all content flowing through their networks, regardless of its kind, source, or destination. But if the key issue is access and impact on innovation, shouldn't SEs be part of the equation? Indeed, similarly to ISPs, search engines have a gatekeeper position and can significantly distort the competition among actors on the Internet.

There is reluctance to accept the search neutrality debate in the same way as the Net neutrality debate. First, the nature of an SE is often argued to allow to make various and sometimes new/surprising propositions to open-minded users; but why helping some quality-demanding applications should correspondingly be forbidden by ISPs? Second, it is often advocated that if you are not happy with an SE, switching to another is just "one click away". But it might not be easy to detect biases and switch SEs when unfairness is just for a limited number of keywords, and the SE market is not as competitive as it seems, with as of June 2020 3 Google concentrating 91.75% of worldwide searches, the followers being Bing (2.75%), Yahoo (1.7%), Baidu (1.02%), Yandex (0.92%), and Duck-DuckGo (0.49%). Finally, it is often thought that defining a neutral behavior is simple for an ISP but not for an SE. But defining packet-level neutrality as "equal treatment at nodes of the network" does not encompass differences at the flow level, which could for example come from different round-trip times when using TCP (dependent on distance), a possible discrimination, and does not deal with activities such as content delivery networks [START_REF] Maillé | Toward a net neutrality debate that conforms to the 2010s[END_REF]. For SEs, addressing the neutrality debate also means introducing a definition of a neutral behavior in a clear and objective manner. A fair way would be to rank according to relevance to keywords, but the notion of relevance is difficult to define, subjective, since potentially very user-dependent. Personalization of SE ranking, using location or cookies, refines but also complicates the notion. A "solution" could be to ask SEs to be transparent about the used algorithms to check whether voluntary discrimination is implemented, an approach more and more pushed by (European) regulators 4 , but which induces secret/copyright issues and is out of the scope of the present paper.

Defining relevance is a very sensitive and complicated issue, the considered definition being revealed by SEs or not. The PageRank method [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF] developed by Google is an example of such an algorithmic definition, basically ranking pages based on their incoming links (backlinks), but is computationally demanding. We will take a simpler alternative here, by making use of already existing ranking systems by SEs (hence no computationally-demanding algorithm to add): we will define the relevance of a page/link as the average visibility of its positions among SEs. Given some visibility values of the different positions (e.g., estimated from measurements on the click behavior of users), that metric is simple to compute, and smooths potential irregularities by SEs. The issue of fairness in rankings has also been addressed in [START_REF] Biega | Equity of attention: Amortizing individual fairness in rankings[END_REF][START_REF] Dwork | Rank aggregation methods for the web[END_REF] but not with the notion of visibility and click-through-rates which specifically concerns search results.

There exist many works on search non-neutrality, with sometimes different conclusions. Mowshowitz and Kawaguchi [START_REF] Mowshowitz | Measuring search engine bias[END_REF] use an own-defined measure of similarity between SE results, and show that there are significant differences, particularly sensitive to the subject domain but not the search terms in a given domain. The same authors claim similarly to us that "A family of comparable search engines can be used to approximate the ideal or fair distribution of items retrieved for a set of queries" [START_REF] Mowshowitz | Assessing bias in search engines[END_REF], but they do not provide statistical tests to detect bias, and instead use a notion of dissimilarity not involving any interpretation in terms of visibility. A comparison and illustration of differences among SEs is discussed in [START_REF] Vaughan | Search engine coverage bias: evidence and possible causes[END_REF], trying to determine the possible causes. Another nice reference on ranked list comparison is [START_REF] Webber | A similarity measure for indefinite rankings[END_REF], particularly interesting when comparing truncated lists with partly different elements; see also [START_REF] Pitoura | On Measuring Bias in Online Information[END_REF]. [START_REF] Wright | Defining and measuring search bias: Some preliminary evidence[END_REF] analyses how own content by Bing or Google is ranked first more than on competing engines to highlight a general bias. Our work can also be linked with the study of political bias and the role of search engines in elections [START_REF] Kulshrestha | Quantifying search bias[END_REF][START_REF] Robertson | Auditing partisan audience bias within google search[END_REF], but the latter involves different measures related to personalization. Evaluating the performance of SEs (information retrieval) is another related topic [START_REF] Lewandowski | Evaluating the retrieval effectiveness of web search engines using a representative query sample[END_REF], the score we define being original in this respect, as it requires no human but is based on the assumption that SEs point out to the right links on average.

The purpose of this paper is multifold. Our contributions, and the differences with respect to the literature can be decomposed as follows.

1. We formalize a definition of visibility which will be used to rank pages (links). The score of a page will be the average displayed interest/visibility of the positions obtained by that page at SEs. In this sense the score is applying a weighted Borda rule [START_REF] De Borda | Mémoire sur les élections au scrutin[END_REF][START_REF] Young | An axiomatization of Borda's rule[END_REF]. As a consequence, we are also able to compute a score for each SE, by summing the scores of the presented pages/links weighted by their positions. We can then easily compare SEs for a given keyword and for a population of keywords.

We develop a statistical methodology to identify potential bias based on

Dixon's Q test. The proposed tests are more precisely: i) Looking at scores of SEs for a keyword, an excessively low score being suspect since it indicates a ranking very different from other SEs. ii) Investigating whether the highest-ranked link of a SE is ranked as high by others. iii) Looking at the rankings of the most consensual link and checking whether that link is ranked abnormally low by some SEs. We are not aware of any other work using a similar statistical testing procedure to detect search engine bias.

3. We propose two meta-engines. The first one, called consensus SE, ranks links according to the weighted Borda scores (average visibility among SEs) obtained above. The second one is following the majority judgment rule defined in [START_REF] Balinski | Majority Judgment: Measuring Ranking and Electing[END_REF] for votes and adapted to our context. Voters are SEs voting for pages as candidates. Pages are ranked according to the median of votes, that is the rank for which 50% or more of the SEs give at least this rank. This ranking is expected to erase bias more than the consensus SE and we provide a theoretical framework to illustrate it through simulations. Aggregating search results to get a meta-engine is not new (see [START_REF] Dwork | Rank aggregation methods for the web[END_REF]), but our two aggregation techniques (weighted Borda or majority judgment) have not been implemented so far to our knowledge.

4. We present a publicly-available platform/web page https://snide.irisa. fr/ on which a keyword can be composed, the results of 15 engines plus the two meta engines are displayed, and potential bias are pointed out, if detected by statistical tests.

5. We provide results of bias on searches through statistics of failed tests for each SE, and give illustrative examples.

6. We compare the meta-engines in terms of average scores, highlight how they smooth bias, and provide statistics on their performance.

7. Thanks to extensive studies on campaigns of most dialed keywords, we compare the results of all SEs (not only our meta-engines, but also the "regular" ones). We are able to compute and compare expected scores over searches, but also their distributions, in order to see similarities, highlight if they use close algorithms, and compute the frequencies of potential bias to emphasize how often they can be trusted. Again, comparing ranking algorithms has already been done in the literature, see [START_REF] Bar-Ilan | Methods for comparing rankings of search engine results[END_REF][START_REF] Dwork | Rank aggregation methods for the web[END_REF][START_REF] Mowshowitz | Measuring search engine bias[END_REF][START_REF] Webber | A similarity measure for indefinite rankings[END_REF], with methods mostly coming from models related to voting systems. An example is to use the Kendall distance, looking at the pairwise ordering disagreement between lists. But those methods do not take into account the weights associated to CTRs of positions and their economic impact, nor do they compute distributions of scores and bias.

The paper is an extension of a conference paper where preliminary results were presented [START_REF] Kamoun | Evaluating search engines and defining a consensus implementation[END_REF]. While the principle of using visibility as a page score and the consensus search engine were already introduced, the additional results are: i) the statistical tests of bias, the main purpose of this activity; ii) an analysis of outlier detection on scores for an extensive list of representative keywords; iii) the introduction of the second meta-engine based on majority judgment theory and believed to further reduce bias with respect to the consensus one; iv) a comparison of all SE outputs as well as our two meta-engines; v) the use of a more complete list of 15 SEs, while "only" 9 were considered in [START_REF] Kamoun | Evaluating search engines and defining a consensus implementation[END_REF]; vi) the introduction of a publicly available tool to compare SEs and perform bias detection tests.

The rest of the paper is organized as follows. Section 2 presents our model, more precisely how we compute scores of links and SEs for given keywords based on average visibility. Section 3 introduces the statistical tests for potential bias, each of them based on Dixon's Q test for outlier detection. Given the several SEs available, Section 4 proposes the two meta-engines aiming at reducing bias. The whole methodology is implemented on a publicly available web site to detect and reduce bias (thanks to our meta engines) as described in Section 5. Extensive tests are conducted and analyzed in Section 6, on detected bias but also to compare all the search engine outputs. Finally we conclude and describe our next research directions in Section 7.

Model/scoring system

This section recalls and expands the discussion in [START_REF] Kamoun | Evaluating search engines and defining a consensus implementation[END_REF].

Score/relevance: visibility among SEs

The ranking of an SE is supposed to correspond to a list of links ordered by their relevance with respect to the composed keyword. Defining the notion of relevance is a complicated issue which can be considered subjective. Our goal is not to discuss how relevance should be defined, and it seems good to observe several different notions implemented to leave the choice to (informed) users; this problem is also often related to the notion of transparency of algorithms but is out of the scope of the present paper (for more, see [START_REF] Maillé | Toward a net neutrality debate that conforms to the 2010s[END_REF]). SEs use computationally-demanding algorithms to set their relevance score, such as PageRank for Google [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF]. Bing 5 as another main SE defines relevance as "how closely the content on the landing page matches the intent behind the search query. This includes matching terms directly on the page as well as terms used in links referring to the page. Bing also considers semantic equivalents, including synonyms or abbreviations, which may not be exact matches of the query terms but are understood to have the same meaning." But Bing also uses other parameters for its ranking, such as the quality/reputation of the page, the fact that users already clicked on this link, the user location, the page load time, etc. The algorithm is therefore complex and resource and experience demanding.

We choose to make use of the outputs from the (already existing) complex algorithms of SEs rather than defining our own (which could be seen at least as arbitrary as any SE). For a given keyword, our definition of a score (or relevance) of a page will be its average visibility over SEs, the visibility for an SE depending on the page's position in the ranking [START_REF] Maillé | An overview of research on sponsored search auctions[END_REF]. That choice presents several advantages:

• The method is computationally simple, taking benefit of the complex algorithms implemented by SEs; we just need to launch a search on all SEs and associate visibility values to the different positions 6 .

• What typically counts for content providers is to be clicked, the complaint in the search neutrality debate coming from the lack of reachability. It therefore makes sense to focus on visibility and quantify the differences with respect to that notion.

• Averaging over SEs reduces potential biases in relevance expressions and/or considers all dimensions of relevance considered by SEs, even if neglected by others.

Formalization

We formalize the model in this subsection, recalling and extending the notions in [START_REF] Kamoun | Evaluating search engines and defining a consensus implementation[END_REF]. We consider n SEs, a set K of keywords (possibly infinite), and a finite set L of pages/links corresponding to all the results displayed for the whole set of searches. For any keyword k ∈ K, let p k be its probability to be dialed during a search, such that k∈K p k = 1; p k is therefore related to the frequency of keyword k.

Even if SEs can display several pages of results for a given search we will limit ourselves to the first displayed result page for each SE, and assume for simplicity that it shows a number a > 0 of results, even if it can be easily generalized to the heterogeneous case.

As explained above, we will define the score of a page/link as its average visibility among SEs, a notion easier to consider than the subjective and manyparameters-dependent notion of relevance. Visibility can be estimated through the click-through-rate (CTR) of a page at a given position, measuring the rate, or probability, at which it is clicked, denoted by c i, for a Page i at position [START_REF] Maillé | An overview of research on sponsored search auctions[END_REF]. That value is typically SE-, position-and link-dependent, but we assume here for convenience, and as commonly adopted in the literature, a separability property [START_REF] Maillé | An overview of research on sponsored search auctions[END_REF] formalized as c i, = q i q ,

i.e., the CTR is the product of a link-specific factor q i (some links are more attractive by nature) and a position-specific factor q for position . We will interpret that expression in terms of probabilities, with the CTR c i, (probability of being clicked) being the product of a probability of being seen q (that depends on the link position) and a probability of being clicked when seen q i (that depends on the link's relevance to the request). We will therefore identify the visibility that a SE gives to a link/page shown in position with the term q .

In general those terms can also be SE-dependent, but we will here consider the same values across SEs, since estimating them would require data obtained from extensive experiments-which is out of the scope of this paper-or directly from SEs. Nevertheless, that aspect is generalizable in our model without technical difficulty. Finally, note that we typically have q 1 ≥ q 2 ≥ • • • ≥ q a , meaning that the better ranked, the more visible.

The visibility values q we will use in our numerical studies come from CTR values obtained through measurements in [START_REF] Dejarnette | Click-through rate of top 10 search results in Google[END_REF] and displayed in Table 1, with a = 10. Note that only the relative values of (q ) are needed, multiplying all of them by a positive constant does not change anything in the model or the results. The underlying assumption for obtaining those values from statistics on click numbers is that the link-specific terms will tend to average out over a large number of searches, so that the click probabilities on each position will be proportional to the position-specific terms (q ). Note also that it is easy to Table 1: CTR values used in the paper, taken from [START_REF] Dejarnette | Click-through rate of top 10 search results in Google[END_REF] q 1 q 2 q 3 q 4 q 5 q 6 q 7 q 8 q 9 q 10 0.364 0.125 0.095 0.079 0.061 0.041 0.038 0.035 0.03 0.022 change those values, considering for example the ones obtained more recently and available at https://www.sistrix.com/blog/why-almost-everythingyou-knew-about-google-ctr-is-no-longer-valid/.

Having introduced all the required notations, we can define the score of a page for a given keyword from outputs provided by SEs.

Definition 1. The score R i,k of a page i ∈ L for a keyword k ∈ K is defined as the average visibility of that page over the rankings from all considered SEs for that keyword:

R i,k := 1 n n j=1 q πj (i,k) (1)
where π j (i, k) denotes the position of page i on SE j for keyword k. If a page is not displayed by an SE, the visibility is taken as 0 (equivalently, we can define a position a + 1 for non-displayed pages, with q a+1 = 0).

With that score definition, any bias from an SE is smoothed (reduced) due to the averaging procedure, so that we expect page scores to be closely linked to the actual relevance of pages with respect to keywords.

Search engine score

Even if it is not the initial purpose of the work, defining a score for pages allows to define a corresponding score for SEs, for a given keyword but also for the whole set of searches. It quantifies how "consensual" with respect to the other SEs a given SE is.

Definition 2. The score S j,k of an SE j for a given keyword k is defined as the total "page score visibility" of its results for that keyword:

S j,k := page i∈L q πj (i,k) R i,k ,
where again q p = 0 if a page is ranked at position p ≥ a + 1 (i.e., not shown).

Note that equivalently, the score can be reformulated by summing over the displayed pages,

S j,k = a p=1 q p R πj (p,k),k
where πj (p, k) is the page ranked at the p th position by SE j for keyword k, i.e., πj (•, k) is the inverse permutation of π j (•, k).

To interpret that score, the higher an SE ranks highly exposed pages, the higher its score, meaning that the score measures the visibility that the SE gives to pages that are well-exposed on average by SEs. Another way to interpret it is to see the page scores as approximations of the actual page relevances, so the SE score somehow measures the relevance seen by users on that SE.

From the SE scores per keyword, we can also define an overall score of SE j over the whole set of keywords:

Definition 3. S j := E K [S j,k ] = k∈K p k S j,k , (2)
where E K [•] is for the expected value of probability distribution (p k ) k∈K over K.

This definition takes into account the frequency/probability p k of each keyword k ∈ K, so that S j represents the expected score that SE j would obtain when a (random) keyword is typed in.

Statistical tests of bias

Our main goal is to develop a tool to detect potential biases in SEs' outputs, based on the lists of results from all SEs. This is typically the goal of outlier detection [START_REF] Aggarwal | Outlier Analysis[END_REF][START_REF] Hodge | A survey of outlier detection methodologies[END_REF]. We want to use a non-heuristic statistical test designed for a small to moderate sample size (the size being the number of SEs): the natural candidate is then Dixon's Q test [START_REF] Dean | Simplified statistics for small numbers of observations[END_REF][START_REF] Dixon | Processing data for outliers[END_REF].

Dixon's Q test

Dixon's Q test [START_REF] Dean | Simplified statistics for small numbers of observations[END_REF][START_REF] Dixon | Processing data for outliers[END_REF] is designed to quickly identify outliers in datasets that only contain a small number of observations. Assume a data set of n (independent and identically distributed) values normally distributed and sorted in increasing order

x 1 ≤ x 2 ≤ • • • ≤ x n .
To see if the largest value is an outlier, define the statistics

Q :=          Q 10 = xn-xn-1 xn-x1 if 3 ≤ n ≤ 7 Q 11 = xn-xn-1 xn-x2 if 8 ≤ n ≤ 10 Q 21 = xn-xn-2 xn-x2 if 11 ≤ n ≤ 13 Q 22 = xn-xn-2 xn-x3 if 14 ≤ n ≤ 25. (3)
Values q α,n are tabulated (see [START_REF] Dixon | Processing data for outliers[END_REF]) such that x n is considered an outlier at confidence level 1 -α (or risk α) if Q > q α,n .

Similarly, if we rather want to investigate whether the smallest value x 1 is an outlier, we will consider the statistics

Q :=          Q 10 = x2-x1 xn-x1 if 3 ≤ n ≤ 7 Q 11 = x2-x1 xn-1-x1 if 8 ≤ n ≤ 10 Q 21 = x3-x1 xn-1-x1 if 11 ≤ n ≤ 13 Q 22 = x3-x1 xn-2-x1 if 14 ≤ n ≤ 25. (4)
The Gaussian assumption is often violated, which may be a problem for a small data set, and it is also often advised to use Dixon's Q test to only detect outliers and not to remove them7 , but it is the existing tool that corresponds best to our purpose, namely statistically detect potential bias/outlier.

We will consider n = 15 SEs, that is, we will use the statistics

Q = Q 22 .
The three next subsections describe the three implementations of Dixon's Q test we will consider in practice.

Abnormal SE score for a given keyword

The first test we will consider aims to determine whether, for a given keyword, an SE score as of Definition 2 is abnormally low with respect to the others.

For a keyword k ∈ K, the values used for the test are therefore x j = S (j),k , the SE scores, sorted in increasing order. We consider the statistics Q defined in (4), and will say that the SE with the smallest score is an outlier and potentially biased at risk α if Q > q α,n .

By that test, we identify SEs with outputs significantly different from competitors. An uncommon behavior with respect to competitors means a low score.

Investigating SEs disregarding the most visible link

Consider the page/link ranked as the most visible for a given keyword k (i.e., the page with the largest score R •,k ). Our aim is to determine if an SE is ranking and making abnormally less visible this page considered relevant by the consensus.

If * is the page in L with the highest score, the values x i for 1 ≤ i ≤ n are the ordered scores/visibilities among the n SEs, that is,

x i = q πi( * ,k) , 1 ≤ i ≤ n.
We again consider the statistics Q defined in (4), and will say that the SE with the smallest score is an outlier and abnormally "hides" the most relevant page (as per the consensus ranking) at risk α if Q > q α,n .

Investigating if the top-ranked page of each SE is also visible at other SEs

The third test is to investigate whether an SE abusively gives the top spot to a link (as we did in our simulations in Subsection 4.2.2) to create an abnormal advantage.

To do that for any keyword k ∈ K, consider for each SE j the top-ranked page (j), and then take (x i ) 1≤i≤n as the ordered visibilities (q πi( (j),k) ) 1≤i≤n of that page among SEs.

We end up with n tests for 1 ≤ j ≤ n suggesting that at risk α the visibility of the top-ranked page at SE j (necessarily the largest visibility q 1 ) is abusively high with respect to the visibility of that page at other SEs if the statistics Q defined in (3) verifies Q > q α,n .

Investigating if an SE ranks first a page not considered relevant by others

The last test looks at the visibilities of the pages ranked first by SEs. If one of these top-ranked pages has a visibility (a score R •,k ) abnormally low with respect to the others, it may mean that this page is biased upward by the SE. Formally, for a keyword k ∈ K, the values used for the test are therefore

x j = R π (j) (1,k),k , 1 ≤ j ≤ n,
the ordered n scores of the SE top-ranked pages. We consider the statistics Q defined in (4), and will say that the SE whose top-ranked page has the smallest score is an outlier and potentially biased at risk α if Q > q α,n .

Meta search engines

Defining page scores and looking for an SE without bias leads naturally to the definition of meta SEs with bias reduction. In Section 4.1, we redefine the SE first introduced in [START_REF] Kamoun | Evaluating search engines and defining a consensus implementation[END_REF], and in Section 4.2 we introduce another meta SE, based on the majority judgment rule and expected to limit the potential biases even further.

Consensus SE

Using the score definition of pages in the previous section, it seems natural to define a consensus SE as the one showing the pages with the highest scores, i.e., maximizing the SE score for each keyword. Definition 4. For a given keyword k, the consensus SE is a meta-SE that shows at position p the page π (k) (p), where the permutation

π (k) (•) is chosen such that π (k) (•) ∈ arg max π(•) a p=1 q p R π(p),k .
In other terms, pages are displayed in decreasing order of their computed score (their "estimated relevance") R •,k for that keyword k.

We will also be able to compute the total score of the consensus SE, maximal among all SE scores by definition, which will allow us to compare how close to "optimal" the other SEs are.

Majority judgment SE

Definition

Another meta SE we propose here is based on the so-called majority judgment considered for voting systems and presenting nice properties [START_REF] Balinski | Majority Judgment: Measuring Ranking and Electing[END_REF][START_REF] Balinski | [END_REF]. We adapt it to our context to build a ranking procedure expected to further reduce biases induced by SEs with respect to the consensus SE.

Consider a keyword k ∈ K. In the majority judgment, "voters" give an evaluation to each candidate. In our context, voters are SEs, and candidates are pages to be displayed. The evaluations are the visibility values (or equivalently the positions) associated to each page, r i,k,j := q πj (i,k) for page i on SE j: pages ranked first have the highest scores/evaluations. Definition 5. The majority judgment ranking for a keyword k works as follows:

• For each page i, compute its majority judgment r i,k as the best (highest) evaluation among (r i,k,j ) 1≤j≤n for which 50% or more SE give at least that value. In case of an odd number n of SEs, it is the middle value (median) of the ordered values, but for an even number, it is the lowest value of the two in the middle interval (so that more than 50% of the SEs give at least this value). Formally, if

r i,k,(1) ≥ r i,k,(2) ≥ • • • ≥ r i,k,(n) are the ordered values, r i,k = r i,k,( (n+1)/2 )
In summary, it is the best score accepted by a majority of SEs.

• The final majority judgment ranking is the ranking according to the values r i,k , from the largest to the smallest.

In case of equality in a given subset, a vote equal to r i,k is removed for all competitors i, and the algorithm repeated with this excluded value (for this subset of competitors) by computing the new majority judgment values. This is repeated up to a differentiation is made, which happens except if some candidates have exactly the same set of rankings.

Remark that while the consensus ranking allowed naturally to give a score to SEs and make comparisons (computing through the score how far from the consensus a given SE is), it is not that obvious with the majority judgment; that open question is left to future research.

Sensitivity to bias/outliers: Majority Judgment versus Consensus

If an SE is biased and associates to a page a visibility value that is uncorrelated with its relevance, the value itself does not influence the majority judgment ranking (only its position with respect to the median can have an impact); that should smooth biases even more than the consensus ranking.

To illustrate this, we build an artificial model made of 15 SEs, and 20 potential pages to be displayed. When we simulate a search, each page has an intrinsic relevance, that we draw from a uniform distribution over the interval [0, 1]. SEs on the other hand may only be able to imperfectly estimate that relevance: to model that we add for each SE and for each page a Gaussian random variable with mean 0 and variance σ 2 (all those 15 × 20 "noise" variables being independent). If unbiased, SEs then rank pages according to that estimation, so that the larger σ 2 the more differences between SEs, and all SEs give exactly the same ranking when σ = 0.

We aim to investigate the impact on meta-SE rankings of one SE biasing in favor of one page, displaying it first whatever its relevance estimation. (We assume that the SE still ranks all the other pages by estimated relevance, and all the other SEs also rank with respect to their estimated relevances.) We plot in Figure 1, when the "estimation imperfection" σ varies, the average visibility (along with the corresponding 95% confidence interval) of the favored page when repeating 10 5 independent experiments for the simulated and estimated relevances. We use the visibility values (q ) given in Table 1.

We can readily check that average visibilities for the two meta SEs are similar in value when not biasing, and not sensitive to the noise level σ in relevance evaluation by SEs. On the other hand, there are significant differences in the visibility of biased pages for our meta SEs: i) the bias (i.e., the difference of 0 0.2 0.4 0.6 0.8 1 0 visibility with respect to the un-biased case) is significantly lower when using majority judgment with respect to consensus; ii) in both cases, the more variability in relevance estimation, the larger the bias; this is due to less consensually defined positions (and scores) when variability is high, hence less consensus among non-biased SEs which leaves more room to affect meta-SEs; iii) the bias increase with σ is significantly lower for the majority judgment, even close to marginal, as expected. On the same figure, we superimpose the frequency of rejection of the null hypothesis "the score of SE1 (the one with a potential bias) is not abnormally low with respect to the other SEs", with the Dixon test at risk level 1% (described in Section 3.2). Notice that when that SE does not bias the results, it almost never is labeled as an outlier, i.e., false positives are rare. When implemented, bias is frequently detected for low noise values σ: in those cases there is a clear consensus among all the other SEs and the bias is easily detectable. For large noise values, SEs have difficulty agreeing on what pages to display, which benefits the biasing SE in two ways: it has a larger impact on the visibility that its target page gets with the meta-engines, but the bias introduced is harder to detect.

2 • 10 -2 4 • 10 -2 6 • 10 -2

A publicly available platform: SNIDE

We have designed a tool/website to implement the theory developed in previous sections. The tool, available at https://snide.irisa.fr/ is both designed for single (general audience) and multiple (research) search purposes 8 . Figure 2 (left) displays the home page for single searches (e.g., for a user wishing to use our meta-engines or just compare SEs visually), and (right) the page after clicking on the "advanced" button, designed to run the tool for multiple searches (e.g., to carry out larger-scale analyses on the differences among SEs).

For both single or multiple searches, the tool is a web crawler written in Python. The code to get page URLs is adapted to each SE, because they display the results differently. It gives the results from 13 search engines9 selected among the most used worldwide. Note that we excluded SEs such as Baidu due to language issues. The 13 SEs are: Let us focus on the "simple" search first. The web site provides various data when composing keywords, as illustrated in Figure 3. The list of SEs appears on the left, and their scores for this search are displayed. The tool also highlights in color and indicates below the list of SEs whether one SE has a score abnormally low according to the test described in Section 3.2. To go more into details, the user can get the list of the 10 first results of each SE (together with the scores of those pages) by a click on the "down" arrow near each SE. On the right-hand side of the page, the tool gives by default the results of the bias tests described in Sections 3.3 and 3.4, and the rankings of our two meta SEs can be obtained by clicking on the "consensus ranking" or "majority judgment" buttons. That is useful to make comparisons between SEs, but may also be of interest for users interested in engines smoothing possible biases.

• AllTheInternet • AOL • Ask • Bing • DirectHit • Duckduckgo • Ecosia • Google • Lilo • Lycos • Teoma • Yahoo • Yippy
With the "advanced" option of multiple searches, designed more for research purposes, the user can download two files: one with the full output (the top 10 results by each SE for each search), and the other including the analysis (scores and test results). Two format options are possible: text to immediately visualize the results, or JSON for a use with databases.

As often in such a situation, we had to deal with many practical issues. To list a few:

• A priori different URLs can lead to the same page. It is for example the case of http://www.maps.com/FunFacts.aspx, http://www.maps. com/FunFacts.aspx?nav=FF, http://www.maps.com/FunFacts, etc. It can be checked that they actually lead to the same webpage output when accessing the links proposed by the SEs. Sometimes pages are indifferently http or https. We have tried to handle these cases as much as possible.

• For some specific keywords such as Facebook, some SEs do not provide a list of corresponding responses, but rather redirect immediately to the facebook.com webpage. That is typically what AllTheInternet is doing. This is treated in our stats as the SE providing a single response, ranked first. (An alternative approach would have been to assume a different q 1 for those cases-meaning a very high visibility for that page-but this would have altered the meaning of the tests we perform.)

• Sending too many requests over a short period results in our tool being banned by SEs like Google or Startpage; this is typically what happened after our campaign of tests presented in next section. We are working on preventing that behavior; a solution could be for the tool to run locally (on the user's machine) instead of on our central server, which will reduce the searches per day from a given host; another way could be to have regulators intervene to legally prevent blocking when SEs are used for research purposes, as suggested in Europe. These propositions are left for future research.

• Sometimes, SEs update their platforms so that our parser may not get the relevant information to recover the top 10 results. We need to frequently update our tool to avoid those issues.

Comparisons on a large campaign of keywords

We now aim to analyze the results obtained from a campaign of searches. We chose to use 767 keywords among the most searched from https://www.mondovo.com/keywords/most-searched-words-on-google/, and for which we also have the search volume, so that we can compute p k for any keyword k ∈ K, and the related expected values (of scores, of positive tests...). Note that we ran our tool on the 1000 most-searched terms according to the mentioned website, but we encountered some data collection issues for 233 of them. The list of searched terms, as well as their search frequencies and the top 10 result we collected from each SE are publicly available10 . Interestingly, the search terms with data collection issues are not spread independently of their search volume: out of the 19 most-searched terms, 15 led to data collection issues, and they represent 39% of the total search volume from the 1000 most-searched terms. However, we believe this does not affect the analysis we make in this paper, because those specific terms are generally typed in a search engine merely to access the service with that name, not to obtain information regarding the search term. For example the top-searched term "facebook" is mostly searched by people using the SE almost as a DNS service: they just want to access their Facebook page. The other 14 terms with issues among the top 19 are of the same type: "youtube", "google", "gmail", "xxnx", "xvideos", "facebook+login", "pornos", "xxx", "google+translate", "yahoo", "ebay", "google+maps", "yahoomail", and "instagram". Excluding those 15 search terms from the total search volume, the results we managed to collect represent 91.7% of the (remaining) search volume. We plot in Figure 4 the volumes of searches for the 767 search terms in the study, as given by the aforementioned webpage. When plotted in doublelogarithmic scale, the curve is close to a straight line, in accordance with the Zipf distribution, a distribution often observed in natural language, content or webpage popularity, and many other domains [START_REF] Reed | From gene families and genera to incomes and internet file sizes: Why power laws are so common in nature[END_REF].

For the analysis in this section, we consider the 13 SEs given in the previous section, and the visibility/CTR values of Table 2.

Search engines scores

Table 2 gives the average (weighted) scores of the 13 search engines, plus the 2 meta engines. We also include the 95% confidence intervals that would be obtained (abusively) assuming requests are independently drawn from a distribution on all possible requests. One can check the score of her/his favorite SE. To see how close an SE is with the consensus SE, Figure 5 displays by SE the percentage of common results with the consensus SE for each position range. More specifically, for each SE we plot the proportion of links among the top x positions that are also in the top x positions of the consensus ranking.

SE

Finally here, we draw in Figure 6 the distribution of the SE scores over searches (relatively to the consensus score), with on the x-axis the searches ordered (for each SE) by increasing relative scores. That representation allows to see how far each SE tends to be from the consensus ranking. It is not too surprising that the highest curve be the one from our other meta-SE (Majority Judgment), although it is at some points slightly below the curves for Yippy, Lycos, Lilo or Bing. Among SEs, one can also notice some distributions that look very close, like those from Ask and DirectHit, or those from Yahoo and AOL that almost coincide, or Lilo and Bing. Those apparent similarities need to be taken with care though, since for each SE the search terms are reordered by increasing values of the relative score, so having similar distributions does not imply that the SEs return the same results.

To investigate further that question of similarities between SEs, we compute an average (weighted) distance between each pair of SEs. The distance metric that we use is inspired by the Wasserstein distance used in optimal transport problems [START_REF] Villani | Optimal transport: old and new[END_REF]: considering that a ranking gives some visibility weight to some webpages, we compute the minimum effort to move "visibility mass" (from some pages to others) to obtain the visibilities given by a second ranking. Since there is no clear distance defined between two webpages, we consider that any two different webpages are at the same distance (say, 1), so that the total effort to convert one ranking into another is just the amount of visibility to displace. That amount will then be considered as the distance between the two rankings. Mathematically, the distance (for a given search) between rankings π and π (with π(i) the position of page i in ranking π, and similarly for π) is therefore expressed as

D(π, π) = i∈L [q πi -q πi ] + ,
where x + = max(0, x). Those pairwise distances are given in Table 3. This metric allows to see which SEs tend to give similar results. In particular, the distance between AOL and Yahoo is very small, which is consistent with our observations of Figure 6. Other SEs with relatively small distances are the triplet Bing, Lilo, Lycos (with pairwise distances below 0.35). On the other hand, some other pairs like Ask/DirectHit appear less similar than what could be seen in Figure 6, although their distance remains more than one standard deviation below the average value among SE pairs. Finally, we notice that our two meta-SEs, the Consensus and Majority Judgment rankings, even if quite close when compared to other measured distances, are yielding clearly different results, with an average distance over our search terms of 0.3 (i.e., on average one has to "move" 30% of the "visibility points" to get from one meta-ranking to the other).

Identifying potential biases

We now see how SEs perform with respect to the tests defined in Section 3, for our set of search terms. Figure 7 presents the proportions of keywords (weighted by their frequency) for which each SE was rejected by our various tests (based on the Dixon outlier detection test) with risk 1%:

• for having a low score (test "SE score", with tested hypothesis "the score of that SE is not an outlier "),

• for not showing high enough the most consensual page (test "Slot of topconsensus page", with tested hypothesis "the visibility given by that SE to the top-consensus page is not an outlier "),

• for displaying in their top slot a page that is not deemed relevant by the other SEs (test "Top-SE page vs others", with tested hypothesis "the visibility given by that SE to its top-ranked page is not an outlier (among all visibilities given by SEs for that page)"),

• for displaying in their top slot a page much less relevant than the others (test "Top-SE page scores", with tested hypothesis "the score of that SE's top-ranked page is not an outlier (among all SE top-ranked-page scores)").

We note that Ask is the SE performing worst in all 4 test categories, followed closely by DirectHit and Duckduckgo, with Google a bit behind. Looking at those 4 metrics, the best-performing SEs appear to be AOL, Bing, Lilo and Yahoo. However, note that this is likely to be a consequence of those SEs returning quite similar results, as shown before in Table 3: since the tests are based on outlier detection, a biased behavior will not be detected if implemented by enough SEs. Hence again, those results do not show that AOL, Bing, Lilo and Yahoo are better than the other SEs, but rather that their behavior do not individually stand out when compared to the 12 others. The fourth test experiences more detections, probably false positives, that test being more sensitive to the unsatisfied Gaussian assumption, comparing the (relatively much higher) CTR of the first position with potentially other CTR values if the page is not ranked first by other SEs.

To correlate with what we did in [START_REF] Kamoun | Evaluating search engines and defining a consensus implementation[END_REF], we re-identify in Table 4 for each SE the (ordered) 10 queries with lowest relative score with respect to the consensus SE. The table seems to show less sensitive terms than what we had observed in [START_REF] Kamoun | Evaluating search engines and defining a consensus implementation[END_REF], suggesting either that the discrepancies among SEs are not economically motivated or that such biases are not detected since implemented by several SEs. One can nevertheless notice the search term "chrome", in the list of the terms for which Google's score is the lowest relative to the consensus. For that term, one can expect that Google tends to refer more to its Chrome web browser rather than to the metal plating when compared with the other SEs; that specific search term is analyzed further below.

Another observation which might be of interest is to look at the most important pages (that is, those having the largest visibility-their average CTR among SEs-over all weighted keywords) and compare their visibility at the various SEs. To do so, we aggregate pages within the same domain. The goal is to highlight SEs giving to some pages/domaines a very different visibility from others: far above average could mean ties with the page, and far below would mean neglecting it in a suspect way. Figure 8 displays the distance with the average score (divided by the standard deviation), when we normalize the visibility scores. SEs are identified when at the extremes.

Figure 8 illustrates that Wikipedia is the most visible domain overall, even when its English-speaking and French-speaking variants are considered separate domains (all our searches have been performed from France). It seems that Google makes an extensive use of the geographical data of the user, and refers to the French-speaking version significantly more often than the other SEs; Google is also on the lower-end side for the visibility it gives to the English-speaking version. Finally regarding Google, one can notice that surprisingly, it is the SE giving the lowest visibility to YouTube, despite owning it. Maybe this is due to Google having a specific "video" option for its search, while all our tests were using the "all" (all types of results) filter.

The figure also highlights the higher visibility that Duckduckgo gives to Facebook and Twitter (visibility more than 3 standard-deviations above the SE average), and the low visibility it gives to some Google-owned services like Google Play, Google Translate, or just the Google website www.google.com. Notably, the SE Ecosia has a behavior opposite to Duckduckgo for those five domains.

Comparison of meta engines

We already illustrated in Section 4.2.2 in an artificial setting the advantage of the majority judgment ranking over the consensus one to reduce biases. Our goal here is to see what happens with "real" searches.

On Table 2, we can check that the majority judgment SE gives an average score about 10% smaller than the consensus one (built as the score-maximizing ranking). That score is significantly larger than any available engine, with the advantage of significantly reducing biases.

To emphasize the gain in bias reduction by the majority judgment ranking, we show in Figure 9, among the pages ranked first by an SE and identified by a Dixon's Q test as a potential outlier (Section 3.4), their position distribution at both the consensus and majority judgment ranking. The figure highlights the lower sensitivity of the Majority Judgment ranking to one page being artificially boosted by an SE, as we had observed for the numerical experiment of Section 4.2.2. Indeed, among the SE top-ranked pages detected as outliers due to a low score, the Majority Judgment ejects nearly 80% (versus 30% for the Consensus ranking), and generally tends to rank them worse than the Consensus ranking. That higher sensitivity of the Consensus ranking is due to the fact one SE showing a page on the top of its results already guarantees the page a score of at least q 1 /N (attained if the page is only shown by this SE), which can be sufficient to be among the 10 highest-score pages; by contrast, the Majority Judgment would prefer a page that is shown-event in low positions-by two SEs or more over a top-result shown by only one SE.

An example: the "chrome" keyword

We previously evoked the search term "chrome", as one for which Google disagrees most with our Consensus meta-SE. In this section we analyze that case in more detail. The detailed results from each SE can be found on our shared archive, to save space we only provide in Table 5 the rankings given by our two meta-SEs.

Several points are worth mentioning for that specific search:

• The SEs Ask and DirectHit give the exact same three pages in their three top results, from the domain "questionsanswered.net", but no page from that domain is shown by any other SE;

• Nevertheless, since there are two SEs showing the same top result, neither of them is labeled as an outlier regarding the visibility that their top-page has among others (test from Subsection 3.4), but both are detected by the depending only on position). We also compared results from "new" users, i.e., without any cookie, browsing or search history, or personal data; the method proposed in this paper could be used to investigate how such information affects SE results through test campaigns using a variety of user profiles, checking whether a bias occurs for some specific profiles.

Figure 1 :

 1 Figure 1: Visibility with the two meta-SEs, with and without bias introduced by the first SE, and corresponding results of the Dixon test for that SE (Dixon test on the SE score being abnormally low). 95% confidence intervals are also displayed.

Figure 2 :Figure 3 :

 23 Figure 2: Home page of the website https://snide.irisa.fr/ (left), and for multiple searches (right) when clicking on "advanced"

8 Figure 4 :

 84 Figure 4: Search volumes of the 767 search terms used in the study

Figure 5 :

 5 Figure 5: Similarities with the consensus within the first ranking positions.

Figure 7 :

 7 Figure 7: Proportion of failed tests (Dixon tests presented in Section 3) at risk level 1% for each SE (results for risk levels 5% and 10% are very similar).

Figure 9 :

 9 Figure 9: Repartitions of the position on the meta-SEs of the suspected topresults from SEs.

Table 2 :

 2 SE average scores, and 95% confidence intervals half-widths.

		Score
	Consensus	0.106 ± 0.002
	Majority	0.096 ± 0.002
	AllTheInternet 0.079 ± 0.003
	AOL	0.087 ± 0.002
	Ask	0.058 ± 0.003
	Bing	0.087 ± 0.002
	DirectHit	0.06 ± 0.003
	Duckduckgo	0.062 ± 0.003
	Ecosia	0.084 ± 0.002
	Google	0.069 ± 0.003
	Lilo	0.087 ± 0.002
	Lycos	0.088 ± 0.002
	Teoma	0.081 ± 0.003
	Yahoo	0.087 ± 0.002
	Yippy	0.08 ± 0.003

Table 3 :

 3 Average Wasserstein distances between SEs (darker cells indicate a higher similarity). The average distance value is 0.67, the median 0.71, and the standard deviation 0.17.

Table 4 :

 4 10 lowest-scores terms (relative to the consensus) for each SE.

https://searchengineland.com/google\%2Dnow\%2Dhandles\%2D2\%2D999\ %2Dtrillion\%2Dsearches\%2Dper\%2Dyear\%2D250247

See for example https://www.technologyreview.com/s/610275/meet\%2Dthe\%2Dwoman\%2Dwho\ %2Dsearches\%2Dout\%2Dsearch\%2Dengines\%2Dbias\%2Dagainst\%2Dwomen\%2Dand\%2Dminorities/

See http://gs.statcounter.com/search-engine-market-share

https://ec.europa.eu/digital-single-market/en/online-platforms-digital-single-market

See https://www.bing.com/webmaster/help/webmaster-guidelines-30fba23a

Those visibility values (at least relative values, which is sufficient for us) can be estimated from the click-through-rate (CTR) values on the links displayed in different positions; we keep that estimation out of the scope of this paper and assume the visibility values are given.

See https://sebastianraschka.com/Articles/2014_dixon_test.html

We continuously update the website to follow the changes implemented by SEs when collecting results; as a result, the website may experience some small issues. When we carried out the analysis presented in this paper, we checked that the result collection was working properly.

Our initial web crawler[START_REF] Kamoun | Evaluating search engines and defining a consensus implementation[END_REF] was limited to 9 SEs and was not available as a public web tool

All the data we use in this paper can be accessed in the folder https://partage.imt.fr/ index.php/s/6HWNPGit7BdAmXn

Acknowledgement

The authors would like to acknowledge the support of Inria through the exploratory action SNIDE (for Search Non neutralIty DEtection).

Conclusions

This paper proposes a model and tools to analyze the results from search engines (SEs), combine them to build some meta-SEs, and detect possible bias using statistical tests. The whole framework is presented in a publicly-available tool.

The basis of our model is the interpretation of the positions in search engines ranking in terms of visibility given to webpages. This allows us to aggregate the visibility that a webpage is given from a set of SEs, and to define several types of tests using the Dixon outlier detection test.

The meta-SEs we have defined and implemented have satisfying properties: the Consensus ranking allows to average out some possible bias ranks by ranking according to pages' aggregated visibility for a search term, and the Majority Judgment favors pages that deserve visibility by at least half of the SE, hence being more robust to manipulations by one or a few SEs.

The test campaign that we have carried out on 767 search terms allows to identify some differences and similarities among SEs, for example highlighting some tendencies to comparatively favor or disfavor some specific domains.

The work presented in this paper opens several directions for future research. First, the data collection tool would need to be improved to be able to deal with SEs' changes in the presentation of their result pages, so that some further campaigns could be run on whole sets of search terms (for our campaign we had to remove 233 terms out of the initial 1000). Also, a fine tuning of the parameters in the model would be worth considering, in particular the visibility values for each position and on each SE would need to be estimated with more precision, and the results compared with what we get with our coarse approach (visibility


Minchul Lee

Thibaut Jonckheere

Thierry Martin

Josephson Effect through an Isotropic Magnetic Molecule

Keywords: numbers: 73.63.-b, 74.50.+r, 72.15.Qm, 73.63.Kv

We investigate the Josephson effect through a molecular quantum dot magnet connected to superconducting leads. The molecule contains a magnetic atom, whose spin is assumed to be isotropic. It is coupled to the electron spin on the dot via exchange coupling. Using the numerical renormalization group method we calculate the Andreev levels and the supercurrent and examine intertwined effect of the exchange coupling, Kondo correlation, and superconductivity on the current. Exchange coupling typically suppresses the Kondo correlation so that the system undergoes a phase transition from 0 to π state as the modulus of exchange coupling increases. Antiferromagnetic coupling is found to drive exotic transitions: the reentrance to the π state for a small superconducting gap and the restoration of 0 state for large antiferromagnetic exchange coupling. We suggest that the asymmetric dependence of supercurrent on the exchange coupling could be used as to detect its sign in experiments.

Molecular spintronics [1] aims at exploring spindependent electronic transport through molecules with intrinsic degrees of freedom such as spin, connected to leads of various nature. On the theoretical and experimental side, recent advances have concerned both coherent [2] and incoherent [3,4,5] transport through these molecular quantum dot magnets (MQDM). They consist of a magnetic molecule with either a large [6] or a small anisotropy, as is the case for a endofullerene molecule [7].

Here, we provide a nonperturbative computation of the low temperature transport properties of a MQDM connected to superconducting leads using a numeral renormalization group (NRG) approach. The Josephson current allows a diagnosis of the interaction between the intrinsic spin of the molecule, its itinerant electron spin, and the polarization of the leads. It has been known for some time [8,9,10,11], and recently analyzed in experiments [12], that a quantum dot sandwiched between superconducting leads can show a π junction behavior [13]. At the same time, a quantum dot connected to leads at low enough temperatures exhibits the Kondo effect [14]. It was shown [9,15,16] that with superconducting leads, at low temperature the 0 junction state of the Josephson current is restored when the Kondo temperature exceeds the superconducting gap. The stability of this Kondo phase is put in question in the presence of additional spin degrees for freedom [17] which may compete with Kondo screening. Here the Josephson current flows through an isotropic MQDM which can describe a endofullerene molecule [18]. The electron spin in the quantum dot and the magnetic ion inside it interact via an exchange coupling [4]. We calculate the Andreev level (AL) spectrum and the supercurrent and determine the spin of the ground state. We find that the exchange coupling typically suppresses the Kondo effect and drives a transition from 0 to π state. Moreover, antiferromagnetic coupling is found to drive exotic transitions: the reentrance to π state for small superconducting gap and the restoration of 0 state for large J.

The MQDM connected to two s-wave superconducting leads (inset of Fig. 1) is modeled by a single-impurity Anderson model:

H = H M + H L + H T ,
where

H M = ǫ 0 n + U n ↑ n ↓ + JS • S e (1)
H L = ℓk ǫ k n ℓk -∆ e iφ ℓ c † ℓk↑ c † ℓ-k↓ + (h.c.) (2)
H T = ℓkµ t d † µ c ℓkµ + (h.c.) . (3)
Here c ℓkµ (d µ ) destroys an electron with energy ǫ k , and spin µ on lead ℓ = L, R (on the carbon cell); n ℓk and n are occupation operators for the leads and the cell. The single-particle energy ǫ 0 can be tuned by gate voltages. J denotes the exchange energy between the ion spin S and the electron spin

S e = 1 2 µµ ′ d † µ σ µµ ′ d µ ′ .
∆ is the superconducting gap. Except for the finite phase difference φ = φ L -φ R , the leads are identical and their coupling to the MQDM is symmetric. The hybridization between the molecule and the leads is well characterized by a tunneling rate Γ = πρ 0 |t| 2 , where ρ 0 is the density of states of the leads at the Fermi energy. As we are interested in the low temperature behavior, we concentrate for the most part on the Kondo regime with a localized level -ǫ 0 ≫ Γ with large charging energy U ≫ |ǫ 0 |. Specifically, we choose ǫ 0 = -0.1D (the band width D is taken as a unit of energy), Γ = 0.01D, and U = ∞ and introduce the bare Kondo temperature

T 0 K = DΓ/2 exp πǫ0 2Γ 1 + ǫ0 U (at J = ∆ = 0)
. The energy spectrum is found with the NRG method [19] extended to superconducting leads [15,20]. Within the NRG method, the supercurrent is directly obtained by evaluating the expectation value of the current operator [15].

Fig. 1 shows the phase diagram of our system, which constitutes the main result. The junction property switches between 0 and π state, depending on the strengths of J and ∆ with respect to T 0 K . For J = 0, the system undergoes the Kondo-driven phase transition [9,15,16]: The ground-state wave function is of spin singlet kind for ∆ < ∆ c ≈ 1.84 T 0 K and of spin doublet for ∆ > ∆ c . In the strong coupling limit (∆ < ∆ c ) Kondo correlations screen out the localized spin and Cooper pairs tunnel through the Kondo resonance state, resulting in a 0-junction [15,16]. In the weak coupling limit (∆ > ∆ c ), strong superconductivity in the leads leaves the local spin unscreened and the tunneling of Cooper pairs subject to strong Coulomb interaction acquires an additional phase π, making a π-junction [8,9,10,15,16]. It is also found [15] that the transition is φ-dependent so that a narrow region of the intermediate states 0 ′ and π ′ exists; see the enlarged view in Fig. 1.

0 ∆/T 0 K ∆ c /T 0 K J/T 0 K 0 1 0 ′ 1 0 ′ 1 π ′ 1 π 1 π ′ 2 π 2
Finite exchange coupling between electron spins and the ion spin introduces another electronic correlation and affects Cooper pair transport. Fig. 2 shows typical variations of ALs and supercurrents with J along the line aa ′ (see Fig. 1) in the strong coupling limit (∆/T 0 K = 0.1). Any finite J clearly induces a splitting in subgap excitations and consequently causes a crossing between the ground state and the lowest excitation at φ = π (at least for |J/T 0 K | O( 1)); the level crossing otherwise takes place only at φ = π. Across the crossing, the ground state spin is changed from S to S∓1/2 for J ≷ 0. Similarly, the ALs defined as the one-electron/hole subgap excitations (identified as the poles of the dot Green's functions [21]) exhibit discontinuities like kinks in the spectra; for J ≷ 0 two outmost ALs with spin S±1/2 with respect to the spin-S ground state cannot remain as (spin-1/2) one-electron excitations with respect to the ground state with spin S∓1/2 at the transition and are replaced by new ALs with spin S∓1. In parallel with an abrupt change in ALs, the supercurrent-phase relation (SPR) shows a discontinuous sign change (note that I ∝ -∂E A /∂φ, as the continuum-excitation contribution is negligible [21]), culminating in a transition from 0 to π state: two π (′) states labeled as π (′) 1,2 are identified according to the ground-state spin S ∓ 1/2, respectively. The intermediate states 0 ′ 1 and π ′ 1/2 are defined as in Ref. [11]. The full 0 state exists only at J = 0 because any small J drives the system to the π state at φ = π; see Fig. 2. The curve of I(φ) then has three distinct segments [15]. The central segment resembles that of a short ballistic junction, while the two surrounding segments are parts of π-junction curve. As J grows in magnitude the central segment shrinks and eventually vanishes. The SPR then becomes sinusoidal like in a tunnel junction. It should be noted that the 0-π transition is asymmetric with respect to the sign of J: the transition for J > 0 takes place at δE S ∼ T 0 K , where δE S = J 2 (2S+1) is the exchange-coupling energy gap, while the 0 state survives much larger ferromagnetic coupling (J < 0). Once the π-junction is fully established, stronger ferromagnetic coupling does not lead to any qualitative change in the SPR, while a second transition back to 0 state is observed for large antiferromagnetic coupling (J ≫ ∆). The NRG results distinguish the second 0 state (0 2 ) from the former one (0 1 ) in three points: (1) the ground state has spin S -1/2 like the π 1 phase, (2) the SPR is that of a tunneling junction, and (3) the π 1 -0 2 transition has no intermediate state. Figure 3 (c) shows that the critical current has its maximum at J = 0 and decreases with increasing |J| rapidly across the phase boundary for J > 0 or rather gradually for J < 0. The critical current totally vanishes at the π 1 -0 2 boundary and increases again slowly with J in 0 2 phase (see the curve for ∆/T 0 K = 0.01). The 0-π transitions (0 1 -π 1 and 0 1 -π 2 ) can be attributed to the competition between superconducting and Kondo correlations as in the absence of exchange coupling. The relevant parameters are then the Kondo temperature T K and the superconducting gap ∆, and the 0-π phase transition occurs when they are comparable to each other: In our choice of parameters the transition happens at ∆ c /T K ≈ 1.84. The exchange coupling manifests itself by renormalizing the Kondo temperature T K (J). To see this, we applied the poor man's scaling theory to a corresponding Kondo Hamiltonian with no superconductivity and S = 1/2:

-1 -1/2 0 1/2 1 -1/2 0 1/2 1 -1 0 +1 -1 0 +1 -1 0 +1 -1 0 +1 -1 0 +1 -1 0 +1 -1 0 +1 -1 0 +1 -1 0 +1 E A / ∆ J/T K 0 =20 x100 J/T K 0 =10 x50 J/T K 0 =1 J/T K 0 =0.5 J/T K 0 =0.1 J/T K 0 =0 J/T K 0 =-1 J/T K 0 =-10 J/T K 0 =-10 2 x5 φ / π (a) (b)
H KM = k ǫ k n k + JS • S e + (J K S e + J M S) • S L
, where S L is the spin operator for the lead electrons at molecule site. The last term S • S L describing direct coupling between spins of the ion and the lead electrons arises during the scaling process. The renormalization group analysis leads to the following scaling equations: together with J ≈ J(Λ = D),

dJ K/M dln Λ ≈ -ρ 0 J 2 K/M + J 4D (2J K J M -J 2 M/K ) . ( 4
)
As the band width Λ is decreased from D to T K , the coefficient J K , responsible for the Kondo correlation, diverges and the scaling breaks down. In the presence of finite exchange coupling, however, since JJ K J M > 0 with J M (Λ = D) = 0 and |J M | ≪ J K , the term proportional to J in Eq. ( 4) turns out to slow down the flow of J K and accordingly lowers the Kondo temperature. This point is confirmed by NRG calculations applied in the absence of superconductivity. As can be seen in Fig. 3 (a) and (b), the width of the spectral density for dot electrons, identified as the Kondo temperature T K (J), decreases with increasing |J| (for J < 0 this decrease, being marginal, is not clearly shown with the logarithmic scale). We find out that for the ferromagnetic case the ratio T K (J)/T 0 K coincides with ∆ c (J)/∆ c (J = 0). For the antiferromagnetic case, the Kondo correlation is observed to be suppressed not only by the Kondo peak narrowing but by lowering the peak height. Antiferromagnetic exchange coupling can, on the other hand, exert a more profound effect than simply renormalizing the Kondo temperature: it gives rise to a reentrant transition to the π state at small ∆ and restoration of the 0 state for large J. It is known that small antiferromagnetic exchange coupling (J T 0 K ), studied in the context of coupled impurities [22] and side-coupled quantum dot systems [23] and observed in experiments [24], can produce a two-stage Kondo effect. After the magnetic moment of the dot is screened by conduction electrons below T K , at a much lower energy scale (denoted as T J K ) the ion spin is screened by the local Fermi liquid that is formed on the dot. T J K is then the Kondo temperature of a magnetic moment screened by electrons of a bandwidth ∼ T K and density of states ∼ 1/(πT K ) [23]:

T J K ∼ T K exp -πTK J .
The second Kondo effect leads to a Fano resonance and makes a dip in the dot electron density of states as shown in Fig. 3 (a). The dip becomes widened with J and overrides the Kondo peak when T J K ≈ T K so that the Kondo effect is completely overridden. As long as ∆ > T J K , the second Kondo effect does not appear since the superconducting gap blocks any quasi-particle excitation with energy less than ∆. For ∆ T J K , however, Cooper pairs notice the suppression of the Kondo resonance level, and their tunneling is governed by cotunneling under strong Coulomb interaction, forming a π-junction again. Since T J K decreases with decreasing J, ∆ c decreases to zero as J → 0. Note that the extremely small T J K ≪ T K (unless δE S ∼ T 0 K ) might make it hard to detect the reentrance even under rather weak thermal fluctuations with T K > T > T J K . The revival of the 0-state for strong antiferromagnetic coupling can be explained in the picture of cotunneling of Cooper pairs [10]. In weak coupling limit, the fourth- order perturbation theory leads to the supercurrent:

I = 4e sin φ kk ′ t 2 L t 2 R u k u k ′ v k v k ′ E k E k ′ (5) × 1 2S+1 1 E k +E k ′ - 2S+2 δE S +E k +E k ′ , where E k = ∆ 2 + ǫ 2 k , u k = (1 + ǫ k /E k )/2, v k = (1 -ǫ k /E k )/2, and E k = -ǫ d -J 2 (S + 1) -E k < 0.
For antiferromagnetic coupling, the ground state for the uncoupled system has spin S -1/2. After one electron tunnels through the molecule the system can be in spin eigenstate of either S -1/2 and S + 1/2. The latter virtual process, costing more energy by the gap δE S , turns out to acquire a π phase, contributing to a negative supercurrent. The larger amplitude of this process by a factor 2S + 2 (degeneracy of the spin state S + 1/2) dominates over spin-preserving process as long as the gap δE S is small. For a large gap δE S , however, this process becomes negligible and the sign of the supercurrent is reversed. Note that according to Eq. ( 5) the SPR is always sinusoidal and the current should vanish at the transition, which is also confirmed in our NRG calculations.

The physical arguments for the 0-π transitions discussed so far are valid for arbitrary values of the ion spin S, while the phase boundaries are shifted with changing S as shown in Fig. 1. The exchange-coupling energy gap δE S that is supposed to compete with T K increases with S so that for larger S the transitions can occur at smaller J. On the other hand, we have observed that the π 1 -0 2 transition takes place at slightly larger J for larger S. This is because the increase in the degeneracy factor 2S + 2 overwhelms the decrease in matrix elements due to a larger energy cost by δE S [see Eq. ( 5)].

Finally, we present potential experimental manifestations of exchange-coupling-driven 0-π transition. While the direct control of exchange coupling in molecules is difficult to achieve, the relative strength J/T 0 K can be controlled by the gate voltage which can tune the Kondo temperature. Fig. 4 proposes a possibility to observe a double transition (along the line bb ′ in Fig. 1) as the gate voltage is swept. Note that the double transition is an evidence of strong exchange coupling (J ≫ T 0 K ≫ ∆): for examples, with T 0 K ∼ 3K measured in a recent C 60 single-molecular transistor [24], one estimates J ∼ 30K. Asymmetry of the phase diagram enables the sign and possibly the amplitude of J to be determined without ambiguity by observing the evolution of the SPR or the critical current.

FIG. 1 :

 1 FIG. 1: (color online) Schematic phase diagram of a MQDM superconducting junction system [see the upper inset] indicating the 0, 0' (blue), π ′ (green), and π regions. Each region is divided into two subregions according to the ground-state spin: S and S-1/2 for 0 (′) 1 and 02 regions and S-1/2 and S+1/2 for π (′) 1 and π (′) 2 regions, respectively. Note that the 01 state exists only along the line J=0 [see the lower inset]. For larger molecular spin S ′ >S (see the dotted lines), the phase boundaries between 01 and π 1/2 are shifted toward smaller |J|, and one between 02 and π1 moves toward larger J.

FIG. 2 :

 2 FIG.2:(color online) (a) ALs in units of ∆ and (b) supercurrents I in units of I s c ≡ e∆/ as functions of φ in the strong coupling limit (∆/T 0 K = 0.1) for various values of J/T 0 K : see the line aa ′ in Fig.1. Here the ion spin S is set to 1/2.

FIG. 3 :

 3 FIG. 3: (color online) Spectral weights A(ω) for dot electrons coupled to normal leads with antiferromagnetic [(a)] and ferromagnetic [(b)] exchange coupling to ion spin for various values of J/T 0 K (as annotated). (c) Critical currents as functions of J/T 0 K for different values of ∆/T 0 K (see the annotations). The arrows locate transition points corresponding to data with the same color. Here we have used S = 1/2.

FIG. 4 :

 4 FIG. 4: (color online) (a) ALs in units of ∆ and (b) supercurrents I in units of I s c as functions of φ with J/T 0 K = 10 and ∆/T 0 K = 0.02 (at ǫ d = -0.1) while the gate voltage ǫ d is tuned from -0.1 to -0.04. See the line bb ′ in Fig. 1.

The authors thank W. Wernsdorfer, F. Balestro, and Mahn-Soo Choi for helpful discussions. This work is supported by ANR-PNANO Contract MolSpintronics No. ANR-06-NANO-27.