  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 $b_t$ is charged not the highest competing bid $d_t$ but a
manipulated price $p_t = \alpha_0 d_t + (1-\alpha_0) b_t$, where the parameter
$\alpha_0 \in [0, 1]$ in essence measures the seller's credibility. Unlike
classic repeated-auction settings where the bidder has access to samples
$(d_s)_{s=1}^{t-1}$, she can only receive mixed signals of $(b_s)_{s=1}^{t-1}$,
$(d_s)_{s=1}^{t-1}$ and $\alpha_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 $\alpha_0$ and the distribution of
the highest competing bids are known. Our goal is to characterize the landscape
of online bidding in non-credible auctions and understand the impact of the
seller's credibility on online bidding algorithm design under different
information structures.
