# Lightmorphic Signatures Analysis Toolkit

Dumitru Damian<EMAIL_ADDRESS>
Information and Communication Engineering
Research and development consultant
Timișoara, RO

###### Abstract

In this paper we discuss the theory used in the design of an open source
lightmorphic signatures analysis toolkit (LSAT). In addition to providing a
core functionality, the software package enables specific optimizations with
its modular and customizable design.

To promote its usage and inspire future contributions, LSAT is publicly
available. By using a self-supervised neural network and augmented machine
learning algorithms, LSAT provides an easy-to-use interface with ample
documentation.

The experiments demonstrate that LSAT improves the otherwise tedious and
error-prone tasks of translating lightmorphic associated data into usable
spectrograms, enhanced with parameter tuning and performance analysis.

With the provided mathematical functions, LSAT validates the nonlinearity
encountered in the data conversion process while ensuring suitability of the
forecasting algorithms.

Keywords: lightmorphic, machine learning, spectrogram, graph chord, neural
network

##  1 Introduction

It is common knowledge, in the machine learning domain, to use differential
values, since they provide a simple way to model the data. However, such
algorithms may not fit the lightmorphic signature properly, leading to a
reduced quality of the obtained results. Training a neural network to predict
the lightmorphic signature can significantly increase the data quality. This
is the task that LSAT tries to accomplish.

As such we define the lightmorphic metric learning (LML) as a branch of
machine learning algorithms, set out with the purpose of learning lightmorphic
signatures from multiple datasets trough usage of vibrating graph chords.

In the pursuing sections we describe the main features of the toolkit, explain
the general mathematical concepts and finally detail the plans regarding
future functionalities.

##  2 General mathematical concepts

In this section we expand the mathematical concepts and link them with the
reasoning encountered in the implemented code.

We define the lightmorphic signature as a function of: light intensity (I)
that varies according to seasons and local weather conditions, trajectory
distribution characteristics (D), and specific adjustments (T):

$f_{L_{\odot}}=\int\limits_{1}^{I}\int\limits_{1}^{D}\int\limits_{1}^{T}\Gamma_{t}\zeta_{t}{dt}$
(1)

where:

  * •

$\Gamma_{t}$ – trajectory tensor

  * •

$\zeta_{t}$ – point in time specificity

Storage of these trajectory specific lightmorphic signatures is done in a
database ($\Theta$). The segments containing isochronous surfaces with
similarities are stored in another database ($\Phi$) that serves as a baseline
for training the neural network implementation.

The isochronous surfaces that constitute the lightmorphic signature are
interlinked trough the definition and usage of graph chords ($\delta(t)$).
Observing their vibrational amplitude allows the prediction of alternative
lightmorphic signatures and, at the same time, correction of the already known
values.

Since the primary light source considered is the Earth’s Sun, specific
spacetime metrics (ex. $g_{\mu\nu},\eta_{\mu\nu},h_{+},h_{\times},G_{\mu\nu}$)
have to be used in order to describe the encountered anisotropies. These are
implemented as a function of distant astrophysical forces that stretch and
compress the fabric of spacetime.

According to special relativity, spacetime is seen as a four dimensional
manifold described by a flat Minkowski metric defined in Cartesian coordinates
(t, x, y, z, c = 1) as:

$\eta_{\mu\nu}=\begin{pmatrix}-1&0&0&0\\\ 0&1&0&0\\\ 0&0&1&0\\\ 0&0&0&1\\\
\end{pmatrix},$ (2)

When considering the geometry of curved space, we have made use of the metric
$g_{\mu\nu}$, that replaces the flat Minkowski metric $\eta_{\mu\nu}$. This
substitution was done considering that the geometry of curved space will
eventually reduce to the flat spacetime of special relativity at a
sufficiently small scale.

The interaction between curvature of spacetime and the mass distribution was
modeled following (Blackburn (2010)) work, as:

$G_{\mu\nu}=kT_{\mu\nu}$ (3)

where $G_{\mu\nu}$ is defined as the Einstein curvature tensor, $T_{\mu\nu}$
is the stress-energy tensor and represents the mass-energy distribution, while
k describes the Einstein constant of gravitation defined as:

$k=\frac{8\pi G}{c^{4}}$ (4)

where c is the speed of light in a vacuum.

At the same time, in order to improve the results quality, the Einstein tensor
was also considered under the form:

$G_{\mu\nu}=R_{\mu\nu}-\frac{1}{2}g_{\mu\nu}R,$ (5)

where $R_{\mu\nu}$ is the Riemann tensor for the local spacetime, and R is the
Ricci scalar.

Since there is not one general solution for the complex Einstein equations,
but a large variety of possible solutions that apply to particular
circumstances, we’ve considered a weak-field approximation, where the
nonlinear Einstein equations where approximated towards linearity.

For example, a very small perturbation specific to a gravitational wave, will
impact the flat spacetime and it is defined as $h_{\mu\nu}(x)$ and it’s value
will be $|h_{\mu\nu}|<<1$.

Thus, the Einstein equation becomes:

$g_{\mu\nu}(x)=\eta_{\mu\nu}+h_{\mu\nu}(x).$ (6)

or by simply considering the induced strain variations:

$\Box h_{\mu\nu}(x)=0,$ (7)

By further pursuing such linearization, we can represent in the TT gauge, a
propagating wave, under the following form:

$h_{\mu\nu}^{TT}=\begin{pmatrix}0&0&0&0\\\ 0&h_{+}&h_{\times}&0\\\
0&h_{\times}&-h_{+}&0\\\ 0&0&0&0\\\ \end{pmatrix},$ (8)

where the constant amplitudes ($h_{+}$, $h_{\times}$) represent the two
gravitational wave polarizations, the plus- and cross-polarization.

We represent the distance between two neighboring points as defined by (Berit
(2013)) for a flat spacetime, trough the following expression:

$ds^{2}=-c^{2}dt^{2}+dx^{2}+dy^{2}+dz^{2}=-c^{2}dt^{2}+[1+h_{+}(t)]dx^{2}+[1-h_{+}(t)]dy^{2}$

That allows us to model in the TT gauge, the gravitational wave stretching
along the x axis and compression along the y axis with the specific factor of:
$\sqrt{1\pm h_{+}(t)}\simeq 1+\frac{1}{2}h_{+}(t)$

Having modeled the photon’s traveling path in outer space, in order to
simplify the inherent path inhomogeneities, we separated the domains into
outer space domain, atmospheric domain and Earth specific domains
(lithosphere, hydrosphere, biosphere, noises, etc).

We further define the phase of an electromagnetic wave of frequency
$\omega_{0}$ as $\phi$. Following Driggers (2015)’s work, we consider that the
starting light phase is at 0 and it travels at the speed of light c. After a
distance L it will have a phase $\delta_{\phi_{space}}$ that can be expressed
as a distance integral over the spacetime metric,

$\delta_{\phi_{space}}=\frac{\omega_{0}}{c}\int_{0}^{L}gdx,$ (9)

with $g(t)=\eta+h(t)$, where $\eta$ is the Minkowski metric and h(t) is the
dimensionless spacetime strain.

Summing the light phase shift $\delta_{\phi_{atm}}$ and the
$\delta_{\phi_{Earth}}$ which is derived from the noise sources like seismic
or electromagnetic interferences, leads to the dataset of trajectory specific
lightmorphic signatures:

$\Phi_{\Gamma_{IDT}}=\sum_{j=1}^{\mathbb{N}}{\Gamma_{IDT}^{j}}$ (10)

The signature parameter estimation is performed considering a prior
distribution p($\Phi|L_{\odot}$) that is updated upon receiving the new data d
to give a posterior distribution p($\Phi|d,L_{\odot}$)

$p(\Phi|d,L_{\odot})=\frac{p(\Phi|L_{\odot})p(d|\Phi,L_{\odot})}{p(d|L_{\odot})}$
(11)

While observing the distribution of multiple light segments within the dataset
$\Phi_{\Gamma_{IDT}}$, it will be possible to estimate the probability for
trajectory specific lightmorphic evolution:

$p_{\Phi}=f({\rho_{k}\cdot p_{\Phi_{k}}})$ (12)

where $p_{\Phi_{k}}$ is the database’s k-th segment specific probability,
$\rho_{k}$ is the prediction weight for the k-th segment.

##  3 Software package design

The distribution matrices specific to the isochronous segmentation surfaces,
which define the lightmorphic signature model, form the LSAT core.

As such we’ve used a design principle that ensures simplicity for the whole
package, while making the source codes easy to read and maintain. As the
toolkit is written in a modular way, new functionalities can be easily plugged
in. This makes the LSAT not only a lightmorphic signature machine learning
tool but also an experimental platform.

LSAT comes with plenty of documentation for all the interface functionalities
and related data structures. The README file describes the installation
process and interface usage. For developers who use the toolkit in their
applications, the API documentation can provide additional information related
to functionality calls.

##  4 Practical Usage

In the examples, we provide sample values for the lightmorphic signature
updates, as a function of $\delta_{\phi_{atm}}$ derived by the neural network
from the values of a large dataset of atmospheric meteorological data for 317
cities in Romania, with hundreds of thousands data points. Automatic learning
is supported trough API calls to the domain specific data providers.

Beyond this simple way of running the lightmorphic signatures analysis
toolkit, there are several enhancement options for advanced usage. As example,
one may activate additional functionalities that consider input parameters
like complex space weather forecasting, different electromagnetic wave
disturbances or lithosphere, hydrosphere and biosphere specific localized
data.

##  5 Conclusion and Future Work

With the lightmorphic signatures analysis toolkit we provided an open source
SW package that is simple and easy-to-use.

Experiments and analysis conclude that the modular design and customization
support are performing excellent in practice and can provide the base for
additional research on lightmorphic signatures.

The toolkit is constantly being improved by new research results and user
feed-back with the ultimate goal of having an automated toolkit to use in
maintaining and updating a large database of high-quality light signatures.

Future work will focus on probability estimates, additional functionalities
that mitigate the large uncertainties in the available observational input
data which arise from the complex interaction processes. In addition, the
inclusion of artificial intelligence (AI) options will be considered while
building a national/international network for lightmorphic signature analysis.

##  6 References

## References

  * Adhikari (2004) Rana Adhikari.  _Sensitivity and noise analysis of 4 km laser interferometric gravitational wave antennae_.  PhD thesis, Massachusetts Institute of Technology, 2004.
  * Berit (2013) Behnke Berit.  _A Directed Search for Continuous Gravitational Waves from Unknown Isolated Neutron Stars at the Galactic Center_.  PhD thesis, Leibniz University Hannover, 2013.
  * Biscoveanu et al. (2021) Sylvia Biscoveanu, Maximiliano Isi, Salvatore Vitale, and Vijay Varma.  New Spin on LIGO-Virgo Binary Black Holes.  _Phys. Rev. Lett._ , 126(17):171103, 2021.  doi: 10.1103/PhysRevLett.126.171103.
  * Blackburn (2010) Lindy Blackburn.  _Open Issues in the Search for Gravitational Wave Transients_.  PhD thesis, Massachusetts Institute of Technology, 2010.
  * Clark (2013) Daniel E. Clark.  _Control of Differential Motion between Adjacent Advanced LIGO Seismic Isolation Platforms_.  PhD thesis, Stanford University, 2013.
  * Dooley (2011) Katherine Laird Dooley.  _Design and performance of high laser power interferometers for gravitational-wave detection_.  PhD thesis, University of Florida, 2011.
  * Driggers (2015) Jennifer Clair Driggers.  _Noise Cancellation for Gravitational Wave Detectors_.  PhD thesis, California Institute of Technology, 2015.
  * Fricke (2011) Tobin Thomas Fricke.  _Homodyne detection for laser-interferometric gravitational wave detectors_.  PhD thesis, Louisiana State University and Agricultural and Mechanical College, 2011.
  * Lasky et al. (2016) Paul D. Lasky et al.  Gravitational-wave cosmology across 29 decades in frequency.  _Phys. Rev. X_ , 6(1):011035, 2016.  doi: 10.1103/PhysRevX.6.011035.
  * Maggiore (2000) Michele Maggiore.  Gravitational wave experiments and early universe cosmology.  _Phys. Rept._ , 331:283–367, 2000.  doi: 10.1016/S0370-1573(99)00102-7.
  * Martynov (2015) Denis Martynov.  _Lock Acquisition and Sensitivity Analysis of Advanced LIGO Interferometers_.  PhD thesis, California Institute of Technology, 2015.
  * Quitzow-James (2016) Ryan Quitzow-James.  _Search for Long-Duration Transient Gravitational Waves Associated with Magnetar Bursts during LIGO’s Sixth Science Run_.  PhD thesis, Oregon U., 2016.
  * Romano and Cornish (2017) Joseph D. Romano and Neil J. Cornish.  Detection methods for stochastic gravitational-wave backgrounds: a unified treatment.  _Living Rev. Rel._ , 20(1):2, 2017.  doi: 10.1007/s41114-017-0004-1.
  * Ross (2020) Michael P. Ross.  _Precision Mechanical Rotation Sensors for Terrestrial Gravitational Wave Observatories_.  PhD thesis, University of Washington, 2020.
  * Tuyenbayev (2017) Darkhan Tuyenbayev.  _Extending the scientific reach of Advanced LIGO by compensating for temporal variations in the calibration of the detectors_.  PhD thesis, The University of Texas at San Antonio, 2017.
  * Wade (2015) Madeline Wade.  _Gravitational-Wave Science with the Laser Interferometer Gravitational-Wave Observatory_.  PhD thesis, University of Wisconsin–Milwaukee, 2015.


