9 Search Results for "Fiat, Amos"


Document
Track A: Algorithms, Complexity and Games
Truthful Matching with Online Items and Offline Agents

Authors: Michal Feldman, Federico Fusco, Simon Mauras, and Rebecca Reiffenhäuser

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)


Abstract
We study truthful mechanisms for welfare maximization in online bipartite matching. In our (multi-parameter) setting, every buyer is associated with a (possibly private) desired set of items, and has a private value for being assigned an item in her desired set. Unlike most online matching settings, where agents arrive online, in our setting the items arrive online in an adversarial order while the buyers are present for the entire duration of the process. This poses a significant challenge to the design of truthful mechanisms, due to the ability of buyers to strategize over future rounds. We provide an almost full picture of the competitive ratios in different scenarios, including myopic vs. non-myopic agents, tardy vs. prompt payments, and private vs. public desired sets. Among other results, we identify the frontier up to which the celebrated e/(e-1) competitive ratio for the vertex-weighted online matching of Karp, Vazirani and Vazirani extends to truthful agents and online items.

Cite as

Michal Feldman, Federico Fusco, Simon Mauras, and Rebecca Reiffenhäuser. Truthful Matching with Online Items and Offline Agents. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 58:1-58:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{feldman_et_al:LIPIcs.ICALP.2023.58,
  author =	{Feldman, Michal and Fusco, Federico and Mauras, Simon and Reiffenh\"{a}user, Rebecca},
  title =	{{Truthful Matching with Online Items and Offline Agents}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{58:1--58:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.58},
  URN =		{urn:nbn:de:0030-drops-181106},
  doi =		{10.4230/LIPIcs.ICALP.2023.58},
  annote =	{Keywords: Online matching, Karp-Vazirani-Vazirani, truthfulness}
}
Document
APPROX
Max-Min Greedy Matching

Authors: Alon Eden, Uriel Feige, and Michal Feldman

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


Abstract
A bipartite graph G(U,V;E) that admits a perfect matching is given. One player imposes a permutation pi over V, the other player imposes a permutation sigma over U. In the greedy matching algorithm, vertices of U arrive in order sigma and each vertex is matched to the highest (under pi) yet unmatched neighbor in V (or left unmatched, if all its neighbors are already matched). The obtained matching is maximal, thus matches at least a half of the vertices. The max-min greedy matching problem asks: suppose the first (max) player reveals pi, and the second (min) player responds with the worst possible sigma for pi, does there exist a permutation pi ensuring to match strictly more than a half of the vertices? Can such a permutation be computed in polynomial time? The main result of this paper is an affirmative answer for these questions: we show that there exists a polytime algorithm to compute pi for which for every sigma at least rho > 0.51 fraction of the vertices of V are matched. We provide additional lower and upper bounds for special families of graphs, including regular and Hamiltonian graphs. Our solution solves an open problem regarding the welfare guarantees attainable by pricing in sequential markets with binary unit-demand valuations.

Cite as

Alon Eden, Uriel Feige, and Michal Feldman. Max-Min Greedy Matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{eden_et_al:LIPIcs.APPROX-RANDOM.2019.7,
  author =	{Eden, Alon and Feige, Uriel and Feldman, Michal},
  title =	{{Max-Min Greedy Matching}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{7:1--7:23},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.7},
  URN =		{urn:nbn:de:0030-drops-112229},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.7},
  annote =	{Keywords: Online matching, Pricing mechanism, Markets}
}
Document
APPROX
Dynamic Pricing of Servers on Trees

Authors: Ilan Reuven Cohen, Alon Eden, Amos Fiat, and Łukasz Jeż

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


Abstract
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.

Cite as

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-dev.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
Truthful Prompt Scheduling for Minimizing Sum of Completion Times

Authors: Alon Eden, Michal Feldman, Amos Fiat, and Tzahi Taub

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


Abstract
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.

Cite as

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-dev.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
Carpooling in Social Networks

Authors: Amos Fiat, Anna R. Karlin, Elias Koutsoupias, Claire Mathieu, and Rotem Zach

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


Abstract
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).

Cite as

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-dev.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
Strong Price of Anarchy for Machine Load Balancing

Authors: Amos Fiat, Meital Levy, Haim Kaplan, and Svetlana Olonetsky

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


Abstract
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.

Cite as

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-dev.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
Online Algorithms (Dagstuhl Seminar 02271)

Authors: Susanne Albers, Amos Fiat, and Gerhard J. Woeginger

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


Abstract

Cite as

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-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.347},
  URN =		{urn:nbn:de:0030-drops-152281},
  doi =		{10.4230/DagSemRep.347},
}
Document
Competitive Algorithms (Dagstuhl Seminar 99251)

Authors: Amos Fiat, Anna Karlin, and Gerhard Woeginger

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


Abstract

Cite as

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-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.243},
  URN =		{urn:nbn:de:0030-drops-151295},
  doi =		{10.4230/DagSemRep.243},
}
Document
On-line Algorithms (Dagstuhl Seminar 9626)

Authors: Amos Fiat and Gerhard Woeginger

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


Abstract

Cite as

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-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.149},
  URN =		{urn:nbn:de:0030-drops-150369},
  doi =		{10.4230/DagSemRep.149},
}
  • Refine by Author
  • 7 Fiat, Amos
  • 3 Eden, Alon
  • 3 Feldman, Michal
  • 2 Woeginger, Gerhard
  • 1 Albers, Susanne
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Algorithmic mechanism design
  • 2 Theory of computation → Online algorithms
  • 1 Applied computing → Online auctions
  • 1 Mathematics of computing → Matchings and factors
  • 1 Theory of computation → Computational pricing and auctions
  • Show More...

  • Refine by Keyword
  • 3 Online algorithms
  • 2 Online matching
  • 1 Carpool problem
  • 1 Competitive ratio
  • 1 Fairness
  • Show More...

  • Refine by Type
  • 9 document

  • Refine by Publication Year
  • 2 2019
  • 1 1996
  • 1 2000
  • 1 2002
  • 1 2007
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail