capbtabboxtable[][]

# Multi-step Problem Solving Through a Verifier: An Empirical Analysis on
Model-induced Process Supervision

Zihan Wang1 Yunxuan Li2 Yuexin Wu2 Liangchen Luo2 Le Hou2 Hongkun Yu2 Jingbo
Shang1
1University of California, San Diego 2Google  This work was done during the
author’s internship at Google. Correspondence<EMAIL_ADDRESS>
###### Abstract

Large language models often struggle to generate error-free solutions in
complex problem-solving scenarios. To address this, recent advancements have
adopted a reasoner-verifier framework, where a verifier model is trained in a
supervised fashion, to evaluate intermediate solution steps generated by a
reasoning model. However, this “process supervision” approach requires
obtaining ground truth annotations on intermediate solution steps to train the
verifier model, which is resource-intensive and expensive. In this paper, we
introduce Model-induced Process Supervision (MiPS), a novel method for
automating data curation. MiPS annotates an intermediate step by sampling
completions of this solution through the reasoning model, and obtaining an
accuracy defined as the proportion of correct completions. Errors in the
reasoner would cause MiPS to underestimate the accuracy of intermediate steps,
therefore, we suggest and empirically show that verification focusing on high
predicted values of the verifier shall be preferred over that of low predicted
values, contrary to prior work. Our approach significantly improves the
performance of PaLM 2 on math and coding tasks (accuracy +0.67% on GSM8K,
+4.16% on MATH, +0.92% on MBPP compared with an output verifier).
Additionally, our study demonstrates that the verifier exhibits strong
generalization ability across different reasoning models.

##  1 Introduction

Multi-step problem solving (e.g., math problems and coding challenges)
showcases the capabilities of machine intelligence. While researchers have
shown that model- and data-upscaling still hold powerful for large language
models (LLMs) on multi-step problem solving Achiam et al. (2023); Touvron et
al. (2023); Team Gemini et al. (2023); Huang et al. (2022); Azerbayev et al.
(2023); Luo et al. (2023a); Yu et al. (2023a), even the state-of-the-art LLMs
still produce easily observable mistakes. Furthermore, standard fine-tuning on
the training dataset or model generated solutions directly does not yield
consistent and significant improvements Luo et al. (2023a); Yu et al. (2023a);
Ni et al. (2022). In Tab. 2, we show the test set performance of PaLM 2-S on a
math problem dataset, GSM8K Cobbe et al. (2021), before and after task-
specific finetuning. It is observed that such fine-tuning does not exploit the
model’s full potential, as the performance falls much behind using a standard
self-consistency approach Wang et al. (2022) and especially when considering
that the model very likely generates a correct-answer solution to the problem.

Self-consistency can be seen as an inference-time technique where the goal is
to pick one model-generated solution among many. This broadly falls under a
reasoner-verifier paradigm (Fig. 2). In particular, the reasoner model
generates solution(s) given a problem to solve and the verifier model makes
predictions to the solutions, selecting the solution with the highest
predicted value.

Training a verifier in a supervised fashion has demonstrated strong
performance in both coding and math language problems. Cobbe et al. (2021)
showed that by simply gathering correct and incorrect solutions to train a
binary classification model and using such model to pick the highest
confidence solution generated by the reasoner during inference time, the
accuracy can be improved significantly. More recent studies suggest that
verifying on intermediate steps could offer better guidance than training
solely on the whole solutions Li et al. (2022); Uesato et al. (2022); Paul et
al. (2023); Lightman et al. (2023); Feng et al. (2023); Yu et al. (2023b); Liu
et al. (2023a); Wang et al. (2023). As such, verifiers trained (and applied)
on intermediate steps are called process supervised verifiers (PSV), whereas
those trained on whole solutions are called output supervised verifiers (OSV).
In prior work, process supervision data is either obtained by an ad-hoc
algorithm Li et al. (2022); Paul et al. (2023), or through expensive human
annotations Uesato et al. (2022); Lightman et al. (2023), lacking an automatic
and generic way of constructing of annotations of intermediate solutions.

Figure 1: An illustration of the reasoner-verifier paradigm. The verifier
predicts scores for the solutions generated by the reasoner, and selectes the
solution with the highest score.

Method | Acc.
---|---
Base, FT on Train (2K) | 61.6
FT on Train (7K) | 62.9
FT on Generated ($\sim$100K) | 66.0
Self-consistency (Base, 32 paths) | 77.1
At Least 1 Solve (Base, 32 paths) | 95.6

Figure 2: We fine-tune PaLM 2-S on GSM8K. The base model is tuned with 2K
training data to adhere with the problem format. Figure 3: The Model-induced
Process Supervision (MiPS) data construction method we introduce in this work.
By completing a intermediate solution with a reasoner several times, we can
obtain the percentage value of these completions being correct, which is used
to annotated the step-wise solutions.

Training verifier models require solution wise or step wise labels, which is
expensive to collect. There have been a series of work following an LLM-as-a-
verifier approach where an off-the-shelf LLM is employed to judge the
solutions through prompting Madaan et al. (2023); Kim et al. (2023); Pan et
al. (2023). However, while such work may have seen improvements on language
tasks, they haven’t been very successful in math or coding problems Huang et
al. (2023); Luo et al. (2023b).

In conclusion, to achieve optimal quality, training data is needed for
building a strong verifier model. On the other hand, manually collecting
solution verification labels is expensive and non-scalable. In this work, we
propose to use Monte Carlo Sampling on the completions of the intermediate
solutions to obtain step-wise training annotations (Fig. 3). Specifically, for
each intermediate solution, we complete the solution with the reasoner several
times through a sample decoding mechanism, and the percentage of the completed
solutions being correct is referred to as the correctness of the solution.
Such correctness scores can be used to train a PSV. Because of the nature of
involving the reasoning model’s completion on the intermediate solutions, we
call the construction of this data Model-induced Process Supervision (MiPS).
While such an idea is also explored in a concurrent work Wang et al. (2023),
we supplement with analysis of using MiPS constructed data. We found out that
because the reasoner model, which completes the solutions, is not perfect, the
noises it introduces would affect the design choices of using the process
supervised verifier:

  * •

We analyzed various ways to merge step-wise prediction scores to a single
score value (we refer to this process as using an aggregation function) when
using the verifier. Prior work used an aggregation function that focuses on
low predicted scores that worked well for PSV trained on noise-free human
annotated data Lightman et al. (2023). For the noisy MiPS data, we suggest
aggregation functions that focuses on high predicted scores.

  * •

We re-examine the usefulness of process supervision by isolating the trained
PSV and studying the benefits of incorporating the score from each
intermediate step during verification. Our results reveal that (1) the
verification scores from later intermediate steps are indeed useful even for a
PSV trained on the noisy MiPS data, however, the earlier step scores could
hurt the verification, depending on the aggregation function; and (2) only
using the PSV predicted score of the last step, in similar fashion as OSV, can
sometimes be much better than OSV itself, indicating process supervision data
can regularize OSV training.

  * •

We show that verifiers trained on MiPS data generated by a reasoner can
transfer to validate solutions by a different (and more competent) reasoner.
This indicates that MiPS would not produce verifiers that are overly biased
towards mistakes of the reasoner that generated the data.

Following in this paper, we will provide a more complete review of related
works, a precise definition of our method, and empirical results of the method
and analysis on two math problem dataset and one coding dataset. The
contributions of the paper is mainly (1) we propose MiPS to construct process
supervision data automatically for training process supervision verifiers; (2)
we extend the evaluation of problem solving verifiers to coding problems; (3)
we provide empirical analysis on design choices and properties of the trained
verifier from MiPS data.

##  2 Related Works

The advances of problem solving of LLMs can be broadly chracterized into two
regimes, first by training a better reasoning model and the second by
validating the solution from the reasoning model at inference time.

Pre-training/Fine-tuning Better Reasoners. Standard training recipes also
transfer to training better reasoners for problem solving. During pre-
training, larger model sizes and training compute yields an LLM that is more
competent in multiple aspects, including language abilities and problem
solving (Achiam et al., 2023; Touvron et al., 2023; Anil et al., 2023, inter
alia). Within fine-tuning, it is also observed that transfer learning
Azerbayev et al. (2023) from a pile of generic math datasets, training on an
augmented dataset on failure examples or diverse statements Huang et al.
(2022); Luo et al. (2023a); Yu et al. (2023a); Ni et al. (2022) leads to
improvements. Despite these approaches, it is apparent that (1) the state-of-
the-art LLM still can fail at simple mistakes during multi-step problem
solving and (2) the improvement of a simple verfication method by majority
voting (self consistency Wang et al. (2022)) is still significant upon fine-
tuning. Therefore, the exploration of verifiers to validate and pick the
solutions is necessary.

Validating Through LLM-as-a-verifier. There have been numerous attempts on
using the LLM reasoner itself to correct and validate its generated solutions.
Madaan et al. (2023); Kim et al. (2023) and many methods surveyed in Pan et
al. (2023) broadly follow the strategy where the LLM validates and provides
feedback to the generated solutions through prompting. Huang et al. (2023) and
Luo et al. (2023b) revisited these methods and found that LLMs do not serve as
good verifiers for equally competent solutions at the time being, and such
methods improves marginally on math word problems.

Validating Through Trained Verifiers. In contrast, verifiers trained on a
human labelled dataset does show significant improvements Cobbe et al. (2021);
Uesato et al. (2022); Lightman et al. (2023). Importantly, Lightman et al.
(2023) showed that on a challenging competition-level mathematics problem set
Hendrycks et al. (2021), verifiers trained on annotated intermediate solutions
(PSV) surpasses verifiers trained on final solutions by a large margin, and
both substantially better than self-consistency. Other analysis also emphasize
on the importance of step-wise feedback: Uesato et al. (2022) showed that PSV
selects solutions that are more accurate in their reasonings and Yao et al.
(2023); Feng et al. (2023); Liu et al. (2023b), inter alia, showed that during
decoding, LLMs can be guided towards better solutions step-by-step. We believe
that improving the training of a PSV, and especially, identifying a scalable
solution to generate the process supervision data, is of imminent importance.
Therefore, in this work, we identify an automatic and generic solution to
generate process supervision data (MiPS), and conducted detailed analysis
centered on the noises of this automatic process.

Math-Shepherd. Coincidentally, such an automatic process supervision data
curation method was studied concurrently and independently by Wang et al.
(2023). We share a generally similar methodology with their work, with a few
minor design differences we highlight in later sections. The empirical results
of MiPS is similar on the two datasets we share (GSM8K and MATH) despite using
different, but about competent, LLMs. Their work extended training the
verifier by applying it to fine-tune the reasoner through reinforcement
learning, while our work included an additional coding dataset (MBPP) and
provided analysis on the design choices of using the verifier, addressing the
data noises. We believe these two works compliment each other.

##  3 Model-induced Process Supervision

We consider the reasoner-verifier framework where we start with a fairly
competent reasoner on a task, generate verifier training data on a given set
of problems with the reasoner, and train a verifier on the data to validate
some new generated solutions by a reasoner. We first introduce discuss Model-
induced Process Supervision, our data curation method that automatically
creates process supervision data (annotations of accuracy of intermediate
solutions). Then, we discuss the details about the verification process.

###  3.1 Scope

We start our introduction of MiPS with the requirements it is bound to: there
should be a solution checker and the solutions could be decomposed into
intermediate steps.

Without a solution checker, MiPS might require as much human annotation power
as the original process supervision annotation schema Lightman et al. (2023).
Fortunately, many tasks have a checker. For example, several math tasks are
written in the form of multi-class classification (MMLU Hendrycks et al.
(2020), MATHQA Amini et al. (2019)) or open-ended generation but with a
special format that supports automatic parsing and checking (GSM8K Cobbe et
al. (2021), MATH Hendrycks et al. (2021)). For coding problems, while the
generated code is not directly verifiable, a common approach is to execute it
on a series of test cases designed for the problem, and the code is only
correct if it passes all the test cases (MBPP Austin et al. (2021), HumanEval
Chen et al. (2021)).

Step-decomposition requires the solutions to be a multi-step problem that can
be programmatically broken into intermediate solutions. This is also often the
case. For example, in the math problems, the common approach is to treat a
valid step as each individual line in the solution and the decomposition is
simply dividing at the line breaks.

###  3.2 Obtaining MiPS data

MiPS constructs process supervision data through Monte Carlo sampling. First,
we employ a reasoner model $r_{g}$ to generate a fix number of $n_{g}$
solutions for each problem, using temperature based decoding with a
temperature of $t_{g}$. Then, for each solution, we decompose them into
individual steps. After that, for each intermediate solution containing a
prefix list of steps, we employ a reasoner model $r_{mc}$ to generate again a
fix number of $n_{mc}$ solutions, with a termperature of $t_{mc}$, completing
the intermediate solution. For each completed intermediate solution, we
calculate the percentage (out of $n_{mc}$) of them being correct, and these
correctness values comprises the MiPS data. In all experiments in this paper,
we consider $r_{g}=r_{mc}$, namely, the reasoner model that is used to
estimate the intermediate solution’s correctness is the same model that
generates the solution data. This is particularly the most challenging case
for MiPS, otherwise, using a more capable reasoner for the completion would
enjoy a reduction of noise in MiPS data.

###  3.3 Training an Output Supervised Verifier (OSV)

We diverge a bit to illustrate how one would train a verifier from output
supervision, which would later aid in explaining how the process supervised
verifier is trained. The training data for OSV are the generations from the
reasoner $r_{g}$ with the same temperature value $t_{g}$. The verifier itself
is nothing different from a standard language model.

###  3.4 Training a Process Supervised Verifier (PSV)

The main differences of training PSV from OSV are:

  * •

To enable predicting a score at each step in the solution, we mark the last
token of the each step (e.g., if each step is represented as a single line,
the last token will be the new line token), and optimize step-wise predictions
at each step at the same time. During inference, we would also obtain a score
for each step in a solution.

  * •

While for the output supervision data, or human labelled process supervision
data, the score is either 0 or 1, for MiPS data, the correctness scores are
percentage values. The training objective considered in this work is to learn
the percentage values $c_{i}$ for the $i$th step in the solution directly,
through the same binary cross entropy loss. However, we note that it is
possible to consider a different learning objective. For example, Wang et al.
(2023) considered learning a binarized score:

$\tilde{c_{i}}=\begin{cases}\text{1,}&\quad\text{if }c_{i}>0.0\\\
\text{0.}&\quad\text{otherwise.}\\\ \end{cases}$

###  3.5 Aggregating Step-wise Predictions

Table 1: We show the statistics of the datasets we use in this paper. The average number of steps is depicted with a granuarity of 0.5, using PaLM 2-S for GSM8K and MBPP, and PaLM 2-L for MATH. We note that these are not the most standard data splits, for reasons explained in Sec 4.2.  Dataset | GSM8K | MATH | MBPP
---|---|---|---
Domain | math | math | coding
Fine-tuning # Data | 2000 | 4000 | 0
Verification Training # Data | 5000 | 8000 | 384
Testing # Data | 1319 | 500 | 500
Average Steps | 4.5 | 11.0 | 7.0

The trained verifier is used to score the solutions generated by the reasoner.
For OSV, the verifier prediction can be directly used as the score for the
solution. For PSV, the verifier predictions are a list of predicted
probabilities $p_{1},p_{2},\ldots,p_{n}$, one for each step in the solution.
Aggregating the predictions into a final score is necessary. Lightman et al.
(2023) considered two aggregation functions:

$\begin{split}&\texttt{min}=\min\\{p_{1},p_{2},\ldots,p_{n}\\},\\\
&\texttt{sum\\_logprob}=\sum_{i=1}^{n}\log
p_{i}=\log\prod_{i=1}^{n}p_{i},\end{split}$

They claimed that both are equivalently good aggregation functions. In later
analysis, we show that for MiPS data, these two functions are underperforming
for the trained verifier, whereas some tweaks

$\begin{split}&\texttt{max}=\max\\{p_{1},p_{2},\ldots,p_{n}\\},\\\
&\texttt{sum\\_logit}=\sum_{i=1}^{n}\log\frac{p_{i}}{1-p_{i}},\\\
&\texttt{mean\\_odd}=\frac{\sum_{i=1}^{n}\frac{p_{i}}{1-p_{i}}}{n},\end{split}$

performs much better. We analyze a much larger set of aggregation functions
and suggest that the noise in the MiPS data causes the discrepancy.

##  4 Analysis

(a) GSM8K, PaLM 2-S (b) GSM8K, PaLM 2-L (c) MATH, PaLM 2-L * (d) MBPP base
model

Figure 4: We apply the trained output- and process-supervised verifiers on
various combinations of model and datasets. No verification and self
consistency are also shown, wherever applicable. We use the default training
objective that directly learns the estimate accuracies and the max aggregation
function for the process verifier. In the x-axis, we vary the number of
generated solutions to apply the verifier on, and in the y-axis we plot the
performance (accuracy %). The standard deviation is also given. As a
reference, we note that the purple line, representing the average performance
of the generated solutions of the reasoner without any verification, matches
the expectation to be an (almost) flat horizontal line with decreasing
standard deviation. *While the reasoner that generates MiPS data and the
reasoner that the verifier validates on is PaLM 2-L, the verifier is trained
from a PaLM 2-S.

###  4.1 Models

In our experiments, we consider two LLMs, PaLM 2-S and PaLM 2-L Anil et al.
(2023) to conduct our experiments on. We intend to understand the capability
of MiPS data and analyze design choices of the verifier when trained on it. A
concurrent work Wang et al. (2023) conducted a similar experiment on a
different set of LLMs, namely LLama2, LLemma, Mixtral, and Deepseek Touvron et
al. (2023); Azerbayev et al. (2023); Jiang et al. (2024); Bi et al. (2024).

###  4.2 Datasets

We use two math datasets and one coding dataset for evaluations in this paper.

  * •

GSM8K Cobbe et al. (2021) is a dataset of grade school math problems. The
solution is given in a one-line-per-step format with an exact numerical answer
in the last line in the format of $\\#\\#\\#\\#\\{\text{answer}\\}.$ To
enforce the reasoner following this format, we use the first 2000 instances in
its training set to fine-tune the reasoner model to follow such a format. The
solutions to fine-tune are from the training set. We use the coming $5000$
data to train the verifier and evaluate the verifier on solutions generated by
the reasoner on the test set.

  * •

MATH Hendrycks et al. (2021) is also a math word problems dataset. It consists
of math problems of high school math competitions. The solutions are given in
a format that mixes latex code and natural language. A dedicated solution
checker was developed Hendrycks et al. (2021); Lightman et al. (2023). While
the dataset itself does not resemble steps into different lines, we prompted
GPT-4 to break down the reference solutions into one step per line, and fine-
tuned the reasoner on the line separated dataset to make it follow the format.
We use the test split suggested in Lightman et al. (2023).

  * •

MBPP is an entry-level Python programming dataset. The questions are coding
challenges along with a test case that defines the function format and the
solutions are Python code that is expected to solve several hidden test cases.
We treat each individual line in the generated code as a step. For languages
like Python, this resembles one statement per step. Due to the small dataset
size, we can not afford to fine-tune the reasoner model, and decide to use 3
prompts in the validation split as in context examples to make sure the model
generates code in the expected format.

Table 1 contains detailed statistics about the datasets.

###  4.3 Settings

Throughout the paper, we choose to use a temperature value of
$r_{g}=r_{mc}=0.7$ for both constructing MiPS and generating solutions on the
test set. The number of generations for constructing MiPS $n_{g}$ is set to 32
for GSM8K and MBPP, and 8 for MATH. The number of completions $n_{mc}$ is also
32 for GSM8K and MBPP, and 8 for MATH. For GSM8K, we experiment with both PaLM
2-S and PaLM 2-L in the reasoner-verifier framework. For MATH, due to compute
constraints, the reasoner we use is the PaLM 2-L, and the verifier trained is
the PaLM 2-S. For MBPP, we find marginal differences in performance between
using PaLM 2-S and PaLM 2-L as the reasoner, therefore we experiment only with
the PaLM 2-S. During generation, all models are 8-bit quantized, and during
training, we use a bfloat16 percision. Since MiPS contains an annotation for
each intermediate step in the solution, it is naturally the number of steps
times larger than output supervision. Therefore, we additionally generate more
data to train the OSV. For training, we follow standard reward model training
recipes, with an exception on the training epochs. Similar to Lightman et al.
(2023), we also find it better to train the OSV for 1 epoch and the PSV for 2
epochs. For the OSV on MATH data, we find that training with a small 0.2
epochs (essentially training on less data) is better than training longer. For
all experiments, we report the results of the average of 5 independently
trained verifiers with different random seeds.

###  4.4 Directly Applying MiPS

(a) GSM8K, PaLM 2-S (b) MATH, PaLM 2-L (c) MBPP, PaLM 2-S

Figure 5: For each aggregation function, we show its accuracy on the MiPS data
generated and the accuracy of using it with the PSV trained. We additionally
plot two lines for easier understanding of the figure, a horizontal line
corresponding to the performance of OSV and a vertical line corresponding to
the maximum accuracy achievable by the reasoner on the dataset (some problems
are not solvable by the reasoner among the all solutions we generate).

(a) GSM8K, PaLM 2-S,sum_logit (b) MATH, PaLM 2-L, sum_logit (c) MBPP, PaLM
2-S, sum_logit (d) MATH, PaLM 2-L, sum_logit

(e) MATH, PaLM 2-L, max (f) MATH, PaLM 2-L, sum_odd

Figure 6: We plot the performance of using various aggreagtion functions with
PSV while restricting it to predict only the last $k$ steps or the last $p$
percentage of steps.

We first present the performance of the process verifier trained on MiPS data,
using the default training objective on correctness scores directly, and the
max aggregation function on the three datasets. For this experiment, we varied
the number of solutions to be verified by the verifier from 2 to 128, to
clearly depict the trend of the compared verifier’s performance. The results
are shown in Fig. 4. The plots conveys several pieces of information.

  * •

It is evident that using any verifier improves significantly upon no
verification, matching with the initial assumption that verification plays a
vital role in multi-step problem solving.

  * •

In all experiments, the verifier trained on MiPS using the max aggregation
function showed stronger results than output verification. On GSM8K, the
process verification is better than self consistency. On MATH, the performance
lacks a bit. We note that this may be because we are training a less competent
verifier (PaLM 2-S) than the reasoner (PaLM 2-L). Wang et al. (2023) showed
improvements upon self consistency when the verifier and reasoner are of the
same sizes.

  * •

The high performance of max may be unexpected if one believes max would be
biased towards the first few correct steps of in in correct solution. In later
analysis, we will show that (1) max favors high scores, similar to some other
aggregation functions that perform well, that is preferred on MiPS data; (2)
Due to higher noise in the earlier steps in MiPS data, the prediction scores
of the earlier steps is of lower value (i.e., model confidence is lower), thus
showing less affect to max.

  * •

In all experiments, the sum_logprob (product of probabilities) and min
aggregation function are much worse than max and even using OSV, nevertheless
still providing benefits over not using a verifier.

  * •

For several verifiers, we observe that the performance of the verifier is on a
decreasing trend when the number of generations is high. This is particularly
interesting since the larger the generations, the closer the performance
should approximate the true verification performance. This would indicate that
the while the verifier might identify some correct solutions with high scores,
it also incorrectly predicts some fewer incorrect solutions with even higher
scores, a sign of improper generalization.

From these results, we focus our analysis on two subjects: (1) the choice of
aggregation functions, and (2) the affect of noise on generalization of the
PSV.

###  4.5 Aggregation Functions

Table 2: We train a verifier based on PaLM 2-S and data generated by PaLM 2-S and test its applicability to transfer to validate solutions generated by two different reasoners, PaLM 2-L and gpt-turbo-3.5. A reference score of validing solutions generated by PaLM 2-S is also given. We evaluate this on both GSM8K and MBPP. GSM8K PaLM 2-S | No Verifier | Self Consistency | OSV |  PSV w/ sum_logit
---|---|---|---|---
$\to$ PaLM 2-S | 61.6 | 78.7 | 89.5 | 90.5
$\to$ PaLM 2-L | 80.7 | 89.4 | 92.1 | 92.6
$\to$ gpt-turbo-3.5 | 72.5 | 86.2 | 88.0 | 89.1
MBPP PaLM 2-S | No Verifier | OSV |  PSV w/ sum_logit |  PSV w/ sum_logit (last 3 steps)
$\to$ PaLM 2-S | 41.7 | 56.8 | 54.2 | 57.8
$\to$ PaLM 2-L | 42.4 | 56.6 | 55.0 | 57.4
$\to$ gpt-turbo-3.5 | 66.2 | 67.6 | 67.6 | 68.2

To start with the analysis, we consider ten aggregation functions (sum and
means of log probabilities, probabilities, logits, and odds, and maximum and
minimum value over all steps). We obtain their performance on the MiPS dataset
and plot it with the performance of the verifier using the aggragation
function on the test set (Fig. 5). We first observe that in general, the two
performances have positive correlations, indicating that it is possible to
select a aggregation function on the MiPS dataset and use it during inference.
Second, we notice that both min and sum_logprob have low performances not only
during inference, but also in MiPS. This indicates that the poor performance
of them likely is related to the construct of MiPS. Indeed, we realize that
sum_logprob does not have a high correlation with a correct solution as it
naturally penalizes long solutions. Similarly, for min, the possibility for a
set of solutions to be wrongly verified using min is when the solution with
the largest minimum correctness over all steps turns out to be wrong. This is
not an unlikely event to happen, particularly in hard datasets where the
largest minimum correctness is not high. To clarify these better, we answer
the following questions:

What are common in good aggregation functions for MiPS data? We believe a rule
of thumb of a good aggregation function is a function that values highly
scores highly. Consider two functions, one that values high scores (selects
the solution with the highest high scores, e.g., max) and one that values the
low scores (selects the solutions with the highest low scores, e.g., min). The
first function is wrong only when the highest score solution is incorrect, in
a simple case where there is only one observed step score for each solution,
the probability is $1-s_{\text{max}},$ where $s_{\text{max}}$ is the score.
Similarly, for min, the probability that the solution with the highest minimum
score is wrong is $1-s_{\text{min}}.$ Since $s_{\text{max}}\geq
s_{\text{min}},$ the first function shall be preferred. This is in line with
the observation from Fig. 5 that aggregations of odds and logits are usually
better than that of probabilities and log probabilities.

Why did sum_logprob and min work well in Lightman et al. (2023) and Wang et
al. (2023)? In Lightman et al. (2023), the dataset is constructed by human
identifying all (earliest) incorrect steps, which corresponds to a prediction
of 0 for the verifier (i.e., following the analogy in the previous discussion,
this indicates that $s_{\text{max}}=s_{\text{min}}=1.0$). The min function
would be correct on every instance in the training dataset, and if the
verifier generalizes well, resembles human identification of mistakes on the
test dataset. For Wang et al. (2023), we note two differences during MiPS data
construction. First, their training objective is to predict the binary value
of the correctness score. Second, they are using a different reasoner to
complete the intermediate solutions than the reasoner that generates the
solutions. We leave this difference for further investigations.

The aggregation function analysis would indicate that a good MiPS dataset
score indicates a good aggregation function. This is not completely correct,
since, a contradictory result is that the final step score, which is used to
train the output supervised verifier, achieves 100% accuracy on the training
dataset, while not as good as the process supervised verifier on the test set.
This suggests that the output supervised verifier might encounter some
generalization issues from the data, and MiPS data can help relieve them.

###  4.6 Different Length Aggregations

To understand how the intermediate steps in process supervision help the
verifier model, we illustrate the result of applying an aggregation function
to only the last $k$ steps or last $p$ percentage steps of the solutions in
Fig. 6. In the upper three plots, we show the performance of an aggregation
function sum_logit on the three datasets with $1\leq k\leq 5$. In the lower
three plots, we show the performance of three aggregation functions on MATH
with $10\leq p\leq 100$. We note that only the MATH dataset have solutions
long enough such that looking at a percentage number of steps is sensible.

  * •

For all experiments, the performance increases with more steps considered from
the end, up to some point. This indicates that the verifier predictions on the
final few steps brings in increasing value, suggesting that process scores
indeed is beneficial.

  * •

For most experiments, the performance starts to drop after including some
earlier steps. This suggests that the quality of the predictions for the first
steps are poor. We believe this is because MiPS has a poorer estimation of the
first steps than the last steps, since (1) intuitively it is hard to predict
the correctness of a very early solution even for humans, causing burden for
the verifier to learn, and (2) Monte Carlo samplings that create MiPS data
also tend to suffer from longer horizons.

  * •

For max, the performance does not change significantly across including more
earlier steps. We examined the predicted scores and find the usually earlier
steps are smaller in value, causing it to contribute little to max. This is
another evidence that PSV trained on MiPS data might suffer from noise in the
earlier steps.

  * •

In all experiments, using the last-step process verifier predicted value is
more beneficial than output supervision alone. Recall that this is not because
of the problem of data quantity as we upscaled the data to train the output
verifier. We suggest that this is because the process supervision data is of
more diverse context, thus helping the model in generalization.

###  4.7 Transferring to a Different Reasoner

Finally, we provide an auxiliary experiment to check whether the trained
verifiers would transfer to different reasoning models. We apply the verifiers
trained on reasoning data generated by a PaLM 2-S and use it to valid
solutions generated by stronger reasoners (reasoners having higher No Verifier
accuracy). We find the sum_logit aggregation function working well in this
case. The result is shown in Tab. 2, which shows that the trained verifier
transfers to different and stronger reasoners with a strong validation
ability, indicating that the verifier is not learning something overly
specific to the reasoner that generates the data

##  5 Conclusion

In this work, we introduce MiPS to automatically annotate intermediate
solutions for multi-step problem solving. Such data can be used to train a
process supervised verifier that validates solutions generated by a reasoner.
On two math datasets and one coding dataset, we demonstrated that MiPS
improves the ability of picking the correct solution over an otherwise trained
output supervised verifier. We conduct analysis on the aggregation function
used to pick the solution and suggest that compared to verifiers trained on
human-annotated process supervision, MiPS data trained verifiers prefer
different aggregation functions. We also showed that such verifiers do not
overly emphasize on the mistakes of the reasoner that produced the data, and
can be transferred to different reasoners. Furture work could explore creating
a scalable way to obtain MiPS data for each token in solutions to train a more
competent verifier and use it to tune the reasoner via reinforcement learning.

## References

  * Achiam et al. [2023] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al.  Gpt-4 technical report.  _arXiv preprint arXiv:2303.08774_ , 2023.
  * Touvron et al. [2023] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_ , 2023.
  * Team Gemini et al. [2023] Team Gemini, Rohan Anil, Sebastian Borgeaud, Yonghui Wu, Jean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, et al.  Gemini: a family of highly capable multimodal models.  _arXiv preprint arXiv:2312.11805_ , 2023.
  * Huang et al. [2022] Jiaxin Huang, Shixiang Shane Gu, Le Hou, Yuexin Wu, Xuezhi Wang, Hongkun Yu, and Jiawei Han.  Large language models can self-improve.  _arXiv preprint arXiv:2210.11610_ , 2022.
  * Azerbayev et al. [2023] Zhangir Azerbayev, Hailey Schoelkopf, Keiran Paster, Marco Dos Santos, Stephen McAleer, Albert Q Jiang, Jia Deng, Stella Biderman, and Sean Welleck.  Llemma: An open language model for mathematics.  _arXiv preprint arXiv:2310.10631_ , 2023.
  * Luo et al. [2023a] Haipeng Luo, Qingfeng Sun, Can Xu, Pu Zhao, Jianguang Lou, Chongyang Tao, Xiubo Geng, Qingwei Lin, Shifeng Chen, and Dongmei Zhang.  Wizardmath: Empowering mathematical reasoning for large language models via reinforced evol-instruct.  _arXiv preprint arXiv:2308.09583_ , 2023a.
  * Yu et al. [2023a] Longhui Yu, Weisen Jiang, Han Shi, Jincheng Yu, Zhengying Liu, Yu Zhang, James T Kwok, Zhenguo Li, Adrian Weller, and Weiyang Liu.  Metamath: Bootstrap your own mathematical questions for large language models.  _arXiv preprint arXiv:2309.12284_ , 2023a.
  * Ni et al. [2022] Ansong Ni, Jeevana Priya Inala, Chenglong Wang, Alex Polozov, Christopher Meek, Dragomir Radev, and Jianfeng Gao.  Learning math reasoning from self-sampled correct and partially-correct solutions.  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Cobbe et al. [2021] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al.  Training verifiers to solve math word problems.  _arXiv preprint arXiv:2110.14168_ , 2021.
  * Wang et al. [2022] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou.  Self-consistency improves chain of thought reasoning in language models.  _arXiv preprint arXiv:2203.11171_ , 2022.
  * Li et al. [2022] Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian-Guang Lou, and Weizhu Chen.  Making large language models better reasoners with step-aware verifier.  _arXiv preprint arXiv:2206.02336_ , 2022.
  * Uesato et al. [2022] Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins.  Solving math word problems with process-and outcome-based feedback.  _arXiv preprint arXiv:2211.14275_ , 2022.
  * Paul et al. [2023] Debjit Paul, Mete Ismayilzada, Maxime Peyrard, Beatriz Borges, Antoine Bosselut, Robert West, and Boi Faltings.  Refiner: Reasoning feedback on intermediate representations.  _arXiv preprint arXiv:2304.01904_ , 2023.
  * Lightman et al. [2023] Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe.  Let’s verify step by step.  _arXiv preprint arXiv:2305.20050_ , 2023.
  * Feng et al. [2023] Xidong Feng, Ziyu Wan, Muning Wen, Ying Wen, Weinan Zhang, and Jun Wang.  Alphazero-like tree-search can guide large language model decoding and training.  _arXiv preprint arXiv:2309.17179_ , 2023.
  * Yu et al. [2023b] Fei Yu, Anningzhe Gao, and Benyou Wang.  Outcome-supervised verifiers for planning in mathematical reasoning.  _arXiv preprint arXiv:2311.09724_ , 2023b.
  * Liu et al. [2023a] Bingbin Liu, Sebastien Bubeck, Ronen Eldan, Janardhan Kulkarni, Yuanzhi Li, Anh Nguyen, Rachel Ward, and Yi Zhang.  Tinygsm: achieving> 80% on gsm8k with small language models.  _arXiv preprint arXiv:2312.09241_ , 2023a.
  * Wang et al. [2023] Peiyi Wang, Lei Li, Zhihong Shao, RX Xu, Damai Dai, Yifei Li, Deli Chen, Y Wu, and Zhifang Sui.  Math-shepherd: Verify and reinforce llms step-by-step without human annotations.  _CoRR, abs/2312.08935_ , 2023.
  * Madaan et al. [2023] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al.  Self-refine: Iterative refinement with self-feedback.  _arXiv preprint arXiv:2303.17651_ , 2023.
  * Kim et al. [2023] Geunwoo Kim, Pierre Baldi, and Stephen McAleer.  Language models can solve computer tasks.  _arXiv preprint arXiv:2303.17491_ , 2023.
  * Pan et al. [2023] Liangming Pan, Michael Saxon, Wenda Xu, Deepak Nathani, Xinyi Wang, and William Yang Wang.  Automatically correcting large language models: Surveying the landscape of diverse self-correction strategies.  _arXiv preprint arXiv:2308.03188_ , 2023.
  * Huang et al. [2023] Jie Huang, Xinyun Chen, Swaroop Mishra, Huaixiu Steven Zheng, Adams Wei Yu, Xinying Song, and Denny Zhou.  Large language models cannot self-correct reasoning yet.  _arXiv preprint arXiv:2310.01798_ , 2023.
  * Luo et al. [2023b] Liangchen Luo, Zi Lin, Yinxiao Liu, Lei Shu, Yun Zhu, Jingbo Shang, and Lei Meng.  Critique ability of large language models.  _arXiv preprint arXiv:2310.04815_ , 2023b.
  * Anil et al. [2023] Rohan Anil, Andrew M Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, et al.  Palm 2 technical report.  _arXiv preprint arXiv:2305.10403_ , 2023.
  * Hendrycks et al. [2021] Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt.  Measuring mathematical problem solving with the math dataset.  In _Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2)_ , 2021.
  * Yao et al. [2023] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L Griffiths, Yuan Cao, and Karthik Narasimhan.  Tree of thoughts: Deliberate problem solving with large language models.  _arXiv preprint arXiv:2305.10601_ , 2023.
  * Liu et al. [2023b] Jiacheng Liu, Andrew Cohen, Ramakanth Pasunuru, Yejin Choi, Hannaneh Hajishirzi, and Asli Celikyilmaz.  Making ppo even better: Value-guided monte-carlo tree search decoding.  _arXiv preprint arXiv:2309.15028_ , 2023b.
  * Hendrycks et al. [2020] Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt.  Measuring massive multitask language understanding.  _arXiv preprint arXiv:2009.03300_ , 2020.
  * Amini et al. [2019] Aida Amini, Saadia Gabriel, Peter Lin, Rik Koncel-Kedziorski, Yejin Choi, and Hannaneh Hajishirzi.  Mathqa: Towards interpretable math word problem solving with operation-based formalisms.  _arXiv preprint arXiv:1905.13319_ , 2019.
  * Austin et al. [2021] Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al.  Program synthesis with large language models.  _arXiv preprint arXiv:2108.07732_ , 2021.
  * Chen et al. [2021] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al.  Evaluating large language models trained on code.  _arXiv preprint arXiv:2107.03374_ , 2021.
  * Jiang et al. [2024] Albert Q Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, et al.  Mixtral of experts.  _arXiv preprint arXiv:2401.04088_ , 2024.
  * Bi et al. [2024] Xiao Bi, Deli Chen, Guanting Chen, Shanhuang Chen, Damai Dai, Chengqi Deng, Honghui Ding, Kai Dong, Qiushi Du, Zhe Fu, et al.  Deepseek llm: Scaling open-source language models with longtermism.  _arXiv preprint arXiv:2401.02954_ , 2024.


ifaamas [AAMAS ’23]Proc. of the 22nd International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2023)May 29 – June 2, 2023 London, United
KingdomA. Ricci, W. Yeoh, N. Agmon, B. An (eds.) 2023 2023 ??? Charles
University Prague Czechia Charles University Prague Czechia Charles University
Prague Czechia

# Promoting Non-Cooperation Through Ordering

David Sychrovsky<EMAIL_ADDRESS>,  Sameer Desai
<EMAIL_ADDRESS>and  Martin Loebl<EMAIL_ADDRESS>
###### Abstract.

In many real world situations, like minor traffic offenses in big cities, a
central authority is tasked with periodic administering punishments to a large
number of individuals. Common practice is to give each individual a chance to
suffer a smaller fine and be guaranteed to avoid the legal process with
probable considerably larger punishment. However, thanks to the large number
of offenders and a limited capacity of the central authority, the individual
risk is typically small and a rational individual will not choose to pay the
fine. Here we show that if the central authority processes the offenders in a
publicly known order, it properly incentives the offenders to pay the fine. We
show analytically and on realistic experiments that our mechanism promotes
non-cooperation and incentives individuals to pay. Moreover, the same holds
for an arbitrary coalition. We quantify the expected total payment the central
authority receives, and show it increases considerably.

###### Key words and phrases:

mechanism design; non-cooperation

##  1\. Introduction

In this work, we study a special case of a classic dilemma, how to effectively
enforce a rule in a large population with only a very small number of
enforcing agents. This task is impossible if the large population cooperates
and thus a critical aspect of any suggested mechanism is the promotion of non-
cooperation. A well-known count Dracula way is to make the punishment for
breaking the rule extremely severe. We suggest an alternative mechanism, for a
special case of the dilemma motivated by collecting fines for traffic
violations.

