Competitive algorithms about online reverse auctions

Similar to the concept of on-line auctions presented by Ron Lavi and Noam Nisan [3], this paper discusses pricing algorithms for on-line reverse auction which bidders arrive one by one and on-line buyer must be required to make a decision immediately about each bid as it is received. For online buyer in a reverse auction, we propose on-line mean pricing algorithm and on-line randomized pricing algorithm, and then prove that the two algorithms are competitive and incentive compatible. Moreover, as the bid prices concentrated in a small domain, by competitive analysis for the two algorithms, we find their merits which can avoid the results of purchasing failure or more cost caused by reservation price algorithm. Finally, an example is obtained to illustrate their application.