Eliciting Honest Reputation Feedback in a Markov Setting

1 Introduction

Online reputation mechanisms are a prominent way to establish trust and cooperation in anonymous online interactions [e. g., Dellarocas, 2006]. Signaling reputation mechanisms applied at opinion forums, in particular, have become a popular source of information. Customers of products and services give feedback regarding the quality they experienced and the publication of this previously undisclosed information allows future customers to make better-informed decisions. From a game-theoretic point of view, however, most of these mechanisms are problematic. Two aspects of the feedback part stand out in particular. The first is under-provision. The customers are usually required to register an account and fill out forms describing their experiences. This process is time consuming and rational agents will only invest the effort of giving feedback when remunerated appropriately. The second issue is honesty. External interests (i. e. biases towards dishonest reporting) come from a variety of motivations. Imagine two companies competing for the same group of customers. Both have incentives to badmouth their competitor, praise their own products or pay the rating agents to do so. Moreover, both positive and negative externalities are wide-spread. That is, an agent's utility of a good changes if other agents consume it as well. For example, the utility of an agent using a voice-over-IP service is higher the more agents she can call with it. Honest reputation feedback is thus crucial to incorporate into the design of the mechanism. This task is difficult because it is not clear how to decide whether a given feedback is honest. In contrast to prediction markets, for example, where a publicly observable event eventually materializes [e. g., Wolfers and Zitzewitz, 2004], the inherent quality of a good is never revealed. Thus, the designer of the mechanism has to find other ways to condition the payments.

One solution is provided by Miller, Resnick and Zeckhauser [2005] (henceforth, MRZ). They compare the quality reports of two agents about the same good with one another and apply strictly proper scoring rules [e. g., Cooke, 1991] to compute a payment scheme that makes honest reporting a Nash equilibrium. Jurca and Faltings [2006] (henceforth JF) study a largely similar setting but use automated mechanism design [Conitzer and Sandholm, 2002] to compute a budgetoptimal payment scheme. Furthermore, they developed numerous extensions to the base model, such as incorporating collusion resistance [Jurca and Faltings, 2007].

The mechanisms of MRZ and JF, however, critically depend on the good's quality to stay fixed, while many realworld settings are inherently dynamic. Applying the static mechanisms to dynamic settings is problematic for two reasons: first, the payment scheme is rendered useless if the agents know about the dynamic nature of the process, as by watching the type belief updates they can derive the posted signals and use them to learn the parameters of the process. Second, the mechanism's type architecture is only capable of publishing the average abilities whereas the users are interested in its present quality.

The rest of the paper is organized as follows. In the next section we present the setting. Section 3 describes the proposed reputation mechanism that generalizes the fixed architecture of MRZ and JF to hidden Markov models. Motivated by the example of Section 4, Section 5 shows how the acquisition of signals can be used to make honest reporting the unique Nash equilibrium. Section 6 provides experimental results and Section 7 concludes with an outlook.

2 The Setting

A sequence of agents experiences the same product or service and its quality (henceforth its type) is drawn out of a finite set of possible types Θ = {θ1, ... , θ|Θ|}. All agents share a common prior belief Pr(θ) that the product is of type θ with ∑θ∈Θ Pr(θ) = 1 and Pr(θ) > 0 for all θ ∈ Θ.

The quality observations by the agents are noisy, so that after experiencing the product, a buying agent does not know with certainty the product's actual type. Instead, she receives a signal drawn out of a set of signals S = {s1, ... , sM}. Let Oi denote the signal received by agent i and let f(sm| θ) = P r(Oi = sm| θ) be the probability that agent i receives the signal sm ∈ S given that the product is of type θ ∈ Θ. These signal emissions again constitute a probability distribution: ∑Mm=1 f(sm| θ) = 1 ∀θ ∈ Θ. We assume that different types generate different conditional signal distributions and that all f(sm| θ) are common knowledge.

