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.

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.

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.

Strategy-proofness makes the difference: deferred-acceptance with responsive priorities

In college admissions and student placements at public schools, the admission decision can be thought of as assigning indivisible objects with capacity constraints to a set of students such that each student receives at most one object and monetary compensations are not allowed. In these important market design problems, the agent-proposing deferred-acceptance (DA-)mechanism with responsive strict priorities performs well and economists have successfully implemented DA-mechanisms or slight variants thereof. We show that almost all real-life mechanisms used in such environments - including the large classes of priority mechanisms and linear programming mechanisms - satisfy a set of simple and intuitive properties. Once we add strategy-proofness to these properties, DA-mechanisms are the only ones surviving. In market design problems that are based on weak priorities (like school choice), generally multiple tie-breaking (MTB)procedures are used and then a mechanism is implemented with the obtained strict priorities. By adding stability with respect to the weak priorities, we establish the first normative foundation for MTB-DA-mechanisms that are used in NYC.

Pareto Dominance of Deferred Acceptance through Early Decision

An early decision market is governed by rules that allow each student to apply to (at most) one college and require the student to attend this college if admitted. This market is ubiquitous in college admissions in the United States. We model this market as an extensive-form game of perfect information and study a refinement of subgame perfect equilibrium (SPE) that induces undominated Nash equilibria in every subgame (SPUE). Our main result shows that this game can be used to define a decentralized matching mechanism that weakly Pareto dominates student-proposing deferred acceptance.

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.

School Choice with Control

Controlled choice over public schools is a common policy of school boards in the United States. It attempts giving choice to parents while maintaining racial and ethnic balance at schools. This paper provides a foundation for controlled school choice programs. We develop a natural notion of fairness and show that assignments, which are fair for same type students and constrained non-wasteful, always exist in controlled choice problems; a "controlled" version of the student proposing deferred acceptance algorithm (CDAA) always finds such an assignment which is also weakly Pareto-optimal. CDAA provides a practical solution for controlled school choice programs.

Strategy-proof tie-breaking

We study a general class of priority-based allocation problems with weak priority orders and identify conditions under which there exists a strategy-proof mechanism which always chooses an agent-optimal stable, or constrained efficient, matching. A priority structure for which these two requirements are compatible is called solvable. For the general class of priority-based allocation problems with weak priority orders,we introduce three simple necessary conditions on the priority structure. We show that these conditions completely characterize solvable environments within the class of indifferences at the bottom (IB) environments, where ties occur only at the bottom of the priority structure. This generalizes and unifies previously known results on solvable and unsolvable environments established in school choice, housing markets and house allocation with existing tenants. We show how the previously known solvable cases can be viewed as extreme cases of solvable environments. For sufficiency of our conditions we introduce a version of the agent-proposing deferred acceptance algorithm with exogenous and preference-based tie-breaking.

«School choice with controlled choice constraints: hard bounds versus soft bounds»

Controlled choice over public schools attempts giving options to parents while maintaining diversity, often enforced by setting feasibility constraints with hard upper and lower bounds for each student type. We demonstrate that there might not exist assignments that satisfy standard fairness and non-wastefulness properties; whereas constrained non-wasteful assignments which are fair for same type students always exist. We introduce a "controlled" version of the deferred acceptance algorithm with an improvement stage (CDAAI) that finds a Pareto optimal assignment among such assignments. To achieve fair (across all types) and non-wasteful assignments, we propose the control constraints to be interpreted as soft bounds-flexible limits that regulate school priorities. In this setting, a modified version of the deferred acceptance algorithm (DAASB) finds an assignment that is Pareto optimal among fair assignments while eliciting true preferences. CDAAI and DAASB provide two alternative practical solutions depending on the interpretation of the control constraints. JEL C78, D61, D78, I20.

Segmentation d’images intravasculaires ultrasonores

