Katharina Eickhoff: Design and Analysis of Algorithms for Combinatorial Optimization Problems under Uncertainties
Matchings appear in many combinatorial optimization models of applications where assignments between two parties (sellers and buyers, students and courses, . . . ) have to be found. In these examples each player has preferences to which he would like to be matched. Often, prices might be used to regulate imbalances between supplies and demands. A possible aim is to find assignments and prices such that everyone is happy, i.e., with these prices no one prefers to trade with someone else instead of the assigned person. These prices are called equilibrium prices. Combinatorial algorithms to find equilibrium prices often use the concept of duality. For example, in two-side matching markets with valuations on both sides, equilibrium prices can be found by iteratively applying a primal-dual algorithm to find a max-cardinality matching in a bipartite graph. Another example are markets in which trade occurs via intermediaries. Sellers and buyers have valuations for trading with each other and only trade if they profit. It can be shown that welfare maximizing equilibrium prices exist and can be computed efficiently via a primaldual algorithm for solving a max-weight matching in a bipartite graph and adapting the dual prices so that they form equilibrium prices.