Multi-Prover and parallel repetition in non-classical interactive games

Depuis l’introduction de la mécanique quantique, plusieurs mystères de la nature ont trouvé leurs explications. De plus en plus, les concepts de la mécanique quantique se sont entremêlés avec d’autres de la théorie de la complexité du calcul. De nouvelles idées et solutions ont été découvertes et élaborées dans le but de résoudre ces problèmes informatiques. En particulier, la mécanique quantique a secoué plusieurs preuves de sécurité de protocoles classiques. Dans ce m´emoire, nous faisons un étalage de résultats récents de l’implication de la mécanique quantique sur la complexité du calcul, et cela plus précisément dans le cas de classes avec interaction. Nous présentons ces travaux de recherches avec la nomenclature des jeux à information imparfaite avec coopération. Nous exposons les différences entre les théories classiques, quantiques et non-signalantes et les démontrons par l’exemple du jeu à cycle impair. Nous centralisons notre attention autour de deux grands thèmes : l’effet sur un jeu de l’ajout de joueurs et de la répétition parallèle. Nous observons que l’effet de ces modifications a des conséquences très différentes en fonction de la théorie physique considérée.

Entrelacement de la tradition imaginaire du western et du réalisme contemporain

La création cinématographique de l’étudiante qui accompagne ce mémoire sous la forme d’un DVD est disponible à la Médiathèque de la Bibliothèque des lettres et sciences humaines sous le titre : Désarçonné.(http://atrium.umontreal.ca/notice/UM-ALEPH002343646)

Budget-Balance, Fairness and Minimal Manipulability

A common real-life problem is to fairly allocate a number of indivisible objects and a fixed amount of money among a group of agents. Fairness requires that each agent weakly prefers his consumption bundle to any other agent’s bundle. Under fairness, efficiency is equivalent to budget-balance (all the available money is allocated among the agents). Budget-balance and fairness in general are incompatible with non-manipulability (Green and Laffont, 1979). We propose a new notion of the degree of manipulability which can be used to compare the ease of manipulation in allocation mechanisms. Our measure counts for each problem the number of agents who can manipulate the rule. Given this notion, the main result demonstrates that maximally linked fair allocation rules are the minimally manipulable rules among all budget-balanced and fair allocation mechanisms. Such rules link any agent to the bundle of a pre-selected agent through indifferences (which can be viewed as indirect egalitarian equivalence).

La structure du sommeil et l’activité cardiaque nocturne chez les adolescents ayant un trouble anxieux

L’objectif de la présente thèse était de caractériser le sommeil d’un groupe clinique d’enfants et d’adolescents ayant un trouble d’anxiété comme diagnostic primaire et le comparer à un groupe témoin. Dans un premier temps, nous avons vérifié si le profil de la fréquence cardiaque nocturne des enfants et des adolescents pouvait être regroupé selon le diagnostic. Pour ce faire, la fréquence cardiaque nocturne de 67 adolescents anxieux et 19 sujets non anxieux a été enregistrée à l’aide d’un équipement ambulatoire. Les résultats de cette étude montrent que le profil de la fréquence cardiaque nocturne chez les enfants anxieux varie selon le diagnostic. Alors que les adolescents non anxieux montrent un profil de la fréquence cardiaque nocturne plat, on retrouve les associations suivantes chez les adolescents ayant un trouble anxieux : a) un profil croissant de la fréquence cardiaque chez les adolescents ayant un trouble d’anxiété de séparation; b) un profil décroissant de la fréquence cardiaque chez les adolescents ayant un trouble d’anxiété généralisé; c) un profil en forme de U chez les adolescents ayant un trouble d’anxiété sociale. De plus, une association significative a été observée entre le diagnostic et la présence de fatigue matinale. L’association d’un profil de la fréquence cardiaque nocturne avec un diagnostic d’anxiété suggère la présence d’une dysrégulation de la modulation chronobiologique du système nerveux autonome. Étant donné que le profil de la fréquence cardiaque nocturne s’exprime différemment selon le diagnostic, qu’en est-il de l’architecture du sommeil? Dans un deuxième temps, nous avons enregistré le sommeil en laboratoire d’un groupe clinique de 19 jeunes ayant un trouble d’anxiété comme diagnostic primaire, avec comorbidités et médication et comparé à 19 jeunes non anxieux. Les résultats de cette étude ont montré que les participants du groupe anxieux ont une latence au sommeil plus longue, une latence au sommeil paradoxal plus longue et une durée d’éveil plus longue lorsque comparé au groupe témoin. L’évaluation subjective de la qualité du sommeil chez le groupe d’adolescents anxieux montre que leur auto-évaluation reflète les valeurs enregistrées en laboratoire. Nous avons également observé chez le groupe anxieux une fréquence cardiaque moyenne plus élevée et un index plus élevé d’apnée-hypopnée, bien que non pathologique. Nous avons également observé une association positive entre l’anxiété de trait et l’indice d’apnée-hypopnée et la latence au sommeil, ainsi qu’une association positive entre l’anxiété manifeste et la latence au sommeil paradoxal. Ces résultats suggèrent que le sommeil chez cette population est altéré, que des signes d’hypervigilance physiologique sont présents et qu'une association existe entre ces deux paramètres. Finalement, dans la troisième étude de cette thèse, nous avons analysé l’activité cardiaque pendant le sommeil en utilisant les paramètres temporels et fréquentiels de la variabilité cardiaque chez un groupe clinique de dix-sept enfants et adolescents ayant un trouble d’anxiété comme diagnostic primaire avec comorbidité et médication, et comparé à un groupe non anxieux. Les résultats ont montré que les participants du groupe anxieux, lorsque comparés au groupe non anxieux, présentent des intervalles interbattements plus courts, un indice temporel de la variabilité cardiaque représentant la branche parasympathique moindre, une activité des hautes fréquences normalisées moindre et un ratio basse fréquence sur haute fréquence augmenté. Plusieurs corrélations ont été observées entre les mesures cliniques de l’anxiété et les mesures de la variabilité cardiaque. Ces résultats viennent ajouter à la littérature actuelle un volet descriptif clinique à ce jour non documenté, soit l’impact de l’anxiété pathologique chez un groupe clinique d’enfants et d’adolescents sur le processus normal du sommeil et sur la régulation de la fréquence cardiaque. En résumé, les résultats de ces trois études ont permis de documenter chez un groupe clinique d’enfants et d’adolescents ayant de l’anxiété pathologique, la présence d’une altération circadienne du profil de la fréquence cardiaque, d’une architecture altérée du sommeil ainsi qu’une dysrégulation du système nerveux contrôlant l’activité cardiaque.

(Minimally) 'epsilon'-incentive compatible competitive equilibria in economies with indivisibilities

We consider competitive and budget-balanced allocation rules for problems where a number of indivisible objects and a fixed amount of money is allocated among a group of agents. In 'small' economies, we identify under classical preferences each agent's maximal gain from manipulation. Using this result we find the competitive and budget-balanced allocation rules which are minimally manipulable for each preference profile in terms of any agent's maximal gain. If preferences are quasi-linear, then we can find a competitive and budget-balanced allocation rule such that for any problem, the maximal utility gain from manipulation is equalized among all agents.

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.

Transferring ownership of public housing to existing tenants: a mechanism design approach

This paper explores situations where tenants in public houses, in a specific neighborhood, are given the legislated right to buy the houses they live in or can choose to remain in their houses and pay the regulated rent. This type of legislation has been passed in many European countries in the last 30-35 years (the U.K. Housing Act 1980 is a leading example). The main objective with this type of legislation is to transfer the ownership of the houses from the public authority to the tenants. To achieve this goal, selling prices of the public houses are typically heavily subsidized. The legislating body then faces a trade-off between achieving the goals of the legislation and allocating the houses efficiently. This paper investigates this specific trade-off and identifies an allocation rule that is individually rational, equilibrium selecting, and group non-manipulable in a restricted preference domain that contains “almost all” preference profiles. In this restricted domain, the identified rule is the equilibrium selecting rule that transfers the maximum number of ownerships from the public authority to the tenants. This rule is preferred to the current U.K. system by both the existing tenants and the public authority. Finally, a dynamic process for finding the outcome of the identified rule, in a finite number of steps, is provided.

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.