# The Consensus Game: Language Model
Generation via Equilibrium Search

Athul Paul Jacob
MIT
&Yikang Shen
MIT-IBM AI Lab
&Gabriele Farina
MIT
&Jacob Andreas
MIT
Correspondence to<EMAIL_ADDRESS>
###### Abstract

When applied to question answering and other text generation tasks, language
models (LMs) may be queried _generatively_ (by sampling answers from their
output distribution) or _discriminatively_ (by using them to score or rank a
set of candidate outputs). These procedures sometimes yield very different
predictions. How do we reconcile mutually incompatible scoring procedures to
obtain coherent LM predictions? We introduce a new, a training-free, game-
theoretic procedure for language model decoding. Our approach casts language
model decoding as a regularized imperfect-information sequential signaling
game—which we term the consensus game—in which a generator seeks to
communicate an abstract correctness parameter using natural language sentences
to a discriminator. We develop computational procedures for finding
approximate equilibria of this game, resulting in a decoding algorithm we call
equilibrium-ranking. Applied to a large number of tasks (including reading
comprehension, commonsense reasoning, mathematical problem-solving, and
dialog), equilibrium-ranking consistently, and sometimes substantially,
improves performance over existing LM decoding procedures—on multiple
benchmarks, we observe that applying equilibrium-ranking to LLaMA-7B
outperforms the much larger LLaMA-65B and PaLM-540B models. These results
highlight the promise of game-theoretic tools for addressing fundamental
challenges of truthfulness and consistency in LMs.

##  1 Introduction

Current language models (LMs) perform quite well on some tasks involving
generation or verification of factual assertions—including question answering,
fact-checking, and even unconditional text generation. But they are far from
perfectly reliable, and there is increasing evidence that LMs actually grow
more prone to generating false but frequently repeated statements with
increasing scale (McKenzie et al., 2023). Further complicating matters, LMs
offer multiple affordances for solving factual generation tasks. They may be
used both _generatively_ (e.g. by asking for the most probable answer to a
question) or _discriminatively_ (e.g. by presenting a (question, answer) pair
and asking whether the answer is acceptable) and, these two procedures do not
always produce consistent results: generative procedures may fail when
probability mass is spread across multiple contradicting answers (Wang et al.,
2022; Mitchell et al., 2022), while discriminative procedures may fail due to
miscalibration (Han et al., 2022; Chen et al., 2022) or subtle dependence on
question wording (Jiang et al., 2020). Given these noisy and often-conflicting
signals, how should we distill out an LM’s best guess at the truth?

This paper presents an approach for reconciling generative and discriminative
LM decoding procedures by formulating decoding as a signaling game (Lewis,
2008) that we call the consensus game. At a high level, this game features a
generator agent that must communicate an abstract correct or incorrect value
to a discriminator agent, but may only do so using a set of candidate natural
language strings (Fig. 1). Intuitively, an effective _strategy_ for this game
(i.e. a joint policy) is one in which the generator and discriminator agree on
the assignment of strings to correctness values. Given such a strategy, we may
inspect it to identify candidates agreed by consensus to be correct.

Doing so requires solving a multi-step game with a complex (string-valued)
action space. In recent years, _no-regret learning_ algorithms have emerged as
the preferred technique to compute effective strategies for such games, and
have been successfully deployed in Poker (Brown & Sandholm, 2018; 2019),
Stratego (Perolat et al., 2022), and Diplomacy (Bakhtin et al., 2023; FAIR et
al., 2022; Jacob et al., 2022). Here, we show that they can also be applied to
free-form language generation tasks. We call this game-theoretic approach to
LM decoding equilibrium-ranking. Applied in 6 question answering benchmarks:
MMLU (Hendrycks et al., 2020), ARC (Clark et al., 2018), RACE (Lai et al.,
2017), HHH (Askell et al., 2021), TruthfulQA (Lin et al., 2022) and, GSM8K
(Cobbe et al., 2021), equilibrium-ranking offers substantial improvements over
existing generative, discriminative, and mixed decoding procedures. More
generally, our results highlight the usefulness of the game-theoretic toolkit
for formalizing and improving coherence in LMs. Improved coherence in turn
leads to improved accuracy on factual tasks.

Figure 1: (Left) Overview of our approach. Differing LM queries fail to
exhibit consensus about the answer to a factual question. By reconciling
predictions between generative and discriminative LM queries using the
consensus game, we obtain an accurate prediction. (Right) Structure of the
consensus game, a two-player sequential signaling game with imperfect
information. First, the environment (N) uniformly samples a correctness
parameter. A generator (G) conditioned on this parameter produces a natural
language string from a set of candidates. The discriminator (D) only observes
this string and must predict the correctness parameter sampled by environment.
If the discriminator correctly identifies this parameter, then both players
receive a reward of 1. The dashed line connects nodes that are
indistinguishable by the discriminator, since the discriminator does not
observe the correctness parameter. By computing _regularized equilibrium
strategies_ for this game, we obtain predictions that reflect a consensus
between the generator and discriminator.

##  2 Language Model Consensus as Equilibrium Search

We study the problem of obtaining correct output from a language model, which
maps input strings $x$ to output strings $y$ according to some distribution
$P_{\textsf{LM}}(y\mid x)$. While the techniques we present here are general,
we focus in this paper on question answering problems consisting of a query
$x$ (_In which of the following cities was Barack Obama born?_) and a set of
candidate answers $\mathcal{Y}$ (_Honolulu, Chicago, …_) which may themselves
have been sampled from the complete $P_{\textsf{LM}}(\cdot\mid x)$. Given a
set of candidates, we may them with an LM in (at least) two ways:

  * •

_Generatively_ , by supplying as input (i) the query $x$, (ii) the set of
candidates $\mathcal{Y}$, and (iii) a natural language prompt indicating that
a correct answer is desired. In this case, the LM may be thought of as
modeling a distribution $P_{\textsf{LM}}(y\mid
x,\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}})$,
where the token correct denotes the fact that the model was prompted to
generate a correct answer.

  * •

_Discriminatively_ , by supplying as input (i) the query $x$ and (ii) a
possible candidate answer $y\in\mathcal{Y}$, together with (iii) a prompt
indicating that a correctness assessment
$v\in\\{\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}},\texttt{{\color[rgb]{0.525,0,0.175}\definecolor[named]{pgfstrokecolor}{rgb}{0.525,0,0.175}incorrect}}\\}$
is sought. In this case, the language model acts as a model of as modeling a
distribution $P_{\textsf{LM}}(v\mid x,y)$ where
$v\in\\{\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}},\texttt{{\color[rgb]{0.525,0,0.175}\definecolor[named]{pgfstrokecolor}{rgb}{0.525,0,0.175}incorrect}}\\}$.

These two approaches are conceptually equivalent. But as noted in the
introduction, current LMs may give very different answers when queried in
these different ways: answers produced generatively might be assessed
incorrect with high probability or vice-versa. Research on LMs has proposed
two broad solutions to this problem. Ensembling methods (Ouyang et al., 2022;
Li & Jurafsky, 2016; Glaese et al., 2022) simply combine discriminative and
generative scores directly. While moderately effective, such approaches suffer
from the fact that LM predictions are often poorly calibrated both within and
across contexts, meaning that scores may not combine in meaningful or
consistent ways. Deliberation methods (Wei et al., 2022; Yao et al., 2023; Du
et al., 2023) perform this reconciliation within the LM itself, e.g. by re-
prompting with competing inputs and an instruction to generate a textual
justification for the best one. Such methods incur significant computational
overhead.111As shown in Section 3, they are also orthogonal to, and composable
with, the approach we propose here.

How might we design a principled and computationally efficient procedure for
obtaining a “consensus” between competing LM predictions? Informally, a
consensus prediction would satisfy two key properties: coherence (generative
and discriminative scoring procedures should agree about which candidate
answers are correct) and reasonableness (predictions should not be arbitrary,
but instead as close as possible to original generator / discriminator
behavior). The key idea in this paper is to operationalize these high-level
desiderata in language of game theory, using regularized equilibrium concepts
as formal framework for defining both coherence and reasonableness. Below, we
introduce and explain this framework in detail, describing how to instantiate
decoding as a signaling game, then compute equilibrium strategies of this game
to obtain consensus LM predictions.

###  2.1 The consensus game

Our approach to language generation begins by formulating language generation
as a signaling game (Lewis, 2008) that we call the consensus game. The
consensus game is played on a game tree, as depicted in Figure 1. At the start
of the game (that is, at the root of the game tree), a _correctness parameter_
$v\in\\{\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}},\texttt{{\color[rgb]{0.525,0,0.175}\definecolor[named]{pgfstrokecolor}{rgb}{0.525,0,0.175}incorrect}}\\}$
is selected uniformly at random by the environment. The correctness parameter
is observed only by the generator, and controls whether the generator should
aim to generate _correct_ or _incorrect_ answers. Upon observing this
parameter, the generator produces a natural language string from a fixed set
of candidates. Finally, this string is observed by the discriminator, who
tries to guess the value of the correctness parameter by selecting one of
$\\{\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}},\texttt{{\color[rgb]{0.525,0,0.175}\definecolor[named]{pgfstrokecolor}{rgb}{0.525,0,0.175}incorrect}}\\}$
as an answer. Both players obtain a payoff of 1 if the discriminator correctly
identifies the value of the correctness parameter, 0 otherwise.

With this definition, it may be observed that players’ expected utilities (the
payoffs they may expect to receive) are as follows:

$\displaystyle
u_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}(\pi_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}},\pi_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}})$
$\displaystyle\coloneqq\frac{1}{2}\sum_{v\in\\{\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}},\texttt{{\color[rgb]{0.525,0,0.175}\definecolor[named]{pgfstrokecolor}{rgb}{0.525,0,0.175}incorrect}}\\}}\sum_{y\in\mathcal{Y}}\pi_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}(y\mid
v)\cdot\pi_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}(v\mid
y),$ $\displaystyle
u_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}(\pi_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}},\pi_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}})$
$\displaystyle\coloneqq\frac{1}{2}\sum_{v\in\\{\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}},\texttt{{\color[rgb]{0.525,0,0.175}\definecolor[named]{pgfstrokecolor}{rgb}{0.525,0,0.175}incorrect}}\\}}\sum_{y\in\mathcal{Y}}\pi_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}(y\mid
v)\cdot\pi_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}(v\mid
y).$

What is an effective strategy for maximizing these utilities? A standard
answer to this question in the game theory literature is that a Nash
equilibrium of the game should be sought. A Nash equilibrium is a pair of
policies—one for the generator and one for the discriminator—such that each
policy is optimal. That is, each player’s strategy maximizes their expected
given the other player’s strategy. At a Nash equilibrium, no player has an
incentive to unilaterally behave in any other way. In signaling games, Nash
equilibria offer a natural way of formalizing the coherence criterion above:
at equilibrium, both the generator and discriminator must agree about which
messages correspond to correct and incorrect respectively in order to obtain a
nonzero payoff.

However, Nash equilbria of the consensus game are not guaranteed to provide
the second criterion of reasonableness. This is because the consensus game
admits a multitude of Nash equilibria that are incompatible with the common-
sense notion of truthfulness. For example, the strategy in which the generator
deterministically maps correct $\mapsto$ “Nairobi”, incorrect $\mapsto$
“Honolulu”, and the discriminator maps “Nairobi” $\mapsto$ correct, “Honolulu”
$\mapsto$ incorrect forms a Nash equilibrium.

In order to sidestep the inappropriate equilibria and ensure reasonableness,
we introduce a regularization term in the utility of the players, so that both
the generator and the discriminator are penalized for settling on strategies
that are far from some pair of _initial policies_ :
$\smash{\pi^{(1)}_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}}$
and
$\smash{\pi^{(1)}_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}}$.
By parameterizing these policies using a pre-trained LM, we may use knowledge
about what answers are likely to be correct _a priori_ to guide selection of
an equilibrium. As in Jacob et al. (2022), we incorporate this regularization
term directly into the utility function (payoff) that the generator and
discriminator attempt to optimize. Rather than the simple 0–1 payoff
determined by agreement on the correctness parameter, they now attempt to
optimize:

$\displaystyle
u_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}(\pi_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}},\pi_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}})$
$\displaystyle\coloneqq-\lambda_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}\cdot\mathrm{D}_{\mathrm{KL}}[\pi_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}(\cdot\mid
v),\pi^{(1)}_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}(\cdot\mid
x,v)]+\frac{1}{2}\sum_{v}\sum_{y\in\mathcal{Y}}\pi_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}(y\mid
x,v)\cdot\pi_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}(v\mid
x,y),$ $\displaystyle
u_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}(\pi_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}},\pi_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}})$
$\displaystyle\coloneqq-\lambda_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}\cdot\mathrm{D}_{\mathrm{KL}}[\pi_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}(\cdot\mid
y),\pi^{(1)}_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}(\cdot\mid
x,y)]+\frac{1}{2}\sum_{v}\sum_{y\in\mathcal{Y}}\pi_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}(y\mid
x,v)\cdot\pi_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}(v\mid
x,y).$

Note that the initial policies
$\smash{\pi^{(1)}_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}}(y\mid
x,v)$ and $\smash{\pi^{(1)}_{L}(v\mid x,y)}$ may be derived from an LM
_prompted_ with some initial string $x$, in order to obtain context-
predictions (e.g. answers to a question). With these utilities, Nash
equilibria for the game are pulled by the initial generator and discriminator
policies in the direction of increased consensus.

Bakhtin et al. (2023) and FAIR et al. (2022) employed a similar regularization
method for choosing actions, rather than messages, in versions of the board
game Diplomacy. Franke (2013; 2017) have explored signaling games in the
context of linguistic pragmatics to explain human language use. To the best of
our knowledge, however, this is the first proposal for using regularized
equilibrium concepts in signaling games to define target behavior in a
language generation task.

###  2.2 equilibrium-ranking: LM Ranking via equilibrium search

With this formulation, text generation requires finding a Nash equilibrium of
the game with the utilities given above. How should we compute such an
equilibrium? No-regret learning algorithms have emerged in recent years as the
preferred technique to approximate equilibria in large games, and have been
successfully employed to solve games at human or even superhuman level. At a
high level, these algorithms find equilibrium by repeatedly interacting in the
game and refining their policies after each iteration $t$. so as to minimize
regret (the gap between the chosen action and the best action in hindsight).

In this section, we describe in detail how to perform no-regret learning in
the consensus game in order to obtain consensus policies. Importantly, this
approach modifies only signalling policies, and not the base policies
$\smash{\pi^{(1)}_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}}$
and
$\smash{\pi^{(1)}_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}}$
(i.e. the LM). In this sense, generating text by performing no-regret learning
in the consensus game might be described as a _training-free consensus-
planning method_. We call this method equilibrium-ranking.

#### Initial policies

At time $t=1$, that is, before any equilibrium computation has happened,
equilibrium-ranking defines the initial policies
$\pi^{(1)}_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}$
and
$\pi^{(1)}_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}$
of the generator and discriminator, respectively, as follows.
$\pi^{(1)}_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}$
normalizes $P_{\textsf{LM}}$222In ARC, RACE, HHH, TruthfulQA, and GSM8K, based
on prior work (Touvron et al., 2023; Brown et al., 2020), we additionally
normalize $P_{\textsf{LM}}(u|x)$ by the likelihood of the completion given
“Answer:” as context: $P_{\textsf{LM}}(u\mid\text{"Answer:"})$. across $v$ and
$y$:

$\displaystyle\pi^{(1)}_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}(y\mid
x,v)\propto\frac{P_{\textsf{LM}}(y\mid
x,v)}{\sum_{v^{\prime}}P_{\textsf{LM}}(y\mid x,v^{\prime})}.$

Similarly for the discriminator, the initial policy normalizes across $y$ and
$v$:

$\displaystyle\pi^{(1)}_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}(v\mid
x,y)\propto\frac{P_{\textsf{LM}}(v\mid
x,y)}{\sum_{y^{\prime}}P_{\textsf{LM}}(v\mid x,y^{\prime})}.$

This crucial step enables us to extract a well calibrated generator and
discriminator from $P_{\textsf{LM}}$. The specific form of the generator
incorporates
$v=\texttt{{\color[rgb]{0.525,0,0.175}\definecolor[named]{pgfstrokecolor}{rgb}{0.525,0,0.175}incorrect}}$,
and this resembles contrastive decoding (Li et al., 2022), where they rely on
a weaker LM as opposed to an LM conditioned on incorrect (See, Section 3 for
details). This discriminator resembles approaches that query the LM itself to
produce critiques (Ganguli et al., 2023; Chen et al., 2023b; Yao et al.,
2023). However, to the best of our knowledge, this specific instantiation has
not been explored in the past.

#### Evolution of policies

A classic observation in the theory of imperfect-information sequential games
is that minimization of regret (viewed as a function of their overall policy
on the game tree) can be achieved by solving separate, _local_ , regret
minimization problems at each information set (i.e., decision point) of the
game. This observation underpins the CFR framework (Zinkevich et al., 2007),
as well as its generalization to more general convex losses, known as laminar
regret decomposition (Farina et al., 2019). In our case, these techniques
enable us to decompose the policy update of the players into separate updates
for each correctness parameter $v$ (for the generator) and for each sequence
$y$ (for the discriminator). We provide more detail and background in Appendix
A.

In our setting, after operating the regret decomposition step, we find that
the local regret minimization problems are composed of a bilinear term, plus a
strongly convex KL-regularization term. Such composite utilities can be
handled by the piKL algorithm (Jacob et al., 2022), which is specifically
designed to perform regret minimization on KL-regularized objectives. In our
setting, piKL prescribes that each player keep track of their average values:

$\displaystyle
Q^{(t)}_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}(y\mid
x,v)\coloneqq\frac{1}{2t}\sum_{\tau=1}^{t}\pi^{(\tau)}_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}(v\mid
x,y),\qquad
Q^{(t)}_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}(v\mid
x,y)\coloneqq\frac{1}{2t}\sum_{\tau=1}^{t}\pi^{(\tau)}_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}(y\mid
x,v).$

Each player then updates their policy according to:

$\displaystyle\pi_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}^{(t+1)}(y\mid
x,v)$
$\displaystyle\propto\exp\left\\{\frac{Q^{(t)}_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}(y\mid
x,v)+\lambda_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}\log\pi_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}^{(1)}(y\mid
x,v)}{1/(\eta_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}t)+\lambda_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}}\right\\},$
(1)
$\displaystyle\pi_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}^{(t+1)}(v\mid
x,y)$
$\displaystyle\propto\exp\left\\{\frac{Q^{(t)}_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}(v\mid
x,y)+\lambda_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}\log\pi_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}^{(1)}(v\mid
x,y)}{1/(\eta_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}t)+\lambda_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}}\right\\},$
(2)

where
$\eta_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}},\eta_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}>0$
are _learning rate_ hyperparameters. piKL no-regret dynamics are known to have
strong guarantees, including the following (more formal statements about the
guarantees are available in Appendix A):

  * •

Convergence to an equilibrium point. The average correlated distribution of
play of generator and discriminator converges to the set of (regularized)
coarse-correlated equilibria of the game.

  * •

Regularization toward reasonableness. The average policy of any player remains
within a radius of size roughly $1/\lambda_{i}$ from the initial policy
$\pi_{i}^{(1)}$, where $\lambda_{i}$ is the amount of regularization applied
to any player
$i\in\\{\textsc{{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}generator}},\textsc{{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}discriminator}}\\}$
(see Proposition 3).

  * •

Avoidance of regret. The cumulative regret incurred by each of the players
grows only logarithmic in the number of training steps (see Proposition 1).

At convergence, equilibrium-ranking returns
$\pi_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}^{*}$
and
$\pi_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}^{*}$,
which are the refined generator and discriminator. We also remark that a
recent result by Anagnostides et al. (2022) showed that as long as the
regularization function has Lipschitz-continuous gradients (a condition that
can be easily achieved by introducing a small perturbation in the KL
regularization term), decentralized learning dynamics similar to piKL converge
in iterates to a regularized Nash equilibrium of the consensus game, since it
is a potential game (Monderer & Shapley, 1996). In practice, we do not
investigate introducing a small perturbation, as we witness good convergence
properties in practice even without any perturbation. As mentioned earlier,
convergence to a regularized Nash equilibrium is important to guarantee both
coherence and reasonableness. Extensive empirical validation presented in the
next section demonstrates the benefits of this approach in practice.

#### Computational cost of our method.

At each iteration, our method needs to update the policies
$Q^{(t)}_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}},Q^{(t)}_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}$
according to (1) and (2). The number of operations at each iteration of the
method is therefore linear in the number $|\mathcal{Y}|$ of sequences
available to the generator.

##  3 Experiments

As discussed in the previous section, equilibrium-ranking focuses on improving
the _correctness_ of language models in question-answering (QA) tasks.
However, correctness manifests in various forms across different domains,
including truthfulness, factuality, valid reasoning, value alignment, among
others. Therefore, we will evaluate its performance on a diverse set of QA
tasks: MMLU (Hendrycks et al., 2020), ARC (Clark et al., 2018), RACE (Lai et
al., 2017), HHH (Askell et al., 2021), and TruthfulQA (Lin et al., 2022). It’s
important to note that equilibrium-ranking is a sampling strategy and not a
delibration method like chain-of-thought (CoT) (Wei et al., 2022) and self-
consistency (Wang et al., 2022). Nevertheless, we will demonstrate in GSM8K
(Cobbe et al., 2021) that we can achieve some additional gains when combining
equilibrium-ranking with self-consistency and CoT.

#### Hyperparameters

equilibrium-ranking has four parameters,
$\eta_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}},\lambda_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}$
and
$\eta_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}},\lambda_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}$.
Although tuning these parameters will lead to better performance, in all our
experiments we set
$\eta_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}=\lambda_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}=\eta_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}=\lambda_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}=0.1$.
We run equilibrium-ranking for 5000 iterations 333 As remarked at the end of
the previous section, each iteration of the learning process requires a number
of floating-point operations that is linear in the number $|\mathcal{Y}|$
available to the generator. In most of our settings, $|\mathcal{Y}|=4$, making
the overhead from the learning dynamics on the consensus game negligible
compared to the cost of inference for the language model. As such, even with
an unoptimized implementation of the dynamics (1,2), we observe that the
computational cost associated with each iteration of the learning process
takes about 40 microseconds on average.

#### Actions in the consensus game

As mentioned in Section 2, in order to make our approach amenable to current
computational techniques, we make the modeling assumption that the generator
picks distribution over a finite set of candidates $\mathcal{Y}$. In multiple-
choices tasks, these are the multiple choice options. In generative tasks, a
common approach to generate the finite set of candidates is via sampling with
nucleus (Holtzman et al., 2019) and top-$k$ (Fan et al., 2018b) from the
distribution $P_{\textsf{LM}}(y\mid
q,\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}})$
where $y\in\mathcal{Y}$. This is exactly the approach we use in our
experiments, with $p=0.9$ for nucleus sampling and $k=50$.

#### Models

We use the 7B and 13B parameter models from the LLaMA family (Touvron et al.,
2023) and perform 16-bit inference for all our experiments.

#### Prompting for correct and incorrect answers

In our work, unless otherwise specified, conditioning on
$(x,\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}})$
for the $P_{\textsf{LM}}$ corresponds to the standard zero-shot prompt.
Similarly, conditioning on
$(x,\texttt{{\color[rgb]{0.525,0,0.175}\definecolor[named]{pgfstrokecolor}{rgb}{0.525,0,0.175}incorrect}})$
is similar to
$(x,\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}})$
with the only difference that ”Answer:” is replaced with ”Incorrect Answer:”
in the prompt.

#### Baselines

In the multiple-choice based datasets (ARC, RACE, HHH, MMLU), we consider the
following approaches:

  * •

Generative Ranking (G): This baseline (Brown et al., 2020; Touvron et al.,
2023) ranks every candidate $y$ by $P_{\text{LM}}(y\mid
x,\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}})$
and picks the top candidate. This is the standard approach used in past work.
Due to implementational differences, when available, we include both official
scores and our version.

  * •

Mutual Information Ranking (MI): This mutual-information based (Li & Jurafsky,
2016) baseline is an ensemble-based approach that reweights every candidate
$y$ by $P_{\text{LM}}(y\mid
x,\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}})\cdot
P_{\text{LM}}(\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}}\mid
x,y)$.

  * •

Self-Contrastive Ranking (SC): This approach utilizes the normalized generator
$\pi^{(1)}_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}$
to reweight every candidate $y$ by
$\smash{\pi^{(1)}_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}(\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}}\mid
x,y)}$. As discussed in Section 2, this shares similarities with contrastive
decoding (Li et al., 2022).

  * •

Discriminative Ranking (D): This approach reweights every query-candidate pair
$(x,y)$ by
$\pi^{(1)}_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}(\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}}\mid
x,y)$.

  * •

Equilibrium Ranking Generator (ER-G): Similar to SC, this approach utilizes
the final equilibrium-ranking-based generator
$\pi^{*}_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}$
to reweight every candidate $y$ by
$\pi^{*}_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}(y\mid
x,\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}})$.

  * •

Equilibrium Ranking Discriminator (ER-D): Similar to D, this approach utilizes
the final equilibrium-ranking-based discriminator
$\pi^{*}_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}$.
This approach reweights every query-candidate pair $(x,y)$ by
$\pi^{*}_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}(\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}}\mid
x,y)$.

In free-form text generation tasks (TruthfulQA, GSM8K), we additionally
consider greedy decoding. In the mathematical reasoning task (GSM8K), we also
consider self-consistency (Wang et al., 2022).

|  |  |  |  |  |  | Equil. ranking
---|---|---|---|---|---|---|---
Domain | Model | G∗ | G | MI | SC | D | ER-G | ER-D
MMLU | LLaMA-7B | – |  30.4 |  33.1 |  30.5 |  40.4 |  39.4 |  39.9
LLaMA-13B | – |  41.7 |  41.8 |  41.7 |  41.9 |  44.9 |  45.1
ARC Easy | LLaMA-7B |  72.8 |  68.2 |  68.8 |  69.5 |  52.5 |  71.6 |  71.5
LLaMA-13B |  74.8 |  71.2 |  71.5 |  73.0 |  65.0 |  76.1 |  76.4
ARC Challenge | LLaMA-7B |  47.6 |  47.3 |  47.4 |  56.5 |  42.7 |  58.7 |  58.3
LLaMA-13B |  52.7 |  51.9 |  52.1 |  59.3 |  48.5 |  61.1 |  61.4
RACE Middle | LLaMA-7B |  61.1 |  57.7 |  57.7 |  60.4 |  51.5 |  63.2 |  63.5
LLaMA-13B |  61.6 |  60.1 |  60.2 |  64.8 |  58.3 |  67.9 |  68.6
RACE High | LLaMA-7B |  46.9 |  46.4 |  46.3 |  53.1 |  46.0 |  56.3 |  56.4
LLaMA-13B |  47.2 |  47.9 |  48.4 |  58.9 |  55.1 |  62.1 |  62.8
HHH | LLaMA-7B | – |  59.3 |  57.9 |  67.4 |  70.1 |  71.5 |  71.5
LLaMA-13B | – |  60.2 |  59.7 |  57.9 |  69.2 |  61.1 |  61.1
Table 1: Results of the different approaches across multiple tasks. We compute
the accuracies on the test set of these benchmarks. equilibrium-ranking
outperforms other approaches on most tasks. equilibrium-ranking performs well,
even in cases where one of generator or discriminator is far worse than the
other. G: Generative Ranking, MI: Mutual Information Ranking, SC: Self-
Contrastive Ranking, D: Discriminative Ranking, ER-G: Equilibrium Ranking
Generator, ER-D: Equilibrium Ranking Discriminator. * indicates the results
from Touvron et al. (2023). Colors in the table entries are assigned relative
to the G baseline, according to the colorbar  (differences exceeding $\pm
10$ are clipped to $\pm 10$ when calculating the colors).

#### MMLU

The massive multi-task language understanding benchmark (MMLU) (Hendrycks et
al., 2020) is used to measure language model’s multitask accuracy. It consists
of questions in the multiple choice format across a wide variety of subdomains
in social sciences, humanities and STEM. We evaluate our models in the zero-
shot setting following the format described in Hendrycks et al. (2020);
Touvron et al. (2023) and the results are presented in the first row of Table
1. For both LLaMA-7B and LLaMA-13B, the equilibrium-ranking-based approaches
matches or outperforms all other baselines. In fact, zero-shot LLaMA-7B with
ER-D (39.9) outperforms 5-shot LLaMA-7B (35.1), while zero-shot LLaMA-13B with
ER-D (45.1) is competitive with 5-shot LLaMA-13B (46.9). LLaMA-7B with ER-D
(39.9) even outperforms zero-shot GPT3-175B (37.7) (Hendrycks et al., 2020),
while zero-shot LLaMA-13B with ER-D (45.1) outperforms 5-shot GPT3-175B (43.9)
(Hendrycks et al., 2020).

#### ARC

The AI2 Reasoning Challenge (ARC) (Clark et al., 2018) is an advanced question
answering dataset used to study a model’s knowledge and reasoning abilities
based on grade school science questions. It is split in to two subcategories:
easy (ARC-Easy) and challenge (ARC-Challenge). The challenge set was
constructed as the set of questions that were answered incorrectly by
retrieval and word co-occurence based algorithms. The results are presented in
second and third rows of Table 1. On ARC-Easy, ER-D outperforms our
implementation of generative ranking. We also note that LLaMA-13B with ER-D
(76.4) outperform all the baseline approaches and is even competitive with the
much larger PaLM-540B model (76.6) (Chowdhery et al., 2022). On ARC-Challenge,
ER-D significantly outperforms all the baseline approaches. We also note that
LLaMA-7B with ER-D (58.3) and LLaMA-13B with ER-D (61.4) outperforms even the
much larger models: LLaMA-65B (56.0) (Touvron et al., 2023) and PaLM-540B
(53.0) (Chowdhery et al., 2022) by up to 8%.

#### RACE

RACE is a reading comprehension benchmark introduced in Lai et al. (2017)
collected from English examinations of middle and high school students. The
dataset is correspondingly split into RACE-middle and Race-high. The dataset
consists of a passage followed by questions. The passages were constructed for
evaluating student’s English reasoning and understanding ability. The results
on this benchmark is presented in rows 4 and 5 of Table 1. On RACE-middle,
like before, ER-D based models outperforms all the baselines. We note that
LLaMA-13B with ER-D (68.6) even outperforms much larger models: LLaMA-65B
(67.9) (Touvron et al., 2023) and PaLM-540B (68.1) (Chowdhery et al., 2022).
On RACE-high, we have a similar story as with ARC-C. ER-D outperforms all
baselines. LLaMA-7B with ER-D (56.4) is able to significantly outperform much
larger models: LLaMA-65B (51.6) (Touvron et al., 2023) and PaLM-540B (49.1)
(Chowdhery et al., 2022).

#### HHH

HHH (Helpful, Honest and Harmless) (Srivastava et al., 2023; Askell et al.,
2021) is a dataset of 200 multiple-choice designed to measure LM alignment
with high-level quality guidelines. Here we use a different set of prompts for
the generator (see Appendix B). Results are presented in the last row of Table
1. LLaMA-7B with ER-D outperforms baselines; although LLaMA-13B with ER-D with
the default parameter performs worse than discriminative ranking (D) (69.2),
ER-D with
$\lambda_{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}\textsf{G}}=0.01$
and
$\lambda_{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}\textsf{D}}=1.0$
achieves an accuracy of 70.6%.

#### TruthfulQA

TruthfulQA (Lin et al., 2022) is a benchmark consisting of over 800 questions
across a multitude of domains that were crafted to encourage humans to answer
them incorrectly due to misconceptions. The dataset evaluates a model’s
ability to not generate false answers learnt from imitation learning on text.
On this task, we consider greedy decoding in addition to our other ranking-
based approaches. In this setting, 10 candidate sequences are sampled using
nucleus and top-k sampling. These candidates are then ranked based on the
approaches we described earlier. The results on the test set are presented in
Table 2. Based on past work (Lin et al., 2022), we measure BLEU accuracy
(BLEU-Acc). For a sequence $a$, the BLEU-Acc over reference correct candidates
$b_{\text{correct}}$ and reference incorrect candidates $b_{\text{correct}}$
is computed as follows:

$\displaystyle\text{BLEU-
Acc}(a)\coloneqq\mathbb{I}(\text{BLEU}(a,b_{\text{correct}})>\text{BLEU}(a,b_{\text{incorrect}}))$
(3)

Where $\text{BLEU}(a,b)$ computes the BLEU score (Papineni et al., 2002) of a
candidate string $a$ over a set of reference candidates $b$. With LLaMA-7B, we
observe only modest improvements for ER-G and ER-D over the greedy baseline.
However, with LLaMA-13B, we note increased scores for both methods. This
benchmark is known to exhibit negative scaling (Lin et al., 2022) (performance
drop as the model size increases). The performance difference with ER-G
between LLaMA-7B and LLaMA-13B shows that equilibrium-ranking is in fact
capable of mitigating this behavior.

|  |  |  |  |  | Equil. ranking
---|---|---|---|---|---|---
Domain | Model | Greedy | MI | SC | D | ER-G | ER-D
TruthfulQA | LLaMA-7B |  33.41 |  34.79 $\pm$ 0.90 |  34.91
$\pm$ 0.57 |  34.17 $\pm$ 1.19 |  34.61 $\pm$ 0.99 |  34.27 $\pm$ 0.39
LLaMA-13B |  33.05 |  36.30 $\pm$ 0.37 |  34.61 $\pm$ 1.33 |  39.05 $\pm$ 1.42 |  39.83
$\pm$ 2.20 |  38.63 $\pm$ 1.76
Table 2: Results on TruthfulQA (Generative). Average BLEU-Acc results on the
held-out set across 5 runs. LLaMA-13B with ER-G outperforms or is on par with
all baselines. MI: Mutual Information Ranking, SC: Self-Contrastive Ranking,
D: Discriminative Ranking, ER-G: Equilibrium Ranking Generator, ER-D:
Equilibrium Ranking Discriminator. $\pm$ indicates 1 standard deviation
computed across 5 runs. Colors are as in Table 1, relative to the Greedy
baseline.

#### GSM8K

In our last set of experiments, we consider grade-school math (GSM8K) (Cobbe
et al., 2021), a popular benchmark used to study model’s mathematical
reasoning ability. We use this benchmark to study whether we can combine our
approach with chain-of-thought (Wei et al., 2022). As we described earlier, we
generate 20 candidate reasoning paths sampled using nucleus and top-k using
the 8-shot setup proposed in Wei et al. (2022). We employ self-consistency
(Wang et al., 2022) over the candidate sequences, where we score each
reasoning path with our baselines. Finally, we aggregate the scores for each
answer corresponding to the reasoning paths and pick the answer with the
highest score. In Table 3, we present the results. We note that equilibrium-
ranking-based approaches performs on par or slightly better compared to self-
consistency (majority vote).

