A note on concurrent graph sharing games

MaRDI QIDQ2830435zbMATH OpenFDO

Authors Steven Chaplick, Piotr Micek, Torsten Ueckerdt, Veit Wiechert

Publication date 28 October 2016

Published in Integers (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.1021, http://www.emis.de/journals/INTEGERS/papers/qg1/qg1.Abstract.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) 2-person games (91A05) Games involving graphs (91A43)

Abstract: In the concurrent graph sharing game, two players, called First and Second, share the vertices of a connected graph with positive vertex-weights summing up to $1$ as follows. The game begins with First taking any vertex. In each proceeding round, the player with the smaller sum of collected weights so far chooses a non-taken vertex adjacent to a vertex which has been taken, i.e., the set of all taken vertices remains connected and one new vertex is taken in every round. (It is assumed that no two subsets of vertices have the same sum of weights.) One can imagine the players consume their taken vertex over a time proportional to its weight, before choosing a next vertex. In this note we show that First has a strategy to guarantee vertices of weight at least $1/3$ regardless of the graph and how it is weighted. This is best-possible already when the graph is a cycle. Moreover, if the graph is a tree First can guarantee vertices of weight at least $1/2$, which is clearly best-possible.

Recommendations

• Graph sharing games: complexity and connectivity
• Graph sharing games: complexity and connectivity
• Parity in graph sharing games
• Distributed algorithms for aggregative games on graphs
• Coordination games on graphs (extended abstract)
• Graph sharing game and the structure of weighted graphs with a forbidden subdivision
• On concurrent games with payoff
• scientific article; zbMATH DE number 4180791
• Coordination games on graphs

Cited in

(11)

• A general theory of sharing graphs
• The graph grabbing game on \(K_{m, n}\)-trees
• Graph grabbing game on totally-weighted graphs
• Convex grabbing game of the point set on the plane
• Playing weighted Tron on trees
• Graph sharing games: complexity and connectivity
• Graph sharing games: complexity and connectivity
• Parity in graph sharing games
• Graph sharing game and the structure of weighted graphs with a forbidden subdivision
• Graph grabbing game on graphs with forbidden subgraphs
• The graph grabbing game on blow-ups of trees and cycles

This page was built for publication: A note on concurrent graph sharing games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2830435)