# Automatic Prompt Selection for Large Language Models

Viet-Tung Do1, Van-Khanh Hoang1, Duy-Hung Nguyen1, Shahab Sabahi1,
Jeff Yang1, Hajime Hotta1, Minh-Tien Nguyen1,2 and Hung Le3
1 Cinnamon AI, Vietnam.
{ace, kay, hector, sshahab, jeff.yang, hajime<EMAIL_ADDRESS>
2 Hung Yen University of Technology and Education, Vietnam.
<EMAIL_ADDRESS>
3 Deakin University, Australia.
<EMAIL_ADDRESS>
###### Abstract

Large Language Models (LLMs) can perform various natural language processing
tasks with suitable instruction prompts. However, designing effective prompts
manually is challenging and time-consuming. Existing methods for automatic
prompt optimization either lack flexibility or efficiency. In this paper, we
propose an effective approach to automatically select the optimal prompt for a
given input from a finite set of synthetic candidate prompts. Our approach
consists of three steps: (1) clustering the training data and generating
candidate prompts for each cluster using an LLM-based prompt generator; (2)
synthesizing a dataset of input-prompt-output tuples for training a prompt
evaluator to rank the prompts based on their relevance to the input; (3) using
the prompt evaluator to select the best prompt for a new input at test time.
Our approach balances prompt generality-specificity and eliminates the need
for resource-intensive training and inference. It demonstrates competitive
performance on zero-shot question-answering datasets: GSM8K, MultiArith, and
AQuA.

##  1 Introduction

Large Language Models (LLMs) have emerged as a cornerstone in natural language
processing (NLP), propelled by advancements in scaling techniques and
attention mechanisms. These colossal models have a remarkable ability to
generate texts based on initial inputs, showcasing extraordinary proficiency
across diverse tasks, particularly in zero-shot and few-shot scenarios Brown
et al. (2020); Srivastava et al. (2023); Nguyen et al. (2023). The key to
unlocking this exceptional performance heavily depends on the choice of
prompts–extra text added to the initial input to query LLMs. Recent studies
underscore the pivotal role of well-crafted prompts in enhancing the accuracy,
adequacy, and relevance of LLM responses across various tasks such as question
answering, text summarization, and text generation Lu et al. (2022); Lyu et
al. (2023); White et al. (2023). Effective prompting reduces the necessity for
resource-intensive fine-tuning on task-specific data, offering a cost-
effective and time-saving alternative. Additionally, when provided with
appropriate prompts, LLMs can engage in intricate reasoning and problem-
solving. This can be achieved by breaking down complex problems into
manageable steps or by providing illustrative examples and demonstrations Yao
et al. (2022); Wei et al. (2022).

Prompting provides a good method for working with LLMs for many NLP tasks,
yet, we argue that manual prompting is a nontrivial task. It requires careful
engineering and testing to achieve the best results, which is time-consuming
and labor-expensive. Early attempts for automatic prompting use gradient
descent optimization on prompt token embeddings, a.k.a "soft prompts" Qin and
Eisner (2021). Alternatively, prompt generation directly generates prompt
tokens, which enhance human interpretability and flexibility Deng et al.
(2022); Zhang et al. (2022a). In this direction, LLMs are viewed as frozen
black boxes where different optimization methods such as evolutionary
algorithm (EA) and reinforcement learning (RL) can be applied to search for an
optimal prompt for all inputs of the downstream task Prasad et al. (2023);
Deng et al. (2022). Other methods use RL to dynamically generate specific
prompts for each input Zhang et al. (2022a). On a different front, LLM-based
approaches employ multiple LLMs to generate and explore better prompts Zhou et
al. (2022); Yang et al. (2023); Liao et al. (2022).

One limitation of current approaches is that they struggle to strike a balance
between prompt generality and specificity, either relying on a single prompt
for all inputs (lacking flexibility) or generating a distinctive prompt per
input (expanding the search space and potentially destabilizing the system).
Intuitively, prompts should change only when there is a shift in input type.
For instance, mathematical data featuring algebraic inputs necessitates an
algebra-related prompt, while geometry inputs require a geometry-related
prompt. Also, current methods are inefficient in computation. EA and RL-based
approaches involve complex optimization and numerous iterations with
downstream LLMs in training. Furthermore, LLM-based methods need to query
multiple LLMs during training or inference, which is slow and expensive.

In this paper, we address the identified limitations of discrete prompt
optimization. Our approach combines prompt generation and ranking to find the
best prompt for a given input and task, achieving a balance between prompt
generality and specificity while ensuring computational efficiency. Our
method, dubbed Automatic Prompt Selection (APS), consists of three steps: (1)
we cluster the task data into coherent groups and use LLM-based prompt
generators to create a set of prompts for each group. We combine these sets to
form a prompt database that covers different input types. (2) We use the
prompts in the database to query an LLM and generate a dataset of tuples, each
containing an input, a prompt, an LLM output, and a ground-truth output. We
train a prompt evaluator on this dataset using a preference loss, which
assigns higher scores to prompts that produce outputs closer to the ground
truth. (3) Given an input, we "generate" an optimal prompt by selecting the
one from the prompt database with the highest score, as determined by the
prompt evaluator. In short, we summarize our contributions as follows.

  * •

We propose a novel approach for discrete prompt optimization, aiming to
identify the optimal prompt from a finite fixed set generated by another LLM.
This strategy minimizes the search space while maintaining a degree of
flexibility to strike a balance between prompt generality and specificity. Our
approach is lightweight, necessitating only standard supervised training on
offline data and enabling cost-effective inference without additional LLM
access.

  * •

We conduct extensive experiments on three challenging QA datasets and show
that our method outperforms state-of-the-art baselines

##  2 Related Works

Prompt engineering plays a crucial role in optimizing LLMs for various tasks,
whether performed manually or automatically Gao et al. (2021); Reynolds and
McDonell (2021). This field encompasses different strategies, such as prompt
tuning Qin and Eisner (2021), prompt generation Zhang et al. (2022a); Singh et
al. (2022), and prompt selection for specific tasks Liao et al. (2022);
Sorensen et al. (2022); Zhang et al. (2022b). Prompt tuning methods employ
gradient-based searches to refine prompts Qin and Eisner (2021); Pang et al.
(2023). However, these methods typically require access to the LLM’s
parameters, limiting their applicability to LLMs with restricted access to
training data. In contrast, our approach belongs to the class of prompt
generation, treating downstream LLMs as black boxes and seeking optimal token-
level prompts without fine-tuning token embeddings.

Figure 1: Automatic Prompt Selection (APS) has three steps. (1) Prompt
Database Generation: We cluster training data, use LLM-based prompt generator
$\mathtt{A}_{1}$ for diverse prompts in each group, and combine them into a
versatile prompt database. (2) Prompt Evaluator Training: We query a data
generation LLM $\mathtt{A}_{2}$ with generated prompts and training inputs to
generate tuples: input ($q,c$), prompt ($p$), LLM output ($a^{\prime}$), and
ground-truth output ($a^{\prime}$). Training the prompt evaluator $\mathtt{E}$
on this dataset, we adopt a preference loss, encouraging high scores for good
prompts and low scores for bad ones. (3) Prompt Ranking: During inference,
given a testing input, we pick the highest-scoring prompt from the database
with the help of the prompt evaluator. The selected prompt (highlighted with
red border) will be used with a downstream LLM $\mathtt{M}$ to compute the
final output $a^{\prime}$.

Prompt generation methods leverage different optimization techniques to
directly generate prompt tokens. For example, RL-Prompt Deng et al. (2022) and
TEMPERA Zhang et al. (2022a) employ reinforcement learning, while GRIPS Prasad
et al. (2023) relies on evolutionary algorithms. These approaches involve
complex optimization processes with extensive interactions with LLMs during
training. In contrast, our method only requires standard supervised training
using offline data, making it efficient and cost-effective. Another line of
research involves leveraging the in-context learning capability of LLMs as
prompt optimizers. For instance, APE Zhou et al. (2022) uses LLMs to generate
multiple instruction candidates, evaluates them using the target model, and
selects the most effective instruction based on calculated evaluation scores.
OPRO Yang et al. (2023) iteratively generates and evaluates multiple prompts,
selecting the most effective ones based on evaluation scores. These approaches
apply the generated prompts to all inputs. In contrast, our approach focuses
on generating diverse prompts and selecting the topmost suitable ones for
different inputs. This strategy strikes a balance between exploration and
exploitation–a dynamic adaptation to contexts-enhancing the effectiveness of
LLMs across diverse applications.

Prompt selection methods, such as ZPS Liao et al. (2022), MI Sorensen et al.
(2022), and Auto-CoT Zhang et al. (2022b), aim to identify high-quality
prompts tailored to specific tasks and inputs. ZPS filters out underperforming
prompts and assembles the remaining prompts for data labeling, while MI
maximizes mutual information between inputs and model predictions. We note
that these methods require an initial human-crafted prompt database or
templates whereas we automatically generate them. Auto-CoT clusters and
generates reasoning chains for questions, selecting representative questions
from each cluster to create a diverse set of examples. However, these prompt
selection methods typically require LLMs to produce outputs for all candidate
prompts before ranking them, leading to significant computational costs or
latency. To address this challenge, our method introduces a trainable prompt
evaluator that is capable of ranking prompts in our database without executing
the LLMs. This approach significantly reduces computational overhead and
latency while maintaining the robustness and diversity of the prompts.

##  3 Automatic Prompt Selection

###  3.1 Problem Statement

The task is to find an optimal prompt for a given question and its relevant
context. Formally, we define a prompt $p$ as an instruction added to the
original input. A downstream task LLM $\mathtt{M}$ will take the prompt-
augmented input and generate an output. In the question answering (QA)
setting, the input can consist of a question $q$ and an optional context $c$,
thus the generated output can be represented as $\mathtt{M}(q,c,p)$. Our
objective is to find an optimal prompt generator $\mathtt{G}^{*}$ so that for
every question and context $(q,c)$, we can sample a prompt $p$ from the prompt
generator to guide the LLM $\mathtt{M}$ to produce an output matching the
correct output $a$. Formally, the selection can be shown as follows.

$\mathtt{G}^{*}=\arg\max_{\mathtt{G}}\mathbb{E}_{(a,q,c),p\sim\mathtt{G}(q,c)}f(\mathtt{M}(q,c,p),a)$
(1)

where $f(\cdot)$ can be any evaluating functions such as exact matching
$1_{\mathtt{M}(q,c,p)=a}$. We note that the training data is only used for
learning the prompt generator. The LLM $\mathtt{M}$ is not fine-tuned or does
not access the training data, thus, our downstream task is equivalent to zero-
shot QA.

This task becomes notably challenging when employing traditional prompt
generation approaches that utilize generative models to craft a new prompt for
each sample, leading to extensive prompt search space. The process turns into
cost-prohibitive with multiple iterations of querying LLMs using these new
prompts. To significantly lower the cost of prompting, we suggest replacing
the generative model with a prompt evaluator. This evaluator can assign a
score to a tuple $(q,c,p)$, indicating the fitness of the prompt $p$ for a
question-context input. We then iterate over a fixed representative prompt
database to choose the prompt with the highest score given by the evaluator.
In the next sections, we will detail 3 steps of our approach: prompt database
generation, prompt evaluator training, and prompt ranking (see Figure 1).

###  3.2 Prompt Database Generation

We argue that similar inputs (question-context pairs) benefit equally from the
same prompt. This is because similar inputs share a common meaning represented
in the form of tokens. We therefore create a prompt database used for matching
with the inputs. The database generation consists of two steps: clustering and
meta-prompt generation.

#### Clustering

The first step is to assign the training data $\mathcal{D}_{train}$ into
different coherent groups (clusters), expecting that inputs from the same
group can share the same prompt. Specifically, we use Sentence-Transformer
Reimers and Gurevych (2019) to encode the concatenations of the input
questions and the corresponding contexts which are then fed into $K$-Means
clustering algorithm MacQueen et al. (1967) to calculate the clusters.

#### Prompt generation

Once clusters have been formed, the second step is to generate prompts for
each cluster. The generation follows the generative approach of APE (Automatic
Prompt Engineer) Zhou et al. (2022). Specifically, we create a meta-prompt
consisting of a few question-context-answer tuples from each cluster $(q,c,a)$
as demonstrative examples and an instruction to ask an additional LLM
$\mathtt{A}_{1}$ to generate candidate prompts. We conduct a basic exact match
checking to eliminate duplicate prompts, ensuring that the prompt database
consists of distinct entries. Compared to manual prompts from humans with
limited patterns, this approach provides more freedom to creatively produce
diverse candidate prompts. The union of all generated prompts forms the prompt
database. We can control the size of the prompt database by specifying
hyperparameters such as $c$\- the number of clusters, and $n_{p}$\- the number
of generated prompts per cluster. The prompt database generation process is
summarized in Algorithm 1.

Algorithm 1 Prompt database generation.

1:Training data $\mathcal{D}_{train}$, clustering algorithm $C$, LLM-based
prompt generator $\mathtt{A}_{1}$, hyperparameters $c$ and $n_{p}$.

2:Initialize the prompt database $\mathcal{P}=\emptyset$

3:Group the training data into $c$ clusters
$\mathcal{G}_{1},\mathcal{G}_{2},..,\mathcal{G}_{c}=C(\mathcal{D}_{train})$

4:for $\mathcal{G}$ in $\mathcal{G}_{1},\mathcal{G}_{2},..,\mathcal{G}_{c}$ do

5: Randomly construct a set of demonstrations
$\mathcal{D}_{demo}\subset\mathcal{G}$ to build meta-prompt $p_{meta}$

6: Generate prompts $\mathcal{P}^{\prime}=\mathtt{A}_{1}(p_{meta},n_{p})$

7: $\mathcal{P}\leftarrow\mathcal{P}\cup\mathcal{P}^{\prime}$

8:end for

9:return Prompt database $\mathcal{P}$

###  3.3 Prompt Evaluator Training

Our objective is to develop a model capable of evaluating the relevance of a
prompt by assigning a corresponding score to it. The model called prompt
evaluator ($\mathtt{E}$), receives input question $q$, a context text $c$, and
a prompt $p$ to produce a score that gauges the relevance of the prompt to the
input.

$s=\mathtt{E}_{\theta}(q,c,p)$ (2)

To find the parameter $\theta$ of the prompt evaluator, we adopt a preference
learning scheme by preparing a comparison dataset Christiano et al. (2017).
With this setting, we can still estimate the score for each prompt following
the Bradley-Terry model without requiring the exact score labels Bradley and
Terry (1952). The training process is done in two steps: data collection and
evaluator training.

#### Data collection

The first step of training the evaluator is to collect training samples. To do
that, given a separate question-context pair $(q,c)$ and the correct answer
$a$ belonging to a group $\mathcal{G}$, we partition the set of prompts of
that group $\mathcal{P}_{\mathcal{G}}$ into two subsets called good prompts
($\mathcal{P}_{q,c}^{good}$) and bad prompts ($\mathcal{P}_{q,c}^{bad}$). A
good prompt is a prompt, combined with the input question and its context,
that can be fed into an LLM $\mathtt{A}_{2}$ to output an answer that is very
similar to the correct answer $a$ in terms of meaning. On the other hand, a
bad prompt tends to make the LLM $\mathtt{A}_{2}$ to produce a different
answer compared to the correct answer $a$. The collection of good and bad
prompts is shown as follows.

$\centering\mathcal{P}_{q,c}^{good}=\\{f(\mathtt{A}_{2}(q,c,p),a)\geq\lambda,\forall
p\in\mathcal{P}_{\mathcal{G}}\\}\@add@centering$ (3)
$\mathcal{P}_{q,c}^{bad}=\\{f(\mathtt{A}_{2}(q,c,p),a)<\lambda,\forall
p\in\mathcal{P}_{\mathcal{G}}\\}$ (4)

where $\lambda=(\max f-\min f)/2$ is a decision threshold. Notably, we only
collect the good and bad prompts for only $m$ closest question-context pairs
to the centroid of each cluster to ignore unrepresentative inputs and ensure a
manageable synthetic data size. We note that the data collection is done
automatically without human evaluation.

#### Evaluator training

Once the two distinct prompt sets have been created, we form all possible bi-
partite combinations as the training data for the prompt evaluator. With each
sample $(q,c)$ with the correct answer $a$, the evaluator samples a good
prompt $p_{good}$ and a bad prompt $p_{bad}$ so that the tuple of
$(q,c,p_{good})$ can output an answer $a^{\prime}$ that approximates the
correct answer $a$ and the tuple of $(q,c,p_{bad})$ outputs a different answer
compared to the correct answer $a$. In this sense, $\mathtt{E}()$ returns a
high score if it receives a good prompt while outputting a low score with a
bad prompt. By doing that, we force the evaluator to select a good prompt
rather than a bad prompt. The prompt evaluator $\mathtt{E}$ is trained by
minimizing the preference loss:

$\mathcal{L}=-\sum_{\mathcal{P}_{q,c}^{good}}\sum_{\mathcal{P}_{q,c}^{bad}}\log(\mathtt{E}_{\theta}(q,c,p_{good})-\mathtt{E}_{\theta}(q,c,p_{bad})+\epsilon)$
(5)

With the margin $\epsilon$, we can control the minimum distance between a
correct input and an incorrect one to reduce noisy model predictions.

###  3.4 Prompt Ranking

At test time, given a new input $(q^{\prime},c^{\prime})$, we use the prompt
evaluator $\mathtt{E}$ to calculate the score for all candidate prompts in the
prompt database $\mathcal{P}$ when pairing them with the input. Finally, the
selected prompt $p^{*}$ is the one with the highest score. Hence, the prompt
generator can be formulated as:

$p^{*}=\mathtt{G}(q^{\prime},c^{\prime})=\arg\max_{p\in\mathcal{P}}\mathtt{E}_{\theta}(q^{\prime},c^{\prime},p)$
(6)

A notable benefit of our approach is the ability to rank all prompts in the
databases and choose the top-$k$ best prompts. These prompts can produce
varied responses, and we can utilize voting mechanisms to ascertain the most
common outputs generated by the majority of the prompts:

$a^{\prime}=\mathtt{Mode}(\\{\mathtt{M}(q,c,p^{*}_{i}),\forall i=1\ldots
k\\})$ (7)

where $\\{p^{*}_{i}\\}_{i=1}^{k}$ denotes prompts with the top-$k$ scores
defined in Eq. (6). The voting mechanism acts as a safeguard against potential
biases or outliers associated with specific prompts, ensuring a more balanced
and accurate result.

##  4 Experimental Setup

###  4.1 Datasets

We examine the proposed method on challenging question-answering datasets that
necessitate non-trivial prompts. Specifically, we concentrate on arithmetic
problems because of their intricate reasoning processes. Unlike typical
retrieval question-answering scenarios, extractive approaches cannot be
employed to solve arithmetic questions. We used three benchmark datasets for
evaluation. Table 1 summarizes datasets’ information.

#### GSM8K

consists of 8.5K high-quality linguistically diverse grade school math word
problems created by human problem writers Karl Cobbe et al. (2021). The
dataset is segmented into 7.5K training and 1K test problems. These problems
require between 2 and 8 steps to solve, and solutions primarily involve
performing a sequence of elementary calculations using basic arithmetic
operations $\pm\times\div$ to reach the final answer.

#### MultiArith

Roy and Roth (2016) is the subset of the Mawps repository Rik Koncel-
Kedziorski and Hajishirzi (2016). This dataset is a collection of mathematical
problems that are specifically designed to test the ability of machine
learning models to perform complex arithmetic operations and reasoning. These
problems demand the application of multiple arithmetic operations and logical
reasoning to be successfully solved.

#### AQuA

consists of more than 100,000 algebraic word problems that include both
answers and natural language rationales Wang Ling and Blunsom (2017). Unlike
other datasets, here, each data sample contains four parts: question, options
(context), rationale, and the correct option. We measure accuracy on the
correct option, and only use the rationale for the clustering step.

Table 1: Three QA arithmetic datasets. FF and MC mean free form and multiple choice, respectively. Dataset | Train | Test | Answer type
---|---|---|---
GSM8K | 7473 | 1319 | FF
MultiArith | 420 | 180 | FF
AQuA | 97467 | 254 | MC

###  4.2 LLM Models

We used the GPT-3.5-turbo model for both the prompt generator
$\mathtt{A}_{1}$, the data synthesizer $\mathtt{A}_{2}$, and the downstream
task solver $\mathtt{M}$. To maintain consistent and replicable results, we
created and used only one API version and model deployment name. The model
name is gpt-3.5-turbo-0613 with the version of 2023-05-15. We set the
temperature as 0.0 to restrict the randomness of GPT when decoding. The top
$p$ parameter is set as 1.0 and the maximum number of tokens is 1000.

For the prompt evaluator $\mathtt{E}$, we used the common facebook/opt-125m
model, a decoder-only pre-trained Transformer language model Susan Zhang
(2022). To adapt this model with preference learning, we changed the last
layer to output a scalar score. The training setup is facilitated by the
Hugging Face Transformers library. We opt for this model due to its commonly
used lightweight design for handling text inputs.

We used the following hyperparameters for training the prompt evaluator
$\mathtt{E}$. We used AdamW optimizer with $\beta_{1}=0.9$ and
$\beta_{2}=0.95$. The training process uses the weight decay of 0.1 and the
batch size of 16. The model was trained in 30 epochs.

###  4.3 Baselines

We compare our APS approach with other strong prompt optimization methods. To
ensure fairness, we choose methods that use similar-sized downstream LLM
$\mathtt{M}$, in particular those that have hundreds of billions of parameters
(e.g., Chat-GPT3). In particular, in No Prompt, we directly ask the LLM
$\mathtt{M}$ to answer the question with only provided context but not any
instructions or prompts. This is the simplest form of the question-answering
task that helps us to prove the importance of a prompt to an LLM in later
baselines. Fixed Prompt is the basic setting of our proposed method. It uses
one prompt for all samples in test sets. We chose this single prompt as the
one with the highest accuracy tested on training sets. This baseline is to
verify the necessity of per-sample prompts if they surpass this single fixed
prompt. Naive Prompt represents a naive approach in prompt generation where we
simply ask Chat-GPT3.5 to generate the prompt for the current input. Auto CoT
Zhang et al. (2022b) is an upgraded chain-of-thought prompting technique
employing clustering to build demonstration examples. OPRO (Optimization by
PROmpting) Yang et al. (2023) is a strong method for prompt creation. It
collects the past generated prompts and their accuracy as history and asks the
generator LLM $\mathtt{A}_{1}$ to generate a new prompt with a higher
accuracy. At testing time, the prompt with the highest score in the history in
the training phase is selected and applied to all testing samples. This is an
advanced version of the fixed prompt where we conditionally generate new
prompts with probably higher accuracies other than the unconditional
generation in the previous baseline. APE Zhou et al. (2022) leverages input-
output data to instruct the LLM $\mathtt{A}_{1}$ to generate prompts and
assess them based on the downstream LLM’s performance. The found prompt is
then used for all inputs during testing time. This baseline is closely related
to our approach and can considered as part of our APS. To make the baseline
more robust, we create another variant of APE named APE (voting) by asking APE
to find 5 prompts to solve the task and do voting similarly to Eq. (6).

Table 2: APS with and without voting. Method | GSM8K | MultiArith | AQuA
---|---|---|---
APS (no voting) | 79.14 | 99.45 | 63.78
APS ( top-3 voting) | 80.88 | 99.45 | 61.81
APS (top-5 voting) | 81.49 | 100 | 64.57
APS (top-10 voting) | 81.49 | 100 | 61.81
Table 3: APS with and without clustering in both voting and no voting settings. Cluster | Vote | GSM8K | MultiArith | AQuA
---|---|---|---|---
✗ | ✗ | 75.64 | 97.70 | 59.45
✗ | ✔ | 78.53 | 99.45 | 58.66
✔ | ✗ | 79.14 | 99.45 | 63.78
✔ | ✔ | 81.49 | 100 | 64.57
Table 4: Hyperparameter sensitivity test. $c$/$n_{p}$ | GSM8K | MultiArith | AQuA
---|---|---|---
10/3 | 81.49 | 100 | 64.57
10/5 | 81.49 | 100 | 64.57
20/3 | 81.56 | 100 | 64.96
20/5 | 81.63 | 100 | 65.35
Table 5: Case study from AQUA dataset: Prompts that have higher scores and from the same cluster as the input tend to be better and achieve better accuracy. The actual answers are much longer. We only show the extracted final output (bold). |  Question: Of the 200 students in a school, at least 45% attended the prom night and at least 35% took part in the debating session.
---
What is the maximum number of students who could have neither attended the
prom night nor the debating session?
Options: [’A)27’, ’B)81’, ’C)90’, ’D)99’, ’E)110’]
Correct answer: E |  |
Prompt | Answer | Score
Good prompt (same cluster): Given a mathematical question, the AI should follow these steps to solve it: 1\. Read and understand the question thoroughly. 2\. Identify the relevant mathematical concepts required to solve the problem. 3\. Organize the given information and identify the unknown variable. 4\. Use the relevant mathematical formulae to form an equation or system of equations. 5\. Solve the equation(s) to obtain the value of the unknown variable. 6\. Verify the solution by checking if it satisfies the given conditions. 7\. If the solution is not correct, recheck the steps and calculations and identify any errors. 8\. If no errors are found, check for any omitted or extraneous solutions. 9\. Present the answer in the required format, such as a fraction or decimal. 10\. Double-check the answer for any errors or mistakes. The AI should follow these steps and provide the answer to the given mathematical problem. |  … E)110 | 0.98
Bad prompt (different cluster): Imagine you are a math teacher and the AI is your student. Your task is to guide the AI to solve the given mathematical problem. Begin by highlighting the variables in the problem and their relationships. Then, define the formula or equation that suits the problem and apply it to solve for the unknown variable. Finally, double-check the solution by verifying it with the provided options. Remember, the AI has basic knowledge of mathematical operations, so explain every step in plain English. Output the complete guideline for the AI to solve the mathematical problem. |  … None. | 0.05

