Switch to German Switch to English

Contact

Algorithms and Complexity Group
Institute for Computer Science
Goethe University Frankfurt
Robert-Mayer-Strasse 11-15
D-60325 Frankfurt am Main

Secretary Office:
Teresa Fischer
Institute for Computer Science
Room 116
Tel.: +49 (0) 69 798-28119

Canvas

A New Beginning 1 June 2024

After more than 7 very successful years at Goethe University, our group will be moving to RWTH Aachen University over the summer. We are excited about the new opportunities and thank everyone for the great time in Frankfurt.



New Paper in Journal of Artificial Intelligence Research 5 May 2024

Computational aspects of fair division have recently received a lot of attention in algorithms and social choice. Especially fair allocation of indivisible items (like real-estate, cars, jewelry, etc.) to multiple agents is a very challenging problem. In our new paper ''Best of Both Worlds: Agents with Entitlements'' (by Martin Hoefer, Marco Schmalhofer, Giovanna Varricchio) we propose randomized algorithms with ex-ante and ex-post fairness guarantees when agents can have heterogeneous entitlements or priorities. Our guarantees refer to variants of envy-freeness (where agents do not (strongly) prefer bundles of other agents) and are optimal for additive valuations. We also propose the first (ex-ante + ex-post)-guarantees beyond additive valuations. The paper has been accepted for publication in the Journal of Artificial Intelligence Research, a top journal in artificial intelligence.



New Paper in Distributed Comptuting 28 Mar 2024

Opinion formation is usually modeled as a process where agents adjust their publicly expressed views to popularity and similarity in their peer group. In the classic Hegselmann-Krause model, opinions are expressed by numerical values, and agents adapt to opinions within a bounded range around their current value. While convergence properties in this model are reasonably well-understood with synchronous updates of the entire population, our new paper ''Asynchronous Opinion Dynamics in Social Networks'' (by Petra Berenbrink, Martin Hoefer, Pascal Lenzner, Malin Rau, Dominik Schallmoser, Daniel Schmand) reveals that even asynchronous updates do not require substantially more time. Moreover, we provide parametrized bounds on the convergence time to near-stable states when the interactions between agents are apriori restricted to a social network. The paper has been accepted for publication in Distributed Computing, a top journal in the area.



New Paper at STACS 2024 13 Dec 2023

Our paper ''Algorithms for Claims Trading'' (by Martin Hoefer, Carmine Ventre, Lisa Wilhelmi) was accepted at the 41st Symposium on Theoretical Aspects of Computer Science (STACS 2024), a leading conference in theoretical computer science.



New Paper in Mathematics of Operations Research 11 Dec 2023

In our paper ''Flow Allocation Games'' (by Nils Bertschinger, Martin Hoefer, Daniel Schmand) we study a game-theoretic model for clearing in financial networks. Network clearing requires that banks determine if they have enough assets to clear their debt -- and if not, which debt contract is cleared to which extent. Naturally, each bank has an incentive to maximize the debt that is cleared. This represents a natural network circulation problem, in which a node allocates flow to outgoing capacitated edges in order to maximize the amount of flow circulating through the node. We study a game-theoretic version of this problem and characterize the existence and computational complexity of equilibria. Our results reveal an interesting dichotomy: If allocation strategies are monotone and ordering-based over individual flow units, then for a variety of social objective functions, there exist optimal equilibria which can also be computed in polynomial time. If allocation strategies are ordering-based over entire edges, equilibria can be absent or very hard to compute. The paper has been accepted for publication in Mathematics of Operations Research, a leading journal in operations research.