Dans cette thèse, nous étudions le contrôle dynamique des systèmes de partage de ressources qui se posent dans divers domaines : réseaux de gestion des stocks, services de santé, réseaux de communication, etc. Nous visons à allouer efficacement les ressources disponibles entre des projets concurrents, selon certains critères de performance. Ce type de problème est de nature stochastique et peut être très complexe à résoudre. Nous nous concentrons donc sur le développement de méthodes heuristiques performantes. Dans la partie I, nous nous plaçons dans le cadre des Restless Bandit Problems, qui est une classe générale de problèmes d’optimisation dynamique stochastique. Relaxer la contrainte de trajectoire dans le problème d’optimisation permet de définir une politique d’index comme heuristique pour le modèle contraint d’origine, aussi appelée politique d’index de Whittle. Nous dérivons une expression analytique pour l’index de Whittle en fonction des probabilités stationnaires de l’état dans le cas où les bandits (ou projets) suivent un processus de naissance et de mort. D’une part, cette expression nécessite la vérification de plusieurs conditions techniques, d’autre part elle ne peut être calculée explicitement que dans certains cas spécifiques. Nous prouvons ensuite, que dans le cas particulier d’une file d’attente multi-classe avec abandon, la politique d’index de Whittle est asymptotiquement optimale aussi bien pour les régimes à faible trafic comme pour ceux à fort trafic. Dans la partie II, nous dérivons des heuristiques issues de l’approximation des systèmes stochastiques de partage de ressources par des modèles fluides déterministes. Nous formulons dans un premier temps une version fluide du problème d’optimisation relaxé que nous avons introduit dans la partie I, et développons une politique d’index fluide. L’index fluide peut toujours être calculé explicitement et surmonte donc les questions techniques qui se posent lors du calcul de l’index de Whittle. Nous appliquons les politiques d’index de Whittle et de l’index fluide à plusieurs cas : les fermes de serveurs éco-conscients, l’ordonnancement opportuniste dans les systèmes sans fil, et la gestion de stockage de produits périssables. Nous montrons numériquement que ces politiques d’index sont presque optimales. Dans un second temps, nous étudions l’ordonnancement optimal de la version fluide d’une file d’attente multi-classe avec abandon. Nous obtenons le contrôle optimal du modèle fluide en présence de deux classes de clients en concurrence pour une même ressource. En nous appuyant sur ces derniers résultats, nous proposons une heuristique pour le cas général de plusieurs classes. Cette heuristique montre une performance quasi-optimale lorsqu’elle est appliquée au modèle stochastique original pour des charges de travail élevées. Enfin, dans la partie III, nous étudions les phénomènes d’abandon dans le contexte d’un problème de distribution de contenu. Nous caractérisons une politique optimale de regroupement afin que des demandes issues d’utilisateurs impatients puissent être servies efficacement en mode diffusion. / In this thesis we study the dynamic control of resource-sharing systems that arise in various domains: e.g. inventory management, healthcare and communication networks. We aim at efficiently allocating the available resources among competing projects according to a certain performance criteria. These type of problems have a stochastic nature and may be very complex to solve. We therefore focus on developing well-performing heuristics. In Part I, we consider the framework of Restless Bandit Problems, which is a general class of dynamic stochastic optimization problems. Relaxing the sample-path constraint in the optimization problem enables to define an index-based heuristic for the original constrained model, the so-called Whittle index policy. We derive a closed-form expression for the Whittle index as a function of the steady-state probabilities for the case in which bandits (projects) evolve in a birth-and-death fashion. This expression requires several technical conditions to be verified, and in addition, it can only be computed explicitly in specific cases. In the particular case of a multi-class abandonment queue, we further prove that the Whittle index policy is asymptotically optimal in the light-traffic and heavy-traffic regimes. In Part II, we derive heuristics by approximating the stochastic resource-sharing systems with deterministic fluid models. We first formulate a fluid version of the relaxed optimization problem introduced in Part I, and we develop a fluid index policy. The fluid index can always be computed explicitly and hence overcomes the technical issues that arise when calculating the Whittle index. We apply the Whittle index and the fluid index policies to several systems: e.g. power-aware server-farms, opportunistic scheduling in wireless systems, and make-to-stock problems with perishable items. We show numerically that both index policies are nearly optimal. Secondly, we study the optimal scheduling control for the fluid version of a multi-class abandonment queue. We derive the fluid optimal control when there are two classes of customers competing for a single resource. Based on the insights provided by this result we build a heuristic for the general multi-class setting. This heuristic shows near-optimal performance when applied to the original stochastic model for high workloads. In Part III, we further investigate the abandonment phenomena in the context of a content delivery problem. We characterize an optimal grouping policy so that requests, which are impatient, are efficiently transmitted in a multi-cast mode.

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第24939号 / 情博第850号 / 新制||情||142(附属図書館) / 京都大学大学院情報学研究科システム科学専攻 / (主査)准教授 本多 淳也, 教授 田中 利幸, 教授 鹿島 久嗣 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

La thèse comporte trois essais en microéconomie appliquée. En utilisant des modèles d’apprentissage (learning) et d’externalité de réseau, elle étudie le comportement des agents économiques dans différentes situations. Le premier essai de la thèse se penche sur la question de l’utilisation des ressources naturelles en situation d’incertitude et d’apprentissage (learning). Plusieurs auteurs ont abordé le sujet, mais ici, nous étudions un modèle d’apprentissage dans lequel les agents qui consomment la ressource ne formulent pas les mêmes croyances a priori. Le deuxième essai aborde le problème générique auquel fait face, par exemple, un fonds de recherche désirant choisir les meilleurs parmi plusieurs chercheurs de différentes générations et de différentes expériences. Le troisième essai étudie un modèle particulier d’organisation d’entreprise dénommé le marketing multiniveau (multi-level marketing). Le premier chapitre est intitulé "Renewable Resource Consumption in a Learning Environment with Heterogeneous beliefs". Nous y avons utilisé un modèle d’apprentissage avec croyances hétérogènes pour étudier l’exploitation d’une ressource naturelle en situation d’incertitude. Il faut distinguer ici deux types d’apprentissage : le adaptive learning et le learning proprement dit. Ces deux termes ont été empruntés à Koulovatianos et al (2009). Nous avons montré que, en comparaison avec le adaptive learning, le learning a un impact négatif sur la consommation totale par tous les exploitants de la ressource. Mais individuellement certains exploitants peuvent consommer plus la ressource en learning qu’en adaptive learning. En effet, en learning, les consommateurs font face à deux types d’incitations à ne pas consommer la ressource (et donc à investir) : l’incitation propre qui a toujours un effet négatif sur la consommation de la ressource et l’incitation hétérogène dont l’effet peut être positif ou négatif. L’effet global du learning sur la consommation individuelle dépend donc du signe et de l’ampleur de l’incitation hétérogène. Par ailleurs, en utilisant les variations absolues et relatives de la consommation suite à un changement des croyances, il ressort que les exploitants ont tendance à converger vers une décision commune. Le second chapitre est intitulé "A Perpetual Search for Talent across Overlapping Generations". Avec un modèle dynamique à générations imbriquées, nous avons étudié iv comment un Fonds de recherche devra procéder pour sélectionner les meilleurs chercheurs à financer. Les chercheurs n’ont pas la même "ancienneté" dans l’activité de recherche. Pour une décision optimale, le Fonds de recherche doit se baser à la fois sur l’ancienneté et les travaux passés des chercheurs ayant soumis une demande de subvention de recherche. Il doit être plus favorable aux jeunes chercheurs quant aux exigences à satisfaire pour être financé. Ce travail est également une contribution à l’analyse des Bandit Problems. Ici, au lieu de tenter de calculer un indice, nous proposons de classer et d’éliminer progressivement les chercheurs en les comparant deux à deux. Le troisième chapitre est intitulé "Paradox about the Multi-Level Marketing (MLM)". Depuis quelques décennies, on rencontre de plus en plus une forme particulière d’entreprises dans lesquelles le produit est commercialisé par le biais de distributeurs. Chaque distributeur peut vendre le produit et/ou recruter d’autres distributeurs pour l’entreprise. Il réalise des profits sur ses propres ventes et reçoit aussi des commissions sur la vente des distributeurs qu’il aura recrutés. Il s’agit du marketing multi-niveau (multi-level marketing, MLM). La structure de ces types d’entreprise est souvent qualifiée par certaines critiques de système pyramidal, d’escroquerie et donc insoutenable. Mais les promoteurs des marketing multi-niveau rejettent ces allégations en avançant que le but des MLMs est de vendre et non de recruter. Les gains et les règles de jeu sont tels que les distributeurs ont plus incitation à vendre le produit qu’à recruter. Toutefois, si cette argumentation des promoteurs de MLMs est valide, un paradoxe apparaît. Pourquoi un distributeur qui désire vraiment vendre le produit et réaliser un gain recruterait-il d’autres individus qui viendront opérer sur le même marché que lui? Comment comprendre le fait qu’un agent puisse recruter des personnes qui pourraient devenir ses concurrents, alors qu’il est déjà établi que tout entrepreneur évite et même combat la concurrence. C’est à ce type de question que s’intéresse ce chapitre. Pour expliquer ce paradoxe, nous avons utilisé la structure intrinsèque des organisations MLM. En réalité, pour être capable de bien vendre, le distributeur devra recruter. Les commissions perçues avec le recrutement donnent un pouvoir de vente en ce sens qu’elles permettent au recruteur d’être capable de proposer un prix compétitif pour le produit qu’il désire vendre. Par ailleurs, les MLMs ont une structure semblable à celle des multi-sided markets au sens de Rochet et Tirole (2003, 2006) et Weyl (2010). Le recrutement a un effet externe sur la vente et la vente a un effet externe sur le recrutement, et tout cela est géré par le promoteur de l’organisation. Ainsi, si le promoteur ne tient pas compte de ces externalités dans la fixation des différentes commissions, les agents peuvent se tourner plus ou moins vers le recrutement. / This thesis includes three essays in applied microeconomics. Using learning and network effects models, we study agents’ behavior in various environments through three chapters. The first chapter examines natural resource exploitation under uncertainty with learning and heterogeneous priors. In the second chapter, we examine the problem of research Foundation concerned with finding good quality researchers for today and the future. The third chapter studies the Multi-level marketing organizations. The first chapter is entitled "Renewable Resource Consumption in a Learning Environment with Heterogeneous beliefs". This work uses a learning model with heterogeneity of beliefs to study natural resources consumption under uncertainty. Following Koulovatianos et al (2009), we distinguish two types of learning process: adaptive learning and learning. I find that learning decreases the total consumption of the resource in comparison with adaptive learning. However, individually and under some conditions, some exploiters could consume more in learning than in adaptive learning. In learning, the exploiter faces two kinds of incentive to invest in the resource: self-incentive which is always positive and heterogeneity incentive which may be negative. The effect of learning on individual consumption depends on the sign and the extent of the heterogeneity incentive. Using absolute change and relative change of consumption due to a change in beliefs, we find that the exploiters tend to converge to a common behaviour. The second chapter is entitled "A perpetual Search for Talent across Overlapping Generations". We use a dynamic discrete time model with overlapping generations to study how a research Fund should optimally rank and select which researchers to give a grant. The optimal decision rule depends on both the perceived quality of researchers based on past success histories and on age. Between two researchers of equal perceived qualities the Fund should select the youngest. This work contributes to the understanding of the bandit problems sometime known to be untractable and pspace-hard. Here, instead of looking for an index characterization, we propose to rank or eliminate progressively the researchers by comparing them two by two. The third chapter is entitled "Paradox about the Multi-Level Marketing". Over the past 50 years, the Multi-level Marketing (MLM) has become an important business strategy. vi MLM is a marketing method in which independent distributors of a product get profits not only from their own sales, but also from recruiting other distributors. According to the promoters of this organization, the purpose of the business and the will of the distributors are to sell the product and not to set up a scam. The question is the following: if the real intention is to sell, why does a distributor recruit other distributors who will become his competitors? It is well known in classical industrial organization that people avoid competition as well as possible. Why is it not the case in the MLM organization? We explain this paradox by the particular economic structure of the MLM. Distributor could not sell enough if he did not recruit. Recruiting provides a price leading power and allows to sell more and make more profit (in some respect). Moreover, the MLM is similar to the multi-sided market structure a la Rochet and Tirole (2003, 2006) and Weyl (2010). There is network effect between recruitment and selling activity. Thus, the extent of the paradox can also be explained by the different commissions set by the MLM promoters.

La thèse comporte trois essais en microéconomie appliquée. En utilisant des modèles d’apprentissage (learning) et d’externalité de réseau, elle étudie le comportement des agents économiques dans différentes situations. Le premier essai de la thèse se penche sur la question de l’utilisation des ressources naturelles en situation d’incertitude et d’apprentissage (learning). Plusieurs auteurs ont abordé le sujet, mais ici, nous étudions un modèle d’apprentissage dans lequel les agents qui consomment la ressource ne formulent pas les mêmes croyances a priori. Le deuxième essai aborde le problème générique auquel fait face, par exemple, un fonds de recherche désirant choisir les meilleurs parmi plusieurs chercheurs de différentes générations et de différentes expériences. Le troisième essai étudie un modèle particulier d’organisation d’entreprise dénommé le marketing multiniveau (multi-level marketing). Le premier chapitre est intitulé "Renewable Resource Consumption in a Learning Environment with Heterogeneous beliefs". Nous y avons utilisé un modèle d’apprentissage avec croyances hétérogènes pour étudier l’exploitation d’une ressource naturelle en situation d’incertitude. Il faut distinguer ici deux types d’apprentissage : le adaptive learning et le learning proprement dit. Ces deux termes ont été empruntés à Koulovatianos et al (2009). Nous avons montré que, en comparaison avec le adaptive learning, le learning a un impact négatif sur la consommation totale par tous les exploitants de la ressource. Mais individuellement certains exploitants peuvent consommer plus la ressource en learning qu’en adaptive learning. En effet, en learning, les consommateurs font face à deux types d’incitations à ne pas consommer la ressource (et donc à investir) : l’incitation propre qui a toujours un effet négatif sur la consommation de la ressource et l’incitation hétérogène dont l’effet peut être positif ou négatif. L’effet global du learning sur la consommation individuelle dépend donc du signe et de l’ampleur de l’incitation hétérogène. Par ailleurs, en utilisant les variations absolues et relatives de la consommation suite à un changement des croyances, il ressort que les exploitants ont tendance à converger vers une décision commune. Le second chapitre est intitulé "A Perpetual Search for Talent across Overlapping Generations". Avec un modèle dynamique à générations imbriquées, nous avons étudié iv comment un Fonds de recherche devra procéder pour sélectionner les meilleurs chercheurs à financer. Les chercheurs n’ont pas la même "ancienneté" dans l’activité de recherche. Pour une décision optimale, le Fonds de recherche doit se baser à la fois sur l’ancienneté et les travaux passés des chercheurs ayant soumis une demande de subvention de recherche. Il doit être plus favorable aux jeunes chercheurs quant aux exigences à satisfaire pour être financé. Ce travail est également une contribution à l’analyse des Bandit Problems. Ici, au lieu de tenter de calculer un indice, nous proposons de classer et d’éliminer progressivement les chercheurs en les comparant deux à deux. Le troisième chapitre est intitulé "Paradox about the Multi-Level Marketing (MLM)". Depuis quelques décennies, on rencontre de plus en plus une forme particulière d’entreprises dans lesquelles le produit est commercialisé par le biais de distributeurs. Chaque distributeur peut vendre le produit et/ou recruter d’autres distributeurs pour l’entreprise. Il réalise des profits sur ses propres ventes et reçoit aussi des commissions sur la vente des distributeurs qu’il aura recrutés. Il s’agit du marketing multi-niveau (multi-level marketing, MLM). La structure de ces types d’entreprise est souvent qualifiée par certaines critiques de système pyramidal, d’escroquerie et donc insoutenable. Mais les promoteurs des marketing multi-niveau rejettent ces allégations en avançant que le but des MLMs est de vendre et non de recruter. Les gains et les règles de jeu sont tels que les distributeurs ont plus incitation à vendre le produit qu’à recruter. Toutefois, si cette argumentation des promoteurs de MLMs est valide, un paradoxe apparaît. Pourquoi un distributeur qui désire vraiment vendre le produit et réaliser un gain recruterait-il d’autres individus qui viendront opérer sur le même marché que lui? Comment comprendre le fait qu’un agent puisse recruter des personnes qui pourraient devenir ses concurrents, alors qu’il est déjà établi que tout entrepreneur évite et même combat la concurrence. C’est à ce type de question que s’intéresse ce chapitre. Pour expliquer ce paradoxe, nous avons utilisé la structure intrinsèque des organisations MLM. En réalité, pour être capable de bien vendre, le distributeur devra recruter. Les commissions perçues avec le recrutement donnent un pouvoir de vente en ce sens qu’elles permettent au recruteur d’être capable de proposer un prix compétitif pour le produit qu’il désire vendre. Par ailleurs, les MLMs ont une structure semblable à celle des multi-sided markets au sens de Rochet et Tirole (2003, 2006) et Weyl (2010). Le recrutement a un effet externe sur la vente et la vente a un effet externe sur le recrutement, et tout cela est géré par le promoteur de l’organisation. Ainsi, si le promoteur ne tient pas compte de ces externalités dans la fixation des différentes commissions, les agents peuvent se tourner plus ou moins vers le recrutement. / This thesis includes three essays in applied microeconomics. Using learning and network effects models, we study agents’ behavior in various environments through three chapters. The first chapter examines natural resource exploitation under uncertainty with learning and heterogeneous priors. In the second chapter, we examine the problem of research Foundation concerned with finding good quality researchers for today and the future. The third chapter studies the Multi-level marketing organizations. The first chapter is entitled "Renewable Resource Consumption in a Learning Environment with Heterogeneous beliefs". This work uses a learning model with heterogeneity of beliefs to study natural resources consumption under uncertainty. Following Koulovatianos et al (2009), we distinguish two types of learning process: adaptive learning and learning. I find that learning decreases the total consumption of the resource in comparison with adaptive learning. However, individually and under some conditions, some exploiters could consume more in learning than in adaptive learning. In learning, the exploiter faces two kinds of incentive to invest in the resource: self-incentive which is always positive and heterogeneity incentive which may be negative. The effect of learning on individual consumption depends on the sign and the extent of the heterogeneity incentive. Using absolute change and relative change of consumption due to a change in beliefs, we find that the exploiters tend to converge to a common behaviour. The second chapter is entitled "A perpetual Search for Talent across Overlapping Generations". We use a dynamic discrete time model with overlapping generations to study how a research Fund should optimally rank and select which researchers to give a grant. The optimal decision rule depends on both the perceived quality of researchers based on past success histories and on age. Between two researchers of equal perceived qualities the Fund should select the youngest. This work contributes to the understanding of the bandit problems sometime known to be untractable and pspace-hard. Here, instead of looking for an index characterization, we propose to rank or eliminate progressively the researchers by comparing them two by two. The third chapter is entitled "Paradox about the Multi-Level Marketing". Over the past 50 years, the Multi-level Marketing (MLM) has become an important business strategy. vi MLM is a marketing method in which independent distributors of a product get profits not only from their own sales, but also from recruiting other distributors. According to the promoters of this organization, the purpose of the business and the will of the distributors are to sell the product and not to set up a scam. The question is the following: if the real intention is to sell, why does a distributor recruit other distributors who will become his competitors? It is well known in classical industrial organization that people avoid competition as well as possible. Why is it not the case in the MLM organization? We explain this paradox by the particular economic structure of the MLM. Distributor could not sell enough if he did not recruit. Recruiting provides a price leading power and allows to sell more and make more profit (in some respect). Moreover, the MLM is similar to the multi-sided market structure a la Rochet and Tirole (2003, 2006) and Weyl (2010). There is network effect between recruitment and selling activity. Thus, the extent of the paradox can also be explained by the different commissions set by the MLM promoters.

In this Thesis, we first deploy Gittins index theory to establish the indexability of inter-alia general families of restless bandits that arise in problems of stochastic scheduling with switching penalties and machine maintenance. We also give formulae for the resulting indices. Numerical investigations testify the strong performance of the index heuristics.The second class of problems concerns two families of Markov decision problems. The spinning plates problem concerns the optimal management of a portfolio of assets whose yields grow with investment but otherwise decline. In the model of asset exploitation called the squad system, the yield from an asset declines when it is utilised but will recover when the asset is at rest. Simply stated conditions are given which guarantee general indexability of the problem together with necessary and sufficient conditions for strict indexability. The index heuristics, which emerge from the analysis, are assessed numerically and found to perform strongly.

No description available.

1 Introduction In this doctoral thesis, we address several representative problems that arise in the context of learning from multiple heterogeneous agents. These problems are relevant to many modern applications such as crowdsourcing and internet advertising. In scenarios such as crowdsourcing, there is a planner who is interested in learning a task and a set of noisy agents provide the training data for this learning task. Any learning algorithm making use of the data provided by these noisy agents must account for their noise levels. The noise levels of the agents are unknown to the planner, leading to a non-trivial difficulty. Further, the agents are heterogeneous as they differ in terms of their noise levels. A key challenge in such settings is to learn the noise levels of the agents while simultaneously learning the underlying model. Another challenge arises when the agents are strategic. For example, when the agents are required to perform a task, they could be strategic on the efforts they put in. As another example, when required to report their costs incurred towards performing the task, the agents could be strategic and may not report the costs truthfully. In general, the performance of the learning algorithms could be severely affected if the information elicited from the agents is incorrect. We address the above challenges that arise in the following representative learning problems. Multi-label Classification from Heterogeneous Noisy Agents Multi-label classification is a well-known supervised machine learning problem where each instance is associated with multiple classes. Since several labels can be assigned to a single instance, one of the key challenges in this problem is to learn the correlations between the classes. We first assume labels from a perfect source and propose a novel topic model called Multi-Label Presence-Absence Latent Dirichlet Allocation (ML-PA-LDA). In the current day scenario, a natural source for procuring the training dataset is through mining user-generated content or directly through users in a crowdsourcing platform. In the more practical scenario of crowdsourcing, an additional challenge arises as the labels of the training instances are provided by noisy, heterogeneous crowd-workers with unknown qualities. With this as the motivation, we further adapt our topic model to the scenario where the labels are provided by multiple noisy sources and refer to this model as ML-PA-LDA-MNS (ML-PA-LDA with Multiple Noisy Sources). With experiments on standard datasets, we show that the proposed models achieve superior performance over existing methods. Active Linear Regression with Heterogeneous, Noisy and Strategic Agents In this work, we study the problem of training a linear regression model by procuring labels from multiple noisy agents or crowd annotators, under a budget constraint. We propose a Bayesian model for linear regression from multiple noisy sources and use variational inference for parameter estimation. When labels are sought from agents, it is important to minimize the number of labels procured as every call to an agent incurs a cost. Towards this, we adopt an active learning approach. In this specific context, we prove the equivalence of well-studied criteria of active learning such as entropy minimization and expected error reduction. For the purpose of annotator selection in active learning, we observe a useful connection with the multi-armed bandit framework. Due to the nature of the distribution of the rewards on the arms, we resort to the Robust Upper Confidence Bound (UCB) scheme with truncated empirical mean estimator to solve the annotator selection problem. This yields provable guarantees on the regret. We apply our model to the scenario where annotators are strategic and design suitable incentives to induce them to put in their best efforts. Ranking with Heterogeneous Strategic Agents We look at the problem where a planner must rank multiple strategic agents, a problem that has many applications including sponsored search auctions (SSA). Stochastic multi-armed bandit (MAB) mechanisms have been used in the literature to solve this problem. Existing stochastic MAB mechanisms with a deterministic payment rule, proposed in the literature, necessarily suffer a regret of (T 2=3), where T is the number of time steps. This happens because these mechanisms address the worst case scenario where the means of the agents’ stochastic rewards are separated by a very small amount that depends on T . We however take a detour and allow the planner to indicate the resolution, , with which the agents must be distinguished. This immediately leads us to introduce the notion of -Regret. We propose a dominant strategy incentive compatible (DSIC) and individually rational (IR), deterministic MAB mechanism, based on ideas from the Upper Confidence Bound (UCB) family of MAB algorithms. The proposed mechanism - UCB achieves a -regret of O(log T ). We first establish the results for single slot SSA and then non-trivially extend the results to the case of multi-slot SSA.