Matching problems involving preferences occur in widespread applications such as the assignment of children to schools, school-leavers to universities, junior doctors to hospitals, students to campus housing, kidney transplant patients to donors and so on. Very often the common thread is that agents have ordinal preferences over the possible outcomes – that is, some notion of first, second, third choice, etc. The task is to find a matching (i.e., an assignment of the participants to one another) that is in some sense optimal with respect to these preferences. These problems are growing in importance in an era in which more and more elements of society are embracing diverse forms of electronic communication, and individuals are increasingly used to making choices via the internet. The ease by which preference information can now be collected has contributed to the growing tendency for matching processes to be centralised. Due to the typical size of applications (for example, in China, over 10 million students apply for admission to higher education annually through a centralised process), trying to construct optimal allocations manually (given a suitable definition of “optimal”) is simply not feasible. Thus algorithms are required to automate the process of constructing optimal matchings. Again, due to the size of typical applications, the efficiency of the algorithms is of paramount importance. The notion of optimality is also a key consideration: many matching processes are conducted by publicly-funded organisations, and there is an increasing tendency for the decisions reached by these organisations to be scrutinised both in the media and by individuals through Freedom of Information requests, for example. Thus the algorithms need to construct matchings that are not just provably optimal, but also are seen to be “fair” by the agents involved.
This seminar is based on the book "Algorithmics of matching under perferences" by David Manlove and focuses on algorithmic aspects of matching problems involving preferences. Some of the many applications in which these algorithms feature are also described.
Alle Studierenden erhalten ein konkretes Thema. Sie erhalten nach Zuteilung eines Platzes im Seminar eine Themenliste und können hier Wünsche äußern, die im Abgleich mit den anderen Studenten berücksichtigt werden.
Sie werden in Ihrem Thema und Ihrer Ausarbeitung individuell betreut.
Nach Zuteilung der Seminarplätze erhalten Sie weitere Informationen zu den Themen per E-Mail, sodass Sie ihre Auswahl besser treffen können.
Das Seminar findet in 3 bis 4 Blöcken statt, immer Mittwochs, 14-18 Uhr, Oettingenstr. 67, C 003.
Bachelor Informatik oder Medieninformatik. Gefordert ist ein Vortrag von 40 Minuten mit anschließender, 10 minütiger, Diskussion und eine Ausarbeitung mit 7-12 Seiten.
Vorlesung “Algorithmen und Datenstrukturen”