# Online Bipartite Matching and Adwords

Vijay V. Vazirani111Supported in part by NSF grant CCF-1815901. University of
California, Irvine

###### Abstract

The simplicity of the recently obtained proof of the optimal algorithm for
online bipartite matching (OBM), called RANKING [KVV90], naturally raises the
possibility of extending this algorithm to the adwords problem, or its special
case called SMALL, in which bids are small compared to budgets; the latter has
been of considerable practical significance in ad auctions [MSVV07].

The attractive feature of our approach, in contrast to [MSVV07], was that it
would yield a budget-oblivious algorithm, i.e., during its execution, the
algorithm would not need to know what fraction of budget each bidder has spent
— only whether there is budget left-over. This would immediately render the
algorithm useful for autobidding platforms.

Our attempt met several hurdles, which are described in detail in the paper.
In particular, a substantial probabilistic development led us to obtain an
optimal, online, budget-oblivious algorithm for SINGLE-VALUED, which is
intermediate between OMB and the adwords problem; this algorithm is a natural
generalization of RANKING. For SMALL, we managed to overcome all but one
hurdle, namely failure of a property, called the no-surpassing property.
Interestingly enough, this property plays a minor role in the proofs of
RANKING as well as our algorithm for SINGLE-VALUED.

In this paper, we have stated our result for SMALL, namely an optimal, online,
budget-oblivious algorithm, as a Conditional Theorem, after assuming the no-
surpassing property. Considering the importance of budget-obliviousness, it is
important to remove the assumption — we leave this as an open problem. Another
viewpoint is that to make the no-surpassing property fail, the instance has to
be intricately “doctored up”. Therefore, we believe that in typical instances,
this property fails on very few queries, if any; this needs to be
experimentally verified. If so, our Conditional Algorithm may be useful as
such in practice.

##  1 Introduction

The online bipartite matching problem (OBM) occupies a central place not only
in online algorithms but also in matching-based market design, see details in
Sections 1.2 and 1.1. For formal statements of problems studied in this paper,
see Section 2. For OBM, a simple, optimal, randomized online algorithm, called
RANKING, was given in [KVV90]. Its competitive ratio is $\left(1-{1\over
e}\right)$ and [KVV90] showed that no randomized online algorithm can achieve
a better ratio than $\left(1-{1\over e}\right)+o(1)$.

The analysis of RANKING given in [KVV90] was considered “extremely difficult”.
Over the years, several researchers contributed valuable ideas to simplifying
its proof; indeed, our work would not have been possible without these ideas,
see details in Section 1.2. These proofs involve methodology from two domains,
probability theory and combinatorics, with the former playing a dominant role.
The simplicity of the final proof [EFFS21] naturally raises the possibility of
extending RANKING to generalizations of OBM. Our attempt at this had the
effect of applying a stress test to the proof, as a result of which, the
combinatorial part was found to be incomplete in a small though essential way,
see details in Sections 1.2 and 1.3.

We have named the missing piece the No-Surpassing Property, see Property 10
and have given a simple combinatorial fact which helps prove this property.
Our paper starts by presenting this analysis222The proof presented in this
paper is meant to be a “textbook quality” exposition and will appear in the
chapter [EIV22] of an upcoming edited book on matching markets.. Our goal was
to extend RANKING all the way to the adwords problem, called GENERAL in this
paper, or even its special case, called SMALL. Informally, GENERAL involves
matching keyword queries, as they arrive online, to advertisers having budget
limits, and SMALL is the special case in which bids are small compared to
budgets.

The latter problem captures a key computational issue that arises in the
context of ad auctions, for instance in Google’s AdWords marketplace. An
optimal algorithm achieving a competitive ratio of $\left(1-{1\over e}\right)$
was first given in [MSVV07]; for the impact of this result in the marketplace,
see 1.1. We note that previous attempts at extending RANKING to SMALL did not
meet with success; the alternative approach followed by [MSVV07] is described
in Section 1.2. In contrast, GENERAL is a notoriously difficult problem, one
of the reasons being inherent structural difficulties, see Section 5.1, and
has remained largely unresolved; see below for marginal progress made
recently.

Whereas the approach of [MSVV07] attacks SMALL directly, without having to
deal with GENERAL, our approach, of building directly on RANKING, needs to
first solve GENERAL. Our way of bypassing the structural difficulties of
GENERAL was to use the idea of fake money, see Section 1.3, and then resort to
the fact that in SMALL, the fake money used is negligible in the limit.

Given the complications in GENERAL and the already challenging probabilistic
argument in the proof of RANKING, extending RANKING directly to GENERAL
appeared quite hopeless. Fortunately, a clean setting was offered by an
intermediate problem, which we call SINGLE-VALUED. Under this problem, each
bidder can make bids of one value only, although the value may be different
for different bidders. It turns out that SINGLE-VALUED had already been solved
by a reduction to online vertex weighted matching, see Section 1.2.

However, for our purposes, SINGLE-VALUED needed to be solved from first
principles, for reasons explained in Section 1.3. This turned out to be
valuable in three respects: our algorithm for SINGLE-VALUED, which can be seen
as a natural generalization of RANKING, uses fewer random bits (see Section
1.3), the algorithm is budget-oblivious333The question of budget-obliviousness
for the previous approach [AGKM11] does not arise since in the reduced
instance, each bidder only makes one bid. (see explanation below), and the
probabilistic part of the proof of RANKING got extended in a substantial
enough manner that we could then attack GENERAL with the idea of fake money.
In this last step, whereas the probabilistic argument panned out, the
combinatorial part of the proof, in particular, the no-surpassing property,
failed to hold. This came as a surprise, since in the proofs of RANKING and
SINGLE-VALUED, this property was a small aspect of the combinatorial part,
which was a small part of the entire proof!

Since the ideas underlying the algorithm and the rest of the proof of
correctness are quite substantial, it was not appropriate to simply abandon
them, especially considering the potential gains if the hurdle can be
overcome; these gains are specified below. For these reasons, in Section 5.2,
we have assumed that the property of no-surpassing and stated our result for
SMALL as Conditional Theorem 41. We leave the open problem of filling the gap.
Another viewpoint is that in order to make the no-surpassing property fail,
the instance has to be intricately “doctored up”. For this reason, we believe
that in typical instances, this property fails on very few queries, if at all,
and the competitiveness of the algorithm may be comparable to that of
[MSVV07]; this needs to be experimentally verified. If so, our Conditional
Algorithm may be useful as such in practice, especially because of its budget-
obliviousness.

We note that our approach to SMALL is more basic than the one used in
[MSVV07], since it builds directly on OBM and RANKING, as a result, our
conditional algorithm for SMALL is more elementary than the one in [MSVV07].
The effective bid of each bidder $j$ for a query is simply its bid multiplied
by its price $p_{j}=e^{w_{j}-1}$, where $w_{j}$, called the rank of $j$, is
picked at random from $[0,1]$. On the other hand, the effective bid in
[MSVV07] is the bid multiplied by $(1-e^{L_{j}/B_{j}})$, where $B_{j}$ and
$L_{j}$ are the total budget and the leftover budget of bidder $j$,
respectively. As a result, whereas the algorithm of [MSVV07] needs to know the
total budget of each bidder, our algorithm does not. During its run, our
algorithm only needs to know whether the budget of a bidder has been
exhausted. Yet, its revenue is compared to the optimal revenue generated by an
offline algorithm with full knowledge of the budget. This budget-obliviousness
gives our approach a distinct advantage, since it can be used in autobidding
platforms [ABM19, DM22], which dynamically adjust the bids and budgets of
advertisers over multiple search engines to improve performance.

For GENERAL, the greedy algorithm, which matches each query to the highest
bidder, achieves a competitive ratio of $1/2$. Until recently, that was the
best possible. In [HZZ20] a marginally improved algorithm, with a ratio of
$0.5016$, was given. It is important to point out that this 60-page paper was
a tour-de-force, drawing on a diverse collection of ideas — a testament to the
difficulty of this problem.

######  Remark 1.

The objective of all adwords problems studied in this paper is to maximize the
total revenue accrued by the online algorithm. In economics, such a solution
is referred to as efficient, since the amount bid by an advertiser is
indicative of how useful the query is to it, and hence to the economy.

###  1.1 Significance and Practical Impact

Google’s AdWords marketplace generates multi-billion dollar revenues annually
and the current annual worldwide spending on digital advertising is almost
half a trillion dollars. These revenues of Google and other Internet services
companies enable them to offer crucial services, such as search, email,
videos, news, apps, maps etc. for free – services that have virtually
transformed our lives.

We note that SMALL is the most relevant case of adwords for the search ads
marketplace e.g., see [DM22]. A remarkable feature of Google, and other search
engines, is the speed with which they are able to show search results, often
in milliseconds. In order to show ads at the same speed, together with search
results, the solution for SMALL needed to be minimalistic in its use of
computing power, memory and communication.

The online algorithm of [MSVV07] satisfied these criteria and therefore had a
substantial impact in this marketplace. Furthermore, the idea underlying their
algorithm was extracted into a simple heuristic, called bid scaling, which
uses even less computation and is widely used by search engine companies
today. As mentioned above, our Conditional Algorithm for SMALL is even more
elementary and is budget-oblivious.

It will be useful to view the AdWords marketplace in the context of a bigger
revolution, namely the advent of the Internet and mobile computing, and the
consequent resurgence of the area of matching-based market design. The birth
of this area goes back to the seminal 1962 paper of Gale and Shapley on stable
matching [GS62]. Over the decades, this area became known for its highly
successful applications, having economic as well as sociological impact. These
included matching medical interns to hospitals, students to schools in large
cities, and kidney exchange.

The resurgence led to a host of highly innovative and impactful applications.
Besides the AdWords marketplace, which matches queries to advertisers, these
include Uber, matching drivers to riders; Upwork, matching employers to
workers; and Tinder, matching people to each other, see [Ins19] for more
details.

A successful launch of such markets calls for economic and game-theoretic
insights, together with algorithmic ideas. The Gale-Shapley deferred
acceptance algorithm and its follow-up works provided the algorithmic backbone
for the “first life” of matching-based market design. The algorithm RANKING
has become the paradigm-setting algorithmic idea in the “second life” of this
area. Interestingly enough, this result was obtained in the pre-Internet days,
over thirty years ago.

###  1.2 Related Works

We start by describing simplifications to the proof of RANKING for OBM. The
first simplifications, in [GM08, BM08], got the ball rolling, setting the
stage for the substantial simplification given in [DJK13], using a randomized
primal-dual approach. [DJK13] introduced the idea of splitting the
contribution of each matched edge into primal and dual contributions and
lower-bounding each part separately. Their method for defining prices $p_{j}$
of goods, using randomization, was used by subsequent papers, including this
one444For a succinct proof of optimality of the underlying function,
$e^{x-1}$, see Section 2.1.1 in [HT22]..

Interestingly enough, the next simplification involved removing the
scaffolding of LP-duality and casting the proof in purely probabilistic
terms555Even though there is no overt use of LP-duality in the proof of
[EFFS21], it is unclear if this proof could have been obtained directly,
without going the LP-duality-route., using notions from economics to split the
contribution of each matched edge into the contributions of the buyer and the
seller. This elegant analysis was given by [EFFS21]. We note that when we move
to generalizations of OBM, even this economic interpretation needs to be
dropped, see Remark 18.

We now point out the exact places in the last two papers in which the proofs
were incomplete. In Lemma 1, [DJK13] state “Since $Y_{i}<y^{c}$, $j$ is
matched to $i$”; note that in this paper, goods are indexed by $i$ and buyers
by $j$. At this place, the proof needs to argue that there is no other good
$i^{\prime}$, which is available to $j$ and satisfies
$Y_{i^{\prime}}<Y_{i}<y^{c}$. Next, in Observation 1 in the proof of Lemma
2.3, [EFFS21] state, “This follows since buyer $l_{i}$ derives higher utility
from item $r_{j}$ than from its match in $M_{-j}$.” Once again, the proof
needs to show that in the run with all goods, an even better match than
$r_{j}$ does not show up for buyer $l_{i}$.

An important generalization of OBM is online $b$-matching. This problem is a
special case of GENERAL in which the budget of each advertiser is $\$b$ and
the bids are $0/1$. [KP00] gave a simple optimal online algorithm, called
BALANCE, for this problem. BALANCE awards the next query to the interested
bidder who has been matched least number of times so far. [KP00] showed that
as $b$ tends to infinity, the competitive ratio of BALANCE tends to
$\left(1-{1\over e}\right)$.

The importance of online $b$-matching arises from the fact that it is a
special case of SMALL, if $b$ is large. Indeed, the first online algorithm
[MSVV07] for SMALL was obtained by extending BALANCE as follows: [MSVV07]
first gave a simpler proof of the competitive ratio of BALANCE using the
notion of a factor-revealing LP [JMM+03]. Then they gave the notion of a
tradeoff-revealing LP, which yielded an algorithm achieving a competitive
ratio of $\left(1-{1\over e}\right)$. [MSVV07] also proved that this is
optimal for $b$-matching, and hence SMALL, by proving that no randomized
algorithm can achieve a better ratio for online $b$-matching; previously,
[KP00] had shown a similar result for deterministic algorithms. Following
[MSVV07], a second optimal online algorithm for SMALL was given in [BJN07],
using a primal-dual approach.

Another relevant generalization of OBM is online vertex weighted matching, in
which the offline vertices have weights and the objective is to maximize the
weight of the matched vertices. [AGKM11] extended RANKING to obtain an optimal
online algorithm for this problem. Clearly, SINGLE-VALUED is intermediate
between GENERAL and online vertex weighted matching; moreover, it can be
reduced to the latter by creating $k_{j}$ copies of each advertiser $j$. As
observed by [AGKM11], via this reduction, their algorithm for online vertex
weighted matching yields an optimal online algorithm for SINGLE-VALUED, see
Section 1.3 for additional comments on this.

In the decade following the conference version (FOCS 2005) of [MSVV07], search
engine companies generously invested in research on models derived from OBM
and adwords. Their motivation was two-fold: the substantial impact of [MSVV07]
and the emergence of a rich collection of digital ad tools. It will be
impossible to do justice to this substantial body of work, involving both
algorithmic and game-theoretic ideas; for a start, see the surveys [Meh13,
HT22].

###  1.3 Technical Ideas

Our proof of RANKING involves new combinatorial facts, given in Lemma 7 and
Corollary 8, which help prove the no-surpassing property. We also introduce a
new random variable, $u_{e}$, called threshold, corresponding to each edge
$e=(i,j)\in E$ in the underlying graph, see Definition 9. Besides leading to a
slight simplification of the analysis of RANKING, it sets the stage for
extension to SINGLE-VALUED via the truncated threshold random variable
described below. The key fact needed in the analysis of RANKING is that for
any edge $(i,j)$, its expected contribution is at least $(1-1/e)$, and our
proof of this fact crucially uses the threshold random variable for edge
$(i,j)$.

As noted in Section 1.2, RANKING has been extended all the way to SINGLE-
VALUED by [AGKM11]. Our goal is to extend it to GENERAL, and thereby address
SMALL. However, GENERAL is very different from SINGLE-VALUED in the following
sense. Whereas the latter can be reduced to online vertex weighted matching,
the former cannot. The reason is that the manner in which budget $B_{j}$ of
bidder $j$ gets partitioned into bids is not predictable in the former; it
depends on the queries, their order of arrival and the randomization executed
in a run of the algorithm. Therefore, in order to solve GENERAL, we will first
need to solve SINGLE-VALUED without reducing it to online vertex weighted
matching. An immediate advantage is that such an algorithm for SINGLE-VALUED
will require fewer random bits — only one random rank for each bidder $j$, as
opposed one rank for each of the $k_{j}$ copies of $j$.

This is done in Algorithm 20. Almost all of our new ideas, on the
probabilistic front, were obtained in the process analyzing this algorithm.
First, since vertex $j$ is not split into $k_{j}$ copies, we cannot talk about
the contribution of edges anymore. Even worse, we don’t have individual
vertices for keeping track of the revenue accrued from each match, as per the
scheme of [EFFS21]. Our algorithm gets around this difficulty by accumulating
revenue in the same “account” each time bidder $j$ gets matched. The
corresponding random variable, $r_{j}$, is called the total revenue of bidder
$j$, for want of a better name, see Remark 18. Lower bounding
$\mathbb{E}[r_{j}]$ is much more tricky than lower bounding the revenue of a
good in OBM, since it involves “teasing apart” the $k_{j}$ accumulations made
into this account; this is done in Lemma 28.

A replacement is also needed for the key lemma in the analysis of RANKING,
namely Lemma 14, which lower bounds the contribution of each edge. For this
purpose, we give the notion of a $j$-star, denoted $X_{j}$, which consists of
bidder $j$ together with edges to $k_{j}$ of its neighbors in $G$, see
Definition 24. The contribution of $j$-star $X_{j}$, is denoted by
$\mathbb{E}[X_{j}]$, which is also defined in Definition 24. Finally, using
the lower bound on $\mathbb{E}[r_{j}]$, Lemma 28 gives a lower
$\mathbb{E}[X_{j}]$ for every $j$-star, $X_{j}$. This lemma crucially uses a
new random variable, called truncated threshold, see Definition 23.

Next, we explain the reason for truncation in the definition of this random
variable. Consider bidder $j$ and a query $i_{l}$ that is desired by $j$.
Observe that in run $\mathcal{R}_{j}$, query $i_{l}$ can get a bid as large as
$B\cdot(1-{1\over e})$, where $B=\max_{k\in A}\\{b_{k}\\}$, whereas the
largest bid that $j$ can make to $i_{l}$ is $b_{j}\cdot(1-{1\over e})$; in
general, $b_{j}$ may be smaller than $B$. Now, $i_{l}$ contributes revenue to
$r_{j}$ only if $i_{l}$ is matched to $j$ in run $\mathcal{R}$, an event which
will definitely not happen if $u_{e_{l}}>b_{j}\cdot(1-{1\over e})$. Therefore,
whenever $u_{e_{l}}\in[b_{j}\cdot(1-{1\over e}),\ B\cdot(1-{1\over e})]$, the
contribution to $r_{j}$ is zero. By truncating $u_{e_{l}}$ to
$b_{j}\cdot(1-{1\over e})$, we have effectively changed the probability
density function of $u_{e_{l}}$ so that the probability of the event
$u_{e_{l}}\in[b_{j}\cdot(1-{1\over e}),B\cdot(1-{1\over e})]$ is now
concentrated at the event $u_{e_{l}}=b_{j}\cdot(1-{1\over e})$. From the
viewpoint of lower bounding the revenue accrued in $r_{j}$, the two
probability density functions are equivalent since the revenue accrued is zero
under both these events. On the other hand, the truncated random variable
enables us to apply the law of total expectation, in the proof of Lemma 28, in
the same way as it was done in the proof of lemma 12, without introducing more
difficulties.

The combinatorial facts given for RANKING, in Lemma 7 and Corollary 8, also
need to be extended for SINGLE-VALUED; this is done in Lemma 21 and Corollary
22. The distinction is that the former facts are based on sets and the latter
on multisets. In both cases, these facts help establish the no-surpassing
property.

Finally, Algorithm 35 for GENERAL needs to get around the structural
difficulties mentioned in Section 5.1. The idea of “fake” money helps get
around this problem for the special case of SMALL, since for SMALL, the fake
money can be upper-bounded in the worst case.

##  2 Preliminaries

Online Bipartite Matching (OBM): Let $B$ be a set of $n$ buyers and $S$ a set
of $n$ goods. A bipartite graph $G=(B,S,E)$ is specified on vertex sets $B$
and $S$, and edge set $E$, where for $i\in B,\ j\in S$, $(i,j)\in E$ if and
only if buyer $i$ likes good $j$. $G$ is assumed to have a perfect matching
and therefore each buyer can be given a unique good she likes. Graph $G$ is
revealed in the following manner. The $n$ goods are known up-front. On the
other hand, the buyers arrive one at a time, and when buyer $i$ arrives, the
edges incident at $i$ are revealed.

We are required to design an online algorithm $\mathcal{A}$ in the following
sense. At the moment a buyer $i$ arrives, the algorithm needs to match $i$ to
one of its unmatched neighbors, if any; if all of $i$’s neighbors are matched,
$i$ remains unmatched. The difficulty is that the algorithm does not “know”
the edges incident at buyers which will arrive in the future and yet the size
of the matching produced by the algorithm will be compared to the best off-
line matching; the latter of course is a perfect matching. The formal measure
for the algorithm is defined in Section 2.1.

General Adwords Problem (GENERAL): Let $A$ be a set of $m$ advertisers, also
called bidders, and $Q$ be a set of $n$ queries. A bipartite graph $G=(Q,A,E)$
is specified on vertex sets $Q$ and $A$, and edge set $E$, where for $i\in Q$
and $j\in A$, $(i,j)\in E$ if and only if bidder $j$ is interested in query
$i$. Each query $i$ needs to be matched666Clearly, this is not a matching in
the usual sense, since a bidder may be matched to several queries. to at most
one bidder who is interested in it. For each edge $(i,j)$, bidder $j$ knows
his bid for $i$, denoted by $\mbox{\rm bid}(i,j)\in\mathbb{Z_{+}}$. Each
bidder also has a budget $B_{j}\in\mathbb{Z_{+}}$ which satisfies
$B_{j}\geq\mbox{\rm bid}(i,j)$, for each edge $(i,j)$ incident at $j$.

Graph $G$ is revealed in the following manner. The $m$ bidders are known up-
front and the queries arrive one at a time. When query $i$ arrives, the edges
incident at $i$ are revealed, together with the bids associated with these
edges. If $i$ gets matched to $j$, then the matched edge $(i,j)$ is assigned a
weight of $\mbox{\rm bid}(i,j)$. The constraint on $j$ is that the total
weight of matched edges incident at it be at most $B_{j}$. The objective is to
maximize the total weight of all matched edges at all bidders.

Adwords under Single-Valued Bidders (SINGLE-VALUED): SINGLE-VALUED is a
special case of GENERAL in which each bidder $j$ will make bids of a single
value, $b_{j}\in\mathbb{Z_{+}}$, for the queries he is interested in. If $i$
accepts $j$’s bid, then $i$ will be matched to $j$ and the weight of this
matched edge will be $b_{j}$. Corresponding to each bidder $j$, we are also
given $k_{j}\in\mathbb{Z_{+}}$, the maximum number of times $j$ can be matched
to queries. The objective is to maximize the total weight of matched edges.
Observe that the matching $M$ found in $G$ is a $b$-matching with the
$b$-value of each query $i$ being 1 and of advertiser $j$ being $k_{j}$.

Adwords under Small Bids (SMALL): SMALL is a special case of GENERAL in which
for each bidder $j$, each bid of $j$ is small compared to its budget.
Formally, we will capture this condition by imposing the following constraint.
For a valid instance $I$ of SMALL, define

$\mu(I)=\max_{j\in A}\ \ \left\\{{{\max_{(i,j)\in E}\ \\{\mbox{\rm
bid}(i,j)-1\\}}\over{B_{j}}}\right\\}.$

Then we require that

$\lim_{n(I)\rightarrow\infty}\ {\mu(I)}=0,$

where $n(I)$ denotes the number of queries in instance $I$.

###  2.1 The competitive ratio of online algorithms

We will define the notion of competitive ratio of a randomized online
algorithm in the context of OBM.

######  Definition 2.

Let $G=(B,S,E)$ be a bipartite graph as specified above. The competitive ratio
of a randomized algorithm $\mathcal{A}$ for OBM is defined to be:

$c(\mathcal{A})=\min_{G=(B,S,E)}\min_{{{\rho}}(B)}\
{\frac{\mathbb{E}[\mathcal{A}(G,{{\rho}}(B))]}{n}},$

where $\mathbb{E}[\mathcal{A}(G,{{\rho}}(B))]$ is the expected size of
matching produced by $\mathcal{A}$; the expectation is over the random bits
used by $\mathcal{A}$. We may assume that the worst case graph and the order
of arrival of buyers, given by ${{\rho}}(B)$, are chosen by an adversary who
knows the algorithm. It is important to note that the algorithm is provided
random bits after the adversary makes its choices.

######  Remark 3.

For each problem studied in this paper, we will assume that the offline
matching is complete. It is easy to extend the arguments, without changing the
competitive ratio, in case the offline matching is not complete. As an
example, this is done for OBM in Remark 17.

##  3 Online Bipartite Matching: RANKING

Algorithm 4 presents an optimal algorithm for OBM. Note that this algorithm
picks a random permutation of goods only once. Its competitive ratio is
$(1-{\frac{1}{e}})$, as shown in Theorem 16. Furthermore, as shown in [KVV90],
it is an optimal online bipartite matching algorithm: no randomized algorithm
can do better, up to an $o(1)$ term.

We will analyze Algorithm 6 which is equivalent to Algorithm 4 and operates as
follows. Before the execution of Step (1), the adversary determines the order
in which buyers will arrive, say ${{\rho}}(B)$. In Step (1), each good $j$ is
assigned a price $p_{j}=e^{w_{j}-1}$, where $w_{j}$, called the rank of $j$,
is picked at random from $[0,1]$; observe that $p_{j}\in[{1\over e},1]$. In
Step (2), buyers will arrive in the order ${{\rho}}(B)$, picked by the
adversary, and will be matched to the cheapest available good. With
probability 1 all $n$ prices are distinct and sorting the goods by increasing
prices results in a random permutation. Furthermore, since Algorithm 6 uses
this sorted order only and is oblivious of the actual prices, it is equivalent
to Algorithm 4. As we will see, the random variables representing actual
prices are crucially important as well – in the analysis. We remark that for
the generalizations of OBM studied in this paper, the prices are used not only
in the analysis, but also by the algorithms.

######  Algorithm 4.

(Algorithm RANKING)

1. Initialization: Pick a random permutation, $\pi$, of the goods in $S$. 2. Online buyer arrival: When a buyer, say $i$, arrives, match her to the first unmatched good she likes in the order $\pi$; if none, leave $i$ unmatched. Output the matching, $M$, found.

###  3.1 Analysis of RANKING

We will use an economic setting for analyzing Algorithm 6 as follows. Each
buyer $i$ has unit-demand and 0/1 valuations over the goods she likes, i.e.,
she accrues unit utility from each good she likes, and she wishes to get at
most one of them. The latter set is precisely the set of neighbors of $i$ in
$G$. If on arrival of $i$ there are several of these which are still
unmatched, $i$ will pick one having the smallest price 777As stated above,
with probability 1 there are no ties.. Therefore the buyers will maximize
their utility as defined below.

For analyzing this algorithm, we will define two sets of random variables,
$u_{i}$ for $i\in B$ and $r_{j}$, for $j\in S$. These will be called utility
of buyer $i$ and revenue of good $j$, respectively. Each run of RANKING
defines these random variables as follows. If RANKING matches buyer $i$ to
good $j$, then define $u_{i}=1-p_{j}$ and $r_{j}=p_{j}$, where $p_{j}$ is the
price of good $j$ in this run of RANKING. Clearly, $p_{j}$ is also a random
variable, which is defined by Step (1) of the algorithm. If $i$ remains
unmatched, define $u_{i}=0$, and if $j$ remains unmatched, define $r_{j}=0$.
Observe that for each good $j$, $p_{j}\in[{1\over e},1]$ and for each buyer
$i$, $u_{i}\in[0,1-{1\over e}]$. Let $M$ be the matching produced by RANKING
and let random variable $|M|$ denote its size.

Lemma 5 pulls apart the contribution of each matched edge $(i,j)$ into $u_{i}$
and $r_{j}$. Next, we established in Lemma 14 that for each edge $(i,j)$ in
the graph, the total expected contribution of $u_{i}$ and $r_{j}$ is at least
$1-{1\over e}$. Then, linearity of expectation allows us to reassemble the
$2n$ terms in the right hand side of Lemma 5 so they are aligned with a
perfect matching in $G$, and this yields Theorem 16.

######  Lemma 5.

$\mathbb{E}[|M|]\ =\sum_{i}^{n}{\mathbb{E}\left[{u_{i}}\right]}\ +\
\sum_{j}^{n}{\mathbb{E}[r_{j}]}.$

###### Proof.

By definition of the random variables,

$\mathbb{E}[|M|]\ =\mathbb{E}\left[\sum_{i=1}^{n}{u_{i}}\ +\
\sum_{j=1}^{n}{r_{j}}\right]\ =\sum_{i}^{n}{\mathbb{E}\left[{u_{i}}\right]}\
+\ \sum_{j}^{n}{\mathbb{E}[r_{j}]},$

where the first equality follows from the fact that if $(i,j)\in M$ then
$u_{i}+r_{j}=1$ and the second follows from linearity of expectation. ∎

######  Algorithm 6.

(Algorithm RANKING: Economic Viewpoint)

1. Initialization: $\forall j\in S$: Pick $w_{j}$ independently and uniformly from $[0,1]$.
Set price $p_{j}\leftarrow e^{w_{j}-1}$.
2. Online buyer arrival: When a buyer, say $i$, arrives, match her to the cheapest unmatched good she likes; if none, leave $i$ unmatched. Output the matching, $M$, found.

While running Algorithm 6, assume that the adversary has picked the order of
arrival of buyers, say ${{\rho}}(B)$, and Step (1) has been executed. We next
define several ways of executing Step (2). Let $\mathcal{R}$ denote the run of
Step (2) on the entire graph $G$. Corresponding to each good $j$, let $G_{j}$
denote graph $G$ with vertex $j$ removed. Define $\mathcal{R}_{j}$ to be the
run of Step (2) on graph $G_{j}$.

Lemma 7 and Corollary 8 establish a relationship between the sets of available
goods for a buyer $i$ in the two runs $\mathcal{R}$ and $\mathcal{R}_{j}$; the
latter is crucially used in the proof of Lemma 12. For ease of notation in
proving these two facts, let us renumber the buyers so their order of arrival
under ${{\rho}}(B)$ is $1,2,\ldots n$. Let $T(i)$ and $T_{j}(i)$ denote the
sets of unmatched goods at the time of arrival of buyer $i$ (i.e., just before
the buyer $i$ gets matched) in the graphs $G$ and $G_{j}$, in runs
$\mathcal{R}$ and $\mathcal{R}_{j}$, respectively. Similarly, let $S(i)$ and
$S_{j}(i)$ denote the set of unmatched goods that buyer $i$ is incident to in
$G$ and $G_{j}$, in runs $\mathcal{R}$ and $\mathcal{R}_{j}$, respectively.

We have assumed that Step (1) of Algorithm 6 has already been executed and a
price $p_{k}$ has been assigned to each good $k$. With probability 1, the
prices are all distinct. Let $F_{1}$ and $F_{2}$ be subsets of $S$ containing
goods $k$ such that $p_{k}<p_{j}$ and $p_{k}>p_{j}$, respectively.

######  Lemma 7.

For each $i$, $1\leq i\leq n$, the following hold:

  1. 1.

$(T_{j}(i)\cap F_{1})=(T(i)\cap F_{1})$.

  2. 2.

$(T_{j}(i)\cap F_{2})\subseteq(T(i)\cap F_{2})$.

###### Proof.

Clearly, in both runs, $\mathcal{R}$ and $\mathcal{R}_{j}$, any buyer having
an available good in $F_{1}$ will match to the most profitable one of these,
without even considering the rest of the goods. Since $j\notin F_{1}$, the two
runs behave in an identical manner on the set $F_{1}$, thereby proving the
first statement.

The proof of the second statement is by induction on $i$. The base case is
trivially true since $j\notin F_{2}$. Assume that the statement is true for
$i=k$ and let us prove it for $i=k+1$. By the first statement, we need to
consider only the case that there are no available goods for the $k^{th}$
buyer in $F_{1}$ in the runs $\mathcal{R}$ and $\mathcal{R}_{j}$. Assume that
in run $\mathcal{R}_{j}$, this buyer gets matched to good $l$; if she remains
unmatched, we will take $l$ to be null. Clearly, $l$ is the most profitable
good she is incident to in $T_{j}(k)$. Therefore, the most profitable good she
is incident to in run $\mathcal{R}$ is the best of $l$, the most profitable
good in $T(k)-T_{j}(k)$, and $j$, in case it is available. In each of these
cases, the induction step holds. ∎

In the corollary below, the first two statements follow from Lemma 7 and the
third statement follows from the first two.

######  Corollary 8.

For each $i$, $1\leq i\leq n$, the following hold:

  1. 1.

$(S_{j}(i)\cap F_{1})=(S(i)\cap F_{1})$.

  2. 2.

$(S_{j}(i)\cap F_{2})\subseteq(S(i)\cap F_{2})$.

  3. 3.

$S_{j}(i)\subseteq S(i)$.

Next we define a new random variable, $u_{e}$, for each edge $e=(i,j)\in E$.
This is called the threshold for edge $e$ and is given in Definition 9. It is
critically used in the proofs of Lemmas 12 and 14.

######  Definition 9.

Let $e=(i,j)\in E$ be an arbitrary edge in $G$. Define random variable,
$u_{e}$, called the threshold for edge $e$, to be the utility of buyer $i$ in
run $\mathcal{R}_{j}$. Clearly, $u_{e}\in[0,1-{1\over e}]$.

######  Property 10.

(No-Surpassing for OBM) Let $p_{j}$ be such that the bid of $j$, namely
$1-p_{j}$, is better than the best bid that buyer $i$ gets in run
$\mathcal{R}_{j}$. Then, in run $\mathcal{R}$, no bid to $i$ will surpass
$1-p_{j}$.

######  Lemma 11.

The No-Surpassing Property holds for OBM.

###### Proof.

Suppose the bid of $j$, namely $1-p_{j}$, is better than the best bid that
buyer $i$ gets in run $\mathcal{R}_{j}$. If so, $i$ gets no bid from $F_{1}$
in $\mathcal{R}_{j}$; observe that they are all higher than $1-p_{j}$. Now, by
the first part of Corollary 8, $i$ gets no bid from $F_{1}$ in run
$\mathcal{R}$ as well, i.e., in run $\mathcal{R}$, no bid to $i$ will surpass
$1-p_{j}$. ∎

######  Lemma 12.

Corresponding to each edge $(i,j)\in E$, the following hold.

  1. 1.

$u_{i}\geq u_{e}$, where $u_{i}$ and $u_{e}$ are the utilities of buyer $i$ in
runs $\mathcal{R}$ and $\mathcal{R}_{j}$, respectively.

  2. 2.

Let $z\in[0,1-{1\over e}]$. Conditioned on $u_{e}=z$, if $p_{j}<1-z$, then $j$
will definitely be matched in run $\mathcal{R}$.

###### Proof.

1). By the third statement of Corollary 8, $i$ has more options in run
$\mathcal{R}$ as compared to run $\mathcal{R}_{j}$, and therefore $u_{i}\geq
u_{e}$.

2). In run $\mathcal{R}$, if $j$ is already matched when $i$ arrives, there is
nothing to prove. Next assume that $j$ is not matched when $i$ arrives. The
crux of the matter is that by Lemma 11, the No-Surpassing Property holds.
Therefore, in run $\mathcal{R}$, $i$ will not have any option that is better
than $j$ and will therefore get matched to $j$. Since $1-p_{j}>z$,
$S_{j}(i)\cap F_{1}=\emptyset$. Therefore by the first statement of Corollary
8, $S(i)\cap F_{1}=\emptyset$. Since $i$ will get no bid better than $j$ in
$\mathcal{R}$, the no-surpassing property indeed holds and $i$ must get
matched to $j$. ∎

######  Remark 13.

The random variable $u_{e}$ is called threshold because of the second
statement of Lemma 12. It defines a value such that whenever $p_{j}$ is
smaller than this value, $j$ is definitely matched in run $\mathcal{R}$.

The intuitive reason for the next, and most crucial, lemma is the following.
The smaller $u_{e}$ is, the larger is the range of values for $p_{j}$, namely
$[0,1-u_{e})$, over which $(i,j)$ will be matched and $j$ will accrue revenue
of $p_{j}$. Integrating $p_{j}$ over this range, and adding
$\mathbb{E}[u_{i}]$ to it, gives the desired bound. Crucial to this argument
is the fact that $p_{j}$ is independent of $u_{e}$. This follows from the fact
that $u_{e}$ is determined by run $\mathcal{R}_{j}$ on graph $G_{j}$, which
does not contain vertex $j$.

######  Lemma 14.

Corresponding to each edge $(i,j)\in E$,

$\mathbb{E}[u_{i}+r_{j}]\geq 1-{\frac{1}{e}}.$

###### Proof.

By the first part of Lemma 12, $\mathbb{E}[u_{i}]\geq\mathbb{E}[u_{e}]$.

Next, we will lower bound $\mathbb{E}[r_{j}]$. Let $z\in[0,1-{1\over e}]$ and
let us condition on the event $u_{e}=z$. The critical observation is that
$u_{e}$ is determined by the run $\mathcal{R}_{j}$. This is conducted on graph
$G_{j}$, which does not contain vertex $j$. Therefore $u_{e}$ is independent
of $p_{j}$.

By the second part of Lemma 12, $r_{j}=p_{j}$ whenever $p_{j}<1-z$. We will
ignore the contribution to $\mathbb{E}[r_{j}]$ when $p_{j}\geq 1-z$. Let $w$
be s.t. $e^{w-1}=1-z$.

Now $p_{j}$ is obtained by picking $x$ uniformly at random from the interval
$[0,1]$ and outputting $e^{x-1}$. In particular, when $x\in[0,w)$,
$p_{j}<1-z$. If so, by the second part of Lemma 12, $j$ is matched and revenue
is accrued in $r_{j}$, see Figure 2. Therefore,

$\mathbb{E}[r_{j}~{}|~{}u_{e}=z]\geq\int_{0}^{w}{e^{x-1}\ dx}\ =\
e^{w-1}-{\frac{1}{e}}\ =\ 1-{\frac{1}{e}}-z.$

Let $f_{u_{e}}(z)$ be the probability density function of $u_{e}$; clearly,
$f_{u_{e}}(z)=0$ for $z\notin[0,1-{1\over e}]$. Therefore,

$\mathbb{E}[r_{j}]\ =\ \mathbb{E}[\mathbb{E}[r_{j}~{}|~{}u_{e}]]\ =\
\int_{z=0}^{1-1/e}{\mathbb{E}[r_{j}~{}|~{}u_{e}=z]\cdot f_{u_{e}}(z)dz}$
$\geq\ \int_{z=0}^{1-1/e}{\left(1-{\frac{1}{e}}-z\right)\cdot f_{u_{e}}(z)dz}\
\ =\ \ 1-{\frac{1}{e}}-\mathbb{E}[u_{e}],$

where the first equality follows from the law of total expectation and the
inequality follows from fact that we have ignored the contribution to
$\mathbb{E}[r_{j}~{}|~{}u_{e}]$ when $p_{j}\geq 1-z$. Hence we get

$\mathbb{E}[u_{i}+r_{j}]=\mathbb{E}[u_{i}]+\mathbb{E}[r_{j}]\geq
1-{\frac{1}{e}}.$

∎

Figure 2: The shaded area is a lower bound on
$\mathbb{E}[r_{j}~{}|~{}u_{e}=z]$.

######  Remark 15.

Observe that Lemma 14 is not a statement about $i$ and $j$ getting matched to
each other, but about the utility accrued by $i$ and the revenue accrued by
$j$ by being matched to various goods and buyers, respectively, over the
randomization executed in Step (1) of Algorithm 6.

######  Theorem 16.

The competitive ratio of RANKING is at least $1-{\frac{1}{e}}$.

###### Proof.

Let $P$ denote a perfect matching in $G$. The expected size of matching
produced by RANKING is

$\mathbb{E}\left[|M|\right]\ =\ \sum_{i}^{n}{\mathbb{E}\left[{u_{i}}\right]}\
+\ \sum_{j}^{n}{\mathbb{E}[r_{j}]}\ =\ \sum_{(i,j)\in
P}{\mathbb{E}[u_{i}+r_{j}]}\ \geq\ n\left(1-{\frac{1}{e}}\right),$

where the first equality uses Lemma 5, the second follows from linearity of
expectation and the inequality follows from Lemma 14 and the fact that
$|P|=n$. The theorem follows. ∎

######  Remark 17.

In case $G$ does not have a perfect matching, let $P$ denote a maximum
matching in $G$, of size $k$, say. Then summing
${\mathbb{E}\left[{u_{i}}\right]}$ and ${\mathbb{E}[r_{j}]}$ over the the
vertices $i$ and $j$ matched by $P$, we get that the expected size of matching
produced by RANKING is at least $k\left(1-{\frac{1}{e}}\right)$.

##  4 Algorithm for SINGLE-VALUED

Algorithm 20, which will be denoted by $\mathcal{A}_{2}$, is an online
algorithm for SINGLE-VALUED. Before execution of Step (1) of
$\mathcal{A}_{2}$, the order of arrival of queries, say ${{\rho}}(B)$, is
fixed by the adversary. We will define several random variables whose purpose
will be quite similar to that in RANKING and they will be given similar names
as well; however, their function is not as closely tied to these economics-
motivated names as in RANKING, see also Remark 18. Three of these random
variables are the price $p_{j}$ and total revenue $r_{j}$ of each bidder $j\in
A$, and the utility $u_{i}$ of each query $i\in Q$.

We now describe how values are assigned to these random variables in a run of
Algorithm 20. In Step (1), for each bidder $j$, $\mathcal{A}_{2}$ picks a
price $p_{j}\in[{1\over e},1]$ via the specified randomized process.
Furthermore, the revenue $r_{j}$ and degree $d_{j}$ of bidder $j$ are both
initialized to zero, the latter represents the number of times $j$ has been
matched. During the run of $\mathcal{A}_{2}$, $j$ will get matched to at most
$k_{j}$ queries; each match will add $b_{j}$ to the total revenue generated by
the algorithm. $b_{j}$ is broken into a revenue and a utility component, with
the former being added to $r_{j}$ and the latter forming $u_{i}$. At the end
of $\mathcal{A}_{2}$, $r_{j}$ will contain all the revenue accrued by $j$.

In Step (2), on the arrival of query $i$, we will say that bidder $j$ is
available if $(i,j)\in E$ and $d_{j}<k_{j}$. At this point, for each available
bidder $j$, the effective bid of $j$ for $i$ is defined to be $\mbox{\rm
ebid}(j)=b_{j}\cdot(1-p_{j})$; clearly, $\mbox{\rm
ebid}(j)\in[0,b_{j}\cdot\left(1-{1\over e}\right)]$. Query $i$ accepts the
bidder whose effective bid is the largest. If there are no bids, matching $M$
remains unchanged. If $i$ accepts $j$’s bid, then edge $(i,j)$ is added to
matching $M$ and the weight of this edge is set to $b_{j}$. Furthermore, the
utility of $i$, $u_{i}$, is defined to be $\mbox{\rm ebid}(j)$ and the revenue
$r_{j}$ of $j$ is incremented by $b_{j}\cdot p_{j}$. Once all queries are
processed, matching $M$ and its weight $W$ are output.

######  Remark 18.

The economics-based names of random variables used in our proof of RANKING
came from [EFFS21]. Although we have used the same names for similar random
variables in Sections 4 and 5.2, for SINGLE-VALUED and GENERAL, the reader
should not attribute an economic interpretation to these the names as was done
in RANKING 888We failed to come up with more meaningful names for these random
variables and therefore have stuck to the old names..

###  4.1 Analysis of Algorithm 20

For the analysis of Algorithm $\mathcal{A}_{2}$, we will use the random
variables $W$, $p_{j},r_{j}$ and $u_{i}$ defined above; their values are fixed
during the execution of $\mathcal{A}_{2}$. In addition, corresponding to each
edge $e=(i,j)\in E$, in Definition 23, we will introduce a new random
variable, $u_{e}$, which will play a central role.

######  Lemma 19.

$\mathbb{E}[W]\ =\sum_{i}^{n}{\mathbb{E}\left[{u_{i}}\right]}\ +\
\sum_{j}^{m}{\mathbb{E}[r_{j}]}.$

###### Proof.

For each edge $(i,j)\in M$, its contribution to $W$ is $b_{j}$. Furthermore,
the sum of $u_{i}$ and the contribution of $(i,j)$ to $r_{j}$ is also $b_{j}$.
This gives the first equality below. The second equality follows from
linearity of expectation.

$\mathbb{E}[W]\ =\mathbb{E}\left[\sum_{i=1}^{n}{u_{i}}\ +\
\sum_{j=1}^{m}{r_{j}}\right]\ =\sum_{i}^{n}{\mathbb{E}\left[{u_{i}}\right]}\
+\ \sum_{j}^{m}{\mathbb{E}[r_{j}]},$

∎

######  Algorithm 20.

($\mathcal{A}_{2}$: Algorithm for SINGLE-VALUED)
1. Initialization: $M\leftarrow\emptyset$.
$\forall j\in A$, do: (a) Pick $w_{j}$ uniformly from $[0,1]$ and set price
$p_{j}\leftarrow e^{w_{j}-1}$. (b) $r_{j}\leftarrow 0$. (c) $d_{j}\leftarrow
0$.
2. Query arrival: When query $i$ arrives, do: (a) $\forall j\in A$ s.t. $(i,j)\in E$ and $d_{j}<k_{j}$ do: i. $\mbox{\rm ebid}(j)\leftarrow b_{j}\cdot(1-p_{j})$. ii. Offer effective bid of $\mbox{\rm ebid}(j)$ to $i$. (b) Query $i$ accepts the bidder whose effective bid is the largest.
(If there are no bids, matching $M$ remains unchanged.)
If $i$ accepts $j$’s bid, then do: i. Set utility: $u_{i}\leftarrow
b_{j}\cdot(1-p_{j})$. ii. Update revenue: $r_{j}\leftarrow r_{j}+b_{j}\cdot
p_{j}$. iii. Update degree: $d_{j}\leftarrow d_{j}+1$. iv. Update matching:
$M\leftarrow M\cup(i,j)$. Define the weight of $(i,j)$ to be $b_{j}$. (c)
Output: Output matching $M$ and its total weight $W$.

As in the case of RANKING, we will define several runs of Algorithm 20. In
these runs, we will assume Step (1) is executed once. We next define several
ways of executing Step (2). Let $\mathcal{R}$ denote the run of Step (2) on
the entire graph $G$. Corresponding to each bidder $j\in A$, let $G_{j}$
denote graph $G$ with bidder $j$ removed. Define $\mathcal{R}_{j}$ to be the
run of Step (2) on graph $G_{j}$.

Analogous to Lemma 7 and Corollary 8 proved for RANKING, we will prove Lemma
21 and Corollary 22, which establish a relationship between the available
bidders for a query $i$ in the two runs $\mathcal{R}$ and $\mathcal{R}_{j}$.
One difference is that now bidders are available in multiplicity and therefore
we will have to use the notion of a multiset rather than a set; this is
established next.

A multiset contains elements with multiplicity. Let $A$ and $B$ be two
multisets over $n$ elements $\\{1,2,\ldots n\\}$, and let $a_{i}\geq 0$ and
$b_{i}\geq 0$ denote the multiplicities of element $i$ in $A$ and $B$,
respectively. We will say that $A\subseteq B$ if for each $i$, $a_{i}\leq
b_{i}$, and $A=B$ if for each $i$, $a_{i}=b_{i}$. We will say that $i\in A$ if
$a_{i}\geq 1$. We will define $A\cap B$ to be the multiset containing each
element $i$ exactly $\min\\{a_{i},b_{i}\\}$ times, and $A-B$ to be the
multiset containing each element $i$ exactly $\max\\{a_{i}-b_{i},0\\}$ times.

As before, let us renumber the queries so their order of arrival under
${{\rho}}(B)$ is $1,2,\ldots n$. Let $T(i)$ and $T_{j}(i)$ denote the
multisets of available bidders at the time of arrival of query $i$ (i.e., just
before the query $i$ gets matched) in runs $\mathcal{R}$ and
$\mathcal{R}_{j}$, respectively. In particular, $T(1)$ will contain $k_{l}$
copies of $l$ for each bidder $l$ and $T_{j}(1)$ will contain $k_{l}$ copies
of $l$ for each bidder $l$, other than $j$. Similarly, let $S(i)$ and
$S_{j}(i)$ denote the projections of $T(i)$ and $T_{j}(i)$ on the neighbors of
$i$ in $G$ and $G_{j}$, respectively.

We have assumed that Step (1) of Algorithm 6 has already been executed and a
price $p_{k}$ has been assigned to each bidder $k$. The effective bid of
bidder $k$ is $\mbox{\rm ebid}(k)=b_{k}\cdot(1-p_{k})$. With probability 1,
the effective bids of all bidders are distinct. Let $F_{1}$ be the multiset
containing $k_{l}$ copies of $l$ for each $l\in A$ such that
$b_{l}\cdot(1-p_{l})>b_{j}\cdot(1-p_{j})$. Similarly, let $F_{2}$ be the
multiset containing $k_{l}$ copies of $l$ for each $l\in A$ such that and
$b_{l}\cdot(1-p_{l})<b_{j}\cdot(1-p_{j})$. Observe that $j$ is not contained
in either multiset.

######  Lemma 21.

For each $i$, $1\leq i\leq n$, the following hold:

  1. 1.

$(T_{j}(i)\cap F_{1})=(T(i)\cap F_{1})$.

  2. 2.

$(T_{j}(i)\cap F_{2})\subseteq(T(i)\cap F_{2})$.

###### Proof.

1). Clearly, in both runs, $\mathcal{R}$ and $\mathcal{R}_{j}$, any query
having an available bidder in $F_{1}$ will match to the most profitable one of
these, without even considering the rest of the bidders. Since $j\notin
F_{1}$, the two runs behave in an identical manner on the set $F_{1}$, thereby
proving the first statement.

2). The proof is by induction on $i$. The base case is trivially true because
$(T_{j}(1)\cap F_{2})=(T(1)\cap F_{2})$, since $j\notin F_{2}$. Assume that
the statement is true for $i=k$ and let us prove it for $i=k+1$. By the first
statement, we need to consider only the case that there are no available
bidders for the $k^{th}$ query in $F_{1}$ in the runs $\mathcal{R}$ and
$\mathcal{R}_{j}$. Assume that in run $\mathcal{R}_{j}$, this query gets
matched to bidder $l$; if it remains unmatched, we will take $l$ to be null.
Clearly, $l$ is the most profitable bidder it is incident to in $T_{j}(k)$.
Therefore, the most profitable bidder it is incident to in run $\mathcal{R}$
is the best of $l$, the most profitable bidder in $T(k)-T_{j}(k)$, and $j$, in
case it is available. In each of these cases, the induction step holds. ∎

In the corollary below, the first two statements follow from Lemma 21 and the
third statement follows from the first two statements.

######  Corollary 22.

For each $i$, $1\leq i\leq n$, the following hold:

  1. 1.

$(S_{j}(i)\cap F_{1})=(S(i)\cap F_{1})$.

  2. 2.

$(S_{j}(i)\cap F_{2})\subseteq(S(i)\cap F_{2})$.

  3. 3.

$S_{j}(i)\subseteq S(i)$.

Next we define a new random variable, $u_{e}$, for each edge $e=(i,j)\in E$.
This is called the truncated threshold for edge $e$ and is given in Definition
23. It is critically used in the proofs of Lemmas 27 and 28.

######  Definition 23.

Let $e=(i,j)\in E$ be an arbitrary edge in $G$. Define random variable,
$u_{e}$, called the truncated threshold for edge $e$, to be
$u_{e}=\min\\{{ut}_{i},\ b_{j}\cdot\left(1-{\frac{1}{e}}\right)\\}$, where
${ut}_{i}$ is the utility of query $i$ in run $\mathcal{R}_{j}$.

######  Definition 24.

Let $j\in A$. Henceforth, we will denote $k_{j}$ by $k$ in order to avoid
triple subscripts. Let $i_{1},\ldots,i_{k}$ be queries such that for $1\leq
l\leq k$, $(i_{l},j)\in E$. Then $(j;\ i_{1},\ldots,i_{k})$ is called a
$j$-star. Let $X_{j}$ denote this $j$-star. The contribution of $X_{j}$ to
$\mathbb{E}[W]$ is $\mathbb{E}[r_{j}]+\sum_{l=1}^{k}{\mathbb{E}[u_{i_{l}}]}$,
and it will be denote by $\mathbb{E}[X_{j}]$.

Corresponding to $j$-star $X_{j}=(j;\ i_{1},\ldots,i_{k})$, denote by $e_{l}$
the edge $(i_{l},j)\in E$, for $1\leq l\leq k$. Furthermore, let $u_{e_{l}}$
denote the truncated threshold random variable corresponding to $e_{l}$.

######  Property 25.

