Minimum Payments that Reward Honest ReputationFeedbackRadu 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 truth onlywhen explicit rewards offset the cost of reporting and the po-tential gains that can be obtained from lying. Side-paymentschemes (monetary rewards for submitted feedback) can maketruth-telling rational based on the correlation between therep orts of different buyers.In this paper we use the idea of automated mechanismdesign to construct the payments that minimize the budgetrequired by an incentive-compatible reputation mechanism.Such payment schemes are defined by a linear optimizationproblem that can be solved efficiently in realistic settings.Furthermore, we investigate two directions for further low-ering the cost of incentive-compatibility: using several ref-erence reports to construct the side-payments, and filteringout reports that are probably false.Categories and Subject DescriptorsI.2.11 [Artificial Intelligence]: Distributed Artificial In-telligenceGeneral TermsAlgorithms, Design, EconomicsKeywordshonest feedback, reputation mechanisms, mechanism design1. INTRODUCTIONOnline buyers increasingly resort to reputation forums forobtaining information ab out the products or services theyintend to purchase. The testimonies of previous buyersdisclose hidden, experience-related [13], product attributes(e.g., quality, reliability, ease of use, etc.) that can only bePermission to make digital or hard copies of all or part of this work forpersonal or classroom use is 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 redistribute to lists, requires prior specificpermission and/or a fee.EC’06, June 11–15, 2006, Ann Arbor, Michigan, USA.Copyright 2006 ACM 1-59593-236-4/06/0006 ...$5.00.observed after the purchase. This previously unavailable in-formation allows the buyers to take better, more efficientdecisions.Quality-based differentiation of products is also beneficialfor the sellers. High quality, when recognizable by the buy-ers, brings higher revenues. Manufacturers can thereforeoptimally plan the investment in their products, such thatthe difference between the higher revenues of a better prod-uct, and the higher cost demanded by the improved quality,is maximized. Honest reputation feedback is thus essentialfor establishing an efficient market.Human users exhibit high levels of honest behavior (andtruthful sharing of information) without explicit incentives.However, in a future e-commerce environment dominatedby rational agents, reputation mechanism designers need tomake sure that sharing truthful information is in the bestinterest of the reporter.Two factors make this task difficult. First, feedback re-porting is usually costly. Most forums still require a con-scious effort to formulate and submit feedback: buyers needto understand the rating scale (e.g., five star ratings – whereone star is the lowest score, five star is the highest score –or “top five” preferences where one is the best score andfive is the lowest), they need to manually fill in forms, andsupervise the submission of the report. As feedback report-ing does not bring direct benefits, many agents only reportwhen they have ulterior motives, thus leading to a biasedsample of reputation information.Second, truth-telling is not always in the best interest ofthe reporter. In some settings, for instance, false denigra-tion decreases the reputation of a product and allows thereporter to make a future purchase for a lower price. Inother contexts, providers can offer monetary compensationsin exchange for favorable feedback: e.g., doctors get gifts forrecommending new drugs, authors ask their friends to writepositive reviews about their latest book [6, 19]. One way oranother, external benefits can be obtained from lying andselfish agents will exploit them.Both problems can be addressed by a payment schemethat explicitly rewards honest feedback by a sufficient amount∆ to offset both the cost of reporting and the gains thatcould be obtained through lying. Seminal work in the mech-anism design literature [5, 4] shows that side payments canbe designed to create the incentive for agents to report theirprivate opinions truthfully, a property called incentive com-patibility. The best such payment schemes have been con-structed based on “proper scoring rules” [11, 8, 2], and ex-ploit the correlation between the observations of differentbuyers about the same good.Miller, Resnick and Zeckhauser (henceforth referred to asMRZ) [12] present a payment mechanism based on properscoring rules that is particularly well suited for online feed-back forums. In their mechanism, a central processing fa-cility “scores” every submitted feedback by comparing itwith another report (called the reference report) about thesame good. The score does not reflect the agreement withthe reference report; instead it measures the quality of theprobability distribution for the reference report, induced bythe submitted feedback. Payments directly proportional tothese scores make honest reporting a Nash equilibrium. Thepayments can then be scaled so that in equilibrium, the re-turn when reporting honestly is better by at least a margin∆. However, this scaling can lead to arbitrarily high feed-back payments. This can be a problem because the pay-ments cause a loss to the reputation mechanism that mustb e made up in some way, either by sponsorship or by chargeslevied on the users of the reputation information.In this paper, we use the idea of automated mechanismdesign [3, 14] and compute optimal payments that minimizethe budget required to achieve a certain margin ∆. We thuslose the simplicity of a closed-form scoring rule, but gainin efficiency of the mechanism. Specifically, we derive theoptimal payment scheme such that:• given a required margin ∆ to offset reporting and hon-esty costs, the expected budget required for feedbackpayments is minimized; or, conversely,• given certain budget