Randomisierte Methoden im algorithmischen Mechanismen-Design

• Antragstellerin: Professorin Dr. Britta Peis, seit 11/2014
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2013 bis 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 230665258

• Erstellungsjahr: 2019

Zusammenfassung der Projektergebnisse

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.

Projektbezogene Publikationen (Auswahl)

• 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
  (Siehe online unter 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
  (Siehe online unter https://doi.org/10.1007/s10107-016-1068-5)
• Extensions of secretary problems towards submodular objectives and temporal arrival. PhD thesis
  Andreas Tönnis
  (Siehe online unter https://doi.org/10.18154/RWTH-2017-02825)
• Selfishness and Uncertainty - Successful Stratea gies in Algorithmic Game Theory. PhD thesis
  Rebecca Reiffenhäuser
  (Siehe online unter 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
  (Siehe online unter https://doi.org/10.1137/1.9781611975482.120)