Objectif du cours

The objectives are to understand and master how to sequentially take that may have a strong impact on the future (typically depletion of budget). This course will be at the junction of mathematics, theoretical computer science and economics.

More precisely, the goal is to construct and analyse algorithms that discover, and then treat, data one after the other one rather than directly with the whole batch. Typical examples are stopping times (prophets, secretary), online matching, k-servers, etc. I will cover the main techniques used (related to linear optimisation, stochastic approximation, tree reductions..) and will provide as many open questions as possible.

The « quality » of a sequence of decisions is then compared with the optimal ones, that know everything in advance. The typical cases are

* Prophet inequalities: Data X_1,…,X_n, are observed sequentially and the decision maker chooses when to stop and he receives X_t (here t is a stopping time). The prophet would get max X_i, hence the performance is measured in terms of Competitive Ratio E[X_t]/max X_i. Variants of this problem are called secretaries, pandora box, etc. The new motivations for this problem are online auctions.

* Online matching: A bipartite (say) graph is discovered sequentially, and a matching is constructed vertex by vertex as follows. One side of the graph is present from the beginning (call it the offline side) while the other vertices (on the online side) arrive sequentially and each time a vertex – with its edges – is discovered, one must match it to an offline vertex, if possible. The performance is measured with respect to the size (or the weight) of the matching constructing, divided by the size/weight of the optimal matching. The variants include b-matching, ad-words, delayed matching, etc. The motivation is online resource allocation (for instance, how to spend the budget of different campaigns)

* Metrical Task System: The typical, most complicated case is the k-server problem. The DM has k servers in some metrical space. At each time, a request pops up somewhere and the DM must move a server from its current location to the location of the query. The cost is the total distance of all the servers. There are many other examples of such tasks, such as convex body chasing, online transportation (like optimal transport, but in an online fashion), onling paging and caching, etc.

Disclaimer : the concept of online algorithms is related to online learning (and bandits) but the main question is rather to figure when to make a decision than which decision to make. Techniques, tools and results are fundamentally different