Wenjuan Li
email: wenjuan.li@my.cityu.edu.hk

Lijun Jiang

Weizhi Meng

Lam-For Kwok

Trust It or Not? An Empirical Study of Rating Mechanism and Its Impact on Smartphone Malware Propagation

Keywords: Malicious Applications, Anti-Malware Software, Rating Mechanism, Smartphone Security, User Trust and Awareness

Malicious applications (malware) have attracted much attention from both academia and industry. Thanks to this, common users start to install anti-malware tools to help protect their phones. However, we notice that attackers can still take advantage of some existing mechanisms to induce users to download malware and bypass anti-malware software. In this paper, we focus on the app rating mechanism on smartphones and aim to evaluate its impact on malware propagation. More specifically, we investigate how this mechanism can be maliciously used to leverage the trust levels of users and achieve particular goals (i.e., inducing users to download malware). In the evaluation, we develop a malicious rating system and conduct a study with over 400 participants. Our results indicate that such rating mechanism can affect users' trust on app download and can be utilized to propagate malware.

Introduction

Thanks to the significant portability and the availability of mobile applications, smartphones have quickly become one prevalent computing platform. According to a report from the International Data Corporation (IDC), most existing markets will have a robust growth annually and the worldwide smartphone shipment volumes are forecast to reach 1.9 billion units by 2019 [START_REF]Global Smartphone Growth Expected to Slow to 11.3% in 2015[END_REF]. Since the popularity of smartphones increases, security challenges and threats also become a big concern on this platform.

Malicious applications (malware) are one of these challenges. There were more than 317 million new pieces of malware created in 2014, meaning nearly one million new threats were released into the wild each day [9]. Due to the large news reports and propaganda, more and more users are willing to install one kind of anti-malware software to safeguard their smartphones. In the literature, many efforts have been made through developing various advanced anti-malware

The author was previously known as Yuxin Meng. techniques. Differently, our interest in this work was motivated by the fact that attackers may invade users' phones through reducing user awareness, even if an anti-malware software is pre-installed.

In this work, we take app rating mechanism on phones as a case and conduct an empirical study to investigate its impact on users' trust and malware spread. In particular, we develop a malicious rating mechanism that can leverage the rating scores and comments of target apps. Our purpose is to investigate whether users can be induced to download those malicious apps under the rating system. If users download and install these apps, a self-defined message will be sent to our server and a high rating score will automatically give to those apps in turn. Totally, over 400 users are involved in our study and provide their feedback about their attitude and behaviors. The study results are evaluated based on statistical data and users' feedback. To sum up, the results reveal that attackers can make use of rating mechanisms to reduce user awareness and increase their trust levels on app download, which may greatly degrade the effectiveness of anti-malware tools and cause malware propagation on smartphones.

The remainder of this paper is organized as follows. Section 2 introduces the typical rating mechanism and Section 3 describes the developed malicious rating system that was used in the study. Then, Section 4 illustrates our study methodologies and analyzes the collected results, and Section 5 discusses related studies. Finally, we conclude our work in Section 6.

Rating Mechanism

This rating mechanism is a user feedback channel, attempting to encourage users to share their experience for downloaded apps. The major purpose of this mechanism is to promote the high rating apps and to allow users to share their experience associated with their used apps. Several examples of this mechanism are depicted in Figure 1. Specifically, Figure 1 (a) shows the rating action (i.e., giving a rating score to an app), Figure 1 (b) describes the overall rating score for an app and Figure 1 (c) presents the rating score and users' comments. To summarize, there are three main features of a typical rating mechanism: 1) the rating score usually ranges from 1 to 5, where 5 indicates the highest score (satisfied); 2) the overall rating score is shown on the downloading page of an app and 3) for each app, the details of rating score (e.g., votes for each score) and users' comments are available to all users.

Malicious Rating System

As the app rating mechanism may play an important role in users' downloading choice, it is possible for attackers to utilize it to reduce user awareness and increase their trust on particular apps. To validate this, we develop a malicious rating system and its high-level architecture is depicted in Figure 2. In real-world cases, this alternative market can be popular under some scenarios. For example, an app is not free in official markets but is available in an alternative market (e.g., Anzhi market [1]).

Popular App Category

To simulate a typical app market, it is expected to provide more popular apps that are likely to be downloaded by users. To achieve this goal, we conduct a survey about popular app categories with 729 participants. The concrete question is: what is your most frequently downloaded app category. Each participant can only vote one category. The voting results are shown in Figure 3.

It is found that up to 302 participants (with a rate of 41.4%) are frequently to download entertainment apps (e.g., games). There are 183 participants (about 25.1%) are often to download tool apps. In contrast, few participants (less than 2%) download puzzle and education apps in their spare time. Based on these results, we deploy apps in the market with a similar distribution (i.e., entertainment apps are the most).

Market Settings and Malicious Rating

In this section, we discuss how to construct the app market in detail and how the malicious rating system works.

-Market construction. According to the app distribution in Figure 3, our app market is configured to contain a total of 1405 apps, where 603 of them are entertainment apps, 354 of them are tool apps and the remaining apps belong to other relevant categories. Users can connect to the market through a web link, search and download apps to their mobile phones. The rating scores (the highest score is 5) and users' comments would be shown on each app-downloading page. -Malicious rating system. To deploy those malware to our market, we camouflage 500 entertainment and 300 tool apps using such malware. Moreover, to explore the effect of rating scores on users' choice, 300 entertainment apps were given a high rating score between 4.5 and 5, while the other entertainment apps were given a low rating score between 2 and 2.5. It is the

Download

App Market

1.

Given high rating scores

Given good comments

High Rating Apps Fig. 2. The high-level architecture of our malicious rating system. same for other app categories, in which only half of them were given a high score. After users' installation of our malicious apps, a message will be sent to the server. Afterwards, the server will give the highest score (5 score) to that app and generate a corresponding benign comment.

Our study

Due to security reasons, it is not feasible to use an existing app market in our study directly. In this case, we developed a web-based app market (named as Popstar market) on our self-maintained server, in which its structure and workflow are similar to the existing Anzhi market [1].

Study Methodology

In the study, most participants were recruited from a university environment, since students are one of the main body of smartphone users. Before the study, we got approvals from the university and security office, so that we can use an online system to recruit participants. All study deployment and processing were not relevant to the university environment. More specifically, we mainly conducted two case studies: in-lab study and out-lab study.

-In-lab study. Participants were recruited online, where a total of 317 students were willing to attend this study. None of them were from securityrelated majors. All participants were invited to our lab and were given an Android phone. The phone was pre-installed an antivirus tool that can make an alert when the user encounters and installs the developed malware. This design aims to explore whether users will ignore such kind of alerts. In addition, before the study, we explained our goal to all participants, and they were required to download up to 15 apps. After the study, all participants were given a questionnaire form to provide their feedback. A gift card $10 will be given to each participant as incentive. -Out-lab study. In order to simulate a real scenario, we conducted another case study, where users did not need to come to the lab environment to complete their tasks. In fact, all participants should use their own phones to finish the study. For this purpose, 112 new students were recruited online. None of them were from security-related majors. Before the study, we introduced our objectives to all participants. Similar to our tasks in the in-lab condition, all participants were asked to download 15 apps from our market. After the study, all participants were invited to give feedback on a questionnaire form. Finally, 109 participants were consent to give feedback and approved us to use the statistical data. In this case, we only analyze the data from these 109 participants and all of them were given a $10 gift card as incentive. The whole study took three weeks to finish.

Statistical Results

According to our system design, as long as one participant successfully installed the malicious app, our server can receive a message for that app. This can help compute statistics relevant to users' choice and actions during the app download.

After the study, we calculate the statistical results based on the received messages from the server. The infection rates and the numbers of installed high and low rating apps are shown in Figure 4. -In-lab study. Figure 4 (a) shows that up to 142 participants suffered from the malicious rating system and installed the malware, in which the infected rate is 44.8%. In the study, it is observed that those infected participants have ignored the pop-up alert and disabled the pre-installed anti-malware software. To look closer to the installed number of different rating apps, Figure 4 (b) shows that those participants are very likely to continue installing an application with a high rating score, instead of installing a low rating app.

The figure presents that nearly 74% installed malicious applications are high rating apps, while only 26% apps with low rating scores. -Out-lab study. The main purpose of this study is to investigate users' behavior in a practical environment. Under the out-lab condition, users can use their own phones to search and download apps from our market. Similarly, the infection rate and installed app numbers are shown in Figure 4. Figure 4 (a) shows that up to 60 participants continued installing the malicious apps on their own phones so that the infected rate is 53.6%. The infection rate is a bit higher than that of the in-lab study. According to Figure 4 (b), participants were mostly willing to continue the installation of high-rating apps, where 90% successful cases came from high-rating apps.

User Feedback

In this part, we analyze the collected user feedback regarding their choice, awareness and trust levels during the app download. Some key questions and user feedback from both case studies are summarized in Table 1.

App download choice. In Table 1, the first question reflects that 59.3% participants selected to download high-rating apps in the lab environment, but more than 85% participants did so outside the lab (in the second user study). In contrast, in the out-lab study (with their own phones), users prefer to start downloading their interested apps. The numbers of this question indicate that users usually begin downloading an app according to their interests, even under a constrained condition.

In Table 1, the second question shows that 226 out of 317 participants (about 71.3%) were likely to download high-rating apps under the in-lab condition, while 100 out of 109 participants (about 91.7%) prefer to download high-rating apps under the out-lab condition. The latter is much higher than the former due to environmental factors, whereas both rates verify that users are willing to install high-rating apps. They generally believe that high-rating apps are more secure than those low rating ones. For example, if there are several app versions, they are more likely to download the version that has a higher score.

User trust. The third question shows that up to 76.3% and 90.8% participants in respective condition will check others' comments before they download an app. In our interview, it is found that users' comments have a high impact if the app download or installation encounters some issues. For example, when the app installation is alerted by an antivirus, users will check others comments to confirm the situation. If the comments are good enough, users may decide to ignore the alert and continue the installation.

Regarding the fourth question, most participants (over 85%) notice that some apps require to disable anti-malware software before downloading & installing the apps. The fifth question shows that nearly half participants would follow the instructions to disable the anti-malware software and continue the installation. In our interview, most infected participants considered that this may be a common case for some entertainment and tool apps, especially in a new market, that false alarms often occur.

