Joachim Stadel

Bounds for Monotone Algorithms

Mechanism Design, Monotone Algorithms and Bounds for Monotone Scheduling Algorithms

• Broschiertes Buch

Produktbeschreibung

In the first part "Mechanism Design and Monotone Algorithms", the motivating question is whether the results on truthful mechanisms in Archer and Tardos' paper "Truthful Mechanisms for One-Parameter Agents" are basically a rediscovery of those Myerson introduces in his paper "Optimal Auction Design". To answer that question, we reveal similarities and differences of both papers and give alternative proofs of the main result to underline the correlation of the approaches. The first part also provides the background for the second part "Bounds for Monotone Scheduling Algorithms". Here, we consider monotone algorithms in the context of scheduling problems. We develop a general model to find lower bounds for a certain scheduling problem. In a related matter, we classify monotone algorithms for the deterministic, randomized and online case and prove lower bounds for these algorithms.

Produktdetails

• Verlag: VDM Verlag Dr. Müller
• Seitenzahl: 96
• Englisch
• ISBN-13: 9783639239935
• ISBN-10: 3639239938
• Artikelnr.: 28950604

Autorenporträt

After his studies in applied mathematics in Kaiserslautern, Germany and Auckland, New Zealand, the author worked on analyzing truthful mechanisms, a specific topic in mechanism design, which provides the framework for this book.