1. INTRODUCTION

This paper discusses the model proposed by Novikov in [1, 2]. The meaning of the investigated structures is as follows. Two players choose a control from a given set \(V \). The choice is made in two stages. Player 1 (Principal) fixes a non-empty subset of the set \(V\) from which player 2 finally chooses a control. In addition, player 2 is assumed to make a decision rationally; player 1 knows the goals of his partner and, therefore, is able to a priori estimate the latter’s set of optimal choices. The payoff of player 2 is supposed to depend on his own control only, whereas the payoff of player 1 depends on his own control and also on the set he chose: “introducing certain constraints may incur definite costs for the Principal.”

An interpretation of this model was described in the papers [1, 2]. It raises some questions, but they should not discussed in detail here, since the model can be generalized or modified for eliminating the associated problems.

The problems under consideration belong to a new class: it is required to find an optimal subset of some set. No effective methods for solving such problems have been proposed so far. In the papers [1, 2], the complexity of this problem was noted, and the idea was suggested to replace it by a simpler problem: find an optimal subset in some parametric family of sets. But in this case, purely formally, the problem immediately passes from the new class described above to the class of ordinary game-theoretic problems. And the only conceptual issue remaining is to select an appropriate parametric family. If a “narrow” family is selected, there is a high probability of obtaining a result much worse than can be expected. In the case of a “wide” family, most likely, there will be problems with finding the optimal subset in this family. Other authors also addressed this model (see [3, 4]), but no efficient solutions were proposed.

This problem will be studied below. From the very beginning, note that the problem will hardly be solved without making some additional assumptions about the nature of the payoff functions. After all, even a common optimization problem cannot be solved without such assumptions (usually, smoothness or convexity conditions are imposed). However, the assumptions like smoothness or convexity are difficult to use in this case. But there is another way as follows.

The class of subsets of a given set is partially ordered by the inclusion relation. Therefore, a monotonic dependence of the payoff of player 1 on his choice can be assumed. Non-decreasing functions will be considered below, which seems to agree with the quote in the first paragraph of this paper. Formally, non-increasing functions can be considered too. But this problem is quite simple, and besides, has no convincing interpretation; therefore, it will not be considered.

Also, standard topological constraints are imposed. Moreover, if the assumption of benevolence is rejected, some additional constraints are imposed for excluding the degenerate and rarely encountered problems (in a certain sense) from consideration. Under these conditions, sufficiently constructive solutions of the stated problems can be found; see below.

2. PROBLEM STATEMENT

Introduce the following notations: \(\Phi (X, Y)\) is the class of all functions mapping a set \(X\) into a set \(Y \); \(\Sigma (X)\) is the family of all non-empty subsets of the set \(X\); finally, \(\Psi (X, Y) \) is the family of all point-to-set mappings associating with each point \(x\in X\) a non-empty subset of the set \(Y \). As usual, the symbol \(\mathbb {R} \) denotes the set of real numbers.

As has been noted in the Introduction, this paper considers a game in which the set of possible choices of the lower-level player depends on the Principal’s decision. Therefore, the game with forbidden situations is an adequate model. This is formalized as follows.

A game with forbidden situations (or simply, a game) is a quintuple

$$ \Gamma =\langle U, V, \Omega , g, h\rangle ,$$

where \(U \) and \(V \) are some sets, \(\Omega \in \Psi (U, V) \), and \(g \) and \(h \) are some functions from the set \(\Phi \left ( {U \times V,\mathbb {R}} \right )\).

This construction can be interpreted in the following way. The Principal can choose any control \(u\in U\). If such a choice is made, then player 2 can choose any control \(v \) from the set \(\Omega (u) \subset V \). After choosing controls \(u \) and \(v \), the players obtain the payoffs \(g(u, v) \) and \(h(u, v) \), respectively.

To close the model, it is necessary to specify the order of moves and the attitude of both players to uncertainty. Further, two approaches will be applied, dating back to Germeier and Stackelberg. In both cases, the Principal is considered to have the right of the first move.

In this setup, there are no problems with describing the attitude of player 2 to uncertainty: under a fixed control \(u\) of the Principal, the result of player 2 depends only on his own choice (no uncertainty). Therefore, he should choose controls from the set

$$ BR\left ( u \right )=\left \{ {v\in \Omega \left ( u \right ):h\left ( {u,v}\right )=\mathop {\max }\limits _{{\omega }\in \Omega \left ( u \right )}h\left ( {u,{\omega }} \right )} \right \}. $$
(1)

If the Principal knows the interests of the partner, he can estimate this set. Therefore, with a guarantee he can expect to obtain the result

$$ R\left ( \Gamma \right )=\mathop {\sup }\limits _{u\in U} \mathop {\inf }\limits _{v\in BR\left ( u \right )} g\left ( {u, v} \right ). $$
(2)

An additional assumption can be made about the benevolence of player 2 to the Principal: from the set \(BR(u)\), he will always choose the control best for the Principal. In this case, the Principal can expect to obtain the result

$$ S\left ( \Gamma \right )=\mathop {\sup }\limits _{u\in U} \mathop {\sup }\limits _{v\in BR\left ( u \right )} g\left ( {u,v} \right ). $$
(3)

This paper will study one special game of the following form: \(U =\Sigma (V) \), \(\Omega (u)=u\) for any set \(u \subset \) \(U\), and the function \(h \) is independent of \(u \), i.e.,

$$ h(u, v)=f(v).$$

An interpretation is as follows. The Principal first chooses a constraint \(u \) imposed on player 2. After that, player 2 has the right to choose any control \(v\) from the set \(u \), and his payoff depends only on this choice. The Principal’s payoff also depends on the choice of player 2, but the Principal also bears some costs to check the constraint. Therefore, his payoff also depends on the chosen set \(u \).

One more significant assumption will be made regarding the form of the function \(g \). Suppose that for any fixed \(v \), this function monotonically depends on \(u \), i.e., the inclusion \(u \subset w \) implies the inequality

$$ g(u,v)\le g(w, v). $$

Let the set \(V\) be equipped with a topology and compact, the function \(f\) be continuous, and the function \(g \) be continuous in \(v \) for any fixed \(u \). These assumptions are rather standard.

Calculating the values \(R(\Gamma )\) and \(S(\Gamma ) \) in the game of this form will be the main problem of this paper. In one respect, the formulation of this problem requires clarification. Since the set \(u \) can be quite arbitrary, the maximum in the definition of the set \(BR(u)\) may not be achieved. Therefore, formally speaking, the definition of the mapping \(BR \) must be extended. This will be done where necessary. First, consider the case when these problems do not arise. More specifically, first assume that the set \(V\) is finite.

In this case, the set \(U\) will also be finite; therefore, formally, the game \(\Gamma \) will be a standard game with forbidden situations. But, it is clear that if the set \(V \) contains \(n \) elements, then calculating the values \(R(\Gamma ) \) and \(S(\Gamma ) \) directly by their definitions, without taking into consideration the specifics of the game, will require the enumerative search of \((2^{n}-1) \) strategies of player 1, which is generally difficult. Therefore, the problem can be considered solved when finding an appropriate procedure for the enumerative search of the number of options polynomial in \(n \).

Consideration of such a finite game transparentizes the conceptual meaning of the additional assumptions and ideas used. Moreover, the results obtained in this case do not formally follow from those for the games with infinite sets \(V \).

3. FINITE GERMEIER GAME

In this section, an additional assumption is accepted as follows.

Regularity hypothesis 1 (RD).

The function \(f\) is such that for all controls \(v \) and \(\omega \) from the set \(V \), the inequality \(v \ne \omega \) implies the inequality \(f(v)\ne f(\omega ) \). \(\diamondsuit \)

This assumption will be discussed at the end of Section 3.

For a real number \(\lambda \), define the set

$$ D(\lambda ) = {\{}v\in V: f(v) \le \lambda {\}},$$

and for any subset \(w \) of the set \(V \), define the value

$$ l( w )= \sup \limits _{v\in w} f( v ).$$

Let \(u\) be an arbitrary strategy of the Principal. Consider also the strategy \(w =D(l(u)) \). By definitions of the set \(D \) and the value \(l \), \(l(u)=l(w)\). Due to the RD hypothesis, each of the sets \(BR(u)\) and \(BR(w) \) consists of one point, and hence,

$$ BR(u) =BR(w) = {\{}v^{0}{\}}. $$

In addition, by the construction procedure, \(u \subset w \). Therefore,

$$ \mathop {\inf }\limits _{v\in u} g(u,v)=g\left ( {u,v^0} \right )\le g\left ({w,v^0} \right )=\mathop {\inf }\limits _{v\in w} g(w,v).$$

Thus, when searching for the optimal strategy of the Principal, only the sets of the form \(D(\lambda ) \) can be considered.

In other words, the following result holds.

Theorem 1.

Under the assumptions accepted above,

$$ R\left ( \Gamma \right )=\mathop {\max }\limits _{{\lambda }\in {\rm \mathbb {R}}}g\left ( {D\left ({\lambda } \right ),\,\,v\left ({\lambda }\right )} \right ),$$
(4)

where the (unique) control \( v(\lambda )\) is given by the condition \(f(v(\lambda ))=l(D(\lambda )) \). \( \diamondsuit \)

Clearly, in this theorem, it is possible to consider only those values \(\lambda \) for which there exists an \(\omega \in V \) such that \(\lambda =f(\omega ) \). Therefore, for calculating the maximum in formula (4), it suffices to enumerate \(n \) values of the function \(f \). For obtaining the set \(D(\lambda ) \) and control \(v(\lambda ) \) for each \(\lambda \), the enumerative search of not more than \(n \) options is required. Thus, the value \(R(\Gamma ) \) can be calculated using a procedure of quadratic complexity.

Now discuss the meaning of the RD hypothesis. According to the generally accepted strategy dating back to Poincaré, the study of new mathematical objects should begin with objects of generic position and only then proceed to the study of various kinds of degenerate cases. The RD condition is precisely the condition of generic position. This can be formalized in different ways, e.g., as follows. If the number of elements \(n \) in the set \(V \) is fixed, then the game under consideration is completely characterized by an ordered set of numbers—the payoffs of the players. Such a set can be treated as an element of a finite-dimensional linear space (of dimension \(n^{2}2^{n}) \). With the Euclidean topology considered on this space and with such an identification, the games not satisfying the RD condition will correspond to the set of the first category (in the sense of Baire). With the Lebesgue measure considered on the same space, the irregular games will correspond to null sets (set of measure 0).

Where will the rejection of this assumption lead? As is easily seen, in the general case, it is impossible to avoid the enumerative search of subsets of the set

$$ D^{\ast }(\lambda ) = {\{}v \in V: f(v)=\lambda {\}}.$$

Generally speaking, the number of elements of the set \(D^{\ast }(\lambda )\) can be close to that of the set \(V\). Hence, a polynomial algorithm will not be constructed. One approach is trying to replace the RD hypothesis with some kind of assumption regarding the dependence of the function \(g \) on both arguments. However, quite natural assumptions of this kind are not found.

Finally, note that when the RD hypothesis is rejected, the problem of calculating \(R(\Gamma ) \) becomes unstable: for infinitesimal variations of the values of the function \(f\), the value \(R(\Gamma ) \) can change significantly. Therefore, the problem of calculating the value \(R(\Gamma )\) becomes, to a large extent, meaningless. It makes sense to calculate the upper and lower regularizing estimates of this value. But these issues take too far from the subject of this paper.

4. FINITE STACKELBERG GAME

The value \( S(\Gamma )\) is calculated even simpler, and no additional assumptions like regularity are required.

Consider again an arbitrary strategy \(u \in U \) and compare it with the strategy \(w =D(l(u)) \).

As above, it can be established that \(l(u)=l(w) \) and \(u \subset w \). And since by definition

$$ BR(u) = {\{}v\in u: f(v)=l(u){\}}$$

and

$$ BR(w) = {\{}v\in w: f(v)= l(w){\}},$$

the inclusion \(BR(u)\subset BR(w) \) holds. Hence,

$$ \mathop {\max }\limits _{v\in BR(w)} f\left ( v \right )\ge \mathop {\max }\limits _{v\in BR(u)} f\left ( v \right ).$$

Thus, the optimal strategy can be found among the strategies of the form \(D(\lambda )\).

Let

$$ q(\lambda )=\max \limits _{v\in D^\ast \left ({\lambda } \right )}g\left ( {D\left ({\lambda } \right ),v} \right ).$$

Then, the following result is true.

Theorem 2.

$$ S\left ( \Gamma \right )=\mathop {\max }\limits _{ {\lambda }\in { \mathbb {R}}}q\left ( {\lambda } \right ). \quad \diamondsuit$$

In the general case, the game under consideration can have several optimal strategies. (For example, if the function \(g\) is constant, then any strategy will be optimal.) In this regard, the fact below is of certain interest.

Corollary 1.

There exists an optimal strategy \(u \) such that for any optimal strategy \(w\) , the inclusion \(w\subset u\) holds.

5. INFINITE GERMEIER GAME

Now turn to the problem of calculating the value \(R(\Gamma ) \) in the case of an infinite set \(V \). In this case, the strategy \(u \subset V \) can be chosen so that the upper bound \(\sup \limits _{v\in V} f( v)\) will not be achieved, making the value \(R(\Gamma ) \) undefined. Therefore, the definition of the maximum guaranteed result requires some clarification. This will be done in a standard way for general-form games.

Suppose that if the upper bound \(\sup \limits _{w\in \Omega \left ( u\right )} h\left ( {u,w} \right )\) is achieved, then the set \(BR(u)\) is determined by formula (1); otherwise, by the formula

$$ BR ( u )=\left \{ {v\in \Omega \left ( u \right ):h\left ( {u,\,\,v}\right )\ge \mathop {\sup }\limits _{w\in \Omega \left ( u \right )} h\left ({u, w} \right )- {\kappa }} \right \},$$
(5)

where \(\kappa \) is some fixed number. The value \(R(\Gamma ) \) will be determined by the same formula (2).

For further presentation, some condition of generic position will be required again. Formulate it as follows.

Regularity hypothesis 2 (RC).

For any \(v\in V\) and any number \(\lambda \), the equality \(g(D(\lambda ),v)= g(D^{0}(\lambda ), v)\) holds, where \(D^{0}(\lambda ) = {\{}v\in V: f(v) < \lambda {\}}\). \(\diamondsuit \)

Discuss this condition at an informal level. In fact, there are two meaningful assumptions contained in it:

  1. a)

    The level set \(D^{\ast }(\lambda )\) of the function \(f \) represents a “small” set.

  2. b)

    Under the invariable strategy \(v\) of player 2, the Principal’s payoff will not change if a small set is added to his strategy.

The basic model example is as follows: the set \(V \) is a convex subset of a finite-dimensional Euclidean space with a non-empty interior, the function \(f\) is a nonconstant polynomial, and the function \(g\) can be represented in the form

$$ g(u,v)=\varphi (\mu (u),v),$$

where a function \({\varphi }\in \Phi \left ({\mathbb {R}\times V,{\mathbb {R}}} \right ) \) and \(\mu \) is an external (or internal) Lebesgue measure. In this case, the RC condition is surely satisfied.

Condition a) is the condition of generic position. In the typical case, the level set of a function is a hypersurface that “has zero measure,” “the first category,” etc. The terms in quotation marks can be defined exactly and the corresponding statements can be proved, but such issues goes beyond the scope of this paper.

Condition b) is the “continuity” condition, which would hardly cause any objections.

Quite probably, the RC condition cannot be significantly weakened, while preserving the constructive solvability of the problem stated. At the same time, a possible approach is to change it somehow, for example, by weakening condition a) and simultaneously strengthening condition b), or vice versa. However, there is no particular need for this yet.

Proceed to the solution of the problem. Introduce the following notations:

$$ \begin {gathered} r(u)=\inf \limits _{v\in BR\left ( u \right )} g\left ( {u,v}\right ),\\ E\left ({\lambda }\right )=\left \{ {v\in D^\ast \left ({\lambda }\right ):g\left ( {D\left ({\lambda } \right ),v} \right )=\mathop {\max }\limits _{w\in D^\ast \left ({\lambda }\right )}g\left ({D\left ({\lambda }\right ),w}\right )}\right \}. \end {gathered}$$

Fix an arbitrary strategy \(u\in U\). Also, consider the strategy \( w=D^0({l(u)})\cup E({l(u)})\), and compare the results \(r(u) \) and \(r(w) \) with one another.

Select a sequence \(v_{1}, v_{2},{\ldots } \) of elements of the set \(BR(u) \) so that

$$ \lim \limits _{k\to \infty } f(v_k )=\sup \limits _{v\in u}f\left ( v \right ).$$

(If the maximum in formula (1) is achieved, this sequence can be selected constant.) Due to the compactness of the set \(V \), without loss of generality, suppose that this sequence converges to an element \(v_{0}\). Then, \(f(v_{0})=l(u) \) by the continuity of the function \(f \).

Since the set \(BR(u)\) contains the elements \(v_{k} \), the inequalities \(g(u,v_{k})\ge r(u) \) are satisfied. Hence, due to the continuity of the function \(g \), the inequality \(g(u, v_{0}) \ge r(u) \) holds. And as \(u\subset (l(u)) \), from the monotonicity property it follows that \(g(D(l(u)), v_{0}) \ge r(u)\).

It can be directly verified that

$$ BR(w)=E(l(u)).$$

Therefore, for any \(\omega \in BR(w)\),

$$ g( {D( {l( u )}),v_0 } )\le g({D( {l( u )} ),{\omega }} )=\inf \limits _{v\in BR( w )} g( {D( {l( u)} ),v}). $$

Since

$$ D^{0}(l(u)) \subset w \subset D(l(u)) $$

by the construction procedure, the monotonicity property implies the inequalities

$$ g(D^{0}(l(u)), v) \le g(w, v) \le g(D(l(u)), v)$$

for any \(v \). However, due to the RC condition,

$$ g(D^{0}(l(u)), v)=g(D(l(u)), v),$$

and therefore,

$$ g(w, v)=g(D(l(u)), v). $$

Consequently,

$$ r\left ( w \right )=\inf \limits _{v\in BR\left ( w \right )} g\left ({w,v} \right )=\inf \limits _{v\in BR\left ( w \right )} g\left ({D\left ( {l\left ( u \right )} \right ),v} \right ).$$

Summarizing the considerations presented above, obtain the inequality \(r(u)\le r(w) \). Hence, among the strategies yielding the result \(R(\Gamma ) \) with any a priori given accuracy, there surely exists a strategy in the form \(D^0\left ({\lambda } \right )\cup E\left ({\lambda } \right )\) with some number \(\lambda \). Therefore, the following statement is true.

Theorem 3.

$$ R\left ( \Gamma \right )=\sup \limits _{{\lambda }\in {\mathbb {R}}}\max \limits _{w\in D^\ast \left ({\lambda } \right )} g\left ({D\left ({\lambda } \right ),w} \right ). \quad \diamondsuit$$

Discuss the relation between the RD and RC conditions. If the set \(V \) is finite, then the RC condition obviously holds only for those functions \(g\) that do not depend on \(u \). This is of little interest. In turn, the RD condition can be satisfied only in the case when the dimension of the set \(V \) does not exceed 1, which is also very restrictive. Thus, Theorems 1 and 3 are independent of one another. They both make sense, but each for its own field of application.

6. MAXIMUM GUARANTEED RESULT IN GAME WITH BENEVOLENT SECOND PLAYER

For calculating the value \(S(\Gamma )\) in the game with an infinite set \(V\), the definition has to be refined again. This causes a problem: such models have been considered many times, but in most cases exact definitions are absent.

The same ideas as employed for refining the definition of \(R(\Gamma ) \) are inapplicable here, for the following reasons. When defining the set of rational responses by formulas (1) and (5), the Principal is deliberately “pushed” to choose a strategy so that the maximum in formula (1) will not be achieved. This poorly agrees with conceptual interpretations. For the stated reason, the result \(S(\Gamma ) \) will depend on the value \(\kappa \). This makes both the interpretation and identification of the resulting model difficult. In addition, the solutions of similar problems turn out to be very difficult; for example, see the paper [5]. Therefore, the application of the results obtained becomes complicated. As can be expected, the same concerns the case under study.

Therefore, proceed as follows.

For the problem under consideration, under the assumptions made in Section 3, the following result is true.

Lemma 1.

The value \(R(\Gamma ) \) is equal to the least upper bound of the numbers \(\gamma \) for which there exist a strategy \(u \in U \) and a number \( \lambda \in \mathbb {R}\) that satisfy the following conditions:

  1. –

    There exists a strategy \(\omega \) for which \( h(u, \omega ) \ge \lambda \) and \(g(u, \omega )\ge \) \( \gamma \) .

  2. –

    For any strategy \(v\in V \) , either \( g(u, \omega ) \ge \gamma \) or \(h(u, \omega ) < \lambda \) . \( \diamondsuit \)

This lemma will not be used below; therefore, its proof is omitted here. For a detailed description of the technique of proving, see the paper [6]. Such constructions have been applied many times and demonstrated their effectiveness. Further, they will be adopted for determining the value \(S(\Gamma ) \).

Definition 1.

The value \( S(\Gamma )\) is equal to the least upper bound of the numbers \(\gamma \) for which there exist a strategy \(u \in U \) and a number \({\lambda }\in {\mathbb {R}} \) that satisfy the following conditions:

  1. 1)

    There exists a strategy \(\omega \in \Omega (u) \) for which \(h(u, \omega )\ge \lambda \) and \(g(u, \omega )\ge \gamma \).

  2. 2)

    For any strategy \(v\in \Omega (u)\), either \(g(u, v)\ge \gamma \) or \(h(u, v) \le \lambda \).

In this case, the number \(\gamma \) is called a guaranteed result. \(\diamondsuit \)

The meaning of this definition is clear. If a strategy \(u \) is chosen and known to player 2, then for him all his strategies \(v \) are divided into two classes, beneficial (for which \(h(u, \omega ) \ge \lambda )\) and unbeneficial (for which \(h(u, \omega ) < \lambda )\). Obviously, the Principal should choose his control so that all partner’s choices yielding that an insufficiently good result for the Principal would be unbeneficial for player 2. Item 2) of Definition 1 ensures such a choice. Item 1), first, fixes the existence of a beneficial strategy of player 2, and second, notes his benevolence.

In addition, the rationale for using this definition can be obtained by comparing it with the traditional definition in the case when the latter is correct. Therefore, prove the following statement.

Lemma 2.

Let the game be such that for any strategy \( u\in U\), the maximum in formula (1) and the upper bounds in formula (3) are achieved. Then the values given by formula (3) and Definition 1 coincide with one another.

Proof. For the time being, denote by \(S_{0}(\Gamma ) \) the value given by Definition 1. It is necessary to establish the equality \(S(\Gamma )=S_{0}(\Gamma ) \). First, prove the inequality \(S(\Gamma ) \le S_{0}(\Gamma ) \).

Select a strategy \(u\in U\) so that

$$ \max \limits _{v\in BR( u )} g( {u,v})=\max \limits _{w\in U} \max \limits _{v\in BR( u )} g( {w,v} )=S( \Gamma ).$$

Let a control \(\omega \in BR(u) \) satisfy the condition

$$ g( {u,{\omega }})=\max \limits _{v\in BR( u )} g( {w,v} )=S( \Gamma ),$$

and let \(\lambda = \max \limits _{v\in \Omega (u)} h(u,v)\).

Then, the number \(\gamma =S(\Gamma )\) satisfies item 1) of Definition 1 by the construction procedure. Due to the choice of the number \(\lambda \), for \(v \in \Omega (u) \) the inequality \(h(u \), \(v) \le \lambda \) holds and, hence, item 2) of Definition 1 is satisfied. Hence, \(\gamma \) is the guaranteed result, and therefore,

$$ \gamma = S(\Gamma ) \le S_{0}(\Gamma ).$$

Now, prove the inverse inequality \(S(\Gamma )\ge S_{0}(\Gamma ) \).

Fix an arbitrary guaranteed result \(\gamma \). Let a strategy \(u \in U \), a number \(\lambda \in \,\mathbb {R} \) and a strategy \(\omega \in \Omega (u) \) be selected so that items 1) and 2) of Definition 1 are satisfied. Without loss of generality, it can be supposed that \(\lambda =\max \limits _{v\in \Omega ( u )} h({u,v}) \).

Actually, if \(h(u,\omega )=\max \limits _{v\in \Omega (u)}h({u,v}) \), then everything is obvious. Otherwise, select an arbitrary element \(\omega _{0}\) so that \(h({u,\omega _0})=\max \limits _{v\in \Omega (u)}h( {u,v}) \). In this case, the inequality \(h(u, \omega _{0}) > \lambda \) will be satisfied, and due to item 2) of Definition 1, \(g(u, \omega _{0}) \ge \gamma \). But then for the same strategy \(u \), the number \(\lambda _0 =\max \limits _{v\in \Omega ( u )}h( {u,v} )\) and the strategy \(\omega _{0}\), item 1) of Definition 1 will be satisfied. And item 2) of Definition 1 will be satisfied due to the inequality \(\lambda _{0} \ge \lambda \).

But if \(\lambda \) is selected so that \(\lambda =\max \limits _{v\in \Omega ( u )}h( {u,v} ) \), then the strategy \(\omega \) (which exists by item 1) of Definition 1) belongs to the set \(BR(u) \). Hence,

$$ {\gamma }\le g\left ( {u,{\omega }} \right )\le \max \limits _{v\in BR( u )} g( {u,v} )\le \max \limits _{u\in U} \max \limits _{v\in BR( u )} g({u,v})=S( \Gamma ). $$

Due to the arbitrariness of \(\gamma \), the inequality \(S(\Gamma )\ge S_{0}(\Gamma ) \) follows, and the proof of Lemma 2 is complete. \(\quad \blacksquare \)

Remark 1.

The condition of Lemma 2 can be slightly weakened. This will lengthen the reasoning, not changing anything in essence. Therefore, a more general result is not considered here.

7. INFINITE STACKELBERG GAME

In this section, the value \(S(\Gamma )\) (see Definition 1) will be calculated.

Use the previous notations:

$$ \begin {gathered} D(\lambda ) = {\{}v \in V: f(v) \le \lambda {\}}, \\ D^{\ast }(\lambda ) = {\{}v \in V: f(v)=\lambda {\}}, \\ q( {\lambda })=\max \limits _{v\in D^\ast ({\lambda })} g( {D({\lambda } ),\,v}). \end {gathered}$$

The following result is true.

Theorem 4.

$$ S( \Gamma )=\sup \limits _{\sigma \in \mathbb {R}}q({\sigma }).$$

Proof. First, establish the inequality \(S( \Gamma )\ge \sup \limits _{\lambda \in \mathbb {R}}q({\lambda }) \). Fix an arbitrary number \(\varepsilon >0 \) and select \(\lambda \) so that

$$ q({\lambda } )\ge \sup \limits _{\sigma \in \mathbb {R}}q({\sigma })-{\varepsilon }. $$

Let \(u =D(\lambda )\) and select a strategy \( \omega \in D^{\ast }(\lambda )\) so that

$$ g( {u,\omega } )=\max \limits _{v\in D^\ast ({\lambda })} g( {u,v} ). $$

Then, the number \(\gamma =g(u, \omega ) \) will be the guaranteed result. Really, item 1) of Definition 1 is satisfied, since \(\gamma =g(u, \omega ) \), and the equality \(h(u,\omega )=\lambda \) holds due to the of choice \(\omega \in D^{\ast }(\lambda ) \). Item 2) of Definition 1 is satisfied as well: for all \(v \in u = D(\lambda ) \), the inequality \(h(u, v) \le \lambda \) holds by definition.

Thus,

$$ S\left ( \Gamma \right )\ge {\gamma }=g\left ( {u,\,{\omega }}\right )=\max \limits _{v\in D^\ast \left ({\lambda } \right )}g\left ( {u,\,\,v} \right )=\max \limits _{v\in D^\ast \left ({\lambda } \right )} g\left ( {D\left ({\lambda } \right ),\,v}\right )=q\left ({\lambda } \right )\ge \sup \limits _{{\sigma }\in \mathbb {R}} q\left ({\sigma }\right )-{\varepsilon }.$$

In view of the arbitrariness of \(\varepsilon \), the required inequality follows.

Now, prove the inequality \(S\left ( \Gamma \right )\le \sup \limits _{{\lambda }\in \mathbb {R}} q\left ({\lambda } \right )\). Let \(\gamma \) be an arbitrary guaranteed result. Select a strategy \(u \in U \), a number \({\lambda }\in \mathbb {R} \) and a strategy \(\omega \in \Omega (u) \) so that items 1) and 2) of Definition 1 are satisfied.

