A Network-Based Rating System and Its Resistance to Bribery

1 Introduction

Imagine to be the owner of a new and still relatively unknown restaurant. The quality of food is not spectacular and the customers you have seen so far are only limited to a tiny number of friends of yours. Your account on Tripadvisor R© has received no review and your financial prospects look grim at best. There is one easy solution to your problems: you ask your friends to write an enthusiastic review for you, in exchange for a free meal. After this, Tripadvisor R© lists your restaurant as excellent and the number of customers, together with your profit, suddenly florishes.

Systems such as Tripadvisor R©, where a small proportion of customers writes reviews and influences a large number of potential customers, are not bribery-proof: each restaurant owner - or the owner of whichever service - is able to offer a compensation - monetary or not - in exchange for positive evaluation, having an impact on the whole set of potential customers. Tripadvisor R© is based on what we call "Objective Rating", or O-RATING: individual evaluations are aggregated into a single figure, which is seen by, and thus influences, every potential customer.

What we study in this paper is a system in which each individual only receives the evaluation given by the set of trusted peers, his or her friends, and only this aggregated opinion

Paolo Turrini

Imperial College London United Kingdom p.turrini@imperial.ac.uk

influences his or her decision. This is what we call "Personalised Rating", or P-RATING, which can be seen a generalisation of O-RATING in which influence has a complex network-structure. So, while in the case of O-RATING the restaurant owner knows exactly how influence flows among the customers, this might not be the case with P-RATING.

Our contribution We analyse the effect of bribing strategies in the case of O-RATING and P-RATING under various constraints, depending on the presence of customers who do not express any opinion and the knowledge of the network by the service provider: the exact network is known, the network is known but not the customers' exact position, the network is completely unknown. We show under what conditions the system is bribery-proof, i.e., there is no bribe yielding a strictly positive expected gain to the service provider, and we provide algorithms for the computation of (all) optimal bribing strategies when they exist.

Intuitively, being able to know and bribe influential customers is crucial for guaranteeing a positive expected reward of a bribing strategy. However, while with large populations of non-voters "random" bribes can still be profitable, the effect of P-RATING is largely different from that of O-RATING and, as we show, the expected profit in the former can be severely limited and drops below zero in all networks, under certain (mild) conditions on the cost of bribes.

Our study can be applied to all situations in which individuals influence one another in the opinion they give and bribery can have a disruptive role in determining collective decisions. Related research lines Our approach relates to several re-

search lines in artificial intelligence, game theory and (computational) social choice [Brandt et al., 2015].

Network-based voting and mechanism design We study social networks in which individuals' local decisions can be manipulated to modify the resulting global properties. A similar approach is taken by Apt and Markakis [2014] and Simon and Apt [2015], which study the changes on a social network needed to make a certain product adopted among users. Further contributions include rational secret sharing and multi-party computation [Abraham et al., 2006], the strategic manipulation of peer reviews [Kurokawa et al., 2015], and the growing literature on voting in social networks [Conitzer, 2012; Salehi-Abari and Boutilier, 2014; Elkind, 2014; Tsang et al., 2015; Procaccia et al., 2015].

Lobbying and Bribery Our framework features an external agent trying to influence individual decisions to reach his or her private objectives. Lobbying in decision-making is an important problem in the area of social choice, from the seminal contribution of [Helpman and Persson, 1998] to more recent studies in multi-issue voting [Christian et al., 2007]. Lobbying and bribery are also established concepts in computational social choice, with their computational complexity being analysed extensively [Faliszewski et al., 2009; Baumeister et al., 2011; Bredereck et al., 2014; 2016].

Reputation-based systems We study the aggregation of possibly insincere individual evaluations by agents that can influence one another through trust relations. In this sense ours can be seen as a study of reputation in Multi Agent Systems, which has been an important concern of MAS for the past decades [Conte and Paolucci, 2002; Sabater and Sierra, 2005; Garcin et al., 2009]. In particular, our framework treats reputation as a manipulable piece of information, not just a static aggregate of individual opinions, coherently with the work of Conte et al. [2008] and Pinyol and Sabater-Mir [2013].

Paper structure Section 2 presents the basic setup, introducing O-RATING, P-RATING and bribing strategies. Section 3 focusses on O-RATING, studying its bribery-proofness under various knowledge conditions. Section 4 evaluates P-RATING against the same knowledge conditions. In Section 5 we compare the two systems, taking the cost of bribery into account. We conclude by summarising the main findings and pointing at future research directions (Section 6).

2 Basic setup

In this section we provide the basic formal definitions.

2.1 Restaurant and customers

Our framework features an object r, called restaurant, being evaluated by a finite non-empty set of individuals C = ¶c1↪ ▷ ▷ ▷ ↪ cn♦, called customers. Customers are connected by an undirected graph E ✓ C ⇥ C, called the customers network. Given c 2 C we call N(c) = ¶x 2 C ♣ (c↪ x) 2 E♦ the neighbourhood of c, always including c itself.

Customers concurrently submit an evaluation of the restaurant, drawn from a set of values Val ✓ [0↪ 1], together with a distinguished element ¶⇤♦, symbolising no opinion. Examples of values are the set [0↪ 1] itself, or a discrete assignment of 1 to 5 stars, as common in online rating systems. We make the assumption that ¶0↪ 1♦ ✓ Val and that Val is closed under the operation min¶1↪ x + y♦ for all x↪ y 2 Val. The vast majority of known rating methods can be mapped onto the [0↪ 1] interval and analysed within our framework.

