Bidding and Pricing in Budget and ROI Constrained Markets

In online advertising markets, setting budget and return on investment (ROI) constraints are two prevalent ways to help advertisers (i.e. buyers) utilize limited monetary resources efficiently. In this work, we provide a holistic view of ROI and budget constrained markets. We first tackle the buyer's bidding problem subject to both budget and ROI constraints in repeated second-price auctions. We show that the optimal buyer hindsight policy admits a "threshold-based" structure that suggests the buyer win all auctions during which her valuation-to-expenditure ratio is greater than some threshold. We further propose a threshold-based bidding framework that aims to mimic the hindsight bidding policy by learning its threshold. We show that when facing stochastic competition, our algorithm guarantees the satisfaction of both budget and ROI constraints and achieves sublinear regret compared to the optimal hindsight policy. Next, we study the seller's pricing problem against an ROI and budget constrained buyer. We establish that the seller's revenue function admits a bell-shaped structure, and then further propose a pricing algorithm that utilizes an episodic binary-search procedure to identify a revenue-optimal selling price. During each binary search episode, our pricing algorithm explores a particular price, allowing the buyer's learning algorithm to adapt and stabilize quickly. This, in turn, allows our seller algorithm to achieve sublinear regret against adaptive buyer algorithms that quickly react to price changes.