On Fixed-Path Rationing Methods.

Moulin (1999) characterizes the fixed-path rationing methods by efficiency, strategy-proofness, consistency, and resource-monotonicity. In this note, we give a straightforward proof of his result.

Efficient Priority Rules

We study the assignment of indivisible objects with quotas (houses, jobs, or offices) to a set of agents (students, job applicants, or professors). Each agent receives at most one object and monetary compensations are not possible. We characterize efficient priority rules by efficiency, strategy-proofness, and reallocation-consistency. Such a rule respects an acyclical priority structure and the allocations can be determined using the deferred acceptance algorithm.

Respecting Priorities when Assigning Students to Schools

We consider the problem of assigning students to schools on the basis of priorities. Students are allowed to have equal priority at a school. We characterize the efficient rules which weakly/strongly respect students’ priorities. When priority orderings are not strict, it is not possible to simply break ties in a fixed manner. All possibilities of resolving the indifferences need to be considered. Neither the deferred acceptance algorithm nor the top trading cycle algorithm successfully solve the problem of efficiently assigning the students to schools whereas a modified version of the deferred acceptance algorithm might. In this version tie breaking depends on students’ preferences.

From Smeed's Single-Damage Fixed-Form Three-Variable Model to Multinational and Multiprovincial Drag-Type Formulations: Does the Mystery of 1972-1973 Disapear ?

Rapport de recherche

Priorities in the Location of Multiple Public Facilities

A collective decision problem is described by a set of agents, a profile of single-peaked preferences over the real line and a number k of public facilities to be located. We consider public facilities that do not su¤er from congestion and are non-excludable. We provide a characterization of the class of rules satisfying Pareto-efficiency, object-population monotonicity and sovereignty. Each rule in the class is a priority rule that selects locations according to a predetermined priority ordering among interest groups. We characterize each of the subclasses of priority rules that respectively satisfy anonymity, hiding-proofness and strategy-proofness. In particular, we prove that a priority rule is strategy-proof if and only if it partitions the set of agents into a fixed hierarchy. Alternatively, any such rule can be viewed as a collection of fixed-populations generalized peak-selection median rules (Moulin, 1980), that are linked across populations, in a way that we describe.

Top trading with fixed tie-breaking in markets with indivisible goods

We study markets with indivisible goods where monetary compensations are not possible. Each individual is endowed with an object and a preference relation over all objects. When preferences are strict, Gale's top trading cycle algorithm finds the unique core allocation. When preferences are not necessarily strict, we use an exogenous profile of tie-breakers to resolve any ties in individuals' preferences and apply Gale's top trading cycle algorithm for the resulting profile of strict preferences. We provide a foundation of these simple extensions of Gale's top trading cycle algorithm from strict preferences to weak preferences. We show that Gale's top trading cycle algorithm with fixed tie-breaking is characterized by individual rationality, strategy-proofness, weak efficiency, non-bossiness, and consistency. Our result supports the common practice in applications to break ties in weak preferences using some fixed exogenous criteria and then to use a 'good and simple' rule for the resulting strict preferences. This reinforces the market-based approach even in the presence of indifferences because always competitive allocations are chosen.

Solution Methods for Service Network Design with Resource Management Consideration

La gestion des ressources, équipements, équipes de travail, et autres, devrait être prise en compte lors de la conception de tout plan réalisable pour le problème de conception de réseaux de services. Cependant, les travaux de recherche portant sur la gestion des ressources et la conception de réseaux de services restent limités. La présente thèse a pour objectif de combler cette lacune en faisant l’examen de problèmes de conception de réseaux de services prenant en compte la gestion des ressources. Pour ce faire, cette thèse se décline en trois études portant sur la conception de réseaux. La première étude considère le problème de capacitated multi-commodity fixed cost network design with design-balance constraints(DBCMND). La structure multi-produits avec capacité sur les arcs du DBCMND, de même que ses contraintes design-balance, font qu’il apparaît comme sous-problème dans de nombreux problèmes reliés à la conception de réseaux de services, d’où l’intérêt d’étudier le DBCMND dans le contexte de cette thèse. Nous proposons une nouvelle approche pour résoudre ce problème combinant la recherche tabou, la recomposition de chemin, et une procédure d’intensification de la recherche dans une région particulière de l’espace de solutions. Dans un premier temps la recherche tabou identifie de bonnes solutions réalisables. Ensuite la recomposition de chemin est utilisée pour augmenter le nombre de solutions réalisables. Les solutions trouvées par ces deux méta-heuristiques permettent d’identifier un sous-ensemble d’arcs qui ont de bonnes chances d’avoir un statut ouvert ou fermé dans une solution optimale. Le statut de ces arcs est alors fixé selon la valeur qui prédomine dans les solutions trouvées préalablement. Enfin, nous utilisons la puissance d’un solveur de programmation mixte en nombres entiers pour intensifier la recherche sur le problème restreint par le statut fixé ouvert/fermé de certains arcs. Les tests montrent que cette approche est capable de trouver de bonnes solutions aux problèmes de grandes tailles dans des temps raisonnables. Cette recherche est publiée dans la revue scientifique Journal of heuristics. La deuxième étude introduit la gestion des ressources au niveau de la conception de réseaux de services en prenant en compte explicitement le nombre fini de véhicules utilisés à chaque terminal pour le transport de produits. Une approche de solution faisant appel au slope-scaling, la génération de colonnes et des heuristiques basées sur une formulation en cycles est ainsi proposée. La génération de colonnes résout une relaxation linéaire du problème de conception de réseaux, générant des colonnes qui sont ensuite utilisées par le slope-scaling. Le slope-scaling résout une approximation linéaire du problème de conception de réseaux, d’où l’utilisation d’une heuristique pour convertir les solutions obtenues par le slope-scaling en solutions réalisables pour le problème original. L’algorithme se termine avec une procédure de perturbation qui améliore les solutions réalisables. Les tests montrent que l’algorithme proposé est capable de trouver de bonnes solutions au problème de conception de réseaux de services avec un nombre fixe des ressources à chaque terminal. Les résultats de cette recherche seront publiés dans la revue scientifique Transportation Science. La troisième étude élargie nos considérations sur la gestion des ressources en prenant en compte l’achat ou la location de nouvelles ressources de même que le repositionnement de ressources existantes. Nous faisons les hypothèses suivantes: une unité de ressource est nécessaire pour faire fonctionner un service, chaque ressource doit retourner à son terminal d’origine, il existe un nombre fixe de ressources à chaque terminal, et la longueur du circuit des ressources est limitée. Nous considérons les alternatives suivantes dans la gestion des ressources: 1) repositionnement de ressources entre les terminaux pour tenir compte des changements de la demande, 2) achat et/ou location de nouvelles ressources et leur distribution à différents terminaux, 3) externalisation de certains services. Nous présentons une formulation intégrée combinant les décisions reliées à la gestion des ressources avec les décisions reliées à la conception des réseaux de services. Nous présentons également une méthode de résolution matheuristique combinant le slope-scaling et la génération de colonnes. Nous discutons des performances de cette méthode de résolution, et nous faisons une analyse de l’impact de différentes décisions de gestion des ressources dans le contexte de la conception de réseaux de services. Cette étude sera présentée au XII International Symposium On Locational Decision, en conjonction avec XXI Meeting of EURO Working Group on Locational Analysis, Naples/Capri (Italy), 2014. En résumé, trois études différentes sont considérées dans la présente thèse. La première porte sur une nouvelle méthode de solution pour le "capacitated multi-commodity fixed cost network design with design-balance constraints". Nous y proposons une matheuristique comprenant la recherche tabou, la recomposition de chemin, et l’optimisation exacte. Dans la deuxième étude, nous présentons un nouveau modèle de conception de réseaux de services prenant en compte un nombre fini de ressources à chaque terminal. Nous y proposons une matheuristique avancée basée sur la formulation en cycles comprenant le slope-scaling, la génération de colonnes, des heuristiques et l’optimisation exacte. Enfin, nous étudions l’allocation des ressources dans la conception de réseaux de services en introduisant des formulations qui modèlent le repositionnement, l’acquisition et la location de ressources, et l’externalisation de certains services. À cet égard, un cadre de solution slope-scaling développé à partir d’une formulation en cycles est proposé. Ce dernier comporte la génération de colonnes et une heuristique. Les méthodes proposées dans ces trois études ont montré leur capacité à trouver de bonnes solutions.

Managing Profound Suffering at the End-of-Life: Should expanding access to continuous deep sedation be the priority?

Commentaire / Commentary

Fixed point results for multivalued contractions on graphs and their applications

Nous présentons dans cette thèse des théorèmes de point fixe pour des contractions multivoques définies sur des espaces métriques, et, sur des espaces de jauges munis d’un graphe. Nous illustrons également les applications de ces résultats à des inclusions intégrales et à la théorie des fractales. Cette thèse est composée de quatre articles qui sont présentés dans quatre chapitres. Dans le chapitre 1, nous établissons des résultats de point fixe pour des fonctions multivoques, appelées G-contractions faibles. Celles-ci envoient des points connexes dans des points connexes et contractent la longueur des chemins. Les ensembles de points fixes sont étudiés. La propriété d’invariance homotopique d’existence d’un point fixe est également établie pour une famille de Gcontractions multivoques faibles. Dans le chapitre 2, nous établissons l’existence de solutions pour des systèmes d’inclusions intégrales de Hammerstein sous des conditions de type de monotonie mixte. L’existence de solutions pour des systèmes d’inclusions différentielles avec conditions initiales ou conditions aux limites périodiques est également obtenue. Nos résultats s’appuient sur nos théorèmes de point fixe pour des G-contractions multivoques faibles établis au chapitre 1. Dans le chapitre 3, nous appliquons ces mêmes résultats de point fixe aux systèmes de fonctions itérées assujettis à un graphe orienté. Plus précisément, nous construisons un espace métrique muni d’un graphe G et une G-contraction appropriés. En utilisant les points fixes de cette G-contraction, nous obtenons plus d’information sur les attracteurs de ces systèmes de fonctions itérées. Dans le chapitre 4, nous considérons des contractions multivoques définies sur un espace de jauges muni d’un graphe. Nous prouvons un résultat de point fixe pour des fonctions multivoques qui envoient des points connexes dans des points connexes et qui satisfont une condition de contraction généralisée. Ensuite, nous étudions des systèmes infinis de fonctions itérées assujettis à un graphe orienté (H-IIFS). Nous donnons des conditions assurant l’existence d’un attracteur unique à un H-IIFS. Enfin, nous appliquons notre résultat de point fixe pour des contractions multivoques définies sur un espace de jauges muni d’un graphe pour obtenir plus d’information sur l’attracteur d’un H-IIFS. Plus précisément, nous construisons un espace de jauges muni d’un graphe G et une G-contraction appropriés tels que ses points fixes sont des sous-attracteurs du H-IIFS.