|  |  |  |  |  |  | Equil. ranking
---|---|---|---|---|---|---|---
Domain | Model | Greedy | MV | MI | SC | D | ER-G | ER-D
GSM8K | LLaMA-7B |  10.8 |  14.7 $\pm$ 0.2 |  14.6 $\pm$ 0.5 |  13.4 $\pm$ 0.3 |  15.0 $\pm$ 0.6 |  13.0 $\pm$ 0.5 |  15.1
$\pm$ 0.6
LLaMA-13B |  14.9 |  22.5 $\pm$ 0.5 |  22.5 $\pm$ 0.8 |  23.1
$\pm$ 0.5 |  22.5 $\pm$ 0.6 |  22.5 $\pm$ 0.6 |  23.0 $\pm$ 0.5
Table 3: Average accuracy of methods on the test set of GSM8K acroos 5 runs.
In all cases, except greedy, 20 candidates were sampled. equilibrium-ranking-
based approaches performs on par or slightly better compared to the majority
vote baseline. MV: Majority Vote, MI: Mutual Information Ranking, SC: Self-
Contrastive Ranking, D: Discriminative Ranking, ER-G: Equilibrium Ranking
Generator, ER-D: Equilibrium Ranking Discriminator. $\pm$ indicates 1 standard
deviation. Colors are as in Table 1, relative to the Greedy basline.

#### Discussion

The application of equilibrium-ranking-based approaches consistently yields
improved results, surpassing or at least matching the performance of all
baseline approaches across various tasks. This robustness is particularly
interesting, as it demonstrates that equilibrium-ranking is adept at handling
diverse scenarios, even in situations when the initial generator or
discriminator are not effective. As equilibrium-ranking is a sampling
strategy, it can even be combined with deliberation methods like self-
consistency (Wang et al., 2022) or tree-of-thought (Yao et al., 2023).
Finally, we note that equilibrium-ranking demonstrates computational
efficiency by eliminating the need for repetitive queries to language models.

##  4 Other Related Work

Many decoding strategies have been proposed for language models, such as top-k
sampling (Fan et al., 2018a), nucleus sampling (Holtzman et al., 2020), and
typical sampling (Meister et al., 2023). These methods primarily focus on
producing diverse, high-quality text from a language model. However, they
decode from the LM without any emphasis on the correctness of the generated
sequences. As we show in Section 3, equilibrium-ranking is naturally
complementary and be combined with any of these sampling strategies.

Re-ranking is a common approach for selecting the correct answer from a set of
candidates sampled from LM. Cobbe et al. (2021) train a verifier to re-ranked
the sampled outputs. Shen et al. (2021) jointly train a ranking model with the
generation model to improve the model accuracy. Thoppilan et al. (2022)
collect additional human annotations to train the ranking model for response
filtering. As we discuss in Section 2, our work focuses on leveraging an
existing LM and using them in a training-free manner as a discriminator.
However, we note that we do not make any specific assumption on the specific
form of a the generator or discriminator. As such, equilibrium-ranking can be
combined with these approaches.

As previously mentioned, equilibrium-ranking differs from recent deliberation
methods, as highlighted in various recent work (Wei et al., 2022; Madaan et
al., 2023; Shinn et al., 2023; Yao et al., 2023; Dohan et al., 2022). In
Section 3, we demonstrate how equilibrium-ranking can be integrated with these
approaches. In another line of work, Du et al. (2023) and Chen et al. (2023a)
employ multiple instances of language models suggest and ”debate” individual
responses and reasoning processes across multiple iterations, ultimately
converging on a shared final answer. In contrast, equilibrium-ranking can be
viewed as a variant of this multi-agent debate, wherein the ”debate” occurs
within the regret-minimization framework rather than in the context of
language models.

##  5 Conclusion

We have presented equilibrium-ranking, a training-free, game theoretic
approach for generating from language models (LMs). equilibrium-ranking
reconciles scores from generative and discriminative LM decoding procedures by
formulating decoding as an imperfect-information signaling game between a
generator and a discriminator, and leveraging computational game solving
techniques to compute approximate equilibria of this game. When applied to 6
diverse question answering benchmarks: MMLU, ARC, RACE, HHH, TruthfulQA and,
GSM8K, equilibrium-ranking offers substantial improvements over existing
generative, discriminative, and mixed decoding procedures: applying
equilibrium-ranking to LLaMA-7B sometimes outperforms much larger LLaMA-65B
and PaLM-540B models. These results highlight the usefulness of game-theoretic
tools in formalizing desiderata like truthfulness and stability in language
modeling. Beyond the applications studied here (which focus mainly on question
answer), future work might apply this toolkit to more general tasks like long-
form text generation.

## References

  * Anagnostides et al. (2022) Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm.  On last-iterate convergence beyond zero-sum games.  In _International Conference on Machine Learning_ , 2022.
  * Askell et al. (2021) Amanda Askell, Yuntao Bai, Anna Chen, Dawn Drain, Deep Ganguli, Tom Henighan, Andy Jones, Nicholas Joseph, Ben Mann, Nova DasSarma, et al.  A general language assistant as a laboratory for alignment.  _arXiv preprint arXiv:2112.00861_ , 2021.
  * Bakhtin et al. (2023) Anton Bakhtin, David J Wu, Adam Lerer, Jonathan Gray, Athul Paul Jacob, Gabriele Farina, Alexander H Miller, and Noam Brown.  Mastering the game of no-press Diplomacy via human-regularized reinforcement learning and planning.  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * Brown & Sandholm (2018) Noam Brown and Tuomas Sandholm.  Superhuman ai for heads-up no-limit poker: Libratus beats top professionals.  _Science_ , 359(6374):418–424, 2018.
  * Brown & Sandholm (2019) Noam Brown and Tuomas Sandholm.  Superhuman ai for multiplayer poker.  _Science_ , 365(6456):885–890, 2019.
  * 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.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Chen et al. (2023a) Justin Chih-Yao Chen, Swarnadeep Saha, and Mohit Bansal.  Reconcile: Round-table conference improves reasoning via consensus among diverse llms.  _arXiv preprint arXiv:2309.13007_ , 2023a.
  * Chen et al. (2023b) Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou.  Teaching large language models to self-debug.  _arXiv preprint arXiv:2304.05128_ , 2023b.
  * Chen et al. (2022) Yangyi Chen, Lifan Yuan, Ganqu Cui, Zhiyuan Liu, and Heng Ji.  A close look into the calibration of pre-trained language models.  _arXiv preprint arXiv:2211.00151_ , 2022.
  * Chowdhery et al. (2022) Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al.  Palm: Scaling language modeling with pathways.  _arXiv preprint arXiv:2204.02311_ , 2022.
  * Clark et al. (2018) Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord.  Think you have solved question answering? try arc, the ai2 reasoning challenge.  _arXiv preprint arXiv:1803.05457_ , 2018.
  * Cobbe et al. (2021) Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman.  Training verifiers to solve math word problems, 2021.
  * Dohan et al. (2022) David Dohan, Winnie Xu, Aitor Lewkowycz, Jacob Austin, David Bieber, Raphael Gontijo Lopes, Yuhuai Wu, Henryk Michalewski, Rif A Saurous, Jascha Sohl-Dickstein, et al.  Language model cascades.  _arXiv preprint arXiv:2207.10342_ , 2022.
  * Du et al. (2023) Yilun Du, Shuang Li, Antonio Torralba, Joshua B Tenenbaum, and Igor Mordatch.  Improving factuality and reasoning in language models through multiagent debate.  _arXiv preprint arXiv:2305.14325_ , 2023.
  * FAIR et al. (2022) Meta FAIR, Anton Bakhtin, Noam Brown, Emily Dinan, Gabriele Farina, Colin Flaherty, Daniel Fried, Andrew Goff, Jonathan Gray, Hengyuan Hu, et al.  Human-level play in the game of diplomacy by combining language models with strategic reasoning.  _Science_ , 378(6624):1067–1074, 2022.
  * Fan et al. (2018a) Angela Fan, Mike Lewis, and Yann Dauphin.  Hierarchical neural story generation.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 889–898, Melbourne, Australia, July 2018a. Association for Computational Linguistics.  doi: 10.18653/v1/P18-1082.  URL https://aclanthology.org/P18-1082.
  * Fan et al. (2018b) Angela Fan, Mike Lewis, and Yann Dauphin.  Hierarchical neural story generation.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 889–898, 2018b.
  * Farina et al. (2019) Gabriele Farina, Christian Kroer, and Tuomas Sandholm.  Online convex optimization for sequential decision processes and extensive-form games.  In _AAAI Conference on Artificial Intelligence (AAAI)_ , 2019.
  * Franke (2013) Michael Franke.  Game theoretic pragmatics.  _Philosophy Compass_ , 8(3):269–284, 2013.
  * Franke (2017) Michael Franke.  Game theory in pragmatics: Evolution, rationality, and reasoning.  In _Oxford Research Encyclopedia of Linguistics_. 2017.
  * Ganguli et al. (2023) Deep Ganguli, Amanda Askell, Nicholas Schiefer, Thomas I. Liao, Kamilė Lukošiūtė, Anna Chen, Anna Goldie, Azalia Mirhoseini, Catherine Olsson, Danny Hernandez, Dawn Drain, Dustin Li, Eli Tran-Johnson, Ethan Perez, Jackson Kernion, Jamie Kerr, Jared Mueller, Joshua Landau, Kamal Ndousse, Karina Nguyen, Liane Lovitt, Michael Sellitto, Nelson Elhage, Noemi Mercado, Nova DasSarma, Oliver Rausch, Robert Lasenby, Robin Larson, Sam Ringer, Sandipan Kundu, Saurav Kadavath, Scott Johnston, Shauna Kravec, Sheer El Showk, Tamera Lanham, Timothy Telleen-Lawton, Tom Henighan, Tristan Hume, Yuntao Bai, Zac Hatfield-Dodds, Ben Mann, Dario Amodei, Nicholas Joseph, Sam McCandlish, Tom Brown, Christopher Olah, Jack Clark, Samuel R. Bowman, and Jared Kaplan.  The capacity for moral self-correction in large language models, 2023.
  * Glaese et al. (2022) Amelia Glaese, Nat McAleese, Maja Trebacz, John Aslanides, Vlad Firoiu, Timo Ewalds, Maribeth Rauh, Laura Weidinger, Martin Chadwick, Phoebe Thacker, et al.  Improving alignment of dialogue agents via targeted human judgements.  _arXiv preprint arXiv:2209.14375_ , 2022.
  * Han et al. (2022) Zhixiong Han, Yaru Hao, Li Dong, Yutao Sun, and Furu Wei.  Prototypical calibration for few-shot learning of language models.  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Hendrycks et al. (2020) Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt.  Measuring massive multitask language understanding.  In _International Conference on Learning Representations_ , 2020.
  * Holtzman et al. (2019) Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi.  The curious case of neural text degeneration.  In _International Conference on Learning Representations_ , 2019.
  * Holtzman et al. (2020) Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi.  The curious case of neural text degeneration.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=rygGQyrFvH.
  * Jacob et al. (2022) Athul Paul Jacob, David J. Wu, Gabriele Farina, Adam Lerer, Hengyuan Hu, Anton Bakhtin, Jacob Andreas, and Noam Brown.  Modeling strong and human-like gameplay with kl-regularized search.  In _International Conference on Machine Learning_ , 2022.
  * Jiang et al. (2020) Zhengbao Jiang, Frank F Xu, Jun Araki, and Graham Neubig.  How can we know what language models know?  _Transactions of the Association for Computational Linguistics_ , 8:423–438, 2020.
  * Lai et al. (2017) Guokun Lai, Qizhe Xie, Hanxiao Liu, Yiming Yang, and Eduard Hovy.  Race: Large-scale reading comprehension dataset from examinations.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pp. 785–794, 2017.
  * Lewis (2008) David Lewis.  _Convention: A philosophical study_.  John Wiley & Sons, 2008.
  * Li & Jurafsky (2016) Jiwei Li and Dan Jurafsky.  Mutual information and diverse decoding improve neural machine translation.  _arXiv preprint arXiv:1601.00372_ , 2016.
  * Li et al. (2022) Xiang Lisa Li, Ari Holtzman, Daniel Fried, Percy Liang, Jason Eisner, Tatsunori Hashimoto, Luke Zettlemoyer, and Mike Lewis.  Contrastive decoding: Open-ended text generation as optimization.  _arXiv preprint arXiv:2210.15097_ , 2022.
  * Lin et al. (2022) Stephanie Lin, Jacob Hilton, and Owain Evans.  Truthfulqa: Measuring how models mimic human falsehoods.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 3214–3252, 2022.
  * Madaan et al. (2023) Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark.  Self-refine: Iterative refinement with self-feedback, 2023.
  * McKenzie et al. (2023) Ian R McKenzie, Alexander Lyzhov, Michael Pieler, Alicia Parrish, Aaron Mueller, Ameya Prabhu, Euan McLean, Aaron Kirtland, Alexis Ross, Alisa Liu, et al.  Inverse scaling: When bigger isn’t better.  _arXiv preprint arXiv:2306.09479_ , 2023.
  * Meister et al. (2023) Clara Isabel Meister, Tiago Pimentel, Gian Wiher, and Ryan Cotterell.  Locally typical sampling.  _Transactions of the Association for Computational Linguistics_ , 11:102–121, 2023.
  * Mitchell et al. (2022) Eric Mitchell, Joseph Noh, Siyan Li, Will Armstrong, Ananth Agarwal, Patrick Liu, Chelsea Finn, and Christopher D Manning.  Enhancing self-consistency and performance of pre-trained language models through natural language inference.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pp. 1754–1768, 2022.
  * Monderer & Shapley (1996) Dov Monderer and Lloyd S. Shapley.  Potential games.  _Games and Economic Behavior_ , 1(14):124–143, 1996.
  * Ouyang et al. (2022) Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al.  Training language models to follow instructions with human feedback.  _Advances in Neural Information Processing Systems_ , 35:27730–27744, 2022.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th annual meeting of the Association for Computational Linguistics_ , pp. 311–318, 2002.
  * Perolat et al. (2022) Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T Connor, Neil Burch, Thomas Anthony, et al.  Mastering the game of stratego with model-free multiagent reinforcement learning.  _Science_ , 378(6623):990–996, 2022.
  * Shen et al. (2021) Jianhao Shen, Yichun Yin, Lin Li, Lifeng Shang, Xin Jiang, Ming Zhang, and Qun Liu.  Generate & rank: A multi-task framework for math word problems.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pp. 2269–2279, Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.findings-emnlp.195.  URL https://aclanthology.org/2021.findings-emnlp.195.
  * Shinn et al. (2023) Noah Shinn, Federico Cassano, Beck Labash, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao.  Reflexion: Language agents with verbal reinforcement learning, 2023.
  * 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.  Beyond the imitation game: Quantifying and extrapolating the capabilities of language models.  _Transactions on Machine Learning Research_ , 2023.
  * Thoppilan et al. (2022) Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam Shazeer, Apoorv Kulshreshtha, Heng-Tze Cheng, Alicia Jin, Taylor Bos, Leslie Baker, Yu Du, YaGuang Li, Hongrae Lee, Huaixiu Steven Zheng, Amin Ghafouri, Marcelo Menegali, Yanping Huang, Maxim Krikun, Dmitry Lepikhin, James Qin, Dehao Chen, Yuanzhong Xu, Zhifeng Chen, Adam Roberts, Maarten Bosma, Vincent Zhao, Yanqi Zhou, Chung-Ching Chang, Igor Krivokon, Will Rusch, Marc Pickett, Pranesh Srinivasan, Laichee Man, Kathleen Meier-Hellstern, Meredith Ringel Morris, Tulsee Doshi, Renelito Delos Santos, Toju Duke, Johnny Soraker, Ben Zevenbergen, Vinodkumar Prabhakaran, Mark Diaz, Ben Hutchinson, Kristen Olson, Alejandra Molina, Erin Hoffman-John, Josh Lee, Lora Aroyo, Ravi Rajakumar, Alena Butryna, Matthew Lamm, Viktoriya Kuzmina, Joe Fenton, Aaron Cohen, Rachel Bernstein, Ray Kurzweil, Blaise Aguera-Arcas, Claire Cui, Marian Croak, Ed Chi, and Quoc Le.  Lamda: Language models for dialog applications, 2022.
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_ , 2023.
  * Wang et al. (2022) Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou.  Self-consistency improves chain of thought reasoning in language models.  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in Neural Information Processing Systems_ , 35:24824–24837, 2022.
  * 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.
  * Zinkevich et al. (2007) Martin Zinkevich, Michael Bowling, Michael Johanson, and Carmelo Piccione.  Regret minimization in games with incomplete information.  In _Neural Information Processing Systems (NIPS)_ , 2007.

##  Appendix A Details about Regret and Regret Decomposition Methods

After each repetition $t$ of the game, each player—in this case, the generator
and the discriminator—refines their policies, in such a way that throughout
the course of time, the _regrets_

$\displaystyle\mathrm{Reg}^{(T)}_{G}$
$\displaystyle\coloneqq\max_{\pi^{*}_{G}}\left\\{\sum_{t=1}^{T}u_{G}(\pi^{*}_{G},\pi^{(t)}_{D})-\sum_{t=1}^{T}u_{G}(\pi^{(t)}_{G},\pi^{(t)}_{D})\right\\},$
(4) $\displaystyle\mathrm{Reg}^{(T)}_{D}$
$\displaystyle\coloneqq\max_{\pi^{*}_{D}}\left\\{\sum_{t=1}^{T}u_{D}(\pi^{(t)}_{G},\pi^{*}_{D})-\sum_{t=1}^{T}u_{D}(\pi^{(t)}_{G},\pi^{(t)}_{D})\right\\},$
(5)

cumulated by the players are guaranteed to grow sublinearly as a function of
the number of rounds of learning $T$.

As mentioned in the body, a classic observation in the theory of imperfect-
information sequential games is that minimization of regret (viewed as a
function of their overall policy on the game tree) can be achieved by solving
separate, _local_ , regret minimization problems at each information set
(i.e., decision point) of the game. In our case, these techniques enable us to
decompose the policy update of the players into separate updates for each
correctness parameter $v$ (for the generator) and for each sequence $y$ (for
the discriminator). More specifically, suppose that the generator updates
their policies $\pi_{G}^{(t)}(\cdot\mid x,v)$ independently for each
correctness parameter
$v\in\\{\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}},\texttt{{\color[rgb]{0.525,0,0.175}\definecolor[named]{pgfstrokecolor}{rgb}{0.525,0,0.175}incorrect}}\\}$
they might receive, seeking to independently minimize regret

$\mathrm{Reg}^{(T)}_{G}(v)\coloneqq\max_{\pi^{*}\in\Delta(\mathcal{Y})}\left\\{\sum_{t=1}^{T}\tilde{u}^{(t)}_{G}(\pi^{*}\mid
x,v)-\tilde{u}^{(t)}_{G}(\pi_{G}^{(t)}(\cdot\mid x,v)\mid x,v)\right\\}$

with respect to the following _counterfactual utility functions_

$\displaystyle\tilde{u}^{(t)}_{G}(\pi_{G}\mid
x,v)\coloneqq-\lambda_{G}\mathrm{D}_{\mathrm{KL}}\bigg{(}\pi_{G}(\cdot\mid
x,v)\,\bigg{\|}\,\pi_{G}^{(0)}(\cdot\mid
x,v)\bigg{)}+\frac{1}{2}\sum_{y\in\mathcal{Y}}\pi^{(t)}_{D}(v\mid
x,y)\cdot\pi_{G}(y\mid x,v)$ (6)

for all $v$. Then, it is known that when these independent goals are met for
all $v$, so is the goal of keeping regret (4) subliner, and in particular

$\mathrm{Reg}^{(T)}_{G}\leq\mathrm{Reg}^{(T)}_{G}(\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}})+\mathrm{Reg}^{(T)}_{G}(\texttt{{\color[rgb]{0.525,0,0.175}\definecolor[named]{pgfstrokecolor}{rgb}{0.525,0,0.175}incorrect}})$

no matter the time horizon $T$. Similarly, when the discriminator seeks to
update their policy $\pi_{D}^{(t)}(\cdot\mid x,y)$ for each $y\in\mathcal{Y}$
independently, so as to minimize regret

$\mathrm{Reg}^{(T)}_{D}(y)\coloneqq\max_{\pi^{*}\in\Delta(\\{\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}},\texttt{{\color[rgb]{0.525,0,0.175}\definecolor[named]{pgfstrokecolor}{rgb}{0.525,0,0.175}incorrect}}\\})}\left\\{\sum_{t=1}^{T}\tilde{u}^{(t)}_{D}(\pi^{*}\mid
x,y)-\tilde{u}^{(t)}_{D}(\pi_{D}^{(t)}(\cdot\mid x,y)\mid x,y)\right\\}$

with respect to the counterfactual utility functions

$\displaystyle\tilde{u}^{(t)}_{D}(\pi_{D}\mid
x,y)\coloneqq-\lambda_{D}\mathrm{D}_{\mathrm{KL}}\bigg{(}\pi_{D}(\cdot\mid
x,y)\,\bigg{\|}\,\pi_{D}^{(0)}(\cdot\mid
x,y)\bigg{)}+\frac{1}{2}\sum_{\begin{subarray}{c}v\in\\{\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}},\\\
\texttt{{\color[rgb]{0.525,0,0.175}\definecolor[named]{pgfstrokecolor}{rgb}{0.525,0,0.175}incorrect}}\\}\end{subarray}}\\!\\!\\!\\!\\!\pi^{(t)}_{G}(v\mid
x,y)\cdot\pi_{D}(v\mid x,y),$

then their overall regret $\mathrm{Reg}^{(T)}_{D}$ satisfies

$\mathrm{Reg}^{(T)}_{D}\leq\sum_{y\in\mathcal{Y}}\mathrm{Reg}^{(t)}_{D}(y).$

The counterfactual utilities $\tilde{u}_{G}$ and $\tilde{u}_{D}$ defined above
are composed of a bilinear term and a strongly convex KL-regularization term.
To guarantee sublinear regret with respect to such utility functions, we use
the piKL algorithm Jacob et al. (2022).

###  A.1 Guarantees of the piKL No-Regret Dynamics

We recall the following known properties of the piKL algorithm. An informal
description of the guarantees was included in Section 2.

######  Proposition 1 (Bakhtin et al. 2023).

Let
$i\in\\{\textsc{{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}generator}},\textsc{{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}discriminator}}\\}$
be any player. After any $T$ iterations of training, the regret
$\mathrm{Reg}_{i}^{(T)}$ cumulated by the policies $\pi_{i}^{(t)}$ of player
$i$ produced by piKL, is upper bounded by only a logarithmic quantity in $T$.
More precisely, $\mathrm{Reg}_{i}^{(T)}=O\left(\min\left\\{\frac{2\log
T}{\lambda_{i}},T\eta_{i}\right\\}+\frac{\log|\mathcal{Y}|}{\eta_{i}}\right)$,
where the asymptotic $O$ notation hides constants independent on the time
horizon $T$, learning rate $\eta_{i}$ of the player, and regularization
coefficient $\lambda_{i}$.

######  Proposition 2 (Folklore connection between regret minimization and
equilibria).

The empirical frequency of play converges to the set of coarse correlated
equilibria of the consensus game.

######  Proposition 3 (Jacob et al. 2022).

The average policy $\bar{\pi}^{(T)}_{i}$ of player
$i\in\\{\textsc{{\color[rgb]{0,0.3,0.3}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.3,0.3}generator}},\textsc{{\color[rgb]{0.45,0.3,0.15}\definecolor[named]{pgfstrokecolor}{rgb}{0.45,0.3,0.15}discriminator}}\\}$
produced by piKL after $T$ iterations is guaranteed to be within a radius
proportional to $\lambda_{i}$ centered in the initial policy $\pi_{i}^{(1)}$.
More precisely,
$\mathrm{D}_{\mathrm{KL}}(\bar{\pi}^{(T)}_{i},\pi_{i}^{(1)})\leq\frac{1}{\lambda_{i}}(1+o(1))$,
where the asymptotic notation $o(1)$ denotes a quantity decreasing, as a
function of the time horizon $T$, at a rate of $\log T/(\lambda_{i}T)$.

##  Appendix B HHH Prompts

In the HHH experiments,
$(x,\texttt{{\color[rgb]{0,0.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.5,0}correct}})$
corresponds to the prompt:
"You are a helpful, honest and harmless assistant.
Human: {x}
Assistant:"

And
$(x,\texttt{{\color[rgb]{0.525,0,0.175}\definecolor[named]{pgfstrokecolor}{rgb}{0.525,0,0.175}incorrect}})$
corresponds to the prompt:
"You are a unhelpful, dishonest and harmful assistant.
Human: {x}
Assistant:"


# Conormal homology of manifolds with corners

Thomas Schick  e-mail<EMAIL_ADDRESS>www:
http://www.uni-math.gwdg.de/schick Mathematisches Institut
Universität Göttingen
Germany  and  Mario Velásquez<EMAIL_ADDRESS>https://sites.google.com/site/mavelasquezm/ Current addresss: Departamento de
Matemáticas
Universidad Nacional de Colombia
Cra. 30 cll 45 - Ciudad Universitaria
Bogotá, Colombia

(Date: November 2021)

###### Abstract.

Given a manifold with corners $X$, we associates to it the corner structure
simplicial complex $\Sigma_{X}$. Its reduced K-homology is isomorphic to the
K-theory of the $C^{*}$-algebra $\mathcal{K}_{b}(X)$ of b-compact operators on
$X$. Moreover, the homology of $\Sigma_{X}$ is isomorphic to the conormal
homology of $X$.

In this note, we constract for an arbitrary abstract finite simplicial complex
$\Sigma$ a manifold with corners $X$ such that $\Sigma_{X}\cong\Sigma$. As a
consequence, the homology and K-homology which occur for finite simplicial
complexes also occur as conormal homology of manifolds with corners and as
K-theory of their b-compact operators. In particular, these groups can contain
torsion.

This work was carried out during a research stay of the second author at
Univerity of Göttingen funded by the German Science Foundation RTG “Fourier
analysis and spectral theory”

##  1\. Introduction

In this note we contribute to the index theory and homology of compact
manifolds with corners. More specifically, a fundamental question in this
field asks for obstructions to the Fredholm property for boundary value
problems, initiated in [3]. Let $X$ be such a manifold with corners. The
geometrically relevant boundary value problems (and their inverses) are
contained in the algebra of b-pseudodifferential operators as introduced by
[6]. Given such an operator which is _elliptic_ (has an elliptic principal
symbol) it is in general not true that the operator is Fredholm.

In this situation, on asks if one can find a smoothing perturbation (possibly
after stabilization) to render the given operator Fredholm. If this is
possible, the operator satisfies the stable Fredholm perturbation property
(SFP). As one can guess, not all operators have the SFP: it is proven in [7]
that the obstruction to this is precisely the boundary analytic index which
takes values in $K_{*}(\mathcal{K}_{b}(\partial X))$ where
$\mathcal{K}_{b}(\partial X)$ is the $C^{*}$-algebra of b-compact operators on
the boundary of $X$. A modern proof of the same fact, using deformation
groupoids, is given in [8]. By [3, Proposition 5.6], the restriction to the
boundary induces an isomorphism $K_{*}(\mathcal{K}_{b}(X))\to
K_{*}(\mathcal{K}_{b}(\partial X))$ provided $\partial X\neq\emptyset$.

It turns out that the relevant group $K_{*}(\mathcal{K}_{b}(X))$ depends only
on the combinatorics of the faces of the manifold with corners $X$ and how
they intersect. Indeed, one essentially can compute these K-groups
combinatorially. To this end, Bunke [2] introduced the _conormal homology_ of
$X$ (called differently in [2]), computed from a chain complex generated
abstractly by the faces of $X$. In [3], it is shown that this conormal
homology contains the obstructions to SFP if the corners in $X$ are of
codimension $\leq 3$.

More systematically, in [9] a natural Chern character

(1) $K_{*}(\mathcal{K}_{b}(X))\to H^{cn}_{*+2\mathbb{Z}}(X)\otimes\mathbb{Q}$

is constructed and proven to be rationally an isomorphism.

In the situation studied in [3] it is useful if the conormal homology is
torsion free. There and in [9], the authors therefore ask if the conormal
homology always is torsion free, and whether prehaps the Chern character (1)
can be improved to an integral isomorphism.

The main goal of the present paper is to provide examples of manifolds with
corners which show that the conormal homology does not have any of these nice
properties. Instead, it can be as rich as the homology of an arbitrary finite
simplicial complex. The same applies to the K-theory of $\mathcal{K}_{b}(X)$.

More specifically, in the present paper, we associate to a manifold with
embedded corners $X$ its _corner structure complex_ , a simplicial complex
$\Sigma_{X}$ encoding the _corner structure_ in such way that the reduced
K-homology of $\Sigma_{X}$ is isomorphic to the topological K-theory of the
$C^{*}$-algebra $\mathcal{K}_{b}(X)$, and the conormal homology of $X$
isomorphic to the homology of $\Sigma_{X}$. We then prove that every finite
simplicial complex can be realized as $\Sigma_{X}$ of some manifold with
embeded corners $X$.

In particular it implies that the conormal homology defined in [3] and [9] in
general does contain torsion.

##  2\. The corner structure complex of a manifold with corners

Let us recall the definition of a smooth manifold with embedded corners. We
adopt the approach where a manifold with corners is defined as a suitable
subset of a smooth ordinary manifold (without boundary).

######  Definition 2.1.

A compact smooth manifold with embedded corners $X$ is defined in the
following way. Start with a compact smooth manifold $\widetilde{X}$ (without
boundary) and with smooth maps
$\rho_{1},\ldots,\rho_{n}\colon\widetilde{X}\to\mathbb{R}$. Set

$H_{j}=\rho_{j}^{-1}(0)\cap X,\;j=1,\ldots,n,\quad
H_{j_{1},\dots,j_{k}}:=H_{j_{1}}\cap\ldots\cap H_{j_{k}}.$

such that

$\\{d\rho_{j_{1}},\ldots,d\rho_{j_{k}}\\}\text{ has maximum rank at each }x\in
H_{j_{1},\dots,j_{k}}\quad\forall\\{j_{1},\dots,j_{k}\\}\subset\\{0,\dots,n\\}$

This defines the manifold with corners $X$ as

  1. (1)

$X:=\bigcap_{j=1}^{n}\rho_{j}^{-1}([0,+\infty))\subseteq\widetilde{X}$.

  2. (2)

Each $H_{j}$ is called a _boundary component of codimension 1_.

  3. (3)

If $\left\lvert\\{j_{1},\dots,j_{k}\\}\right\rvert=k$ then we call
$H_{j_{1}}\cap\ldots\cap H_{j_{k}}$ a _face of codimension $k$_.

  4. (4)

We denote by $F_{k}$ to the set of faces of codimension $k$.

Throughout the paper, we assume that each face $H_{j_{1}}\cap\ldots\cap
H_{j_{k}}$ of arbitrary codimension is connected, in particular each boundary
component of codimension 1.

######  Definition 2.2.

Let $X$ be a manifold with embeded corners with $n+1$ boundary components
$H_{0}$,…, $H_{n}$ of codimension $1$. Define the _corner structure complex_
as the simplicial complex $\Sigma_{X}$ associated to $X$ with vertex set
$\\{H_{0},\ldots,H_{n}\\}$ with the following simplices: for
$A\subseteq\\{H_{0},\ldots,H_{n}\\}$

$A\in\Sigma_{X}$ if and only if $\bigcap_{i\in A}H_{i}\neq\emptyset$.

It is clear that $\Sigma_{X}$ is closed under inclusions and therefore is an
abstract simplicial complex.

######  Example 2.3.

  1. (1)

If $X$ be a smooth manifold without boundary then $\Sigma_{X}=\emptyset$.

  2. (2)

Let $(Y,\partial Y)$ be a connected manifold with connected boundary. Then
$\Sigma_{Y}$ is a point.

  3. (3)

More generally, set $X=\prod_{i=1}^{n}Y$. This is a manifold with embeded
corners and $\Sigma_{X}=\Delta_{n}$ is the $n$-simplex.

  4. (4)

Even more generally, if $X$ and $Y$ are manifolds with embeded corners then
$X\times Y$ evidently also is a manifold with embedded corners and
$\Sigma_{X\times Y}=\Sigma_{X}*\Sigma_{Y}$ is the join of the simplicial
complex $\Sigma_{X}$ and $\Sigma_{Y}$.

Here, the join of two simplicial complexes $\Sigma_{1},\Sigma_{2}$ has vertex
set the disjoint union $V(\Sigma_{1})\amalg V(\Sigma_{2})$ (where
$V(\Sigma_{j})$ is the vertex set of $\Sigma_{j}$). A subset $A\subset
V(\Sigma_{1})\amalg V(\Sigma_{2})$ is a simplex of $\Sigma_{1}*\Sigma_{2}$ if
and only if $A=A_{1}\amalg A_{2}$ with $A_{1}\in\Sigma_{1}$ and
$A_{2}\in\Sigma_{2}$.

Note that the geometric realisation of the join of simplicial complexes is the
topoolgical join of the geometric realisations of the individual simplicial
complexes.

  5. (5)

We can also directly construct a $n+2$ dimensional manifold $A$ with embeddeed
corners (all of whose faces are connected) such that
$\Sigma_{A}\cong\Delta_{n}$. For this aim, start with $\tilde{A}:=S^{n+2}$,
but decompose $S^{n+2}=S^{1}\times D^{n+1}\cup_{S^{1}\times S^{n}}D^{2}\times
S^{n}$. This way, we haven an obvious projection map to the second factor
$\pi\colon S^{n+2}\to D^{n+1}$, with $n+1$ component functions
$\rho_{1},\dots,\rho_{n+1}\colon\tilde{A}\to\mathbb{R}$. Then we set

$A:=\bigcup_{j=1}^{n+1}\\{\rho_{j}\geq 0\\}=S^{1}\times
Q^{n+1}\cup_{S^{1}\times(S^{n}\cap Q^{n+1})}D^{2}\times S^{n}\cap Q^{n+1},$

where we write $Q^{n+1}:=\\{(x_{1},\dots,x_{n+1})\in D^{n+1}\mid x_{j}\geq
0,\forall j\\}$, the positive hyperquadrant sector. Then $A$ is a manifold
with embedded corners with $\Sigma_{A}\cong\Delta_{n}$ and all faces are
connected.

  6. (6)

Let $X$ be a connected manifold with boundary with $n$ boundary components.
Then $\Sigma_{X}$ is the simplicial complex with $n$ points and no edges.

Our first main result is constructive: for every finite simplicial complex we
can construct a manifold with corners.

######  Theorem 2.4.

Let $\Sigma$ be an arbitrary finite simplicial complex. Then there exists a
compact manifold with embeded corners $X$ such that $\Sigma_{X}$ is isomorphic
to $\Sigma$.

As a preparation for the proof, we introduce further definitions.

######  Definition 2.5.

Let $X$ be a manifold with embeded corners and let $x_{0}\in X$, let $V_{0}$
be a coordinate neighborhood around $x_{0}$. Then $V_{0}$ is a manifold with
embeded corners and corner structure complex $\Sigma_{V_{0}}$ is called the
simplicial complex of $X$ around $x_{0}$. Given points $x_{0}\in X$ and
$y_{0}\in Y$, where $X$ and $Y$ are manifolds with embeded corners of the same
dimension, we say that _$x_{0}$ and $y_{0}$ have the same local corner
structure_ if the corner structure complexes of $X$ around $x_{0}$ and of $Y$
around $y_{0}$ are isomorphic.

Now we will define the connected sum around 0-dimensional submanifolds. This
will be a key ingredient in the constructions required to prove Theorem 2.4.

Let $X$ and $Y$ be manifolds with embeded corners of dimension $n$, let
$\\{x_{1},\ldots,x_{m}\\}\subseteq X$ and $\\{y_{1},\ldots,y_{m}\\}\subseteq
Y$ be finite subsets of $X$ and $Y$, respectively, such that for $i=1,\ldots
m$, $x_{i}$ and $y_{i}$ have the same local corner structure. By results in
[5] there are tubular neighbohoods $V$ and $W$ with

