Matching Markets under (In)complete Information

We are the first to introduce incomplete information to centralized many-to-one matching markets such as those to entry-level labor markets or college admissions. This is important because in real life markets (i) any agent is uncertain about the other agents' true preferences and (ii) most entry-level matching is many-to-one (and not one-to-one). We show that for stable (matching) mechanisms there is a strong and surprising link between Nash equilibria under complete information and Bayesian Nash equilibria under incomplete information. That is,given a common belief, a strategy profile is a Bayesian Nash equilibrium under incomplete information in a stable mechanism if and only if, for any true profile in the support of the common belief, the submitted profile is a Nash equilibrium under complete information at the true profile in the direct preference revelation game induced by the stable mechanism. This result may help to explain the success of stable mechanisms in these markets.

Von Neumann-Morgenstern Stable Sets in Matching Problems

The following properties of the core of a one well-known: (i) the core is non-empty; (ii) the core is a lattice; and (iii) the set of unmatched agents is identical for any two matchings belonging to the core. The literature on two-sided matching focuses almost exclusively on the core and studies extensively its properties. Our main result is the following characterization of (von Neumann-Morgenstern) stable sets in one-to-one matching problem only if it is a maximal set satisfying the following properties : (a) the core is a subset of the set; (b) the set is a lattice; (c) the set of unmatched agents is identical for any two matchings belonging to the set. Furthermore, a set is a stable set if it is the unique maximal set satisfying properties (a), (b) and (c). We also show that our main result does not extend from one-to-one matching problems to many-to-one matching problems.

Assigning Refugees to Landlords in Sweden: Stable Maximum Matchings

The member states of the European Union received 1.2 million first time asylum applications in 2015 (a doubling compared to 2014). Even if asylum will be granted for many of the refugees that made the journey to Europe, several obstacles for successful integration remain. This paper focuses on one of these obstacles, namely the problem of finding housing for refugees once they have been granted asylum. In particular, the focus is restricted to the situation in Sweden during 2015–2016 and it is demonstrated that market design can play an important role in a partial solution to the problem. More specifically, because almost all accommodation options are exhausted in Sweden, the paper investigates a matching system, closely related to the system adopted by the European NGO “Refugees Welcome”, and proposes an easy-to-implement algorithm that finds a stable maximum matching. Such matching guarantees that housing is provided to a maximum number of refugees and that no refugee prefers some landlord to their current match when, at the same time, that specific landlord prefers that refugee to his current match.

Exact Multivariate Tests of Asset Pricing Models with Stable Asymmetric Distributions

In this paper, we propose exact inference procedures for asset pricing models that can be formulated in the framework of a multivariate linear regression (CAPM), allowing for stable error distributions. The normality assumption on the distribution of stock returns is usually rejected in empirical studies, due to excess kurtosis and asymmetry. To model such data, we propose a comprehensive statistical approach which allows for alternative - possibly asymmetric - heavy tailed distributions without the use of large-sample approximations. The methods suggested are based on Monte Carlo test techniques. Goodness-of-fit tests are formally incorporated to ensure that the error distributions considered are empirically sustainable, from which exact confidence sets for the unknown tail area and asymmetry parameters of the stable error distribution are derived. Tests for the efficiency of the market portfolio (zero intercepts) which explicitly allow for the presence of (unknown) nuisance parameter in the stable error distribution are derived. The methods proposed are applied to monthly returns on 12 portfolios of the New York Stock Exchange over the period 1926-1995 (5 year subperiods). We find that stable possibly skewed distributions provide statistically significant improvement in goodness-of-fit and lead to fewer rejections of the efficiency hypothesis.

Manipulation via Capacities Revisited

This paper revisits manipulation via capacities in centralized two-sided matching markets. Sönmez (1997) showed that no stable mechanism is nonmanipulable via capacities. We show that non-manipulability via capacities can be equivalently described by two types of non-manipulation via capacities: non-Type-I-manipulability meaning that no college with vacant positions can manipulate by dropping some of its empty positions; and non-Type-II-manipulability meaning that no college with no vacant positions can manipulate by dropping some of its filled positions. Our main result shows that the student-optimal stable mechanism is the unique stable mechanism which is non-Type-I-manipulable via capacities and independent of truncations. Our characterization supports the use of the student-optimal stable mechanism in these matching markets because of its limited manipulability via capacities by colleges.

The Effects of the Length of the Period of Commitment on the Size of Stable International Environmental Agreements

This paper extends the standard model of self-enforcing dynamic international environmental agreements by allowing the length of the period of commitment of such agreements to vary as a parameter. It analyzes the pattern of behavior of the size of stable coalitions, the stock of pollutant and the emission rate as a function of the length of the period of commitment. It is shown that the length of the period of commitment can have very significant effects on the equilibrium. Three distinct intervals for the length of the period of commitment are identified, across which the equilibrium and its dynamic behavior differ considerably. Whereas for sufficiently high values of the period of commitment only self-enforcing agreements of two countries are possible, for sufficiently low such values full cooperation can be generated. Lengths of periods of commitment between those two thresholds are characterized by an inverse relationship between the length of commitment and the membership size of the agreement. This suggests that considerable attention should be given to the determination of the length of such international agreements.

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.

Evaluating Design Decay during Software Evolution

Les logiciels sont en constante évolution, nécessitant une maintenance et un développement continus. Ils subissent des changements tout au long de leur vie, que ce soit pendant l'ajout de nouvelles fonctionnalités ou la correction de bogues dans le code. Lorsque ces logiciels évoluent, leurs architectures ont tendance à se dégrader avec le temps et deviennent moins adaptables aux nouvelles spécifications des utilisateurs. Elles deviennent plus complexes et plus difficiles à maintenir. Dans certains cas, les développeurs préfèrent refaire la conception de ces architectures à partir du zéro plutôt que de prolonger la durée de leurs vies, ce qui engendre une augmentation importante des coûts de développement et de maintenance. Par conséquent, les développeurs doivent comprendre les facteurs qui conduisent à la dégradation des architectures, pour prendre des mesures proactives qui facilitent les futurs changements et ralentissent leur dégradation. La dégradation des architectures se produit lorsque des développeurs qui ne comprennent pas la conception originale du logiciel apportent des changements au logiciel. D'une part, faire des changements sans comprendre leurs impacts peut conduire à l'introduction de bogues et à la retraite prématurée du logiciel. D'autre part, les développeurs qui manquent de connaissances et–ou d'expérience dans la résolution d'un problème de conception peuvent introduire des défauts de conception. Ces défauts ont pour conséquence de rendre les logiciels plus difficiles à maintenir et évoluer. Par conséquent, les développeurs ont besoin de mécanismes pour comprendre l'impact d'un changement sur le reste du logiciel et d'outils pour détecter les défauts de conception afin de les corriger. Dans le cadre de cette thèse, nous proposons trois principales contributions. La première contribution concerne l'évaluation de la dégradation des architectures logicielles. Cette évaluation consiste à utiliser une technique d’appariement de diagrammes, tels que les diagrammes de classes, pour identifier les changements structurels entre plusieurs versions d'une architecture logicielle. Cette étape nécessite l'identification des renommages de classes. Par conséquent, la première étape de notre approche consiste à identifier les renommages de classes durant l'évolution de l'architecture logicielle. Ensuite, la deuxième étape consiste à faire l'appariement de plusieurs versions d'une architecture pour identifier ses parties stables et celles qui sont en dégradation. Nous proposons des algorithmes de bit-vecteur et de clustering pour analyser la correspondance entre plusieurs versions d'une architecture. La troisième étape consiste à mesurer la dégradation de l'architecture durant l'évolution du logiciel. Nous proposons un ensemble de m´etriques sur les parties stables du logiciel, pour évaluer cette dégradation. La deuxième contribution est liée à l'analyse de l'impact des changements dans un logiciel. Dans ce contexte, nous présentons une nouvelle métaphore inspirée de la séismologie pour identifier l'impact des changements. Notre approche considère un changement à une classe comme un tremblement de terre qui se propage dans le logiciel à travers une longue chaîne de classes intermédiaires. Notre approche combine l'analyse de dépendances structurelles des classes et l'analyse de leur historique (les relations de co-changement) afin de mesurer l'ampleur de la propagation du changement dans le logiciel, i.e., comment un changement se propage à partir de la classe modifiée è d'autres classes du logiciel. La troisième contribution concerne la détection des défauts de conception. Nous proposons une métaphore inspirée du système immunitaire naturel. Comme toute créature vivante, la conception de systèmes est exposée aux maladies, qui sont des défauts de conception. Les approches de détection sont des mécanismes de défense pour les conception des systèmes. Un système immunitaire naturel peut détecter des pathogènes similaires avec une bonne précision. Cette bonne précision a inspiré une famille d'algorithmes de classification, appelés systèmes immunitaires artificiels (AIS), que nous utilisions pour détecter les défauts de conception. Les différentes contributions ont été évaluées sur des logiciels libres orientés objets et les résultats obtenus nous permettent de formuler les conclusions suivantes: • Les métriques Tunnel Triplets Metric (TTM) et Common Triplets Metric (CTM), fournissent aux développeurs de bons indices sur la dégradation de l'architecture. La d´ecroissance de TTM indique que la conception originale de l'architecture s’est dégradée. La stabilité de TTM indique la stabilité de la conception originale, ce qui signifie que le système est adapté aux nouvelles spécifications des utilisateurs. • La séismologie est une métaphore intéressante pour l'analyse de l'impact des changements. En effet, les changements se propagent dans les systèmes comme les tremblements de terre. L'impact d'un changement est plus important autour de la classe qui change et diminue progressivement avec la distance à cette classe. Notre approche aide les développeurs à identifier l'impact d'un changement. • Le système immunitaire est une métaphore intéressante pour la détection des défauts de conception. Les résultats des expériences ont montré que la précision et le rappel de notre approche sont comparables ou supérieurs à ceux des approches existantes.

Action collective patronale : les mécanismes de diffusion entre les niveaux sectoriel et local

Cette recherche s'intéresse à l'acteur patronal organisé, encore peu étudié en Amérique du Nord. Pourtant, cet acteur est fortement organisé au Québec et il exerce une influence reconnue sur les politiques publiques et les relations industrielles. Cette recherche vise à mieux comprendre la logique d’action des employeurs et les lieux où ils exercent leur influence. Plus important encore, la recherche s’interroge sur les mécanismes de diffusion utilisés par les associations patronales pour transmettre à leurs membres des orientations et des lignes directrices à adopter. Tout comme pour l’acteur syndical qui doit développer sa capacité représentative (Dufour, Hege, Levesque et Murray, 2009), nous croyons qu’il en est de même pour l’acteur patronal. Bref, cette étude cherche à comprendre comment les associations patronales vont s'assurer que leurs membres adoptent des pratiques en lien avec les positions défendues dans les institutions du marché du travail et dans la sphère des politiques publiques. Notre question de recherche est la suivante : Quels sont les mécanismes développés par les associations patronales pour diffuser leurs orientations en matière de politiques publiques et de relations du travail en vue d’influencer les pratiques locales de gestion de leurs membres? Au plan théorique, cette étude mobilise les idées développées par les approches néo-institutionnalistes pour mieux expliquer comment les acteurs vont utiliser les institutions en place pour façonner les règles dans leurs intérêts, ce qui suppose d’abord une capacité de représentation et une cohérence dans les actions entre les niveaux où se situent l’acteur. On cherche à comprendre comment les associations peuvent coordonner les actions patronales en réaction aux changements qui s’opèrent dans l’environnement institutionnel. Les associations patronales sont des entrepreneurs institutionnels (Crouch, 2005) qui sont à la recherche active d’opportunités et de leviers de pouvoir à utiliser pour maximiser leurs intérêts de leurs membres et par la même occasion, réduire les incertitudes en provenance de l’environnement (Campbell, 2004; Streeck et Thelen, 2005; Crouch, 2005). Toujours au niveau théorique, cette étude se base sur les idées avancées par la sociologie des logiques d’action. Cette approche théorique nous permet de rendre compte des niveaux sectoriel et local où s’enracinent les comportements des employeurs. Au niveau sectoriel, il existe une pluralité d’instances qui contribuent à façonner les logiques d’actions des associations patronales. La sociologie des logiques d’actions nous permet d’envisager l’association patronale comme un groupe qui dispose d’une vie qui lui est propre avec une relative autonomie de fonctionnement. La capacité d’influence de l’association serait tributaire des mécanismes de coordination de l’action utilisés pour susciter l’accord au sein du groupe. Les mécanismes de coordination de l’action devraient permettre une connexion régulière et stable entre l’association et ses membres. Cette recherche s’intéresse aux associations patronales qui ont recours à un ensemble de moyens pour diffuser les orientations privilégiées aux entreprises membres. Au plan empirique, cette recherche propose de répondre aux trois objectifs suivants : (1) mieux comprendre les formes d’organisation patronales dans les mines au Québec; (2) mieux saisir la structure et la logique d’action des associations patronales sur les politiques publiques, les relations de travail et le marché du travail et finalement (3) mieux comprendre les mécanismes développés par les associations patronales pour diffuser leurs orientations en vue d’influencer les pratiques locales de gestion de leurs membres. Pour atteindre nos objectifs de recherche, nous avons utilisé une méthodologie qualitative de recherche soit une étude de cas du secteur des mines au Québec. Cette dernière a été conduite en trois étapes : la préparation, la collecte des données et l’interprétation (Merriam, 1998). Les données de cette étude ont été recueillies à l’hiver 2012, par le biais d’entretiens semi-directifs auprès de gestionnaires d’entreprises minières et de dirigeants d’associations minières. Une analyse qualitative du contenu de ces entrevues a été effectuée en lien avec la revue de littérature et nos propositions de recherche. À cette fin, nous avons utilisé la technique de l’appariement logique de Yin (1994), ce qui nous a permis de comparer nos observations à nos propositions de recherche. Au niveau des résultats, nous avons pu constater que les associations patronales du secteur des mines au Québec, endossent davantage le rôle de porte-parole de l’industrie auprès du gouvernement que celui de développeur de services aux membres. Les actions des associations patronales s’exercent à tous les niveaux décisionnels afin d’assurer la meilleure promotion possible des intérêts des employeurs. La représentation politique représente le champ d’activité le plus important qui compose la logique d’action des associations patronales de la filière minérale québécoise. Mentionnons également que la représentation des intérêts des entreprises auprès du public et des médias est également vitale à l’action collective patronale dans un souci d’acceptabilité sociale. Les associations d’employeurs vont tenter principalement d’influencer les pratiques en relations industrielles qui permettent d’assurer une meilleure image de l’industrie et qui sont jugées prioritaires en fonction du contexte institutionnel en place. La recherche nous a permis d’observer un impact favorable et significatif à la capacité de diffusion pour cinq des sept mécanismes de diffusion faisant partie de notre modèle d’analyse. Trois de ces cinq mécanismes favorisent la capacité de diffusion descendante (transposition de la logique d’action sectorielle sur les pratiques locales des membres) et les deux autres favorisent plutôt la capacité de diffusion ascendante (transposition des enjeux locaux jugés prioritaires sur la logique d’action sectorielle). Les mécanismes qui supportent au mieux la cohésion au sein de l’association sont ceux qui impliquent une relation dynamique entre les représentants et les membres et entre les membres eux-mêmes d’où la pertinence d’une diffusion descendante et ascendante des orientations. Il est à noter qu’étant donné que cette recherche consiste en une étude de cas, des limites méthodologiques liées à la généralisation des résultats sont présentes. Il n’est pas aisé d’affirmer que les résultats de cette microanalyse soient généralisables en raison des spécificités du secteur à l’étude. En contrepartie, les analyses ont servi à l’élaboration d’un modèle qui pourra être utilisé dans des études futures.