An \(O(n)\)-round strategy for the Magnus-Derek game
type: Item
instance of: scholarly article
title: An \(O(n)\)-round strategy for the Magnus-Derek game
zbMATH Open document ID: 1461.91073
author: Zhivko Nedev
published in: Algorithms
publication date: 2018-08-20T00:00:00Z
review text: Summary: We analyze further the \textit{Magnus-Derek} game, a two-player game played on a round table with \(n\) positions. The players jointly control the movement of a token. One player, Magnus, aims to maximize the number of positions visited while minimizing the number of rounds. The other player, Derek, attempts to minimize the number of visited positions. We present a new strategy for Magnus that succeeds in visiting the maximal number of positions in \(3(n-1)\) rounds, which is the optimal number of rounds up to a constant factor.
Mathematics Subject Classification ID: 91A46
Mathematics Subject Classification ID: 68R05
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 91A05
zbMATH DE Number: 6920523
zbMATH Keywords: algorithmic game theory
zbMATH Keywords: additive combinatorics
zbMATH Keywords: combinatorial games
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a3030244
OpenAlex ID: W2164222717
cites work: The Magnus-Derek game
cites work: Q3629003
cites work: The c game revisited
cites work: BALANCED SETS AND THE VECTOR GAME
cites work: An algorithm for finding a nearly minimal balanced set in 𝔽_{𝕡}
cites work: The On-Line Encyclopedia of Integer Sequences
cites work: On the Addition of Residue Classes
DOI: 10.3390/A3030244
description: scientific article; zbMATH DE number 6920523