(No-Surpassing for SINGLE-VALUED) Let $p_{j}$ be such that the effective bid
of $j$ to $i_{l}$, namely $\mbox{\rm ebid}(j)=b_{j}\cdot(1-p_{j})$, is better
than the best bid that query $i_{l}$ gets in run $\mathcal{R}_{j}$. Then, in
run $\mathcal{R}$, no bid to $i_{l}$ will surpass $b_{j}\cdot(1-p_{j})$.

######  Lemma 26.

The No-Surpassing Property holds for SINGLE-VALUED.

###### Proof.

Suppose the bid of $j$, namely $b_{j}\cdot(1-p_{j})$, is better than the best
bid that buyer $i$ gets in run $\mathcal{R}_{j}$. If so, $i$ gets no bid from
$F_{1}$ in $\mathcal{R}_{j}$; observe that they are all higher than
$b_{j}\cdot(1-p_{j})$. Now, by the first part of Corollary 22, $i$ gets no bid
from $F_{1}$ in run $\mathcal{R}$ as well, i.e., in run $\mathcal{R}$, no bid
to $i$ will surpass $b_{j}\cdot(1-p_{j})$. ∎

######  Lemma 27.

Corresponding to $j$-star $X_{j}=(j;\ i_{1},\ldots,i_{k})$, the following
hold.

  * •

For $1\leq l\leq k$, $u_{i_{l}}\geq u_{e_{l}}$.

###### Proof.

By the third statement of Corollary 22, $i_{l}$ has more options in run
$\mathcal{R}$ as compared to run $\mathcal{R}_{j}$. Furthermore, the
truncation of the random variable only aids the inequality needed and
therefore $u_{i_{l}}\geq u_{e_{l}}$. ∎

Our next goal is to lower bound the contribution of an arbitrary $j$-star,
$\mathbb{E}[X_{j}]$, which in turn involves lower bounding
$\mathbb{E}[r_{j}]$. The latter crucially uses the fact that $p_{j}$ is
independent of $u_{e_{l}}$. This follows from the fact that $u_{e_{l}}$ is
determined by run $\mathcal{R}_{j}$ on graph $G_{j}$, which does not contain
vertex $j$.

######  Lemma 28.

Let $j\in A$ and let $X_{j}=(j;\ i_{1},\ldots,i_{k})$ be a $j$-star. Then

$\mathbb{E}[X_{j}]\ \geq\ k\cdot b_{j}\cdot\left(1-{\frac{1}{e}}\right).$

###### Proof.

We will first lower bound $\mathbb{E}[r_{j}]$. Let $f_{U}(b_{j}\cdot
z_{1},\ldots b_{j}\cdot z_{k})$ be the joint probability density function of
$(u_{e_{1}},\ldots u_{e_{k}})$; clearly, $f_{U}(b_{j}\cdot z_{1},\ldots
b_{j}\cdot z_{k})$ can be non-zero only if $z_{l}\in[0,1-{1\over e}]$, for
$1\leq l\leq k$. By the law of total expectation,

$\mathbb{E}[r_{j}]\
=\int_{(z_{1},\ldots,z_{k})}{\mathbb{E}[r_{j}~{}|~{}u_{e_{1}}=b_{j}\cdot
z_{1},\ldots,u_{e_{k}}=b_{j}\cdot z_{k}]\cdot f_{U}(b_{j}\cdot z_{1},\ldots
b_{j}\cdot z_{k})\ dz_{1}\ldots dz_{k}},$

where the integral is over $z_{l}\in[0,\left(1-{\frac{1}{e}}\right)]$, for
$1\leq l\leq k$.

For lower-bounding the conditional expectation in this integral, let
$w_{l}\in[0,1]$ be s.t. $e^{w_{l}-1}=1-z_{l}$, for $1\leq l\leq k$. For
$x\in[0,1]$, define the set $S(x)=\\{l\ |\ 1\leq l\leq k\ \mbox{and}\
x<w_{l}\\}$.

######  Claim 29.

Conditioned on $(u_{e_{1}}=b_{j}\cdot z_{1},\ldots,u_{e_{k}}=b_{j}\cdot
z_{k})$, if $p_{j}=e^{x-1}$, then the degree of $j$ at the end of Algorithm
$\mathcal{A}_{2}$ is at least $|S(x)|$, i.e., the contribution to $r_{j}$ in
this run was $\geq b_{j}\cdot p_{j}\cdot|S(x)|$.

###### Proof.

Suppose $l\in S(x)$, then $x<w_{l}$. In run $\mathcal{R}_{j}$, the maximum
effective bid that $i_{l}$ received has value $b_{j}\cdot z_{l}$. In run
$\mathcal{R}$, if at the arrival of query $i_{l}$, $j$ is already fully
matched, the contribution to $r_{j}$ in this run was $k\cdot b_{j}\cdot p_{j}$
and the claim is obviously true. If not, then since $x<w_{l}$,
$b_{j}\cdot(1-p_{j})>b_{j}\cdot z_{l}$. The crux of the matter is that by
Lemma 26, the No-Surpassing Property holds. Therefore, query $i_{l}$ will
receive its largest effective bid from $j$, $i_{l}$ will get matched to it,
and $r_{j}$ will be incremented by $b_{j}\cdot p_{j}$. The claim follows. ∎

For $1\leq l\leq k$, define indicator functions
$I_{l}:[0,1]\rightarrow\\{0,1\\}$ as follows.

$I_{l}(x)\ \ =\ \begin{cases}1&\text{if }x<w_{l},\\\
0&\text{otherwise.}\end{cases}$

Clearly, $|S(x)|=\sum_{l=1}^{k}{I_{j}(x)}$. By Claim 29,

$\mathbb{E}[r_{j}~{}|~{}u_{e_{1}}=b_{j}\cdot z_{1},\ldots,u_{e_{k}}=b_{j}\cdot
z_{k}]\ \geq\ b_{j}\cdot\int_{0}^{1}{|S(x)|\cdot e^{x-1}\ dx}$

$=\ b_{j}\cdot\int_{0}^{1}{\sum_{l=1}^{k}{I_{l}(x)}\cdot e^{x-1}\ dx}\ =\
b_{j}\cdot\sum_{l=1}^{k}{\int_{0}^{1}{{I_{l}(x)}\cdot e^{x-1}}\ dx}\ =\
b_{j}\cdot\sum_{l=1}^{k}{\int_{0}^{w_{l}}{e^{x-1}\ dx}}$

$=\ b_{j}\cdot\sum_{l=1}^{k}{\left(e^{w_{l}-1}-{\frac{1}{e}}\right)}\ =\
b_{j}\cdot\sum_{l=1}^{k}\left(1-{\frac{1}{e}}-z_{l}\right).$

Since $I_{l}(x)=0$ for $x\in[w_{l},1]$, we get that
$\int_{0}^{1}{{I_{l}(x)}\cdot e^{x-1}}\ dx\ =\ \int_{0}^{w_{l}}{e^{x-1}}\ dx$;
this fact has been used above. Therefore,

$\mathbb{E}[r_{j}]\
=\int_{(z_{1},\ldots,z_{k})}{\mathbb{E}[r_{j}~{}|~{}u_{e_{1}}=b_{j}\cdot
z_{1},\ldots,u_{e_{k}}=b_{j}\cdot z_{k}]\cdot f_{U}(b_{j}\cdot z_{1},\ldots
b_{j}\cdot z_{k})\ dz_{1}\ldots dz_{k}}$

$\geq
b_{j}\cdot\int_{(z_{1},\ldots,z_{k})}{\sum_{l=1}^{k}\left(1-{\frac{1}{e}}-z_{l}\right)\cdot
f_{U}(b_{j}\cdot z_{1},\ldots b_{j}\cdot z_{k})\ dz_{1}\ldots dz_{k}}$

$=\ k\cdot
b_{j}\cdot\left(1-{\frac{1}{e}}\right)-\sum_{l=1}^{k}{\mathbb{E}[u_{e_{l}}]},$

where both integrals are over $z_{l}\in[0,\left(1-{\frac{1}{e}}\right)]$, for
$1\leq l\leq k$.

By Lemma 27, $\mathbb{E}[u_{i_{l}}]\geq\mathbb{E}[u_{e_{l}}]$, for $1\leq
l\leq k$. Hence we get

$\mathbb{E}[X_{j}]\ =\
\mathbb{E}[r_{j}]+\sum_{l=1}^{k}{\mathbb{E}[u_{i_{l}}]}\ \geq\ k\cdot
b_{j}\cdot\left(1-{\frac{1}{e}}\right),$

∎

######  Theorem 30.

The competitive ratio of Algorithm $\mathcal{A}_{2}$ is at least
$1-{\frac{1}{e}}$. Furthermore, it is budget-oblivious.

###### Proof.

Let $P$ denote a maximum weight $b$-matching in $G$, computed in an offline
manner. By the assumption made in Remark 3, its weight is

$w(P)=\sum_{j=1}^{m}{k_{j}\cdot b_{j}}.$

Let $T_{j}$ denote the $j$-star, under $P$, corresponding to each $j\in A$.
The expected weight of matching produced by $\mathcal{A}_{2}$ is

$\mathbb{E}\left[W\right]\ =\ \sum_{i=1}^{n}{\mathbb{E}\left[{u_{i}}\right]}\
+\ \sum_{j=1}^{m}{\mathbb{E}[r_{j}]}\ =\ \sum_{j=1}^{m}{\mathbb{E}[T_{j}]}\
\geq\ \sum_{j=1}^{m}{b_{j}\cdot k_{j}}\left(1-{\frac{1}{e}}\right)\ =\
\left(1-{\frac{1}{e}}\right)\cdot w(P),$

where the first equality uses Lemma 5, the second follows from linearity of
expectation and the inequality follows from Lemma 28.

Finally, Algorithm $\mathcal{A}_{2}$ is budget-oblivious because it does not
need to know $k_{j}$ for bidders $j$; it only needs to know during a run
whether the $k_{j}$ bids available to bidder $j$ have been exhausted. The
theorem follows. ∎

##  5 Algorithm for SMALL, After Assuming No-Surpassing Property

Two new difficulties arise for the problem GENERAL The first is the inherent
structural difficulty described in Section 5.1. Second, since bidders can have
different bids for different queries, the no-surpassing property does not hold
anymore, see Example 31.

######  Example 31.

Assume that in the given instance for GENERAL, $j,j^{\prime}$ are two of the
bidders, and $1,\ldots,k$ are $k$ of the queries, where $k$ is a large number.
Assume $\mbox{\rm bid}(l,j)=\alpha$ for $1\leq l\leq k$ and $\mbox{\rm
bid}(l,j^{\prime})=\alpha-1$ for $1\leq l\leq k-1$. Further, assume that
$\mbox{\rm bid}(k,j^{\prime})=(\alpha-1)\cdot(k-1)$. Let the budgets be
$B_{j}=\alpha\cdot k$ and $B_{j^{\prime}}=(\alpha-1)\cdot(k-1)$.

Now consider a run in which $p_{j}=p_{j^{\prime}}=p$. Assume that in run
$\mathcal{R}_{j}$, the best effective bid to $1,\ldots,k-1$ comes from
$j^{\prime}$, and in run $\mathcal{R}_{j}$, the best effective bid to
$1,\ldots,k-1$ comes from $j$. In run $\mathcal{R}_{j}$, the budget of
$j^{\prime}$ is exhausted when $k$ arrives and assume that $k$ does not get
any bids, making $u_{e}=0$ for $e=(k,j)$. Now in run $\mathcal{R}$, $\mbox{\rm
ebid}(k,j)=\alpha(1-p)$ and $\mbox{\rm
ebid}(k,j^{\prime})=(\alpha-1)\cdot(k-1)\cdot(1-p)$. Thus, even though
$\mbox{\rm ebid}(k,j)>u_{e}$, $k$ will be matched to $j^{\prime}$ and not $j$.
Clearly, this phenomenon will hold for all runs in which $p_{j^{\prime}}$ is
not too much larger than $p_{j}$.

For the rest of this section, we will make this assumption:

Assumption of No-Surpassing for GENERAL: Let $p_{j}$ be such that the
effective bid of $j$ to $i_{l}$, namely $\mbox{\rm ebid}(i_{l},j)=\mbox{\rm
bid}(i_{l},j)\cdot(1-p_{j})$, is better than the best bid that query $i_{l}$
gets in run $\mathcal{R}_{j}$. Then, in run $\mathcal{R}$, no bid to $i_{l}$
will surpass $\mbox{\rm bid}(i_{l},j)\cdot(1-p_{j})$.

Section 5.2 presents an algorithm for GENERAL, using fake money; the above-
stated assumption is used in its analysis, in particular in the proof of Claim
38. Section 5.4 shows that by upper bounding the fake money used in the worst
case, we get an optimal algorithm for SMALL, again based on the above-stated
assumption.

###  5.1 Structural Difficulties in GENERAL

To describe the structural difficulties in GENERAL, we provide three instances
in Example 32. In order to obtain a completely unconditional result, we would
need to adopt the following convention: assume bidder $j$ has $L_{j}$ money
leftover and impression $i$ just arrived. Assume that $j$’s bid for $i$ is
$\mbox{\rm bid}(i,j)$. If $\mbox{\rm bid}(i,j)>L_{j}$, then $j$ should not be
allowed to bid for $i$, since $j$ has insufficient money.

