Multi-Platform Autobidding with and without Predictions

We study the problem of finding the optimal bidding strategy for an advertiser in a multi-platform auction setting. The competition on a platform is captured by a value and a cost function, mapping bidding strategies to value and cost respectively. We assume a diminishing returns property, whereby the marginal cost is increasing in value. The advertiser uses an autobidder that selects a bidding strategy for each platform, aiming to maximize total value subject to budget and return-on-spend constraint. The advertiser has no prior information and learns about the value and cost functions by querying a platform with a specific bidding strategy. Our goal is to design algorithms that find the optimal bidding strategy with a small number of queries. We first present an algorithm that requires (O(m log (mn) log n)) queries, where m is the number of platforms and n is the number of possible bidding strategies in each platform. Moreover, we adopt the learning-augmented framework and propose an algorithm that utilizes a (possibly erroneous) prediction of the optimal bidding strategy. We provide a O(m log (mη) log η) query-complexity bound on our algorithm as a function of the prediction error η. This guarantee gracefully degrades to (O(m log (mn) log n)). This achieves a "best-of-both-worlds" scenario: (O(m)) queries when given a correct prediction, and (O(m log (mn) log n)) even for an arbitrary incorrect prediction.