Learning against Non-credible Auctions

Digital advertising has experienced significant expansion due to the rapid rise of online-activities, surpassing traditional advertising as the dominant marketing influence in various industries. Between 2021 and 2022, digital advertising revenues in U.S. grew 10.8% year-over-year totalling $209.7 billion dollars (IAB 2023). In practice, a huge amount of online ads are sold via real-time auctions implemented on advertising platforms and advertisers participate in such repeated online auctions to purchase advertising opportunities. This has motivated a flourishing line of work to focus on the problem of online bidding algorithm design. In particular, learning to bid in repeated second-price auctions—often with constraints or unknown own valuations—has been well studied due to the popularity of this auction format in practice (Weed, Perchet, and Rigollet 2016; Balseiro and Gur 2019; Golrezaei et al. 2021; Balseiro, Lu, and Mirrokni 2022; Feng, Padmanabhan, and Wang 2022; Chen et al. 2022, 2023). However, these studies are in fact based on an implicit assumption that the seller commits himself to faithfully implementing the rules of the announced second-price auction.

The possibility that a seller can profitably cheat in a second-price auction was pointed out as early as the seminal paper (Vickrey 1961) that introduced this auction format. After observing all the bids, the seller can strategically exaggerate the highest competing bid and overcharge the winner up to the amount of her own bid. Several following papers studied the issue of seller cheating in second-price auctions (Rothkopf and Harstad 1995; Porter and Shoham 2005; McAdams and Schwarz 2007). Recent theoretical work by Akbarpour and Li (2020) formally modelled credibility in an extensive-form game where the seller is allowed to deviate from the auction rules as long as the deviation cannot be detected by bidders. They defined an auction to be credible if it is incentive-compatible for the seller to follow the rules in the presence of cheating opportunities. In a second-price auction, the seller can even charge the winner the amount of her own bid to obtain higher utility, with an innocent explanation that the highest and second-highest bids are identical. Therefore, the prevalent second-price auction belongs to the class of non-credible auctions in this framework. Taking credibility into consideration, advertisers are confronted with a question of practical importance: how should an advertiser bid in repeated non-credible second-price auctions to maximize her cumulative utility?

In this work, we formulate the above problem as an online learning problem for a single bidder. We consider the scenario with a single seller who runs repeated non-credible 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}$ for some $\alpha_{0}\in[0,1]$. The parameter $\alpha_{0}$ in essence captures the seller’s credibility, the extent to which the seller deviates from the second-price auction rules. Our linear model is equivalent to the classic bid-shilling model (Rothkopf and Harstad 1995; Porter and Shoham 2005; McAdams and Schwarz 2007) in expectation. In the bid-shilling model, the seller cheats by inserting a shill bid after observing all of the bids with probability $P^{c}$. The seller is assumed to take full advantage of his power so the winner will pay her own bid if the seller does cheat. Then the winner’s expected payment is $P^{c}b_{t}+(1-P^{c})d_{t}$. Moreover, no matter what charging rules the seller actually uses, as long as the estimated credibility within this linear model is away from $1$, it can be confirmed that the seller is cheating. We believe our results and techniques have implications for the more complicated setting with $p_{t}=h(b_{t},d_{t};\alpha)$.

We assume the highest competing bids $(d_{t})_{t=1}^{T}$ are i.i.d. sampled from a distribution $G$. The bidder aims to maximize her expected cumulative utility, which is given by the expected difference between the total value and the total payment. Moving to the information model, We investigate three cases of prior information: (1) known $\alpha_{0}$ and unknown $G$; (2) unknown $\alpha_{0}$ and known $G$; (3) unknown $\alpha_{0}$ and unknown $G$. For all three cases, we consider bandit feedback where the bidder can observe the realized allocation and cost at each round. For the last case where neither is unknown, we additionally consider full feedback where the price $p_{t}$ is always observable regardless of the auction outcome. More discussions on modeling will be placed in Section 2.

