京都大学 / 新制・課程博士 / 博士(情報学) / 甲第24030号 / 情博第786号 / 新制||情||133(附属図書館) / 京都大学大学院情報学研究科知能情報学専攻 / (主査)准教授 宮崎 修一, 教授 岡部 寿男, 教授 阿久津 達也, 教授 湊 真一 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

Apresentamos a teoria sobre mercados de dois lados, centralizados e descentralizados, para analisar o mercado de admissão de estudantes aos Centros de Pós-graduação em Economia no Brasil ao longo dos últimos 15 anos. Iniciamos descrevendo a história da organização deste mercado até a época atual. As falhas do sistema descentralizado e as hipóteses sobre o insucesso do procedimento centralizado de 1997 são discutidas. Observações empíricas são utilizadas para propor um modelo teórico que represente aproximadamente o atual mecanismo descentralizado e explique a aparente duradoura aplicação desse mecanismo. Por fim, tecemos considerações a respeito das possibilidades de aprimoramento deste mercado com modificações do mecanismo existente. / We present the theory of two-sided matching markets, with centralized and decentralized mechanisms, in order to analyze a Brazilian market in which graduated students seek positions in postgraduate programs in economics. We first describe the institutional history of this market. The failures of the decentralized procedure and the hypothesis about the failure of the 1997 centralized mechanism are discussed. Empirical observations are used to propose a theoretical model that represents the actual decentralized matching procedure of the market. Based in this model we explain the apparent long-lasting use of this decentralized mechanism. Finally, we make considerations about the possibilities of developments in this market by modifying the mechanism used today.

Apresentamos a teoria sobre mercados de dois lados, centralizados e descentralizados, para analisar o mercado de admissão de estudantes aos Centros de Pós-graduação em Economia no Brasil ao longo dos últimos 15 anos. Iniciamos descrevendo a história da organização deste mercado até a época atual. As falhas do sistema descentralizado e as hipóteses sobre o insucesso do procedimento centralizado de 1997 são discutidas. Observações empíricas são utilizadas para propor um modelo teórico que represente aproximadamente o atual mecanismo descentralizado e explique a aparente duradoura aplicação desse mecanismo. Por fim, tecemos considerações a respeito das possibilidades de aprimoramento deste mercado com modificações do mecanismo existente. / We present the theory of two-sided matching markets, with centralized and decentralized mechanisms, in order to analyze a Brazilian market in which graduated students seek positions in postgraduate programs in economics. We first describe the institutional history of this market. The failures of the decentralized procedure and the hypothesis about the failure of the 1997 centralized mechanism are discussed. Empirical observations are used to propose a theoretical model that represents the actual decentralized matching procedure of the market. Based in this model we explain the apparent long-lasting use of this decentralized mechanism. Finally, we make considerations about the possibilities of developments in this market by modifying the mechanism used today.

