Collusion-resistant, Incentive-compatibleFeedback PaymentsRadu JurcaEcole Polytechnique F´ed´erale de Lausanne(EPFL)Artificial Intelligence LaboratoryCH-1015 Lausanne, [email protected] FaltingsEcole Polytechnique F ´ed ´erale de Lausanne(EPFL)Artificial Intelligence LaboratoryCH-1015 Lausanne, [email protected] reputation mechanisms need honest feedback to func-tion effectively. Self-interested agents report the truthonly when explicit rewards offset the potential gains ob-tained from lying. Feedback payment schemes (monetaryrewards for submitted feedback) can make truth-telling ra-tional based on the correlation between the reports of dif-ferent buyers.In this paper we investigate incentive-compatible paymentmechanisms that are also resistant to collusion: groups ofagents cannot collude on a lying strategy without suffer-ing monetary losses. We analyze several scenarios, where,for example, some or all of the agents collude. For eachscenario we investigate both existential and implementationproblems. Throughout the paper we use automated mecha-nism design to compute the best possible mechanism for agiven setting.Categories and Subject DescriptorsI.2.11 [Artificial Intelligence]: Distributed Artificial In-telligenceGeneral TermsAlgorithms, Design, EconomicsKeywordsreputation mechanisms, mechanism design, incentive com-patibility, collusion resistance1. INTRODUCTIONUsers increasingly resort to online feedback forums (rep-utation mechanisms) for obtaining information about theproducts or services they intend to purchase. The testi-monies of previous buyers disclose hidden, experience-related[19], product attributes (e.g., quality, reliability, ease of use,Permission to make digital or hard copies of all or part of this work forpersonal or classroom use i s granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistrib ute to lists, requires prior specificpermission and/or a fee.E C’07, J une 11–15, 2007, San D iego, California, USA.Copyright 2007 ACM 978-1-59593-653-0/07/0006 ...$5.00.etc.) that can only be observed after the purchase. This pre-viously unavailable information allows the buyers to makebetter, more efficient decisions.A key ingredient for all reputation mechanisms is hon-est feedback. Human users exhibit high levels of altruistic(i.e., honest) reporting, despite empirical evidence that ly-ing can bring external benefits [8, 21]. Nevertheless, the fu-ture online economy may be dominated by rational, utilitymaximizing software agents, that will exploit such misre-porting opportunities. Hence the need for designing reputa-tion mechanisms that are incentive-compatible: i.e., rationalagents find it in their best interest to report the truth.Fundamental results in the mechanism design literature[7, 5] show that side payments can be designed to create theincentive for agents to report their private opinions truth-fully. The best such payment schemes have been constructedbased on proper scoring rules [15, 12, 2], and exploit the cor-relation between the observations of different buyers aboutthe same good.Miller, Resnick and Zeckhauser [18] adapt these results toonline feedback forums. A central processing facility (thereputation mechanism) scor es every submitted feedback bycomparing it with another report (called the reference re-port) about the same good. They prove the existence ofgeneral incentive-compatible payment mechanisms that cre-ate an equilibrium where the return when reporting honestlyis better by at least an arbitrary margin δ.Jurca and Faltings [14] use an identical setting to applyautomated mechanism design [3, 20]. Incentive-compatiblepayments are computed by solving an optimization prob-lem with the objective of minimizing the required budget.The simplicity of specifying payments through closed-formscoring rules is sacrificed for significant gains in efficiency.Intuitively, payment mechanisms encourage truth-tellingbecause reporters expect to get paid according to how welltheir feedback improves the current predictor of the refer-ence report. Every feedback report modifies the reputationinformation, which acts as a predictor for future observa-tions. The payment received by the reporter reflects thequality of the updated predictor, tested against the refer-ence report. Assuming that the reference report is honest,every agent has the incentive to update the current reputa-tion such that it mirrors her subjective beliefs. Agents thusreport honestly, and truth-telling is a Nash equilibrium.For example, consider the owner (she) of a new house whoneeds some plumbing work done. There are good and badplumbers; the one chosen by our owner has a fairly good200reputation that predicts high quality work with probabil-ity 75%. Once the work gets done, the owner will have anew (private) belief regarding the reputation of the plumber.If she is happy with the service, she believes the plumbershould have an even better reputation (that predicts, for ex-ample, good service with probability 87%1). On the otherhand, if the owner is dissatisfied with the service, she be-lieves that the plumber should have a lower reputation (theprobability of good service should only be 39%). An on-line reputation mechanism asks the owner to share feedbackabout the plumber, and proposes the following paymentrule: “the submitted report is paid only if it matches thereport submitted by another client ab out the same plumber.A negative report will be paid $2.62, while a positive rep ortwill be paid $1.54”. One can verify that honest reportingmaximizes the expected payment of the owner, regardless ofthe actual experience2.While honest reporting is a Nash Equilibrium (NEQ), so isalways reporting negative (or positive) feedback. Moreover,the expected payoff from these constant reporting strategies($2.62 or $1.54 respectively) are both higher than the ex-pected payoff from the honest equilibrium. Unfortunately,the existence of multiple equilibria is not an isolated problemspecific to our example. In previous work [13] we show thatall binary incentive-compatible payment mechanisms sufferfrom the same drawback: there are lying equilibria that gen-erate higher expected payoffs than the truthful equilibrium.This brings forth the problem of collusion.