Uniform-machines scheduling: Difference between revisions

Revision as of 00:05, 20 June 2025

Latest revision as of 15:49, 27 August 2025

Line 40:

=== Monotonicity and Truthfulness ===

In some settings, the machine speed is the machine's private information, and we want to incentivize machines to reveal their true speed, that is, we want a [[truthful mechanism]]. An important consideration for attaining truthfulness is ''monotonicity''.<ref>{{Cite book|last1=Archer|first1=A.|last2=Tardos|first2=E.|title=Proceedings 42nd IEEE Symposium on Foundations of Computer Science |chapter=Truthful mechanisms for one-parameter agents |date=2001-10-01|chapter-url=https://ieeexplore.ieee.org/document/959924|pages=482–491|doi=10.1109/SFCS.2001.959924|isbn=0-7695-1390-5 |s2cid=11377808 }}</ref> It means that, if a machine reports a higher speed, and all other inputs remain the same, then the total processing time allocated to the machine weakly increases. For this problem:

* '''Auletta, De Prisco, Penna and Persiano'''<ref>{{Cite book|last1=Auletta|first1=Vincenzo|last2=De Prisco|first2=Roberto|last3=Penna|first3=Paolo|last4=Persiano|first4=Giuseppe|title=Stacs 2004 |chapter=Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines |date=2004|editor-last=Diekert|editor-first=Volker|editor2-last=Habib|editor2-first=Michel|chapter-url=https://link.springer.com/chapter/10.1007/978-3-540-24749-4_53|series=Lecture Notes in Computer Science|volume=2996 |language=en|___location=Berlin, Heidelberg|publisher=Springer|pages=608–619|doi=10.1007/978-3-540-24749-4_53|isbn=978-3-540-24749-4}}</ref> presented a 4-approximation monotone algorithm, which runs in polytime when the number of machines is fixed.