We revisit the celebrated Ranking algorithm by Karp, Vazirani, and Vazirani (STOC 1990) for online bipartite matching under the random arrival model, that is shown to be 0.696-competitive for unweighted graphs by Mahdian and Yan (STOC 2011) and 0.662-competitive for vertex-weighted graphs by Jin and Williamson (WINE 2021).

We consider the robust contract design problem when the principal only has limited information about the actions the agent can take. The principal evaluates a contract according to its worst-case performance caused by the uncertain action space. Carroll (AER 2015) showed that a linear contract is optimal among deterministic contracts. Recently, Kambhampati (JET 2023) showed that the principal's payoff can be strictly increased via randomization over linear contracts. In this paper, we characterize the optimal randomized contract, which remains linear and admits a closed form of its cumulative density function. The advantage of randomized contracts over deterministic contracts can be arbitrarily large even when the principal knows only one non-trivial action of the agent. Furthermore, our result generalizes to the model of contracting with teams, by Dai and Toikka (Econometrica 2022).

In the classical prophet inequality, a gambler faces a sequence of items, whose values are drawn independently from known distributions. Upon the arrival of each item, its value is realized and the gambler either accepts it and the game ends, or irrevocably rejects it and continues to the next item. The goal is to maximize the value of the selected item and compete against the expected maximum value of all items. A tight competitive ratio of $\frac{1}{2}$ is established in the classical setting and various relaxations have been proposed to surpass the barrier, including the i.i.d. model, the order selection model, and the random order model. In this paper, we advance the study of the order selection prophet inequality, in which the gambler is given the extra power for selecting the arrival order of the items. Our main result is a 0.725-competitive algorithm, that substantially improves the state-of-the-art 0.669 ratio by Correa, Saona and Ziliotto (Math. Program. 2021), achieved in the harder random order model. Recently, Agrawal, Sethuraman and Zhang (EC 2020) proved that the task of selecting the optimal order is NP-hard. Despite this fact, we introduce a novel algorithm design framework that translates the discrete order selection problem into a continuous arrival time design problem. From this perspective, we can focus on the arrival time design without worrying about the threshold optimization afterwards. As a side result, we achieve the optimal 0.745 competitive ratio by applying our algorithm to the i.i.d. model.