# reputationaware_continuous_double_auction__36681fa6.pdf

Reputation-Aware Continuous Double Auction

Yuan Liu Jie Zhang Han Yu Chunyan Miao School of Computer Engineering Nanyang Technological University, Singapore {yliu3, zhangj, han.yu, ascymiao}@ntu.edu.sg http://trust.sce.ntu.edu.sg/ liuyuan/

Truthful bidding is a desirable property for continuous double auctions (CDAs). Many incentive mechanisms have been proposed to elicit truthful bids. However, existing truthful CDA mechanisms often overlook the possibility that sellers may choose not to deliver the auctioned items to buyers as promised. In this situation, buyers may become unwilling to bid their true valuations in the future to compensate for their risks of being cheated, thereby rendering CDAs ineffective. In this paper, we propose a novel reputation-aware CDA (named RCDA) mechanism to consider the honesty of auction participants. It dynamically adjusts bids and asks according to the reputation of participants to reflect the risks involved in the transactions. Theoretical analysis proves that RCDA is effective in eliciting truthful bids from buyers and sellers in the presence of possible dishonest behavior from both buyers and sellers.

Introduction Auctions have been widely used in the exchange of items ranging from antiques, jewelery, and home furniture. In particular, continuous double auctions (CDA) with multiple buyers and sellers are becoming increasingly popular in electronic marketplaces (Bredin and Parkes 2005; Lwasaki et al. 2013). Each bidder (buyer) or asker (seller) has a private valuation for an item, and in truthful auction mechanisms, e.g., (Bredin and Parkes 2005), the weakly dominant strategy is to bid/ask their true valuations. Existing truthful CDA mechanisms generally have one important assumption: both buyers and sellers will fulfill their contractual obligations once their bids are matched. In the case where sellers choose not to deliver auctioned items as promised after receiving payment, buyers will suffer losses (Zhang, Cohen, and Larson 2012). This may, in turn, cause the buyers to be unwilling to bid their true valuations in the future, in an attempt to compensate for the risks of being cheated. Thus, existing truthful CDA mechanisms are not effective in the presence of malicious sellers. To address this problem, in this paper, we propose a novel reputation-aware continuous double auction (RCDA) mechanism. Buyers bids are adjusted by RCDA according to

Copyright c 2014, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

the reputation of sellers, and sellers asks are also adjusted considering the credibility of buyers. Here, the reputation of a seller reflects the the seller s probability of delivering the promised items; the credibility of a buyer reflects the buyer s probability of providing truthful opinions about the sellers after their transactions. Theoretical analysis proves that RCDA is truthful in the presence of dishonest behavior of auction participatnts.

The RCDA Mechanism In RCDA, both buyers and sellers submit their requests for buying or selling a single item as they normally do in standard CDAs. Based on their requests as well as their reputation or credibility1, RCDA matches buyers with sellers, and determines the prices paid by the buyers and those paid to the sellers. After a transaction, each buyer will submit a binary rating to evaluate the performance of the matched seller (i.e. positive rating for satisfactory delivery, and negative rating otherwise), which are aggregated by an existing trust/reputation model. Following the conventions of standard CDAs, a buying request is referred to as a bid , and a selling request as an ask . The bid of a buyer i is denoted as bi (bi > 0), and the ask of a seller j as aj (aj < 0).

The Bids Adaption Process As the expected utility that buyer i can gain depends on the likelihood of seller j delivering the promised item to i s satisfaction, it is reasonable that the bid bi provided by i should reflect the risk taken by i when trusting j. In view of this, we propose an adaptive bid component in RCDA. We assume buyer i could gain utility of vi from a satisfactorily delivered item; otherwise, the buyer gains 0 utility. Thus, the expected utility gain from a transaction with seller j whose reputation is Rj [0, 1] can be calculated as vij = Rjvi. For different sellers, a buyer s bid should be adjusted according to the sellers reputation. Specifically, buyer i s bid bi for an item provided by a particular seller j with reputation Rj is adjusted by RCDA as follows:

bj i = Rjbi. (1) With RCDA, a buyer only needs to provide her true valuation for the item, and her bid will then be automatically adjusted by Equation (1) before being presented to each seller.

1These values can be computed by many existing trust models, such as (Zhang, Cohen, and Larson 2012).

Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence

This process is transparent to the buyer so that she does not have to behave differently from as in a standard CDA.

The Asks Adaption Process