$\\{x_{1},\ldots,x_{m}\\}\subseteq V\subseteq X\text{ and
}\\{y_{1},\ldots,y_{m}\\}\subseteq W\subseteq Y.$

We have

$V\cong V_{1}\sqcup\ldots\sqcup V_{m}\text{ and }W\cong
W_{1}\sqcup\ldots\sqcup W_{m},$

where $V_{i}$ is a coordinate neighborhood of $x_{i}$ and $W_{i}$ is a
coordinate neighborhood of $y_{i}$. Then we can choose identifications

$V_{i}=(-1,1)^{n_{i}}\times[0,1)^{n-n_{i}}\subset(-1,1)^{n_{i}}\times(-1,1)^{n-n_{i}}=:\widetilde{V_{i}},$

and

$W_{i}=(-1,1)^{m_{i}}\times[0,1)^{n-m_{i}}\subset\widetilde{W_{i}}.$

In these coordinates, the face defining functions $\rho_{j}$ of Definition 2.1
are just the coordinate functions for the closed intervals.

Moreover, as $x_{i}$ and $y_{i}$ have the same local corner structure, we have
$n_{i}=m_{i}$.

We now follow the description of the ordinary connected sum in [4] to define
our connected sum of manifolds with corners.

######  Definition 2.6.

Define the _connected sum of $X$ and $Y$ along the subsets
$\\{x_{0},\ldots,x_{m}\\}$ and $\\{y_{0},\ldots,y_{m}\\}$_ as follows:

(2)
$(X,\\{x_{0},\ldots,x_{m}\\})\sharp(Y,\\{y_{0},\ldots,y_{m}\\}):=\frac{(X-\\{x_{0},\ldots,x_{m}\\})\bigsqcup(Y-\\{y_{0},\ldots,y_{m}\\})}{tz\in
V_{i}\sim(1-t)z\in W_{i}}$

for every $z\in S^{n-1}$. When $\\{x_{0},\ldots,x_{m}\\}$ and
$\\{y_{0},\ldots,y_{m}\\}$ are clear from the context, we denote the connected
sum by $X\sharp Y$.

###### Proof.

For the sake of completeness, let us give the details how it is an
straighforward verification that $X\sharp Y$ is a manifold with embeded
corners. To do so, we have to define the ambient smooth ordinary manifold and
the boundary defining functions.

Of course, the ambient manifold for the connected sum is defined as the
connected sum of the ambient manifolds $\tilde{X}$ of $X$ and $\tilde{Y}$ of
$Y$, defined precisely with the same formula as (2).

The boundary defining function $\rho_{j}$ remains unchanged outside the set
$V_{i}\sqcup W_{i}$ but have to be modified in the coordinate regions where
the identifications are carried out. We redefine $\rho_{j}$ on $V_{i}\sqcup
W_{i}$ by

$\rho_{j}(x):=\phi_{x}(\left\lvert x\right\rvert)\cdot x_{j};$

with and $\phi_{x}\colon(0,1)\to(0,1)$ a smooth monotonously decreasing
function with

$\phi_{x}(t)=\begin{cases}1;&t>0.6\\\ \frac{1-t}{t};&t<0.4\end{cases}$

In the coordinates of $W_{i}$, we have for $y\in W_{i}$ that $y\sim
x:=\frac{1-\left\lvert y\right\rvert}{\left\lvert y\right\rvert}y\in V_{i}$
and therefore

$\rho_{j}(y)=\begin{cases}\frac{1-\left\lvert y\right\rvert}{\left\lvert
y\right\rvert}y_{j};&1-\left\lvert y\right\rvert>0.6\equiv\left\lvert
y\right\rvert<0.4\\\ \frac{1-(1-\left\lvert y\right\rvert)}{\left\lvert
y\right\rvert}\frac{1-\left\lvert y\right\rvert}{\left\lvert
y\right\rvert}y_{j}=y_{j}&\left\lvert y\right\rvert>0.6\end{cases}$

We observe that we indeed defined a smooth function on the connected sum of
$\tilde{X}$ and $\tilde{Y}$ as the expressions are unchanged on the “outer”
part of $U_{i}$ or $V_{i}$, where the norm is $>0.6$. ∎

######  Remark 2.7.

The connected sum of two manifolds with corners $X$ and $Y$ will again be a
manifold with corners. However, even if all faces of arbitrary codimension of
$X$ and of $Y$ are connected, in general this will not be the case for
$X\sharp Y$.

######  Lemma 2.8.

Assume that $X$ is a compact manifold of dimension $d$ with embedeed corners
(all faces connected). Assume we have an embedding
$\iota\colon\partial\Delta_{n}\hookrightarrow\Sigma_{X}$, but the simplex
spanned by the vertices in the image of $\iota$ is not contained in
$\Sigma_{X}$.

Then for each $d^{\prime}\geq\max\\{d,n+2\\}$ there is a compact smooth
manifold $Z$ with embedded corners (all faces connected) such that
$\Sigma_{Z}\cong\Sigma_{X}\cup_{\iota}\Delta_{n}$, i.e. $\Sigma_{Z}$ is
isomorphic to the simplicial complex obtained from $\Sigma_{X}$ by adding the
simplex spanned by the image of $\iota$.

###### Proof.

We write $\Delta_{n}=\mathcal{P}(\\{0,\dots,n\\})$, the power set of
$\\{0,\dots,n\\}$. Taking the product with a smooth connected manifold, a
process which does not change the corner structure, we can assume that
$\dim(X)=d^{\prime}$. Let $H_{k}\subset X$ be the boundary component which
correspondgs to $\iota(k)$ for $k=0,\dots,n$, and set

$H_{k^{c}}:=\bigcap_{j\neq k}H_{j},$

the face of $X$ of codimension $n$ corresponding to
$\\{0,\dots,n\\}\setminus\\{k\\}\subset\partial\Delta_{n}$. By the assumption
that $\iota(\partial\Delta_{n})\subset\Sigma_{X}$ we have
$H_{k^{c}}\neq\emptyset$ and $\dim(H_{k^{c}})=d^{\prime}-(n-1)>0$ for all $k$.
Pick then $x_{k}\in(H_{k^{c}})^{\circ}$. The local corner structure around
$x_{k}$ is precisely the $(n-1)$-simplex spannde by
$\\{0,\dots,n\\}\setminus\\{k\\}$.

Choose a $d^{\prime}$-dimensional manifold $M$ with embedded corners (all
faces connected) with a fixed isomorphism
$\Delta_{n}\xrightarrow{\cong}\Sigma_{M}$. For this, start with $A$ of Example
2.3 (5) and take the cartesian product with a connected smooth manifold to
adjust the dimension. Given the fixed isomorphism $\Sigma_{M}\cong\Delta_{n}$,
let $H_{k}^{M}$ be the boundary face corresponding to the vertex $k$ of
$\Delta_{n}$ and set $H^{M}_{k^{c}}:=\bigcap_{j\neq k}H^{M}_{j}$. Note that
$\dim(H^{M}_{k^{c}})=d^{\prime}-n>0$ and pick
$y_{k}\in(H_{k^{c}}^{M})^{\circ}$, with local corner structure the
$(n-1)$-simplex spanned by $\\{0,\dots,n\\}\setminus\\{k\\}$.

Define now $Z:=(X;x_{0},\dots,x_{n})\\#(M;y_{0},\dots,y_{n})$, using at each
point the given identifications of the local corner structure with a
determined $(n-1)$-dimensional subsimplex of
$\Delta_{n}=\mathcal{P}(\\{0,\dots,n\\})$. This way, the face $H_{k}$ is glued
near the $n$ points $x_{j}$ with $j\in\\{0,\dots,n\\}\setminus\\{k\\}$ to the
face $H_{k}^{M}$. Moreover, for each $0\leq k_{0}<\dots<k_{\alpha}\leq n$ the
face $H_{k_{0}}\cap\dots H_{k_{\alpha}}$ is glued (at $n-\alpha$ points) to
the intersection face $H^{M}_{k_{0}}\cap\dots\cap H^{M}_{k_{\alpha}}$. It
follows that each face of arbitrary codimeision of $Z$ remains connected. The
boundary faces of $Z$ are in obvious bijection with those of $X$ and the
corner complex is a simplicial complex with vertex set the one of
$\Sigma_{X}$. As $H_{0}^{M}\cap\dots H_{n}^{M}\neq\emptyset$, taking
everything together, we now get
$\Sigma_{Z}=\Sigma_{X}\cup_{\iota(\partial\Delta_{n})}\iota(\Delta_{n})$. ∎

######  Theorem 2.9.

Let $K$ be a finite simplicial complex and let $n$ be the maximal dimension of
a simplex in $k$. If $d\geq n+2$ then there is a compact $d$-dimensional
manifold with embeded corners $X$ (all faces connected) such that

$\Sigma_{X}\cong K.$

###### Proof.

The result follows by induction on the number of positive dimensional
simplices in $K$.

By Example 2.3 (3) any 0-dimensional simplicial complex satisfies the result.

If $K$ contains a positive dimensional simplex, let $\sigma$ be one such of
maximal dimension. Then $K=K^{\prime}\cup_{\partial\sigma}\sigma$. By
induction, there exists the required $X^{\prime}$ with
$\Sigma_{X^{\prime}}\cong K^{\prime}$ and by Lemma 2.8 we then can also
construct the required $X$ with $\Sigma_{X}\cong K$. ∎

##  3\. Groupoids and the space $O_{X}$

Let $X$ be a manifold with embedded corners. In [9], for sufficiently large
$m$ a non-compact topological space $O_{X}$ is introduced such that we have a
Connes-Thom isomorphism

$CT\colon K_{*}(C^{*}(\mathcal{K}_{b}(X)))\xrightarrow{\cong}K^{m+*}(O_{X}).$

The space $O_{X}$ is constructed as the orbit space of a free and proper
groupoid. We recall this construction briefly.

Let $X$ be dfined by the smooth manifold $\widetilde{X}$ and the defining
functions $\rho_{1},\dots,\rho_{n}$, i.e.

$\bigcap_{j=1}^{n}\\{\rho_{j}\geq 0\\}=:X\subseteq\widetilde{X}.$

The puff groupoid is defined as a subgroupoid of
$\tilde{X}\times\tilde{X}\times\mathbb{R}^{n}$, where
$\tilde{X}\times\tilde{X}$ is the arrow space of the pair groupoid and where
$\mathbb{R}^{n}$ is the additive group (groupoid with one object). The arrow
space of the puff groupoid is then defined as

$G(\widetilde{X},(\rho_{i})):=\\{(x,y,\lambda_{1},\ldots,\lambda_{n})\in\widetilde{X}\times\widetilde{X}\times\mathbb{R}^{n}\mid\rho_{i}(x)=e^{\lambda_{i}}\rho_{i}(y)\\}.$

Denote by $G_{c}(\widetilde{X},(\rho_{i}))$ the s-connected component of
$G(\widetilde{X},(\rho_{i}))$.

Choose for sufficiently large an embedding

$\iota\colon\widetilde{X}\to\mathbb{R}^{m-n}$

.

Using this embedding, in [9, Section 3] the authors construct a new groupoid

$\mathbb{R}^{m}\rtimes_{\iota}G_{c}(\widetilde{X},(\rho_{i})_{i})\rightrightarrows\mathbb{R}^{m}\times\widetilde{X}.$

By [9, Proposition 3.1] this groupoid is a free and proper Lie groupoid (this
uses that all faces of each codimesion are connected). Hence the orbit space

$O_{\widetilde{X}}=Orb(G_{c}(\widetilde{X},(\rho_{i})_{i})\rtimes_{h}\mathbb{R}^{M})=\mathbb{R}^{m}\times\tilde{X}/\sim$

has a natural structure of smooth manifold. Decomposing $v\in\mathbb{R}^{m}$
as $v=(v^{\prime},v^{\prime\prime})\in\mathbb{R}^{m-n}\times\mathbb{R}^{n}$
set

