# Is the set of optimal strategies convex in a single-agent decision choice problem?

EDITED with insights from the comment below.

Consider a decision maker who has to choose an action among $$\mathcal{Y}\equiv \{1,2,...,L\}$$. The payoff from choosing action $$y\in \mathcal{Y}$$ depends on the state of the world, $$V$$, with support $$\mathcal{V}$$. Specifically, choosing action $$y\in \mathcal{Y}$$ leads the payoff $$u(y,v)$$, where $$u:\mathcal{Y}\times \mathcal{V}\rightarrow \mathbb{R}$$.

Suppose the decision maker has complete information about the realisation of $$V$$ drawn by nature.

A (mixed) strategy of this choice problem is a probability kernel, $$\mathcal{P}_{Y|V}\equiv \{P_{Y}(\cdot| v)\in \Delta(\mathcal{Y}): v\in \mathcal{V}\}$$, collecting probability distributions of $$Y$$ conditional on every realisations $$v$$ of $$V$$.

Hence, $$\mathcal{P}_{Y|V}$$ is an optimal strategy of the choice problem above if $$\forall v\in \mathcal{V}$$ such that $$P_{Y}(y|v)>0$$, and $$\forall \tilde{y}\neq y$$ \begin{aligned} u(y, v) \geq u(\tilde{y},v). \\ \end{aligned}

Let $$\mathcal{Q}^*$$ be the collection of all optimal strategies of the choice problem above, that is $$\mathcal{Q}^*\equiv \Big\{\mathcal{P}_{Y|V}: \forall v\in \mathcal{V}, \forall y \in \mathcal{Y}\\ \hspace{6cm}\underbrace{P_{Y}(y|v)>0 \Rightarrow u(y, v) \geq u(\tilde{y},v)\text{ } \forall \tilde{y}\neq y}_{\text{This is not a linear constraint because of the form "IF ... THEN ..."}}\Big\}$$

Question 1) The definition of $$\mathcal{Q}^*$$ just given seems to highlight that $$\mathcal{Q}^*$$ is not a convex set. This is because it is defined by a constraint of the type "IF ... THEN ...", which is not linear.

Is this comment correct?

Question 2) Consider a payoff function $$u(1,v)=u(L,v)>u(y,v)$$ $$\forall y \neq 1,L$$ and $$\forall v \in \mathcal{V}$$. Consider the following strategies $$1) \mathcal{P}_{Y|V}\text{ s.t. } P_{Y}(1|v)=1 \text{ and }P_{Y}(y|v)=0 \text{ }\forall y\neq 1, \forall v \in \mathcal{V}$$ $$2) \tilde{\mathcal{P}}_{Y|V}\text{ s.t. } \tilde{P}_{Y}(L|v)=1 \text{ and }\tilde{P}_{Y}(y|v)=0 \text{ }\forall y\neq L, \forall v \in \mathcal{V}$$ $$3) \mathcal{P}^*_{Y|V;\alpha}\text{ s.t. } P^*_{Y}(1|v;\alpha)=\alpha P_Y(1|v) \text{, } P^*_{Y}(L|v;\alpha)=(1-\alpha) \tilde{P}_Y(L|v) \text{, and }P^*_{Y}(y|v;\alpha)=0 \text{ }\forall y\neq 1,L, \forall v \in \mathcal{V}, \forall \alpha \in (0,1)$$ I believe that the set $$\mathcal{B}\equiv \{\mathcal{P}_{Y|V}, \tilde{\mathcal{P}}_{Y|V}, \mathcal{P}^*_{Y|V;\alpha} \text{ }\forall \alpha\in (0,1)\}$$ is convex. Indeed it seems to me that $$\mathcal{B}$$ is the convex hull of $$\{\mathcal{P}_{Y|V}, \tilde{\mathcal{P}}_{Y|V}\}$$.

Correct?

What is the relation between $$\mathcal{Q}^*$$ and $$\mathcal{B}$$?

I think that $$\mathcal{B}\subseteq \mathcal{Q}^*$$. This is because for each element in $$\mathcal{B}$$, the "IF ... THEN ..." condition defining $$\mathcal{Q}^*$$ is satisfied.

Does $$\mathcal{Q}^*\subseteq \mathcal{B}$$ too? If my assertion is question 1) is correct, then it should be $$\mathcal{Q}^*\supset \mathcal{B}$$ because otherwise $$\mathcal{Q}^*$$ would be convex. But here I'm lost: which element of $$\mathcal{Q}^*$$ does not belong to $$\mathcal{B}$$?

• Regarding your first question, we know that if a set is described by linear inequalities only, then it is a convex set. Your's is not only described by linear inequalities. However, you cannot conclude it is not a convex set. – Regio Aug 24 '19 at 21:23

The set $$Q^*$$ is the set of probability distributions over the maximizers of $$u$$ for each value of $$v$$. So for a fixed $$v$$ all the values of $$Y$$ that have positive probability must give the same utility. That is, if $$P_Y(y|v)>0$$ and $$P_Y(y'|v)>0$$ then $$u(y,v)=u(y',v)\geq u(\tilde y,v)$$ for all $$\tilde y\neq y, y'$$. Therefore, convex combinations of elements in $$Q^*$$ must also be collections of probability distributions $$P_{Y|V}$$ supported over the same elements in $$Y$$. That is, the convex combination will also be supported over maximizers of $$u$$ for each $$v$$.
In conclusion, even though the set of maximizers is not guaranteed to be convex, the set $$Q^*$$, of distributions, is a convex set.
• Thanks. Hence, $\mathcal{Q}^*=\mathcal{B}$ and it is convex. Correct? – user3285148 Aug 26 '19 at 12:58
• Yes, for the particular $u$ described in your second question, those two sets are the same, I think. – Regio Aug 27 '19 at 14:31