Bidding in Uniform Price Auctions for Value Maximizing Buyers

Optimal Universally Feasible Class of Bidding Policies. In Section 4, as our first result, we show that the optimal class of UF bidding policies, denoted by $\mathcal{P}_{m}^{\star}$, can be viewed as a natural extension of truthful bidding, depending only on the bidder’s valuation vector $[v_{1},v_{2},\ldots,v_{K}]$ with diminishing returns (i.e., $v_{1}\geq v_{2}\geq\ldots\geq v_{K}$) and target RoI, $\gamma$:

The theorem demonstrates that once the bidder determines the quantities $q_{1},\ldots,q_{m}$, the best action is to submit $w_{Q_{1}}/(1+\gamma)$ as the first bid, which represents the normalized average per-unit value of the first $Q_{1}=q_{1}$ units. Subsequently, for the second bid, one should submit $w_{Q_{2}}/(1+\gamma)$, which is the normalized average per-unit value of the first $Q_{2}=q_{1}+q_{2}$ units, and so forth. This theorem, which further emphasizes the nested structure within the optimal UF bidding policies as illustrated in Figure 2, reinforces the conventional wisdom that bidding in uniform price auctions should follow a truthful pattern. Specifically, the optimal UF class of bidding policies depends solely on the valuation vector $[v_{1},\ldots,v_{K}]$ and $\gamma$.

Price of Universal Feasibility (RoI-Robustness). To characterize the optimal bidding policies, we enforce the desirable property of the bidding policies being UF. This leads to robust bidding policies that are RoI feasible regardless of the competing bids. However, one might be curious about the cost incurred when enforcing the bidding policies to be UF. In Section 5, we quantify this cost by introducing a concept called the price of universal feasibility, which is the maximum ratio of the value obtained by an optimal bidding policy that is not necessarily UF to the value of the optimal UF bidding policy. We show that:

Generalized $m$-Uniform Bidding versus Classical Uniform Bidding (with $m=1$). In  Section 6, we study the impact of generalizing the classical uniform bidding format, where the bidder submits a single pair of bid and quantity. It is evident that by increasing the number of bid-quantity pairs, as done in $m$-uniform bidding, one anticipates an increase in the bidder’s obtained value. In this work, we characterize this gain and show that, in the best case, the value can exhibit linear growth with respect to $m$. The main result of this section is:

Discussion on Learning to Bid. In Section 7, we discuss how the bidder can identify the optimal (value-maximizing) bidding policy within the class $\mathcal{P}_{m}^{\star}$. For a constant $m$, off-the-shelf no-regret online learning algorithms can help identify the optimal policy efficiently. However, such methods can become computationally intractable for a large value of $m$. To this end, we also propose an efficient (polynomial time) method for identifying an $(1-1/e)$-approximate solution by leveraging the structure of the bidding policies.

Numerical Simulations. In Section 8, we conduct numerical simulations on semi-synthetic data generated from aggregate statistics of the past EU ETS auctions. We observe that the UF bidding policies perform significantly better in practice than the theoretical bounds presented in Section 5 and Section 6. These experiments suggest that bidders can obtain near-optimal performance (in terms of obtained value) while adhering to simple UF bidding strategies in uniform price auctions.

The core challenge in our work stems from the interdependence of the values obtained by the constituent bid-quantity pairs in a $m$-uniform bidding policy. Recall that a $m$-uniform bidding policy consists of $m$ bid-quantity pairs of the form $(b_{i},q_{i})$. In the considered setting, the values obtained by the individual bid-quantity pairs in the bidding policy are interdependent; i.e., even for a fixed competing bid profile, the value obtained by any bid-quantity pair $(b_{j},q_{j})$ depends on the remaining $m-1$ bid-quantity pairs in the policy. As a key technical contribution (see Lemma 3 and a stronger version in Lemma 8), we show that the value obtained by a $m$-uniform RoI feasible bid (see definition in Section 2.1) can be expressed as the maximum of the value obtained by $m$ independent 1-uniform feasible bids $(b_{j}^{\prime},q_{j}^{\prime})$. This result decouples the dependency equipping us to approximate the value obtained by the optimal $m$-uniform UF policy using 1-uniform UF policies as components; which is crucial for establishing the upper bounds in Section 5 and Section 6. In Section 7, we utilize it to learn an efficient approximate optimal solution in the online setting.

