Document

APPROX

**Published in:** LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

In this paper we consider the k-server problem where events are generated by selfish agents, known as the selfish k-server problem. In this setting, there is a set of k servers located in some metric space. Selfish agents arrive in an online fashion, each has a request located on some point in the metric space, and seeks to serve his request with the server of minimum distance to the request. If agents choose to serve their request with the nearest server, this mimics the greedy algorithm which has an unbounded competitive ratio. We propose an algorithm that associates a surcharge with each server independently of the agent to arrive (and therefore, yields a truthful online mechanism). An agent chooses to serve his request with the server that minimizes the distance to the request plus the associated surcharge to the server.
This paper extends [Ilan Reuven Cohen et al., 2015], which gave an optimal k-competitive dynamic pricing scheme for the selfish k-server problem on the line. We give a k-competitive dynamic pricing algorithm for the selfish k-server problem on tree metric spaces, which matches the optimal online (non truthful) algorithm. We show that an alpha-competitive dynamic pricing scheme exists on the tree if and only if there exists alpha-competitive online algorithm on the tree that is lazy and monotone. Given this characterization, the main technical difficulty is coming up with such an online algorithm.

Ilan Reuven Cohen, Alon Eden, Amos Fiat, and Łukasz Jeż. Dynamic Pricing of Servers on Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.APPROX-RANDOM.2019.10, author = {Cohen, Ilan Reuven and Eden, Alon and Fiat, Amos and Je\.{z}, {\L}ukasz}, title = {{Dynamic Pricing of Servers on Trees}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {10:1--10:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.10}, URN = {urn:nbn:de:0030-drops-112252}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.10}, annote = {Keywords: Online algorithms, Online mechanisms, k-server problem, Online pricing} }

Document

**Published in:** LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

We give a prompt online mechanism for minimizing the sum of [weighted] completion times. This is the first prompt online algorithm for the problem. When such jobs are strategic agents, delaying scheduling decisions makes little sense. Moreover, the mechanism has a particularly simple form of an anonymous menu of options.

Alon Eden, Michal Feldman, Amos Fiat, and Tzahi Taub. Truthful Prompt Scheduling for Minimizing Sum of Completion Times. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{eden_et_al:LIPIcs.ESA.2018.27, author = {Eden, Alon and Feldman, Michal and Fiat, Amos and Taub, Tzahi}, title = {{Truthful Prompt Scheduling for Minimizing Sum of Completion Times}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {27:1--27:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.27}, URN = {urn:nbn:de:0030-drops-94905}, doi = {10.4230/LIPIcs.ESA.2018.27}, annote = {Keywords: Scheduling, Mechanism design, Online algorithms} }

Document

**Published in:** LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

We consider the online carpool fairness problem of [Fagin and Williams, 1983] in which an online algorithm is presented with a sequence of pairs drawn from a group of n potential drivers. The online algorithm must select one driver from each pair, with the objective of partitioning the driving burden as fairly as possible for all drivers. The unfairness of an online algorithm is a measure of the worst-case deviation between the number of times a person has driven and the number of times they would have driven if life was completely fair.
We introduce a version of the problem in which drivers only carpool with their neighbors in a given social network graph; this is a generalization of the original problem, which corresponds to the social network of the complete graph. We show that for graphs of degree d, the unfairness of deterministic algorithms against adversarial sequences is exactly d/2. For random sequences of edges from planar graph social networks we give a [deterministic] algorithm with logarithmic unfairness (holds more generally for any bounded-genus graph). This does not follow from previous random sequence results in the original model, as we show that restricting the random sequences to sparse social network graphs may increase the unfairness.
A very natural class of randomized online algorithms are so-called static algorithms that preserve the same state distribution over time. Surprisingly, we show that any such algorithm has unfairness ~Theta(sqrt(d)) against oblivious adversaries. This shows that the local random greedy algorithm of [Ajtai et al, 1996] is close to optimal amongst the class of static algorithms. A natural (non-static) algorithm is global random greedy (which acts greedily and breaks ties at random). We improve the lower bound on the competitive ratio from Omega(log^{1/3}(d)) to Omega(log(d)). We also show that the competitive ratio of global random greedy against adaptive adversaries is Omega(d).

Amos Fiat, Anna R. Karlin, Elias Koutsoupias, Claire Mathieu, and Rotem Zach. Carpooling in Social Networks. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 43:1-43:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{fiat_et_al:LIPIcs.ICALP.2016.43, author = {Fiat, Amos and Karlin, Anna R. and Koutsoupias, Elias and Mathieu, Claire and Zach, Rotem}, title = {{Carpooling in Social Networks}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {43:1--43:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.43}, URN = {urn:nbn:de:0030-drops-63234}, doi = {10.4230/LIPIcs.ICALP.2016.43}, annote = {Keywords: Online algorithms, Fairness, Randomized algorithms, Competitive ratio, Carpool problem} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 7261, Fair Division (2007)

As defined by Aumann in 1959, a strong equilibrium is a Nash
equilibrium that is resilient to deviations by coalitions. We give
tight bounds on the strong price of anarchy for load balancing on
related machines. We also give tight bounds for $k$-strong
equilibria, where the size of a deviating coalition is at most
$k$, for unrelated machines.

Amos Fiat, Meital Levy, Haim Kaplan, and Svetlana Olonetsky. Strong Price of Anarchy for Machine Load Balancing. In Fair Division. Dagstuhl Seminar Proceedings, Volume 7261, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{fiat_et_al:DagSemProc.07261.12, author = {Fiat, Amos and Levy, Meital and Kaplan, Haim and Olonetsky, Svetlana}, title = {{Strong Price of Anarchy for Machine Load Balancing}}, booktitle = {Fair Division}, pages = {1--19}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {7261}, editor = {Steven Brams and Kirk Pruhs and Gerhard Woeginger}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07261.12}, URN = {urn:nbn:de:0030-drops-12256}, doi = {10.4230/DagSemProc.07261.12}, annote = {Keywords: Game theory, Strong Nash equilibria, Load balancing, Price of Anarchy} }

Document

**Published in:** Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Susanne Albers, Amos Fiat, and Gerhard J. Woeginger. Online Algorithms (Dagstuhl Seminar 02271). Dagstuhl Seminar Report 347, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{albers_et_al:DagSemRep.347, author = {Albers, Susanne and Fiat, Amos and Woeginger, Gerhard J.}, title = {{Online Algorithms (Dagstuhl Seminar 02271)}}, pages = {1--20}, ISSN = {1619-0203}, year = {2002}, type = {Dagstuhl Seminar Report}, number = {347}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.347}, URN = {urn:nbn:de:0030-drops-152281}, doi = {10.4230/DagSemRep.347}, }

Document

**Published in:** Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Amos Fiat, Anna Karlin, and Gerhard Woeginger. Competitive Algorithms (Dagstuhl Seminar 99251). Dagstuhl Seminar Report 243, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{fiat_et_al:DagSemRep.243, author = {Fiat, Amos and Karlin, Anna and Woeginger, Gerhard}, title = {{Competitive Algorithms (Dagstuhl Seminar 99251)}}, pages = {1--25}, ISSN = {1619-0203}, year = {2000}, type = {Dagstuhl Seminar Report}, number = {243}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.243}, URN = {urn:nbn:de:0030-drops-151295}, doi = {10.4230/DagSemRep.243}, }

Document

**Published in:** Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Amos Fiat and Gerhard Woeginger. On-line Algorithms (Dagstuhl Seminar 9626). Dagstuhl Seminar Report 149, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1996)

Copy BibTex To Clipboard

@TechReport{fiat_et_al:DagSemRep.149, author = {Fiat, Amos and Woeginger, Gerhard}, title = {{On-line Algorithms (Dagstuhl Seminar 9626)}}, pages = {1--25}, ISSN = {1619-0203}, year = {1996}, type = {Dagstuhl Seminar Report}, number = {149}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.149}, URN = {urn:nbn:de:0030-drops-150369}, doi = {10.4230/DagSemRep.149}, }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail