Katharina Eickhoff: Design and Analysis of Algorithms for Combinatorial Optimization Problems under Uncertainties

 

Matching Markets

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. If furthermore as much as possible is sold we call the prices market-clearing. Prices which are competitive and market-clearing describing the set of Walrasian prices. One possibility to find Walrasian prices is by a price raising auction (see for example [1,2,3]).

To find the set of objects whose prices should be raised is quite complicated in the general case. We could show that these sets could be found by a max-flow computation in case of linear valuations. Furthermore we could give sensitivity results for the prices if the demand or supply in the matching-market changes. Currently, we generalize this results for matroid valuations.
There are many ways to expand this approach which we might consider in the future.
One example are two-stage variants. In the first stage, agents decide on a strategy based on probability distributions of the agents’ valuations. The agents are allowed to switch their strategies in a given neighborhood in the second stage when the true valuations are common knowledge. For example, the agents decide on a strategy based on guesses of the valuations and they can adapt their strategies in a given scope in the real scenario. The objective of an agent is to maximize the expected profit.
Furthermore, we like to consider the setting with risk-averse agents. They prefer a robust solution within all possible situations which means that the profit they receive in the worst-case scenario should be maximized. The strategies of the agents are in equilibrium if each strategy is the best robust response given the other strategies. We study the existence of equilibria in such markets. If equilibria exist, we like to analyze the complexity and design algorithms to compute or approximate them.

Stackelberg Network Pricing Games

Consider a game with to players. The leader can choose prices for some items of an underling network in the first stage. Afterwards, in the second stage, the follower chooses the items which yields a min cost solution of his optimization problem (e.g. matching, vertex cover, closure). Most of these problems are NP-hard in general, but if the underling network or the set of priceable items is restricted there might be a polynomial algorithm to solve it.

We consider the Stackelberg Bipartite Vertex Cover Problem, which is NP-hard [4]. It is known that the problem is polynomial solvable if the pricable vertices are on one side of the bipartition [5]. We like to show similar results for pricable vertices on both sides but if the underling graph has a special structure, e.g. if it is a path or a tree.

In the future we like to consider instances of Stackelberg games where the leader has to choose the prices of his items given some uncertainty of the followers preferences, e.g. if the fixed prices are just given as a probability distribution in the first stage.

References

[1] L.M. Ausubel: An efficient dynamic auction for heterogeneous commodities. American Economic Review 96(3), p. 602–629, 2006.

[2] G. Demange, D. Gale and M. Sotomayor. Multi-item auctions. Journal of political economy, vol. 94.4, p. 863-872, 1986.

[3] K. Murota, A. Shioura, Z. Yang: Computing a walrasian equilibrium in iterative auctions with multiple differentiated items. International Symposium on Algorithms and Computation. p. 468–478. 2013.

[4] K. Jungnitsch, B. Peis, M.Schröder: Stackelberg Max Weight Closure with Multiple Followers. Preprint:https://www.oms.rwth-aachen.de/global/show_document.asp?id=aaaaaaaaapdbhng

[5] P. Briest, M. Hoefer, P. Krysta: Stackelberg network pricing games. Algorithmica, 62(3), p. 733–753. 2012.