Renato Paes Leme
Renato Paes Leme is a research scientist at Google New York. He is broadly interested in algorithm design, specially for problems on the interface between Economics and Computation. Some topics he is particularly excited about are: mechanism design for non-quasi-linear settings, Price of Anarchy of auctions, sequential games and applications of game-theory to ad auctions. See http://renatoppl.com/ for my personal homepage.
Research Areas
Authored Publications
Google Publications
Other Publications
Sort By
Calibrated Click-Through Auctions
Dirk Bergemann
Paul Duetting
Proceedings of the ACM Web Conference 2022, pp. 47-57
Preview abstract
We analyze the optimal information design in a click-through auction with stochastic click-through rates and known valuations per click. The auctioneer takes as given the auction rule of the click-through auction, namely the generalized second-price auction. Yet, the auctioneer can design the information flow regarding the click-through rates among the bidders. We require that the information structure to be calibrated in the learning sense. With this constraint, the auction needs to rank the ads by a product of the value and a calibrated prediction of the click-through rates. The task of designing an optimal information structure is thus reduced to the task of designing an optimal calibrated prediction.
We show that in a symmetric setting with uncertainty about the click-through rates, the optimal information structure attains both social efficiency and surplus extraction. The optimal information structure requires private (rather than public) signals to the bidders. It also requires correlated (rather than independent) signals, even when the underlying uncertainty regarding the click-through rates is independent. Beyond symmetric settings, we show that the optimal information structure requires partial information disclosure, and achieves only partial surplus extraction.
View details
Preview abstract
In the contextual pricing problem a seller repeatedly obtains products described by an adversarially chosen feature vector in $\R^d$ and only observes the purchasing decisions of a buyer with a fixed but unknown linear valuation over the products. The regret measures the difference between the revenue the seller could have obtained knowing the buyer valuation and what can be obtained by the learning algorithm.
We give a poly-time algorithm for contextual pricing with $O(d \log \log T + d \log d)$ regret which matches the $\Omega(d \log \log T)$ lower bound up to the $d \log d$ additive factor. If we replace pricing loss by the symmetric loss, we obtain an algorithm with nearly optimal regret of $O(d \log d)$ matching the $\Omega(d)$ lower bound up to $\log d$. These algorithms are based on a novel technique of bounding the value of the Steiner polynomial of a convex region at various scales. The Steiner polynomial is a degree $d$ polynomial with intrinsic volumes as the coefficients.
We also study a generalized version of contextual search where the hidden linear function over the Euclidean space is replaced by a hidden function $f : \X \rightarrow \Y$ in a certain hypothesis class $\H$. We provide a generic algorithm with $O(d^2)$ regret where $d$ is the covering dimension of this class. This leads in particular to a $\tilde{O}(s^2)$ regret algorithm for linear contextual search if the linear function is guaranteed to be $s$-sparse. Finally we also extend our results to the noisy feedback model, where each round our feedback is flipped with a fixed probability $p < 1/2$.
View details
Contextual Recommendations and Low-Regret Cutting-Plane Algorithms
Guru Prashanth Guruganesh
NeurIPS (2021)
Preview abstract
We consider the following variant of contextual linear bandits motivated by routing applications in navigational engines and recommendation systems. We wish to learn a hidden $d$-dimensional value $w^*$. Every round, we are presented with a subset $\mathcal{X}_t \subseteq \mathbb{R}^d$ of possible actions. If we choose (i.e. recommend to the user) action $x_t$, we obtain utility $\langle x_t, w^* \rangle$ but only learn the identity of the best action $\arg\max_{x \in \X_t} \langle x, w^* \rangle$.
We design algorithms for this problem which achieve regret $O(d\log T)$ and $\exp(O(d \log d))$. To accomplish this, we design novel cutting-plane algorithms with low “regret” -- the total distance between the true point $w^*$ and the hyperplanes the separation oracle returns.
We also consider the variant where we are allowed to provide a list of several recommendations. In this variant, we give an algorithm with $O(d^2 \log d)$ regret and list size $\poly(d)$. Finally, we construct nearly tight algorithms for a weaker variant of this problem where the learner only learns the identity of an action that is better than the recommendation. Our results rely on new algorithmic techniques in convex geometry (including a variant of Steiner’s formula for the centroid of a convex set) which may be of independent interest.
View details
Non-Excludable Dynamic Mechanism Design
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, pp. 1357-1373
Preview abstract
Dynamic mechanism design expands the scope on what type of allocation rules can be implemented and what revenue can be extracted when compared to static mechanisms. The case of excludable environments (i.e. one player can be de-allocated while keeping the allocation of the remaining players intact) is very well understood. The mechanisms in the literature don’t extend to the non-excludable environments. Two prototypical examples of such environments are: (i) public projects, where all players must have the same allocation; and (ii) non-disposable goods, where each item must be allocated to some player. We show a general mechanism that can asymptotically extract the full surplus in such environments. Moreover, we fully characterize which abstract mechanism design environments allow for full surplus extraction in the limit. Our characterization is based on the geometry of achievable utility sets – a convex set characterizing the expected utility profiles that can be implemented in a static mechanism.
View details
Secretaries with Advice
Paul Duetting
Proceedings of the 22nd ACM Conference on Economics and Computation (EC'21) (2021), pp. 409-429
Preview abstract
The secretary problem is probably the purest model of decision making under uncertainty. In this
paper we ask which advice can we give the algorithm to improve its success probability?
We propose a general model that unifies a broad range of problems: from the classic secretary problem
with no advice, to the variant where the quality of a secretary is drawn from a known distribution and
the algorithm learns each candidate’s quality quantile on arrival, to more modern ML-based versions of
advice where a binary classifier gives us noisy advice about whether or not the current secretary is the
best on the market.
Our main technique is a factor revealing LP that captures all of the problems above. We use this LP
formulation to gain structural insight into the optimal policy and present two case studies: a re-derivation
of the classic known distributions result with tools from linear programming and a tight analysis of the
noisy binary advice model.
View details
Preview abstract
We study a variant of linear regression with a dis-continuous loss function that we term Myersonianregression. In this variant, we wish to find a linearfunctionf:Rd→Rthat well approximates a setof points(xi,vi)∈Rd×[0,1]in the followingsense: we receive a loss ofviwhenf(xi)> viand a loss ofvi−f(xi)whenf(xi)≤vi. Thisarises naturally in the economic application ofdesigning a pricing policy for differentiated items(where the loss is the gap between the perfor-mance of our policy and the optimal Myersonprices).We show that Myersonian regression is NP-hardto solve exactly and furthermore that no fullypolynomial-time approximation scheme exists forMyersonian regression conditioned on the Expo-nential Time Hypothesis being true. In contrast tothis, we demonstrate a polynomial-time approx-imation scheme for Myersonian regression thatobtains anmadditive approximation to the op-timal possible revenue and can be computed intimeO(exp(poly(1/))poly(m,n)). We showthat this algorithm is stable and generalizes wellover distributions of samples
View details
Preview abstract
We study optimization with an approximate zero order oracle where there is a cost c() associated
with querying the oracle with accuracy. We consider the task of reconstructing a linear function:
given a linear function f : X ⊆ R
d → [−1, 1] defined on a not-necessarily-convex set X, the goal is
to reconstruct ˆf such that |f(x) − ˆf(x)| ≤ for all x ∈ X. We show that this can be done with cost
O(d · c(/d)). The algorithm is based on a (poly-time computable) John-like theorem for simplices
instead of ellipsoids, which may be of independent interest.
This question is motivated by optimization with threshold queries, which are common in
economic applications such as pricing. With threshold queries, approximating a number up to
precision requires c() = log(1/). For this, our algorithm has cost O(d log(d/)) which matches
the Ω(d log(1/)) lower bound up to log factors
View details
Preview abstract
We study an intermediary model between stochastic and adversarial bandits, which
we term adversarial scaling, where the rewards are a product between a stochastic
component and an adversarial component shared by all arms. This can be viewed as
a model where the ratios between the mean rewards remain fixed, but the magniture
of rewards is rescaled by an adaptive adversary. We obtain logarithmic regret
bounds for this setting. As a by-product we improve the regret of purely stochastic
bandits in the special case where all the means are small. Finally we show that
classical algorithms such as UCB and Thompson Sampling are susceptible to
adversarial scaling attacks.
View details
Non-Clairvoyant Dynamic Mechanism Design
Pingzhong Tang
Econometrica, vol. 88(5) (2020), pp. 1939-1963
Preview abstract
We introduce a new family of dynamic mechanisms that restricts sellers from using future distributional knowledge. Since the allocation and pricing of each auction period do not depend on the type distributions of future periods, we call this family of dynamic mechanisms non‐clairvoyant.
We develop a framework (bank account mechanisms) for characterizing, designing, and proving lower bounds for dynamic mechanisms (clairvoyant or non‐clairvoyant). We use the same methods to compare the revenue extraction power of clairvoyant and non‐clairvoyant dynamic mechanisms.
View details
Preview abstract
We consider a setting in which bidders participate in multiple auctions run by different sellers, and optimize their bids for the \emph{aggregate} auction. We analyze this setting by formulating a game between sellers, where a seller's strategy is to pick an auction to run. Our analysis aims to shed light on the recent change in the Display Ads market landscape: here, ad exchanges (sellers) were mostly running second price auctions earlier and over time they switched to variants of the first price auction, culminating in Google's Ad Exchange moving to a first price auction in 2019. Our model and results offer an explanation for why the first price auction occurs as a natural equilibrium in such competitive markets.
View details
Improved Approximations for Posted Price and Second-price Mechanisms
Hedyeh Beyhaghi
Negin Golrezaei
Operations Research (2020)
Preview abstract
We study the fundamental problem of selling a single indivisible good to one ofnbuyers with independentvaluations. We seek to design improved approximations to the optimal revenue achievable through two simpleand widely used mechanisms: second price auction with eager personalized reserve prices, and sequentialposted price mechanisms. Until recently, the best known approximation for both these mechanisms was 1−1e.We give improved approximations of 1−1e+0.022∼0.6543 for the sequential posted price mechanism and1−1e+0.029∼0.662 for the second price auction with eager reserve prices. We also make some progresstowards the problem of computing the optimal personalized eager reserve prices for a second price auction.
View details
Dynamic Double Auctions: Towards First Best
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pp. 157-172
Preview abstract
We study the problem of designing dynamic double auctions for two-sided markets in which a platform intermediates the trade between one seller offering independent items to multiple buyers, repeatedly over a finite horizon, when agents have private values. Motivated by online advertising and ride-hailing markets, we seek to design mechanisms satisfying the following properties: no positive transfers, i.e., the platform never asks the seller to make payments nor buyers are ever paid and periodic individual rationality, i.e., every agent should derive a non-negative utility from every trade opportunity. We provide mechanisms satisfying these requirements that are asymptotically efficient and budget-balanced with high probability as the number of trading opportunities grows. Moreover, we show that the average expected profit obtained by the platform under these mechanisms asymptotically approaches first-best (the maximum possible welfare generated by the market).
View details
Optimal Dynamic Auctions are Virtual Welfare Maximizers
Pingzhong Tang
Proceedings of the AAAI Conference on Artificial Intelligence (2019), pp. 2125-2132
Preview abstract
We are interested in the setting where a seller sells sequentially
arriving items, one per period, via a dynamic auction.
At the beginning of each period, each buyer draws a private
valuation for the item to be sold in that period and this valuation
is independent across buyers and periods. The auction
can be dynamic in the sense that the auction at period
t can be conditional on the bids in that period and all previous
periods, subject to certain appropriately defined incentive
compatible and individually rational conditions. Perhaps
not surprisingly, the revenue optimal dynamic auctions are
computationally hard to find and existing literatures that aim
to approximate the optimal auctions are all based on solving
complex dynamic programs. It remains largely open on the
structural interpretability of the optimal dynamic auctions.
In this paper, we show that any optimal dynamic auction is
a virtual welfare maximizer subject to some monotone allocation
constraints. In particular, the explicit definition of
the virtual value function above arises naturally from the
primal-dual analysis by relaxing the monotone constraints.
We further develop an ironing technique that gets rid of the
monotone allocation constraints. Quite different from Myerson’s
ironing approach, our technique is more technically involved
due to the interdependence of the virtual value functions
across buyers. We nevertheless show that ironing can be
done approximately and efficiently, which in turn leads to a
Fully Polynomial Time Approximation Scheme of the optimal
dynamic auction.
View details
Contextual Pricing for Lipschitz Buyers
Jieming Mao
Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montr\'eal, Canada., pp. 5648-5656
Preview abstract
We investigate the problem of learning a Lipschitz function from binary feedback.
In this problem, a learner is trying to learn a Lipschitz function f : [0, 1] d → [0, 1]
over the course of T rounds. On round t, an adversary provides the learner with an
input x t , the learner submits a guess y t for f (x t ), and learns whether
P y t > f (x t )
or y t ≤ f (x t ). The learner’s goal is to minimize their total loss t `(f (x t ), y t )
(for some loss function `). The problem is motivated by contextual dynamic pric-
ing, where a firm must sell a stream of differentiated products to a collection of
buyers with non-linear valuations for the items and observes only whether the item
was sold or not at the posted price.
For the symmetric loss `(f (x t ), y t ) = |f (x t ) − y t |, we provide an algorithm for
(d−1)/d
this problem achieving total loss O(log T ) when d = 1 and O(T
) when
√
d > 1, and show that both bounds are tight (up to a factor of log T ). For the
pricing loss function `(f (x t ), y t ) = f (x t ) − y t 1{y t ≤ f (x t )} we show a regret
bound of O(T d/(d+1) ) and show that this bound is tight. We present improved
bounds in the special case of a population of linear buyers
View details
On the Construction of Substitutes
Eric Balkanski
Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, pp. 643
Preview abstract
Gross substitutability is a central concept in Economics and is connected to important notions in
Discrete Convex Analysis, Number Theory and the analysis of Greedy algorithms in Computer
Science. Many different characterizations are known for this class, but providing a constructive
description remains a major open problem. The construction problem asks how to construct
all gross substitutes from a class of simpler functions using a set of operations. Since gross
substitutes are a natural generalization of matroids to real-valued functions, matroid rank
functions form a desirable such class of simpler functions.
Shioura proved that a rich class of gross substitutes can be expressed as sums of matroid
rank functions, but it is open whether all gross substitutes can be constructed this way. Our
main result is a negative answer showing that some gross substitutes cannot be expressed
as positive linear combinations of matroid rank functions. En route, we provide necessary
and sufficient conditions for the sum to preserve substitutability, uncover a new operation
preserving substitutability and fully describe all substitutes with at most 4 items.
View details
Stochastic bandits robust to adversarial corruptions
Thodoris Lykouris
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, ?114-122
Preview abstract
We introduce a new model of stochastic bandits with adversarial corruptions which aims to capture settings where most of the input follows a stochastic pattern but some fraction of it can be adversarially changed to trick the algorithm, e.g., click fraud, fake reviews and email spam. The goal of this model is to encourage the design of bandit algorithms that (i) work well in mixed adversarial and stochastic models, and (ii) whose performance deteriorates gracefully as we move from fully stochastic to fully adversarial models.
We consider a setting with $K$ arms with underlying stochastic distributions such that $\Delta(a)$ is the difference between the mean of arm $a$ and the optimal arm $a^*$. The total corruption $C$ corresponds to the total perturbation that an adversary can add to the stochastic input. Our main result is an algorithm with regret bounded by {$\bigO\prn*{\sum_{a{\neq a^*}}\frac{K\cdot C\log\prn*{\nicefrac{KT}{\delta}}+\log\prn*{T}}{\Delta(a)}\cdot\log\prn*{\nicefrac{KT}{\delta}}}$ with $1-\delta$ probability and pseudoregret $\bigO\prn*{\sum_{a{\neq a^*}}\frac{K\cdot C+\log\prn*{T}}{\Delta(a)}\cdot\log\prn*{KT}}$.}
Notably, our algorithm is agnostic to the total corruption and the bound holds with respect to the total corruption that was added in retrospect. We also provide a lower bound showing that the linear dependency on the corruption level is necessary.
View details
Non-Clairvoyant Dynamic Mechanism Design
Pingzhong Tang
Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, ACM, pp. 169
Preview abstract
Despite their better revenue and welfare guarantees for repeated auctions, dynamic mechanisms have not been widely adopted in practice. This is partly due to the complexity of their implementation as well as their unrealistic use of forecasting for future periods. We address these shortcomings and present a new family of dynamic mechanisms that are simple and require no distributional knowledge of future periods.
This paper introduces the concept of non-clairvoyance in dynamic mechanism design, which is a measure-theoretic restriction on the information that the seller is allowed to use. A dynamic mechanism is non-clairvoyant if the allocation and pricing rule at each period does not depend on the type distributions in the future periods.
We develop a framework (bank account mechanisms) for characterizing, designing, and proving lower bounds for dynamic mechanisms (clairvoyant or non-clairvoyant). This framework is used to characterize the revenue extraction power of the non-clairvoyant mechanisms with respect to the mechanisms that are allowed unrestricted use of distributional knowledge.
View details
Dynamic Mechanism Design in the Field
Rita Ren
Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018, Lyon, France, April 23-27, 2018, {ACM}, pp. 1359-1368
Preview abstract
Dynamic mechanisms are a powerful technique in designing revenue-maximizing repeated auctions. Despite their strength, these types of mechanisms have not been widely adopted in practice for several reasons, e.g., for their complexity, and for their sensitivity to the accuracy of predicting buyers' value distributions. In this paper, we aim to address these shortcomings and develop simple dynamic mechanisms that can be implemented efficiently, and provide theoretical guidelines for decreasing the sensitivity of dynamic mechanisms on prediction accuracy of buyers' value distributions. We prove that the dynamic mechanism we propose is provably dynamic incentive compatible, and introduce a notion of buyers' regret in dynamic mechanisms, and show that our mechanism achieves bounded regret while improving revenue and social welfare compared to a static reserve pricing policy. Finally, we confirm our theoretical analysis via an extensive empirical study of our dynamic auction on real data sets from online adverting. For example, we show our dynamic mechanisms can provide a 17% revenue lift with relative regret less than 0.2%.
View details
Contextual Search via Intrinsic Volumes
59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pp. 268-282
Preview abstract
We study the problem of contextual search, a multidimensional generalization of bi- nary search that captures many problems in contextual decision-making. In contextual search, a learner is trying to learn the value of a hidden vector v ∈ [0, 1]d. Every round the learner is provided an adversarially-chosen context ut ∈ Rd, submits a guess pt for the value of ⟨ut, v⟩, learns whether pt < ⟨ut, v⟩, and incurs loss ⟨ut, v⟩. The learner’s goal is to minimize their total loss over the course of T rounds.
We present an algorithm for the contextual search problem for the symmetric loss function l(θ,p) = |θ−p| that achieves Od(1) total loss. We present a new algorithm for the dynamic pricing problem (which can be realized as a special case of the contextual search problem) that achieves Od(log log T ) total loss, improving on the previous best known upper bounds of Od(logT) and matching the known lower bounds (up to a polynomial dependence on d). Both algorithms make significant use of ideas from the field of integral geometry, most notably the notion of intrinsic volumes of a convex set. To the best of our knowledge this is the first application of intrinsic volumes to algorithm design.
View details
Preview abstract
We propose a new framework called Ego-splitting for detecting
clusters in complex networks which leverage the local structures
known as ego-nets (i.e. the subgraph induced by the neighborhood
of each node) to de-couple overlapping clusters. Ego-splitting is
highly scalable and flexible framework, with provable theoretical
guarantees, that reduce the complex overlapping clustering problem
to a simpler and more amenable non-overlapping (partitioning)
problem. We can solve community detection in graphs with tens
of billions of edges and outperform previous solutions based on
ego-nets analysis.
More precisely, our framework works in two steps: a local ego-
net analysis, and a global graph partitioning. In the local step, we
first partition the nodes’ ego-nets using non-overlapping clustering.
We then use these clusters to split each node of the graph into
its persona nodes that represents the instantiation of the node in
its communities. Then, in the global step, we partition these new
persona nodes to obtain an overlapping clustering of the original
graph.
View details
Preview abstract
We present the first polynomial time algorithm for computing Walrasian equilibrium in an economy with indivisible goods and \emph{general} buyer valuations having only access to an \emph{aggregate demand oracle}, i.e., an oracle that given prices on all goods, returns the aggregated demand over the entire population of buyers. For the important special case of gross substitute valuations, our algorithm queries the aggregate demand oracle O˜(n) times and takes O˜(n3) time, where n is the number of goods. At the heart of our solution is a method for exactly minimizing certain convex functions which cannot be evaluated but for which the subgradients can be computed.
We also give the fastest known algorithm for computing Walrasian equilibrium for gross substitute valuations in the \emph{value oracle model}. Our algorithm has running time O˜((mn+n3)TV) where TV is the cost of querying the value oracle. A key technical ingredient is to regularize a convex programming formulation of the problem in a way that subgradients are cheap to compute. En route, we give necessary and sufficient conditions for the existence of \emph{robust Walrasian prices}, i.e., prices for which each agent has a unique demanded bundle and the demanded bundles clear the market. When such prices exist, the market can be perfectly coordinated by solely using prices.
View details
Preview abstract
We study the dynamic mechanism design problem of a seller who repeatedly sells independent items to a buyer with private values. In this setting, the seller could potentially extract the entire buyer surplus by running efficient auctions and charging an upfront participation fee at the beginning of the horizon. In some markets, such as internet advertising, participation fees are not practical since buyers expect to inspect items before purchasing them. This motivates us to study the design of dynamic mechanisms under successively more stringent requirements that capture the implicit business constraints of these markets. We first consider a periodic individual rationality constraint, which limits the mechanism to charge at most the buyer's value in each period. While this prevents large upfront participation fees, the seller can still design mechanisms that spread a participation fee across the first few auctions. These mechanisms have the unappealing feature that they provide close-to-zero buyer utility in the first auctions in exchange for higher utility in future auctions. To address this problem, we introduce a martingale utility constraint, which imposes the requirement that from the perspective of the buyer, the next item's expected utility is equal to the present one's. Our main result is providing a dynamic auction satisfying martingale utility and periodic individual rationality whose profit loss with respect to first-best (full extraction of buyer surplus) is optimal up to polylogarithmic factors. The proposed mechanism is a dynamic two-tier auction with a hard floor and a soft floor that allocates the item whenever the buyer's bid is above the hard floor and charges the minimum of the bid and the soft floor.
View details
Dynamic Revenue Sharing
Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA
Preview abstract
Many online platforms act as intermediaries between a seller and a set of buyers. Examples of such settings include online retailers (such as Ebay) selling items on behalf of sellers to buyers, or advertising exchanges (such as AdX) selling pageviews on behalf of publishers to advertisers. In such settings, revenue sharing is a central part of running such a marketplace for the intermediary, and fixed-percentage revenue sharing schemes are often used to split the revenue among the platform and the sellers. In particular, such revenue sharing schemes require the platform to (i) take at most a constant fraction α of the revenue from auctions and (ii) pay the seller at least the seller declared opportunity cost c for each item sold. A straightforward way to satisfy the constraints is to set a reserve price at c/(1 − α ) for each item, but it is not the optimal solution on maximizing the profit of the intermediary.
While previous studies (by Mirrokni and Gomes, and by Niazadeh et al) focused on revenue-sharing schemes in static double auctions, in this paper, we take advantage of the repeated nature of the auctions, and present solutions based on dynamic mechanism design. In particular, we introduce dynamic revenue sharing schemes where we balance the two constraints over different auctions to achieve higher profit. This is directly motivated by the practice of advertising exchanges where the fixed-percentage revenue-share should be met across all auctions and not in each auction. In this paper, we characterize the optimal revenue sharing scheme that satisfies both constraints in expectation. Finally, we empirically evaluate our revenue sharing scheme on real
data.
View details
Preview abstract
We consider a multidimensional search problem that is motivated by questions in contextual decision-making, such as dynamic pricing and personalized medicine. Nature selects a state from a d-dimensional unit ball and then generates a sequence of d-dimensional directions. We are given access to the directions, but not access to the state. After receiving a direction, we have to guess the value of the dot product between the state and the direction. Our goal is to minimize the number of times when our guess is more than ϵ away from the true answer. We construct a polynomial time algorithm that we call Projected Volume achieving regret O(dlog(d/ϵ)), which is optimal up to a logd factor. The algorithm combines a volume cutting strategy with a new geometric technique that we call cylindrification.
View details
Reservation Exchange Markets for Internet Advertising
Gagan Goel
Stefano Leonardi
Afshin Nikzad
LIPIcs, vol. 55, 142:1-142:13
Preview abstract
Internet display advertising industry follows two main business models. One model is based on direct deals between publishers and advertisers where they sign legal contracts containing terms of fulfillment for a future inventory. The second model is a spot market based on auctioning page views in real-time on advertising exchange (AdX) platforms such as DoubleClick's Ad Exchange, RightMedia, or AppNexus. These exchanges play the role of intermediaries who sell items (e.g. page-views) on behalf of a seller (e.g. a publisher) to buyers (e.g., advertisers) on the opposite side of the market. The computational and economics issues arising in this second model have been extensively investigated in recent times. In this work, we consider a third emerging model called reservation exchange market. A reservation exchange is a two-sided market between buyer orders for blocks of advertisers' impressions and seller orders for blocks of publishers' page views. The goal is to match seller orders to buyer orders while providing the right incentives to both sides. In this work we first describe the important features of mechanisms for efficient reservation exchange markets. We then address the algorithmic problems of designing revenue sharing schemes to provide a fair division between sellers of the revenue collected from buyers. A major conceptual contribution of this work is in showing that even though both clinching ascending auctions and VCG mechanisms achieve the same outcome from a buyer perspective, however, from the perspective of revenue sharing among sellers, clinching ascending auctions are much more informative than VCG auctions.
View details
Where to sell: Simulating auctions from learning algorithms
Hamid Nazerzadeh
Proceedings of the Seventeenth ACM Conference on Economics and Computation (EC2016)
Preview abstract
Ad Exchange platforms connect online publishers and advertisers and facilitate selling billions of impressions every day. We study these environments from the perspective of a publisher who wants to find the profit maximizing exchange to sell his inventory. Ideally, the publisher would run an auction among exchanges. However, this is not possible due to technological and other practical considerations. The publisher needs to send each impression to one of the exchanges with an asking price. We model the problem as a variation of multi-armed bandits where exchanges (arms) can behave strategically in order to maximizes their own profit. We propose mechanisms that find the best exchange with sub-linear regret and have desirable incentive properties.
View details
Preview abstract
We study the question of setting and testing reserve prices in single item auctions when the bidders are not identical. At a high level, there are two generalizations of the standard second price auction: in the lazy version we first determine the winner, and then apply reserve prices; in the eager version we first discard the bidders not meeting their reserves, and then determine the winner among the rest. We show that the two versions have dramatically different properties: lazy reserves are easy to optimize, and A/B test in production, whereas eager reserves always lead to higher welfare, but their optimization is NP-complete, and naive A/B testing will lead to incorrect conclusions. Despite their different characteristics, we show that the overall revenue for the two scenarios is always within a factor of 2 of each other, even in the presence of correlated bids. Moreover, we prove that the eager auction dominates the lazy auction on revenue whenever the bidders are independent or symmetric. We complement our theoretical results with simulations on real world data that show that even suboptimally set eager reserve prices are preferred from a revenue standpoint.
View details
Preview abstract
Despite their better revenue and welfare guarantees for repeated auctions, dynamic mechanisms have not been widely adopted in practice. This is partly due to their computational and implementation complexity, and also due to their unrealistic use of forecasting for future periods. We address the above shortcomings and present a new family of dynamic mechanisms that are computationally efficient and do not use any distribution knowledge of future periods. Our contributions are three-fold:
1. We present the first polynomial-time dynamic incentive-compatible and ex-post individually rational mechanism for multiple periods and for any number of buyers that is a constant approximation to the optimal revenue. Unlike previous mechanisms, we require no expensive pre-processing step and in each period we run a simple auction that is a combination of virtual value maximizing auctions.
2. We introduce the concept of obliviousness in dynamic mechanism design. A dynamic mechanism is oblivious if the allocation and pricing rule at each period does not depend on the type distributions in future periods. Our mechanism is oblivious and guarantees a 5-approximation compared to the optimal mechanism that knows all the distributions in advance.
3. We develop a framework for characterizing, designing, and proving lower bounds for dynamic mechanisms (oblivious or not). In addition to the aforementioned positive results, we use this characterization to show that no oblivious mechanism can produce a better-than-2 approximation to the mechanism that knows all the distributions.
View details
Feature-based Dynamic Pricing
Maxime Cohen
Ilan Lobel
Proceedings of the 2016 ACM Conference on Economics and Computation
Preview abstract
We consider the problem faced by a firm that receives highly differentiated products in an online fashion and needs to price them in order to sell them to its customer base. Products are described by vectors of features and the market value of each product is linear in the values of the features. The firm does not initially know the values of the different features, but it can learn the values of the features based on whether products were sold at the posted prices in the past. This model is motivated by a question in online advertising, where impressions arrive over time and can be described by vectors of features. We first consider a multi-dimensional version of binary search over polyhedral sets, and show that it has exponential worst-case regret. We then propose a modification of the prior algorithm where uncertainty sets are replaced by their Lowner-John ellipsoids. We show that this algorithm has a worst-case regret that is quadratic in the dimensionality of the feature space and logarithmic in the time horizon.
View details
Dynamic Auctions with Bank Accounts
Pingzhong Tang
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (2016), pp. 387-393
Preview abstract
Consider a buyer with independent additive valuations for a set of goods, and a seller who is constrained to sell one item at a time in an online fashion. If the seller is constrained to run independent auctions for each item, then he would run Myerson’s optimal auction for each item. If the seller is allowed to use the full power of dynamic mechanism design and have the auction for each item depend on the outcome of the previous auctions, he is able to perform much better. The main issues in implementing such strategies in online settings where items arrive over time are that the auction might be too complicated or it makes too strong assumptions on the buyer’s rationality or seller’s commitment over time. This motivates us to explore a restricted family of dynamic auctions that can be implemented in an online fashion and without too much commitment from the seller ahead of time. In particular, we study a set of auction in which the space of single-shot auctions is augmented with a structure that we call bank account, a real number for each node that summarizes the history so far. This structure allows the seller to store deficits or surpluses of buyer utility from each individual auction and even them out on the long run. This is akin to enforcing individual rationality constraint on average rather than per auction. We also study the effect of enforcing a maximum limit to the values that bank account might grow, which means that we enforce that besides the auction being individually rational on average it is also not far from being individually rational at any given interval. Interestingly, even with these restrictions, we can achieve
significantly better revenue and social welfare compared to separate Myerson auctions.
View details
Preview abstract
We consider a single buyer with a combinatorial preference that would like to purchase related products and services from different vendors, where each vendor supplies exactly one product. We study the general case where subsets of products can be substitutes as well as complementary and analyze the game that is induced on the vendors, where a vendor's strategy is the price that he asks for his product. This model generalizes both Bertrand competition (where vendors are perfect substitutes) and Nash bargaining (where they are perfect complements), and captures a wide variety of scenarios that can appear in complex crowd sourcing or in automatic pricing of related products.
We study the equilibria of such games and show that a pure efficient equilibrium always exists. In the case of submodular buyer preferences we fully characterize the set of pure Nash equilibria, essentially showing uniqueness. For the even more restricted "substitutes" buyer preferences we also prove uniqueness over {\em mixed} equilibria. Finally we begin the exploration of natural generalizations of our setting such as when services have costs, when there are multiple buyers or uncertainty about the the buyer's valuation, and when a single vendor supplies multiple products.
View details
Preview abstract
Constraints on agent's ability to pay play a major role in auction design for any setting where the magnitude of financial transactions is sufficiently large. Those constraints have been traditionally modeled in mechanism design as hard budget, i.e., mechanism is not allowed to charge agents more than a certain amount. Yet, real auction systems (such as Google AdWords) allow more sophisticated constraints on agents' ability to pay, such as average budgets. In this work, we investigate the design of Pareto optimal and incentive compatible auctions for agents with constrained quasi-linear utilities, which captures more realistic models of liquidity constraints that the agents may have. Our result applies to a very general class of allocation constraints known as polymatroidal environments, encompassing many settings of interest such as multi-unit auctions, matching markets, video-on demand and advertisement systems.
Our design is based Ausubel's clinching framework. Incentive compatibility and feasibility with respect to ability-to-pay constraints are direct consequences of the clinching framework. Pareto-optimality, on the other hand, is considerably more challenging, since the no-trade condition that characterizes it depends not only on whether agents have their budgets exhausted or not, but also on prices {at} which the goods are allocated. In order to get a handle on those prices, we introduce novel concepts of dropping prices and saturation. These concepts lead to our main structural result which is a characterization of the tight sets in the clinching auction outcome and its relation to dropping prices.
View details
Preview abstract
Auctions for perishable goods such as internet ad inventory need to make real-time allocation and pricing decisions as the supply of the good arrives in an online manner, without knowing the entire supply in advance. These allocation and pricing decisions get complicated when buyers have some global constraints. In this work, we consider a multi-unit model where buyers have global {\em budget} constraints, and the supply arrives in an online manner. Our main contribution is to show that for this setting there is an individually-rational, incentive-compatible and Pareto-optimal auction that allocates these units and calculates prices on the fly, without knowledge of the total supply. We do so by showing that the Adaptive Clinching Auction satisfies a {\em supply-monotonicity} property.
We also analyze and discuss, using examples, how the insights gained by the allocation and payment rule can be applied to design better ad allocation heuristics in practice. Finally, while our main technical result concerns multi-unit supply, we propose a formal model of online supply that captures scenarios beyond multi-unit supply and has applications to sponsored search. We conjecture that our results for multi-unit auctions can be extended to these more general models.
View details
Preview abstract
A central issue in applying auction theory in practice is the problem of dealing with budget-constrained agents. A desirable goal in practice is to design incentive compatible, individually rational, and Pareto optimal auctions while respecting the budget constraints. Achieving this goal is particularly challenging in the presence of nontrivial combinatorial constraints over the set of feasible allocations.
Toward this goal and motivated by AdWords auctions, we present an auction for polymatroidal environments satisfying these properties. Our auction employs a novel clinching technique with a clean geometric description and only needs an oracle access to the submodular function defining the polymatroid. As a result, this auction not only simplifies and generalizes all previous results, it applies to several new applications including AdWords Auctions, bandwidth markets, and video on demand. In particular, our characterization of the AdWords auction as polymatroidal constraints might be of independent interest. This allows us to design the first mechanism for Ad Auctions taking into account simultaneously budgets, multiple keywords and multiple slots.
We show that it is impossible to extend this result to generic polyhedral constraints. This also implies an impossibility result for multiunit auctions with decreasing marginal utilities in the presence of budget constraints.
View details
Pricing public goods for private sale
Michal Feldman
David Kempe
Brendan Lucier
Proceedings of the 14th ACM Conference on Eletronic Commerce (EC 2013), pp. 417-434
Signaling schemes for revenue maximization
Yuval Emek
Michal Feldman
Iftah Gamzu
Moshe Tennenholtz
Proceedings of the 13th ACM Conference on Eletronic Commerce (EC 2012), pp. 514-531
The curse of simultaneity
Vasilis Syrgkanis
Éva Tardos
Proceedings of the 3rd Innovations in Theoretical Computer Science conference (ITCS 2012, pp. 60-67
Optimal mechanisms for selling information
Moshe Babaioff
Robert Kleinberg
13th ACM Conference on Eletronic Commerce (EC 2012), pp. 92-109
Sequential auctions and externalities
Vasilis Syrgkanis
Éva Tardos
Proceedings of the 24rd ACM-SIAM Symposium of Discrete Algorithms (SODA 2013) (2012), pp. 869-886
On revenue in the generalized second price auction
Brendan Lucier
Éva Tardos
Proceedings of the 21st International World Wide Web Conference (WWW 2012), pp. 361-370
The dining bidder problem: à la russe et à la française
GSP auctions with correlated types
Brendan Lucier
Proceedings of the 12th ACM Conference on Electronic Commerce (EC 2011), pp. 71-80
Pure and Bayes-Nash Price of Anarchy for Generalized Second Price Auction
Éva Tardos
Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), pp. 735-744