###  4.4 Key Hyperparameters

There are several hyperparameters specific to our methods. Specifically,
throughout our experiments, we used a fixed number of clusters ($c=10$),
prompts per cluster ($n_{p}=3$), number of demonstrations per meta-prompt
($|\mathcal{D}_{demo}|=10$), number of examples per cluster in synthesizing
data ($m=10$), number of top-$k$ voting ($k=5$). We determined that these
values strike the optimal balance between performance and training cost. As a
result, for each dataset, we had 30 prompts in the prompt database and 3000
synthetic data samples for training the prompt evaluator. A detailed ablation
study and hyperparameter analysis is shown in Section 5.2.

###  4.5 The cost of training APS

Training APS requires $\mathcal{O}(|\mathcal{P}|+c\times
m\times|\mathcal{P}|)$ API call to GPT-3.5, where: $|\mathcal{P}|$ is the
prompt database size, $c$ is the number of clusters and $m$ is the number of
examples per cluster that are closest to the cluster center.

In total, prompt and synthetic data generation steps cost between $\$5-10$ for
30 prompts in the prompt database and 3000 synthetic data samples. The total
financial cost for all the experiments is $\approx\$30$. Also, it costs
$\approx\$10$ for evaluation on all the test sets.

Table 6: QA accuracy on math reasoning datasets. ${\dagger}$ denotes results reported in the original papers while $\diamondsuit$ indicates results run by our machines using the same setup as our method. Method | GSM8K | MultiArith | AQuA
---|---|---|---
No Prompt♢ | 74.60 | 98.89 | 58.26
Fixed Prompt♢ | 78.45 | 97.22 | 59.45
Naive Prompt♢ | 58.76 | 90.00 | 56.59
Auto CoT† | 62.8 | 93.20 | 36.50
OPRO† | 80.20 | 95.30 | 54.30
APE♢ | 76.02 | 98.33 | 61.81
APE (voting)♢ | 77.61 | 99.45 | 61.14
APS (Our) | 81.49 | 100 | 64.57

##  5 Results and Discussion

In this section, we first present a comparison between our method APS and
other baselines. We then conduct an ablation study to assess the contribution
of each component and the impact of hyperparameters in the model. Finally, we
offer several case studies illustrating the behavior of APS.

###  5.1 Effectiveness of Automatic Prompt Selection (APS)

Table 6 summarizes the performance comparison in terms of accuracy. The
proposed APS method surpasses all other baselines with a significant gap. APS
performs better of $1.28\%$ than the second-best baseline on GSM8K, $0.55\%$
on MultiArith, and $2.76\%$ on AQuA. To our knowledge, AQuA is the most
difficult benchmark with more complex questions when most of them are taken
from GMAT (Graduate Management Admission Test) and GRE (General Test) compared
to questions using basic arithmetic operation questions $\pm\times\div$ like
MultiArith and GSM8K data. Therefore, the optimized prompts contribute a more
significant role with a bigger gap on this dataset. Compared to the stronger
APE with voting, our method shows an improvement of approximately $4\%$ on
GSM8K, $0.5\%$ on MultiArith, and $3\%$ on AquaA thanks to our additional
components like cluster-based generation and the prompt evaluator. Compared to
another LLM-based prompting approach called OPRO, our APS creates even a
larger gap on MultiArith and AQuA due to the per-sample advantage of
leveraging a prompt evaluator. On the other hand, while AutoCoT and Naive
Prompt generate prompts for each sample, these methods perform significantly
behind other baselines, including No Prompt. We hypothesize that without
appropriate optimization, per-sample prompting is unstable and may impede
downstream performance. This underscores the significance of our approach in
introducing a stable procedure through the use of a prompt evaluator.

###  5.2 Ablation Study

In this section, we investigate the role of the voting mechanism and the
importance of the clustering step in our approach. We also examine the
performance of our method when varying important hyperparameters such as the
number of clusters $c$ and the number of prompts per cluster $n_{p}$.

#### The role of voting

As mentioned in Section 3.4, the prompt evaluator allows us to extract the
list of prompts with the highest scores for a given input question-context
pair. In this experiment, we investigate the actual performance gap between
using a voting mechanism and not using it. According to Table 2, the best
setting top-5 voting shows consistent improvement of approximately $2\%$ on
GSM8K against no-voting, $0.5\%$ on MultiArith, and $1\%$ on AQuA.
Interestingly, the choice of voting numbers has to be selected carefully to
lead to the best performance. Specifically, in a challenging dataset like
AQuA, both the selection of top-3 and top-10 lead to the same suboptimal
performance even lower than the no-voting setting. Using too few votes limits
the potential diversity of the voting models while using too many votes can
introduce noises from other less certain predictions.

#### The importance of generating the cluster-based prompt database

According to Table 3, the generated cluster-based prompt database always
performs better than not using clustering information. Specifically, when not
using voting, the performance of the cluster-based approach is lower than that
of using voting as nearly $4\%$ gap on GSM8K, $2\%$ on MultiArith, and $5\%$
on AQuA. Similarly, when both approaches use a voting mechanism, the cluster-
based approach still performs better than the non-cluster one around $3\%$ on
GSM8K, $0.5\%$ on MultiArith, and $5\%$ on AQuA. As presented in Section 3.2,
similar inputs should share the same prompt, and different inputs should be
paired with different prompts. Therefore, our proposed cluster-based prompt
generation plays a very important role in the whole APS architecture.

#### Hyperparameter sensitivity of $c$ and $n_{p}$

We tried different combinations of the number of clusters $c$ and the number
of prompts $n_{p}$ and report the results in Table 4. Overall, the results
show that increasing the number of clusters and generating more prompts per
cluster are beneficial for improving performance. We hypothesize that this
enables a more diverse prompt database and thus increases the robustness of
the approach. However, due to the significant high cost of increasing $c$ and
$n_{p}$ in exchange for a small gain, we selected $c=10$ and $n_{p}=3$ across
all other experiments.

###  5.3 Case Study

In this section, we analyze the quality of our prompt generation for one
question from AQUA dataset (see Table 5). The question involves complex
algebra, necessitating multiple reasoning steps, unlike general questions
answerable by LLMs using "role-playing" prompts. Our prompt evaluator selects
a prompt with the highest score of $0.98$ (a good prompt) for this specific
question. As anticipated, the chosen prompt aligns with the cluster associated
with the input question, offering a detailed and sophisticated step-by-step
guideline for the LLM to produce the correct answer. For comparison, we choose
a low-score (bad) prompt with a score of $0.05$, which is a "role-playing"
type prompt belonging to a different cluster. Consequently, it is unsuitable
for the question, leading to an incorrect answer.

##  6 Conclusion

In this paper, we have presented Automatic Prompt Selection (APS), a novel
method to automate prompting for Large Language Models (LLMs). Our method
marries prompt generation and prompt ranking. It reduces the prompt search
space by grouping similar inputs into clusters and generating prompts for each
cluster. It then trains a prompt evaluator to score the prompts based on their
ability to guide the LLM to produce outputs that match the correct answers.
Experimental results on three benchmark QA datasets show two important points.
First, the proposed method can select appropriate prompts for different
inputs. Second, the method achieves competitive performance in the zero-shot
setting of the QA task on GSM8K, MultiArith, and AQuA datasets. As future
work, we plan to extend our method to few-shot in-context learning and apply
it to various NLP tasks.

## Limitations

Given the automated generation of the prompt database, ensuring the quality of
candidate prompts can be tricky. Notably, issues such as prompt duplication
may arise despite our efforts to eliminate exact matches. Semantically
equivalent prompts with minor token variations may persist, diminishing both
the prompt database’s diversity and our approach’s flexibility. To mitigate
this, a potential solution involves assessing the semantic similarity between
prompts and retaining only those that exhibit distinctiveness. In addition,
implementing our approach involves several steps and introduces additional
hyperparameters, a process that may be time-consuming during tuning. While we
have diligently tuned these parameters and verified their effectiveness on the
datasets under examination, we recommend practitioners explore varying
hyperparameter values to optimize results for their specific tasks.

## Ethics Statement

All datasets and baseline models experimented in this work have no unethical
applications or risky broader impacts. The evaluation uses public datasets
that are widely used for mathematical QA reasoning. It does not include any
confidential or personal information of workers or companies. The baseline
methods used for evaluation can be publicly accessed with GitHub links. There
is no bias for the re-implementation that can affect the final results. The
primary objective of our work is to automate the prompt engineering task for
Large Language Models (LLMs), aspiring to enhance the practical application of
LLMs. Our intentions are sincere, and we do not foresee immediate adverse
consequences. Nevertheless, we acknowledge the potential pitfalls should our
method be employed to augment large language models, leading to the generation
of hallucinated or negative content. Such issues are common in prompt
generation approaches, and we are committed to proactively addressing and
preventing these concerns to the best of our ability.

## References

  * Bradley and Terry (1952) Ralph Allan Bradley and Milton E Terry. 1952.  Rank analysis of incomplete block designs: I. the method of paired comparisons.  _Biometrika_ , 39(3/4):324–345.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901.
  * Christiano et al. (2017) Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. 2017.  Deep reinforcement learning from human preferences.  _Advances in neural information processing systems_ , 30.
  * Deng et al. (2022) Mingkai Deng, Jianyu Wang, Cheng-Ping Hsieh, Yihan Wang, Han Guo, Tianmin Shu, Meng Song, Eric Xing, and Zhiting Hu. 2022.  Rlprompt: Optimizing discrete text prompts with reinforcement learning.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 3369–3391.
  * Gao et al. (2021) Tianyu Gao, Adam Fisch, and Danqi Chen. 2021.  Making pre-trained language models better few-shot learners.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 3816–3830.
  * Karl Cobbe et al. (2021) Mohammad Bavarian Mark Chen Heewoo Jun Lukasz Kaiser Matthias Plappert Jerry Tworek Jacob Hilton Reiichiro Nakano Karl Cobbe, Vineet Kosaraju et al. 2021.  Training verifiers to solve math word problems.  _arXiv preprint arXiv:2110.14168_.
  * Liao et al. (2022) Chonghua Liao, Yanan Zheng, and Zhilin Yang. 2022.  Zero-label prompt selection.  _arXiv preprint arXiv:2211.04668_.
  * Lu et al. (2022) Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp. 2022\.  Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 8086–8098.
  * Lyu et al. (2023) Hanjia Lyu, Song Jiang, Hanqing Zeng, Yinglong Xia, and Jiebo Luo. 2023.  Llm-rec: Personalized recommendation via prompting large language models.  _arXiv preprint arXiv:2307.15780_.
  * MacQueen et al. (1967) James MacQueen et al. 1967.  Some methods for classification and analysis of multivariate observations.  In _Proceedings of the fifth Berkeley symposium on mathematical statistics and probability_ , volume 1, pages 281–297. Oakland, CA, USA.
  * Nguyen et al. (2023) Minh-Tien Nguyen, Duy-Hung Nguyen, Shahab Sabahi, Hung Le, Jeff Yang, and Hajime Hotta. 2023.  When giant language brains just aren’t enough! domain pizzazz with knowledge sparkle dust.  _arXiv preprint arXiv:2305.07230_.
  * Pang et al. (2023) Bo Pang, Semih Yavuz, Caiming Xiong, and Yingbo Zhou. 2023.  SharPT: Shared latent space prompt tuning.  In _Findings of the Association for Computational Linguistics: EACL 2023_ , pages 1244–1250, Dubrovnik, Croatia. Association for Computational Linguistics.
  * Prasad et al. (2023) Archiki Prasad, Peter Hase, Xiang Zhou, and Mohit Bansal. 2023.  Grips: Gradient-free, edit-based instruction search for prompting large language models.  In _Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics_ , pages 3827–3846.
  * Qin and Eisner (2021) Guanghui Qin and Jason Eisner. 2021.  Learning how to ask: Querying lms with mixtures of soft prompts.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 5203–5212.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-bert: Sentence embeddings using siamese bert-networks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics.
  * Reynolds and McDonell (2021) Laria Reynolds and Kyle McDonell. 2021.  Prompt programming for large language models: Beyond the few-shot paradigm.  In _Extended Abstracts of the 2021 CHI Conference on Human Factors in Computing Systems_ , pages 1–7.
  * Rik Koncel-Kedziorski and Hajishirzi (2016) Aida Amini Nate Kushman Rik Koncel-Kedziorski, Subhro Roy and Hannaneh Hajishirzi. 2016.  Mawps: A math word problem repository.  In _Proceedings of the 2016 conference of the north american chapter of the association for computational linguistics: human language technologies)_ , pages 1152––1157.
  * Roy and Roth (2016) Subhro Roy and Dan Roth. 2016.  Solving general arithmetic word problems.  _arXiv preprint arXiv:1608.01413_.
  * Singh et al. (2022) Chandan Singh, John X Morris, Jyoti Aneja, Alexander M Rush, and Jianfeng Gao. 2022\.  Explaining patterns in data with language models via interpretable autoprompting.  _arXiv preprint arXiv:2210.01848_.
  * Sorensen et al. (2022) Taylor Sorensen, Joshua Robinson, Christopher Rytting, Alexander Shaw, Kyle Rogers, Alexia Delorey, Mahmoud Khalil, Nancy Fulda, and David Wingate. 2022.  An information-theoretic approach to prompt engineering without ground truth labels.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 819–862.
  * Srivastava et al. (2023) Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, et al. 2023.  Beyond the imitation game: Quantifying and extrapolating the capabilities of language models.  _Transactions on Machine Learning Research_.
  * Susan Zhang (2022) Naman Goyal Mikel Artetxe Moya Chen Shuohui Chen Christopher Dewan Mona Diab Xian Li Xi Victoria Lin Todor Mihaylov Myle Ott Sam Shleifer Kurt Shuster Daniel Simig Punit Singh Koura Anjali Sridhar Tianlu Wang Luke Zettlemoyer Susan Zhang, Stephen Roller. 2022.  Opt: Open pre-trained transformer language models.  _arXiv preprint arXiv:1608.01413_.
  * Wang Ling and Blunsom (2017) Chris Dyer Wang Ling, Dani Yogatama and Phil Blunsom. 2017.  Program induction by rationale generation: Learning to solve and explain algebraic word problems.  _arXiv preprint arXiv:1705.04146_.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. 2022.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in Neural Information Processing Systems_ , 35:24824–24837.
  * White et al. (2023) Jules White, Quchen Fu, Sam Hays, Michael Sandborn, Carlos Olea, Henry Gilbert, Ashraf Elnashar, Jesse Spencer-Smith, and Douglas C Schmidt. 2023.  A prompt pattern catalog to enhance prompt engineering with chatgpt.  _arXiv preprint arXiv:2302.11382_.
  * Yang et al. (2023) Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V Le, Denny Zhou, and Xinyun Chen. 2023.  Large language models as optimizers.  _arXiv preprint arXiv:2309.03409_.
  * Yao et al. (2022) Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R Narasimhan, and Yuan Cao. 2022.  React: Synergizing reasoning and acting in language models.  In _The Eleventh International Conference on Learning Representations_.
  * Zhang et al. (2022a) Tianjun Zhang, Xuezhi Wang, Denny Zhou, Dale Schuurmans, and Joseph E Gonzalez. 2022a.  Tempera: Test-time prompt editing via reinforcement learning.  In _The Eleventh International Conference on Learning Representations_.
  * Zhang et al. (2022b) Zhuosheng Zhang, Aston Zhang, Mu Li, and Alex Smola. 2022b.  Automatic chain of thought prompting in large language models.  In _The Eleventh International Conference on Learning Representations_.
  * Zhou et al. (2022) Yongchao Zhou, Andrei Ioan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy Ba. 2022.  Large language models are human-level prompt engineers.  In _The Eleventh International Conference on Learning Representations_.


BR^{f}(z_{1:T},\tilde{\sigma}_{1:t-1}^{l},\sigma_{t}^{l,i},\tilde{\sigma}_{t}^{l,-i},\tilde{\sigma}_{t+1:T}^{l},\hat{\sigma}^{m})$
(115) $\displaystyle\hat{\sigma}^{m}$ $\displaystyle\in
BR^{f}(z_{1:T},\tilde{\sigma}_{1:t-1}^{l},\sigma_{t}^{l,i},\tilde{\sigma}_{t}^{l,-i},\tilde{\sigma}_{t+1:T}^{l},\hat{\sigma}^{m},\hat{\sigma}^{f})$
(116)

where we assume that $\hat{\sigma}^{f},\hat{\sigma}^{m}$ are of type $m$
(Since if they are not, one can find an equivalent policies of type $m$ that
achieve same reward profile, as shown in Appendix B). Let

