Doctorant F/H Online matching with delays and batching
Inria
Palaiseau, Essonne
Doctorant F/H Online matching with delays and batching
Type de contrat : CDD
Niveau de diplôme exigé : Bac + 5 ou équivalent
Fonction : Doctorant
A propos du centre ou de la direction fonctionnelle
The Inria Saclay-Île-de-France Research Centre was established in 2008. It has developed as part of the Saclay site in partnership with Paris-Saclay University and with the Institut Polytechnique de Paris .
The centre has 39 project teams , 27 of which operate jointly with Paris-Saclay University and the Institut Polytechnique de Paris; Its activities occupy over 600 people, scientists and research and innovation support staff, including 44 different nationalities.
Contexte et atouts du poste
Many markets are two-sided, with supply on one side and demand on the other, that are paired via some mechanisms. For instance, in “physical” markets, such as flea/fruit and vegetables/etc. markets, stores are fixed and clients arrive and decide themselves where and what to purchase. Such decentralized and physical marketplaces are interesting at small scale for obvious reasons, but many other, new markets are nowadays opened digitally and the offer is too large/complicated for this individual "window shopping" behaviors (and even, in the aforementioned examples, case-by-case bargaining) and moreover both sides can refuse the pairing. As a consequence, demand cannot be matched this easily with supply.
The future markets are going to be online, wide (national or even international) and the pairing between offer and demand (that we will call, from now on, matchings [10, 13]) are going to be facilitated, organized, and regularized by some platforms, obviously learning from gathered data, past errors and successes, in some automatic fashion. Artificial intelligence will certainly be their core technique.
There are different types of matching markets, sometimes with their specificities, such as online market-place (where small companies can sell their items on large platforms whose names do not necessarily need to be disclosed), students in universities allocations, housing markets (with the development of working from home policies), kidney exchanges (with donors and recipients), 5G networks (with user on available bandwidths), gaming platforms (to play online with strangers), dating apps, vehicles (any kind of them) on demand, labor market (firms or universities looking to hire employees),crowdsourcing, etc.
Mission confiée
The standard mathematical formulation of the online matching problem described above is interesting but quite limited; few of the motivating examples can be appropriately modeled by it. This explains why variants already exist.
Instead of generalizing the model, many “simpler” models were also considered. For instance, the celebrated establishing “prophet inequalities”consists in finding the best online matching when |U| is reduced to a singleton (or only a few numbers of them). In the latter, the additional assumption is usually that costs and/or rewards are random variables with known distribution (other variants of this problem are called secretary problems, Pandora’s boxes, etc. but the space limit prevents developing them, while still interesting).
We aim at considering the impacts and/or benefits of the fact that, in practice, decisions might not be taken sequentially, at each stage, but can be batched, i.e., the decision maker can wait d time-steps before making the irrevocable decisions for those. This is highly motivated by the motivating applications and examples (as companies bundle their decisions to save time/costs, even if that is at the cost of some immediate reward). This assumption requires going beyond the worst-case examples. Indeed, given any instance of a decision process without delay, it is possible to generate another instance where the batching has no impact: simply create d − 1 dummy decisions (with 0 cost/reward).
This approach has been widely studied in multi-armed bandit, but only marginally in competitive analysisalthough it will certainly be quite impactful (and a nice way to interpolate between the online and the offline cases).
Principales activités
Main activity: Conduct research on online matchings/algorithms
Additional activity : Publish papers on the subject
Compétences
Technical skills and level required : Mathematics/Computer Science
Languages : French or English
Avantages
Subsidized meals
Partial reimbursement of public transport costs
Leave: 7 weeks of annual leave + 10 extra days off due to RTT (statutory
reduction in working hours) + possibility of exceptional leave (sick children,
moving home, etc.)
Possibility of teleworking (after 6 months of employment) and flexible
organization of working hours
Professional equipment available (videoconferencing, loan of computer
equipment, etc.)
Social, cultural and sports events and activities
Access to vocational training
Social security coverage
Rémunération
Salary : 1st and 2nd year monthly gross salary : 2.082 euros, 3rd year : 2.190 euros monthly gross salary