Abstract
In this talk, I will discuss recent progress on combinatorial contracts, where complexity arises in two natural ways: from the many possible combinations of actions an agent may take, and from the many possible compositions of a team of agents whose efforts jointly determine the outcome. I will present several models capturing these scenarios and highlight the algorithmic and complexity questions they raise. The results reveal a rich landscape that includes polynomial-time algorithms under structured reward functions, approximation guarantees in more general settings, and hardness barriers. Overall, these results illustrate how tools from algorithms and economic theory interact in the study of incentives, and point to a range of open problems at the frontier of algorithms and incentives.
Coffee and tea will be provided to enjoy during the talk.
About the speaker
Michal Feldman is a Professor of Computer Science in the Blavatnik School of Computer Science at Tel Aviv University, where she holds the Chair of Computation and Economics. She is the Chair of ACM SIGecom. She is a Visiting Professor at the Department of Mathematics in London School of Economics, and a Visiting Scholar at Microsoft ILDC. Her research lies in the interface of Computer Science, Game Theory and Economics, where she studies the design and analysis of markets under different types of uncertainty, with an emphasis on efficiency, simplicity, robustness and fairness. She received her Ph.D. from UC Berkeley in 2005. She held a visiting position at Harvard University and Microsoft Research New England (2011-13). She is an Associate Editor in GEB, MOR, FnTML ACM TEAC, and JCSS, and served as the PC chair of ACM EC 2015 and WINE 2021. She is an alumna of the Global Young Academy, and the Israeli Young Academy. She is the recipient of multiple prizes and awards, including ICM Speaker (2026), Weizmann Prize (2025), ACM Fellow (2024), AAIA Fellow (2025), SIGecom Mid-Career (2023), Bruno (2022), Kadar (2022), Amazon Research (2018) and Alon (2008), multiple Rector’s Teaching Awards, and numerous grants, including three ERC grants, ISF Breakthrough, Marie Curie IOF, ISF, and NSF-BSF.