Given that buyer ratings affect a seller s reputation which, in turn, influences the seller s future profit, it is reasonable that an honest seller prefers to trade with buyers with high credibility. By selling an item to buyer i with credibility Ci [0, 1], seller j can expect to receive a truthful rating with probability Ci. Then, seller j has a probability 1 Ci of being harmed by an untruthful rating from buyer i. This will reduce seller j s future opportunity of transacting with credible buyers, which is referred to as the opportunity cost. Thus, the opportunity cost for seller j to transact with buyer i is inversely related to Ci. Specifically, when seller j submits an asking price of aj, it reflects j s expected gain from selling the item, and that she should receive a truthful rating from the buyer. Any decrease in seller j s reputation as a result of untruthful ratings will lead to lowered bids from future buyers according to Equation (1). Thus, the opportunity cost for seller j in trading with buyer i whose credibility is Ci is a decreasing function of Ci. When the credibility of buyer i is 1, there is no extra cost caused by untruthful ratings. In this case, it is reasonable that seller j is willing to reveal her true valuation for the item, aj, to the buyer. Otherwise, the ask value should be adjusted higher to reduce the chance of matching with less credible buyers. Thus, aj is adjusted for buyer i whose credibility is Ci by:

ai j = aj + aj(1 Ci). (2)

Similar to the case of the adaptive bid, this process is transparent from a seller s perspective so that she does not have to behave differently from as in a standard CDA.

The Pricing Process

With the bids and asks adjusted, the next important step is to determine which buyer-seller pairs should conduct transactions and how much they should pay or receive. RCDA first searches for the pair with the highest bj i + ai j value. Then, for buyer i, RCDA will search for a seller k who satisfies arg maxk,k =i{bk i + ai k > 0}. Similarly, for seller j, RCDA will search for another buyer m who satisfies arg maxm,m =j{bm i + ai m 0}. Then, the prices for buyer i and seller j are calculated as follows:

pi = bj k + ak j ai j, pj = (bm i + ai m bj i). (3)

In the proposed matching and pricing scheme, credible buyers with high bids and reputable sellers with low asks are matched first, and the price is determined by their respective second-choice transaction partners.

Theoretical Analysis

Here, we theoretically analyze the effectiveness of RCDA in eliciting truthful bids when malicious behavior exists.

Proposition 1 RCDA is a truthful mechanism.

Proof 1 For a buyer i with true valuation bi for an item, and a seller j with true cost aj for the same item, we need to show that among all possible bids ˆbi from buyer i, setting ˆbi = bi maximizes her utility. For simplicity, we ignore ties because the proof works with any arbitrary tie breaking. Two cases then need to be considered.

Case 1: buyer i belongs to the buyer-seller pair with the highest bj i + ai j value by following RCDA. If i were to bid ˆbi < bi such that ˆbj i + ai j < bj k + ak j , then she loses the auction and receives zero utility; If i were to bid ˆbi < bi such that ˆbj i + ai j = bj k + ak j , then she has probability 0.5 of losing the auction and receiving zero utility. The expected utility from decreasing her bid is lower than that from bidding truthfully, because the price does not only depend her own bid; If i were to bid ˆbi > bi such that ˆbj i + ai j > bj k + ak j , then she still wins the auction and gains the same utility as if she bids truthfully.

Case 2: buyer i does not belong to the buyer-seller pair with the highest bj i +ai j value by following RCDA (i.e., there exists another buyer k such that bj k + ak j is the highest). If i were to bid ˆbi > bi such that ˆbj i + ai j bj k + ak j , then she wins the auction and pays pi > bi j which brings worse (negative) utility for i than bidding truthfully; If i were to bid ˆbi > bi such that ˆbj i + ai j < bj k + ak j , or bid ˆb < bi, then she still loses the auction and gains zero utility which is the same as bidding truthfully.

In all cases, buyer i has no incentive to bid any valuation other than her true valuation for the item. Similarly, for seller j, it can be shown that ˆaj = aj is her weakly dominant strategy. Thus, RCDA is a truthful mechanism in the presence of malicious behavior.

Conclusion and Future Work In this paper we proposed a reputation-aware CDA mechanism that adapts bids and asks for buyers and sellers according to their reputation/credibility (honesty of their behaviors). Theoretical analysis has shown that the proposed mechanism is truthful where the weakly dominant strategy for any buyer or seller is to bid/ask truthfully, even in the presence of malicious behavior. In future work, we will analyze other properties of RCDA, such as budget balance.

References Bredin, J., and Parkes, D. C. 2005. Models for truthful online double auctions. In UAI, 50 59. Lwasaki, A.; Fujita, E.; Todo, T.; Yao, M.; and Yokoo, M. 2013. VCG-equilvalent in expectation mechanism: General framework for constructing iterative combinatorial auction mechanisms. In AAMAS, 699 706. Zhang, J.; Cohen, R.; and Larson, K. 2012. Combinding trust modeling and mechansim design for promoting honesty in e-marketplaces. Computational Intelligence 28(4):549 578.