Learning to bid in repeated first-price auctions is a fundamental problem at
the interface of game theory and machine learning, which has seen a recent
surge in interest due to the transition of display advertising to first-price
auctions. In this work, we propose a novel concave formulation for
pure-strategy bidding in first-price auctions, and use it to analyze natural
Gradient-Ascent-based algorithms for this problem. Importantly, our analysis
goes beyond regret, which was the typical focus of past work, and also accounts
for the strategic backdrop of online-advertising markets where bidding
algorithms are deployed -- we prove that our algorithms cannot be exploited by
a strategic seller and that they incentivize truth-telling for the buyer.
Concretely, we show that our algorithms achieve $O(\sqrt{T})$ regret when the
highest competing bids are generated adversarially, and show that no online
algorithm can do better. We further prove that the regret improves to $O(\log
T)$ when the competition is stationary and stochastic. Moving beyond regret, we
show that a strategic seller cannot exploit our algorithms to extract more
revenue on average than is possible under the optimal mechanism, i.e., the
seller cannot do much better than posting the monopoly reserve price in each
auction. Finally, we prove that our algorithm is also incentive compatible --
it is a (nearly) dominant strategy for the buyer to report her values
truthfully to the algorithm as a whole.

学习在重复的一价拍卖中进行投标是博弈论和机器学习之间的一个基本问题，我们提出了一种新颖的凸形式用于分析一价拍卖中的纯策略投标，并证明了我们的算法可以有效鼓励拍卖买家真实报价并且无法被巧言利用。