Under this convention, it is easy to see that even a randomized algorithm will
accrue only $\$W$ expected revenue on at least one of the instances given in
Example 32, provided it is greedy, i.e., if a match is possible, it does not
rescind this possibility; the latter condition is a simple way of ensuring
that the algorithm is “fine tuned” for a particular type of example. Note that
the optimal for each instance is $\$2W$.

######  Example 32.

Let $W\in\mathbb{Z_{+}}$ be a large number. We define three instances of
GENERAL, each having two bidders, $b_{1}$ and $b_{2}$, with budgets of $\$W$
each. Instances $I_{1}$ and $I_{2}$ have $W+1$ queries, where for the first
$W$ queries, both bidders bid $\$1$ each. For the last query, under $I_{1}$,
$b_{1}$ bids $\$W$ and $b_{2}$ is not interested. Under $I_{2}$, $b_{2}$ bids
$\$W$ and $b_{1}$ is not interested. Instance $I_{3}$ has $2W$ queries and
both bidders bid $\$1$ for each of them.

Therefore, to obtain a non-trivial competitive ratio, bidder $j$ must be
allowed to bid for $i$ even if $L_{j}<\mbox{\rm bid}(i,j)$. This amounts to
the use of free disposal, since $j$ will be allowed to obtain query $i$ for
less money than its value for $i$. Next, let’s consider a second convention:
if $L_{j}<\mbox{\rm bid}(i,j)$, then $j$ will bid $L_{j}$ for $i$. As stated
in Remark 40, this convention is not supported by our proof technique, since
Claim 38 fails to hold, breaking the proof of Lemma 37 and hence Lemma 39.

This led us to a third convention: if $L_{j}<\mbox{\rm bid}(i,j)$, then $j$
will bid $L_{j}$ real money and $\mbox{\rm bid}(i,j)-L_{j}$ “fake” money for
$i$. As a result, the total revenue of the algorithm consists of real money as
well as fake money; in Algorithm 35, these are denoted by $W$ and $W_{f}$,
respectively. The problem now is that Lemma 39, which compares the total
revenue of the algorithm, namely $W+W_{f}$, with the optimal offline revenue,
does not yield the competitive ratio of Algorithm 35. Remark 40 explains why
our proof technique does not allow us to dispense with the use of fake money.

We note that when Algorithm 35 is run on instances of OBM, it reduces to
RANKING. Therefore, it is indeed a (simple) extension of RANKING to GENERAL.

###  5.2 Algorithm for GENERAL

Algorithm 35, which will be denoted by $\mathcal{A}_{3}$, is an attempt at
online algorithm for GENERAL. As stated in Section 5.1, because of the use of
fake money, we will not be able to give a competitive ratio for it, instead,
in Lemma 39, we will compare the sum of real and fake money spent by the
algorithm with the real money spent by an optimal offline algorithm.

In algorithm $\mathcal{A}_{3}$, $L_{j}\in\mathbb{Z_{+}}$ will denote bidder
$j$’s leftover budget; it is initialized to $B_{j}$. At the arrival of query
$i$, bidder $j$ will bid for $i$ if $(i,j)\in E$ and $L_{j}>0$. In general,
$i$ will receive a number of bids. The exact procedure used by $i$ to accept
one of these bids is given in algorithm $\mathcal{A}_{3}$; its steps are self-
explanatory. If $i$ accepts $j$’s bid then $i$ is matched to $j$, the edge
$(i,j)$ is assigned a weight of $\mbox{\rm bid}(i,j)$ and $L_{j}$ is
decremented by $\min\\{L_{j},\mbox{\rm bid}(i,j)\\}$.

Note that we do not require that there is sufficient left-over money, i.e.,
$L_{j}\geq\mbox{\rm bid}(i,j)$, for $j$ to bid for $i$. In case
$L_{j}<\mbox{\rm bid}(i,j)$ and $i$ accepts $j$’s bid, then $\mbox{\rm
bid}(i,j)-L_{j}$ of the money paid by $j$ for $i$ is fake money; this will be
accounted for by incrementing $W_{f}$ by $\mbox{\rm bid}(i,j)-L_{j}$. The
rest, namely $L_{j}$, is real money and is added to $W$. If $\mbox{\rm
bid}(i,j)\geq L_{j}$ and $i$ accepts $j$’s bid, then $L_{j}$ becomes zero and
$j$ does not bid for any future queries. At the end of the algorithm, random
variable $W$ denotes the total real money spent and $W_{f}$ denotes the total
fake money spent.

The offline optimal solution to this problem is defined to be a matching of
queries to advertisers that maximizes the weight of the matching; this is done
with full knowledge of graph $G$. As stated in Remark 3, we will assume that
under such a matching, $P$, the budget $B_{j}$ of each bidder $j$ is fully
spent, i.e., $w(P)=\sum_{j=1}^{m}{B_{j}}$.

###  5.3 Analysis of Algorithm 35

######  Lemma 33.

$\mathbb{E}[W+W_{f}]\ =\sum_{i}^{n}{\mathbb{E}\left[{u_{i}}\right]}\ +\
\sum_{j}^{m}{\mathbb{E}[r_{j}]}.$

###### Proof.

For each edge $(i,j)\in M$, its contribution to $W+W_{f}$ is $\mbox{\rm
bid}(i,j)$. Furthermore, the sum of $u_{i}$ and the contribution of $(i,j)$ to
$r_{j}$ is also $\mbox{\rm bid}(i,j)$. This gives the first equality below.
The second equality follows from linearity of expectation.

$\mathbb{E}[W+W_{f}]\ =\mathbb{E}\left[\sum_{i=1}^{n}{u_{i}}\ +\
\sum_{j=1}^{m}{r_{j}}\right]\ =\sum_{i}^{n}{\mathbb{E}\left[{u_{i}}\right]}\
+\ \sum_{j}^{m}{\mathbb{E}[r_{j}]},$

∎

Recall that for SINGLE-VALUED, we gave Lemma 21 and Corollary 22, which
established a relationship between the available bidders for a query $i$ in
the two runs $\mathcal{R}$ and $\mathcal{R}_{j}$. These facts dealt with
multisets rather than sets; the latter sufficed for Lemma 7 and Corollary 8,
which were used in the analysis of RANKING. In Section 4, we also defined
operations on multisets.

We will need Lemma 21 and Corollary 22 for analyzing Algorithm 35 as well,
though the definitions of the multisets will be guided by the following: If
bidder $k\in A$ has leftover money of $L_{k}$, as determined by Algorithm 35,
then we will say that $i$ has $L_{k}$ copies of $k$ available to it.
Furthermore, if $i$’s bid for $k$ is $\mbox{\rm bid}(i,k)$ and this bid is
successful, then $L_{k}$ will be decremented by $\min\\{L_{k},\mbox{\rm
bid}(i,k)\\}$, as stated in Step 2(b)(v) of the algorithm, and the available
copies of $k$ for the next bidder will decrease accordingly.

As before, let us renumber the queries so their order of arrival under
${{\rho}}(B)$ is $1,2,\ldots n$. Let $T(i)$ and $T_{j}(i)$ denote the
multisets of available copies of each bidder at the time of arrival of query
$i$ (i.e., just before the query $i$ gets matched), in runs $\mathcal{R}$ and
$\mathcal{R}_{j}$, respectively. Similarly, let $S(i)$ and $S_{j}(i)$ denote
the multisets obtained by restricting $T(i)$ and $T_{j}(i)$ to the bidders
that have edges to query $i$ in graphs $G$ and $G_{j}$, respectively.

We have assumed that Step (1) of Algorithm 6 has already been executed and a
price $p_{k}$ has been assigned to each good $k$. With probability 1, the
prices are all distinct. Let $F_{1}$ be the multiset containing $B_{l}$ copies
of $l$ for each $l\in A$ such that $p_{l}<p_{j}$. Similarly, let $F_{2}$ be
the multiset containing $B_{l}$ copies of $l$ for each $l\in A$ such that and
$p_{l}>p_{j}$.

Under the definitions and operations stated above, it is easy to check that
Lemma 21 and Corollary 22 hold for Algorithm 35 as well. Therefore, Lemma 27
also carries over. Definition 23 needs to be modified to the following.

######  Definition 34.

Let $e=(i,j)\in E$ be an arbitrary edge in $G$. Define random variable,
$u_{e}$, called the truncated threshold for edge $e$, to be
$u_{e}=\min\\{u_{i},\ \mbox{\rm
bid}(i,j)\cdot\left(1-{\frac{1}{e}}\right)\\}$, where $u_{i}$ is the utility
of query $i$ in run $\mathcal{R}_{j}$.

######  Algorithm 35.

($\mathcal{A}_{3}$: Algorithm for GENERAL)
1. Initialization: $M\leftarrow\emptyset$, $W\leftarrow 0$ and $W_{f}\leftarrow 0$
$\forall j\in A$, do: (a) Pick $w_{j}$ uniformly from $[0,1]$ and set price
$p_{j}\leftarrow e^{w_{j}-1}$. (b) $r_{j}\leftarrow 0$. (c) $L_{j}\leftarrow
B_{j}$.
2. Query arrival: When query $i$ arrives, do: (a) $\forall j\in A$ s.t. $(i,j)\in E$ and $L_{j}>0$ do: i. $\mbox{\rm ebid}(i,j)\leftarrow\mbox{\rm bid}(i,j)\cdot(1-p_{j})$. ii. Offer effective bid of $\mbox{\rm ebid}(i,j)$ to $i$. (b) Query $i$ accepts the bidder whose effective bid is the largest.
(If there are no bids, matching $M$ remains unchanged.)
If $i$ accepts $j$’s bid, then do: i. Set utility: $u_{i}\leftarrow\mbox{\rm
bid}(i,j)\cdot(1-p_{j})$. ii. Update revenue: $r_{j}\leftarrow r_{j}+\mbox{\rm
bid}(i,j)\cdot p_{j}$. iii. Update matching: $M\leftarrow M\cup(i,j)$. iv.
Update weight: $W\leftarrow\min\\{L_{i},\mbox{\rm bid}(i,j)\\}$ and
$W_{f}\leftarrow\max\\{0,\ \mbox{\rm bid}(i,j)-L_{i}\\}$. v. Update $L_{j}$:
$L_{j}\leftarrow L_{j}-\min\\{L_{j},\mbox{\rm bid}(i,j)\\}$. 3. Output: Output
matching $M$, real money spent $W$, and fake money spent $W_{f}$.

Definition 24 needs to be changed to the following.

######  Definition 36.

Let $j\in A$. Let $i_{1},\ldots,i_{k}$ be queries such that for $1\leq l\leq
k$, $(i_{l},j)\in E$ and $\sum_{l=1}^{k}{\mbox{\rm bid}(i_{l},j)}=B_{i}$. Then
$(j;\ i_{1},\ldots,i_{k})$ is called a $B_{j}$-star. Let $X_{j}$ denote this
$B_{j}$-star. The contribution of $X_{j}$ to $\mathbb{E}[W]$ is
$\mathbb{E}[r_{j}]+\sum_{l=1}^{k}{\mathbb{E}[u_{i_{l}}]}$, and it will be
denote by $\mathbb{E}[X_{j}]$.

Corresponding to $B_{j}$-star $X_{j}=(j;\ i_{1},\ldots,i_{k})$, denote by
$e_{l}$ the edge $(i_{l},j)\in E$, for $1\leq l\leq k$. Furthermore, let
$u_{e_{l}}$ denote the truncated threshold random variable corresponding to
$e_{l}$. The next lemma crucially uses the fact that $p_{j}$ is independent of
$u_{e_{l}}$; the reason for this fact is the same as in SINGLE-VALUED.

######  Lemma 37.

Let $j\in A$ and let $X_{j}=(j;\ i_{1},\ldots,i_{k})$ be a $B_{j}$-star. Then

$\mathbb{E}[X_{j}]\ \geq\ B_{j}\cdot\left(1-{\frac{1}{e}}\right).$

###### Proof.

We will first lower bound $\mathbb{E}[r_{j}]$. Let $f_{U}(\mbox{\rm
bid}(i_{1},j)\cdot z_{1},\ \ldots\ ,\mbox{\rm bid}(i_{k},j)\cdot z_{k})$ be
the joint probability density function of $(u_{e_{1}},\ldots u_{e_{k}})$;
clearly, $f_{U}(\mbox{\rm bid}(i_{1},j)\cdot z_{1},\ \ldots\ ,\mbox{\rm
bid}(i_{k},j)\cdot z_{k})$ can be non-zero only if $z_{l}\in[0,1-{1\over e}]$,
for $1\leq l\leq k$.

By the law of total expectation, $\mathbb{E}[r_{j}]=$

$\int_{(z_{1},\ldots,z_{k})}{\mathbb{E}[r_{j}~{}|~{}u_{e_{1}}=\mbox{\rm
bid}(i_{1},j)\cdot z_{1},\ldots,u_{e_{k}}=\mbox{\rm bid}(i_{k},j)\cdot
z_{k}]\cdot f_{U}(\mbox{\rm bid}(i_{1},j)\cdot z_{1},\ldots\mbox{\rm
bid}(i_{k},j)\cdot z_{k})\ dz_{1}\ldots dz_{k}},$

where the integral is over $z_{l}\in[0,\left(1-{\frac{1}{e}}\right)]$, for
$1\leq l\leq k$.

For lower-bounding the conditional expectation in this integral, let
$w_{l}\in[0,1]$ be s.t. $e^{w_{l}-1}=1-z_{l}$, for $1\leq l\leq k$. Let
$x\in[0,1]$. For $1\leq l\leq k$, define indicator functions
$I_{l}:[0,1]\rightarrow\\{0,1\\}$ as follows.

