IMPROVED FIRST PLAYER STRATEGY FOR THE ZERO-SUM SEQUENTIAL UNCROSSING GAME
This paper deals with the known uncrossing zero-sum two-player sequential game, which is employed to obtain upper running time bound for the transformation of an arbitrary subset family of some finite set to an appropriate laminar one. In this game, the first player performs such a transformation, w...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ural Branch of the Russian Academy of Sciences and Ural Federal University named after the first President of Russia B.N.Yeltsin, Krasovskii Institute of Mathematics and Mechanics
2024-07-01
|
| Series: | Ural Mathematical Journal |
| Subjects: | |
| Online Access: | https://umjuran.ru/index.php/umj/article/view/826 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | This paper deals with the known uncrossing zero-sum two-player sequential game, which is employed to obtain upper running time bound for the transformation of an arbitrary subset family of some finite set to an appropriate laminar one. In this game, the first player performs such a transformation, while the second one tries to slow down this process as much as possible. It is known that for any game instance specified by the ground set and initial subset family of size $n$ and $m$ respectively, the first player has a winning strategy of $O(n^4m)$ steps. In this paper, we show that the first player has a more efficient strategy, which helps him (her) to win in $O\bigl(\max\{n^2,mn\}\bigr)$ steps. |
|---|---|
| ISSN: | 2414-3952 |