The key challenge of this problem lies in the lack of credibility and its impact on the learning process. If assuming the seller has full commitment, it is well known that truthful bidding is the dominant strategy in second-price auctions, but this truthful property no longer holds in non-credible second-price auctions. Identifying optimal bidding strategies for utility maximization requires not only knowing the bidder’s own values but also considering the strategies of her competitors and the seller. In classic repeated-auction settings (assuming a trustworthy seller), online bidding algorithms can collect historical samples $(d_{s})_{s=1}^{t-1}$ to estimate distribution $G$. However, the bidder in non-credible auctions needs to cope with an additional dimension of uncertainty: the available observations under either bandit or full feedback are all manipulated prices, i.e., mixed signals of $(b_{s})_{s=1}^{t-1},(d_{s})_{s=1}^{t-1}$ and $\alpha_{0}$. As a result, difficulties arise in the estimation of the distribution of her competitors’ bids and the seller’s credibility.

We consider the problem of online learning in repeated non-credible second-price auctions. We focus on a single bidder in a large population of bidders during a time horizon $T$. In each round $t=1,\ldots,T$, there is an available item auctioned by a single seller. The bidder perceives a value $v_{t}\in[0,1]$ for this item, and then submits a bid $b_{t}\in\mathbb{R}_{+}$ based on $v_{t}$ and all historical observations available to her. We denote the maximum bid of all other bidders by $d_{t}\in\mathbb{R}_{+}$. As usual, we use the bold symbol $\bm{v}$ without subscript $t$ to denote the vector $(v_{1},\ldots,v_{T})$; the same goes for other variables in the present paper.

We consider a stochastic setting where $v_{t}$ is i.i.d. sampled from a distribution $F$ and $d_{t}$ is i.i.d. sampled from a distribution $G$. The latter assumption follows from the standard mean-field approximation (Iyer, Johari, and Sundararajan 2014; Balseiro, Besbes, and Weintraub 2015) and is a common practice in literature. The main rationale behind this assumption is that when the number of other bidders is large, on average their valuations and bidding strategies are static over time. Whether $G$ is known to the bidder depends on the information structure while $F$ is always unknown to the bidder.

The seller claims that he follows the rules of the second-price auction, but he actually uses a combination of the first-price auction and the second-price auction. For simplicity, we assume a linear model. The auction outcome in round $t$ is then as follows: if $b_{t}\geq d_{t}$, the bidder wins the item and pays $p_{t}\coloneqq\alpha_{0}d_{t}+(1-\alpha_{0})b_{t}$, where $\alpha_{0}$ is assumed to be a fixed weight throughout the period; if $b_{t}<d_{t}$, the bidder loses the auction and pays nothing. Here we assume that ties are broken in favor of the bidder we concern to simplify exposition. We only consider $\alpha_{0}\in[0,1]$ since $\alpha_{0}<0$ will be immediately detected by the winner and $\alpha_{0}>1$ will lead to lower revenue than mere second-price auctions. One can observe the pricing rule follows the second-price auction when $\alpha_{0}=1$, and it follows the first-price auction when $\alpha_{0}=0$.

Let $x_{t}\coloneqq\mathbb{I}\left\{b_{t}\geq d_{t}\right\}$ be the binary variable indicating whether the bidder wins the item. Let $c_{t}\coloneqq x_{t}p_{t}$ be the bidder’s cost and let $r_{t}\coloneqq x_{t}v_{t}-c_{t}$ be the corresponding reward.

We start with the scenario where the credibility parameter $\alpha$ is known but the distribution $G$ of the highest competing bids is unknown. The algorithms and proofs of this section are deferred to Appendix A.

Observe that when $\alpha$ reaches an endpoint of $[0,1]$, this problem will degenerate into a bidding problem in repeated first-price or second-price auctions. Therefore, We will consider three cases separately: $\alpha_{0}=0$, $\alpha_{0}=1$, and $\alpha_{0}\in(0,1)$. The following Theorem 3.1 provides a comprehensive characterization of this setting. For each case, it establishes a regret lower bound and gives an algorithm with optimal performance up to log factors.