User awareness. The last question shows that only about half participants (53.9% and 50.4% for each condition) are really aware of any risk in downloading apps from our market. Most participants considered that those apps, especially high-rating apps, should be benign and at least not harmful, since the rating scores and comments are quite good from others.

Discussions. Overall, based on the feedback, it is validated that rating scores and comments can greatly affect users' trust on app download. That is, the rating mechanism can impact users' attitude in downloading an app from a market. Therefore, through proper camouflage, attackers can utilize such rating mechanism to induce users to disable anti-malware tools and continue downloading & installing particular apps. This situation opens a hole for attackers to spread malware even if users have pre-installed antivirus software.

Related Work

As smartphones have become a major target for attackers, various research studies have focused on the detection of malware from market [START_REF] Peng | Smartphone malware and its propagation modeling: A survey[END_REF][START_REF] Teufl | Malware detection by applying knowledge discovery processes to application metadata on the Android Market (Google Play)[END_REF]. There are also some studies discussing recommender and rating systems [START_REF] Josang | Robustness of trust and reputation systems: Does it matter?[END_REF][START_REF] Muller | On Robustness of Trust Systems[END_REF]. Different from those studies, in this work, we target on app rating mechanism and attempt to evaluate its impact on users' trust on app download and malware propagation on smartphones. From this aspect, to the best of our knowledge, our work is the first study in the literature to investigate this topic.

Our study reveals that users' trust can be greatly affected by a malicious rating system and be induced to download malicious apps, resulting in malware propagation. Even worse, it is worth noting that such malicious rating system can collaborate with existing advanced malware techniques to achieve an even larger impact (i.e., stealing users' sensitive information and data). There is a line of research studies on applying various attacks to infer users' private information and data on smartphones, including side channel attacks [START_REF] Meng | Surveying the Development of Biometric User Authentication on Mobile Phones[END_REF] and physical access attacks like charging attacks [START_REF] Meng | Charging Me and I Know Your Secrets! Towards Juice Filming Attacks on Smartphones[END_REF][START_REF] Meng | A Framework for Large-Scale Collection of Information from Smartphone Users based on Juice Filming Attacks[END_REF].

Conclusion

Different from other studies on rating systems, in this paper, we focus on app rating mechanism on smartphones and aim to evaluate its impact on users' trust and malware propagation. We have two specific questions: whether users can be induced to download malicious apps, and whether the rating systems can affect users' trust on app download. Our results indicate that users' trust can be greatly affected by such system by manipulating high rating scores and good comments. By taking advantage of this system, attackers can propagate malware and bypass antivirus tools. Our research attempts to raise more attention for malware research community on user-centric solutions.

Fig. 1 .

 1 Fig. 1. App rating mechanism: (a) rating action, (b) overall rating score and (c) rating score details and users' comments.

PFig. 3 .

 3 Fig. 3. A survey of popular app category.

Fig. 4 .

 4 Fig. 4. (a) Infection rates for in-lab and out-lab conditions, and (b) Installed high rating apps versus low rating apps.

Table 1 .

 1 User feedback during the study.

	Questions/users


Tim Muller

Dongxia Wang

Yang Liu

Jie Zhang

How to Use Information Theory to Mitigate Unfair Rating Attacks

In rating systems, users want to construct accurate opinions based on ratings. However, the accuracy is bounded by the amount of information transmitted (leaked) by ratings. Rating systems are susceptible to unfair rating attacks. These attacks may decrease the amount of leaked information, by introducing noise. A robust trust system attempts to mitigate the effects of these attacks on the information leakage. Defenders cannot influence the actual ratings: being honest or from attackers. There are other ways for the defenders to keep the information leakage high: blocking/selecting the right advisors, observing transactions and offering more choices. Blocking suspicious advisors can only decrease robustness. If only a limited number of ratings can be used, however, then less suspicious advisors are better, and in case of a tie, newer advisors are better. Observing transactions increases robustness.

Offering more choices may increase robustness.

Introduction

Online systems nowadays are typically too large for a single user to oversee. A user must rely on recommendations, reviews, feedback or ratings from other users (i.e., advisors), to be able to use a system to its fullest extent. In practice, we see that ratings are ubiquitous in large online systems. The exact design challenges introduced by supporting ratings depend on context (e.g. rating format, distributing ratings, subjectivity). One major challenge for all systems is how to deal with unfair ratings.

Typical approaches perform some or all of the following: incentivise honest ratings, detect and filter unfair ratings, update advisors' trustworthiness. More involved approaches may attempt to use possibly unfair ratings, and correct for the possible error, e.g. using machine learning or statistical methods. We call such methods aggregation mechanisms. The power of aggregation mechanisms is limited. Specifically, given a set of ratings, the amount of information that can be extracted is bounded upwards by a certain quantity. We call this quantity the information leakage of the ratings. No aggregation mechanism can be expected to do better than that.

Fortunately, the set of ratings that an aggregation mechanism operates on is not a universal given. One may control factors such as the number of advisors, which advisors to ask and the rating format. Changing these factors will change the information leakage of the ratings, and thus the limits of the power of aggregation mechanisms. Ideally, we want to increase the limit.

We formalise an abstract model of rating systems that assumes the bare minimum. Its only assumption is that there exist honest advisors, and their ratings correlate somehow with the decision that a user should make. Furthermore, we show that information theory offers effective tools to measure the quality of ratings. Specifically, we prove that information leakage of a rating about a decision puts a hard bound on the accuracy of a decision. The remaining results are a set of design guidelines. These guidelines are valid for any rating system that has ratings that somehow correlate with good decisions. Specifically, 1) blocking suspicious advisors is not helpful and can decrease robustness, 2) when receiving ratings is costly, less suspicious advisors should be preferred, 3) and if advisors are equally suspicious, newer ones are preferable, 4) if possible, keep track of who has direct experience, and 5) changing the rating format and the options in a decision may increase robustness.

The paper is organised as follows: we discuss related idea and approaches in Section 2. We discuss the problem at hand -unfair rating attacks, in Section 3. Then we introduce the abstract notion of trust systems, in Section 4, formalise them (Section 4.1) and discuss what defenders can alter (Section 4.2). Then we show that limiting the information leakage is limiting the accuracy, in Section 5. In Section 6, we prove the five aforementioned guidelines.

Related Work

Multiple types of approaches exist to deal with unfair rating attacks. Some approaches provide incentives to promote honest rating behaviour [?,?,?]. Jurca and Faltings design a payment-based incentive scheme, which explicitly rewards honest feedback by an amount that offsets both the cost and the benefit of lying [?]. The payment schemes can be based on proper scoring rules, or correlation between the ratings of different advisors. In [?], they study how to resist against collusive advisors: colluders that share a lying strategy have to suffer monetary losses. Some other approaches aim to detect and filter out unfair ratings [?,?]. For product-rating based online rating systems, Yafei et al. propose to detect collaborative biased ratings by observing time intervals where they are highly likely [?]. Reporting ratings is treated as a random process, and signal-processing techniques are applied to detect changes in rating values (e.g., detecting mean change). Most approaches evaluate advisors' trustworthiness, based on which reliable advisors are selected or ratings get discounted [?,?]. Yu et al., propose a reinforcement learning based framework to filter unfair ratings and make more accurate decisions in selecting trustees [?]. Both direct experiences and indirect evidences from advisors are aggregated to select highly reputable trustees. The reward derived from the interaction with a trustee is used to update advisors' credibility, and ratings from less credible advisors are discarded. Meanwhile, weights assigned to direct and indirect trust evidences are also updated in trust evidence aggregation. We call these defense approaches as aggregation mechanisms.

The classification for different aggregation mechanisms is not absolute. Different types of approaches may be aggregated. For example, in [?], statistical methods are used to detect unfair ratings, of which the results are used to evaluate trustworthiness of advisors. The trustworthiness of advisors is then used to aggregate ratings, and also detect future suspicious ratings.

Despite of deviating from the truth, unfair ratings may still contain useful information (e.g., if they are correlated with a user's direct experiences). There are approaches which exploit such correlation to make use of unfair ratings [?,?,?]. BLADE [?] and HABIT [?] learn from statistical correlations between a user's direct experiences and an advisor' ratings to adjust his ratings. For example, if an advisor always report bad ratings about a trustee, of which the user has good trust opinion, then his ratings get reversed. In this paper, we proved that suspicious advisors may still provide useful ratings (Proposition 4). Ratings from honest advisors may be subjectively different from a user's direct experiences, but they differentiate from unfair ratings from attackers. Subjective ratings may provide useful information as they are relevant for a user. By directly discarding or filtering ratings that deviate from direct experiences, subjective ratings from honest advisors may also get excluded.

The quantification of the amount of information in ratings (i.e., information leakage) is already well studied in [?]. The defense approaches above cannot change the information leakage of ratings in a system, and they only differ in the way of exploiting it. Hence, their effectiveness is limited. From [?], we know that different attacks make information leakage in a system different. In the worst-case attacks where there is little information leakage, these approaches may not help at all. A robust rating system should not let its limitation to be controlled by attacks. Hence, it is vital to increase the limit of information leakage under attacks.

We found that some properties of a system, like the format of ratings, can affect the information leakage. Also, the conditions to achieve the minimal information leakage may also change based on these properties. By proper design, the power of defense approaches can be limited less, and the power of attacks can be decreased.

Unfair Rating Attacks

Unfair rating attacks are known to exist. They have been detected on existing trust systems [?,?], and they are well-studied in the literature [?]. It seems straightforward what an unfair rating attack is (unfair ratings are provided to mislead a user). But in reality, only 'rating' is unambiguous. For example, subjectivity may blur the truth and lies, meaning ratings deviating from the truth may not be from attackers, but subjective honest advisors. Moreover, with some probability, an honest user may perform the same sequence of actions (trace) as a user that intends to attack the system [?]; is that trace an attack? The issues lies in considering only the actual ratings.

Ratings cannot be fair or unfair by themselves. Not only may subjectivity lead to false ratings that are not unfair, but unfair ratings can be (objectively or subjectively) true. Advisors may tell the truth to mislead users that believe the advisor is more likely to lie [?]. Advisors may tell the truth because they are colluding, but want to remain undetected [?]. Or advisors may tell the truth because they do not want to lose the user's trust [?]. In each case, the unfairness lays in the fact that the advisor merely acts out some malicious strategy, rather than respecting the truth.

We want to have a pragmatic definition of unfair rating attacks. Our goal is to make rating systems robust against unfair rating attacks. In other words, ratings must be useful, even if some sources are malicious. However, how useful ratings are to a user, depends on what the user chooses to do with these ratings. The aim of this paper is not to provide the right aggregation mechanism or dictate user's decisions, so -pragmatically -we take a measure of how much a user can do with the ratings: information leakage. We prove, in Theorem 1, that the information leakage measures the potential usefulness of ratings.

Attackers have an underlaying strategy. Attacks are considered successful, when they achieve some goal. The goal is not known in advance. Since we are considering robustness, we primarily care about the worst-case for a user -the information leakage is minimal. Hence, we pragmatically assert that the goal of an attack is to minimise information leakage. We assume attackers select the strategy that minimises information leakage. If we are wrong, then the information leakage increases by definition. Section 5.1 provides detailed formal analysis.

Rating System

In this paper, we are not necessarily interested in rating systems themselves, but rather in which aspects we can control in our advantage. Particularly, we study how to set the parameters that we control to harden a rating system -maximising the minimal information leakage (Section 3). In this section, we present an abstract representation of a rating system, that allows us to analyse the relevant aspects without dissolving in details.

Users make decisions based on ratings. Some decisions are better than others. We take a simple notion of correctness of decisions. Users are given n choices to make a decision, of which 1 choice is the best option. The relevant part is that we have a ground truth, that the user wants to deduce.

We exemplify the theory with a simple example. The results that we present in this paper are general results for all rating systems that follow the notions from this section. However, the results are easier to interpret on a simple example (e-commerce) system: Example 1. On an e-commerce system, two similar products are offered for sale. The user has three options: buy product x, buy product y, or buy neither. In the e-commerce system, another buyer can fulfill the role of advisor, and assign scores of 1 -5 stars to x, y, neither or both. Each of these (combinations of) scores may imply something about the user's decision, hence the abstract rating must contain each. Thus, there are 1 (neither) plus 5 (just x) plus 5 (just y) plus 5 • 5 (both), which is 36, possible ratings. An honest advisor provides a rating that -at the very least -correlates with the correct decision. Here, if buying x is the best option for the user, then an honest advisor is more likely to assign 5 stars than 1 star to x. Some participants may have a hidden agenda, for example, to boost sales of product y. These participants provide ratings strategically, and we call them attackers.

The example shows that the actual details of the decision are not very important. The relationship between the abstract honest ratings and the decision is crucial for users. In this paper, we assert an arbitrary non-independent relationship between honest ratings and the decision. We do not concretely model this relationship (contrary to e.g. [?]).

Formal Model

A user makes a decision by picking one option from the ratings. And he tries to select the best option. We simply model the decision as a random variable, with its (unknown) outcome representing the (unknown) best option. The outcomes of a decision consists of a set of options O -= {0, . . . , n -1}). We use the random variable Θ over the options O -to denote the best option. Thus, P (Θ = θ|φ) is the probability that θ is the best option, when φ is given.

A rating has a certain format, it could be a number of stars (i.e. discrete and ordered), a list of tags (i.e. discrete and not ordered) or a real value in some range. On an abstract level, the structure is actually not that relevant. Specifically, it is only relevant when constructing an aggregation mechanismwhich is not the purpose of this paper. We consider a rating format to be a set of scores R, and a rating to be a random variable R, which has the property that it says something about Θ when the advisor is honest. To accommodate for multiple advisors giving ratings, let A = 0, . . . , m -1 be the set of advisors, and let R j be the rating provided by j ∈ A. We use R A to mean R a0 , . . . , R a k for {a 0 , . . . , a k } = A ⊆ A.

Advisors can be honest or malicious. We introduce the status of advisor a, which is honest ( ) or malicious (⊥), as a random variable S a . An honest advisor would typically not give the same rating as a malicious advisor. We introduce R and R, both over R, to represent the rating an honest or malicious advisor would give. Thus, R a = R a whenever S a = , and R a = R a whenever S a = ⊥. We shorthand the prior probability that a is honest as P (S a ) = s a . As we reason about a trust system, we assert 0 < s a < 1.

In the running example, we mentioned that the honest advisors' ratings say something about the best option (decision). We distil that notion by saying Θ is not independent from honest advisors' ratings A ⊆ A: P (Θ) = P (Θ| R A ). Another way to phrase this, is to say that honest advisors' ratings leak information about the decision. We need to use information theory to encode this notion [?]: Definition 1. Let X, Y, Z be discrete random variables. The surprisal of an outcome x of X is -log(P (x)). The entropy of X is

