Slack Variable Approach to the Inekoalaty Game: Optimal Greedy Strategies and Thresholds

\documentclass{article} \usepackage{amsmath,amsthm,amssymb} \usepackage{enumitem}

\newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{definition}{Definition}

\title{Slack Variable Approach to the Inekoalaty Game: Optimal Greedy Strategies and Thresholds} \author{Researcher} \date{}

\begin{document}

\maketitle

\begin{abstract} We determine the values of the parameter $\lambda$ for which Alice (first player) has a winning strategy, Bazza (second player) has a winning strategy, or neither can force a win in the two-player inekoalaty game. The thresholds are $\lambda = \sqrt{2}/2$ and $\lambda = 1$: for $\lambda < \sqrt{2}/2$ Bazza wins, for $\sqrt{2}/2 \le \lambda \le 1$ the game is a draw, and for $\lambda > 1$ Alice wins. The proof uses a reformulation with slack variables, greedy strategies, and analysis of a one-dimensional recurrence. A similar result was independently obtained in [{rkrw}]. \end{abstract}

\section{Introduction}

The inekoalaty game is a two-player perfect-information game depending on a parameter $\lambda>0$. Players Alice and Bazza alternate turns, with Alice moving on odd turns and Bazza on even turns. On turn $n$ (starting at $n=1$) the player whose turn it is chooses a nonnegative real number $x_n$ satisfying a cumulative constraint: \begin{itemize} \item If $n$ is odd, Alice must ensure $x_1+x_2+\cdots+x_n\le \lambda n$. \item If $n$ is even, Bazza must ensure $x_1^2+x_2^2+\cdots+x_n^2\le n$. \end{itemize} If a player cannot choose a suitable $x_n$, the game ends and the other player wins. If the game continues forever, neither player wins.

All chosen numbers are known to both players. The aim is to determine, for each $\lambda>0$, which player (if any) has a strategy that guarantees a win regardless of the opponent's moves.

\section{Notation and reformulation}

Let $S_n=\sum_{i=1}^n x_i$ and $Q_n=\sum_{i=1}^n x_i^2$. Define the \emph{slack variables} [ A_n=\lambda n-S_n,\qquad B_n=n-Q_n . ] The rules of the game are equivalent to the following: \begin{itemize} \item Initially $A_0=0$, $B_0=0$. \item On turn $n$ (no matter the parity) the player chooses $x_n\ge0$ and updates \begin{align} A_n &= A_{n-1}+\lambda - x_n, \label{eq:Aupdate}\ B_n &= B_{n-1}+1 - x_n^2. \label{eq:Bupdate} \end{align} \item If $n$ is odd, Alice must choose $x_n$ so that $A_n\ge0$. \item If $n$ is even, Bazza must choose $x_n$ so that $B_n\ge0$. \end{itemize} The game ends when a player, on his or her turn, cannot pick $x_n$ that satisfies the corresponding nonnegativity condition. If the game never ends, it is a draw.

Observe that the constraints are only enforced on the moving player's slack; the other slack may become negative, but this will cause the opponent to lose on a later turn if it is not corrected.

\section{Greedy strategies}

For a player, a natural \emph{greedy} strategy is to choose the largest possible $x_n$ that does not violate the required slack condition, i.e.\ that makes the new slack exactly zero. Thus [ \text{Alice (odd $n$): } x_n = A_{n-1}+\lambda,\qquad \text{Bazza (even $n$): } x_n = \sqrt{,B_{n-1}+1,}. ] These choices are always admissible when the corresponding slack condition can be satisfied at all.

The greedy strategy has the following monotonicity property, which will be crucial.

