SU\G(𝔸)/K·U
Sign Up for free Log In

Author Description

Login to generate an author description

Ask a Question About This Mathematician

Stochastic bandits robust to adversarial corruptions

2018-06-20
Thodoris Lykouris , Vahab Mirrokni , Renato Paes Leme
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 … 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.
View PDF Chat

Optimal mechanisms for selling information

2012-06-04
Moshe Babaioff , Robert Kleinberg , Renato Paes Leme
The buying and selling of information is taking place at a scale unprecedented in the history of commerce, thanks to the formation of online marketplaces for user data. Data providing … The buying and selling of information is taking place at a scale unprecedented in the history of commerce, thanks to the formation of online marketplaces for user data. Data providing agencies sell user information to advertisers to allow them to match ads to viewers more effectively. In this paper we study the design of optimal mechanisms for a monopolistic data provider to sell information to a buyer, in a model where both parties have (possibly correlated) private signals about a state of the world, and the buyer uses information learned from the seller, along with his own signal, to choose an action (e.g., displaying an ad) whose payoff depends on the state of the world.
View PDF Chat

Bounding the inefficiency of outcomes in generalized second price auctions

2014-04-30
Ioannis Caragiannis , Christos Kaklamanis , Panagiotis Kanellopoulos +4 more
View PDF Chat

Sequential Auctions and Externalities

2012-01-17
Renato Paes Leme , Vasilis Syrgkanis , Éva Tardos
In many settings agents participate in multiple different auctions that are not necessarily implemented simultaneously. Future opportunities affect strategic considerations of the players in each auction, introducing externalities. Motivated by … In many settings agents participate in multiple different auctions that are not necessarily implemented simultaneously. Future opportunities affect strategic considerations of the players in each auction, introducing externalities. Motivated by this consideration, we study a setting of a market of buyers and sellers, where each seller holds one item, bidders have combinatorial valuations and sellers hold item auctions sequentially.Our results are qualitatively different from those of simultaneous auctions, proving that simultaneity is a crucial aspect of previous work. We prove that if sellers hold sequential first price auctions then for unit-demand bidders (matching market) every subgame perfect equilibrium achieves at least half of the optimal social welfare, while for submodular bidders or when second price auctions are used, the social welfare can be arbitrarily worse than the optimal. We also show that a first price sequential auction for buying or selling a base of a matroid is always efficient, and implements the VCG outcome.An important tool in our analysis is studying first and second price auctions with externalities (bidders have valuations for each possible winner outcome), which can be of independent interest. We show that a Pure Nash Equilibrium always exists in a first price auction with externalities.
View PDF Chat

Polyhedral clinching auctions and the adwords polytope

2012-05-19
Gagan Goel , Vahab Mirrokni , Renato Paes Leme
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 … 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 the above 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.
View PDF Chat

Efficiency Guarantees in Auctions with Budgets

2014-01-01
Shahar Dobzinski , Renato Paes Leme
View PDF Chat

On the efficiency of the walrasian mechanism

2014-05-30
Moshe Babaioff , Brendan Lucier , Noam Nisan +1 more
Central results in economics guarantee the existence of efficient equilibria for various classes of markets. An underlying assumption in early work is that agents are price-takers, i.e., agents honestly report … Central results in economics guarantee the existence of efficient equilibria for various classes of markets. An underlying assumption in early work is that agents are price-takers, i.e., agents honestly report their true demand in response to prices. A line of research in economics, initiated by Hurwicz (1972), is devoted to understanding how such markets perform when agents are strategic about their demands. This is captured by the Walrasian Mechanism that proceeds by collecting reported demands, finding clearing prices in the reported market via an ascending price tatonnement procedure, and returns the resulting allocation. Similar mechanisms are used, for example, in the daily opening of the New York Stock Exchange and the call market for copper and gold in London.
View PDF Chat

Polyhedral Clinching Auctions and the AdWords Polytope

2015-06-30
Gagan Goel , Vahab Mirrokni , Renato Paes Leme
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 … 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 PDF Chat

A Field Guide to Personalized Reserve Prices

2016-04-11
Renato Paes Leme , Martin Pál , Sergei Vassilvitskii
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 … 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 PDF Chat

On the efficiency of equilibria in generalized second price auctions

2012-01-31
Ioannis Caragiannis , Christos Kaklamanis , Panagiotis Kanellopoulos +4 more
The Generalized Second Price (GSP) auction is the primary auction used for monetizing the use of the Internet. It is well-known that truthtelling is not a dominant strategy in this … The Generalized Second Price (GSP) auction is the primary auction used for monetizing the use of the Internet. It is well-known that truthtelling is not a dominant strategy in this auction and that inefficient equilibria can arise. In this paper we study the space of equilibria in GSP, and quantify the efficiency loss that can arise in equilibria under a wide range of sources of uncertainty, as well as in the full information setting. The traditional Bayesian game models uncertainty in the valuations (types) of the participants. The Generalized Second Price (GSP) auction gives rise to a further form of uncertainty: the selection of quality factors resulting in uncertainty about the behavior of the underlying ad allocation algorithm. The bounds we obtain apply to both forms of uncertainty, and are robust in the sense that they apply under various perturbations of the solution concept, extending to models with information asymmetries and bounded rationality in the form of learning strategies. We present a constant bound (2.927) on the factor of the efficiency loss (\emph{price of anarchy}) of the corresponding game for the Bayesian model of partial information about other participants and about ad quality factors. For the full information setting, we prove a surprisingly low upper bound of 1.282 on the price of anarchy over pure Nash equilibria, nearly matching a lower bound of 1.259 for the case of three advertisers. Further, we do not require that the system reaches equilibrium, and give similarly low bounds also on the quality degradation for any no-regret learning outcome. Our conclusion is that the number of advertisers in the auction has almost no impact on the price of anarchy, and that the efficiency of GSP is very robust with respect to the belief and rationality assumptions imposed on the participants.

Multidimensional Binary Search for Contextual Decision-Making

2018-07-25
Ilan Lobel , Renato Paes Leme , Adrian Vladu
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 … 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 log d factor. The algorithm combines a volume cutting strategy with a new geometric technique that we call cylindrification.
View PDF Chat

Signaling Schemes for Revenue Maximization

2012-02-08
Yuval Emek , Michal Feldman , Iftah Gamzu +2 more
Signaling is an important topic in the study of asymmetric information in economic settings. In particular, the transparency of information available to a seller in an auction setting is a … Signaling is an important topic in the study of asymmetric information in economic settings. In particular, the transparency of information available to a seller in an auction setting is a question of major interest. We introduce the study of signaling when conducting a second price auction of a probabilistic good whose actual instantiation is known to the auctioneer but not to the bidders. This framework can be used to model impressions selling in display advertising. We study the problem of computing a signaling scheme that maximizes the auctioneer's revenue in a Bayesian setting. While the general case is proved to be computationally hard, several cases of interest are shown to be polynomially solvable. In addition, we establish a tight bound on the minimum number of signals required to implement an optimal signaling scheme and show that at least half of the maximum social welfare can be preserved within such a scheme.

Contextual Search via Intrinsic Volumes

2018-10-01
Renato Paes Leme , Jon Schneider
We study the problem of contextual search, a multidimensional generalization of binary search that captures many problems in contextual decision-making. In contextual search, a learner is trying to learn the … We study the problem of contextual search, a multidimensional generalization of binary search that captures many problems in contextual decision-making. In contextual search, a learner is trying to learn the value of a hidden vector. Every round the learner is provided an adversarially-chosen context vector, submits a guess for the inner product of the context vector with the hidden vector, learns whether their guess was too high or too low, and incurs some loss based on the quality of their guess. The learner's goal is to minimize their total loss over the course of some number of rounds. We present an algorithm for the contextual search problem for the symmetric loss function that achieves constant 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 doubly-logarithmic total loss, improving exponentially on the previous best known upper bounds and matching the known lower bounds (up to a polynomial dependence on dimension). 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 PDF Chat

Price competition in online combinatorial markets

2014-04-07
Moshe Babaioff , Noam Nisan , Renato Paes Leme
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 … 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.
View PDF Chat

Optimal dynamic mechanisms with ex-post IR via bank accounts

2016-01-01
Vahab Mirrokni , Renato Paes Leme , Pingzhong Tang +1 more
Lately, the problem of designing multi-stage dynamic mechanisms has been shown to be both theoretically challenging and practically important. In this paper, we consider the problem of designing revenue optimal … Lately, the problem of designing multi-stage dynamic mechanisms has been shown to be both theoretically challenging and practically important. In this paper, we consider the problem of designing revenue optimal dynamic mechanism for a setting where an auctioneer sells a set of items to a buyer in multiple stages. At each stage, there could be multiple items for sale but each item can only appear in one stage. The type of the buyer at each stage is thus a multi-dimensional vector characterizing the buyer's valuations of the items at that stage and is assumed to be stage-wise independent. In particular, we propose a novel class of mechanisms called bank account mechanisms. Roughly, a bank account mechanism is no different from any stage-wise individual mechanism except for an augmented structure called bank account, a real number for each node that summarizes the history so far. We first establish that the optimal revenue from any dynamic mechanism in this setting can be achieved by a bank account mechanism, and we provide a simple characterization of the set of incentive compatible and ex-post individually rational bank account mechanisms. Based on these characterizations, we then investigate the problem of finding the (approximately) optimal bank account mechanisms. We prove that there exists a simple, randomized bank account mechanism that approximates optimal revenue up to a constant factor. Our result is general and can accommodate previous approximation results in single-shot multi-dimensional mechanism design. Based on the previous mechanism, we further show that there exists a deterministic bank account mechanism that achieves constant-factor approximation as well. Finally, we consider the problem of computing optimal mechanisms when the type space is discrete and provide an FPTAS via linear and dynamic programming.

Improved Revenue Bounds for Posted-Price and Second-Price Mechanisms

2021-10-19
Hedyeh Beyhaghi , Negin Golrezaei , Renato Paes Leme +2 more
How to optimize posted price mechanisms? The sequential posted-price (SPP) mechanism is one of the widely used selling mechanisms in practice. In this mechanism, the seller presents each buyer with … How to optimize posted price mechanisms? The sequential posted-price (SPP) mechanism is one of the widely used selling mechanisms in practice. In this mechanism, the seller presents each buyer with a price sequentially and the buyer can either accept or reject the mechanism's offer. Despite the widespread use of the SPP mechanism, the problem of optimizing prices in this mechanism has not been fully addressed. In a paper entitled, “Improved Revenue Bounds for Posted-Price and Second-Price Mechanisms,” H. Beyhaghi, N. Golrezaei, R. Paes Leme, M. Pal, and B. Sivan construct SPP mechanisms by considering the best of two simple pricing rules: one that imitates the optimal mechanism and the other that posts a uniform price (same price for every buyer). Their simple pricing rules can be easily generalized to the setting with multiple units and yield the first improvement over long-established approximation factors.
View PDF Chat

Improved Approximations for Free-Order Prophets and Second-Price Auctions.

2018-07-10
Hedyeh Beyhaghi , Negin Golrezaei , Renato Paes Leme +2 more
We study the fundamental problem of selling a single indivisible item to one of $n$ buyers with independent and potentially nonidentical value distributions. We focus on two simple and widely … We study the fundamental problem of selling a single indivisible item to one of $n$ buyers with independent and potentially nonidentical value distributions. We focus on two simple and widely used selling mechanisms: the second price auction with \emph{eager} personalized reserve prices and the sequential posted price mechanism. Using a new approach, we improve the best-known performance guarantees for these mechanisms. We show that for every value of the number of buyers $n$, the eager second price (ESP) auction and sequential posted price mechanisms respectively earn at least $0.6620$ and $0.6543$ fractions of the optimal revenue. We also provide improved performance guarantees for these mechanisms when the number of buyers is small, which is the more relevant regime for many applications of interest. This in particular implies an improved bound of $0.6543$ for free-order prophet inequalities. Motivated by our improved revenue bounds, we further study the problem of optimizing reserve prices in the ESP auctions when the sorted order of personalized reserve prices among bidders is exogenous. We show that this problem can be solved polynomially. In addition, by analyzing a real auction dataset from Google's advertising exchange, we demonstrate the effectiveness of order-based pricing.

Why Do Competitive Markets Converge to First-Price Auctions?

2020-04-20
Renato Paes Leme , Balasubramanian Sivan , Yifeng Teng
We consider a setting in which bidders participate in multiple auctions run by different sellers, and optimize their bids for the aggregate auction. We analyze this setting by formulating a … We consider a setting in which bidders participate in multiple auctions run by different sellers, and optimize their bids for the 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 PDF Chat

Pricing public goods for private sale

2013-06-16
Michal Feldman , David Kempe , Brendan Lucier +1 more
We consider the pricing problem faced by a seller who assigns a price to a good that confers its benefits not only to its buyers, but also to other individuals … We consider the pricing problem faced by a seller who assigns a price to a good that confers its benefits not only to its buyers, but also to other individuals around them. For example, a snow-blower is potentially useful not only to the household that buys it, but also to others on the same street. Given that the seller is constrained to selling such a (locally) public good via individual private sales, how should he set his prices given the distribution of values held by the agents?
View PDF Chat

Tight Bounds for Approximate Carathéodory and Beyond

2015-01-01
Vahab Mirrokni , Renato Paes Leme , Adrian Vladu +1 more
We give a deterministic nearly-linear time algorithm for approximating any point inside a convex polytope with a sparse convex combination of the polytope's vertices. Our result provides a constructive proof … We give a deterministic nearly-linear time algorithm for approximating any point inside a convex polytope with a sparse convex combination of the polytope's vertices. Our result provides a constructive proof for the Approximate Carathéodory Problem, which states that any point inside a polytope contained in the $\ell_p$ ball of radius $D$ can be approximated to within $ε$ in $\ell_p$ norm by a convex combination of only $O\left(D^2 p/ε^2\right)$ vertices of the polytope for $p \geq 2$. We also show that this bound is tight, using an argument based on anti-concentration for the binomial distribution. Along the way of establishing the upper bound, we develop a technique for minimizing norms over convex sets with complicated geometry; this is achieved by running Mirror Descent on a dual convex function obtained via Sion's Theorem. As simple extensions of our method, we then provide new algorithms for submodular function minimization and SVM training. For submodular function minimization we obtain a simplification and (provable) speed-up over Wolfe's algorithm, the method commonly found to be the fastest in practice. For SVM training, we obtain $O(1/ε^2)$ convergence for arbitrary kernels; each iteration only requires matrix-vector operations involving the kernel matrix, so we overcome the obstacle of having to explicitly store the kernel or compute its Cholesky factorization.

Clinching auctions beyond hard budget constraints

2014-05-30
Gagan Goel , Vahab Mirrokni , Renato Paes Leme
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 … 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.
View PDF Chat

Pricing public goods for private sale

2013-06-11
Michal Feldman , David Kempe , Brendan Lucier +1 more
We consider the pricing problem faced by a seller who assigns a price to a good that confers its benefits not only to its buyers, but also to other individuals … We consider the pricing problem faced by a seller who assigns a price to a good that confers its benefits not only to its buyers, but also to other individuals around them. For example, a snow-blower is potentially useful not only to the household that buys it, but also to others on the same street. Given that the seller is constrained to selling such a (locally) public good via individual private sales, how should he set his prices given the distribution of values held by the agents?
View PDF Chat

Optimal Contextual Pricing and Extensions

2021-01-01
Allen Liu , Renato Paes Leme , Jon Schneider
In the contextual pricing problem a seller repeatedly obtains products described by an adversarially chosen feature vector in ℝd and only observes the purchasing decisions of a buyer with a … In the contextual pricing problem a seller repeatedly obtains products described by an adversarially chosen feature vector in ℝ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 Ω(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 Ω(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 : → in a certain hypothesis class ℋ. We provide a generic algorithm with O(d2) regret where d is the covering dimension of this class. This leads in particular to a Õ(s2) 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 PDF Chat

LP-based Approximation for Personalized Reserve Prices

2019-06-17
Mahsa Derakhshan , Negin Golrezaei , Renato Paes Leme
We study the problem of computing personalized reserve prices in eager second price auctions without having any assumption on valuation distributions. Here, the input is a dataset that contains the … We study the problem of computing personalized reserve prices in eager second price auctions without having any assumption on valuation distributions. Here, the input is a dataset that contains the submitted bids of n buyers in a set of auctions and the goal is to return personalized reserve prices r that maximize the revenue earned on these auctions by running eager second price auctions with reserve r. We present a novel LP formulation to this problem and a rounding procedure which achieves a (1+2(√2-1)e√2-2)-1≅0.684-approximation. This improves over the 1/2-approximation Algorithm due to Roughgarden and Wang. We show that our analysis is tight for this rounding procedure. We also bound the integrality gap of the LP, which bounds the performance of any algorithm based on this LP.
View PDF Chat

Clinching Auctions with Online Supply

2013-01-06
Gagan Goel , Vahab Mirrokni , Renato Paes Leme
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 … 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 PDF Chat

Multidimensional Binary Search for Contextual Decision-Making

2017-06-20
Ilan Lobel , Renato Paes Leme , Adrian Vladu
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 … 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 PDF Chat

Clinching auctions with online supply

2015-12-18
Gagan Goel , Vahab Mirrokni , Renato Paes Leme
View PDF Chat

Variable Decomposition for Prophet Inequalities and Optimal Ordering

2021-07-18
Allen Liu , Renato Paes Leme , Martin Pál +2 more
We introduce a new decomposition technique for random variables that maps a generic instance of the prophet inequalities problem to a new instance where all but a constant number of … We introduce a new decomposition technique for random variables that maps a generic instance of the prophet inequalities problem to a new instance where all but a constant number of variables have a tractable structure that we refer to as (ε, δ)-smallness. Using this technique, we make progress on several outstanding problems in the area: We show that, even in the case of non-identical distributions, it is possible to achieve (arbitrarily close to) the optimal approximation ratio of β ~0.745 when the items arrive in a random order (this version is commonly known as prophet secretary) as long as we are allowed to remove a small constant number of distributions. We show that forfrequent instances (where each distribution reoccurs some number of times) and random arrival order, it is possible to achieve the optimal approximation ratio of β (improving over the previous best-known bound of 0.738). We give a new, simpler proof of Kertz's optimal approximation guarantee of β ~0.745 for prophet inequalities with i.i.d. distributions. The proof is primal-dual and simultaneously produces upper and lower bounds. Using this decomposition in combination with a novel convex programming formulation, we construct the first (in parallel work with[1]) an Efficient PTAS (EPTAS) for the Optimal Ordering problem.
View PDF Chat

Core-competitive Auctions

2015-06-12
Gagan Goel , Mohammad Reza Khani , Renato Paes Leme
One of the major drawbacks of the celebrated VCG auction is its low (or zero) revenue even when the agents have high value for the goods and a competitive outcome … One of the major drawbacks of the celebrated VCG auction is its low (or zero) revenue even when the agents have high value for the goods and a competitive outcome would have generated a significant revenue. A competitive outcome is one for which it is impossible for the seller and a subset of buyers to 'block' the auction by defecting and negotiating an outcome with higher payoffs for themselves. This corresponds to the well-known concept of core in cooperative game theory.
View PDF Chat

Price Competition, Fluctuations and Welfare Guarantees

2015-06-12
Moshe Babaioff , Renato Paes Leme , Balasubramanian Sivan
In various markets where sellers compete in price, price oscillations are observed rather than convergence to equilibrium. Such fluctuations have been empirically observed in the retail market for gasoline, in … In various markets where sellers compete in price, price oscillations are observed rather than convergence to equilibrium. Such fluctuations have been empirically observed in the retail market for gasoline, in airline pricing and in the online sale of consumer goods. Motivated by this, we study a model of price competition in which equilibria rarely exist. We seek to analyze the welfare, despite the nonexistence of equilibria, and present welfare guarantees as a function of the market power of the sellers. We first study best response dynamics in markets with sellers that provide a homogeneous good, and show that except for a modest number of initial rounds, the welfare is guaranteed to be high. We consider two variations: in the first the sellers have full information about the buyer's valuation. Here we show that if there are n items available across all sellers and nmax is the maximum number of items controlled by any given seller, then the ratio of the optimal welfare to the achieved welfare will be at most log n/(n-nmax + 1))+1. As the market power of the largest seller diminishes, the welfare becomes closer to optimal. In the second variation we consider an extended model in which sellers have uncertainty about the buyer's valuation. Here we similarly show that the welfare improves as the market power of the larger seller decreases, yet with a worse ratio of n/(n-nmax + 1). Our welfare bounds in both cases are essentially tight. The exponential gap in welfare between the two variations quantifies the value of accurately learning the buyer's valuation in such settings.
View PDF Chat

Improved Social Welfare Bounds for GSP at Equilibrium

2010-11-14
Brendan Lucier , Renato Paes Leme
The Generalized Second Price auction is the primary method by which sponsered search advertisements are sold. We study the performance of this auction under various equilibrium concepts. In particular, we … The Generalized Second Price auction is the primary method by which sponsered search advertisements are sold. We study the performance of this auction under various equilibrium concepts. In particular, we demonstrate that the Bayesian Price of Anarchy is at most $2(1-1/e)^{-1} \approx 3.16$, significantly improving upon previously known bounds. Our techniques are intuitively straightforward and extend in a number of ways. For one, our result extends to a bound on the performance of GSP at coarse correlated equilibria, which captures (for example) a repeated-auction setting in which agents apply regret-minimizing bidding strategies. In addition, our analysis is robust against the presence of byzantine agents who cannot be assumed to participate rationally. Additionally, we present tight bounds for the social welfare obtained at pure NE for the special case of an auction for 3 slots, and discuss potential methods for extending this analysis to an arbitrary number of slots.

Bounding the inefficiency of outcomes in generalized second price auctions

2012-01-31
Ioannis Caragiannis , Christos Kaklamanis , Panagiotis Kanellopoulos +4 more
The Generalized Second Price (GSP) auction is the primary auction used for monetizing the use of the Internet. It is well-known that truthtelling is not a dominant strategy in this … The Generalized Second Price (GSP) auction is the primary auction used for monetizing the use of the Internet. It is well-known that truthtelling is not a dominant strategy in this auction and that inefficient equilibria can arise. In this paper we study the space of equilibria in GSP, and quantify the efficiency loss that can arise in equilibria under a wide range of sources of uncertainty, as well as in the full information setting. The traditional Bayesian game models uncertainty in the valuations (types) of the participants. The Generalized Second Price (GSP) auction gives rise to a further form of uncertainty: the selection of quality factors resulting in uncertainty about the behavior of the underlying ad allocation algorithm. The bounds we obtain apply to both forms of uncertainty, and are robust in the sense that they apply under various perturbations of the solution concept, extending to models with information asymmetries and bounded rationality in the form of learning strategies. We present a constant bound (2.927) on the factor of the efficiency loss (\emph{price of anarchy}) of the corresponding game for the Bayesian model of partial information about other participants and about ad quality factors. For the full information setting, we prove a surprisingly low upper bound of 1.282 on the price of anarchy over pure Nash equilibria, nearly matching a lower bound of 1.259 for the case of three advertisers. Further, we do not require that the system reaches equilibrium, and give similarly low bounds also on the quality degradation for any no-regret learning outcome. Our conclusion is that the number of advertisers in the auction has almost no impact on the price of anarchy, and that the efficiency of GSP is very robust with respect to the belief and rationality assumptions imposed on the participants.

Stochastic bandits robust to adversarial corruptions

2018-03-25
Thodoris Lykouris , Vahab Mirrokni , Renato Paes Leme
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 … 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. In our model, the rewards for all arms are initially drawn from a distribution and are then altered by an adaptive adversary. We provide a simple algorithm whose performance gracefully degrades with the total corruption the adversary injected in the data, measured by the sum across rounds of the biggest alteration the adversary made in the data in that round; this total corruption is denoted by $C$. Our algorithm provides a guarantee that retains the optimal guarantee (up to a logarithmic term) if the input is stochastic and whose performance degrades linearly to the amount of corruption $C$, while crucially being agnostic to it. We also provide a lower bound showing that this linear degradation is necessary if the algorithm achieves optimal performance in the stochastic setting (the lower bound works even for a known amount of corruption, a special case in which our algorithm achieves optimal performance without the extra logarithm).

On the Construction of Substitutes

2019-07-18
Eric Balkanski , Renato Paes Leme
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 … 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. Because 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 four items.
View PDF Chat

On the Construction of Substitutes

2018-06-11
Eric Balkanski , Renato Paes Leme
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 … 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 PDF Chat

Secretaries with Advice

2020-11-13
Paul Dütting , Silvio Lattanzi , Renato Paes Leme +1 more
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? … 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 on arrival, to more modern versions of advice in the form of samples, to an ML-inspired model where a classifier gives us noisy signal 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. Using tools from linear programming, we present a tight analysis of optimal algorithms for secretaries with samples, optimal algorithms when secretaries' qualities are drawn from a known distribution, and a new noisy binary advice model.

Price Competition in Online Combinatorial Markets

2014-01-08
Moshe Babaioff , Noam Nisan , Renato Paes Leme
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 … 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 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.

Bandits with adversarial scaling

2020-03-04
Thodoris Lykouris , Vahab Mirrokni , Renato Paes Leme
We study scaling, a multi-armed bandit model where rewards have a stochastic and an adversarial component. Our model captures display advertising where the click-through-rate can be decomposed to a (fixed … We study scaling, a multi-armed bandit model where rewards have a stochastic and an adversarial component. Our model captures display advertising where the click-through-rate can be decomposed to a (fixed across time) arm-quality component and a non-stochastic user-relevance component (fixed across arms). Despite the relative stochasticity of our model, we demonstrate two settings where most bandit algorithms suffer. On the positive side, we show that two algorithms, one from the action elimination and one from the mirror descent family are adaptive enough to be robust to adversarial scaling. Our results shed light on the robustness of adaptive parameter selection in stochastic bandits, which may be of independent interest.

Improved Revenue Bounds for Posted-Price and Second-Price Mechanisms

2018-07-10
Hedyeh Beyhaghi , Negin Golrezaei , Renato Paes Leme +2 more
We study revenue maximization through sequential posted-price (SPP) mechanisms in single-dimensional settings with $n$ buyers and independent but not necessarily identical value distributions. We construct the SPP mechanisms by considering … We study revenue maximization through sequential posted-price (SPP) mechanisms in single-dimensional settings with $n$ buyers and independent but not necessarily identical value distributions. We construct the SPP mechanisms by considering the best of two simple pricing rules: one that imitates the revenue optimal mchanism, namely the Myersonian mechanism, via the taxation principle and the other that posts a uniform price. Our pricing rules are rather generalizable and yield the first improvement over long-established approximation factors in several settings. We design factor-revealing mathematical programs that crisply capture the approximation factor of our SPP mechanism. In the single-unit setting, our SPP mechanism yields a better approximation factor than the state of the art prior to our work (Azar, Chiplunkar & Kaplan, 2018). In the multi-unit setting, our SPP mechanism yields the first improved approximation factor over the state of the art after over nine years (Yan, 2011 and Chakraborty et al., 2010). Our results on SPP mechanisms immediately imply improved performance guarantees for the equivalent free-order prophet inequality problem. In the position auction setting, our SPP mechanism yields the first higher-than $1-1/e$ approximation factor. In eager second-price (ESP) auctions, our two simple pricing rules lead to the first improved approximation factor that is strictly greater than what is obtained by the SPP mechanism in the single-unit setting.

Contextual Search via Intrinsic Volumes

2022-07-18
Renato Paes Leme , Jon Schneider
We study the problem of contextual search, a multidimensional generalization of binary search that captures many problems in contextual decision-making. In contextual search, a learner is trying to learn the … We study the problem of contextual search, a multidimensional generalization of binary 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 \in [0,1]^d$. Every round the learner is provided an adversarially chosen context $u_t \in \R^d$, submits a guess $p_t$ for the value of $\langle u_t, v\rangle$, learns whether $p_t < \langle u_t, v\rangle$, and incurs loss $\ell(\langle u_t, v\rangle, p_t)$ (for some loss function $\ell$). 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 $\ell(\theta, p) = |\theta - p|$ that achieves $O_{d}(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 $O_{d}(\log \log T)$ total loss, improving on the previous best known upper bounds of $O_{d}(\log T)$ 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 PDF Chat

Multidimensional Binary Search for Contextual Decision-Making

2016-11-02
Ilan Lobel , Renato Paes Leme , Adrian Vladu
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 … 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 $\epsilon$ away from the true answer. We construct a polynomial time algorithm that we call Projected Volume achieving regret $O(d\log(d/\epsilon))$, which is optimal up to a $\log d$ factor. The algorithm combines a volume cutting strategy with a new geometric technique that we call cylindrification.

Pricing Query Complexity of Revenue Maximization

2023-01-01
Renato Paes Leme , Balasubramanian Sivan , Yifeng Teng +1 more
The common way to optimize auction and pricing systems is to set aside a small fraction of the traffic to run experiments. This leads to the question: how can we … The common way to optimize auction and pricing systems is to set aside a small fraction of the traffic to run experiments. This leads to the question: how can we learn the most with the smallest amount of data? For truthful auctions, this is the sample complexity problem. For posted price auctions, we no longer have access to samples. Instead, the algorithm is allowed to choose a price pt; then for a fresh sample vt ~ D we learn the sign st = sign(pt — vt) ∈ {-1, +1}. How many pricing queries are needed to estimate a given parameter of the underlying distribution?We give tight upper and lower bounds on the number of pricing queries required to find an approximately optimal reserve price for general, regular and MHR distributions. Interestingly, for regular distributions, the pricing query and sample complexities match. But for general and MHR distributions, we show a strict separation between them.All known results on sample complexity for revenue optimization follow from a variant of using the optimal reserve price of the empirical distribution. In the pricing query complexity setting, we show that learning the entire distribution within an error of ε in Levy distance requires strictly more pricing queries than to estimate the reserve. Instead, our algorithm uses a new property we identify called relative flatness to quickly zoom into the right region of the distribution to get the optimal pricing query complexity.* The full version of the paper can be accessed at https://arxiv.org/abs/2111.03158
View PDF Chat

Multiparameter Bernoulli factories

2023-10-01
Renato Paes Leme , Jon Schneider
We consider the problem of computing with many coins of unknown bias. We are given access to samples of n coins with unknown biases p1,…,pn and are asked to sample … We consider the problem of computing with many coins of unknown bias. We are given access to samples of n coins with unknown biases p1,…,pn and are asked to sample from a coin with bias f(p1,…,pn) for a given function f:[0,1]n→[0,1]. We give a complete characterization of the functions f for which this is possible. As a consequence, we show how to extend various combinatorial sampling procedures (most notably, the classic Sampford sampling for k-subsets) to the boundary of the hypercube.
View PDF Chat

Mechanism Design for Large Language Models

2024-05-08
Paul Dütting , Vahab Mirrokni , Renato Paes Leme +2 more
View PDF Chat

Computing Walrasian Equilibria: Fast Algorithms and Economic Insights.

2015-11-12
Renato Paes Leme , Sam Chiu-wai Wong
We give the first polynomial algorithm to compute a Walrasian equilibrium in an economy with indivisible goods and general valuations having only access to an aggregate demand oracle, i.e., an … We give the first polynomial algorithm to compute a Walrasian equilibrium in an economy with indivisible goods and general valuations having only access to an aggregate demand oracle, i.e., an oracle that given a price vector, returns the aggregated demand over the entire population of buyers. Our algorithm queries the aggregate demand oracle $\tilde{O}(n)$ times and takes $\tilde{O}(n^3)$ time, where n is the number of items. We also give the fastest known algorithm for computing Walrasian equilibrium for gross substitute valuations in the value oracle model. Our algorithm has running time $\tilde{O}((mn+n^3 )T_V)$ where $T_V$ is the cost of querying the value oracle. En route, we give necessary and sufficient conditions for the existence of robust Walrasian prices, i.e., price vectors such that 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.

Computing Walrasian Equilibria: Fast Algorithms and Structural Properties

2017-01-01
Renato Paes Leme , Sam Chiu-wai Wong
We present the first polynomial time algorithm for computing Walrasian equilibrium in an economy with indivisible goods and general buyer valuations having only access to an aggregate demand oracle, i.e., … We present the first polynomial time algorithm for computing Walrasian equilibrium in an economy with indivisible goods and general buyer valuations having only access to an 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 Õ(n) times and takes Õ(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 value oracle model. Our algorithm has running time Õ((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 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 PDF Chat

Learning to Clear the Market

2019-06-04
Weiran Shen , Sébastien Lahaie , Renato Paes Leme
The problem of market clearing is to set a price for an item such that quantity demanded equals quantity supplied. In this work, we cast the problem of predicting clearing … The problem of market clearing is to set a price for an item such that quantity demanded equals quantity supplied. In this work, we cast the problem of predicting clearing prices into a learning framework and use the resulting models to perform revenue optimization in auctions and markets with contextual information. The economic intuition behind market clearing allows us to obtain fine-grained control over the aggressiveness of the resulting pricing policy, grounded in theory. To evaluate our approach, we fit a model of clearing prices over a massive dataset of bids in display ad auctions from a major ad exchange. The learned prices outperform other modeling techniques in the literature in terms of revenue and efficiency trade-offs. Because of the convex nature of the clearing loss function, the convergence rate of our method is as fast as linear regression.

A Field Guide to Personalized Reserve Prices

2016-02-24
Renato Paes Leme , Martin Pál , Sergei Vassilvitskii
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 … 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.

Efficiency Guarantees in Auctions with Budgets

2013-04-26
Shahar Dobzinski , Renato Paes Leme
In settings where players have a limited access to liquidity, represented in the form of budget constraints, efficiency maximization has proven to be a challenging goal. In particular, the social … In settings where players have a limited access to liquidity, represented in the form of budget constraints, efficiency maximization has proven to be a challenging goal. In particular, the social welfare cannot be approximated by a better factor then the number of players. Therefore, the literature has mainly resorted to Pareto-efficiency as a way to achieve efficiency in such settings. While successful in some important scenarios, in many settings it is known that either exactly one incentive-compatible auction that always outputs a Pareto-efficient solution, or that no truthful mechanism can always guarantee a Pareto-efficient outcome. Traditionally, impossibility results can be avoided by considering approximations. However, Pareto-efficiency is a binary property (is either satisfied or not), which does not allow for approximations. In this paper we propose a new notion of efficiency, called \emph{liquid welfare}. This is the maximum amount of revenue an omniscient seller would be able to extract from a certain instance. We explain the intuition behind this objective function and show that it can be 2-approximated by two different auctions. Moreover, we show that no truthful algorithm can guarantee an approximation factor better than 4/3 with respect to the liquid welfare, and provide a truthful auction that attains this bound in a special case. Importantly, the liquid welfare benchmark also overcomes impossibilities for some settings. While it is impossible to design Pareto-efficient auctions for multi-unit auctions where players have decreasing marginal values, we give a deterministic $O(\log n)$-approximation for the liquid welfare in this setting.

On the Efficiency of the Walrasian Mechanism

2013-11-04
Moshe Babaioff , Brendan Lucier , Noam Nisan +1 more
Central results in economics guarantee the existence of efficient equilibria for various classes of markets. An underlying assumption in early work is that agents are price-takers, i.e., agents honestly report … Central results in economics guarantee the existence of efficient equilibria for various classes of markets. An underlying assumption in early work is that agents are price-takers, i.e., agents honestly report their true demand in response to prices. A line of research in economics, initiated by Hurwicz (1972), is devoted to understanding how such markets perform when agents are strategic about their demands. This is captured by the \emph{Walrasian Mechanism} that proceeds by collecting reported demands, finding clearing prices in the \emph{reported} market via an ascending price t\^{a}tonnement procedure, and returns the resulting allocation. Similar mechanisms are used, for example, in the daily opening of the New York Stock Exchange and the call market for copper and gold in London. In practice, it is commonly observed that agents in such markets reduce their demand leading to behaviors resembling bargaining and to inefficient outcomes. We ask how inefficient the equilibria can be. Our main result is that the welfare of every pure Nash equilibrium of the Walrasian mechanism is at least one quarter of the optimal welfare, when players have gross substitute valuations and do not overbid. Previous analysis of the Walrasian mechanism have resorted to large market assumptions to show convergence to efficiency in the limit. Our result shows that approximate efficiency is guaranteed regardless of the size of the market.

Full Swap Regret and Discretized Calibration

2025-02-13
Maxwell Fishelson , Robert Kleinberg , Princewill Okoroafor +3 more
We study the problem of minimizing swap regret in structured normal-form games. Players have a very large (potentially infinite) number of pure actions, but each action has an embedding into … We study the problem of minimizing swap regret in structured normal-form games. Players have a very large (potentially infinite) number of pure actions, but each action has an embedding into $d$-dimensional space and payoffs are given by bilinear functions of these embeddings. We provide an efficient learning algorithm for this setting that incurs at most $\tilde{O}(T^{(d+1)/(d+3)})$ swap regret after $T$ rounds. To achieve this, we introduce a new online learning problem we call \emph{full swap regret minimization}. In this problem, a learner repeatedly takes a (randomized) action in a bounded convex $d$-dimensional action set $\mathcal{K}$ and then receives a loss from the adversary, with the goal of minimizing their regret with respect to the \emph{worst-case} swap function mapping $\mathcal{K}$ to $\mathcal{K}$. For varied assumptions about the convexity and smoothness of the loss functions, we design algorithms with full swap regret bounds ranging from $O(T^{d/(d+2)})$ to $O(T^{(d+1)/(d+2)})$. Finally, we apply these tools to the problem of online forecasting to minimize calibration error, showing that several notions of calibration can be viewed as specific instances of full swap regret. In particular, we design efficient algorithms for online forecasting that guarantee at most $O(T^{1/3})$ $\ell_2$-calibration error and $O(\max(\sqrt{\epsilon T}, T^{1/3}))$ \emph{discretized-calibration} error (when the forecaster is restricted to predicting multiples of $\epsilon$).
View PDF Chat

Data-Driven Mechanism Design: Jointly Eliciting Preferences and Information

2024-12-20
Dirk Bergemann , Marek Bojko , Paul Dütting +3 more
We study mechanism design when agents hold private information about both their preferences and a common payoff-relevant state. We show that standard message-driven mechanisms cannot implement socially efficient allocations when … We study mechanism design when agents hold private information about both their preferences and a common payoff-relevant state. We show that standard message-driven mechanisms cannot implement socially efficient allocations when agents have multidimensional types, even under favorable conditions. To overcome this limitation, we propose data-driven mechanisms that leverage additional post-allocation information, modeled as an estimator of the payoff-relevant state. Our data-driven mechanisms extend the classic Vickrey-Clarke-Groves class. We show that they achieve exact implementation in posterior equilibrium when the state is either fully revealed or the utility is linear in an unbiased estimator. We also show that they achieve approximate implementation with a consistent estimator, converging to exact implementation as the estimator converges, and present bounds on the convergence rate. We demonstrate applications to digital advertising auctions and large language model (LLM)-based mechanisms, where user engagement naturally reveals relevant information.
View PDF Chat

Charting the Shapes of Stories with Game Theory

2024-12-07
Constantinos Daskalakis , Ian Gemp , Yanchen Jiang +3 more
Stories are records of our experiences and their analysis reveals insights into the nature of being human. Successful analyses are often interdisciplinary, leveraging mathematical tools to extract structure from stories … Stories are records of our experiences and their analysis reveals insights into the nature of being human. Successful analyses are often interdisciplinary, leveraging mathematical tools to extract structure from stories and insights from structure. Historically, these tools have been restricted to one dimensional charts and dynamic social networks; however, modern AI offers the possibility of identifying more fully the plot structure, character incentives, and, importantly, counterfactual plot lines that the story could have taken but did not take. In this work, we use AI to model the structure of stories as game-theoretic objects, amenable to quantitative analysis. This allows us to not only interrogate each character's decision making, but also possibly peer into the original author's conception of the characters' world. We demonstrate our proposed technique on Shakespeare's famous Romeo and Juliet. We conclude with a discussion of how our analysis could be replicated in broader contexts, including real-life scenarios.
View PDF Chat

Procurement Auctions via Approximately Optimal Submodular Optimization

2024-11-20
Yuan Deng , Amin Karbasi , Vahab Mirrokni +3 more
We study procurement auctions, where an auctioneer seeks to acquire services from strategic sellers with private costs. The quality of services is measured by a submodular function known to the … We study procurement auctions, where an auctioneer seeks to acquire services from strategic sellers with private costs. The quality of services is measured by a submodular function known to the auctioneer. Our goal is to design computationally efficient procurement auctions that (approximately) maximize the difference between the quality of the acquired services and the total cost of the sellers, while ensuring incentive compatibility (IC), individual rationality (IR) for sellers, and non-negative surplus (NAS) for the auctioneer. Our contributions are twofold: (i) we provide an improved analysis of existing algorithms for non-positive submodular function maximization, and (ii) we design efficient frameworks that transform submodular optimization algorithms into mechanisms that are IC, IR, NAS, and approximation-preserving. These frameworks apply to both the offline setting, where all sellers' bids and services are available simultaneously, and the online setting, where sellers arrive in an adversarial order, requiring the auctioneer to make irrevocable decisions. We also explore whether state-of-the-art submodular optimization algorithms can be converted into descending auctions in adversarial settings, where the schedule of descending prices is determined by an adversary. We show that a submodular optimization algorithm satisfying bi-criteria $(1/2, 1)$-approximation in welfare can be effectively adapted to a descending auction. Additionally, we establish a connection between descending auctions and online submodular optimization. Finally, we demonstrate the practical applications of our frameworks by instantiating them with state-of-the-art submodular optimization algorithms and empirically comparing their welfare performance on publicly available datasets with thousands of sellers.
View PDF Chat

Online Matroid Embeddings

2024-07-14
Andrés Cristi , Paul Dütting , Robert Kleinberg +1 more
We introduce the notion of an online matroid embedding, which is an algorithm for mapping an unknown matroid that is revealed in an online fashion to a larger-but-known matroid. The … We introduce the notion of an online matroid embedding, which is an algorithm for mapping an unknown matroid that is revealed in an online fashion to a larger-but-known matroid. The existence of such embedding enables a reduction from the version of the matroid secretary problem where the matroid is unknown to the version where the matroid is known in advance. We show that online matroid embeddings exist for binary (and hence graphic) and laminar matroids. We also show a negative result showing that no online matroid embedding exists for the class of all matroids. Finally, we define the notion of an approximate matroid embedding, generalizing the notion of {\alpha}-partition property, and provide an upper bound on the approximability of binary matroids by a partition matroid, matching the lower bound of Dughmi et al.
View PDF Chat

Dynamical Analysis of Autobidding Systems

2024-06-27
Renato Paes Leme , Georgios Piliouras , Jon Schneider +2 more
It has become the default in markets such as ad auctions for participants to bid in an auction through automated bidding agents (autobidders) which adjust bids over time to satisfy … It has become the default in markets such as ad auctions for participants to bid in an auction through automated bidding agents (autobidders) which adjust bids over time to satisfy return-over-spend constraints. Despite the prominence of such systems for the internet economy, their resulting dynamical behavior is still not well understood. Although one might hope that such relatively simple systems would typically converge to the equilibria of their underlying auctions, we provide a plethora of results that show the emergence of complex behavior, such as bi-stability, periodic orbits and quasi periodicity. We empirically observe how the market structure (expressed as motifs) qualitatively affects the behavior of the dynamics. We complement it with theoretical results showing that autobidding systems can simulate both linear dynamical systems as well logical boolean gates.
View PDF Chat

Mechanism Design for Large Language Models

2024-05-08
Paul Dütting , Vahab Mirrokni , Renato Paes Leme +2 more
View PDF Chat

Winner-Pays-Bid Auctions Minimize Variance

2024-03-07
Preston McAfee , Renato Paes Leme , Balasubramanian Sivan +1 more
Any social choice function (e.g the efficient allocation) can be implemented using different payment rules: first price, second price, all-pay, etc. All of these payment rules are guaranteed to have … Any social choice function (e.g the efficient allocation) can be implemented using different payment rules: first price, second price, all-pay, etc. All of these payment rules are guaranteed to have the same expected revenue by the revenue equivalence theorem, but have different distributions of revenue, leading to a question of which one is best. We prove that among all possible payment rules, winner-pays-bid minimizes the variance in revenue and, in fact, minimizes any convex risk measure.
View PDF Chat

Bernoulli Factories for Flow-Based Polytopes

2024-02-06
Rad Niazadeh , Renato Paes Leme , Jon Schneider
.We construct explicit combinatorial Bernoulli factories for the following class of flow-based polytopes: integral 0/1-polytopes defined by a set of network flow constraints. This generalizes the results of Niazadeh et … .We construct explicit combinatorial Bernoulli factories for the following class of flow-based polytopes: integral 0/1-polytopes defined by a set of network flow constraints. This generalizes the results of Niazadeh et al. (who constructed an explicit factory for the specific case of bipartite perfect matchings) and provides novel exact sampling procedures for sampling paths, circulations, and \(k\)-flows. In the process, we uncover new connections to algebraic combinatorics.Keywordsexact samplingBernoulli factoriesrandom flowscirculationsMSC codes60-0868W0105E99
View PDF Chat

Multiparameter Bernoulli factories

2023-10-01
Renato Paes Leme , Jon Schneider
We consider the problem of computing with many coins of unknown bias. We are given access to samples of n coins with unknown biases p1,…,pn and are asked to sample … We consider the problem of computing with many coins of unknown bias. We are given access to samples of n coins with unknown biases p1,…,pn and are asked to sample from a coin with bias f(p1,…,pn) for a given function f:[0,1]n→[0,1]. We give a complete characterization of the functions f for which this is possible. As a consequence, we show how to extend various combinatorial sampling procedures (most notably, the classic Sampford sampling for k-subsets) to the boundary of the hypercube.
View PDF Chat

Combinatorial Bernoulli factories

2023-02-20
Rad Niazadeh , Renato Paes Leme , Jon Schneider
A Bernoulli factory is an algorithmic procedure for exact sampling of certain random variables having only Bernoulli access to their parameters. Bernoulli access to a parameter p∈[0,1] means the algorithm … A Bernoulli factory is an algorithmic procedure for exact sampling of certain random variables having only Bernoulli access to their parameters. Bernoulli access to a parameter p∈[0,1] means the algorithm does not know p, but has sample access to independent draws of a Bernoulli random variable with mean equal to p. In this paper, we study the problem of Bernoulli factories for polytopes: given Bernoulli access to a vector x∈P for a given polytope P⊂[0,1]n, output a randomized vertex such that the expected value of the i-th coordinate is exactly equal to xi. For example, for the special case of the perfect matching polytope, one is given Bernoulli access to the entries of a doubly stochastic matrix [xij] and asked to sample a matching such that the probability of each edge (i,j) be present in the matching is exactly equal to xij. We show that a polytope P admits a Bernoulli factory if and and only if P is the intersection of [0,1]n with an affine subspace. Our construction is based on an algebraic formulation of the problem, involving identifying a family of Bernstein polynomials (one per vertex) that satisfy a certain algebraic identity on P. The main technical tool behind our construction is a connection between these polynomials and the geometry of zonotope tilings. We apply these results to construct an explicit factory for the perfect matching polytope. The resulting factory is deeply connected to the combinatorial enumeration of arborescences and may be of independent interest. For the k-uniform matroid polytope, we recover a sampling procedure known in statistics as Sampford sampling.1 1 A preliminary conference version of this work has appeared in the proceeding of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC'21) [24]. The current version presents all the missing proofs and technical details, as well as new results, alternative proofs, and more explanations.
View PDF Chat

Pricing Query Complexity of Revenue Maximization

2023-01-01
Renato Paes Leme , Balasubramanian Sivan , Yifeng Teng +1 more
The common way to optimize auction and pricing systems is to set aside a small fraction of the traffic to run experiments. This leads to the question: how can we … The common way to optimize auction and pricing systems is to set aside a small fraction of the traffic to run experiments. This leads to the question: how can we learn the most with the smallest amount of data? For truthful auctions, this is the sample complexity problem. For posted price auctions, we no longer have access to samples. Instead, the algorithm is allowed to choose a price pt; then for a fresh sample vt ~ D we learn the sign st = sign(pt — vt) ∈ {-1, +1}. How many pricing queries are needed to estimate a given parameter of the underlying distribution?We give tight upper and lower bounds on the number of pricing queries required to find an approximately optimal reserve price for general, regular and MHR distributions. Interestingly, for regular distributions, the pricing query and sample complexities match. But for general and MHR distributions, we show a strict separation between them.All known results on sample complexity for revenue optimization follow from a variant of using the optimal reserve price of the empirical distribution. In the pricing query complexity setting, we show that learning the entire distribution within an error of ε in Levy distance requires strictly more pricing queries than to estimate the reserve. Instead, our algorithm uses a new property we identify called relative flatness to quickly zoom into the right region of the distribution to get the optimal pricing query complexity.* The full version of the paper can be accessed at https://arxiv.org/abs/2111.03158
View PDF Chat

Description Complexity of Regular Distributions

2023-01-01
Renato Paes Leme , Balasubramanian Sivan , Yifeng Teng +1 more
Myerson's regularity condition of a distribution is a standard assumption in economics. In this paper, we study the complexity of describing a regular distribution within a small statistical distance. Our … Myerson's regularity condition of a distribution is a standard assumption in economics. In this paper, we study the complexity of describing a regular distribution within a small statistical distance. Our main result is that $\tilde{\Theta}{(\epsilon^{-0.5})}$ bits are necessary and sufficient to describe a regular distribution with support $[0,1]$ within $\epsilon$ Levy distance. We prove this by showing that we can learn the regular distribution approximately with $\tilde{O}(\epsilon^{-0.5})$ queries to the cumulative density function. As a corollary, we show that the pricing query complexity to learn the class of regular distribution with support $[0,1]$ within $\epsilon$ Levy distance is $\tilde{\Theta}{(\epsilon^{-2.5})}$. To learn the mixture of two regular distributions, $\tilde{\Theta}(\epsilon^{-3})$ pricing queries are required.
View PDF Chat

U-Calibration: Forecasting for an Unknown Agent

2023-01-01
Robert Kleinberg , Renato Paes Leme , Jon Schneider +1 more
We consider the problem of evaluating forecasts of binary events whose predictions are consumed by rational agents who take an action in response to a prediction, but whose utility is … We consider the problem of evaluating forecasts of binary events whose predictions are consumed by rational agents who take an action in response to a prediction, but whose utility is unknown to the forecaster. We show that optimizing forecasts for a single scoring rule (e.g., the Brier score) cannot guarantee low regret for all possible agents. In contrast, forecasts that are well-calibrated guarantee that all agents incur sublinear regret. However, calibration is not a necessary criterion here (it is possible for miscalibrated forecasts to provide good regret guarantees for all possible agents), and calibrated forecasting procedures have provably worse convergence rates than forecasting procedures targeting a single scoring rule. Motivated by this, we present a new metric for evaluating forecasts that we call U-calibration, equal to the maximal regret of the sequence of forecasts when evaluated under any bounded scoring rule. We show that sublinear U-calibration error is a necessary and sufficient condition for all agents to achieve sublinear regret guarantees. We additionally demonstrate how to compute the U-calibration error efficiently and provide an online algorithm that achieves $O(\sqrt{T})$ U-calibration error (on par with optimal rates for optimizing for a single scoring rule, and bypassing lower bounds for the traditionally calibrated learning procedures). Finally, we discuss generalizations to the multiclass prediction setting.
View PDF Chat

Bayesian Conversations

2023-01-01
Renato Paes Leme , Jon Schneider , Shuran Zheng
We initiate the study of Bayesian conversations, which model interactive communication between two strategic agents without a mediator. We compare this to communication through a mediator and investigate the settings … We initiate the study of Bayesian conversations, which model interactive communication between two strategic agents without a mediator. We compare this to communication through a mediator and investigate the settings in which mediation can expand the range of implementable outcomes. In the first part of the paper, we ask whether the distributions of posterior beliefs that can be induced by a mediator protocol can also be induced by a (unmediated) Bayesian conversation. We show this is not possible -- mediator protocols can ``correlate'' the posteriors in a way that unmediated conversations cannot. Additionally, we provide characterizations of which distributions over posteriors are achievable via mediator protocols and Bayesian conversations. In the second part of the paper, we delve deeper into the eventual outcome of two-player games after interactive communication. We focus on games where only one agent has a non-trivial action and examine the performance of communication protocols that are individually rational (IR) for both parties. We consider different levels of IR including ex-ante, interim, and ex-post; and we impose different restrictions on how Alice and Bob can deviate from the protocol: the players are committed/non-committed. Our key findings reveal that, in the cases of ex-ante and interim IR, the expected utilities achievable through a mediator are equivalent to those achievable through unmediated Bayesian conversations. However, in the models of ex-post IR and non-committed interim IR, we observe a separation in the achievable outcomes.
View PDF Chat

Bandits with Deterministically Evolving States

2023-01-01
Khashayar Khosravi , Renato Paes Leme , Chara Podimata +1 more
We propose a model for learning with bandit feedback while accounting for deterministically evolving and unobservable states that we call Bandits with Deterministically Evolving States ($B$-$DES$). The workhorse applications of … We propose a model for learning with bandit feedback while accounting for deterministically evolving and unobservable states that we call Bandits with Deterministically Evolving States ($B$-$DES$). The workhorse applications of our model are learning for recommendation systems and learning for online ads. In both cases, the reward that the algorithm obtains at each round is a function of the short-term reward of the action chosen and how "healthy" the system is (i.e., as measured by its state). For example, in recommendation systems, the reward that the platform obtains from a user's engagement with a particular type of content depends not only on the inherent features of the specific content, but also on how the user's preferences have evolved as a result of interacting with other types of content on the platform. Our general model accounts for the different rate $\lambda \in [0,1]$ at which the state evolves (e.g., how fast a user's preferences shift as a result of previous content consumption) and encompasses standard multi-armed bandits as a special case. The goal of the algorithm is to minimize a notion of regret against the best-fixed sequence of arms pulled, which is significantly harder to attain compared to standard benchmark of the best-fixed action in hindsight. We present online learning algorithms for any possible value of the evolution rate $\lambda$ and we show the robustness of our results to various model misspecifications.
View PDF Chat

Nonbossy Mechanisms: Mechanism Design Robust to Secondary Goals

2023-01-01
Renato Paes Leme , Jon Schneider , Hanrui Zhang
We study mechanism design when agents may have hidden secondary goals which will manifest as non-trivial preferences among outcomes for which their primary utility is the same. We show that … We study mechanism design when agents may have hidden secondary goals which will manifest as non-trivial preferences among outcomes for which their primary utility is the same. We show that in such cases, a mechanism is robust against strategic manipulation if and only if it is not only incentive-compatible, but also nonbossy -- a well-studied property in the context of matching and allocation mechanisms. We give complete characterizations of incentive-compatible and nonbossy mechanisms in various settings, including auctions with single-parameter agents and public decision settings where all agents share a common outcome. In particular, we show that in the single-item setting, a mechanism is incentive-compatible, individually rational, and nonbossy if and only if it is a sequential posted-price mechanism. In contrast, we show that in more general single-parameter environments, there exist mechanisms satisfying our characterization that significantly outperform sequential posted-price mechanisms in terms of revenue or efficiency (sometimes by an exponential factor).
View PDF Chat

Mechanism Design for Large Language Models

2023-01-01
Paul Duetting , Vahab Mirrokni , Renato Paes Leme +2 more
We investigate auction mechanisms to support the emerging format of AI-generated content. We in particular study how to aggregate several LLMs in an incentive compatible manner. In this problem, the … We investigate auction mechanisms to support the emerging format of AI-generated content. We in particular study how to aggregate several LLMs in an incentive compatible manner. In this problem, the preferences of each agent over stochastically generated contents are described/encoded as an LLM. A key motivation is to design an auction format for AI-generated ad creatives to combine inputs from different advertisers. We argue that this problem, while generally falling under the umbrella of mechanism design, has several unique features. We propose a general formalism -- the token auction model -- for studying this problem. A key feature of this model is that it acts on a token-by-token basis and lets LLM agents influence generated contents through single dimensional bids. We first explore a robust auction design approach, in which all we assume is that agent preferences entail partial orders over outcome distributions. We formulate two natural incentive properties, and show that these are equivalent to a monotonicity condition on distribution aggregation. We also show that for such aggregation functions, it is possible to design a second-price auction, despite the absence of bidder valuation functions. We then move to designing concrete aggregation functions by focusing on specific valuation forms based on KL-divergence, a commonly used loss function in LLM. The welfare-maximizing aggregation rules turn out to be the weighted (log-space) convex combination of the target distributions from all participants. We conclude with experimental results in support of the token auction formulation.

Ex-post Individually Rational Bayesian Persuasion

2023-01-01
Jiahao Zhang , Shuran Zheng , Renato Paes Leme +1 more
The success of Bayesian persuasion relies on the key assumption that the sender will commit to a predetermined information disclosure policy (signaling scheme). However, in practice, it is usually difficult … The success of Bayesian persuasion relies on the key assumption that the sender will commit to a predetermined information disclosure policy (signaling scheme). However, in practice, it is usually difficult for the receiver to monitor whether the sender sticks to the disclosure policy, which makes the credibility of the sender's disclosure policy questionable. The sender's credibility is particularly tenuous when there are obvious deviations that benefit the sender. In this work, we identify such a deviation: the sender may be unwilling to send a signal that will lead to a less desirable outcome compared to no information disclosure. We thus propose the notion of ex-post individually rational (ex-post IR) Bayesian persuasion: after observing the state, the sender is never required to send a signal that will make the outcome worse off (compared to no information disclosure). An ex-post IR Bayesian persuasion policy is more likely to be truthfully followed by the sender, and thus more credible for the receiver. Our contribution is threefold. Firstly, we demonstrate that the optimal ex-post IR Bayesian persuasion policy can be efficiently computed through a linear program, while also offering geometric characterizations of this optimal policy. Second, we show that surprisingly, for non-trivial classes of games, the imposition of ex-post IR constraints does not affect the sender's expected utility. Finally, we compare ex-post IR Bayesian persuasion to other information disclosure models that ensure different notions of credibility.
View PDF Chat

Contextual Search via Intrinsic Volumes

2022-07-18
Renato Paes Leme , Jon Schneider
We study the problem of contextual search, a multidimensional generalization of binary search that captures many problems in contextual decision-making. In contextual search, a learner is trying to learn the … We study the problem of contextual search, a multidimensional generalization of binary 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 \in [0,1]^d$. Every round the learner is provided an adversarially chosen context $u_t \in \R^d$, submits a guess $p_t$ for the value of $\langle u_t, v\rangle$, learns whether $p_t < \langle u_t, v\rangle$, and incurs loss $\ell(\langle u_t, v\rangle, p_t)$ (for some loss function $\ell$). 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 $\ell(\theta, p) = |\theta - p|$ that achieves $O_{d}(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 $O_{d}(\log \log T)$ total loss, improving on the previous best known upper bounds of $O_{d}(\log T)$ 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 PDF Chat

Multiparameter Bernoulli Factories

2022-01-01
Renato Paes Leme , Jon Schneider
We consider the problem of computing with many coins of unknown bias. We are given samples access to $n$ coins with \emph{unknown} biases $p_1,\dots, p_n$ and are asked to sample … We consider the problem of computing with many coins of unknown bias. We are given samples access to $n$ coins with \emph{unknown} biases $p_1,\dots, p_n$ and are asked to sample from a coin with bias $f(p_1, \dots, p_n)$ for a given function $f:[0,1]^n \rightarrow [0,1]$. We give a complete characterization of the functions $f$ for which this is possible. As a consequence, we show how to extend various combinatorial sampling procedures (most notably, the classic Sampford Sampling for $k$-subsets) to the boundary of the hypercube.
View PDF Chat

Corruption-Robust Contextual Search through Density Updates

2022-01-01
Renato Paes Leme , Chara Podimata , Jon Schneider
We study the problem of contextual search in the adversarial noise model. Let $d$ be the dimension of the problem, $T$ be the time horizon and $C$ be the total … We study the problem of contextual search in the adversarial noise model. Let $d$ be the dimension of the problem, $T$ be the time horizon and $C$ be the total amount of noise in the system. For the $\eps$-ball loss, we give a tight regret bound of $O(C + d \log(1/\eps))$ improving over the $O(d^3 \log(1/\eps)) \log^2(T) + C \log(T) \log(1/\eps))$ bound of Krishnamurthy et al (STOC21). For the symmetric loss, we give an efficient algorithm with regret $O(C+d \log T)$. Our techniques are a significant departure from prior approaches. Specifically, we keep track of density functions over the candidate vectors instead of a knowledge set consisting of the candidate vectors consistent with the feedback obtained.
View PDF Chat

Bernoulli Factories for Flow-Based Polytopes

2022-01-01
Rad Niazadeh , Renato Paes Leme , Jon Schneider
We construct explicit combinatorial Bernoulli factories for the class of \emph{flow-based polytopes}; integral 0/1-polytopes defined by a set of network flow constraints. This generalizes the results of Niazadeh et al. … We construct explicit combinatorial Bernoulli factories for the class of \emph{flow-based polytopes}; integral 0/1-polytopes defined by a set of network flow constraints. This generalizes the results of Niazadeh et al. (who constructed an explicit factory for the specific case of bipartite perfect matchings) and provides novel exact sampling procedures for sampling paths, circulations, and $k$-flows. In the process, we uncover new connections to algebraic combinatorics.
View PDF Chat

Improved Revenue Bounds for Posted-Price and Second-Price Mechanisms

2021-10-19
Hedyeh Beyhaghi , Negin Golrezaei , Renato Paes Leme +2 more
How to optimize posted price mechanisms? The sequential posted-price (SPP) mechanism is one of the widely used selling mechanisms in practice. In this mechanism, the seller presents each buyer with … How to optimize posted price mechanisms? The sequential posted-price (SPP) mechanism is one of the widely used selling mechanisms in practice. In this mechanism, the seller presents each buyer with a price sequentially and the buyer can either accept or reject the mechanism's offer. Despite the widespread use of the SPP mechanism, the problem of optimizing prices in this mechanism has not been fully addressed. In a paper entitled, “Improved Revenue Bounds for Posted-Price and Second-Price Mechanisms,” H. Beyhaghi, N. Golrezaei, R. Paes Leme, M. Pal, and B. Sivan construct SPP mechanisms by considering the best of two simple pricing rules: one that imitates the optimal mechanism and the other that posts a uniform price (same price for every buyer). Their simple pricing rules can be easily generalized to the setting with multiple units and yield the first improvement over long-established approximation factors.
View PDF Chat

Variable Decomposition for Prophet Inequalities and Optimal Ordering

2021-07-18
Allen Liu , Renato Paes Leme , Martin Pál +2 more
We introduce a new decomposition technique for random variables that maps a generic instance of the prophet inequalities problem to a new instance where all but a constant number of … We introduce a new decomposition technique for random variables that maps a generic instance of the prophet inequalities problem to a new instance where all but a constant number of variables have a tractable structure that we refer to as (ε, δ)-smallness. Using this technique, we make progress on several outstanding problems in the area: We show that, even in the case of non-identical distributions, it is possible to achieve (arbitrarily close to) the optimal approximation ratio of β ~0.745 when the items arrive in a random order (this version is commonly known as prophet secretary) as long as we are allowed to remove a small constant number of distributions. We show that forfrequent instances (where each distribution reoccurs some number of times) and random arrival order, it is possible to achieve the optimal approximation ratio of β (improving over the previous best-known bound of 0.738). We give a new, simpler proof of Kertz's optimal approximation guarantee of β ~0.745 for prophet inequalities with i.i.d. distributions. The proof is primal-dual and simultaneously produces upper and lower bounds. Using this decomposition in combination with a novel convex programming formulation, we construct the first (in parallel work with[1]) an Efficient PTAS (EPTAS) for the Optimal Ordering problem.
View PDF Chat

Combinatorial Bernoulli factories: matchings, flows, and other polytopes

2021-06-15
Rad Niazadeh , Renato Paes Leme , Jon Schneider
A Bernoulli factory is an algorithmic procedure for exact sampling of certain random variables having only Bernoulli access to their parameters. Bernoulli access to a parameter p ∈ [0,1] means … A Bernoulli factory is an algorithmic procedure for exact sampling of certain random variables having only Bernoulli access to their parameters. Bernoulli access to a parameter p ∈ [0,1] means the algorithm does not know p, but has sample access to independent draws of a Bernoulli random variable with mean equal to p. In this paper, we study the problem of Bernoulli factories for polytopes: given Bernoulli access to a vector x∈ P for a given polytope P⊂ [0,1]n, output a randomized vertex such that the expected value of the i-th coordinate is exactly equal to xi. For example, for the special case of the perfect matching polytope, one is given Bernoulli access to the entries of a doubly stochastic matrix [xij] and asked to sample a matching such that the probability of each edge (i,j) be present in the matching is exactly equal to xij.
View PDF Chat

Contextual Recommendations and Low-Regret Cutting-Plane Algorithms

2021-06-09
Sreenivas Gollapudi , Guru Guruganesh , Kostas Kollias +3 more
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 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 \mathcal{X}_t} \langle x, w^* \rangle$. We design algorithms for this problem which achieve $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)$ and list size $\mathrm{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.

Interactive Communication in Bilateral Trade

2021-06-03
Jieming Mao , Renato Paes Leme , Kangning Wang
We define a model of interactive communication where two agents with private types can exchange information before a game is played. The model contains Bayesian persuasion as a special case … We define a model of interactive communication where two agents with private types can exchange information before a game is played. The model contains Bayesian persuasion as a special case of a one-round communication protocol. We define message complexity corresponding to the minimum number of interactive rounds necessary to achieve the best possible outcome. Our main result is that for bilateral trade, agents don't stop talking until they reach an efficient outcome: Either agents achieve an efficient allocation in finitely many rounds of communication; or the optimal communication protocol has infinite number of rounds. We show an important class of bilateral trade settings where efficient allocation is achievable with a small number of rounds of communication.
View PDF Chat

Calibrated Click-Through Auctions: An Information Design Approach

2021-05-19
Dirk Bergemann , Paul Duetting , Renato Paes Leme +1 more
We analyze the optimal information design in a click-through auction with fixed valuations per click, but stochastic click-through rates. While the auctioneer takes as given the auction rule of the … We analyze the optimal information design in a click-through auction with fixed valuations per click, but stochastic click-through rates. While the auctioneer takes as given the auction rule of the click-through auction, namely the generalized second-price auction, the auctioneer can design the information flow regarding the click-through rates among the bidders. A natural requirement in this context is to ask for 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 bid and an unbiased estimator of the click-through rates, and the task of designing an optimal information structure is thus reduced to the task of designing an optimal unbiased estimator. 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.

Optimal Contextual Pricing and Extensions

2021-01-01
Allen Liu , Renato Paes Leme , Jon Schneider
In the contextual pricing problem a seller repeatedly obtains products described by an adversarially chosen feature vector in ℝd and only observes the purchasing decisions of a buyer with a … In the contextual pricing problem a seller repeatedly obtains products described by an adversarially chosen feature vector in ℝ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 Ω(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 Ω(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 : → in a certain hypothesis class ℋ. We provide a generic algorithm with O(d2) regret where d is the covering dimension of this class. This leads in particular to a Õ(s2) 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 PDF Chat

Combinatorial Bernoulli Factories: Matchings, Flows and Other Polytopes

2021-01-01
Rad Niazadeh , Renato Paes Leme , Jon Schneider
A Bernoulli factory is an algorithmic procedure for exact sampling of certain random variables having only Bernoulli access to their parameters. Bernoulli access to a parameter p ∈ [0, 1] … A Bernoulli factory is an algorithmic procedure for exact sampling of certain random variables having only Bernoulli access to their parameters. Bernoulli access to a parameter p ∈ [0, 1] means the algorithm does not know p, but has sample access to independent draws of a Bernoulli random variable with mean equal to p. In this paper, we study the problem of Bernoulli factories for polytopes: given Bernoulli access to a vector x ∈ P for a given polytope P ⊂ [0, 1]^n, output a randomized vertex such that the expected value of the i-th coordinate is exactly equal to xi. For example, for the special case of the perfect matching polytope, one is given Bernoulli access to the entries of a doubly stochastic matrix [x_ij] and asked to sample a matching such that the probability of each edge (i,j) be present in the matching is exactly equal to x_ij.We show that a polytope P admits a Bernoulli factory if and and only if P is the intersection of [0, 1]^n with an affine subspace. Our construction is based on an algebraic formulation of the problem, involving identifying a family of Bernstein polynomials (one per vertex) that satisfy a certain algebraic identity on P. The main technical tool behind our construction is a connection between these polynomials and the geometry of zonotope tilings. We apply these results to construct an explicit factory for the perfect matching polytope. The resulting factory is deeply connected to the combinatorial enumeration of arborescences and may be of independent interest. For the k-uniform matroid polytope, we recover a sampling procedure known in statistics as Sampford sampling.
View PDF Chat

Learning to Price Against a Moving Target

2021-01-01
Renato Paes Leme , Balasubramanian Sivan , Yifeng Teng +1 more
In the Learning to Price setting, a seller posts prices over time with the goal of maximizing revenue while learning the buyer's valuation. This problem is very well understood when … In the Learning to Price setting, a seller posts prices over time with the goal of maximizing revenue while learning the buyer's valuation. This problem is very well understood when values are stationary (fixed or iid). Here we study the problem where the buyer's value is a moving target, i.e., they change over time either by a stochastic process or adversarially with bounded variation. In either case, we provide matching upper and lower bounds on the optimal revenue loss. Since the target is moving, any information learned soon becomes out-dated, which forces the algorithms to keep switching between exploring and exploiting phases.

Calibrated Click-Through Auctions: An Information Design Approach

2021-01-01
Dirk Bergemann , Paul Duetting , Renato Paes Leme +1 more
We analyze the optimal information design in a click-through auction with fixed valuations per click, but stochastic click-through rates. While the auctioneer takes as given the auction rule of the … We analyze the optimal information design in a click-through auction with fixed valuations per click, but stochastic click-through rates. While the auctioneer takes as given the auction rule of the click-through auction, namely the generalized second-price auction, the auctioneer can design the information flow regarding the click-through rates among the bidders. A natural requirement in this context is to ask for 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 bid and an unbiased estimator of the click-through rates, and the task of designing an optimal information structure is thus reduced to the task of designing an optimal unbiased estimator. 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.

Interactive Communication in Bilateral Trade

2021-01-01
Jieming Mao , Renato Paes Leme , Kangning Wang
We define a model of interactive communication where two agents with private types can exchange information before a game is played. The model contains Bayesian persuasion as a special case … We define a model of interactive communication where two agents with private types can exchange information before a game is played. The model contains Bayesian persuasion as a special case of a one-round communication protocol. We define message complexity corresponding to the minimum number of interactive rounds necessary to achieve the best possible outcome. Our main result is that for bilateral trade, agents don't stop talking until they reach an efficient outcome: Either agents achieve an efficient allocation in finitely many rounds of communication; or the optimal communication protocol has infinite number of rounds. We show an important class of bilateral trade settings where efficient allocation is achievable with a small number of rounds of communication.
View PDF Chat

Pricing Query Complexity of Revenue Maximization

2021-01-01
Renato Paes Leme , Balasubramanian Sivan , Yifeng Teng +1 more
The common way to optimize auction and pricing systems is to set aside a small fraction of the traffic to run experiments. This leads to the question: how can we … The common way to optimize auction and pricing systems is to set aside a small fraction of the traffic to run experiments. This leads to the question: how can we learn the most with the smallest amount of data? For truthful auctions, this is the \emph{sample complexity} problem. For posted price auctions, we no longer have access to samples. Instead, the algorithm is allowed to choose a price $p_t$; then for a fresh sample $v_t \sim \mathcal{D}$ we learn the sign $s_t = sign(p_t - v_t) \in \{-1,+1\}$. How many pricing queries are needed to estimate a given parameter of the underlying distribution? We give tight upper and lower bounds on the number of pricing queries required to find an approximately optimal reserve price for general, regular and MHR distributions. Interestingly, for regular distributions, the pricing query and sample complexities match. But for general and MHR distributions, we show a strict separation between them. All known results on sample complexity for revenue optimization follow from a variant of using the optimal reserve price of the empirical distribution. In the pricing query complexity setting, we show that learning the entire distribution within an error of $\epsilon$ in Levy distance requires strictly more pricing queries than to estimate the reserve. Instead, our algorithm uses a new property we identify called \emph{relative flatness} to quickly zoom into the right region of the distribution to get the optimal pricing query complexity.
View PDF Chat

Contextual Recommendations and Low-Regret Cutting-Plane Algorithms

2021-01-01
Sreenivas Gollapudi , Guru Guruganesh , Kostas Kollias +3 more
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 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 \mathcal{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 $\mathrm{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.

Are Gross Substitutes a Substitute for Submodular Valuations?

2021-01-01
Shahar Dobzinski , Uriel Feige , Michal Feldman +1 more
The class of gross substitutes (GS) set functions plays a central role in Economics and Computer Science. GS belongs to the hierarchy of {\em complement free} valuations introduced by Lehmann, … The class of gross substitutes (GS) set functions plays a central role in Economics and Computer Science. GS belongs to the hierarchy of {\em complement free} valuations introduced by Lehmann, Lehmann and Nisan, along with other prominent classes: $GS \subsetneq Submodular \subsetneq XOS \subsetneq Subadditive$. The GS class has always been more enigmatic than its counterpart classes, both in its definition and in its relation to the other classes. For example, while it is well understood how closely the Submodular, XOS and Subadditive classes (point-wise) approximate one another, approximability of these classes by GS remained wide open. Our main result is the existence of a submodular valuation (one that is also budget additive) that cannot be approximated by GS within a ratio better than $\Omega(\frac{\log m}{\log\log m})$, where $m$ is the number of items. En route, we uncover a new symmetrization operation that preserves GS, which may be of independent interest. We show that our main result is tight with respect to budget additive valuations. Additionally, for a class of submodular functions that we refer to as {\em concave of Rado} valuations (this class greatly extends budget additive valuations), we show approximability by GS within an $O(\log^2m)$ factor.

Secretaries with Advice

2020-11-13
Paul Dütting , Silvio Lattanzi , Renato Paes Leme +1 more
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? … 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 on arrival, to more modern versions of advice in the form of samples, to an ML-inspired model where a classifier gives us noisy signal 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. Using tools from linear programming, we present a tight analysis of optimal algorithms for secretaries with samples, optimal algorithms when secretaries' qualities are drawn from a known distribution, and a new noisy binary advice model.

Combinatorial Bernoulli Factories: Matchings, Flows and Other Polytopes

2020-11-07
Rad Niazadeh , Renato Paes Leme , Jon Schneider
A Bernoulli factory is an algorithmic procedure for exact sampling of certain random variables having only Bernoulli access to their parameters. Bernoulli access to a parameter $p \in [0,1]$ means … A Bernoulli factory is an algorithmic procedure for exact sampling of certain random variables having only Bernoulli access to their parameters. Bernoulli access to a parameter $p \in [0,1]$ means the algorithm does not know $p$, but has sample access to independent draws of a Bernoulli random variable with mean equal to $p$. In this paper, we study the problem of Bernoulli factories for polytopes: given Bernoulli access to a vector $x\in \mathcal{P}$ for a given polytope $\mathcal{P}\subset [0,1]^n$, output a randomized vertex such that the expected value of the $i$-th coordinate is \emph{exactly} equal to $x_i$. For example, for the special case of the perfect matching polytope, one is given Bernoulli access to the entries of a doubly stochastic matrix $[x_{ij}]$ and asked to sample a matching such that the probability of each edge $(i,j)$ be present in the matching is exactly equal to $x_{ij}$. We show that a polytope $\mathcal{P}$ admits a Bernoulli factory if and and only if $\mathcal{P}$ is the intersection of $[0,1]^n$ with an affine subspace. Our construction is based on an algebraic formulation of the problem, involving identifying a family of Bernstein polynomials (one per vertex) that satisfy a certain algebraic identity on $\mathcal{P}$. The main technical tool behind our construction is a connection between these polynomials and the geometry of zonotope tilings. We apply these results to construct an explicit factory for the perfect matching polytope. The resulting factory is deeply connected to the combinatorial enumeration of arborescences and may be of independent interest. For the $k$-uniform matroid polytope, we recover a sampling procedure known in statistics as Sampford sampling.

Competing Optimally Against An Imperfect Prophet

2020-04-21
Allen Liu , Renato Paes Leme , Martin Pál +2 more
Consider a gambler who observes the realizations of $n$ independent, non-negative, distribution-labeled random variables arriving in a uniform random order and can stop the sequence at any time to obtain … Consider a gambler who observes the realizations of $n$ independent, non-negative, distribution-labeled random variables arriving in a uniform random order and can stop the sequence at any time to obtain a reward of the most recent observation. In 2017, Correa et al. showed that when all distributions are identical, it is possible to design a stopping time that achieves a $\beta \approx 0.745$ fraction of the maximum value (the ``prophet'' benchmark), matching an upper bound of Hill and Kertz. In 2019, Correa et al. showed that when the distributions differ, it is no longer possible to achieve this bound: they prove an upper bound of $\sqrt{3} - 1 < 0.74$ on the best approximation ratio. We show that it is possible to asymptotically achieve the $\beta \approx 0.745$ bound even in the case of non-identical distributions, as long as we are allowed to remove a small constant number of distributions. Formally, we show that for any $\varepsilon$, there exists a constant $C_{\varepsilon} = \mathrm{poly}(1/\varepsilon)$ (independent of $n$) such that after removing $C_{\varepsilon}$ distributions of our choice, we can achieve a $(\beta - \varepsilon)$-approximation to the resulting maximum. We additionally show it is possible to asymptotically achieve an exact $\beta$ approximation ratio for several natural classes of problem instances, including small prophets (where each distribution is concentrated near zero) and frequent prophets (where each distribution occurs at least some number of times).

Why Do Competitive Markets Converge to First-Price Auctions?

2020-04-20
Renato Paes Leme , Balasubramanian Sivan , Yifeng Teng
We consider a setting in which bidders participate in multiple auctions run by different sellers, and optimize their bids for the aggregate auction. We analyze this setting by formulating a … We consider a setting in which bidders participate in multiple auctions run by different sellers, and optimize their bids for the 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 PDF Chat

Bandits with adversarial scaling

2020-03-04
Thodoris Lykouris , Vahab Mirrokni , Renato Paes Leme
We study scaling, a multi-armed bandit model where rewards have a stochastic and an adversarial component. Our model captures display advertising where the click-through-rate can be decomposed to a (fixed … We study scaling, a multi-armed bandit model where rewards have a stochastic and an adversarial component. Our model captures display advertising where the click-through-rate can be decomposed to a (fixed across time) arm-quality component and a non-stochastic user-relevance component (fixed across arms). Despite the relative stochasticity of our model, we demonstrate two settings where most bandit algorithms suffer. On the positive side, we show that two algorithms, one from the action elimination and one from the mirror descent family are adaptive enough to be robust to adversarial scaling. Our results shed light on the robustness of adaptive parameter selection in stochastic bandits, which may be of independent interest.

Contextual Search for General Hypothesis Classes.

2020-03-03
Allen Liu , Renato Paes Leme , Jon Schneider

Why Do Competitive Markets Converge to First-Price Auctions?

2020-01-01
Renato Paes Leme , Balasubramanian Sivan , Yifeng Teng
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 … 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 PDF Chat

Optimal Contextual Pricing and Extensions

2020-01-01
Allen Liu , Renato Paes Leme , Jon Schneider
In the contextual pricing problem a seller repeatedly obtains products described by an adversarially chosen feature vector in $\mathbb{R}^d$ and only observes the purchasing decisions of a buyer with a … In the contextual pricing problem a seller repeatedly obtains products described by an adversarially chosen feature vector in $\mathbb{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 : \mathcal{X} \rightarrow \mathcal{Y}$ in a certain hypothesis class $\mathcal{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$.

Variable Decomposition for Prophet Inequalities and Optimal Ordering

2020-01-01
Allen Liu , Renato Paes Leme , Martin Pál +2 more
We introduce a new decomposition technique for random variables that maps a generic instance of the prophet inequalities problem to a new instance where all but a constant number of … We introduce a new decomposition technique for random variables that maps a generic instance of the prophet inequalities problem to a new instance where all but a constant number of variables have a tractable structure that we refer to as $(\varepsilon, \delta)$-smallness. Using this technique, we make progress on several outstanding problems in the area: - We show that, even in the case of non-identical distributions, it is possible to achieve (arbitrarily close to) the optimal approximation ratio of $\beta \approx 0.745$ as long as we are allowed to remove a small constant number of distributions. - We show that for frequent instances of prophet inequalities (where each distribution reoccurs some number of times), it is possible to achieve the optimal approximation ratio of $\beta$ (improving over the previous best-known bound of $0.738$). - We give a new, simpler proof of Kertz's optimal approximation guarantee of $\beta \approx 0.745$ for prophet inequalities with i.i.d. distributions. The proof is primal-dual and simultaneously produces upper and lower bounds. - Using this decomposition in combination with a novel convex programming formulation, we construct the first Efficient PTAS for the Optimal Ordering problem.

Improved Revenue Bounds for Posted-Price and Second-Price Mechanisms

2020-01-01
Hedyeh Beyhaghi , Negin Golrezaei , Renato Paes Leme +2 more
We study revenue maximization through sequential posted-price (SPP) mechanisms in single-dimensional settings with n buyers and independent but not necessarily identical value distributions. We construct the SPP mechanisms by considering … We study revenue maximization through sequential posted-price (SPP) mechanisms in single-dimensional settings with n buyers and independent but not necessarily identical value distributions. We construct the SPP mechanisms by considering the best of two simple pricing rules: one that imitates the optimal/Myersonian mechanism via the taxation principle and the other that posts a uniform price. Our pricing rules are rather generalizable and yield the first improvement over long-established approximation factors in several settings. We design factor-revealing mathematical programs that crisply capture the approximation factor of our SPP mechanism. In the single-unit setting, our SPP mechanism yields a better approximation factor than the state of the art prior to our work (Azar et al. 2018). In the multi-unit setting, our SPP mechanism yields the first improved approximation factor over the state of the art after over nine years (Yan (2011) and Chakraborty et al. (2010)). Our results on SPP mechanisms immediately imply improved performance guarantees for the equivalent free-order prophet inequality problem. In the position auction setting, our SPP mechanism yields the first higher-than 1 − 1/e approximation factor. In eager second-price (ESP) auctions, our two simple pricing rules lead to the first improved approximation factor that is strictly greater than what is obtained by the SPP mechanism in the single-unit setting
View PDF Chat

Combinatorial Bernoulli Factories: Matchings, Flows and Other Polytopes

2020-01-01
Rad Niazadeh , Renato Paes Leme , Jon Schneider
A Bernoulli factory is an algorithmic procedure for exact sampling of certain random variables having only Bernoulli access to their parameters. Bernoulli access to a parameter $p \in [0,1]$ means … A Bernoulli factory is an algorithmic procedure for exact sampling of certain random variables having only Bernoulli access to their parameters. Bernoulli access to a parameter $p \in [0,1]$ means the algorithm does not know $p$, but has sample access to independent draws of a Bernoulli random variable with mean equal to $p$. In this paper, we study the problem of Bernoulli factories for polytopes: given Bernoulli access to a vector $x\in P$ for a given polytope $P\subset [0,1]^n$, output a randomized vertex such that the expected value of the $i$-th coordinate is \emph{exactly} equal to $x_i$. For example, for the special case of the perfect matching polytope, one is given Bernoulli access to the entries of a doubly stochastic matrix $[x_{ij}]$ and asked to sample a matching such that the probability of each edge $(i,j)$ be present in the matching is exactly equal to $x_{ij}$. We show that a polytope $P$ admits a Bernoulli factory if and and only if $P$ is the intersection of $[0,1]^n$ with an affine subspace. Our construction is based on an algebraic formulation of the problem, involving identifying a family of Bernstein polynomials (one per vertex) that satisfy a certain algebraic identity on $P$. The main technical tool behind our construction is a connection between these polynomials and the geometry of zonotope tilings. We apply these results to construct an explicit factory for the perfect matching polytope. The resulting factory is deeply connected to the combinatorial enumeration of arborescences and may be of independent interest. For the $k$-uniform matroid polytope, we recover a sampling procedure known in statistics as Sampford sampling.
View PDF Chat

Bandits with adversarial scaling

2020-01-01
Thodoris Lykouris , Vahab Mirrokni , Renato Paes Leme
We study "adversarial scaling", a multi-armed bandit model where rewards have a stochastic and an adversarial component. Our model captures display advertising where the "click-through-rate" can be decomposed to a … We study "adversarial scaling", a multi-armed bandit model where rewards have a stochastic and an adversarial component. Our model captures display advertising where the "click-through-rate" can be decomposed to a (fixed across time) arm-quality component and a non-stochastic user-relevance component (fixed across arms). Despite the relative stochasticity of our model, we demonstrate two settings where most bandit algorithms suffer. On the positive side, we show that two algorithms, one from the action elimination and one from the mirror descent family are adaptive enough to be robust to adversarial scaling. Our results shed light on the robustness of adaptive parameter selection in stochastic bandits, which may be of independent interest.
View PDF Chat

Secretaries with Advice

2020-01-01
Paul Dütting , Silvio Lattanzi , Renato Paes Leme +1 more
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? … 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 on arrival, to more modern versions of advice in the form of samples, to an ML-inspired model where a classifier gives us noisy signal 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. Using tools from linear programming, we present a tight analysis of optimal algorithms for secretaries with samples, optimal algorithms when secretaries' qualities are drawn from a known distribution, and a new noisy binary advice model.
Coauthor Papers Together
Jon Schneider 25
Vahab Mirrokni 23
Balasubramanian Sivan 18
Martin Pál 12
Gagan Goel 12
Brendan Lucier 12
Moshe Babaioff 11
Negin Golrezaei 10
Song Zuo 10
Yifeng Teng 8
Rad Niazadeh 7
Robert Kleinberg 6
Sergei Vassilvitskii 6
Michal Feldman 6
Allen Liu 6
Hedyeh Beyhaghi 6
Éva Tardos 6
Noam Nisan 6
Thodoris Lykouris 5
Adrian Vladu 5
Paul Dütting 5
Eric Balkanski 5
Pratik Worah 4
Ilan Lobel 4
Maria Kyropoulou 4
Shahar Dobzinski 4
Christos Kaklamanis 4
Mahsa Derakhshan 4
Ioannis Caragiannis 4
Sam Chiu-wai Wong 4
Pingzhong Tang 4
Paul Duetting 3
David Kempe 3
Dirk Bergemann 3
Haifeng Xu 3
Panagiotis Kanellopoulos 3
Vasilis Syrgkanis 2
Pasin Manurangsi 2
Moshe Tennenholtz 2
Kangning Wang 2
Yuval Emek 2
Iftah Gamzu 2
Sébastien Lahaie 2
Silvio Lattanzi 2
Chara Podimata 2
Kostas Kollias 2
Sreenivas Gollapudi 2
Weiran Shen 2
Guru Guruganesh 2
Shuran Zheng 2

Convexity and Steinitz's Exchange Property

1996-12-01
Kazuo Murota

Prior-free auctions for budgeted agents

2013-06-16
Nikhil R. Devanur , Bach Q. Ha , Jason D. Hartline
We consider prior-free auctions for revenue and welfare maximization when agents have a common budget. The abstract environments we consider are ones where there is a downward-closed and symmetric feasibility … We consider prior-free auctions for revenue and welfare maximization when agents have a common budget. The abstract environments we consider are ones where there is a downward-closed and symmetric feasibility constraint on the probabilities of service of the agents. These environments include position auctions where slots with decreasing click-through rates are auctioned to advertisers. We generalize and characterize the envy-free benchmark from Hartline and Yan [2011] to settings with budgets and characterize the optimal envy-free outcomes for both welfare and revenue. We give prior-free mechanisms that approximate these benchmarks. A building block in our mechanism is a clinching auction for position auction environments. This auction is a generalization of the multi-unit clinching auction of Dobzinski et al. [2008] and a special case of the polyhedral clinching auction of Goel et al. [2012]. For welfare maximization, we show that this clinching auction is a good approximation to the envy-free optimal welfare for position auction environments. For profit maximization, we generalize the random sampling profit extraction auction from Fiat et al. [2002] for digital goods to give a 10.0-approximation to the envy-free optimal revenue in symmetric, downward-closed environments. Even without budgets this revenue maximization question is of interest and we obtain an improved approximation bound of 7.5 (from 30.4 by Ha and Hartline [2012]).
View PDF Chat

On sampling without replacement with unequal probabilities of selection

1967-01-01
M. R. Sampford
A sample of n different units is to be drawn from a population or stratum in such a way that unit i has probability npi, assumed less than 1, of … A sample of n different units is to be drawn from a population or stratum in such a way that unit i has probability npi, assumed less than 1, of appearing in the sample. A mathematical solution of this problem is given by a formula from which the required probability of selection of any possible sample can be calculated: this formula is an extension of one, due to Durbin, for n = 2. The required npican be achieved in practice in three ways: (a) by evaluating the required probabilities for all possible samples, and selecting one; (b) selecting units without replacement, with probabilities of selection that must be recalculated after each drawing; and (c) by selecting up to n units with replacement, the first drawing being made with probabilities pi, and all subsequent ones with probabilities proportional to pi/(1−npi), and rejecting completely any sample that does not contain n different units. Method (c) seems likely to be the most convenient in practice. The probability of the simultaneous appearance in the sample of any pair of units is relatively easily calculated, so that unbiased variance estimates can be obtained without undue labour.

Stationarity detection in the initial transient problem

1992-04-01
Søren Asmussen , Peter W. Glynn , Hermann Þórisson
Let X = {X(t)} t ≥ 0 be a stochastic process with a stationary version X * . It is investigated when it is possible to generate by simulation a … Let X = {X(t)} t ≥ 0 be a stochastic process with a stationary version X * . It is investigated when it is possible to generate by simulation a version X˜ of X with lower initial bias than X itself, in the sense that either X˜ is strictly stationary (has the same distribution as X * ) or the distribution of X˜ is close to the distribution of X * . Particular attention is given to regenerative processes and Markov processes with a finite, countable, or general state space. The results are both positive and negative, and indicate that the tail of the distribution of the cycle length τ plays a critical role. The negative results essentially state that without some information on this tail, no a priori computable bias reduction is possible; in particular, this is the case for the class of all Markov processes with a countably infinite state space. On the contrary, the positive results give algorithms for simulating X˜ for various classes of processes with some special structure on τ . In particular, one can generate X˜ as strictly stationary for finite state Markov chains, Markov chains satisfying a Doeblin-type minorization, and regenerative processes with the cycle length τ bounded or having a stationary age distribution that can be generated by simulation.
View PDF Chat

Estimating Ocean Circulation: An MCMC Approach With Approximated Likelihoods via the Bernoulli Factory

2014-04-24
Radu Herbei , L. Mark Berliner
We provide a Bayesian analysis of ocean circulation based on data collected in the South Atlantic Ocean. The analysis incorporates a reaction-diffusion partial differential equation that is not solvable in … We provide a Bayesian analysis of ocean circulation based on data collected in the South Atlantic Ocean. The analysis incorporates a reaction-diffusion partial differential equation that is not solvable in closed form. This leads to an intractable likelihood function. We describe a novel Markov chain Monte Carlo approach that does not require a likelihood evaluation. Rather, we use unbiased estimates of the likelihood and a Bernoulli factory to decide whether or not proposed states are accepted. The variates required to estimate the likelihood function are obtained via a Feynman–Kac representation. This lifts the common restriction of selecting a regular grid for the physical model and eliminates the need for data preprocessing. We implement our approach using the parallel graphic processing unit (GPU) computing environment.

New Coins From Old: Computing With Unknown Bias

2005-12-01
Elchanan Mossel , Yuval Peres
View PDF Chat

Provable quantum advantage in randomness processing

2015-09-18
Howard Dale , David Jennings , Terry Rudolph
Quantum advantage is notoriously hard to find and even harder to prove. For example the class of functions computable with classical physics actually exactly coincides with the class computable quantum-mechanically. … Quantum advantage is notoriously hard to find and even harder to prove. For example the class of functions computable with classical physics actually exactly coincides with the class computable quantum-mechanically. It is strongly believed, but not proven, that quantum computing provides exponential speed-up for a range of problems, such as factoring. Here we address a computational scenario of "randomness processing" in which quantum theory provably yields, not only resource reduction over classical stochastic physics, but a strictly larger class of problems which can be solved. Beyond new foundational insights into the nature and malleability of randomness, and the distinction between quantum and classical information, these results also offer the potential of developing classically intractable simulations with currently accessible quantum technologies.
View PDF Chat

Polyhedral clinching auctions and the adwords polytope

2012-05-19
Gagan Goel , Vahab Mirrokni , Renato Paes Leme
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 … 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 the above 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.
View PDF Chat

Fast simulation of new coins from old

2005-02-01
Şerban Nacu , Yuval Peres
Let S⊂(0,1). Given a known function f:S→(0,1), we consider the problem of using independent tosses of a coin with probability of heads p (where p∈S is unknown) to simulate a … Let S⊂(0,1). Given a known function f:S→(0,1), we consider the problem of using independent tosses of a coin with probability of heads p (where p∈S is unknown) to simulate a coin with probability of heads f(p). We prove that if S is a closed interval and f is real analytic on S, then f has a fast simulation on S (the number of p-coin tosses needed has exponential tails). Conversely, if a function f has a fast simulation on an open set, then it is real analytic on that set.
View PDF Chat

Non-price equilibria in markets of discrete goods

2011-06-05
Avinatan Hassidim , Haim Kaplan , Yishay Mansour +1 more
No abstract available. No abstract available.
View PDF Chat

Bayesian mechanism design for budget-constrained agents

2011-06-05
Shuchi Chawla , David L. Malec , Azarakhsh Malekian
We study Bayesian mechanism design problems in settings where agents have budgets. Specifically, an agent's utility for an outcome is given by his value for the outcome minus any payment … We study Bayesian mechanism design problems in settings where agents have budgets. Specifically, an agent's utility for an outcome is given by his value for the outcome minus any payment he makes to the mechanism, as long as the payment is below his budget, and is negative infinity otherwise. This discontinuity in the utility function presents a significant challenge in the design of good mechanisms, and classical mechanisms fail to work in settings with budgets. The goal of this paper is to develop general reductions from budget-constrained Bayesian MD to unconstrained Bayesian MD with small loss in performance. We consider this question in the context of the two most well-studied objectives in mechanism design---social welfare and revenue---and present constant factor approximations in a number of settings. Some of our results extend to settings where budgets are private and agents need to be incentivized to reveal them truthfully.
View PDF Chat

Bernoulli factories and black-box reductions in mechanism design

2017-06-15
Shaddin Dughmi , Jason D. Hartline , Robert Kleinberg +1 more
We provide a polynomial-time reduction from Bayesian incentive-compatible mechanism design to Bayesian algorithm design for welfare maximization problems. Unlike prior results, our reduction achieves exact incentive compatibility for problems with … We provide a polynomial-time reduction from Bayesian incentive-compatible mechanism design to Bayesian algorithm design for welfare maximization problems. Unlike prior results, our reduction achieves exact incentive compatibility for problems with multi-dimensional and continuous type spaces.
View PDF Chat

Barker’s algorithm for Bayesian inference with intractable likelihoods

2017-11-01
Flávio B. Gonçalves , Krzysztof Łatuszyński , Gareth O. Roberts
In this expository paper, we abstract and describe a simple MCMC scheme for sampling from intractable target densities. The approach has been introduced in Gonçalves, Łatuszyński and Roberts (2017a) in … In this expository paper, we abstract and describe a simple MCMC scheme for sampling from intractable target densities. The approach has been introduced in Gonçalves, Łatuszyński and Roberts (2017a) in the specific context of jump-diffusions, and is based on the Barker's algorithm paired with a simple Bernoulli factory type scheme, the so called 2-coin algorithm. In many settings, it is an alternative to standard Metropolis–Hastings pseudo-marginal method for simulating from intractable target densities. Although Barker's is well known to be slightly less efficient than Metropolis–Hastings, the key advantage of our approach is that it allows to implement the "marginal Barker's" instead of the extended state space pseudo-marginal Metropolis–Hastings, owing to the special form of the accept/reject probability. We shall illustrate our methodology in the context of Bayesian inference for discretely observed Wright–Fisher family of diffusions.
View PDF Chat

Optimal Linear Bernoulli Factories for Small Mean Problems

2016-10-12
Mark Huber
View PDF Chat

Bayesian Games and the Smoothness Framework

2012-01-01
Vasilis Syrgkanis
We consider a general class of Bayesian Games where each players utility depends on his type (possibly multidimensional) and on the strategy profile and where players' types are distributed independently. … We consider a general class of Bayesian Games where each players utility depends on his type (possibly multidimensional) and on the strategy profile and where players' types are distributed independently. We show that if their full information version for any fixed instance of the type profile is a smooth game then the Price of Anarchy bound implied by the smoothness property, carries over to the Bayes-Nash Price of Anarchy. We show how some proofs from the literature (item bidding auctions, greedy auctions) can be cast as smoothness proofs or be simplified using smoothness. For first price item bidding with fractionally subadditive bidders we actually manage to improve by much the existing result \cite{Hassidim2011a} from 4 to $\frac{e}{e-1}\approx 1.58$. This also shows a very interesting separation between first and second price item bidding since second price item bidding has PoA at least 2 even under complete information. For a larger class of Bayesian Games where the strategy space of a player also changes with his type we are able to show that a slightly stronger definition of smoothness also implies a Bayes-Nash PoA bound. We show how weighted congestion games actually satisfy this stronger definition of smoothness. This allows us to show that the inefficiency bounds of weighted congestion games known in the literature carry over to incomplete versions where the weights of the players are private information. We also show how an incomplete version of a natural class of monotone valid utility games, called effort market games are universally $(1,1)$-smooth. Hence, we show that incomplete versions of effort market games where the abilities of the players and their budgets are private information has Bayes-Nash PoA at most 2.

Entropy, optimization and counting

2014-05-31
Mohit Singh , Nisheeth K. Vishnoi
We study the problem of computing max-entropy distributions over a discrete set of objects subject to observed marginals. There has been a tremendous amount of interest in such distributions due … We study the problem of computing max-entropy distributions over a discrete set of objects subject to observed marginals. There has been a tremendous amount of interest in such distributions due to their applicability in areas such as statistical physics, economics, biology, information theory, machine learning, combinatorics and algorithms. However, a rigorous and systematic study of how to compute such distributions has been lacking. Since the underlying set of discrete objects can be exponential in the input size, the first question in such a study is if max-entropy distributions have polynomially-sized descriptions. We start by giving a structural result which shows that such succinct descriptions exist under very general conditions. Subsequently, we use techniques from convex programming to give a meta-algorithm that can efficiently (approximately) compute max-entropy distributions provided one can efficiently (approximately) count the underlying discrete set. Thus, we can translate a host of existing counting algorithms, developed in an unrelated context, into algorithms that compute max-entropy distributions. Conversely, we prove that counting oracles are necessary for computing max-entropy distributions: we show how algorithms that compute max-entropy distributions can be converted into counting algorithms.
View PDF Chat

From the Bernoulli factory to a dice enterprise via perfect sampling of Markov chains

2022-02-01
Giulio Morina , Krzysztof Łatuszyński , Piotr Nayar +1 more
Given a p-coin that lands heads with unknown probability p, we wish to produce an f(p)-coin for a given function f:(0,1)→(0,1). This problem is commonly known as the Bernoulli factory … Given a p-coin that lands heads with unknown probability p, we wish to produce an f(p)-coin for a given function f:(0,1)→(0,1). This problem is commonly known as the Bernoulli factory and results on its solvability and complexity have been obtained in (ACM Trans. Model. Comput. Simul. 4 (1994) 213–219; Ann. Appl. Probab. 15 (2005) 93–115). Nevertheless, generic ways to design a practical Bernoulli factory for a given function f exist only in a few special cases. We present a constructive way to build an efficient Bernoulli factory when f(p) is a rational function with coefficients in R. Moreover, we extend the Bernoulli factory problem to a more general setting where we have access to an m-sided die and we wish to roll a v-sided one; that is, we consider rational functions between open probability simplices. Our construction consists of rephrasing the original problem as simulating from the stationary distribution of a certain class of Markov chains—a task that we show can be achieved using perfect simulation techniques with the original m-sided die as the only source of randomness. In the Bernoulli factory case, the number of tosses needed by the algorithm has exponential tails and its expected value can be bounded uniformly in p. En route to optimizing the algorithm we show a fact of independent interest: every finite, integer valued, random variable will eventually become log-concave after convolving with enough Bernoulli trials.
View PDF Chat

Rado's theorem for polymatroids

1975-09-01
Colin McDiarmid
The theorem of R. Rado (12) to which I refer by the name ‘Rado's theorem for matroids’ gives necessary and sufficient conditions for a family of subsets of a finite … The theorem of R. Rado (12) to which I refer by the name ‘Rado's theorem for matroids’ gives necessary and sufficient conditions for a family of subsets of a finite set Y to have a transversal independent in a given matroid on Y . This theorem is of fundamental importance in both transversal theory and matroid theory (see, for example, (11)). In (3) J. Edmonds introduced and studied ‘polymatroids’ as a sort of continuous analogue of a matroid. I start this paper with a brief introduction to polymatroids, emphasizing the role of the ‘ground-set rank function’. The main result is an analogue for polymatroids of Rado's theorem for matroids, which I call not unnaturally ‘Rado's theorem for polymatroids’.

The sample complexity of revenue maximization

2014-05-31
Richard Cole , Tim Roughgarden
In the design and analysis of revenue-maximizing auctions, auction performance is typically measured with respect to a prior distribution over inputs. The most obvious source for such a distribution is … In the design and analysis of revenue-maximizing auctions, auction performance is typically measured with respect to a prior distribution over inputs. The most obvious source for such a distribution is past data. The goal of this paper is to understand how much data is necessary and sufficient to guarantee near-optimal expected revenue.
View PDF Chat

Composable and efficient mechanisms

2013-05-28
Vasilis Syrgkanis , Éva Tardos
We initiate the study of efficient mechanism design with guaranteed good properties even when players participate in multiple mechanisms simultaneously or sequentially. We define the class of smooth mechanisms, related … We initiate the study of efficient mechanism design with guaranteed good properties even when players participate in multiple mechanisms simultaneously or sequentially. We define the class of smooth mechanisms, related to smooth games defined by Roughgarden, that can be thought of as mechanisms that generate approximately market clearing prices. We show that smooth mechanisms result in high quality outcome both in equilibrium and in learning outcomes in the full information setting, as well as in Bayesian equilibrium with uncertainty about participants. Our main result is to show that smooth mechanisms compose well: smoothness locally at each mechanism implies global efficiency.
View PDF Chat

Multidimensional Binary Search for Contextual Decision-Making

2018-07-25
Ilan Lobel , Renato Paes Leme , Adrian Vladu
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 … 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 log d factor. The algorithm combines a volume cutting strategy with a new geometric technique that we call cylindrification.
View PDF Chat

Prior-free auctions for budgeted agents

2013-06-11
Nikhil R. Devanur , Bach Q. Ha , Jason D. Hartline
We consider prior-free auctions for revenue and welfare maximization when agents have a common budget. The abstract environments we consider are ones where there is a downward-closed and symmetric feasibility … We consider prior-free auctions for revenue and welfare maximization when agents have a common budget. The abstract environments we consider are ones where there is a downward-closed and symmetric feasibility constraint on the probabilities of service of the agents. These environments include position auctions where slots with decreasing click-through rates are auctioned to advertisers. We generalize and characterize the envy-free benchmark from Hartline and Yan [2011] to settings with budgets and characterize the optimal envy-free outcomes for both welfare and revenue. We give prior-free mechanisms that approximate these benchmarks. A building block in our mechanism is a clinching auction for position auction environments. This auction is a generalization of the multi-unit clinching auction of Dobzinski et al. [2008] and a special case of the polyhedral clinching auction of Goel et al. [2012]. For welfare maximization, we show that this clinching auction is a good approximation to the envy-free optimal welfare for position auction environments. For profit maximization, we generalize the random sampling profit extraction auction from Fiat et al. [2002] for digital goods to give a 10.0-approximation to the envy-free optimal revenue in symmetric, downward-closed environments. Even without budgets this revenue maximization question is of interest and we obtain an improved approximation bound of 7.5 (from 30.4 by Ha and Hartline [2012]).
View PDF Chat

Comparison of Threshold Stop Rules and Maximum for Independent Nonnegative Random Variables

1984-11-01
Ester Samuel‐Cahn
Let $X_i \geq 0$ be independent, $i = 1, \cdots, n$, and $X^\ast_n = \max(X_1, \cdots, X_n)$. Let $t(c) (s(c))$ be the threshold stopping rule for $X_1, \cdots, X_n$, defined … Let $X_i \geq 0$ be independent, $i = 1, \cdots, n$, and $X^\ast_n = \max(X_1, \cdots, X_n)$. Let $t(c) (s(c))$ be the threshold stopping rule for $X_1, \cdots, X_n$, defined by $t(c) = \text{smallest} i$ for which $X_i \geq c(s(c) = \text{smallest} i$ for which $X_i > c), = n$ otherwise. Let $m$ be a median of the distribution of $X^\ast_n$. It is shown that for every $n$ and $\underline{X}$ either $EX^\ast_n \leq 2EX_{t(m)}$ or $EX^\ast_n \leq 2EX_{s(m)}$. This improves previously known results, [1], [4]. Some results for i.i.d. $X_i$ are also included.
View PDF Chat

Determinants and the volumes of parallelotopes and zonotopes

2010-03-05
Eugene Gover , Nishan Krikorian

Real stable polynomials and matroids: optimization and counting

2017-06-15
Damian Straszak , Nisheeth K. Vishnoi
Several fundamental optimization and counting problems arising in computer science, mathematics and physics can be reduced to one of the following computational tasks involving polynomials and set systems: given an … Several fundamental optimization and counting problems arising in computer science, mathematics and physics can be reduced to one of the following computational tasks involving polynomials and set systems: given an oracle access to an m-variate real polynomial g and to a family of (multi-)subsets ℬ of [m], (1) compute the sum of coefficients of monomials in g corresponding to all the sets that appear in B(1), or find S ε ℬ such that the monomial in g corresponding to S has the largest coefficient in g. Special cases of these problems, such as computing permanents and mixed discriminants, sampling from determinantal point processes, and maximizing sub-determinants with combinatorial constraints have been topics of much recent interest in theoretical computer science.
View PDF Chat

Simulating events of unknown probabilities via reverse time martingales

2010-05-27
Krzysztof Łatuszyński , Ioannis Kosmidis , Omiros Papaspiliopoulos +1 more
Abstract Let s ∈(0,1) be uniquely determined but only its approximations can be obtained with a finite computational effort. Assume one aims to simulate an event of probability s . … Abstract Let s ∈(0,1) be uniquely determined but only its approximations can be obtained with a finite computational effort. Assume one aims to simulate an event of probability s . Such settings are often encountered in statistical simulations. We consider two specific examples. First, the exact simulation of non‐linear diffusions ([ 3 ]). Second, the celebrated Bernoulli factory problem ([ 10 , 13 ]) of generating an f ( p )‐coin given a sequence X 1 , X 2 ,… of independent tosses of a p ‐coin (with known f and unknown p ). We describe a general framework and provide algorithms where this kind of problems can be fitted and solved. The algorithms are straightforward to implement and thus allow for effective simulation of desired events of probability s . Our methodology links the simulation problem to existence and construction of unbiased estimators. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 441–452, 2011
View PDF Chat

On simulating a class of Bernstein polynomials

2012-03-01
Vineet Goyal , Karl Sigman
Given a black box that generates independent Bernoulli samples with an unknown bias p, we consider the problem of simulating a Bernoulli random variable with bias f ( p ) … Given a black box that generates independent Bernoulli samples with an unknown bias p, we consider the problem of simulating a Bernoulli random variable with bias f ( p ) (where f is a given function) using a finite (computable in advance) number of independent Bernoulli samples from the black box. We show that this is possible if and only if f is a Bernstein polynomial with coefficients between 0 and 1, and we explicitly give the algorithm. Our results differ from Keane and O'Brien [1994] in that our goal is more modest/stringent, since we are considering algorithms that use a finite number of samples as opposed to allowing a random number (such as in acceptance rejection algorithms).

Exact sampling with coupled Markov chains and applications to statistical mechanics

1996-08-01
James Propp , David Bruce Wilson
For many applications it is useful to sample from a finite set of objects in accordance with some particular distribution. One approach is to run an ergodic (i.e., irreducible aperiodic) … For many applications it is useful to sample from a finite set of objects in accordance with some particular distribution. One approach is to run an ergodic (i.e., irreducible aperiodic) Markov chain whose stationary distribution is the desired distribution on this set; after the Markov chain has run for M steps, with M sufficiently large, the distribution governing the state of the chain approximates the desired distribution. Unfortunately, it can be difficult to determine how large M needs to be. We describe a simple variant of this method that determines on its own when to stop and that outputs samples in exact accordance with the desired distribution. The method uses couplings which have also played a role in other sampling schemes; however, rather than running the coupled chains from the present into the future, one runs from a distant point in the past up until the present, where the distance into the past that one needs to go is determined during the running of the algorithm itself. If the state space has a partial order that is preserved under the moves of the Markov chain, then the coupling is often particularly efficient. Using our approach, one can sample from the Gibbs distributions associated with various statistical mechanics models (including Ising, random-cluster, ice, and dimer) or choose uniformly at random from the elements of a finite distributive lattice. © 1996 John Wiley & Sons, Inc.

An asymptotically optimal Bernoulli factory for certain functions that can be expressed as power series

2018-12-05
Luis Mendo
View PDF Chat

On Optimal Ordering in the Optimal Stopping Problem

2020-07-09
Shipra Agrawal , Jay Sethuraman , Xingyu Zhang
Consider a player who can probe a sequence of n independent random variables X1, . . . , Xn with known distributions. After observing (the realized value of) Xi, the … Consider a player who can probe a sequence of n independent random variables X1, . . . , Xn with known distributions. After observing (the realized value of) Xi, the player needs to decide whether to stop and earn reward Xi, or reject the reward and probe the next variable Xi+1. The goal is to maximize the expected reward at the stopping time. This is an instance of the optimal stopping problem, which is a fundamental problem studied from many different aspects in mathematics, statistics, and computer science, and has found a wide variety of applications in sequential decision making and mechanism design.
View PDF Chat

Frugal Mechanism Design via Spectral Techniques

2010-10-01
Ning Chen , Edith Elkind , Nick Gravin +1 more
We study the design of truthful mechanisms for set systems, i.e., scenarios where a customer needs to hire a team of agents to perform a complex task. In this setting, … We study the design of truthful mechanisms for set systems, i.e., scenarios where a customer needs to hire a team of agents to perform a complex task. In this setting, frugality [Archer&Tardos'02] provides a measure to evaluate the "cost of truthfulness", that is, the overpayment of a truthful mechanism relative to the "fair" payment. We propose a uniform scheme for designing frugal truthful mechanisms for general set systems. Our scheme is based on scaling the agents' bids using the eigenvector of a matrix that encodes the interdependencies between the agents. We demonstrate that the r-out-of-k-system mechanism and the \sqrt-mechanism for buying a path in a graph [Karlin et. al'05] can be viewed as instantiations of our scheme. We then apply our scheme to two other classes of set systems, namely, vertex cover systems and k-path systems, in which a customer needs to purchase k edge-disjoint source-sink paths. For both settings, we bound the frugality of our mechanism in terms of the largest eigenvalue of the respective interdependency matrix. We show that our mechanism is optimal for a large subclass of vertex cover systems satisfying a simple local sparsity condition. For k-path systems, while our mechanism is within a factor of k + 1 from optimal, we show that it is, in fact, optimal, when one uses a modified definition of frugality proposed in [Elkind et al.'07]. Our lower bound argument combines spectral techniques and Young's inequality, and is applicable to all set systems. As both r-out-of-k systems and single path systems can be viewed as special cases of k-path systems, our result improves the lower bounds of [Karlin et al.'05] and answers several open questions proposed in that paper.
View PDF Chat

Algorithmic pricing via virtual valuations

2007-06-11
Shuchi Chawla , Jason D. Hartline , Robert Kleinberg
Algorithmic pricing is the computational problem that sellers (e.g.,in supermarkets) face when trying to set prices for their items to maximize their profit in the presence of a known demand. … Algorithmic pricing is the computational problem that sellers (e.g.,in supermarkets) face when trying to set prices for their items to maximize their profit in the presence of a known demand. Guruswami etal. (SODA, 2005) proposed this problem and gave logarithmic approximations (in the number of consumers) for the unit-demand and single-parameter cases where there is a specific set of consumers and their valuations for bundles are known precisely. Subsequently several versions of the problem have been shown to have poly-logarithmic in approximability. This problem has direct ties to the important open question of better understanding the Bayesian optimal mechanism in multi-parameter agent settings; however, for this purpose approximation factors logarithmic in the number of agents are inadequate. It is therefore of vital interest to consider special cases where constant approximations are possible. We consider the unit-demand variant of this pricing problem. Here a consumer has a valuation for each different item and their value for aset of items is simply the maximum value they have for any item in the set. Instead of considering a set of consumers with precisely known preferences, like the prior algorithmic pricing literature, we assume that the preferences of the consumers are drawn from a distribution. This is the standard assumption in economics; furthermore, the setting of a specific set of customers with specific preferences, which is employed in all of the prior work in algorithmic pricing, is a special case of this general Bayesian pricing problem, where there is a discrete Bayesian distribution for preferences specified by picking one consumer uniformly from the given set of consumers. Notice that the distribution over the valuations for the individual items that this generates is obviously correlated. Our work complements these existing works by considering the case where the consumer's valuations for the different items are independent random variables. Our main result is a constant approximation algorithm for this problem that makes use of an interesting connection between this problem and the concept of virtual valuations from the single-parameter Bayesian optimal mechanism design literature.
View PDF Chat

Solving convex programs by random walks

2004-07-01
Dimitris Bertsimas , Santosh Vempala
Minimizing a convex function over a convex set in n -dimensional space is a basic, general problem with many interesting special cases. Here, we present a simple new algorithm for … Minimizing a convex function over a convex set in n -dimensional space is a basic, general problem with many interesting special cases. Here, we present a simple new algorithm for convex optimization based on sampling by a random walk. It extends naturally to minimizing quasi-convex functions and to other generalizations.

Contextual Search via Intrinsic Volumes

2018-10-01
Renato Paes Leme , Jon Schneider
We study the problem of contextual search, a multidimensional generalization of binary search that captures many problems in contextual decision-making. In contextual search, a learner is trying to learn the … We study the problem of contextual search, a multidimensional generalization of binary search that captures many problems in contextual decision-making. In contextual search, a learner is trying to learn the value of a hidden vector. Every round the learner is provided an adversarially-chosen context vector, submits a guess for the inner product of the context vector with the hidden vector, learns whether their guess was too high or too low, and incurs some loss based on the quality of their guess. The learner's goal is to minimize their total loss over the course of some number of rounds. We present an algorithm for the contextual search problem for the symmetric loss function that achieves constant 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 doubly-logarithmic total loss, improving exponentially on the previous best known upper bounds and matching the known lower bounds (up to a polynomial dependence on dimension). 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 PDF Chat

Online Learning with an Unknown Fairness Metric

2018-01-01
Stephen Gillen , Christopher Jung , Michael Kearns +1 more
We consider the problem of online learning in the linear contextual bandits setting, but in which there are also strong individual fairness constraints governed by an unknown similarity metric. These … We consider the problem of online learning in the linear contextual bandits setting, but in which there are also strong individual fairness constraints governed by an unknown similarity metric. These constraints demand that we select similar actions or individuals with approximately equal probability (arXiv:1104.3913), which may be at odds with optimizing reward, thus modeling settings where profit and social policy are in tension. We assume we learn about an unknown Mahalanobis similarity metric from only weak feedback that identifies fairness violations, but does not quantify their extent. This is intended to represent the interventions of a regulator who "knows unfairness when he sees it" but nevertheless cannot enunciate a quantitative fairness metric over individuals. Our main result is an algorithm in the adversarial context setting that has a number of fairness violations that depends only logarithmically on $T$, while obtaining an optimal $O(\sqrt{T})$ regret bound to the best fair policy.

An experimental quantum Bernoulli factory

2019-01-04
Raj B. Patel , Terry Rudolph , Geoff J. Pryde
There has been a concerted effort to identify problems computable with quantum technology which are intractable with classical technology or require far fewer resources to compute. Recently, randomness processing in … There has been a concerted effort to identify problems computable with quantum technology which are intractable with classical technology or require far fewer resources to compute. Recently, randomness processing in a Bernoulli factory has been identified as one such task. Here, we report two quantum photonic implementations of a Bernoulli factory, one utilising quantum coherence and single-qubit measurements and the other which uses quantum coherence and entangling measurements of two qubits. We show that the former consumes three orders of magnitude fewer resources than the best known classical method, while entanglement offers a further five-fold reduction. These concepts may provide a means for quantum enhanced-performance in the simulation of stochastic processes and sampling tasks.
View PDF Chat

Beating 1-1/e for ordered prophets

2017-06-15
Melika Abolhassani , Soheil Ehsani , Hossein Esfandiari +3 more
Hill and Kertz studied the prophet inequality on iid distributions [The Annals of Probability 1982]. They proved a theoretical bound of 1 - 1/e on the approximation factor of their … Hill and Kertz studied the prophet inequality on iid distributions [The Annals of Probability 1982]. They proved a theoretical bound of 1 - 1/e on the approximation factor of their algorithm. They conjectured that the best approximation factor for arbitrarily large n is 1/1+1/e ≃ 0.731. This conjecture remained open prior to this paper for over 30 years. In this paper we present a threshold-based algorithm for the prophet inequality with n iid distributions. Using a nontrivial and novel approach we show that our algorithm is a 0.738-approximation algorithm. By beating the bound of 1/1+1/e, this refutes the conjecture of Hill and Kertz. Moreover, we generalize our results to non-uniform distributions and discuss its applications in mechanism design.
View PDF Chat

Dynamic Pricing in High-dimensions

2016-09-24
Adel Javanmard , Hamid Nazerzadeh
We study the pricing problem faced by a firm that sells a large number of products, described via a wide range of features, to customers that arrive over time. Customers … We study the pricing problem faced by a firm that sells a large number of products, described via a wide range of features, to customers that arrive over time. Customers independently make purchasing decisions according to a general choice model that includes products features and customers' characteristics, encoded as $d$-dimensional numerical vectors, as well as the price offered. The parameters of the choice model are a priori unknown to the firm, but can be learned as the (binary-valued) sales data accrues over time. The firm's objective is to minimize the regret, i.e., the expected revenue loss against a clairvoyant policy that knows the parameters of the choice model in advance, and always offers the revenue-maximizing price. This setting is motivated in part by the prevalence of online marketplaces that allow for real-time pricing. We assume a structured choice model, parameters of which depend on $s_0$ out of the $d$ product features. We propose a dynamic policy, called Regularized Maximum Likelihood Pricing (RMLP) that leverages the (sparsity) structure of the high-dimensional model and obtains a logarithmic regret in $T$. More specifically, the regret of our algorithm is of $O(s_0 \log d \cdot \log T)$. Furthermore, we show that no policy can obtain regret better than $O(s_0 (\log d + \log T))$.

Exact sampling for intractable probability distributions via a Bernoulli factory

2012-01-01
James M. Flegal , Radu Herbei
Many applications in the field of statistics require Markov chain Monte Carlo methods. Determining appropriate starting values and run lengths can be both analytically and empirically challenging. A desire to … Many applications in the field of statistics require Markov chain Monte Carlo methods. Determining appropriate starting values and run lengths can be both analytically and empirically challenging. A desire to overcome these problems has led to the development of exact, or perfect, sampling algorithms which convert a Markov chain into an algorithm that produces i.i.d. samples from the stationary distribution. Unfortunately, very few of these algorithms have been developed for the distributions that arise in statistical applications, which typically have uncountable support. Here we study an exact sampling algorithm using a geometrically ergodic Markov chain on a general state space. Our work provides a significant reduction to the number of input draws necessary for the Bernoulli factory, which enables exact sampling via a rejection sampling approach. We illustrate the algorithm on a univariate Metropolis-Hastings sampler and a bivariate Gibbs sampler, which provide a proof of concept and insight into hyper-parameter selection. Finally, we illustrate the algorithm on a Bayesian version of the one-way random effects model with data from a styrene exposure study.
View PDF Chat

A Field Guide to Personalized Reserve Prices

2016-04-11
Renato Paes Leme , Martin Pál , Sergei Vassilvitskii
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 … 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 PDF Chat

Frugality ratios and improved truthful mechanisms for vertex cover

2007-06-11
Edith Elkind , Leslie Ann Goldberg , Paul W. Goldberg
In set-system auctions, there are several overlapping teams of agents, and a task that can be completed by any of these teams. The auctioneer's goal is to hire a team … In set-system auctions, there are several overlapping teams of agents, and a task that can be completed by any of these teams. The auctioneer's goal is to hire a team and pay as little as possible. Examples of this setting include shortest-path auctions and vertex-cover auctions. Recently, Karlin, Kempe and Tamir introduced a new definition of for this problem. Informally, the frugality ratio is the of the total payment of a mechanism to a desired payment bound. The captures the extent to which the mechanism overpays, relative to perceived fair cost in a truthful auction. In this paper, we propose a new truthful polynomial-time auction for the vertex cover problem and bound its ratio. We show that the solution quality is with a constant factor of optimal and the is within a constant factor of the best possible worst-case bound; this is the first auction for this problem to have these properties. Moreover, we show how to transform any truthful auction into a frugal one while preserving the approximation ratio. Also, we consider two natural modifications of the definition of Karlin et al., and we analyse the properties of the resulting payment bounds, such as monotonicity, computational hardness, and robustness with respect to the draw-resolution rule. We study the relationships between the different payment bounds, both for general set systems and for specific set-system auctions, such as path auctions and vertex-cover auctions. We use these new definitions in the proof of our main result for vertex-cover auctions via a boot-strapping technique, which may be of independent interest.
View PDF Chat

Dynamic Pricing with Demand Covariates

2016-01-01
Sheng Qiang , Mohsen Bayati
We consider a firm that sells a product over T periods without knowing the demand function. The firm sequentially sets prices to earn revenue and to learn the underlying demand … We consider a firm that sells a product over T periods without knowing the demand function. The firm sequentially sets prices to earn revenue and to learn the underlying demand function simultaneously. In practice, this problem is commonly solved via greedy iterative least squares (GILS). At each time period, GILS estimates the demand as a linear function of the price by applying least squares to the set of prior prices and realized demands. Then a price that maximizes the revenue is used for the next period. The performance is measured by the regret, which is the expected revenue compared to an oracle that knows the true demand function. Recently, den Boer and Zwart (2014) and Keskin and Zeevi (2014) demonstrated that GILS is sub-optimal and introduced optimal algorithms which integrate forced price-dispersion with GILS. Here, we consider this dynamic pricing problem in a data-rich environment. We assume that the firm has access to demand covariates which may be predictive of the demand and prove that GILS achieves an asymptotically optimal regret of order log(T). We also show that the asymptotic optimality of GILS holds even when the covariates are uninformative. We validate our results via simulations on synthetic and real data.
View PDF Chat

On Multiple Round Sponsored Search Auctions with Budgets

2011-01-01
Martin Starnberger , Stefano Leonardi , Monika Henzinger +1 more
In a sponsored search auction the advertisement slots on a search result page are generally ordered by click-through rate. Bidders have a valuation, which is usually assumed to be linear … In a sponsored search auction the advertisement slots on a search result page are generally ordered by click-through rate. Bidders have a valuation, which is usually assumed to be linear in the click-through rate, a budget constraint, and receive at most one slot per search result page (round). We study multi-round sponsored search auctions, where the different rounds are linked through the budget constraints of the bidders and the valuation of a bidder for all rounds is the sum of the valuations for the individual rounds. All mechanisms published so far either study one-round sponsored search auctions or the setting where every round has only one slot and all slots have the same click-through rate, which is identical to a multi-item auction. This paper contains the following three results: (1) We give the first mechanism for the multi-round sponsored search problem where different slots have different click-through rates. Our mechanism is incentive compatible in expectation, individually rational in expectation, Pareto optimal in expectation, and also ex-post Pareto optimal for each realized outcome. (2) Additionally we study the combinatorial setting, where each bidder is only interested in a subset of the rounds. We give a deterministic, incentive compatible, individually rational, and Pareto optimal mechanism for the setting where all slots have the same click-through rate. (3) We present an impossibility result for auctions where bidders have diminishing marginal valuations. Specifically, we show that even for the multi-unit (one slot per round) setting there is no incentive compatible, individually rational, and Pareto optimal mechanism for private diminishing marginal valuations and public budgets.

Experimental Quantum Randomness Processing Using Superconducting Qubits

2016-06-29
Xiao Yuan , Ke Liu , Yuan Xu +7 more
Coherently manipulating multipartite quantum correlations leads to remarkable advantages in quantum information processing. A fundamental question is whether such quantum advantages persist only by exploiting multipartite correlations, such as entanglement. … Coherently manipulating multipartite quantum correlations leads to remarkable advantages in quantum information processing. A fundamental question is whether such quantum advantages persist only by exploiting multipartite correlations, such as entanglement. Recently, Dale, Jennings, and Rudolph negated the question by showing that a randomness processing, quantum Bernoulli factory, using quantum coherence, is strictly more powerful than the one with classical mechanics. In this Letter, focusing on the same scenario, we propose a theoretical protocol that is classically impossible but can be implemented solely using quantum coherence without entanglement. We demonstrate the protocol by exploiting the high-fidelity quantum state preparation and measurement with a superconducting qubit in the circuit quantum electrodynamics architecture and a nearly quantum-limited parametric amplifier. Our experiment shows the advantage of using quantum coherence of a single qubit for information processing even when multipartite correlation is not present.
View PDF Chat

Comments on bases in dependence structures

1969-08-01
Richard A. Brualdi
Dependence structures (in the finite case, matroids) arise when one tries to abstract the properties of linear dependence of vectors in a vector space. With the help of a theorem … Dependence structures (in the finite case, matroids) arise when one tries to abstract the properties of linear dependence of vectors in a vector space. With the help of a theorem due to P. Hall and M. Hall, Jr concerning systems of distinct representatives of families of finite sets, it is proved that if B 1 and B 2 are bases of a dependence structure, then there is an injection σ: B 1 → B 2 such that ( B 2 / {σ( e )}) ∩ { e } is a basis for all e in B 1 . A corollary is the theorem of R. Rado that all bases have the same cardinal number. In particular, it applies to bases of a vector space. Also proved is the fact that if B 1 and B 2 are bases of a dependence structure then given e in B 1 there is an f in B 2 such that both ( B 1 / { e }) ∩ { f } and ( B 2 / { f }) ∩ { e } are bases. This is a symmetrical kind of replacement theorem.
View PDF Chat

A Truthful Mechanism for Offline Ad Slot Scheduling

2008-01-01
Jon Feldman , S. Muthukrishnan , Evdokia Nikolova +1 more
View PDF Chat

Simultaneous auctions are (almost) efficient

2013-05-28
Michal Feldman , Hu Fu , Nick Gravin +1 more
Simultaneous item auctions are simple and practical procedures for allocating items to bidders with potentially complex preferences. In a simultaneous auction, every bidder submits independent bids on all items simultaneously. … Simultaneous item auctions are simple and practical procedures for allocating items to bidders with potentially complex preferences. In a simultaneous auction, every bidder submits independent bids on all items simultaneously. The allocation and prices are then resolved for each item separately, based solely on the bids submitted on that item. We study the efficiency of Bayes-Nash equilibrium (BNE) outcomes of simultaneous first- and second-price auctions when bidders have complement-free (a.k.a. subadditive) valuations. While it is known that the social welfare of every pure Nash equilibrium (NE) constitutes a constant fraction of the optimal social welfare, a pure NE rarely exists, and moreover, the full information assumption is often unrealistic. Therefore, quantifying the welfare loss in Bayes-Nash equilibria is of particular interest. Previous work established a logarithmic bound on the ratio between the social welfare of a BNE and the expected optimal social welfare in both first-price auctions (Hassidim et al., 2011) and second-price auctions (Bhawalkar and Roughgarden, 2011), leaving a large gap between a constant and a logarithmic ratio. We introduce a new proof technique and use it to resolve both of these gaps in a unified way. Specifically, we show that the expected social welfare of any BNE is at least 1/2 of the optimal social welfare in the case of first-price auctions, and at least 1/4 in the case of second-price auctions.
View PDF Chat

Inequalities between intrinsic volumes

1991-03-01
Peter McMullen

Approximation Schemes for Sequential Posted Pricing in Multi-unit Auctions

2010-01-01
Tanmoy Chakraborty , Eyal Even-Dar , Sudipto Guha +2 more
View PDF Chat

Pricing Strategies for Viral Marketing on Social Networks

2009-01-01
David Arthur , Rajeev Motwani , Aneesh Sharma +1 more
View PDF Chat