Alpern's Caching Game is played by $2$ players. Player $1$ is a squirrel, who is hiding his $d$ nuts in $n$ different holes, with the restriction that he can only dig down a distance of $1$ metre altogether. After that, Player $2$ wants to find all the nuts, and she is allowed to dig down a distance of $k$ metres altogether. Player $2$ wins after finding all the nuts, if she fails then the squirrel wins. We investigate a discrete version of the game, finding strategies and statements for both smaller and general values of $n,d,k$. In particular, we answer a question of Pálvölgyi, by exhibiting an example, where the value of the game can change depending on which nut the squirrel reveals, when he has multiple options in the discrete game. We also investigate and invent other continuous versions of the game, one of them having a connection to the Manickam-Miklós-Singhi Conjecture.

Keywords: game theory, probability, strategies, caching games, 2-person game

MSC: 91A05

[1]Institute of Mathematics, Eötvös Loránd University, Hungary
[2]Rényi Institute, Hungary
[3]Research supported by ERC Advanced Grant ”GeoScape”

§ INTRODUCTION

Alpern's Caching Game, introduced in a paper of Alpern, Fokkink, Leszek and Lindelauf [1], is played between two players, where we say that Player 1 is the “squirrel" or “hider", and we refer to Player 2 as the “searcher". We will use “he" for the squirrel and “she" for the searcher for clarity. The squirrel starts the game by hiding $d$ nuts in $n$ given holes. The squirrel is allowed to dig down a total distance of $1$ metre in the holes combined. He can hide several nuts in the same hole at different depths, but he cannot hide any nut deeper than the depth he dug in the given hole. After that, the task of Player $2$ will be to find all of the nuts. To do that, she is allowed to dig down a distance of $k$ metres combined in the $n$ holes. She can find a nut by digging under its depth in its hole. The searcher's strategy is adaptive, so it can depend on partial result of her digging. For example, she can change strategy after finding a nut in one of the holes. The searcher can only win if she finds all the nuts in the holes. The squirrel wins the game if at least one of the nuts stays hidden. An example game can be seen on Figure <ref>.

[green!30!brown!70!] (0.0,0) rectangle (0.8,2);
[black] (0.0,0) rectangle (0.8,2);

[black!20] (2.0,0) rectangle (2.8,2);
[green!30!brown!70!] (2.0,0) rectangle (2.8,4/3);
[black] (2.0,0) rectangle (2.8,2);

[green!30!brown!70!] (4.0,0) rectangle (4.8,2);
[black!20] (4.0,2/3) rectangle (4.8,2);
[black] (4.0,0) rectangle (4.8,2);

[brown] (2.4,2/3) circle (0.2);
[black] (2.4,2/3) circle (0.2);
[brown] (4.4,4/3) circle (0.2);
[black] (4.4,4/3) circle (0.2);
[brown] (2.4,5/3) circle (0.2);
[black] (2.4,5/3) circle (0.2);

In the above example of Alpern's Caching Game, $n=3$, $d=3$, and $k=1$. The squirrel hid one of the nuts in hole $2$ at depth $1/6$, one at depth $2/3$, and hid the third one in hole $3$ at depth $1/3$. The searcher failed to find one of the nuts, therefore lost the game.

If $k<1$, the squirrel has a winning strategy by hiding a nut $1$ metre deep in the first hole. If $k\ge n$, then the searcher has a winning strategy since she can just dig down $1$ metre in all of the $n$ holes.

The question first arose in a paper by Alpern, Fokkink, Lidbetter, and Clayton  [1]. Afterwards, some other papers were also published on the game: [2, 3, 4, 5].

The Multiple Caching Game is a discrete version of the above game, introduced by Pálvölgyi [5] based on Csóka's method in [3]. In that game, the squirrel hides $d$ nuts in $n$ holes, with no limit on the number of nuts in any of the holes. The searcher can find these nuts in the following way: she is allowed to ask $d$ questions and to shape the next question based on the results of the previous questions. In each question, she can choose at most $k$ of the holes. If there is at least one nut in some of these holes, the squirrel must give the searcher a nut from one of the chosen holes. The squirrel can decide which one he wants to give her. The searcher cannot know how many nuts were in the chosen holes, but she can see which hole contained the nut she received. The searcher wins the game if after $d$ questions she finds all the $d$ nuts. If any of her questions ask only about empty holes, then the squirrel wins since some of the nuts stay hidden. For an example game, see Figure <ref>. Here a naturally arising question is, what the maximal winning chances of both players are, if they both play optimally, and what their optimal strategies are. That obviously depends on the parameters $n,d,k$.

Let $v_A(n,d,k)$ denote the winning probability of the searcher if both players play optimally in Alpern's Caching Game.
Let $v_M(n,d,k)$ denote the winning probability of the searcher if both players play optimally in Multiple Caching Game.

Call these numbers the values of the corresponding games.

Note that these values are well-defined, since this is a zero-sum game, and there must be a Nash equilibrium in any such game.

at (1.5, 0.75) Question 1;

/in 1/1,2/1,3/0

[fill=mygray] (1.5 + *1.5, 0) rectangle ++(1,1);
(1.5 + *1.5, 0) rectangle ++(1,1);
at (1.5 + *1.5 + 0.5, 0.5) ;

at (1.5, -1.25) Question 2;

/in 1/0,2/1,3/0

[fill=mygray] (1.5 + *1.5, -1.5) rectangle ++(1,1);
(1.5 + *1.5, -1.5) rectangle ++(1,1);
at (1.5 + *1.5 + 0.5, -1.5 + 0.5) ;

In the above example of Multiple Caching Game, $n=3$, $d=2$, and $k=2$. The squirrel hid one of the nuts in hole $1$ and one in hole $2$. In each step the searcher queried the grey holes. After the first step, the squirrel gives her the nut from the first hole. In the second question, there was no nut in the chosen hole, so the searcher lost the game.

Based on Csóka's [3] and Pálvölgyi's [5] previous results, we already know that $v_M(n,d,k)\le v_A(n,d,k)\le\frac{k^d}{\binom{n+d-1}{d}}$. (For completeness, we include these results with their proofs, see Theorems <ref>. and <ref>. ) Pálvölgyi also showed that if $n$ is large enough compared to $k$ and $d$, and $k$ is an integer, then the values of both games are $\frac{k^d}{\binom{n+d-1}{d}}$.

Most of our paper is concerned with the Multiple Caching Game. We establish several useful Theorems in Section $2$, in particular we prove the following theorem:

For any $n,d,k$ integers such that $k\leq n$, there is an optimal searcher strategy that asks exactly $k$ holes in each step.

In the beginning of Section $3$, we are mainly concerned with characterizing accurate triplets:

We call a triplet $(n,d,k)$ accurate, if $v_M(n,d,k)=v_A(n,d,k)=\frac{k^d}{\binom{n+d-1}{d}}$.

Csóka conjectured the following:

[Csóka [3]]
If $n\ge dk$ and $k$ is a positive real number, then $v_A(n,d,k)=\frac{k^d}{\binom{n+d-1}{d}}$.

Based on our observations and examples, we claim that even the following should hold:

If $n, d, k$ are integers, and $n\ge d(k-1)+1$, then $(n, d, k)$ is accurate.

For smaller values, we found the following monotonicity statements to be true, so we decided to include it as a conjecture:

If the triplet $(n,d,k)$ of integers is accurate, then $(n,d-1,k)$, $(n,d,k-1)$ and $(n+1,d,k)$ are all accurate.

As one of our main results, we settled a question of Pálvölgyi [5], where he asked whether the choice of the squirrel is important for the game value, when the query finds more than one nut at once. Chapter $3.3$ is entirely devoted to this question.

[Importance of nut choice]
When the searcher asks more than one hole containing a nut, the choice of which nut to give away matters for the squirrel, restricting that choice can change the game's value.

We finished Chapter 3 with examining what happens when the number of nuts goes to infinity. It turns out that the searcher still has a positive probability of winning that game:

For any integer $k \geq 2$, $v_M(n,d,k) \geq c(n,k)>0$, where $c(n,k)$ is a positive constant depending only on $n$ and $k$.

In Chapter $4$, we investigate some possible continuous versions of the game and establish a nice connection between one of those games, and the Manickam-Miklós-Singhi Conjecture.

§ THE MULTIPLE CACHING GAME

§.§ Intuitive helpful lemmas

We proved some simple lemmas and theorems, which will be useful in the later parts of the paper.

Getting a "helpful nut" at any point in the game does not decrease the value of the game.
A helpful nut is a nut who's position is revealed by the squirrel as a help.

If the squirrel tells the position of a nut, the searcher can forget the bonus information and play following his original strategy. Therefore the value of the game cannot decrease.

Getting a "gift nut" at any point in the game does not decrease the value of the game.
A gift nut is given to the searcher without any query. It still decreases the searcher's remaining question number.

If the squirrel gives the searcher a gift nut, without loss of generality we can call its hole the first hole.
The searcher can follow a strategy that gives at least the value her original game would give:
She will follow her original optimal strategy with one change. The first time she would question the first hole after the gift nut, she just omits the question and imagines that she asked it and was given a nut from the first hole.
This way, the winning probability stays the same, as her strategy was the optimal one, which means the squirrel's nut-giving strategy cannot decrease the winning probability of the searcher under the game's value. Therefore, getting the nut from the first hole is not making her chances worse compared to the original strategy.
If the rest of her queries would never ask the first hole, then originally the winning probability would be zero, in this case, so then following any new strategy will not give a smaller winning chance.
This new strategy, therefore, has at least the same winning percentage as the optimal one without the gift nut.

The value of the Multiple Caching Game is monotonically decreasing in parameter $d$: $v_M(n,d+1,k) \leq v_M(n,d,k)$ for any $n,d,k$ integers.

Suppose that the $(d+1)$-nut game has value $v_M(n,d+1,k)$. For any starting hiding position, we can force the squirrel to give a gift nut to the searcher. By Lemma <ref>. the value of that game with one necessary gift nut is at least $v_M(n,d+1,k)$. Now we just need to show that this game is equivalent to the $d$-nut game, which is obvious since the squirrel has a nut that he gives away anyways, and is only able to hide $d$ nuts in the holes. Hence, by Lemma <ref>.  $v_M(n,d+1,k) \leq v_M(n,d,k)$.

Now we can prove Theorem <ref> mentioned in the introduction:

Let the searcher play one of her optimal strategies. We will slightly modify it:
If any of the questions only ask $l<k$ holes, we modify the strategy by adding some arbitrary $k-l$ holes into the query. After that, if the squirrel gives a nut from the original $l$ holes, then the searcher will just continue with her strategy as if it was the $l$ hole query.
If the question fails, the original question would have failed too.

If the squirrel gives a nut from another hole, then she keeps repeating the same question until she gets one from the $l$ holes or loses. If she loses, she would have lost in the original strategy too. If she gets a nut from the $l$ holes, and $M$ additional nuts in the other $k-l$ holes, then we claim that this new state is at least as good as the original result of the $l$ hole question would be for the searcher. If instead of those $M$ extra questions in-between, she just gets $M$ gift nuts from one of those holes, then we know by lemma <ref>. that the value of the game does not decrease, so the searcher must have a strategy at least as good as the original one without gift nuts from that point. She did not get them as gift nuts, but she can just decide to forget what the query was on those $M$ questions, act like they were gift nuts, and apply the new optimal strategy with $M$ gift nuts. Then this new state is equivalent to getting $M$ gift nuts. That means that there is a search strategy that is at least as good as continuing the original strategy without the gift nuts would be.

After that point, she again plays the new optimal strategy, adding arbitrary holes to questions with less than $k$ holes, repeating them if she gets an unexpected nut, and applying this "act as if they were gift nuts" approach to unexpected nuts. Unexpected nuts are the nuts coming from these added arbitrary holes.
It is easy to see that this strategy's winning chance is at least as large as the original winning probability, since it only differs from the optimal strategy when she gets gift nuts (after forgetting), and we know that gift nuts cannot decrease the value. The defined strategy asks $k$ holes in each step.

When looking for an optimal strategy, it is enough to consider strategies with all questions asking exactly $k$ holes.

[Csóka [3]]
For any integers $n, d, k$,  $v_M(n,d,k)\le\frac{k^d}{\binom{n+d-1}{d}}$.

The number of all the possible hiding variations is $\binom{n+d-1}{d}$ since the squirrel hides $d$ nuts in $n$ holes, and multiple nuts can go into the same hole.
If the squirrel hides by choosing any of the hiding variations with the same probability, so he chooses uniformly between them, then the searcher can win with probability at most $\frac{k^d}{\binom{n+d-1}{d}}$. That is because the searcher can only win in $k^d$ different ways depending on which hole she gets the nuts from in each query, hence she can win at most $k^d$ different hiding variations out of all.

That upper bound holds in Alpern's Caching Game too, see Csóka's paper for proof: <cit.>.

[Pálvölgyi [5], Csóka [3]]
If $k$ is an integer, $v_M(n,d,k)\le v_A(n,d,k)$.

We define a strategy in Alpern's Caching Game that finds the nut with at least the same probability as the value of the game in the Multiple Caching Game.
We use the optimal searcher strategy from the Multiple Caching Game:
If our next query asks $k$ holes, in our game the searcher will start digging on these $k$ holes simultaneously, with equal speed in all of them. As soon as she finds a nut, she can just imagine that the squirrel chose to give it to her (since the squirrel could indeed choose that one in the other game). If there are more nuts at the same depth, she just takes one of them, and only digs the other out later if a query asks the hole. The searcher then continues the strategy with the next question and so on. If she ever asks only nut-free holes, then she loses the game as in the Multiple Caching Game. If she could find all the nuts with this method in the discrete game, she finds them here too. She has dug at most $1$ unit altogether for the nuts themselves, and for every query, she dug at most $k$ times the required amount, so she dug at most $k$ distance in the holes. Therefore with this strategy, the searcher wins precisely when she would win in the Multiple Caching Game with nuts placed in the same holes. So the value in Alpern's Caching Game is at least the value in the Multiple Caching Game.

The following statement was proven in several other papers.

For any integers $n, d, k$,  $v_M(n,d,k)\le\frac kn$.

If the squirrel hides all his nuts in the same hole, then the searcher's first query finds a nut with at most $\frac kn$ probability, therefore the value must be $v_M(n,d,k)\le\frac kn$.

§ NEW BOUNDS AND STRATEGIES FOR SPECIAL CASES

First, we investigated the $(n,d,k)=(4,3,2)$ case. Pálvölgyi ([5]) suggested that in this game, the values of Alpern's Caching Game and Multiple Caching Game might be different since here the prerequisites of Conjecture <ref>. do not hold, and also his strategy could not prove this triplet is accurate. We showed that the two values are still equal here, so the bound in Csóka's conjecture is not the best possible bound.

§.§ The $(4,3,2)$ game

By using a new strategy, we managed to reach the theoretical maximum possible value of the game: $\frac{k^d}{\binom{n+d-1}{d}}=\frac{2^3}{\binom{4+3-1}{3}}=\frac8{20}=\frac25$.

Using Theorem <ref>, we only considered searching strategies that ask 2 holes in each step.

The optimal strategy we found is:

* In the first step, the searcher chooses between her $6$ possible queries with equal probability. We can call the two holes she picked hole $1$ and hole $2$. We can also assume that she was given a nut from hole $1$ (if she was given one).

* Her second question has two options. This is the first one, which she asks with $\frac45$ probability: Here she asks hole $1$ and one of the two numberless holes with equal probability. We call the chosen one hole $3$, the other one will be hole $4$. If she receives nut from hole $1$, then her last question is hole $1$ and hole $4$. If she receives nut from hole $3$, then the last question is hole $3$ and hole $4$.

* The other possible second question, with $\frac15$ probability, is the following: She asks holes $3$ and $4$. If she gets a nut from hole $3$, her last question is hole $1$ and hole $3$. If she gets a nut from hole $4$, her last question is hole $1$ and hole $4$.

This strategy has $\frac25$ winning probability against any hiding strategy. This strategy is a special case of the $d=3$ general case, for which the proof can be found at Theorem <ref>. See Figure <ref> for visual representation of the strategy.

[line cap=round,line join=round,>=triangle 45,x=0.6cm,y=0.6cm]
(-14.077056627706742,-5.148554262269194) rectangle (18.501305063321407,2.203948110660301);
(-12.009185040850435,-0.7597778487318287) node[font=,anchor=north west] $(1,1,0,0)$;
(-5.004887851246821,1.2537458946719848) node[font=,anchor=north west] $(1,0,1,0)$;
(-5.004887851246821,-2.750677729850206) node[font=,anchor=north west] $(0,0,1,1)$;
(2.799409338356793,1.2537458946719848) node[font=,anchor=north west] $(1,0,0,1)$;
(2.799409338356793,-0.7597778487318287) node[font=,anchor=north west] $(0,0,1,1)$;
(2.7999409338356793,-2.750677729850206) node[font=,anchor=north west] $(1,0,1,0)$;
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$1.$] (-2.3,0.8) – (2.8,0.8);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$3.$] (-2.3,0.8) – (2.8,-1.15);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$3.$] (-2.3,-3.2) – (2.8,-3.2);
[line width=0.8pt] (-7,0.8) – (-5,0.8);
[line width=0.8pt] (-7,-3.2) – (-5,-3.2);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$1.$] (-9.5,-1.2) – (-7,-1.2);

[color=black] (-5.814392402105076,1.1431038289535264) node $\frac45$;
[color=black] (-5.874566818387592,-2.8839436578541007) node $\frac15$;

On the diagram, the positions of the $1$-s show which holes were part of the given query. The numbers on the arrows tell us the position of the hole from which the searcher received the last nut. Where the diagram splits into several rows, we write the probability of each query occurring on a segment before the query.

Hence we have shown that $(4,3,2)$ is accurate.

In this strategy, the searcher never asks a hole if she has not received a nut from it during a previous question. Therefore, if the squirrel ever had to choose which nut to give her, then she automatically loses, since she never asks back the other hole. Hence the nut-giving choice of the squirrel is redundant here.

§.§ New Conjecture on triplet accuracy

Based on the $(4,3,2)$ game, we came up with the new Conjecture <ref> on when should a triplet be accurate. That was based on the observation that our strategy never asked back on holes, where the searcher received no nuts during a previous question. Therefore the nut-giving strategy of the squirrel was redundant. If we look for such a strategy, each question takes $k-1$ holes out of the game, except the last one, therefore the searcher needs at least $(d-1)(k-1)+1$ holes for such a strategy, but she also needs $k$ more holes for the last question, which gives the requirement $n\ge(d-1)(k-1)+k=d(k-1)+1$ in the conjecture.

If $n\geq d(k-1)+1$, then $\frac{k^d}{\binom{n+d-1}{d}}\le \frac kn$, hence Theorem <ref> is the stronger upper bound in these cases.

If we believe Conjecture <ref>. and use a theorem in Pálvölgyi's paper (<cit.>), we can see that there must be a theorem in the form of Conjecture <ref>, maybe with a different bound on $n$.

If we use Theorem <ref>.  we can show that the bound on $n$ in Conjecture <ref> is the best possible:  $\frac{k^d}{\binom{n+d-1}{d}}\le \frac{k^{d-1}}{\binom{n+(d-1)-1}{d-1}}\Rightarrow k\le \frac{\frac{(n+d-1)!}{d!}}{\frac{(n+d-2)!}{(d-1)!}}\Rightarrow dk\le n+d-1\Rightarrow d(k-1)+1\le n$.

Now we show strategies for some small $d$ values satisfying the conjecture:

If $n\geq 2k-1$, then the triplet $(n,2,k)$ is accurate.

Here we give a search strategy for $n=(2k-1)$. See Figure <ref>. Pálvölgyi already solved the case $n\geq 2k$ in [5].

[line cap=round,line join=round,>=triangle 45,x=0.6cm,y=0.6cm]
(-14.077056627706742,-3.148554262269194) rectangle (0.501305063321407,0.203948110660301);
(-14.009185040850435,-0.7597778487318287) node[font=,anchor=north west] $(\underbrace{1,\ldots,1}_{k \textup{ db}},\underbrace{0,\ldots, 0}_{k-1 \textup{ db}})$;
(-6.999409338356793,-0.7597778487318287) node[font=,anchor=north west] $(1,\underbrace{0,\ldots,0}_{k-1 \textup{ db}},\underbrace{1,\ldots,1}_{k-1 \textup{ db}})$;
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$1.$] (-9.5,-1.2) – (-7,-1.2);

We put $1$-s on the hole positions that the searcher asks in her query and zeros on the other positions. The number on the arrow tells us the hole from which she received a nut.

There are $2$ cases here, either the nuts are in the same hole, or they are in $2$ different holes.

* If the nuts are in the same hole, the searcher finds them with probability $\frac kn$, since she only finds them if the hole is one of the first $k$ holes.

* If the nuts are in different holes, the searcher finds them with probability $\frac{k(k-1)}{\binom {n}{2}}$. This is because one nut needs to be in the first $k$ holes, the other one needs to be in the last $k-1$ holes, and all the possible nut positions are $\binom {n}{2}$.

* Since $n=2k-1$, the winning probability in both cases are $\frac{k(k-1)}{\binom{n}{2}}=\frac kn$.

If $n\geq 3k-2$, then the triplet $(n,3,k)$ is accurate.

Here we give a strategy for $n=(3k-2)$. See Figure <ref>. Pálvölgyi already proved accuracy for $n\geq(3k-1)$ in [5].

[line cap=round,line join=round,>=triangle 45,x=0.6cm,y=0.6cm]
(-14.077056627706742,-5.148554262269194) rectangle (18.501305063321407,2.203948110660301);
(-14.009185040850435,-0.7597778487318287) node[font=,anchor=north west] $(\underbrace{1,\ldots,1}_{k \textup{ db}},\underbrace{0,\ldots, 0}_{2k-2 \textup{ db}})$;
(-5.004887851246821,1.2537458946719848) node[font=,anchor=north west] $(1,\underbrace{0,\ldots,0}_{k-1 \textup{ db}},\underbrace{1,\ldots,1}_{k-1 \textup{ db}},\underbrace{0,\ldots,0}_{k-1 \textup{ db}})$;
(-5.004887851246821,-2.750677729850206) node[font=,anchor=north west] $(\underbrace{0,\ldots,0}_{k \textup{ db}},\underbrace{1,\ldots,1}_{k \textup{ db}},\underbrace{0,\ldots,0}_{k-2 \textup{ db}})$;
(4.799409338356793,1.2537458946719848) node[font=,anchor=north west] $(1,\underbrace{0,\ldots,0}_{2k-2 \textup{ db}},\underbrace{1,\ldots,1}_{k-1 \textup{ db}})$;
(4.799409338356793,-0.7597778487318287) node[font=,anchor=north west] $(\underbrace{0,\ldots,0}_{k \textup{ db}},1,\underbrace{0,\ldots,0}_{k-2 \textup{ db}},\underbrace{1,\ldots,1}_{k-1 \textup{ db}})$;
(4.7999409338356793,-2.750677729850206) node[font=,anchor=north west] $(1,\underbrace{0,\ldots,0}_{k-1 \textup{ db}},1,\underbrace{0,\ldots,0}_{k-1 \textup{ db}},\underbrace{1,\ldots,1}_{k-2 \textup{ db}})$;
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$1.$] (2.3,0.8) – (4.8,0.8);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$(k+1).$] (2.3,0.8) – (4.8,-1.15);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$(k+1).$] (2.3,-3.2) – (4.8,-3.2);
[line width=0.8pt] (-7,0.8)– (-5,0.8);
[line width=0.8pt] (-5,-3.2)– (-7,-3.2);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$1.$] (-9.5,-1.2) – (-7,-1.2);

[color=black] (-5.814392402105076,1.5431038289535264) node $\frac{nk^2}{\binom{n+2}{3}}$;
[color=black] (-5.874566818387592,-2.4839436578541007) node $1-\frac{nk^2}{\binom{n+2}{3}}$;

On the diagram, the positions of the $1$-s show which holes were part of the given query. The numbers on the arrows tell us the position of the hole from which the searcher received the last nut. Where the diagram splits into several rows, we write the probability of each query occurring on a segment before the query.

Here the nuts can be positioned in the holes in three different ways. They can all be in the same hole, they can all be in separate holes, or two can be together and the third one in a different hole.

* If all three nuts are in the same hole, the searcher finds them with probability $\frac kn\cdot\frac{nk^2}{\binom{n+2}{3}}=\frac{k^3}{\binom{n+2}{3}}$. That is because the hole has to be one of the first $k$ holes ($\frac kn$), then she has to continue with the branch that chooses the first hole again  $\left(\frac{nk^2}{\binom{n+2}{3}}\right)$. The final step is deterministic, so she has no more error possibility there.

* If $2$ nuts are in the same hole, and the last one is in a different one, then there are $(3k-2)(3k-3)$ ways the nuts can be in the holes.
Now we count the ways the searcher can find the nuts following our strategy.

On the upper branch, she can find all nuts in the following ways:

* There are $2$ nuts in one of the first $k$ holes and $1$ nut in one of the last $k-1$ holes. ($\frac{nk^2}{\binom{n+2}{3}}\cdot k(k-1)$)

* There is $1$ nut in one of the first $k$ holes, and the $2$ nuts in one of the holes between the $k+1$-th and the $2k-1$-th. ($\frac{nk^2}{\binom{n+2}{3}}\cdot k(k-1)$)

On the lower branch, the searcher can win in one of the following ways:

* There are $2$ nuts in one of the first $k$ holes and $1$ nut in one of the next $k$ holes. ($(1-\frac{nk^2}{\binom{n+2}{3}})\cdot k^2$)

* There is $1$ nut in one of the first $k$ holes, and the $2$ nuts in one of the next $k$ holes. ($(1-\frac{nk^2}{\binom{n+2}{3}})\cdot k^2$)

Adding these together and using $n=3k-2$, we get that the winning probability of the searcher is:

* If all three nuts are in different holes, then the number of ways the squirrel could hide them is $\binom n3$.

On the upper branch, the searcher can find the nuts if one nut is hidden in one of the first $k$ holes, another one is hidden in the next $k-1$ holes, and one is hidden in the last $k-1$ holes. ($\frac{nk^2}{\binom{n+2}{3}}\cdot k(k-1)^2$)

On the lower branch, the searcher can find them, if there is a nut in the first $k$ holes, a nut in the next $k$ holes, and one in the last $k-2$ holes. ($(1-\frac{nk^2}{\binom{n+2}{3}})\cdot k^2(k-2)$)

Adding these together and using $n=3k-2$, we get that the winning probability of the searcher is:

$$\frac{1}{\binom{n}{3}}\cdot\left(\frac{nk^2}{\binom{n+2}{3}}\cdot k(k-1)^2+\left(1-\frac{nk^2}{\binom{n+2}{3}}\right)\cdot k^2(k-2)\right)=\frac{k^3}{\binom{n+2}{3}}$$

Hence we proved that the value of the game is $\frac{k^3}{\binom{n+2}{3}}$.

We checked our conjecture for a few more cases:
$(5,4,2),(9,4,3),(13,4,4),(6,5,2)$. We include the strategy for the $(5,4,2)$ game, see Figure <ref>.

[line cap=round,line join=round,>=triangle 45,x=0.6cm,y=0.6cm]
(-0.1,-8) rectangle (30,6);
(0,0) node[font=,anchor=north west] $(1,1,0,0,0)$;
(6,2) node[font=,anchor=north west] $(1,0,1,0,0)$;
(6,-4) node[font=,anchor=north west] $(0,0,1,1,0)$;
(12,4) node[font=,anchor=north west] $(1,0,0,1,0)$;
(12,2) node[font=,anchor=north west] $(0,0,1,1,0)$;
(12,-2) node[font=,anchor=north west] $(0,0,1,0,1)$;
(12,-4) node[font=,anchor=north west] $(1,0,0,0,1)$;
(12,-6) node[font=,anchor=north west] $(1,0,1,0,0)$;

(18,5) node[font=,anchor=north west] $(1,0,0,0,1)$;
(18,4) node[font=,anchor=north west] $(0,0,0,1,1)$;
(18,3) node[font=,anchor=north west] $(0,0,1,0,1)$;
(18,2) node[font=,anchor=north west] $(0,0,0,1,1)$;
(18,-1) node[font=,anchor=north west] $(1,0,1,0,0)$;
(18,-2) node[font=,anchor=north west] $(1,0,0,0,1)$;
(18,-3) node[font=,anchor=north west] $(1,0,1,0,0)$;
(18,-4) node[font=,anchor=north west] $(0,0,1,0,1)$;
(18,-5) node[font=,anchor=north west] $(1,0,0,0,1)$;
(18,-6) node[font=,anchor=north west] $(0,0,1,0,1)$;

[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$1.$] (3,-0.5) – (4.5,-0.5);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$1.$] (9,1.5) – (12,3.5);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$3.$] (9,1.5) – (12,1.5);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$3.$] (9,-4.5) – (10.5,-4.5);

[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=right,text=$1.$] (15,3.5) – (18,4.5);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=right,text=$4.$] (15,3.5) – (18,3.5);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=right,text=$3.$] (15,1.5) – (18,2.5);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=right,text=$4.$] (15,1.5) – (18,1.5);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=right,text=$3.$] (15,-2.5) – (18,-1.5);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=right,text=$5.$] (15,-2.5) – (18,-2.5);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=right,text=$1.$] (15,-4.5) – (18,-3.5);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=right,text=$5.$] (15,-4.5) – (18,-4.5);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=right,text=$1.$] (15,-6.5) – (18,-5.5);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=right,text=$3.$] (15,-6.5) – (18,-6.5);

[line width=0.8pt] (4.7,1.5) – (6,1.5);
[line width=0.8pt] (4.7,-4.5) – (6,-4.5);
[line width=0.8pt] (10.7,-2.5) – (12,-2.5);
[line width=0.8pt] (10.7,-4.5) – (12,-4.5);
[line width=0.8pt] (10.7,-6.5) – (12,-6.5);

[color=black] (5.35,1.9) node $\frac47$;
[color=black] (5.35,-4.1) node $\frac37$;
[color=black] (11.35,-2.1) node $\frac13$;
[color=black] (11.35,-4.1) node $\frac13$;
[color=black] (11.35,-6.1) node $\frac13$;

On the diagram, the positions of the $1$-s show which holes were part of the given query. The numbers on the arrows tell us the position of the hole from which the searcher received the last nut. Where the diagram splits into several rows, we write the probability of each query occurring on a segment before the query.

§.§ Evil, Kind, and Random Squirrel

After arguing strategies in the last section, one could be curious to see if it is significant, whether the squirrel can choose which nut he gives the searcher. To figure that out, we define two other versions of the Multiple Caching Game.

The game itself does not change in any of the cases, the only thing that changes is how the squirrel chooses the nut to give away when multiple nuts are found in a single question.

The value of each game is the winning probability of the searcher if both players play optimally.

If the searcher guesses more nuts in a single question, the Evil Squirrel chooses one to give her, following his strategy to win the game.
This is the original version of the Discrete Caching Game.

We still call the value of that game $v_M(n,d,k)$.

If the searcher guesses more nuts in a single question, the Random Squirrel gives the searcher one of them with equal probability.

We call the value of that game $v_{Mr}(n,d,k)$.

If the searcher guesses more nuts in a single question, the Kind Squirrel gives the searcher a nut, following a strategy discussed with the searcher in advance. So basically the searcher decided in advance how to receive the nut.

We call the value of that game $v_{Mj}(n,d,k)$.

For any integer triplet $(n,d,k)$,  $v_M(n,d,k)\leq v_{Mr}(n,d,k)\leq v_{Mj}(n,d,k)\leq\frac{k^d}{\binom{n+d-1}{d}}$.

In the proof of Theorem <ref>.  we only used the hiding strategy and never mentioned how the squirrel chooses which nut to give. Therefore the upper bound holds for all defined versions of the game, even with the kind squirrel.

$v_M(n,d,k)\leq v_{Mr}(n,d,k)$, since the evil squirrel can choose to follow the random squirrel strategy, which gives him a maximal winning chance at least as large as the random squirrel has. Therefore the value of the random squirrel game is at least as large as the evil squirrel game.

$v_{Mr}(n,d,k)\leq v_{Mj}(n,d,k)$, since the searcher can just tell the kind squirrel to apply the random nut-giving strategy, which shows that she can get the same winning probability as in the random squirrel case.

Up until now, all the triplets we checked turned out to be accurate, therefore $v_M(n,d,k)=v_{Mr}(n,d,k)=v_{Mj}(n,d,k)$ was true in the previously discussed games.

We managed to find a triplet, for which these 3 games differ in value. This is the $(3,3,2)$ game. Pálvölgyi in [5] discussed this case, but he made a mistake since he stated that $v_M(3,3,2)=\frac23$. In reality, this value can only be reached in the kind squirrel game, and it is also the largest possible value because of Theorem <ref>.

To find the values of the other two games we used a computer. The method was the following: We made choice variables for every single choice the squirrel or the searcher has during the game. (including hiding strategy, questioning strategy, nut-giving strategy (for which it was fixed for the random squirrel as an equal probability for all included nuts)), these variables ranged between $0$ and $1$ as they described the probability of choosing the given option. From all of these variables, one can calculate the searcher's winning probability with these parameters. Now we shall be aware that the squirrel wants to minimize that probability, and the searcher wants to maximize it. Hence to get the value of the game, the squirrel's choices will always be such that they minimise the probability with the given searcher parameters, and we need to find the searcher strategy for which this minimised value is maximal. The equations were linear in each variable, except the minimums and maximums. Here we just used a simple program to numerically maximize our long function of these parameters.

This maximization must be a lower bound for the game value since for the search strategy it gives, it defined a hiding strategy that makes the winning probability equal to the estimate we got.

We also calculated the other way, so the searcher optimized her steps parametrically based on the squirrel moves, and the program looked for the squirrel choices that minimize the searcher's winning probability. The probability this approach gives must be an upper bound for the value since for that hiding strategy it also gives a searching strategy for which the squirrel loses with the given probability.

Finally, we got the following results:

$0.6312\leq v_{Mr}(n,d,k)\leq 0.6316$

$0.5999\leq v_{M}(n,d,k)\leq 0.6001$

The exact hiding and searching strategies for these bounds can be found in Appendix (<ref>.).

Figure <ref> shows the optimal strategy of the searcher in the kind squirrel game. Here we have shown that $v_{Mj}(3,3,2)=\frac23$.

[line cap=round,line join=round,>=triangle 45,x=0.6cm,y=0.6cm]
(-0.1,-2) rectangle (15,2);
(0,0) node[font=,anchor=north west] $(1,1,0)$;
(5,0) node[font=,anchor=north west] $(1,1,0)$;
(10,1) node[font=,anchor=north west] $(1,0,1)$;
(10,-1) node[font=,anchor=north west] $(0,1,1)$;

[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$1.$] (2,-0.5) – (5,-0.5);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$1.$] (7,-0.5) – (10,0.5);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$2.$] (7,-0.5) – (10,-1.5);

On the diagram, the positions of the $1$-s show which holes were part of the given query. The numbers on the arrows tell us the position of the hole from which the searcher received the last nut.

The searcher has $\frac 23$ winning probability if she applies that strategy. Since the squirrel is kind, the searcher tells him to give a nut from the hole which has the least amount of nuts, if both questioned holes have nuts in them.

Keeping this in mind, we show that this is indeed an optimal strategy for the searcher:

* If the squirrel hides all the nuts in the same hole, then the searcher has $\frac23$ probability of asking it in the first question, and if that happens, she will ask it two more times, so she surely wins if that happens. This gives $\frac23$ winning chance.

* If the squirrel hides two nuts in the same hole, and the last one in another, then there are a few cases.

* With $\frac 13$ chance, one of the first two holes contains $1$ nut, and the other one contains $2$ nuts. Through the kindness of the squirrel, the searcher gets the lonely nut from the first hole. Then it is easy to see that she will ask the second hole $2$ more times.

* With $\frac 13$ chance, hole one has $2$ nuts and hole three has the last nut. In this case, the searcher surely wins again.

* With $\frac 13$ chance, hole one has $1$ nuts and hole three has the other $2$ nuts. In that case, the searcher never wins.

Altogether, we can see that the searcher wins with $\frac 23$ probability in this case too.

* If the squirrel hides all the nuts in different holes, then following the diagram one can see that the searcher will always find all $3$ nuts. So she surely wins in that case.

Therefore we can see that this strategy has $\frac 23$ winning probability even in the worst case. It is an optimal strategy since the upper bound of Theorem <ref> holds.

§.§ Lower bound for $v_M(n,d,k)$ as $d \to \infty$

We proved that $v_M(n,d,k)$ is monotonically decreasing with respect to $d$. This makes one wonder, whether as $d\to\infty$ how does the value of the Multiple Caching Game behave? We show that the value does not converge to $0$ if $k \geq 2$. Hence there is a positive probability, such that no matter how many nuts the squirrel hides, the searcher can find all of them. Now we restate and prove the main theorem of this subsection:

Fix $n$ and $k \geq 2$. We define a strategy that finds all the nuts with a probability independent from $d$: In the first step, the searcher asks $k$ arbitrarily chosen holes. In all the subsequent steps, she asks the hole she received the nut from in the previous step and asks $k-1$ more holes chosen uniformly out of all the other holes. In the first step, she loses with probability at most $\frac{n-k}n$ since there must be at least one hole with a nut. In a general step, the searcher can only lose, if the last nut she received was the last in its hole. If before the step there were $i-1$ empty holes, and after the step there are $i$ empty holes, then in the next step the searcher loses with probability $\frac{\binom{i-1}{k-1}}{\binom{n-1}{k-1}}$, since she guesses $k-1$ random holes out of all the remaining ones. Therefore the win probability of the searcher with this strategy is at least
$c(n,k)=\left(1-\frac{n-k}n \right)\cdot\prod\limits_{i=1}^{n-1}\left( 1-\frac{\binom{i-1}{k-1}}{\binom{n-1}{k-1}} \right)>0$.

For any $k \geq 2$, $v_A(n,d,k) \geq c(n,\lfloor k \rfloor)>0$, where $c(n,\lfloor k \rfloor)$ is a positive constant only depending on $n$ and $\lfloor k \rfloor$.

Using Theorem <ref>.  for any integer $k$, $v_A(n,d,k) \ge c(n,k)$. For non-integer $k$ values, $v_A(n,d,k) \ge v_A(n,d,\lfloor k \rfloor)\ge c(n,\lfloor k \rfloor)$ using the game's definition.

§ CONTINUOUS VERSIONS

§.§ Discrete game for real $k$ values

We can define the game for non-integer values of $k$. The searcher is allowed to use a probabilistic strategy, giving a probability for each possible query, such that the expected number of chosen holes is $k$.

In this whole section, we assume $k$ to be any positive real number.

$\frac{k^d}{\binom{n+d-1}{d}}$ is an upper bound for the value of the Discrete Caching Game with arbitrary positive real $k$ values.

We want to use the proof of Theorem <ref> and show that the expected number of hiding positions the searcher can find is at most $k^d$.
We argue the following way. We do not know how many allocations of $d-1$ nuts the searcher can find in the first $d-1$ steps, so we call it $E_{d-1}$, but we do know that in the last step, the searcher is expected to find a nut in at most $k$ positions. So the expected value of all the cases the searcher can find (call it $E_d$) is certainly $E_d\leq kE_{d-1}$.
Similarly, we call the expected number of $d-2$ nut allocations the searcher can find in the first $d-2$ questions $E_{d-2}$, and notice that in the $d-1$-th question she is expected to ask $k$ holes. Therefore it is sure that $E_{d-1}\leq kE_{d-2}$. Continuing that argument until $E_1=k$, and substituting every inequality in the last one we get $E_d\leq k^d$. Therefore the proof of Theorem <ref> works here too.

If $n$ is large enough compared to $d$ and $k$, then the value of the game is $\frac{k^d}{\binom{n+d-1}{d}}$ for any positive real $k$.

We already have the upper bound from the previous theorem.

For the lower bound, we use a search strategy similar to the one in the paper of Pálvölgyi. <cit.>.
In each step, the searcher will ask $\lfloor k\rfloor$ holes with probability $p$ and $\lceil k\rceil$ holes with probability $1-p$ such that the expected value is $k$.
We define $p_\lambda (n,d,1)$ the same way Pálvölgyi did in his paper.

For this, we need to revisit the strategy of the searcher if she can only ask 1 hole in each step. Then her strategy is the following:

She picks randomly a starting allocation $\mu$ of the nuts, uniformly distributed among all the $\binom{n+d-1}{d}$ possibilities. Then she will ask the hole with the most nuts in $\mu$. She asks it as many times, as many nuts are there in that hole in $\mu$.
Then she asks the hole with the second most nuts and asks just enough times to make it empty assuming $\mu$. She repeats that until she asked all her questions. If several holes have the same amount of nuts, she picks one of them with equal probability. This way, if we count the found nuts in the holes she picked in order, we get a Young diagram $\lambda$ at any point of the game.
For the outside observer, who does not know $\mu$, the Young diagram $\lambda$ tells a probability of the searcher asking the same hole again in the next question. (provided that the observer knows the strategy, but does not know the $\mu$, he can calculate conditional probabilities of all possible Young diagram shapes.). This probability with a given Young table $\lambda$ is called $p_\lambda (n,d,1)$.
Now we define $p_\lambda (n,d,s)=s\cdot p_\lambda (n,d,1)$.

We now have to assume that $n$ is large enough, such that $p_\lambda (n,d,\lceil k\rceil)\leq 1$, and also such that $n\geq d\cdot \lceil k\rceil$.

Now we can define the strategy of the searcher. The strategy will be such a strategy, that the found nuts will form a Young diagram at any point. If $k$ is an integer, use the same strategy Pálvölgyi described in his paper. If $k$ is not an integer, then the searcher will ask:

* The hole she received the last nut from, and $\lfloor k\rfloor-1$ brand new, previously untouched holes with $p\cdot p_\lambda (n,d,\lfloor k\rfloor)$ probability.

* $\lfloor k\rfloor$ brand new, previously untouched holes with $p\cdot (1-p_\lambda (n,d,\lfloor k\rfloor))$ probability.

* The hole she received the last nut from, and $\lceil k\rceil-1$ brand new, previously untouched holes with $(1-p)\cdot p_\lambda (n,d,\lceil k\rceil)$ probability.

* $\lceil k\rceil$ brand new, previously untouched holes with $(1-p)\cdot (1-p_\lambda (n,d,\lceil k\rceil))$ probability.

Now we need to show that this strategy wins with $\frac{k^d}{\binom{n+d-1}{d}}$ probability. If any question asks more than one hole that contains nuts, the searcher has already lost. Therefore, it is enough to show that with this strategy, each step has $k$ times the probability of finding the door $i$ with a nut than the corresponding step in the $k=1$ case.

Here we have 2 cases to consider: If door $i$ is the door she last received a nut from, then if $k=1$, she had a probability $p_\lambda (n,d,1)$ to find it. In the current strategy, her chance to find the hole is:

$p\cdot p_\lambda (n,d,\lfloor k\rfloor)+(1-p)\cdot p_\lambda (n,d,\lceil k\rceil)=p_\lambda (n,d,1)\cdot (p\lfloor k\rfloor +(1-p)\lceil k\rceil)=k\cdot p_\lambda (n,d,1)$

which we wanted to show.

If door $i$ is a new door and $k=1$ she had probability $1-p_\lambda (n,d,1)$ to find it.
In the current strategy, her chance to find the hole is:

$(\lfloor k\rfloor-1)\cdot p\cdot p_\lambda (n,d,\lfloor k\rfloor)+\lfloor k\rfloor \cdot p\cdot (1-p_\lambda (n,d,\lfloor k\rfloor))+(\lceil k\rceil-1)\cdot (1-p)\cdot p_\lambda (n,d,\lceil k\rceil)+\lceil k\rceil \cdot (1-p)\cdot (1-p_\lambda (n,d,\lceil k\rceil))=\\(\lfloor k\rfloor p+\lceil k\rceil (1-p))-(p\cdot p_\lambda (n,d,\lfloor k\rfloor)+(1-p)\cdot p_\lambda (n,d,\lceil k\rceil))=k\cdot (1-p_\lambda (n,d,1)$

which we wanted to show.

If $k$ was $1$, the searcher could win the game with probability $\frac{1}{\binom{n+d-1}{d}}$. Therefore since the game consists of $d$ steps, and the chance of finding a new nut in each step is $k$ times the chance of finding it with $1$-sized queries, we get that the winning probability of the searcher is $\frac{k^d}{\binom{n+d-1}{d}}$.

§.§ Peanut butter

We also generalised the Multiple Caching Game for non-integer nut numbers. In this game the squirrel is not hiding nuts, he is hiding peanut butter in the holes. He has a jar of $d$ units of peanut butter which he digs into the holes entirely, putting into each hole some non-negative real quantity of peanut butter. Here the searcher can choose $k$ holes for a query, and if those $k$ holes contain together at least $1$ unit of peanut butter, then the squirrel gives her $1$ unit of peanut butter out of those holes as he wants. Otherwise, the searcher lost.

Even if the searcher only wants to find $1$ unit of peanut butter, the game is still not trivial. Hence we considered that case first. Here the searcher does not have a strategy, she just chooses $k$ out of the $n$ holes and wins if these holes contain at least $1$ unit of peanut butter. The hider wants to spread the peanut butter in a way to minimise the sets of $k$ holes that contain $1$ unit of butter added together.

If $d\geq n$ then no matter how the squirrel hides, there will be a hole with at least $1$ unit of peanut butter. Therefore the squirrel has the best winning probability if he hides all the peanut butter in that single hole. In this case, the searcher has a win probability of $\frac{k}{n}$. If $d< \frac{n}{k}$ then the squirrel can just hide the same amount of peanut butter in each hole, making it impossible to find $k$ holes that sum up to $1$ unit of nut.
The interesting cases to see are when $d$ is between these two values.

If $k\mid n$, then there is no in-between case, so whenever $d \geq \frac{n}{k}$, the searcher will win with probability at least $\frac{k}{n}$.

To prove that, we use the Baranyai Theorem [6]: We can partition the set of all $k$-element subsets of $[n]$ in a way such that each partition contains $\frac{n}{k}$ elements, whose disjoint union is precisely $[n]$. Since altogether there are at least $\frac{n}{k}$ units of peanut butter in the holes, in each partition at least one of the $k$-element sets must contain at least $1$ unit of peanut butter by the pigeonhole principle. Therefore at least  $\frac{1}{\frac{n}{k}}$ fraction of all $k$-elemented sets have at least $1$ unit of peanut butter, so the searcher wins with a probability at least $\frac{k}{n}$.

If $k \nmid n$, usually there are cases in-between:

If $n=5$, $k=2$ and $\frac{5}{2} \leq d < 3$, the best hiding strategy of the squirrel gives a chance of $\frac{3}{10}$ for the searcher to win.

If the squirrel hides $\frac{d}{3}$ units in $3$ holes, and nothing in the other holes, the searcher can only win if she guesses $2$ of these $3$ holes. She has $\frac{3}{10}$ chance to do so.

Now we show that the hider cannot achieve $\frac{2}{10}$ probability of the searcher succeeding.
Suppose there is such a hiding allocation. Let's say that the holes contain $a_1 \geq a_2 \geq a_3 \geq a_4 \geq a_5$ units of peanut butter respectively. Since precisely $2$ of the pairwise sums add up to at least $1$ unit, these sums must be $a_1+a_2$ and $a_1+a_3$.
Hence the other sums must be strictly less than $1$, which means $a_1+a_4, a_1+a_5, a_4+a_5$ are all less than $1$. Therefore $a_1+a_4+a_5<\frac32$. We also know $a_2+a_3<1$. Therefore $d=a_1+a_2+a_3+a_4+a_5<\frac{5}{2}$, which is not a possible value for $d$.

Our question is quite similar to the Manickam-Miklós-Singhi Conjecture, which can be found in Csóka's paper [3]. It was stated there for a different reason because it has a similar limes problem to a limes problem of Alpern's Caching Game.

Let $n,k$ be fixed integers. Let $\{i_1, i_2, \dots, i_k \} \subset \{ 1,2, \dots, n\}$ be a $k$ elemented subset, chosen uniformly. Try to find $a_1,a_2, \dots, a_n$ real numbers, such that
\begin{equation}\label{MMSeq}
P\left( a_{i_1} + a_{i_2} + \dots + a_{i_k} > \frac{k}{n} \sum\limits_{i=1}^n a_i \right)
\end{equation}
is maximized.

If $4k \leq n$, then the maximum probability is $1 - \frac{k}{n}$.

Notice that if we ask about maximizing
\begin{equation*}
P\left( a_{i_1} + a_{i_2} + \dots + a_{i_k} < \frac{k}{n} \sum\limits_{i=1}^n a_i \right)
\end{equation*}
instead, we get an equivalent question since if we have an optimal solution for one of them, we can just reflect all of the numbers over their average to get a solution to the other question. This new question is then equivalent to minimizing

\begin{equation*}
P\left( a_{i_1} + a_{i_2} + \dots + a_{i_k} \geq \frac{k}{n} \sum\limits_{i=1}^n a_i \right)
\end{equation*}
. Based on the conjecture, the optimal solution would give $\frac{k}{n}$ whenever $4k \leq n$.

We can call the units of the peanut butter in each corresponding hole as $a_1,a_2\dots ,a_n$, and their sum as $d$. If $\frac{k}{n} d =1$, then we get an equivalence between the question of the Manickam-Miklós-Singhi Conjecture and the game with $d=\frac nk$. So if the MMS conjecture is true, it would mean that in our game, whenever $4k \leq n$ there are no cases between $d<\frac nk$ and $d\geq n$.

For all the games that had in-between cases, the best hiding strategy was always of a specific kind, so we conjecture that this is always true:

No matter what the parameters are, there is always an optimal hiding strategy of the following form: The hider chooses $r$ holes and hides exactly $\frac dr$ units of peanut butter in each of them. The rest of the holes remain empty.

§ ACKNOWLEDGEMENT

The research was carried out in the REU 2021 programme at Eötvös Loránd University in Budapest. We are tremendously grateful to Dömötör Pálvölgyi and Dániel Lenger for supervising us and organising the programme.

[1] S. Alpern, R. Fokkink, T. Lidbetter, and N. S. Clayton, A search game model of the scatter hoarder’s problem, Journal of The Royal Society Interface 9(70):869–879, 2012.

[2] Search theory: a game theoretic perspective (S. Alpern, R. Fokkink, G. Leszek, R. Lindelauf,
V. S. Subrahmanian (Eds.)), Springer Science & Business Media, 2013.

[3] Endre Csóka, Limit theory of discrete mathematics problems, <https://arxiv.org/pdf/1505.06984.pdf>

[4]  E. Csóka and T. Lidbetter, The solution to an open problem for a caching game, Naval Research Logistics 63(1):23–31, 2016.

[5] Dömötör Pálvölgyi, All or Nothing Caching Games with Bounded Queries, International Game Theory Review, 20(1):1-9, 2018., <https://arxiv.org/pdf/1702.00635.pdf>

[6] Zs. Baranyai, On the factorization of the complete uniform hypergraph, in Infinite and Finite
Sets (A. Hajnal, R. Rado, V. T. Sós, (Eds.)), Proc. Coll. Keszthely, Colloquia Math. Soc.
János Bolyai 10, North-Holland, 91–107, 1973.

Details of the authors:

Áron Jánosik, ELTE<EMAIL_ADDRESS>
Csenge Miklós, ELTE<EMAIL_ADDRESS>
Dániel Gábor Simon, Rényi Institute<EMAIL_ADDRESS>
Kristóf Zólomy, ELTE<EMAIL_ADDRESS>
Dömötör Pálvölgyi, ELTE Department of Computer Science

Dániel Lenger, ELTE Department of Computer Science

§ SEARCHING STRATEGIES WITH PROGRAMMING

[line cap=round,line join=round,>=triangle 45,x=0.6cm,y=0.6cm]
(-0.1,-13) rectangle (20,13);
(0,0) node[font=,anchor=north west] $(1,1,0)$;

(8,8) node[font=,anchor=north west] $(1,1,0)$;
(8,0) node[font=,anchor=north west] $(1,0,1)$;
(8,-8) node[font=,anchor=north west] $(0,1,1)$;

(16,11) node[font=,anchor=north west] $(1,1,0)$;
(16,10) node[font=,anchor=north west] $(1,0,1)$;
(16,9) node[font=,anchor=north west] $(0,1,1)$;

(16,7) node[font=,anchor=north west] $(1,1,0)$;
(16,6) node[font=,anchor=north west] $(1,0,1)$;
(16,5) node[font=,anchor=north west] $(0,1,1)$;

(16,3) node[font=,anchor=north west] $(1,1,0)$;
(16,2) node[font=,anchor=north west] $(1,0,1)$;
(16,1) node[font=,anchor=north west] $(0,1,1)$;

(16,-1) node[font=,anchor=north west] $(1,1,0)$;
(16,-2) node[font=,anchor=north west] $(1,0,1)$;
(16,-3) node[font=,anchor=north west] $(0,1,1)$;

(16,-5) node[font=,anchor=north west] $(1,1,0)$;
(16,-6) node[font=,anchor=north west] $(1,0,1)$;
(16,-7) node[font=,anchor=north west] $(0,1,1)$;

(16,-9) node[font=,anchor=north west] $(1,1,0)$;
(16,-10) node[font=,anchor=north west] $(1,0,1)$;
(16,-11) node[font=,anchor=north west] $(0,1,1)$;

[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$1.$] (2,-0.5) – (5,-0.5);

[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$1.$] (10,7.5) – (13,9.5);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$2.$] (10,7.5) – (13,5.5);

[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$1.$] (10,-0.5) – (13,1.5);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$3.$] (10,-0.5) – (13,-2.5);

[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$2.$] (10,-8.5) – (13,-6.5);
[->,line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$3.$] (10,-8.5) – (13,-10.5);

[line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$p{_1}$] (5.5,7.5) – (7.5,7.5);
[line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$p{_2}$] (5.5,-0.5) – (7.5,-0.5);
[line width=0.8pt] (5.5,-8.5) – (7.5,-8.5);

[line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$p{_3}$] (13.5,10.5) – (15.5,10.5);
[line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$p{_4}$] (13.5,9.5) – (15.5,9.5);
[line width=0.8pt] (13.5,8.5) – (15.5,8.5);

[line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$p{_5}$] (13.5,6.5) – (15.5,6.5);
[line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$p{_6}$] (13.5,5.5) – (15.5,5.5);
[line width=0.8pt] (13.5,4.5) – (15.5,4.5);

[line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$p{_7}$] (13.5,2.5) – (15.5,2.5);
[line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$p{_8}$] (13.5,1.5) – (15.5,1.5);
[line width=0.8pt] (13.5,0.5) – (15.5,0.5);

[line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$p{_9}$] (13.5,-1.5) – (15.5,-1.5);
[line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$p{_{10}}$] (13.5,-2.5) – (15.5,-2.5);
[line width=0.8pt] (13.5,-3.5) – (15.5,-3.5);

[line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$p{_{11}}$] (13.5,-5.5) – (15.5,-5.5);
[line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$p{_{12}}$] (13.5,-6.5) – (15.5,-6.5);
[line width=0.8pt] (13.5,-7.5) – (15.5,-7.5);

[line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$p{_{13}}$] (13.5,-9.5) – (15.5,-9.5);
[line width=0.8pt,postaction=decorate,decoration=raise=1ex,text along path,text align=center,text=$p{_{14}}$] (13.5,-10.5) – (15.5,-10.5);
[line width=0.8pt] (13.5,-11.5) – (15.5,-11.5);

On the diagram, the positions of the $1$-s show which holes were part of the given query. The numbers on the arrows tell us the position of the hole from which the searcher received the last nut. Where the diagram splits into several rows, we write the probability of each query occurring on a segment before the query.

§ PARAMETERS AND RESULTS FOUND BY THE PROGRAM

The following values were found by numerically maximizing the winning probability of the searcher, which can be described as a long expression of all the parameters the searcher can choose.

\begin{array}{ | l | l | }
\hline
\text{Random Squirrel searching strategy:} & \text{Evil Squirrel searching strategy:} \\ \hline
v_{Mr}(3,3,2) =  & v_M(3,3,2) = \\ \hline
0.631266583766597 &   0.599999998988798 \\ \hline
p_1 =  & p_1 = \\ \hline
1.433265356398650\cdot10^{-8} &    0.300000004173928 \\ \hline
p_2 =  & p_2 = \\ \hline
0.946899861317246 &    0.599999994319573 \\ \hline
p_3 =  & p_3 = \\ \hline
2.125486469051197\cdot10^{-7} &      1.217151379684367\cdot10^{-10} \\ \hline
p_4 =  & p_4 = \\ \hline
0.999999712433013 &    0.999999999878112 \\ \hline
p_5 =  & p_5 = \\ \hline
4.989166940971845\cdot10^{-5} &      3.085953476089642\cdot10^{-8} \\ \hline
p_6 =  & p_6 = \\ \hline
0.442763073625245 &      2.598550738776247\cdot10^{-10} \\ \hline
p_7 =  & p_7 = \\ \hline
0.999999990714073 &    0.500000011498288 \\ \hline
p_8 =  & p_8 = \\ \hline
9.285925092871882\cdot10^{-9} &    0.499999988484626 \\ \hline
p_9 =  & p_9 = \\ \hline
2.718295488701727\cdot10^{-8} &      6.920797268605838\cdot10^{-12} \\ \hline
p_{10} =  & p_{10} = \\ \hline
0.342734797303237 &    0.499999988494791 \\ \hline
p_{11} =  & p_{11} = \\ \hline
0.664699872406349 &    0.999999999901808 \\ \hline
p_{12} =  & p_{12} = \\ \hline
0.335300123056941 &      1.069900352273958\cdot10^{-12} \\ \hline
p_{13} =  & p_{13} = \\ \hline
1.314916509009834\cdot10^{-10} &      1.003127747534194\cdot10^{-9} \\ \hline
p_{14} =  & p_{14} = \\ \hline
0.999999965441518 &    0.999999996373835 \\ \hline
\end{array}$

In the next table, we write the hiding strategies of the squirrel. This was also found by a numerical minimizer program, which was running on the long expression describing the winning probability of the searcher based on the squirrel's parameters.

$l_1$: The probability of the squirrel hiding all of the nuts in the same hole.

$l_2$: The probability of the squirrel hiding each of the nuts in separate holes.

$l_3$: The probability of the squirrel hiding $2$ nuts in the same hole, and the third one in a different hole.

$q_1$: If the first hole contains $2$ nuts, the third one contains $1$ nut, then if in the second question, the searcher asks holes $1$ and $3$, the squirrel will give the nut from hole $1$ with $q_1$ probability.

$q_2$: If the first hole contains $1$ nut, and the second one contains $2$ nuts, the squirrel will give the nut from the first hole with $q_2$ probability.

$q_3$: If the first hole contains 2 nuts, the second contains 1 nut, and in the first step the searcher received a nut from the first hole, and she asks holes $1$ and $2$ again, the squirrel will give her a nut from hole $1$ with $q_3$ probability.

$q_4$: If all $3$ holes contain $1$ nut, the searcher received a nut from the first hole in the first step, and in the second question she asks holes $2$ and $3$, the squirrel will give her the nut from hole $2$ with $q_4$ probability.

$\begin{array}{ | l | l | }
\hline
\text{Random Squirrel hiding strategy} & \text{Evil Squirrel hiding strategy} \\ \hline
v_{Mr}(3,3,2) =  & v_M(3,3,2) =  \\ \hline
0.631579844026254 &    0.600002218914396 \\ \hline
l_1 =  & l_1 =  \\ \hline
0.263159544659304 &    0.300001109457198 \\ \hline
l_2 =  & l_2 =  \\ \hline
0.105264762894245 &    0.099996671628406 \\ \hline
l_3 =  & l_3 =  \\ \hline
0.631575692446451 &    0.600002218914396 \\ \hline
q_1 =  & q_1 =  \\ \hline
0.500000000000000 &    0.500018490884919 \\ \hline
q_2 =  & q_2 =  \\ \hline
0.333333333333333 &    0.500018490884919 \\ \hline
q_3 =  & q_3 =  \\ \hline
0.500000000000000 &    0.955197063889760 \\ \hline
q_4 =  & q_4 =  \\ \hline
0.500000000000000 &    0.319507062168597 \\ \hline

\end{array}$


# Redefining Aerial Innovation: Autonomous Tethered Drones as a Solution to
Battery Life and Data Latency Challenges

Samuel O. Folorunsho  *  A , , and William R. Norris  *  A

# Redefining Aerial Innovation: Autonomous Tethered Drones as a Solution to
Battery Life and Data Latency Challenges

Samuel O. Folorunsho  *  A , , and William R. Norris  *  A

###### Abstract

The emergence of tethered drones represents a major advancement in unmanned
aerial vehicles (UAVs) offering solutions to key limitations faced by
traditional drones. This article explores the potential of tethered drones
with a particular focus on their ability to tackle issues related to battery
life constraints and data latency commonly experienced by battery operated
drones. Through their connection to a ground station via a tether, autonomous
tethered drones provide continuous power supply and a secure direct data
transmission link facilitating prolonged operational durations and real time
data transfer. These attributes significantly enhance the effectiveness and
dependability of drone missions in scenarios requiring extended surveillance,
continuous monitoring and immediate data processing needs. Examining the
advancements, operational benefits and potential future progressions
associated with tethered drones, this article shows their increasing
significance across various sectors and their pivotal role in pushing the
boundaries of current UAV capabilities. The emergence of tethered drone
technology not only addresses existing obstacles but also paves the way for
new innovations within the UAV industry.

Index Terms – Autonomous Drones, Tethered Drones, UAV, Battery Life, Data
Transmission.

##  I Introduction

Aerial technology has undergone notable advancements with the introduction and
evolution of drone technology. Drones, once seen as a novelty have now become
tools in various industries from surveillance to agriculture disaster
management to entertainment. Tethered drones, which simply can be defined as
drones with physical connection to a ground station through a cable called
tether, are changing the usability of drones in many of these industries. The
global market for tethered drones has experienced significant growth with an
estimated value of US$ 327 million in 2022 and a projected rise to
approximately US$ 1629.7 million by 2029 indicating a Compound Annual Growth
Rate (CAGR) of 25.8% [1]. This increase not only reflects the increasing
interest but also the expanding use of tethered drone technology across
different sectors.

Tethered drones are gaining popularity for reasons that set them apart from
traditional drones [2, 3, 4]. While conventional drones are known for their
versatility and agility they face limitations related to battery life and data
transmission. The finite battery capacity often results in restricted time
leading to frequent recharges or replacements that disrupt continuous
operations. Additionally these drones encounter issues with data latency which
can hinder real time data transmission critical for applications relating to
autonomous navigation.

The advent of tethered drones is changing this landscape by addressing
challenges related to battery life and data latency offering improved
reliability and consistent performance. The physical connection not only
ensures a constant power source but also creates a steady platform for data
transfer up to 10Gb per second via fiber optics [5] improving the safety and
efficiency of operations.

##  II Understanding Autonomous Tethered Drones

In industries utilizing unmanned aerial vehicles (UAVs), autonomous tethered
drones mark a major technological advancement overcoming key limitations of
untethered drones.

###  II-A Tethered Drones Concept and Design

Tethered drones are UAVs linked physically to a ground station or vehicle
through a cord [6]. This cord, usually made up of power cables and data lines
serves two purposes. Firstly it supplies power to the drone eliminating
battery life constraints common in regular drones. This feature allows for
flight times sometimes even indefinitely which is extremely useful for
continuous monitoring or surveillance missions. Additionally, the tether
serves as a channel for high speed data transfer. Unlike drones that depend on
wireless communication systems, which are prone to delays, signal interference
and security risks, tethered drones offer a direct and reliable data
connection. This guarantees data transmission without the interruptions or
security vulnerabilities associated with wireless signals.

###  II-B Advancements in Technology

The emergence of tethered drones has been supported by significant progress in
drone technology and tether materials. Modern tethers can efficiently transmit
power and data while being lightweight and durable to minimize any impact on
the drones agility. Improvements in drone design have also led to compact and
effective models capable of performing various tasks despite being physically
connected by a tether. Their ability to execute tasks without human input is a
result of advancements in artificial intelligence and machine learning. These
technologies empower drones to navigate, adapt to conditions and even make
operational decisions independently enhancing their versatility and
effectiveness.

###  II-C Operational Advantages

The benefits of using tethered drones are abundant. Their continuous power
source allows for missions without the hassle of changing or recharging
batteries [7, 8]. This feature proves valuable in scenarios where
uninterrupted aerial surveillance is crucial like during large events,
prolonged surveillance tasks or ongoing monitoring of industrial areas or
time-sensitive agricultural tasks.

Moreover the direct and secure data transmission function ensures that high
quality data be it video feeds, images or sensor readings can be instantly and
securely relayed. This capability is essential in situations requiring real
time data, such as emergency responses or monitoring infrastructure in real
time.

These operational advantages not only address key limitations of traditional
drones but also open up new possibilities for their usage across different
industries.

##  III Addressing Battery Life Limitations

Addressing Battery Life Limitations One of the obstacles faced by conventional
drone technology is the restriction imposed by battery life. This section
explores how autonomous tethered drones tackle and surpass these limitations.

###  III-A The Challenge of Drones Reliant on Batteries

Relying on battery power poses a dilemma for drones. While it grants them
freedom of movement and adaptability, it also imposes restrictions on their
usage duration. Despite advances in technology, batteries still have an energy
capacity restricting flight times to around 20 to 40 minutes before
necessitating a recharge or replacement. Please see Fig.1 for the average
battery life of popular drone makers and Table I for a more detailed list.
This limitation is not merely an obstacle; it can prove crucial in scenarios
that demand extended aerial presence, such as ongoing surveillance, continuous
data collection or lengthy inspections.

TABLE I: Battery life of various drone models across manufacturers. Manufacturer | Model | Battery Life (min) | Source
---|---|---|---
DJI | Mini 2 | 31 | [9]
| Air 2S | 31 | [10]
| Mini 3 | 34 | [11]
| Mavic 3 | 46 | [12]
| FPV | 20 | [13]
| Matrice 300 | 55 | [14]
Yuneec International | Breeze | 12 | [15]
| Typhoon H | 25 | [15]
| Q500 4K | 25 | [15]
| Mantis Q | 33 | [15]
| H520 | 28 | [15]
PowerVision | PowerEgg X | 34 | [16]
| Power Eye | 29.5 | [17]
Parrot | Anafi | 25 | [18]
| Bebop | 30 | [19]
| Anafi Ai | 32 | [20]
Autel Robotics | Evo max | 42 | [21]
| Evo II | 38 | [22]
| Evo Lite | 40 | [23]
Skydio | X10 | 40 | [24]
| X2 | 35 | [25]
| 2+ | 27 | [26]
FreeFly | Alta X | 30 | [27]
| Astro | 37 | [28]
Figure 1: Average battery life of drones across manufacturers. Sources listed
in Table I

Furthermore, battery performance is influenced by different environmental
factors. Extreme temperatures for example can notably diminish battery
efficiency further curtailing flight durations. The frequent need for
recharging or changing batteries leads to downtime and can interrupt the
seamless execution of tasks. In operations like search and rescue missions or
disaster responses or agricultural insecticide spraying where time is of the
essence, these constraints can have significant repercussions.

###  III-B Tethered Drones: A Leap in Endurance

Autonomous drones offer an innovative solution to the challenge of battery
life. By drawing power from a ground based source via the tether, these drones
can operate for extended periods – as long as the power supply remains
uninterrupted. This consistent power supply brings an advantage especially for
tasks that require prolonged operational periods. Using this approach not only
extends the flight time but also ensures reliable performance. Unlike
batteries that can lose power over time the constant and dependable power
supply from the tether enables the drone to function efficiently throughout
its mission.

###  III-C Enhanced Operational Efficiency

The longer operational duration of drones enhances their overall efficiency.
By eliminating the limitation of battery life these drones can be deployed for
missions without frequent interruptions for recharging. This continuous
operation allows for thorough data collection, uninterrupted surveillance and
prolonged inspection tasks without interruptions or downtime associated with
changing batteries.

Moreover this enhanced efficiency results in cost savings in the long term. By
reducing the need for multiple drones to cover missions and minimizing
downtime, operational costs are lowered along with resource utilization.

##  IV Overcoming Data Latency

Apart from tackling battery life issues, autonomous tethered drones also play
a role in addressing the problem of data latency, which significantly impacts
the efficiency of drone operations. This section explores how these advanced
drones offer a solution to data transmission delays that often hinder drones.

###  IV-A Data Latency in Conventional Drones

Data latency refers to the time gap between when the drone captures data
through onboard sensors and when it is sent to the operator or processing
center. In drones that rely on wireless communication systems, various factors
contribute to data latency, including signal interference, bandwidth
constraints and the distance between the drone and the receiver. In situations
like emergency responses or real time surveillance even a slight delay can
hinder operation effectiveness potentially leading to risks or missed
opportunities.

Moreover, wireless transmission is vulnerable to security threats. The
transmitted data can be breached, posing risks to sensitive information
confidentiality and integrity. This poses concerns in fields such as law
enforcement, border monitoring and corporate espionage.

###  IV-B The Tethered Advantage

Autonomous tethered drones present a solution to these challenges. The
physical tether establishes a secure link, for data transmission.

This direct physical link ensures data transfer effectively even up to 10Gb/s
for fiber optics cables removing the delay linked with wireless
communications. The immediacy of this data transfer is crucial in situations
where real time analysis and prompt decision making are vital.

Furthermore, the tethered system offers a pathway for data transmission. The
physical connection is less susceptible to interception or hacking when
compared to wireless signals thus significantly boosting data security. This
is especially important in activities that demand levels of privacy like
military operations or monitoring critical infrastructure.

###  IV-C Enhanced Data Transmission Capabilities

The enhanced data transfer capabilities of drones go beyond just reducing
delays. They also enable the transmission of larger amounts of data and
support higher quality data streams. For example, the stable connection
facilitates the transfer of high definition video feeds which are essential
for detailed surveillance and inspection tasks.

Additionally, the reliability of the connection ensures consistent performance
even in challenging environments where wireless communications could be
compromised such as heavily populated urban areas or remote locations with
limited connectivity.

Autonomous tethered drones effectively address the data latency challenges
often encountered in drone operations. By enabling time, secure and high
capacity data transmission, they facilitate more efficient and productive
operations, across various applications. This advancement in technology not
only improves drone capabilities but also broadens its potential applications
making it a valuable tool in our increasingly data centric world.

##  V Challenges and Future Prospects

While autonomous tethered drones offer advantages over traditional models,
they do come with their own set of challenges. This section looks into these
limitations and the future possibilities of this technology outlining both the
challenges and the potential advancements on the horizon.

###  V-A Challenges Facing Tethered Drones

  * •

Mobility Limitations: One key challenge is the mobility caused by the physical
tether. Although it ensures power and secure data transmission, it constrains
the drones operational range. Navigating environments or covering extensive
areas can be more demanding for tethered drones compared to their untethered
counterparts. Future research can consider integrating the tethering station
on a moving platform to enhance mobility and coverage.

  * •

Tether Management: The handling of the tether itself presents challenges.
Ensuring that it remains untangled, undamaged and does not hinder operations
requires planning and at times additional equipment. Future research in this
area can explore advanced and model-based control systems to ensure the tether
is always taut and not too taut to affect the drone navigation.

  * •

Deployment Time: Tethered drones may require setup times more than battery
operated drones. The necessity to set up the tether system could potentially
delay readiness, in time sensitive scenarios. Research in this area could
explore automating the deployment system with minimal human interactions.

  * •

Weather and Environmental Impact: Although tethered drones are more resistant
to conditions compared to battery powered drones, they can still be affected
by extreme weather impacting both their performance and the durability of the
tether. For example, the tether might be affected by a gause of wind thereby
affecting the stability of the drone. Research in this area should explore
incorporating disturbances like wind and drag into the dynamics of both the
drone model and the tether model.

###  V-B Future Prospects and Technological Developments

Despite these obstacles the future of tethered drones appears promising, with
various avenues for technological progress;

  * •

Advanced Tether Materials and Designs: Research focusing on developing more
flexible, sturdy and lightweight tether materials could improve the agility
and range of tethered drones. Innovations in tether design may involve
mechanisms for deployment and automated management systems for tethers.

  * •

Improved Autonomy and AI Integration: Progress in intelligence and self-guided
navigation will further boost the capabilities of these drones making them
more effective and adaptable in intricate operational settings.

  * •

Expanded Applications: With advancements, new uses for tethered drones are
likely to emerge. This could involve utilizing them in communication networks,
traffic control systems and extensive environmental monitoring efforts.

  * •

Integration with Other Technologies: The potential integration of tethered
drones with emerging technologies, like 5G networks, IoT devices and advanced
sensors could introduce fresh opportunities while enhancing their operational
efficiency.

##  VI Conclusion

This article explored the emerging technology of tethered drones and their
abilities to revolutionize the functionalities and uses of unmanned aerial
vehicles. The examination has shed light on how these drones tackle the
constraints of traditional battery operated drones especially concerning
operational endurance and data transmission reliability. With their tethered
configuration enabling power supply and secure real time data transfer, new
avenues for extended and effective drone operations are unlocked. Nevertheless
the path of tethered drones is not without its hurdles. Challenges like
mobility, tether management issues and susceptibility to environmental factors
pose barriers that must be overcome. Despite these potential limitations, the
future looks promising for tethered drones as advancements in materials,
autonomy capabilities and integration with state of the art technologies pave
the way for broader applications and enhanced functionalities. The importance
of tethered drones, in overcoming the inherent limitations of standard drones
cannot be emphasized enough. With the rising need for secure aerial operations
in different industries, tethered drones play a vital role. It is essential
for both scientific and industrial sectors to continue exploring and enhancing
this technology, expanding its capabilities. Embracing and improving tethered
drone technology not only enhances UAV functions but also paves the way for
new opportunities in a society increasingly dependent on autonomous systems.

## References

  * [1] VLRVC, “Tethered drones market share, size, growth & supply [2023-2030],” LinkedIn, accessed: Feb. 25, 2024. [Online]. Available: https://www.linkedin.com/pulse/tethered-drones-market-share-size-growth-supply-2023-2030-vlrvc/
  * [2] S. Prior and M. Stock, “Tethered drone could fly’forever’,” _Reuters_ , 2016.
  * [3] M. N. Marques, S. A. Magalhães, F. N. Dos Santos, and H. S. Mendonça, “Tethered unmanned aerial vehicles—a systematic review,” _Robotics_ , vol. 12, no. 4, p. 117, 2023.
  * [4] B. E. Y. Belmekki and M.-S. Alouini, “Unleashing the potential of networked tethered flying platforms: Prospects, challenges, and applications,” _IEEE Open Journal of Vehicular Technology_ , vol. 3, pp. 278–320, 2022.
  * [5] “Usa’s [united states of america] leading wireless infrastructure provider,” Tripwireless Inc., accessed: Feb. 25, 2024. [Online]. Available: https://www.tripwireless.com/usas
  * [6] M. F. M. Fauzi and M. Z. RAHIM, “The development of tethered drone station,” _Research Progress in Mechanical and Manufacturing Engineering_ , vol. 3, no. 1, pp. 605–613, 2022.
  * [7] M. N. Boukoberine, Z. Zhou, and M. Benbouzid, “Power supply architectures for drones-a review,” in _IECON 2019-45th Annual Conference of the IEEE Industrial Electronics Society_ , vol. 1. IEEE, 2019, pp. 5826–5831.
  * [8] A. Aktaş, “Up to 2 kw power transfer system for tether powered unmanned aerial vehicles to provide long flight time,” Master’s thesis, Fen Bilimleri Enstitüsü, 2019.
  * [9] DJI, “DJI Mini 2 Support,” DJI Official Website, 2020, accessed: 2024-02-25. [Online]. Available: https://www.dji.com/support/product/mini-2
  * [10] DJI, “DJI Air 2S,” DJI Official Website, 2021, accessed: 2024-02-25. [Online]. Available: https://www.dji.com/air-2s
  * [11] DJI, “Dji mini 3,” DJI Official Website, 2022, accessed: 2024-02-25. [Online]. Available: https://www.dji.com/mini-3
  * [12] DJI, “Dji mavic 3 support,” DJI Official Website, 2021, accessed: 2024-02-25. [Online]. Available: https://www.dji.com/support/product/mavic-3
  * [13] DJI, “Dji fpv,” DJI Official Website, 2024, accessed: 2024-02-25. [Online]. Available: https://www.dji.com/dji-fpv
  * [14] DJI, “Matrice 300 rtk and dji care plus,” DJI Store, 2021, accessed: 2024-02-25. [Online]. Available: https://store.dji.com/product/matrice-300-rtk-and-dji-care-plus?vid=111261
  * [15] DroneBlog, “Yuneec battery,” DroneBlog, 2024, accessed: 2024-02-25. [Online]. Available: https://www.droneblog.com/yuneec-battery/
  * [16] PowerVision, “Poweregg x,” PowerVision, 2019, accessed: 2024-02-25. [Online]. Available: https://www.powervision.me/en/product/powereggx/
  * [17] PowerVision, “Powereye,” PowerVision, 2017, accessed: 2024-02-25. [Online]. Available: https://www.powervision.me/en/product/powereye/
  * [18] Parrot, “Anafi usa product sheet,” Parrot Official Website, 2018, accessed: 2024-02-25. [Online]. Available: https://www.parrot.com/assets/s3fs-public/2023-02/ANAFI-USA-product-sheet.pdf
  * [19] DroneBlog, “Parrot battery,” DroneBlog, 2015, accessed: 2024-02-25. [Online]. Available: https://www.droneblog.com/parrot-battery/
  * [20] Parrot, “Anafi ai technical specifications,” Parrot Official Website, 2022, accessed: 2024-02-25. [Online]. Available: https://www.parrot.com/us/drones/anafi-ai/technical-documentation/technical-specifications
  * [21] Autel Robotics, “Evo max 4t,” Autel Robotics Store, 2023, accessed: 2024-02-25. [Online]. Available: https://shop.autelrobotics.com/products/evo-max-4t
  * [22] Autel Robotics, “Autel evo ii series,” Autel Robotics Store, 2023, accessed: 2024-02-25. [Online]. Available: https://shop.autelrobotics.com/collections/autel-evo-ii-series
  * [23] Autel Robotics, “Evo lite series,” Autel Robotics Store, 2021, accessed: 2024-02-25. [Online]. Available: https://shop.autelrobotics.com/collections/drones-evo-lite-series
  * [24] Skydio, “Skydio x10,” Skydio Official Website, 2016, accessed: 2024-02-25. [Online]. Available: https://www.skydio.com/x10
  * [25] Skydio, “Skydio x2,” Skydio Official Website, 2019, accessed: 2024-02-25. [Online]. Available: https://www.skydio.com/skydio-x2
  * [26] Skydio, “Skydio 2+ enterprise,” Skydio Official Website, 2019, accessed: 2024-02-25. [Online]. Available: https://www.skydio.com/skydio-2-plus-enterprise
  * [27] Freefly Systems, “Alta x,” Freefly Systems, 2019, accessed: 2024-02-25. [Online]. Available: https://freeflysystems.com/alta-x
  * [28] Freefly Systems, “Astro,” Freefly Systems, 2019, accessed: 2024-02-25. [Online]. Available: https://freeflysystems.com/astro

|  SAMUEL O. FOLORUNSHO is a Graduate member of IEEE and a PhD student
conducting research at the Autonomous and Unmanned Vehicle Systems Lab (AUVSL)
and the Center for Autonomous Construction and Manufacturing at Scale (CACMS)
in the Department of Systems Engineering at the University of Illinois,
Urbana-Champaign (UIUC) under the advisorship of Prof. William R. Norris. His
research is focused on control systems, computer vision and robotics - and the
intersection of those for safety-critical systems in industrial and
agricultural applications. He earned his M.S. from UIUC in 2023 and his B.S.
in 2017 at the University of Ilorin, Nigeria both in Agricultural and
Biological Systems Engineering. He has 3 years of working experience in
management consulting.
---|---
|  WILLIAM R. NORRIS (Member, IEEE) received the B.S., M.S., and Ph.D. degrees
in systems engineering from the University of Illinois at Urbana– Champaign,
in 1996, 1997, and 2001, respectively, and the M.B.A. degree from the Fuqua
School of Business, Duke University, in 2007. He has over 23 years of industry
experience with autonomous systems. He is currently a Clinical Associate
Professor with the Industrial and Enterprise Systems Engineering Department,
University of Illinois at Urbana–Champaign, the Director of the Autonomous and
Unmanned Vehicle System Laboratory (AUVSL), as well as the Founding Director
of the Center for Autonomous Construction and Manufacturing at Scale (CACMS).
---|---