$\displaystyle\widetilde{\rho}_{i}\colon O_{\widetilde{X}}$
$\displaystyle\to\mathbb{R}$ $\displaystyle[(v,x)]$
$\displaystyle\to\rho_{i}(x)e^{v_{i}^{\prime\prime}}.$

By [9, Section 3], these maps are indeed well defined and determine a manifold
with corners $O_{X}$:

######  Definition 3.1.

We denote by

$O_{X}=\bigcap_{i=1}^{n}\\{\widetilde{\rho}_{i}\geq 0\\}.$

In [9] is verified that $O_{X}$ is manifold with embeded corners with defining
functions $\widetilde{\rho}_{1},\ldots,\widetilde{\rho}_{n}$.

The main result in [9] is the following.

######  Theorem 3.2.

There is a Connes-Thom isomorphism

$CT_{h}\colon K_{*}(C^{*}(\mathcal{K}_{b}(X)))\to K^{m+*}(O_{X}).$

Here $K^{*}(O_{X})$ denotes topological K-theory with compact support.

##  4\. Relation between $\Sigma_{X}$ and $O_{X}$

In [9, Prop. 3.4], an explicit homeomorphism between $O_{X}$ and a subset
$\tilde{O}_{X}$ of $\mathbb{R}^{m}$ is constructed, which is entirely
determined by the combinatorics of the corner structure of $X$.

Canonically, $\tilde{O}_{X}$ is defined as subset of
$\mathbb{R}^{m-|V|}\times\mathbb{R}^{V}$ where $V$ is the set of boundary
faces of $X$, i.e. the vertex set of $\Sigma_{X}$. We denote the standard
basis vectors $\delta_{H}\in(\mathbb{R}_{\geq 0})^{V}$ for $H\in V$. Note that
then $|\Delta(V)|\subset\mathbb{R}^{V}$ is the convex hull of the
$\delta_{H}$, $H\in V$.

To define $\tilde{O}_{X}$, for every face $F$ of $X$ set

$B_{F}:=\\{x\in\mathbb{R}^{V}\mid x_{H}=0\text{ if }F\subset H,x_{H}>0\text{
if }F\cap H=\emptyset\iff F\nsubseteq H\\}.$

Recall that we have a correspondence between the faces $F$ and the subsets
$\sigma\in\Sigma_{X}\subset\mathcal{P}(V)$, namely $F=\bigcap_{H\in\sigma}H$,
and $B_{F}$ is the open positive quadrant “spanned” by all $\delta_{H}$ with
$H\notin\sigma$.

Define then

$\tilde{O}_{X}:=\mathbb{R}^{m-|V|}\times\bigcup_{F\text{ face of
}X}B_{F}=\mathbb{R}^{m-|V|}\times\amalg_{F\text{ face of }X}B_{F}.$

The computation in [9, Section 3] then gives a homeomorphism between $O_{X}$
and $\tilde{O}_{X}$.

Note that $\Sigma_{X}=\Delta(V)$ is the full simplex spanned by $V$ if and
only if $\tilde{O}_{X}=\mathbb{R}^{m-|V|}\times(\mathbb{R}_{\geq 0})^{V}$.
Otherwise, $0\notin\tilde{O}_{X}$ and we have a homeomorphism

$\tilde{O}_{X}\cong R^{m-|V|}\times\mathbb{R}_{>0}\times P_{X}$

where the factor $\mathbb{R}_{>0}$ is the norm (radial variable) and

$P_{X}=|\Delta(V)|\cap\tilde{O}_{X}\subset(\mathbb{R}_{\geq 0})^{V}.$

Observe that, if $F=\bigcap_{H\in\sigma}H$ then $B_{F}\cap|\Delta(V)|$ is the
interior of the convex hull $F_{V\setminus\sigma}$ of the $\delta_{H}$ for
$H\notin\sigma$.

$B_{F}\cap|\Delta(V)|=(F_{V\setminus\sigma})^{\circ}.$

Now

$|\Delta(V)|^{\circ}\subset P_{X}\subset|\Delta(V)|,$

i.e. $|\Delta(V)|$ is a compactification of $P_{X}$. This implies that we get
for the one-point compactification $(P_{X})^{+}$

$(P_{X})^{+}\cong|\Delta(V)|/(|\Delta(V)|\setminus P_{X}),$

i.e. we identify all the missing points in the compactification $|\Delta(V)|$
of $P_{X}$ to one point.

We next show that $|\Delta(V)|\setminus P_{X}$ is the geometric realization of
the dual of the simplicial complex $\Sigma_{X}$. First recall that the
geometric realization of a simplicial complex $K$ with vertex set $V$ can be
defined as follows:

If $I\subseteq V$, set

$F_{I}:=\text{closed convex hull of }\delta_{V},\;v\in H.$

Then

$|K|=\bigcup_{I\in K}F_{I}=\amalg_{I\in K}(F_{K})^{\circ}.$

Here we define the open face $F_{I}^{\circ}:=F_{I}\setminus\partial F_{I}$, in
particular $F_{\\{H\\}}=\\{\delta_{H}\\}$ is the singleton (not the empty
set).

Let us now also recall the definition of the dual of a simplicial complex.

######  Definition 4.1.

Let $K$ be a simplicial complex with vertex set $V$ . Then the (Alexander)
dual of $K$ is

$K^{\vee}=\\{A\subset V\mid V-A\notin K\\}.$

Note that, in particular,

(3) $|\Delta(V)|=\amalg_{\sigma\subset V}(F_{\sigma})^{\circ}.$

######  Lemma 4.2.

We have

$|\Sigma_{X}^{\vee}|=|\Delta(V)|\setminus P_{X}.$

###### Proof.

By definition,

(4)
$|\Sigma_{X}^{\vee}|=\amalg_{\sigma\in\Sigma_{X}^{\vee}}(F_{\sigma})^{\circ}=\amalg_{V\setminus\sigma\notin\Sigma_{X}}(F_{\sigma})^{\circ}$

On the other hand, as observed above,

(5)
$P_{X}=\amalg_{\sigma\in\Sigma_{X}}(F_{V\setminus\sigma})^{\circ}=\amalg_{V\setminus\sigma\in\Sigma_{X}}(F_{\sigma})^{\circ}.$

The three decompositions (3), (4) and (5) prove the claim. ∎

Then we have proved the following result.

######  Theorem 4.3.

Let $X$ be a manifold with embeded corners (all faces connected) such that
$\Sigma_{X}$ is not the full simplex on the vertex set $V$ with embedding
$\tilde{X}\to\mathbb{R}^{m-|V|}$ as above. Then there is a homeomorphism

$O_{X}\cong\mathbb{R}^{m-|V|+1}\times(|\Delta(V)|\setminus|\Sigma_{X}^{\vee}|),$

where $|\Sigma_{X}^{\vee}|$ denotes the geometric realization of the dual of
$\Sigma_{X}$.

To prove the main result of this note we need to recall the Spanier-Whitehead
duality theorem, for a proof see [1].

######  Theorem 4.4.

Let $E^{*}$ be a generalized cohomology theory with dual homology theory
$E_{*}$. let $|K|\subsetneq|\partial\Delta(V)|$ be the geometric realization
of a simplicial complex with vertex set $V$ consisting of $|V|$ elements, so
that $\dim(\partial|\Delta(V)|)=|V|-2$. Then there is a canonical isomorphism

$\widetilde{E}^{r}(|K|)\cong\widetilde{E}_{|V|-2-r}(|K^{\vee}|).$

Applying this to K-theory and to $|\Sigma_{X}|$ we obtain the following
theorem.

######  Theorem 4.5.

Let $X$ be a manifold with embeded corners with associated simplicial complex
$\Sigma_{X}\neq\Delta(V)$ on the vertex set $V$. Then we have a canonical
isomorphism

$K_{*}(C^{*}(\mathcal{K}_{b}(X)))\to\widetilde{K}_{-*}(|\Sigma_{X}|).$

###### Proof.

We already know by Theorem 3.2 that

$K_{*}(C^{*}(\mathcal{K}_{b}(X)))\to K^{m+*}(O_{X}).$

On the other hand, by definition

$K^{*}(O_{X})\cong\widetilde{K}^{*}((O_{X})^{+}),$

where $(O_{X})^{+}$ is the one-point compatification. But

$O_{X}^{+}\cong S^{m-|V|+1}\wedge P_{X}^{+}\cong
S^{m-|V|+1}\wedge\left(|\Delta(V)|/(|\Delta(V)|\setminus
P_{X})\right)=S^{m-|V|+1}\wedge\left(|\Delta(V)|/(|\Sigma_{X}^{\vee}|)\right).$

We therefore get

$\begin{split}K^{m+*}(\tilde{O}_{X})&=\widetilde{K}^{m+*}((\tilde{O}_{X})^{+})\\\
&\cong\widetilde{K}^{*+|V|-1}(|\Delta(V)|/|\Sigma_{X}^{\vee}|)\\\
&\cong\widetilde{K}^{*+|V|-2}(|\Sigma_{X}^{\vee}|)\\\
&\cong\widetilde{K}_{-*}(|\Sigma_{X}|).\end{split}$

Here, the first isomorphism is the definition of compactly supported K-theory,
the second is the suspension isomorphism, the third is the boundary map in the
long exact pair sequence, using that $|\Delta(V)|$ is contractible and the
last is Spanier-Whitehead duality. ∎

We get the corresponding result for conormal homology $H_{*}^{cn}(-)$ defined
in [3]. To prove this, one could construct a direct correspondence between the
chain complex which defines conormal homology and the simplicial chain complex
of $\Sigma_{X}$. We use the shortcut that in [9, Corollary 4.2] it is already
established that $H^{cn}_{*}(X)\cong H^{m-*}(O_{X})$. Combined with the
argument above, applied to ordinary (co)homology instead of K-theory, we
obtain the final result of this note.

######  Theorem 4.6.

Let $X$ be a manifold with embeded corners (all faces connected) with
associated simplicial complex $\Sigma_{X}$. Then we have an isomorphism

$H^{cn}_{*}(X)\to\widetilde{H}_{*}(|\Sigma_{X}|).$

In particular, Theorem 2.9 implies that for every finite abellian group there
are examples such conormal homology contains that torsion group.

## References

  * [1] J. F. Adams.  Stable homotopy and generalised homology.  Chicago Lectures in Mathematics. University of Chicago Press, Chicago, IL, 1995.  Reprint of the 1974 original.
  * [2] Ulrich Bunke.  Index theory, eta forms, and Deligne cohomology.  Mem. Amer. Math. Soc., 198(928):vi+120, 2009.
  * [3] Paulo Carrillo Rouse and Jean-Marie Lescure.  Geometric obstructions for Fredholm boundary conditions for manifolds with corners.  Ann. K-Theory, 3(3):523–563, 2018.
  * [4] Michel A. Kervaire and John W. Milnor.  Groups of homotopy spheres. I.  Ann. of Math. (2), 77:504–537, 1963.
  * [5] Richard Melrose.  Differential analysis on manifolds with corners, 1996.
  * [6] Richard B. Melrose and Paolo Piazza.  Analytic $K$-theory on manifolds with corners.  Adv. Math., 92(1):1–26, 1992.
  * [7] Vladimir Nazaikinskii, Anton Savin, and Boris Sternin.  Elliptic theory on manifolds with corners. II. Homotopy classification and $K$-homology.  In $C^{\ast}$-algebras and elliptic theory II, Trends Math., pages 207–226. Birkhäuser, Basel, 2008.
  * [8] P. Carrillo Rouse, J. M. Lescure, and B. Monthubert.  A cohomological formula for the Atiyah-Patodi-Singer index on manifolds with boundary.  J. Topol. Anal., 6(1):27–74, 2014.
  * [9] Paulo Carrillo Rouse, Jean-Marie Lescure, and Mario Velásquez.  On Fredholm boundary conditions on manifolds with corners i: Global corner’s cycles obstructions, 2019.