  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 provide the first guarantees of
strategic-robustness and incentive-compatibility for Gradient Ascent.
  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 reduces to $O(\log
T)$ when the competition is stationary and stochastic, which drastically
improves upon the previous best of $O(\sqrt{T})$. 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. 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. Altogether, these guarantees make our algorithms the first to
simultaneously achieve both optimal regret and strategic-robustness.