The lower bounds in Theorem 3.1 show that the hardness of this learning problem increases as $\alpha_{0}$ decreases, which demonstrates the impact of reduced credibility on online bidding optimization. When $\alpha_{0}$ deviates from $1$, truthful bidding is no longer a dominant strategy. The bidder has to learn the competitors’ bids to make decisions, and thus the distribution estimation error would introduce an inevitable regret of order $\Omega(T^{1/2})$. As long as $\alpha_{0}>0$, the bidder can infer the highest competing bid $d_{t}$ from her payment once she wins an auction by measuring the difference between $c_{t}$ and $b_{t}$. However, when $\alpha_{0}$ becomes $0$, $c_{t}\equiv b_{t}$ in winning rounds provides no additional information about $d_{t}$. The complete loss of credibility cripples the bidder’s ability to observe the competitive environment and estimate the distribution $G$, so the regret lower bound leaps from $\Omega(T^{1/2})$ to $\Omega(T^{2/3})$.

The first statement of Theorem 3.1 is trivial due to the nature of the second-price auction.

The second case is equivalent to bidding in repeated first-price auctions with binary feedback (receiving only $x_{t}=1$ or $0$), which can be modeled as a contextual bandits problem with cross learning:

• •

  Cross learning over contexts. The bidder in round $t$ not only receives the reward $r_{t}$ under $(v_{t},b_{t})$, but also observes the rewards $r^{\prime}$ under $(v^{\prime},b_{t})$ for every other $v^{\prime}$.

For the contextual bandits problem with cross-learning over contexts in the stochastic setting, Balseiro et al. (2019) proposed a UCB-based algorithm that can achieve an $O(\sqrt{KT})$ regret, where $K$ is the number of actions. Applying this algorithm to the auction setting results in a regret bound of $\widetilde{O}(\sqrt{KT}+T/K)$, where the last term comes from the discretization error and the upper bound becomes $\widetilde{O}(T^{2/3})$ with $K\sim T^{1/3}$. They also proved the regret lower bound is $\Omega(T^{2/3})$ via a reduction to the problem of dynamic pricing.

The third case is similar to bidding in repeated first-price auctions with censored feedback, where the seller runs first-price auctions and always reveals the winner’s bid to each bidder so the bidder can see the highest competing bid only if she loses the auction. Han, Zhou, and Weissman (2020) modeled that problem as a contextual bandits problem with cross learning, partial ordering:

• •

  Cross learning over contexts.

• •

  Partial ordering over actions. There exists a partial order $\preceq_{\mathcal{B}}$ over the action set $\mathcal{B}$. The bidder in round $t$ not only receives the reward $r_{t}$ under $(v_{t},b_{t})$, but also observes the rewards $r^{\prime}$ under $(v_{t},b^{\prime})$ for every other $b^{\prime}\preceq_{\mathcal{B}}b_{t}$.

• •

  Partial ordering over contexts. There exists a partial order $\preceq_{\mathcal{V}}$ over the context set $\mathcal{V}$ such that if $v_{1}\preceq_{\mathcal{V}}v_{2}$, then $b^{*}(v_{1})\preceq_{\mathcal{B}}b^{*}(v_{2})$ where $b^{*}(v)$ is the optimal auction under context $v$.

We carefully adapt their algorithm to our setting (Algorithm A.2) and verify that the third case with $\alpha_{0}\in(0,1)$ satisfies the above three properties:

• •

  Cross learning over values. The bidder can calculate $r^{\prime}$ under $(v^{\prime},b_{t})$ by

  $\displaystyle r^{\prime}=r_{t}+x_{t}(v^{\prime}-v_{t}).$

  (1)

• •

  Partial ordering over bids. If the bidder wins in round $t$, she can infer the highest competing bid $d_{t}$ by

  $\displaystyle d_{t}=\left(c_{t}-(1-\alpha_{0})b_{t}\right)/\alpha_{0}.$

  (2)

  Therefore the reward $r^{\prime}$ under $(v_{t},b^{\prime})$ for any other $b<b_{t}$ can be calculated by using the corresponding allocation $\mathbb{I}\left\{b\geq d_{t}\right\}$ and price $\alpha_{0}d_{t}+(1-\alpha_{0})b$. If the bidder loses the auction with $b_{t}$, she should also lose with $b^{\prime}<b_{t}$ and the reward $r^{\prime}$ is $0$.

