Applied matching algorithms - Selected problems from the domains of computer science education and market design

Reischmann Tobias

Zusammenfassung
Matching algorithms are a topic of research in various domains, from the applications in computer science education to the areas of market design in economics. Matching problems can be characterized by their parameter space, its constraints on the validity of a solution, and the optimization goal. This thesis depicts the similarity and differences between matching problems as well as between the algorithms that are applied to solve them in an interdisciplinary context. It highlights the incentives of different domains to solve similar problems through different techniques and approaches. In this context, two selected matching problems from the domains of computer science education and market design are presented and discussed. The first problem deals with the automatic assessment of UML class diagrams in the setting of formative e-assessment. A new e-assessment tool is proposed, which uses error-tolerant graph matching techniques to analyse a student's submission regarding the implementation of design patterns. Then, feedback is generated based on the design pattern applied by the student and the differences to an exemplary solution. The second problem approaches the allocation of children to childcare facilities in German cities. A case study is outlined that investigates this two-sided market and analyses it in the context of game-theoretic matching theory. The identified requirements are used for the design of the new iterative deferred acceptance with ties mechanism. In the thesis, this mechanism is defined and evaluated for its applicability in different markets. The two projects exemplify how existing matching theory can be applied in practice and how the adaption of ideas from different domains can be helpful to improve the knowledge base of research about matching algorithms in general.