In many large cities, there is a huge number of traffic offences, highly
exceeding the capacity of state employees assigned to manage them. The
assigned state employees should primarily concentrate on serious and
repetitive offenders. However, a large number of minor offences are still to
be settled which makes the former considerably harder. A common practise is
that a smaller fine is assigned in an almost automated way and if an offender
settles this fine then the legal process does not start. Otherwise, the legal
process should start with considerably larger cost for the offender. The
offence is also forgotten after a certain judiciary period.

However, thanks to the limited capacity of state employees, legal processes
for non-repetitive minor traffic offenses are typically enforced in a small
number of cases111For instance, in the city of Prague considerably more than
100 000 such offenses are dismissed every year because the judiciary period
expires.. The individual risk is thus small and a large fraction of the
offenders choose to ignore the fine. In this paper, we propose a simple
mechanism which properly incentives the offenders to pay the fine even under
these conditions.

###  1.1. Main Contribution

In our proposed mechanism, the central authority processes the offenders in a
given order. Each offender is aware of his position in this ‘queue of
offenders’ and has the option of publicly donating money to a fund of traffic
infrastructure or a charity predetermined by the central authority. If their
total donations amount to at least the fine, it is used to settle the offence.
After the judiciary period expires, or if the legal process is started, the
fund retains the individual donation. The central authority periodically sorts
the offenders in ascending order of their average donation, and starts the
legal process with those who paid the least on average.

Compared to processing the offenders in random order, this mechanism increases
the individual risk of some offenders. This incentives them to pay the fine,
which in turn puts others in danger. We show both analytically and on
realistic experiments that under the proposed mechanism, the strategic
behaviour of the offenders is to engage with the mechanism, and quantify the
expected revenue of the charity. Moreover, we show it is not beneficial for
any group of offenders to ignore the mechanism and share the cost of those who
enter the legal process. Finally, we study how the central authority can most
efficiently use its limited capacity to maximize the revenue of the charity.

###  1.2. Related Work

To our best knowledge, the field of non-cooperative mechanism design has not
been studied extensively yet. Our approach is somewhat similar to that of
Chiam C. (2020), where the authors consider a variation of the elimination
game which includes bids.

Our model can also be viewed as a generalization of the stopping games
Kobylanski M. (2013), where participants choose a time to stop bidding and
trade off their gain from outlasting other players for the cost accumulated
over time in the game. In our case, the “prize” won by the lowest paying
participant is cost of entering the legal process.

However, both approaches did not consider the ranking of players, which is at
the core of our mechanism.

##  2\. Problem Definition

Informally, we model the interaction of agents as a game we call Queue. Queue
consists of a finite sequence of Round, in which each agent can choose to pay,
however with some probability they forget and pay nothing. Those who paid at
least the fine in total, or spent enough time in Queue are removed. The rest
is ordered according to the amount they paid on average. A fixed number of
those at the start are then forced to pay a large penalty, and leave Queue.
Let us now define the interaction formally, starting with how Round is
realized.

###  2.1. Round: One Step in Queue

Round is a parametric game $\mathbb{O}$
$(\mathcal{N})$=$\mathbb{O}(\mathcal{N},F,Q,T,k,p)$, where $\mathcal{N}$ is an
ordered subset of agents222The agents are ordered according to their average
payment in ascending order, i.e. those who paid the least on average are
sorted to the front of $\mathcal{N}$., $F\in\mathbb{N}$ is the fine, $Q>F$ is
the cost associated with entering the legal process, $T\in\mathbb{N}$ is the
judiciary period, i.e., the number of Round instances after which agents are
removed, $k\in\mathbb{N}$ is the number of agents forced to pay $Q$ in each
Round, $p\in[0,1]$ is the probability of ignorance.

Each $a\in\mathcal{N}$ is characterized by a triplet $(n_{a},t_{a},m_{a})$ and
his strategy $\pi_{a}$. The triplet corresponds to his observations — his
position $n_{a}$ in $\mathcal{N}$, the number $t_{a}$ of past Round games he
participated in, and his total individual payment $m_{a}$ in the past Round
games.

Round proceeds in three phases

  1. (1)

Each agent $a\in\mathcal{N}$, based on his observation, declares his strategy
for this Round $\pi_{a}\in\Delta^{F+1}$, where $\Delta$ is the probability
simplex. His payment $\mu_{a}$ is then sampled from333This simulates that with
probability $p$, the agent forgot to act in this Round.

$\mu_{a}\sim p\sigma^{0}+(1-p)\pi_{a}(n_{a},t_{a},m_{a}),$ (1)

where $\sigma^{\nu}$ is the pure strategy of paying $\nu$.

  2. (2)

Each agent’s total payment and time is updated

$\displaystyle m_{a}$ $\displaystyle\leftarrow m_{a}+\mu_{a},$ (2)
$\displaystyle t_{a}$ $\displaystyle\leftarrow t_{a}+1,$ (3)

and $\mathcal{N}$ is sorted444We use stable sort, i.e. whenever there is a
tie, the original order is preserved. according to the ratio of current total
payment and time $m_{a}/t_{a}$.

  3. (3)

Some agents are removed from $\mathcal{N}$, which is done in three sub-phases.
We call such agents terminal and denote the set of terminal agents in this
Round as $\mathcal{T}$.

    1. (a)

All agents $a\in\mathcal{N}$ with $m_{a}\geq F$ are removed.

    2. (b)

First $k$ agents in $\mathcal{N}$ have their $m_{a}$ increased by $Q$ and are
removed.

    3. (c)

All agents $a\in\mathcal{N}$ with $t_{a}\geq T$ are removed.

The result of each Round is the ordered set of agents
$\mathcal{N}\setminus\mathcal{T}$, and the set of terminal agents
$\mathcal{T}$. Only the terminal agents are assigned their final utility.

######  Definition  (Utility).

The utility of each agent $a\in\mathcal{T}$ is the negative amount he paid

$u_{a}=-m_{a}.$ (4)

###  2.2. Queue: A Game on Updating Sequences

Formally, Queue is $\mathbb{G}$ = $\mathbb{G}(F,Q,T,k,p,x,x_{0},w)$, where
$F,Q,T,k$ and $p$ have the same meaning as in Section 2.1, $x$ is the number
of entering agents after each Round, $x_{0}$ is the initial size of
$\mathcal{N}$ and $w$ is the horizon, i.e. the number of repetitions of Round.

Queue aggregates Round in the following two simple phases. Starting with
$\mathcal{N}^{1}$ s.t. $|\mathcal{N}^{1}|=x_{0}$, and $m_{a},t_{a}=0$ for each
$a\in\mathcal{N}^{1}$. We repeat them $w$-times.

  1. (1)

The agents in $\mathcal{N}^{t}$ play Round and non-terminal agents proceed to
the next iteration.

$\mathcal{N}^{t+1},\mathcal{T}^{t+1}\leftarrow\mathbb{O}(\mathcal{N}^{t}).$
(5)

  2. (2)

$x$ new agents enter the game

$\mathcal{N}^{t+1}\leftarrow\mathcal{N}^{t+1}\cup X,$ (6)

where $X$ is a set of agents with $m_{a},t_{a}=0$, and $|X|=x$. These new
agents are sorted to the end of $\mathcal{N}^{t+1}$.

 In the last Round, all agents terminate,
$\mathcal{T}^{w}\leftarrow\mathcal{T}^{w}\cup\mathcal{N}^{w}$.

The new agents come from universum $U$. The strategy of all agents is then
given as $\pi=\times_{a\in U}\pi_{a}$. We denote space of all such strategies
as $\Pi$.

Each agents wants to choose strategy $\pi_{a}$, which maximizes their utility
in $\mathbb{G}$ given strategies of other agents $\pi_{-a}$. A strategy
profile $\pi\in\Pi$ is an equilibrium, if no agent can increase his utility.
Formally,

######  Definition  ($\epsilon$-Equilibrium).

$\pi\in\Pi$ is an $\epsilon$-equilibrium of $\mathbb{G}$ if $\forall\
\overline{\pi}\in\Pi$, $\forall t\in\\{1,\dots w\\}$ and $\forall
a\in\mathcal{T}^{t}$,

$\mathbb{E}_{\pi}\left[u_{a}(\pi)\right]\geq\mathbb{E}_{(\overline{\pi}_{a}\pi_{-a})}\left[u_{a}(\overline{\pi}_{a},\pi_{-a})\right]-\epsilon.\hskip
12.91663pt$ (7)

We note that the equilibrium always exists which can be shown by a standard
transformation to a normal form game.

###  2.3. Avalanche Effect

Intuitively, every agent wants to pay as little as possible, while avoiding
paying $Q$. This translate to paying more than the others. However, if all
agents adapt this reasoning, the only option to avoid paying $Q$ is to pay
$F$. We formally show this in Section 3.1

Crucially, not all other agents can use this reasoning thanks to the
probability of ignorance. But as that vanishes, the agents should be
incentivised to pay more. Similarly, if the number of entering agents
increases, so should the total payment. We formally capture this in the
avalanche effect.

######  Definition  (Avalanche effect).

We say that Queue exhibits the avalanche effect if at least one of the
following holds in equilibrium when changing $p$, or $x$.

  1. (1)

The expected terminal payment of all agents is increasing as $p\to 0^{+}$

$\lim_{p\to 0^{+}}\frac{\rm d}{{\rm d}p}\sum_{a\in\mathcal{T}}m_{a}>0.$ (8)

  2. (2)

The expected terminal payment of all agents decreases slower than $1/x$ as
$x\to\infty$

$\lim_{x\to\infty}\sum_{a\in\mathcal{T}}m_{a}=\infty.$ (9)

###  2.4. Division Problem

In our model, the judiciary period is split into $T$ equal time intervals and
sorted at the start of each interval. The central authority can process $kT$
offenders over the judiciary period, and $xT$ will enter the system.

The central authority can influence the system in two ways.

  1. (1)

it can choose how often the sorting takes place, and

  2. (2)

it can virtually split the entering offenders into $g$ groups of size $x/g$,
and process $k/g$ offenders in each.

The Division problem is how to set $T$ and $g$ to maximize the expected
revenue the central authority receives. We refer to the two cases as Time-
Division problem and Group-Division problem respectively.