• •

  Partial ordering over values. We have shown in the previous section that the optimal bid under value $v$ is $b^{*}(v,\alpha_{0})=\arg\max_{b}r(v,b,\alpha_{0})$. The following lemma shows it is a non-decreasing function in $v$.

Therefore, Algorithm A.2 can achieve an $\widetilde{O}(T^{1/2})$ regret when $\alpha_{0}\in(0,1)$. For the last piece of the puzzle, we prove the following regret lower bound. Remark that Lemma 3.5 holds for any $\alpha_{0}$, though the bound is not tight when $\alpha_{0}=0$.

We next consider the scenario where distribution $G$ is known but credibility $\alpha_{0}$ is unknown. The proofs of this section are deferred to Appendix B.

Our bidding algorithm for this setting is depicted in Algorithm 4.1. The bidder first conducts a one-round exploration to make an appropriate initialization. After receiving the value $v_{t}$ in each round $t=2,\ldots,T$, the bidder computes $\widetilde{\alpha}_{t}$, which is the estimation of $\alpha_{0}$ based on the historical observations in the past $t-1$ rounds. Recall that the optimal bid $b^{*}_{t}$ shown in Section 2 maximizes $r(v_{t},b,\alpha_{0})$. Thus, by the choice of $b_{t}$, if the estimator $\widetilde{\alpha}_{t}$ is close to $\alpha_{0}$, the expected reward $r(v_{t},b_{t},\alpha_{0})$ will be close to the optimal reward $r(v_{t},b_{t}^{*},\alpha_{0})$.

Equation 3 in Algorithm 4.1 aims to estimate $\alpha_{0}$ by fitting the observed rewards $\{r_{s}\}_{s=1}^{t-1}$ to the expected rewards $\{r(v_{s},b_{s},\alpha)\}_{s=1}^{t-1}$, which can be computed given $G$ is known. We apply the Azuma-Hoeffding inequality to obtain the following result.

For technical purpose, we make the following assumption.

The CDFs of many common distributions, such as gamma distributions, Gaussian distributions and uniform distributions, are all log-concave. The existence of positive bounds on the density function is also a standard and common assumption in various learning problems.

Remark that due to the additional assumption, we cannot actually draw the conclusion that estimating $\alpha$ is generally easier than estimating $G$ by comparing two lower bounds in Theorem 4.3 and Theorem 3.1. For example, the two-point method used in the proof of Lemma 3.5 constructs two discrete $G$ distributions to show no bidding algorithm can obtain low regret simultaneously under both distributions, while Assumption 4.2 has ruled out such bad cases.

A key step in the proof of Theorem 4.3 involves showing that the reward per round obtained by the bidder is close to the reward under optimal bid with high probability. We have with probability at least $1-\delta$, $\forall t$,

Then the regret upper bound can be established by showing $w_{t}\sim\sqrt{\log T/t}$ and summing up through $1$ to $T$. It is also worth discussing the robustness of this result. Even without Assumption 4.2, we can get

And with a weaker continuity condition, it still holds that $w_{t}\sim\sqrt{\log T/t}$.

An intuition on why the proof of the regret upper bound may fail under some discontinuous distributions is given in Example B.3. In spite of this, we conjecture that Algorithm 4.1 can also guarantee a lower regret in the case with discontinuous $G$ and we leave that as a future direction.

In this paper, we formulate and study the problem of learning against non-credible auctions and evaluate several algorithms under various information structures.

It remains an open problem whether we can further relax the assumptions over distribution $G$, especially for Theorem 4.3 and Theorem 5.6. Can we design a near optimal algorithm for general distributions with unknown $\alpha_{0}$ and known $G$? Can we apply the upper bound result of Theorem 5.6 to the bandit feedback model? In this work, we assume the seller’s credibility $\alpha_{0}$ is fixed. Another research direction is to consider that the seller may use a time-dependent charging rule. Will learning learning become impossible in this more complicated setting?