Research Areas
Authored Publications
Google Publications
Other Publications
Sort By
Autobidding Auctions in the Presence of User Costs
Hanrui Zhang
Proceedings of the ACM Web Conference 2023, pp. 3428-3435
Preview abstract
Although costs are prevalent in ad auctions, not many auction theory works study auction design in the presence of cost in the classic settings. One reason is that most auctions design in the setting without cost directly generalize to the setting with cost when the bidders maximizing quasi-linear utility.
However, as auto-bidding becomes a major choice of advertisers in online advertising, the distinction from the underlying behavior model often leads to different solutions of many well-studied auctions. In the context of ad auctions with cost, VCG achieves optimal welfare with quasi-linear utility maximizing bidders, while has 0 welfare approximation guarantee with value maximizing bidders who follow the optimization behind common auto-bidding algorithms.
In this paper, we prove that the approximation welfare guarantee of VCG auction can be significantly improved by a minimal change --- introducing cost multipliers. We note that one can use either one multiplier per auction or one multiplier per bidder, but one global multiplier across all auctions and bidders does not work. Finally, to echo with our theoretical results, we conduct empirical evaluations using semi-synthetic data derived from real auction data of a major advertising platform.
View details
Calibrated Click-Through Auctions
Dirk Bergemann
Paul Duetting
Proceedings of the ACM Web Conference 2022, pp. 47-57
Preview abstract
We analyze the optimal information design in a click-through auction with stochastic click-through rates and known valuations per click. The auctioneer takes as given the auction rule of the click-through auction, namely the generalized second-price auction. Yet, the auctioneer can design the information flow regarding the click-through rates among the bidders. We require that the information structure to be calibrated in the learning sense. With this constraint, the auction needs to rank the ads by a product of the value and a calibrated prediction of the click-through rates. The task of designing an optimal information structure is thus reduced to the task of designing an optimal calibrated prediction.
We show that in a symmetric setting with uncertainty about the click-through rates, the optimal information structure attains both social efficiency and surplus extraction. The optimal information structure requires private (rather than public) signals to the bidders. It also requires correlated (rather than independent) signals, even when the underlying uncertainty regarding the click-through rates is independent. Beyond symmetric settings, we show that the optimal information structure requires partial information disclosure, and achieves only partial surplus extraction.
View details
Optimal Mechanisms for Value Maximizers with Budget Constraints via Target Clipping
Proceedings of the 23rd ACM Conference on Economics and Computation (2022), pp. 475
Preview abstract
We study the design of revenue-maximizing mechanisms for value-maximizing agents with budget constraints. Agents have return-on-spend constraints requiring a minimum amount of value per unit of payment made and budget constraints limiting their total payments. The agents' only private information are the minimum admissible ratios on the return-on-spend constraint, referred to as the target ratios.
Our work is motivated by internet advertising platforms, where automated bidders are increasingly being adopted by advertisers to purchase advertising opportunities on their behalf. Instead of specifying bids for each keyword, advertiser set high-level goals, such as maximizing clicks, and targets on cost-per-clicks or return-on-spend, and the platform automatically purchases opportunities by bidding in different auctions. We present a model that abstracts away the complexities of the auto-bidding procurement process that is general enough to accommodate many allocation mechanisms such as auctions, matchings, etc.
We reduce the mechanism design problem when agents have private target ratios to a challenging non-linear optimization problem with monotonicity constraints. We provide a novel decomposition approach to tackle this problem that yields insights into the structure of optimal mechanisms and show that surprising features stem from the interaction on budget and return-on-spend constraints. Our optimal mechanism, which we dub the target-clipping mechanism, has an appealing structure: it sets a threshold on the target ratio of each agent, targets above the threshold are allocated efficiently, and targets below are clipped to the threshold.
View details
Revenue-Incentive Tradeoffs in Dynamic Reserve Pricing
International Conference on Machine Learning (2021), pp. 2601-2610
Preview abstract
Online advertisements are primarily sold via repeated auctions with reserve prices. In this paper, we study how to set reserves to boost revenue based on the historical bids of strategic buyers, while controlling the impact of such a policy on the incentive compatibility of the repeated auctions. Adopting an incentive compatibility metric which quantifies the incentives to shade bids, we propose a novel class of reserve pricing policies and provide analytical tradeoffs between their revenue performance and bid-shading incentives. The policies are inspired by the exponential mechanism from the literature on differential privacy, but our study uncovers mechanisms with significantly better revenue-incentive tradeoffs than the exponential mechanism in practice. We further empirically evaluate the tradeoffs on synthetic data as well as ad auction data from a major ad exchange to verify and support our theoretical findings.
View details
Non-Clairvoyant Dynamic Mechanism Design with Budget Constraints and Beyond
Proceedings of the 22nd ACM Conference on Economics and Computation (2021), pp. 369
Preview abstract
We provide a general design framework for dynamic mechanisms under complex environments, coined Lossless History Compression mechanisms. Lossless history compression mechanisms compress the history into a state carrying the least historical information without losing any generality in terms of either revenue or welfare. In particular, the characterization works for almost arbitrary constraints on the outcomes, and any objective function defined on the historical reports, allocations, and the cumulative payments. We then apply our framework to design a non-clairvoyant dynamic mechanism under budget and ex-post individual rationality constraints that is dynamic incentive-compatible and achieves non-trivial revenue performance, even without any knowledge about the future. In particular, our dynamic mechanism obtains a constant approximation to the optimal dynamic mechanism having access to all information in advance. To the best of our knowledge, this is the first dynamic mechanism that achieves a constant approximation and strictly respects dynamic incentive-compatibility and budget constraints without relying on any forecasts of the future.
View details
Preview abstract
Auto-bidding has become one of the main options for bidding in online advertisements, in which advertisers only need to specify high-level objectives and leave the complex task of bidding to auto-bidders. In this paper, we propose a family of auctions with boosts to improve welfare for auto-bidders with both return on ad spend constraints and budget constraints. Our empirical results validate our theoretical findings and show that both the welfare and revenue can be improved by selecting the weight of the boosts properly.
View details
The Landscape of Autobidding Auctions: Value versus Utility Maximization
Proceedings of the 22nd ACM Conference on Economics and Computation (2021), pp. 132-133
Preview abstract
Internet advertisers are increasingly adopting automated bidders to buy advertising opportunities. Automated bidders simplify the procurement process by allowing advertisers to specify their goals and then bidding on their behalf in the auctions that are used to sell advertising slots. One popular goal adopted by advertisers is to maximize their clicks (or conversions) subject to a return on spend (RoS) constraint, which imposes that the ratio of total value to total spend is greater than a target ratio specified by the advertisers. The emergence of automated bidders brings into question whether the standard mechanisms used to sold ads are still effective in this new landscape. Thus motivated, in this paper we study the problem of characterizing optimal mechanisms for selling an item to one of multiple agents with return on spend constraints when either the values or target ratios are private. We consider two objectives for the agents: value maximization, which is becoming the prevalent objective in advertising markets, and utility maximization, which is the de facto paradigm in economic theory. Our goal is to understand the impact of the agents' private information and their objectives on the seller's revenue, and determine whether the first-best revenue, which is the optimal revenue without private information, is achievable.
View details
Non-Excludable Dynamic Mechanism Design
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, pp. 1357-1373
Preview abstract
Dynamic mechanism design expands the scope on what type of allocation rules can be implemented and what revenue can be extracted when compared to static mechanisms. The case of excludable environments (i.e. one player can be de-allocated while keeping the allocation of the remaining players intact) is very well understood. The mechanisms in the literature don’t extend to the non-excludable environments. Two prototypical examples of such environments are: (i) public projects, where all players must have the same allocation; and (ii) non-disposable goods, where each item must be allocated to some player. We show a general mechanism that can asymptotically extract the full surplus in such environments. Moreover, we fully characterize which abstract mechanism design environments allow for full surplus extraction in the limit. Our characterization is based on the geometry of achievable utility sets – a convex set characterizing the expected utility profiles that can be implemented in a static mechanism.
View details
Robust Auction Design in the Auto-bidding World
Advances in Neural Information Processing Systems (2021)
Preview abstract
In classic auction theory, reserve prices are known to be effective for improving revenue for the auctioneer against quasi-linear utility maximizing bidders. The introduction of reserve prices, however, usually do not help improve total welfare of the auctioneer and the bidders. In this paper, we focus on value maximizing bidders with return on spend constraints---a paradigm that has drawn considerable attention recently as more advertisers adopt auto-bidding algorithms in advertising platforms---and show that the introduction of reserve prices has a novel impact on the market. Namely, by choosing reserve prices appropriately the auctioneer can improve not only the total revenue but also the total welfare. Our results also demonstrate that reserve prices are robust to bidder types, i.e., reserve prices work well for different bidder types, such as value maximizers and utility maximizers, without using bidder type information. We generalize these results for a variety of auction mechanisms such as VCG, GSP, and first-price auctions. Moreover, we show how to combine these results with additive boosts to improve the welfare of the outcomes of the auction further. Finally, we complement our theoretical observations with an empirical study confirming the effectiveness of these ideas using data from online advertising auctions.
View details
Bayesian Nash Equilibrium in First Price Auction with Discrete Value Distribution
Zihe Wang
Weiran Shen
Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems (2020), pp. 1458-1466
Preview abstract
First price auction is widely used in government contract and industrial auctions. We study Bayesian Nash Equilibrium (BNE) in first price auction with discrete value distribution.We constructively prove the existence of BNE in first price auction and provide an algorithm to compute BNE at the same time. Moreover, we prove that BNE is unique. Some previous results of equilibrium in continuous value distribution do not suit for discrete value distribution. We cannot prove the uniqueness result in discrete case by using the uniqueness property in continuous case either. Furthermore, unlike the continuous case, we do not have the computation error when solving ordinary differential equations. Experiments show that our algorithm for discrete distribution is faster and more accurate than applying previous method on the continuous distribution which approximates the very discrete distribution.
The results in this paper are derived in the asymmetric independent private values model, which assumes that the distributions of buyers’ valuations are common knowledge.
View details
Non-Clairvoyant Dynamic Mechanism Design
Pingzhong Tang
Econometrica, vol. 88(5) (2020), pp. 1939-1963
Preview abstract
We introduce a new family of dynamic mechanisms that restricts sellers from using future distributional knowledge. Since the allocation and pricing of each auction period do not depend on the type distributions of future periods, we call this family of dynamic mechanisms non‐clairvoyant.
We develop a framework (bank account mechanisms) for characterizing, designing, and proving lower bounds for dynamic mechanisms (clairvoyant or non‐clairvoyant). We use the same methods to compare the revenue extraction power of clairvoyant and non‐clairvoyant dynamic mechanisms.
View details
A Data-Driven Metric of Incentive Compatibility
Proceedings of The Web Conference (2020), pp. 1796-1806
Preview abstract
An incentive-compatible auction incentivizes buyers to truthfully reveal their private valuations. However, many ad auction mechanisms deployed in practice are not incentive-compatible, such as first-price auctions (for display advertising) and the generalized second-price auction (for search advertising). We introduce a new metric to quantify incentive compatibility in both static and dynamic environments. Our metric is data-driven and can be computed directly through black-box auction simulations without relying on reference mechanisms or complicated optimizations. We provide interpretable characterizations of our metric and prove that it is monotone in auction parameters for several mechanisms used in practice, such as soft floors and dynamic reserve prices. We empirically evaluate our metric on ad auction data from a major ad exchange and a major search engine to demonstrate its broad applicability in practice.
View details
Preview abstract
We study the computation contests where players compete for searching a solution to a given problem with a winner-take-all reward. The search processes are independent across the players and the search speeds of players are proportional to their computational powers. One concrete application of this abstract model is the mining process of proof-of-work type blockchain systems, such as Bitcoin. Although one's winning probability is believed to be proportional to his computational power in previous studies on Bitcoin, we show that it is not the case in the strict sense.
Because of the gaps between the winning probabilities and the proportions of computational powers, the Matthew effect will emerge in the system, where the rich get richer and the poor get poorer. In addition, we show that allowing the players to pool with each other or reducing the number of solutions to the problem may aggravate the Matthew effect and vice versa.
View details
Automated mechanism design via neural networks
Weiran Shen
Pingzhong Tang
Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, International Foundation for Autonomous Agents and Multiagent Systems (2019), pp. 215-223
Preview abstract
Using AI approaches to automatically design mechanisms has been a central research mission at the interface of AI and economics [Conitzer and Sandholm, 2002]. Previous approaches that attempt to design revenue optimal auctions for the multi-dimensional settings fall short in at least one of the three aspects: 1) representation — search in a space that probably does not even contain the optimal mechanism; 2) exactness — finding a mechanism that is either not truthful or far from optimal; 3) domain dependence — need a different design for different environment settings.
To resolve the three difficulties, in this paper, we put forward a unified neural network based framework that automatically learns to design revenue optimal mechanisms. Our framework consists of a mechanism network that takes an input distribution for training and outputs a mechanism, as well as a buyer network that takes a mechanism as input and output an action. Such a separation in design mitigates the difficulty to impose incentive compatibility constraints on the mechanism, by making it a rational choice of the buyer. As a result, our framework easily overcomes the previously mentioned difficulty in incorporating IC constraints and always returns exactly incentive compatible mechanisms.
We then applied our framework to a number of multi-item auction design settings, for a few of which the theoretically optimal mechanisms are unknown. We then go on to theoretically prove that the mechanisms found by our framework are indeed optimal.
View details
Learning the Optimal Strategies to Commit to
Binghui Peng
Weiran Shen
Pingzhong Tang
Proceedings of the AAAI Conference on Artificial Intelligence (2019), pp. 2149-2156
Preview abstract
Over the past decades, various theories and algorithms have been developed under the framework of Stackelberg games and part of these innovations have been fielded under the scenarios of national security defenses and wildlife protections. However, one of the remaining difficulties in the literature is
that most of theoretical works assume full information of the payoff matrices, while in applications, the leader often has no prior knowledge about the follower’s payoff matrix, but may gain information about the follower’s utility function through repeated interactions. In this paper, we study the problem of learning the optimal leader strategy in Stackelberg (security) games and develop novel algorithms as well as new hardness results.
View details
Optimal Dynamic Auctions are Virtual Welfare Maximizers
Pingzhong Tang
Proceedings of the AAAI Conference on Artificial Intelligence (2019), pp. 2125-2132
Preview abstract
We are interested in the setting where a seller sells sequentially
arriving items, one per period, via a dynamic auction.
At the beginning of each period, each buyer draws a private
valuation for the item to be sold in that period and this valuation
is independent across buyers and periods. The auction
can be dynamic in the sense that the auction at period
t can be conditional on the bids in that period and all previous
periods, subject to certain appropriately defined incentive
compatible and individually rational conditions. Perhaps
not surprisingly, the revenue optimal dynamic auctions are
computationally hard to find and existing literatures that aim
to approximate the optimal auctions are all based on solving
complex dynamic programs. It remains largely open on the
structural interpretability of the optimal dynamic auctions.
In this paper, we show that any optimal dynamic auction is
a virtual welfare maximizer subject to some monotone allocation
constraints. In particular, the explicit definition of
the virtual value function above arises naturally from the
primal-dual analysis by relaxing the monotone constraints.
We further develop an ironing technique that gets rid of the
monotone allocation constraints. Quite different from Myerson’s
ironing approach, our technique is more technically involved
due to the interdependence of the virtual value functions
across buyers. We nevertheless show that ironing can be
done approximately and efficiently, which in turn leads to a
Fully Polynomial Time Approximation Scheme of the optimal
dynamic auction.
View details
Dynamic Double Auctions: Towards First Best
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pp. 157-172
Preview abstract
We study the problem of designing dynamic double auctions for two-sided markets in which a platform intermediates the trade between one seller offering independent items to multiple buyers, repeatedly over a finite horizon, when agents have private values. Motivated by online advertising and ride-hailing markets, we seek to design mechanisms satisfying the following properties: no positive transfers, i.e., the platform never asks the seller to make payments nor buyers are ever paid and periodic individual rationality, i.e., every agent should derive a non-negative utility from every trade opportunity. We provide mechanisms satisfying these requirements that are asymptotically efficient and budget-balanced with high probability as the number of trading opportunities grows. Moreover, we show that the average expected profit obtained by the platform under these mechanisms asymptotically approaches first-best (the maximum possible welfare generated by the market).
View details
Dispatching Through Pricing: Modeling Ride-Sharing and Designing Dynamic Prices
Mengjing Chen
Weiran Shen
Pingzhong Tang
Proceedings of the 28th International Joint Conference on Artificial Intelligence (2019), pp. 165-171
Preview abstract
Over the past few years, ride-sharing has emerged as an effective way to relieve traffic congestion.
A key problem for the ride-sharing platforms is to come up with a revenue-optimal (or GMV-optimal)
pricing scheme and a vehicle dispatching policy that incorporate geographic and temporal information. In this paper, we aim to tackle this problem via an economic approach. Modeled naively, the underlying optimization problem may be non-convex and thus hard to solve. To this end, we use a so-called “ironing” technique to convert the problem into an equivalent convex optimization one via a clean Markov decision process (MDP) formulation, where the states are the driver distributions and the decision variables are the prices for each pair of locations. Our main finding is an efficient algorithm that computes the exact revenue-optimal (or GMV-optimal) randomized pricing scheme, which naturally induces the accompany vehicle dispatching policy. We also conduct empirical evaluations of our solution through real data of a major ride-sharing platform and show its advantages over fixed pricing schemes as well as several prevalent surge-based pricing schemes.
View details
Non-Clairvoyant Dynamic Mechanism Design
Pingzhong Tang
Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, ACM, pp. 169
Preview abstract
Despite their better revenue and welfare guarantees for repeated auctions, dynamic mechanisms have not been widely adopted in practice. This is partly due to the complexity of their implementation as well as their unrealistic use of forecasting for future periods. We address these shortcomings and present a new family of dynamic mechanisms that are simple and require no distributional knowledge of future periods.
This paper introduces the concept of non-clairvoyance in dynamic mechanism design, which is a measure-theoretic restriction on the information that the seller is allowed to use. A dynamic mechanism is non-clairvoyant if the allocation and pricing rule at each period does not depend on the type distributions in the future periods.
We develop a framework (bank account mechanisms) for characterizing, designing, and proving lower bounds for dynamic mechanisms (clairvoyant or non-clairvoyant). This framework is used to characterize the revenue extraction power of the non-clairvoyant mechanisms with respect to the mechanisms that are allowed unrestricted use of distributional knowledge.
View details
Incentive-Aware Learning for Large Markets
Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018, Lyon, France, April 23-27, 2018, pp. 1369-1378
Preview abstract
In a typical learning problem, one key step is to use training data to pick one model from a collection of models that optimizes an objective function. In many multi-agent settings, the training data is generated through the actions of the agents, and the model is
used to make a decision (e.g., how to sell an item) that affects the agents. An illustrative example of this is the problem of learning the
reserve price in an auction. In such cases, the agents have an incentive to influence the training data (e.g., by manipulating their bids in
the case of an auction) to game the system and achieve a more favorable outcome. In this paper, we study such incentive-aware learning
problem in a general setting and show that it is possible to approximately optimize the objective function under two assumptions:
(i) each individual agent is a “small” (part of the market); and (ii) there is a cost associated with manipulation. For our illustrative
application, this nicely translates to a mechanism for setting approximately optimal reserve prices in auctions where no individual
agent has significant market share. For this application, we also show that the second assumption (that manipulations are costly) is
not necessary since we can “perturb” any auction to make it costly for the agents to manipulate.
View details
Dynamic Mechanism Design in the Field
Rita Ren
Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018, Lyon, France, April 23-27, 2018, {ACM}, pp. 1359-1368
Preview abstract
Dynamic mechanisms are a powerful technique in designing revenue-maximizing repeated auctions. Despite their strength, these types of mechanisms have not been widely adopted in practice for several reasons, e.g., for their complexity, and for their sensitivity to the accuracy of predicting buyers' value distributions. In this paper, we aim to address these shortcomings and develop simple dynamic mechanisms that can be implemented efficiently, and provide theoretical guidelines for decreasing the sensitivity of dynamic mechanisms on prediction accuracy of buyers' value distributions. We prove that the dynamic mechanism we propose is provably dynamic incentive compatible, and introduce a notion of buyers' regret in dynamic mechanisms, and show that our mechanism achieves bounded regret while improving revenue and social welfare compared to a static reserve pricing policy. Finally, we confirm our theoretical analysis via an extensive empirical study of our dynamic auction on real data sets from online adverting. For example, we show our dynamic mechanisms can provide a 17% revenue lift with relative regret less than 0.2%.
View details
Dynamic Revenue Sharing
Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA
Preview abstract
Many online platforms act as intermediaries between a seller and a set of buyers. Examples of such settings include online retailers (such as Ebay) selling items on behalf of sellers to buyers, or advertising exchanges (such as AdX) selling pageviews on behalf of publishers to advertisers. In such settings, revenue sharing is a central part of running such a marketplace for the intermediary, and fixed-percentage revenue sharing schemes are often used to split the revenue among the platform and the sellers. In particular, such revenue sharing schemes require the platform to (i) take at most a constant fraction α of the revenue from auctions and (ii) pay the seller at least the seller declared opportunity cost c for each item sold. A straightforward way to satisfy the constraints is to set a reserve price at c/(1 − α ) for each item, but it is not the optimal solution on maximizing the profit of the intermediary.
While previous studies (by Mirrokni and Gomes, and by Niazadeh et al) focused on revenue-sharing schemes in static double auctions, in this paper, we take advantage of the repeated nature of the auctions, and present solutions based on dynamic mechanism design. In particular, we introduce dynamic revenue sharing schemes where we balance the two constraints over different auctions to achieve higher profit. This is directly motivated by the practice of advertising exchanges where the fixed-percentage revenue-share should be met across all auctions and not in each auction. In this paper, we characterize the optimal revenue sharing scheme that satisfies both constraints in expectation. Finally, we empirically evaluate our revenue sharing scheme on real
data.
View details
Dynamic Auctions with Bank Accounts
Pingzhong Tang
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (2016), pp. 387-393
Preview abstract
Consider a buyer with independent additive valuations for a set of goods, and a seller who is constrained to sell one item at a time in an online fashion. If the seller is constrained to run independent auctions for each item, then he would run Myerson’s optimal auction for each item. If the seller is allowed to use the full power of dynamic mechanism design and have the auction for each item depend on the outcome of the previous auctions, he is able to perform much better. The main issues in implementing such strategies in online settings where items arrive over time are that the auction might be too complicated or it makes too strong assumptions on the buyer’s rationality or seller’s commitment over time. This motivates us to explore a restricted family of dynamic auctions that can be implemented in an online fashion and without too much commitment from the seller ahead of time. In particular, we study a set of auction in which the space of single-shot auctions is augmented with a structure that we call bank account, a real number for each node that summarizes the history so far. This structure allows the seller to store deficits or surpluses of buyer utility from each individual auction and even them out on the long run. This is akin to enforcing individual rationality constraint on average rather than per auction. We also study the effect of enforcing a maximum limit to the values that bank account might grow, which means that we enforce that besides the auction being individually rational on average it is also not far from being individually rational at any given interval. Interestingly, even with these restrictions, we can achieve
significantly better revenue and social welfare compared to separate Myerson auctions.
View details
No Results Found