$I_{l}(x)\ \ =\ \begin{cases}1&\text{if }x<w_{l},\\\
0&\text{otherwise.}\end{cases}$

Furthermore, define

$V(x)=\sum_{l=1}^{k}{I_{l}(x)\cdot\mbox{\rm bid}(i_{l},j)}.$

######  Claim 38.

Conditioned on $(u_{e_{1}}=\mbox{\rm bid}(i_{1},j)\cdot
z_{1},\ldots,u_{e_{k}}=\mbox{\rm bid}(i_{k},j)\cdot z_{k})$, if
$p_{j}=e^{x-1}$, where $x\in[0,1]$, then the contribution to $r_{j}$ in this
run of algorithm $\mathcal{A}_{3}$ was $\geq p_{j}\cdot V(x)$.

###### Proof.

Suppose $I_{l}(x)=1$, then $x<w_{l}$. In run $\mathcal{R}_{j}$, the maximum
effective bid that $i_{l}$ received has value $\mbox{\rm bid}(i_{l},j)\cdot
z_{l}$. In run $\mathcal{R}$, if on the arrival of query $i_{l}$, $L_{j}=0$,
i.e., $j$ is already fully matched, then the contribution to $r_{j}$ in this
run was $B_{j}\cdot p_{j}$ and the claim is obviously true. If $L_{j}>0$, then
since $x<w_{l}$, $1-p_{j}>z_{l}$. Therefore, by Corollary 22, query $i_{l}$
will receive its largest effective bid from $j$. Hence, $i_{l}$ will get
matched to $j$ and $r_{j}$ will be incremented by $\mbox{\rm
bid}(i_{l},j)\cdot p_{j}$. The claim follows. ∎

By Claim 38,

$\mathbb{E}[r_{j}~{}|~{}u_{e_{1}}=\mbox{\rm bid}(i_{1},j)\cdot
z_{1},\ldots,u_{e_{k}}=\mbox{\rm bid}(i_{k},j)\cdot z_{k}]\ \geq\
\int_{0}^{1}{V(x)\cdot e^{x-1}\ dx}$

$=\sum_{l=1}^{k}{\mbox{\rm bid}(i_{l},j)\cdot{\int_{0}^{1}{I_{l}(x)\cdot
e^{x-1}\ dx}}}\ =\ \sum_{l=1}^{k}{\mbox{\rm
bid}(i_{l},j)\cdot{\int_{0}^{w_{l}}{e^{x-1}\ dx}}}$

$=\ B_{j}\cdot\sum_{l=1}^{k}{\left(e^{w_{l}-1}-{\frac{1}{e}}\right)}\ =\
B_{j}\cdot\sum_{l=1}^{k}\left(1-{\frac{1}{e}}-z_{l}\right).$

Therefore, $\mathbb{E}[r_{j}]\ =$

$\int_{(z_{1},\ldots,z_{k})}{\mathbb{E}[r_{j}~{}|~{}u_{e_{1}}=\mbox{\rm
bid}(i_{1},j)\cdot z_{1},\ldots,u_{e_{k}}=\mbox{\rm bid}(i_{k},j)\cdot
z_{k}]\cdot f_{U}(\mbox{\rm bid}(i_{1},j)\cdot z_{1},\ldots\mbox{\rm
bid}(i_{k},j)\cdot z_{k})\ dz_{1}\ldots dz_{k}},$

$\geq
B_{j}\cdot\int_{(z_{1},\ldots,z_{k})}{\sum_{l=1}^{k}\left(1-{\frac{1}{e}}-z_{l}\right)\cdot
f_{U}(\mbox{\rm bid}(i_{1},j)\cdot z_{1},\ldots\mbox{\rm bid}(i_{k},j)\cdot
z_{k})\ dz_{1}\ldots dz_{k}}$

$=\
B_{j}\cdot\left(1-{\frac{1}{e}}\right)-\sum_{l=1}^{k}{\mathbb{E}[u_{e_{l}}]}.$

By Lemma 27, $\mathbb{E}[u_{i_{l}}]\geq\mathbb{E}[u_{e_{l}}]$, for $1\leq
l\leq k$. Hence we get

$\mathbb{E}[X_{j}]\ =\
\mathbb{E}[r_{j}]+\sum_{l=1}^{k}{\mathbb{E}[u_{i_{l}}]}\ \geq\
=B_{j}\cdot\left(1-{\frac{1}{e}}\right),$

∎

######  Lemma 39.

Algorithm $\mathcal{A}_{3}$ satisfies

$\mathbb{E}\left[W+W_{f}\right]\ \geq\ \left(1-{\frac{1}{e}}\right)\cdot
w(P).$

Furthermore, it is budget-oblivious.

###### Proof.

Let $P$ denote a maximum weight $b$-matching in $G$. By the assumption made in
Remark 3, its weight is

$w(P)=\sum_{j=1}^{m}{B_{j}}.$

Let $T_{j}$ denote the $j$-star, under $P$, corresponding to each $j\in A$.
The expected weight of matching produced by $\mathcal{A}_{3}$ is

$\mathbb{E}\left[W+W_{f}\right]\ =\
\sum_{i=1}^{n}{\mathbb{E}\left[{u_{i}}\right]}\ +\
\sum_{j=1}^{m}{\mathbb{E}[r_{j}]}\ =\ \sum_{j=1}^{m}{\mathbb{E}[T_{j}]}\ \geq\
\sum_{j=1}^{m}{B_{j}}\cdot\left(1-{\frac{1}{e}}\right)\ =\
\left(1-{\frac{1}{e}}\right)\cdot w(P),$

where the first equality uses Lemma 5, the second follows from linearity of
expectation and the inequality follows by using Lemma 37.

Finally, Algorithm $\mathcal{A}_{3}$ is budget-oblivious because it does not
need to know the budgets $B_{j}$ for bidders $j$; it only needs to know during
a run whether $B_{j}$ has been exhausted. The lemma follows. ∎

######  Remark 40.

Let us consider the following two avenues for dispensing with the use of fake
money altogether; we will show places where our proof technique breaks down
for each one. Assume $L_{j}<\mbox{\rm bid}(i,j)$.

  1. 1.

Why not modify Step 2 of Algorithm 35 so that $j$’s bid for $i$ is taken to be
$L_{j}$ instead of $\mbox{\rm bid}(i,j)$?

  2. 2.

Why not modify Step 2(b)(i) so it sets $u_{i}$ to $L_{j}\cdot(1-p_{j})$ rather
than $B_{j}\cdot(1-p_{j})$

Under the first avenue, we cannot ensure $u_{i}\geq u_{e}$, since it may
happen that $u_{e}>L_{j}\cdot(1-p_{j})=u_{i}$. The condition $u_{i}\geq u_{e}$
is used for deriving $\mathbb{E}[u_{i}]\geq\mathbb{E}[u_{e}]$, which is
essential in the proof of Lemma 37.

To make the second avenue work, the proof of Claim 38 would need to be changed
as follows: the last case, $L_{j}>0$, will need to be split into the two cases
given above. However, under Case 2, which applies if $L_{j}<\mbox{\rm
bid}(i,j)$, even though $p_{j}<p$, the largest effective bid that query
$i_{l}$ receives may not be the one from $j$, since the effective bid of $j$
has value $L_{j}\cdot(1-p_{j})<\mbox{\rm bid}(i_{l},j)\cdot(1-p_{j})$.
Therefore, $i_{l}$ may not get matched to $j$, thereby invalidating Claim 38.

###  5.4 Algorithm for SMALL

We will use Lemma 39 to show that Algorithm 35 yields algorithms for SMALL by
upper bounding the fake money used in the worst case. Their budget-
obliviousness follows from that of Algorithm 35.

######  Conditional Theorem 41.

Algorithm $\mathcal{A}_{3}$ is an optimal online algorithm for SMALL;
furthermore, it is budget-oblivious.

###### Proof.

Let $I$ be an instance of SMALL.

$W_{f}\leq\ {\sum_{j\in A}{\max_{(i,j)\in E}\ \\{\mbox{\rm bid}(i,j)-1\\}}}$

Therefore,

$\mu(I)=\max_{j\in A}\ \ \left\\{{{\max_{(i,j)\in E}\ \\{\mbox{\rm
bid}(i,j)-1\\}}\over{B_{j}}}\right\\}\geq{{\sum_{j\in A}{\max_{(i,j)\in E}\
\\{\mbox{\rm bid}(i,j)-1\\}}}\over{\sum_{j\in
A}{B_{j}}}}\geq{{W_{f}}\over{w(P)}},$

where $\mu(I)$ is defined in Section 2. Now, by definition of SMALL,

$\lim_{n(I)\rightarrow\infty}\ {\mu(I)}=0,$

where $n(I)$ denotes the number of queries in instance $I$.

Therefore

$\lim_{n(I)\rightarrow\infty}\ {{W_{f}}\over{w(P)}}=0.$

The theorem follows from Lemma 39. ∎

##  6 Discussion

The open question mentioned in the Introduction, of removing the assumption of
no-surpassing property from our proof of Algorithm 35 for SMALL, deserves
special attention because of its potential impact in the ad auctions
marketplace.

The main open question of the area is to make a substantial dent on GENERAL,
or even better give an optimal online algorithm for it, without making any
assumptions on bids vs budgets.

##  7 Acknowledgements

I wish to thank Asaf Ferber, Alon Orlitsky, Will Ma and Thorben Trobst for
valuable comments and discussions.

## References

  * [ABM19] Gagan Aggarwal, Ashwinkumar Badanidiyuru, and Aranyak Mehta.  Autobidding with constraints.  In International Conference on Web and Internet Economics, pages 17–30. Springer, 2019.
  * [AGKM11] Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta.  Online vertex-weighted bipartite matching and single-bid budgeted allocations.  In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1253–1264, 2011.
  * [BC21] Guy Blanc and Moses Charikar.  Multiway online correlated selection.  arXiv preprint arXiv:2106.05579, 2021.
  * [BJN07] Niv Buchbinder, Kamal Jain, and Joseph Seffi Naor.  Online primal-dual algorithms for maximizing ad-auctions revenue.  In European Symposium on Algorithms, pages 253–264, 2007.
  * [BM08] Benjamin Birnbaum and Claire Mathieu.  On-line bipartite matching made simple.  ACM Sigact News, 39(1):80–87, 2008.
  * [DJK13] Nikhil R Devanur, Kamal Jain, and Robert D Kleinberg.  Randomized primal-dual analysis of ranking for online bipartite matching.  In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 101–107. SIAM, 2013.
  * [DM22] Nikhil Devanur and Aranyak Mehta.  Online matching in advertisement auctions.  In Federico Echenique, Nicole Immorlica, and Vijay V. Vazirani, editors, Online and Matching-Based Market Design. Cambridge University Press, 2022.  [To appear] https://www.ics.uci.edu/~vazirani/AdAuctions.pdf.
  * [EFFS21] Alon Eden, Michal Feldman, Amos Fiat, and Kineret Segal.  An economic-based analysis of ranking for online bipartite matching.  In SIAM Symposium on Simplicity in Algorithms, 2021.
  * [EIV22] Federico Echenique, Nicole Immorlica, and Vijay V. Vazirani.  One-sided matching markets.  In Federico Echenique, Nicole Immorlica, and Vijay V. Vazirani, editors, Online and Matching-Based Market Design. Cambridge University Press, 2022.  [To appear] https://www.ics.uci.edu/~vazirani/Chapter2.pdf.
  * [FHTZ20] Matthew Fahrbach, Zhiyi Huang, Runzhou Tao, and Morteza Zadimoghaddam.  Edge-weighted online bipartite matching.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 412–423, 2020.
  * [GM08] Gagan Goel and Aranyak Mehta.  Online budgeted matching in random input models with applications to adwords.  In SODA, volume 8, pages 982–991, 2008.
  * [GS62] David Gale and Lloyd S Shapley.  College admissions and the stability of marriage.  The American Mathematical Monthly, 69(1):9–15, 1962.
  * [HT22] Zhiyi Huang and Thorben Trobst.  Online matching.  In Federico Echenique, Nicole Immorlica, and Vijay V. Vazirani, editors, Online and Matching-Based Market Design. Cambridge University Press, 2022.  [To appear] https://www.ics.uci.edu/~vazirani/Ch4.pdf.
  * [HZZ20] Zhiyi Huang, Qiankun Zhang, and Yuhao Zhang.  Adwords in a panorama.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1416–1426. IEEE, 2020.
  * [Ins19] Simons Institute.  Online and matching-based market design, 2019.  https://simons.berkeley.edu/programs/market2019.
  * [JMM+03] Kamal Jain, Mohammad Mahdian, Evangelos Markakis, Amin Saberi, and Vijay V Vazirani.  Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP.  Journal of the ACM (JACM), 50(6):795–824, 2003.
  * [KP00] Bala Kalyanasundaram and Kirk R Pruhs.  An optimal deterministic algorithm for online b-matching.  Theoretical Computer Science, 233(1-2):319–325, 2000.
  * [KVV90] Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani.  An optimal algorithm for on-line bipartite matching.  In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 352–358, 1990.
  * [Meh13] Aranyak Mehta.  Online matching and ad allocation.  2013\.
  * [MSVV07] Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani.  Adwords and generalized online matching.  Journal of the ACM (JACM), 54(5), 2007.