H(X) = E X (-log(P (x)) = i P (x i ) • -log(P (x i ))
The conditional entropy of X given Y is

H(X|Y ) = E X (-log(P (x|y))) = i,j P (x i , y j ) • -log(P (x i |y j ))
The mutual information of X and Y is

I(X; Y ) = E X,Y (log( P (x, y) P (x)P (y) )) = i,j
P (x, y) log( P (x, y) P (x)P ( y) )

The conditional mutual information of X and Y given Z is

I(X; Y |Z) = E Z (I(X; Y )|Z) = i,j,k P (x, y, z) log( P (x, y|z) P (x|z)P (y|z) )
Information leakage of Y about X (given Z) is the (conditional) mutual information of X and Y (given Z). Information leakage is the difference in the information about X when Y is given and not given:

I(X; Y ) = H(X)-H(X|Y ), or I(X; Y |Z) = H(X|Z) -H(X|Y, Z) [?]. Information leakage is non-negative.
Information theory allows us to rewrite the link between honest ratings and correct options as conditional information leakage:

I(Θ; R A |S A = ) =H(Θ|S A = ) -H(Θ|R A , S A = ) = θ p(θ|S A = ) - r A p(r A ) θ p(θ|r A , S A = )
We assume honest ratings are always correlated with correct options, hence there is always conditional information leakage:

I(Θ; R A |S A = ) > 0.
Now, the dishonest advisors select R j such that I(Θ; R A |Φ) is minimised for given Φ (such as Φ = S A ). The term, I(Θ; R A |Φ), quantifies how much the ratings say about the optimal option.

I(Θ; R A |Φ) =H(Θ|Φ) -H(Θ|R A , Φ) = θ p(θ|φ) - r A ,φ p(r A , φ) θ p(θ|r A , φ)
We can use Example 1 to showcase parts of the formalisation: Example 2. In Example 1, option "buy x" becomes 0, "buy y" 1 and "nothing" 2. The decision outcomes are {0, 1, 2} . We have 4 advisors, {0, 1, 2, 3}, and 0, 1 are suspicious with P (S 0 ) = 0.2, P (S 1 = 0.3), and 2, 3 are not with P (S 2 ) = 0.8, P (S 3 ) = 0.9. Ratings can be any of {(r, s)|r, s ∈ {∅, 1, 2, 3, 4, 5}}.

Controlled Parameters

In the case of a centralised system, the designer himself can make these decisions.

For decentralised systems, it may be users themselves to make decisions. In the latter case, the designer of the system should try to encourage users to make the right decisions. Either way, it is important to have theoretically rigourous guidelines to make robust decisions. Here, we look at the parameters of a system that can or cannot be controlled.

In this paper, we take the viewpoint of any party that wants to increase the robustness of the system. We refer to the parties that want to increase the minimal information leakage as the defender. For example, when we say "under the defender's control", we mean that the user, the designer or any party that strives for robustness controls it.

The set of advisors A is not under the defender's control. Moreover, for any advisor a ∈ A, the random variables S a , R a , R a and R a cannot be controlled. However, the defender can blacklist/whitelist a subset of the advisors. Formally, the defender can choose A ⊆ A in I(Θ; R A ). Moreover, in some systems, the defender can monitor which advisors potentially have information (e.g. which advisors have performed relevant transactions). If random variable K a captures this fact for advisor a, then the defender may choose to have K A as a condition: I(Θ; R A |K A ). Finally, the advisor may be able to change the actual decision, thus changing (the size of) the random variable Θ.

Limited Information Implies Inaccuracy

For the conclusions in this paper to hold relevance, we need to show that limited information leakage leads to limited accuracy. We do so constructively. In other words, we construct the best possible opinions that can result from given information leakage and some aggregation mechanism, and show that the accuracy of these opinions is limited by the amount of information leakage.

An opinion is an assignment of probability to each of the options in a decision. An opinion is said to be accurate, when the probability assigned to the right option is high. One way of measuring this is to take the cross entropy: Definition 2. For discrete random variables X, Y with the same support, the cross entropy is

H cross (X, Y ) = E xi (log(P (y i )) = - i P (x i ) log(P (y i ))
The Kullback-Leibler divergence is

D KL (X||Y ) = H cross (X, Y ) -H(X) = i P (x i ) log P (x i ) P (y i )
The cross entropy (and Kullback-Leibler divergence) is a standard tool to measure the quality of an approximation Y of the true distribution X. Specifically, the cross entropy takes the expectation of the surprisal one has under the approximation Y . An advantage of Kullback-Leibler divergence is that the term -H(X) translates the values, such that 0 divergence occurs when X ∼ Y . Moreover, Kullback-Leibler divergence must be non-negative. We use cross-entropy to measure accuracy. Let O : O -→ [0, 1] such that θ∈O -O(θ) = 1 be an opinion. The accuracy of an opinion O isi P (Θ = i) log(O(i)). The accuracy of O is limited by the information leakage of Θ. Specifically, given ratings R, no matter how we select O, its accuracy cannot exceed a certain value, namely H(Θ|R). The theorem must state that O's accuracy cannot exceed a threshold determined by the information leakage.

Theorem 1. There is no opinion O, such thati P (Θ = i|R) log(O(i)) exceeds the threshold H(Θ) -I(Θ; R).

Proof. Using only standard notions from information theory: First, note H(Θ)-I(Θ; R) = H(Θ|R). Second,i P (Θ = i|R) log(O(i)) = H(Θ|R) -D KL (Θ||O), which suffices, since D KL (Θ||O) ≥ 0.

Minimising Information Leakage

By definition, when all users are honest, there is non-zero information leakage. After all, if all users are honest I(Θ; R A ) = I(Θ; R A ) > 0. However, if some users are malicious, then there may not be information leakage. Formally: Proposition 1. There exist A, Θ, R, R, S, such that I(Θ; R A ) = 0.

Proof. Take A = {a, b}, P (Θ=0) = 1 /2 = P (Θ = 1), P ( R=Θ) = 1, P ( R=1 -Θ) = 1 and P (S a =h) = P (S b =h) = 1 /2. Obviously, honest ratings leak (1 bit of) information, however, the actual ratings leak no information (about Θ).

On the other hand, it is not guaranteed for all A, Θ, R and S, a malicious strategy exists that achieves zero information leakage: Proposition 2. There exist A, Θ, R, S, such that for all R, H(Θ)-H(Θ|R A ) > 0.

Proof. Take A, Θ, R as in Proposition 1, but P (S a =h) = P (S b =h) = 0.51. Now

P (Θ = 1|R a = 1, R b = 1) ≥ P (Θ = 1, S a = h, S b = h|R a = 1, R b = 1) ≥ 0.51.
Under certain specific circumstances, it is even possible to deduce exactly when it is possible for malicious advisors to block information leakage. The quantities depend on the exact assumptions. In [?,?,?], we looked at cases where the ratings perfectly match the option (i.e. full information leakage for honest users). For example, if malicious advisors are static and independent, the average probability of honesty must be below 1 /n, for n options [?]. In this paper, we do not quantify values, but study their relationships.

It may be possible for attackers to block information leakage (Proposition 1), but it may also be impossible (Proposition 2). Does the latter imply that there is no harmful attack? To answer that, we must determine the existence of an attack, such that the information leakage with the attack is lower than without. In fact, such an attack must always exist, provided that there is at least one user that has non-zero probability of being malicious.

Theorem 2. For all A, Θ, R, S, there exists R such that I(Θ; R A ) < I(Θ; R A ).

Proof. Since I(Θ; R A ), Θ and R A are not independent, and there exists θ, r A , such that P (θ| r) > P (θ) + and P (θ| r ) < P (θ) -for some other rating r .

Take P ( R = r|θ) = P ( R = r|θ) -, and P ( R = r |θ) = P ( R = r |θ) + . All summands but two remain the same: P (θ, r) log P (θ| r) + P (θ, r ) log P (θ| r ) are closer to their average, we can apply Jensen's inequality to get the theorem.

So far, we have proven that some attacks may block all information leakage, but that such an attack may not exist, and that, nevertheless, a harmful attack must exist, except in trivial cases. These results suggest the possibility that all attacks reduce information leakage. However, this is not the case. There exist attacks that increase the information leakage:

Proposition 3. There exist A, Θ, R, R, S, such that I(Θ; R A ) > I(Θ; R A ).
Proof. Take A and Θ as in Proposition 1. Take P ( R = Θ) = 0.6, P ( R = Θ) = 0.7 and 0 < P (S A ) < 1. The inequality is satisfied with these values.

Notice that in the proof of Proposition 3, the information leakage of R is (strictly) greater than R. This is a necessary condition for an attack not to be harmful. However, it is not a sufficient condition. If we had taken P ( R = Θ) = 0.3, then the information leakage of R remains the same, but the information leakage of R decreases (as long as P (S) is not close to 0).

A realistic scenario where Proposition 3 could apply, is a camouflage attack. In the camouflage attack, an advisor provides high quality ratings (i.e. high information leakage), to gain trust, and later abuses the trust for a specific goal. In [?], we have studied these camouflage attacks, and identified that an existing attack is actually not harmful. Furthermore, we found that a probabilistic version of the camouflage attack can minimise information leakage.

If we want a trust system to be robust, then it must be able to deal graciously with the all malicious ratings, including the ones that minimise information leakage. The ratings that minimise information leakage are referred to as the minimal R A . Which ratings minimise information leakage depends on A, Θ, R A and S A .

Design Guidelines

This section is the core of the paper. Here, we study choices that one can make to mitigate unfair rating attacks. This section is divided into subsections, each of which considers an individual choice. To give a quick overview of the results: 1. It is not helpful to block seemingly malicious advisors, and often counterproductive. 2. When the number of advisors is limited, seemingly honest advisors should be preferred. 3. Disregard advisors that should not have information about the decision; e.g. buyers that never bought from a seller. 4. When forced to choose between two seemingly equally honest advisors, the better-known advisor should be preferred. 5. Different groups of honest advisors whose ratings may have the same information leakage, but different robustness towards attackers. We find a property that characterises the robustness of ratings from equally informative groups of honest advisors. This shows that for a reasonable way to increase the size of a decision, information leakage increases.

In the relevant sections, we not merely show the results, but, more importantly, we analyse and interpret them. Some our suggestions are already widely adopted. However, they are adopted for reasons other than robustness. Moreover, our guidelines are based on a solid information-theoretic foundation.

Blocking Malicious Advisors

Theorem 2 states that the minimum information leakage of ratings is strictly smaller than the honest ratings. So problematic attacks reduce information leakage. Perhaps, we can robustly increase the information leakage, by blocking suspicious advisors. On the other hand, blocking suspicious advisors may decrease the information leakage, as even a suspicious advisor may provide honest ratings. We show in this section, that the latter holds: Blocking malicious advisors does not increase the robustness against unfair rating attacks. First, we start with a weak version of the theorem, that directly refutes the intuition that sufficiently suspicious advisors must be blocked. We introduce a threshold of suspicion c, such that only those ratings from advisors at or above the threshold are considered. If indeed it helps to block sufficiently suspicious advisors, then such a c must exist. However, this is not the case: Proposition 4. For all A, Θ, R, R and S, there is no threshold c ∈ [0, 1], with A ≥c ⊆ A as the set of advisors such that s a ≥ c, such that

I(Θ; R A ≥c ) > I(Θ; R A ). Proof. Since H(X|Y, Z) ≤ H(X|Y ), -H(Θ|R A ≥c ) ≤ -H(Θ|R A ).
Proof. The attacker can select R A such that P (R A = x|ϕ) = P (R A = x|ϕ), for any condition ϕ. The minimum information leakage is at most equal to the construction's information leakage.

Design Hint 2 When there is a cost to gathering too many ratings, then seemingly more honest advisors should be asked before more suspicious ones.

Unknowing Advisors

The first question is, whether it is useful to be aware of whether advisors could have knowledge. We introduce a random variable K a , such that K a = 0 if a does not have knowledge, and K a = 1 if a may have some knowledge. Formally, I(Θ; R a |K a = 0) = 0 and I(Θ; R a |K a = 1) > 0. Now we can reason about the difference in information with and without K a as a condition: I(Θ; R A ) is the information leakage without knowing whether advisors could have knowledge, and I(Θ; R a |K) is the expected information leakage when we know whether advisors could have knowledge. In fact, in the latter case, we have at least as much information leakage: Based on that result, we can revisit the notion of blocking users. Should we block unknowing advisors? It turns out that blocking unknowing advisors never changes information leakage: Corollary 1. For arbitrary conditions ψ, ϕ, and a ∈ A, Θ, R a , K a , we have I(Θ; R a , ψ|K a = 0, ϕ) = I(Θ; ψ|ϕ) Proof. Since I(Θ; R a |K a = 0, ϕ, ψ) = 0, the optimal strategy for the malicious advisor is to set R a to satisfy I(Θ; R a |K a = 0, ϕ, ψ) = 0, which implies I(Θ; R a |K a = 0, ϕ, ψ) = 0. Then, R a can be eliminated without loss of generality, and then also K a .

Design Hint 3 When possible, keep track of whether an advisor can provide useful advise; e.g. because he actually performed a transaction. Advisors that cannot provide useful advise can be filtered out without loss of generality.

Newer Advisors

Throughout the paper, we have ignored previous ratings. However, as we show in [?], if we learn about the correctness of an advisor's rating in hindsight, then we learn about the status of that advisor. Concretely, for some random variable Q, if P (Q = 1|R a = R a ) > P (Q = 1|R a = R a ), then P (S a |Q) = P (S a ). Here Q corresponds to the probability that an advisor's rating is correct in hindsight.

To keep the notation simple, we did not introduce Q previously. Here, we need it to prove a theorem.

For an honest user, R a is always equal to R a , and an attacker may or may not set R a equal to R a (by selecting R a = R a ). Often, there may be multiple Q's per advisor, so we use Q ≤i a to denote Q 1 , Q 2 , . . . , Q i . Let a, a be advisors, such that P (S a |Q ≤i a ) = P (S a |Q ≤j a ) and i < j. Then, a and a are equally suspicious (their statuses are equiprobable with the given conditions), but a is a newer advisor than a . For the current rating, a and a are equally useful (as they are equally likely to be honest), but if the current rating will be correct in hindsight, then a loses suspicion quicker than a .

For example, let a be completely new -its suspicion is the prior P (S a )and a be older, but have both seemingly correct and seemingly wrong ratings in hindsight, such that P (S a |Q) = P (S a ). Clearly, if we got a seemingly correct rating from a in hindsight, its suspicion level changes much more radically than when the rating of a was correct in hindsight. The same holds if the rating was seemingly wrong. However, if we only select a or a , then the other advisor's suspicion level remains unchanged. Therefore, if we must select either a or a and both are equally suspicious, then we should prefer the newer advisor.

To formalise this concept, measure the information leakage over two ratings, where we switch advisor if their ratings seemed wrong in hindsight: Theorem 6. For a, a , such that P (S a |Q ≤i a ) = P (S a |Q ≤j a ) and i < j:

I(Θ; R a |Q ≤i a ) + P (Q=0|R a , Θ) • I(Θ; R a |Q ≤j a ) + P (Q=1|R a , Θ) • I(Θ; R a |Q ≤i a , Q=1) ≥ I(Θ; R a |Q ≤j a ) + P (Q=0|R a , Θ) • I(Θ; R a |Q ≤i a ) + P (Q=1|R a , Θ) • I(Θ; R a |Q ≤j a , Q=1).
Proof. Note that since I(Θ; R a |Q ≤i a ) = I(Θ; R a |Q ≤j a ), all terms on both sides are equal, except I(Θ; R a |Q ≤i a , Q) and I(Θ; R a |Q ≤j a , Q). Hence it suffices to prove I(Θ; R a |Q ≤i a , Q=1) ≥ I(Θ; R a |Q ≤j a , Q=1). The Q's are independent of Θ, meaning that it suffices to prove H(Θ|R a , Q ≤i a , Q=1) ≤ H(Θ|R a , Q ≤i a , Q=1). Now, P (Θ|R a , Q ≤i a , Q=1) = P (Θ|R a , S * ), with S * a S a |Q ≤i a , Q=1, and similarly on the other side. Thus, if E(S * a ) ≥ E(S * a ), then the theorem follows. Since the Q's are Bayesian updates, we can model S * as a Beta distribution times an arbitrary prior. The expectation of the Beta distribution is p+1 p+n+2 , which is more sensitive to increasing p when p + n is small. Design Hint 4 When two advisors appear equally likely to be honest, but only one may provide a rating, then the advisor with whom we have the shortest history should be preferred.

More Options

The defender may want to increase the robustness of the rating system, by changing the rating format or the number of choices in a decision. There is an immediate problem when formalising this idea, which is that we have not formalised how honest users respond when either the domain of Θ or R changes. Naively, we may simply assert that the information leakage of honest ratings remains unchanged. Thus I(Θ; R A ) = I(Θ ; R A ). However, the robustness of the system on the left is not equal to that on the right. Theorem 7. For given A, Θ, Θ , R, R with minimising R and R , I(Θ; R

A ) = I(Θ ; R A ) does not imply I(Θ; R A ) = I(Θ ; R A ). Proof. Let the prior P (Θ) = P (Θ ) = 1 /3. Moreover let P (Θ = i| R A = i) = 1 /2 and P (Θ = i| R A = i) = 1 /4; meaning I(Θ; R A ) = 1.5. Then, we let P (Θ = i| R A = i) = 7 /
15, then it follows from the fact that the information leakage is 1.5 that P (Θ = i| R A ≡ 3 i + 1) ≈ 0.195 ≈ 1 /5 and P (Θ = i| R A ≡ 3 i + 2) ≈ 0.338 ≈ 1 /3 (or vice versa). See Figure 1. When P (S A ) ≈ 5 /7, we can achieve 0 information leakage by setting P (Θ = i| R A ≡ 3 i+1) = 1 /3, and P (Θ = i| R A ≡ 3 i+1) = 2 /3, then it follows that P (Θ |R A ) = 1 /3 = P (Θ = i). Thus, for P (S A ) ≈ 5 /7 we have 0 information leakage for Θ , but since P (Θ = i|R A = i) ≥ P (Θ = i| R A = i) • 5 /7 = 5 /14, P (Θ = i|R A = i) = 1 /3 = P (Θ = i), there is non-zero information leakage for Θ. Hence their robustness is different.

The proof is visualised in Figure 1, where the yellow/light bars are the honest ratings, and the blue/dark bars are the overall ratings. The honest ratings have the same information leakage in both graphs, whereas the overall ratings clearly do not.

More choices generally mean more information leakage. However, as proven in Theorem 7, special circumstances must be met when expanding Θ. In particular, Θ is expanded together with R in an orthogonal way -the additional options have their own corresponding ratings: Intuitively, one of two ratings can happen, if the additional rating occurs, the user gains a lot of information -namely that the additional option occurred. The remaining cases do not involve the new rating or choice, and remains essentially unchanged (only linear weights change proportionally).

Design Hint 5 Increasing the number of options in a decision is good, assuming that the additional options are sufficiently distinctive for the advisors. Care should be taken, because additional options may harm robustness in some cases.

Conclusion

Users form opinions based on ratings. Systems that allow more accurate opinions are better. We use cross entropy (or Kullback-Leibler divergence) to measure the accuracy of opinions. The maximum accuracy is limited by a quantity called information leakage. Information leakage measures how much a rating tells about the decision a user wants to make.

The amount of information leakage of honest ratings has a certain non-zero quantity. Thus, we assume that there is some correlation between honest ratings and what the best decision is. We cannot make such assumptions about ratings from attackers. Attackers have a hidden agenda that they base their ratings upon. We want to reduce the negative effect that attackers have on the information leakage. To be on the safe side, we assume that attackers rate in the way that minimises the information leakage -any other behaviour results in at least as much information leakage.

Our model of a rating system is abstract. Decisions and ratings are abstract entities. Ratings are not under the control of the defender. However, the defender can select which advisors to use, potentially monitor whether an advisor may be knowledgable, and consider more options in his decision. Our main contribution is a set of guidelines for the defender to use these factors in his advantage.

Our main guidelines are: Blocking suspicious advisors can only decrease robustness [START_REF] Thomas | Entropy, relative entropy and mutual information[END_REF]. If only a limited number of ratings can be used, however, then less suspicious advisors are better [START_REF] Fang | Misleading opinions provided by advisors: Dishonesty or subjectivity[END_REF], and in case of a tie, newer advisors are better [START_REF] Hu | Fraud detection in online consumer reviews[END_REF]. Observing transactions increases robustness [START_REF] Jøsang | A survey of trust and reputation systems for online service provision[END_REF]. Offering more choices may increase robustness [START_REF] Jurca | Minimum payments that reward honest reputation feedback[END_REF].

Theorem 5 .

 5 For all A, Θ, R A and K,I(Θ; R A ) ≤ I(Θ; R A |K) Proof. Since H(Θ|K) = H(Θ), I(Θ; R A |K) = I(Θ; R a , K).And additional conditions do not increase entropy, hence I(Θ; R A , K) ≥ I(Θ; R a ).

Fig. 1 .

 1 Fig.1. Two ratings (blue), the corresponding honest ratings (yellow), with the values of θ on the x-axis, and the corresponding probability on the y-axis.

Theorem 8 .

 8 Given two rating systems that one has more options for ratings and choices:|Θ| = |Θ | + 1, |R A | = |R A | + 1, if p(θ|r) = p(θ |r), then I(Θ; R a ) can be equal, or larger than I(Θ ; R a ) Proof. Let p(θ|r) = 0 for either θ>|Θ | or r>|R A |, except that there is a ṙ > |R A | and a θ > |Θ |, for which p( θ| ṙ) = 1. We get H(Θ) = H(Θ ) -f (p( ṙ)), and H(Θ|R a ) = H(Θ |R a ) -p( ṙ) • f (p( θ| ṙ)) = H(Θ|R a ). Given p( ṙ) ≥ 0, H(Θ) -H(Θ|R a ) ≥ H(Θ ) -H(Θ |R a ). Hence, I(Θ; R a ) ≥ I(Θ ; R a ).

For a pair c < d, we can let A = A ≥d and automatically A ≥c = A ≥c , and the proposition applied to A proves that I(Θ; R A ≥c ) > I(Θ; R ≥d A ). Therefore, Proposition 4 proves monotonicity of I(Θ; R A ≥c ) over c.

For the vast majority of thresholds, however, blocking suspicious advisors is not just ineffective, but actually harmful. Thus, for some (small but nonzero) blocking thresholds, blocking does not alter information leakage, but for most thresholds -including all thresholds over 1 /2 -blocking strictly decreases information leakage: Theorem 3. For all A, Θ, R, S and minimal R, there exists a threshold d ∈

Proof. Note that if c = 0 then trivially the equality holds, and if c = 1, then the equality trivially does not hold, since s a < 1, A ≥c = ∅ and thus I(Θ; R A ≥c ) = 0 < I(Θ; R A ). Using the monotonicity proved in Proposition 4, it suffices to prove the equality for c = 1 n : Now

Arguably, Proposition 4 is not particularly interesting from an informationtheoretic perspective -although it may be somewhat surprising superficially. After all, meaningless additional information does not decrease the information leakage. However, Theorem 3 strengthens the result to say that there exists a level of suspicion below which blocking is harming robustness. In [?,?], we show that for typical systems, this threshold is very low.

Design Hint 1 Unless the suspicion that an advisor is malicious is extremely high, blocking a suspicious advisor is either useless or counterproductive for robustness.

More Honest Advisors

The reason that blocking advisors does not help is the simple theorem that more random variables in the condition cannot decrease information leakage. However, clearly, a seemingly honest advisor contributes more information than a suspicious one. There may be a cost associated to requesting/receiving too many ratings, or other reasons why the number of advisors is limited. In these cases, we expect that preferring those advisors that are more likely to be honest is better for gaining information.

Take two near-identical trust systems, that only differ in the degree of honesty of the advisors. The decisions and honest ratings remain the same, and the attacker minimises information leakage on both sides. Then, the more honest system has higher information leakage:


Tim Muller

Yang Liu

Jie Zhang

Limitations on Robust Ratings and Predictions

Predictions are a well-studied form of ratings. Their objective nature allows a rigourous analysis. A problem is that there are attacks on prediction systems and rating systems. These attacks decrease the usefulness of the predictions. Attackers may ignore the incentives in the system, so we may not rely on these to protect ourselves. The user must block attackers, ideally before the attackers introduce too much misinformation. We formally axiomatically define robustness as the property that no rater can introduce too much misinformation. We formally prove that notions of robustness come at the expense of other desirable properties, such as the lack of bias or effectiveness. We also show that there do exist trade-offs between the different properties, allowing a prediction system with limited robustness, limited bias and limited effectiveness.

Introduction

Ratings are an important tool in online cooperation. Ratings are used in, e.g., recommender systems, trust and reputation systems, e-commerce systems and security systems [START_REF] Hoffman | A survey of attack and defense techniques for reputation systems[END_REF][START_REF] Weng Jianshu | An entropy-based approach to protecting rating systems from unfair testimonies[END_REF][START_REF] Jøsang | A survey of trust and reputation systems for online service provision[END_REF]. We reason about a specific type of predictions, namely those that we can judge in hindsight -called predictions. Prediction are also an interesting topic of research in themselves [START_REF] Kenneth J Arrow | The promise of prediction markets[END_REF]. Typically, users that give predictions that are better (accurate or honest) are rewarded by becoming more credible. However, there are incentives outside of the system that may drive a user to give worse (inaccurate or dishonest) predictions. These unfair ratings attacks are well-known in literature, and found to occur in real systems. On a robust prediction system, the impact of these unfair ratings is limited.

A standard technique in prediction systems is to have a mechanism to encourage users to behave in a certain way, by setting the right incentives. However, in practice, users may have a bigger incentive to give bad predictions. We know that users attack systems by providing false predictions [START_REF] Hanson | Information aggregation and manipulation in an experimental market[END_REF][START_REF] Snowberg | Partisan impacts on the economy: evidence from prediction markets and close elections[END_REF] despite losing credit within the system. A user that ignores the incentives of a system is called an attacker. In other words, an attacker does not necessarily care about the rewards and punishments that the prediction system sets, because incentives outside of the system (e.g. bribes, collusion) are greater.

As we cannot modify the behaviour of these attackers, we must resort to interpreting the predictions in a robust fashion. Specifically, we must somehow limit the impact of unfair ratings. In this paper, we introduce notions of robustness (differing in strength) that codify that the amount of noise that a single agent can introduce is limited. We have a threefold motivation for the exact formulations: intuitive grounds, information theory and hypothesis testing. Given our definition of robustness, we can prove a specific prediction system to be robust.

Robustness comes at a cost. With no tolerance towards misinformation, any useful way of using predictions is impossible. For weaker robustness requirements, we have more subtle impossibilities regarding the use of predictions. One main contribution in this paper is a general and rigourous proof that robustness, bias and effectiveness are tradeoffs, and that certain combinations are impossible. The proofs are axiomatic, meaning that we have axioms for the various levels of robustness, bias and effectiveness, and we prove that no model can satisfy all of them. Specifically:

-No meaningful model exists for absolute robustness (no tolerance towards misinformation). -Any model for strict robustness (fixed misinformation threshold) has some bias and a finite lifespan. -Any model for weak robustness (growing tolerance towards misinformation) has some bias and cannot be fully effective.

The results are summarised in Table 1.

Fortunately, if we are willing to make the trade-offs, then robust models do exist. We show that a prediction system with strict robustness can exist and be useful despite its hampered effectiveness. Similarly, we also show that a prediction system with weak robustness can be implemented and be far more effective. These results extend only to prediction systems, since they rely on the user knowing the validity of the predictions after the fact.

The paper is organised as follows. First we discuss work related to our domain, but also impossibility results in social choice which inspired the methodology. In Section 3, we present the requirements that we want a prediction system to fulfill, in natural language. Then, in Section 4, we present a formal model of predictions, events, filters and misinformation. In Section 5, we formalise the requirements in that model. In Section 6, we establish the relationships between the axioms -particularly we close the bridge between the information-theoretic and the statistical perspective on the quality of predictions. In Section 7, we prove the impossibility results. All the limitations of robust prediction systems can be found in this section. In Section 8, we prove the existence of prediction systems that have robustness, albeit with considerable reduction of effectiveness. In these latter two sections, non-technical formulations of the results are presented in bold font. We provide a conclusion in Section 9.

Related Work

Our original research interest lies in robust ratings, as e.g. in [START_REF] Wang | Using information theory to improve the robustness of trust systems[END_REF][START_REF] Wang | Is it harmful when advisors only pretend to be honest[END_REF]. There, the ratings are quantified using information theory. This idea is not novel, as e.g. [START_REF] Weng Jianshu | An entropy-based approach to protecting rating systems from unfair testimonies[END_REF] also uses information theory to quantify ratings. Our novelty is that we are able to formulate a system with a strict robustness cutoff. The damage of attacks is strictly limited. However, for the system to work, the ratings must be predictions -verifiable in hindsight.

WU SU WU & T SU & T T AR 0 0 0 0 0 SR(θ) 2 θ 0 θ 0 θ WR(f ) > 2 f (1) 0 f (n) 0 f (n)
Prediction systems are widely used and studied [START_REF] Berg | Prediction market accuracy in the long run[END_REF][START_REF] Kesten C Green | Methods to elicit forecasts from groups: Delphi and prediction markets compared[END_REF]. An important type of prediction system is a prediction market. There has been lots of research on prediction markets, especially their resistance against manipulation [START_REF] Buckley | The effect of malicious manipulations on prediction market accuracy[END_REF][START_REF] Deck | Prediction markets in the laboratory[END_REF][START_REF] Hanson | Information aggregation and manipulation in an experimental market[END_REF]. An inherent problem of prediction markets is that raters insensitive to the system's incentives have absolute freedom to manipulate [START_REF] Buckley | The effect of malicious manipulations on prediction market accuracy[END_REF][START_REF] Deck | Prediction markets in the laboratory[END_REF]. Our approach limits the influence of individual raters, without taking away the ability to predict.

We formulate a set of axioms that we want prediction systems to satisfy. That approach is inspired on social choice theory [START_REF] Taylor | Social choice and the mathematics of manipulation[END_REF]. Arrow's impossibility theorem [START_REF] Arrow | Social Choice and Individual Values[END_REF] states that the result of a vote must 1) have X over Y if all prefer X over Y , 2) let the order of X and Y be independent of Z and 3) there is no dictator. In fact, robustness against manipulation is also a well-studied issue there [START_REF] Taylor | Social choice and the mathematics of manipulation[END_REF]. Our axioms are fundamentally different, but the idea that certain combinations of axioms do not admit a model is directly taken from social choice theory.

Axiomatic Requirements

A trust system is robust, when it operates well under attacks. A common way to increase the robustness of the system, is to try to detect attacks. While such detection mechanisms certainly mitigate attacks, they cannot prevent them, by their nature. A detection mechanism detects attacks that have already occurred (at least partially). Ideally, however, we can prevent the attacks from occurring in the first place.

In this paper, we are concerned with attacks that introduce misinformation to the users. However, first, not all attacks induce noise towards the user, but break the system in other ways (e.g. the reputation lag attack [START_REF] Kerr | Smart cheaters do prosper: defeating trust and reputation systems[END_REF], where the attacker exploits a time delay before his infamy is spread) 1 . Thus, we only consider attacks by strategic unfair predictions. Second, not all unfair prediction attacks are harmful (e.g. the camouflage attack, where users are honest to gain trust, and betray others when trusted; see [START_REF] Wang | Is it harmful when advisors only pretend to be honest[END_REF]). We ignore attacks that do not introduce noise to the user; attacks that do not (aim to) deceive users. Rather, we look at gathering predictions in a robust manner.

The requirements in this section are informally defined using natural language. Later, we formally define our terminology, and translate the requirements to formal statements. For the sake of precision, we fix the meaning of some terms: A prediction is a statement about an event before it occurs. An event has an outcome, after which the degree of correctness of the prediction is known. Noise is the inverse of that degree of correctness. A rater is an agent (human or system) that produces predictions. Ratings are accurate when they assign the true (subjective) probabilities to outcomes (i.e. outcomes assigned x% happen x% of the time), and raters are accurate when they produce accurate ratings. See Section 4 for a more formal definition of the terminology.

Robustness Requirements

Consider the strictest formulation of robustness, called absolute robustness (AR): No rater may introduce noise. Note that AR implies that no group of raters may introduce noise either. Intuitively, AR seems too strong. If no predictions can introduce any noise, no matter how small or improbable, then how can the rater make any meaningful predictions? In fact, in Section 7, we prove this intuition correct; no non-trivial system can be absolutely robust.

The generalisation of absolute robustness is θ-strict robustness (SR): No rater may introduce noise larger than θ. Note that SR implies that no group of raters sized n may introduce noise larger than θ • n. Strict robustness is also a strong axiom, and it is somewhat workable, although it negatively affects other aspects of the system. Particularly, due to the fixed-size tolerance of noise, and the inevitability of noise, any rater can only provide a limited number of predictions. We refer to this property as effectiveness, and its axiom is stated below.

Strict robustness can be weakened, e.g. by allowing more noise. Finally, we weaken robustness to f -weak robustness (WR), where f is a non-decreasing function: In the first n selected predictions, no rater may introduce noise larger than f (n). Weak robustness is a generalisation of strict robustness (let f be a constant function). Here, good (selected) predictions from the past give the rater some credit. Picking f (n) = n • θ would encode that the average noise is limited by θ. Whether weak robustness is sufficient is debatable, but we should expect increased effectiveness for some f .

We formulate a radically different notion of robustness, based on hypothesis testing. The idea is that one initially assumes perfect accuracy (null hypothesis), and that the null hypothesis may be rejected in favor of any alternative hypothesis if the data is unlikely to fit the predictions. The hypothesis testing variant of robustness is (HR): The probability of a sequence of events, given that the predictions are accurate, must not go below α. We show later that SR = HR, when α = -2 θ .

Remark 1. Note that we are not subjecting the rater to a single statistical test, but to many. Then, we require that the rater cannot fail any of the statistical tests. This models the notion that we do not know what kind of attack the rater may be performing (i.e. what the alternative hypothesis is). For every sequence of outcomes there is one statistical test, where H 0 is that the rater accurately predicts it, and H 1 is that the rater underreports it. For each individual statistical test, the probability of falsely rejecting H 0 is bounded by α. Since we have multiple tests, the probability that at least one test rejects H 0 can (and does) exceed α.

Auxiliary Requirements

The system that needs to be robust must also have a variety of other properties. The filter should not introduce bias, it must not rely on foreknowledge, and it must not exclude excessively many predictions.

The first requirement is that the system must be implementable -it cannot make decisions based on future events. Specifically, users cannot be prescient (T): Whether a prediction is used should not depend on its outcome, nor on future predictions or outcomes. There are combinations of requirements that are logically non-contradicting, but that contradict T. Rejecting T means asserting prescience. Such systems cannot be implemented in a meaningful way, since the purpose of the prediction was to be able to act before the future happened. Note that T does not exclude analysing a prediction in the future, it just prohibits users from using such a future analysis in the present.

Another property of a selection mechanism is that it should not be biased. The ideal notion of unbiasedness, called strictly unbiased (SU) states: A prediction from a user about an event is used iff any alternative prediction from that user about that event would be used too. However, this notion may be too strong, as the mere possibility of an extreme prediction that may introduce an unacceptable amount of noise would imply that all predictions must be blocked. Hence we formulate (weakly) unbiased selection (WU): A prediction from a user about an event is used iff the opposite prediction from that user about that event would be used too. This notion matches the idea that we can not "prefer" one outcome over the other, and thus that the selection mechanism mistakenly favours one side. However, weak unbiased selection may introduce a bias towards the center, meaning unlikely events may be overestimated.

Finally, the property that forms the typical trade-off with robustness: effectiveness. Effectiveness measures how many predictions can be used over the lifetime of a trust system. We formulate two incarnations of effectiveness. The first is optimistic k, n-effectiveness (OE): It is possible to select k predictions for n events. Optimistic k, n-effectiveness can be used to prove hard limits on robustness of trust systems. The second notion of effectiveness is realistic k, n-effectiveness (RE): Assuming all raters are accurate, we can expect k predictions for n events. The realistic k, n-effectiveness is used for the positive results.

Raters send predictions to users -be it by broadcasting or upon request. Predictions concern events with an outcome that will eventually be known. Users want to estimate how likely outcomes of events are, and use predictions for this purpose. After the event, users use the outcome to judge the predictors. Good predictors assign high likelihood to actual outcomes, and bad predictors assign lower likelihood.

There is a sequence P of binary events, where the i th event, denoted p i , either equals 0 or 1. The prediction of rater a about p i is r a i , which (for honest raters) represents his estimate of p(p i =1) -and

r a i = p(p i =0) = 1 -p(p i =1
). The sequence of all predictions of rater a is R a , with R a i his prediction about the i th event. For a set of raters A, we can write R A to mean {R a |a ∈ A} Together A, P and R A form a trust system.

The user has no influence on the values of the predictions or on the outcomes of the events. The only way to achieve the goal of dealing with predictions in a robust manner, is to select the right predictions from the predictions that are given. Note that blocking raters can be accomplished by never selecting that rater's predictions, regardless of the values. Thus, the focus on this paper is on selecting the right predictions. The sequence of predictions that is selected is called the sequence of filtered predictions, denoted R A (where R A is the set that R A is selected from).

Our motivating question is what the limitations are to such a filter. The filtered predictions may be biased, can we avoid such a bias? All things considered equal, a looser filter is superior, as it allows the user to consider more information. How many (sufficiently unbiased) predictions can R contain? Finally, the crucial question, can we put a hard limit on how much noise a rater can introduce?

Every prediction has an amount of information [START_REF] Weng Jianshu | An entropy-based approach to protecting rating systems from unfair testimonies[END_REF]. Information is the dual of entropy, and entropy is the expected surprisal of a random variable [START_REF] Thomas | Entropy, relative entropy and mutual information[END_REF]:

Definition 1. Let X, Y, Z be discrete random variables. The surprisal of an outcome x of X is -log(P (x)). The entropy of X is H(X) = E X (-log(P (x)) = i P (x i ) • -log(P (x i )).
Once the actual outcome p i of the event is known, we can analyse the surprisal of the prediction, which islog r a i orlog r a i , when p i = 1 or p i = 0, respectively. The surprisal of r a i given the outcome p i is denoted f (r a i , p i ) (to avoid the case distinction for p i ). With perfect information (zero entropy), the surprisal is 0, so surprisal measures noise (misinformation).

Therefore, surprisal can be used to measure the quality of a prediction (this is, e.g., the basis of the cross-entropy method [START_REF] Thomas | Entropy, relative entropy and mutual information[END_REF]). A high quality prediction assigns a higher probability to the actual outcome. But more importantly, a prediction is of low quality when a low probability is assigned to the outcome. Since a high surprisal corresponds to low quality predictions, we use surprisal to measure the noise of a prediction. However, a high degree of noise in the prediction does not necessarily mean that the rater was malicious or even in error. Raters can introduce noise by sheer bad luck.

Other measures could be used than surprisal. There are, however, two advantages being logarithmic: First, the sum of the surprisal of two outcomes of independent events is equal to the surprisal of the outcome of the joint event.

The surprisal of a combination of outcomes is the sum of the surprisal of the individual outcomes; formally log p(x) + log p(y) = log p(x, y), for independent X, Y . Second, it matches the intuition that the difference between 1% and 2% is far more significant than the difference between 50% and 51%. However, we also consider another measure for the quality of predictions, which is based on hypothesis testing; a statistical tool, rather than information theoretic.

Before continuing, we define a couple of shorthand notations. Typically, we denote predictions with r, but we may use q instead. Furthermore, we allow substitution in a sequence/set, denoted R A [r a i \ q a i ], where r a i is replaced by q a i in R A . We may want to get the index of r a i in the sequence R, which we denote as ρ R (r a i ). Finally, X Y if X is a subsequence of Y (same elements and order). These notations are particularly introduced to simplify the notation of the axioms.

Axioms

We need to have a formal model of the trust system to base the formal version of our axioms on. The idea here follows the standard approach in social choice. We formulate a generic collection of events and predictions, and prove that set of filtered predictions can satisfy a certain combination of axioms. Thus, we can show the impossibility of a combination of desirable properties.

Axiom AR -absolute robustness -must encode that "no rater may introduce noise." That axiom can be stated as:

AR : ∀ i,a r a i ∈ R a f (r a i , p i ) = 0.
Axiom SR -strict robustness -must encode that "no rater may introduce noise larger than θ." That axiom can be stated as:

SR : ∀ i,a r a i ∈ R a f (r a i , p i ) ≤ θ.
Axiom WR -weak robustness -must encode that "in the first n selected predictions, no rater may introduce noise larger than f (n)." That axiom can be stated as:

WR : ∀ n,a r a i ∈ R a ∧ρ R a (r a i )<n f (r a i , p i ) ≤ f (n).
Axiom HR -hypothesis testing-based robustness -must encode that "the probability of a sequence of events, given that the predictions are accurate, must not go below α." That axiom can be stated as:

HR : ∀ a ( r a i ∈ R a r a i ≥ α).
The product of the prediction assigned to the actual outcome is what the joint probability of the outcomes would be if the predictions are accurate. This probability may not go below α.

Axiom T -non-prescience -must encode that "whether a prediction is used should not depend on its outcome, nor on future predictions or outcomes." The axiom can be stated as:

T : ∀ i≤k,a (r a i ∈ R a =r a i ∈ R a ) ∧ ∀ i<k (p i ∈P =p i ∈P ) =⇒ (r a k ∈ R a ⇔ r a k ∈ Q a )
, whenever two trust systems are equal up to point k, they must allow the same predictions to be selected or blocked. In other words, at time k the selection cannot depend on p k+j or r a k+j , since there exists a system identical up to k steps with p k+j = p k,j and r a k+j = r a k+j . Axiom SU -strong unbiasedness -must encode that "a prediction from a user about an event is used iff any alternative prediction from that user about that event would be used too." The axiom can be stated as:

SU : ∀ i,a (r a i ∈ R a ∧ Q a = R a [r a i \ r a i ] =⇒ r a i ∈ Q a )
, every prediction from user a at time i can be replaced by another prediction from a at i.

Axiom WU -weak unbiasedness -must encode that "a prediction from a user about an event is used iff the opposite prediction from that user about that event would be used too." The axiom can be stated as:

WU : ∀ i,a (r a i ∈ R a ∧ Q a = R a [r a i \ r a i ] =⇒ r a i ∈ Q a )
, every prediction from user a at time i can be replaced by another prediction from a at i.

Axiom OE -optimistic effectiveness -must encode that "it is possible to select k predictions for n events." The axiom can be stated as:

OE :

∀ a (max i<n ρ R a (r a i ) ≥ k), there highest index of a prediction in R a with index below n in R a is at least k.

Axiom RE -realistic effectiveness -must encode that "assuming all raters are accurate, we can expect k predictions for n events." The axiom can be stated as:

RE : ∀ a, R a R a (max i<n ρ R a [ R a \ R a ]
(r a i ) ≥ k), which is similar to OE, except it must also hold if we swap arbitrary values of r a i for their negation. With the arbitrary swapping of predictions, RE captures the possibility that the actual outcome was p i , in which case the surprisal would belog(r a i ), rather thanlog(r a i ). Thus, the effectiveness here is attainable for all sequences of outcomes, rather than just one.

Relative Strength of the Axioms

With the exception of Theorem 1, all the propositions and corollaries in this section are straightforward sanity proofs. Propositions 1, 2, 3 and 4 and Corollaries 1 and 2 merely show that axioms that are supposed to be weaker are indeed weaker. The relative strength of the axioms is depicted in Figure 1 and HR(α), for α = 1 2 θ . Thus Theorem 1 shows that an information-theoretic perspective coincides with a view based in statistical methods; specifically hypothesis testing.

The first proposition shows that a lower fixed robustness threshold is a stronger requirement:

Proposition 1. If θ ≤ θ , then SR(θ) =⇒ SR(θ ). Proof. By transitivity: ∀ i,a r a i ∈ R a f (r a i , p i ) ≤ θ ≤ θ .
Proposition 1 shows that strict robustness is a weaker requirement than absolute robustness:

Corollary 1. For all θ, AR =⇒ SR(θ).
The second proposition shows that a consistently lower robustness threshold is a stronger requirement:

Proposition 2. If, for all n, f (n) ≤ f (n), then WR(f ) =⇒ WR(f ). Proof. By transitivity: ∀ i,a r a i ∈ R a f (r a i , p i ) ≤ f (n) ≤ f (n).
Proposition 2 shows that weak robustness is a weaker requirement than strict robustness:

Corollary 2. If f (1) ≥ θ, then SR(θ) =⇒ WR(f ).
The third proposition shows that no bias towards any prediction is a stronger requirement than no bias w.r.t. the opposite prediction:

Proposition 3. SU =⇒ WU Proof.
The term r a i in WU is an instance of r a i in SU, and SU dictates that substitution can be done for all r a i . The fourth proposition shows that realistic effectiveness is a stronger requirement than optimistic effectiveness:

Proposition 4. RE =⇒ OE Proof.
In RE, we can find OE by letting R a = ∅.

Finally, this section's main theorem, which shows the deep link between information-theoretic robustness and hypothesis testing robustness:

Theorem 1. If α = 1 2 θ , then SR(θ) ↔ HR(α). Proof. Note that r a i ∈ R a r a i ≥ α iff log( r a i ∈ R a r a i ) ≥ log(α).
Distributing the log over the product and negating,r a i ∈ R a log(r a i ) = -log(α). This is SR(θ) with θ = log( 1 /α).

Impossibility Results

Here, we study the relationship between the axioms. Specifically, we investigate whether certain combinations of axioms admit a non-trivial set of filtered ratings. Moreover, where applicable, we investigate what the size of the set of filtered ratings can be. Any statement made in this section is a general truth about all rating systems. The results are summarized in Table 1.

The first is the effective impossibility of a system that has absolute robustness. The only ways in which a system can be absolutely robust, is if it either never uses predictions or if it only uses predictions that predict 100% probability for the correct outcomes. The former implies an effectiveness of 0 (i.e. it is ineffective); the latter breaks non-prescience. An absolutely robust trust system without prescience is ineffective:

Theorem 2. AR + T + OE(k, n) =⇒ k = 0 Proof. Let R a be a subset of R a such that it satisfies AR. Since noise is a positive quantity, ∀ r a i ∈ R a f (r a i , p i ) = 0. Thus r a i = 1 iff p i = 1.
If R is non-empty, then we can take such a, i. Due to T, when p i = 0, R remains the same up to i. However, if p i = 0, then r a i = 1 implies f (r a i , p i ) = ∞ > 0. By T, if R is non-empty, then there exists a system that violates AR or T. Hence, R = ∅ and k = 0. This theorem (and the following) can be stated as an impossibility theorem: There is no non-prescient, effective, absolutely robust trust system.

Moreover, even if we drop non-prescience (thus using predictions given foreknowledge), the system would not even be weakly unbiased unless all predictions are ignored. In other words, if we select 100% correct predictions, we would lose (weak) unbiasedness. A weakly unbiased absolutely robust trust system is ineffective:

Proposition 5. AR + WU + OE(k, n) =⇒ k = 0
Proof. Similar to to Theorem 2, except rather than swapping p i , we swap r A i .

There is no unbiased, effective, absolutely robust trust system.

Weakening the robustness requirement to strict robustness, we finally obtain a bit of robustness. A non-prescient rating system with strict robustness can allow at most θ ratings to be selected from users:

Theorem 3. SR(θ) + T + OE(k, n) =⇒ k ≤ θ
Proof. Let R a be a sequence of r a i . Due to axiom T, the choice of r a i is independent of p i . Thus, if r a i = 1 /2, then the model must hold with noise f (r a i , p i ) and f (r a i , p i ). Without loss of generality, we can therefore assume r a i ≤ r a i . Now, via

SR(ic), θ ≥ r a i ∈ R a f (r a i , p i ) ≥ r a i ∈ R a f ( 1 /2, p i ) = k
There is no non-prescient, unboundedly effective, strictly robust trust system.

An interesting academic question is whether the fixed bound on effectiveness can be lifted when we are aware of the future. It turns out that if we replace nonprescience with weak unbiasedness, that the bound is widened, but still fixed:

Theorem 4. SR(θ) + WU + OE(k, n) =⇒ k ≤ 2 θ
Proof. As T is not an axiom, we can select r a i knowing p i . However, due to WU, f ( R a ≤k , p) + r a i must be at most θ. Let c k = θ -f ( R a ≤k , p). Then we obtain the recursive equation

c k + log(1 -1 2 c k ) = c k-1 . Via 1 -1 2 c k = 2 c k-1 -c k , and 2 c k -1 = 2 c k-1 that becomes c k = log(2 c k-1 + 1). Basic arithmetics show that c k = log(k).
There is no unbiased, unboundedly effective, strictly robust trust system.

When tightening the requirement on unbiasedness to strong unbiasedness, we lose effectiveness completely. Even without non-prescience. Thus, strict robustness and strong unbiased cannot be meaningfully combined. Proof. Let r a i in R a , then the theorem must also hold for q a i . However, if we let q a i < -log(θ), and p i = 1, then the strict robustness is broken. Hence, there cannot be any r a i ∈ R a , and k = 0. There is no strongly unbiased, effective, strictly robust trust system.

Again, we weaken the robustness requirement. When we keep strong unbiasedness, we again lose effectiveness. Thus, not a single notion of robustness can combine meaningfully with strong unbiasedness. There is no strongly unbiased, effective, weakly robust trust system.

Finally, we consider a weakly robust, non-prescient system. Here, the limitation on the effectiveness is the weakest (assuming θ = f (1)):

Theorem 7. WR(f ) + T + OE(k, n) =⇒ k ≤ f (n) Proof.
Reuse the proof of Theorem 3, replacing θ with f (n).

There is no non-prescient, unlimited effective, weakly robust trust system.

We have shown the negative impact of robustness on other desirable requirements on a rating system. Perhaps robustness is simply a problematic notion in itself. In the proofs, we have shown that models cannot exist in certain combinations, not that models do exist in the negation. In this section, we show that there do exist reasonable models that strike a balance between robustness, fairness and effectiveness.

It does not suffice to prove the converse of the impossibility theorems, as that would simply prove that there exists a set of filtered ratings of a certain size. However, the setting in which that size is reached may be a pathological case. We want to show that filters can be expected to achieve a certain size. Hence, we are using axiom RE, rather than OE. Realistic effectiveness is an assertion about raters whose ratings correspond to the true probabilities. We want to show that these honest raters are expected to have a certain number of ratings selected by the filter.

First we introduce an auxiliary lemma, that shows that under T, RE = OE:

Lemma 1. T + RE(k, n) ⇔ T + OE(k, n) Proof. For given R a , if r a i is in R a , then, via T, r a i ∈ Q a .
We can take R a , and swap all r a i as above. Then we can make OE match any individual instance of RE for R a . Thus, for OE(k, n) and T to hold, RE(k, n) can be deduced to hold too. Together with Proposition 4, that proves the lemma.

The following theorem concerns strict robustness. A non-prescient, weakly unbiased, strictly robust filter can be expected to have over θ ratings selected over a lifetime: Theorem 8. There is a model that satisfies T + WU + SR(θ) + RE(θ -1, n), for sufficiently large n.

Proof. Via Lemma 1, it suffices to prove for T + WU + SR(θ) + OE(θ -1, n). If we only select those ratings that are within distance from 1 /2, then the noise is at most k + k • . Letting k = θ -1, the noise is at most θ -1 + (θ -1) • , which is under θ for sufficiently small . It is straightforward to verify that this scheme does not violate WU.

For the next theorem, we look at an interesting subclass of weak robustness. We consider only those functions where f (i) -f (i -1) is constant; specifically, 1. Thus, every prediction, the rater gets an additional bit credit. If the rater randomly provides ratings, the expected loss equals the gain and a bad rater is expected to make a nett loss. Specifically, the expected change in nett score is f (r a i , p 1 ) -1, which can be negative, 0 or positive. Theorem 9. Raters whose ratings do not correlate with the events, or correlate negatively, have a finite effectiveness. Raters whose ratings correlate positively with the event have a non-zero probability of infinite effectiveness.

Proof. This is a simple application of a rule in random walks [START_REF] Feller | An Introduction to Probability Theory and Its Applications[END_REF]. The probability of ruin -losing all credit -is 1 for random walks with E(step) ≤ 0, and the probability of ruin is strictly below 1 for random walks with E(step) > 1.

Theorem 9 is a superficially surprising result. We have a hard guarantee that below average predictors are eventually unable to get their ratings selected. We cannot guarantee that a high quality predictor is not shunned too. If a high quality predictor is unlucky, he can still have a random walk ending in ruin. Note that for simplicity, we took the cutoff at 1 /2, we could have chosen arbitrary values, or even a dynamic version. In all these cases, random walks without expected gain eventually run into ruin.

Conclusion

We have presented a simple formal model for prediction systems. That formal model focusses on the actual predictions, the outcomes and which predictions are used, and ignores the non-essential aspects of a prediction system.

We have outlined desirable properties for such a prediction system to have. Specifically, we have three notions of robustness -how much noise an attacker (or any rater) can introduce -in various strength (absolute, strict, weak). All three notions are formulated in information theory, but strict robustness can be stated in classical statistical term too. Two notions deal with bias, the strong version disallows any form of bias, whereas the weak version allows bias towards the center. Two more notions deal with effectiveness -how often the user can use the ratings. One version (weak) overestimates the effectiveness, to strengthen the impossibility results. Finally, one notion deals with the fact that users should not be able to foreknow the future.

All these notions have been translated into axioms in the language of the formal model for prediction systems. We show that the axioms do indeed satisfy the desired strength relations.

Based on the axioms, we present a collection of impossibility results. The absolute notion of robustness cannot have any effectiveness whatsoever. The strict notion of robustness can have a bounded effectiveness, meaning that the system cannot keep providing useful predictions indefinitely. For the weak notion of robustness the effectiveness remains hampered.

Finally, we show that a strict robust system can exist, and while its life-span is limited, reaching the theoretically maximal effectiveness is feasible. More importantly, we show that if we weaken robustness, an interesting property regarding effectiveness arises. Selecting the right function (f (n) = n + θ), we get that better-than-random raters could have infinite effectiveness, whereas random-orworse raters have finite effectiveness. In other words, the quality of the ratings determines whether the effectiveness is bounded.

Together the results in this paper sketch the idea that fairly strong notions of robustness are feasible, but come at a high cost. An interesting research direction would be to fine-tune all the desirable properties into an actual system -rather than a theoretically induced model.

Fig. 1 .

 1 Fig. 1. Relations between axioms. Arrows point from strong to weak.

Theorem 5 .

 5 SR(θ) + SU + OE(k, n) =⇒ k = 0

Theorem 6 .

 6 WR(θ) + SU + OE(k, n) =⇒ k = 0Proof. Reuse the proof of Theorem 5, replacing θ with f (1).

Table 1 .

 1 Effectiveness given levels of robustness (AR, SR, WR), bias (SU, WU) and non-prescience (T).

We ignore security attacks, such as identity theft or denial of service attacks.