7 Search Results for "Durfee, Edmund H."

Document
DOI: 10.4230/LIPIcs.MFCS.2025.21
On the Performance of Mildly Greedy Players in k-Coloring Games

Authors: Vittorio Bilò, Andrea D'Ascenzo, Mattia D'Emidio, and Giuseppe F. Italiano

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We study the performance of mildly greedy players in k-coloring games, a relevant subclass of anti-coordination games. A mildly greedy player is a selfish agent who is willing to deviate from a certain strategy profile only if her payoff improves by a factor of more than ε, for some given ε ≥ 0. In presence of mildly greedy players, stability is captured by the concept of (1+ε)-approximate Nash equilibrium. In this paper, we first show that, for any k-coloring game, the (1+ε)-approximate price of anarchy, i.e., the price of anarchy of (1+ε)-approximate pure Nash equilibria, is at least (k-1)/((k-1)ε +k), and that this bound is tight for any ε ≥ 0. Then, we evaluate the approximation ratio of the solutions achieved after a (1 + ϵ)-approximate one-round walk starting from any initial strategy profile, where a (1 + ϵ)-approximate one-round walk is a sequence of (1 + ε)-approximate best-responses, one for each player. We provide a lower bound of min{(k-2)/k, (k-1)/((k-1)ε+k)} on this ratio, for any ε ≥ 0 and k ≥ 5; for the cases of k = 3 and k = 4, we give finer bounds depending on ε. Our work generalizes the results known for cut games, the special case of k-coloring games restricted to k = 2.
Cite as