L'imagerie intravasculaire ultrasonore (IVUS) est une technologie médicale par cathéter qui produit des images de coupe des vaisseaux sanguins. Elle permet de quantifier et d'étudier la morphologie de plaques d'athérosclérose en plus de visualiser la structure des vaisseaux sanguins (lumière, intima, plaque, média et adventice) en trois dimensions. Depuis quelques années, cette méthode d'imagerie est devenue un outil de choix en recherche aussi bien qu'en clinique pour l'étude de la maladie athérosclérotique. L'imagerie IVUS est par contre affectée par des artéfacts associés aux caractéristiques des capteurs ultrasonores, par la présence de cônes d'ombre causés par les calcifications ou des artères collatérales, par des plaques dont le rendu est hétérogène ou par le chatoiement ultrasonore (speckle) sanguin. L'analyse automatisée de séquences IVUS de grande taille représente donc un défi important. Une méthode de segmentation en trois dimensions (3D) basée sur l'algorithme du fast-marching à interfaces multiples est présentée. La segmentation utilise des attributs des régions et contours des images IVUS. En effet, une nouvelle fonction de vitesse de propagation des interfaces combinant les fonctions de densité de probabilité des tons de gris des composants de la paroi vasculaire et le gradient des intensités est proposée. La segmentation est grandement automatisée puisque la lumière du vaisseau est détectée de façon entièrement automatique. Dans une procédure d'initialisation originale, un minimum d'interactions est nécessaire lorsque les contours initiaux de la paroi externe du vaisseau calculés automatiquement sont proposés à l'utilisateur pour acceptation ou correction sur un nombre limité d'images de coupe longitudinale. La segmentation a été validée à l'aide de séquences IVUS in vivo provenant d'artères fémorales provenant de différents sous-groupes d'acquisitions, c'est-à-dire pré-angioplastie par ballon, post-intervention et à un examen de contrôle 1 an suivant l'intervention. Les résultats ont été comparés avec des contours étalons tracés manuellement par différents experts en analyse d'images IVUS. Les contours de la lumière et de la paroi externe du vaisseau détectés selon la méthode du fast-marching sont en accord avec les tracés manuels des experts puisque les mesures d'aire sont similaires et les différences point-à-point entre les contours sont faibles. De plus, la segmentation par fast-marching 3D s'est effectuée en un temps grandement réduit comparativement à l'analyse manuelle. Il s'agit de la première étude rapportée dans la littérature qui évalue la performance de la segmentation sur différents types d'acquisition IVUS. En conclusion, la segmentation par fast-marching combinant les informations des distributions de tons de gris et du gradient des intensités des images est précise et efficace pour l'analyse de séquences IVUS de grandes tailles. Un outil de segmentation robuste pourrait devenir largement répandu pour la tâche ardue et fastidieuse qu'est l'analyse de ce type d'images.

BA'S : The practice and law of bankers' acceptance

Au cours d'une transaction portant sur une acceptation bancaire (ci-après «BA» tel que dénommée dans le jargon juridique) différents types de relations peuvent s'établir entre les parties impliquées, certaines plus directes que d'autres. Dans une transaction donnée, à part le client et la banque, on peut trouver une ou plusieurs banques participantes et un ou plusieurs investisseurs, qui deviennent détenteurs de BA. La situation peut devenir complexe et les relations légales risquent de devenir assez compliquées. Cependant, il est important d'identifier si la relation s'est établie à travers l'instrument de BA, si elle existe par le biais d'une relation contractuelle ordinaire ou encore, si elle existe par le fait de la loi. Une bonne analyse des circonstances entourant la transaction, des facteurs connexes à la transaction et des droits et obligations qui existent entre les parties, sera nécessaire pour déterminer laquelle de la loi provinciale ou fédérale s'appliquera, et dans quelle mesure. Une fois accordée, la BA est gouvernée par la Loi sur les lettres de change. Toutes solutions apportées à un problème qui implique des BA, doivent, en principe, respecter la nature inhérente de la BA en tant qu'effet de commerce, gouverné par la loi fédérale. En matière de BA, c'est, soit la Loi sur les lettres de change soit la Loi sur les lettres et billets de dépôt (Depository Bills and Note Act) qui s'appliqueront à l'acte. Comme il existe des lois fédérales applicables à la BA, l'objet de notre étude est de déterminer si, et dans quelle circonstance la loi de la province, tel que le Code civil du Québec, trouvera application et éclaircira dans certains cas la disposition contenue dans la Loi sur les lettres de change, notamment lorsque les dispositions de ladite loi sont silencieuses ou ambigües. La solution la plus simple serait d'appliquer la loi provinciale aux matières qui ne sont pas traitées dans la loi, étant donné que les lois provinciales apportent souvent un complément à la législation fédérale. Cependant, la Loi sur les lettres de change contient des dispositions spéciales, tel que l'article 9 qui stipule : « 9. Les règles de la common law d'Angleterre, y compris en droit commercial, s'appliquent aux lettres, billets et chèques dans la mesure de leur compatibilité avec les dispositions expresses de la présente loi. » Cette disposition a crée une certaine confusion relativement à l'application du droit civil du Québec en matière de Lettres de change. En effet, il existe un doute quant à savoir si l'application de l'article 9 est une incorporation par référence qui exclue totalement l'application du droit civil. Cette question continue de se poser inexorablement dans la doctrine et la jurisprudence. Elle a en effet donné lieu à une série de théories quand au degré d'application de la common law en matière de lettres de change. Une revue de la jurisprudence dominante nous permet de conclure que les tribunaux ont accepté l'application du droit provinciale dans certaines questions impliquant les lettres de change. La question essentielle traitée lors de notre analyse est la suivante: lorsqu'un litige prend naissance dans une transaction de BA, quelle est la règle qui devra s'appliquer? Quel sera le droit qui gouvernera les problèmes émergeant dans une BA, celui du Code Civil du Québec ou celui de la common law d'Angleterre? Étant donne le nombre de cas qui sont portés devant les cours de justice en rapport avec des transactions de BA, comprendre quelle sera la loi applicable est d'une importance fondamentale. Pour répondre à cette question, nous commencerons par un examen de l'historique, du développement et de l'évolution de la BA. Afin de mieux comprendre la BA, nous débuterons par un bref survol des origines de cet instrument juridique. Dans le deuxième chapitre, nous analyserons la nature et le caractère légal de la BA. Cela constituera le cadre aux travers duquel nous pourrons identifier les règles et les principes qui s'appliquent aux différents aspects de la transaction de BA. Le chapitre trois fera l'objet d'un examen détaillé des mécanismes de l'opération de BA tout en étudiant de près les exigences imposées par la législation applicable. Après avoir examine l'aspect légal de la BA, nous procéderons au chapitre quatre, à l'étude de l'applicabilité de la loi provinciale relativement à certains aspects de la transaction de BA. A cet effet, nous examinerons les différentes approches de compréhension de la Loi sur les lettres de change et plus particulièrement la problématique rencontrée à l'article 9. Nous étudierons aussi l'application et l'interprétation de cette loi par les tribunaux du Québec au cours du siècle dernier. Les juges et les juristes se sont penchés sur les sens qu'a voulu donner le législateur lorsqu'il a stipulé dans l'article 9 «Le règles de la common law d'Angleterre, y compris en droit commercial, s appliquent aux lettres, billets et chèques dans la mesure de leur compatibilité avec les dispositions expresses de la présente loi ». Cette section doit-elle être appliquée à la lettre, nous obligeant à appliquer la common law d'Angleterre a chaque problème qui peut se poser en relation avec les lettres et les billets? Le Parlement a-t-il l'intention que cette disposition s'applique également au Québec, dont le droit privé est basé sur le système du Code Civil? Notre étude portera sur les différentes approches d'interprétation qui offrent une diversité de solutions au problème posé par l'article 9. Finalement, compte tenu des nouveaux développements législatifs, au chapitre cinq, nous proposons une méthode en vue de déterminer la loi applicable aux différents aspects de la transaction de BA. Notre analyse nous a conduit à adopter la solution proposée par la majorité des juristes, à la différence que notre approche de l'article 9 est basée sur des raisons de politique. Nous avons donc adopté la stricte dichotomie (en tant qu'effet négociable d'une part, et d'une sorte de contrat et de propriété de l'autre) en prenant en compte les difficultés inhérentes à déterminer quand l'un finit et l'autre commence. En conclusion, selon notre opinion, il existe deux solutions. Premièrement, il y a la possibilité que l'article 9 puisse être écarté. Dans ce cas, toutes les matières qui ne sont pas expressément évoquées dans la loi tomberont dans la compétence de la loi provinciale, comme c'est le cas dans d'autres types de législations fédérales. Dans ces situations, le droit civil du Québec joue un rôle supplétif dans les applications d'une loi fédérale au Québec. Deuxièmement, modifier l'article 9 plutôt que d'en écarter son application offre une autre possibilité. Incorporer la large stricte dichotomie dans l'article 9 nous semble être une solution préférable. La disposition pourrait se lire comme suit: « Les règles de la common law d'Angleterre incluant le droit commercial dans la mesure ou elles ne sont pas incompatibles avec les dispositions expresses de la Loi, s’appliquent aux lettres, billets, et chèques au sens stricte. Pour plus de certitude, les lettres et les billets au sens strict, incluent la forme, la délivrance et I’émission des lettres, billets, et chèques.» Ce type de changement se révélera être un pas important dans le but de clarifier la loi et déterminer l'équilibre à trouver entre l'application des lois fédérales et provinciales en matière de BA.

An algorithm for identifying agent-k-linked allocations in economies with indivisibilities

We consider envy-free (and budget-balanced) rules that are least manipulable with respect to agents counting or with respect to utility gains. Recently it has been shown that for any profile of quasi-linear preferences, the outcome of any such least manipulable envy-free rule can be obtained via agent-k-linked allocations. This note provides an algorithm for identifying agent-k-linked allocations.

Recyclage des candidats dans l'algorithme Metropolis à essais multiples

Les méthodes de Monte Carlo par chaînes de Markov (MCCM) sont des méthodes servant à échantillonner à partir de distributions de probabilité. Ces techniques se basent sur le parcours de chaînes de Markov ayant pour lois stationnaires les distributions à échantillonner. Étant donné leur facilité d’application, elles constituent une des approches les plus utilisées dans la communauté statistique, et tout particulièrement en analyse bayésienne. Ce sont des outils très populaires pour l’échantillonnage de lois de probabilité complexes et/ou en grandes dimensions. Depuis l’apparition de la première méthode MCCM en 1953 (la méthode de Metropolis, voir [10]), l’intérêt pour ces méthodes, ainsi que l’éventail d’algorithmes disponibles ne cessent de s’accroître d’une année à l’autre. Bien que l’algorithme Metropolis-Hastings (voir [8]) puisse être considéré comme l’un des algorithmes de Monte Carlo par chaînes de Markov les plus généraux, il est aussi l’un des plus simples à comprendre et à expliquer, ce qui en fait un algorithme idéal pour débuter. Il a été sujet de développement par plusieurs chercheurs. L’algorithme Metropolis à essais multiples (MTM), introduit dans la littérature statistique par [9], est considéré comme un développement intéressant dans ce domaine, mais malheureusement son implémentation est très coûteuse (en termes de temps). Récemment, un nouvel algorithme a été développé par [1]. Il s’agit de l’algorithme Metropolis à essais multiples revisité (MTM revisité), qui définit la méthode MTM standard mentionnée précédemment dans le cadre de l’algorithme Metropolis-Hastings sur un espace étendu. L’objectif de ce travail est, en premier lieu, de présenter les méthodes MCCM, et par la suite d’étudier et d’analyser les algorithmes Metropolis-Hastings ainsi que le MTM standard afin de permettre aux lecteurs une meilleure compréhension de l’implémentation de ces méthodes. Un deuxième objectif est d’étudier les perspectives ainsi que les inconvénients de l’algorithme MTM revisité afin de voir s’il répond aux attentes de la communauté statistique. Enfin, nous tentons de combattre le problème de sédentarité de l’algorithme MTM revisité, ce qui donne lieu à un tout nouvel algorithme. Ce nouvel algorithme performe bien lorsque le nombre de candidats générés à chaque itérations est petit, mais sa performance se dégrade à mesure que ce nombre de candidats croît.

Le diagnostic des tuméfactions latérales solides cervicales chez l'enfant

Introduction : Faute de tests diagnostiques précis, une étude histologique est souvent nécessaire pour diagnostiquer les tuméfactions latérales solides cervicales (TLSC) chez l’enfant. Nous étudierons les modalités diagnostiques pour les TLSC afin de créer une approche diagnostique standardisée intégrant de nouveaux outils diagnostics à ceux actuellement offerts. Méthodologie : Après révision des étiologies et des modalités diagnostiques, une revue de la littérature a été effectuée. Une étude rétrospective entre 2002 à 2012 est présentée suivie d’une étude de faisabilité de la cytoponction. Puis, un arbre décisionnel est créé basé sur nos résultats et sur l’avis d’un groupe d’experts de différentes disciplines médicales. Résultats : Le diagnostic différentiel des TLSC est varié, la littérature scientifique est désuète et la comparaison reste difficile. Pour nos 42 enfants avec un âge médian de sept ans, les tuméfactions inflammatoires représentent 59% (26/44 biopsies) des TLSC, surtout des lymphadénites à mycobactérie atypique (13/26) qui ont un dépistage ardu et multimodal. La biopsie fut peu contributive à la prise en charge dans 39% (17/44) des cas. La cytoponction sous échoguidance est une technique diagnostique faisable et moins invasive que la biopsie. L’arbre décisionnel offre aux cliniciens une approche diagnostique standardisée des TLSC appuyée sur des faits scientifiques que nous souhaitons valider par une étude prospective. Conclusion : Les TLSC chez l’enfant représentent un défi diagnostic et notre arbre décisionnel répond au manque de standardisation dans l’approche diagnostique. Une étude prospective sur notre arbre décisionnel est en voie d’acceptation au CHU Sainte-Justine.