De nos jours, avec l'utilisation croissante des technologies numériques, l'éducation à la préservation de la vie privée joue un rôle important en particulier pour les adolescents. Bien que plusieurs plateformes d'apprentissage en ligne à la sensibilisation à la vie privée aient été mises en œuvre, elles sont généralement basées sur des techniques traditionnelles d'apprentissage. Plus particulièrement, ces plateformes ne permettent pas aux étudiants de coopérer et de partager leurs connaissances afin d’améliorer leur apprentissage ensemble. En d'autres termes, elles manquent d'interactions élève-élève. Des recherches récentes sur les méthodes d'apprentissage montrent que la collaboration entre élèves peut entraîner de meilleurs résultats d'apprentissage par rapport à d'autres approches. De plus, le domaine de la vie privée étant fortement lié à la vie sociale des adolescents, il est préférable de fournir un environnement d'apprentissage collaboratif où l’on peut enseigner la préservation de la vie privée, et en même temps, permettre aux étudiants de partager leurs connaissances. Il serait souhaitable que ces derniers puissent interagir les uns avec les autres, résoudre des questionnaires en collaboration et discuter de problèmes et de situations de confidentialité. À cet effet, ce travail propose « Teens-online », une plateforme d'apprentissage en ligne collaborative pour la sensibilisation à la vie privée. Le programme d'études fourni dans cette plateforme est basé sur le Référentiel de formation des élèves à la protection des données personnelles. De plus, la plateforme proposée est équipée d'un mécanisme d'appariement de partenaires basé sur la théorie des jeux. Ce mécanisme garantit un appariement élève-élève stable en fonction des besoins de l'élève (comportement et / ou connaissances). Ainsi, des avantages mutuels seront obtenus en minimisant les chances de coopérer avec des pairs incompatibles. Les résultats expérimentaux montrent que l'utilité moyenne obtenue en appliquant l'algorithme proposé est beaucoup plus élevée que celle obtenue en utilisant d'autres mécanismes d'appariement. Les résultats suggèrent qu'en adoptant l'approche proposée, chaque élève peut être jumelé avec des partenaires optimaux, qui obtiennent également en retour des résultats d'apprentissage plus élevés. / Nowadays, with the increasing use of digital technologies, especially for teenagers, privacy education plays an important role in their lives. While several e-learning platforms for privacy awareness training have been implemented, they are typically based on traditional learning techniques. In particular, these platforms do not allow students to cooperate and share knowledge with each other in order to achieve mutual benefits and improve learning outcomes. In other words, they lack student-student interaction. Recent research on learning methods shows that the collaboration among students can result in better learning outcomes compared to other learning approaches. Motivated by the above-mentioned facts, and since privacy domain is strongly linked to the social lives of teens, there is a pressing need for providing a collaborative learning platform for teaching privacy, and at the same time, allows students to share knowledge, interact with each other, solve quizzes collaboratively, and discuss privacy issues and situations. For this purpose, this work proposes “Teens-online”, a collaborative e-learning platform for privacy awareness. The curriculum provided in this platform is based on the Personal Data Protection Competency Framework for School Students. Moreover, the proposed platform is equipped with a partner-matching mechanism based on matching game theory. This mechanism guarantees a stable student-student matching according to a student's need (behavior and/or knowledge). Thus, mutual benefits will be attained by minimizing the chances of cooperating with incompatible students. Experimental results show that the average learning-related utility obtained by applying the proposed partner-matching algorithm is much higher than the average utility obtained using other matching mechanisms. The results also suggest that by adopting the proposed approach, each student can be paired with their optimal partners, which in turn helps them reach their highest learning outcomes.

[pt] A teoria de Morse relaciona a topologia de um espaço aos elementos críticos de uma função escalar definida nele. Isso vale tanto para a teoria clássica quanto para a versão discreta proposta por Forman em 1995. Essas teorias de Morse permitem caracterizar a topologia do espaço a partir de funções definidas nele, mas também permite estudar funções a partir de construções tipológicas derivadas dela, como por exemplo o complexo de Morse-Smale. Apesar da teoria de Morse discreta se aplicar para complexos celulares gerais de forma inteiramente combinatória, o que torna a teoria particularmente bem adaptada para o computador, as funções usadas na teoria não são amostragens de funções contínuas, mas casamentos especiais no grafo que codifica as adjacências no complexo celular, chamadas de casamentos de Morse. Quando usar essa teoria para estudar um espaço topológico, procura- se casamentos de Morse ótimos, i.e. com o menor número possível de elementos críticos, para obter uma informação topológica do complexo sem redundância. Na primeira parte desta tese, investiga-se a complexidade parametrizada de encontrar esses casamentos de Morse ótimos. Por um lado, prova-se que o problema ERASABILITY, um problema fortemente relacionado à encontrar casamentos de Morse ótimos, é W [P ]-completo. Por outro lado, um algoritmo é proposto para calcular casamentos de Morse ótimos em triangulações de 3-variedades, que é FPT no parâmetro do tree- width de seu grafo dual. Quando usar a teoria de Morse discreta para estudar uma função escalar definida no espaço, procura-se casamentos de Morse que capturam a informação geométrica dessa função. Na segunda parte é proposto uma construção de casamentos de Morse baseada em casamentos estáveis. As garantias teóricas sobre a relação desses casamentos com a geometria são elaboradas a partir de provas surpreendentemente simples que aproveitam da caracterização local do casamento estável. A construção e as suas garantias funcionam em qualquer dimensão. Finalmente, resultados mais fortes são obtidos quando a função for suave discreta, uma noção definida nesta tese. / [en] Morse theory relates the topology of a space to the critical elements of a scalar function defined on it. This applies in both the classical theory and a discrete version of it defined by Forman in 1995. Those Morse theories permit to characterize a topological space from functions defined on it, but also to study functions based on topological constructions it implies, such as the Morse-Smale complex. While discrete Morse theory applies on general cell complexes in an entirely combinatorial manner, which makes it suitable for computation, the functions it considers are not sampling of continuous functions, but special matchings in the graph encoding the cell complex adjacencies, called Morse matchings. When using this theory to study a topological space, one looks for optimal Morse matchings, i.e. one with the smallest number of critical elements, to get highly succinct topological information about the complex. The first part of this thesis investigates the parameterized complexity of finding such optimal Morse matching. On the one hand the Erasability problem, a closely related problem to finding optimal Morse matchings, is proven to be W[P]-complete. On the other hand, an algorithm is proposed for computing optimal Morse matchings on triangulations of 3-manifolds which is fixed parameter tractable in the tree-width of its dual graph. When using discrete Morse theory to study a scalar function defined on the space, one looks for a Morse matching that captures the geometric information of that function. The second part of this thesis introduces a construction of Morse matchings based on stable matchings. The theoretical guarantees about the relation of such matchings to the geometry are established through surprisingly simple proofs that benefits from the local characterization of the stable matching. The construction and its guarantees work in any dimension. Finally stronger results are obtained if the function is discrete smooth on the complex, a notion defined in this thesis.

Cette thèse aborde les facettes dynamiques des principes fondamentaux du problème de l'appariement stable plusieurs-à-un. Nous menons notre étude dans le contexte du choix de l'école et de l'appariement entre les hôpitaux et les résidents. Dans la première étude, en utilisant le modèle résident-hôpital, nous étudions la complexité de calcul de l'optimisation des variations de capacité des hôpitaux afin de maximiser les résultats pour les résidents, tout en respectant les contraintes de stabilité et de budget. Nos résultats révèlent que le problème de décision est NP-complet et que le problème d'optimisation est inapproximable, même dans le cas de préférences strictes et d'allocations de capacités disjointes. Ces résultats posent des défis importants aux décideurs qui cherchent des solutions efficaces aux problèmes urgents du monde réel. Dans la seconde étude, en utilisant le modèle du choix de l'école, nous explorons l'optimisation conjointe de l'augmentation des capacités scolaires et de la réalisation d'appariements stables optimaux pour les étudiants au sein d'un marché élargi. Nous concevons une formulation innovante de programmation mathématique qui modélise la stabilité et l'expansion des capacités, et nous développons une méthode efficace de plan de coupe pour la résoudre. Des données réelles issues du système chilien de choix d'école valident l'impact potentiel de la planification de la capacité dans des conditions de stabilité. Dans la troisième étude, nous nous penchons sur la stabilité de l'appariement dans le cadre de priorités dynamiques, en nous concentrant principalement sur le choix de l'école. Nous introduisons un modèle qui tient compte des priorités des frères et sœurs, ce qui nécessite de nouveaux concepts de stabilité. Notre recherche identifie des scénarios où des appariements stables existent, accompagnés de mécanismes en temps polynomial pour leur découverte. Cependant, dans certains cas, nous prouvons également que la recherche d'un appariement stable de cardinalité maximale est NP-difficile sous des priorités dynamiques, ce qui met en lumière les défis liés à ces problèmes d'appariement. Collectivement, cette recherche contribue à une meilleure compréhension des capacités et des priorités dynamiques dans les scénarios d'appariement stable et ouvre de nouvelles questions et de nouvelles voies pour relever les défis d'allocation complexes dans le monde réel. / This research addresses the dynamic facets in the fundamentals of the many-to-one stable matching problem. We conduct our study in the context of school choice and hospital-resident matching. In the first study, using the resident-hospital model, we investigate the computational complexity of optimizing hospital capacity variations to maximize resident outcomes, while respecting stability and budget constraints. Our findings reveal the NP-completeness of the decision problem and the inapproximability of the optimization problem, even under strict preferences and disjoint capacity allocations. These results pose significant challenges for policymakers seeking efficient solutions to pressing real-world issues. In the second study, using the school choice model, we explore the joint optimization of increasing school capacities and achieving student-optimal stable matchings within an expanded market. We devise an innovative mathematical programming formulation that models stability and capacity expansion, and we develop an effective cutting-plane method to solve it. Real-world data from the Chilean school choice system validates the potential impact of capacity planning under stability conditions. In the third study, we delve into stable matching under dynamic priorities, primarily focusing on school choice. We introduce a model that accounts for sibling priorities, necessitating novel stability concepts. Our research identifies scenarios where stable matchings exist, accompanied by polynomial-time mechanisms for their discovery. However, in some cases, we also prove the NP-hardness of finding a maximum cardinality stable matching under dynamic priorities, shedding light on challenges related to these matching problems. Collectively, this research contributes to a deeper understanding of dynamic capacities and priorities within stable matching scenarios and opens new questions and new avenues for tackling complex allocation challenges in real-world settings.

With growing information availability recommendation systems help users navigate and filter the many options. The home rental market has been pointed out as one of the unexplored areas for recommendations system. This project examines the effects of incorporating historical data for probabilistic weighting and matching algorithms for increased recommendation diversity for a tenant to landlord recommendation system. This was done by implementing two new recommendation systems. The first uses probabilistic weighting to measure the similarity between tenants and landlord homes. The second combines this probabilistic weighting with a variant of the Deferred Acceptance algorithm to enhance recommendation diversity. These two recommendation systems were A/B tested together with the existing tenant recommendation system on the Qasa platform, a digital end-to-end rental apartments marketplace in Sweden. With the objective of having the recommendation system increase landlord engagement a good recommendation was defined as one where the landlord choose to contact the tenant. After the A/B test period, the three recommendation variants were evaluated on Coverage@N, Gini-Index@K, Precision@K and Recall@K. The result revealed that the use of the Deferred Acceptance algorithm did increase the recommendation diversity, but it led to reduced precision in the top recommendations compared to the first new implementation that only used probabilistic weighting. However, the incorporation of historical data for the probabilistic weighting for similarity in booth new recommendation systems showed higher precision and number of contacted tenants compared to the existing tenant recommendation model on the Qasa platform. / Med växande informationstillgänglighet hjälper rekommendationssystem användarna att navigera och filtrera bland många alternativ. Hyresmarknaden har pekats ut som ett av de outforskade områdena för rekommendationssystem. Detta projekt undersöker effekterna av att inkorporera historiska data för statistiska vikter och matchningsalgoritmer för ökad rekommendations mångfald i ett rekommendationssystem från hyresgäster till hyresvärdar. Detta gjordes genom att implementera två nya rekommendationssystem. Det första använder statistiska vikter för att mäta likheten mellan hyresgäster och hyresvärdars bostäder. Det andra kombinerar dessa statistiska vikter med en variant av deferred acceptance algorithm algoritmen för att förbättra rekommendations mångfaldet. Dessa två rekommendationssystem A/B testades tillsammans med det befintliga rekommendationssystemet av hyresgäster på Qasa-plattformen, en digital marknadsplats för andrahandsuthyrning av lägenheter i Sverige. Med målet att rekommendationssystemet skulle öka hyresvärdens engagemang definierades en bra rekommendation som en där hyresvärden valde att kontakta hyresgästen. Efter A/B-testperioden utvärderades de tre rekommendationsvarianterna baserat på Coverage@N, Gini-Index@K, Precision@K och Recall@K. Resultatet visade att användningen av algoritmen för uppskjuten acceptans ökade mångfaldet i ett rekommendationssystem, men det ledde till minskad precision i de första rekommendationerna jämfört med den första nya implementationen som endast använde statistiska vikter. Däremot visade inkorporeringen av historiska data för statistiska vikter vid uträkning av likhet, något som gjordes i båda nya rekommendationssystem, högre precision och fler antal kontaktade hyresgäster jämfört med den befintliga modellen för hyresgästrekommendationer på Qasa-plattformen.