# Bidder Selection Problem in Position Auctions: A Fast and Simple Algorithm
via Poisson Approximation

Nikolai Gravin<EMAIL_ADDRESS>0000-0002-3845-947X Shanghai
University of Finance and EconomicsShanghaiChina ,  Yixuan Even Xu
<EMAIL_ADDRESS>0009-0003-9360-753X Tsinghua
UniversityBeijingChina and  Renfei Zhou<EMAIL_ADDRESS>0000-0002-0095-0626 Tsinghua UniversityBeijingChina

(2024)

###### Abstract.

In the Bidder Selection Problem (BSP) there is a large pool of $n$ potential
advertisers competing for ad slots on the user’s web page. Due to strict
computational restrictions, the advertising platform can run a proper auction
only for a fraction $k<n$ of advertisers. We consider the basic optimization
problem underlying BSP: given $n$ independent prior distributions, how to
efficiently find a subset of $k$ with the objective of either maximizing
expected social welfare or revenue of the platform. We study BSP in the
classic multi-winner model of position auctions for welfare and revenue
objectives using the optimal (respectively, VCG mechanism, or Myerson’s
auction) format for the selected set of bidders. This is a natural
generalization of the fundamental problem of selecting $k$ out of $n$ random
variables in a way that the expected highest value is maximized. Previous PTAS
results ([Chen, Hu, Li, Li, Liu, Lu, NIPS 2016], [Mehta, Nadav, Psomas,
Rubinstein, NIPS 2020], [Segev and Singla, EC 2021]) for BSP optimization were
only known for single-item auctions and in case of [Segev and Singla 2021] for
$l$-unit auctions. More importantly, all of these PTASes were computational
complexity results with impractically large running times, which defeats the
purpose of using these algorithms under severe computational constraints.

We propose a novel Poisson relaxation of BSP for position auctions that
immediately implies that 1) BSP is polynomial-time solvable up to a
vanishingly small error as the problem size $k$ grows; 2) there is a PTAS for
position auctions after combining our relaxation with the trivial brute force
algorithm. Unlike all previous PTASes, we implemented our algorithm and did
extensive numerical experiments on practically relevant input sizes. First,
our experiments corroborate the previous experimental findings of Mehta et al.
that a few simple heuristics used in practice (e.g., Greedy for general
submodular maximization) perform surprisingly well in terms of approximation
factor. Furthermore, our algorithm outperforms Greedy both in running time and
approximation on medium and large-sized instances, i.e., its running time
scales better with the instance size.

Bidder Selection, Submodular Maximization, Position Auctions

††journalyear: 2024††copyright: acmlicensed††conference: Proceedings of the
ACM Web Conference 2024; May 13–17, 2024; Singapore, Singapore††booktitle:
Proceedings of the ACM Web Conference 2024 (WWW ’24), May 13–17, 2024,
Singapore, Singapore††doi: 10.1145/3589334.3645418††isbn:
979-8-4007-0171-9/24/05††ccs: Theory of computation Approximation algorithms
analysis††ccs: Applied computing Online auctions††ccs: Theory of computation
Algorithmic game theory and mechanism design

##  1\. Introduction

Online advertising is a big part of the modern e-commerce industry and a key
to the monetization of many online businesses. The majority of ad slots on a
user web page are sold in _real time_ via an automated auction to a group of
candidate advertisers. The whole process from the time when an auction is
initiated based on the impression about advertising opportunity up to the time
when ads are displayed on the user’s page usually has to be completed in a few
milliseconds. This makes it imperative for the platform (Ad exchange ADX, or
Demand side DSP) to keep the auction processing and communication time under a
strict limit. Meanwhile, a platform usually runs a complex ML model on each
advertiser to get an accurate estimate of their auction score111An auction
score is comprised of estimates for click-through-rate (CTR), ad relevance,
and value-per-click bid.. As some platforms already have or anticipate to have
in the near future an excessive number of prospective advertisers, the
comprehensive ML model can only be run on a fraction $k$ of $n$ advertisers
due to strict time222In some case, the platform may also estimate the bids to
avoid communication lag. limit. In practice, the platform handles this by a
two-stage selection process: it filters out all but $k$ advertisers by running
a much faster and less accurate ML model, and then it runs a proper auction
for the remaining $k$ advertisers using the comprehensive and slow ML model.
E.g., for the ADX platforms $n$ may be in the range $20-50$ and $k$ depends on
the specific company, e.g., $k=10$ or $k=20$; in the case of DSPs, $n$ may
vary a lot and can reach thousands, while $k$ cannot be too large, e.g.,
$k=100$ or $k=200$.

This raises multiple practical challenges for the ADX and/or DSP platforms. A
platform first needs to get $n$ rough score estimates, which can be viewed as
$n$ distributions of the bidders’ accurate auction scores. One problem is how
to obtain these estimates online in a constantly changing environment. Another
learning problem, recently considered by Goel et al. (Goel et al., 2023) is
how to retrieve this information from strategic agents, who might affect the
selection stage by adjusting their bids. Third, there is an underlying
optimization question: for $n$ prospective bidders with known independent
prior distributions $({D_{i}})_{i\in[n]}$ how to select $k<n$ of them with the
objective of either maximizing expected score (social welfare) or platform’s
revenue. We focus on this basic optimization problem termed the Bidder
Selection Problem (BSP).

The welfare maximization BSP for the VCG single-item (or more generally
$\ell$-unit) auction is equivalent to the following fundamental algorithmic
question: select $k$ out of $n$ independent random variables, with the
objective of maximizing the expected maximum (expected sum of top $\ell$
values). This question (for single-item) has received significant attention
under different names: model-driven optimization (Goel et al., 2010),
$k\textup{-MAX}$ (Chen et al., 2016), team selection with test scores
(Kleinberg and Raghu, 2018), subset selection for expected maximum (Mehta et
al., 2020), non-adaptive ProbeMax (Segev and Singla, 2021), which extends to
the top-$\ell$-out-of-$k$ problem.

It is also natural to consider the selection problem with a more general set
of objectives given by linear combinations of the top-$\ell$ objectives. The
latter problem generalizes $\ell$-unit auctions and corresponds to the widely
used position auction (Varian, 2007; Edelman et al., 2007) environment as
described, e.g., in (Hartline, [n. d.]). In position auction, there are $m$
sorted positions that appear alongside the search results and $n$ advertisers
competing for these $m$ slots. Each slot $j\in[m]$ has a different click-
through rate $w_{{j}}$ (additional multiplicative factor for the click
probability on $j$-th position), which translates into the value ${v_{i}}\cdot
w_{{j}}$ for advertiser $i$ if $i$’s ad is displayed at $j$-th position.

#### Prior Results for the BSP

The basic BSP of welfare maximization (second-price auction) was shown to be
NP-hard by Goel et al. (Goel et al., 2010) and later by Mehta et al. (Mehta et
al., 2020). On the positive side, there are a few known Polynomial Time
Approximation Schemes (PTAS). First, Chen et al. (Chen et al., 2016) gave a
dynamic programming-based polynomial time approximation scheme (PTAS). Later,
Mehta et al. (Mehta et al., 2020) and Segev and Singla (Segev and Singla,
2021) respectively proposed an Efficient PTAS (EPTAS) for the BSP. Both of
their approaches are based on discretizing and enumerating all possible
distributions for the maximum of a few random variables: (Mehta et al., 2020)
characterize all $n$ distributions into one of $C(\varepsilon)$ bins (where
$C(\varepsilon)=O(1/\varepsilon)^{O(1/\varepsilon)}$ depends on the
approximation guarantee $1-\varepsilon$) and then run a brute force search
with the complexity of $O\left(n\cdot\log(k)^{O(C(\varepsilon))}\right)$;
(Segev and Singla, 2021) use a complex reduction to a multi-dimensional
extension of _Santa Claus_ problem of (Bansal and Sviridenko, 2006) with at
least $O(1/\varepsilon)^{O(1/\varepsilon)^{O(1/\varepsilon^{2})}}$ running
time333We give a lower bound on the running time, as it is hard to say what is
the exact time complexity of their approach, as they did not specify it
explicitly and their result proceeds by a sequence of reductions with non-
trivial running time dependencies.. We would like to emphasize that the
findings of Mehta et al. and Segev and Singla could only be considered as
purely computational complexity results rather than real algorithms to be used
in practice or even in testing/numerical experiments. Indeed, their approaches
are rather involved and not very easy to implement, e.g., Segev and Singla
only state an existential result without explicitly describing their
algorithm. Furthermore, the running times of these EPTASes even for the basic
$k$-MAX problem and small values of $n$ and $k$ are enormously large444Note
that $k$-MAX is a special case of general submodular optimization which
already admits efficient $1-1/e$ approximation. Hence, $\varepsilon<1/e$ and
the time complexity of
$2^{\Theta(1/\varepsilon)^{\Theta(1/\varepsilon)}}>2^{9000}$ with conservative
estimates of $\Theta(1/\varepsilon)=2/\varepsilon$.. I.e., using any of the
existing PTASes would completely defeat the purpose of a two-stage selection
process.

For the revenue objective, Mehta et al. (Mehta et al., 2020) also considered
BSP for the second-price auction, which is equivalent to maximizing the
expectation of the second largest value among selected $k$ random variables.
They showed strong impossibility results: it is impossible to get any constant
factor approximation in polynomial time under either of the exponential time,
or the planted clique hypothesises.

#### Auction Formats

One of the most commonly used formats in advertising industry is the
Generalized Second Price (GSP) auction. It was shown in (Varian, 2007; Edelman
et al., 2007) that GSP of any position auction with any set of bidders has a
Nash equilibrium equivalent to the welfare-maximizing outcome of the VCG. In
some cases (e.g., Google’s auction for selling contextual ads (Varian and
Harris, 2014)) the platform’s auction format is based directly on the VCG.
Thus, in the BSP context with the welfare-maximization objective, it is most
natural to analyze the VCG mechanism. For the revenue objective, it is natural
to study the optimal Myerson’s auction, as it gives an upper bound on the
revenue of any other auction format. Then one can reduce revenue maximization
to welfare maximization of the VCG format. I.e., it is w.l.o.g. to only study
welfare-maximization BSP for the VCG format, which we do in the rest of our
paper. It is also natural to study revenue maximization BSP for the GSP format
(or by the revenue equivalence of the VCG format). Unfortunately, it does not
admit polynomial time $O(1)$-approximation even for the basic single-item
auction due to strong impossibility results of (Mehta et al., 2020).

###  1.1. Our Results

We propose a novel relaxation of the BSP for a more general position auction
environment, which we call Poisson (or Poisson-Chernoff) relaxation. It has
the following theoretical guarantees.

  1. (1)

The relaxation is a continuous maximization problem with a concave objective
that can be solved in time polynomial in $n$ and $k$. In fact, the objective
of this relaxation is a nicely structured algebraic function that lends itself
to efficient convex minimization solvers.

  2. (2)

With small adjustments (summarized in Section 4.1), the relaxed objective
_converges_ at the rate $1-O(k^{-1/4})$ to the actual social welfare of
fractional BSP as the problem size $k$ grows (Theorem 4.4). The standard
rounding of this fractional solution suffers only a small loss of
$O(k^{-1/2})$, yielding $\bigl{(}1-O(k^{-1/4})\bigr{)}$-approximation (Theorem
4.5) for the integral BSP.

  3. (3)

For the special case of the single-item auction, our algorithm achieves
$1-O\bigl{(}\sqrt{\ln k/k}\bigr{)}$ approximation (see Appendix C).

These results have immediate theoretical implications and can be implemented
in practice unlike all previous PTAS algorithms, as our approach has far
superior running time to the point where it outperforms some of the existing
heuristics used in practice, such as the Greedy algorithm for general
submodular maximization. Furthermore, our results bring new theoretical
insight for BSP: the BSP converges to a polynomial-time solvable optimization
problem as the problem size $k$ grows.

#### Theoretical Implications.

Our Section 4.1 gives a $\left(1-\varepsilon\right)$ approximation to the BSP
for any position auction with $\varepsilon=\Omega(k^{-1/4})$ and works in
polynomial time (independent of $\varepsilon$). On the other hand, for small
values of $\varepsilon$ ($\varepsilon=O(k^{-1/4})$), a straightforward
exhaustive search algorithm gives a perfect solution in
$O(n^{k})=n^{\mathrm{poly}(1/\varepsilon)}$ time. I.e., the combination of our
relaxation with the brute force algorithm yields a PTAS:

###### Corollary 1.1.

BSP for any position auction admits a $(1-\varepsilon)$ PTAS that runs in
$n^{\mathrm{poly}(1/\varepsilon)}$ time.

Moreover, the algorithm as in Corollary 1.1 is an EPTAS with a much better
dependency on $\varepsilon$ than previous PTASes under a mild assumption that
$k\geq\log n$:

###### Corollary 1.2.

BSP for position auctions admits a $(1-\varepsilon)$ EPTAS for any $k\geq\log
n$ that runs in $O(\mathrm{poly}(n,k))+2^{O(\varepsilon^{-8})}$ time.

###### Proof.

Section 4.1 runs in $O(\mathrm{poly}(n,k))$. We run brute force only when
$\varepsilon=O(k^{-1/4})$, i.e., when $k^{2}=O(\varepsilon^{-8})$. Then its
running time is not more than $n^{k}\leq 2^{k^{2}}=2^{O(\varepsilon^{-8})}$,
since $k\geq\log n$. ∎

#### Comparison with Previous Theoretical Results.

Our novel Poisson approximation approach yields more general theoretical
results than previous work. E.g., as Segev and Singla (Segev and Singla, 2021)
briefly mention how their scheme can be extended from $k$-MAX (i.e., single-
item auction) to $\ell$-unit auctions, one may wonder if a similar approach
also extends to the more general position auction environment. To the best of
our knowledge, it does not. Indeed, their main idea is to consider two regimes
for $\ell$: small (a constant) $\ell<1/\varepsilon^{3}$, and large
$\ell>1/\varepsilon^{3}$. They claim that the former case can be handled with
a similar approach (maybe with a significantly worse dependency of the running
time on $\varepsilon$ than the case $\ell=1$), and in the later case, one can
use concentration bounds similar to the (3) case described in Section 3.1.
This argument cannot be used for the objective that is a linear combination of
welfare in $1$-unit and $k/2$-unit auctions.

#### Relevance in Practice.

Our relaxation is a white-box approach that can be easily adapted to different
scenarios. E.g., if some bidders have to be included in the final solution
(which is often the case in industry because of contract obligations), then
our approach gives the same approximation with these additional
constraints555In fact, the approximation guarantee holds not only for the
global objective, but also for the surplus objective, i.e., the additional
gain to welfare from the non-fixed bidders.. Also, depending on the type of
problem instances, a few steps of our algorithm can be removed or simplified
to fit the specific domain, which results in simpler and more efficient
solutions.

Furthermore, unlike the case with all previous PTASes, we actually implemented
our algorithm and did numerical experiments on several generated data sets of
practically relevant sizes. Note that a company cares much more about the
implementability and running time of their algorithms rather than its
theoretical approximation guarantees666In the context of BSP any reasonable
heuristic is preferable to a complex and slow algorithm with good
approximation efficiency guarantees., which has been the main focus of
previous PTAS results. In contrast, our algorithm is not very complex and is
based on standard continuous convex maximization methods, which means that it
is much easier to understand and adopt by a platform’s product team. The
experiments are summarized in Section 5. We slightly simplified our
theoretical Section 4.1 to avoid the hard-coded efficiency loss of
$O(k^{-1/4})$ in the approximation.

We observed that among all tested algorithms, our algorithm produced solutions
that were always within 0.1% of the best-performing algorithm in terms of
objective value. Furthermore, our algorithm’s running time scales
significantly slower than any other tested algorithm. For large instances
where $n=1000,k=200$, our algorithm took less than 1 minute to complete, while
even Greedy (which is a subroutine in all previous PTASes) took more than 1
day and Local Search could not finish within 1 week. These findings
demonstrate the practical relevance of our approach.

###  1.2. Other Related Work

Mehta et al. (Mehta et al., 2020) mention a few other scenarios besides bidder
selection with similar mathematical formulations. The applications range from
a two-tier solution for scoring documents in a search result (Broder et al.,
2003), to filtering initial proposals in procurement auctions (Rong and Lu,
2007; Tan, 1992), to voting theory (Procaccia et al., 2012). Bei at al. (Bei
et al., 2023) studied BSP with the revenue objective under multiple auction
formats including Myerson’s auction and gave constant factor approximation for
the second-price auction with anonymous reserve. They also introduced another
optimization framework for the BSP under costs, which is more challenging than
the BSP under capacity constraint.

Poisson approximation is a well-developed technique from probability theory
and statistics. A survey (Novak, 2019) mentions at least twenty different
results on the basic question of approximating the sum of independent
Bernoulli random variables by the Poisson distribution. In statistics, Poisson
approximation is commonly used in Extreme Value Theory (EVT) with applications
to structural and geological engineering, traffic prediction, and finance
(see, e.g., a book (Novak, 2011)). It has also been used in theoretical
computer science, e.g., (Li and Yuan, 2013) used Le Cam’s Poisson
approximation theorem for stochastic bin packing and knapsack problems and
also for EUM introduced in (Li and Deshpande, 2019).

In fact, the expected utility maximization (EUM) is closely related to our
objective. EUM is formulated as choosing a feasible subset $S$ out of $n$
random variables $X_{1},\ldots,X_{n}$ to maximize
$\operatorname{\mathbf{E}}\mathchoice{\left[u(\sum_{i\in
S}X_{i})\right]}{[u(\sum_{i\in S}X_{i})]}{[u(\sum_{i\in
S}X_{i})]}{[u(\sum_{i\in S}X_{i})]}$, where $u$ is a given utility function.
The problem has been studied under capacity (Bhalgat and Khanna, 2014) or
other combinatorial constraints (Li and Deshpande, 2019; Li and Yuan, 2013; Yu
and Ahmed, 2016) with a non-linear (typically concave) utility function. The
BSP for single-item auction, i.e., the $k$-MAX problem, has a similar
objective $\operatorname{\mathbf{E}}\mathchoice{\left[\max_{i\in
S}\\{X_{i}\\}\right]}{[\max_{i\in S}\\{X_{i}\\}]}{[\max_{i\in
S}\\{X_{i}\\}]}{[\max_{i\in S}\\{X_{i}\\}]}$ to EUM but with $\max$ operator
instead of the sum. When the distributions of $X_{i}$ are unknown, EUM becomes
an online learning problem. Chen et al. (Chen et al., 2016) gave the first
PTAS for $k$-MAX, but their main focus is on Combinatorial Multi-Armed
Bandits.

##  2\. Preliminaries

A set of $n$ bidders wish to receive some service and each bidder $i\in[n]$
has a private non-negative value ${v_{i}}\in\mathbb{R}_{\geq 0}$ indicating
how much they are willing to pay for it. We denote the vector of bidder values
as $\mathbf{v}=({v_{i}})_{i\in[n]}$. By the revelation principle, we can
restrict our attention to incentive compatible and individually rational
single-round auctions $\mathcal{A}$, where each bidder $i$ submits a sealed
bid ${b_{i}}$ to the auctioneer. The auctioneer then decides on a feasible
allocation vector $\mathbf{a}(\mathbf{b})=({a_{i}}(\mathbf{b}))_{i\in[n]}$ and
payments $\mathbf{p}(\mathbf{b})=({p_{i}}(\mathbf{b}))_{i\in[n]}$. The
incentive compatibility and individual rationality mean that by bidding
truthfully ${b_{i}}={v_{i}}$, each bidder $i\in[n]$ (a) maximizes her utility
$u_{i}({b_{i}},\mathbf{b}_{\text{-}i})\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}{v_{i}}\cdot{a_{i}}({b_{i}},\mathbf{b}_{\text{-}i})-{p_{i}}({b_{i}},\mathbf{b}_{\text{-}i})$
and (b) receives non-negative utility
$u_{i}({v_{i}},\mathbf{b}_{\text{-}i})\geq 0$. The seminal VCG mechanism (a
second-price auction in the case of single-item auction) is an example of
incentive compatible mechanism that also maximizes _social welfare_
$\textup{{SW}}(\mathbf{a},\mathbf{v})=\sum_{i=1}^{n}{a_{i}}\cdot{v_{i}}$.

We study auctions in the Bayesian setting, where we assume that bidder values
are drawn independently from known prior distributions
$\mathbf{v}\sim\mathbf{D}=\prod_{i\in[n]}{D_{i}}$. We also use
${D_{i}}(\tau)=\operatorname{\mathbf{Pr}}_{{v_{i}}\sim{D_{i}}}\mathchoice{\left[{v_{i}}\leq\tau\right]}{[{v_{i}}\leq\tau]}{[{v_{i}}\leq\tau]}{[{v_{i}}\leq\tau]}$
to denote the cumulative distribution function. The auction designer is
usually concerned about two objectives: the expected _social welfare_
$\textup{{SW}}=\operatorname{\mathbf{E}}_{\mathbf{v}\sim\mathbf{\mathbf{D}}}\mathchoice{\left[\textup{{SW}}(\mathbf{a}(\mathbf{v}),\mathbf{v})\right]}{[\textup{{SW}}(\mathbf{a}(\mathbf{v}),\mathbf{v})]}{[\textup{{SW}}(\mathbf{a}(\mathbf{v}),\mathbf{v})]}{[\textup{{SW}}(\mathbf{a}(\mathbf{v}),\mathbf{v})]}$,
and _revenue_
$\textup{{Rev}}=\operatorname{\mathbf{E}}_{\mathbf{v}\sim\mathbf{\mathbf{D}}}$
$[\sum_{i\in[n]}{p_{i}}(\mathbf{v})]$. The VCG mechanism maximizes the welfare
on every valuation profile $\mathbf{v}$, and thus maximizes SW in expectation
for any prior $\mathbf{\mathbf{D}}$. The well-known Myerson’s auction
maximizes Rev. This auction reduces the problem of revenue maximization to
_virtual welfare_ maximization by transforming values $({v_{i}})_{i\in[n]}$ to
virtual values $\varphi_{i}({v_{i}})$ for regular distribution ${D_{i}}$ and
by doing ironing $\overline{\varphi}_{i}({v_{i}})$ for irregular distribution
${D_{i}}$. I.e., the expected revenue of Myerson’s auction can be written as
$\textup{{Rev}}=\operatorname{\mathbf{E}}_{\mathbf{v}}\mathchoice{\left[\textup{{SW}}(\mathbf{a}(\mathbf{v}),\varphi(\mathbf{v}))\right]}{[\textup{{SW}}(\mathbf{a}(\mathbf{v}),\varphi(\mathbf{v}))]}{[\textup{{SW}}(\mathbf{a}(\mathbf{v}),\varphi(\mathbf{v}))]}{[\textup{{SW}}(\mathbf{a}(\mathbf{v}),\varphi(\mathbf{v}))]}$
for regular distributions and
$\textup{{Rev}}=\operatorname{\mathbf{E}}_{\mathbf{v}}\mathchoice{\left[\textup{{SW}}(\mathbf{a}(\mathbf{v}),\overline{\varphi}(\mathbf{v}))\right]}{[\textup{{SW}}(\mathbf{a}(\mathbf{v}),\overline{\varphi}(\mathbf{v}))]}{[\textup{{SW}}(\mathbf{a}(\mathbf{v}),\overline{\varphi}(\mathbf{v}))]}{[\textup{{SW}}(\mathbf{a}(\mathbf{v}),\overline{\varphi}(\mathbf{v}))]}$
for general distributions.

#### Auction Environments.

The single-item auction is an environment with the feasible allocations given
by $\\{\mathbf{a}:\sum_{i\in[n]}{a_{i}}\leq 1\\}$. A more general $\ell$-unit
auction environment for $\ell\in{\mathbb{N}}$ is given by the feasibility
constraints: $\sum_{i\in[n]}{a_{i}}\leq\ell$ and ${a_{i}}\in[0,1]$ for all
$i\in[n]$. A position auction environment further generalizes $\ell$-unit
auctions. It is specified by a sorted weight vector $\mathbf{w}=(1\geq
w_{{1}}\geq w_{{2}}\geq\ldots\geq w_{{n}}\geq 0)$, which represents the click-
through rate probabilities for $n$ advert positions777The number of available
positions $m$ is usually smaller than the number of bidders $n$, in which case
we simply let $w_{m+1}=\cdots=w_{n}=0$.. Every bidder may get at most one
position and each advert position can be assigned to at most one advertiser.
Formally, the feasibility allocations can be specified with an assignment
function $\pi:[n]\to[n]$ of $n$ advertisers to $n$ sorted slots as follows:
$\\{\mathbf{a}:\exists\pi,~{}~{}{a_{i}}\in[0,w_{{\pi(i)}}]\text{ for all
}i\in[n]\\}$.

#### Bidder Selection.

In the Bidder Selection Problem (BSP) the seller first decides
${x_{i}}\in\\{0,1\\}$ which bidders $i\in[n]$ to invite to the auction. The
selected set of bidders $S$ may not exceed a certain capacity $k\geq|S|$,
i.e., $\sum_{i\in[n]}{x_{i}}\leq k$. Then the auctioneer runs an optimal
auction $\mathcal{A}$ for the set $S$ of invited bidders: VCG mechanism for
the welfare objective, and Myerson for the revenue objective. Since revenue of
the Myerson’s auction can be rewritten as the expected virtual welfare with
independent (ironed) virtual values
$(\varphi_{i}({v_{i}}):{v_{i}}\sim{D_{i}})_{i\in S}$, the BSP for the revenue
maximization is equivalent to the BSP for the welfare maximization. Thus it
suffices to only consider the welfare maximization problem. Specifically, we
denote by $\mathbf{v}\sim\mathbf{x}\cdot\mathbf{\mathbf{D}}$ the independent
draws of ${v_{i}}\sim{x_{i}}\cdot{D_{i}}$ (i.e., ${v_{i}}\sim{D_{i}}$ when
${x_{i}}=1$, and ${v_{i}}=0$ when ${x_{i}}=0$) for all $i\in[n]$, then the BSP
of the VCG mechanism for any $\ell$-unit/position auction with weights
$\mathbf{w}$ can be written as follows:

$\displaystyle\textsf{OPT}(\ell)$
$\displaystyle\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\max_{\begin{subarray}{c}\mathbf{x}\in\\{0,1\\}^{n}\\\
|\mathbf{x}|_{1}\leq
k\end{subarray}}~{}\operatornamewithlimits{\mathbf{E}}\limits_{\mathbf{v}\sim\mathbf{x}\cdot\mathbf{D}}\mathchoice{\left[\sum_{i=1}^{\ell}{v_{(i)}}\right]}{[\sum_{i=1}^{\ell}{v_{(i)}}]}{[\sum_{i=1}^{\ell}{v_{(i)}}]}{[\sum_{i=1}^{\ell}{v_{(i)}}]},$
$\displaystyle\textsf{OPT}(\mathbf{w})$
$\displaystyle\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\max_{\begin{subarray}{c}\mathbf{x}\in\\{0,1\\}^{n}\\\
|\mathbf{x}|_{1}\leq
k\end{subarray}}~{}\operatornamewithlimits{\mathbf{E}}\limits_{\mathbf{v}\sim\mathbf{x}\cdot\mathbf{D}}\mathchoice{\left[\sum_{i=1}^{n}w_{{i}}\cdot{v_{(i)}}\right]}{[\sum_{i=1}^{n}w_{{i}}\cdot{v_{(i)}}]}{[\sum_{i=1}^{n}w_{{i}}\cdot{v_{(i)}}]}{[\sum_{i=1}^{n}w_{{i}}\cdot{v_{(i)}}]},$

where ${v_{(i)}}$ is the $i$-th largest value among $\\{{v_{i}}\\}_{i\in[n]}$.
We want to obtain good approximation algorithms for these BSPs. I.e., we would
like to find in polynomial time $\mathbf{x}\in\\{0,1\\}^{n}$ with
$|\mathbf{x}|_{1}\leq k$ such that
$\operatorname{\mathbf{E}}_{\mathbf{v}\sim\mathbf{x}\cdot\mathbf{D}}\mathchoice{\left[\sum_{i=1}^{\ell}{v_{(i)}}\right]}{[\sum_{i=1}^{\ell}{v_{(i)}}]}{[\sum_{i=1}^{\ell}{v_{(i)}}]}{[\sum_{i=1}^{\ell}{v_{(i)}}]}\geq(1-\varepsilon)\,\textsf{OPT}(\ell)$
and
$\operatorname{\mathbf{E}}_{\mathbf{v}\sim\mathbf{x}\cdot\mathbf{D}}\mathchoice{\left[\sum_{i=1}^{n}w_{{i}}\cdot{v_{(i)}}\right]}{[\sum_{i=1}^{n}w_{{i}}\cdot{v_{(i)}}]}{[\sum_{i=1}^{n}w_{{i}}\cdot{v_{(i)}}]}{[\sum_{i=1}^{n}w_{{i}}\cdot{v_{(i)}}]}\geq(1-\varepsilon)\,\textsf{OPT}(\mathbf{w})$
for a small $\varepsilon>0$. To simplify the presentation, we assume that all
distributions $({D_{i}})_{i\in[n]}$ have finite supports and are given
explicitly as the algorithm’s input.

It has been observed before that the BSP’s objective is a monotone submodular
function of the set $S=\\{i:{x_{i}}=1\\}$ of invited bidders, i.e.,
$\textup{{SW}}(S)+\textup{{SW}}(T)\geq\textup{{SW}}(S\cap
T)+\textup{{SW}}(S\cup T)$ for any $S,T\subseteq[n]$. The same property holds
for the $\ell$-unit and position auctions with an almost identical proof (see
(Chen et al., 2016)).

We also consider the standard (in submodular optimization literature) multi-
linear extension of the BSP objective. I.e., for a fractional
$\mathbf{x}\in[0,1]^{n}$, we invite each bidder $i$ to the auction
independently with probability ${x_{i}}$. We employ the same notation
$\mathbf{v}\sim\mathbf{x}\cdot\mathbf{\mathbf{D}}$ as in the integral problem,
where ${v_{i}}\sim{x_{i}}\cdot{D_{i}}$ means that we first decide whether to
invite $\xi_{i}\in\\{0,1\\}$ bidder $i$ according to a Bernoulli distribution
$\xi_{i}\sim\textup{Ber}({x_{i}})$, then draw their value
${v_{i}}\sim\xi_{i}\cdot{D_{i}}$. The capacity constraint transforms into the
bound on the expected number of invited bidders $\sum_{i=1}^{n}{x_{i}}\leq k$.
We describe this new mathematical formulation in Section 3. In Section 4, we
first consider this fractional relaxation of BSP and we discuss in Section 4.2
how to obtain a good solution to the integral BSP from the fractional problem.

##  3\. New Mathematical Formulation

In this section, we give a fractional relaxation of BSP. As the welfare of any
position auction can be written as a linear combination of $\ell$-unit
auctions, we begin with a fractional relaxation of BSP for the $\ell$-unit
auction. Specifically, the expected social welfare with a fractional set of
bidders $\mathbf{x}$ is
$\textup{{SW}}(\mathbf{x},\ell)=\operatornamewithlimits{\mathbf{E}}\limits_{\mathbf{v}\sim\mathbf{x}\cdot\mathbf{\mathbf{D}}}\mathchoice{\left[\sum_{i=1}^{\ell}{v_{(i)}}\right]}{[\sum_{i=1}^{\ell}{v_{(i)}}]}{[\sum_{i=1}^{\ell}{v_{(i)}}]}{[\sum_{i=1}^{\ell}{v_{(i)}}]},$
where ${v_{(i)}}$ denotes the $i$-th largest value among
$\\{{v_{i}}\\}_{i\in\\{1,2,\dots,n\\}}$. Hence, the following mathematical
program represents BSP for $\ell$-unit auction:

$\begin{array}[]{ccl}\text{Maximize}&\textup{{SW}}(\mathbf{x},\ell)&\\\
\text{Subject To}&\sum_{i=1}^{n}{x_{i}}\leq k,&{x_{i}}\in[0,1],\forall
i\in\\{1,2,\dots,n\\}.\end{array}$

As $\ell$ is fixed, whenever it is clear from the context, we will simply
write $\textup{{SW}}(\mathbf{x})$.

#### Bernoulli Representation.

We now derive an explicit formula for the social welfare
$\textup{{SW}}(\mathbf{x})$. Fixing a threshold $\tau$, the expected number of
bidders with values exceeding $\tau$ among the highest $\ell$ bidders is
$\operatorname{\mathbf{E}}_{\mathbf{v}\sim\mathbf{x}\cdot\mathbf{\mathbf{D}}}\mathchoice{\left[\min(\sum_{i=1}^{n}\mathbb{I}\left[\vphantom{\sum}{v_{i}}\geq\tau\right],\ell)\right]}{[\min(\sum_{i=1}^{n}\mathbb{I}\left[\vphantom{\sum}{v_{i}}\geq\tau\right],\ell)]}{[\min(\sum_{i=1}^{n}\mathbb{I}\left[\vphantom{\sum}{v_{i}}\geq\tau\right],\ell)]}{[\min(\sum_{i=1}^{n}\mathbb{I}\left[\vphantom{\sum}{v_{i}}\geq\tau\right],\ell)]}$.
Therefore, by integrating888The function inside the integral is piece-wise
constant, i.e., it is constant between consecutive values of the threshold
$\tau$ in the supports of $\\{{D_{i}}\\}_{i\in[n]}$. over
$\tau\in[0,+\infty)$, we get

$\textup{{SW}}(\mathbf{x})=\int_{0}^{+\infty}\operatornamewithlimits{\mathbf{E}}\limits_{\mathbf{v}\sim\mathbf{x}\cdot\mathbf{\mathbf{D}}}\mathchoice{\left[\min\left(\sum_{i=1}^{n}\mathbb{I}\left[\vphantom{\sum}{v_{i}}\geq\tau\right],\,\ell\right)\right]}{[\min\left(\sum_{i=1}^{n}\mathbb{I}\left[\vphantom{\sum}{v_{i}}\geq\tau\right],\,\ell\right)]}{[\min\left(\sum_{i=1}^{n}\mathbb{I}\left[\vphantom{\sum}{v_{i}}\geq\tau\right],\,\ell\right)]}{[\min\left(\sum_{i=1}^{n}\mathbb{I}\left[\vphantom{\sum}{v_{i}}\geq\tau\right],\,\ell\right)]}\mathrm{d}\tau.$

Note that $\mathbb{I}\left[\vphantom{\sum}{v_{i}}\geq\tau\right]$ for
${v_{i}}\sim{x_{i}}\cdot{D_{i}}$ is a Bernoulli random variable, and
$\operatorname{\mathbf{E}}_{\mathbf{v}\sim\mathbf{x}\cdot\mathbf{\mathbf{D}}}\mathchoice{\left[\min(\sum_{i=1}^{n}\mathbb{I}\left[\vphantom{\sum}{v_{i}}\geq\tau\right],\ell)\right]}{[\min(\sum_{i=1}^{n}\mathbb{I}\left[\vphantom{\sum}{v_{i}}\geq\tau\right],\ell)]}{[\min(\sum_{i=1}^{n}\mathbb{I}\left[\vphantom{\sum}{v_{i}}\geq\tau\right],\ell)]}{[\min(\sum_{i=1}^{n}\mathbb{I}\left[\vphantom{\sum}{v_{i}}\geq\tau\right],\ell)]}$
is the minimum of a sum of independent Bernoulli random variables and $\ell$.
To simplify notations, we explicitly define the probabilities of Bernoulli
random variables $\mathbb{I}\left[\vphantom{\sum}{v_{i}}\geq\tau\right]$:
$\quad
q_{i}({x_{i}},\tau)\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\operatornamewithlimits{\mathbf{Pr}}\limits_{{v_{i}}\sim{x_{i}}\cdot{D_{i}}}\mathchoice{\left[{v_{i}}\geq\tau\right]}{[{v_{i}}\geq\tau]}{[{v_{i}}\geq\tau]}{[{v_{i}}\geq\tau]}={x_{i}}\cdot\left(1-{D_{i}}(\tau)\right)$

(2) $\textup{and
let}\quad\mathbf{q}(\mathbf{x},\tau)\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}(q_{i})_{i\in[n]}.$

###### Definition 3.1 (Bernoulli Objective).

For a vector $\mathbf{q}\in[0,1]^{n}$ and $\ell$, the Bernoulli objective term
of $\mathbf{q}$ and $\ell$ is a function
$\textup{H}_{\textup{ber}}(\mathbf{q},\ell)$:

$\displaystyle\textup{H}_{\textup{ber}}(\mathbf{q},\ell)$
$\displaystyle\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\operatornamewithlimits{\mathbf{E}}\limits_{\mathbf{z}\sim\textup{Ber}(\mathbf{q})}\mathchoice{\left[\min\left(\sum_{i=1}^{n}{z_{i}},\,\ell\right)\right]}{[\min\left(\sum_{i=1}^{n}{z_{i}},\,\ell\right)]}{[\min\left(\sum_{i=1}^{n}{z_{i}},\,\ell\right)]}{[\min\left(\sum_{i=1}^{n}{z_{i}},\,\ell\right)]},$
(3) $\displaystyle\textup{then}\quad\textup{{SW}}(\mathbf{x})$
$\displaystyle=\int_{0}^{+\infty}\textup{H}_{\textup{ber}}(\mathbf{q}(\mathbf{x},\tau),\ell)\,\mathrm{d}\tau.$

#### Position Auctions.

A position auction is given by a vector of non-negative weights999Usually
weights are only for the first $k$ slots, as we only select a set of $k$
bidders. In this case, we simply assume that $w_{k+1}=\ldots=w_{n}=0$.
$\mathbf{w}:(w_{{1}}\geq w_{{2}}\geq\cdots\geq w_{{n}}\geq 0)$. The highest
social welfare we get from the set $S$ of invited bidders is
$\sum_{i=1}^{|S|}{v_{(i)}}\cdot w_{{i}}$, where
${v_{(1)}}\geq\cdots\geq{v_{(|S|)}}$ are ordered values of bidders in $S$.
Thus the expected social welfare for a fractional set $\mathbf{x}$ is

$\textup{{SW}}(\mathbf{x},\mathbf{w})=\operatornamewithlimits{\mathbf{E}}\limits_{\mathbf{v}\sim\mathbf{x}\cdot\mathbf{\mathbf{D}}}\mathchoice{\left[\sum_{i=1}^{n}{v_{(i)}}\cdot
w_{{i}}\right]}{[\sum_{i=1}^{n}{v_{(i)}}\cdot
w_{{i}}]}{[\sum_{i=1}^{n}{v_{(i)}}\cdot
w_{{i}}]}{[\sum_{i=1}^{n}{v_{(i)}}\cdot
w_{{i}}]}=\sum_{\ell=1}^{n}(w_{{\ell}}-w_{{\ell+1}})\cdot\textup{{SW}}(\mathbf{x},\ell),$

where $w_{n+1}\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}0$. Then the
respective fractional BSP program for position auctions is as follows.

$\begin{array}[]{ccl}\text{Maximize}&\textup{{SW}}(\mathbf{x},\mathbf{w})&\\\
\text{Subject To}&\sum_{i=1}^{n}{x_{i}}\leq k,&{x_{i}}\in[0,1],\forall
i\in\\{1,2,\dots,n\\}.\end{array}$

We will often omit dependency on $\mathbf{w}$ in SW whenever it is clear from
the context. We further consider the _Bernoulli representation_ for position
auctions:

$\displaystyle\textup{{SW}}(\mathbf{x},\mathbf{w})$
$\displaystyle=\int_{0}^{+\infty}\textup{H}_{\textup{ber}}(\mathbf{q}(\mathbf{x},\tau),\mathbf{w})\,\mathrm{d}\tau,$
(5)
$\displaystyle\text{where}\quad\textup{H}_{\textup{ber}}(\mathbf{q},\mathbf{w})$
$\displaystyle\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\sum_{\ell=1}^{n}(w_{{\ell}}-w_{{\ell+1}})\,\textup{H}_{\textup{ber}}(\mathbf{q},\ell).$

As in (2), $\mathbf{q}(\mathbf{x},\tau)$ represents the probabilities of each
bidder’s value exceeding $\tau$.
$\textup{H}_{\textup{ber}}(\mathbf{q},\mathbf{w})$ is called the Bernoulli
objective term for position auctions.

###  3.1. Overview of Our Approach

