The amount of business taking place in online marketplaces such as eBay is growing rapidly. At the end of 2005 eBay Inc. reported annual growth rates of 42.5% [3] and in February 2006 received 3 million user feedback comments per day [1]. Now we are faced with the task of using the limited information provided on auction sites to transact with complete strangers with whom we will most likely only interact with once. People will naturally be comfortable with old fashioned “corner store” business practice [14], based on a person to person trust which is lacking in large-scale electronic marketplaces such as eBay and Amazon.com. We analyse reasons why the current feedback scores on eBay and most other online auctions are too positive. We introduce AuctionRules, a trust-mining algorithm which captures subtle indications of negativity from user comments in cases where users have rated a sale as positive but still voiced some grievance in their feedback. We explain how these new trust values can be propagated using a graph-representation of the eBay marketplace to provide personalized trust values for both parties in a potential transaction. Our experimental results show that AuctionRules beats seven benchmark algorithms by up to 21%, achieving up to 97.5% accuracy , with a false negative rate of 0% in comment classification tests compared with up to 8.5% from other algorithms tested.