Learning against Non-credible Second-Price Auctions

The standard framework of online bidding algorithm design assumes that the seller commits himself to faithfully implementing the rules of the adopted auction. However, the seller may attempt to cheat in execution to increase his revenue if the auction belongs to the class of non-credible auctions. For example, in a second-price auction, the seller could create a fake bid between the highest bid and the second highest bid. This paper focuses on one such case of online bidding in repeated second-price auctions. At each time t, the winner with bid bt is charged not the highest competing bid dt but a manipulated price pt = α0 dt + (1-α0) bt, where the parameter α0 ∈ [0, 1] in essence measures the seller's credibility. Unlike classic repeated-auction settings where the bidder has access to samples (ds)s=1t-1, she can only receive mixed signals of (bs)s=1 t-1, (ds)s=1 t-1 and α0 in this problem. The task for the bidder is to learn not only the bid distributions of her competitors but also the seller's credibility. We establish regret lower bounds in various information models and provide corresponding online bidding algorithms that can achieve near-optimal performance. Specifically, we consider three cases of prior information based on whether the credibility α0 and the distribution of the highest competing bids are known. Our goal is to characterize the landscape of online bidding in non-credible second-price auctions and understand the impact of the seller's credibility on online bidding algorithm design under different information structures.