Specific optimization problem algorithm

Question

This task is related to optimization problems, where we set the objective function equal to a given fixed number, subject to a number of constraints. Consider a gambling situation. We have a particular box, with one of $n$ items inside. The probability of getting $i$th item from the box is $p_i$. Pulling from a particular item from the box is an elementary outcome: these outcomes are independent of each other, and the sum of the probabilities of the onset of all elementary outcomes is equal to one. A player wants to open the box, and he pays a price of $C$ for this. Each of $n$ items that may be pulled from the box has its value $c_i,i=(1,n)$ ̅. These values may be smaller or significantly greater than the box price. Let $x$ is a random variable, which reflects the value of an item pulled from the box. This is a discrete random variable, therefore, its expectation is: $$E(x)=\sum_{i=1}^nc_i p_i $$ A game owner has a desired level of profitability, which can be calculated as follows: $$R(x)=\frac{C-E(x)}{C}$$ In addition, the owner wants this profitability to be controlled by changing the probabilities of elementary outcomes in the way, such that $R(x)=R_0$, the desired level of profitability. Box price and values of all items, as well as their number are constants. Some probabilities, for example, $p_1,…,p_k,k<n$, can be manually assigned, therefore, the remaining variables will be only $p_(k+1),….,p_n$. Upon studying competitors’ experience, it was found out that there is a requirement to the distribution of random variable $x$. In particular, this distribution should be skewed to the right:

Let’s sort the prices on items in the ascending order of price levels: $c_1≤c_2≤⋯≤c_n$
Then, we come to the optimization problem of the following form:

Set the objective function $R(x)=1-\frac{\sum_{i=1}^nc_i p_i}{C}→R_0$ Subject to constraints: $$p_1,p_2,…p_n>0$$ $$\sum_{i=1}^np_i =1$$ $$p_1<p_2<⋯<p_m$$ $$p_n<p_{n-1}<⋯<p_m$$ Where $m$ is an index of a particular item, pulled from the box, with a cost $c_m$, which depends from the value of the box approximately as follows (these bounds were received experimentally): $$0.4C≤c_m≤1.15C$$ The last constraint is an attempt to assign higher probabilities to items with “middle” level of values, as compared to those with low and high values. This should imply the probability distribution to have the desired form.

What is required? To write down the algorithm of calculations, which can solve the optimization problem and can be implemented on PhP. This task can be solved in Excel using Excel Solver, however, since we cannot work with Excel files effectively, we need a manually written algorithm, which can be implemented in a programming code.

Answer 1

Fix $n$ as a positive integer and fix $m \in \{1, ..., n\}$. Let $\mathcal{P}$ be the set of all vectors $p=(p_1, ..., p_n)$ that satisfy these constraints: \begin{align} &\sum_{i=1}^n p_i = 1\\ &p_i \geq 0 \quad \forall i \in \{1, ..., n\}\\ &p_1 \leq p_2 \leq ... \leq p_m\\ &p_m \geq p_{m+1} \geq ... \geq p_n \end{align} Now fix constants $C, C_1, ..., C_n$ and assume $C>0$ and $$ 0\leq C_1 \leq C_2 \leq ... \leq C_n$$ Define the function $R(p)$ (for the vector $p=(p_1,...,p_n)$) by: $$ R(p) = 1 - \frac{1}{C}\sum_{i=1}^n p_iC_i$$ One may want to know the possible values of $R(p)$, considering all vectors $p \in \mathcal{P}$. The smallest possible value is $R_{min}$ and is achieved at: \begin{align} p^{min} &= (p_1^{min},..., p_n^{min}) \\ &= \left(0, 0, ..., 0, \underbrace{\frac{1}{n-m+1}}_{\mbox{location $m$}}, \frac{1}{n-m+1},..., \frac{1}{n-m+1}\right) \end{align} so that $$ \boxed{R_{min} = R(p^{min})}$$ The largest possible value is $R_{max}$ and is achieved at: \begin{align} p^{max}&=(p_1^{max},..., p_n^{max}) \\ &= \left(\frac{1}{m}, \frac{1}{m}, ..., \underbrace{\frac{1}{m}}_{\mbox{location $m$}}, 0, 0, ..., 0\right) \end{align} so that $$ \boxed{R_{max} = R(p^{max})}$$

---

Now since $p^{min} \in \mathcal{P}$ and $p^{max} \in \mathcal{P}$ we have that for every $\theta \in [0,1]$: $$ \theta p^{min} + (1-\theta)p^{max} \in \mathcal{P}$$ which means that for any $R_0 \in [R_{min}, R_{max}]$ there is a $\theta_0$ such that $$ R_0 = \theta_0 R_{min} + (1-\theta_0)R_{max}$$ and this value $R_0$ is achieved by the probability vector: $$ \theta_0p^{min} + (1-\theta_0)p^{max}$$ meaning that $$\boxed{R(\theta_0p^{min} + (1-\theta_0)p^{max}) = R_0}$$ In particular, if $R_0 \notin [R_{min}, R_{max}]$ then it is impossible to find a vector $p \in \mathcal{P}$ that satisfies $R(p)=R_0$.

---

For example if $n=6$ and $m=3$ and $\theta_0=1/2$ then \begin{align} &(1/2)p^{min} + (1/2)p^{max} \\ &= (1/2)(0, 0, 1/4, 1/4, 1/4, 1/4) + (1/2)(1/3, 1/3, 1/3, 0, 0,0)\\ &=(1/6, 1/6, 7/24, 1/8, 1/8, 1/8) \end{align}

---

Now open inequalities $<$ are usually not used in optimization. One reason is that closed inequalities $\leq$ typically yield problems with well defined optimums, while $<$ often do not. Another reason is that, if desired, we know we can perturb a solution by $\delta$, where $0<\delta < 10^{-1000000}$, to change $\leq$ into $<$. For example: $$(1/6, 1/6 + \delta, 7/24, 1/8, 1/8-\delta/3, 1/8 - 2\delta/3)$$ and such precision to a million decimal places is clearly impractical, is merely an annoyance, and so we might as well use the (simpler) $\leq$ constraints.

For example do you really care if $p_6$ is: $$ p_6 = 0.125 $$ versus $$ p_6 = 0.124\underbrace{9999999999999999999999999999999999....9}_{\mbox{a million 9s}}$$ ?

It would be a different story if you wanted the gap to be at least some value, say, $gap=0.01$, so that $p_1+0.01\leq p_2$ and so on. Of course, the $gap$ value must be sized so that the constraints are feasible. One could also potentially pose this as a problem of maximizing $gap$ subject to the desired constraints.