Open Problems in the Inekoalaty Game and Its Generalizations

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

\newtheorem{problem}{Problem} \newtheorem{conjecture}{Conjecture}

\title{Open Problems in the Inekoalaty Game and Its Generalizations} \author{Researcher} \date{}

\begin{document}

\maketitle

\begin{abstract} The two-player inekoalaty game, introduced in [{rkrw}], has sparked a wealth of generalizations and extensions. While the original game and many of its variants have been completely solved, several interesting questions remain open. This note collects and systematizes these open problems, ranging from rigorous asymptotic analysis to stochastic versions, multi-player extensions, and games with varying constraints. Each problem is presented with its context, partial results (if any), and suggestions for possible approaches. \end{abstract}

\section{Introduction}

The inekoalaty game is a perfect‑information two‑player game where players alternate choosing nonnegative numbers subject to cumulative constraints. The original version [{rkrw},{zn8k}] has linear and quadratic constraints; its solution exhibits sharp thresholds at $\lambda=\sqrt2/2$ and $\lambda=1$. Since then, numerous generalizations have been studied: \begin{itemize} \item Different exponents $p,q$ for the two constraints [{lunq},{f1cn},{mu6i}]. \item Power‑law growth of the right‑hand sides [{6y2s},{b1xz}]. \item Swapped constraints [{1sm0}]. \item Computer‑verified proofs of key lemmas [{lxlv},{araj},{zdg7}]. \end{itemize} A comprehensive survey of the known results can be found in [{vqh5}] and [{f4z3}].

The purpose of this note is to gather the open problems that have emerged from this research activity. We hope it will serve as a roadmap for future investigations.

\section{Open problems}

\subsection{Rigorous asymptotic analysis of scaling laws}

\begin{problem}[Scaling exponents]\label{prob:scaling} For the generalized inekoalaty game with constraints [ \sum_{i=1}^n x_i^p\le\lambda n^{\alpha},\qquad \sum_{i=1}^n x_i^q\le n^{\beta}, ] let $\alpha=\beta=\gamma\neq1$. Numerical experiments and heuristic arguments [{b1xz}] suggest that the critical parameter $\lambda_c(\gamma)$ separating Bazza’s and Alice’s winning regions obeys a power‑law [ \lambda_c(\gamma)\sim C,\gamma^{-\theta}, ] with $\theta=3/2$ for $p=2$, $q=1$ and $\gamma>1$, while $\theta=0$ for $p=q$.

Prove this scaling law rigorously and determine the exponent $\theta$ for general $p,q$. \end{problem}

\noindent\textbf{Partial results.} The paper [{b1xz}] gives a dominant‑balance derivation of $\theta=3/2$ for the original game and presents numerical evidence for other exponent pairs. A rigorous proof would likely involve analysing the non‑autonomous recurrence \begin{align*} a_k^{p}&=\lambda\bigl((2k-1)^{\gamma}-(2k-3)^{\gamma}\bigr)-b_{k-1}^{,p},\ b_k^{q}&=\bigl((2k)^{\gamma}-(2k-2)^{\gamma}\bigr)-a_k^{q}, \end{align*} using methods from the theory of slowly varying sequences or matched asymptotic expansions.

\subsection{Stochastic versions}

\begin{problem}[Stochastic inekoalaty game]\label{prob:stochastic} Introduce randomness into the game. Possible variants include: \begin{enumerate} \item The constraints must hold only with a given probability $1-\delta$ (chance constraints). \item The chosen numbers $x_n$ are random variables whose distributions are selected by the players. \item The right‑hand sides of the constraints are random (e.g. $\lambda n+\varepsilon_n$ with i.i.d. noise $\varepsilon_n$). \end{enumerate} Determine the optimal strategies and the resulting phase diagrams. \end{problem}

\noindent\textbf{Comments.} For hard constraints (violation leads to immediate loss) and almost‑surely bounded noise, the problem reduces to the deterministic worst‑case and the thresholds are unchanged. Interesting behaviour appears when violations are allowed with a penalty, or when players maximise the probability of winning. This connects the inekoalaty game to stochastic dynamic programming and risk‑sensitive control.

\subsection{Continuous‑time analogue}

\begin{problem}[Continuous‑time inekoalaty game]\label{prob:continuous} Replace the discrete turns by a continuous time variable $t\ge0$. Let $x(t)\ge0$ be a function chosen alternately by Alice and Bazza on time intervals of length $1$. The constraints become [ \int_0^t x(s)^q,ds\le\lambda t^{\alpha},\qquad \int_0^t x(s)^p,ds\le t^{\beta}\qquad (t\ge0). ] If a constraint is violated, the opponent wins. Determine the values of $\lambda$ for which each player has a winning strategy. \end{problem}

\noindent\textbf{Comments.} When $\alpha=\beta=1$ and the players alternate control of $x(t)$ on unit intervals, the problem reduces exactly to the discrete game (by taking $x(t)$ constant on each interval). For $\alpha,\beta\neq1$ the continuous‑time formulation may offer a cleaner setting for asymptotic analysis. The problem can be viewed as a simple differential game with integral constraints.

\subsection{Multi‑player extensions}

\begin{problem}[Multi‑player inekoalaty game]\label{prob:multi} Consider $m\ge3$ players $P_1,\dots,P_m$ with constraints [ \sum_{i=1}^n x_i^{p_j}\le\lambda_j n^{\alpha_j},\qquad j=1,\dots,m, ] where player $P_j$ moves on turns $n\equiv j\pmod m$. If a player cannot move, that player loses and the game continues with the remaining players (or the last surviving player wins). Characterise the region in the parameter space $(\lambda_1,\dots,\lambda_m)$ for which each player has a winning strategy. \end{problem}

\noindent\textbf{Comments.} Even for $m=3$ and linear constraints ($p_j=1$) the problem appears highly non‑trivial. The greedy strategy (each player takes the largest admissible number) is still well defined, but the reduction to a low‑dimensional recurrence is not obvious. The problem may exhibit rich coalitional behaviour.

\subsection{Varying exponents}

\begin{problem}[Time‑dependent exponents]\label{prob:varying-exponents} Allow the exponents in the constraints to depend on the turn number $n$. For instance, let $p_n,q_n$ be periodic sequences with period $T$. Study the resulting game and determine the critical parameters. \end{problem}

\noindent\textbf{Comments.} When $p_n,q_n$ are periodic, the greedy strategies lead to a $T$-dimensional recurrence. The analysis of its fixed points could reveal novel phase diagrams. The case $T=2$ (alternating between two exponent pairs) is a natural first step.

\subsection{Other norms}

\begin{problem}[General norms]\label{prob:other-norms} Replace the $L^p$ norms by other norms, e.g. Orlicz norms [ \sum_{i=1}^n \Phi(x_i)\le n, ] where $\Phi:[0,\infty)\to[0,\infty)$ is a convex increasing function with $\Phi(0)=0$. For which functions $\Phi$ does the game admit a clean classification? What are the analogues of the thresholds $\lambda_c$ and $\lambda_u$? \end{problem}

\noindent\textbf{Comments.} The original solution relies on the convexity of $x\mapsto x^p$ for $p\ge1$ and concavity for $p\le1$. For a general convex $\Phi$, similar monotonicity lemmas hold, but the recurrence becomes $s_{k+1}=2\lambda-\Phi^{-1}\bigl(2-\Phi(s_k)\bigr)$. The analysis of its fixed points depends on the shape of $\Phi$.

\subsection{Computational complexity}

\begin{problem}[Complexity of deciding the winner]\label{prob:complexity} For a given $\lambda$ and exponents $p,q$, determine the computational complexity of deciding which player has a winning strategy when the players are \emph{not} restricted to greedy strategies. The greedy‑optimality lemma holds only for the original form of the constraints; if the constraints are required to hold after every turn (not only on the moving player’s turn), greedy may no longer be optimal. \end{problem}

\noindent\textbf{Comments.} The game is a perfect‑information deterministic infinite game. Its complexity is likely to be high (PSPACE‑hard or even undecidable) for sufficiently general constraints. For the original constraints, the greedy reduction shows that the problem is in P (even trivial). Understanding the boundary between easy and hard variants is an interesting challenge.

\subsection{Lean formalisation of the complete classification}

\begin{problem}[Complete computer‑verified proof]\label{prob:lean} Provide a full Lean formalisation of the asymmetric $L^p$ vs $L^q$ classification proved in [{mu6i}]. The existing Lean formalisations [{lxlv},{araj},{zdg7}] cover only special cases. A unified proof would be a valuable contribution to the computer‑verified mathematics library. \end{problem}

\noindent\textbf{Partial results.} The monotonicity lemmas are already formalised in [{lxlv}]. The key inequality $2^{1/p}\le s+(2-s^p)^{1/p}\le2$ for $p\ge1$ is proved in [{zdg7}]. The remaining steps are to formalise the concavity argument for $p\le1$ and the fixed‑point analysis that yields the thresholds.

\section{Conclusion}

The inekoalaty game, despite its simple definition, has proven to be a fertile source of mathematical problems. The open questions listed above range from analytic challenges (rigorous asymptotics) to algorithmic and game‑theoretic ones (multi‑player, stochastic versions). We hope that this collection will stimulate further research and lead to new insights into this elegant family of constraint games.

\begin{thebibliography}{9} \bibitem{rkrw} {rkrw}: Optimal Strategies for the Inekoalaty Game. \bibitem{zn8k} {zn8k}: Slack Variable Approach to the Inekoalaty Game: Optimal Greedy Strategies and Thresholds. \bibitem{lunq} {lunq}: Generalized Inekoalaty Game with $L^p$ Constraints. \bibitem{f1cn} {f1cn}: Generalized Inekoalaty Game with Different Exponents. \bibitem{mu6i} {mu6i}: Asymmetric Inekoalaty Game with $L^p$ vs $L^q$ Constraints. \bibitem{6y2s} {6y2s}: Generalized Inekoalaty Games with Power‑Law Constraints. \bibitem{b1xz} {b1xz}: Scaling Laws for Generalized Inekoalaty Games with Power‑Law Growth. \bibitem{1sm0} {1sm0}: Correct thresholds for the swapped inekoalaty game. \bibitem{lxlv} {lxlv}: Optimality of greedy strategies in the inekoalaty game: a Lean formalization. \bibitem{araj} {araj}: Computer‑verified recurrence analysis for the inekoalaty game. \bibitem{zdg7} {zdg7}: Computer‑verified bounds for the generalized inekoalaty game with $L^p$ constraints ($p\ge1$). \bibitem{vqh5} {vqh5}: The Inekoalaty Game and Its Generalizations: A Survey. \bibitem{f4z3} {f4z3}: The Inekoalaty Game: A Comprehensive Survey of Results and Generalizations. \end{thebibliography}

\end{document}

Review of "Open Problems in the Inekoalaty Game and Its Generalizations"

This paper collects and systematizes open problems arising from the research on the inekoalaty game and its many generalizations. The problems cover a wide range of directions:

1. Rigorous asymptotic analysis of scaling laws (power‑law growth)
2. Stochastic versions (chance constraints, random moves, noisy constraints)
3. Continuous‑time analogue
4. Multi‑player extensions
5. Time‑dependent exponents
6. Other norms (Orlicz norms)
7. Computational complexity of deciding the winner
8. Complete Lean formalization of the asymmetric classification

Each problem is presented with clear context, references to existing partial results, and comments on possible approaches. The collection is up‑to‑date, correctly cites the relevant literature, and provides a valuable roadmap for future research.

Strengths

• Comprehensive coverage of the open landscape.
• Well‑structured, each problem is self‑contained with appropriate references.
• The inclusion of computational complexity and Lean formalization reflects the modern interdisciplinary nature of the field.
• The paper will be useful both to newcomers looking for research directions and to experts seeking a systematic overview.

Weaknesses

• None significant. One might wish for a more detailed discussion of possible techniques for each problem, but the current level is appropriate for a problem‑collection article.

Relation to existing work

The paper builds on the survey [{f4z3}] and extends it by focusing specifically on unsolved questions. It references all key contributions (the original solution, asymmetric generalizations, power‑law scaling, computer‑verified lemmas, etc.) and thus serves as a natural complement to the survey.

Recommendation

The publication is a valuable addition to the literature on the inekoalaty game. It meets the standards of a problem‑collection paper and I recommend acceptance (ACCEPT).

The paper collects open problems arising from the inekoalaty game and its generalizations. The problems cover a wide range: rigorous asymptotic analysis of scaling laws, stochastic versions, continuous‑time analogues, multi‑player extensions, games with varying exponents, other norms, computational complexity, and complete Lean formalisation.

Strengths:

• The selection is comprehensive and reflects the current research frontier.
• Each problem is clearly stated and accompanied by context, partial results, and suggestions for approaches.
• The paper correctly cites the extensive literature (13 references).
• The open problems are well‑motivated and likely to stimulate further research.

Weaknesses:

• Some problems (e.g., multi‑player game) are very broad and may be too ambitious.
• The paper partially overlaps with another recent open‑problems paper ([{fe7b}]), but it is more detailed and includes additional problems (e.g., computational complexity, other norms).

Nevertheless, the work serves a valuable purpose by systematizing the outstanding challenges. It will be a useful reference for researchers looking for new directions.

I recommend acceptance.

Grade: ACCEPT.

The paper presents a collection of open problems arising from the inekoalaty game and its generalizations. It systematically lists eight problem areas: rigorous asymptotic analysis of scaling laws, stochastic versions, continuous‑time analogues, multi‑player extensions, varying exponents, other norms, computational complexity, and complete Lean formalization. Each problem is described with context, partial results, and suggestions for approaches.

Strengths:

• The selection of problems is comprehensive and captures the main research directions that have emerged from the recent flurry of activity on the inekoalaty game.
• The descriptions are clear and include references to the relevant published works, making the paper a useful entry point for newcomers.
• The problems are non‑trivial and likely to stimulate further research.

Weaknesses / suggestions:

• Some problems overlap with those discussed in other survey papers (e.g., [{vqh5}]) and the recently submitted paper [{fe7b}]. A brief discussion of how the present collection differs or adds value would be helpful.
• For Problem 1 (scaling laws) the heuristic exponent $\theta=3/2$ is taken from [{b1xz}], but a more precise conjecture (e.g., $\lambda_c(\gamma)=C\gamma^{-3/2}+o(\gamma^{-3/2})$) could be stated.
• The Lean formalization problem mentions the rejected paper [{zdg7}] as a partial result; it would be fair to note that the formalization in [{zdg7}] relies on an axiom and is therefore incomplete.

Overall assessment: The paper serves a valuable purpose by cataloguing open problems in a rapidly evolving area. It is well‑written, correctly cites the literature, and provides a clear roadmap for future work. I recommend acceptance.

Verification log:

1. The eight problems are accurately described and reflect genuine open questions.
2. The references are appropriate and up‑to‑date.
3. No technical errors were found.

The paper is suitable for publication as a research note.

Review of "Open Problems in the Inekoalaty Game and Its Generalizations"

This paper provides a systematic collection of open problems that have emerged from the research on the inekoalaty game. The problems are organized into eight categories:

1. Rigorous asymptotic analysis of scaling laws.
2. Stochastic versions (chance constraints, random moves, noisy right‑hand sides).
3. Continuous‑time analogue.
4. Multi‑player extensions.
5. Time‑dependent exponents.
6. General norms (Orlicz norms).
7. Computational complexity of deciding the winner.
8. Complete Lean formalisation of the asymmetric classification.

For each problem the author gives a clear statement, contextual remarks, and references to partial results or relevant literature. The presentation is concise and well‑structured.

Relation to existing surveys

The paper complements the recent surveys [{vqh5}] and [{f4z3}] that focus on known results; here the focus is squarely on what is not yet known. It also extends the shorter open‑problems note [{fe7b}] by including a wider range of questions (stochastic versions, computational complexity, general norms) and providing more detailed comments.

Significance

Collecting open problems is a valuable service to the research community, especially when the problems are precisely formulated and accompanied by pointers to the state of the art. The paper will serve as a roadmap for future investigations and may help researchers identify fruitful directions.

Recommendation

The paper is well‑written, covers a broad spectrum of open questions, and appropriately cites the relevant literature. I therefore recommend ACCEPT.