##  3\. Analytic Solution

As described in Section 1, the individual risk when the central authority
processes the agents in random order is typically small, i.e.
$kQ/|\mathcal{N}|\ll F$. Each agent is also guaranteed to pay
$kQ/|\mathcal{N}|$ if everyone cooperates and shares the costs of those
entering the legal process. Let us begin by showing that this is not the case
in our proposed system. That is, there is no coalition can benefit from
choosing to pay nothing and share the cost of those forced to pay $Q$. In our
setting, this is analogous to coalition proofness.

###### Proposition

Let $\mathcal{A}$ be a set of agents using strategy $\pi_{a}=\sigma^{0}\
\forall a\in\mathcal{A}$, and sharing the cost, i.e. their utility becomes

$\tilde{u}_{a}=-\frac{1}{|\mathcal{A}|}\sum_{i=1}^{w}\sum_{a\in\mathcal{A}\cap\mathcal{T}^{i}}m_{a},\hskip
12.91663pt\forall a\in\mathcal{A}.$

If $\tilde{u}_{a}>0$, then $\exists a^{\prime}\in\mathcal{A}$ s.t.
$a^{\prime}$ can deviate and increase his utility.

###### Proof.

We split the proof into two parts according to how much an individual needs to
contribute.

  1. (1)

$0<\tilde{u}_{a}<Q$: In this situation, not all agents of $\mathcal{A}$ were
forced to pay $Q$. Consider the agent $a^{\prime}\in\mathcal{N}$ who
terminated last. Then, since $a^{\prime}$ paid zero, his original utility is
zero and $\tilde{u}_{a}>u_{a}$. Therefore, $a^{\prime}$ would benefit from
leaving $\mathcal{A}$.

  2. (2)

$\tilde{u}_{a}=Q$: In this case, all agents were forced to enter the legal
process. Any $a\in\mathcal{A}$ would therefore benefit from paying the fine,
since then $u_{a}=F<Q=\tilde{u}_{a}$.

∎

While existence of an analytic solution of Queue remains an open question, we
can find it in certain special cases.

###  3.1. Active participants

Let us first focus on a situation when no agent forgets to participate in
Round, i.e. $p=0$. Then it is easy to see that $\pi_{a}=\sigma^{F}$ is unique
equilibrium. Consider the first agent $a\in\mathcal{N}$ in the first Round,
who chose to pay $\mu_{a}<F$. Then he is forced to pay $Q$, resulting to
utility $u_{a}=-Q-\mu_{a}<-F$. Therefore, switching to paying $F$ is
beneficial and the strategy of paying $\mu_{a}<F$ is not an equilibrium. This
means all agents will pay $F$ in the first Round, and the situation thus
repeat in the following Round.

###  3.2. $w$-Fines: Special Case of Queue

Let us focus on the system without the introduction of the option to donate a
portion of the fine. Thus after scaling currency we can let $F=1$, and there
are only two pure strategies $\sigma^{0},\sigma^{F}$ the agents can take. If
now $T=w$ and no agents are added after each Round $x=0$, we call the game
$w$-Fines.

######  Definition  ($w$-Fines).

Let $w\in\mathbb{N}$, then we refer to reduced Queue
$\mathbb{F}(w,F,Q,k,p,x_{0})=\mathbb{G}(F,Q,w,k,p,0,x_{0},w)$ as $w$-Fines.

We begin by showing a crucial property of $w$-Fines.

###### Lemma

In the $w$-Fines, the expected payment of $\forall a\in\mathcal{N}$ depends
only on the actions of agents in front of $a$.

###### Proof.

If $a$ pays zero, he remains in the Queue and is sorted in front of agents who
were behind him. He is potentially forced to pay $Q$, depending on the actions
of agents in front of him. If he pays $F=1$, he is removed. In either case,
the actions of agents behind $a$ have no impact on his payment. ∎

In each Round, $a\in\mathcal{N}$ has $n_{a}-1$ agents in front of him. Due to
the probability of ignorance, even if all the agents decide to pay, $a$ can
estimate the probability that at most $k-1$ will forget. If that happens, $a$
will be forced to pay $Q$ in this Round. Formally,

######  Definition .

Let $n$ be a positive integer. We denote by $\alpha(p,n,k)$ the probability
that in $n-1$ independent coin tosses with the head probability $p$, the
number of heads is less than $k$.

Since $\alpha$ will be important in the following discussion, we briefly
mention some of its properties.

###### Lemma

Let $k<np$, then $\alpha(p,n+1,k)\leq e^{-\frac{(np-k)^{2}}{2np}}$.

###### Proof.

Let $\xi_{i}$ denote the random variable such that

$\xi_{i}=\begin{cases}1&\text{ w.p. }p,\\\ 0&\text{ otherwise },\end{cases}$

and $\xi^{n}=\underset{i=1}{\overset{n}{\sum}}\xi_{i}$. Thus,
$\mathbb{E}[\xi_{i}]=p$ and $\mathbb{E}[\xi^{n}]=np$. As per the Chernoff
bounds, $\mathbb{P}[\xi^{n}\leq(1-\delta)np]\leq e^{\frac{-\delta^{2}np}{2}}$,
for all $0<\delta<1$. Thus $\alpha(p,n+1,k)=\mathbb{P}[\xi^{n}\leq k]\leq
e^{{-\left(1-\frac{k}{np}\right)^{2}np}/{2}}=e^{-\frac{\left(np-k\right)^{2}}{2np}}$.
∎

###### Proposition

If $\alpha(p,n,k)\leq F/Q\leq\frac{1}{4}$ then $np>k$. Moreover for large
enough $n$, $\alpha(p,n,k)\geq\alpha(p,2n,2k)$.

###### Proof.

For $\gamma\sim B(n,p)$ if $p<1-\frac{1}{n}$, then $\frac{1}{4}<{\rm
Pr}(\gamma\leq np)$ Greenberg and Mohri (2014). Therefore, when
$\frac{1}{4}\geq\frac{F}{Q}$, then $k<np$. Further, we note that Lemma 3.2 is
tight for large enough $np$. Hence, it suffices to prove the proposition for
the upper bound $e^{-\frac{\left(np-k\right)^{2}}{2np}}$ for which the
statement clearly holds. ∎

Finally, we formulate a conjecture that if true, would allow us to extend the
analytic study of the division problem presented below.

For $pn>k$, $\alpha(p,n,k)\geq\alpha(p,n+n/p,2k)$.

####  3.2.1. Single Sorting Instance

We start by analysing the $1$-Fines game, which is equivalent to one Round. In
this case, when an agent is sufficiently far from the start of $\mathcal{N}$,
it is beneficial to pay nothing, while near the start it is beneficial to pay
and avoid paying $Q$. The boundary between the two will prove important.

######  Definition  (Critical strategy).

Let $r\in\mathbb{N}$ be the smallest such that $\alpha(p,r,k)Q\leq F$. Then
$r$ is called critical position.

The critical strategy is

$\pi_{a}^{{\rm crit}}(n_{a},t_{a},m_{a})=\begin{cases}\sigma^{F}&{\rm if}\
\alpha(p,n_{a},k)Q>F,\\\ \sigma^{0}&{\rm otherwise}.\end{cases}$ (10)

We note that $t_{a}=1$ and $m_{a}=0$ $\forall a\in\mathcal{N}$ for $1$-Fines.
We will show that $\pi_{a}^{{\rm crit}}$ is the only equilibrium of the
$1$-Fines. First, we define $\alpha^{\rm crit}$ as the probability with which
an agent is forced to pay $Q$ when all agents follow $\pi_{a}^{{\rm crit}}$.

###### Proposition

Let $r$ be the critical position. Then if agents follow $\pi_{a}^{{\rm
crit}}$, $\forall a\in\mathcal{N}$ are forced to pay $Q$ w.p.

$\alpha^{\rm crit}(p,r,n_{a},k)=\begin{cases}\alpha(p,n_{a},k)&{\rm if}\
n_{a}<r,\\\ \alpha(p,r,k-(n_{a}-r))&{\rm otherwise}.\end{cases}$ (11)

###### Proof.

Fix $a\in\mathcal{N}$. When $\alpha(p,n_{a},k)>F/Q$ (i.e. $n_{a}<r$), then
agents in front of $a$ pay $F$ and thus $a$ will not pay $Q$ only if enough of
them forget. If $n_{a}\geq r$, then $n_{a}-r$ agents choose not to pay.
Therefore, $a$ only needs $k-(n_{a}-r)$ of the $r$ agents to forget. ∎

Observe that $\alpha^{\rm crit}\leq\alpha$, since some agents may choose to
pay zero. Also, by Definition 3.2, $\alpha^{\rm crit}=0$ for $n_{a}>r+k$.

###### Proposition

Let $r$ be the critical position and let all agents follow $\pi_{a}^{{\rm
crit}}$, except for $a\in\mathcal{N}$, whose strategy is $\pi_{a}=(q,1-q)$.
Then the expected payment of $a$ is

$(1-p-q)F+(p+q)\alpha^{\rm crit}(p,r,n_{a},k)Q.$ (12)

###### Proof.

By definition of $\pi_{a}$, $a$ pays $F$ w.p. $1-p-q$ and he does not forget.
If he does, or pays zero w.p. $q$, he is forced to pay $Q$ w.p. $\alpha^{\rm
crit}(p,r,n_{a},k)$. ∎

###### Corollary

Let $r$ be the critical position and let all agents follow $\pi_{a}^{{\rm
crit}}$. Then the expected payment of $a\in\mathcal{N}$ is

$G_{a}(p,n_{a},k)=\begin{cases}(1-p)F+p\alpha^{\rm crit}(p,r,n_{a},k)Q,&{\rm
if}\ n_{a}<r,\\\ \alpha^{\rm crit}(p,r,n_{a},k)Q,&{\rm otherwise}.\end{cases}$
(13)

The strategy $\pi_{a}^{{\rm crit}}$ is unique equilibrium of $1$-Fines.

###### Proof.

Consider $a\in\mathcal{N}$ in the sorted order. We will show by induction
$\pi_{a}^{{\rm crit}}$ is a unique best-response to strategies of agents in
front of a given agent. For the first agent, $\pi_{a}^{{\rm crit}}$ clearly
maximizes the utility $-G_{a}$ of $a$. In the induction step we assume
$a^{\prime}$ in front of $a$ follow $\pi_{a}^{{\rm crit}}$. Following Lemma
3.2, the actions of the others can be arbitrary. Observe the $\pi_{a}^{{\rm
crit}}$ minimizes the expected payment (12). Thus $a$ wants to follow
$\pi_{a}^{{\rm crit}}$. ∎

####  3.2.2. Two Sorting Instances

In this section we present analytic solution of the $2$-Fines game. We start
by defining extension of $\pi_{a}^{{\rm crit}}$, and showing no agent can
benefit by deviating from it. Later, we discuss some properties of this
analytic solution.

In $2$-Fines, no agents are added after sorting. After the first Round the
game is thus identical to $1$-Fines. This recursive relation motivates us to
introduce the analogues of the variables used in the previous section
recursively. We use upper index to denote the game length $w$ and number of
Round, i.e. in the previous section we would use $r^{1,1}$ for the critical
position $r$.

We extend Definition 3.2.1 of critical strategy to pay $F$ if $a$’s position
is in front of some critical position $r^{2,t}$, defined below. Note that
since the second Round corresponds to $1$-Fines, $r^{2,2}=r^{1,1}=r$.

######  Definition  (2-Critical strategy).

The $2$-critical strategy is

$\pi_{a}^{{\rm crit},2}(n_{a},t_{a},m_{a})=\begin{cases}\sigma^{F}&{\rm if}\
n_{a}<r^{2,t_{a}},\\\ \sigma^{0}&{\rm otherwise}.\end{cases}$ (14)

Let all agents follow $\pi_{a}^{{\rm crit},2}$. Then if $a\in\mathcal{N}^{1}$,
$n_{a}<r^{2,1}$ does not terminate in the first Round, his expected payment in
the second Round is

$\mathcal{G}_{a}^{2}(p,n_{a},k)=\mathbb{E}_{\gamma\sim
B(n_{a}-1,1-p)}[G_{a}(p,n_{a}-\gamma-k,k)],$ (15)

where $G_{a}$ is the expected payment given in Corollary 3.2.1. In words,
since all agents in front of $a$ want to pay $F$, $a$’s position decreases by
$\gamma+k,\gamma\sim B(n_{a}-1,1-p)$. At the new position, he is expected to
pay $G_{a}$.

Similarly to Definition 3.2.1, we define the critical position in the first
Round as the smallest $r^{2,1}\in\mathbb{N}$ such that
$\alpha(p,r^{2,1},k)Q+(1-\alpha(p,r^{2,1},k))\mathcal{G}_{a}^{2}(p,r^{2,1},k)\leq
F$. In words, assume all agents in front of $a$ want to pay $F$. In the first
Round, if $a$ pays zero he risks paying $Q$ w.p. $\alpha$ and the expected
payment in the second Round w.p. $1-\alpha$. The critical position $r^{2,1}$
is the smallest position $n_{a}$ at which, assuming all agents in front of
that position try to pay $F$, it is beneficial to pay zero.

###### Lemma

Let $r^{2,t}$ be the critical position in Round $t\in\\{1,2\\}$. Then
$r^{2,1}\geq r^{2,2}+k$.

###### Proof.

By definition, $r^{2,1}$ is the smallest such that
$\alpha(p,r^{2,1},k)Q+(1-\alpha(p,r^{2,1},k))\mathcal{G}_{a}^{2}(p,r^{2,1},k)\leq
F$. For a contradiction we assume that $r^{2,1}<r^{2,2}+k$. It suffices to
show that $\mathcal{G}_{a}^{2}(p,r^{2,1},k)>F$ since this inequality along
with $Q>F$ violates the defining property of $r^{2,1}$.

If $r^{2,1}-k<r^{2,2}=r^{1,1}$ then for each $\gamma\geq 0$,

$G_{a}(p,r^{2,1}-\gamma-k,k)=(1-p)F+p\alpha(p,r^{2,1}-\gamma-k,k)Q,$

see Corollary 3.2.1 and Proposition 3.2.1.

Moreover, by the definition of $r^{1,1}=r$,

$\alpha(p,r^{2,1}-\gamma-k,k)Q>F.$

Hence for each $\gamma\geq 0$,

$G_{a}(p,r^{2,1}-\gamma-k,k)>F$

and thus $\mathcal{G}_{a}^{2}(p,r^{2,1},k)>F$.

∎

We are now ready to show the main result of this section.

[Equilibrium of $2$-Fines ] $\pi_{a}^{{\rm crit},2}$ is unique equilibrium of
$2$-Fines.

###### Proof.

The second Round, corresponding to $1$-Fines, has a unique equilibrium (10).
In the first Round, we can use a modification of proof of Theorem 3.2.1.
Consider now agents in the sorted order. Using Lemma 3.2, we can again use
induction over agents. For each $a\in\mathcal{N}^{1}$ let his strategy be
$\pi_{a}=(q,1-q)$ and let all agents in front of him follow $\pi_{a}^{{\rm
crit},1}$. Then his expected payment in a Round is

$G_{a}^{1}(p,n_{a},k)=(1-p-q)F+(p+q)\left(\alpha^{\rm crit}Q+(1-\alpha^{\rm
crit})\mathcal{G}_{a}^{2}\right),$ (16)

where we drop the arguments from $\alpha^{\rm crit}(p,r^{2,1},n_{a},k)$ for
brevity. This is because w.p. $1-p-q$ he pays $F$ and leaves. Otherwise, since
all agents in front of him follow $\pi_{a}^{{\rm crit},1}$, he is forced to
pay $Q$ w.p. $\alpha^{\rm crit}$. The remaining option is that he proceeds to
the next Round, where his expected payment is $\mathcal{G}_{a}^{2}$. Strategy
$\pi_{a}^{{\rm crit},1}$ is chosen to minimize $a$’s expected payment (16),
since $\alpha^{\rm crit}\leq\alpha$. Therefore, $a$ will follow it even in the
first Round. ∎

The equilibrium strategies of both $1$-Fines and $2$-Fines exhibit the
avalanche effect.

###### Proof.

Since $\lim_{p\to 0^{+}}\alpha(p,n,k)=1$ and $Q>F$, the critical position in
the last Round $r^{1,1},r^{2,2}\to\infty$. Using Lemma 3.2.2, the equilibrium
strategies of both $t$-Fines satisfy $\pi_{a}^{{\rm crit},t}\to\sigma^{F}$
$\forall t=1,2$. Thus, $\pi_{a}^{{\rm crit},t}$ satisfies Definition 2.3. ∎

In this simplified model, decreasing the probability of ignorance virtually
increases the number of state employees assigned to processing the fines. This
allows the central authority to increase the total payment through
advertising, rather than hiring additional employees, which may be much
cheaper. We show in Section 4 that these results translate well to a more
general case where non-zero number of agents enter the system in each Round.

####  3.2.3. Division problem

To give a partial answer to the Division problem in this setting, we will
compare the total expected payment of $2$-Fines with $k$, and $1$-Fines with
$2k$.

###### Proposition

Let $r^{2,2}$ be the critical position in the second Round of $2$-Fines, and
let all players follow $\pi_{a}^{{\rm crit},2}$. Then the total expected
payment is at least

$2F(1-p)(r^{2,2}-1)+2kQ.$ (17)

###### Proof.

In the first Round, $(1-p)(r^{2,1}-1)$ agents are expected to pay $F$, and $k$
are forced to pay $Q$. In the second, the situation is analogous, so the total
expected payment is

$F(1-p)(r^{2,1}+r^{2,2}-2)+2kQ.$

The statement follows from Lemma 3.2.2. ∎

Let $Q\gg F$. Then the equilibrium strategy of $\mathbb{F}(2,F,Q,k,p,x_{0})$
achieves a higher total payment than the equilibrium of
$\mathbb{F}(1,F,Q,2k,p,x_{0})$ in expectation.

###### Proof.

Let us denote the critical position in $1$-Fines with $2k$ by $r^{1,1}(2k)$
and in $2$-Fines with $k$ by $r^{2,1}(k),r^{2,2}(k)$ respectively. In the
former, $r^{1,1}(2k)-1$ agents will pay $F$ w.p. $(1-p)$, and $2k$ are forced
to pay $Q$. Therefore, the total expected payment is

$F(1-p)(r^{1,1}(2k)-1)+2kQ.$ (18)

By comparing this to Eq. (17), all we need to show is that
$r^{1,1}(2k)<2r^{2,2}(k)$. By Definition 3.2.1 this is equivalent to
$\alpha(p,2n,2k)<\alpha(p,n,k)$. Since $Q\gg F$, this is true by Proposition
3.2. ∎

Question. Is $n_{1}(2k)<n_{1}(K)+n_{1}(K)/p$?

##  4\. Experiments

We investigate two approaches based on how the agents choose their payments.
In Section 4.1, we define a simple strategy based on how the agent’s position
changes over the course of the Queue. In Section 4.2, we use reinforcement
learning to obtain a strategy which approximates equilibrium. In both cases we
simplify the model by assuming the function $\pi_{a}$ is the same for all
agents.

###  4.1. Basic Rational Strategy

To model behaviour of real decision makers, we introduce basic rational
strategy (BRS). Informally, each agent keeps track of a quantity he is willing
to pay in each Round. If, based on his shift in Queue since last Round, he
determines he will reach the beginning before $T$ steps, his willingness to
pay increases. Formally,

######  Definition  (basic rational strategy).

Let $a\in\mathcal{N}$, $(n^{\prime}_{a},t^{\prime}_{a},m^{\prime}_{a})$ be the
observation of $a$ in previous Round, and $(n_{a},t_{a},m_{a})$ his current
observation. We call $\omega_{a}$ the willingness to pay of $a$. In the first
Round $a$ participates in, i.e. when $t_{a}=0$, his willingness to pay is
$\omega_{a}=0$. In subsequent Round games, the willingness to pay is updated
before declaring $\pi_{a}$ according to