The fractional relaxation (3) is still neither convex nor concave and thus is
too unwieldy. The central idea of our paper is to use instead _Poisson
approximation_ to the Bernoulli objective terms
$\textup{H}_{\textup{ber}}(\mathbf{q}(\mathbf{x},\tau),\mathbf{w})$.
Specifically, we substitute each Bernoulli random variable
$z\sim\textup{Ber}(p)$ with $p=q_{i}(x_{i},\tau)$ by the Poisson random
variable $y\sim\textup{Pois}(p)$ with the same expectation as $z$. We use the
following Poisson objective term $\textup{H}_{\textup{pois}}(\mathbf{q},\ell)$
to approximate $\textup{H}_{\textup{ber}}(\mathbf{q},\ell)$.

$\displaystyle\textup{H}_{\textup{pois}}(\mathbf{q},\ell)$
$\displaystyle\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\operatornamewithlimits{\mathbf{E}}\limits_{\mathbf{y}\sim\textup{Pois}(\mathbf{q})}\left[\min\left(\sum_{i=1}^{n}y_{i},\,\ell\right)\right]$
$\displaystyle=\operatornamewithlimits{\mathbf{E}}\limits_{Y\sim\textup{Pois}(\sum_{i=1}^{n}q_{i})}\mathchoice{\left[\min\left(Y,\,\ell\right)\right]}{[\min\left(Y,\,\ell\right)]}{[\min\left(Y,\,\ell\right)]}{[\min\left(Y,\,\ell\right)]}.$

The advantage of the Poisson approximation
$\textup{H}_{\textup{pois}}(\mathbf{q},\ell)$ is that the resulting functions
$\textup{H}_{\textup{pois}}(\mathbf{q},\ell)$ and
$\textup{H}_{\textup{pois}}(\mathbf{q},\mathbf{w})$ are _concave_ in
$\mathbf{q}$. This in turn allows us to efficiently solve the optimization
problem for the Poisson approximation analogous to (3). This Poisson
approximation works well101010The sum of Poisson random variables approaches
the sum of Bernoulli random variables in TV and other statistical distances.
in the following situations.

  1. (1)

When the probabilities $p_{i}=q_{i}(x_{i},\tau)$ of
$z_{i}\sim\textup{Ber}(p_{i})$ are small (i.e., $p_{i}\leq\delta,\forall
i\in[n]$). This allows us to handle the crucial contribution to the welfare
comprised of small probability tail events for large thresholds $\tau$.

  2. (2)

When
$\operatorname{\mathbf{E}}\mathchoice{\left[\sum_{i=1}^{n}{z_{i}}\right]}{[\sum_{i=1}^{n}{z_{i}}]}{[\sum_{i=1}^{n}{z_{i}}]}{[\sum_{i=1}^{n}{z_{i}}]}$
is large (when thresholds $\tau$ are small). Indeed, by Chernoff bounds the
sums of independent random variables (both Bernoulli and Poisson)
$\sum_{i=1}^{n}{z_{i}}$ and $\sum_{i=1}^{n}y_{i}$ are close to their
expectations. In fact, we simply use Chernoff objective term
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\min\left(\sum_{i=1}^{n}q_{i},\,\ell\right)$
instead of Poisson approximation in this case.

  3. (3)

When $\ell$ is large. In this case, either the concentration inequality gives
a good approximation when
$\operatorname{\mathbf{E}}\mathchoice{\left[\sum_{i=1}^{n}{z_{i}}\right]}{[\sum_{i=1}^{n}{z_{i}}]}{[\sum_{i=1}^{n}{z_{i}}]}{[\sum_{i=1}^{n}{z_{i}}]}=\operatorname{\mathbf{E}}\mathchoice{\left[\sum_{i=1}^{n}y_{i}\right]}{[\sum_{i=1}^{n}y_{i}]}{[\sum_{i=1}^{n}y_{i}]}{[\sum_{i=1}^{n}y_{i}]}$
is large, or when this expectation is much smaller than $\ell$ then the
probability that either of $\sum_{i=1}^{n}{z_{i}}$ or $\sum_{i=1}^{n}y_{i}$
exceeds the threshold $\ell$ is small.

Then the algorithmic framework for the BSP is rather straightforward. We need
to solve the following _concave_ program of $\mathbf{x}$:

$\begin{array}[]{cl}\text{Maximize}&\sum_{\ell=1}^{n}(w_{{\ell}}-w_{{\ell+1}})\int_{0}^{+\infty}\textup{H}_{\textup{pois}}(\mathbf{q}(\mathbf{x},\tau),\ell)\,\mathrm{d}\tau\\\
\text{Subject To}&\sum_{i=1}^{n}{x_{i}}\leq k,\quad{x_{i}}\in[0,1],\forall
i\in\\{1,2,\dots,n\\}.\end{array}$

We define the approximate social welfare
$\widetilde{\textup{{SW}}}(\mathbf{x},\mathbf{w})$ to be the objective of
(3.1). Here,
$\textup{H}_{\textup{pois}}(\mathbf{q}(\mathbf{x},\tau),\ell)=\operatorname{\mathbf{E}}_{Y\sim\textup{Pois}(\sum
q_{i})}\mathchoice{\left[\min\left(Y,\,\ell\right)\right]}{[\min\left(Y,\,\ell\right)]}{[\min\left(Y,\,\ell\right)]}{[\min\left(Y,\,\ell\right)]}$
and all functions under the integral are piece-wise constant with the number
of pieces bounded by the size of the union of the supports of ${D_{i}}$. The
optimal fractional solution $\mathbf{x}$ can be computed rather efficiently
using continuous convex optimization. Finally, we use a rounding procedure
(similar to the multi-linear extension of submodular function) to the
fractional solution of (3.1) to obtain an integral solution with a small loss
to the approximation guarantee.

##  4\. Our Algorithm

_Poisson approximation_ is the central idea of this paper. We use the Poisson
Objective to approximate Bernoulli objective terms.

###### Definition 4.1 (Poisson Objective).

For $\mathbf{q}\in[0,1]^{n}$ and $\ell\in\mathbb{N}$, the Poisson objective
term is a function $\textup{H}_{\textup{pois}}(\mathbf{q},\ell)$ given by

$\displaystyle\textup{H}_{\textup{pois}}(\mathbf{q},\ell)$
$\displaystyle\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\operatornamewithlimits{\mathbf{E}}\limits_{\mathbf{y}\sim\textup{Pois}(\mathbf{q})}\left[\min\left(\sum_{i=1}^{n}y_{i},\,\ell\right)\right]$
$\displaystyle=\operatornamewithlimits{\mathbf{E}}\limits_{Y\sim\textup{Pois}(\sum_{i=1}^{n}q_{i})}\mathchoice{\left[\min\left(Y,\,\ell\right)\right]}{[\min\left(Y,\,\ell\right)]}{[\min\left(Y,\,\ell\right)]}{[\min\left(Y,\,\ell\right)]}.$

Note that the latter equality is an important property of Poisson
distribution: the sum of independent Poisson random variables
$y_{i}\sim\textup{Pois}(q_{i})$ follows the Poisson distribution
$\textup{Pois}(\sum_{i=1}^{n}q_{i})$. Another crucial property is the
concavity of Poisson approximation.

###### Claim 4.2 (Concavity of Poisson).

$\textup{H}_{\textup{pois}}(\mathbf{q},\ell)$ is a concave function in
$\mathbf{q}\in[0,1]^{n}$ for $\forall\ell\in{\mathbb{N}}$.

###### Proof.

Let $\lambda=\sum_{i=1}^{n}q_{i}$. Notice that
$\textup{H}_{\textup{pois}}(\mathbf{q},\ell)$ only depends on $\lambda$, which
is linear in $\mathbf{q}$. We use $\textup{H}_{\textup{pois}}(\lambda)$ to
represent this function. Then, we only need to prove that
$\textup{H}_{\textup{pois}}(\lambda)$ is concave in $\lambda$. Rewrite

$\textup{H}_{\textup{pois}}(\lambda)=\ell-\sum_{j=0}^{\ell-1}\operatornamewithlimits{\mathbf{Pr}}\limits_{Y\sim\textup{Pois}(\lambda)}\mathchoice{\left[Y=j\right]}{[Y=j]}{[Y=j]}{[Y=j]}\cdot(\ell-j)=\ell-\sum_{j=0}^{\ell-1}\frac{\lambda^{j}}{j!}e^{-\lambda}\cdot(\ell-j).$

By a straightforward differentiation of the partial series we get

$\frac{\mathrm{d}}{\mathrm{d}\lambda}\textup{H}_{\textup{pois}}=\sum_{j=0}^{\ell-1}\frac{\lambda^{j}}{j!}e^{-\lambda},\quad\quad\frac{\mathrm{d}^{2}}{\mathrm{d}\lambda^{2}}\textup{H}_{\textup{pois}}=-e^{-\lambda}\frac{\lambda^{\ell-1}}{(\ell-1)!}<0.$

Therefore, $\textup{H}_{\textup{pois}}(\mathbf{q},\ell)$ is concave in
$\lambda$, and thus concave in $\mathbf{q}$. ∎

#### Chernoff Approximation.

As we mentioned earlier Poisson approximation is useful for small
probabilities $q_{i}\leq\delta$. For another extreme case where
$\lambda=\sum_{i=1}^{n}q_{i}$ is large, due to concentration bounds, Poisson
approximation also works well with $O(\lambda^{-1/2})$ relative error, because
both $\sum_{i=1}^{n}\textup{Ber}(q_{i})$ and $\textup{Pois}(\lambda)$
concentrate around $\lambda$. To optimize the presentation for an easier
understanding, we will use Chernoff objective term
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\min\left(\sum_{i=1}^{n}q_{i},\ell\right)$
as an alternative of Poisson in this case. It is also concave in $\mathbf{q}$.

In a number of cases $\textup{H}_{\textup{pois}}(\mathbf{q},\ell)$ and
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)$ are good approximations to
$\textup{H}_{\textup{ber}}(\mathbf{q},\ell)$. In Appendix A, we present these
approximation guarantees along with a simple algorithm that illustrates our
approach in an important special case.

###  4.1. Algorithm for Position Auctions

Below, we consider Bidder Section Problem for position auctions. We first
analyze the fractional BSP, and then explain in Section 4.2 how to do integral
rounding of the fractional solution with only a small loss to the
approximation guarantee. For the fractional BSP, we give an efficient
polynomial time $(1-O(k^{-4}))$-approximation algorithm (see Theorem 4.4 for
the exact statement).

Recall that the Bernoulli objective term for position auctions
$\textup{H}_{\textup{ber}}(\mathbf{q},\mathbf{w})$ is defined in Section 3.
The expected welfare
$\textup{{SW}}(\mathbf{x})=\textup{{SW}}(\mathbf{x},\mathbf{w})$ is written as
an integral of $\textup{H}_{\textup{ber}}$. Below, we will also need the
Chernoff objective term

$\textup{H}_{\textup{cher}}(\mathbf{q},\mathbf{w})\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\sum_{\ell=1}^{n}(w_{{\ell}}-w_{{\ell+1}})\,\textup{H}_{\textup{cher}}(\mathbf{q},\ell).$

We sometimes slightly abuse notations and write
$\textup{H}_{\textup{ber}}(\mathbf{x},\tau)$ and
$\textup{H}_{\textup{cher}}(\mathbf{x},\tau)$ instead of
$\textup{H}_{\textup{ber}}(\mathbf{q},\mathbf{w})$ and
$\textup{H}_{\textup{cher}}(\mathbf{q},\mathbf{w})$.

In order to effectively use the Poisson approximation we would like to have
the small probability assumption $q_{i}\leq\delta$, which is achieved by
fixing a small bidder set $S_{\textup{fix}}$ properly (see Appendix A for
formal approximation guarantees).

#### Fixing Small Bidder Set.

We will fix a small set of bidders $S_{\textup{fix}}$ (set ${x_{i}}=1$ for
$i\in S_{\textup{fix}}$) with $|S_{\textup{fix}}|=\varepsilon\cdot k$ and make
sure that all other bidders $i\notin S_{\textup{fix}}$ have only a small
probability
$\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}\geq\tau\right]}{[{v_{i}}\geq\tau]}{[{v_{i}}\geq\tau]}{[{v_{i}}\geq\tau]}\leq\delta$
to exceed any of the thresholds $\tau>\eta$ for certain $\eta>0$. This allows
us to use Poisson approximation for the high range thresholds $\tau>\eta$ and
bidders $i\in M\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}[n]\setminus
S_{\textup{fix}}$. On the other hand, for the low range thresholds
$\tau\leq\eta$, we would like to see a certain number $\ell^{*}$ of bidders
$i\in S_{\textup{fix}}$ to exceed the threshold ${v_{i}}\geq\tau$. To this
end, we choose $S_{\textup{fix}}$ so that the expected number of bidders $i\in
S_{\textup{fix}}$ with ${v_{i}}\geq\tau$ is at least $\ell^{*}$. We can
achieve the following guarantees for $\varepsilon,\delta,$ and $\ell^{*}$.

###### Claim 4.3 (Small Bidder Set).

Let $\varepsilon\in[\frac{\ell^{*}}{\delta\cdot k},1)$ be a multiple of $1/k$
for $\ell^{*}\in\mathbb{R}_{\geq 0}:\ell^{*}<k$ and $\delta\in(0,1)$. We can
find in polynomial time a threshold $\eta\geq 0$ and a set
$S_{\textup{fix}}\subseteq[n]$ of size $|S_{\textup{fix}}|=\varepsilon\cdot
k$:

  1. (a)

$\displaystyle\forall\,0\leq\tau\leq\eta,\quad\sum_{i\in
S_{\textup{fix}}}\operatornamewithlimits{\mathbf{Pr}}\limits_{{v_{i}}\sim{D_{i}}}\mathchoice{\left[{v_{i}}\geq\tau\right]}{[{v_{i}}\geq\tau]}{[{v_{i}}\geq\tau]}{[{v_{i}}\geq\tau]}\geq\ell^{*}$;

  2. (b)

$\displaystyle\forall\,i\notin
S_{\textup{fix}},\qquad\;\operatornamewithlimits{\mathbf{Pr}}\limits_{{v_{i}}\sim{D_{i}}}\mathchoice{\left[{v_{i}}>\eta\right]}{[{v_{i}}>\eta]}{[{v_{i}}>\eta]}{[{v_{i}}>\eta]}<\delta.$

###### Proof.

We search through all thresholds $\tau$ in the supports of
$\\{{D_{i}}\\}_{i\geq 1}$ and find two consecutive threshold values $\eta$ and
$\eta_{+}\\!>\eta$ such that
$|\\{i:\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}\geq\eta\right]}{[{v_{i}}\geq\eta]}{[{v_{i}}\geq\eta]}{[{v_{i}}\geq\eta]}\geq\delta\\}|\geq\varepsilon\cdot
k$, but a similar number of bidders
$|\\{i:\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}>\eta\right]}{[{v_{i}}>\eta]}{[{v_{i}}>\eta]}{[{v_{i}}>\eta]}=\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}\geq\eta_{+}\right]}{[{v_{i}}\geq\eta_{+}]}{[{v_{i}}\geq\eta_{+}]}{[{v_{i}}\geq\eta_{+}]}\geq\delta\\}|<\varepsilon\cdot
k$ for the next value $\eta_{+}$. We place each bidder $i$ with
$\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}>\eta\right]}{[{v_{i}}>\eta]}{[{v_{i}}>\eta]}{[{v_{i}}>\eta]}\geq\delta$
into $S_{\textup{fix}}$ and fill the remaining positions in $S_{\textup{fix}}$
up to $\varepsilon\cdot k$ with bidders from
$\\{i:\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}\geq\eta\right]}{[{v_{i}}\geq\eta]}{[{v_{i}}\geq\eta]}{[{v_{i}}\geq\eta]}\geq\delta>\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}\geq\eta_{+}\right]}{[{v_{i}}\geq\eta_{+}]}{[{v_{i}}\geq\eta_{+}]}{[{v_{i}}\geq\eta_{+}]}\\}$.

Thus, every bidder $i\notin S_{\textup{fix}}$ has
$\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}>\eta\right]}{[{v_{i}}>\eta]}{[{v_{i}}>\eta]}{[{v_{i}}>\eta]}=\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}\geq\eta_{+}\right]}{[{v_{i}}\geq\eta_{+}]}{[{v_{i}}\geq\eta_{+}]}{[{v_{i}}\geq\eta_{+}]}<\delta$
as required by condition (b). On the other hand,
$|S_{\textup{fix}}|=\varepsilon\cdot k$ and
$\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}\geq\eta\right]}{[{v_{i}}\geq\eta]}{[{v_{i}}\geq\eta]}{[{v_{i}}\geq\eta]}\geq\delta$
for every $i\in S_{\textup{fix}}$, which implies (a), since
$\forall\tau\leq\eta$,

$\sum_{i\in
S_{\textup{fix}}}\operatornamewithlimits{\mathbf{Pr}}\limits_{{v_{i}}\sim{D_{i}}}\mathchoice{\left[{v_{i}}\geq\tau\right]}{[{v_{i}}\geq\tau]}{[{v_{i}}\geq\tau]}{[{v_{i}}\geq\tau]}\geq\sum_{i\in
S_{\textup{fix}}}\operatornamewithlimits{\mathbf{Pr}}\limits_{{v_{i}}\sim{D_{i}}}\mathchoice{\left[{v_{i}}\geq\eta\right]}{[{v_{i}}\geq\eta]}{[{v_{i}}\geq\eta]}{[{v_{i}}\geq\eta]}\geq\delta\cdot|S_{\textup{fix}}|=\delta\cdot\varepsilon\cdot
k\geq\ell^{*}.$

Thus we constructed in polynomial time the desired threshold $\eta$ and set
$S_{\textup{fix}}$. ∎

We need to balance three parameters $\ell^{*},$ $\delta$, and $\varepsilon$,
which must satisfy the conditions of 4.3. Specifically, we choose
$\ell^{*}=k^{1/2}$, $\varepsilon=k^{-1/4}$ rounded up to a multiple of $1/k$,
and $\delta=\varepsilon\geq k^{-1/4}$. 4.3 leads to Section 4.1 (which we will
present shortly).

For thresholds $\tau>\eta$, any bidder outside $S_{\textup{fix}}$ has only
$\leq\delta$ probability to exceed the threshold, which is ideal for applying
the Poisson approximation. Therefore, to achieve the approximation guarantees
when the probability of exceeding the threshold is low, we recalculate the
adjusted Poisson objective term by applying Poisson approximation only on
these bidders. Specifically, we let
$M\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}[n]\setminus
S_{\textup{fix}}$ and define
$Z_{\textup{fix}}(\tau)\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\sum_{i\in
S_{\textup{fix}}}\mathbb{I}\left[\vphantom{\sum}{v_{i}}\geq\tau\right]$ (as
$\mathbf{x}_{S_{\textup{fix}}}=\mathbf{1}_{S_{\textup{fix}}}$, random variable
$Z_{\textup{fix}}(\tau)$ has Poisson binomial distribution). Indeed, we may
calculate all probabilities
$\operatorname{\mathbf{Pr}}\mathchoice{\left[Z_{\textup{fix}}(\tau)=j\right]}{[Z_{\textup{fix}}(\tau)=j]}{[Z_{\textup{fix}}(\tau)=j]}{[Z_{\textup{fix}}(\tau)=j]}$
for each $j\in[0,\varepsilon\cdot k]$ in polynomial time, and define the
adjusted Poisson objective term as a conditional expectation depending on
$Z_{\textup{fix}}(\tau)$:

$\displaystyle\textup{G}_{\textup{pois}}(\mathbf{x}_{\scriptscriptstyle
M},\tau)$
$\displaystyle\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\sum_{j=0}^{|S_{\textup{fix}}|}\operatorname{\mathbf{Pr}}\mathchoice{\left[Z_{\textup{fix}}(\tau)=j\right]}{[Z_{\textup{fix}}(\tau)=j]}{[Z_{\textup{fix}}(\tau)=j]}{[Z_{\textup{fix}}(\tau)=j]}\cdot\biggl{(}\sum_{\ell=1}^{j}w_{{\ell}}+{}$
(7)
$\displaystyle\quad\;\sum_{\ell=j+1}^{n}(w_{{\ell}}-w_{{\ell+1}})\cdot\textup{H}_{\textup{pois}}(\mathbf{x}_{\scriptscriptstyle
M},\,\ell\\!-\\!j,\,\tau)\biggr{)},$

where $\textup{H}_{\textup{pois}}(\mathbf{x}_{\scriptscriptstyle
M},\ell-j,\tau)=\operatornamewithlimits{\mathbf{E}}\limits_{Y\sim\textup{Pois}(\lambda_{M})}\mathchoice{\left[\min\left\\{Y,\,\ell-j\right\\}\right]}{[\min\left\\{Y,\,\ell-j\right\\}]}{[\min\left\\{Y,\,\ell-j\right\\}]}{[\min\left\\{Y,\,\ell-j\right\\}]}$,
and $\lambda_{M}=\sum_{i\in M}q_{i}({x_{i}},\tau)$. For the low-range
thresholds $\tau\leq\eta$, we use the Chernoff objective
$\textup{H}_{\textup{cher}}(\mathbf{x},\tau)=\textup{H}_{\textup{cher}}(\mathbf{q}(\mathbf{x},\tau),\mathbf{w})$
to approximate
$\textup{H}_{\textup{ber}}(\mathbf{x},\tau)=\textup{H}_{\textup{ber}}(\mathbf{q}(\mathbf{x},\tau),\mathbf{w})$
for $\mathbf{x}=(\mathbf{x}_{\scriptscriptstyle
M},\mathbf{1}_{S_{\textup{fix}}})$. Importantly, unlike the high-range
thresholds, we do not recalculate $\textup{H}_{\textup{cher}}$ as a function
of $\mathbf{x}_{\scriptscriptstyle M}$, but use Chernoff approximation for the
entire $n$-dimensional vector $\mathbf{x}=(\mathbf{x}_{\scriptscriptstyle
M},\mathbf{x}_{S_{\textup{fix}}})$ with
$\mathbf{x}_{S_{\textup{fix}}}=\mathbf{1}_{S_{\textup{fix}}}$. Thus, as
$\ell^{*}=k^{1/2}$ grows with $k$,
$\textup{H}_{\textup{cher}}(\mathbf{x},\tau)\to\textup{H}_{\textup{ber}}(\mathbf{x},\tau)$.

#### Algorithm.

Our main algorithm is summarized as Algorithm 4.1.

Algorithm 0 Fractional BSP for Position Auctions Let $\ell^{*}=k^{1/2}$;
$\varepsilon$ be $k^{-1/4}$ rounded up to a multiple of $1/k$
$\big{(}\varepsilon=\frac{\lceil k\cdot k^{-1/4}\rceil}{k}\big{)}$;
$\delta=\varepsilon$. (1) Find $\eta$ and $S_{\textup{fix}}$ according to 4.3.
Set ${x_{i}}=1$ for $\forall i\in S_{\textup{fix}}$. Let
$M\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}[n]\setminus
S_{\textup{fix}}$. (2) Define the approximate welfare using adjusted Poisson
objective (7):
$\displaystyle\widetilde{\textup{{SW}}}(\mathbf{x}_{\scriptscriptstyle M})$
$\displaystyle\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\int_{0}^{\eta}\textup{H}_{\textup{cher}}((\mathbf{x}_{\scriptscriptstyle
M},\mathbf{1}_{S_{\textup{fix}}}),\tau)\,\mathrm{d}\tau$ (8)
$\displaystyle\quad\
+\int_{\eta}^{+\infty}\textup{G}_{\textup{pois}}\left(\mathbf{x}_{\scriptscriptstyle
M},\tau\right)\,\mathrm{d}\tau,$ (3) Return
$\widetilde{\mathbf{x}}^{*}=(\widetilde{\mathbf{x}}_{\scriptscriptstyle
M}^{*},\mathbf{1}_{S_{\textup{fix}}})$, where
$\widetilde{\mathbf{x}}_{\scriptscriptstyle M}^{*}$ is the solution to the
concave program in $\mathbf{x}_{\scriptscriptstyle M}$:
$\begin{array}[]{lll}\text{Maximize}&\widetilde{\textup{{SW}}}(\mathbf{x}_{\scriptscriptstyle
M})\\\ \text{Subject To}&\sum_{i\in M}{x_{i}}\leq k-\varepsilon\cdot
k,\;\;{x_{i}}\in[0,1]\;\forall i\in M.\end{array}$

###### Theorem 4.4.

Section 4.1 works in polynomial time and is a
$(1-O(\varepsilon))$-approximation, i.e., $(1-43\,k^{-1/4})$-approximation to
the fractional BSP for any position auction.

The proof of this theorem is deferred to Section B.1.

###  4.2. Rounding

We conclude Section 4 by presenting the rounding algorithm, which takes our
solution $\widetilde{\mathbf{x}}^{*}$ to the fractional BSP produced by
Section 4.1 and returns a solution to the integral BSP.

Our fractional relaxation works as the standard multi-linear extension of
submodular functions, which corresponds to sampling a random set of bidders
$S\sim\prod_{i=1}^{n}\textup{Ber}({x_{i}})$ in the integral BSP. To align the
notations for fractional and integral BSPs, we shall use vectors
$\mathbf{y},\mathbf{z}\in\\{0,1\\}^{n}$ for the respective sets of selected
bidders. Specifically, we use $\mathbf{y}\sim\textup{Ber}(\mathbf{x})$ to
represent the random set $S$ in the multi-linear extension. Our rounding
procedure is in Section 4.2.

Algorithm 0 Rounding: algorithm for Integral BSP (1) Run Section 4.1 to obtain
a fractional solution $\mathbf{x}$. (2) Sample an integral solution
$\mathbf{y}\sim\textup{Ber}(\mathbf{x})$, with $\mathbf{y}\in\\{0,1\\}^{n}$.
(3) • If $|\mathbf{y}|_{1}\leq k$, return $\mathbf{z}=\mathbf{y}$, • Else
($|\mathbf{y}|_{1}>k$), return $k$ bidders
$\mathbf{z}\sim\binom{\mathbf{y}}{k}$ chosen uniformly at random from
$\mathbf{y}$.

###### Theorem 4.5.

Section 4.2 works in polynomial time and in expectation is a
$\bigl{(}1-43\,k^{-1/4}-O(k^{-1/2})\bigr{)}$-approximation to the integral BSP
for any position auction.

The proof of Theorem 4.5 is deferred to Section B.2. Since
$\textup{{SW}}(\mathbf{z})\leq\textsf{OPT}$, by running the rounding algorithm
a few times and taking the best produced solution, we get a slightly worse
approximation guarantee of $(1-O(k^{-1/4}))\textsf{OPT}$ with high
probability.

##  5\. Numerical Experiments

We focus on testing welfare maximization Bidder Selection Problem for position
auctions. In our experiments, we used synthetically generated prior
distributions, as (1) the BSP is a pure optimization problem, which ignores
the issue of data retrieval (2) due to companies’ strict nondisclosure rules,
it is infeasible to experiment on real historical data. We generally followed
the AuctionGym (Jeunen et al., 2023) setup, a popular online simulation
environment for advertising auctions run by Amazon, in the design of our
synthetic data.

#### Implementation.

We implemented Sections 4.2 and 4.1 as well as its modified version for BSP.
In this simpler modification, we used a slightly different objective
$\widetilde{\textup{{SW}}}(\mathbf{x})\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\int_{0}^{+\infty}\textup{H}_{\textup{pois}}(\mathbf{x},\tau)\,\mathrm{d}\tau$
than (8): we did not fix any small bidder set, only applied Poisson
approximation, and used the same rounding step. The original Section 4.1 was
designed with the worst-case theoretical guarantees in mind, while the
modified one is more practically oriented and retains only the most important
Poisson approximation. The modification did not affect the run-time much, but
allowed us to avoid hard-coded approximation loss of $O(k^{-1/4})$ due to the
potentially suboptimal decision of fixing a small bidder set
$S_{\textup{fix}}$. We implemented the practical variant in Python with the
help of Gurobi (Gurobi Optimization, LLC, 2023), a well-known commercial
convex optimization solver, and present its comparison111111We also compared
the performances of the modified version and the theoretical version of our
algorithm in Section D.1. The approximation efficiency of the theoretical
version was worse than the modified version as expected. with benchmark
algorithms in Table 1.

Table 1. Experimental results of Local Search, Greedy, and our algorithm. The “solution” column for each algorithm denotes the average relative quality of the produced solution to that of the best-performing algorithm that terminated in $1$ week. Error bars denote the standard deviation. The “time” column denotes the average running time of each algorithm.  Setting | Local Search | Greedy | Our Algorithm
---|---|---|---
$n$ | $k$ | Solution | Time | Solution | Time | Solution | Time
50 | 5 | 100.00% ± 0.00% | 1.01 seconds | 98.93% ± 0.50% | 0.21 seconds | 99.99% ± 0.03% | 1.29 seconds
10 | 100.00% ± 0.00% | 6.05 seconds | 98.71% ± 0.38% | 1.11 seconds | 99.99% ± 0.04% | 1.59 seconds
20 | 100.00% ± 0.00% | 65.23 seconds | 99.17% ± 0.28% | 9.02 seconds | 99.99% ± 0.01% | 2.58 seconds
200 | 10 | 100.00% ± 0.00% | 1.02 minutes | 98.06% ± 0.35% | 8.10 seconds | 99.99% ± 0.01% | 2.83 seconds
20 | 100.00% ± 0.00% | 10.83 minutes | 97.92% ± 0.24% | 44.72 seconds | 100.00% ± 0.00% | 3.88 seconds
40 | 100.00% ± 0.00% | 60.66 minutes | 97.97% ± 0.26% | 170.29 seconds | 99.99% ± 0.00% | 3.97 seconds
1000 | 50 | 100.00% ± 0.00% | 33.71 hours | 97.18% ± 0.14% | 0.90 hours | 99.99% ± 0.00% | 21.54 seconds
100 | N/A |  $>1$ week | 97.15% ± 0.15% | 4.26 hours | 100.00% ± 0.00% | 41.21 seconds
200 | N/A |  $>1$ week | 97.38% ± 0.11% | 27.65 hours | 100.00% ± 0.00% | 45.16 seconds

#### Benchmarks.

Ideally, we would like to compare our solutions to the optimum, which is
usually not possible, as BSP is an NP-hard problem even for the case of
single-item auction (Goel et al., 2010). It is also infeasible to use any of
the existing PTAS algorithms, as only (Chen et al., 2016) implemented their
PTAS but could only run experiments on tiny input sizes of $(n=9,k=3)$, while
EPTASes of (Mehta et al., 2020; Segev and Singla, 2021) are pure computational
complexity results with unrealistically large estimates on running times for
inputs of any size. Instead, we used two well-known heuristic algorithms as
our benchmarks: Greedy for submodular maximization following numerical
experiments in (Chen et al., 2016; Mehta et al., 2020), and Local Search
mentioned in (Bei et al., 2023). They are easy to implement and run in
feasible times on most of our datasets. Note that if Local Search starts with
the solution produced by Greedy, it can only improve upon it, i.e., it seems
reasonable to use Local Search as a main reference point for approximation
efficiency guarantees. We also tested Local Search against the exact optimum
computed by Brute Force on small instances $(n=50,k=5)$ and found that they
always produced the same results. We implemented Greedy, Local Search, and
Brute Force in Python to ensure a fair comparison with our algorithm. We also
limited the number of threads used by our algorithm to $1$, as the benchmark
algorithms are not parallelizable.

#### Datasets.

We generated each of the $n$ prior distributions as a log-normal distribution
$\mathrm{Lognormal}(\mu,\sigma^{2})$ as in AuctionGym (Jeunen et al., 2023).
We selected parameters $\mu$ and $\sigma$ of each individual distribution by
drawing them independently from continuous uniform distributions
$\mathcal{U}[0,0.2]$ and $\mathcal{U}[0,0.5]$, respectively.121212 AuctionGym
uses comparable $\mu=0.1$ and $\sigma=0.2$. We then discretized each
distribution to a common, finite support $\\{0\\}\cup\\{1+\frac{i}{50}\mid
i=0,1,\dots,49\\}$ by moving probability mass on each discretized interval
inside $[0,2]$ to its left point and by redistributing the mass on
$(2,+\infty)$ to the discrete points, proportional to their respective
probabilities. The weights $\mathbf{w}$ of the position auction on each
instance were set as: $w_{{i}}=1$ for $i\in[1,0.2k]$, $w_{{i}}=0.2$ for
$i\in(0.2k,0.6k]$, and $w_{{i}}=0$ for $i\in(0.6k,k]$. We constructed datasets
with $3$ different $n\in\\{50,200,1000\\}$. For each $n$, we used $3$
different values of $k$: for $n=50$, we set $k\in\\{5,10,20\\}$; for $n=200$,
we set $k\in\\{10,20,40\\}$; and for $n=1000$, we set $k\in\\{50,100,200\\}$.
The general idea was to capture practically relevant scenarios of different
scales, and also have our benchmarks solve them in a reasonable time.
Moreover, we picked $k$ so that it is always significantly smaller than $n$.
Note that this puts our algorithm at a disadvantage, as our Poisson relaxation
gets more accurate as $k$ grows.

#### Results.

The numerical experiments are given in Table 1. We ran Local Search, Greedy,
and our algorithm on all $9$ combinations of $n$ and $k$. We recorded the
approximate efficiency (“solution” column) and the running time of each
algorithm (if an algorithm did not terminate in $1$ week, we would stop it and
write “N/A” for the respective dataset). We measure efficiency as the relative
quality of the produced solution with respect to the solution of the best-
performing algorithm that terminated in $1$ week on that test case.

  1. (1)

As shown in Table 1, Greedy performs surprisingly well: on each generated
dataset, it produced solutions within 5% of the best-performing algorithm. It
is much better than the $(1-1/e)$-approximation guarantee for general
submodular maximization. Similar observations have been made in (Mehta et al.,
2020).

  2. (2)

Our modified algorithm produced solutions that were always within 0.1% of the
solution of the best-performing algorithm and also had very small variance.
I.e., our algorithm is effective and consistently produces good results.
Moreover, its effectiveness improves as the problem size $k$ grows, which
concurs with our theoretical analysis.

  3. (3)

The running time is the most crucial parameter in the context of BSP, as the
optimization algorithm must stop within strict time limits and approximate
efficiency is only a secondary objective. According to Table 1, the running
time of our algorithm scales much slower than that of Greedy and Local Search
with $n$ and $k$. The time complexities of Greedy and one iteration of Local
Search are both $O(nk^{3}\cdot|\mathrm{Support}|)$. When $k$ is constant
($k=5$), this time complexity is linear in $n$, but even then our algorithm
has comparable running time and when $k=\Theta(n)$, it is much faster than the
benchmarks.

##  6\. Concluding Remarks

In this paper, we studied a more general setting of position auction than all
previous work on the Bidder Selection Problem. We proposed a new relaxation
that can be solved in time polynomial in $n$ and $k$, and the polynomial is
rather small. The proposed Poisson approximation approach is much simpler than
previous PTAS _complexity results_ for $k$-MAX or non-adaptive probing, and it
can be implemented in practice. We also did extensive numerical experiments on
inputs with practically relevant sizes and observed that our algorithm
outperforms some commonly used heuristics, such as Greedy for general
submodular maximization. Furthermore, we showed that the Poisson approximation
approach also yields good theoretical guarantees. Namely, that BSP becomes
solvable in polynomial time for any fixed $\varepsilon$, when the problem size
$k$ grows. Our algorithm is the first one with a nearly perfect efficiency
guarantee of PTAS, that is relevant in the application domain of the BSP and
can be used by a company. Indeed, all previous PTASes had enormous running
times and high implementation complexities that made them completely
irrelevant to the problem, which was motivated by getting a speedup of $n/k$
magnitude.

A natural next step would be to consider BSP of various auction environments
under richer sets of feasibility constraints such as matroid, matching, and
intersection of matroids. Another interesting direction is to identify
conditions where it is possible to efficiently optimize the revenue of BSP for
VCG/GSP auction formats.

## References

  * (1)
  * ApS (2022) MOSEK ApS. 2022\.  _The MOSEK optimization toolbox for MATLAB manual. Version 10.0._ MOSEK.  http://docs.mosek.com/10.0/toolbox/index.html
  * Bansal and Sviridenko (2006) Nikhil Bansal and Maxim Sviridenko. 2006.  The Santa Claus Problem. In _Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006_ (Seattle, WA, USA) _(STOC ’06)_. Association for Computing Machinery, New York, NY, USA, 31–40.  https://doi.org/10.1145/1132516.1132522
  * Bei et al. (2023) Xiaohui Bei, Nick Gravin, Pinyan Lu, and Zhihao Gavin Tang. 2023\.  Bidder Subset Selection Problem in Auction Design. In _Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023_ , Nikhil Bansal and Viswanath Nagarajan (Eds.). SIAM, 3788–3801.  https://doi.org/10.1137/1.9781611977554.ch147
  * Bhalgat and Khanna (2014) Anand Bhalgat and Sanjeev Khanna. 2014.  A Utility Equivalence Theorem for Concave Functions. In _Integer Programming and Combinatorial Optimization_ , Jon Lee and Jens Vygen (Eds.). Springer International Publishing, Cham, 126–137.
  * Broder et al. (2003) Andrei Z. Broder, David Carmel, Michael Herscovici, Aya Soffer, and Jason Zien. 2003.  Efficient Query Evaluation Using a Two-Level Retrieval Process. In _Proceedings of the Twelfth International Conference on Information and Knowledge Management_ (New Orleans, LA, USA) _(CIKM ’03)_. Association for Computing Machinery, New York, NY, USA, 426–434.  https://doi.org/10.1145/956863.956944
  * Chen et al. (2016) Wei Chen, Wei Hu, Fu Li, Jian Li, Yu Liu, and Pinyan Lu. 2016.  Combinatorial Multi-Armed Bandit with General Reward Functions. In _Advances in Neural Information Processing Systems_ , Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett (Eds.), Vol. 29. Curran Associates Inc., Red Hook, NY, USA, 1651–1659.  https://proceedings.neurips.cc/paper/2016/hash/aa169b49b583a2b5af89203c2b78c67c-Abstract.html
  * Daley and Vere-Jones (2008) D. J. Daley and D. Vere-Jones. 2008.  _An introduction to the theory of point processes. Vol. II: General Theory and Structure_ (second ed.).  Springer, New York.  https://link.springer.com/book/10.1007/978-0-387-49835-5
  * Edelman et al. (2007) Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. 2007\.  Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords.  _American Economic Review_ 97, 1 (March 2007), 242–259.  https://doi.org/10.1257/aer.97.1.242
  * Goel et al. (2010) Ashish Goel, Sudipto Guha, and Kamesh Munagala. 2010\.  How to probe for an extreme value.  _ACM Trans. Algorithms_ 7, 1 (2010), 12:1–12:20.  https://doi.org/10.1145/1868237.1868250
  * Goel et al. (2023) Gagan Goel, Renato Paes Leme, Jon Schneider, David Thompson, and Hanrui Zhang. 2023\.  Eligibility Mechanisms: Auctions Meet Information Retrieval. In _Proceedings of the ACM Web Conference 2023_ (Austin, TX, USA) _(WWW ’23)_. Association for Computing Machinery, New York, NY, USA, 3541–3549.  https://doi.org/10.1145/3543507.3583478
  * Gurobi Optimization, LLC (2023) Gurobi Optimization, LLC. 2023\.  Gurobi Optimizer Reference Manual.
  * Hartline ([n. d.]) Jason Hartline. [n. d.].  Mechanism Design and Approximation.  http://jasonhartline.com/MDnA/.  Accessed: 2022-01-10.
  * Jeunen et al. (2023) Olivier Jeunen, Sean Murphy, and Ben Allison. 2023\.  Off-Policy Learning-to-Bid with AuctionGym. In _Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_. 4219–4228.
  * Kleinberg and Raghu (2018) Jon Kleinberg and Maithra Raghu. 2018.  Team Performance with Test Scores.  _ACM Trans. Econ. Comput._ 6, 3–4, Article 17 (oct 2018), 26 pages.  https://doi.org/10.1145/3274644
  * Li and Deshpande (2019) Jian Li and Amol Deshpande. 2019.  Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems.  _Mathematics of Operations Research_ 44, 1 (February 2019), 354–375.  https://doi.org/10.1287/moor.2017.0927
  * Li and Yuan (2013) Jian Li and Wen Yuan. 2013\.  Stochastic Combinatorial Optimization via Poisson Approximation. In _Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing_ (Palo Alto, California, USA) _(STOC ’13)_. Association for Computing Machinery, New York, NY, USA, 971–980.  https://doi.org/10.1145/2488608.2488731
  * Mehta et al. (2020) Aranyak Mehta, Uri Nadav, Alexandros Psomas, and Aviad Rubinstein. 2020.  Hitting the high notes: Subset selection for maximizing expected order statistics.  _Advances in Neural Information Processing Systems_ 33 (2020), 15800–15810.
  * Novak (2011) S.Y. Novak. 2011\.  _Extreme Value Methods with Applications to Finance_.  CRC Press, Boca Raton.
  * Novak (2019) S. Y. Novak. 2019\.  Poisson approximation.  _Probability Surveys_ 16 (2019), 228 – 276.  https://doi.org/10.1214/18-PS318
  * Procaccia et al. (2012) Ariel D. Procaccia, Sashank Jakkam Reddi, and Nisarg Shah. 2012\.  A Maximum Likelihood Approach For Selecting Sets of Alternatives. In _Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence, Catalina Island, CA, USA, August 14-18, 2012_ , Nando de Freitas and Kevin P. Murphy (Eds.). AUAI Press, Corvallis, Oregon, 695–704.  https://dslpitt.org/uai/displayArticleDetails.jsp?mmnu=1&smnu=2&article_id=2333&proceeding_id=28
  * Rong and Lu (2007) Zhou Rong and Zhixue Lu. 2007.  Two-stage procurement auction with bidders of asymmetric capacity.  _Systems Engineering-Theory & Practice_ 27, 12 (2007), 36–41.
  * Segev and Singla (2021) Danny Segev and Sahil Singla. 2021.  Efficient Approximation Schemes for Stochastic Probing and Prophet Problems. In _EC ’21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021_ , Péter Biró, Shuchi Chawla, and Federico Echenique (Eds.). ACM, New York, NY, USA, 793–794.  https://doi.org/10.1145/3465456.3467614
  * Tan (1992) Guofu Tan. 1992\.  Entry and R & D in procurement contracting.  _Journal of Economic Theory_ 58, 1 (1992), 41–60.
  * Varian (2007) Hal Varian. 2007\.  Position auctions.  _International Journal of Industrial Organization_ 25, 6 (2007), 1163–1178.  https://EconPapers.repec.org/RePEc:eee:indorg:v:25:y:2007:i:6:p:1163-1178
  * Varian and Harris (2014) Hal R. Varian and Christopher Harris. 2014.  The VCG Auction in Theory and Practice.  _American Economic Review_ 104, 5 (May 2014), 442–45.  https://doi.org/10.1257/aer.104.5.442
  * Yu and Ahmed (2016) Jiajin Yu and Shabbir Ahmed. 2016.  Maximizing expected utility over a knapsack constraint.  _Operations Research Letters_ 44, 2 (2016), 180–185.

