Online computational platforms that directly engage with users must account for the strategic behavior of self-interested individuals. The goal of mechanism design is to optimize an objective, such as efficiency or revenue, in such scenarios, i.e., when the agents that participate in the mechanisms act strategically. In many fundamental computational settings the theoretical optimal mechanisms are highly complex and thus are not practical. In this talk I will discuss the tradeoff between the complexity of mechanisms and their performance, illustrated on the fundamental problem of profit maximization when selling multiple goods. Optimal mechanisms for this problem are highly complex. Nevertheless, I will present a simple deterministic mechanism that guarantees a constant percentage of the optimal revenue. I will then present results regarding the complexity of mechanisms that are almost optimal, and regarding the tradeoff between performance and complexity for this problem.
Moshe Babaioff is a Senior Principal Researcher at Microsoft Research, located in Israel. His research focuses on establishing rigorous theoretical foundations of solutions to real-world problems in the intersection of Economics and Computation (EC), using tools and approaches from Computer Science, Game Theory, and Microeconomic Theory. Moshe has served on multiple leadership positions at the EC community, including serving as Program co-Chair of ACM-EC 2017, as General Chair of ACM-EC 2014, and as co-chair of the Economics, Monetization, and Online Markets Track of The Web Conference (2023).
Moshe has been at Microsoft Research (MSR) for 15 years, first at MSR Silicon Valley lab (2007-2014) and then at MSR in Israel (since 2014). Before joining MSR he was a postdoctoral scholar at the University of California, Berkeley. He received his PhD in Computer Science from the Hebrew University in Jerusalem.