We represent the evaluation of the customers as a function eval : C ! Val [ ¶⇤♦ and define V ✓ C as the subset of customers that expresses an evaluation over the restaurant, i.e., V = ¶c 2 C ♣ eval(c) 6= ⇤♦. We refer to this set as the set of voters and we assume it to be always non-empty, i.e., there is at least one customer that expresses an evaluation.

2.2 Two rating systems

In online rating systems such as Tripadvisor R© every interested customer can see - and is therefore influenced by - (the average of) what the other customers have written. We call this method O-RATING, which stands for objective rating.

Given an evaluation function eval of a restaurant, the associated O-RATING is defined as follows:

Where avg is the average function across real-valued eval (c), disregarding ⇤. We omit eval when clear from the context.

O-RATING flattens individual evaluations into a unique objective aggregate, the rating that a certain restaurant is given. What we propose is a refinement of O-RATING, which takes the network of influence into account. In this system customers are only interested in the evaluation of other customers they can trust, e.g., their friends. We call our method P-RATING, which stands for personalised rating. It is defined for a pair customer-evaluation (c↪ eval) as follows:

So the P-RATING(c↪ eval) calculates what customer c comes to think of the restaurant, taking the average of the opinions of the customers c is connected to. Again we omit eval whenever clear from the context.

Observe that in case a customer has no connection with a voter, then P-RATING is not defined. To facilitate the analysis we make the technical assumption that each customer is connected to at least one voter. Also observe that when E = C⇥C, i.e., in case the network is complete and each individual is influenced by each other individual, then for all c 2 C and eval we have that P-RATING(c↪ eval) = O-RATING(eval).

2.3 Utilities and strategies

We interpret a customer evaluation as a measure of his or her propensity to go to the restaurant. We therefore assume that the utility that a restaurant gets is proportional to its rating. To simplify the analysis we assume a factor 1 proportionality.

The case of O-RATING. For the O-RATING, we assume that the initial utility u0 of the restaurant is defined as:

Intuitively, the initial utility amounts to the number of customers that actually go to the restaurant, weighted with their (average) predisposition.

At the initial stage of the game, the restaurant owner receives u0 , and can then decide to invest a part of it to influence a subset of customers and improve upon the initial gain. We assume utility to be fully transferrable and, to facilitate the analysis, that such transfers translate directly into changes of customers' predispositions.

Definition 1. A strategy is a function σ : C ! Val such that Pc2C σ(c)  u0 .

Definition 1 imposes that strategies are budget balanced, i.e., restaurants can only pay with resources they have.

Let ⌃ be the set of all strategies. We denote σ0 the strategy that assigns 0 to all customers and we call bribing strategy any strategy that is different from σ0 . After the execution of a bribing strategy, the evaluation is updated as follows:

Definition 2. The evaluation evalσ (c) after execution of σ is eval σ (c) = min¶1↪ eval(c) + σ(c)♦, where ⇤ + σ(c) = σ(c), if σ(c) 6= 0, and ⇤ + σ(c) = ⇤, if σ(c) = 0.

In this definition we are making the assumption that the effect of bribing a non-voter to vote is equivalent to that of bribing a voter that had a 0-level review, as, intuitively, the individual has no associated predisposition to go to the restaurant.

A strategy is called efficient if σ(c) + eval(c)  1 for all c 2 C. Let B(σ) = ¶c 2 C ♣ σ(c) 6= 0♦ be the set of bribed customers. Let V σ be the set of voters after the execution of σ. Executing σ induces the following change in utility:

Intuitively, uσO is obtained by adding to the initial utility of the restaurant the rating obtained as an effect of the money invested on each individual minus the amount of money spent.

We define the revenue of a strategy σ as the marginal utility obtained by executing it:

Definition 3. Let σ be a strategy. The revenue of σ is defined as rO(σ) = uσO -u0 . We say that σ is profitable if rO(σ) > 0. Finally, we recall the standard notion of dominance:

Definition 4. A strategy σ is weakly dominant if uσO ≥ uσ0 O for all σ02⌃. It is strictly dominant if uσO > uσ0 O for all σ2⌃.

Hence a non-profitable strategy is never strictly dominant.

The case of P-RATING. The previous definitions can be adapted to the case of P-RATING as follows:

which encodes the initial utility of each restaurant, and

which encodes the utility change after the execution of a σ. Finally, let the revenue of σ be rP(σ) = uσP -u0P . If clear from the context, we use P-RATINGσ (c) for P-RATING(evalσ ↪ c).

In order to determine the dominant strategies, we need to establish how the customers vote, how they are connected, and what the restaurant owner knows. In this paper we assume that the restaurant knows eval, leaving the interesting case when eval is unknown to future work. We focus instead on the following cases: the restaurant knows the network, the restaurant knows the shape of the network but not the individuals' position, and the network is unknown. We analyse the effect of bribing strategies on P-RATING in each such case. Notice how for the case of O-RATING the cases collapse to the first. We also look at the special situation in which every customer is a voter.

Given a set of such assumptions, we say that O-RATING (or P-RATING) are bribery-proof under those assumptions if σ0 is weakly dominant.

Discussion Our model is built upon a number of simplifying assumptions which do not play a significant role in the results and could therefore be dispensed with: (i) customers' ratings correspond to their propensity to go to the restaurant. (ii) the restaurant utility equals the sum of all such propensities (iii) bribe σ(c) affects evaluation eval(c) linearly. All these assumptions could be generalised by multiplicative factors, such as an average price R paid at the restaurant, and a "customer price" Dc, such that evalσ (c) = eval(c) + σ(c) Dc .

3 Bribes under O-RATING

In this section we look at bribing strategies under O-RATING, first focussing on the case where everyone expresses an opinion, then moving on to the more general case.

3.1 All vote

Let us now consider the case in which V = C. Recall that B(σ) is the set of customers bribed by σ. We say that two strategies σ1 and σ2 are disjoint if B(σ1) [ B(σ2) = ;. By direct calculation it follows that the revenue of disjoint strategies exhibits the following property:

Lemma 1. If V = C and σ1 and σ2 are two disjoint strategies, then rO(σ1 ◦ σ2) = rO(σ1) + rO(σ2).

We now show that bribing a single individual is not profitable.

Lemma 2. Let σ be a bribing strategy, V = C and ♣B(σ)♣ = 1. Then, rO(σ)  0, i.e., σ is not profitable.

Proof sketch. Let ¯ c be the only individual such that σ(¯ c) 6= 0. By calculation, r(σ) = uσO -u0O = O-RATINGσ -O-RATINGPc σ(c) = min¶1↪ eval(¯ c)+σ(¯ c)♦-eval(¯ c)-σ(¯ c)  0.

By combining the two lemmas above we are able to show that no strategy is profitable for bribing the O-RATING.

Proposition 3. If V = C, then no strategy is profitable.

Proof sketch. Any bribing strategy σ can be decomposed into n pairwise disjoint strategies such that σ = σc1 ◦· · ·◦σcn and ♣B(σcj )♣ = 1 for all 1  j  n. By applying Lemma 1 and Lemma 2 we then obtain that rO(σ)  0.

From this it follows that σ0 is weakly dominant and thus O-RATING bribery-proof when all customers voted.

3.2 Non-voters

Let us now consider the case of V ⇢ C, i.e., when there is at least one customer who is not a voter. In this case Lemma 1 no longer holds, as shown in the following example.

Example 1. Let C = ¶A↪B↪C♦, and let eval(A) = 0▷5, eval(B) = 0▷5, and eval(C) = ⇤. The initial resources are u0 = O-RATING ⇥ 3 = 1▷5. Let now σ1(A) = 0▷5 and σ1(B) = σ1(C) = 0, and let σ2(C) = 0▷5 and σ2(A) = σ2(B) = 0. Now uσ1 O = 0▷75 ⇥ 3 - 0▷5 = 1▷75 and uσ2 O = 0▷5 ⇥ 3 - 0▷5 = 1, but uσ1◦σ2 O = 0▷¯6⇥3-1 = 1.

The example (in particular σ1) also shows that O-RATING in this case is not bribery-proof.

We now turn to characterise the set of undominated bribing strategies. We begin by showing that bribing a non-voter is always dominated. Let first σ be a strategy such that σ(¯ c) 6= 0 for some c 2 C∩V and recall that V σ is the set of voters after execution of σ. Let us define the c-greedy restriction of σ to be any strategy σ-¯ c such that:

• ÷ V σ-¯ c = V σ ∩ ¶c♦, i.e., the greedy restriction eliminates ¯ c from the set of voters.
• ÷ For each c 2 V σ ∩ c, max(1↪ eval(c) + σ(c)) = max(1↪ eval(c) + σ-¯ c (c)), i.e., the greedy restriction does not waste further resources.
• ÷ If there exists c 2 V σ ∩c such that eval(c)+σ-¯ c (c) < 1 then Pc2C σ-¯ c (c) = Pc2C σ(c), i.e., the σ-¯ c redistributes σ(¯ c) among the remaining voters.

We now show that each strategy bribing a non-voter is strictly dominated by any of its greedy restrictions.

Proposition 4. Let V 6= C, and ¯ c 2 C ∩ V . Then each strategy σ with σ(c) 6= 0 is strictly dominated by σ-¯ c .

Proof. Let σ be a strategy with σ(c) 6= 0 for some non-voter c, and let σ-¯ c be one of its greedy restriction defined above.

Observe first that σ-¯ c is a redistribution, hence Pc σ(c) - Pc σ-¯ c (c) ≥ 0, i.e., the second addendum in the above equation is positive. Consider now the case where there exists c 2 V σ ∩ c such that eval(c) + σ-¯ c (c) < 1. Then by the definition of σ-¯ c we have that Pc2V σ evalσ (c) = Pc2V σ-¯ c evalσ-¯ c (c), i.e., the greedy restriction preserves the overall evaluation. By straightforward calculation this entails that uσ-¯ c O - uσO > 0. If no such c exists, and therefore O-RATINGσ-¯ c = 1 we have that either O-RATINGσ < 1 or, by the efficiency requirement and the fact that σ(c) 6= 0, we have that Pc2C σ(c) > Pc2C σ-¯ c (c). In either cases we have that uσ-¯ c O -uσO > 0.

Let an O-greedy strategy be any efficient strategy that redistributes all the initial resources u0O among voters. Making use of the previous result, we are able to characterise the set of all dominant strategies for O-RATING.

Proposition 5. Let V 6= C. A strategy is weakly dominant for O-RATING if and only if it is an O-greedy strategy.

Proof sketch. For the right-to-left direction, first observe that all O-greedy strategies are payoff-equivalent, and that a nonefficient strategy is always dominated by its efficient counterpart. By Proposition 4 we know that strategies bribing nonvoters are dominated, and by straightforward calculations we obtain that in presence of non-voters it is always profitable to bribe as much as possible. For the left-to-right direction, observe that a non-greedy strategy is either inefficient, or it bribes a non-voter, or does not bribe as much as possible. In either circumstance it is strictly dominated.

While there may be cases in which the number of weakly dominant strategies under O-RATING is exponential, all such strategies are revenue equivalent, and Proposition 5 gives us a polynomial algorithm to find one of them: starting from an evaluation vector eval, distribute all available resources u0O to the voters, without exceeding the maximal evaluation of 1. By either exhausting the available budget or distributing it all, we are guaranteed the maximum gain by Proposition 5.

4 Bribes under P-RATING

In this section we look at bribing strategies under P-RATING, against various knowledge conditions on the social network. As for Section 3 we start by looking at the case where everyone votes and later on allowing non-voters. Before doing that, we introduce a useful graph-theoretic measure of influence.

Definition 5. The influence weight of a customer c 2 C in a network E is defined as follows:

Intuitively, each individual's rating influences the rating of each of its connections, and does so with a factor that is inversely proportional to the number of connections this individual has. We formalise this statement in the following lemma, which is restricted to strategies that only bribe voters:

Lemma 6. Let B(σ) ✓ V . The utility obtained by playing σ with P-RATING is uσP = Pc2C wc ⇥ evalσ (c) - Pc2C σ(c). Proof. By calculation:

In particular, when V = C, we obtain wc = Pk2N(c) 1 deg(k) , where deg(c) = ♣N(c)♣ is the degree of c in E.

4.1 All vote, known network

We begin by studying the simplest case in which the restaurant knows the evaluation eval, the network E as well as the position of each customer on the network. The following corollary is a straightforward consequence of Lemma 6:

Corollary 7. Let V = C and let σ1 and σ2 be two disjoint strategies, then rP(σ1 ◦ σ2) = rP(σ1) + rP(σ2).

We are now able to show a precise characterisation of the revenue obtained by any efficient strategy σ:

Proposition 8. Let V = C, let E be a known network, and let σ be an efficient strategy. Then rP(σ) = Pc2C (wc -1)σ(c).

Proof. By calculation, where Step (2) uses Lemma 6, and Step (4) uses the fact that σ is efficient:

Proposition 8 tells us that the factors wc are crucial in determining the revenue of a given bribing strategy. Bribing a customer c is profitable whenever wc>1 (provided its evaluation was not 1 already), while bribing a customer c with wc1 is at most as profitable as doing nothing, as can be seen in the example below. Most importantly, it shows that P-RATING is not bribery-proof when the restaurant knows both the network and the customers' evaluations.

Example 2. Let E be a four arms stars, and let A be the individual in the centre. Assume each individual values the restaurant 0.5. We have that wA = 2▷2 and wc = 0▷7 for all c different from A. Consider now two bribing strategies: σA which bribes A with 0▷5, and σB which bribes a single individual B 6= A with the same amount. What we obtain is that rP(σA) = 0▷6, while rP(σB ) = -0▷15.

Given a network E and an evaluation vector eval, let Algorithm 1 define the P-greedy bribing strategy.

Input: Evaluation function eval and network E Output: A bribing strategy σG P : C !Val

σG

Budget=u0P

Sort c 2 C in descending order c0↪ ▷ ▷ ▷ ↪ cm based on wc

P (c) = 0 for all c 2 C Compute wc for all c 2 C

for i=0,. . . ,m do

Algorithm 1: The P-greedy bribing strategy σG P

As a consequence of Proposition 8 we obtain:

Corollary 9. The P-greedy bribing strategy defined in Algorithm 1 is weakly dominant.

As in the case of O-RATING, Corollary 9 has repercussions on the computational complexity of bribery: it shows that computing a weakly dominant strategy can be done in polynomial time. Notice how the most costly operation lies in the computation of the influence weights wc, which can be performed only once, assuming the network is static. Similar problems, such as recognising whether bribing a certain individual is profitable, or estimating whether individuals on a network can be bribed above a certain threshold, are also computable in polynomial time.

4.2 All vote, unknown network

We now move to study the more complex case of an unknown network. Surprisingly, we are able to show that no bribing strategy is profitable (in expectation), and hence P-RATING is bribery-proof in this case. Recall that we are still assuming that the restaurant knows eval and everybody voted.

We begin by assuming that the restaurant knows the structure of the network, but not the position of each participant. Formally, the restaurant knows E, but considers any permutation of the customers in C over E as possible. Let us thus define the expected revenue of a strategy σ over a given network E as the average over all possible permutations of customers: E[rP(σ)] = P 1 n! [uσ⇢ -u0⇢ ]↪ where we abuse notation by writing uσ⇢ as uσP under permutation ⇢ over the network E. What we are able to show is that all strategies are at most as profitable as σ0 in expected return:

Proposition 10. Let V = C, let the network structure of E be known but not the relative positions of customers on E. Then E[rP(σ)] = 0 for all strategies σ.

Proof sketch. Let ♣C♣ = n. We show the result for any strategy σ that bribes a single customer ¯ c. The general statement follows from the linearity of E[r(σ)]. Equation (5) uses Proposition 8 to compute the revenue for each permutation ⇢ of customers C on the network:

The last line follows from the observation that Pc wc = ♣C♣ and hence Pc (wc -1) = 0, by a consequence of Definition 5 when everybody votes.

Hence, if we assume a uniform probability over all permutations of customers on the network, a straightforward consequence of Proposition 10 concludes that it is not profitable (in expectation) to bribe customers.

Corollary 11. If V = C and the network is unknown, then no bribing strategy for P-RATING is profitable in expected return.

4.3 Non-voters, known network

With P-RATING it is possible to find a network where bribing a non-voter is profitable:

Example 3. Consider 4 individuals ¶B↪ C↪ D↪ E♦ connected only to a non-voter in the middle. Let eval(j) = 0▷2 for all j but the center. We have u0P = 1. Let A be the non-voter, and let σ1(A) = 1 and 0 otherwise. The utility of σ1 is:

All other strategies can be shown to be dominated by σ1. Take for instance a strategy σ2 such that σ2(B) = 0▷8, σ2(C) = 0▷2 and 0 otherwise. The utility of σ2 is uσ2 P = 1▷25.

It is quite hard to obtain analytical results for strategies bribing non-voters, due to the non-linearity of the P-RATING in this setting. We can however provide results in line with those of the previous section if we restrict to voter-only strategies, i.e., strategies σ such that σ(c) = 0 for all c 62 V . In this case, a similar proof to Proposition 8 shows the following:

Proposition 12. Let V 6= C, E be a known network, and σ be an efficient bribing strategy such that B(σ) ✓ V . Then, rP(σ) = Pc2C (wc - 1)σ(c).

The difference with the case of V = C is that wc can be arbitrarily large in the presence of non-voters, such as in our Example 3.

4.4 Non-voters, unknown positions

Unlike the case of V = C, in this case it is possible to define bribing strategies that are profitable (in expected return).

Example 4. Let C = ¶A↪B↪C♦, and the initial evaluation eval(A) = eval(B) = 0▷2 and eval(C) = ⇤. Assume that the structure of the network is known, but the position of the individuals is not. Let the three possible network positions (without counting the symmetries) be depicted in Figure 1. Let σ(B) = 0▷2 and σ(A) = σ(C) = 0. In the first case:

In the second case r2P (σ) = 0 while in the third:

Therefore, P-RATING is not bribery-proof (in expectation) in the presence of non-voters when the network is unknown. Interesting computational problems open up in this setting, such as identifying the networks that allow for profitable bribing strategies, and their expected revenue.

5 Boundaries of bribery-proofness

The previous sections have shown that having a networkbased rating systems, where individuals are influenced by their peers, is not bribery-proof, even when the position of individuals in a given network is not known. However bribing strategies have a different effect in the overall score. While the utility of O-RATING is a sum of the global average of voters' evaluation, the utility of P-RATINGis a sum of local averages of voters' evalution against the one of their peers.

Therefore a strategy bribing one voter affects everyone in the case of O-RATING, but it can be shown to have a limited effect in the case of P-RATING.

Proposition 13. Let σ be an efficient strategy s.t. ♣B(σ)♣ = 1, and let ¯ c be such that σ(c) 6= 0. Then rP(σ) < N(¯ c).

Proof. By calculation, we have that:

The previous result shows that increasing the number of individuals that are not connected to an agent that is bribed, even if these are non-voters, does not increase the revenue of the bribing strategy. This is not true when we use O-RATING.

Proposition 14. Let σ be an efficient strategy. The revenue rO(σ) of σ is monotonically increasing with the number of non-voters, and is unbounded.

Proof. It follows from our definitions that:

The above figure is unbounded and monotonically increasing in the number of non-voters, which can be obtained by increasing C keeping V σ fixed.

So while P-RATING and O-RATING are not bribery-proof in general, it turns out that the impact of the two in the overall network are significantly different. In particular, under realistic assumptions such as a very large proportion of non-voters and with participants having a few connections, bribing under O-RATING is increasingly rewarding, while under P-RATING this is no longer the case.

6 Conclusive remarks

We introduced P-RATING, a network-based rating system which generalises the commonly used O-RATING, and analysed their resistance to external bribery under various conditions. The main take-home message of our contribution can be summarised in one point, deriving from our main results:

P-RATING and O-RATING are not bribery-proof in general. However, if we assume that a service provider has a cost for bribing an individual, there are situations in which P-RATING is fully bribery proof, while O-RATING is not. For instance, if the cost of bribing an individual c is at least N(c) then P-RATING is bribery-proof. As observed previously, this is not necessarily true for O-RATING. In particular, if we assume the presence of unreachable individuals the difference is more significant. As shown, for P-RATING we need to bribe individuals with wc > 1. With O-RATING is sufficient to find one voter who accepts a bribe.

There is a number of avenues open to future research investigation. The most important ones include the case of partially known customers' evaluation, and the study of ratings of multiple restaurants, where the probability of a customer choosing a restaurant determines his or her probability not to choose the others.

Acknowledgments

Umberto Grandi acknowledges the support of the Labex CIMI project "Social Choice on Networks" (ANR-11LABX-0040-CIMI). Paolo Turrini the support of Imperial College London for the Junior Research Fellowship Designing negotiation spaces for collective decision-making (DoCAI1048). This work has also been partly supported by COST Action IC1205 on Computational Social Choice.