Gain maximization when gambling on all possible outcomes

Question

Consider an event with $n>1$ possible mutually exclusive outcomes, and a betting system which rewards each outcome $1, \ldots, n$ with quotes $q_1, \ldots, q_n > 1$, i.e., if I bet a positive real $x_i$ on the outcome $i$, $1 \le i \le n$, I have a net gain of $(q_i-1)x_i$.

Now suppose that I want to bet something on all outcomes and decide, given the quotes, whether there can always be a gain. I want, therefore, to find solutions to:

$$\begin{cases} (q_1-1)x_1-x_2-x_3+\cdots -x_n \gt 0 \\ -x_1+(q_2-1)x_2-x_3+\cdots -x_n \gt 0 \\ \qquad\qquad\qquad \vdots \\ -x_1-x_2-x_3+\cdots +(q_n-1)x_n \gt 0 \\ \end{cases}$$

I have first modified the system with equalities for the "fair game" condition ($=0$ instead of $>0$), then "normalized" with $x_n=1$, and with the help of Wolfram Alpha, found a solution for the first $n-1$ equations ($n \le 4$), replaced it in the last equation to guess the conjecture that my first system above has solutions if and only if:

$$\prod_{i=1}^n{q_i} \gt \sum_{1 \le j_1 \lt j_2 \lt \cdots \lt j_{n-2} \lt j_{n-1} \le n} {q_{j_1}q_{j_2} \cdots q_{j_{n-2}}q_{j_{n-1}}}$$

For example with $n=2$ if and only if $q_1q_2 \gt q_1+q_2$, with $n=3$ if and only if $$q_1q_2q_3 \gt q_1q_2+q_1q_3+q_2q_3$$ and so on.

Assuming that the conjecture is true and can be proven formally (hints on material on the subject or a proof are welcome anyway), my main question is: when the first system has solutions, is it possible to find analytically the tuple $(x_1/x_n,x_2/x_n, \ldots ,x_{n-1}/x_n,1)$ that maximizes the expected gain supposing that each outcome $i$ has a probability proportional to $1/(q_i-1)$? Or is linear programming for specific cases the only way to go?

EDIT 2022-09-13

Empirically, the result seems to be $(q_n/q_1,q_n/q_2, \ldots ,q_n/q_{n-1},1)$ which gives the same gain for any outcome.

Answer 1

Take the case of $n=2$. The quotes are $q_1$ and $q_2$. Suppose we bet $x_1$ and $x_2$, and let $x'_1=\frac{x_1}{x_2}$. Our minimum profit is then $\min((q_1-1)x_1-x_2,(q_2-1)x_2-x_1)=x_2(\min((q_1x'_1-x'_1-1,q_2-1-x'_1))=x_2(\min((q_1x'_1,q_2)-1-x'_1)$. We want the minimum profit to be positive, so $x_2(\min((q_1x'_1,q_2)-1-x'_1)>0$. Specifically, this means that both $x_2((q_1x'_1-1-x'_1)>0$ and $x_2(q_2-1-x'_1)>0$. Dividing by $x_2$, we have that both $(q_1x'_1-1-x'_1>0$ and $q_2-1-x'_1>0$. This means that $x'_1>\frac1{q_1-1}$ and $x'_1<q_2-1$. Combining these inequalities and removing the middle part gives that $\frac{1}{q_1-1}<q_2-1$, or $1<(q_1-1)(q_2-1)=q_1q_2-(q_1+q_2)+1$. As a result, we get the requirement $q_1+q_2<q_1q_2$ and then any $x'_1$ fulfilling $\frac{1}{q_1-1}<x'_1<q_2-1$ is a guaranteed winning strategy.

I'd imagine you could use similar methodology for higher values of $n$.

Answer 2

Let $A$ be the matrix whose diagonal entries are $q_i-1$, and whose off-diagonal entries are $-1$. If you bet $x$, then your possible winnings are described by the vector $Ax$. Call a vector "positive" if all of its entries are positive. In order to ensure a positive gain, you need to find a positive vector $x$ for which $Ax$ is positive.

Theorem: You can ensure a positive gain if and only if $q_1^{-1}+q_2^{-1}+\dots+q_n^{-1}<1$.

Proof: We may as well normalize our vector $x$ so that $\sum_{i=1}^n x_i=1$. For any normalized vector, $$ Ax=\begin{bmatrix}q_1x_1-1\\q_2x_2-1\\\vdots \\q_nx_n-1\end{bmatrix} $$ This is positive if and only if $x_i> q_i^{-1}$ for all $i$. Since $\sum_i x_i=1$, this is only possible if $1>\sum_i q_i^{-1}$.

---

For the second part, you are putting a certain probability distribution on the set of outcomes, and asking how to find the maximum expected gain. Let $p=\begin{bmatrix}p_1&p_2&\cdots & p_n \end{bmatrix}$ be the vector describing the probability distribution. Then your expected gain is $$ p_1q_1x_1+p_2q_2x_2+\dots+p_nq_nx_n - 1 $$ If we were only optimizing for expected value, the optimal strategy is to find the index $j$ for which $p_jq_j$ is maximized, and to bet your entire stake on outcome $j$. This gives an expected gain of $p_jq_j-1$.

However, I think you are talking about about finding the maximum expected gain, subject to the constraint that your gain is always positive. We saw before that you need to bet $x_i>q_i^{-1}$ for all $i$ to ensure positive gain. If you bet $x_i=q_i^{-1}+\varepsilon$ on all vectors for some small $\varepsilon>0$, then you have $1-(q_1^{-1}+\dots+q_n^{-1}+n\epsilon)$ leftover. It is then optimal to bet all of the leftovers on the $j$ for which $p_jq_j$ is maximized. However, there is no maximum expected value; you can always increase your expected gain by decreasing $\varepsilon$ further, giving you more leftovers to place on the most efficient bet.