DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2022.12

Grabbing Olives on Linear Pizzas and Pissaladières

Authors: Jean-Claude Bermond, Frédéric Havet, and Michel Cosnard

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract

In this paper we revisit the problem entitled Sharing a Pizza stated by P. Winkler by considering a new puzzle called Sharing a Pissaladiere. The game is played by two polite coatis Alice and Bob who share a pissaladière (a p×q grid) which is divided into rectangular slices. Alice starts in a corner and then the coatis alternate removing a remaining slice adjacent to at most two other slices. On some slices there are precious olives of Nice and the aim of each coati is to grab the maximum number of olives. We first study the particular case of 1×n grid (i.e. a path) where the game is a graph grabbing game known as Sharing a linear pizza. In that case each player can take only an end vertex of the remaining path. These problems are particular cases of a new class of games called d-degenerate games played on a graph with non negative weights assigned to the vertices with the rule that coatis alternatively take a vertex of degree at most d. Our main results are the following. We give optimal strategies for paths (linear pizzas) with no two adjacent weighty vertices. We also give a recurrence formula to compute the gains which depend only on the parity of n and of the respective parities of weighty vertices with a complexity in O(h²) where h denotes the number of parity changes in the weighty vertices. When the weights are only {0,1} we reduce the computation of the average number of olives collected by each player to a word counting problem. We solve Sharing a pissaladière with {0,1} weights, when there is one olive or 2 olives. In that case Alice (resp. Bob) grabs almost all the olives if the number of vertices of the grid n = p×q is odd (resp. even). We prove that for a 2×q grid with a fixed number k of olives Bob grabs at least ⌈(k-1)/3⌉ olives and almost always grabs all the k olives.

Cite as

Jean-Claude Bermond, Frédéric Havet, and Michel Cosnard. Grabbing Olives on Linear Pizzas and Pissaladières. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bermond_et_al:LIPIcs.FUN.2022.12,
  author =	{Bermond, Jean-Claude and Havet, Fr\'{e}d\'{e}ric and Cosnard, Michel},
  title =	{{Grabbing Olives on Linear Pizzas and Pissaladi\`{e}res}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{12:1--12:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.12},
  URN =		{urn:nbn:de:0030-drops-159826},
  doi =		{10.4230/LIPIcs.FUN.2022.12},
  annote =	{Keywords: Grabbing game, degenerate graph, path, grid}
}

Document

DOI: 10.4230/LIPIcs.FUN.2018.6

How long does it take for all users in a social network to choose their communities?

Authors: Jean-Claude Bermond, Augustin Chaintreau, Guillaume Ducoffe, and Dorian Mazauric

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

Abstract

We consider a community formation problem in social networks, where the users are either friends or enemies. The users are partitioned into conflict-free groups (i.e., independent sets in the conflict graph G^- =(V,E) that represents the enmities between users). The dynamics goes on as long as there exists any set of at most k users, k being any fixed parameter, that can change their current groups in the partition simultaneously, in such a way that they all strictly increase their utilities (number of friends i.e., the cardinality of their respective groups minus one). Previously, the best-known upper-bounds on the maximum time of convergence were O(|V|alpha(G^-)) for k <= 2 and O(|V|^3) for k=3, with alpha(G^-) being the independence number of G^-. Our first contribution in this paper consists in reinterpreting the initial problem as the study of a dominance ordering over the vectors of integer partitions. With this approach, we obtain for k <= 2 the tight upper-bound O(|V| min {alpha(G^-), sqrt{|V|}}) and, when G^- is the empty graph, the exact value of order ((2|V|)^{3/2})/3. The time of convergence, for any fixed k >= 4, was conjectured to be polynomial [Escoffier et al., 2012][Kleinberg and Ligett, 2013]. In this paper we disprove this. Specifically, we prove that for any k >= 4, the maximum time of convergence is an Omega(|V|^{Theta(log{|V|})}).

Cite as

Jean-Claude Bermond, Augustin Chaintreau, Guillaume Ducoffe, and Dorian Mazauric. How long does it take for all users in a social network to choose their communities?. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 6:1-6:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bermond_et_al:LIPIcs.FUN.2018.6,
  author =	{Bermond, Jean-Claude and Chaintreau, Augustin and Ducoffe, Guillaume and Mazauric, Dorian},
  title =	{{How long does it take for all users in a social network to choose their communities?}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{6:1--6:21},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.6},
  URN =		{urn:nbn:de:0030-drops-87972},
  doi =		{10.4230/LIPIcs.FUN.2018.6},
  annote =	{Keywords: communities, social networks, integer partitions, coloring games, graphs}
}

Search Results

Documents authored by Bermond, Jean-Claude

Grabbing Olives on Linear Pizzas and Pissaladières

Abstract

Cite as

How long does it take for all users in a social network to choose their communities?

Abstract

Cite as

Thanks for your feedback!

Could not send message