Randomized methods in algorithmic mechanism design

• Applicant: Professorin Dr. Britta Peis, since 11/2014
• Subject Area: Theoretical Computer Science
• Term: from 2013 to 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 230665258

• Final Report Year: 2019

Final Report Abstract

Troughout the duration of the project, various impressive results have been established on secretary-type problems with bidders arriving in random order. We were able to find algorithms that handle rather complex settings with close-to-optimal expected outcome. After this great progress regarding the quality of approximation for a variety of complex optimization problems in the random-order model, efforts to extend these results to truthful mechanisms did not succeed for several years. However, just towards the end of the project, we were able to prove that indeed, the eapproximation for weighted bipartite matching in the random-order model can also be achieved via a truthful mechanism.

Publications

• Online optimization in the random order model. PhD thesis
  Klaus Radke
  
• Primal beats dual on online packing LPs in the random-order model. In: Proc. 46th annual ACM Symposium on Theory of Computing (STOC), pp. 303-312 , 2014
  Thomas Kesselheim, Klaus Radke, Andreas Tonnis, Berthold Vöcking
  (See online at https://doi.org/10.1145/2591796.2591810)
• Truthful Mechanism Design via Correlated Tree Rounding. Mathematical Programming, Volume 163, Issue 1–2, pp. 445–469
  Yossi Azar, Martin Hoefer, Idan Maor, Rebecca Reiffenhäuser, Berthold Vöcking
  (See online at https://doi.org/10.1007/s10107-016-1068-5)
• Extensions of secretary problems towards submodular objectives and temporal arrival. PhD thesis
  Andreas Tönnis
  (See online at https://doi.org/10.18154/RWTH-2017-02825)
• Selfishness and Uncertainty - Successful Stratea gies in Algorithmic Game Theory. PhD thesis
  Rebecca Reiffenhäuser
  (See online at https://doi.org/10.18154/RWTH-2018-224989)
• An Optimal Truthful Mechanism for the Online Weighted Bipartite Matching Problem. Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1982-1993, 2019
  Rebecca Reiffenhäuser
  (See online at https://doi.org/10.1137/1.9781611975482.120)