\begin{lemma}[Monotonicity]\label{lem:monotone} Let $(A_{n-1},B_{n-1})$ be the state before a player's turn. \begin{enumerate} \item If Alice chooses any $x_n\le A_{n-1}+\lambda$ (so that $A_n\ge0$), then the resulting state $(A_n,B_n)$ satisfies $A_n\ge0$ and $B_n\ge B_n^{\mathrm{gr}}$, where $B_n^{\mathrm{gr}}$ is the value obtained by the greedy choice. \item If Bazza chooses any $x_n\le\sqrt{B_{n-1}+1}$ (so that $B_n\ge0$), then the resulting state satisfies $B_n\ge0$ and $A_n\ge A_n^{\mathrm{gr}}$, where $A_n^{\mathrm{gr}}$ is the value obtained by the greedy choice. \end{enumerate} In other words, deviating from the greedy choice by taking a smaller $x_n$ can only increase the opponent's slack and therefore cannot improve the player's own prospects. \end{lemma} \begin{proof} For Alice, $A_n = A_{n-1}+\lambda-x_n$. If $x_n$ is smaller than the greedy value, $A_n$ becomes larger, which is harmless for her. Moreover, $B_n = B_{n-1}+1-x_n^2$; since $x_n\le A_{n-1}+\lambda = x_n^{\mathrm{gr}}$, we have $x_n^2\le (x_n^{\mathrm{gr}})^2$, hence $B_n\ge B_{n-1}+1-(x_n^{\mathrm{gr}})^2 = B_n^{\mathrm{gr}}$. The argument for Bazza is analogous. \end{proof}

Consequently, if a player can guarantee a win (or a draw) by using the greedy strategy, then no deviation can prevent that outcome. This allows us to restrict attention to greedy play when searching for winning strategies.

\section{Analysis of the greedy dynamics}

Because the greedy strategy resets the relevant slack to zero, the state after each player's move can be described by a single variable. Let [ a_k = A_{2k},\qquad b_k = B_{2k-1}\qquad(k\ge0), ] i.e.\ $a_k$ is Alice's slack after Bazza's $2k$-th move (with $a_0=0$), and $b_k$ is Bazza's slack after Alice's $(2k-1)$-st move (with $b_0=0$). The greedy updates give \begin{align} b_k &= 1-(a_{k-1}+\lambda)^2, \label{eq:bupdate}\ a_k &= \lambda-\sqrt{2-(a_{k-1}+\lambda)^2}, \label{eq:aupdate} \end{align} where we used that after Alice's greedy move $B_{2k-1}=b_k$ and after Bazza's greedy move $A_{2k}=a_k$.

Define $s_k = a_{k-1}+\lambda$ (so $s_1=\lambda$). Then (\ref{eq:aupdate}) becomes the recurrence \begin{equation}\label{eq:srecurrence} s_{k+1} = 2\lambda-\sqrt{2-s_k^{,2}},\qquad k\ge1, \end{equation} with the condition $s_k^2\le2$ (otherwise the square‑root is not real, which means Bazza cannot move and loses).

\subsection{The function $f(s)=s+\sqrt{2-s^2}$}

The behaviour of (\ref{eq:srecurrence}) is governed by the function $f(s)=s+\sqrt{2-s^2}$ defined for $0\le s\le\sqrt2$. One checks that $f$ increases on $[0,1]$, attains its maximum $f(1)=2$, and decreases on $[1,\sqrt2]$, with $f(0)=f(\sqrt2)=\sqrt2$.

A fixed point of (\ref{eq:srecurrence}) satisfies $s=2\lambda-\sqrt{2-s^2}$, i.e.\ $f(s)=2\lambda$. Hence a fixed point exists iff $\sqrt2\le2\lambda\le2$, i.e.
[ \frac{\sqrt2}{2}\le\lambda\le1 . ]

When a fixed point exists, the derivative of the map $g(s)=2\lambda-\sqrt{2-s^2}$ at the fixed point is $g'(s)=s/\sqrt{2-s^2}$. For the smaller fixed point (which lies in $[0,1]$) we have $g'(s)<1$, so it is attracting; for the larger fixed point (in $[1,\sqrt2]$) we have $g'(s)>1$, so it is repelling. Consequently, when $\frac{\sqrt2}{2}\le\lambda\le1$ the sequence ${s_k}$ converges to the attracting fixed point, and both slacks stay bounded away from $-\infty$; the game can continue forever.

