DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2020.10

Coverage and Vacuity in Network Formation Games

Authors: Gili Bielous and Orna Kupferman

Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)

Abstract

The frameworks of coverage and vacuity in formal verification analyze the effect of mutations applied to systems or their specifications. We adopt these notions to network formation games, analyzing the effect of a change in the cost of a resource. We consider two measures to be affected: the cost of the Social Optimum and extremums of costs of Nash Equilibria. Our results offer a formal framework to the effect of mutations in network formation games and include a complexity analysis of related decision problems. They also tighten the relation between algorithmic game theory and formal verification, suggesting refined definitions of coverage and vacuity for the latter.

Cite as

Gili Bielous and Orna Kupferman. Coverage and Vacuity in Network Formation Games. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bielous_et_al:LIPIcs.CSL.2020.10,
  author =	{Bielous, Gili and Kupferman, Orna},
  title =	{{Coverage and Vacuity in Network Formation Games}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{10:1--10:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Fern\'{a}ndez, Maribel and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.10},
  URN =		{urn:nbn:de:0030-drops-116532},
  doi =		{10.4230/LIPIcs.CSL.2020.10},
  annote =	{Keywords: Network Formation Games, Vacuity, Coverage}
}

Search Results

Documents authored by Bielous, Gili

Coverage and Vacuity in Network Formation Games

Abstract

Cite as

Thanks for your feedback!

Could not send message