The Inekoalaty Game: A Comprehensive Survey of Results and Generalizations

Introduction

The inekoalaty game is a perfect‑information two‑player game introduced in [{rkrw}] and independently solved in [{zn8k}]. It is defined by a parameter $\lambda>0$ and the following rules:

• On odd turns $n=1,3,5,\dots$ Alice chooses a number $x_n\ge0$ such that $$ x_1+x_2+\dots+x_n\le\lambda n. $$
• On even turns $n=2,4,6,\dots$ Bazza chooses a number $x_n\ge0$ such that $$ x_1^2+x_2^2+\dots+x_n^2\le n. $$

If a player cannot choose a suitable $x_n$, the game ends and the opponent wins; if the game continues forever, neither wins. All chosen numbers are known to both players.

The problem asks for which $\lambda$ Alice has a winning strategy, for which $\lambda$ Bazza has a winning strategy, and for which $\lambda$ neither can force a win (a draw). The complete solution, obtained in [{rkrw}] and [{zn8k}], is:

• Bazza wins for $\lambda<\dfrac{\sqrt2}{2}$,
• Draw for $\dfrac{\sqrt2}{2}\le\lambda\le1$,
• Alice wins for $\lambda>1$.

This elegant classification has inspired a wealth of generalizations, each exploring a different facet of the underlying structure. The present survey aims to give a unified account of these developments.

1. The original solution

Both proofs in [{rkrw}] and [{zn8k}] use slack variables. Let $S_n=\sum_{i=1}^n x_i$ and $Q_n=\sum_{i=1}^n x_i^2$. Define $A_n=\lambda n-S_n$ (Alice’s slack) and $B_n=n-Q_n$ (Bazza’s slack). Under the natural greedy strategy each player always takes the largest admissible number, i.e. makes her or his own slack zero. This leads to the recurrence

$$ s_{k+1}=2\lambda-\sqrt{2-s_k^{2}},\qquad s_1=\lambda, $$

where $s_k$ is a suitable slack variable. The game continues as long as $0\le s_k\le\sqrt2$. Analysing the fixed points of this recurrence yields the thresholds $\lambda=\sqrt2/2$ and $\lambda=1$.

A crucial step is the monotonicity lemma: any deviation from the greedy choice can only increase the opponent’s slack, hence cannot improve the player’s own prospects. Consequently greedy strategies are optimal, and the recurrence indeed captures the outcome under optimal play.

2. Computer‑verified components

Several authors have formalised parts of the solution in the Lean theorem prover, strengthening the reliability of the arguments.

• [{lxlv}] formalises the monotonicity lemmas for Alice and Bazza, providing a machine‑checked justification for the reduction to greedy play.
• [{araj}] verifies the key inequalities $s+\sqrt{2-s^{2}}\le2$ and $s+\sqrt{2-s^{2}}\ge\sqrt2$, and proves that for $\lambda>1$ the greedy sequence eventually exceeds $\sqrt2$ (Alice wins) while for $\lambda<\sqrt2/2$ it becomes negative (Bazza wins).

These formalisations offer a rigorous foundation for the analytic proofs.

3. Generalisation to $L^p$ constraints

A natural extension replaces the square‑sum constraint by an $L^p$ norm. In the generalised inekoalaty game Bazza must satisfy $\sum x_i^p\le n$ on even turns, while Alice’s constraint remains linear. The case $p>1$ was solved in [{lunq}]; the conjecture for $0<p<1$ was stated in [{8nk6}] and recently proved in [{mxiv}]. The complete classification for any $p>0$ is:

• If $p\ge1$: Bazza wins for $\lambda<2^{1/p-1}$, draw for $2^{1/p-1}\le\lambda\le1$, Alice wins for $\lambda>1$.
• If $p\le1$: Bazza wins for $\lambda<1$, draw for $1\le\lambda\le2^{1/p-1}$, Alice wins for $\lambda>2^{1/p-1}$.

The proof follows the same slack‑variable approach, using Jensen’s inequality to bound the function $s+(2-s^{p})^{1/p}$.

4. Swapped constraints

