Efficient Strategy-Proof Allocation Functions in Linear Production Economies

In a linear production model, we characterize the class of efficient and strategy-proof allocation functions, and the class of efficient and coalition strategy-proof allocation functions. In the former class, requiring equal treatment of equals allows us to identify a unique allocation function. This function is also the unique member of the latter class which satisfies uniform treatment of uniforms.

Resource-Monotonicity for House Allocation Problems

We study a simple model of assigning indivisible objects (e.g., houses, jobs, offices, etc.) to agents. Each agent receives at most one object and monetary compensations are not possible. We completely describe all rules satisfying efficiency and resource-monotonicity. The characterized rules assign the objects in a sequence of steps such that at each step there is either a dictator or two agents who “trade” objects from their hierarchically specified “endowments.”

Consistent House Allocation

In practice we often face the problem of assigning indivisible objects (e.g., schools, housing, jobs, offices) to agents (e.g., students, homeless, workers, professors) when monetary compensations are not possible. We show that a rule that satisfies consistency, strategy-proofness, and efficiency must be an efficient generalized priority rule; i.e. it must adapt to an acyclic priority structure, except -maybe- for up to three agents in each object's priority ordering.

Fair Allocation of Production Externalities: Recent Results

We survey recent axiomatic results in the theory of cost-sharing. In this litterature, a method computes the individual cost shares assigned to the users of a facility for any profile of demands and any monotonic cost function. We discuss two theories taking radically different views of the asymmetries of the cost function. In the full responsibility theory, each agent is accountable for the part of the costs that can be unambiguously separated and attributed to her own demand. In the partial responsibility theory, the asymmetries of the cost function have no bearing on individual cost shares, only the differences in demand levels matter. We describe several invariance and monotonicity properties that reflect both normative and strategic concerns. We uncover a number of logical trade-offs between our axioms, and derive axiomatic characterizations of a handful of intuitive methods: in the full responsibility approach, the Shapley-Shubik, Aumann-Shapley, and subsidyfree serial methods, and in the partial responsibility approach, the cross-subsidizing serial method and the family of quasi-proportional methods.

Pour une allocation équitable des ressources en GMF

Objectif : Évaluer la « lourdeur » de la prise en charge clinique des personnes vivant avec le VIH/SIDA (PVVIH) afin d’ajuster l’allocation des ressources en GMF. Méthodologie : Analyse comparative entre le GMF de la Clinique médicale l’Actuel, les GMF montréalais et de l’ensemble du Québec, en identifiant les différences dans les profils de consommation de soins pour les années civiles 2006 à 2008 et les coûts d’utilisation des services pour l’année 2005. Résultats : En 2008, 78% de la clientèle inscrite au GMF de la Clinique médicale l’Actuel est vulnérable comparativement à 28% pour les autres GMF montréalais, une tendance observée pour l’ensemble du Québec. Le nombre moyen de visites par individu inscrit et vulnérable est de 7,57 au GMF l’Actuel alors que la moyenne montréalaise est de 3,37 et celle du Québec de 3,47. Enfin, le coût moyen des visites médicales au GMF l’Actuel en 2005 est de 203,93 $ comparativement à des coûts variant entre 132,14 et 149,53 $ pour les unités de comparaison. Conclusion : L’intensité de l’utilisation des ressources au GMF de la Clinique médicale l’Actuel (nombre d’individus vulnérables, nombre de visites et coûts) suggère que la prise en charge clinique des personnes vivant avec le VIH/SIDA est beaucoup plus lourde qu’un citoyen tout venant ou même de la majorité des autres catégories de vulnérabilité. Afin d’offrir un traitement juste et équitable aux GMF, l’inscription devrait être ajustée afin de tenir compte de la « lourdeur » de cette clientèle et valoriser la prise en charge des personnes qui présentent des tableaux cliniques complexes.

Allocation via Deferred-Acceptance under Responsive Priorities

In many economic environments - such as college admissions, student placements at public schools, and university housing allocation - indivisible objects with capacity constraints are assigned to a set of agents when each agent receives at most one object and monetary compensations are not allowed. In these important applications the agent-proposing deferred-acceptance algorithm with responsive priorities (called responsive DA-rule) performs well and economists have successfully implemented responsive DA-rules or slight variants thereof. First, for house allocation problems we characterize the class of responsive DA-rules by a set of basic and intuitive properties, namely, unavailable type invariance, individual rationality, weak non-wastefulness, resource-monotonicity, truncation invariance, and strategy-proofness. We extend this characterization to the full class of allocation problems with capacity constraints by replacing resource- monotonicity with two-agent consistent con ict resolution. An alternative characterization of responsive DA-rules is obtained using unassigned objects invariance, individual rationality, weak non-wastefulness, weak consistency, and strategy-proofness. Various characterizations of the class of "acyclic" responsive DA-rules are obtained by using the properties efficiency, group strategy-proofness, and consistency.

Allocation optimale des ressources pour les applications et services de grille de calcul

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

House allocation via deferred-acceptance

We study the simple model of assigning indivisible and heterogenous objects (e.g., houses, jobs, offi ces, etc.) to agents. Each agent receives at most one object and monetary compensations are not possible. For this model, known as the house allocation model, we characterize the class of rules satisfying unavailable object invariance, individual rationality, weak non-wastefulness, resource-monotonicity, truncation invariance, and strategy-proofness: any rule with these properties must allocate objects based on (implicitly induced) objects' priorities over agents and the agent-proposing deferred-acceptance-algorithm.

Tactical Vehicle Routing Planning with Application to Milk Collection and Distribution

De nombreux problèmes pratiques qui se posent dans dans le domaine de la logistique, peuvent être modélisés comme des problèmes de tournées de véhicules. De façon générale, cette famille de problèmes implique la conception de routes, débutant et se terminant à un dépôt, qui sont utilisées pour distribuer des biens à un nombre de clients géographiquement dispersé dans un contexte où les coûts associés aux routes sont minimisés. Selon le type de problème, un ou plusieurs dépôts peuvent-être présents. Les problèmes de tournées de véhicules sont parmi les problèmes combinatoires les plus difficiles à résoudre. Dans cette thèse, nous étudions un problème d’optimisation combinatoire, appartenant aux classes des problèmes de tournées de véhicules, qui est liée au contexte des réseaux de transport. Nous introduisons un nouveau problème qui est principalement inspiré des activités de collecte de lait des fermes de production, et de la redistribution du produit collecté aux usines de transformation, pour la province de Québec. Deux variantes de ce problème sont considérées. La première, vise la conception d’un plan tactique de routage pour le problème de la collecte-redistribution de lait sur un horizon donné, en supposant que le niveau de la production au cours de l’horizon est fixé. La deuxième variante, vise à fournir un plan plus précis en tenant compte de la variation potentielle de niveau de production pouvant survenir au cours de l’horizon considéré. Dans la première partie de cette thèse, nous décrivons un algorithme exact pour la première variante du problème qui se caractérise par la présence de fenêtres de temps, plusieurs dépôts, et une flotte hétérogène de véhicules, et dont l’objectif est de minimiser le coût de routage. À cette fin, le problème est modélisé comme un problème multi-attributs de tournées de véhicules. L’algorithme exact est basé sur la génération de colonnes impliquant un algorithme de plus court chemin élémentaire avec contraintes de ressources. Dans la deuxième partie, nous concevons un algorithme exact pour résoudre la deuxième variante du problème. À cette fin, le problème est modélisé comme un problème de tournées de véhicules multi-périodes prenant en compte explicitement les variations potentielles du niveau de production sur un horizon donné. De nouvelles stratégies sont proposées pour résoudre le problème de plus court chemin élémentaire avec contraintes de ressources, impliquant dans ce cas une structure particulière étant donné la caractéristique multi-périodes du problème général. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. La troisième partie propose un algorithme de recherche adaptative à grands voisinages où de nombreuses nouvelles stratégies d’exploration et d’exploitation sont proposées pour améliorer la performances de l’algorithme proposé en termes de la qualité de la solution obtenue et du temps de calcul nécessaire.

On the design of customized risk measures in insurance, the problem of capital allocation and the theory of fluctuations for Lévy processes

Dans cette thèse, nous étudions quelques problèmes fondamentaux en mathématiques financières et actuarielles, ainsi que leurs applications. Cette thèse est constituée de trois contributions portant principalement sur la théorie de la mesure de risques, le problème de l’allocation du capital et la théorie des fluctuations. Dans le chapitre 2, nous construisons de nouvelles mesures de risque cohérentes et étudions l’allocation de capital dans le cadre de la théorie des risques collectifs. Pour ce faire, nous introduisons la famille des "mesures de risque entropique cumulatifs" (Cumulative Entropic Risk Measures). Le chapitre 3 étudie le problème du portefeuille optimal pour le Entropic Value at Risk dans le cas où les rendements sont modélisés par un processus de diffusion à sauts (Jump-Diffusion). Dans le chapitre 4, nous généralisons la notion de "statistiques naturelles de risque" (natural risk statistics) au cadre multivarié. Cette extension non-triviale produit des mesures de risque multivariées construites à partir des données financiéres et de données d’assurance. Le chapitre 5 introduit les concepts de "drawdown" et de la "vitesse d’épuisement" (speed of depletion) dans la théorie de la ruine. Nous étudions ces concepts pour des modeles de risque décrits par une famille de processus de Lévy spectrallement négatifs.

Object allocation via deferred-acceptance: strategy-proofness and comparative statics

We study the problem of assigning indivisible and heterogenous objects (e.g., houses, jobs, offices, school or university admissions etc.) to agents. Each agent receives at most one object and monetary compensations are not possible. We consider mechanisms satisfying a set of basic properties (unavailable-type-invariance, individual-rationality, weak non-wastefulness, or truncation-invariance). In the house allocation problem, where at most one copy of each object is available, deferred-acceptance (DA)-mechanisms allocate objects based on exogenously fixed objects' priorities over agents and the agent-proposing deferred-acceptance-algorithm. For house allocation we show that DA-mechanisms are characterized by our basic properties and (i) strategy-proofness and population-monotonicity or (ii) strategy-proofness and resource-monotonicity. Once we allow for multiple identical copies of objects, on the one hand the first characterization breaks down and there are unstable mechanisms satisfying our basic properties and (i) strategy-proofness and population-monotonicity. On the other hand, our basic properties and (ii) strategy-proofness and resource-monotonicity characterize (the most general) class of DA-mechanisms based on objects' fixed choice functions that are acceptant, monotonic, substitutable, and consistent. These choice functions are used by objects to reject agents in the agent-proposing deferred-acceptance-algorithm. Therefore, in the general model resource-monotonicity is the «stronger» comparative statics requirement because it characterizes (together with our basic requirements and strategy-proofness) choice-based DA-mechanisms whereas population-monotonicity (together with our basic properties and strategy-proofness) does not.

Variabilité individuelle de l'allocation fonctionnelle des régions cérébrales perceptives dans l'autisme

Introduction : Une augmentation de la plasticité cérébrale est susceptible d’être impliquée dans la réallocation des régions corticales et dans les nombreuses altérations microstructurelles observées en autisme. Considérant les nombreux résultats démontrant un surfonctionnement perceptif et un fonctionnement moteur atypique en autisme, l’augmentation de la plasticité cérébrale suggère une plus grande variabilité individuelle de l’allocation fonctionnelle chez cette population, plus spécifiquement dans les régions perceptives et motrices. Méthode : Afin de tester cette hypothèse, 23 participants autistes de haut-niveau et 22 non-autistes appariés pour l’âge, le quotient intellectuel, les résultats au test des Matrices de Raven et la latéralité, ont réalisé une tâche d’imitation visuo-motrice dans un appareil d’imagerie par résonnance magnétique fonctionnelle (IRMf). Pour chaque participant, les coordonnées du pic d’activation le plus élevé ont été extraites des aires motrices primaires (Aire de Brodmann 4 (BA4)) et supplémentaires (BA6), du cortex visuo-moteur pariétal supérieur (BA7) ainsi que des aires visuelles primaires (BA17) et associatives (BA18+19) des deux hémisphères. L’étendue des activations, mesurée en fonction du nombre de voxels activés, et la différence d’intensité des activations, calculée en fonction du changement moyen d’intensité du signal ont également été considérées. Pour chaque région d’intérêt et hémisphère, la distance entre la localisation de l’activation maximale de chaque participant par rapport à celle de la moyenne de son groupe a servi de variable d’intérêt. Les moyennes de ces distances individuelles obtenues pour chaque groupe et chacune des régions d’intérêt ont ensuite été soumises à une ANOVA à mesures répétées afin de déterminer s’il existait des différences de variabilité dans la localisation des activations entre les groupes. Enfin, l’activation fonctionnelle générale à l’intérieur de chaque groupe et entre les groupes a également été étudiée. Résultats : Les résultats démontrent qu’une augmentation de la variabilité individuelle en terme de localisation des activations s’est produite à l’intérieur des deux groupes dans les aires associatives motrices et visuelles comparativement aux aires primaires associées. Néanmoins, malgré le fait que cette augmentation de variabilité dans les aires associatives soit partagée, une comparaison directe de celle-ci entre les groupes a démontré que les autistes présentaient une plus grande variabilité de la localisation des activations fonctionnelles dans le cortex visuo-moteur pariétal supérieur (BA7) et les aires associatives visuelles (BA18+19) de l’hémisphère gauche. Conclusion : Des stratégies différentes et possiblement uniques pour chaque individu semblent être observées en autisme. L’augmentation de la variabilité individuelle de la localisation des activations fonctionnelles retrouvée chez les autistes dans les aires associatives, où l’on observe également davantage de variabilité chez les non-autistes, suggère qu’une augmentation et/ou une altération des mécanismes de plasticité est impliquée dans l’autisme.

The berth allocation problem at port terminals : a column generation framework

Le problème d'allocation de postes d'amarrage (PAPA) est l'un des principaux problèmes de décision aux terminaux portuaires qui a été largement étudié. Dans des recherches antérieures, le PAPA a été reformulé comme étant un problème de partitionnement généralisé (PPG) et résolu en utilisant un solveur standard. Les affectations (colonnes) ont été générées a priori de manière statique et fournies comme entrée au modèle %d'optimisation. Cette méthode est capable de fournir une solution optimale au problème pour des instances de tailles moyennes. Cependant, son inconvénient principal est l'explosion du nombre d'affectations avec l'augmentation de la taille du problème, qui fait en sorte que le solveur d'optimisation se trouve à court de mémoire. Dans ce mémoire, nous nous intéressons aux limites de la reformulation PPG. Nous présentons un cadre de génération de colonnes où les affectations sont générées de manière dynamique pour résoudre les grandes instances du PAPA. Nous proposons un algorithme de génération de colonnes qui peut être facilement adapté pour résoudre toutes les variantes du PAPA en se basant sur différents attributs spatiaux et temporels. Nous avons testé notre méthode sur un modèle d'allocation dans lequel les postes d'amarrage sont considérés discrets, l'arrivée des navires est dynamique et finalement les temps de manutention dépendent des postes d'amarrage où les bateaux vont être amarrés. Les résultats expérimentaux des tests sur un ensemble d'instances artificielles indiquent que la méthode proposée permet de fournir une solution optimale ou proche de l'optimalité même pour des problème de très grandes tailles en seulement quelques minutes.