Marco Scarsini

Marco Scarsini, Eran Shmaya

We consider an M/M/s queueing model in which customers strategically decide, based on the service reward and waiting cost, whether to join upon arrival or balk and, at any time, whether to remain in the queue or renege. Rational strategic behavior yields an equilibrium whose outcome may be socially efficient or inefficient, depending on the queueing regime. Some regimes yield an efficient equilibrium only under precise calibration to the model parameters. Others are universally optimal, meaning that their equilibrium outcome is efficient for all parameter values. Universal optimality is therefore an appealing property for a planner choosing a queueing regime. We characterize the class of universally optimal queueing regimes. A by-product of our characterization is that preemption plays an unavoidable role in universally optimal regimes.

Nicolò Cesa-Bianchi, Tommaso Cesari, Takayuki Osogami et al.

We study a repeated game between a supplier and a retailer who want to maximize their respective profits without full knowledge of the problem parameters. After characterizing the uniqueness of the Stackelberg equilibrium of the stage game with complete information, we show that even with partial knowledge of the joint distribution of demand and production costs, natural learning dynamics guarantee convergence of the joint strategy profile of supplier and retailer to the Stackelberg equilibrium of the stage game. We also prove finite-time bounds on the supplier's regret and asymptotic bounds on the retailer's regret, where the specific rates depend on the type of knowledge preliminarily available to the players. In the special case when the supplier is not strategic (vertical integration), we prove optimal finite-time regret bounds on the retailer's regret (or, equivalently, the social welfare) when costs and demand are adversarially generated and the demand is censored.

Maurizio D'Andrea, Marco Scarsini

We consider a strategic M/M/1 queueing model under a first-come-first-served regime, where customers are split into two classes and class $A$ has priority over class $B$. Customers can decide whether to join the queue or balk, and, in case they have joined the queue, whether and when to renege. We study the equilibrium strategies and compare the equilibrium outcome and the social optimum in the two cases where the social optimum is or is not constrained by priority.

Etienne Boursier, Tristan Garrec, Vianney Perchet et al.

We study online learning for optimal allocation when the resource to be allocated is time. %Examples of possible applications include job scheduling for a computing server, a driver filling a day with rides, a landlord renting an estate, etc. An agent receives task proposals sequentially according to a Poisson process and can either accept or reject a proposed task. If she accepts the proposal, she is busy for the duration of the task and obtains a reward that depends on the task duration. If she rejects it, she remains on hold until a new task proposal arrives. We study the regret incurred by the agent, first when she knows her reward function but does not know the distribution of the task duration, and then when she does not know her reward function, either. This natural setting bears similarities with contextual (one-armed) bandits, but with the crucial difference that the normalized reward associated to a context depends on the whole distribution of contexts.

Etienne Boursier, Vianney Perchet, Marco Scarsini

Potential buyers of a product or service, before making their decisions, tend to read reviews written by previous consumers. We consider Bayesian consumers with heterogeneous preferences, who sequentially decide whether to buy an item of unknown quality, based on previous buyers' reviews. The quality is multi-dimensional and may occasionally vary over time; the reviews are also multi-dimensional. In the simple uni-dimensional and static setting, beliefs about the quality are known to converge to its true value. Our paper extends this result in several ways. First, a multi-dimensional quality is considered, second, rates of convergence are provided, third, a dynamical Markovian model with varying quality is studied. In this dynamical setting the cost of learning is shown to be small.