Vittorio Bilò, Andrea D'Ascenzo, Mattia D'Emidio, and Giuseppe F. Italiano. On the Performance of Mildly Greedy Players in k-Coloring Games. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 21:1-21:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.MFCS.2025.21,
  author =	{Bil\`{o}, Vittorio and D'Ascenzo, Andrea and D'Emidio, Mattia and Italiano, Giuseppe F.},
  title =	{{On the Performance of Mildly Greedy Players in k-Coloring Games}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{21:1--21:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.21},
  URN =		{urn:nbn:de:0030-drops-241287},
  doi =		{10.4230/LIPIcs.MFCS.2025.21},
  annote =	{Keywords: Coloring games, (Approximate) Nash Equilibria, Price of Anarchy}
}
Document
DOI: 10.4230/LITES-v005-i001-a001
Risk-Aware Scheduling of Dual Criticality Job Systems Using Demand Distributions

Authors: Bader Naim Alahmad and Sathish Gopalakrishnan

Published in: LITES, Volume 5, Issue 1 (2018). Leibniz Transactions on Embedded Systems, Volume 5, Issue 1

Abstract
We pose the problem of scheduling Mixed Criticality (MC) job systems when there are only two criticality levels, Lo and Hi -referred to as Dual Criticality job systems- on a single processing platform, when job demands are probabilistic and their distributions are known. The current MC models require that the scheduling policy allocate as little execution time as possible to Lo-criticality jobs if the scenario of execution is of Hi criticality, and drop Lo-criticality jobs entirely as soon as the execution scenario's criticality level can be inferred and is Hi. The work incurred by "incorrectly" scheduling Lo-criticality jobs in cases of Hi realized scenarios might affect the feasibility of Hi criticality jobs; we quantify this work and call it Work Threatening Feasibility (WTF). Our objective is to construct online scheduling policies that minimize the expected WTF for the given instance, and under which the instance is feasible in a probabilistic sense that is consistent with the traditional deterministic definition of MC feasibility. We develop a probabilistic framework for MC scheduling, where feasibility is defined in terms of (chance) constraints on the probabilities that Lo and Hi jobs meet their deadlines. The probabilities are computed over the set of sample paths, or trajectories, induced by executing the policy, and those paths are dependent upon the set of execution scenarios and the given demand distributions. Our goal is to exploit the information provided by job distributions to compute the minimum expected WTF below which the given instance is not feasible in probability, and to compute a (randomized) "efficiently implementable" scheduling policy that realizes the latter quantity. We model the problem as a Constrained Markov Decision Process (CMDP) over a suitable state space and a finite planning horizon, and show that an optimal (non-stationary) Markov randomized scheduling policy exists. We derive an optimal policy by solving a Linear Program (LP). We also carry out quantitative evaluations on select probabilistic MC instances to demonstrate that our approach potentially outperforms current MC scheduling policies.
Cite as

Bader Naim Alahmad and Sathish Gopalakrishnan. Risk-Aware Scheduling of Dual Criticality Job Systems Using Demand Distributions. In LITES, Volume 5, Issue 1 (2018). Leibniz Transactions on Embedded Systems, Volume 5, Issue 1, pp. 01:1-01:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{alahmad_et_al:LITES-v005-i001-a001,
  author =	{Alahmad, Bader Naim and Gopalakrishnan, Sathish},
  title =	{{Risk-Aware Scheduling of Dual Criticality Job Systems Using Demand Distributions}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{01:1--01:30},
  ISSN =	{2199-2002},
  year =	{2018},
  volume =	{5},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v005-i001-a001},
  URN =		{urn:nbn:de:0030-drops-192720},
  doi =		{10.4230/LITES-v005-i001-a001},
  annote =	{Keywords: Mixed criticalities, Probability distribution, Real time systems, Scheduling, Chance constrained Markov decision process, Linear programming, Randomized policy}
}
Document
DOI: 10.4230/DagSemProc.08461.1
08461 Abstracts Collection – Planning in Multiagent Systems

Authors: Jürgen Dix, Edmund H. Durfee, and Cees Witteveen

Published in: Dagstuhl Seminar Proceedings, Volume 8461, Planning in Multiagent Systems (2009)

Abstract
From the 9th of November to the 14th of November 2008 the Dagstuhl Seminar 08461 '`Planning in Multiagent Systems'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Jürgen Dix, Edmund H. Durfee, and Cees Witteveen. 08461 Abstracts Collection – Planning in Multiagent Systems. In Planning in Multiagent Systems. Dagstuhl Seminar Proceedings, Volume 8461, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{dix_et_al:DagSemProc.08461.1,
  author =	{Dix, J\"{u}rgen and Durfee, Edmund H. and Witteveen, Cees},
  title =	{{08461 Abstracts Collection – Planning in Multiagent Systems}},
  booktitle =	{Planning in Multiagent Systems},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8461},
  editor =	{J\"{u}rgen Dix and Edmund H. Durfee and Cees Witteveen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08461.1},
  URN =		{urn:nbn:de:0030-drops-18740},
  doi =		{10.4230/DagSemProc.08461.1},
  annote =	{Keywords: Multi-agent systems, AI-planning, coordination, robustness, temporal planning}
}
Document
DOI: 10.4230/DagSemProc.08461.2
08461 Executive Summary – Planning in Multi-Agent Systems

Authors: Jürgen Dix, Edmund H. Durfee, and Cees Witteveen

Published in: Dagstuhl Seminar Proceedings, Volume 8461, Planning in Multiagent Systems (2009)

Abstract
Planning in Multiagent Systems, or Multiagent Planning (MAP for short), considers the planning problem in the context of multiagent systems. It extends traditional AI planning to domains where multiple agents are involved in a plan and need to act together. Research in multiagent planning is promising for real-world problems: on one hand, AI planning techniques provide powerful tools for solving problems in single agent settings; on the other hand, multiagent systems, which have made significant progress over the past few years, are recognized as a key technology for tackling complex problems in realistic application domains. The motivation for this seminar is thus to bring together researchers working on these different fields in AI planning and multiagent systems to discuss the central topics mentioned above, to identify potential opportunities for coordination, and to develop benchmarks for future research in multiagent planning.
Cite as

Jürgen Dix, Edmund H. Durfee, and Cees Witteveen. 08461 Executive Summary – Planning in Multi-Agent Systems. In Planning in Multiagent Systems. Dagstuhl Seminar Proceedings, Volume 8461, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{dix_et_al:DagSemProc.08461.2,
  author =	{Dix, J\"{u}rgen and Durfee, Edmund H. and Witteveen, Cees},
  title =	{{08461 Executive Summary – Planning in Multi-Agent Systems }},
  booktitle =	{Planning in Multiagent Systems},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8461},
  editor =	{J\"{u}rgen Dix and Edmund H. Durfee and Cees Witteveen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08461.2},
  URN =		{urn:nbn:de:0030-drops-18739},
  doi =		{10.4230/DagSemProc.08461.2},
  annote =	{Keywords: Multi-agent systems, AI-planning, coordination, robustness, temporal planning}
}
Document
DOI: 10.4230/DagSemProc.08461.3
ASODPOP: Making Open DPOP Asynchronous

Authors: Brammert Ottens

Published in: Dagstuhl Seminar Proceedings, Volume 8461, Planning in Multiagent Systems (2009)

Abstract
In this paper we show how ODPOP can be adapted to an asynchronous environment where agents might have to decide their values before the algorithm has ended, giving us Asynchronous ODPOP (ASODPOP). We have compared the algorithm with both ADOPT and distributed local search (DSA). Compared to ADOPT we show that our approach sends fewer messages, converges to a reasonable solution faster, and uses an equal amount of NCCCs. We also show that this convergence is much faster than local search, whilst the solution that local search converges to is far from optimal.
Cite as

Brammert Ottens. ASODPOP: Making Open DPOP Asynchronous. In Planning in Multiagent Systems. Dagstuhl Seminar Proceedings, Volume 8461, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{ottens:DagSemProc.08461.3,
  author =	{Ottens, Brammert},
  title =	{{ASODPOP: Making Open DPOP Asynchronous}},
  booktitle =	{Planning in Multiagent Systems},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8461},
  editor =	{J\"{u}rgen Dix and Edmund H. Durfee and Cees Witteveen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08461.3},
  URN =		{urn:nbn:de:0030-drops-18714},
  doi =		{10.4230/DagSemProc.08461.3},
  annote =	{Keywords: DCOP, Logistics, Planning, Coordination}
}
Document
DOI: 10.4230/DagSemProc.08461.4
Creating incentives to prevent execution failures: an extension of VCG mechanism

Authors: Yingqian Zhang and Mathijs de Weerdt

Published in: Dagstuhl Seminar Proceedings, Volume 8461, Planning in Multiagent Systems (2009)

Abstract
When information or control in a multiagent planning system is private to the agents, they may misreport this information or refuse to execute an agreed outcome, in order to change the resulting end state of such a system to their benefit. In some domains this may result in an execution failure. We show that in such settings VCG mechanisms lose truthfulness, and that the utility of truthful agents can become negative when using VCG payments (i.e., VCG is not strongly individually rational). To deal with this problem, we introduce an extended payment structure which takes into account the actual execution of the promised outcome. We show that this extended mechanism can guarantee a nonnegative utility and is (i) incentive compatible in a Nash equilibrium, and (ii) incentive compatible in dominant strategies if and only if all agents can be verified during execution.
Cite as

Yingqian Zhang and Mathijs de Weerdt. Creating incentives to prevent execution failures: an extension of VCG mechanism. In Planning in Multiagent Systems. Dagstuhl Seminar Proceedings, Volume 8461, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{zhang_et_al:DagSemProc.08461.4,
  author =	{Zhang, Yingqian and de Weerdt, Mathijs},
  title =	{{Creating incentives to prevent execution failures: an extension of VCG mechanism}},
  booktitle =	{Planning in Multiagent Systems},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8461},
  editor =	{J\"{u}rgen Dix and Edmund H. Durfee and Cees Witteveen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08461.4},
  URN =		{urn:nbn:de:0030-drops-18705},
  doi =		{10.4230/DagSemProc.08461.4},
  annote =	{Keywords: Mechanism design, multiagent planning}
}
Document
DOI: 10.4230/DagSemProc.08461.5
Using Options with Set Exercise Prices to Reduce Bidder Exposure in Sequential Auctions

Authors: Lonneke Mous, Valentin Robu, and Han La Poutre

Published in: Dagstuhl Seminar Proceedings, Volume 8461, Planning in Multiagent Systems (2009)

Abstract
The exposure problem appears whenever an agent with complementary valuations bids to acquire a bundle of items sold sequentially, in separate auctions. In this talk, we review a possible solution that can help solve this problem, which involves selling options for the items, instead of the items themselves. We provide a brief overview of the state of the art in this field and discuss, based on our recent results, under which conditions using option mechanisms would be desirable for both buyers and sellers, by comparison to direct auctioning of items. We conclude with a brief discussion of further research directions in this field, as well as the relation to other techniques proposed to address the problem, such as leveled commitment mechanisms.
Cite as

Lonneke Mous, Valentin Robu, and Han La Poutre. Using Options with Set Exercise Prices to Reduce Bidder Exposure in Sequential Auctions. In Planning in Multiagent Systems. Dagstuhl Seminar Proceedings, Volume 8461, pp. 1-35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{mous_et_al:DagSemProc.08461.5,
  author =	{Mous, Lonneke and Robu, Valentin and La Poutre, Han},
  title =	{{Using Options with Set Exercise Prices to Reduce Bidder Exposure in Sequential Auctions}},
  booktitle =	{Planning in Multiagent Systems},
  pages =	{1--35},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8461},
  editor =	{J\"{u}rgen Dix and Edmund H. Durfee and Cees Witteveen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08461.5},
  URN =		{urn:nbn:de:0030-drops-18724},
  doi =		{10.4230/DagSemProc.08461.5},
  annote =	{Keywords: Options, sequential auctions, multi-agent systems, exposure problem, bidding strategies, mechanism design, leveled commitment}
}
  • Refine by Type
  • 7 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2018
  • 5 2009

  • Refine by Author
  • 2 Dix, Jürgen
  • 2 Durfee, Edmund H.
  • 2 Witteveen, Cees
  • 1 Alahmad, Bader Naim
  • 1 Bilò, Vittorio
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 LITES
  • 5 DagSemProc

  • Refine by Classification
  • 1 Mathematics of computing → Graph coloring
  • 1 Mathematics of computing → Markov processes
  • 1 Software and its engineering → Real-time schedulability
  • 1 Software and its engineering → Real-time systems software
  • 1 Theory of computation → Exact and approximate computation of equilibria

  • Refine by Keyword
  • 2 AI-planning
  • 2 Multi-agent systems
  • 2 coordination
  • 2 robustness
  • 2 temporal planning
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact