Algorithmik und Komplexitätstheorie

Matching under Preferences: Multimodal Views and Domain Restrictions (MaMu)


Given the great relevance of matching under preferences, the goals of this joint research project are basically two-fold. First, we want to investigate how restrictions on the allowed preferences can improve the efficiency for several solving algorithms. Doing so, we want to extend and improve results from the literature. Second, we plan to study stable matching for multi-layer preferences, a new direction we introduce here. Indeed, it is very well-motivated by the fact of having multi-modal data available (from different sources). To this end, after carefully introducing the relevant notions it is of central interest to investigate how classical concepts and algorithms can be transferred to this more general scenario. Finally, in a third part we plan to study further models, going beyond the two mentioned main parts. In particular, here we aim at touching on issues such as “incremental scenarios” or game-theoretic aspects.
The projects brings together the expertise of the Chinese and the German research groups. Both sides have actively contributed to several topics related to Computational Social Choice and, in particular, to restricted preferences and issues of preference aggregation. Moreover, both groups are heavily involved into parameterized complexity analysis and algorithms for hard combinatorial problems in general. Based on this common ground, the proposed project builds on (partially joint) previous experiences and joins forces in attacking a fundamental issue of Computational Social Choice and closely related areas; matching under preferences, as we will demonstrate, both being fundamental and being unexplored in several directions, allows for numerous future innovations (conceptually and methodologically) we want to provide.

Funded by

Deutsche Forschungsgemeinschaft (Project MaMu, NI 369/19) and the National Natural Science Foundation of China


Since April 2018


with Shandong University

Head (TU Berlin)


Robert Bredereck

Ehemaliger Mitarbeiter

People (TU Berlin)

Head (Cooperation)

Daming Zhu

Einrichtung Shandong University

People (Cooperation)


Jiong Guo

Ehemaliger Mitarbeiter

Einrichtung Shandong University

Hong Liu

Einrichtung Shandong University