$\displaystyle\hat{\gamma}_{t}^{f}$
$\displaystyle\in\bar{BR}_{t}^{f}(\pi_{t},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m})$
(117) $\displaystyle\hat{\gamma}_{t}^{m}$
$\displaystyle\in\bar{BR}_{t}^{m}(\pi_{t},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},\hat{\gamma}_{t}^{f})$
(118)

where
$\gamma_{t}^{l,i}=\sigma_{t}^{l,i}(\cdot|a_{1:t-1}^{l,m},z_{1:t},x_{1:t-1}^{l,i},\cdot)$.
Then $\forall a_{1:t-1},x_{1:t-1}^{f},x_{1:t-1}^{m,j},x_{1:t-1}^{l,i}$, and
for every $\hat{\gamma}_{t}^{f},\hat{\gamma}_{t}^{m}$ that satisfy (117),
(118) $\exists(\hat{\sigma}_{t}^{f},\hat{\sigma}_{t}^{m})$ that satisfy (115)
(116) such that

$\displaystyle\hat{\gamma}_{t}^{f}$
$\displaystyle=\hat{\sigma}_{t}^{f}(\cdot|z_{1:t},a_{1:t-1},\cdot)$ (119)
$\displaystyle\hat{\gamma}_{t}^{m,j}$
$\displaystyle=\hat{\sigma}_{t}^{m,j}(\cdot|z_{1:t},a^{l,m}_{1:t-1},\cdot)$
(120)

where,

$\displaystyle
BR^{f}(z_{1:T},\sigma^{l},\sigma^{m}):=\bigcap_{t}\bigcap_{a_{1:t-1}^{l,m}}\bigcap_{x_{1:t}^{f}}\arg\max_{\sigma^{f}}\mathbb{E}^{\sigma_{t:T}^{l,m},{\sigma}_{t:T}^{f},\underline{\pi_{t}}}[\sum_{n=t}^{T}\delta^{n-t}R^{f}(Z_{n},X_{n},A_{n})|z_{1:t},a_{1:t-1}^{l,m},x_{1:t}^{f}]$
(121) $\displaystyle
BR_{t}^{m,j}(\underline{\pi_{t}},z_{1:t},a_{1:t-1}^{l,m},x_{1:t}^{m,j},\sigma_{t:T}^{l},\sigma_{t:T}^{m,-j},\sigma_{t:T}^{f})$
$\displaystyle:=\arg\max_{\sigma^{m,j}}\mathbb{E}^{\sigma_{t:T}^{l}\sigma_{t:T}^{m,j}\sigma_{t:T}^{m,-j},\sigma_{t:T}^{f},\underline{\pi_{t}}}\big{\\{}\sum_{n=t}^{T}\delta^{n-t}R_{n}^{m,j}(Z_{n},X_{n}^{l,m},A_{n}^{l,m})|\underline{\pi_{t}},z_{1:t},a_{1:t-1}^{l,m},x_{1:t}^{m,j}\big{\\}}$
(122) $\displaystyle
BR^{m,j}(z,\sigma^{l},\sigma^{m,-j},\sigma^{f}):=\bigcap_{t}\bigcap_{a_{1:t-1}^{m,j}}\bigcap_{x_{1:t}^{m,j}}BR_{t}^{m,j}(\underline{\pi_{t}},z_{1:t},a_{1:t-1}^{l,m},x_{1:t}^{m,j},\sigma_{t:T}^{l},\sigma_{t:T}^{m,-j},\sigma_{t:T}^{f}).$
(123)

where

$\displaystyle\pi_{t}(\cdot)=P^{\tilde{\sigma}_{1:t-1}^{l,m,f}}(\cdot|z_{1:t},a_{1:t-1}).$
(124)
$\displaystyle\bar{BR}_{t}^{f}(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,m}):=\big{\\{}\tilde{\gamma}_{t}^{f}:\forall
x_{t}^{f}\in\mathcal{X}^{f},\tilde{\gamma}_{t}^{f}(\cdot|x_{t}^{f})\in\arg\max_{\gamma^{f}_{t}(\cdot|x_{t}^{f})}\mathbb{E}^{\gamma^{f}_{t}(\cdot|x_{t}^{f}){\gamma}^{l,m}_{t},\,z_{t},\underline{\pi_{t}}}$
$\displaystyle\big{\\{}R_{t}^{f}(z_{t},X_{t},A_{t})+\delta
V_{t+1}^{f}(\underline{F}(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,m},A^{l,m}_{t}),\phi(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,m},\tilde{\gamma}^{f}_{t}),X^{f}_{t+1})\big{\lvert}\underline{\pi_{t}},z_{t},x_{t}^{f}\big{\\}}\big{\\}},$
(125)
$\displaystyle\bar{BR}_{t}^{m,j}(\underline{\pi_{t}},z_{t},\gamma_{t}^{l},\gamma_{t}^{m,-j},\gamma_{t}^{f}):=\big{\\{}\tilde{\gamma}_{t}^{m,j}:\forall
x_{t}^{m,j}\in\mathcal{X}^{m,j},\tilde{\gamma}_{t}^{m,j}(\cdot|x_{t}^{m,j})\in\arg\max_{\gamma^{m,j}_{t}(\cdot|x_{t}^{m,j})}\mathbb{E}^{\gamma^{m,j}_{t}(\cdot|x_{t}^{m,j}){\gamma}^{l}_{t},\gamma_{t}^{m,-j},\gamma_{t}^{f},\,z_{t},\underline{\pi_{t}}}$
$\displaystyle\big{\\{}R_{t}^{f}(z_{t},X^{l,m,f}_{t},A_{t})+\delta
V_{t+1}^{f}(\underline{F}(\underline{\pi_{t}},z_{t},\gamma_{t}^{l},\tilde{\gamma}_{t}^{m,j},\gamma_{t}^{m,-j},A^{l,m}_{t}),\phi(\underline{\pi_{t}},z_{t},\gamma_{t}^{l},\tilde{\gamma}_{t}^{m,j},\gamma_{t}^{m,-j},{\gamma}^{f}_{t}),X^{f}_{t+1})\big{\lvert}\underline{\pi_{t}},z_{t},x_{t}^{f}\big{\\}}\big{\\}},$
(126)

and

$\displaystyle\pi_{t}(\cdot)=P^{\tilde{\sigma}_{1:t-1}^{l},\hat{\sigma}_{1:t-1}^{m},\hat{\sigma}_{1:t-1}^{f}}(\cdot|z_{1:t},a_{1:t-1}).$
(127)

###### Proof:

Part 1: Minor Follower

$\displaystyle\mathbb{E}^{\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},\hat{\gamma}^{f}_{t}(\cdot|x_{t}^{f}),\,\pi_{t}}\big{\\{}R_{t}^{f}(Z_{t},X_{t},A_{t})+$
$\displaystyle\delta
V_{t+1}^{f}(\underline{F}(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},A^{l,m}_{t}),\phi(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},\hat{\gamma}^{f}_{t}),X^{f}_{t+1})\big{\lvert}\underline{\pi_{t}},z_{t},x_{t}^{f}\big{\\}}\big{\\}}$
$\displaystyle=\max_{\gamma^{f}_{t}(\cdot|x_{t}^{f})}\mathbb{E}^{\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},{\gamma}^{f}_{t}(\cdot|x_{t}^{f}),\,\pi_{t}}\big{\\{}R_{t}^{f}(Z_{t},X_{t},A_{t})+$
$\displaystyle\delta
V_{t+1}^{f}(\underline{F}(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},A^{l,m}_{t}),\phi(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},\hat{\gamma}^{f}_{t}),X^{f}_{t+1})\big{\lvert}\underline{\pi_{t}},z_{t},x_{t}^{f}\big{\\}}\big{\\}}$
(128a)
$\displaystyle=\max_{\gamma^{f}_{t}(\cdot|x_{t}^{f})}\mathbb{E}^{\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},{\gamma}^{f}_{t}(\cdot|x_{t}^{f})\,\pi_{t}}\big{\\{}R_{t}^{f}(Z_{t},X_{t},A_{t})+\mathbb{E}^{\tilde{\sigma}_{t+1:T}^{l,m,f},\underline{F}(\underline{\pi}_{t},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},A^{l,m}_{t})}$
$\displaystyle\big{\\{}\sum_{n=t+1}^{T}\delta^{n-t}R_{n}^{f}(Z_{n},X_{n},A_{n})|z_{1:t},\phi(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},\hat{\gamma}^{f}_{t}),a_{1:t-1},A_{t},x_{1:t}^{f},X_{t+1}^{f}\big{\\}}\big{\lvert}\pi_{t},z_{t},x_{t}^{f}\big{\\}}$
(128c)
$\displaystyle=\max_{\gamma^{f}_{t}(\cdot|x_{t}^{f})}\mathbb{E}^{\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},{\gamma}^{f}_{t}(\cdot|x_{t}^{f})\,\pi_{t}}\big{\\{}R_{t}^{f}(Z_{t},X_{t},A_{t})+\max_{\sigma_{t+1:T}^{f}}\mathbb{E}^{\tilde{\sigma}_{t+1:T}^{l,m},\sigma_{t+1:T}^{f},\underline{F}(\underline{\pi}_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},A^{l,m}_{t})}$
$\displaystyle\big{\\{}\sum_{n=t+1}^{T}\delta^{n-t}R_{n}^{f}(Z_{n},X_{n},A_{n})|z_{1:t},\phi(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},\hat{\gamma}^{f}_{t}),a_{1:t-1},A_{t},x_{1:t}^{f},X_{t+1}^{f}\big{\\}}\big{\lvert}\pi_{t},z_{t},x_{t}^{f}\big{\\}}$
(128d)
$\displaystyle=\max_{\gamma^{f}_{t}(\cdot|x_{t}^{f})}\mathbb{E}^{\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},{\gamma}^{f}_{t}(\cdot|x_{t}^{f}),\,\pi_{t}}\big{\\{}R_{t}^{f}(Z_{t},X_{t},A_{t})+\max_{\sigma_{t+1:T}^{f}}\mathbb{E}^{\sigma_{t}^{l,i},\tilde{\sigma}_{t}^{l,-i},\hat{\sigma}_{t}^{m},\hat{\sigma}_{t}^{f},\tilde{\sigma}_{t+1:T}^{l,m}\sigma_{t+1:T}^{f},\underline{\pi}_{t}}$
$\displaystyle\big{\\{}\sum_{n=t+1}^{T}R_{n}^{f}(Z_{n},X_{n},A_{n})\big{\lvert}z_{1:t},\phi(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},\hat{\gamma}^{f}_{t}),a_{1:t-1},A_{t},x_{1:t}^{f},X_{t+1}^{f}\big{\\}}\big{|}z_{1:t},a_{1:t-1},x_{1:t}^{f}\big{\\}}$
(128e)
$\displaystyle=\max_{\sigma_{t}^{f}}\mathbb{E}^{\sigma_{t}^{l,i},\tilde{\sigma}_{t}^{l,-i},\hat{\sigma}_{t}^{m},{\sigma}_{t}^{f},\underline{\pi}_{t}}\big{\\{}R_{t}^{f}(Z_{t},X_{t},A_{t})+\max_{\sigma_{t+1:T}^{f}}\mathbb{E}^{\sigma_{t}^{l,i},\tilde{\sigma}_{t}^{l,-i},\hat{\sigma}_{t}^{m},\hat{\sigma}_{t}^{f},\tilde{\sigma}_{t+1:T}^{l,m}\sigma_{t+1:T}^{f},\underline{\pi}_{t}}$
$\displaystyle\big{\\{}\sum_{n=t+1}^{T}R_{n}^{f}(Z_{n},X_{n},A_{n})\big{\lvert}z_{1:t},\phi(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},\hat{\gamma}^{f}_{t}),a_{1:t-1},A_{t},x_{1:t}^{f},X_{t+1}^{f}\big{\\}}\big{|}z_{1:t},a_{1:t-1},x_{1:t}^{f}\big{\\}}$
(128f)
$\displaystyle=\max_{\sigma_{t:T}^{f}}\mathbb{E}^{\sigma_{t}^{l,i},\tilde{\sigma}_{t}^{l,-i},\hat{\sigma}_{t}^{m},{\sigma}_{t:T}^{f},\tilde{\sigma}_{t+1:T}^{l,m},\underline{\pi}_{t}}\big{\\{}\sum_{n=t}^{T}\delta^{t-n}R_{n}^{f}(Z_{n},X_{n},A_{n})\big{|}z_{1:t},a_{1:t-1},x_{1:t}^{f}\big{\\}}$
(128g)

where (128a) follows from definition of $\hat{\gamma}_{t}^{f}$ in (116),
(128c) follows from Lemma 5 in Appendix D, (128e) follows from the fact that
the probability on $Z_{t+1:T},X_{t+1:T},A_{t+1:T}$ conditioned on
$\tilde{\sigma}^{l,m}_{t:T},\sigma^{f}_{t:T},\underline{\pi}_{t}$ only depends
on
$\tilde{\sigma}_{t+1:T}^{l,m},\sigma_{t+1:T}^{f},\underline{F}(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}^{l,m},A_{t}^{l,m})$
as the follower’s strategy $\sigma_{t}^{f}$ doesn’t affect either the update
of the belief $\underline{\pi}_{t}$ or the update of the mean field $z_{t}$,
(128f) follows from the fact that $\hat{\sigma}^{f,m}_{t}$ are of type $m$ and
definition of $\hat{\gamma}_{t}^{f},\hat{\gamma}_{t}^{m}$.

Part 2: Major Follower (The arguments are similar but now for major player
$j$)

$\displaystyle\mathbb{E}^{\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},\hat{\gamma}^{f}_{t},\,\pi_{t}}\big{\\{}R_{t}^{m,j}(Z_{t},X^{l,m}_{t},A^{l,m}_{t})+$
$\displaystyle\delta
V_{t+1}^{m,j}(\underline{F}(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},A^{l,m}_{t}),\phi(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},\hat{\gamma}^{f}_{t}),X^{m,j}_{t+1})\big{\lvert}\underline{\pi_{t}},z_{t},x_{t}^{m,j}\big{\\}}\big{\\}}$
$\displaystyle=\max_{\gamma^{m,j}_{t}(\cdot|x_{t}^{m,j})}\mathbb{E}^{\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\gamma_{t}^{m,j}(\cdot|x_{t}^{m,j}),\hat{\gamma}_{t}^{m,-j}\hat{\gamma}^{f}_{t},\,\pi_{t}}\big{\\{}R_{t}^{m,j}(Z_{t},X^{l,m}_{t},A^{l,m}_{t})+$
$\displaystyle\delta
V_{t+1}^{m,j}(\underline{F}(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},A^{l,m}_{t}),\phi(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},\hat{\gamma}^{f}_{t}),X^{m,j}_{t+1})\big{\lvert}\underline{\pi_{t}},z_{t},x_{t}^{m,j}\big{\\}}\big{\\}}$
$\displaystyle=\max_{\gamma^{m,j}_{t}(\cdot|x_{t}^{m,j})}\mathbb{E}^{\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\gamma_{t}^{m,j}(\cdot|x_{t}^{m,j})\hat{\gamma}_{t}^{m,-j},{\gamma}^{f}_{t}\,\pi_{t}}\big{\\{}R_{t}^{m,j}(Z_{t},X^{l,m}_{t},A^{l,m}_{t})+\mathbb{E}^{\tilde{\sigma}_{t+1:T}^{l,m,f},\underline{F}(\underline{\pi}_{t},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},A^{l,m}_{t})}$
$\displaystyle\big{\\{}\sum_{n=t+1}^{T}\delta^{n-t}R_{n}^{m,j}(Z_{n},X^{l,m}_{n},A^{l,m}_{n})|z_{1:t},\phi(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},\hat{\gamma}^{f}_{t}),a^{l,m}_{1:t-1},A^{l,m}_{t},x_{1:t}^{m,j},X_{t+1}^{m,j}\big{\\}}\big{\lvert}\pi_{t},z_{t},x_{t}^{m,j}\big{\\}}$
(129a)
$\displaystyle=\max_{\gamma^{m,j}_{t}(\cdot|x_{t}^{m,j})}\mathbb{E}^{\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\gamma_{t}^{m,j}(\cdot|x_{t}^{m,j})\hat{\gamma}_{t}^{m,-j},{\gamma}^{f}_{t})\,\pi_{t}}\big{\\{}R_{t}^{m,j}(Z_{t},X^{l,m}_{t},A^{l,m}_{t})+\max_{\sigma_{t+1:T}^{m,j}}\mathbb{E}^{\tilde{\sigma}_{t+1:T}^{l},\sigma_{t+1:T}^{m,j},\tilde{\sigma}_{t+1:T}^{m,-j},\tilde{\sigma}_{t+1:T}^{f},\underline{F}(\underline{\pi}_{t},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},A^{l,m}_{t})}$
$\displaystyle\big{\\{}\sum_{n=t+1}^{T}\delta^{n-t}R_{n}^{m,j}(Z_{n},X^{l,m}_{n},A^{l,m}_{n})|z_{1:t},\phi(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},\hat{\gamma}^{f}_{t}),a^{l,m}_{1:t-1},A^{l,m}_{t},x_{1:t}^{m,j},X_{t+1}^{m,j}\big{\\}}\big{\lvert}\pi_{t},z_{t},x_{t}^{m,j}\big{\\}}$
(129b)
$\displaystyle=\max_{\gamma^{m,j}_{t}(\cdot|x_{t}^{m,j})}\mathbb{E}^{\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\gamma_{t}^{m,j}(\cdot|x_{t}^{m,j})\hat{\gamma}_{t}^{m,-j},{\gamma}^{f}_{t},\,\pi_{t}}\big{\\{}R_{t}^{m,j}(Z_{t},X^{l,m}_{t},A^{l,m}_{t})+\max_{\sigma_{t+1:T}^{m,j}}\mathbb{E}^{\sigma_{t}^{l,i},\tilde{\sigma}_{t}^{l,-i},\hat{\sigma}_{t}^{m},\hat{\sigma}_{t}^{f},\tilde{\sigma}_{t+1:T}^{l}\sigma_{t+1:T}^{m,j},\sigma_{t+1:T}^{m,-j},\tilde{\sigma}_{t+1:T}^{f},\underline{\pi}_{t}}$
$\displaystyle\big{\\{}\sum_{n=t+1}^{T}R_{n}^{m,j}(Z_{n},X^{l,m}_{n},A^{l,m}_{n})\big{\lvert}z_{1:t},\phi(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},\hat{\gamma}^{f}_{t}),a^{l,m}_{1:t-1},A^{l,m}_{t},x_{1:t}^{m,j},X_{t+1}^{m,j}\big{\\}}\big{|}\pi_{t},z_{1:t},a^{l,m}_{1:t-1},x_{1:t}^{m,j}\big{\\}}$
(129c)
$\displaystyle=\max_{\sigma_{t}^{m,j}}\mathbb{E}^{\sigma_{t}^{l,i},\tilde{\sigma}_{t}^{l,-i},\sigma_{t}^{m,j}\hat{\sigma}_{t}^{m,-j},\hat{\sigma}^{f}_{t},\underline{\pi}_{t}}\big{\\{}R_{t}^{m,j}(Z_{t},X^{l,m}_{t},A^{l,m}_{t})+\max_{\sigma_{t+1:T}^{m,j}}\mathbb{E}^{\sigma_{t}^{l,i},\tilde{\sigma}_{t}^{l,-i},\hat{\sigma}_{t}^{m},\hat{\sigma}_{t}^{f},\tilde{\sigma}_{t+1:T}^{l}\sigma_{t+1:T}^{m,j},\sigma_{t+1:T}^{m,-j},\tilde{\sigma}_{t+1:T}^{f},\underline{\pi}_{t}}$
$\displaystyle\big{\\{}\sum_{n=t+1}^{T}R_{n}^{m,j}(Z_{n},X^{l,m}_{n},A^{l,m}_{n})\big{\lvert}z_{1:t},\phi(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},\hat{\gamma}^{f}_{t}),a^{l,m}_{1:t-1},A^{l,m}_{t},x_{1:t}^{m,j},X_{t+1}^{m,j}\big{\\}}\big{|}\pi_{t},z_{1:t},a^{l,m}_{1:t-1},x_{1:t}^{m,j}\big{\\}}$
(129d)
$\displaystyle=\max_{\sigma_{t:T}^{m,j}}\mathbb{E}^{\sigma_{t}^{l,i},\tilde{\sigma}_{t}^{l,-i},\sigma_{t}^{m,j}\hat{\sigma}_{t}^{m,-j},\hat{\sigma}_{t}^{f},\tilde{\sigma}_{t+1:T}^{l}\sigma_{t+1:T}^{m,j},\tilde{\sigma}_{t+1:T}^{m,-j},\tilde{\sigma}_{t+1:T}^{f},\underline{\pi}_{t}}\big{\\{}\sum_{n=t}^{T}\delta^{t-n}R_{n}^{m,j}(Z_{n},X^{l,m}_{n},A^{l,m}_{n})\big{|}\pi_{t},z_{1:t},a^{l,m}_{1:t-1},x_{1:t}^{m,j}\big{\\}}$
(129e)

where (128c) follows from Lemma 5 in Appendix D, (128e) follows from Lemma 8,
(128f) follows from the fact that $\hat{\sigma}^{f,m}_{t}$ are of type $m$ and
definition of $\hat{\gamma}_{t}^{f},\hat{\gamma}_{t}^{m}$. This proves the
theorem.

∎

###### Lemma 13

Let $(\tilde{\sigma}^{l,m,f},z)$ be an SMFE-ML for the game considered and let
$\forall x_{t}^{l,m}$

$\displaystyle\pi_{t}(x_{t}^{l,m})=P^{\tilde{\sigma}_{1:t-1}^{l,m,f}}(x^{l,m}_{t}|z_{1:t},a^{l,m}_{1:t-1})$
(130)

. Then for any given $(\sigma_{t}^{l,i},a_{1:t-1},x_{1:t}^{l})$, let

$\displaystyle{\gamma}^{l,i}_{t}$
$\displaystyle={\sigma}_{t}^{l,i}(\cdot|z_{1:t},{a}^{l,m}_{1:t-1},\cdot)$
(131)

Then

$\displaystyle
P^{\tilde{\sigma}_{1:t-1}^{l},\sigma_{t}^{l,i},\tilde{\sigma}_{t}^{l,-i},\tilde{\sigma}_{t+1:T}^{l},\hat{\sigma}^{m}}(x^{l,m}_{t+1}|z_{1:t+1},a_{1:t})=F(\pi_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},a_{t}^{l,m})(x^{l,m}_{t+1})$
(132)

where $\hat{\sigma}^{f}\in
BR^{f}(\tilde{\sigma}_{1:t-1}^{l},\sigma_{t}^{l,i},\tilde{\sigma}_{t}^{l,-i},\tilde{\sigma}_{t+1:T}^{l},\hat{\sigma}^{m})$,
$\hat{\sigma}^{m}\in
BR^{m}(\tilde{\sigma}_{1:t-1}^{l},\sigma_{t}^{l,i},\tilde{\sigma}_{t}^{l,-i},\tilde{\sigma}_{t+1:T}^{l},\hat{\sigma}^{f},\hat{\sigma}^{m})$
where $\hat{\sigma}^{f},\hat{\sigma}^{m}$ are of type $m$. Also
$\hat{\gamma}_{t}^{m}\in\bar{BR}_{t}^{m}(\pi_{t},z_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m})$

###### Proof:

Let $\hat{\sigma}^{f}\in
BR^{f}(\tilde{\sigma}_{1:t-1}^{l},\sigma_{t}^{l,i},\tilde{\sigma}_{t}^{l,-i},\tilde{\sigma}_{t+1:T}^{l},\hat{\sigma}^{m})$
and
$\gamma_{t}^{f}\in\bar{BR}^{f}(\pi_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m})$
be of type $m$. Then $\forall
a_{1:t-1},x_{1:t-1}^{f},x_{1:t-1}^{m,j},x_{1:t-1}^{l,i}$, and for every
$\hat{\gamma}_{t}^{f},\hat{\gamma}_{t}^{m}$ that satisfy (117), (118)
$\exists(\hat{\sigma}_{t}^{m})$ that satisfy (115) (116) such that

$\displaystyle\hat{\gamma}_{t}^{m,j}$
$\displaystyle=\hat{\sigma}_{t}^{m,j}(\cdot|z_{1:t},a^{l,m}_{1:t-1},\cdot)$
(133)

where,

Thus

$\displaystyle
P^{\tilde{\sigma}_{1:t-1}^{l},\sigma_{t}^{l,i},\tilde{\sigma}_{t}^{l,-i},\tilde{\sigma}_{t+1:T}^{l},\hat{\sigma}^{m},\hat{\sigma}^{f}}(x^{l,m}_{t+1}|z_{1:t+1},a_{1:t})$
$\displaystyle=\frac{\sum_{x^{l,m}_{1:t}}P^{\tilde{\sigma}_{1:t-1}^{l},\sigma_{t}^{l,i},\tilde{\sigma}_{t}^{l,-i},\tilde{\sigma}_{t+1:T}^{l},\hat{\sigma}^{m},\hat{\sigma}^{f}}(x^{l,m}_{1:t+1},z_{t+1},a^{l,m}_{t}|z_{1:t},a^{l,m}_{1:t-1})}{\sum_{x^{l,m}_{1:t}}P^{\tilde{\sigma}_{1:t-1}^{l},\sigma_{t}^{l,i},\tilde{\sigma}_{t}^{l,-i},\tilde{\sigma}_{t+1:T}^{l},\hat{\sigma}^{m},\hat{\sigma}^{f}}(x_{1:t}^{l,m}|z_{1:t},a^{l,m}_{1:t-1})1(z_{t+1}=\phi(z_{t},\tilde{\gamma}_{t}))\sigma_{t}^{l,m}(a^{l,m}_{t}|z_{1:t},a^{l,m}_{1:t-1},x_{1:t}^{l,m}))}$
(134)
$\displaystyle=\frac{\sum_{x^{l,m}_{1:t}}P^{\tilde{\sigma}_{1:t-1}^{l},\sigma_{t}^{l,i},\tilde{\sigma}_{t}^{l,-i},\tilde{\sigma}_{t+1:T}^{l},\hat{\sigma}^{m},\hat{\sigma}^{f}}(x^{l,m}_{1:t}|z_{1:t+1},a^{l,m}_{1:t})\sigma_{t}^{l,i}(a_{t}^{l,i}|a_{1:t-1},x_{1:t}^{l,i}),\tilde{\sigma}_{t}^{l,-i}(a_{t}^{l,-i}|a_{1:t-1},x_{1:t}^{l,-i}),\hat{\sigma}^{m}(a_{t}^{m}|a_{1:t-1},x_{1:t}^{m})Q(x^{l,m}_{t+1}|x^{l,m}_{t},a^{l,m}_{t})}{\sum_{x^{l,m}_{1:t}}P^{\tilde{\sigma}_{1:t-1}^{l},\sigma_{t}^{l,i},\tilde{\sigma}_{t}^{l,-i},\tilde{\sigma}_{t+1:T}^{l},\hat{\sigma}^{m}}(x^{l,m}_{1:t}|z_{1:t},a^{l,m}_{1:t-1})\sigma_{t}^{l,i}(a_{t}^{l,i}|a_{1:t-1},x_{1:t}^{l,i}),\tilde{\sigma}_{t}^{l,-i}(a_{t}^{l,-i}|a_{1:t-1},x_{1:t}^{l,-i}),\hat{\sigma}^{m}(a_{t}^{m}|a_{1:t-1},x_{1:t}^{m})}$
(135)
$\displaystyle=\frac{\sum_{x_{t}}\pi_{t}(x^{l,m}_{t})\gamma_{t}^{l,i}(a^{l,i}_{t}|x_{t}^{l,i}),\tilde{\gamma}_{t}^{l,-i}(a^{l,-i}_{t}|x_{t}^{l,-i}),\hat{\gamma}_{t}^{m}(a^{m}_{t}|x_{t}^{m})Q(x^{l,m}_{t+1}|x^{l,m}_{t},a^{l,m}_{t})}{\sum_{x^{l,m}_{t}}\pi_{t}(x_{t}^{l,m})\gamma_{t}^{l,i}(a^{l,i}_{t}|x_{t}^{l,i}),\tilde{\gamma}_{t}^{l,-i}(a^{l,-i}_{t}|x_{t}^{l,-i}),\hat{\gamma}_{t}^{m}(a^{m}_{t}|x_{t}^{m})}$
(136)
$\displaystyle=F(\pi_{t},\gamma_{t}^{l,i},\tilde{\gamma}_{t}^{l,-i},\hat{\gamma}_{t}^{m},a^{l,m}_{t})(x^{l,m}_{t+1})$
(137)

Moreover,

$\displaystyle z_{t+1}(\cdot)$
$\displaystyle=\sum_{x_{t}^{f},x_{t}^{l,m},a_{t}}z_{t}(x_{t}^{f})P^{\tilde{\sigma}_{t}^{l,m}}(x^{l,m}_{t}|z_{1:t},a_{1:t-1})Q^{f}(\cdot|z_{t},x_{t}^{f},a_{t}^{f},a^{l,m}_{t}){\sigma}^{f}_{t}(a^{f}_{t}|z_{1:t},a_{1:t-1}^{l,m},x_{t}^{f})$
(138)
$\displaystyle\sigma_{t}^{l}(a^{l}_{t}|z_{1:t},a_{1:t-1}^{l,m},x_{1:t}^{l}){\sigma}_{t}^{m}(a^{m}_{t}|z_{1:t},a_{1:t-1}^{l,m},x_{t}^{m})$
(139) $\displaystyle=\phi(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,m,f})$ (140)

where

$\displaystyle\gamma_{t}^{l}=\sigma^{l}_{t}(\cdot|z_{1:t},a_{1:t-1}^{l,m},\cdot)$
(141)
$\displaystyle\gamma_{t}^{m}=\sigma^{m}_{t}(\cdot|z_{1:t},a_{1:t-1}^{l,m},\cdot)$
(142)
$\displaystyle\gamma_{t}^{f}=\sigma^{f}_{t}(\cdot|z_{1:t},a_{1:t-1}^{l,m},\cdot)$
(143) $\displaystyle\underline{\pi}_{t}(\cdot)$
$\displaystyle=P^{\tilde{\sigma}_{1:t-1}^{l,m},}(\cdot|z_{1:t+1},a_{1:t}^{l,m})$
(144)

∎

##  Appendix J Lemmas for converse

###### Proof:

We prove this by contradiction. This implies there exists
$\underline{\pi_{t}},z_{t}$ such that either (a) (55a) doesn’t have a
solution, (b) (55b) doesn’t have a solution, or (c) (55c) doesn’t have a
solution.

  * (a)

Suppose (55a) doesn’t have a solution (concerning the minor follower) i.e. for
any equilibrium generating function $\theta$ that generates
$(\tilde{\sigma}^{l,m,f},z)$ through forward recursion, there exists

$t\in[T],z_{1:t},a_{1:t-1}^{l,m}$ such that for
$\underline{\pi_{t}}(\cdot)=P^{\tilde{\sigma}^{l},\tilde{\sigma}^{m},\tilde{\sigma}^{f}}(\cdot|z_{1:t},a_{1:t-1}^{l,m})$,
(55a) is not satisfied for $\theta_{t}$ i.e. for
$\tilde{\gamma}^{f}_{t}=\theta_{t}^{f}[\underline{\pi_{t}},z_{t}]=\tilde{\sigma}_{t}^{f}(\cdot|\underline{\pi_{t}},z_{t},\cdot),\tilde{\gamma}^{l}_{t}=\theta^{l}[\underline{\pi_{t}},z_{t}]=\tilde{\sigma}_{t}^{l}(\cdot|\underline{\pi_{t}},z_{t},\cdot)$,
$\tilde{\gamma}^{m}_{t}=\theta^{m}[\underline{\pi_{t}},z_{t}]=\tilde{\sigma}_{t}^{m}(\cdot|\underline{\pi_{t}},z_{t},\cdot)$,
$\exists x_{t}^{f}$ such that
$\displaystyle\tilde{\gamma}_{t}^{f}(\cdot|x_{t}^{f})\notin\arg\max_{\gamma^{m,j}_{t}(\cdot|x_{t}^{m,j})}\mathbb{E}^{{\tilde{\gamma}}^{l}_{t},\tilde{\gamma}_{t}^{m},\gamma^{m,j}_{t}(\cdot|x_{t}^{m,j}),\,z_{t},\underline{\pi_{t}}}$
$\displaystyle\big{\\{}R_{t}^{f}(z_{t},X_{t},A_{t})+\delta
V_{t+1}^{m,j}(\underline{F}(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}^{l,m},A_{t}^{l,m}),\phi(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}),X^{f}_{t+1})\big{\lvert}\underline{\pi_{t}},z_{t},x_{t}^{f}\big{\\}}$
(145a) Let $t$ be the first instance in the backward recursion when this
happens. This implies $\exists\ \hat{\gamma}_{t}^{f}$ such that
$\displaystyle\mathbb{E}^{{\tilde{\gamma}}^{l,m}_{t},\hat{\gamma}^{f}_{t}(\cdot|x_{t}^{f}),\,z_{t},\underline{\pi_{t}}}\big{\\{}R_{t}^{f}(z_{t},X_{t},A_{t})+\delta
V_{t+1}^{m,j}(\underline{F}(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}^{l,m},A^{l,m}_{t}),\phi(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}),X^{f}_{t+1})\big{\lvert}\underline{\pi_{t}},z_{t},x_{t}^{f}\big{\\}}$
$\displaystyle>\mathbb{E}^{{\tilde{\gamma}}^{l,m}_{t},\tilde{\gamma}^{f}_{t}(\cdot|x_{t}^{f}),\,z_{t},\underline{\pi_{t}}}\big{\\{}R_{t}^{f}(z_{t},X_{t},A_{t})+\delta
V_{t+1}^{m,j}(\underline{F}(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}^{l,m},A^{l,m}_{t}),\phi(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}),X^{f}_{t+1})\big{\lvert}\underline{\pi_{t}},z_{t},x_{t}^{f}\big{\\}}$
(145b) This implies for
$\hat{\sigma}^{f}_{t}(\cdot|z_{1:t},a_{1:t-1}^{l,m},x_{1:t-1}^{f},\cdot)=\hat{\gamma}_{t}^{f}$,
$\displaystyle\mathbb{E}^{\tilde{\sigma}_{t:T}^{l,m},\tilde{\sigma}_{t:T}^{f},\underline{\pi_{t}}}\big{\\{}\sum_{n=t}^{T}R_{n}^{f}(Z_{n},X_{n},A_{n})\big{\lvert}\underline{\pi_{t}},z_{1:t},a_{1:t-1}^{l,m},x_{1:t}^{f}\big{\\}}$
$\displaystyle=\mathbb{E}^{\tilde{\sigma}_{t}^{l,m},\tilde{\sigma}_{t}^{f},\underline{\pi_{t}}}\big{\\{}R_{t}^{f}(Z_{t},X_{t},A_{t})+\mathbb{E}^{\tilde{\sigma}_{t:T}^{f}\tilde{\sigma}_{t:T}^{l},\underline{\pi_{t}}}$
$\displaystyle\big{\\{}\sum_{n=t+1}^{T}R_{n}^{f}(Z_{n},X_{n},A_{n})\big{\lvert}\underline{\pi_{t}},z_{1:t},\phi(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}),a_{1:t-1},A^{l,m}_{t},x_{1:t}^{f},X_{t+1}^{f}\big{\\}}\big{|}\underline{\pi_{t}},z_{1:t},a_{1:t-1}^{l,m},x_{1:t}^{f}\big{\\}}$
(145c)
$\displaystyle=\mathbb{E}^{\tilde{\sigma}_{t}^{l,m},\tilde{\sigma}_{t}^{f},\,\underline{\pi_{t}}}\big{\\{}R_{t}^{f}(Z_{t},X_{t},A_{t})+\mathbb{E}^{\tilde{\sigma}_{t+1:T}^{f}\tilde{\sigma}_{t+1:T}^{l},\underline{F}(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}^{l,m},A^{l,m}_{t})}$
$\displaystyle\big{\\{}\sum_{n=t+1}^{T}R_{n}^{f}(Z_{n},X_{n},A_{n})\big{\lvert}z_{1:t},\phi(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}),a_{1:t-1}^{l,m},A^{l,m}_{t},x_{1:t}^{f},X_{t+1}^{f}\big{\\}}\big{|}\underline{\pi_{t}},z_{1:t},a_{1:t-1}^{l,m},x_{1:t}^{f}\big{\\}}$
(145d)
$\displaystyle=\mathbb{E}^{\tilde{\gamma}^{l}_{t},\tilde{\gamma}^{m}_{t},\tilde{\gamma}^{f}_{t},\,\underline{\pi_{t}}}\big{\\{}R_{t}^{f}(Z_{t},X_{t},A_{t})+V_{t+1}^{m,j}(\underline{F}(\underline{\pi_{t}},z_{t},\tilde{\gamma}^{l,m}_{t},A^{l,m}_{t}),\phi(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}),X_{t+1}^{f})\big{\lvert}\underline{\pi_{t}},x_{t}^{f}\big{\\}}$
(145e)
$\displaystyle<\mathbb{E}^{\tilde{\gamma}^{l,m}_{t},\hat{\gamma}^{f}_{t}\,\underline{\pi_{t}}}\big{\\{}R_{t}^{f}(Z_{t},X_{t},A_{t})+V_{t+1}^{m,j}(\underline{F}(\underline{\pi}_{t},z_{t},\tilde{\gamma}^{l,m}_{t},A^{l,m}_{t}),\phi(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}),X_{t+1}^{f})\big{\lvert}\underline{\pi_{t}},x_{t}^{f}\big{\\}}$
(145f)
$\displaystyle=\mathbb{E}^{\tilde{\sigma}_{t}^{l,m},\hat{\sigma}_{t}^{f},\underline{\pi_{t}}}\big{\\{}R_{t}^{f}(Z_{t},X_{t},A_{t})+\mathbb{E}^{\tilde{\sigma}_{t+1:T}^{l,m},\tilde{\sigma}_{t+1:T}^{f},\underline{F}(\underline{\pi}_{t},z_{t},\tilde{\gamma}^{l,m}_{t},A^{l,m}_{t})}$
$\displaystyle\big{\\{}\sum_{n=t+1}^{T}R_{n}^{f}(Z_{n},X_{n},A_{n})\big{\lvert}z_{1:t},\phi(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}),a_{1:t-1},A_{t},x_{1:t}^{f},X_{t+1}^{f}\big{\\}}\big{|}\underline{\pi_{t}},z_{1:t},a_{1:t-1}^{l,m},x_{1:t}^{f}\big{\\}}$
(145g)
$\displaystyle=\mathbb{E}^{\tilde{\sigma}_{t:T}^{l,m},\hat{\sigma}_{t}^{f},\tilde{\sigma}_{t+1:T}^{f},\underline{\pi_{t}}}\big{\\{}\sum_{n=t}^{T}R_{n}^{f}(Z_{n},X_{n},A_{n})\big{\lvert}\underline{\pi_{t}},z_{1:t},a_{1:t-1}^{l,m},x_{1:t}^{f}\big{\\}},$
(145h) where (145d) follows from the fact that the probability on
$Z_{t+1:T},X_{t+1:T},A_{t+1:T}$ conditioned on
$\tilde{\sigma}^{l,m}_{t:T},\sigma^{f}_{t:T},\underline{\pi}_{t}$ only depends
on
$\tilde{\sigma}_{t+1:T}^{l,m},\sigma_{t+1:T}^{f},\underline{F}(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}^{l,m},A_{t}^{l,m})$
as the follower’s strategy $\sigma_{t}^{f}$ doesn’t affect either the update
of the belief $\underline{\pi}_{t}$ or the update of the mean field $z_{t}$,
(145e) follows from the definitions of $\tilde{\gamma}_{t}^{f}$ and
$\underline{\pi_{t}}$ and Lemma 5, (145f) follows from (145b) and the
definition of $\hat{\sigma}_{t}^{f}$, (145g) follows from Lemma 4, (145h)
again from the fact that the probability on $Z_{t+1:T},X_{t+1:T},A_{t+1:T}$
conditioned on
$\tilde{\sigma}^{l,m}_{t:T},\sigma^{f}_{t:T},\underline{\pi}_{t}$ only depends
on
$\tilde{\sigma}_{t+1:T}^{l,m},\sigma_{t+1:T}^{f},\underline{F}(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}^{l,m},A_{t}^{l,m})$
as the follower’s strategy $\sigma_{t}^{f}$ doesn’t affect either the update
of the belief $\underline{\pi}_{t}$ or the update of the mean field $z_{t}$..
However, this leads to a contradiction since $(\tilde{\sigma}^{l,m,f},z)$ is a
SMFE-ML of the game.

  * (b)

If (55b) doesn’t have a solution (concerning major follower): Suppose for any
equilibrium generating function $\theta$ that generates
$(\tilde{\sigma}^{l},\tilde{\sigma}^{m},\tilde{\sigma}^{f},z)$ through forward
recursion, there exists $t\in[T],z_{1:t},a_{1:t-1}^{l,m}$ such that for
$\underline{\pi_{t}}(\cdot)=P^{\tilde{\sigma}^{l,m,f}}(\cdot|z_{1:t},a_{1:t-1}^{l,m})$,
(55b) is not satisfied for $\theta$ i.e. for
$\tilde{\gamma}^{f}_{t}=\theta^{f}[\underline{\pi_{t}},z_{t}]=\tilde{\sigma}_{t}^{f}(\cdot|\underline{\pi_{t}},z_{t},\cdot),\tilde{\gamma}^{l}_{t}=\theta^{l}[\underline{\pi_{t}},z_{t}]=\tilde{\sigma}_{t}^{l}(\cdot|\underline{\pi_{t}},z_{t},\cdot),\tilde{\gamma}^{m}_{t}=\theta^{m}[\underline{\pi_{t}},z_{t}]=\tilde{\sigma}_{t}^{m}(\cdot|\underline{\pi_{t}},z_{t},\cdot)$,
$\exists j,x_{t}^{m,j}$ such that

$\displaystyle\tilde{\gamma}_{t}^{m,j}(\cdot|x_{t}^{m,j})\notin\arg\max_{\gamma^{m,j}_{t}(\cdot|x_{t}^{m,j})}\mathbb{E}^{{\tilde{\gamma}}^{l}_{t},\gamma^{m,j}_{t}(\cdot|x_{t}^{m,j})\tilde{\gamma}_{t}^{m,-j},\gamma^{f}_{t}\,z_{t},\underline{\pi_{t}}}$
$\displaystyle\big{\\{}R_{t}^{m,j}(z_{t},X_{t}^{l,m},A^{l,m}_{t})+\delta
V_{t+1}^{m,j}(\underline{F}(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}^{l,m},A_{t}^{l,m}),\phi(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}),X^{m,j}_{t+1})\big{\lvert}\underline{\pi_{t}},z_{t},x_{t}^{m,j}\big{\\}}$
(146a) Let $t$ be the first instance in the backward recursion when this
happens. This implies $\exists\ \hat{\gamma}_{t}^{m,j}$ such that
$\displaystyle\mathbb{E}^{{\tilde{\gamma}}^{l}_{t},\hat{\gamma}_{t}^{m,j}(\cdot|x_{t}^{m,j}),\tilde{\gamma}_{t}^{m,-j},{\tilde{\gamma}}^{f}_{t}\,z_{t},\underline{\pi_{t}}}\big{\\{}R_{t}^{m,j}(z_{t},X^{l,m}_{t},A_{t}^{l,m})+$
$\displaystyle\delta
V_{t+1}^{m,j}(\underline{F}(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}^{l,m},A^{l,m}_{t}),\phi(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}),X^{m,j}_{t+1})\big{\lvert}\underline{\pi_{t}},z_{t},x_{t}^{m,j}\big{\\}}$
$\displaystyle>\mathbb{E}^{{\tilde{\gamma}}^{l}_{t},\tilde{\gamma}^{m,j}_{t}(\cdot|x_{t}^{m,j}),\tilde{\gamma}^{m,-j}_{t},\tilde{\gamma}^{f}_{t}\,z_{t},\underline{\pi_{t}}}\big{\\{}R_{t}^{m,j}(z_{t},X^{l,m}_{t},A^{l,m}_{t})+$
$\displaystyle\delta
V_{t+1}^{m,j}(\underline{F}(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}^{l,m},A^{l,m}_{t}),\phi(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}),X^{m,j}_{t+1})\big{\lvert}\underline{\pi_{t}},z_{t},x_{t}^{m,j}\big{\\}}$
(146b) This implies for
$\hat{\sigma}^{m,j}_{t}(\cdot|z_{1:t},a_{1:t-1}^{l,m},x_{1:t-1}^{m,j},\cdot)=\hat{\gamma}_{t}^{m,j}$,
$\displaystyle\mathbb{E}^{\tilde{\sigma}_{t:T}^{l,m,f},\underline{\pi_{t}}}\big{\\{}\sum_{n=t}^{T}R_{n}^{m,j}(Z_{n},X^{l,m}_{n},A^{l,m}_{n})\big{\lvert}\underline{\pi_{t}},z_{1:t},a^{l,m}_{1:t-1},x_{1:t}^{m,j}\big{\\}}$
$\displaystyle=\mathbb{E}^{\tilde{\sigma}_{t}^{l,m,f},\underline{\pi_{t}}}\big{\\{}R_{n}^{m,j}(Z_{t},X^{l,m}_{t},A^{l,m}_{t})+\mathbb{E}^{\tilde{\sigma}_{t:T}^{l,m,f},\underline{\pi_{t}}}$
$\displaystyle\big{\\{}\sum_{n=t+1}^{T}R_{n}^{m,j}(Z_{n},X^{l,m}_{n},A^{l,m}_{n})\big{\lvert}\underline{\pi_{t}},z_{1:t},\phi(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}),a^{l,m}_{1:t-1},A^{l,m}_{t},x_{1:t}^{m,j},X_{t+1}^{m,j}\big{\\}}\big{|}\underline{\pi_{t}},z_{1:t},a_{1:t-1}^{l,m},x_{1:t}^{m,j}\big{\\}}$
(146c)
$\displaystyle=\mathbb{E}^{\tilde{\sigma}_{t}^{l,m,f},\,\underline{\pi_{t}}}\big{\\{}R_{n}^{m,j}(Z_{t},X^{l,m}_{t},A^{l,m}_{t})+\mathbb{E}^{\tilde{\sigma}_{t+1:T}^{f}\tilde{\sigma}_{t+1:T}^{l},\underline{F}(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}^{l,m},A^{l,m}_{t})}$
$\displaystyle\big{\\{}\sum_{n=t+1}^{T}R_{n}^{m,j}(Z_{n},X^{l,m}_{n},A^{l,m}_{n})\big{\lvert}z_{1:t},\phi(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}),a_{1:t-1}^{l,m},A^{l,m}_{t},x_{1:t}^{m,j},X_{t+1}^{m,j}\big{\\}}\big{|}\underline{\pi_{t}},z_{1:t},a_{1:t-1}^{l,m},x_{1:t}^{m,j}\big{\\}}$
(146d)
$\displaystyle=\mathbb{E}^{\tilde{\gamma}^{l}_{t},\tilde{\gamma}^{m,j}_{t}(\cdot|x_{t}^{m,j}),\tilde{\gamma}^{m,-j}_{t},\tilde{\gamma}^{f}_{t}\,\underline{\pi_{t}}}\big{\\{}R_{n}^{m,j}(Z_{t},X^{l,m}_{t},A^{l,m}_{t})+V_{t+1}^{m,j}(\underline{F}(\underline{\pi_{t}},z_{t},\tilde{\gamma}^{l,m}_{t},A^{l,m}_{t}),\phi(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}),X_{t+1}^{m,j})\big{\lvert}\underline{\pi_{t}},x_{t}^{m,j}\big{\\}}$
(146e)
$\displaystyle<\mathbb{E}^{\tilde{\sigma}_{t}^{l},\hat{\gamma}^{m,j}_{t}(\cdot|x_{t}^{m,j}),{\tilde{\sigma}}_{t}^{m,-j}\tilde{\gamma}^{f}_{t},\,\underline{\pi_{t}}}\big{\\{}R_{n}^{m,j}(Z_{t},X^{l,m}_{t},A^{l,m}_{t})+V_{t+1}^{m,j}(F({\pi}_{t},\tilde{\gamma}_{t},A_{t}),\phi(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}),X_{t+1}^{m,j})\big{\lvert}\underline{\pi_{t}},x_{t}^{m,j}\big{\\}}$
(146f)
$\displaystyle=\mathbb{E}^{\tilde{\sigma}_{t}^{l},\hat{\sigma}_{t}^{m,j},{\tilde{\sigma}}_{t}^{m,-j},{\tilde{\sigma}}_{t}^{f},\underline{\pi_{t}}}\big{\\{}R_{n}^{m,j}(Z_{t},X^{l,m}_{t},A^{l,m}_{t})+\mathbb{E}^{\tilde{\sigma}_{t+1:T}^{f}\tilde{\sigma}_{t+1:T}^{l}\pi_{t+1}}$
$\displaystyle\big{\\{}\sum_{n=t+1}^{T}R_{n}^{m,j}(Z_{n},X^{l,m}_{n},A^{l,m}_{n})\big{\lvert}z_{1:t},\phi(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}),a^{l,m}_{1:t-1},A^{l,m}_{t},x_{1:t}^{m,j},X_{t+1}^{m,j}\big{\\}}\big{|}\underline{\pi_{t}},z_{1:t},a_{1:t-1}^{l,m},x_{1:t}^{m,j}\big{\\}}$
(146g)
$\displaystyle=\mathbb{E}^{\tilde{\sigma}_{t:T}^{l},\hat{\sigma}_{t}^{m,j},\tilde{\sigma}_{t}^{m,-j},\tilde{\sigma}_{t+1:T}^{f},\underline{\pi_{t}}}\big{\\{}\sum_{n=t}^{T}R_{n}^{m,j}(Z_{n},X^{l,m}_{n},A^{l,m}_{n})\big{\lvert}\underline{\pi_{t}},z_{1:t},a_{1:t-1}^{l,m},x_{1:t}^{m,j}\big{\\}},$
(146h) where (146d) follows from Lemma 8, (146e) follows from the definitions
of $\tilde{\gamma}_{t}^{m,j}$ and $\underline{\pi_{t}}$ and Lemma 5, (146f)
follows from (146b) and the definition of $\hat{\sigma}_{t}^{m,j}$, (146g)
follows from Lemma 4, (146h) follows from Lemma 8. However, this leads to a
contradiction since $(\tilde{\sigma}^{l,m,f},z)$ is a SMFE-ML of the game.

  * (c)

(55c) doesn’t have a solution (concerning leader $i$)

Suppose for any equilibrium generating function $\theta$ that generates
$(\tilde{\sigma}^{l,m,f},z)$ through forward recursion, there exists
$t\in[T],z_{1:t},a_{1:t-1}^{l,m}$ such that for
$\underline{\pi_{t}}(\cdot)=P^{\tilde{\sigma}^{l,m,f}}(\cdot|z_{1:t},a_{1:t-1}^{l,m})$,
(55c) is not satisfied for $\theta$ i.e. for
$\tilde{\gamma}^{f}_{t}=\theta^{f}[\underline{\pi_{t}},z_{t}]=\tilde{\sigma}_{t}^{f}(\cdot|\underline{\pi_{t}},z_{t},\cdot),\tilde{\gamma}^{l,m}_{t}=\theta^{l,m}[\underline{\pi_{t}},z_{t}]=\tilde{\sigma}_{t}^{l,m}(\cdot|\underline{\pi_{t}},z_{t},\cdot)$,
$\exists i,x^{l,i}_{t}$ such that

$\displaystyle\tilde{\gamma}_{t}^{l,i}$
$\displaystyle\notin\arg\max_{\gamma_{t}^{l,i}}\mathbb{E}^{{\gamma}^{l,i}_{t},\tilde{\gamma}_{t}^{l,-i},\bar{\gamma}_{t}^{m},\bar{\gamma}_{t}^{f},\,z_{t}}\big{\\{}R_{t}^{l,i}(z_{t},X^{l,m}_{t},A^{l,m}_{t})$
$\displaystyle+\delta
V_{t+1}^{l,i}(\underline{F}(\underline{\pi_{t}},z_{t},{\gamma}^{l,i}_{t},\tilde{\gamma}_{t}^{l,-i},\bar{\gamma}_{t}^{m},A^{l,m}_{t}),\phi(\underline{\pi_{t}},z_{t},{\gamma}^{l,i}_{t},\tilde{\gamma}_{t}^{l,-i},\bar{\gamma}_{t}^{m},\bar{\gamma}_{t}^{f}),X_{t+1}^{l,i})|\underline{\pi_{t}},z_{t},x^{l,i}_{t}\big{\\}},$
(147a) $\displaystyle\text{where
}\bar{\gamma}_{t}^{m}\in\bar{BR}_{t}^{m}(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,i},{\tilde{\gamma}}_{t}^{l,-i},\bar{\gamma}_{t}^{m},\bar{\gamma}_{t}^{f}),\;\;\;\bar{\gamma}_{t}^{f}\in\bar{BR}_{t}^{f}(\underline{\pi_{t}},z_{t},\gamma_{t}^{l,i},{\tilde{\gamma}}_{t}^{l,-i},\bar{\gamma}_{t}^{m})$
(147b)

Let $t$ be the first instance in the backward recursion when this happens.
This implies $\exists i\ \breve{\gamma}_{t}^{l,i}$ such that

$\displaystyle\mathbb{E}^{\breve{\gamma}^{l,i}_{t},{\tilde{\gamma}}_{t}^{l,-i},\hat{\gamma}_{t}^{m},\hat{\gamma}_{t}^{f},\,\underline{\pi}_{t},z_{t}}\big{\\{}R_{t}^{l,i}(z_{t},X^{l,m}_{t},A^{l,m}_{t})$
$\displaystyle+\delta
V_{t+1}^{l,i}(\underline{F}(\underline{\pi_{t}},z_{t},\breve{\gamma}_{t}^{l,i},{\tilde{\gamma}}^{l,-i}_{t},\hat{\gamma}_{t}^{m,f},A^{l,m}_{t}),\phi(\underline{\pi_{t}},z_{t},\breve{\gamma}_{t}^{l,i},{\tilde{\gamma}}_{t}^{l,-i},\hat{\gamma}_{t}^{m,f}),X_{t+1}^{l,i})|\underline{\pi_{t}},z_{t},x^{l,i}_{t}\big{\\}}$
$\displaystyle>\mathbb{E}^{{\tilde{\gamma}}^{l,m,f}_{t},\,\underline{\pi}_{t},z_{t}}\big{\\{}R_{t}^{l,i}(z_{t},X^{l,m}_{t},A^{l,m}_{t})$
$\displaystyle+\delta
V_{t+1}^{l,i}(\underline{F}(\underline{\pi_{t}},z_{t},\tilde{\gamma}^{l,m}_{t},A^{l,m}_{t}),\phi(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}),X_{t+1}^{l,i})|\underline{\pi_{t}},z_{t},x^{l,i}_{t}\big{\\}}$
(147c) $\displaystyle\text{where
}\hat{\gamma}_{t}^{f}\in\bar{BR}_{t}^{f}(\hat{\gamma}^{l,i}_{t},{\tilde{\gamma}}_{t}^{l,-i},\hat{\gamma}_{t}^{m}),\hat{\gamma}_{t}^{m}\in\bar{BR}_{t}^{f}(\underline{\pi_{t}},z_{t},\breve{\gamma}^{l,i}_{t},{\tilde{\gamma}}_{t}^{l,-i},\hat{\gamma}_{t}^{m},\hat{\gamma}_{t}^{f})$
(147d)

This implies for
$\hat{\sigma}^{l,i}_{t}(\cdot|z_{1:t},a_{1:t-1}^{l,m},x_{1:t-1}^{l,i},\cdot)=\hat{\gamma}_{t}^{l,i}$,