Let \({\sigma }=\sup \limits _{v\in u} f(v) \). If \(f(\omega )=\sigma \), then \(\omega \in D^{\ast }(\sigma ) \) and

$$ {\gamma }\le g\left ( {u,\,{\omega }} \right )\le \max \limits _{v\in D^\ast \left ({\sigma } \right )} g\left ( {u,\,v}\right )\le \max \limits _{v\in D^\ast \left ({\sigma }\right )} g\left ( {D\left ({\sigma } \right ),\,v} \right )=q\left ({\sigma } \right ).$$

(Here the monotonicity of the function \(g\) and the inclusion \(u \subset D(\sigma )\) are taken into consideration.) Otherwise, the set {\(v \in u\): \(f(v)> \lambda \)} is non-empty. Select a sequence \(v_{1} \), \(v_{2},{\ldots } \) of elements of the set \({\{}v\in u \): \(f(v) > \lambda {\}} \) so that

$$ \lim \limits _{k\to \infty } f\left ( {v_k } \right )=\sup \limits _{v\in u}f(v)={\sigma }. $$

Due to the compactness of the set \(V \), without loss of generality, suppose that this sequence converges to some element \(v_{0}\). As \(f(v_{k})> \lambda \), item 2) of Definition 1 implies the inequalities \(g(u, v_{k}) \ge \gamma \) (\(k = 1, 2,{\ldots } \)). Then, \(g(u, v_{0})\ge \gamma \) by the continuity of the function \(g \). Since the function \(h \) is continuous, the inclusion \(v_{0 }\in D^{\ast }(\sigma ) \) holds, and consequently,

$$ {\gamma }\le g\left ( {u,\,v_0 } \right )\le \max \limits _{v\in D^\ast \left ({\sigma } \right )} g\left ( {u,\,v}\right )\le \max \limits _{v\in D^\ast \left ({\sigma }\right )} g\left ( {D\left ({\sigma } \right ),\,v} \right )=q\left ({\sigma } \right ). $$

Thus, in any case

$$ {\gamma }\le q\left ({\sigma } \right )\le \sup \limits _{{\lambda }\in \mathbb {R}} q\left ({\lambda } \right ). $$

Due to the arbitrariness of \(\gamma \), the inequality

$$ S\left ( \Gamma \right )\le \sup \limits _{{\lambda }\in \mathbb {R}} q\left ({\lambda } \right ) $$

follows, and the proof of Theorem 4 is complete. \(\quad \blacksquare \)

Corollary 2.

Under the condition \(RC \) , \( R(\Gamma )=S(\Gamma )\) .

Remark 2.

According to the proofs of Theorems 2 and 4, closed sets can always be considered as the \(\varepsilon \)-optimal strategies of the Principal in this game. The statement of the main problem can be modified by admitting only compact subsets of the set \(V \) as the Principal’s strategies. This problem also looks meaningful. Due to the aforesaid, the maximum guaranteed result of the Principal (both in the sense of Germeier and in the sense of Stackelberg) will not change with such a modification of the problem statement. It can be shown that in the modified game, the maximum guaranteed result of the Principal in the sense of Definition 1 can be calculated by formula (3). The proof repeats almost word for word the proof of Lemma 2.

8. CONCLUSIONS

The assumptions presented in this paper have rather convincing practical interpretations and lead to an effective solution of the problems under consideration. The solutions found look quite simple. Therefore, it is possible to study more complex and interesting models of this form. The following fields of research seem to be the most promising.

It is worth considering models that take into account the presence of an external uncertain factor and asymmetric information of the players about this uncertainty.

The structure of the Principal’s strategies can be concretized by assuming that he has the ability to receive information about the partner’s choice. Perhaps, in this case, it is reasonable to take into consideration the existence of constraints on the amount of such information.

The family of subsets of a given set is a partially ordered set and, in addition, an algebra with respect to the operations of union and intersection. Therefore, other constraints, such as superadditivity or subadditivity, can be imposed on the Principal’s payoff function, instead of the monotonicity condition. These conditions can be interpreted somehow, and the problems discussed above can be solved under such assumptions.