4 Search Results for "Tamir, Tami"

Document
DOI: 10.4230/LIPIcs.FUN.2018.32
The Power of One Secret Agent

Authors: Tami Tamir

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
I am a job. In job-scheduling applications, my friends and I are assigned to machines that can process us. In the last decade, thanks to our strong employee committee, and the rise of algorithmic game theory, we are getting more and more freedom regarding our assignment. Each of us acts to minimize his own cost, rather than to optimize a global objective. My goal is different. I am a secret agent operated by the system. I do my best to lead my fellow jobs to an outcome with a high social cost. My naive friends keep doing the best they can, each of them performs his best-response move whenever he gets the opportunity to do so. Luckily, I am a charismatic guy. I can determine the order according to which the naive jobs perform their best-response moves. In this paper, I analyze my power, formalized as the Price of a Traitor (PoT), in cost-sharing scheduling games - in which we need to cover the cost of the machines that process us. Starting from an initial Nash Equilibrium (NE) profile, I join the instance and hurt its stability. A sequence of best-response moves is performed until I vanish, leaving the naive jobs in a new NE. For an initial NE assignment, S_0, the PoT measures the ratio between the social cost of a worst NE I can lead the jobs to, starting from S_0, and the social cost of S_0. The PoT of a game is the maximal such ratio among all game instances and initial NE assignments. My analysis distinguishes between instances with unit- and arbitrary-cost machines, and instances with unit- and arbitrary-length jobs. I give exact bounds on the PoT for each setting, in general and in symmetric games. While it turns out that in most settings my power is really impressive, my task is computationally hard (and also hard to approximate).
Cite as

Tami Tamir. The Power of One Secret Agent. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{tamir:LIPIcs.FUN.2018.32,
  author =	{Tamir, Tami},
  title =	{{The Power of One Secret Agent}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{32:1--32:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.32},
  URN =		{urn:nbn:de:0030-drops-88237},
  doi =		{10.4230/LIPIcs.FUN.2018.32},
  annote =	{Keywords: Job scheduling games, Cost sharing, Equilibrium inefficiency}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2015.365
Congestion Games with Multisets of Resources and Applications in Synthesis

Authors: Guy Avni, Orna Kupferman, and Tami Tamir

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Abstract
In classical congestion games, players' strategies are subsets of resources. We introduce and study multiset congestion games, where players' strategies are multisets of resources. Thus, in each strategy a player may need to use each resource a different number of times, and his cost for using the resource depends on the load that he and the other players generate on the resource. Beyond the theoretical interest in examining the effect of a repeated use of resources, our study enables better understanding of non-cooperative systems and environments whose behavior is not covered by previously studied models. Indeed, congestion games with multiset-strategies arise, for example, in production planing and network formation with tasks that are more involved than reachability. We study in detail the application of synthesis from component libraries: different users synthesize systems by gluing together components from a component library. A component may be used in several systems and may be used several times in a system. The performance of a component and hence the system's quality depends on the load on it. Our results reveal how the richer setting of multisets congestion games affects the stability and equilibrium efficiency compared to standard congestion games. In particular, while we present very simple instances with no pure Nash equilibrium and prove tighter and simpler lower bounds for equilibrium inefficiency, we are also able to show that some of the positive results known for affine and weighted congestion games apply to the richer setting of multisets.
Cite as

Guy Avni, Orna Kupferman, and Tami Tamir. Congestion Games with Multisets of Resources and Applications in Synthesis. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 365-379, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{avni_et_al:LIPIcs.FSTTCS.2015.365,
  author =	{Avni, Guy and Kupferman, Orna and Tamir, Tami},
  title =	{{Congestion Games with Multisets of Resources and Applications in Synthesis}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{365--379},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.365},
  URN =		{urn:nbn:de:0030-drops-56358},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.365},
  annote =	{Keywords: Congestion games, Multiset strategies, Equilibrium existence and computation, Equilibrium inefficiency}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2014.33
Properties and Utilization of Capacitated Automata (Invited Talk)

Authors: Orna Kupferman and Tami Tamir

Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Abstract
We study capacitated automata(CAs), where transitions correspond to resources and may have bounded capacities. Each transition in a CA is associated with a (possibly infinite) bound on the number of times it may be traversed. We study CAs from two points of view. The first is that of traditional automata theory, where we view CAs as recognizers of formal languages and examine their expressive power, succinctness, and determinization. The second is that of resource-allocation theory, where we view CAs as a rich description of a flow network and study their utilization.
Cite as

Orna Kupferman and Tami Tamir. Properties and Utilization of Capacitated Automata (Invited Talk). In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 33-44, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{kupferman_et_al:LIPIcs.FSTTCS.2014.33,
  author =	{Kupferman, Orna and Tamir, Tami},
  title =	{{Properties and Utilization of Capacitated Automata}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{33--44},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Raman, Venkatesh and Suresh, S. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.33},
  URN =		{urn:nbn:de:0030-drops-48306},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.33},
  annote =	{Keywords: Automata, Capacitated transitions, Determinization, Maximum utilization}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2010.169
Minimizing Busy Time in Multiple Machine Real-time Scheduling

Authors: Rohit Khandekar, Baruch Schieber, Hadas Shachnai, and Tami Tamir

Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

Abstract
We consider the following fundamental scheduling problem. The input consists of $n$ jobs to be scheduled on a set of machines of bounded capacities. Each job is associated with a release time, a due date, a processing time and demand for machine capacity. The goal is to schedule all of the jobs non-preemptively in their release-time-deadline windows, subject to machine capacity constraints, such that the total busy time of the machines is minimized. Our problem has important applications in power-aware scheduling, optical network design and unit commitment in power systems. Scheduling to minimize busy times is APX-hard already in the special case where all jobs have the same (unit) processing times and can be scheduled in a fixed time interval. Our main result is a $5$-approximation algorithm for general instances. We extend this result to obtain an algorithm with the same approximation ratio for the problem of scheduling moldable jobs, that requires also to determine, for each job, one of several processing-time vs. demand configurations. Better bounds and exact algorithms are derived for several special cases, including proper interval graphs, intervals forming a clique and laminar families of intervals.
Cite as

Rohit Khandekar, Baruch Schieber, Hadas Shachnai, and Tami Tamir. Minimizing Busy Time in Multiple Machine Real-time Scheduling. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 169-180, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{khandekar_et_al:LIPIcs.FSTTCS.2010.169,
  author =	{Khandekar, Rohit and Schieber, Baruch and Shachnai, Hadas and Tamir, Tami},
  title =	{{Minimizing Busy Time in Multiple Machine Real-time Scheduling}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{169--180},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Lodaya, Kamal and Mahajan, Meena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.169},
  URN =		{urn:nbn:de:0030-drops-28909},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.169},
  annote =	{Keywords: real-time scheduling, busy time, preemption, approximation algorithm}
}
  • Refine by Author
  • 4 Tamir, Tami
  • 2 Kupferman, Orna
  • 1 Avni, Guy
  • 1 Khandekar, Rohit
  • 1 Schieber, Baruch
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Algorithmic game theory

  • Refine by Keyword
  • 2 Equilibrium inefficiency
  • 1 Automata
  • 1 Capacitated transitions
  • 1 Congestion games
  • 1 Cost sharing
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2010
  • 1 2014
  • 1 2015
  • 1 2018

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact