TITLE: Proving f has no min but has a max
QUESTION [1 upvotes]: Let f be a function from the real numbers to (0, $\infty$) and be continuous. Suppose the limit as x approaches negative infinity of f(x) equals 0, as well as the limit as x approaches infinity of f(x) equals 0.
a) Prove f does not have a minimum on R.
b) Prove f has a maximum on R.
I know intuitively why these statements are true and can explain them but am struggling to use the given information to write a formal proof of it. Any help?
Thank you!!

REPLY [0 votes]: Intuitively, the graph of $f$ looks like some kind of "hill" (I'd imagine something that looks like a graph of $y=1/(1+x^2)$ though you could have very nasty ones. Draw graph and try to translate my argument to this particular graph, that might make things easier to see for you) with sides going down and down as go left/right so there must be a highest point somewhere at the "middle", which is maximum of $f$.
You can translate this intuition into formal argument as follows. Look at the hill, the reason by it has highest point is precisely because height of this hill must go to $0$ as you go further to the right/left.
You can "cut" this hill somewhere below the top of the hill, and look at the parts of hill that are above/below this cut.
To say this formally, we can do the following. Let's consider a real number $\varepsilon>0$. Since $f(x)\to 0$ as $x\to\pm\infty$ we must be able to find some $x_m,x_M$ such that $f(x)<\varepsilon$ for $x<x_m$ and $x>x_M$. We have cut the hill with the line $y=\varepsilon$.
Now, we could have some weird cases where $x_m\ge x_M$. But in that case we can just choose another $x_m'<x_M$ with similar properties, because $x_m'<x_M\le x_m$ and we'd still have $f(x)<\varepsilon$ for all $x<x_m'$. So we can assume that $x_m<x_M$ (if not we just choose $x_m'$ and rename it $x_m$).
One final thing: notice that we could be looking at some ridiculous case in which $f(x)<\varepsilon$ for all $x$. For reasons that will be clear later on, we don't want this. We can just choose smaller $\varepsilon>0$ such that $f(x)\ge\varepsilon$ for some $x$. If we can't do that, then $f(x)<\varepsilon$ for all $x$ and $\varepsilon>0$ so it must mean $f(x)\le 0$ for all $x$. But in assumption is that $f>0$ so this cannot be the case. We will assume that there are some $x$ such that $f(x)\ge \varepsilon$ from now on.

Now we have all the ingredient we need. Part b) follows easily. Since $[x_m,x_M]$ is closed, $f$ achieves a maximum $K$ at $x_{0}$ on this interval, and outside of this interval we have $f(x)<\varepsilon$. By earlier discussion on $\varepsilon$ then $K\ge \varepsilon$ and $f(x_0)$ is maximum achieved by $f$.
For a) just notice that if $f$ has a minimum, say $\varepsilon$ then $f(x)\ge \varepsilon$ for all $x$ so we cannot find $x_m$ and $x_M$ for this $\varepsilon$, hence $f(x)\not\to 0$ as $x\to\pm\infty$. This is contradiction, so no minimum achieved.


TITLE: Question about notation in Hardy & Wright's Introduction to the Theory of Numbers
QUESTION [2 upvotes]: I've recently started reading about number theory and am fascinated, but just beginning my study of it. I've started reading Hardy & Wright's Introduction to the Theory of Numbers. Near the beginning (bottom of p. $5$ to top of p. $6$ in the $6$th edition) is this passage:
Suppose that
$$2, 3, 5, \ldots, p$$
are the primes up to $p$. Then all numbers up to $p$ are divisible by one of these primes, and therefore, if
$$2 \cdot 3 \cdot 5 \ldots p = q,$$
all of the $p – 1$ numbers
$$q + 2, q + 3, q + 4, \ldots, q + p$$
are composite.
I don't understand what they mean by this line:
$$2 \cdot 3 \cdot 5 \ldots p = q$$
and consequently I can't follow the logic to the end of the sentence.

REPLY [2 votes]: They authors are defining a number $q$, as the product of all the prime numbers from $2$ up to $p$. For example, if we take $p=7$, then we're setting $q$ equal to $2\times3\times5\times7=210$, and we're noting that each number from $212$ to $217$ is composite, with a factor of $2$, $3$, $5$ or $7$.

REPLY [0 votes]: It means that $q$ is the product $2\times3\times5\times\cdots\times p$.


TITLE: Is this a valid usage of the semidirect product?
QUESTION [0 upvotes]: I've been trying to wrap my head around the semidirect product of two groups, and I think I'm starting to get it, but I wanted to double check if this is true or not.

If $N$ and $H$ are subgroups of $G$ and $N\triangleleft G$, then if $|HN|=|H||N|$, there exists a homomorphism $f: H\rightarrow\operatorname{Aut}(N)$ defined by $f_h(n)=hnh^{-1}$ and $G=N\rtimes H$.

Is this accurate? If not, what would a counterexample look like?

REPLY [3 votes]: You're almost exactly right! We also need to know that $G$ is finite and $|HN| = |H||N| = |G|$.
Really the criterion for a semidirect product that you want (which can be found on wikipedia) is that both of the following hold:
1.
$$
HN = \{hn \mid h \in H, n \in N\} = G
$$
2.
$$H \cap N = \{ e \}$$
In the case that $G$ is finite, $|HN| = |G|$ is equivalent to saying $HN = G$, and $|HN| = |H||N|$ is equivalent to saying $H \cap N = \{ e \}$.

You ask for counterexamples, though, and if we leave out the $|HN| = |G|$ assumption you might consider $N \vartriangleleft G$ and $H = \{e\}$. Then trivially $|HN| = |N| = |H||N|$, but if $N$ is a proper normal subgroup then $G \neq H \ltimes N \cong N$.
If we leave out the assumption that $G$ is finite, then you might try $N = 2\mathbb{Z}$ and $H = 3\mathbb{Z}$ as subgroups of $\mathbb{Z}$. Then $HN = G$, since every integer is the sum of a multiple of $2$ and a mulitple of $3$, and $|H||N| = |HN| = |G| = \aleph_0$, but $G \neq H \ltimes N$ since $H \cap N \neq \{0\}$.

I hope this helps ^_^


text:
\begin{document}
\title{Algorithm for Computing Approximate Nash Equilibrium in Continuous Games with Application to Continuous Blotto\thanks{This research was developed with funding from the Defense Advanced Research Projects Agency (DARPA). The views, opinions and/or findings expressed are those of the author and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government.}}
\author{Sam Ganzfried\\
Ganzfried Research\\
sam@ganzfriedresearch.com

}

\date{\vspace{-5ex}}

\maketitle

\begin{abstract}
Successful algorithms have been developed for computing Nash equilibrium in a variety of finite game classes. However, solving continuous games---in which the pure strategy space is (potentially uncountably) infinite---is far more challenging. Nonetheless, many real-world domains have continuous action spaces, e.g., where actions refer to an amount of time, money, or other resource that is naturally modeled as being real-valued as opposed to integral. We present a new algorithm for {approximating} Nash equilibrium strategies in continuous games. In addition to two-player zero-sum games, our algorithm also applies to multiplayer games and games with imperfect information. We experiment with our algorithm on a continuous imperfect-information Blotto game, in which two players distribute resources over multiple battlefields. Blotto games have frequently been used to model national security scenarios and have also been applied to electoral competition and auction theory. Experiments show that our algorithm is able to quickly compute close approximations of Nash equilibrium strategies for this game.
\end{abstract}

\section{Introduction}
\label{se:introduction}
Successful algorithms have been developed for computing approximate Nash equilibrium strategies in a variety of finite game classes, even classes that are challenging from a computational complexity perspective. For~example, an~algorithm that was recently applied for approximating Nash equilibrium strategies in six-player no-limit Texas hold'em poker defeated strong human professional players~\cite{Brown19:Superhuman}. This is an extremely large extensive-form game of imperfect information. Even solving three-player perfect-information strategic-form games is challenging from a theoretical complexity perspective; it is PPAD-hard to compute a Nash equilibrium in two-player general-sum and multiplayer games, and it is widely believed that no efficient algorithms exist~\cite{Chen05:Nash,Chen06:Settling,Daskalakis09:Complexity}. Strong algorithms have also been developed for stochastic games, even with multiple players and imperfect information~\cite{Ganzfried09:Computing}. Stochastic games have potentially infinite duration but~a finite number of states and actions.

Continuous games are fundamentally different from finite games in several important ways. The~first is that they are not guaranteed to have a Nash equilibrium; Nash's theorem only proved the existence of a Nash equilibrium in finite games~\cite{Nash50:Non-cooperative}. A~second challenge is that we may not even be able to represent mixed strategies in continuous games, as~they correspond to probability distributions over a potentially (uncountably) infinite pure strategy space. So even if a game has a Nash equilibrium, we may not even be able to represent it, let alone compute it. Equilibrium existence results and algorithms have been developed for certain specialized classes; however, there are still many important game classes for which these results do not hold. Even two-player zero-sum games remain a challenge. For~example, the~fictitious play algorithm has been proven to converge to Nash equilibrium for finite two-player zero-sum games (and certain classes of multiplayer and nonzero-sum games), but~this result does not extend to continuous games~\cite{Robinson51:Iterative}.

A strategic-form game consists of a finite set of players $N = \{1,\ldots,n\}$, a~finite set of pure strategies $S_i$ for each player $i$, and~a real-valued utility for each player for each strategy vector (aka \emph{strategy profile}), $u_i : {S_1 \times \ldots \times S_n} \rightarrow \mathbb{R}$.
A two-player game is called \emph{zero sum} if the sum of the payoffs for all strategy profiles equals zero, i.e.,~$u_1(s_1,s_2) + u_2(s_1, s_2) = 0$ for all $s_1 \in S_1, s_2 \in S_2$.

A \emph{mixed strategy} $\sigma_i$ for player $i$ is a probability distribution over pure strategies, where $\sigma_i(s_{i'})$ is the probability that player $i$ plays $s_{i'} \in S_i$ under $\sigma_i$. Let $\Sigma_i$ denote the full set of mixed strategies for player $i$. A~strategy profile $\sigma^* = (\sigma^*_1,\ldots,\sigma^*_n)$ is a \emph{Nash equilibrium} if $u_i(\sigma^*_i,\sigma^*_{-i}) \geq u_i(\sigma_i, \sigma^*_{-i})$ for all $\sigma_i \in \Sigma_i$ for all $i \in N$, where $\sigma^*_{-i}$ denotes the vector of the components of strategy $\sigma^*$ for all players excluding $i$. It is well known that a Nash equilibrium exists in all finite games~\cite{Nash50:Non-cooperative}. In~practice, all that we can hope for {in many games} is the convergence of iterative algorithms to an approximation of Nash equilibrium. For~a given candidate strategy profile $\sigma^*$, define $\epsilon(\sigma^*) = \max_{i \in N} \max_{\sigma_i \in \Sigma_i} \left[ u_i(\sigma_i,\sigma^*_{-i}) - u_i(\sigma^*_i, \sigma^*_{-i}) \right]$. The~goal is to compute a strategy profile $\sigma^*$ with as small a value of $\epsilon$ as possible (i.e., $\epsilon = 0$ indicates that $\sigma^*$ comprises an exact Nash equilibrium). We say that a strategy profile $\sigma^*$ with value $\epsilon$ constitutes an \emph{$\epsilon$-equilibrium}. For~two-player zero-sum games, there are algorithms with bounds on the value of $\epsilon$ as a function of the number of iterations and game size, and~for different variations $\epsilon$ is proven to approach zero in the limit at different worst-case rates (e.g.,~\cite{Gilpin12:First}).

If $\sigma^1_i$ and $\sigma^2_i$ are two mixed strategies for player $i$ and~$p \in (0,1)$, then we can consider mixed strategy $\sigma'_i = p \sigma^1_i + (1-p) \sigma^2_i$ in two different ways. The~first interpretation, which is the traditional one, is that $\sigma'_i$ is the mixed strategy that plays pure strategy $s_i \in S_i$ with probability $p \sigma^1_i(s_i) + (1-p)\sigma^2(s_i)$. Thus, $\sigma'_i$ can be represented as a single mixed strategy vector of length $|S_i|$. A~second interpretation is that $\sigma'_i$ is the mixed strategy that with probability $p$ selects an action by randomizing according to the probability distribution $\sigma^1$, and with probability $1-p$ selects an action by randomizing according to $\sigma^2$. Using this interpretation implementing $\sigma'_i$ requires storing full strategy vectors for both $\sigma^1$ and $\sigma^2$, though~clearly the result would be the same as in the first~case.

In extensive-form imperfect-information games, play proceeds down nodes in a \emph{game tree}. At~each node $x$, the~player function $P(x)$ denote{s} the player to act at $x$. This player can be from the finite set $N$ or~an additional new player called Chance or Nature. Each player's nodes are partitioned into \emph{information sets}, where the player cannot distinguish between the nodes at a given information set. Each player has a finite set of available actions at each of the player's nodes (note that the action sets must be identical at all nodes in the same information set because~the player cannot distinguish the nodes). When play arrives at a leaf node in the game tree, a~terminal real-valued payoff is obtained for each player according to utility function $u_i$. Nash equilibrium existence and computational complexity results from strategic-form games hold similarly for imperfect-information extensive-form games; e.g.,~all finite games are guaranteed to have a Nash equilibrium, two-player zero-sum games can be solved in polynomial time, and~equilibrium computation for other game classes is~PPAD-hard.

Randomized strategies can have two different interpretations in extensive-form games. Note that a \emph{pure strategy} for a player corresponds to a selection of an action for each of that player's information sets. The~classic definition of a \emph{mixed strategy} in an extensive-form game is the same as for strategic-form games: a probability distribution over pure strategies. However, in~general the number of pure strategies is exponential in the size of the game tree, so a mixed strategy corresponds to a probability vector of exponential size. By~contrast, the~concept of a \emph{behavioral strategy} in an extensive-form game corresponds to a strategy that assigns a probability distribution over the set of possible actions at each of the player's information sets. Since the number of information sets is linear in the size of the game tree, representing a behavioral strategy requires only storing a probability vector of size that is linear in the size of the game tree. Therefore, it is much preferable to work with behavioral strategies than mixed strategies, and~algorithms for extensive-form games generally operate on behavioral strategies. Kuhn's theorem states that in any finite extensive-form game with perfect recall, for~any player and any mixed strategy, there exists a behavioral strategy that induces the same distribution over terminal nodes as the mixed strategy against all opponent strategy profiles~\cite{Kuhn53:Extensive}. The~converse is also true. Thus, mixed strategies are still functionally equivalent to behavioral strategies, despite the increased complexity of representing~them.

Continuous games generalize finite strategic-form games to the case of (uncountably) infinite strategy spaces.  Many natural games have an uncountable number of actions; for example, games in which strategies correspond to an amount of time, money, or~space. One example of a game that has recently been modeled as a continuous game in the AI literature is computational billiards, in~which the strategies are vectors of real numbers corresponding to the orientation, location, and~velocity at which to hit the ball~\cite{Archibald09:Modeling}.

\begin{definition}  A \emph{continuous game} is a tuple $G = (N,S,U)$ where
\begin{itemize}
\item $N = \{1,2,3,\ldots,n\}$ is the set of players
\item $S = (S_1,\ldots,S_n)$, where each $S_i$ is a (compact) metric space corresponding to the set of strategies of player $i$
\item $U = (u_1,\ldots,u_n)$, where $u_i: {S_1 \times \ldots \times S_n} \rightarrow \mathbb{R}$ is the utility function of player $i$
\end{itemize}
\label{gamedef}
\end{definition}

Mixed strategies are the space of Borel probability measures on $S_i$. The~existence of a Nash equilibrium for any continuous game with continuous utility functions can be proven using Glicksberg's generalization of the Kakutani fixed point theorem~\cite{Glicksberg52:Further}. The~result is stated formally in Theorem~\ref{th:existence}~\cite{Fudenberg91:Game_theory}. In~general, there may not be a solution if we allow non-compact strategy spaces or discontinuous utility functions. We can define extensive-form imperfect-information continuous games similarly to that for finite games, with~analogous definitions of mixed and behavioral~strategies.

\begin{theorem}
Consider a strategic-form game in which the strategy spaces $S_i$ are nonempty compact subsets of a metric space.  If~the payoff functions $u_i$ are continuous, there exists a (mixed strategy) Nash equilibrium.
\label{th:existence}
\end{theorem}

While this existence result has been around for a long time, there has been very little work on practical algorithms for computing equilibria in continuous games.  One interesting class of continuous games for which algorithms have been developed is \emph{separable games}~\cite{Stein08:Separable};

however, this imposes a significant restriction on the utility functions, and~many interesting continuous games are not separable.  Additionally, algorithms for computing approximate equilibria have been developed for several other classes of continuous games, including simulation-based games~\cite{Vorobeychik08:Stochastic}, graphical tree-games~\cite{Singh04:Computing}, and~continuous poker models~\cite{Ganzfried10:Computing}. The~continuous Blotto game that we consider does not fit in any of these classes, and in fact has discontinuous utility functions, so we cannot apply Theorem~\ref{th:existence} or these~algorithms.

\section{Continuous Blotto~Game}
\label{se:Blotto}
The Blotto game is a type of two-player zero-sum game in which the players are tasked to simultaneously distribute limited resources over several objects (or battlefields). In~the classic version of the game, the~player devoting the most resources to a battlefield wins that battlefield and~the gain (or payoff) is then equal to the total number of battlefields won. The~Blotto game was first proposed and solved by Borel in 1921~\cite{Borel21:La} and~has been frequently applied to national security scenarios.  It has also been applied as a metaphor for electoral competition, with~two political parties devoting money or resources to attract the support of a fixed number of voters: each voter is a ``battlefield'' that can be won by one party. The game also finds application in auction theory where bidders must make simultaneous bids~\cite{Wiki20:Blotto}.

Initial approaches derived analytical solutions for special cases of the general problem. Borel and Ville proposed the first solution for three battlefields~\cite{Borel38:Applications}, and~Gross and Wagner generalized this result for any number of battlefields~\cite{Gross50:Continuous}. However, they assumed that colonels have the same number of troops. Roberson computed optimal strategies of the Blotto games in the continuous version of the problem where all of the battlefields have the same weight, for~models with both symmetric and asymmetric budgets~\cite{Roberson06:Colonel}. Hart considered the discrete version, again when all battlefields have equal weight, and~solved it for certain special cases~\cite{Hart08:Discrete}. It was not until 2016 that the first algorithm was provided to solve the general version of the game. Initially a polynomial-time algorithm that involved solving exponential-sized linear programs was presented~\cite{Ahmadinejad16:Duels}, which was later improved to a linear program of polynomial size~\cite{Behnezhad17:Faster}. These polynomial-time algorithms are for the discrete version of the game; however, no general algorithm has been devised for the original continuous Blotto game. As~described earlier, there are many challenges present for solving continuous games that do not exist for finite games, even for two-player zero-sum~games.

Most of the prior approaches solve perfect-information versions of the game in which all players have public knowledge of the values of the battlefields. Adamo and Matros studied a Blotto game in which players have incomplete information about the other player's resource budgets~\cite{Adamo09:Blotto}. Kovenock and Roberson studied a model where the players are subject to incomplete information about the battlefield valuations~\cite{Kovenock11:Blotto}. In~both of these works, all players are equally uninformed about the parameters. Recently some work has provided analytical solutions for certain settings with asymmetric information, in~which both players know the values of the battlefields but~one player knows their order while the other player only knows a distribution over the possible orders~\cite{Paarporn19:Characterizing,Chandan20:When}. This model is an imperfect-information game in which player 1 must select a strategy without knowing the order, while player 2 can select a different mixed strategy conditional on the actual order. We study and present an algorithm for the asymmetric imperfect-information continuous version of the Blotto game, which is perhaps the most challenging variant. Note that our approach also applies to the perfect information version as~well.

A continuous Blotto game is a tuple $G = (N, F, O, p, v, B, S, \delta, u)$:

\begin{itemize}
\item Set of players $N = \{1,2\}$
\item Set $F = \{1,2,\ldots,|F|\}$ of battlefields
\item {Set of slots $Q = F$}
\item Set $O$ of outcomes, which is a subset of the set of permutations of elements of $F${, where $o(q)$ denotes the battlefield in slot $q$ for $o \in O$, $q \in Q$}. {Let $M = |O|.$}
\item Probability mass function $p$ with $p(o)$ for each $o \in O$
\item Positive real value $v_f$ for each battlefield $f \in F$
\item Positive real-valued budget $B_i$ for each player $i \in N$
\item Pure strategy space of player 1 $S_1$ is $\{(x_q) \in \mathbb{R}^{|Q|} | \sum_q x_q = B_1, x_q \geq 0 \mbox{{ }} \forall q \in Q\}$. {Let $s_1(q)$ denote the probability of selecting slot $q$ for $s_1 \in S_1.$}
\item Pure strategy space of player 2 $S_2$ is $\{(x_{o,q}) \in \mathbb{R}^{|O||Q|} | \sum_q x_{o,q} = B_2, x_{o,q} \geq 0 \mbox{{ }} \forall o \in O \mbox{{ }} {\forall} q \in Q\}$.  {Let $s_2(o,q)$ denote the probability of selecting slot $q$ under outcome $o$ for $s_2 \in S_2.$}
\item $\delta \in \mathbb{R} > 0$
\item Utility function $u_1(s_1,s_2) = \sum_o p(o) \sum_q C_1(s_1(q), s_2(o,q))$ for $s_1 \in S_1, s_2 \in S_2$, where
\begin{itemize}
\item $C_1(s_1(q),s_2(o,q)) = v_{o(q)}$ if $s_1(q) \geq s_2(o,q) + \delta$,
\item $C_1(s_1(q),s_2(o,q)) = -v_{o(q)}$ if $s_1(q) \leq s_2(o,q)$,
\item $C_1(s_1(q),s_2(o,q)) = 0$ otherwise
\end{itemize}
\item Utility function $u_2(s_1,s_2) = \sum_o p(o) \sum_q C_2(s_1(q), s_2(o,q))$ for $s_1 \in S_1, s_2 \in S_2$, where
\begin{itemize}
\item $C_2(s_1(q),s_2(o,q)) = -v_{o(q)}$ if $s_1(q) \geq s_2(o,q) + \delta$,
\item $C_2(s_1(q),s_2(o,q)) = v_{o(q)}$ if $s_1(q) \leq s_2(o,q)$,
\item $C_2(s_1(q),s_2(o,q)) = 0$ otherwise
\end{itemize}
\end{itemize}

Each player must select a real-valued amount of resources to put on the battlefield in slot $q \in Q$, subject to the constraint that the total does not exceed the player's budget $B_i$. Player 1 does not know the outcome $o$, which defines the order of the battlefields; they only know that the outcome is $o \in O$ with probability $p(o)$. Player 2 knows the order and~is able to condition their strategy on this additional information. For~each slot $q$, if~player 1 uses an amount of resources $s_1(q)$ that exceeds player 2's amount $s_2(o,q)$ by at least $\delta$, then player 1 ``wins'' the battlefield $o(q)$ in slot $q$ and receives its value $v_{o(q)}$ (and player 2 receives $-v_{o(q)}$); if $s_2(o,q) \geq s_1(q)$ then player 2 wins $v_{o(q)}$ and player 1 loses $v_{o(q)}$; otherwise, both players get zero. This game is clearly zero sum because player 1 and player 2's payoff sum to zero for each~situation.

Note that the utility function is discontinuous: payoffs for a given slot can shift abruptly between $v_{o(q)}$, $0$, and~$-v_{o(q)}$ with arbitrarily small changes in the strategies. This means that Theorem~\ref{th:existence} does not apply, and~the game is not necessarily guaranteed to have a Nash equilibrium. The~game does also not fall into the specialized classes of games such as separable games for which prior algorithms have been developed. Note that often the Blotto game is presented without the $\delta$ term; typically player 1 wins the battlefield if $s_1(q) > s_2(o,q)$, and~player 2 wins if $s_2(o,q) \geq s_1(q)$. We add in the $\delta$ term because our algorithm involves the invocation of an optimization solver, and~optimization algorithms typically cannot handle strict inequalities. We can set $\delta$ to a value very close to~zero.

\section{Algorithm}
\label{se:Algorithm}
Fictitious play is an iterative algorithm that is proven to converge to Nash equilibrium in two-player zero-sum games (and in certain other game classes), though~not in general for multiplayer or non-zero-sum games~\cite{Brown51:Iterative,Robinson51:Iterative}.  While it is not guaranteed to converge in multiplayer games, it has been proven that if it does converge, then the average of the strategies played throughout the iterations constitute an equilibrium~\cite{Fudenberg98:Theory}. Fictitious play has been successfully applied to approximate Nash equilibrium strategies in a three-player poker tournament to a small degree of approximation error~\cite{Ganzfried08:Computing,Ganzfried09:Computing}. More recently, fictitious play has also been used to approximate equilibrium strategies in multiplayer auction~\cite{Rabinovich09:Generalised,Rabinovich13:Computing} and national security~\cite{Ganzfried20b:Parallel} scenarios. Fictitious play has been demonstrated to outperform another popular iterative algorithm, counterfactual regret minimization, in~convergence to equilibrium in a range of multiplayer game classes~\cite{Ganzfried20:Fictitious}.

In classical fictitious play, each player plays a best response to the average strategies of his opponents thus far. Strategies are initialized arbitrarily (typically they are initialized to be uniformly random). Then each player uses the following rule to obtain the average strategy at time $t$:
$$\sigma^t _i = \left( 1 - \frac{1}{t} \right) \sigma^{t-1} _i + \frac{1}{t} \sigma'^t _i,$$
where $\sigma'^t _i$ is a best response of player $i$ to the profile $\sigma^{t-1} _{-i}$  of the other players played at time $t-1$.
The final strategy output after $T$ iterations $\sigma^T$ is the average of the strategies played in the individual iterations (while the best response $\sigma'^t_i$ is the strategy actually played at iteration $t$).

The classical version of fictitious play involves representing two strategies per player; the current strategy $\sigma^t _i$ and the current best response $\sigma'^t_i$. Note that once we compute the next round strategy $\sigma^{t+1}_i$ from $\sigma^t_i$ and $\sigma'^{t+1}_i$, we no longer need to maintain either $\sigma^t_i$ or $\sigma'^{t_1}_i$ in memory. We interpret $\sigma^t_i$ as a single mixed strategy that selects action $s_j$ with probability $\left( 1 - \frac{1}{t} \right) \sigma^{t-1} _i (s_j) + \frac{1}{t} \sigma'^t _i (s_j).$

An alternative, and~seemingly nonsensical, way to implement fictitious play would be to separately store each of the pure strategies that are played $\sigma'^t_i$, rather than to explicitly average them at each step. Using this representation, the~best response can be computed by selecting the pure strategy that maximizes the average (or sum) of the utilities against $\sigma'^0_{-i},\ldots,\sigma'^{t-1}_{-i}$. This method of implementing fictitious play seems nonsensical for several reasons. First, it involves picking a strategy that maximizes the sum of utilities against $t$ different opponent strategies as opposed to maximizing the utility against a single strategy. And second, it involves storing $t$ pure strategies for each player, which would require using significantly more memory than the original approach when $t$ exceeds $|S_i|$. Despite these clear drawbacks, nonetheless it is apparent that this approach is still equivalent to the original approach and results in the same sequence of strategies being played. When the algorithm is applied to an imperfect-information game, we can view it as operating with mixed as opposed to behavioral strategies (in contrast to prior algorithms for solving imperfect-information games). We refer to this new approach as ``Redundant fictitious play'' due to the fact that it ``redundantly'' stores all of the strategies played individually instead of storing them as a single mixed strategy. Redundant fictitious play is depicted in Algorithm~\ref{al:FP}.

\begin{algorithm}[H]
\caption{Redundant fictitious play for two-player~games}
\label{al:FP}
\textbf{Inputs}: Number of iterations $T$
\begin{algorithmic}
\State Initialize strategy arrays $S_1[T]$, $S_2[T]$
\State $S_1[0], S_2[0] \gets$ InitialValues()
\State $v^*_1[0] \gets u_1(S_1[0], S_2[0])$
\State $v^*_2[0] \gets u_2(S_1[0], S_2[0])$
\For {$t = 1$ to $T$}
\State $S_1[t] \gets BestResponse1(Mix(S_2, 0, t-1))$
\State $S_2[t] \gets BestResponse2(Mix(S_1, 0, t-1))$
\State $\epsilon_1[t] \gets u_1(S_1[t],Mix(S_2, 0, t-1)) - v^*_1[t-1]$
\State $\epsilon_2[t] \gets u_2(Mix(S_1, 0, t-1),S_2[t]) - v^*_2[t-1]$
\State $\epsilon[t] \gets \max_i \epsilon_i[t]$
\State $v^*_1[t] \gets u_1(Mix(S_1, 0, t),Mix(S_2, 0, t))$
\State $v^*_2[t] \gets u_2(Mix(S_1, 0, t),Mix(S_2, 0, t))$
\EndFor
\end{algorithmic}
\end{algorithm}
\vspace{-2pt}

In Algorithm~\ref{al:FP}, we store $T$ strategies for each player, where $T$ is the total number of iterations. We can initialize strategies arbitrarily for the first iteration (e.g., to~uniform random). For~all subsequent iterations the strategy $S_i[t]$ is a pure strategy best response to a strategy of the opponent. The~notation $Mix(S_i, 0, t-1)$ refers to the mixed strategy for player $i$ that plays strategy $S_i[u]$ with probability $\frac{1}{t}$, for~$0 \leq u \leq t-1$; that is, it mixes uniformly over the strategies $S_i[0],\ldots,S_i[t-1]$. The~algorithm then computes the game value to player $i$ under the current iteration strategies as~well as the \emph{exploitability} of each player (difference between best response payoff and game value). This determines the maximum amount that each player can gain by deviating from the strategies; we can then say that the strategies computed at iteration $t-1$ constitute an $\epsilon_t$-equilibrium, where $\epsilon_t = \max_i \epsilon_i[t]$.

Now, suppose that $G$ is a continuous game and no longer a finite game. Assuming that we initialize the strategies $S_i[0]$ to be pure strategies, all of the strategies $S_i[t]$ are now pure strategies and~the algorithm does not need to represent any mixed strategies. This is very useful, since for continuous games a mixed strategy may be a probability distribution that puts weight on infinitely many pure strategies {and cannot be compactly represented}. However, pure strategies can typically be represented compactly in continuous games. For~example, if~the strategy spaces are compact subsets of $\mathbb{R}^n$, then each pure strategy corresponds to a vector of $n$ real numbers, which can be easily represented assuming that $n$ is not too large. For~example in continuous Blotto player 1 must select an amount of resource to use for each of $|F|$ battlefields, and~therefore storing a pure strategy requires storing $|F|$ real numbers, which is easy to do. Thus, Redundant Fictitious Play can be feasibly applied to continuous games, while the classical version~cannot.

The only remaining challenge for continuous games is the best response computation, which may be challenging for certain complex utility functions. However, for~the common assumptions that the pure strategy spaces are compact and the utility functions are continuous, this optimization is typically feasible to~compute.

For the continuous Blotto game, we present optimization formulations for computing player 1 and 2's best response below. Both of these are mixed integer linear programs (with a polynomial number of variables and constraints). Note that we are able to construct efficient best response procedures for this game despite the fact that the utility function is~discontinuous.

Player 1's best response function {is the following, where $X_q$ is a variable denoting the amount of resources put on slot $q$, and~$Y_{t,o,q}$ is the amount of resources put on slot $q$ under outcome $o$ by player 2's fixed strategy at iteration $t$}:\\
Maximize $\sum_t \sum_o \sum_q \left(p(o) \cdot b_{t,o,q} \cdot v_{o(q)} \right)$ subject to:
\begin{align}
&b_{t,o,q} = 1 \rightarrow X_q \geq Y_{t,o,q} + \delta \mbox{ for all } t,o,q \label{eq:ind-1}\\
&\sum_q X_q = B_1\\
&0 \leq X_q \leq B_1 \mbox{ for all } q \\
&b_{t,o,q} \mbox{ binary in } \{0,1\} \mbox{ for all } t,o,q
\end{align}

The constraints in Equation~(\ref{eq:ind-1}) are called indicator constraints and state that if the binary variable $b_{t,o,q}$ has value equal to 1, then the linear constraint $X_q \geq Y_{t,o,q} + \delta$ must hold. Indicator constraints are supported by many integer-linear program optimization solvers, such as CPLEX and Gurobi. We could additionally impose indicator constraints $b_{t,o,q} = 0 \rightarrow X_q \leq Y_{t,o,q}$; however, these are unnecessary and would significantly increase the size of the problem. To~see the correctness of the procedure, suppose that $X_q \geq Y_{t,o,q} + \delta$ and $\sum_q X_q = B_1$ but that $b_{t,o,q} = 0$. Then the objective clearly increases by setting $b_{t,o,q} = 1$ instead to~include the additional term $p(o) \cdot b_{t,o,q} \cdot v_{o(q)}$. So there cannot exist another solution satisfying the budget and indicator constraints with higher objective~value.

While player 1 must assume that the outcome is distributed according to $p$, player 2 is aware of the outcome and therefore can condition their strategy on it. Therefore, player 2 solves a separate optimization for each value of $o \in O$ to compute the best response to the strategy of player~1.

Player 2's best response function given outcome $o \in O$ {is the following, where $Y_q$ is a variable denoting the amount of resources put on slot $q$ and~$X_{t,q}$ is the amount of resources put on slot $q$ according to player 1's fixed strategy at iteration $t$}:\\
Maximize $\sum_t \sum_q \left(b_{t,q} \cdot v_{o(q)} \right)$ subject to:
\begin{align}
&b_{t,q} = 1 \rightarrow Y_q \geq X_{t,q} \mbox{ for all } t,q\\
&\sum_q Y_q = B_2\\
&0 \leq Y_q \leq B_2 \mbox{ for all } q \\
&b_{t,q} \mbox{ binary in } \{0,1\} \mbox{ for all } t,q
\end{align}

Correctness of player 2's best response function follows by similar reasoning to that of player 1's. Player 1's best response optimization
has $T' M |Q|$ binary variables $b_{t,o,q}$, where $T'$ is the current algorithm iteration {and $M = |O|$ denotes the number of outcomes}, and~$|Q|$ continuous variables $X_q$. Since the number of indicator constraints is also $T' M |Q|$, the~size of the formulation is $O(T M |Q|) = O(T M |F|)$, which is polynomial in all of the input parameters. Similarly, player 2 must solve $M$ optimizations, each one with size $O(T' |Q|)$. Note that in practice this algorithm could be parallelized by solving each of these $M+1$ optimizations simultaneously on separate cores as opposed to solving them sequentially (in our implementation we solve them sequentially). However, since player 1's optimization is much larger than each of player 2's, the~bottleneck step is player 1's optimization, and~such a parallelization may not provide a significant reduction in the~runtime.

Note that as we run successive iterations of Algorithm~\ref{al:FP}, the~size of these optimization problems becomes larger, since the opponent's strategy is a mixture over $t$ pure strategies, where $t$ is the current algorithm iteration. We have seen that the number of variables and constraints scales linearly in $t$. Therefore, we expect earlier iterations of the algorithm to run significantly faster than later iterations. We will see the exact magnitude of this disparity in the experiments in Section~\ref{se:exp}. A~potential solution to this issue would be to include an additional parameter $K$ in Algorithm~\ref{al:FP}. Instead of computing a best response to the mixture over all $t$ of the opponent's pure strategies, a~subset of $K$ of them is selected by sampling and~a best response is computed just to a uniform mixture over the pure strategies in the sampled subset. This sampling would occur for each iteration, so a potentially different subset of size $K$ would be selected at each iteration. This would ensure that the complexity of the best response computations remains constant over all iterations and does not become intractable for later iterations. This approach would be unbiased and~produces the same result in expectation over the sampling outcomes. However, it may lead to high variance in results and lead to poor convergence in practice. Perhaps this could be mitigated by performing multiple runs of the sampling algorithm in parallel and selecting the run with lowest value of $\epsilon$.

Note that Algorithm~\ref{al:FP} can be applied to extensive-form imperfect-information games in addition to simultaneous strategic-form games (in fact the continuous Blotto game that we apply it to has imperfect information for player 1, since player 1 does not know the value of $o$ while player 2 does). As~long as pure strategies can be represented and best responses can be computed efficiently (which are both the case for imperfect-information games), the~algorithm can be applied. Also note that while we presented the algorithm just for a two-player game, it can also be run on multiplayer games (just as for standard fictitious play). The~best response computations are still just a single agent optimization problem given fixed strategies for the opposing players. In~fact, fictitious play has been demonstrated to obtain successful convergence to Nash equilibrium in a variety of multiplayer settings~\cite{Ganzfried20:Fictitious}, despite the fact that it is not guaranteed to converge to Nash equilibrium in general for games that are not two-player~zero-sum.

We can compute $v^*_1[t]$ and $\epsilon_1[t]$ for Algorithm~\ref{al:FP} in the continuous Blotto game using the procedures depicted in Algorithms~\ref{al:value} and~\ref{al:epsilon} (and analogously for $v^*_2[t]$ and $\epsilon_2[t]$).

\begin{algorithm}[H]
\caption{Procedure to compute $v^*_1[t]$ in continuous~Blotto}
\label{al:value}

\begin{algorithmic}
\State $v^*_1[t] \gets 0$
\For {$t_1 = 0$ to $t$}
\For {$t_2 = 0$ to $t$}
\For {$o \in O$}
\For {$q \in Q$}
\If  {$S_1[t_1](q) \geq S_2[t_2](o,q) + \delta$}
\State $v^*_1[t] \gets v^*_1[t] + p(o)v_{o(q)}$
\ElsIf {$S_1[t_1](q) \leq S_2[t_2](o,q)$}
\State $v^*_1[t] \gets v^*_1[t] - p(o)v_{o(q)}$
\EndIf
\EndFor
\EndFor
\EndFor
\EndFor
\State $v^*_1[t] \gets \frac{v^*_1[t]}{(t+1)^2}$
\State \Return $v^*_1[t]$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{Procedure to compute $\epsilon_1[t]$ in continuous~Blotto}
\label{al:epsilon}

\begin{algorithmic}
\State $\epsilon_1[t] \gets 0$
\For {$t_2 = 0$ to $t-1$}
\For {$o \in O$}
\For {$q \in Q$}
\If  {$S_1[t](q) \geq S_2[t_2](o,q) + \delta$}
\State $\epsilon_1[t] \gets \epsilon_1[t] + p(o)v_{o(q)}$
\ElsIf {$S_1[t](q) \leq S_2[t_2](o,q)$}
\State $\epsilon_1[t] \gets \epsilon_1[t] - p(o)v_{o(q)}$
\EndIf
\EndFor
\EndFor
\EndFor
\State $\epsilon_1[t] \gets \frac{\epsilon_1[t]}{t}$
\State $\epsilon_1[t] \gets \epsilon_1[t] - v^*_1[t-1]$
\State \Return $\epsilon_1[t]$
\end{algorithmic}
\end{algorithm}
\vspace{-10pt}

\section{Experiments}
\label{se:exp}

We experimented on a game with three battlefields $f_1,f_2,f_3$, with~values $v_1 = 0.7$, $v_2 = 0.2$, $v_3 = 0.1$, and~three outcomes {(each with probability $\frac{1}{3}$)}:
\begin{itemize}
\item Outcome 1 has $f_1$ in slot 1, $f_2$ in slot 2, $f_3$ in slot 3.
\item Outcome 2 has $f_3$ in slot 1, $f_1$ in slot 2, $f_2$ in slot 3.
\item Outcome 3 has $f_2$ in slot 1, $f_3$ in slot 2, $f_1$ in slot 3.
\end{itemize}

We assume that player 2 observes the outcome while player 1 does not. We used a budget $B_1 = 10$ for player 1 and $B_2 = 7$ for player 2. We used $\delta = 0.0001$. We used the default feasibility tolerance in Gurobi, which is $\num{1.0e-6}$. We ran our algorithm for 5000 iterations and~computed $\epsilon_i$ for each player every 10 iterations. Recall that we defined the exploitability of the computed strategies at iteration $t$ as $\epsilon[t] = \max_i \epsilon_i[t].$ The experiments did not use any sampling and~computed the best response against the opponent's full mixed strategy at each iteration using the mixed-integer linear programs described in Section~\ref{se:Algorithm}. We used the parallel version of Gurobi's mixed integer linear programming solver~\cite{Gurobi19:Gurobi} with six cores on a~laptop.

The results are shown in Figure~\ref{fi:results}. It took slightly under 25,000 seconds (around 6.9~hours) to run 5000 iterations of our algorithm. The~final strategies had an exploitability of 0.0307 for player 1 and 0.0292 for player 2, indicating that the strategies constitute an $\epsilon$-equilibrium for $\epsilon = 0.0307$. (After 5000 additional iterations $\epsilon$ decreased further to 0.021.) The exploitability values are not monotonically decreasing, and~the lowest value in these experiments was actually obtained with $\epsilon = 0.0259$ at iteration 4480. The~expected value for player 1 in the final strategies is $-$0.10969. The~exploitability fell below 0.05 for the first time after 1759.4 seconds (29.3 minutes), obtaining $\epsilon = 0.0494$ on iteration 1400. From~the figure we can also see that the runtimes varied for the different iterations, as~expected (nearly half of the 5000 iterations were completed in the first 5000 seconds).

\begin{figure}[H]
\centering

\includegraphics[width=0.9\linewidth]{blotto-1b}
\caption{Exploitability
($\epsilon$) vs. runtime (seconds) and algorithm iteration for continuous imperfect-information Blotto~game.}

\label{fi:results}
\end{figure}

\section{Conclusion}
\label{se:conc}
We presented a new algorithm for computing Nash equilibrium in a broad class of continuous games. The~algorithm is based on integrating a novel variant of fictitious play in which the strategies from all iterations are stored with custom best response functions. Solving continuous games is particularly challenging as a Nash equilibrium is not even guaranteed to exist and mixed strategies may put weight on infinitely many pure strategies; yet for many realistic games it is more natural to model strategies as subsets of real numbers than as integers. We implemented our algorithm on a continuous imperfect-information model of the Blotto game, a~well-studied model of resource allocation with applications to national security. We created a new mixed-integer linear program formulation for the best response function. We demonstrated that the algorithm converged quickly to an $\epsilon$-equilibrium for $\epsilon$ equal to 0.03 after 5000 iterations of the algorithm (several hours), which corresponds to 30\% of the minimum battlefield value. While the Blotto game has been studied analytically and efficient algorithms have been developed for the discrete case, this is the first algorithm for solving the continuous~case.

\section{Acknowledgments}
\label{se:ack}
We would like to acknowledge Arctan, Inc., and in particular Peter Dragos, Charles Morefield, Michael Morefield, and Keith Paarporn.

\bibliographystyle{plain}

\bibliography{C://FromBackup/Research/refs/dairefs}

\end{document}

config: arxiv


TITLE: Prime factorization of $10^n+1$
QUESTION [4 upvotes]: I was just playing with these numbers and it seems to me that the numbers of the form $10^n+1$, where $n>2$ are composite. I can prove that $10^n+1$ can't be prime unless $n$ is a power of $2$, but I do not know for which values of $n$, these numbers are prime, except for $n=2$. Is it an open problem or is there any result on this? Thank you in advance.

REPLY [6 votes]: $10^{2^n}+1$ is a generalized Fermat prime $F_{n}(10)$.
Landau's fourth problem asks if there are infinitely many generalized Fermat primes $F_n(a)$:

As of 2013, all four problems [including yours] are unresolved.

Here are some more numbers, till $n=20$.

REPLY [3 votes]: Updated to add: Due to a typo in the original question, it turns out that this proof is already known to the OP. Never mind, I'll leave it here anyway.
We can write $n=2^km$ where $m$ is odd. Then $10^n \equiv (-1)^m \equiv -1$ mod $(10^{2^k}+1)$, so $10^n+1 \equiv 0$ mod $(10^{2^k}+1)$. Thus $10^n+1$ is composite unless $n=2^k$, i.e. $n$ is a power of $2$.
For instance:

if $n$ is odd, then $10^n+1 \equiv (-1)^n+1 \equiv 0$ mod $11$
if $n \equiv 2$ mod $4$, put $n=4m+2$, then $10^n+1 \equiv 100^{2m+1}+1 \equiv (-1)^{2m+1}+1 \equiv 0$ mod $101$
similarly, if $n \equiv 4$ mod $8$, then $10^n+1 \equiv 0$ mod $10001$
if $n \equiv 8$ mod $16$, then $10^n+1 \equiv 0$ mod $100000001$

and so on.
If $n$ is a power of $2$, you claim that you can prove that $10^n+1$ is prime, but that's not right. In fact $10^n+1$ is prime for $k=1$ (with $10^n+1 = 101$) and composite for $k=0,2,3,4,5$. I can see no reason to rule out prime values for higher values of $k$.


TITLE: Spring with changing equilibrium
QUESTION [1 upvotes]: Suppose that we have two cars on a track, each with a different mass. Now suppose that the cars are connected with a spring. We smack one car. I would like to write down the equations of motion for this scenario and solve them but I am just a lowly mathematician who has never really studied physics. My attempt yielded this ODE
$$m_1x_1''(t)-m_2x_2''(t)= -k(x_1(t)-x_2(t))-c_1x_1'(t)+c_2x_2'(t)$$
where $c_1$ and $c_2$ are the coefficients of friction, $m_1$ and $m_2$ are the masses, and $k$ the spring constant. Is this correct? How do I solve?

REPLY [2 votes]: The two cars each have their own degrees of freedom, such that if the spring force is $F_s$ then
 $$ \begin{aligned} m_1 \ddot{x}_1 & = +F_s - c_1 \dot{x}_1
\\ m_2 \ddot{x}_2 & = -F_s - c_2 \dot{x}_2 \end{aligned}$$
You already mentioed that the spring force is $F_s = -k \left( x_1-x_2 \right) $
So now you have your ODE.


TITLE: What is the precise mathematical definition of what a wavelet is and what is its relation to linear algebra?
QUESTION [11 upvotes]: I was reading on wavelets and it seems that its hard to find a precise mathematical definition of what this concept is. My confusion first arose due to Gilbert Stang's linear algebra book. In particular consider the following extract:

It talks about how to change a vector from one basis to another but it never rigorously defines what a wavelet is (by the way, I did understand that extract I included, just not the concept of "wavelet"). From my understanding, some special basis are called wavelets (for some special reason). But which basis are we allowed to call wavelets? I would assume that they have something to do with linear algebra and oscillation/sinusoidal functions but I don't really see what the relation between the two is.
To look for an alternative explanation I went to wikipedia and the initial paragraph starts as follows:

A wavelet is a wave-like oscillation with an amplitude that begins at
  zero, increases, and then decreases back to zero. It can typically be
  visualized as a "brief oscillation" like one might see recorded by a
  seismograph or heart monitor. Generally, wavelets are purposefully
  crafted to have specific properties that make them useful for signal
  processing. Wavelets can be combined, using a "reverse, shift,
  multiply and integrate" technique called convolution, with portions of
  a known signal to extract information from the unknown signal.

With that description it makes me feel that wavelets are actually functions. However, I've had difficulty understanding this precisely, specially when trying to relate it to linear algebra. I guess I am having a hard time connecting the three, wavelets, linear algebra and their relations to sinusoidal functions (if there is any relation to them).

REPLY [0 votes]: The DFT has global self-similarity properties. That is what allows for the FFT factorizations. However each factor in the FFT spreads to affect the whole signal space.
To derive a DWT is to find or build a family of functions which have local self-similarity properties to allow for a similar factorization which spreads more locally over the signal space.


text:
\section{Definitions and Expressions for Section~\ref{sec:omgnet}}\label{app:def4omg}
Here we provide the definition and expressions for $\Dl \g_i$, $\Du \g_i$, $\ksmin_i$, $\ksmax_i$ and $\Wmax_i$. We start by defining $\Dl \g_i$ and $\Du \g_i$ for each $i \in [n]$.
\begin{definition}
Let $y_i\defeq (\f,\d_i, \p_i)$. For function $\phi_i(u_i, y_i) \defeq \g_i(\u_i-\d_i + \sum_{j=1}^n  \f_{ij}, \p_i)$  that is convex (but not necessarily differentiable) in $\u_i$, a real number $\alpha_i$ is called a (partial) subgradient of $\phi_i$ with respect to argument $\u_i$ at given $(\u_i, y_i)$ if $\phi_i(u_i',y_i) \ge \phi_i(u_i, y_i) + \alpha_i (u_i'-u_i)$ for all $u_i' \in [\umin_i, \umax_i]$. The set of all subgradients at $(\u_i, y_i)$, denoted by $\partial_{u_i} \phi_i(u_i,y_i)$, is called the (partial) subdifferential of $\phi_i(u_i, y_i)$ with respect to $\u_i$ at $(\u_i,y_i)$. Denote $\mathcal{U}_i \defeq [\umin_i,\umax_i]$, $\mathcal{Y}_i \defeq \Fcal \times [\dmin_i, \dmax_i] \times [\pmin_i, \pmax_i]$ where $\Fcal=\big\{\f: -\Fmax_{ij}\le\f_{ij}  \le \Fmax_{ij}, \,\forall i,j \in [n]\big\}$. Define the set
\[
D \g_i \defeq \bigcup_{(u_i,y_i) \in \times\mathcal{U}_i \times \mathcal{Y}_i} \partial_{u_i} \phi_i(\u_i, y_i),
\]
and let real numbers $\Dl g_i$ and $\Du g_i$ be defined such that
\begin{equation}
\Dl\g_i \le \inf D\g_i \le \sup D\g_i \le \Du\g_i.
\end{equation}
That is, $\Dl \g_i$ and $\Du \g_i$ are a lower bound and an upper bound of the sub-gradient of $\phi_i$ over  its (compact) domain, respectively.
\end{definition}
More details and examples regarding how to calculate $\Dl \g_i$ and $\Du \g_i$ can be found in our previous work \cite{OMGarxiv}. The bounds for the algorithmic parameters are
\begin{equation}\label{eq:ineq_1}
\ksmin_i \defeq \frac{1}{\la_i} \left(-\W_i \Dl \g_i + \umax_i - \bmax_i\right),
\end{equation}
\begin{equation}\label{eq:ineq_2}
\ksmax_i \defeq \frac{1}{\la_i} \left(-\W_i \Du \g_i - \bmin_i+ \umin_i\right),\end{equation}
and
\begin{equation}\label{eq:W_max}
\Wmax_i \defeq \frac{(\bmax_i - \bmin_i) -(\umax_i - \umin_i)}{\Du \g_i - \Dl \g_i}  .
\end{equation}


TITLE: A proof in module theory: a set theoretic consideration $|\bigcup_{i \in I} B_i| \leq |Y|$
QUESTION [2 upvotes]: The set-theoretic result used in the proof I want to know about is the following:

Let $(B_i)_{i \in I}$ be a family of sets such that, for all $i,j \in I$, either $B_i \subseteq B_j$ or $B_j \subseteq B_i$ holds and, for all $i \in I$, $|B_i| \leq |Y|$. Then $|\bigcup_{i \in I} B_i| \leq |Y|$.

Which conditions must be true (if any) for this to hold, and why? I tried to put a well-order on both $I$ and $Y$, but didn't succeed even with that. This seem to be implicitly assumed in the following proof (the book is Abstract Algebra by Grillet).
If this inequality is not true in the general case, I wonder if there is a condition in the proof that make it true.

REPLY [1 votes]: The claimed set-theoretic result is wrong. For instance, the first uncountable ordinal $\omega_1$ is a union of a well-ordered family of countable ordinals. So I guess that the proof contains a gap in the assurance that the family $\mathcal S$ is closed with respect to the unions of chains of its elements. Maybe it can be fixed by relaxing  condition $|B|\le |Y|$ for the family $\mathcal S$ and remarking in the last sentence of the proof that $Y=X$ implies $|B|\le |X|$.


TITLE: Solvable Lie algebras: embedded in upper triangular matrices?
QUESTION [5 upvotes]: Let $K$ be an arbitrary field and $\mathfrak{g}$ a finite-dimensional Lie $K$-algebra.
Let $\mathfrak{nil}_n\leq\mathfrak{sol}_n\leq\mathfrak{gl}_n$ be the Lie algebras of all ((strictly) upper-triangular) $n\!\times\!n$ matrices over $K$. By the Ado-Iwasawa theorem, $\mathfrak{g}$ admits an embedding into some $\mathfrak{gl}_n$, and by Engel's theorem $\mathfrak{g}$ is nilpotent iff it admits an embedding into some $\mathfrak{nil}_n$.

Does every finite-dimensional solvable Lie $K$-algebra admit an embedding into some
  $\mathfrak{sol}_n$?

If not, how about if we assume $K$ is algebraically-closed with positive characteristic? The Lie's theorem states that this holds true over algebraically-closed fields of zero characteristic.

REPLY [7 votes]: The shaded question obviously has a negative answer for an arbitrary field $K$ (e.g., if the characteristic is 0 but the field fails to be algebraically closed).  Maybe it's better to rewrite the question?   In any case, it's essential to start with $K$ algebraically closed.  Moreover, you might as well assume $K$ has prime characteristic $p$: Lie's Theorem already takes care of characteristic 0 in the algebraically closed case.  But in prime characteristic the study of solvable Lie algebras (and their finite dimensional representations) gets extremely hard to organize, as one sees for example in papers of Strade and in the textbook by Strade-Farnsteiner.  The old example of a solvable Lie algebra consisting of $p \times p$ matrices which can't be put in triangular form (due I think to Jacobson) illustrates the negative side quite well, since for example its derived algebra fails to be nilpotent.
On the positive side, if you start with a solvable Lie algebra $\mathfrak{g}$ embedded in some $\mathfrak{gl}(V)$ with $p > \dim V$, the usual proof of Lie Theorem's goes through and allows you to realize $\mathfrak{g}$ by upper triangular matrices relative to some basis of $V$.   (This is an exercise in my old book on Lie algebras and has been known for a long time.)   There are also some positive results in the literature for very special cases such as Lie algebras of Borel subgroups of algebraic groups.
In terms of building structure, classification, and representation theories in characteristic $p$, there has been little success in the study of solvable Lie algebras taken in isolation, especially those which are not the Lie algebras of algebraic groups.  The study of simple Lie algebras (especially the restricted ones) and auxiliary solvable subalgebras has gone much further (in work of Block-Wilson, Premet-Strade in particular) for $p>3$, but nothing here is easy.    Although Jacobson did establish the viability of the purely algebraic theory of Lie algebras in all characteristics, his work also showed some of the obstacles ahead.


TITLE: Inequality involving a convex function
QUESTION [3 upvotes]: Do the points that satisfy an inequality involving a convex function constitute a convex set?
Specifically if $x \in \mathbb R^n$ and I have a function $f(x)$ then is the set
 $\{x \mid f(x) \le 0\}$ convex?
If this is true then is it enough to show that the sets formed by constraint functions in a convex optimization problem are convex sets rather than having to show that the constraint function itself is convex?
I am also having trouble understanding what is meant by minimizing a convex function "over a convex set". Does this mean that the feasible set of the problem is convex or the constraint inequalities are convex?

REPLY [1 votes]: The set $\{x | f(x) \leq 0\}$ is so called $0$-level sublevel set of $f(x)$.
If $f(x)$ is convex, then its $\alpha$-sublevel sets are convex, $\alpha \in \mathbb{R}$ and it is not hard to show.
Take two points $x_1, x_2 \in \{x | f(x) \leq 0\}$, then $f(x_1) \leq 0$, and $f(x_2) \leq 0$
From definition of convexity, $f(\theta x_1 + (1-\theta)x_2) \leq \theta f(x_1) + (1- \theta) f(x_2)$
At this point, notice that $\theta \in [0,1]$, so $\theta f(x_1) \leq 0$ is true, and  $(1- \theta) f(x_2) \leq 0$ is true.
$\Rightarrow \theta f(x_1) + (1- \theta) f(x_2) \leq 0$ is also true (why?),
$\Rightarrow \theta x_1 + (1-\theta)x_2 \in \{x | f(\theta x_1 + (1-\theta)x_2) \leq \theta f(x_1) + (1- \theta) f(x_2) \leq 0\}$
Since the straight line lies in the set for all $x_1,x_2$, therefore the set is convex.


TITLE: p-simplex spanned by elements in the boundary of the unit ball of Thurston norm is in the the boundary of this unit ball.
QUESTION [1 upvotes]: in completing my thesis I have reached a momentary impass.
I am trying to solve an exercise given in the book "Foliations II" by Candel and Conlon. In particular, Exercise 10.4.1, and I can't seem to get through it.
Here is what I have to solve and can't seem to manage:
Let $V=\{\lambda_1,\dots,\lambda_p\}\subset\partial B_\xi$ be an affinely independent set, where $\xi$ is the Thurston norm and $\partial B_\xi$ is the boundary of the unit ball of this norm $B_\xi=\{w\in H_2(M,\partial M;\mathbb{R})|\xi(w)=1\}$. Prove that the affine $p$-simplex $\Delta_p$, spanned by $V$, is a subset of $B_\xi$. Generally, $\Delta_p$ is not a subset of $\partial B_\xi$, but if an interior point $\lambda$ of $\Delta_p$ has norm $\xi(\lambda)=1$ prove that $\Delta_p\subset\partial B_\xi$.
I will be using this for the case where $M$ is the complement in $3$-space of a link or knot, but I think this should work in general for $3$-manifolds. Any advice, or elegant solutions??
Thanks in advance,
Paul

REPLY [0 votes]: Using subadditivity we get for $x$ in $\Delta$ that $\xi x = \xi(\sum \lambda_i v_i) \le \sum \lambda_i \xi(v_i) =1$.
For the second part note that if we restrict $\xi$ to the interior $int \Delta \to \mathbb R$, the set $\xi^{-1}(1)$ is closed and non empty. It is also obviously open (use that $x$ in the interior can only be written st all $\lambda_i$ are non zero) and hence the above restriction factors through the trivial space $\{1\}$ and hence through the boundary.


TITLE: How can you elegantly show that the relation is transitive?
QUESTION [0 upvotes]: I have a problem in keeping my reasoning short (that a relation is transitive). As example, let's take the set $S = \left\{1,2,3,4\right\}$ where the relation is $R = \left\{(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)\right\}$.
That relation is transitive but how can you easily show that?
My approach was going pairwise until I realized that's probably the most inefficient way. By pairwise I mean something like that:
$R$ is transitive because:
$(1,2) \in R$ and $(2,3) \in R \Rightarrow (1,3) \in R$ is satisfied,
$(1,2) \in R$ and $(2,4) \in R \Rightarrow (1,4) \in R$ is satisfied,
...
Although my approach is very bad, I'd like to know if it's correct?
But I'm more interested in knowing a better way of showing this :)

REPLY [1 votes]: Note that on the natural numbers $<$ is defined using the successor operator $s$.
We say that $x<y$ iff there exists $k$ such that $y=s^k(x)=\underbrace{s\circ\cdots\circ s}_{k\text{ times}}(x)$.
So the transitivity is ensured because of composition properties $x<y$ and $y<z$ then $z=s^l(y)=s^l(s^k(x))=s^{l+k}(x)$ so $x<z$.
Here in $S=\{1,2,3,4\}$ seen as a subset of $\mathbb N$ your $R$ is defined such that $1$ is in relation only with its successors $2,3,4$ and same for $2$ and $3$ and $4$, so $R$ is just the restriction of $<$ to the set $S$ and thus is transistive.


TITLE: Why aren't repeating decimals irrational but something like $\pi$ is?
QUESTION [2 upvotes]: We use closest representations for both of them, but they are not completely true.
$\frac{22}7$ and $3.14$ are not exactly $\pi$ but we use them as the best option available.
$\frac13$ is $0.\bar3$  but that can be $0.333$ or $0.333333$ and these are not equal.
So why is one irrational and other is not?

REPLY [5 votes]: Repeating decimals are simply geometric series which add up to
$$a + ar + ar^2 + \cdots = \frac {a}{1-r} $$
where $a$ and $r$ are rational numbers, so the result is rational.
For example:
$$\begin{align}
0.23\,23\,23\ldots &= 0.23 +0.00\,23+0.00\,00\,23 +\cdots \\[2ex]
&= 0.23 + 0.23\left(\frac1{100}\right) + 0.23\left(\frac1{100}\right)^2 + \cdots \\[2ex]
&= \frac{0.23}{1-\frac1{100}}=\frac {23}{99}
\end{align}$$


TITLE: How to show $(x_n)$ defined $x_1 = a$, $x_{n+1} = 2x_n - x^2_ny$ is increasing if $ay < 2$
QUESTION [1 upvotes]: $y,a > 0$. Let $x_n = (y^{-1} + \epsilon)$ for $\epsilon \in \mathbb{R}$. Then $x_{n+1} = y^{-1}-\epsilon^2y$, so sup$(x_n) = y^{-1}$. How do i show $(x_n)$ is an increasing sequence so i can conclude $(x_n)$ converges to $y^{-1}$?

REPLY [0 votes]: Wstp $x_n < x_{n+1}$ or that $y^{-1} -\epsilon < y^{-1} - \epsilon^2y$ for $\epsilon \in \mathbb{R}^+$. Since $\forall n \in \mathbb{N}$, $x_n > 0$, $\epsilon < y^{-1}$. Then $y < \epsilon^{-1}$, so $y^{-1} - \epsilon^2y > y^{-1} - \epsilon$.


TITLE: Find $a,b$ such that $a^2+b^2=85113$ and that $\text{lcm}\{a,b\}=1764$
QUESTION [1 upvotes]: Find two positive integers $a,b$ such that $a^2+b^2=85113$ and that $\text{lcm}\{a,b\}=1764$

I have completely no idea where to enter this question.

REPLY [2 votes]: Note that $\text{lcm}(a,b)=1764=(2\cdot 3\cdot 7)^2$ and $85113=3^2\cdot 7^2\cdot 193$. We may assume that $7^2$ divides $b$ then $a^2=85113-b^2$ is divisible by $7^2$ which means that $7$ divides $a$. Let $A:=a/7$, $B:=b/7$ and solve the reduced diophantine equation
$$A^2+B^2=85113/7^2=1737$$
with $\text{lcm}(A,B)=2^2\cdot 3^2\cdot 7$.
Similarly, we can operate with respect to the factor $3$ and solve the reduced diophantine equation
$$X^2+Y^2=1737/3^2=193$$
where $X:=a/21$ and $Y:=b/21$ with $\text{lcm}(X,Y)=2^2\cdot 3\cdot 7$.
Since $13^2<193<14^2$, now it is easy to find the solutions by hand. Can you take it from here?


TITLE: Uncountably infinite union/intersection in sigma-algebra
QUESTION [2 upvotes]: i was wondering whether it makes any difference (or whether it is even true)  that an uncountably infinite union/intersection of sets that are elements of a sigma algebra is again an element of the sigma algebra?

REPLY [1 votes]: If $X$ is a set and $\mathcal B\subset 2^X$ a $\sigma$-algebra on $X$, it's not true. For example, take $\mathbb R$ endowed with the $\sigma$-algebra $\mathcal B$ of the subset of $\mathbb R$ which are at most countable, and their complements. Then write $(0,\infty):=\bigcup_{x\gt 0}\{x\}$.


TITLE: Interpolation inequality
QUESTION [2 upvotes]: Lef $u$ be at least a $C^2$ function on $\mathbb{R}^n$.   Let's denote the gradient by $D$. Also, (using the multiindex notation), define the seminorm $$||D^ku|| = \sup_{|\gamma|=k}{\sup_x{|D^{\gamma}u|}}$$
How can we prove the following :
$$||Du|| \leq \epsilon||D^2u|| + C||u|| $$
where $C$ is some constant depending on $\epsilon$

REPLY [2 votes]: By restricting the function to a line, i.e., considering the function, $t \mapsto u(a+tb)$ for some point $a\in \mathbb{R}^n$ and a unit vector $b\in\mathbb{R}^n$, you can reduce the problem to the case $n=1$. Now the problem is for a $\mathcal{C}^2$ function $f:\mathbb{R}\to\mathbb{R}$ to show $\|f'\| \le \epsilon \|f''\| + C\|f\|$. The idea is that if you have a point $x_0$ and a constant $M>0$ such that $f'(x_0)\ge M+1$ (or $-f'(x_0)\ge M+1$), and if you have a uniform bound $\|f''\|\le K$, then $f'\ge M$ (or $-f'\ge M$) whenever $|x-x_0| \le 1/K$, and then $|f(x_0+1/K)-f(x_0-1/K)| \ge 2M/K$, so $\| f\| \ge M/K$. This implies the desired inequality by juggling of constants.


TITLE: Find the probability that a randomly chosen applicant who was approved by the manager is qualified.
QUESTION [1 upvotes]: Of all the people applying for a certain job, $89\%$ are qualified. The personnel manager claims that she approves qualified people $61\%$ of the time and she approves an unqualified person $12\%$ of the time.
Find the probability that a randomly chosen applicant who was approved by the manager is qualified. Round your answer to the nearest tenth of a percent.
I tried it many times but I always failed. I do not know how to solve this I need help.

REPLY [2 votes]: Let $Q$ mean 'applicant is qualified', $Q'$ 'applicant is not qualified' and $A$ 'approved'. We are given
$$P(Q) = 0.89, P(A|Q) = 0.61, P(A| Q') = 0.12$$
What have you written down for $P(Q|A)$?


TITLE: Proof software for Primitive Recursive Arithmetic
QUESTION [2 upvotes]: Primitive Recursive Arithmetic is a critical foundational system in mathematics at large, and all the more so in areas studying constructive reasoning and/or computability such as Theoretical Computer Science.
Is there any proof software that deals with Primitive Recursive Arithmetic... or equivalent systems?

REPLY [1 votes]: The ACL2 theorem prover seems quite close to what you want, though it is hard to know exactly what the strength of the system is.
From the logical description here it looks like the base is a quantifier-free equational logic with induction principles, which include principles allowing the definition of PR functions.
This gives exactly PRA, but in addition, the standard library defines induction up to $\varepsilon_0$, which brings the strength up to full Peano Arithmetic.
You might therefore want to work in ACL2 with a restricted version of the standard induction principle (I don't know how hard that is).


TITLE: A spectral sequence with only one index in Atiyah's paper?
QUESTION [2 upvotes]: I would like to read Atiyah's paper Characters and cohomology of finite groups; but when I started reading the introduction, Atiyah mentions that he will prove that there is a "spectral sequence $\{E^p_r\}$  with $E^p_2 = H^p(G,\mathbb{Z})$ and $E^p_\infty = R_p(G)/R_{p+1}(G)$"
I can't understand what this means, because a spectral sequence is supposed to have $2$ indices, like $E^{p,q}_2$.
My best guess is that it would be an old notation, for instance that what he denotes $E^p_2$ would the graded module $\displaystyle\bigoplus_{q}E_2^{p,q}$; but I'm not sure, and I would like not to have to guess to understand the paper.
Is this a common notation, an old notation ? What does it mean ?

REPLY [3 votes]: He writes what he means in a section titled 'spectral sequences' at the start of page 34 (end of section 3). He means a sequence of graded complexes $(E_r, d_r)$, with $d_r$ of degree $r$, with specified isomorphisms $H(E_r, d_r) \cong E_{r+1}$.
He writes this with the meaning you expect (collapsing a bigraded spectral sequence to a single grading) for the usual cohomology-to-K-theory AHSS in propositions 2.4 and 2.6.
However, the target for the spectral sequence you're talking about is the representation ring $R(G)$, which in particular is not a graded object; Atiyah introduces a filtration (which I think is from the dimension of an irrep) and then argues that a spectral sequence converges to this target.
I am not familiar enough with the paper to tell you how that spectral sequence is constructed. However, I will point out that because $R(G)$ is not naturally graded, it would be odd to have a bigraded spectral sequence converging to it; this would naturally construct a grading (at least on each filtered piece), which seems like it would be odd; I have no idea where it would come from!
So it seems likely that the SS he constructs does not naturally have a second grading, and that it only fits into the formalism I mentioned at the start of this post.