##  Appendix A Poisson and Chernoff Approximation of Bernoulli Objective

In this section, we present approximation guarantees for Bernoulli objective
term by the Poisson and Chernoff objectives. Poisson approximation is the
central idea of this paper. It is defined in Section 4 as:

$\textup{H}_{\textup{pois}}(\mathbf{q},\ell)\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\operatornamewithlimits{\mathbf{E}}\limits_{Y\sim\textup{Pois}(\sum_{i=1}^{n}q_{i})}\mathchoice{\left[\min\left(Y,\,\ell\right)\right]}{[\min\left(Y,\,\ell\right)]}{[\min\left(Y,\,\ell\right)]}{[\min\left(Y,\,\ell\right)]}.$

We also will solve a special case of fractional Bidder Selection Problem for
$\ell$-unit auction to demonstrate how Poisson approximation can be useful. In
particular, we will assume that each bidder’s value has only $\leq\delta$
probability to be nonzero. Our main goal here will be to illustrate our
approach and analysis ideas rather than to derive independent results for this
special case.

#### Approximation Guarantees.

There are many known Poisson approximation results (see, e.g., a survey
(Novak, 2019)) for the sum of independent Bernoulli random variables, e.g., in
total variation, earth mover’s, uniform (a.k.a. Kolmogorov) distances. These
are typically absolute approximation guarantees, while we need relative
approximations similar to Chernoff approximations from Lemma A.3. As our goal
is to handle small probability tail events, we assume that each bidder’s value
${v_{i}}$ has only a small probability $\delta$ to be greater than zero, i.e.,
$\forall
i\in[n],\;\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}\\!>\\!0\right]}{[{v_{i}}\\!>\\!0]}{[{v_{i}}\\!>\\!0]}{[{v_{i}}\\!>\\!0]}\leq\delta$.
The following Poisson absolute approximation result will be useful to us:

###### Lemma A.1 ((Daley and Vere-Jones, 2008, Lemma 11.3.V, p. 162)).

Let $(z_{i}\sim\textup{Ber}(q_{i}))_{i=1}^{n}$ be $n$ independent Bernoulli
random variables with $q_{i}\leq\delta$ for $\forall i\in[n]$. Let
$Z\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\sum_{i=1}^{n}z_{i}$ and
$Y\sim\textup{Pois}(\lambda)$, where
$\lambda\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\sum_{i=1}^{n}q_{i}$.
Then

(10) $\displaystyle\textup{(total variation
distance)}\quad\sum_{j=0}^{\infty}\left\lvert\mathop{\mathbf{Pr}}[Z=j]-\mathop{\mathbf{Pr}}[Y=j]\right\rvert\leq\delta.$

With Lemma A.1 we can derive relative approximations:

###### Lemma A.2.

Suppose $\mathbf{q}\in[0,\delta]^{n}$ and $\ell\in{\mathbb{N}}$. Then

(a)
$\displaystyle\left\lvert\textup{H}_{\textup{ber}}(\mathbf{q},\ell)-\textup{H}_{\textup{pois}}(\mathbf{q},\ell)\right\rvert\leq
17.5\cdot\delta\cdot\textup{H}_{\textup{ber}}(\mathbf{q},\ell)$
$\displaystyle(\forall\delta,\,\ell),$ (b) $\displaystyle
0\leq\textup{H}_{\textup{ber}}(\mathbf{q},1)-\textup{H}_{\textup{pois}}(\mathbf{q},1)\leq\delta\cdot\textup{H}_{\textup{ber}}(\mathbf{q},1)$
$\displaystyle(\ell=1).$

###### Proof.

(a). Let $z_{i}\sim\textup{Ber}(q_{i})$ be Bernoulli random variables and
$Z=\sum_{i=1}^{n}z_{i}$ be their sum. Then we can rewrite
$\textup{H}_{\textup{ber}}(\mathbf{q},\ell)=\operatorname{\mathbf{E}}\mathchoice{\left[\min(Z,\ell)\right]}{[\min(Z,\ell)]}{[\min(Z,\ell)]}{[\min(Z,\ell)]}=\sum_{j=1}^{\ell}\mathop{\mathbf{Pr}}[Z\geq
j].$ Also let $y_{i}\sim\textup{Pois}(q_{i})$ and define
$Y=\sum_{i=1}^{n}y_{i}$. Clearly, $Y\sim\textup{Pois}(\lambda)$ for
$\lambda=\sum_{i=1}^{n}q_{i}$. Then
$\textup{H}_{\textup{pois}}(\mathbf{q},\ell)=\operatorname{\mathbf{E}}\mathchoice{\left[\min(Y,\ell)\right]}{[\min(Y,\ell)]}{[\min(Y,\ell)]}{[\min(Y,\ell)]}=\sum_{j=1}^{\ell}\mathop{\mathbf{Pr}}[Y\geq
j].$ Hence, we have

$\left\lvert\textup{H}_{\textup{ber}}(\mathbf{q},\ell)-\textup{H}_{\textup{pois}}(\mathbf{q},\ell)\right\rvert\leq\sum_{j=1}^{\ell}\left\lvert\mathop{\mathbf{Pr}}[Z\geq
j]-\mathop{\mathbf{Pr}}[Y\geq j]\right\rvert.$

The RHS is similar to the earth mover’s distance between the sum of Bernoulli
and Poisson random variables (the difference is that the summation instead of
$+\infty$ goes only up to $\ell$). Next, we shall prove the following
inequality:

$\sum_{j=1}^{\ell}\left\lvert\mathop{\mathbf{Pr}}[Z\geq
j]-\mathop{\mathbf{Pr}}[Y\geq j]\right\rvert\leq
2.5\,\delta\cdot\min(\lambda,\ell),$

which together with Lemma A.3 (a) immediately implies the desired result:

$\left\lvert\textup{H}_{\textup{ber}}(\mathbf{q},\ell)-\textup{H}_{\textup{pois}}(\mathbf{q},\ell)\right\rvert\leq
2.5\,\delta\cdot\min(\lambda,\ell)\leq 2.5\,\delta\cdot
7\,\textup{H}_{\textup{ber}}(\mathbf{q},\ell)=17.5\,\delta\cdot\textup{H}_{\textup{ber}}(\mathbf{q},\ell).$

We consider two cases. First, when $\lambda\geq\ell$. Then for any
$j\in{\mathbb{N}}^{+}$ we have by (10)

$\displaystyle\sum_{j=1}^{\ell}\left\lvert\mathop{\mathbf{Pr}}[Z\geq
j]-\mathop{\mathbf{Pr}}[Y\geq
j]\right\rvert\leq\ell\cdot\sum_{j^{\prime}=0}^{\infty}\left\lvert\mathop{\mathbf{Pr}}[Z=j^{\prime}]-\mathop{\mathbf{Pr}}[Y=j^{\prime}]\right\rvert\leq\ell\cdot\delta=\delta\cdot\min(\lambda,\ell).$

Second, when $\min(\lambda,\,\ell)=\lambda<\ell$, we use instead the earth
mover’s distance
$d_{\textup{G}}(Z,Y)=\sum_{j=0}^{+\infty}\left\lvert\mathop{\mathbf{Pr}}[Z\geq
j]-\mathop{\mathbf{Pr}}[Y\geq j]\right\rvert$. We do not calculate the
cumulative density functions of $Z=\sum_{i}^{n}z_{i}$ and
$Y=\sum_{i}^{n}y_{i}$, but get an upper bound by coupling individual $z_{i}$
and $y_{i}$. Specifically, we couple $z_{i}$ and $y_{i}$ so that $z_{i}=0$
implies $y_{i}=0$ (note that
$\mathop{\mathbf{Pr}}[z_{i}=0]=1-q_{i}\leq\mathop{\mathbf{Pr}}[y_{i}=0]=e^{-q_{i}}$).
Conversely, if $z_{i}=1$ it is matched with all $y_{i}=1,2,\ldots$ and the
remaining probability for $y_{i}=0$. Then we have

$\displaystyle
d_{\textup{G}}(Z,Y)\leq\operatornamewithlimits{\mathbf{E}}\limits_{(z_{i},y_{i})_{i=1}^{n}}\mathchoice{\left[|Z-Y|\right]}{[|Z-Y|]}{[|Z-Y|]}{[|Z-Y|]}\leq\sum_{i=1}^{n}\operatornamewithlimits{\mathbf{E}}\limits_{(z_{i},y_{i})}\mathchoice{\left[\left\lvert
z_{i}-y_{i}\right\rvert\right]}{[\left\lvert
z_{i}-y_{i}\right\rvert]}{[\left\lvert z_{i}-y_{i}\right\rvert]}{[\left\lvert
z_{i}-y_{i}\right\rvert]}.$

Since $z_{i}=0$ is matched to $y_{i}=0$, we get the following expression for
the term
$\operatorname{\mathbf{E}}\mathchoice{\left[|z_{i}-y_{i}|\right]}{[|z_{i}-y_{i}|]}{[|z_{i}-y_{i}|]}{[|z_{i}-y_{i}|]}$,

$\displaystyle\operatornamewithlimits{\mathbf{E}}\limits_{(z_{i},y_{i})}\mathchoice{\left[\left\lvert
z_{i}-y_{i}\right\rvert\right]}{[\left\lvert
z_{i}-y_{i}\right\rvert]}{[\left\lvert z_{i}-y_{i}\right\rvert]}{[\left\lvert
z_{i}-y_{i}\right\rvert]}$
$\displaystyle=\sum_{j=0}^{+\infty}\operatornamewithlimits{\mathbf{Pr}}\limits_{(z_{i},y_{i})}\mathchoice{\left[z_{i}=1\land
y_{i}=j\right]}{[z_{i}=1\land y_{i}=j]}{[z_{i}=1\land y_{i}=j]}{[z_{i}=1\land
y_{i}=j]}\cdot\left\lvert j-1\right\rvert$
$\displaystyle=\operatornamewithlimits{\mathbf{Pr}}\limits_{(z_{i},y_{i})}\mathchoice{\left[z_{i}=1\land
y_{i}=0\right]}{[z_{i}=1\land y_{i}=0]}{[z_{i}=1\land y_{i}=0]}{[z_{i}=1\land
y_{i}=0]}+\sum_{j=2}^{+\infty}\operatornamewithlimits{\mathbf{Pr}}\limits_{y_{i}}\mathchoice{\left[y_{i}=j\right]}{[y_{i}=j]}{[y_{i}=j]}{[y_{i}=j]}\cdot(j-1)$
$\displaystyle\leq\frac{q_{i}^{2}}{2}+q_{i}^{2}\sum_{j=2}^{+\infty}2^{-(j-1)}(j-1)\leq
2.5\,q_{i}^{2},$

where the first inequality holds, since
$\operatorname{\mathbf{Pr}}\mathchoice{\left[z_{i}=1\land
y_{i}=0\right]}{[z_{i}=1\land y_{i}=0]}{[z_{i}=1\land y_{i}=0]}{[z_{i}=1\land
y_{i}=0]}=(\operatorname{\mathbf{Pr}}\mathchoice{\left[y_{i}=0\right]}{[y_{i}=0]}{[y_{i}=0]}{[y_{i}=0]}-\operatorname{\mathbf{Pr}}\mathchoice{\left[z_{i}=0\right]}{[z_{i}=0]}{[z_{i}=0]}{[z_{i}=0]})=e^{-q_{i}}-1+q_{i}\leq
q_{i}^{2}/2$ and
$\operatorname{\mathbf{Pr}}\mathchoice{\left[y_{i}=j\right]}{[y_{i}=j]}{[y_{i}=j]}{[y_{i}=j]}=e^{-q_{i}}q_{i}^{j}/j!\leq
q_{i}^{2}/2^{j-1}$ for $j\geq 2$. Therefore,

$\sum_{j=1}^{\ell}\left\lvert\mathop{\mathbf{Pr}}[Z\geq
j]-\mathop{\mathbf{Pr}}[Y\geq j]\right\rvert\leq
d_{\textup{G}}(Z,Y)\leq\sum_{i=1}^{n}2.5\,q_{i}^{2}\leq
2.5\cdot\delta\cdot\sum_{i=1}^{n}q_{i}=2.5\cdot\delta\cdot\min(\lambda,\,\ell),$

which concludes the proof.

(b). As $\ell=1$,
$\textup{H}_{\textup{ber}}(\mathbf{q},1)=1-\prod_{i=1}^{n}(1-q_{i})\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}1-e^{-s},$
where $s=-\sum_{i=1}^{n}\ln(1-q_{i})$. Let $\lambda=\sum_{i=1}^{n}q_{i}$, then
$\textup{H}_{\textup{pois}}(\mathbf{q},1)=1-e^{-\lambda}$. Observe that
$q_{i}\leq-\ln(1-q_{i})\leq\frac{q_{i}}{1-q_{i}}\leq\frac{q_{i}}{1-\delta}.$
Thus $\lambda\leq s\leq\frac{\lambda}{1-\delta}$. The former inequality
implies the desired lower bound
$\textup{H}_{\textup{ber}}(\mathbf{q},1)-\textup{H}_{\textup{pois}}(\mathbf{q},1)\geq
0$.

To prove the required upper bound, observe that
$\textup{H}_{\textup{ber}}(\mathbf{q},1)=f(s)$,
$\textup{H}_{\textup{pois}}(\mathbf{q},1)=f(\lambda)$ for $f(t)=1-e^{-t}$. As
$f(t)$ is a concave function with $f(0)=0$, we have $f(\lambda)\geq
f(s)\cdot\frac{\lambda}{s}\geq f(s)\cdot(1-\delta)$. Thus
$\textup{H}_{\textup{ber}}(\mathbf{q},1)-\textup{H}_{\textup{pois}}(\mathbf{q},1)=f(s)-f(\lambda)\leq\delta\cdot
f(s)=\delta\cdot\textup{H}_{\textup{ber}}(\mathbf{q},1)$, which concludes the
proof. ∎

#### Algorithm for Small Tail Probabilities.

Assume that each bidder’s value ${v_{i}}$ has at most $\delta$ probability to
be greater than zero. Then Lemma A.2 and 4.2 (Concavity of Poisson) suggest
Appendix A.

Algorithm 0 Approximation to Fractional BSP for Tail Probabilities $\ell$-unit
Auctions. Return the optimal solution $\widetilde{\mathbf{x}}^{*}$ to the
concave program:
$\begin{array}[]{lll}\text{Maximize}&\widetilde{\textup{{SW}}}(\mathbf{x},\ell)\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\int_{0}^{+\infty}\textup{H}_{\textup{pois}}(\mathbf{q}(\mathbf{x},\tau),\ell)\,\mathrm{d}\tau\\\
\text{Subject To}&\sum_{i=1}^{n}{x_{i}}\leq k,\quad{x_{i}}\in[0,1],\forall
i\in\\{1,2,\dots,n\\}.\end{array}$

We can solve the above program efficiently via standard concave function
maximization methods, as the objective $\widetilde{\textup{{SW}}}$ is concave
in $\mathbf{x}$. Indeed, from 4.2 we know that
$\textup{H}_{\textup{pois}}(\mathbf{q},\ell)$ is concave in $\mathbf{q}$ and,
since $\mathbf{q}(\mathbf{x},\tau)$ is linear in $\mathbf{x}$ for every fixed
$\tau$, $\textup{H}_{\textup{pois}}$ is also concave in $\mathbf{x}$. As
$\widetilde{\textup{{SW}}}(\mathbf{x},\ell)$ is an integral (non-negative
linear combination) of
$\textup{H}_{\textup{pois}}(\mathbf{q}(\mathbf{x},\tau),\ell)$,
$\widetilde{\textup{{SW}}}$ is concave in $\mathbf{x}$.

From Lemma A.2, we obtain the following approximation guarantees of
$\textup{{SW}}(\mathbf{x},\ell)$ by
$\widetilde{\textup{{SW}}}(\mathbf{x},\ell)$.

$\displaystyle\left\lvert\textup{{SW}}(\mathbf{x},\ell)-\widetilde{\textup{{SW}}}(\mathbf{x},\ell)\right\rvert$
$\displaystyle\leq\int_{0}^{+\infty}\left\lvert\textup{H}_{\textup{ber}}(\mathbf{q}(\mathbf{x},\tau),\ell)-\textup{H}_{\textup{pois}}(\mathbf{q}(\mathbf{x},\tau),\ell)\right\rvert\,\mathrm{d}\tau$
(11) $\displaystyle\leq 17.5\,\delta\cdot\textup{{SW}}(\mathbf{x},\ell).$

Let $\mathbf{x}^{*}$ be the best solution of the original problem (3). We have

$\displaystyle\textup{{SW}}(\widetilde{\mathbf{x}}^{*},\ell)$
$\displaystyle\geq\widetilde{\textup{{SW}}}(\widetilde{\mathbf{x}}^{*},\ell)-17.5\,\delta\,\cdot\,\textup{{SW}}(\widetilde{\mathbf{x}}^{*},\ell)$
$\displaystyle\geq\widetilde{\textup{{SW}}}(\mathbf{x}^{*},\ell)-{}17.5\,\delta\,\cdot\,\textup{{SW}}(\mathbf{x}^{*},\ell)\geq\left(1-35\,\delta\right)\textup{{SW}}(\mathbf{x}^{*},\ell).$

Hence, Appendix A is $(1-35\,\delta)$-approximation.

#### Chernoff Approximation Guarantees.

We recall the following definitions

$\displaystyle\textup{H}_{\textup{ber}}(\mathbf{q},\ell)=\operatornamewithlimits{\mathbf{E}}\limits_{\mathbf{z}\sim\textup{Ber}(\mathbf{q})}\mathchoice{\left[\min\left(\sum_{i=1}^{n}{z_{i}},\,\ell\right)\right]}{[\min\left(\sum_{i=1}^{n}{z_{i}},\,\ell\right)]}{[\min\left(\sum_{i=1}^{n}{z_{i}},\,\ell\right)]}{[\min\left(\sum_{i=1}^{n}{z_{i}},\,\ell\right)]},\qquad\textup{H}_{\textup{cher}}(\mathbf{q},\ell)=\min\left(\sum_{i=1}^{n}q_{i},\,\ell\right).$

Our main algorithm needs the following approximation guarantee of
$\textup{H}_{\textup{cher}}$:

###### Lemma A.3.

For all $\mathbf{q}\in[0,1]^{n},\ell\in\mathbb{N}^{+}$, let
$\lambda=\sum_{i=1}^{n}q_{i}$, the following properties hold.

(a)
$\displaystyle\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq\textup{H}_{\textup{cher}}(\mathbf{q},\ell)\leq
7\cdot\textup{H}_{\textup{ber}}(\mathbf{q},\ell).$ (b)
$\displaystyle\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq\frac{3}{\sqrt{\lambda}}\cdot\textup{H}_{\textup{cher}}(\mathbf{q},\ell)\leq\frac{21}{\sqrt{\lambda}}\cdot\textup{H}_{\textup{ber}}(\mathbf{q},\ell).$
(c)
$\displaystyle\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq\frac{5}{\sqrt{\ell}}\cdot\textup{H}_{\textup{cher}}(\mathbf{q},\ell)\leq\frac{35}{\sqrt{\ell}}\cdot\textup{H}_{\textup{ber}}(\mathbf{q},\ell).$

In order to prove Lemma A.3, we first prove the following two auxiliary
lemmas.

###### Lemma A.4.

For all $\mathbf{q}\in[0,1]^{n},\,\ell\in\mathbb{N}^{+}$, let
$\lambda=\sum_{i=1}^{n}q_{i}$, the following properties hold.

  1. (a)

$\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\geq\lambda(1-\frac{1}{2}\lambda)$.

  2. (b)

If $\lambda\geq 1$,
$\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\geq\frac{1}{2}$.

  3. (c)

If $\ell\geq\lambda$, then
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq\displaystyle\sum\limits_{i=\ell+1}^{n}e^{-\frac{\delta^{2}(i)}{2+\delta(i)}\cdot\lambda}$,
where $\delta(i)=\frac{i-\lambda}{\lambda}$.

  4. (d)

If $\ell\geq\lambda$ and $\alpha\in(0,1)$, then
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq\alpha\lambda+\frac{6}{\alpha}e^{-\alpha^{2}\cdot\frac{\lambda}{3}}.$

  5. (e)

If $\lambda\geq\ell$, then
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq\displaystyle\sum\limits_{i=0}^{\ell-1}e^{-\frac{(\lambda-i)^{2}}{2\lambda}}$.

  6. (f)

If $\lambda\geq\ell$ and $\alpha\in(0,1)$, then
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq\alpha\lambda+\frac{4}{\alpha}e^{-\alpha^{2}\cdot\frac{\lambda}{2}}.$

###### Proof of Lemma A.4.

(a). Since $\ell\geq 1$, We have the following lower bound on
$\textup{H}_{\textup{ber}}(\mathbf{q},\ell)$

$\displaystyle\textup{H}_{\textup{ber}}(\mathbf{q},\ell)$
$\displaystyle\geq\operatornamewithlimits{\mathbf{Pr}}\limits_{\begin{subarray}{c}\mathbf{z}\sim\textup{Ber}(\mathbf{q})\\\
Z=\sum_{i=1}^{n}z_{i}\end{subarray}}\mathchoice{\left[Z\geq 1\right]}{[Z\geq
1]}{[Z\geq 1]}{[Z\geq
1]}=\sum_{i=1}^{n}\operatornamewithlimits{\mathbf{Pr}}\limits_{{z_{i}}\sim\textup{Ber}(q_{i})}\mathchoice{\left[{z_{i}}=1\right]}{[{z_{i}}=1]}{[{z_{i}}=1]}{[{z_{i}}=1]}\cdot\operatornamewithlimits{\mathbf{Pr}}\limits_{\mathbf{z}\sim\textup{Ber}(\mathbf{q})}\mathchoice{\left[\forall
j<i,\;{z_{j}}=0\right]}{[\forall j<i,\;{z_{j}}=0]}{[\forall
j<i,\;{z_{j}}=0]}{[\forall j<i,\;{z_{j}}=0]}$
$\displaystyle\geq\sum_{i=1}^{n}q_{i}\cdot\left(1-\sum_{j=1}^{i-1}q_{j}\right)=\sum_{i=1}^{n}q_{i}-\sum_{j<i}q_{i}q_{j}\geq\lambda\left(1-\frac{1}{2}\lambda\right).$

(b). If $\lambda\geq 1$, there exists $\mathbf{q}^{\prime}\in[0,1]^{n}$ such
that $q_{i}^{\prime}\leq q_{i},\,\forall i\in\\{1,2,\dots,n\\}$ and
$\sum_{i=1}^{n}q_{i}^{\prime}=1$. Using Lemma A.4 (a), we can see that
$\textup{H}_{\textup{ber}}(\mathbf{q}^{\prime},\ell)\geq 0.5$. Then
$\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\geq\textup{H}_{\textup{ber}}(\mathbf{q}^{\prime},\ell)\geq
0.5.$

(c). As $\ell\geq\lambda$, we have
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)=\lambda$. Then

$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)=\operatornamewithlimits{\mathbf{E}}\limits_{\begin{subarray}{c}\mathbf{z}\sim\textup{Ber}(\mathbf{q})\\\
Z=\sum_{i=1}^{n}z_{i}\end{subarray}}\mathchoice{\left[Z-\min\\{Z,\,\ell\\}\right]}{[Z-\min\\{Z,\,\ell\\}]}{[Z-\min\\{Z,\,\ell\\}]}{[Z-\min\\{Z,\,\ell\\}]}=\sum_{i=\ell+1}^{n}\operatornamewithlimits{\mathbf{Pr}}\limits_{\begin{subarray}{c}\mathbf{z}\sim\textup{Ber}(\mathbf{q})\\\
Z=\sum_{i=1}^{n}z_{i}\end{subarray}}\mathchoice{\left[Z\geq i\right]}{[Z\geq
i]}{[Z\geq i]}{[Z\geq i]}.$

We apply Chernoff bound to each tail probability $Z\geq i$ under the sum. Thus

$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq\sum_{i=\ell+1}^{n}e^{-\frac{\delta^{2}(i)}{2+\delta(i)}\cdot\lambda},\quad\text{where
}\delta(i)=\frac{i-\lambda}{\lambda}$

(d). By Lemma A.4 (c)

$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq\sum_{i=\lceil\lambda+1\rceil}^{\infty}e^{-\frac{\delta^{2}(i)}{2+\delta(i)}\cdot\lambda}\leq\alpha\lambda+\sum_{i=\lceil(1+\alpha)\lambda\rceil}^{\infty}e^{-\frac{\delta^{2}(i)}{2+\delta(i)}\cdot\lambda}.$

Note that inside the last summation, $\delta(i)\geq\alpha$ and
$\frac{\delta(i)}{2+\delta(i)}\geq\frac{\alpha}{2+\alpha}\geq\frac{\alpha}{3}$.
Therefore,

$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq\alpha\lambda+\sum_{i=\lceil(1+\alpha)\lambda\rceil}^{\infty}e^{-\frac{\alpha}{2+\alpha}\cdot\delta(i)\lambda}\leq\alpha\lambda+\sum_{i=\lceil(1+\alpha)\lambda\rceil}^{\infty}e^{-(i-\lambda)\cdot\frac{\alpha}{3}}.$

As the summation in the right hand side becomes a geometric series, we get

$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq\alpha\lambda+e^{-\alpha^{2}\cdot\frac{\lambda}{3}}\cdot(1-e^{-\frac{\alpha}{3}})^{-1}\leq\alpha\lambda+\frac{6}{\alpha}e^{-\alpha^{2}\cdot\frac{\lambda}{3}}.$

The last inequality holds as $1-e^{-x}\geq x/2$ for $x\in[0,1]$. Hence, Lemma
A.4 (d) holds.

(e). If $\ell\leq\lambda$, then
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)=\ell$. We have

$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)=\operatornamewithlimits{\mathbf{E}}\limits_{\begin{subarray}{c}\mathbf{z}\sim\textup{Ber}(\mathbf{q})\\\
Z=\sum_{i=1}^{n}z_{i}\end{subarray}}\mathchoice{\left[\ell-\min\\{Z,\,\ell\\}\right]}{[\ell-\min\\{Z,\,\ell\\}]}{[\ell-\min\\{Z,\,\ell\\}]}{[\ell-\min\\{Z,\,\ell\\}]}=\sum_{i=0}^{\ell-1}\operatornamewithlimits{\mathbf{Pr}}\limits_{\begin{subarray}{c}\mathbf{z}\sim\textup{Ber}(\mathbf{q})\\\
Z=\sum_{i=1}^{n}z_{i}\end{subarray}}\mathchoice{\left[Z\leq i\right]}{[Z\leq
i]}{[Z\leq i]}{[Z\leq i]}.$

We again apply Chernoff bound for each tail event $Z\leq i$ under summation
and get

$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq\sum_{i=0}^{\ell-1}e^{-\frac{(\lambda-i)^{2}}{2\lambda}}.$

(f). By Lemma A.4 (e), we have

$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq\sum_{i=0}^{\ell-1}e^{-\frac{(\lambda-i)^{2}}{2\lambda}}\leq\sum_{i=1}^{\infty}e^{-\frac{i^{2}}{2\lambda}}\leq\alpha\lambda+\sum_{i=\lceil\alpha\lambda\rceil}^{\infty}e^{-\frac{i^{2}}{2\lambda}}\leq\alpha\lambda+\sum_{i=\lceil\alpha\lambda\rceil}^{\infty}e^{-i\cdot\frac{\alpha}{2}}.$

The summation in the right hand side is again a geometric series, which allows
us to get

$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq\alpha\lambda+e^{-\alpha^{2}\cdot\frac{\lambda}{2}}\cdot(1-e^{-\frac{\alpha}{2}})^{-1}\leq\alpha\lambda+\frac{4}{\alpha}e^{-\alpha^{2}\cdot\frac{\lambda}{2}}.$

Hence Lemma A.4 (f) holds. ∎

###### Claim A.5.

For any $\alpha\geq 3.4$,
$\sum\limits_{i=1}^{\infty}e^{-\frac{i^{2}}{2\alpha+i}}\leq 0.85\alpha.$

###### Proof.

When $\alpha,x>0$, the function $-\frac{x^{2}}{2\alpha+x}$ is decreasing in
$x$. Therefore,

$\sum_{x=1}^{\infty}e^{-\frac{x^{2}}{2\alpha+x}}\leq\int_{y=0}^{+\infty}e^{-\frac{y^{2}}{2\alpha+y}}\mathrm{d}y\\\
\overset{[y=\alpha\cdot z]}{=}\alpha\cdot\int_{z=0}^{+\infty}e^{-\frac{\alpha
z^{2}}{2+z}}\mathrm{d}z\leq\alpha\cdot\int_{z=0}^{+\infty}e^{-\frac{3.4z^{2}}{2+z}}\mathrm{d}z\leq\alpha\cdot
0.85.\qed$

Now we are ready to prove Lemma A.3.

See A.3

###### Proof of Lemma A.3.

(a). As $\min\\{\,t,\ell\\}$ is a concave function in $t$, the Jensen
inequality gives us

$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)=\min\Big{\\{}\operatornamewithlimits{\mathbf{E}}\limits_{\begin{subarray}{c}\mathbf{z}\sim\textup{Ber}(\mathbf{q})\\\
Z=\sum_{i=1}^{n}z_{i}\end{subarray}}\mathchoice{\left[Z\right]}{[Z]}{[Z]}{[Z]},\;\ell\;\Big{\\}}\geq\operatornamewithlimits{\mathbf{E}}\limits_{\begin{subarray}{c}\mathbf{z}\sim\textup{Ber}(\mathbf{q})\\\
Z=\sum_{i=1}^{n}z_{i}\end{subarray}}\mathchoice{\left[\min\left\\{Z,\,\ell\right\\}\right]}{[\min\left\\{Z,\,\ell\right\\}]}{[\min\left\\{Z,\,\ell\right\\}]}{[\min\left\\{Z,\,\ell\right\\}]}=\textup{H}_{\textup{ber}}(\mathbf{q},\ell),$

which gives the first inequality. To prove the second inequality we consider
the following 4 cases:

  * •

If $\lambda\leq 1$, we use Lemma A.4 (a) to get
$\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\geq\lambda\left(1-\frac{1}{2}\lambda\right)\geq\frac{1}{2}\lambda\geq\frac{1}{2}\cdot\textup{H}_{\textup{cher}}(\mathbf{q},\ell).$

  * •

If $\lambda>1$ and $\min(\lambda,\ell)\leq 3.5$, then Lemma A.4 (b) gives us
$\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\geq\frac{1}{2}\geq\frac{1}{7}\cdot\min(\lambda,\ell)=\frac{1}{7}\cdot\textup{H}_{\textup{cher}}(\mathbf{q},\ell).$

  * •

If $\min(\lambda,\ell)>3.5$ and $\ell\geq\lambda$, then Lemma A.4 (c) gives us

$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq\sum\limits_{i=\ell+1}^{n}e^{-\frac{\delta^{2}(i)}{2+\delta(i)}\cdot\lambda}\leq\sum_{i=\lceil\lambda+1\rceil}^{\infty}e^{-\frac{(i-\lambda)^{2}}{2\lambda+(i-\lambda)}}\leq\sum_{i=1}^{\infty}e^{-\frac{i^{2}}{2\lambda+i}}.$

We apply A.5 for $\alpha=\lambda$ and get
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq
0.85\lambda,$ which implies that
$\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\geq
0.15\cdot\textup{H}_{\textup{cher}}(\mathbf{q},\ell)$ for
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)=\lambda\leq\ell$.

  * •

If $\min(\lambda,\ell)>3.5$ and $\lambda\geq\ell$, then Lemma A.4 (e) gives us
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq\sum\limits_{i=0}^{\ell-1}e^{-\frac{1}{2\lambda}(\lambda-i)^{2}}$.
Note that $\frac{1}{2\lambda}(\lambda-i)^{2}\geq\frac{1}{2\ell}(\ell-i)^{2}$,
when $\lambda\geq\ell\geq i$. Thus

$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq\sum_{i=0}^{\ell-1}e^{-\frac{1}{2\ell}(\ell-i)^{2}}\leq\sum_{i=1}^{\infty}e^{-\frac{i^{2}}{2\ell}}\leq\sum_{i=1}^{\infty}e^{-\frac{i^{2}}{2\ell+i}}.$

By applying A.5 with $\alpha=\ell$, we get
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq
0.85\ell,$ which implies that $\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\geq
0.15\cdot\textup{H}_{\textup{cher}}(\mathbf{q},\ell),$ as
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)=\ell\leq\lambda$.

In all 4 cases,
$7\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\geq\textup{H}_{\textup{cher}}(\mathbf{q},\ell)$.

(b). Let
$\varepsilon\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\frac{1}{\sqrt{\lambda}}$.
We consider three cases to show that
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq
3\varepsilon\cdot\textup{H}_{\textup{cher}}(\mathbf{q},\ell)$, then combine it
with the inequality
$7\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\geq\textup{H}_{\textup{cher}}(\mathbf{q},\ell)$
from Lemma A.3 (a) to conclude the proof. Without loss of generality, we may
assume that $\varepsilon<1/3$.

  * •

If $\ell\geq\lambda$, then Lemma A.4 (d) for $\alpha=1.8\varepsilon$, gives us
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq
2.94\varepsilon\lambda=2.94\varepsilon\cdot\textup{H}_{\textup{cher}}(\mathbf{q},\ell).$

  * •

If $\ell\leq\frac{3}{4}\lambda$, then by Lemma A.4 (e) we have

$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq\sum\limits_{i=0}^{\ell-1}e^{-\frac{(\lambda-i)^{2}}{2\lambda}}\leq\ell\cdot
e^{-\frac{\lambda}{32}}\leq\frac{4e^{-1/2}}{\sqrt{\lambda}}\cdot\textup{H}_{\textup{cher}}(\mathbf{q},\ell)\leq
2.5\cdot\varepsilon\cdot\textup{H}_{\textup{cher}}(\mathbf{q},\ell),$

where the first inequality holds because $\lambda-i\geq\lambda/4$; the second
inequality holds, as $\textup{H}_{\textup{cher}}(\mathbf{q},\ell)=\ell$ and
$e^{-x/c}\sqrt{x}\leq e^{-1/2}\sqrt{c/2}$ for all $x,c>0$.

  * •

If $\ell\in\left(\frac{3}{4}\lambda,\lambda\right)$, by Lemma A.4 (f) for
$\alpha=1.8\varepsilon$ we have

$\displaystyle\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq
2.24\varepsilon\lambda\leq
2.99\varepsilon\ell=2.99\varepsilon\cdot\textup{H}_{\textup{cher}}(\mathbf{q},\ell).$

(c). Let
$\varepsilon\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\frac{1}{\sqrt{\ell}}$.
We first prove
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq
5\varepsilon\cdot\textup{H}_{\textup{cher}}(\mathbf{q},\ell)$ by considering
the following four cases. It implies the second bound when combined with
inequality
$7\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\geq\textup{H}_{\textup{cher}}(\mathbf{q},\ell)$
from Lemma A.3 (a). We may assume without loss of generality that
$\varepsilon<1/5$.

  * •

If $\lambda<\frac{1}{\sqrt{\ell}}$, then
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)=\lambda$ and Lemma A.4 (a) gives
us

$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq\lambda-\lambda\left(1-\frac{1}{2}\lambda\right)=\frac{\lambda^{2}}{2}<\frac{\varepsilon\lambda}{2}=\frac{\varepsilon}{2}\cdot\textup{H}_{\textup{cher}}(\mathbf{q},\ell).$

  * •

If $\lambda\in[\frac{1}{\sqrt{\ell}},\frac{\ell}{3})$, then
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)=\lambda$ and by Lemma A.4 (c) we
have

$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq\sum_{i=\ell+1}^{n}e^{-\frac{\delta^{2}(i)}{2+\delta(i)}\cdot\lambda}\leq\sum_{i=\ell+1}^{n}e^{-\delta(i)\cdot\frac{\lambda}{2}}\leq\sum_{i=\ell+1}^{+\infty}e^{-\frac{i-\lambda}{2}},$

where the second inequality holds, as $\delta(i)=\frac{i-\lambda}{\lambda}\geq
2$ for all $i\geq\ell+1$ and $\lambda<\ell/3$. Furthermore,

$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq
e^{-\frac{\ell}{3}}\cdot(1-e^{-\frac{1}{2}})^{-1}\leq\frac{3e^{-1}/\ell}{1-e^{-1/2}}\leq
2.81\cdot\varepsilon\cdot\textup{H}_{\textup{cher}}(\mathbf{q},\ell),$

where to get the first inequality we simply use the formula for the sum of
geometric progression and estimate $e^{-\frac{\ell+1-\lambda}{2}}\leq
e^{-\ell/3}$; the second inequality holds, because $e^{-x/c}\leq c\cdot
e^{-1}/x$ for any $x,c>0$; the last inequality holds, because
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)=\lambda\geq\varepsilon=1/\sqrt{\ell}$.

  * •

If $\lambda\in[\frac{\ell}{3},\ell]$, then
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)=\lambda$ and by Lemma A.4 (d) for
$\alpha=4\varepsilon$ ($\alpha<1$, since $\varepsilon\leq 1/5$) we get
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq
4\varepsilon\lambda+\frac{6}{4\varepsilon}e^{-16\varepsilon^{2}\cdot\frac{\lambda}{3}}\leq
4.77\varepsilon\lambda=4.77\varepsilon\cdot\textup{H}_{\textup{cher}}(\mathbf{q},\ell),$
where the second inequality holds, since $\ell\leq 3\lambda$ and
$\frac{6}{4\varepsilon}e^{-16\varepsilon^{2}\cdot\frac{\lambda}{3}}=\frac{3\varepsilon\ell}{2}e^{-16\cdot\frac{\lambda}{3\ell}}\leq\frac{9\varepsilon\lambda}{2}e^{-\frac{16\ell}{9\ell}}\leq
0.77\cdot\varepsilon\lambda$.

  * •