The second key challenge lies in obtaining matching lower bounds for Theorem 1.2 and Theorem 1.3 (formally stated as Theorem 5.2 and Theorem 6.1 respectively). Formally, to demonstrate that the ratio obtained for a problem instance is within an interval of a (small) $\delta$ from the upper bound, we need to consider a problem instance with $T=\Theta(1/\delta^{m})$ auctions, each selling $K=\Theta(1/\delta^{m})$ units. As the number of auctions and the number of bidding policies become exponentially large in $m$, the construction of the problem instance and its analysis are quite non-trivial. The construction of the problem instance crucially leverages the result describing the value obtained by 1-uniform bids when compared with the optimal bidding policy (see Lemma 9 for the result and, Section B.2 and Section B.3 for the construction of the problem instances).

Value Maximizers and RoI Constraints. The concept of agents as value maximizers within financial constraints is a well-established notion in microeconomic theory (Mas-Colell et al., 1995, pp. 50). In mechanism design literature, one of the earliest explorations of value-maximizing agents was conducted by Wilkens et al. (2016). Their work primarily delved into the single-parameter setting, characterizing truthful auctions for value maximizers. Similarly, Fadaei and Bichler (2016) studied revenue-maximizing mechanisms in combinatorial markets tailored for such agents.

In recent years, there has been a surge of interest in RoI-constrained value maximizers, particularly in the realms of autobidding and online advertising (Aggarwal et al., 2019; Balseiro et al., 2021a; Deng et al., 2021; Balseiro et al., 2021b, 2022; Deng et al., 2023a, b; Golrezaei et al., 2023; Liaw et al., 2023). See Golrezaei et al. (2021c) as one of the earliest studies on auction design for RoI-constrained buyers, validating such soft financial constraints using data from online advertising auctions.

Our contribution to this body of research lies in the study of value-maximizing buyers in uniform price auctions under RoI constraints. We demonstrate that these buyers can effectively employ nested bidding strategies that depend only on their valuation vector.

Combinatorial Auctions. Our research contributes to the extensive body of literature concerning combinatorial auctions, as evidenced by works by De Vries and Vohra (2003); Pekeč and Rothkopf (2003); Blumrosen and Nisan (2007); Palacios-Huerta et al. (2022). In this work, we focus on auctions for identical goods, which find widespread application in various practical scenarios, including Treasury auctions (Garbade and Ingber, 2005; Binmore and Swierzbinski, 2000; Nyborg et al., 2002), procurement auctions (Cramton and Ausubel, 2006), wholesale electricity markets (Tierney et al., 2008; Fabra et al., 2006), and emissions permit auctions (Goulder and Schein, 2013; Schmalensee and Stavins, 2017; Goldner et al., 2020). Several works have focused on designing truthful multi-unit auctions (in a utility-maximizing sense) that achieve a good approximation of social welfare and/or revenue (Dobzinski and Nisan, 2015; Dobzinski and Leme, 2014; Borgs et al., 2005). Our work contributes to this literature by studying uniform price auctions from the perspective of bidding algorithms for value-maximizing buyers.

Bidding in Auctions and Auction Parameter Optimization. Traditionally, the problems of bidding in auctions and refining auction parameters have been studied under Bayesian settings (Myerson, 1981; Hartline and Roughgarden, 2009; Beyhaghi et al., 2021; Riley and Samuelson, 1981). However, any bidder rarely has an exact characterization of the private valuations (or other parameters) of its competitors (Wilson, 1985). Consequently, in recent years, there has been a growing interest in studying these problems under data-driven settings, for both offline and online contexts. Examples include Sandholm (2003) for automated mechanism design using valuation samples, Roughgarden and Wang (2019); Derakhshan et al. (2022, 2021); Golrezaei et al. (2021a) for using offline or online data to set reserve prices in VCG auctions, Balseiro et al. (2019) for online problems in bidding in first-price auctions, and Golrezaei et al. (2021b) for optimizing boost values of boosted second-price auctions using historical auction bids.

In this line of work, the closest to our work is by Brânzei et al. (2023a); Galgana and Golrezaei (2023). They designed the optimal bidding algorithms for agents with quasilinear utilities in multi-unit uniform price and pay-as-bid auctions on the offline data and leveraged these offline algorithms to obtain their online counterparts with no-regret property. In our work, as one of our focus, we also design an optimal class of bidding policies in multi-unit uniform price auctions. However, as the main difference, we focus on value-maximizing RoI-constrained buyers.

