In online combinatorial allocation, agents arrive sequentially and items are allocated in an online manner. The algorithm designer only knows the distribution of each agent’s valuation, while the actual realization of the valuation is revealed only upon her arrival. Against the offline benchmark, Feldman, Gravin, and Lucier (SODA 2015) designed an optimal 0.5-competitive algorithm for XOS agents. An emerging line of work focuses on designing approximation algorithms against the (computationally unbounded) optimal online algorithm. The primary goal is to design algorithms with approximation ratios strictly greater than 0.5, surpassing the impossibility result against the offline optimum. Positive results are established for unit-demand agents (Papadimitriou, Pollner, Saberi, Wajc, MOR 2024), and for \(k\)-demand agents (Braun, Kesselheim, Pollner, Saberi, EC 2024).

Online advertising platforms must decide how to allocate multiple ads across limited screen real estate, where each ad's effectiveness depends not only on its own placement but also on nearby ads competing for user attention. Such spatial externalities — arising from proximity, clutter, or crowding — can significantly alter welfare and revenue outcomes, yet existing auction and allocation models typically treat ad slots as independent or ordered along a single dimension.

In the secretary problem, a set of secretary candidates arrive in a uniformly random order and reveal their values one by one. A company, who can only hire one candidate and hopes to maximize the expected value of its hire, needs to make irrevocable online decisions about whether to hire the current candidate. The classical framework of evaluating a policy is to compute its worst-case competitive ratio against the optimal solution in hindsight, and there the best policy -- the ''1/e law'' -- has a competitive ratio of 1/e. We propose an alternative evaluation framework through the lens of regret -- the worst-case additive difference between the optimal hindsight solution and the expected performance of the policy, assuming that each value is normalized between 0 and 1. The 1/e law for the classical framework has a regret of 1 - 1/e ≈ 0.632; by contrast, we show that the class of ''pricing curves'' algorithms can guarantee a regret of at most 1/4 = 0.25 (which is tight within the class), and the class of ''best-only pricing curves'' algorithms can guarantee a regret of at most 0.190 (with a lower bound of 0.171). In addition, we show that in general, no policy can give a regret guarantee better than 0.152. Finally, we discuss other objectives in our regret-minimization framework.

Multi-item mechanism design has been studied extensively in the literature of economics and computation in the past two decades. Many recent works in the multi-dimensional mechanism design setting have been focused on approximating the optimal revenue via simple mechanisms. One particularly important mechanism that is both studied in the literature and implemented in real-world scenarios is the item pricing mechanism.

Sequential posted pricing auctions are popular because of their simplicity in practice and their tractability in theory. A usual assumption in their study is that the Bayesian prior distributions of the buyers are known to the seller, while in reality these priors can only be accessed from historical data. To overcome this assumption, we study sequential posted pricing in the bandit learning model, where the seller interacts with n buyers over T rounds: In each round the seller posts n prices for the n buyers and the first buyer with a valuation higher than the price takes the item. The only feedback that the seller receives in each round is the revenue.

The Prophet Inequality and Pandora's Box problems are fundamental stochastic problem with applications in Mechanism Design, Online Algorithms, Stochastic Optimization, Optimal Stopping, and Operations Research. A usual assumption in these works is that the probability distributions of the n underlying random variables are given as input to the algorithm. Since in practice these distributions need to be learned under limited feedback, we initiate the study of such stochastic problems in the Multi-Armed Bandits model.