In order to incorporate dynamic settings, we introduce a common-knowledge transition matrix that models quality changes as a Markov process (MP). Together with the noisy perception of the signals, the resulting structure is a discretetime hidden Markov model (HMM) with a finite set of states. We use an extended definition of HMMs and allow both null transitions and multiple observations. That is, in each time step t, there can be more than one or no agent receiving a signal. The transition matrix P is given with the problem definition and stays the same for all t (i. e. the MP is timehomogeneous). Given type θi, the probability to go to type θj in the next time step is Pr(θt+1 j | θt i ). This value is stored in column i and row j so that P is a so-called left stochastic matrix (i. e. the columns sum up to 1). Left transition matrices allow for a simple way to determine the probability of the type vector in a certain time step. We demand that P is reversible and that at least two columns are different from each other.

We will allow the mechanism (henceforth, center) to pay agents for their feedback and we assume quasilinear utilities. For example, electronic market sites could give away rebates on future sales. However, payments are not necessarily monetary as long as agents have utility for them. Let Ci be the costs reflecting agent i's time and effort required for the rating process and let Δi (sj, sh) be the external benefit agent i could gain by falsely announcing signal sh instead of signal sj (the one actually received). We assume an upper bound on C and Δ(sj, sh). This way the center does not require knowledge on individual agent's preferences.

3 AReputationMechanism for Markov Settings

The reputation mechanism consists of three parts: the payment scheme, the reference reporter choice rule and the rule for publication of updated type beliefs. Before elucidating on these parts, we describe the general procedure and present the agents' options: first, an agent buys or requests a product or service. After experiencing its quality, the center asks the agent for feedback regarding the signal she perceived. As this information is private to the agent, there are three basic alternatives: the agent can choose to report the signal actually received, she can lie (i. e. report some other signal s ̸= Oi ) or she can not report at all. If the agent has chosen to report a signal, it is compared to that of another agent r(i), called the reference reporter. The point in time at which the updated type beliefs (taking into account the announced signal) are published depends on the rule that is used to choose an agent's reference reporter. With exception of the very first agent who is rated against her successor, we will rate an agent against her predecessor. This rule has two advantages: first, the center can pay the reporting agent right away (again, with exception of the very first agent) and, second, right after the announcement it can update and publish the type beliefs considering every signal report but the very last. This quick release of the updated beliefs is generally important but especially so in dynamic contexts where information out-dates.

Let ai = (ai1 , . . . , aiM ) be the reporting strategy of agent i, such that she reports signal aij ∈ S if she received sj. The honest strategy is ¯a = (s1, . . . , sM), i. e. always reporting the signal received. As becomes clear from the definition of the agent strategies, we assume they are independent of both the product and the time step t. This assumption is reasonable if the reputation mechanism is located at an intermediary, such as a booking site. Here, agents can neither lie about the product nor about the time at which they consumed it since the center already knows this from the booking data. It is, however, possible that the good's consumption is postponed or brought forward if that benefits the agents in the rating process. While this has no impact on the truthfulness of the mechanism, it may result in (arguably small) inefficiencies. Depending on the application it may be required to construct an online mechanism and we leave this to future work.

3.1 Probability Computations

The central idea of comparing two signal reports is that knowing one of the received signals should tell you something about the other. This concept is called stochastic relevance.

Definition 1. Random variable Oi is stochastically relevant for random variable Or(i) iff the distribution of Or(i) conditional on Oi is different for different realizations of Oi .

For the fixed setting, MRZ prove that combinations of Pr(θ) and f(·|·) that fail stochastic relevance occur with probability 0 (i. e. have Lebesgue measure 0). As P is required to have at least two columns that are different from each other, this readily extends to the Markov setting. In fact, the added belief perturbations give the center more power to avert these combinations by using another rating agent which then results in a different scheme. We thus assume stochastic relevance holds.

Without loss of generality, let r(i) receive her signal at time t1 while agent i receives her signal at t2. Let st1 k and st2 j denote the signals received by r(i) and agent i, respectively. The probability that r(i) received st1 k given i received st2 j is:

This can be written as:

P r(st1 k | θt1 l ) can be simplified to f(sk| θl) as the probability of a signal given a certain type is independent of when it is received. For reasons of clarity, we slightly abuse the notation and add superscripts to f(·|·) in following equations.

Applying Bayes' Theorem to Eq. 2 we obtain:

Let

