# Optimal Strategy Against Straightforward Bidding
in Clock Auctions

Jad Zeroual, Marianne Akian, Aurélien Bechler, Matthieu Chardy, Stéphane Gaubert

► To cite this version:

Jad Zeroual, Marianne Akian, Aurélien Bechler, Matthieu Chardy, Stéphane Gaubert. Optimal Strategy Against Straightforward Bidding in Clock Auctions. NETGCOOP 2024 - Network Games, Artificial Intelligence, Control and Optimization, Oct 2024, Lille, France. pp.83-93, 10.1007/978-3-031-78600-6_8. hal-04907159

HAL Id: hal-04907159

https://inria.hal.science/hal-04907159v1

Submitted on 12 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Optimal Strategy against Straightforward Bidding in Clock Auctions

Jad Zeroual<fnref n="1" />,<fnref n="2" />, Marianne Akian<fnref n="2" />, Aurélien Bechler<fnref n="1" />, Matthieu Chardy<fnref n="1" />, and Stéphane Gaubert<fnref n="2" />

jad.zeroual@polytechnique.edu, marianne.akian@inria.fr
aurelien.bechler@orange.com, matthieu.chardy@orange.com
stephane.gaubert@inria.fr

**Abstract.** We study a model of auction representative of the 5G auction in France. We determine the optimal strategy of a bidder, assuming that the valuations of competitors are unknown to this bidder and that competitors adopt the straightforward bidding strategy. Our model is based on a Partially Observable Markov Decision Process (POMDP). We show in particular that this special POMDP admits a concise statistics, avoiding the solution of a dynamic programming equation in the space of beliefs. We illustrate our results by numerical experiments, comparing the value of the bidder with the value of a perfectly informed one.

**Keywords:** Auction · Bidding Strategy · POMDP · Optimal Control

# 1 Introduction

## 1.1 Context

The acquisition of frequency spectrum is a vital aspect for telecommunications companies, as their core operations and success rely on these resources. Spectrum auctions have emerged as a prominent method for allocating these valuable resources. They have undergone significant evolution since their introduction, with various auction models being employed over time [15]. Initially, sealed-bid auctions were the preferred method for allocating spectrum rights. In this model, bidders would submit their bids simultaneously without knowing the bids of their competitors, the highest bidder winning the auction. However, this model was found to have limitations. For example, in auctions with several frequency bandwidths at stake (which is usually the case), bidders ended up paying very different amounts for the same goods (see page 8 of [13]). To address these limitations, auction models have evolved to accommodate more complex scenarios. One notable development was the introduction of combinatorial auctions, which allow bidders to bid on packages of items rather than individual items [8]. This innovation significantly improved the efficiency of spectrum allocation by enabling bidders to express their preferences for specific combinations of spectrum licenses. Among the various combinatorial auction formats, the *combinatorial clock auction* (CCA) has emerged as a popular choice for spectrum auctions.

<footnote n="1">¹ Orange Labs, Châtillon, France</footnote>

<footnote n="2">² INRIA and CMAP - Ecole Polytechnique, Palaiseau, France</footnote>
The CCA combines the advantages of the clock auction, where prices increase in rounds until demand equals supply, with the flexibility of combinatorial bidding. This format allows bidders to adjust their bids in response to changing prices, while also considering complementarities and substitutabilities. When the licenses present no complementarities, simplified CCA are implemented. In those cases, bidders can only bid on the number of items they want to acquire rather than the exact bundle of items. This type of auction was used as part of the 5G Auctions in France in 2020 [1]. In this context, [14,15] provide an introduction to auction theory. [12] further explores this issue, suggesting that there may not be a universally truthful strategy for CCA.

The evolution of spectrum auctions has also been motivated by the matter of *optimality* which can be defined differently: it could be to maximize revenue for the auctioneer [16], to maximize the *fairness* of the auction [11] or to maximize one player's profit selfishly. One way it has been studied is through prophet inequalities, which are inequalities between a strategic allocation and the optimal allocation. Those inequalities are widely studied in the literature for different forms of bidder's preference but almost always in a mechanism design perspective, so as to maximize social welfare [9,10]. However, few have studied the question of optimality in a competitive auction where a player wants to selfishly maximize its own utility. An example of such a study can be found in [2] which proposes a Mixed Linear Integer Programming approach in a perfect information setting. Nonetheless, the perfect information setting case presents a difficulty: companies do not disclose their valuation to their competitors in order to keep a competitive edge. As a matter of fact, such valuations can yield strategic information on a company's long-term projects. Thus, we can only have some coarse estimates of the opponent valuations, noting that data are generally insufficient to infer such estimations [1]. Hence, more practical approaches in imperfect information setting are used such as Partially Observable Markov Decision Processes (POMDP). In [4], this framework is used for inferring the utility of each player. Those models have been rare for modelling auction competition. One of the possible reasons is that such model requires to make assumptions on the behavior of competitors. A commonly studied behaviour is the *Straight-forward Bidding* (SB) introduced by [13]. It is characterized by its focus on immediate gains without considering future implications. As a matter of fact, [6] models an ad auction among SB players and [17] uses it as a baseline strategy to rate its agents. This strategy has been at the heart of studies mainly because, despite its simplicity, it can be optimal in various situations. For instance, SB is proven to be a weakly dominant strategy in auctions of 1 item [3]. Moreover, if each bidder demands a single item and has no preference for any of them, SB is a Bayes-Nash equilibrium [19]. What is more, this strategy yields to a situation comparable to a competitive equilibrium when the goods are substitutes for all bidders [13], which is the case for the 5G auction we study [1].

This paper aims to explore what could be the optimal response against SB opponents for a bidder taking part in a simplified CCA such as the French
5G auction. Indeed, the SB strategy is interesting as it is a simple yet efficient strategy [5] for the auction at hand.

## 1.2 Contribution

We introduce a POMDP formulation for clock auctions from the point of view of one player against a single straightforward agent. We justify this assumption by proving that several straightforward agents can be aggregated in this type of auction. Our main result (Theorem 1) provides a simplified expression of the optimal policy under some assumptions on the distribution of the opponents' preferences. It shows that the optimal solution of the POMDP coincides with a strategy with concise expression avoiding the recourse to the belief state. Lastly, we explore the results of the optimal strategy when the theorem holds and show empirical evidence of its performance.

The paper is organized as follows: Section 2 presents the studied auction, the SB strategy and how it is modelled in the rest of the paper. Section 3 provides an optimal strategy to bidding in the modelled auction and introduces the main theorem of simplification. Lastly, Section 4 applies those results to simulated auctions allowing one to compare the performance of this bidding strategy to the one of a perfectly informed bidder.

# 2 5G auction in France

## 2.1 Auction mechanism

We model an auction amongst $n$ players for $m$ items inspired by the clock auction held for the 5G auction in France in 2020 [1]. We denote each player by an integer $i \in \{1, \dots, n\}$. The auction begins at a certain price $P_{\text{init}} \ge 0$. A price increment $\Delta P > 0$ between successive rounds is fixed in advance. The auction mechanism is the following:

1. The auction starts at price $P_{\text{init}}$, we set $P \leftarrow P_{\text{init}}$

2. Each player $i$ asks for a number of items $d_i(P)$. This is her demand or bid. All demands are simultaneous.

3. We check if the total demand does not exceed the number of items, i.e. if $\sum_{i=1}^n d_i(P) \le m$:

- If it is the case, the auction terminates and each player $i$ receives $d_i(P)$ items and pays $d_i(P) \times P$.

- Otherwise, the price is raised, $P \leftarrow P + \Delta P$, and the auction moves to the next round (resuming from step 2).

Moreover, the auction presents an eligibility rule: it is mandatory for player $i$'s demand to be non-increasing, i.e. $\forall P \ge 0, d_i(P + \Delta P) \le d_i(P)$.

This auction presents both public information and private information:

- The demand of each player is revealed at the end of the round. At round $t$, the past demands are public information, i.e. $\{d_i(P_{\text{init}} + s\Delta P) | 0 \le s < t, i = 1, \dots, n\}$ is known by all players.

- Each player $i$ has a budget $B_i$. This is a private information. Every player is under a budget constraint: one's payment cannot exceed one's private budget.
We model the preferences of each player i by a private valuation function $v_i : \{0, \dots, m\} \to \mathbb{R}_+$. This valuation represents a maximal price that the player i is willing to pay for k items. It is also private information. Furthermore, we introduce the utility $u_i(k, P) = v_i(k) - kP$. Each agent i wants to maximize this utility within the constraints of the auction. The following result is immediate.

**Proposition 1.** The eligibility rule and the budget constraint ensure the auction terminates. The number of rounds R is bounded by:

$$R \le \Delta P^{-1} \left( \max_{1 \le i \le n} \left( \max_{1 \le k \le m} \frac{v_i(k)}{k} \right) - P_{init} \right).$$

Hence, during the auction, only a finite number of prices are observed, namely $\mathcal{P} = \{P_{init} + k\Delta P | k \in \{0, \dots, R\}\}$.

## 2.2 Straightforward bidding

In our study, we suppose all but one player play according to a strategy called Straightforward Bidding (SB) [13]. This strategy is a myopic strategy: it consists in maximizing one's utility at each round, as if the auction would terminate immediately. The player handles possible tie breaks by taking the lowest number of items that maximizes her utility. In our case in which there is a single type of items, SB can be formulated as follows.

**Definition 1.** The player i is said to be playing SB if

$$\forall P \ge 0, d_i(P) = \min \left( \arg \max_{0 \le k \le m} \{v_i(k) - kP\} \right)$$

One can notice that in Definition 1, $d_i$ only depends on the map $P \ge 0 \mapsto \max_{0 \le k \le m} \{v_i(k) - kP\}$. This is precisely the Legendre-Fenchel transform of $v_i$ (up to a change of sign), restricted to the non-negative real numbers. Hence, $d_i$ only depends on the non-decreasing concave hull of the private valuation $v_i$. This is formalized by the following result.

**Proposition 2.** Suppose player i plays according to SB. Let

$$\check{v}_i = \inf \{ f : \{0, \dots, m\} \to \mathbb{R} \mid f \text{ is non decreasing, concave and } f \ge v_i \}$$

and for all $P \ge 0$, define $\check{d}_i(P) = \min \left( \arg \max_{0 \le k \le m} \{\check{v}_i(k) - kP\} \right)$. Then,

1. for all $P \ge 0$, we have $d_i(P) = \check{d}_i(P)$.

2. Let $k_0 \in \{1, \dots, m-1\}$ such that there exists $P \in \mathcal{P}$ satisfying $d_i(P) = k_0$. Then, $v_i$ is locally strictly concave in $k_0$ (meaning $v_i(k_0) - v_i(k_0-1) > v_i(k_0+1) - v_i(k_0)$). Moreover, for such a $k_0$, $\check{v}_i(k_0) = v_i(k_0)$.

Hereafter, we will model the valuation of an SB agent as a concave and non-decreasing function.

**Corollary 1.** Suppose player i plays according to SB. If her valuation is normalized, i.e. $v_i(0) = 0$, we can model it by a valuation of the form $v_i(k) = \sum_{j=1}^{k} z_j$ where $z_1 \ge z_2 \ge \dots \ge z_m \ge 0$ and in this case, $d_i(P) = \sum_{j=1}^{m} 1(z_j - P > 0)$.
For the sake of simplicity, we will consider a modified two-players auction. This reduction is without loss of modelling power thanks to the following result.

**Proposition 3.** A clock auction between a player $J_1$ and $n-1$ SB players can be identified to a clock auction between $J_1$ and 1 super SB-player from the point of view of $J_1$, in the sense that, for every strategy $\sigma$ of $J_1$ in either auction, there exists a strategy $\sigma'$ in the other one such as her bid is the same at each round and her final utility is the same.

This result allows us to consider a super player e.g. an aggregated player of demand function $\delta(p) = \sum_{i=1}^{n-1} \delta_i(p)$ where $\delta_i$ is the demand function of the SB player $i$. It can be seen as a super SB-player by reordering the random variable $(Z_j^{(i)})_{1\le j \le m}$ of every player $i$.

## 2.3 Scope of the study

Our goal is to find a strategy for the non-SB player in the auction. In the rest, we call the Straightforward super player the opponent and the non-SB player the player. The latter's private valuation is noted $v$.

We model the opponent's valuation as a random variable $V(k) = \sum_{j=1}^k Z_j$ with $(Z_j)$ random non-negative variables of known distribution. The $(Z_j)$ must verify $Z_1 \ge \dots \ge Z_{(n-1)m}$ almost surely (a.s.). We note her demand function $\delta(p) = \sum_{j=1}^{(n-1)m} 1\{Z_j > p\}$ which is viewed as a random process. As mentioned before, the $(Z_j)_{1\le j \le (n-1)m}$ is a reordering of $n-1$ sequences $(Z_j^i)_{1\le j \le m}$ which verify $Z_1^i \ge \dots \ge Z_m^i$ almost surely (a.s.) for all $i \in \{1, \dots, n-1\}$.

In a perfect information setting i.e. when the opponent's valuation is public, the optimal policy comes naturally:

**Proposition 4.** Against an SB player, the optimal policy for player $i$ is given by the optimization problem :

$$ \max_{\substack{k \in \{0, \dots, m\} \\ p \in \mathcal{P}}} (v(k) - kp) \mathbf{1}(k + \delta(p) \le m), $$

$$ \text{where } \mathcal{P} = \{P_{\text{init}} + r\Delta P \mid 0 \le r \le \max_{k \in \{1, \dots, m\}} \frac{v(k) - P_{\text{init}}}{\Delta P}\}. $$

Since the player knows the opponent's bid at every price, she can decide the moment the auction ends by adapting her own bid. As a matter of fact, since $p \mapsto v(k) - kp$ is decreasing in $p$ for $k > 0$ and is null for $k = 0$, the maximum is necessarily attained at $p_k = \inf\{p \in \mathcal{P} : \delta(p) + k \le m\}$ for a certain $k$ and is non-negative. An optimal strategy for such an oracle player is to bid the $k$ that maximizes $v(k) - kp_k$. Since this result is immediate, the literature primarily examines scenarios where the opponent's valuation is either unknown or revealed through signaling during the auction [9,10].

The following section formally introduces the optimization problem regarding the player's strategy.
# 3 Bellman equation

## 3.1 POMDP

We model the situation as a Partially Observable Markov Decision Process (POMDP):

**Definition 2.** We denote by $\mathcal{S}$ the state space. The state $s_t = (t, p_t, k_t, \omega_t)$ at time $t$ is defined by:

- $t \ge 0$ is a discrete time, it can be interpreted as the round of the auction.

- $p_t \in \mathcal{P}$ is the price at round $t$. The price dynamics is given by $p_0 = P_{init}$ and $\forall t \ge 0, p_{t+1} = p_t + \Delta P$.

- $k_t \in \{0, \dots, m\}$ is the player's bid at round $t-1$.

- $\omega_t$ is the choice of nature for the opponent's valuation during the auction. We suppose that $\forall t \ge 0, \omega_{t+1} = \omega_t$ meaning that the opponent's valuation does not change during the auction.

We denote by $\mathcal{O}$ the set of observations. The observation at time $t$ is given by $o_t = (t, p_t, k_t, \delta_{t-1})$ $\forall t \ge 0$, where $\delta_t = \bar{\delta}(\omega_t, p_t)$ is the opponent's bid at round $t$ ($\bar{\delta}$ is a deterministic function). Let $\delta_{-1}$ be any initial conditional. Let $k_0 := \arg\max_{k \in \{0, \dots, m\}} (v(k) - kP_{init})$. From these observations, at round $t$, the player takes an action $u_t = \sigma_t(o_s, u_s)_{0 \le s \le t-1}, o_t \in \{0, \dots, m\}$ with $\sigma_t$ a measurable function and $u_t \le k_t$. The sequence $(\sigma_t)_{t \ge 0}$ is called an admissible strategy. The state following the action $u_t$ satisfies $k_{t+1} = u_t$.

The action $u$ causes the state to change from $s$ to $s'$ with probability $T(s'|s, u)$. As a matter of fact, in this model, all transitions are deterministic:

$$T((t', p', k', \omega') | (t, p, k, \omega), u) = \begin{cases} 1 & \text{if } \omega' = \omega, k' = u, t' = t+1, p' = p + \Delta P \\ 0 & \text{otherwise} \end{cases}$$

However, the initial state $s_0$ is supposed to be random because $\omega_0$, the unknown nature's choice, is viewed as a random variable.

We will note $O(o'|s', u)$ the probability with which the player observes $o'$ when reaching state $s'$ after taking action $u$.

**Optimization problem** The problem is to maximize the player's expected value. Our goal is thus to find an optimal admissible strategy i.e. optimize with regards to $\sigma$

$$ \begin{array}{l} \text{maximize} \quad \mathbb{E}[v(k_T) - k_T p_T] \\ \text{where } T = \inf\{t \ge 0 \mid \delta_t + k_t \le m\} \quad (\text{termination condition}) \end{array} \qquad (1) $$

We introduce the belief state $b_t$ which is the distribution of the current state conditionally to the history. Thus, $b_t = \mathbb{P}(s_t|o_t, (u_{t-1}, o_{t-1}), \dots, (u_0, o_0))$. Since the decision of the player and the termination condition depend on the last observation, a sufficient statistics of the POMDP includes not only the belief but also the last observation $o_t$.
**Proposition 5.** The optimal value of Problem 1 is given by the Bellman equation in which $o = (t, p, k, \delta)$ with $t \ge 0$ and $b$ denotes the belief:

$$ \psi(o, b) = \begin{cases} v(k) - k(p - \Delta P) & \text{if } k + \delta \le m \\ \max_{u \le k} \sum_{o' \in \mathcal{O}} \sum_{s, s' \in S} O(o'|s', u)T(s'|s, u)b(s)\psi(o', b') & \text{otherwise.} \end{cases} \quad (2) $$

Here, $b'(s') = \frac{O(o'|s', u) \sum_{s \in S} T(s'|s, u)b(s)}{\sum_{s'' \in S} O(o'|s'', u) \sum_{s \in S} T(s''|s, u)b(s)}$ is the updated belief at state $s'$.

This follows from a classical result of optimal control where the belief takes into account all the past rounds to determine a probability distribution over the future state [18,20]. However, it is hard to make out practical use of this form.

## 3.2 Simplification

Solving the Bellman equation requires to consider all histories to compute an optimal response. However, the only source of randomness is $\omega$. The only $\omega$-dependent component of the model is the observed bid $\delta(p_t) = \bar{\delta}(\omega_t, p_t) = \sum_{j=1}^{(n-1)m} 1\{Z_j(\omega_0) > p_t\}$. Hence, we can "transpose" the randomness of the environment to the opponent's bid by seeing $\delta(p_t)$ as a random process.

The following theorem embodies this simplification: under an assumption on the demand function and knowing the initial belief $b_0$, only the demand observed at the last round matters to take an optimal decision.

**Theorem 1.** Let $\forall t \ge 0$,

$$ \varphi(t, k, \delta) = \begin{cases} v(k) - k p_{t-1} & \text{if } k + \delta \le m \\ \max_{u \le k} \sum_{\delta' \le \delta} \mathbb{P}(\delta(p_t) = \delta' | \delta(p_{t-1}) = \delta) \varphi(t+1, u, \delta') & \text{otherwise.} \end{cases} \quad (3) $$

Suppose that $(\delta(p_t))_{t \ge 0}$ is a Markov chain. Let $b_0$ be the distribution of $s_0 = (0, P_{init}, k_0, \omega_0)$ where $\omega_0$ is the nature's choice (for the random sequence $(Z_j)_{0 \le j \le m}$ or the process $(\delta(p_t))_{t \ge 0}$). Then the optimal value given by Equation (2) and $\varphi$ coincide at the initial time: $E_{\delta_1}[\psi(o_0 = (0, P_{init}, k_0, \delta_{-1}), b_0)] = E_{\delta_1}[\varphi(0, k_0, \delta_1)]$.

In other words, we can find an optimal solution avoiding the recourse to dynamic programming in a belief space if the opponent's demand is a Markov chain as it is a sufficient statistics for the optimal value. This leads to a practical algorithm to decide bids at each round. The first decision considers the distribution of $\delta(P_{init})$ and must maximize the discounted utility. Then, if the auction is not finished, it suffices to take the arg max at each round $t$ in Equation (3).

## 4 Optimal bound

Theorem 1 provides a simple algorithm to play an auction optimally. In this section, we quantify the value of this optimum. To this end, we took inspiration from prophet inequalities and their definition of approximation [7]. We investigate how much the algorithm's expected utility differs from the utility of a player with perfect information. We also introduce a stronger notion of approximation which gives a more practical meaning to optimality.
## 4.1 Exponential case

The exponential distribution is associated with life expectancy. In the context of an auction, the demand is similar to the process of aging, as the auctioneer "dies" when her bid reaches 0. Thus, it makes sense to model the time passing between two changes in demand as exponential laws. For an opponent i:

- Let $\lambda > 0$ and $Z_{m+1}^{\text{opp},i} = 0$

- $\forall j \in \{1, \dots, m\}, Z_j^{\text{opp},i} - Z_{j+1}^{\text{opp},i} \sim \mathcal{E}(\lambda)$

- $(Z_j^{\text{opp},i} - Z_{j+1}^{\text{opp},i})$ are iid.

Moreover, we suppose that for all $i \neq i'$, $(Z_j^{\text{opp},i} - Z_{j+1}^{\text{opp},i})$ and $(Z_j^{\text{opp},i'} - Z_{j+1}^{\text{opp},i'})$ are independent for any $j$. We thus define $n-1$ opponent $i \in \{1, \dots, n-1\}$ with a demand function $\delta_i$ with independent increments. Hence, the sum remains a Markov chain. This model allows us to apply the result of Theorem 1 and use the underlying strategy. In this particular case, $\mathbb{P}(\delta_i(p_{t+1}) = \delta_{t+1} | \delta_i(p_t) = \delta_t)$ can be explicitly computed and $\mathbb{P}(\delta(p_{t+1}) = \delta_{t+1} | \delta(p_t) = \delta_t)$ follows.

## 4.2 Empirical evidence of optimality

We simulate auctions and observe the performance of an agent playing according to the strategy we have exhibited. Those performances can be compared to an oracle (see the optimization problem 4) to give a sense of how close the algorithm is to take the optimal decision.

**Simulation setting** We suppose the opponent and the player have the same exponential parameter $\lambda$. Moreover, the player's valuation is fixed at $v(k) = \lambda[k(m+1) - \frac{k(k+1)}{2}]$ whereas the opponents' is randomly drawn. Let's motivate the player's valuation. In an auction, every player would have a similar valuation in a fair auction (otherwise players with widely lower valuation would not be able to compete). We thus set this valuation to be the expectancy of a random SB-opponent's.

Among the simulations, $\Delta P$ the price increment, $P_{\text{init}}$ the initial price and $m$ the number of items are fixed. Each simulation is carried out as follows:

- We draw independently $n-1$ samples of length $m: z_1^{\text{opp},i}, \dots, z_m^{\text{opp},i}$ from random variables $(Z_j^{\text{opp},i})$ to form the demand of one opponent $i$. Then, we define $z_1, \dots, z_{(n-1)m}$ as a reordering of $(z_1^{\text{opp},1}, \dots, z_m^{\text{opp},1}, \dots, z_1^{\text{opp},n-1}, \dots, z_m^{\text{opp},n-1})$.

It yields the opponent's demand $\delta(p) = \sum_{j=1}^{(n-1)m} 1\{z_j > p\}$.

- We then play the same auction (i.e. against the same opponent) using two different strategies:

1. For the first strategy, we suppose the player has access to the opponent's valuation. The player plays with perfect information and obtains an optimal final score $V_i$, her utility at the end of the auction.

2. The second strategy is the policy derived from Equation (3). This results in a final score $\psi_i$.

**Approximations** Usually (see [9,10]), an approximation is defined as follows.

**Definition 3.** For every strategy $\sigma$ with imperfect information, let $V(\sigma)$ be the random variable giving the score such a strategy yields. We denote by $V$ the
score of the optimal strategy in a perfect information setting. $\sigma$ is said to be an $\alpha$-approximation if and only if $\mathbb{E}[V(\sigma)] \geq \alpha \mathbb{E}[V]$.

We extend this notion with the following definition.

**Definition 4.** With the foregoing notation, $\sigma$ is said to be an $\alpha$-strong approximation with probability $p$ if and only if $\mathbb{P}(V(\sigma) \geq \alpha V) \geq p$.

Spectrum auctions are neither repeated nor scalable. Thus, it is more meaningful for an agent to know that there is high chance to approximate the optimal value rather than knowing that this value would be attained in expectancy.

**Empirical results** In order to choose the most realistic parameters, we consider the same parameters as in the French 5G auction: $m = 11$, $P_{init} = 70$ and $\Delta P = 3$ (see [1]). We have conducted $N = 10,000$ auctions for $\lambda \in \{10, 11, 12, 13, 14, 15\}$ in order to mimic different bidding profiles compatible with the 5G auction. From those simulations, we can conjecture that approximation and strong approximation results can be derived on the Bellman strategy.

<table><caption>**Table 1.** Frequency of points $(V_i, \psi_i)$ such as $\psi_i \geq 80\%V_i$</caption><thead><tr><th>λ</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr></thead><tbody><tr><th>Freq</th><td>90%</td><td>89%</td><td>91%</td><td>92%</td><td>90%</td><td>91%</td></tr></tbody></table>

<table><caption>**Table 3.** Estimation of $\mathbb{P}(V = \psi)$</caption><thead><tr><th>λ</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr></thead><tbody><tr><th>P(V = ψ)</th><td>49%</td><td>54%</td><td>57%</td><td>61%</td><td>58%</td><td>58%</td></tr></tbody></table>

<table><caption>**Table 2.** Empirical expectations</caption><thead><tr><th>λ</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr></thead><tbody><tr><th>E[V]</th><td>50</td><td>59</td><td>66</td><td>72</td><td>78</td><td>83</td></tr><tr><th>E[ψ]</th><td>46</td><td>55</td><td>62</td><td>68</td><td>73</td><td>78</td></tr><tr><th>E[V]/E[ψ]</th><td>91%</td><td>94%</td><td>94%</td><td>95%</td><td>94%</td><td>94%</td></tr></tbody></table>

From those figures, we can conjecture that an approximation result can be empirically observed and the value of $\alpha$ seems to be independent on $\lambda$. Such empirical evidence suggests the existence of a constant approximation factor. Plus, from a practical point of view, data show that the outcome of our strategy rarely differs from the optimal outcome since, in at most $\approx 10\%$ of auctions, the obtained utility is lower than 80% of the best-possible utility. Furthermore, in at least half of the sample, the strategy achieved the best possible utility.

# 5 Conclusion

We have modelled a real-life auction against a straightforward but realistic strategy as a POMDP, obtained the optimal strategy, and compared the performances of this strategy and of a perfectly informed one. Future work would focus on having theoretical guarantees for this strategy in the same setting. Moreover, one could study the scaling of this result in higher dimension auctions such as the SAA (Simultaneous Ascending Auction) where players are allowed to bid on multiple items rather than a number of items, raising their prices individually.
References

1. Autorité de Régulation des Communications Electroniques, des postes et de la distribution de la presse: Grand dossier - 5G Attribution des fréquences en métropole, https://www.arcep.fr/la-regulation/grands-dossiers-reseaux-mobiles/la-5g/attribution-des-frequences-en-métropole.html, accessed: 2024-05-24

2. Berge, F., Bechler, A., Chardy, M.: A mixed integer programming approach for 5g spectrum auction strategy optimization. In: ICC 2023 - IEEE International Conference on Communications. pp. 4846–4852 (2023)

3. Bikhchandani, S., Mamer, J.W.: Competitive equilibrium in an exchange economy with indivisibilities. Journal of Economic Theory **74**(2), 385–413 (1997)

4. Boutilier, C.: A POMDP formulation of preference elicitation problems. In: Eigh-teenth National Conference on Artificial Intelligence. p. 239–246. American Asso-ciation for Artificial Intelligence, USA (2002)

5. Bulow, J., Levin, J., Milgrom, P.: Winning play in spectrum auctions. Working Paper 14765, National Bureau of Economic Research (March 2009)

6. Cai, Y., Feng, Z., Liaw, C., Mehta, A., Velegkas, G.: User response in ad auctions: An MDP formulation of long-term revenue optimization (2024)

7. Correa, J., Cristi, A.: A constant factor prophet inequality for online combinatorial auctions. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing. pp. 686–697. ACM (2023)

8. Cramton, P., McMillan, J., Milgrom, P., Miller, B., Mitchell, B., Vincent, D., Wilson, R.: Simultaneous ascending auctions with package bidding (04 1998)

9. Dütting, P., Kesselheim, T., Lucier, B.: An $o(\log \log m)$ prophet inequality for subadditive combinatorial auctions (2020)

10. Eden, A., Feldman, M., Goldner, K., Mauras, S., Mohan, D.: Constant approximation for private interdependent valuations. In: 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). pp. 148–163. IEEE (2023)

11. Jain, R., Chiu, D., Hawe, W.: A quantitative measure of fairness and discrimination for resource allocation in shared computer systems (1998)

12. Levin, J., Skrzypacz, A.: Properties of the combinatorial clock auction. American Economic Review **106**(9), 2528–2551 (2016)

13. Milgrom, P.: Putting Auction Theory to Work. No. 9780521551847 in Cambridge Books, Cambridge University Press (2000)

14. Milgrom, P., Strulovici, B.: Substitute goods, auctions, and equilibrium. Journal of Economic Theory **144**(1), 212–247 (2009)

15. Milgrom, P.R.: Auction Theory. Cowles Foundation Discussion Papers 779, Cowles Foundation for Research in Economics, Yale University (Nov 1985)

16. Myerson, R.B.: Optimal auction design. Mathematics of Operations Research **6**(1), 58–73 (1981)

17. Reeves, D.M., Wellman, M.P., MacKie-Mason, J.K., Osepayshvili, A.: Exploring bidding strategies for market-based scheduling. Decision Support Systems **39**(1), 67–85 (2005)

18. Ross, S., Pineau, J., Paquet, S., Chaib-draa, B.: Online planning algorithms for POMDPs. Journal of Artificial Intelligence Research **32**, 663–704 (2008)

19. Wellman, M., Osepayshvili, A., MacKie-Mason, J., Reeves, D.: Bidding strategies for simultaneous ascending auctions. Topics in Theoretical Economics **8**, 1461–1461 (02 2008)

20. Åström, Karl Johan: Optimal Control of Markov Processes with Incomplete State Information I. Journal of Mathematical Analysis and Applications **10**, 174–205 (1965)