$\displaystyle\mathbb{E}^{\tilde{\sigma}_{t:T}^{l,m,f},\underline{\pi_{t}}}\big{\\{}\sum_{n=t}^{T}R_{n}^{l,i}(Z_{n},X^{l,m}_{n},A^{l,m}_{n})\big{\lvert}\underline{\pi_{t}},z_{1:t},a_{1:t-1}^{l,m},x_{1:t}^{l,i}\big{\\}}$
$\displaystyle=\mathbb{E}^{\tilde{\sigma}_{t}^{l,m,f},\underline{\pi_{t}}}\big{\\{}R_{t}^{l,i}(Z_{t},X^{l,m}_{t},A^{l,m}_{t})+\mathbb{E}^{\tilde{\sigma}_{t:T}^{f}\tilde{\sigma}_{t:T}^{l},\underline{\pi_{t}},z_{t}}$
$\displaystyle\big{\\{}\sum_{n=t+1}^{T}R_{n}^{l,i}(Z_{n},X^{l,m}_{n},A^{l,m}_{n})\big{\lvert}\underline{\pi}_{t},z_{1:t},\phi(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}),a^{l,m}_{1:t-1},A^{l,m}_{t},x_{1:t}^{l,i},X_{t+1}^{i}\big{\\}}\big{|}\underline{\pi}_{t},z_{1:t},a_{1:t-1}^{l,m},x_{1:t}^{l,i}\big{\\}}$
(147e)
$\displaystyle=\mathbb{E}^{\tilde{\sigma}_{t}^{l,m,f},\,\underline{\pi_{t}}}\big{\\{}R_{t}^{l,i}(Z_{t},X^{l,m}_{t},A^{l,m}_{t})+\mathbb{E}^{\tilde{\sigma}_{t+1:T}^{l,m,f},\underline{F}(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}^{l,f},A^{l,f}_{t})}$
$\displaystyle\big{\\{}\sum_{n=t+1}^{T}R_{n}^{l,i}(Z_{n},X^{l,m}_{n},A^{l,m}_{n})\big{\lvert}\underline{\pi_{t}},z_{1:t},\phi(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}),a^{l,m}_{1:t-1},A^{l,m}_{t},x_{1:t}^{l,i},X_{t+1}^{i}\big{\\}}\big{|}\underline{\pi_{t}},z_{1:t},a_{1:t-1}^{l,m},x_{1:t}^{l,i}\big{\\}}$
(147f)
$\displaystyle=\mathbb{E}^{\tilde{\gamma}^{l,m}_{t},\tilde{\gamma}^{f}_{t}(\cdot|x_{t}^{f}),\,\underline{\pi_{t}}}\big{\\{}R_{t}^{l,i}(Z_{t},X^{l,m}_{t},A^{l,m}_{t})$
$\displaystyle+V_{t+1}^{l,i}(\underline{F}(\underline{\pi_{t}},z_{t},\tilde{\gamma}^{l,m}_{t},A^{l,m}_{t}),\phi(\underline{\pi_{t}},z_{t},\tilde{\gamma}_{t}),X_{t+1}^{l,i})\big{\lvert}\underline{\pi_{t}},x^{l,i}_{t}\big{\\}}$
(147g)
$\displaystyle<\mathbb{E}^{\breve{\gamma}^{l,i}_{t},{\tilde{\sigma}}^{l,-i}_{t},\hat{\sigma}^{m}_{t},\hat{\sigma}^{f}_{t},\,\underline{\pi_{t}}}\big{\\{}R_{t}^{l,i}(Z_{t},X^{l,m}_{t},A^{l,m}_{t})+$
$\displaystyle
V_{t+1}^{l,i}(F({\pi}_{t},z_{t},\breve{\gamma}^{l,i}_{t},{\tilde{\sigma}}^{l,-i}_{t},\hat{\sigma}^{m}_{t},\hat{\sigma}^{f}_{t},A^{l,m}_{t}),\phi(\underline{\pi_{t}},z_{t},\breve{\gamma}^{l,i}_{t},{\tilde{\sigma}}^{l,-i}_{t},\hat{\sigma}^{m}_{t},\hat{\sigma}^{f}_{t}),X_{t+1}^{l,i})\big{\lvert}\underline{\pi_{t}},z_{t},x^{l,i}_{t}\big{\\}}$
(147h)
$\displaystyle=\mathbb{E}^{\breve{\gamma}^{l,i}_{t},{\tilde{\sigma}}^{l,-i}_{t},\hat{\sigma}^{m}_{t},\hat{\sigma}^{f}_{t},\underline{\pi_{t}}}\big{\\{}R_{t}^{l,i}(Z_{t},X^{l,m}_{t},A^{l,m}_{t})+\mathbb{E}^{\tilde{\sigma}_{t+1:T}^{l,m,f},F({\pi}_{t},z_{t},\breve{\gamma}^{l,i}_{t},{\tilde{\sigma}}^{l,-i}_{t},\hat{\sigma}^{m}_{t},\hat{\sigma}^{f}_{t},A^{l,m}_{t})}$
$\displaystyle\big{\\{}\sum_{n=t+1}^{T}R_{n}^{l,i}(Z_{n},X^{l,m}_{n},A^{l,m}_{n})\big{\lvert}z_{1:t},\phi(\underline{\pi_{t}},z_{t},\breve{\gamma}^{l,i}_{t},{\tilde{\sigma}}^{l,-i}_{t},\hat{\sigma}^{m}_{t},\hat{\sigma}^{f}_{t}),a^{l,m}_{1:t-1},A^{l,m}_{t},x_{1:t}^{l,i},X_{t+1}^{l,i}\big{\\}}\big{|}\underline{\pi}_{t},z_{1:t},a_{1:t-1}^{l,m},x_{1:t}^{l,i}\big{\\}}$
(147i)
$\displaystyle=\mathbb{E}^{\breve{\sigma}^{l,i}_{t},{\tilde{\sigma}}^{l,-i}_{t},\tilde{\sigma}_{t+1:T}^{l},\hat{\sigma}^{m}_{t},\tilde{\sigma}_{t+1:T}^{m}\hat{\sigma}^{f}_{t},\tilde{\sigma}_{t+1:T}^{f}\underline{\pi_{t}}}\big{\\{}\sum_{n=t}^{T}R_{n}^{l,i}(Z_{n},X^{l,m}_{n},A^{l,m}_{n})\big{\lvert}\underline{\pi_{t}},z_{1:t},a_{1:t-1}^{l,m},x_{1:t}^{l,i}\big{\\}},$
(147j)

where (147f) follows from Lemma 11, (147g) follows Lemma 10, (147h) follows
from (147c) and the definition of $\hat{\sigma}_{t}^{f}$, (147i) follows from
Lemma 9, (147j) again follows from Lemma 11. However, this leads to a
contradiction since $(\tilde{\sigma}^{l,m,f},z)$ is an SMFE-ML of the game.

∎

## References

  * [1] L. S. Shapley, “Stochastic games,” _Proceedings of the national academy of sciences_ , vol. 39, no. 10, pp. 1095–1100, 1953.
  * [2] K. Iyer, R. Johari, and M. Sundararajan, “Mean field Equilibria of dynamic auctions with learning,” _Management Science_ , vol. 60, no. 12, pp. 2949–2970, dec 2014. [Online]. Available: http://pubsonline.informs.org.https//doi.org/10.1287/mnsc.2014.2018http://www.informs.org
  * [3] D. Bergemann and M. Said, “Dynamic Auctions: A Survey,” _SSRN Electronic Journal_ , may 2010. [Online]. Available: https://papers.ssrn.com/abstract=1606892
  * [4] S. R. Etesami and T. Başar, “Dynamic Games in Cyber-Physical Security: An Overview,” _Dynamic Games and Applications 2019 9:4_ , vol. 9, no. 4, pp. 884–913, jan 2019. [Online]. Available: https://link.springer.com/article/10.1007/s13235-018-00291-y
  * [5] P. Visudhiphan and M. D. Ilic, “Dynamic games-based modeling of electricity markets,” _IEEE Engineering Society, Winter Meeting_ , vol. 1, pp. 274–281, 1999.
  * [6] T. J. Boonen, A. A. Pantelous, and R. Wu, “Non-cooperative dynamic games for general insurance markets,” _Insurance: Mathematics and Economics_ , vol. 78, pp. 123–135, jan 2018.
  * [7] J. R. Correa, A. S. Schulz, and N. E. Stier-Moses, “Selfish Routing in Capacitated Networks,” _https://doi.org/10.1287/moor.1040.0098_ , vol. 29, no. 4, pp. 961–976, nov 2004. [Online]. Available: https://pubsonline.informs.org/doi/abs/10.1287/moor.1040.0098
  * [8] E. Meigs, F. Parise, A. Ozdaglar, and D. Acemoglu, “Optimal dynamic information provision in traffic routing,” jan 2020. [Online]. Available: https://arxiv.org/abs/2001.03232v1
  * [9] S. Adlakha, R. Johari, and A. Goldsmith, “Competition in Wireless Systems via Bayesian Interference Games,” _Mechanisms and Games for Dynamic Spectrum Allocation_ , vol. 9781107034, pp. 32–56, sep 2007. [Online]. Available: https://arxiv.org/abs/0709.0516v1
  * [10] D. Vasal and A. Anastasopoulos, “Decentralized Bayesian learning in dynamic games,” _CoRR_ , vol. abs/1607.06847, 2016. [Online]. Available: http://arxiv.org/abs/1607.06847
  * [11] T. N. Le, V. Subramanian, and R. Berry, “The impact of observation and action errors on informational cascades,” in _Decision and Control (CDC), 2014 IEEE 53rd Annual Conference on_ , Dec 2014, pp. 1917–1922.
  * [12] T. Basar and G. Olsder, _Dynamic Noncooperative Game Theory, 2nd Edition_. Society for Industrial and Applied Mathematics, 1998.
  * [13] J. Filar and K. Vrieze, _Competitive Markov decision processes_. Springer Science & Business Media, 2012.
  * [14] E. Maskin and J. Tirole, “Markov perfect equilibrium: I. observable actions,” _Journal of Economic Theory_ , vol. 100, no. 2, pp. 191–219, 2001.
  * [15] M. Huang, R. P. Malhamé, and P. E. Caines, “Large population stochastic dynamic games: closed-loop mckean-vlasov systems and the nash certainty equivalence principle,” _Communications in Information & Systems_, vol. 6, no. 3, pp. 221–252, 2006.
  * [16] J.-M. Lasry and P.-L. Lions, “Mean field games,” _Japanese Journal of Mathematics_ , vol. 2, no. 1, pp. 229–260, 2007.
  * [17] J.-M. Lasry, P.-L. Lions, and O. Guéant, “Application of mean field games to growth theory,” 2008.
  * [18] O. Guéant, J.-M. Lasry, and P.-L. Lions, “Mean field games and applications,” in _Paris-Princeton lectures on mathematical finance 2010_. Springer, 2011, pp. 205–266.
  * [19] J. Subramanian and A. Mahajan, “Reinforcement learning in stationary mean-field games,” in _International Conference on Autonomous Agents and Multiagent Systems (AAMAS)_ , 2019.
  * [20] M. Huang and Y. Ma, “Mean field stochastic games: Monotone costs and threshold policies,” in _2016 IEEE 55th Conference on Decision and Control (CDC)_. IEEE, 2016, pp. 7105–7110.
  * [21] ——, “Mean field stochastic games with binary action spaces and monotone costs,” _arXiv preprint arXiv:1701.06661_ , 2017.
  * [22] ——, “Mean field stochastic games with binary actions: Stationary threshold policies,” in _2017 IEEE 56th Annual Conference on Decision and Control (CDC)_. IEEE, 2017, pp. 27–32.
  * [23] S. Adlakha, R. Johari, and G. Y. Weintraub, “Equilibria of dynamic games with many players: Existence, approximation, and market structure,” _Journal of Economic Theory_ , vol. 156, pp. 269–316, 2015.
  * [24] V. DeMiguel and H. Xu, “A Stochastic Multiple-Leader Stackelberg Model: Analysis, Computation, and Application,” _https://doi.org/10.1287/opre.1080.0686_ , vol. 57, no. 5, pp. 1220–1235, jun 2009. [Online]. Available: https://pubsonline.informs.org/doi/abs/10.1287/opre.1080.0686
  * [25] P. Cardaliaguet, F. Delarue, J.-M. Lasry, and P.-L. Lions, “The master equation and the convergence problem in mean field games,” _Annals of Mathematics Studies_ , vol. 2019-Janua, no. 201, pp. 1–222, sep 2015. [Online]. Available: https://arxiv.org/abs/1509.02505v1
  * [26] D. Vasal, A. Sinha, and A. Anastasopoulos, “A systematic process for evaluating structured perfect bayesian equilibria in dynamic games with asymmetric information,” _IEEE Transactions on Automatic Control_ , 2018\.
  * [27] D. Vasal and A. Anastasopoulos, “Decentralized Bayesian learning in dynamic games,” in _Allerton Conference on Communication, Control, and Computing_ , 2016. [Online]. Available: https://arxiv.org/abs/1607.06847
  * [28] ——, “Signaling equilibria of dynamic LQG games with asymmetric information,” in _Conference on Decision and Control_ , 2016.
  * [29] D. Vasal, “Sequential Decomposition of Mean-Field Games,” in _Proceedings of the American Control Conference_ , vol. 2020-July. Institute of Electrical and Electronics Engineers Inc., jul 2020, pp. 5388–5393.
  * [30] D. Vasal, R. K. Mishra, and S. Vishwanath, “Sequential decomposition of graphon mean field games,” _Proceedings of the American Control Conference_ , vol. 2021-May, pp. 730–736, jan 2020. [Online]. Available: https://arxiv.org/abs/2001.05633v1
  * [31] D. Vasal, “Stochastic Stackelberg games,” may 2020. [Online]. Available: http://arxiv.org/abs/2005.01997
  * [32] D. Vasal and R. Berry, “Master Equation for Discrete-Time Stackelberg Mean Field Games with single leader,” _arxiv preprint arXiv:2201.05959v1_ , jan 2022. [Online]. Available: https://arxiv.org/abs/2201.05959v1
  * [33] A. Nayyar, A. Mahajan, and D. Teneketzis, “Decentralized stochastic control with partial history sharing: A common information approach,” _Automatic Control, IEEE Transactions on_ , vol. 58, no. 7, pp. 1644–1658, 2013.
  * [34] Y.-C. Ho, “Team decision theory and information structures,” _Proceedings of the IEEE_ , vol. 68, no. 6, pp. 644–654, 1980.
  * [35] D. Vasal, A. Sinha, and A. Anastasopoulos, “A systematic process for evaluating structured perfect bayesian equilibria in dynamic games with asymmetric information,” _IEEE Transactions on Automatic Control_ , vol. 64, no. 1, pp. 81–96, Jan 2019.