be the vector of prior type probabilities. As we know both the topology and the parameters of the HMM, calculating the entire probability vector Pr(θt ) is straightforward:

Please note that in the context of a matrix, the superscript denotes exponentiation: P t = P × . . . × P ︸ ︷︷ ︸ .

Using Eq. 5, we obtain the signal probability required for Eq. 3:

The probability that agent i receives signal st2 j given the type was θt1 l (also required for Eq. 3) can be computed as follows:

For the probability of a certain type at time t2 knowing the type at time t1 we need to distinguish two cases:

• t2 ≥ t1 Here, a minor change of Eq. 5 is sufficient:

• t2 < t1 From Bayes' Theorem we know

o ) is analogous to the t2 ≥ t1 case.

3.2 The Payment Scheme

Let τ (aij , ar(i) k ) be the payment that agent i receives if she announced aij and the reference reporter announced ar(i) k . The expected payment to agent i given her received signal and given an honest report by r(i) is:

Similar to JF, we formulate the payment scheme as a Linear Program (LP). Its constraints can be divided into two groups. The first group consists of the honesty constraints which require that the honest signal announcement by agent i is the single best response to an honest report by r(i). For every possible signal observation Oi = sj ∈ S, there exist M - 1 dishonest announcements aij ̸= ¯aj. Given that the reference report is honest, we want the expected payment of an honest announcement by agent i to be larger than the expected payment of any other announcement. More accurately, incorporating external lying incentives, we want it to be larger by a margin greater than Δ(sj , sh):

The second group consist of the participation constraints. An agent will participate in the rating system if and only if she is remunerated with at least as much as the rating process costs her. As the agent's decision whether to participate in the rating is taken after experiencing the good (i. e. she knows her own signal) but without knowing the signals received by the other agents, interim individual rationality is appropriate [e. g., Parkes, 2001, p. 34f]:

In addition, we assume there is no possibility to withdraw credit from the agents, so that we require that all payments are non-negative. In order to find an assignment of τ(ai , ar(i) ) that minimizes the required budget, the objective function is the expected payment given a certain signal weighted with the signal's prior probability. Summarizing, the payment scheme formulated as an LP in standard form is:

Please note that the objective function uses the expected payment of the honest equilibrium since this is what the agents should play given the honesty constraints.

The payment scheme together with the rater choice rule we use induces a temporal order of extensive games with imperfect information. However, the fact that no agent knows the reported signal of her reference reporter make them equivalent to 2-player strategic games for which we can prove the following proposition.

Proposition 1. Reporting honestly is a Nash equilibrium in every strategic game induced by an update of the type beliefs.

Proof. The proof applies induction over the game order.

The basis: The first game is played by agent 1 and 2: agent 1 is rated against agent 2 and given the latter reports honestly, the LP's honesty constraints ensure that the honest report is a best response. Likewise, given an honest report by the first agent, the second agent's best response is reporting honestly. Inductive step: Assume that reporting honestly is an equilibrium in the n-th game. In game n+1, agent n+2 is rated against agent n + 1 while the latter's payoff solely depends on the outcome of game n. That is, agent n + 1 is indifferent about the outcome of game n + 1. Since honest reporting is an equilibrium of game n, agent n + 1's best response was playing honestly, so that honest play by agent n + 2 is a best response. Thus, reporting honestly is a Nash equilibrium of game n + 1.

3.3 Updating the Type Beliefs

Up to this point, we have constructed a payment scheme that induces agents to give honest feedback about the signals they receive. What is supposed to be published, though, are the present beliefs that the product has a certain type. We publish the type changes inherent in the MP in every time step using Equation 5. This is different from publishing information that is updated using signal observations (hence, conditional updates) for when performing the latter we have to ensure that the respective observations are no longer required as reference reports.

As before, let agent n denote the n-th agent to make a signal announcement. Slightly abusing the notation, let tn and On denote her time step and signal, respectively. At t1 there is no conditional belief update as there is no other announcement than that of agent 1 who is still needed as a reference reporter for agent 2. After announcement of On , however, we incorporate the signal observation at tn-1 as we no longer rely on agent n - 1 as a reference reporter. This also means that every conditional belief update incorporates only a single observation. Thus, we compute the conditional type update and "overwrite" the old type priors using Equation 3:

4 AWeb Service Example

We present an example application from a computing context. Imagine a web service that wishes to publish the expected download speed of a file mirrored on different server sites. The users of the service have to choose one of these mirrors to download from. Clearly, this choice determines the download speed as the mirrors vary in both total bandwidth and work load. Every user wishes to download from the mirror that is expected to serve him with highest speed. Unfortunately, this information is only known to the mirrors and they have no interest in sharing it truthfully as they receive advertisement premiums for every access of their site. Users also have to enter a CAPTCHA before downloading which makes it costly for both the operator of the web service and the users to test the present speed of all mirrors beforehand.

Therefore, a reputation mechanism is located at the web service. By logging the user requests, the center can identify both when the download began and which mirror was chosen. The number of users that are directed to the servers by the web service is small compared to the servers' total number of users, so that the impact of the web service's agents on the servers' behavior is negligible. Furthermore, we assume that the servers are programmed to serve at their highest possible speed given their bandwidth and work load. That is, the servers' behavior is entirely stochastic.

Let us first consider the example of Figure 1. There are only two possible types, a good type G and a bad type B. Furthermore, there are only two possible signals, namely a high signal h and a low signal l. Types and signals correspond to the servers' total and load-dependent bandwidths, respectively. The prior type probabilities are Pr(G) = 0.7 and Pr(B) = 0.3. All other probabilities are depicted.

The fixed setting is very noisy as the dynamics of the work load cannot be expressed properly. Alternatively, we can model the servers as the hidden Markov model depicted in Figure 2. The prior type probabilities are Pr(Bl) = 0.18, Pr(Bh) = 0.12, Pr(Gl) = 0.14 and Pr(Gh) = 0.56. As a server may not distribute its bandwidth entirely equally, it is still possible to receive a high signal given a bad state and vice versa. The parameters of this dynamic setting are chosen such that they yield the same prior signal distribution as the fixed setting of Figure 1, namely Pr(l) = 0.371 and Pr(h) = 0.629 (please note that the similar values given in Figure 1 are the conditional signal probabilities). Nonetheless, the computed payment schemes for t2 = 0 are different (see Figure 3). The expected payments are 0.43 and 0.13 for the fixed and dynamic setting, respectively. Figure 4 shows that with larger t2 the expected budget of the dynamic scheme converges to the budget of the fixed setting from below. Thus, with introduction of the Markov setting we can both gain expressiveness and further lower the required budget.

5 Acquisition of Costly Signals

A drawback of the payment scheme from Section 3 is that the honest equilibrium is not unique. In fact, it can even be Pareto-dominated by a lying equilibrium (compare Figure 3). Unfortunately, as long as the mechanism solely depends on announcements by selfish agents, multiple equilibria are essentially unavoidable [Jurca and Faltings, 2005]. Depending on the setting, however, it can be possible for the center to acquire a costly signal himself. Take the web service example: clearly, the costs involved in a signal acquisition by the operator are higher than the reporting costs of an agent. After all, that is why we propose to use a reputation mechanism. Yet, while it is too costly for the operator to learn the speed of each server before every download, it might be affordable to acquire some signals that can then be used as reference reports. In fact, we will see that acquiring a single signal is sufficient to make honest reporting the unique Nash equilibrium in every game induced by a type belief update.

The na¨ıve approach is to acquire a new signal for every agent, rate her against it and update the type beliefs. This is, however, very costly. A cheaper approach is to utilize an acquired signal similar to the publicly observable event in a prediction market: the center commits to an acquisition at time t and rates every agent up to this point against it. Yet, thereafter, the center has to acquire another signal as the types continue to change. Highlighting the importance of the reference reporter choice rule, we propose to acquire a signal before any agent announcement, rate the first agent against it and every subsequent agent against her predecessor. This also allows us to drop the assumption that P is reversible.

Proposition 2. The acquisition of the first signal is sufficient to make honest reporting the unique Nash equilibrium of every strategic game induced by an update of the type beliefs.

Proof. The proof is similar to that of Proposition 1 and also applies induction over the game order.

