Switch to German Switch to English


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.

New Paper at AAAI 2024 9 Dec 2023

Our paper ''Information Design for Congestion Games with Unknown Demand'' (by Svenja Griesbach, Martin Hoefer, Max Klimm, Tim Koglin) was accepted at the 38th Conference on Artificial Intelligence (AAAI 2024), one of the two international top conferences in artificial intelligence.

New Paper in Journal of Artificial Intelligence Research 24 Nov 2023

New algorithms to compute market equilibria in the standard Fisher market model are discussed in our new paper ''Competitive Equilibria with a Constant Number of Chores'' (by Jugal Garg, Martin Hoefer, Peter McGlaughlin, Marco Schmalhofer). When agents have piecewise linear utility functions for goods, computing an equilibrium is known to be a hard problem. Interestingly, the addition of a small number of chores in such markets can make the problem of computing an equilibrium easy. The paper has been accepted for publication in the Journal of Artificial Intelligence Research, a top journal in artificial intelligence.

New Paper at NeurIPS 2023 23 Sep 2023

Our paper ''ε-Fractional Core Stability in Hedonic Games'' (by Simone Fioravanti, Michele Flammini, Bojana Kodric, Giovanna Varricchio) was accepted at the 37th Conference on Neural Information Processing Systems (NeurIPS 2023), the international top-conference in machine learning.

Giovanna Varricchio moves to Università della Calabria 15 Sep 2023

Our group member Giovanna Varricchio accepted an offer to become junior assistant professor (RTD-A) at Università della Calabria. Congratulations!

New Paper in SIAM Journal on Discrete Mathematics 4 Sep 2023

The focus of our paper ''Stochastic Probing with Increasing Precision'' (by Martin Hoefer, Kevin Schewior, Daniel Schmand) are algorithms for probing problems, in which we have a number of choice options (e.g., job candidates, investments, vaccination strategies, etc.). Each option has an unknown quality drawn from a known independent distribution. Before we select an option, we can learn about their quality by testing options adaptively. A test shows whether or not the value is above or below the median value of the conditional distribution (based on outcomes of previous tests). We propose and analyze testing algorithms that provide provably near-optimal performance. The paper has been accepted for publication in SIAM Journal of Discrete Mathematics.

Welcome 1 Sep 2023

Our former secretary Marta Soares moved to a new position in HRZ of Goethe University. We thank her for the excellent service, and we wish her all the best!
At the same time, we welcome Teresa Fischer as the new secretary in our group.

Welcome 1 Sep 2023

We welcome Lars Huth as a new member of our group.

Welcome 1 Aug 2023

We welcome Tolga Tel as a new member of our group.

Click here for older news