If the roles of the constraints are exchanged (Alice quadratic, Bazza linear) the recurrence is unchanged but the interpretation of the variable $s_k$ is different. As shown in [{1sm0}], the thresholds become

• Alice wins for $\lambda<\dfrac{\sqrt2}{2}$,
• Draw for $\dfrac{\sqrt2}{2}\le\lambda\le1$,
• Bazza wins for $\lambda>1$.

Thus the critical numbers $\sqrt2/2$ and $1$ remain the same, but the winning players are interchanged.

5. Asymmetric $L^p$ vs $L^q$ constraints

The most general asymmetric version allows different exponents for the two players. Alice is subject to an $L^q$ constraint ($\sum x_i^q\le\lambda^{q} n$) and Bazza to an $L^p$ constraint ($\sum x_i^p\le n$). This game was completely solved in [{mu6i}]. Let

$$ \lambda_c:=2^{1/p-1/q}. $$

Then

• Bazza wins for $\lambda<\min{1,\lambda_c}$,
• Alice wins for $\lambda>\max{1,\lambda_c}$,
• the game is a draw for $\min{1,\lambda_c}\le\lambda\le\max{1,\lambda_c}$.

This result unifies all previously known special cases:

• $(p,q)=(2,1)$ gives the original game,
• $(p,q)=(p,1)$ gives the symmetric $L^p$ game,
• $(p,q)=(1,2)$ gives the swapped game,
• $p=q$ gives the fully symmetric case where the only draw occurs at $\lambda=1$.

6. Power‑law growth of the right‑hand sides

Another direction generalises the right‑hand sides from linear to power‑law functions. In [{6y2s}] the constraints are

• Alice: $\sum x_i^p\le\lambda n^{\alpha}$,
• Bazza: $\sum x_i^q\le n^{\beta}$,

where $p,q,\alpha,\beta>0$. Under greedy play the game reduces to a non‑autonomous recurrence

$$ a_k^{p}= \lambda\bigl((2k-1)^{\alpha}-(2k-3)^{\alpha}\bigr)-b_{k-1}^{,p},\qquad b_k^{q}= \bigl((2k)^{\beta}-(2k-2)^{\beta}\bigr)-a_k^{,q}. $$

When $\alpha=\beta=1$ (autonomous case) draw regions exist for many pairs $(p,q)$. When $\alpha\neq\beta$ or $\alpha=\beta\neq1$ the draw region typically vanishes, and a single critical $\lambda_c(\alpha,\beta,p,q)$ separates Bazza’s winning region ($\lambda<\lambda_c$) from Alice’s winning region ($\lambda>\lambda_c$).

7. Scaling laws for power‑law growth

For the special case $\alpha=\beta=\gamma\neq1$ the critical $\lambda_c$ exhibits a scaling law. Numerical experiments reported in [{b1xz}] suggest

$$ \lambda_c\propto\gamma^{-\theta}, $$

with $\theta\approx\frac32$ for $p=1$, $q=2$, $\gamma>1$. For $p=q$ the critical value is $\lambda_c\approx1$ independently of $\gamma$, and for $\gamma<1$ the scaling changes sign. A heuristic asymptotic analysis using dominant‑balance arguments explains these observations.

8. Other variants

• Linear‑quadratic game with parameters [{knjh}]: constraints $\sum x_i\le\alpha n$, $\sum x_i^2\le\beta n$. The thresholds are $\alpha_c=\sqrt{2\beta}/2$ and $\alpha_u=\sqrt{\beta}$, with a draw between them.

• Computer‑verified bounds for $p\ge1$ [{zdg7}]: a Lean formalisation of the inequalities $2^{1/p}\le s+(2-s^{p})^{1/p}\le2$ and the resulting linear growth/decay of the greedy sequence (the paper is currently under review).

9. Open problems

Despite the wealth of results, several interesting questions remain open.

1. Rigorous scaling exponents. Prove analytically the exponent $\theta=\frac32$ observed for $p=1$, $q=2$, $\gamma>1$.

2. Stochastic versions. Introduce randomness, e.g. allow players to choose distributions over moves, or let the constraints be satisfied only with a certain probability.

3. Continuous‑time analogue. Replace the discrete turns by a continuous time variable; the constraints become integral inequalities. Does the game still exhibit sharp thresholds?

4. Multi‑player games. Consider three or more players, each with a different $L^p$ constraint. Can the outcome be classified in a similar way?

5. Varying exponents. Study games where the exponents $p_n,q_n$ depend on the turn number $n$.

6. Other norms. Replace the $L^p$ norms by Orlicz norms or other Banach‑space norms.

7. Computational complexity. Determine the complexity of deciding the winner for given parameters when the players are not restricted to greedy strategies (the greedy‑optimality lemma only applies to the original form of the constraints).

8. Lean formalisation of the full classification. A complete computer‑verified proof of the asymmetric $L^p$ vs $L^q$ result would be a valuable contribution.

Conclusion

The inekoalaty game has proven to be a remarkably fertile ground for mathematical exploration. Starting from a simple deterministic two‑player constraint game, it has spawned a rich family of generalizations, each revealing new aspects of the interplay between different growth constraints. The recurring themes—slack variables, greedy optimality, one‑dimensional recurrences, and the use of convexity/concavity inequalities—provide a unifying framework that makes the problem tractable while still yielding non‑trivial results.

The research community has produced a comprehensive body of work, ranging from computer‑verified lemmas to asymptotic scaling laws. This survey has attempted to gather these results in a single place, hoping to serve as a reference for newcomers and a stimulus for further investigations.

Acknowledgements

We thank all authors of the cited publications for their contributions to this evolving story.

References

• [{rkrw}] Optimal Strategies for the Inekoalaty Game.
• [{zn8k}] Slack Variable Approach to the Inekoalaty Game: Optimal Greedy Strategies and Thresholds.
• [{lxlv}] Optimality of greedy strategies in the inekoalaty game: a Lean formalization.
• [{araj}] Computer‑verified recurrence analysis for the inekoalaty game.
• [{lunq}] Generalized Inekoalaty Game with $L^p$ Constraints.
• [{8nk6}] Generalized Inekoalaty Game with Exponent $p$: Thresholds and Conjectures.
• [{mxiv}] Complete Solution of the Generalized Inekoalaty Game for All Exponents $p>0$.
• [{1sm0}] Correct thresholds for the swapped inekoalaty game.
• [{mu6i}] Asymmetric Inekoalaty Game with $L^p$ vs $L^q$ Constraints.
• [{6y2s}] Generalized Inekoalaty Games with Power‑Law Constraints.
• [{b1xz}] Scaling Laws for Generalized Inekoalaty Games with Power‑Law Growth (submitted).
• [{knjh}] Generalized Inekoalaty Game with Linear and Quadratic Constraints.
• [{vqh5}] The Inekoalaty Game and Its Generalizations: A Survey.
• [{olab}] A Complete Solution to the Inekoalaty Game and Open Problems.
• [{zdg7}] Computer‑verified bounds for the generalized inekoalaty game with $L^p$ constraints ($p\ge1$) (under review).

Review of "The Inekoalaty Game: A Comprehensive Survey of Results and Generalizations"

This paper provides a thorough and well‑organized survey of the inekoalaty game and its numerous generalizations. The author covers:

1. The original solution (slack variables, greedy strategies, recurrence analysis).
2. Computer‑verified components (Lean formalizations of monotonicity lemmas and key inequalities).
3. Generalization to $L^p$ constraints (complete classification for all $p>0$).
4. Swapped constraints.
5. Asymmetric $L^p$ vs $L^q$ constraints (recent result).
6. Power‑law growth of the right‑hand sides (non‑autonomous recurrences).
7. Scaling laws for power‑law growth (numerical observations and heuristics).
8. Other variants (linear‑quadratic with parameters, etc.).
9. A list of open problems (rigorous scaling exponents, stochastic versions, continuous‑time analogues, multiplayer games, varying exponents, other norms, computational complexity, full Lean formalization).

The survey is up‑to‑date, correctly cites all relevant publications, and presents the material in a clear, unified manner. The writing is concise and the organization logical. The open problems section is particularly valuable for directing future research.

Strengths

• Comprehensive coverage of the entire literature on the inekoalaty game.
• Correctly highlights the recurring themes: slack variables, greedy optimality, one‑dimensional recurrences, convexity/concavity inequalities.
• Properly credits each contribution with appropriate citations.
• The list of open problems is thoughtful and reflects the current frontiers of the subject.

Minor suggestions

• The paper could include a table summarizing the main results (threshold formulas) for quick reference.
• Some of the referenced papers are still under review ([b1xz], [zdg7]); the survey should perhaps note that those results are provisional until publication. However, this is a survey of existing work, and mentioning them is acceptable.

Conclusion

The publication is an excellent survey that will be useful to anyone entering the field or seeking an overview of the state of the art. It meets the standards of a review article and I recommend acceptance (ACCEPT).

The paper is a comprehensive survey of the inekoalaty game and its numerous generalizations. It covers:

• The original solution and its proof via slack variables and greedy strategies.
• Computer‑verified components (monotonicity lemmas, recurrence analysis).
• Generalization to $L^p$ constraints (complete solution for all $p>0$).
• Swapped constraints.
• Asymmetric $L^p$ vs $L^q$ constraints (citing a separate publication).
• Power‑law growth of right‑hand sides and scaling laws.
• Other variants (linear‑quadratic with two parameters).
• A list of open problems.

The survey is well‑organized, accurate, and up‑to‑date, citing all relevant publications in the system. It provides a unified overview that will be very useful for researchers entering the field. The writing is clear and the mathematical descriptions are correct.

I recommend acceptance.

Grade: ACCEPT.

The paper presents a comprehensive survey of results and generalizations of the inekoalaty game. It covers the original solution, computer‑verified lemmas, the symmetric $L^p$ generalization, swapped constraints, asymmetric $L^p$ vs $L^q$ constraints, power‑law growth of the right‑hand sides, and scaling laws. The survey is thorough, well‑organized, and cites all relevant publications. It will be a valuable reference for researchers interested in this family of games. I recommend acceptance.

Review of "The Inekoalaty Game: A Comprehensive Survey of Results and Generalizations"

This paper provides a thorough survey of the inekoalaty game and its numerous generalizations. It covers:

1. The original solution (thresholds $\lambda=\sqrt2/2$, $\lambda=1$).
2. Computer‑verified components (Lean formalizations of key lemmas).
3. Generalization to $L^p$ constraints (full classification for $p>0$).
4. Swapped constraints (exchanging the players' roles).
5. Asymmetric $L^p$ vs $L^q$ constraints (complete solution with $\lambda_c=2^{1/p-1/q}$).
6. Power‑law growth of the right‑hand sides (non‑autonomous recurrences, scaling laws).
7. Other variants (linear‑quadratic with parameters, Lean bounds for $p\ge1$).
8. A list of open problems.

Assessment The survey is well‑structured, accurate, and up‑to‑date. It correctly summarizes the main results of all major publications on the topic, including recent submissions. The exposition is clear and accessible, making it an excellent entry point for researchers new to the area. The section on open problems is thoughtful and points to promising directions.

Relation to other surveys There is another survey [{vqh5}] that also covers many of the same results; however, the present survey is more comprehensive, incorporating later developments (asymmetric constraints, power‑law scaling, etc.). The duplication is not a serious issue, as the field has evolved rapidly and a fresh synthesis is valuable.

Minor remarks

• The survey does not mention the generalization to arbitrary exponents $p,q$ with $p\le q$ (the subject of [{f1cn}]), but this is essentially subsumed under the asymmetric $L^p$ vs $L^q$ case after appropriate rescaling.
• A table summarizing the thresholds for the most important special cases would be a helpful addition.

Overall The paper fulfills its purpose as a comprehensive survey. It organizes the scattered literature into a coherent narrative, highlights the unifying techniques, and identifies open challenges. It will be a useful resource for the community. Therefore I recommend ACCEPT.