The basis: The first game is now played by the center and agent 1. Agent 1 is rated against the acquired signal which is honest by definition. The honesty constraints ensure that honest reporting is the single best response and thus that honest reporting is the unique Nash equilibrium.

The inductive step is the same as in Proposition 1 except that game n is assumed to have a unique equilibrium and that in game n + 1, agent n + 1 is rated against agent n.

Please note that it is also possible to rate every agent against the acquired signal directly. This would, however, bring about three other problems: first, it is harder to keep a single signal undisclosed if every agent learns it. Second, even myopic agents cannot be allowed to participate again while our proposed choice rule only prohibits successive ratings. Third, the required budget usually grows with the number of time steps that lie in between the two raters (compare next section).

6 Experimental results

If not stated otherwise, the parameters for the experiments are created as described in Appendix A.

6.1 Running Time

There are polynomial algorithms for solving LPs. In practice, however, the Simplex method with exponential worstcase running time usually performs better. Thus, in order to determine whether the reputation mechanism is feasible for real-world settings, we empirically evaluate it on a customary computer with a 1.6 GHz CPU.

Let Δ(t) denote |t2 - t1|. Table 1 shows the CPU time that is required for computation of the payment scheme for Δ(t) = 0 and different values of M. The running time that comes with the MP is depicted in Figure 5. In addition to Δ(t), the runtime also grows with M. This is due to the matrix exponentiation algorithm we use whose running time is O(|Θ|3 · log t). For larger Δ(t), the factor |Θ|3 = M 3 gets more influence although only multiplied by log t. Yet, values of Δ(t) should rarely be higher than 10 so that the slowdown will make up less than 3% even for settings with large signal set. Taking into account the low numbers of Table 1, we believe computational complexity is not a limiting factor for application.

6.2 Expected Budget

In the example of Section 4 the fixed setting requires a higher budget than an equivalent dynamic setting. Hidden Markov models, however, are more expressive. In particular, it is possible that every type can be reached from every other type. Figure 6 shows the expected costs for different values of stochastic movement inherent in the fully connected P of the random setting. The more time passes between the two ratings and the larger ε, the higher are the center's costs. Note that this is inherent in the setting as both factors lead to more type perturbations through the MP. For larger Δ(t) the probability of a certain type at t2 conditional on the types at t1 becomes more alike as the MP converges to a stationary distribution and so do the signal posteriors g(st1 k | st2 j ). As these make up the coefficients of the LP, the solver needs larger τ to separate the honest from the dishonest announcements.

7 Conclusions and FutureWork

We have presented a reputation mechanism that elicits honest feedback in a Markov setting and requires a lower budget than the equivalent fixed setting. When solely relying on the announcements of selfish agents, multiple equilibria are unavoidable. We have shown how in settings where costly signals can be acquired, the acquisition of a single signal is sufficient to make honest reporting the unique Nash equilibrium of every induced game.

A limitation of the setting we studied, however, is the high amount of common knowledge. We believe it is an interesting question under which circumstances it is possible to truthfully elicit the signal observations and also use them to learn the probabilistic parameters. For restricted settings such as the example setting of Section 4 this should be possible: using the fixed payment scheme, one can elicit the first k agents' signals and subsequently expand the model to the equivalent dynamic setting. With the structure and the prior beliefs for the ground types known, one could then learn the parameters with the Baum-Welch algorithm. The choice of k depends on the trade-off between budget and robustness. Please note that we only need to ensure that the center's model is better than that of future reporting agents which is further supported by only publishing the expected quality (e. g., the expected speed) instead of the entire distribution.

Acknowledgments

We thank Malte Helmert, Sven Seuken and three anonymous reviewers for very helpful comments on this work.

A Random Setting

Every type corresponds to a signal, i. e. M = |Θ|. The default is M = 5. All f(sm|θl) are set according to the rule:

P is generated analogously:

The default is ε = 10%. The type vector at t = 0 is uniformly distributed and we set t1 = 0 with t2 ≥ t1. All Δ(sj, sh) (h ̸= j) are set to 0.15, C is set to 0.1 and we average over 1000 randomly generated settings.