If $\lambda>\ell$, then by considering $\mathbf{q}^{\prime}$ with
$q_{i}^{\prime}\leq q_{i}$ and $\sum_{i=1}^{n}q_{i}^{\prime}=\ell$, we get
$\textup{H}_{\textup{ber}}(\mathbf{q})\geq\textup{H}_{\textup{ber}}(\mathbf{q}^{\prime})$
and
$\textup{H}_{\textup{cher}}(\mathbf{q})=\textup{H}_{\textup{cher}}(\mathbf{q}^{\prime})=\ell$.
Then according to the previous case,
$\textup{H}_{\textup{cher}}(\mathbf{q},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\leq\textup{H}_{\textup{cher}}(\mathbf{q}^{\prime},\ell)-\textup{H}_{\textup{ber}}(\mathbf{q}^{\prime},\ell)\leq
4.77\varepsilon\cdot\textup{H}_{\textup{cher}}(\mathbf{q}^{\prime},\ell)=4.77\varepsilon\cdot\textup{H}_{\textup{cher}}(\mathbf{q},\ell)$.

These bounds combined with inequality
$7\textup{H}_{\textup{ber}}(\mathbf{q},\ell)\geq\textup{H}_{\textup{cher}}(\mathbf{q},\ell)$
conclude the proof of (c). ∎

##  Appendix B Missing Proofs

###  B.1. Proof of Theorem 4.4

See 4.4

###### Proof of Theorem 4.4.

We first show that Section 4.1 is polynomial. Indeed, step (1) works in
polynomial time by 4.3. For each $\tau$ in the support of
$\\{{D_{i}}\\}_{i\in[n]}$ and $\mathbf{x}_{\scriptscriptstyle M}$ we can
efficiently calculate
$\textup{H}_{\textup{cher}}((\mathbf{x}_{\scriptscriptstyle M},$
$\mathbf{1}_{S_{\textup{fix}}}),\tau)$ and
$\textup{G}_{\textup{pois}}(\mathbf{x}_{\scriptscriptstyle M},\tau)$, which
allows us to compute $\widetilde{\textup{{SW}}}(\mathbf{x}_{\scriptscriptstyle
M})$ in polynomial time. It is easy to see that
$\widetilde{\textup{{SW}}}(\mathbf{x}_{\scriptscriptstyle M})$ is a concave
function in $\mathbf{x}_{\scriptscriptstyle M}$, as
$\textup{G}_{\textup{pois}}$ is a non-negative linear combination of constant
terms and concave functions
$\textup{H}_{\textup{pois}}(\mathbf{x}_{\scriptscriptstyle
M},\,\ell\\!-\\!j,\,\tau)$, and $\textup{H}_{\textup{cher}}$ is a non-negative
linear combination of concave functions
$\textup{H}_{\textup{cher}}(\mathbf{q}(\mathbf{x},\tau),\ell)$ in
$\mathbf{x}$. Furthermore, given the representation of
$\widetilde{\textup{{SW}}}(\mathbf{x}_{\scriptscriptstyle M})$ as an integral
of nice algebraic functions $\textup{H}_{\textup{cher}}$ and
$\textup{G}_{\textup{pois}}$, we can also compute all first and second order
derivatives of $\widetilde{\textup{{SW}}}(\mathbf{x}_{\scriptscriptstyle M})$
in polynomial time. This allows us to find the optimal solution
$\widetilde{\mathbf{x}}_{\scriptscriptstyle M}^{*}$ to (3) in polynomial time
using standard concave (first or second order) maximization methods.

To get the stated approximation guarantee we first compare the original
objective $\textup{{SW}}(\mathbf{x}_{\scriptscriptstyle
M},\mathbf{1}_{S_{\textup{fix}}})$ in (3) with
$\widetilde{\textup{{SW}}}(\mathbf{x}_{\scriptscriptstyle M})$ and get the
following Lemma.

###### Lemma B.1.

For any $\mathbf{x}=(\mathbf{x}_{\scriptscriptstyle
M},\mathbf{1}_{S_{\textup{fix}}})$ with $\mathbf{x}_{\scriptscriptstyle
M}\in[0,1]^{|M|}$ and any weights vector $\mathbf{w}$,

$\left\lvert\widetilde{\textup{{SW}}}(\mathbf{x}_{\scriptscriptstyle
M})-\textup{{SW}}(\mathbf{x})\right\rvert\leq
21\,\varepsilon\cdot\textup{{SW}}(\mathbf{x}).$

###### Proof.

We rewrite $\textup{{SW}}(\mathbf{x},\mathbf{w})$ for
$\mathbf{x}=(\mathbf{x}_{\scriptscriptstyle M},\mathbf{1}_{S_{\textup{fix}}})$
in the same form as (8).

$\textup{{SW}}(\mathbf{x})=\int_{0}^{\eta}\textup{H}_{\textup{ber}}(\mathbf{x},\tau)\,\mathrm{d}\tau+\int_{\eta}^{+\infty}\textup{G}_{\textup{ber}}(\mathbf{x}_{\scriptscriptstyle
M},\tau)\,\mathrm{d}\tau,$
$\displaystyle\text{where}\quad\textup{G}_{\textup{ber}}(\mathbf{x}_{\scriptscriptstyle
M},\tau)\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}$
$\displaystyle\sum_{j=0}^{|S_{\textup{fix}}|}\operatorname{\mathbf{Pr}}\mathchoice{\left[Z_{\textup{fix}}(\tau)=j\right]}{[Z_{\textup{fix}}(\tau)=j]}{[Z_{\textup{fix}}(\tau)=j]}{[Z_{\textup{fix}}(\tau)=j]}\cdot\biggl{(}\sum_{\ell=1}^{j}w_{{\ell}}+{}\sum_{\ell=j+1}^{n}(w_{{\ell}}-w_{{\ell+1}})\cdot\textup{H}_{\textup{ber}}(\mathbf{x}_{\scriptscriptstyle
M},\,\ell\\!-\\!j,\,\tau)\biggr{)}.$

We first compare the corresponding adjusted Bernoulli and Poisson terms.
Observe that $q_{i}(\mathbf{x},\tau)\leq\delta=\varepsilon$ for each bidder
$i\in M$ and threshold $\tau>\eta$ according to condition (b) in 4.3. Thus by
Lemma A.2 (a),

$\displaystyle\phantom{{}\leq{}}\left\lvert\textup{G}_{\textup{pois}}(\mathbf{x}_{\scriptscriptstyle
M},\tau)-\textup{G}_{\textup{ber}}(\mathbf{x}_{\scriptscriptstyle
M},\tau)\right\rvert$
$\displaystyle\leq\sum_{j=0}^{|S_{\textup{fix}}|}\operatorname{\mathbf{Pr}}\mathchoice{\left[Z_{\textup{fix}}(\tau)=j\right]}{[Z_{\textup{fix}}(\tau)=j]}{[Z_{\textup{fix}}(\tau)=j]}{[Z_{\textup{fix}}(\tau)=j]}\cdot\sum_{\ell=j+1}^{n}(w_{{\ell}}-w_{{\ell+1}})\cdot\left\lvert\textup{H}_{\textup{pois}}(\mathbf{x}_{\scriptscriptstyle
M},\,\ell\\!-\\!j,\,\tau)-\textup{H}_{\textup{ber}}(\mathbf{x}_{\scriptscriptstyle
M},\,\ell\\!-\\!j,\,\tau)\right\rvert$
$\displaystyle\leq\sum_{j=0}^{|S_{\textup{fix}}|}\operatorname{\mathbf{Pr}}\mathchoice{\left[Z_{\textup{fix}}(\tau)=j\right]}{[Z_{\textup{fix}}(\tau)=j]}{[Z_{\textup{fix}}(\tau)=j]}{[Z_{\textup{fix}}(\tau)=j]}\cdot\sum_{\ell=j+1}^{n}(w_{{\ell}}-w_{{\ell+1}})\cdot
17.5\,\delta\cdot\textup{H}_{\textup{ber}}(\mathbf{x}_{\scriptscriptstyle
M},\,\ell\\!-\\!j,\,\tau)$ $\displaystyle\leq
17.5\,\varepsilon\cdot\textup{G}_{\textup{ber}}(\mathbf{x}_{\scriptscriptstyle
M},\tau).$

Next, we compare Chernoff and Bernoulli objectives
($\textup{H}_{\textup{cher}}$ and $\textup{H}_{\textup{ber}}$) for low range
thresholds $\tau\leq\eta$. As both
$\textup{H}_{\textup{cher}}(\mathbf{q},\mathbf{w})$ and
$\textup{H}_{\textup{ber}}(\mathbf{q},\mathbf{w})$ are non-negative linear
combinations of respective terms for $\ell$-unit auctions with
$\sum_{i\in[n]}q_{i}({x_{i}},\tau)\geq\ell^{*}$ for $\tau\leq\eta$, we get by
Lemma A.3 (b) that

$\displaystyle\left\lvert\textup{H}_{\textup{cher}}(\mathbf{q},\mathbf{w})-\textup{H}_{\textup{ber}}(\mathbf{q},\mathbf{w})\right\rvert\leq
21\cdot\frac{\textup{H}_{\textup{ber}}(\mathbf{q},\mathbf{w})}{\sqrt{\ell^{*}}}\leq
21\,\varepsilon\cdot\textup{H}_{\textup{ber}}(\mathbf{q},\mathbf{w}).$

Thus after combining the two bounds for high and low ranges of thresholds
$\tau$ we get

$\left\lvert\widetilde{\textup{{SW}}}(\mathbf{x}_{\scriptscriptstyle
M})-\textup{{SW}}(\mathbf{x})\right\rvert\leq
21\,\varepsilon\cdot\int_{0}^{\eta}\textup{H}_{\textup{ber}}(\mathbf{x},\tau)\,\mathrm{d}\tau+{}17.5\,\varepsilon\cdot\int_{\eta}^{+\infty}\textup{G}_{\textup{ber}}(\mathbf{x}_{\scriptscriptstyle
M},\tau)\,\mathrm{d}\tau\leq 21\,\varepsilon\cdot\textup{{SW}}(\mathbf{x}),$

which concludes the proof of Lemma B.1. ∎

We proceed the proof of Theorem 4.4 by letting $\mathbf{x}^{*}$ be the optimal
solution to fractional BSP in (3). Then, we consider
$\mathbf{x}^{*}_{+}\in\mathbb{R}^{n}_{\geq 0}$ defined as
$\mathbf{x}^{*}_{+}\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}(\mathbf{x}_{\scriptscriptstyle
M}^{*},\mathbf{1}_{S_{\textup{fix}}})$, so that
$\mathbf{x}^{*}_{+}\succeq\mathbf{x}^{*}$. By Lemma B.1, for
$\mathbf{x}=\mathbf{x}^{*}_{+}$, we have

$\widetilde{\textup{{SW}}}(\mathbf{x}_{\scriptscriptstyle
M}^{*})\geq(1-21\,\varepsilon)\cdot\textup{{SW}}(\mathbf{x}^{*}_{+})\geq(1-21\,\varepsilon)\cdot\textup{{SW}}(\mathbf{x}^{*}).$

On the other hand, by Lemma B.1 for $\mathbf{x}=\widetilde{\mathbf{x}}^{*}$ we
have

$\displaystyle(1+21\,\varepsilon)\cdot\textup{{SW}}(\widetilde{\mathbf{x}}^{*})\geq\widetilde{\textup{{SW}}}(\widetilde{\mathbf{x}}_{\scriptscriptstyle
M}^{*})$
$\displaystyle\geq\widetilde{\textup{{SW}}}\left(\frac{k-\varepsilon\cdot
k}{k}\cdot\mathbf{x}_{\scriptscriptstyle
M}^{*}\right)\geq(1-\varepsilon)\cdot\widetilde{\textup{{SW}}}(\mathbf{x}_{\scriptscriptstyle
M}^{*})\geq(1-\varepsilon)\cdot(1-21\,\varepsilon)\cdot\textup{{SW}}(\mathbf{x}^{*}),$

where the second inequality holds, as
$\widetilde{\mathbf{x}}_{\scriptscriptstyle M}^{*}$ is the optimal solution to
(3) and $\frac{k-\varepsilon\cdot k}{k}\cdot\mathbf{x}_{\scriptscriptstyle
M}^{*}$ is a feasible solution; the third inequality holds, as
$\widetilde{\textup{{SW}}}(\mathbf{x})$ is a concave function in $\mathbf{x}$;
the last inequality holds by the last lower bound on
$\widetilde{\textup{{SW}}}(\mathbf{x}_{\scriptscriptstyle M}^{*})$. Finally,
as $\frac{(1-\varepsilon)(1-21\,\varepsilon)}{1+21\,\varepsilon}\geq
1-(1+2\cdot 21)\cdot\varepsilon$,

$\textup{{SW}}(\widetilde{\mathbf{x}}^{*})\geq(1-43\,\varepsilon)\cdot\textup{{SW}}(\mathbf{x}^{*}),$

which concludes the proof of the theorem. ∎

###  B.2. Proof of Theorem 4.5

See 4.5

###### Proof of Theorem 4.5.

Recall that the social welfare $\textup{{SW}}(S)$ of a $\ell$-unit or position
auction is submodular as a function of the invited set of bidders $S$.

###### Claim B.2.

The expected social welfare $\textup{{SW}}(S)$ for a set of bidders
$S\subseteq[n]$ in any $\ell$-unit or position auction is a submodular
function of $S$.

#### Analysis of Algorithm 4.2.

Clearly, $\mathbf{z}$ is a feasible solution to the integral BSP. We will
prove below that Section 4.2 has almost the same approximation guarantee as
Section 4.1. Let us denote the optimal social welfare for integral BSP as OPT.
Then the best solution $\mathbf{x}^{*}$ to the fractional BSP (3) may have
only higher welfare
$\textup{{SW}}(\mathbf{x}^{*},\mathbf{w})\geq\textsf{OPT}$. Furthermore, since
(3) is a multi-linear extension of the integral BSP, we have

$\operatornamewithlimits{\mathbf{E}}\limits_{\mathbf{y}\sim\textup{Ber}(\mathbf{x})}\mathchoice{\left[\textup{{SW}}(\mathbf{y},\mathbf{w})\right]}{[\textup{{SW}}(\mathbf{y},\mathbf{w})]}{[\textup{{SW}}(\mathbf{y},\mathbf{w})]}{[\textup{{SW}}(\mathbf{y},\mathbf{w})]}=\textup{{SW}}(\mathbf{x},\mathbf{w})\geq\left(1-43\,k^{-1/4}\right)\textup{{SW}}(\mathbf{x}^{*},\mathbf{w})\geq\left(1-43\,k^{-1/4}\right)\textsf{OPT}.$

Our solution $\mathbf{z}$ suffers an additional loss when the sample vector
$\mathbf{y}$ has more than $k$ elements $|\mathbf{y}|_{1}>k$. On the other
hand, for each given $\mathbf{y}$ with $|\mathbf{y}|_{1}>k$ we have
$\operatorname{\mathbf{E}}_{\mathbf{z}\sim\binom{\mathbf{y}}{k}}\mathchoice{\left[\textup{{SW}}(\mathbf{z},\mathbf{w})\right]}{[\textup{{SW}}(\mathbf{z},\mathbf{w})]}{[\textup{{SW}}(\mathbf{z},\mathbf{w})]}{[\textup{{SW}}(\mathbf{z},\mathbf{w})]}\geq\frac{k}{|\mathbf{y}|_{1}}\textup{{SW}}(\mathbf{y},\mathbf{w})$,
due to submodularity of $\textup{{SW}}(\mathbf{y},\mathbf{w})$ (here we use a
standard fact about monotone non-negative submodular function $f$: a uniformly
sampled subset $T\subset S$ of given size $|T|=k$ has
$\operatorname{\mathbf{E}}_{T}\mathchoice{\left[f(T)\right]}{[f(T)]}{[f(T)]}{[f(T)]}\geq\frac{k}{|S|}f(S)$).
Thus

$\displaystyle\operatornamewithlimits{\mathbf{E}}\limits_{\mathbf{y}\sim\textup{Ber}(\mathbf{x})}\mathchoice{\left[\textup{{SW}}(\mathbf{y},\mathbf{w})-\textup{{SW}}(\mathbf{z},\mathbf{w})\right]}{[\textup{{SW}}(\mathbf{y},\mathbf{w})-\textup{{SW}}(\mathbf{z},\mathbf{w})]}{[\textup{{SW}}(\mathbf{y},\mathbf{w})-\textup{{SW}}(\mathbf{z},\mathbf{w})]}{[\textup{{SW}}(\mathbf{y},\mathbf{w})-\textup{{SW}}(\mathbf{z},\mathbf{w})]}\leq\operatornamewithlimits{\mathbf{E}}\limits_{\mathbf{y}\sim\textup{Ber}(\mathbf{x})}\mathchoice{\left[\mathbb{I}\left[\vphantom{\sum}|\mathbf{y}|_{1}>k\right]\cdot\frac{|\mathbf{y}|_{1}-k}{|\mathbf{y}|_{1}}\cdot\textup{{SW}}(\mathbf{y},\mathbf{w})\right]}{[\mathbb{I}\left[\vphantom{\sum}|\mathbf{y}|_{1}>k\right]\cdot\frac{|\mathbf{y}|_{1}-k}{|\mathbf{y}|_{1}}\cdot\textup{{SW}}(\mathbf{y},\mathbf{w})]}{[\mathbb{I}\left[\vphantom{\sum}|\mathbf{y}|_{1}>k\right]\cdot\frac{|\mathbf{y}|_{1}-k}{|\mathbf{y}|_{1}}\cdot\textup{{SW}}(\mathbf{y},\mathbf{w})]}{[\mathbb{I}\left[\vphantom{\sum}|\mathbf{y}|_{1}>k\right]\cdot\frac{|\mathbf{y}|_{1}-k}{|\mathbf{y}|_{1}}\cdot\textup{{SW}}(\mathbf{y},\mathbf{w})]}.$

Furthermore, as
$\textsf{OPT}=\max_{S\subseteq[n]:|S|=k}\textup{{SW}}(S,\mathbf{w})$ we have
$\textsf{OPT}\geq\operatorname{\mathbf{E}}_{\mathbf{z}\sim\binom{\mathbf{y}}{k}}\mathchoice{\left[\textup{{SW}}(\mathbf{z},\mathbf{w})\right]}{[\textup{{SW}}(\mathbf{z},\mathbf{w})]}{[\textup{{SW}}(\mathbf{z},\mathbf{w})]}{[\textup{{SW}}(\mathbf{z},\mathbf{w})]}\geq\frac{k}{|\mathbf{y}|_{1}}\textup{{SW}}(\mathbf{y},\mathbf{w})$
for each $\mathbf{y}$ with $|\mathbf{y}|_{1}>k$. Therefore,