$\omega_{a}\leftarrow\begin{cases}\min(F-m_{a},\omega_{a}+1),&n_{a}<(n_{a}-n^{\prime}_{a})(T-t_{a}),\\\
\max(0,\omega_{a}-1),&\text{otherwise}.\end{cases}$ (19)

The strategy of $a$ is to pay $\omega_{a}$, i.e.
$\pi_{a}=\sigma^{\omega_{a}}$.

Note that this is a generalization of the approach introduced in Section 2.1,
as $\pi_{a}$ is not a function of only the observation in the current Round,
but also depends on history. This makes this strategy non-Markovian. As such,
the Definition 2.2 does not apply. However, in our experiments we simply
assess the effect of agents using BRS, and make no claims regarding its
optimality.

###  4.2. Reinforcement Learning

Figure 1. Evolution of NashConv during training, averaged over ten random
seeds.

In order to approximate an equilibrium of Queue, we employ an iterative
algorithm. In each iteration, the algorithm approximates $\overline{\pi}_{a}$
such that

$\overline{\pi}_{a}\in{\rm argmax}\
\mathbb{E}_{(\overline{\pi}_{a},\pi_{-a})}\left[u_{a}(\overline{\pi}_{a},\pi_{-a})\right].$
(20)

In words, we find $\overline{\pi}_{a}$ such that it maximizes utility of $a$,
assuming $\mathcal{N}\setminus\\{a\\}$ follow $\pi$. We denote as $\tau$ the
iteration of the learning algorithm and $\pi^{\tau}$ the strategy the
algorithm approximates the best-response against in iteration $\tau$.

We use PPO Schulman et al. (2017) to find $\overline{\pi}$, utilizing
trajectories of all terminal agents for the update. For details on our
implementation, see Appendix A. This approach is not guaranteed to converge in
general but if it does converge, the resulting strategy is an equilibrium
Ghosh et al. (2020). Similar approach was successfully used before Baker et
al. (2020).

####  4.2.1. NashConv

In order to quantify the quality of the learned solution, we adapt the notion
of NashConv Lanctot et al. (2017). NashConv measures the negative difference
in utility agents are expected to receive under $\pi^{\tau}$ and the
approximate best-response $\pi^{\tau+1}$. We approximate the latter by having
a fraction of agents $\rho$ follow $\pi^{\tau+1}$ while the rest follows
$\pi^{\tau}$. Formally,

######  Definition  (NashConv).

Let each agent added to Queue follow $\pi^{\tau+1}$ w.p. $\rho$ and
$\pi^{\tau}$ otherwise. Let $\overline{\mathcal{N}}$ be the set of agents
following $\pi^{\tau+1}$ and their expected utility

$\mathcal{EU}(\rho,\pi^{\tau+1},\pi^{\tau})=\mathbb{E}_{\left(\pi^{\tau+1}_{\overline{\mathcal{N}}},\pi^{\tau}_{-\overline{\mathcal{N}}}\right)}\left[u_{a}(\pi^{\tau+1}_{a},\pi^{\tau}_{-a})|a\in\overline{\mathcal{N}}\right].$

Then

${\rm
NashConv}^{\tau}(\rho)=\mathcal{EU}(\rho,\pi^{\tau+1},\pi^{\tau})-\mathbb{E}_{\pi^{\tau}}\left[u_{a}(\pi^{\tau})\right].$
(21)

NashConv and $\epsilon$-equilibrium are closely connected. If $\rho$ is small
enough such that $|\overline{\mathcal{N}}|\ll|\mathcal{N}|$, then ${\rm
NashConv}\approx\epsilon$. In Figure 1 we present a representative example of
the evolution of NashConv during learning. We averaged the results over ten
random seeds, and also show the standard error. The results suggest that,
although there is a considerable amount of noise, the algorithm was able to
reach a sufficiently close approximation of the equilibrium. Moreover, we
verified this trend translates to other experiments presented below.

###  4.3. Results

In this section, we numerically demonstrate the Avalanche effect and the
Division problem. Specifically, we show the total expected revenue, which is
given as

$\mathbb{E}_{\pi}\left[\sum_{a\in\mathcal{T}}m_{a}\right].$ (22)

Unless stated otherwise, we use $F=T=4$, $Q=6$, $x=x_{0}=32$, $k=2$ and
$p=1/2$ in all our experiments.

####  4.3.1. Avalanche Effect

In Figure 2 we show the total expected payment as a function of the
probability of ignorance $p$, and the number of entering agents $x$. The
results suggest that the Queue exhibits the Avalanche effect in a general
setting. In fact, it exhibits both properties of Definition 2.3.
Interestingly, the learned solution achieves a considerably lower total
payment compared to BRS.

Figure 2. Expected total payment of terminal agents for varying probability of
ignorance $p$ (left) and number of incoming offenders $x$ (right). The figures
demonstrate the Avalanche effect defined in Section 2.3.

####  4.3.2. Division problem

In this section we numerically study the Division problem introduced in
Section 2.4. Results for both the Time- and Group-Division problem are
presented in Figure 3.

For the Time-Division problem, BRS seems to drastically overpay the learned
strategy if the sorting is frequent, i.e. $T$ is large. On the other hand,
when $T$ is small the willingness to pay doesn’t increase. This leads to
paying only $kQ=48$ for $T=1$, while the learned strategy prefers to pay more.
When the game is sorted more often, the learned strategy seems to favor lower
total payments.

In the Group-Division scenario, both BRS and the learned strategy pay less in
larger system. Splitting the game into several smaller thus increases the
total payment of the offenders. This is in agreement with the analytic
solution presented in Section 3.2.2, suggesting the incoming agents don’t
impact Queue much.

Figure 3. Expected total payment of terminal agents for varying number of
sortings $T$ (left) and number of splits $g$ (right). The figures investigate
the Division problem defined in Section 2.4.

##  5\. Conclusion

In this work, we suggest a simple mechanism for collecting fines for traffic
violations in large cities, by a small number of administrators. We show
analytically and on realistic experiments that this simple mechanism exhibits
the Avalanche effect and thus supports non-cooperation of offenders. We
quantify the fines collection in expectation. Finally, we present some initial
results towards understanding the effective use of the administrators, i.e.,
the Division problem.

Future work: Further study of the Division problem, in particular possible
strengthening of Lemma 3.2.2 and proving Conjecture 3.2 is our work in
progress.

We see a limitation of our numerical approach in that we limit ourselves to
scenarios where all agents share the same strategy $\pi_{a}$. We would like to
improve on our results by having each agent follow a leader, and training each
leader separately. In this framework, we could also access the exploitability
of BRS, by having the learned agents in the same system.

##  Appendix A Learning Algorithm

The shared strategy $\pi_{a}$ is represented by a neural network and trained
from trajectories of all terminal agents. When selecting the strategy for a
Round, we mask all actions which would lead to $m_{a}+\mu_{a}>F$. This makes
the agents unable to overpay the fine $F$.

We use fully-connected networks for both the actor and the critic. Both accept
the scaled observation of $a$ in Round, i.e. $(n_{a},t_{a},m_{a})$. The actor
network has two hidden layers with four hidden units, and the critic has three
hidden layers with 32 units each, all using the ReLU activation function. The
rest of the hyperparameters are given in Table 1.

Parameter | Value | Description
---|---|---
$\varepsilon$ | 0.05 | Policy update clipping
$\gamma$ | 1 | Reward discounting
$\lambda$ | 0.95 | Advantage decay factor
$N_{\rm train}$ | 16 | Number of training updates per cycle
$N_{\rm epochs}$ | 512 | Number of training epochs
$N_{\rm train}$ | $10^{4}$ | Train buffer size
$\alpha_{\rm actor}$ | $3\cdot 10^{-4}$ | Actor learning rate
$\alpha_{\rm critic}$ | $10^{-3}$ | Critic learning rate
$c_{\rm H}$ | $10^{-3}$ | Entropy regularization weight
$\overline{c}$ | 0.1 | Gradient norm clipping
Table 1. Hyperparameters of the learning algorithm.

This work has been supported by the E-POKUTY TACR project no. TL05000450.
Computational resources were supplied by the project e-Infrastruktura CZ
(e-INFRA CZ LM2018140) supported by the Ministry of Education, Youth and
Sports of the Czech Republic.

## References

  * (1)
  * Baker et al. (2020) Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. 2020.  Emergent Tool Use From Multi-Agent Autocurricula. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=SkxpxJBKwS
  * Chiam C. (2020) A. Lee Chiam C., Li J. 2020\.  The Bidding Elimination Game.  (2020).  https://web.stanford.edu/class/aa228/reports/2020/final54.pdf
  * Ghosh et al. (2020) Dibya Ghosh, Marlos C. Machado, and Nicolas Le Roux. 2020\.  An Operator View of Policy Gradient Methods. In _Proceedings of the 34th International Conference on Neural Information Processing Systems_ (Vancouver, BC, Canada) _(NIPS’20)_. Curran Associates Inc., Red Hook, NY, USA, Article 286, 10 pages.
  * Greenberg and Mohri (2014) Spencer Greenberg and Mehryar Mohri. 2014.  Tight lower bound on the probability of a binomial exceeding its expectation.  _Statistics & Probability Letters_ 86 (2014), 91–98.  https://doi.org/10.1016/j.spl.2013.12.009
  * Kobylanski M. (2013) de Campagnolle M. R. Kobylanski M., Quenez† M. 2013.  Dynkin games in a general framework.  https://arxiv.org/abs/1202.1930
  * Lanctot et al. (2017) Marc Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Perolat, David Silver, and Thore Graepel. 2017\.  A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning. In _Advances in Neural Information Processing Systems_ , I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. Curran Associates, Inc.  https://proceedings.neurips.cc/paper/2017/file/3323fe11e9595c09af38fe67567a9394-Paper.pdf
  * Schulman et al. (2017) John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017.  Proximal Policy Optimization Algorithms.  _CoRR_ abs/1707.06347 (2017).  http://dblp.uni-trier.de/db/journals/corr/corr1707.html#SchulmanWDRK17