Switch to German Switch to English


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

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

New Paper at AAAI 2022 01 Dec 2021

Our paper ''Maximizing Nash Social Welfare in 2-Value Instances'' (by Hannaneh Akrami, Bhaskar Ray Chaudhury, Martin Hoefer, Kurt Mehlhorn, Marco Schmalhofer, Golnoosh Shahkarami, Giovanna Varricchio, Quentin Vermande, Ernest van Wijland) was accepted at the 36th AAAI Conference on Artificial Intelligence (AAAI 2022), one of the two international top-conferences in artificial intelligence.

New Paper in Journal of Artificial Intelligence Research 26 Nov 2021

In our paper ''Fair Division of Indivisible Goods for a Class of Concave Valuations'' (by Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, Kurt Mehlhorn) we study approximation algorithms for fair allocation of a set of indivisible goods to a set of agents. Our algorithm computes a near-optimal allocation in terms of the geometric mean (also termed Nash social welfare) of agent valuations. In addition, the allocation satisfies approximate versions of envy-freeness, a standard fairness concept in the literature. Our results unify and extend existing techniques for approximating Nash social welfare for additive valuations to a more general, concave and non-separable class of valuation functions. The paper has been accepted for publication in Journal of Artificial Intelligence Research, a top journal in artificial intelligence.

New Paper in Mathematics of Operations Research 08 Sep 2021

In our paper ''Algorithms for Persuasion with Limited Communication'' (by Ronen Gradwohl, Niklas Hahn, Martin Hoefer, Rann Smorodinsky) we study the problem faced by a recommendation engine (e.g., a website for hotel booking or travel) that wants to persuade a user with a recommendation. We analyze restrictions on the signal space such that there are more potential actions by the user than signals that can be issued for recommendation. For symmetric instances, when a priori all actions have similar profits, we characterize and design efficient algorithms for optimal recommendation schemes for the engine. In a subclass of instances, where profits are independent among actions, we obtain an algorithm that computes a near-optimal scheme. The paper has been accepted for publication in Mathematics of Operations Research, a leading journal in operations research.

Tutorial on Algorithms and Information Design at SAGT 2021 27 Aug 2021

Stay tuned for our tutorial on Algorithmic Challenges in Information Design; on 21 Sep 2021 at SAGT in Aarhus (and online).

New Paper at SAGT 2021 29 Jun 2021

Our paper ''When Dividing Mixed Manna is Easier than Dividing Goods: Competitive Equilibria with a Constant Number of Chores'' (by Jugal Garg, Martin Hoefer, Peter McGlaughlin, Marco Schmalhofer) was accepted at the 14th Int. Symposium on Algorithmic Game Theory (SAGT 2021).

New Paper at IJCAI 2021 29 Apr 2021

Our paper ''Stochastic Probing with Increasing Precision'' (by Martin Hoefer, Kevin Schewior, Daniel Schmand) was accepted at the 30th Int. Joint Conference on Artificial Intelligence (IJCAI 2021), one of the two international top-conferences in artificial intelligence.