$\displaystyle\operatornamewithlimits{\mathbf{E}}\limits_{\begin{subarray}{c}\mathbf{y}\sim\textup{Ber}(\mathbf{x})\\\
\mathbf{z}\sim\binom{\mathbf{y}}{k}\end{subarray}}\mathchoice{\left[\textup{{SW}}(\mathbf{y},\mathbf{w})-\textup{{SW}}(\mathbf{z},\mathbf{w})\right]}{[\textup{{SW}}(\mathbf{y},\mathbf{w})-\textup{{SW}}(\mathbf{z},\mathbf{w})]}{[\textup{{SW}}(\mathbf{y},\mathbf{w})-\textup{{SW}}(\mathbf{z},\mathbf{w})]}{[\textup{{SW}}(\mathbf{y},\mathbf{w})-\textup{{SW}}(\mathbf{z},\mathbf{w})]}$
$\displaystyle\leq\operatornamewithlimits{\mathbf{E}}\limits_{\mathbf{y}\sim\textup{Ber}(\mathbf{x})}\mathchoice{\left[\mathbb{I}\left[\vphantom{\sum}|\mathbf{y}|_{1}>k\right]\cdot\frac{|\mathbf{y}|_{1}-k}{k}\cdot\textsf{OPT}\right]}{[\mathbb{I}\left[\vphantom{\sum}|\mathbf{y}|_{1}>k\right]\cdot\frac{|\mathbf{y}|_{1}-k}{k}\cdot\textsf{OPT}]}{[\mathbb{I}\left[\vphantom{\sum}|\mathbf{y}|_{1}>k\right]\cdot\frac{|\mathbf{y}|_{1}-k}{k}\cdot\textsf{OPT}]}{[\mathbb{I}\left[\vphantom{\sum}|\mathbf{y}|_{1}>k\right]\cdot\frac{|\mathbf{y}|_{1}-k}{k}\cdot\textsf{OPT}]}$
$\displaystyle=\frac{\textsf{OPT}}{k}\cdot\sum_{i=1}^{n-k}i\cdot\operatornamewithlimits{\mathbf{Pr}}\limits_{\mathbf{y}\sim\textup{Ber}(\mathbf{x})}\mathchoice{\left[|\mathbf{y}|_{1}=k+i\right]}{[|\mathbf{y}|_{1}=k+i]}{[|\mathbf{y}|_{1}=k+i]}{[|\mathbf{y}|_{1}=k+i]}=\frac{\textsf{OPT}}{k}\cdot\sum_{i=1}^{n-k}\operatornamewithlimits{\mathbf{Pr}}\limits_{\mathbf{y}\sim\textup{Ber}(\mathbf{x})}\mathchoice{\left[|\mathbf{y}|_{1}\geq
k+i\right]}{[|\mathbf{y}|_{1}\geq k+i]}{[|\mathbf{y}|_{1}\geq
k+i]}{[|\mathbf{y}|_{1}\geq k+i]}.$

###### Claim B.3.

Let $\mathbf{x}\in[0,1]^{n}$ with $|\mathbf{x}|_{1}=k$. Then $\sum_{i\geq
1}\operatorname{\mathbf{Pr}}_{\mathbf{y}\sim\textup{Ber}(\mathbf{x})}\mathchoice{\left[|\mathbf{y}|\geq
k+i\right]}{[|\mathbf{y}|\geq k+i]}{[|\mathbf{y}|\geq k+i]}{[|\mathbf{y}|\geq
k+i]}=O\bigl{(}\sqrt{k}\bigr{)}.$

###### Proof of B.3.

By Chernoff bound, we have

$\sum_{i=1}^{n-k}\operatornamewithlimits{\mathbf{Pr}}\limits_{\mathbf{y}\sim\textup{Ber}(\mathbf{x})}\mathchoice{\left[|\mathbf{y}|\geq
k+i\right]}{[|\mathbf{y}|\geq k+i]}{[|\mathbf{y}|\geq k+i]}{[|\mathbf{y}|\geq
k+i]}\leq\sum_{i=1}^{n-k}e^{-\frac{i^{2}}{i+2k}}\leq\sum_{i=1}^{\infty}e^{-\frac{i^{2}}{i+2k}}\leq\int_{0}^{\infty}e^{-\frac{x^{2}}{x+2k}}\,\mathrm{d}x.$

We further estimate this integral as

$\int_{0}^{\infty}e^{-\frac{x^{2}}{x+2k}}\,\mathrm{d}x\leq\int_{0}^{\sqrt{k}}e^{-\frac{x^{2}}{x+2k}}\,\mathrm{d}x+\int_{\sqrt{k}}^{\infty}e^{-\frac{x}{1+2\sqrt{k}}}\,\mathrm{d}x\leq
1\cdot\sqrt{k}-(1+2\sqrt{k})\left.e^{-\frac{x}{1+2\sqrt{k}}}\right|_{\sqrt{k}}^{+\infty}=O(\sqrt{k}).$

This concludes the proof of B.3. ∎

B.3 allows us to conclude that
$\operatorname{\mathbf{E}}_{\mathbf{y}\sim\textup{Ber}(\mathbf{x})}\mathchoice{\left[\textup{{SW}}(\mathbf{y},\mathbf{w})-\textup{{SW}}(\mathbf{z},\mathbf{w})\right]}{[\textup{{SW}}(\mathbf{y},\mathbf{w})-\textup{{SW}}(\mathbf{z},\mathbf{w})]}{[\textup{{SW}}(\mathbf{y},\mathbf{w})-\textup{{SW}}(\mathbf{z},\mathbf{w})]}{[\textup{{SW}}(\mathbf{y},\mathbf{w})-\textup{{SW}}(\mathbf{z},\mathbf{w})]}=O\bigl{(}\frac{1}{\sqrt{k}}\bigr{)}\cdot\textsf{OPT}$,
i.e.,

$\operatornamewithlimits{\mathbf{E}}\limits_{\mathbf{y}\sim\textup{Ber}(\mathbf{x})}\mathchoice{\left[\textup{{SW}}(\mathbf{z},\mathbf{w})\right]}{[\textup{{SW}}(\mathbf{z},\mathbf{w})]}{[\textup{{SW}}(\mathbf{z},\mathbf{w})]}{[\textup{{SW}}(\mathbf{z},\mathbf{w})]}=\textup{{SW}}(\mathbf{x},\mathbf{w})-O\left(\frac{1}{\sqrt{k}}\right)\cdot\textsf{OPT}=\left(1-43\,k^{-1/4}-O(k^{-1/2})\right)\textsf{OPT}.\qed$

##  Appendix C Better Algorithm for Single-Item Auction

In Section 4, we studied the Bidder Selection Problem (BSP) for position
auctions and obtained a $\bigl{(}1-O(k^{-1/4})\bigr{)}$-approximate algorithm.
In this section, we study the special case of single-item auction (i.e.,
$\ell$-unit auction with $\ell=1$) as it was extensively studied in previous
work, and give a better approximation ratio $\bigl{(}1-O(\sqrt{\ln
k/k})\bigr{)}$.

Similar to Section 4.1, we fix a small set $S_{\textup{fix}}$ of
$\varepsilon\cdot k$ bidders, which affects the final approximation by at most
$(1-\varepsilon)$ factor due to the submodularity of BSP as a set function of
the invited bidders. Formally, recall that for the single-item auction

$\textup{{SW}}(\mathbf{x})=\int_{0}^{+\infty}\textup{H}_{\textup{ber}}(\mathbf{q}(\mathbf{x},\tau),1)\,\mathrm{d}\tau=\int_{0}^{+\infty}\operatornamewithlimits{\mathbf{Pr}}\limits_{\mathbf{v}\sim\mathbf{x}\cdot\mathbf{\mathbf{D}}}\mathchoice{\left[\exists{v_{i}}\geq\tau\right]}{[\exists{v_{i}}\geq\tau]}{[\exists{v_{i}}\geq\tau]}{[\exists{v_{i}}\geq\tau]}\,\mathrm{d}\tau.$

We find the set of $\varepsilon\cdot k$ bidders $S_{\textup{fix}}$ such that
$\operatorname{\mathbf{Pr}}_{\mathbf{v}\sim\mathbf{\mathbf{D}}}\mathchoice{\left[\exists
i\in S_{\textup{fix}}:{v_{i}}\geq\eta\right]}{[\exists i\in
S_{\textup{fix}}:{v_{i}}\geq\eta]}{[\exists i\in
S_{\textup{fix}}:{v_{i}}\geq\eta]}{[\exists i\in
S_{\textup{fix}}:{v_{i}}\geq\eta]}\geq 1-\varepsilon$ for the largest possible
threshold $\eta$. This allows us to take care of thresholds $\tau$ in a low
range $\tau\in[0,\eta]$ by including $S_{\textup{fix}}$ in the solution (i.e.,
make ${x_{i}}=1$ for all $i\in S_{\textup{fix}}$). Naturally, we want to pick
bidders with higher probabilities
$\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}>\eta\right]}{[{v_{i}}>\eta]}{[{v_{i}}>\eta]}{[{v_{i}}>\eta]}$
into $S_{\textup{fix}}$, which means that for the high range thresholds
$\tau>\eta$ we get the small probability property for each bidder $i\notin
S_{\textup{fix}}$. This allows us to reduce BSP to the case of small
probabilities tail events (Appendix A) for $\tau>\eta$ and bidders
$i\in[n]\setminus S_{\textup{fix}}$, which can be effectively solved by the
Poisson approximation. Formally, we can get the following guarantees for
$S_{\textup{fix}}$.

###### Claim C.1 (Small Bidder Set).

Let $\varepsilon\geq\sqrt{\frac{\ln k}{k}}$ be a multiple of $1/k$. We can
find in polynomial time a threshold $\eta\geq 0$ and a set
$S_{\textup{fix}}\subset[n]$ of size $|S_{\textup{fix}}|=\varepsilon\cdot k$,
such that

$\textup{(a)}\;\operatornamewithlimits{\mathbf{Pr}}\limits_{\mathbf{v}\sim\mathbf{\mathbf{D}}}\mathchoice{\left[\exists
i\in S_{\textup{fix}}:{v_{i}}\geq\eta\right]}{[\exists i\in
S_{\textup{fix}}:{v_{i}}\geq\eta]}{[\exists i\in
S_{\textup{fix}}:{v_{i}}\geq\eta]}{[\exists i\in
S_{\textup{fix}}:{v_{i}}\geq\eta]}\geq
1-\frac{1}{k};\qquad\textup{(b)}\;\forall i\notin
S_{\textup{fix}},\;\operatornamewithlimits{\mathbf{Pr}}\limits_{{v_{i}}\sim{D_{i}}}\mathchoice{\left[{v_{i}}>\eta\right]}{[{v_{i}}>\eta]}{[{v_{i}}>\eta]}{[{v_{i}}>\eta]}<\varepsilon.$

###### Proof.

Recall that all distributions $\\{{D_{i}}\\}_{i\in[n]}$ have finite support.
Thus we can search through all thresholds $\tau$ in polynomial time. There
must be two consecutive threshold values $\eta$ and $\eta_{+}\\!>\eta$ such
that the number of bidders
$|\\{i:\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}\geq\eta\right]}{[{v_{i}}\geq\eta]}{[{v_{i}}\geq\eta]}{[{v_{i}}\geq\eta]}\geq\varepsilon\\}|\geq\varepsilon\cdot
k$ with large tail probabilities
$\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}\geq\eta\right]}{[{v_{i}}\geq\eta]}{[{v_{i}}\geq\eta]}{[{v_{i}}\geq\eta]}\geq\varepsilon$
is at least $\varepsilon\cdot k$, but a similar number of bidders
$|\\{i:\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}>\eta\right]}{[{v_{i}}>\eta]}{[{v_{i}}>\eta]}{[{v_{i}}>\eta]}=\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}\geq\eta_{+}\right]}{[{v_{i}}\geq\eta_{+}]}{[{v_{i}}\geq\eta_{+}]}{[{v_{i}}\geq\eta_{+}]}\geq\varepsilon\\}|<\varepsilon\cdot
k$ for the next threshold value $\eta_{+}$ is strictly less than
$\varepsilon\cdot k$.

Let us place each bidder $i$ with
$\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}>\eta\right]}{[{v_{i}}>\eta]}{[{v_{i}}>\eta]}{[{v_{i}}>\eta]}\geq\varepsilon$
into $S_{\textup{fix}}$ and fill the remaining positions in $S_{\textup{fix}}$
up to size $\varepsilon\cdot k$ (so that $|S_{\textup{fix}}|=\varepsilon\cdot
k$) with bidders from
$\\{i:\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}\geq\eta\right]}{[{v_{i}}\geq\eta]}{[{v_{i}}\geq\eta]}{[{v_{i}}\geq\eta]}\geq\varepsilon>\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}\geq\eta_{+}\right]}{[{v_{i}}\geq\eta_{+}]}{[{v_{i}}\geq\eta_{+}]}{[{v_{i}}\geq\eta_{+}]}\\}$.
Then, every bidder $i\notin S_{\textup{fix}}$ has
$\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}>\eta\right]}{[{v_{i}}>\eta]}{[{v_{i}}>\eta]}{[{v_{i}}>\eta]}=\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}\geq\eta_{+}\right]}{[{v_{i}}\geq\eta_{+}]}{[{v_{i}}\geq\eta_{+}]}{[{v_{i}}\geq\eta_{+}]}<\varepsilon$
as required by condition (b). On the other hand,
$|S_{\textup{fix}}|=\varepsilon\cdot k$ and
$\operatorname{\mathbf{Pr}}\mathchoice{\left[{v_{i}}\geq\eta\right]}{[{v_{i}}\geq\eta]}{[{v_{i}}\geq\eta]}{[{v_{i}}\geq\eta]}\geq\varepsilon$
for every $i\in S_{\textup{fix}}$, i.e., condition (a) is satisfied since

$\operatornamewithlimits{\mathbf{Pr}}\limits_{\mathbf{v}\sim\mathbf{\mathbf{D}}}\mathchoice{\left[\exists
i\in S_{\textup{fix}}:{v_{i}}\geq\eta\right]}{[\exists i\in
S_{\textup{fix}}:{v_{i}}\geq\eta]}{[\exists i\in
S_{\textup{fix}}:{v_{i}}\geq\eta]}{[\exists i\in
S_{\textup{fix}}:{v_{i}}\geq\eta]}\geq 1-(1-\varepsilon)^{\varepsilon\cdot
k}\geq 1-e^{-\varepsilon^{2}\cdot k}\geq 1-\frac{1}{k},$

where to get the second inequality, we used the fact that
$(1-\frac{1}{x})^{x}<e^{-1}$ for any $x\geq 1$. ∎

After selecting such set $S_{\textup{fix}}$ and threshold $\eta$, we are ready
to give the complete description of Appendix C.

Algorithm 0 Fractional BSP for Single-Item Auction. Fix
$\varepsilon=\sqrt{\frac{\ln k}{k}}$ rounded up to a multiple of $1/k$, then
do the following steps: (1) Find $(\eta,S_{\textup{fix}})$ as in C.1. Set
${x_{i}}=1$ for $\forall i\in S_{\textup{fix}}$. (2) For the remaining bidders
$M\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}[n]\setminus
S_{\textup{fix}}$ let the Poisson approximation
$\widetilde{\textup{{SW}}}(\mathbf{x}_{\scriptscriptstyle M})$ be
$\qquad\widetilde{\textup{{SW}}}(\mathbf{x}_{\scriptscriptstyle
M})\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\left(1-\frac{1}{k}\right)\eta+\int_{\eta}^{+\infty}\widetilde{\textup{H}}_{\textup{pois}}\\!\left(\mathbf{q}(\mathbf{x}_{\scriptscriptstyle
M},\tau)\right)\,\mathrm{d}\tau,\qquad\text{where}$
$\widetilde{\textup{H}}_{\textup{pois}}\\!\left(\mathbf{q}_{\scriptscriptstyle
M}\right)\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}r_{\tau}+(1-r_{\tau})\cdot\textup{H}_{\textup{pois}}\\!\left(\mathbf{q}_{\scriptscriptstyle
M},\,\ell=1\right),\quad\text{and}\quad
r_{\tau}\overset{\mathrm{def}}{=\mathrel{\mkern-3.0mu}=}\operatornamewithlimits{\mathbf{Pr}}\limits_{\mathbf{v}\sim\mathbf{\mathbf{D}}}\mathchoice{\left[\exists
i\in S_{\textup{fix}}:{v_{i}}\geq\tau\right]}{[\exists i\in
S_{\textup{fix}}:{v_{i}}\geq\tau]}{[\exists i\in
S_{\textup{fix}}:{v_{i}}\geq\tau]}{[\exists i\in
S_{\textup{fix}}:{v_{i}}\geq\tau]}.$ (3) Return
$\widetilde{\mathbf{x}}^{*}=(\mathbf{1}_{S_{\textup{fix}}},\,\widetilde{\mathbf{x}}_{\scriptscriptstyle
M}^{*})$, where $\widetilde{\mathbf{x}}_{\scriptscriptstyle M}^{*}$ is the
solution to the concave program in $\mathbf{x}_{\scriptscriptstyle M}$:
$\begin{array}[]{ll}\text{Maximize}&\widetilde{\textup{{SW}}}(\mathbf{x}_{\scriptscriptstyle
M})\\\ \text{Subject To}&\sum_{i\in M}{x_{i}}\leq k-\varepsilon\cdot
k,\quad{x_{i}}\in[0,1]\quad\forall i\in M.\end{array}$

In the algorithm, we ignore thresholds $\tau\in[0,\eta]$, as by taking
$S_{\textup{fix}}$ we have already achieved high success probability of at
least $1-\frac{1}{k}$ by C.1. For the high range thresholds $\tau>\eta$, we
first observe that as the result of fixing set $S_{\textup{fix}}$, the
probability that there is a bidder with value greater than the threshold
$\tau$ becomes

$\\!\\!\textup{H}_{\textup{ber}}(\mathbf{q},1)=\operatorname{\mathbf{Pr}}\mathchoice{\left[\exists
i\in[n]:{v_{i}}\geq\tau\right]}{[\exists i\in[n]:{v_{i}}\geq\tau]}{[\exists
i\in[n]:{v_{i}}\geq\tau]}{[\exists
i\in[n]:{v_{i}}\geq\tau]}=r_{\tau}+\left(1-r_{\tau}\right)\cdot\operatorname{\mathbf{Pr}}\mathchoice{\left[\exists
i\in M:{v_{i}}\geq\tau\right]}{[\exists i\in M:{v_{i}}\geq\tau]}{[\exists i\in
M:{v_{i}}\geq\tau]}{[\exists i\in M:{v_{i}}\geq\tau]},$

where $r_{\tau}$ is a constant that we can easily compute. Hence, we
respectively adjust the Poisson approximation term
$\widetilde{\textup{H}}_{\textup{pois}}(\mathbf{q}_{\scriptscriptstyle M})$ in
the algorithm according to (2) (we slightly abuse notations by writing
$\textup{H}_{\textup{pois}}(\mathbf{q}_{\scriptscriptstyle M})$ instead of
$\textup{H}_{\textup{pois}}(\mathbf{q})$: for the coordinates $i\notin M$ we
let $q_{i}=0$).

###### Theorem C.2.

Appendix C for single-item auction works in polynomial time and is a
$(1-2\varepsilon)$-approximation, i.e., a $\bigl{(}1-O\big{(}\sqrt{\ln
k/k}\big{)}\bigr{)}$-approximation to the fractional BSP.

###### Proof.

We first verify that Appendix C is polynomial. Note that the step (1) works in
polynomial time by C.1. For each $\tau$ in the support of ${D_{i}}$ we
calculate in polynomial time the constants $r_{\tau}\in[0,1]$. Both
$\widetilde{\textup{H}}_{\textup{pois}}(\mathbf{q}_{\scriptscriptstyle M})$
for each $\mathbf{x}_{\scriptscriptstyle M}$ and $\tau$ in the support and
$\widetilde{\textup{{SW}}}(\mathbf{x}_{\scriptscriptstyle M})$ for each
$\mathbf{x}_{\scriptscriptstyle M}$ can be computed in polynomial time.
Moreover, all first and second order partial derivatives of
$\widetilde{\textup{{SW}}}(\mathbf{x}_{\scriptscriptstyle M})$ can be computed
in the same way as the integral of respective derivatives of
$\widetilde{\textup{H}}_{\textup{pois}}(\mathbf{x}_{\scriptscriptstyle M})$.
Furthermore, it is easy to see that
$\widetilde{\textup{{SW}}}(\mathbf{x}_{\scriptscriptstyle M})$ is a concave
function in $\mathbf{x}_{\scriptscriptstyle M}$, since it is a positive linear
combination of constant terms (such as $(1-1/k)\eta$ and $r_{\tau}$) and
concave functions $\textup{H}_{\textup{pois}}(\mathbf{x}_{\scriptscriptstyle
M})$ according to 4.2. Hence, we can find the optimal solution
$\widetilde{\mathbf{x}}_{\scriptscriptstyle M}^{*}$ in polynomial time using
standard concave (first or second order) maximization methods.

To prove an approximation guarantee of $1-2\varepsilon$ for Appendix C, we
first derive the following approximations of
$\textup{{SW}}(\mathbf{x}_{\scriptscriptstyle
M},\mathbf{1}_{S_{\textup{fix}}})$ by
$\widetilde{\textup{{SW}}}(\mathbf{x}_{\scriptscriptstyle M})$ similar to (11)
(but in a special case of $\ell=1$).

###### Lemma C.3.

$\forall\mathbf{x}_{\scriptscriptstyle M}\in[0,1]^{|M|}$,