Auction Format. Each bidder $i$ submits a bid vector $\mathbf{b}\in\mathbb{R}^{\overline{M}}_{\geq 0}$. The bids submitted by other bidders are denoted as $\bm{\beta}_{-i}$, and we define $\bm{\beta}:=(\mathbf{b},\bm{\beta}_{-i})$.

• •

  Allocation Rule. The auctioneer collects the bids from all the bidders, sorts the bids in non-increasing order, and allocates items to the bidders with the top $K$ bids. That is, if bidder $i$ has $j$ bids in the top $K$ positions, they are allocated $j$ items. We assume that the bidders submit bids from a continuous space; hence, there are no ties almost surely.

• •

  Payment Rule. The auctioneer follows the last-accepted-bid (LAB) payment rule (bidders pay the $K^{th}$ highest bid per unit). An alternative pricing rule is the first-rejected-bid (FRB) payment rule (agents pay the $(K+1)^{th}$ highest bid per unit). The per-unit price is also referred to as the clearing price. In this work, we primarily focus on the LAB payment rule as it is more common in practice and has more appealing properties (see Brânzei et al. (2023a)), but the results can be extended for the FRB payment rule with careful modifications.

For a bid profile let $\bm{\beta}$, $x_{i}(\bm{\beta})$ and $p(\bm{\beta})$ denote the number of units allocated to bidder $i$ and the clearing price respectively. So, the total value obtained, $V_{i}(\bm{\beta})$, and total payments paid, $P_{i}(\bm{\beta})$, is:

$\displaystyle V_{i}(\bm{\beta})=\sum_{j\leq x_{i}(\bm{\beta})}v_{i,j}\quad\text{and}\quad P_{i}(\bm{\beta})=p(\bm{\beta})\cdot x_{i}(\bm{\beta})\,.$

(2)

Repeated Setting. In practice, several multi-unit auctions, such as emission permit auctions, happen in a repeated fashion. Repeated auctions allow bidders to learn from the actions of all participants in previous rounds and improve their bidding policy successively. In this work, we primarily focus on this repeated setting. Formally, the auction described in the previous paragraph takes place sequentially in $T$ rounds indexed by $t\in[T]$. Let $\bm{\beta}_{-i}^{t}$ denote the bids submitted by all bidders except bidder $i$ in round $t$ and $\bm{\beta}_{-i,t}^{-(j)}$ be the $j^{th}$ smallest winning bid in the absence of bids from bidder $i$ for round $t$. The bid history $\mathcal{B}_{-i}=[\bm{\beta}_{-i}^{1},\dots,\bm{\beta}_{-i}^{T}]$ contains bids submitted by all bidders except bidder $i$ for the past $T$ auctions. In round $t$, suppose the bidder $i$ submits a bid $\mathbf{b}^{t}$ and the bid profile is $\bm{\beta}^{t}:=(\mathbf{b}^{t};\bm{\beta}_{-i}^{t})$. Let $x_{i}(\bm{\beta}^{t})$ and $p(\bm{\beta}^{t})$ be the number of units allocated to bidder $i$ and the clearing price, respectively, in round $t$. Hence, the total value obtained is $V_{i}(\bm{\beta}^{t})=\sum_{j\leq x_{i}(\bm{\beta}^{t})}v_{i,j}$, and total payment is $P_{i}(\bm{\beta}^{t})=p(\bm{\beta}^{t})\cdot x_{i}(\bm{\beta}^{t})$.

Value Maximizing Bidders. The objective of the bidders is to maximize their individual total value while adhering to a constraint that ensures the total value obtained is at least a constant multiple of the payments made to acquire those items. This constraint can be equivalently expressed as a return-on-investment (RoI) constraint. We assume that the target RoI (i.e., the multiplier), denoted as $\gamma\geq 0$, is both private and fixed for each bidder $i$. Formally, to derive an optimal bidding policy, a value-maximizing bidder solves Problem (VM).

	$\displaystyle V^{*}(\mathcal{B}_{-i})=\max_{\mathbf{b}\in\mathbb{R}^{\overline{M}}_{\geq 0}}$	$\displaystyle~{}\sum_{t=1}^{T}V_{i}(\mathbf{b};\bm{\beta}_{-i}^{t})$			(VM)
	such that	$\displaystyle~{}V_{i}(\mathbf{b};\bm{\beta}_{-i}^{t})\geq(1+\gamma)P_{i}({\mathbf{b}};\bm{\beta}_{-i}^{t}),$	$\displaystyle\forall t\in[T]\,.$

Here, $\mathcal{B}_{-i}=[\bm{\beta}_{-i}^{t}]_{t\in[T]}$. If in round $t$, the RoI constraint is violated, we define $V_{i}(\mathbf{b};\bm{\beta}_{-i}^{t})=-\infty$. We say a bid vector is feasible if the RoI constraints hold true for each round.

In problem (VM), we enforce the RoI constraints for each auction individually rather than as an aggregate constraint over $T$ rounds, as is typically assumed in online ad auctions (Deng et al., 2021, 2022; Feng et al., 2023). Lucier et al. (2023) consider constraints similar to us, i.e., the value obtained is at least a constant times the payment in each auction for autobidders which they term as marginal RoI (or value) constraint. In this work, we drop the prefix ‘marginal’ for the sake of brevity. Trivially, if the constraints for (VM) hold true for each round, they also hold true in aggregate. The rationale behind imposing constraints for each round is that, unlike ad auctions that often occur simultaneously and frequently, multi-unit auctions in the context of Treasury and emission permit auctions typically take place sequentially over much longer time horizons. It is therefore intuitive that bidders aim to maintain profitability in each auction, rather than waiting for a potentially indefinite period to cover their losses¹¹1Although EU ETS emission permit auctions are scheduled to occur regularly, regulations stipulate that an auction may be canceled if the bidders’ demand falls short of the supply of permits or if the auction clearing price does not meet the reserve prices (Regulations, 2019). Hence, the bidders are more likely to ensure feasibility in each round..

We conclude this section by noting the resemblance between the offline optimization problem in (VM) and those studied in Roughgarden and Wang (2019), Derakhshan et al. (2022), Galgana and Golrezaei (2023), and Brânzei et al. (2023a). Roughgarden and Wang (2019) focus on optimizing reserve prices in VCG auctions with access to historical bid prices, while Brânzei et al. (2023a) and Galgana and Golrezaei (2023) derive optimal bidding policies for quasilinear bidders in multi-unit auctions with similar information available. Both studies demonstrate that efficiently solving the problem and gaining insights into its structure in the offline setting is instrumental in designing no-regret online learning algorithms. For a more in-depth exploration of leveraging offline algorithms to create no-regret learning algorithms, we refer readers to Roughgarden and Wang (2019); Niazadeh et al. (2022); Brânzei et al. (2023a).

Most of the research literature on multi-unit auctions assumes that bidders follow the standard bidding format, wherein they submit a vector of individual bids, with each bid corresponding to one unit (Brânzei et al., 2023a; Babaioff et al., 2023; Birmpas et al., 2019; Galgana and Golrezaei, 2023). In contrast, several works (e.g., (De Keijzer et al., 2013; Birmpas et al., 2019)) study uniform bidding, bidders submit bids in the form of $(b,q)$ pairs, where a bidder bids $b$ for the first $q$ items and zero for the remaining units. For a bid-quantity pair, $(b,q)$, we equivalently state that the bidder has a demand $q$ at bid $b$. We study a natural generalization of the uniform bidding policy, which we term as $m$-uniform bidding, for any integer $m\geq 1$.

The $m$-bidding format format can be viewed as a special case of the bidding language for product-mix auctions when only a single variety of goods is present (Klemperer, 2009). If $m=\overline{M}$, the bidding format is equivalent to standard bidding. However, in practice, bidders often submit only a few bid-quantity pairs. For instance, in the EU ETS emission permit auctions for 2023, bidders submitted an average of approximately 4.35 bid-quantity pairs per auction (EEX, 2023).

In fact, our generalization is motivated by practical settings, such as the aforementioned EU ETS emission auctions and the Treasury auctions, where the number of individual units $K$ can be quite large. Submitting a bid vector listing bid values for each individual unit becomes prohibitive in such cases. Similarly, using a single bid, as done in uniform bidding (which corresponds to a $1$-uniform bidding policy), to represent the entire valuation curve can be misleading and restrictive, particularly if the curve exhibits sharp decay across the items. Therefore, the $m$-uniform bidding policies offer a flexible and computationally efficient approach for submitting bids, a method widely utilized in practice (see an example in Fig. 1).

We illustrate how the auction works in the considered setting in Example 1.

Our objective in this work is to design an optimal bidding strategy, maximizing value from the perspective of a single bidder denoted as $i$. This bidding strategy should universally adhere to RoI feasibility, as defined below:

Alternatively put, UF bidding policies ensure that the total value obtained in any single auction is at least a constant (i.e., $(1+\gamma)\geq 1$) times the total payments for the auction. From the perspective of the bidders, this property is mild, natural and necessary. This property is particularly appealing because under UF bidding strategies, irrespective of the bids submitted by competitors, the bidder consistently maintains RoI feasibility. There is also an inherent necessity for a UF policy class because most sealed bid auctions do not disclose the individual bids ex post to protect sensitive financial information and prevent bidding malpractices. Hence, bidders need to formulate feasible bidding policies under limited information about the bids submitted by others. In addition, UF bidding policies are necessary to design online learning algorithms for bidding, where the bidder needs to submit a RoI feasible bid without having access to the competitors’ bids (see details in Section 7). This property is essential because a causal, optimal, but non-UF bidding policy may be infeasible in future rounds as highlighted in Example 2.

Having established the concept of UF bidding policies, we now focus on developing optimal UF bidding policies for any $m\in\mathbb{Z}_{>0}$. These policies solve the following problem:

	$\displaystyle V_{m}^{*}(\mathcal{B}_{-i})=\max$	$\displaystyle~{}\sum_{t=1}^{T}V_{i}(\mathbf{b};\bm{\beta}_{-i}^{t})$		($\textsc{VM-uni}_{m}$)
	such that	$\displaystyle\mathbf{b}=\langle(b_{1},q_{1}),\dots,(b_{k},q_{k})\rangle\in\mathcal{P}_{m}~{}\quad\text{and }\quad~{}k\in[m]\,.$		(3)

Here, with a slight abuse of notation, we denote $V_{m}^{*}(\mathcal{B}_{-i})$ as the maximum achievable value when considering UF bidding policies in $\mathcal{P}_{m}$, under the bid history, $\mathcal{B}_{-i}$. Observe that the optimal solution to problem ($\textsc{VM-uni}_{m}$) is RoI feasible as ${\bf b}\in\mathcal{P}_{m}$. Let $\mathbf{b}_{m}^{*}(\mathcal{B}_{-i})$ be a UF bidding policy in $\mathcal{P}_{m}$ that achieves the maximum value. We are now equipped to define an optimal UF class.

While being UF is essential, such a requirement can come at a cost. To quantify this cost, denoted as the ‘Price of Universal Feasibility’ or ‘PoUF’ for short, we consider the following strong benchmark. Under the benchmark, similar to Problem ($\textsc{VM-uni}_{m}$), we aim to find a $k$-uniform bidding policy $\mathbf{b}$, where $k\in[m]$, that maximizes the total value for a given bid history $\mathcal{B}_{-i}$. However, unlike Problem ($\textsc{VM-uni}_{m}$), we do not require $\mathbf{b}$ to be UF; that is, we do not enforce $\mathbf{b}\in\mathcal{P}_{m}$. Instead, we only require $\mathbf{b}$ to be RoI feasible under the bid history $\mathcal{B}_{-i}$.

Formally, our benchmark, denoted by $V^{\mathbf{OPT}}_{m}\left(\mathcal{B}_{-i}\right)$, is given as

	$\displaystyle V^{\mathbf{OPT}}_{m}\left(\mathcal{B}_{-i}\right)=\max_{\mathbf{b}}$	$\displaystyle~{}\sum_{t=1}^{T}V_{i}(\mathbf{b};\bm{\beta}_{-i}^{t})$			($\textsc{VM-opt}_{m}$)
	such that	$\displaystyle~{}V_{i}(\mathbf{b};\bm{\beta}_{-i}^{t})\geq(1+\gamma)P_{i}({\mathbf{b}};\bm{\beta}_{-i}^{t}),$	$\displaystyle\forall t\in[T]$
	and	$\displaystyle~{}\mathbf{b}=\langle(b_{1},q_{1}),\dots,(b_{k},q_{k})\rangle~{}$	$\displaystyle\quad\text{for some }\quad~{}k\in[m]\,.$

Let the optimal bidding policy be denoted as $\mathbf{b}_{m}^{\mathbf{OPT}}\left(\mathcal{B}_{-i}\right)$. We emphasize that $\mathbf{b}_{m}^{\mathbf{OPT}}\left(\mathcal{B}_{-i}\right)$ is not necessarily feasible for any other bid history except $\mathcal{B}_{-i}$.

The Price of Universal Feasibility is then defined as

$\displaystyle\textsc{PoUF}_{m}:=\max_{\mathcal{B}_{-i}}$

$\displaystyle~{}\frac{V^{\mathbf{OPT}}_{m}\left(\mathcal{B}_{-i}\right)}{V_{m}^{*}(\mathcal{B}_{-i})}\,.$

(PoUF)

This metric is analogous to established metrics in mechanism design, such as the price of anarchy (Koutsoupias and Papadimitriou, 1999), the price of stability (Anshelevich et al., 2008) to measure the inefficiency of equilibrium, and the price of fairness (Bertsimas et al., 2011) to measure the inefficiency due to fair division in resource allocation. Trivially, $1\leq\textsc{PoUF}_{m}<\infty$³³3Suppose for some $\mathcal{B}_{-i}$, $V^{\mathbf{OPT}}_{m}\left(\mathcal{B}_{-i}\right)=0$. By definition, $V_{m}^{*}(\mathcal{B}_{-i})=0$. In this case, we define $\frac{V^{\mathbf{OPT}}_{m}\left(\mathcal{B}_{-i}\right)}{V_{m}^{*}(\mathcal{B}_{-i})}=\frac{0}{0}=1$..

In Section 2.2, we introduced $m$-uniform bidding and justified its preference over the (1-)uniform bidding format. However, increasing the number of bid quantity pairs $m$ can increase the complexity of bidding (see our discussion in Section 7). Considering this, we aim to characterize the maximum benefit of increasing the number of bid quantity pairs $m$, compared to the base case of $m=1$.

To do so, we introduce the following two metrics

$\displaystyle\textsc{Ratio-uni}_{m}:=\max_{\mathcal{B}_{-i}}\frac{V_{m}^{*}(\mathcal{B}_{-i})}{V_{1}^{*}(\mathcal{B}_{-i})},\qquad\textsc{Ratio-opt}_{m}:=\max_{\mathcal{B}_{-i}}\frac{V^{\mathbf{OPT}}_{m}\left(\mathcal{B}_{-i}\right)}{V^{\mathbf{OPT}}_{1}\left(\mathcal{B}_{-i}\right)}\,.$

(4)

The first metric measures, in the best case, how much more value bidder $i$ obtains by submitting an optimal UF $k$-uniform bid where $k\in[m]$, compared with that an optimal UF $1$-uniform bid. The second metric does a similar comparison without restricting the bids to be UF. By definition, $1\leq\textsc{Ratio-uni}_{m},\textsc{Ratio-opt}_{m}<\infty$.

Recall from Definition 3 that the optimal UF class has two essential properties:

Property 1. It contains the optimal UF bidding policy for any $\mathcal{B}_{-i}$, and

Property 2. It is minimal in a downward closed sense to satisfy Property 1 (see Definition 3).

Showing Property 1. We begin by establishing a general result regarding the monotonocity of feasible bid vectors (not necessarily $m$-uniform bids) for value maximizing agents. As the result holds for any bid vector, it is also true for $m$-uniform bids.

The proof of Lemma 1 is presented in Section A.2. We now leverage Lemma 1 to show Property 1. To do so, we will argue that underbidding is a weakly dominated bidding strategy, i.e., for every underbid $\mathbf{b}$ (per Definition 4), there exists a non-underbidding (NUB) policy $\mathbf{b}^{\prime}\in\mathcal{P}_{m}$ such that for all bid histories, $\mathcal{B}_{-i}=[\bm{\beta}_{-i}^{t}]_{t\in[T]}$, $\sum_{t=1}^{T}V_{i}(\mathbf{b};\bm{\beta}_{-i}^{t})\leq\sum_{t=1}^{T}V_{i}(\mathbf{b}^{\prime};\bm{\beta}_{-i}^{t})$. To show this, suppose $\mathbf{b}=\langle(b_{1},q_{1}),\dots,(b_{k},q_{k})\rangle$, where $k\in[m]$, is an underbid. Consider $\mathbf{b}^{\prime}=\langle(b_{1}^{\prime},q_{1}^{\prime}),\dots,(b_{k}^{\prime},q_{k}^{\prime})\rangle$ such that $q_{j}^{\prime}=q_{j}$ and $b_{j}^{\prime}=\frac{w_{Q_{j}}}{1+\gamma},\forall j\in[k]$. By Theorem 3.1, we establish that $\mathbf{b},\mathbf{b}^{\prime}\in\mathcal{P}_{m}$. Invoking Lemma 1 completes the proof which shows that underbidding is a dominated strategy, and hence such policies can be removed from $\mathcal{P}_{m}$ to obtain the class of nested $m$-uniform policies, $\overline{\mathcal{P}}_{m}$.

Showing Property 2. We will show that $\overline{\mathcal{P}}_{m}$ satisfies Property 2 implying $\overline{\mathcal{P}}_{m}=\mathcal{P}_{m}^{\star}$. We claim that $\overline{\mathcal{P}}_{m}$ satisfies the conditions (also described in Definition 3) and thus complete the proof.

For any $k$-uniform bid $\mathbf{b}\in\mathcal{P}_{m}^{\star}$, where $k\in[m]$, there exists a bid history, $\mathcal{B}_{-i}=[\bm{\beta}_{-i}^{t}]_{t\in[T]}$, for which

• •

  $\mathbf{b}$ is optimal, i.e., $\sum_{t=1}^{T}V_{i}(\mathbf{b};\bm{\beta}_{-i}^{t})\geq\sum_{t=1}^{T}V_{i}(\mathbf{b}^{\prime};\bm{\beta}_{-i}^{t}),\forall~{}~{}\mathbf{b}^{\prime}\in\mathcal{P}_{m}^{\star}$,

• •

  the value obtained under $\mathbf{b}$ and $\mathcal{B}_{-i}$ is strictly larger than that under ANY $k^{\prime}$-uniform bid $\mathbf{b}^{\prime}\in\mathcal{P}_{m}^{\star}$ and $\mathcal{B}_{-i}$ where $k^{\prime}\leq k$. That is, $\sum_{t=1}^{T}V_{i}(\mathbf{b};\bm{\beta}_{-i}^{t})>\sum_{t=1}^{T}V_{i}(\mathbf{b}^{\prime};\bm{\beta}_{-i}^{t}),\forall~{}~{}\mathbf{b}^{\prime}\in\mathcal{P}_{k}^{\star}\setminus\{\mathbf{b}\}\,.$

Our construction. To show the claim, fix any $\mathbf{b}\in\overline{\mathcal{P}}_{m}$. Let $\mathbf{b}=\big{\langle}\big{(}\frac{w_{Q_{1}}}{1+\gamma},q_{1}\big{)},\dots,\big{(}\frac{w_{Q_{k}}}{1+\gamma},q_{k}\big{)}\big{\rangle}$. We construct the bid history, $\mathcal{B}_{-i}(\mathbf{b})$ consisting of $T=k$ rounds. In round $t\in[k]$, for a sufficiently small $\epsilon>0$ and $C\gg w_{1}$,

$\displaystyle\bm{\beta}_{-i,t}^{-(j)}(\mathbf{b})=\begin{cases}\frac{w_{Q_{t}+1}}{1+\gamma}+\epsilon,&~{}\text{if }1\leq j\leq Q_{t}\\ C,&~{}\text{if }Q_{t}<j\leq K\end{cases},$

$\displaystyle~{}\forall t\in[k],Q_{t}<\overline{M}\,.$

(5)

If $Q_{t}=\overline{M}$, set $\bm{\beta}_{-i,t}^{-(j)}(\mathbf{b})=\epsilon,\forall j\in[K]$. We illustrate an example of such a bid history in Table 1.

Note that for any (universally) feasible bidding policy, the maximum number of units that the bidder can get allocated in round $t$ is $Q_{t}$. We claim that $\mathbf{b}=\big{\langle}\big{(}\frac{w_{Q_{1}}}{1+\gamma},q_{1}\big{)},\dots,\big{(}\frac{w_{Q_{k}}}{1+\gamma},q_{k}\big{)}\big{\rangle}$ is an optimal bidding policy for $\mathcal{B}_{-i}(\mathbf{b})$.

To see this, consider any round $t$. In this round, exactly $Q_{t}$ bids, namely $\mathbf{b}[1:t]$, are higher than the competing bids in $\mathcal{B}_{-i}(\mathbf{b})$. As $\mathbf{b}\in\overline{\mathcal{P}}_{m}$, it is UF. Hence, bidding $\mathbf{b}=\big{\langle}\big{(}\frac{w_{Q_{1}}}{1+\gamma},q_{1}\big{)},\dots,\big{(}\frac{w_{Q_{k}}}{1+\gamma},q_{k}\big{)}\big{\rangle}$ wins $Q_{t}$ units in round $t,\forall t\in[k]$. So, it is an optimal bidding policy.

The proof of the second property is then completed by the following lemma.

We present the proof of Lemma 2 in Section A.3. The proof primarily uses the result from Lemma 3 which warrants an in-depth discussion and hence presented separately.

Here, we present only the proof of the upper bound on $\textsc{PoUF}_{m}$. The tightness of the bound is discussed in Section B.1 (for $m=1$) and Section B.2 (for $m\geq 2$).

We begin by defining the following metric for any bid history, $\mathcal{B}_{-i}=[\bm{\beta}_{-i}^{t}]_{t\in[T]}$,

$\displaystyle\textsc{PoUF}_{m}(\mathcal{B}_{-i}):=\frac{V^{\mathbf{OPT}}_{m}\left(\mathcal{B}_{-i}\right)}{V_{m}^{*}(\mathcal{B}_{-i})}=\frac{V^{\mathbf{OPT}}_{m}\left(\mathcal{B}_{-i}\right)}{\max_{\mathbf{b}\in\mathcal{P}_{m}^{\star}}\sum_{t=1}^{T}V_{i}(\mathbf{b},\bm{\beta}_{-i}^{t})}\,.$

(6)

By definition, $\textsc{PoUF}_{m}=\max_{\mathcal{B}_{-i}}\textsc{PoUF}_{m}(\mathcal{B}_{-i})$. We first establish upper bounds on $\textsc{PoUF}_{m}(\mathcal{B}_{-i})$ and then maximizing over $\mathcal{B}_{-i}$, we complete the proof.

Without loss of generality, let $\mathbf{b}_{m}^{\mathbf{OPT}}\left(\mathcal{B}_{-i}\right)=\langle(b_{1}^{*},q_{1}^{*}),\dots,(b_{m}^{*},q_{m}^{*})\rangle$ be the optimal solution to Problem ($\textsc{VM-opt}_{m}$) for $\mathcal{B}_{-i}=[\bm{\beta}_{-i}^{t}]_{t\in[T]}$ and define $Q_{\ell}^{*}=\sum_{j\leq\ell}q_{j}^{*}$. Suppose $\mathbf{b}_{m}^{\mathbf{OPT}}\left(\mathcal{B}_{-i}\right)$ is allocated $r_{t}^{*}$ units in round $t$. For any $j\in[m]$, let $T_{j}$ be the set of rounds in which the least winning bid is $b_{j}^{*}$, i.e.,

$\displaystyle T_{j}=\big{\{}t\in[T]:Q_{j-1}^{*}<r_{t}^{*}\leq Q_{j}^{*}\big{\}}\,.$

(7)

For any $j\in[m]$, partition $T_{j}$ into $T_{j,0}$ and $T_{j,1}$ such that $T_{j,0}$ is the set of rounds where the bidder gets strictly less than $Q_{j}^{*}$ units and $T_{j,1}$ is the set of rounds when she gets exactly $Q_{j}^{*}$ units:

$\displaystyle T_{j,0}=\Big{\{}t\in[T_{j}]:r_{t}^{*}<Q_{j}^{*}\Big{\}},\qquad T_{j,1}=\Big{\{}t\in[T_{j}]:r_{t}^{*}=Q_{j}^{*}\Big{\}}\,.$

(8)

For any $j\in[m]$, let

$\displaystyle\widehat{Q}_{j}=\begin{cases}\max\{r_{t}^{*}:t\in T_{j,0}\},~{}&\text{ if }T_{j,0}\neq\emptyset\\ Q_{j}^{*}~{}&\text{ if }T_{j,0}=\emptyset\,.\end{cases}$

In other words, $\widehat{Q}_{j}$ is the $2^{nd}$ highest number of units allocated to $\mathbf{b}_{m}^{\mathbf{OPT}}\left(\mathcal{B}_{-i}\right)$ over the rounds in $T_{j}$. Then, the result is obtained by showing the following claim.