Switch to German Switch to English



Dynamic Coordination in Large Networks

(gefördert von der DFG im Rahmen der Exzellenzinitiative, 2012 - 2016)

Our focus is the analysis of dynamics in large networked systems such as traffic systems, wireless networks, the Internet, or social networks. In these systems, central coordination of user behavior is often impossible. Instead, distributed and decentralized protocols are needed in order to obtain efficient solutions for coordination problems. Our aim is the analysis and characterization of these systems and the design of efficient algorithms - for instance, distributed learning algorithms for throughput maximization in wireless networks, or routing protocols for rational and selfish users in traffic networks. A special focus are game-theoretic approaches that model rational behavior of individual users in the system and set appropriate incentives that lead the system into globally efficient states. In addition, we analyze natural dynamics and their convergence properties in social networks.

Sequential Information Aggregation with Partial Observability

(gefördert von der German-Israeli Foundation (GIF), 2018 - 2020)

A classical setting where decentralized markets may fail is when critical information exists but is distributed among the agents. Each agent can access the information held by other agents only implicitly by observing their actions. We study structural properties and computationally efficient mechanisms for information aggregation in settings where self-interested agents take actions sequentially and partially observe each other. Our aim is to design mechanisms using ideas from learning theory to limit or even avoid market failure.
One (out of several) settings we study is designing a recommendation system based on the wisdom-of-the-crowd (such as, e.g., TripAdvisor, Hotels.com, etc). In these systems, services that are less recommended are typically consumed by fewer people, thus less reviewed and recommended, which ensures that they maintain a low rank. This tension between exploration and exploitation needs to be addressed to ensure good performance of the system. We study how to design computationally efficient mechanisms to ensure enough exploration even when agents act individually and partially see actions taken by preceding agents. Orchestrated by the system, exploration must be implemented such that agents find it in their best interest to follow the recommendations. The mechanisms must incorporate or even decide about partial observability of agents and actions of predecessors - which, in turn, result from the recommendations they received as well as what they saw (some of) their own predecessors doing.