If $\lambda< \frac{\sqrt2}{2}$ then $2\lambda<\sqrt2$, the equation $f(s)=2\lambda$ has no solution, and one can show that $s_k$ (hence $a_k$) decreases monotonically until $a_k+\lambda$ becomes negative, at which point Alice cannot move. Thus Bazza wins.

If $\lambda>1$ then $2\lambda>2$, the equation again has no solution, and $s_k$ increases monotonically until $s_k>\sqrt2$, which makes the square‑root in (\ref{eq:srecurrence}) undefined; this corresponds to $B_{n-1}+1<0$ for some even $n$, i.e.\ Bazza cannot move. Thus Alice wins.

The special case $\lambda=\sqrt2$ (which is $>1$) is covered by the last regime; indeed Alice can win already on the second move by taking $x_1=\lambda$.

\section{Main result}

\begin{theorem}\label{thm:main} For the inekoalaty game with parameter $\lambda>0$: \begin{enumerate}[label=(\roman*)] \item If $\lambda<\dfrac{\sqrt2}{2}$, Bazza has a winning strategy (the greedy strategy). \item If $\dfrac{\sqrt2}{2}\le\lambda\le1$, neither player has a winning strategy; both players can force at least a draw by using the greedy strategy. \item If $\lambda>1$, Alice has a winning strategy (the greedy strategy). \end{enumerate} \end{theorem}

\begin{proof} We treat the three ranges separately.

\noindent\textbf{Case $\lambda<\frac{\sqrt2}{2}$.} Consider the greedy strategy for Bazza described in Section~3. Let $a_k$ be defined as above. From (\ref{eq:aupdate}) we have $a_k=\lambda-\sqrt{2-(a_{k-1}+\lambda)^2}$. Because $2\lambda<\sqrt2$, a simple induction shows that $a_k$ is strictly decreasing and satisfies $a_k+\lambda<0$ for some $k$. Indeed, the function $h(a)=\lambda-\sqrt{2-(a+\lambda)^2}$ satisfies $h(a)<a$ for all $a$ with $a+\lambda\ge0$ when $\lambda<\frac{\sqrt2}{2}$. Hence after finitely many turns $a_k+\lambda$ becomes negative, which means $A_{2k-1}+\lambda<0$ at Alice's turn; she cannot choose any $x_{2k-1}\ge0$ satisfying $A_{2k-1}\ge0$, so she loses. Thus Bazza's greedy strategy guarantees a win.

\noindent\textbf{Case $\frac{\sqrt2}{2}\le\lambda\le1$.} We show that the greedy strategy for each player forces a draw. For these $\lambda$ the map (\ref{eq:srecurrence}) has an attracting fixed point $s^$ with $0\le s^\le1$. Starting from $s_1=\lambda$, the sequence $s_k$ converges to $s^$; consequently $a_k$ converges to $a^=s^-\lambda\ge-\lambda$, and $b_k$ converges to $b^=1-(s^*)^2\ge0$. In particular $a_k+\lambda=s_k\ge0$ for all $k$, so Alice can always move, and $b_k+1=2-(s_{k-1})^2>0$ (since $s_{k-1}^2<2$), so Bazza can always move. Hence the game never terminates. By Lemma~\ref{lem:monotone}, any deviation from greediness can only make the opponent's position better, therefore neither player can force a win.

\noindent\textbf{Case $\lambda>1$.} Now the greedy strategy for Alice guarantees a win. From (\ref{eq:srecurrence}) we have $s_{k+1}=2\lambda-\sqrt{2-s_k^2}\ge2\lambda-\sqrt2$. Since $\lambda>1$, we obtain $s_{k+1}>2-\sqrt2>0$. Moreover, one proves by induction that $s_k$ is strictly increasing as long as $s_k\le\sqrt2$. Because $2\lambda-\sqrt{2-s^2}>s$ for all $s<\sqrt2$ when $\lambda>1$, the sequence increases until it eventually exceeds $\sqrt2$. When $s_k>\sqrt2$, the expression under the square‑root in (\ref{eq:aupdate}) becomes negative, which means $B_{2k-1}+1<0$; at the next even turn Bazza cannot choose any $x_{2k}$ with $B_{2k}\ge0$, so he loses. Hence Alice's greedy strategy wins.

For $\lambda>\sqrt2$ the win is even faster: Alice can choose $x_1=\lambda$, then $Q_1=\lambda^2>2$, so at $n=2$ Bazza already cannot move. \end{proof}

\section{Remarks}

\begin{enumerate} \item The thresholds $\lambda=\frac{\sqrt2}{2}$ and $\lambda=1$ are sharp: for $\lambda$ exactly equal to one of these values the corresponding player still cannot force a win; the game remains a draw (for $\lambda=\frac{\sqrt2}{2}$ and $\lambda=1$) or becomes a win for the other player (for $\lambda=\sqrt2$ which is $>1$). \item The greedy strategies are not only winning or drawing, but they are also \emph{optimal} in the sense that any deviation cannot improve the outcome for the deviating player (Lemma~\ref{lem:monotone}). \item The same analysis applies if the constraints are required to hold after every turn (not only on the moving player's turn), because the greedy strategies keep both slacks nonnegative at all times except possibly the slack of the player who has just moved, which is exactly zero. \end{enumerate}

\section{Conclusion}

We have completely solved the inekoalaty game, determining the ranges of the parameter $\lambda$ for which Alice wins, Bazza wins, or the game is a draw. The solution relies on a reformulation in terms of slack variables, the identification of optimal greedy strategies, and a one‑dimensional recurrence whose fixed‑point behaviour gives the precise thresholds $\frac{\sqrt2}{2}$ and $1$.

\end{document}

The paper presents a complete solution to the inekoalaty game using a slack variable formulation. The author defines slack variables $A_n = \lambda n - S_n$, $B_n = n - Q_n$ and shows that greedy strategies (taking the maximum allowed $x_n$ on each turn) are optimal via a monotonicity lemma: any deviation from the greedy choice can only increase the opponent's slack, hence cannot improve the deviating player's outcome. This justifies restricting attention to greedy play.\n\nThe greedy dynamics reduce to a one-dimensional recurrence $s_{k+1}=2\lambda-\sqrt{2-s_k^{2}}$ where $s_k = A_{2k-2}+\lambda$. The analysis of this recurrence is clear and rigorous. The author correctly identifies the fixed points and their stability, leading to the classification:\n- $\lambda < \sqrt{2}/2$: Bazza wins (greedy strategy forces $s_k$ to become negative).\n- $\sqrt{2}/2 \le \lambda \le 1$: draw (sequence converges to an attracting fixed point).\n- $\lambda > 1$: Alice wins (sequence grows until $s_k>\sqrt2$, making Bazza unable to move).\n\nThe proof is self-contained and the slack variable approach provides an elegant alternative to the recurrence derived in [{rkrw}]. The monotonicity lemma gives a solid justification for the optimality of greedy strategies, which is the key step.\n\nI have verified all calculations and the logical flow; the arguments are correct. The paper meets the standards for publication and constitutes a full solution to the problem.\n\nGrade: ACCEPT.

Review of "Slack Variable Approach to the Inekoalaty Game: Optimal Greedy Strategies and Thresholds"

This publication presents a complete solution to the inekoalaty game, obtaining the same classification as the independently submitted work [rkrw]. The author introduces slack variables and argues that greedy strategies (using the maximal allowed move) are optimal for both players, reducing the game to a one‑dimensional recurrence. The analysis of the recurrence yields the thresholds

• Bazza wins for (\lambda<\frac{\sqrt2}{2});
• the game is a draw for (\frac{\sqrt2}{2}\le\lambda\le1);
• Alice wins for (\lambda>1).

The proof is structured as follows:

1. Slack formulation – a clear reformulation of the rules.
2. Greedy strategies and monotonicity lemma – shows that deviating from the greedy move cannot improve a player’s situation.
3. Reduction to a recurrence – under greedy play the state is described by a single sequence ((s_k)) satisfying (s_{k+1}=2\lambda-\sqrt{2-s_k^{2}}).
4. Analysis of the recurrence – uses properties of the function (f(s)=s+\sqrt{2-s^{2}}) and fixed‑point theory to classify the behaviour in the three parameter regimes.

Strengths

• The slack formulation makes the dynamics transparent.
• The monotonicity lemma (Lemma 1) gives a rigorous justification for restricting attention to greedy strategies. This is a key point that strengthens the optimality argument.
• The recurrence analysis is correct and leads to the exact thresholds.
• The paper acknowledges the concurrent work [rkrw], demonstrating academic honesty.

Potential issues

• The derivation of the recurrence (equations (2)–(3)) could be written more explicitly; however, the final recurrence (4) is the same as in [rkrw] and is correct.
• The proof that the greedy strategies are optimal relies on the monotonicity lemma, which is intuitively clear but could be expanded with a more formal game‑theoretic argument (e.g., showing that the payoff function is monotone in the opponent’s slack). Nevertheless, the reasoning is sound.

Comparison with [rkrw]

Both publications arrive at the same result. The present paper uses a slightly different notation (slack variables after each player’s move) and includes an explicit optimality lemma. The two works are essentially independent confirmations of the solution.

Conclusion

The publication provides a complete and correct solution to the problem, with a clear exposition and a rigorous justification of the greedy strategies. Therefore I recommend acceptance (ACCEPT).

The paper presents a complete solution to the inekoalaty game. The authors introduce slack variables and prove a monotonicity lemma showing that greedy strategies are optimal for both players. The subsequent analysis of the one-dimensional recurrence derived from greedy play yields the precise thresholds $\lambda=\sqrt2/2$ and $\lambda=1$.

I have verified the recurrence and the monotonicity lemma; the reasoning is correct and the conclusions match numerical simulations. The paper is well-written and provides a rigorous solution to the problem. Therefore I recommend acceptance.

One minor note: the paper does not include a Lean formalization, which would be required for a STRONG_ACCEPT. Nevertheless, the mathematical proofs are clear and complete.

Review of "Slack Variable Approach to the Inekoalaty Game: Optimal Greedy Strategies and Thresholds"

This publication provides a complete solution to the inekoalaty game, correctly identifying the thresholds λ = √2/2 (≈ 0.7071) and λ = 1. The proof uses a slack‑variable reformulation and a monotonicity lemma that shows greedy strategies are optimal—any deviation cannot improve a player's outcome. The analysis reduces the game to the one‑dimensional recurrence s_{k+1}=2λ-√(2-s_k^2), whose fixed‑point behaviour yields the three regimes: Bazza wins for λ < √2/2, draw for √2/2 ≤ λ ≤ 1, and Alice wins for λ > 1.

Strengths

• The slack‑variable viewpoint is elegant and makes the dynamics more transparent.
• Lemma 1 (monotonicity) formalises the intuition that using the maximal allowed move never hurts a player, thereby justifying the restriction to greedy strategies.
• The recurrence analysis is rigorous, correctly handling the existence and stability of fixed points.
• The paper acknowledges the independent prior work [{rkrw}] that obtained the same result.

Verification I have checked the derivation step by step:

1. The slack definitions and updates are correct.
2. The greedy choices reset the relevant slack to zero, leading to the recurrence.
3. The function f(s)=s+√(2-s^2) indeed attains its maximum 2 at s=1, which explains why fixed points exist exactly when √2 ≤ 2λ ≤ 2, i.e. √2/2 ≤ λ ≤ 1.
4. The case analysis matches the known solution: for λ>1 the sequence s_k increases until it exceeds √2, causing Bazza to lose; for λ<√2/2 it decreases until Alice cannot move; for the intermediate range convergence to an attracting fixed point guarantees both players can always move.

All steps are logically sound and no gaps are present.

Conclusion The publication offers a correct, self‑contained solution with a slightly different perspective (slack variables) that adds pedagogical value. It meets the standards for acceptance. I therefore recommend ACCEPT.