# Differential configurational entropy for multi-field of the $\phi^{6}$
theory

F. C. E. Lima  E-mail<EMAIL_ADDRESS>Universidade Federal do
Ceará (UFC), Departamento do Física - Campus do Pici, Fortaleza, CE, C. P.
6030, 60455-760, Brazil.  C. A. S. Almeida  E-mail<EMAIL_ADDRESS>Universidade Federal do Ceará (UFC), Departamento do Física - Campus do Pici,
Fortaleza, CE, C. P. 6030, 60455-760, Brazil.

###### Abstract

The topological structures of a $\phi^{6}$ theory with multi-field are
studied. The $\phi^{6}$ theory is interesting because it is a theory that
allows the shrinkage of topological structures generating double-kink or even
multi-kink configurations. In this work, we consider and study the solutions
of a two real scalar fields model. To reach our purpose, we investigate the
BPS properties of the fields using the approach proposed by Bogomol’nyi-
Prasad-Sommerfield. Using the BPS energy density, the differential
configurational entropy (DCE) of the BPS structures is studied. The result of
the DCE indicates the most likely field configuration of one of the
topological sectors of the model.

##  I Introduction

Since Finkelstein’s seminal paper on kinks Finkelstein , several works have
arisen in the literature discussing these configurations G1 , G2 , B1 , B2 ,
A1 , A2 , LGA , LDA . The applications of kink structures appear in various
physical scenarios such as condensed matter theories Jubert , Vanhaverbeke ,
Uchida , high energies LPA , Matsunami , Dutta , and nonlinear theories Tin .
Recently, attractive studies on kinks in the gravitational background have
aroused the interest of some researchers Zhong0 . Indeed, these studies can
help to explain questions of quantum gravity Henneaux , Alwis , gravitational
collapse Vaz , Vaz1 , and black hole evaporation Callan , Bilal .

It is incontestable that spontaneous symmetry breaking is ubiquitous in
physics FCECAS . In studies of topological structures, spontaneous symmetry
breaking is essential since it relates to the phase transitions and the
generation of localized structures LA1 , LA2 . These topological structures
are finite energy configurations and can generally appear in one, two, and
three spatial dimensions. Therefore, the kinks are the topological structures
that emerge in 2D theories.

The fact is that solitons in classical and quantum field theories play an
important role due to their applications Manton . In the 2D model, the kink is
a solitary wave configuration Rajaraman . This configuration interpolates
between different minima of the theory. The interaction between structures
such as kink-kink or kink-antikink is a research branch with increasing
interest. That interest occurs due to their applications, the study of kink-
antikink creation from particles (or radiation) Tomasz , Sourish  and multi-
kink collisions Marjaneh , Marjaneh1  are some examples.

Currently, the $\phi^{4}$ theory is the most used model in the literature, see
e. g., Refs. Yan , Evslin . In fact, this is because the $\phi^{4}$ model
forms the phenomenological basis of phase transitions in the Ginzburg-Landau
theory Saxena . This model is interesting because it describes a symmetrical
double potential well. On the other hand, higher-order theories like the
$\phi^{6}$ theory become more interesting because they allow the model to
admit multiple phase transitions. We found in the literature some studies
about the $\phi^{6}$ model. For example, the $\phi^{6}$ theory with $O(N)$
symmetry, was used recently to study different phase transitions Herzog . The
$\phi^{6}$ models also were studied in the context of supersymmetry Kwon  and
in the study of scattering of structures azadeh .

Configurational Entropy (CE) is an important tool that helps understand the
topological field configurations. CE is an extension of Shannon’s theory
Gleiser0 , Gleiser , Shannon . However, CE and its variants (differential
configuration entropy and differential configuration complexity) are applied
to continuous systems and provide information about the stability of localized
structures LA1 . In other words, while Shannon’s theory studies the hidden
information in a random process Shannon , CE is interpreted as a theoretical
measure of the stability of the localized structures Gleiser0 , Gleiser ,
Gleiser2 , Gleiser3 , Gleiser4 . The fact is that configurational entropy is
applied to study several systems. For example, Gleiser et al. used CE to study
Q-balls solutions Gleiser2 , Gleiser4  and non-equilibrium dynamics of
spontaneous symmetry breaking Gleiser4 . Meantime, Rocha et al. used CE to
study black holes NR  and holographic models R .

In this letter, we seek to understand how topological structures change in a
model with two real scalar fields. In principle, in a model governed by a
single scalar field with the interaction of the type $\phi^{6}$, one can have
multiple domain walls so that the structure can take the form of a multi-kink.
If the model has two scalar fields with an interaction type $\phi^{6}$, is it
possible to have the emergence of multi-kink? That is the question that we
seek to discuss throughout this work.

We organize this letter as follows: Initially, we investigate the field
configurations using the BPS formalism for an arbitrary potential. Then, a
particular model of the $\phi^{6}$ theory is exposed, and the analytical
solutions of the scalar fields are displayed. Posteriorly, is investigated the
field configuration more likely using the DCE concept. We finish our
discussion by announcing the findings.

##  II The model

In this paper, we propose to study the kink-like topological structures in a
generalized theory in which we have two generalized scalar fields. This model
has already been used by Bazeia et al. Bazeia1  to study the existence of
geometrically contracted structures in the $\phi^{4}$ theory. In this work,
let us use a similar action, although with a $\phi^{6}$ interaction.
Therefore, allow us to assume a flat two-dimensional spacetime. In this way,
the action is

$\displaystyle
S=\int\,d^{2}x\,\bigg{[}\frac{1}{2}f(\chi)\partial_{\mu}\phi\partial^{\mu}\phi+\frac{1}{2}\partial_{\mu}\chi\partial^{\mu}\chi-V(\phi,\chi)\bigg{]}.$
(1)

The function $f(\chi)$ is the generalization function and is positively
defined. In this work, we will assume the metric signature as
$g_{\mu\nu}=$diag$(+,-)$. In natural units, there is still that $\hbar=c=1$.
Here, it is important to highlight that the potential $V(\phi,\chi)$ couples
the scalar fields at the energy saturation limit. Consequently, the
interaction theory will be related to the $f(\chi)$ generalization function.

The equations of motion arise from varying the action concerning the fields
$\phi$ and $\chi$. Therefore, the equation of motion of the $\phi$ field
configuration is

$\displaystyle\frac{d}{dx}\bigg{(}f(\chi)\frac{d\phi}{dx}\bigg{)}-V_{\phi}(\phi,\chi)=0,$
(2)

and, the variation concerning the field $\chi$ gives us the equation of
motion, namely,

$\displaystyle\frac{d^{2}\chi}{dx^{2}}-\frac{1}{2}f_{\chi}\bigg{(}\frac{d\phi}{dx}\bigg{)}^{2}-V_{\chi}(\phi,\chi)=0,$
(3)

where $V_{\phi}=\partial V/\partial\phi$, $V_{\chi}=\partial V/\partial\chi$,
and $f_{\chi}=df/d\chi$.

To obtain kink-like topological structures, the topological conditions of the
scalar fields are

$\displaystyle\phi(x\to\pm\infty)=\nu_{\pm}\hskip 7.11317pt\text{and}\hskip
7.11317pt\chi(x\to\pm\infty)=u_{\pm}.$ (4)

Here, $\nu_{\pm}$ and $u_{\pm}$ correspond to the theory’s vacuum expected
value (VEV).

Let us implement the Bogomol’nyi approach. For this, it is necessary to
construct the energy-momentum tensor. Varying the action concerning the
metric, we obtain that the energy-momentum tensor is

$\displaystyle
T_{\mu\nu}=f(\chi)\partial_{\mu}\phi\partial_{\nu}\phi+\partial_{\mu}\chi\partial_{\nu}\chi-
g_{\mu\nu}\mathcal{L},$ (5)

where $\mathcal{L}$ is the Lagrangian density associated with the action (1).
In other words, the Lagrangian density is the integrand of the expression (1).

The energy density of the fields is the $T_{00}$ component of the energy-
momentum tensor. Thereby allows us to write the energy density of the
structures as

$\displaystyle\mathcal{E}=T_{00}=\frac{1}{2}f(\chi)\bigg{(}\frac{d\phi}{dx}\bigg{)}^{2}+\frac{1}{2}\bigg{(}\frac{d\chi}{dx}\bigg{)}^{2}+V(\phi,\chi).$
(6)

Let us, at this point, turn our attention to the study of self-dual
structures. For this, we will use the Bogomol’nyi-Prasad-Sommerfield (BPS)
approach to restructure the energy density and find the self-dual equations of
the model. Now, the energy density can be rewritten as

$\displaystyle\mathcal{E}=$
$\displaystyle\frac{f(\chi)}{2}\bigg{[}\bigg{(}\frac{d\phi}{dx}\bigg{)}\mp\frac{\mathcal{W}_{\phi}}{f(\chi)}\bigg{]}^{2}+\frac{1}{2}\bigg{[}\frac{d\chi}{dx}\mp\mathcal{W}_{\chi}\bigg{]}^{2}+V(\phi,\chi)-\frac{\mathcal{W}_{\phi}^{2}}{2f(\chi)}-\frac{W_{\chi}^{2}}{2}\pm\frac{d\mathcal{W}}{dx}.$
(7)

To inspect the BPS structures, we rewrite the potential in terms of an
arbitrary function, i. e., the $\mathcal{W}$ function. In Refs. LA ,
Vachaspati , to study topological structures with BPS properties an auxiliary
function $\mathcal{W}$ is considered. In this context, the helper function
$\mathcal{W}$ is called the superpotential function Vachaspati . In general,
the implementation of this auxiliary function allows writing the potential and
energy in terms of the superpotential. This approach using an auxiliary
function is useful in studying the first-order formalism of topological
structures in various scenarios MLSA , Zhong .

Perceive that the energy density is limited. So, at the energy saturation
limit, we obtain the BPS equations, namely,

$\displaystyle\frac{d\phi}{dx}=\pm\frac{\mathcal{W}_{\phi}}{f(\chi)},$ (8)

and

$\displaystyle\frac{d\chi}{dx}=\pm\mathcal{W}_{\chi}.$ (9)

At the energy saturation boundary, for the system to have BPS property, it is
convenient to choose the model potential as

$\displaystyle
V(\phi,\chi)=\frac{\mathcal{W}_{\phi}^{2}}{2f(\chi)}+\frac{\mathcal{W}_{\chi}^{2}}{2}.$
(10)

For this condition, the energy density of the fields is the BPS energy
density, i. e.,

$\displaystyle\mathcal{E}=\mathcal{E}_{BPS}=\pm\frac{d\mathcal{W}}{dx},$ (11)

so that the energy of the fields at the BPS boundary is

$\displaystyle E_{BPS}=$
$\displaystyle\int\,dx\,\mathcal{E}_{BPS}=\pm\int_{-\infty}^{\infty}\,\frac{d\mathcal{W}}{dx}\,dx=\pm[\mathcal{W}(v_{+},u_{+})-\mathcal{W}(v_{-},u_{-})],$
(12)

i. e.,

$\displaystyle
E_{BPS}=\pm[\mathcal{W}(v_{+},u_{+})-\mathcal{W}(v_{-},u_{-})].$ (13)

###  II.1 The $\phi^{6}$ theory

Before assuming a form for the auxiliary function $\mathcal{W}(\phi,\chi)$, it
is important to mention that the case where first-order equations are simplest
is when $\mathcal{W}_{\phi\chi}=\mathcal{W}_{\chi\phi}=0$. In this case, an
interesting particularly choice is

$\displaystyle\mathcal{W}(\phi,\chi)=\mathcal{W}_{1}(\phi)+\mathcal{W}_{2}(\chi).$
(14)

To work in a $\phi^{6}$ theory, let us suppose that the superpotential has the
following profile,

$\displaystyle\mathcal{W}(\phi,\chi)=\frac{\phi^{2}}{2}\bigg{(}1-\frac{\phi^{2}}{2}\bigg{)}+\frac{\chi^{2}}{2}\bigg{(}1-\frac{\chi^{2}}{2}\bigg{)}.$
(15)

The auxiliary function (15) profile is interesting because it reproduces a
symmetric $\phi^{6}$ theory. Indeed, that superpotential is an extension of
the model discussed in reference Bazeia1 . In Ref. Bazeia1 , the authors
choose the superpotential for reproducing the $\phi^{4}$ theory. The choice
(15) leads us to an extension of the $\phi^{4}$ theory, i. e., we will have a
model with three distinct vacuum values. Furthermore, for this extension (15),
it is common to expect the appearance of geometrically contracted structures,
such as the class of multi-kink solutions. Motivated by this hypothesis, we
assume the superpotential (15) and write the interaction as

$\displaystyle
V(\phi,\chi)=\frac{\phi^{2}(1-\phi^{2})^{2}}{2f(\chi)}+\frac{\chi^{2}(1-\chi^{2})^{2}}{2}.$
(16)

Although, in this paper, we have assumed the superpotential to produce a
specific profile of the interaction. In some models, it is usual to apply the
correspondences with the supersymmetric theories to study the BPS property.
For these cases, the supersymmetry (SUSY) can adjust the action to satisfy the
BPS approach. In this way, SUSY can propose a profile for the auxiliary
function, see Ref. CCA . However, in our model, the study of the SUSY
correspondence for the BPS approach is not applied. That’s because, in
principle, a polynomial function that spontaneously breaks symmetry will
preserve the BPS property in our model.

Furthermore, note that the potential described above is equivalent to a theory
like $\phi^{6}$. The $\phi^{6}$-theories are discussed extensively in Refs.
Saxena , Herzog , azadeh . For example, Saxena et al. Saxena  establishes the
theory $\phi^{6}$ in a Ginzburg-Landau theory of successive phase transitions.
In that work, the authors use the $\phi^{6}$ interaction to study the
properties of the structures. Furthermore, the $\phi^{6}$ theory allows for a
connection with the models of high-energy physics, i. e., the “bag models” of
Quarks within Hadrons Saxena .

For the interaction (16), the self-dual equations of topological structures
are

$\displaystyle\frac{d\phi}{dx}=\pm\frac{1}{2}\chi^{n}\phi(1-\phi^{2}),$ (17)

and

$\displaystyle\frac{d\chi}{dx}=\pm\frac{1}{2}\chi(1-\chi^{2}).$ (18)

Here, the parameter $n$ will be assumed to be an integer. In our model, the
parameter $n$ is the degree of the generalization function. The modification
of the parameter $n$ produces alterations of the structure in the topological
sector of the field $\phi$. Let us mention that in Eq. (17) it was considered
that $f(\chi)=1/\chi^{n}$. This choice is one of the simplest forms of the
$f(\chi)$ function that can induce contractions of the kink-like solutions of
the $\phi$ field Bazeia1 .

For this particular model, the BPS energy density of the structure is

$\displaystyle\mathcal{E}_{BPS}=\phi\phi^{\prime}(1-\phi^{2})+\chi\chi^{\prime}(1-\chi^{2}),$
(19)

i. e.,

$\displaystyle\mathcal{E}_{BPS}=\pm\frac{1}{2}[\chi^{n}\phi^{2}(1-\phi^{2})^{2}+\chi^{2}(1-\chi^{2})^{2}].$
(20)

Let us now investigate the solutions of the BPS equations, i. e., Eqs. (17)
and (18). For simplicity, in investigating the solutions of Eq. (18), we have

$\displaystyle\int\,\frac{d\chi}{\chi(1-\chi^{2})}=\pm\frac{1}{2}\int\,dx.$
(21)

The expression (21) leads us to kink and antikink solutions, namely,

$\displaystyle\chi(x)=\frac{1}{\sqrt{1+\text{e}^{(x_{0}\mp x)}}}.$ (22)

The negative sign of the expression above indicates kink-like solutions. On
the other hand, the positive sign indicates the antikink-like solution. The
value $x_{0}$ describes the starting position of the topological structure. In
Fig. 1, the graphical behavior of the $\chi(x)$ field is displayed.

(a) (b)

Figure 1: (a) Kink-like solutions of the $\chi(x)$ field when $x_{0}=1,$ $2$
and $4$. (b) Antikink-like solutions of the $\chi(x)$ field when $x_{0}=1,$
$2$ and $4$.

Using the solution (18), one can find the analytical solution of the Eq. (17).
With the expression (22), we note that Eq. (17) is rewritten as

$\displaystyle\frac{d\phi}{dx}=\pm\frac{1}{2[1+\text{e}^{(x_{0}\mp
x)}]^{n/2}}\phi(1-\phi^{2}).$ (23)

Rewriting the above expression, we arrive at

$\displaystyle\int\,\frac{d\phi}{\phi(1-\phi^{2})}=\pm\frac{1}{2}\int\,\frac{dx}{[1+\text{e}^{(x_{0}\mp
x)}]^{n/2}}.$ (24)

Let us remember that

$\displaystyle F(x,x_{0})=$
$\displaystyle\frac{1}{2}\int\,\frac{dx}{[1+\text{e}^{(x_{0}\mp x)}]^{n/2}}$
$\displaystyle=$ $\displaystyle\pm[1+\text{e}^{(\pm x_{0}-x)}]^{\mp
n/2}[1+\text{e}^{(\mp x_{0}+x)}]^{\pm
n/2}\,_{2}F_{1}\bigg{(}\frac{n}{2},\frac{n}{2},1+\frac{n}{2};\text{e}^{(-x_{0}\pm
x)}\bigg{)}.$

Allow us to highlight that ${}_{2}F_{1}(a,b,c;y)$ is the well-known
hypergeometric function. Thus, we define the hypergeometric function as

${}_{2}F_{1}(a,b,c;y)=\sum_{j=0}^{\infty}\frac{(a)_{j}(b)_{j}}{(c)_{j}}\frac{y^{j}}{j!}$
(25)

where $a=\frac{n}{2}$, $b=\frac{n}{2}$, $c=\frac{n}{2}+1$, and
$y=\text{e}^{(-x_{0}\pm x)}$.

Using (24) and (II.1), solutions for the field $\phi$ are obtained. In this
case, the solutions of the field $\phi$ are

$\displaystyle\phi(x)=\frac{1}{\sqrt{1+\text{e}^{\mp 2F(x,x_{0})\pm c_{0}}}}.$
(26)

Here, $c_{0}$ is a constant of integration and will be responsible for the
initial location of the structure in the topological sector of $\phi(x)$. The
field configurations in the topological sector of $\phi$ are presented in
Figs. 2 and 3.

(a) (b)

Figure 2: (a) Kink-like solutions of the $\phi(x)$ field when $c_{0}=6$,
$n=1$,and $x_{0}=1,$ $2,$ and $4$. (b) Antikink-like solutions of the
$\phi(x)$ field when $c_{0}=-6$, $n=1$, and $x_{0}=1,$ $2,$ and $4$.

(a) (b)

Figure 3: (a) Kink-like solutions of the field $\phi(x)$ when $x_{0}$ and
$c_{0}$ are constant and $n$ varies. (b) Antikink-like solutions of the
$\phi(x)$ field when $c_{0}$ and $x_{0}$ are constant and $n$ varies.

Substituting the Eqs. (22) and (26) in Eq. (20), we obtain the BPS energy
density. We display the BPS energy density profile of the model in Fig. 4.
Note that when $n$ is small, the multi-field configurations of our theory
begin to have an energy profile similar to true kinks, see Ref. Rajaraman .

Figure 4: BPS energy density produced by fields $\chi$ and $\phi$.

##  III Differential Configurational Entropy

The results of the previous section suggest that the parameter n changes the
topological sector structures $\phi$. This result allows the emergence of the
following question: For which value of parameter n is the topological
configurations found to be more stable? To answer this issue, we will use the
concept of configurational entropy (or its variant, namely, DCE) to
investigate the most likely field configuration.

Differential configurational entropy (DCE) is a variant of Configurational
Entropy (CE). DCE plays a relevant role in measuring the informational
complexity of a localized field configuration, see Refs. Gleiser , Wilami ,
MLA . Furthermore, we can express the DCE as Fourier’s transform of the energy
density (BPS energy density).

To calculate the DCE is necessary to define it in terms of the probability
density Gleiser2 , Gleiser3 , Gleiser4 . This probability density is

$\displaystyle
f(\omega)=\frac{|\mathcal{F}(\omega)|^{2}}{\int_{-\infty}^{\infty}d\omega^{\prime}|\mathcal{F}(\omega^{\prime})|^{2}},$
(27)

where

$\displaystyle\mathcal{F}(\omega)=-\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\mathcal{E}_{BPS}(x)\,\text{e}^{i\omega
x}\,dx.$ (28)

Thus, for a continuous and localized function, the DCE is given by

$\displaystyle
S_{C}[f]=-\int_{-\infty}^{\infty}f(\omega)\text{ln}[f(\omega)]\,d\omega.$ (29)

Due to the profile of the fields $\phi(x)$ and $\chi(x)$, it is convenient to
numerically analyze the DCE of the field configurations presented in Eqs. (22)
and (26). To perform this analysis, we start by substituting the solutions
(22) and (26) in the energy density expression, i. e., Eq. (20). Substituting
Eq. (20) in (28), you get $\mathcal{F(\omega)}$. Subsequently, applying the
definition of probability density (27) and DCE (29), respectively, we obtain
the differential configurational entropy of the model previously discussed.

We display in Fig. 5 the DCE result. By definition, the maximum or minimum
point of the DCE indicates the most likely (or most stable) configurations,
see Refs. LA2 , Wilami , MLA . Therefore, the structures most likely of our
theory appear when the parameter $n\simeq 6$, as shown in Fig. 5.

Figure 5: Differential configurational entropy in terms of the parameter $n$
when $c_{0}=x_{0}=1$.

Varying parameters $c_{0}$ and $x_{0}$ and keeping $n$ constant, i. e., $n=1$,
one obtains the results of Fig 6. Fig. 6 shows that DCE is constant when the
parameters $c_{0}$ and $x_{0}$ vary. That occurs because these parameters
describe the initial conditions of topological structures, and these
configurations are equally likely. In other words, this is a consequence of
having infinite initial configurations (i.e., regions where structures can be
initially) for the system.

(a) (b)

Figure 6: Configurational differential entropy assuming n=1. (a) Varying the
parameter $x_{0}$. (b) Varying the parameter $c_{0}$.

##  IV Final remarks

In this letter, we present a study of the field configurations of the
$\phi^{6}$ theory with two scalar fields. Furthermore, to find the appropriate
value for the parameter $n$, the concept of configurational entropy was used
to search for the most stable and probable field configurations.

A peculiar result of our model is that it admits analytic solutions. Another
result emerges when we look at the field setting. As a matter of fact, we show
analytically that our theory has a contraction. We refer to contraction as the
form that the fields only interpolate the vacuums $\phi^{(0)}=0$ and
$\phi^{(0)}=1$. Note the contrast to the usual $\lambda\phi^{4}$ theory, where
we use the potential of type $V\propto(1-\phi^{2})^{2}$ and the fields
interpolate between the vacuums $\phi^{(0)}=\pm 1$.

We found the appropriate value for the parameter n using the concepts derived
from configurational entropy. Indeed, to reach our purpose, we use
differential configurational entropy. The analysis of this quantity shows us
numerically that the most likely, and therefore most stable, field
configurations occur when $n=6$ approximately. Moreover, it is possible to see
that for $n=6$, the field $\chi(x)$ will have the kink-like solutions shown in
Fig. 1, while the field $\phi(x)$ have the kink-like configurations shown in
Fig. 7.

Figure 7: Most likely solutions based on DCE calculation.

Some future perspective of this work is the study of the scattering process in
$\phi^{6}$ type theory with two or more coupled scalar fields. In addition,
another perspective can be an investigation of the extension of this theory to
models in which Lorentz symmetry breaking is considered. Not far away, a
complementary result of this study can emerge by analyzing cases where a
canonical scalar field and a noncanonical one are considered. The present work
is the first step toward understanding these structures in a multi-field
system. Therefore, we hope in the future to carry out studies in this
directions to collaborate with the results presented here.

##  V Acknowledgments

The authors thank the Conselho Nacional de Desenvolvimento Científico e
Tecnológico (CNPq), grants no 309553/2021-0 (CASA) and the Coordenação de
Aperfeiçoamento de Pessoal de Nível Superior (CAPES), grants no
88887.372425/2019-00 (FCEL), for financial support.

## References

  * [1] D. Finkelstein, J. Math. Phys. 7, (1966) 1218.
  * [2] V. A. Gani, A. E. Kudryavtsev and M. A. Lizunova, Phys. Rev. E 89, (2014) 125009.
  * [3] V. A. Gani and A. E. Kudryavtsev, Phys. Rev. E 60, (1999) 3305.
  * [4] D. Bazeia, E. Belendryasova and V. A. Gani, Eur. Phys. J. C 78, (2018) 340.
  * [5] J. D. Edelstein, M. L. Trobo, F. A. Brito and D. Bazeia, Phys. Rev. D 57, (1998) 7561.
  * [6] D. Bazeia and A. Mohammadi, Eur. Phys. J. C 77, (2017) 203.
  * [7] J. G. F. Campos and A. Mohammadi, JHEP 09, (2021) 067.
  * [8] F. C. E. Lima, D. A. Gomes and C. A. S. Almeida, Ann. Phys. 422, (2020) 168315.
  * [9] F. C. E. Lima, D. M. Dantas and C. A. S. Almeida, Europhys. Lett. 130, (2020) 10005.
  * [10] P.-O. Jubert, R. Allenspach, and A. Bischof, Phys. Rev. B 69, (2004) 220410(R).
  * [11] A. Vanhaverbeke, A. Bischof, and R. Allenspach, Phys. Rev. Lett. 101, (2008) 107202.
  * [12] K. Uchida, H. Adachi, T. Ota, H. Nakayama, S. Maekawa, and E. Saitoh, Appl. Phys. Lett. 97, (2010) 172505.
  * [13] F. C. E. Lima, A. Yu. Petrov and C. A. S. Almeida, Phys. Rev. D 105, (2022) 056005.
  * [14] D. Matsunami, L. Pogosian, A. Saurabh and T. Vachaspati, Phys. Rev. Lett. 122, (2019) 201301.
  * [15] S. Dutta, D. A. Steer and T. Vachaspati, Phys. Rev. Lett. 101, (2008) 121601.
  * [16] P. V. Tin, Nonlinear analysis 221, (2022) 112915.
  * [17] Y. Zhong, F.-Y. Li, X.-D. Liu, Phys. Lett. B 822, (2021) 136716.
  * [18] M. Henneaux, Phys. Rev. Lett. 54, (1985) 959.
  * [19] S. de Alwis, Phys. Lett. B 289, (1992) 278.
  * [20] C. Vaz and L. Witten, Phys. Lett. B 325, (1994) 27.
  * [21] C. Vaz and L. Witten, Class. Quantum Gravity 13, (1996) L59.
  * [22] C. G. Callan Jr., S. B. Giddings, J. A. Harvey and A. Strominger, Phys. Rev. D 45, (1992) R1005
  * [23] A. Bilal, J. Callan and G. Curtis, Nucl. Phys. B 394, (1993) 73.
  * [24] F. C. E. Lima and C. A. S. Almeida, Phys. Lett. B 829, (2022) 137042.
  * [25] F. C. E. Lima and C. A. S. Almeida, Eur. Phys. J. C 81, (2021) 1044.
  * [26] F. C. E. Lima and C. A. S. Almeida, Ann. Phys. 442, (2022) 168904.
  * [27] N. Manton and P. Sutcliffe, Topological solitons, Cambridge University Press, Cambridge, England, (2004).
  * [28] R. Rajaraman, Solitons and Instantons, North-Holland, Amsterdam, (1982).
  * [29] Tomasz Romanczukiewicz, J. Phys. A, Math. Gen. 39, (2006) 3479.
  * [30] S. Dutta, D. A. Steer, T. Vachaspati, Phys. Rev. Lett. 101, (2008) 121601.
  * [31] A. M. Marjaneh, D. Saadatmand, K. Zhou, S. V. Dmitriev and M. E. Zomorrodian, Commun. Nonlinear Sci. Numer. Simul. 49, (2017) 30.
  * [32] A. M. Marjaneh, A. Askari, D. Saadatmand and S. V. Dmitriev, Eur. Phys. J. B 91, (2018) 22.
  * [33] H. Yan, Y. Zhong, Yu-Xiao Liu and Kei-ichi Maeda, Phys. Lett. B 807, (2020) 135542.
  * [34] J. Evslin, Phys. Lett. B 822, (2021) 136628.
  * [35] A. Saxena, I. C. Christov and A. Khare, Higher-order field theories: $\phi^{6}$, $\phi^{8}$ and beyond. In: A Dynamical Perspective on the $\phi^{4}$ Model. Springer, Cham, (2019) 253.
  * [36] C. P. Herzog and N. Kobayashi, JHEP 2020, (2020) 121.
  * [37] O-Kab Kwon, C. Kimb and Y. Kima, JHEP 2022, (2022) 140.
  * [38] A. Amado and A. Mohammadi, Eur. Phys. J. C 80, (2020) 576.
  * [39] M. Gleiser, D. Sowinski, Phys. Rev. D 98, (2018) 056026.
  * [40] M. Gleiser and N. Stamatopoulos, Phys. Lett. B 713, (2012) 304.
  * [41] C. E. Shannon, The Bell system technical journal 27, (1948) 379.
  * [42] M. Gleiser and D. Sowinski, Phys. Lett. B 727, (2013) 272.
  * [43] M. Gleiser and N. Graham, Phys. Rev. D 89, (2014) 083502.
  * [44] M. Gleiser and N. Stamatopoulos, Phys. Rev. D 86, (2012) 045004.
  * [45] N. R. F. Braga and R. da Rocha, Phys. Lett. B 767, (2017) 386.
  * [46] A. E. Bernardini and R. da Rocha, Phys. Lett. B 762, (2016) 107.
  * [47] D. Bazeia, M. A. Liao and M. A. Marques, Eur. Phys. J. Plus 135, (2020) 383.
  * [48] F. C. E. Lima and C. A. S. Almeida, Phys. Lett. B 829, (2022) 137042.
  * [49] T. Vachaspati, Kinks and Domain Walls: An Introduction to Classical and Quantum Solitons, Cambridge University Press, Cambridge, England, (2006).
  * [50] A. R. P. Moreira, F. C. E. Lima, J. E. G. Silva and C. A. S. Almeida, Eur. Phys. J. C 81, (2021) 1081.
  * [51] Y. Zhong, R.-Z. Guo, C.-E. Fu, Y.-X. Liu, Phys. Lett. B 782, (2018) 346.
  * [52] F. S. A. Cavalcante, M. S. Cunha and C. A. S. Almeida, Phys. Lett. B 475, (2000) 315.
  * [53] W. T. Cruz, D. M. Dantas, R. V. Maluf and C. A. S. Almeida, Ann. Phys. (Berlin), 531, (2019) 1900178.
  * [54] A. R. P. Moreira, F. C. E. Lima and C. A. S. Almeida, Int. J. Mod. Phys. D 31, (2022) 2250080.


# The Flow Game: Leximin and Leximax Core Imputations

Rohith R. Gangam  University of California, Irvine  Naveen Garg  Indian
Institute of Technology Delhi  Parnian Shahkar  University of California,
Irvine  Vijay V. Vazirani  University of California, Irvine

###### Abstract

Recently [Vaz24] gave mechanisms for finding leximin and leximax core
imputations for the assignment game and remarked, “Within the area of
algorithm design, the “right” technique for solving several types of
algorithmic questions was first discovered in the context of matching and
later these insights were applied to other problems. We expect a similar
phenomenon here.” One of the games explicitly mentioned in this context was
the flow game of Kalai and Zemel [KZ82].

In this paper, we give strongly polynomial time mechanisms for computing the
leximin and leximax core imputations for the flow game, among the set of core
imputations that are captured as optimal solutions to the dual LP. We address
two versions:

  1. 1.

The imputations are leximin and leximax with respect to the distance labels of
edges.

  2. 2.

The imputations are leximin and leximax with respect to the product of
capacities of edges and their distance labels.

##  1 Introduction

Motivated by a need to find equitable core imputations for the assignment
game, recently [Vaz24] gave mechanisms for finding leximin and leximax core
imputations. These mechanisms run in strongly polynomial time and were
obtained via a suitable adaptation of the classical primal-dual paradigm from
combinatorial optimization. [Vaz24] further remarked, “Within the area of
algorithm design, the “right” technique for solving several types of
algorithmic questions was first discovered in the context of matching and
later these insights were applied to other problems. We expect a similar
phenomenon here.” One of the games explicitly mentioned in this context was
the flow game of Kalai and Zemel [KZ82].

In this paper, we give strongly polynomial time mechanisms for computing the
leximin and leximax core imputations for the flow game, among the set of core
imputations that are captured as optimal solutions to the dual LP. We address
two versions:

  1. 1.

The imputations are leximin and leximax with respect to the distance labels of
edges.

  2. 2.

The imputations are leximin and leximax with respect to the product of
capacities of edges and their distance labels.

##  2 Preliminaries

In this section, we introduce our formal model.

######  Definition 2.1.

A cooperative game involves a set $N$ of $n$ players and a function $c$, where
$c:2^{N}\to\mathbb{R}^{+}$ assigns to each subset $S$ of $N$ a value $c(S)$,
representing what that group can achieve on its own. The entire set $N$ is
known as the grand coalition.

######  Definition 2.2.

An imputation is a way to distribute the total value $c(N)$ of the game among
the players using a function $p:N\to\mathbb{R}^{+}$. It ensures the sum of all
individual shares $\sum_{i\in N}p(i)$ equals $c(N)$, with $p(i)$ being the
share of player $i$.

######  Definition 2.3.

We say that an imputation $p$ belongs to the core of the game $(N,c)$ if, for
every possible coalition $S$ within $N$, the aggregate allocation to members
of $S$ is no less than the value they could collectively produce, i.e.,
$\sum_{i\in S}p(i)\geq c(S)$.

###  2.1 Max-flow Game

Consider a directed graph $G=(V,E)$ with specific source $s$ and sink $t$
nodes, along with positive edge capacities $c:E\to\mathbb{R}+$. A feasible
flow $f:E\to\mathbb{R}+$ adheres to the following:

  * •

Capacity constraint: The flow $f_{e}$ through any edge $e$ must not exceed its
capacity $c_{e}$.

  * •

Conservation of flow: For every vertex $v$ except $s$ and $t$, the inflow and
outflow must be equal.

The flow value $f$ is the sum of the flow leaving source $s$ or entering sink
$t$, which are equal due to flow conservation across other vertices. The goal
of the maximum flow problem is to maximize this flow value within given
constraints.

The max-flow game is defined over an instance of the maximum flow problem
which consists a graph $G=(V,E)$, with two distinguished vertices, a source
$s$ and a sink $t$, and non-negative capacities, $c:E\to\mathbb{R}+$. The
edges constitute the players. The flow from $s$ to $t$ generates a profit that
needs to be fairly distributed among these edge-players. The entire set of
edges, $E$, forms the grand coalition, with its value, $worth(E)$, equating to
$G$’s maximum flow value. For a subset of edges $S\subseteq E$, the graph
$G(S)=(V,S)$, maintains the original vertices but only includes edges from
$S$, with capacities restricted to $S$, denoted as $c:S\to\mathbb{R}+$. The
value of such a subset, $worth(S)$, corresponds to the maximum flow in $G(S)$.
The concepts of imputation and the core, as described in the preceding
definitions, are applicable here as well.

Divide the vertex set $V$ of the graph into two distinct subsets, $X$ and
$\bar{X}$, ensuring $s$ is in $X$ and $t$ resides in $\bar{X}$. The collection
of edges leading from $X$ to $\bar{X}$ constitutes an s–t cut, represented by
$(X,\bar{X})$, with its capacity being the aggregate of the capacities for
these edges. It’s evident that the capacity of any s–t cut sets a limit on the
magnitude of a viable flow. Thus, if we encounter an s–t cut, for instance,
$(X,\bar{X})$, whose capacity matches the magnitude of a feasible flow $f$,
then $(X,\bar{X})$ is identified as the minimal s–t cut within $G$, and
correspondingly, $f$ is the maximal flow through $G$. The well-known Max-Flow
Min-Cut Theorem validates the feasibility of achieving such an equivalence
between a flow and an s–t cut.

To frame the maximum flow problem within a linear programming paradigm, we
initially incorporate an edge with unlimited capacity from $t$ to $s$,
ensuring flow conservation at both $s$ and $t$, thereby transforming the
scenario into a circulation problem. The aim is to maximize the flow $f_{ts}$
across this added edge to achieve maximum flow in the original graph. We
assign the primal variable $f_{ij}$ to quantify the flow through each edge
$(i,j)\in E$. The linear program for the maximum flow problem is outlined as
follows:

f_ts ∑_(j,i)∈Ef_ji - ∑_(i,j)∈Ef_ij≤0 ∀i ∈V f_ij≤c_ij ∀(i,j) ∈E f_ij≥0∀(i, j)
∈E The initial inequalities ensure that at each node $i$, the incoming flow
does not surpass the outgoing flow. Although this setup does not strictly
enforce equal incoming and outgoing flows to form a standard maximization
linear program, the principle of equality is nonetheless guaranteed as
discussed in [Vaz23].

######  Definition 2.4.

An edge $(i,j)\in E$ is classified as essential if it is utilized to its full
capacity in all maximum flow solutions.

We proceed by defining dual variables $\pi_{i}$ for node potentials and
$\delta_{ij}$ for the capacity constraints in the edges, leading to the dual
linear program formulation.

∑_(i, j) ∈E c_ij δ_ij δ_ij - π_i + π_j ≥0 ∀(i, j) ∈E π_s - π_t≥1 δ_ij≥0∀(i, j)
∈E π_i≥0∀i ∈V

Considering $\delta_{ij}$ and $\pi_{i}$ as labels for edge distances and
vertex potentials respectively simplifies understanding their application.
Suppose, for a given graph instance $G$, the dual linear program yields an
integral optimal solution. In such a case, it’s straightforward that each
variable in the solution is either 0 or 1, as they need not surpass 1.
Consequently, $\pi_{s}$ would be 1, $\pi_{t}$ would be 0, and the potentials
for other vertices would also be either 0 or 1.

The distance labels in any optimal dual solution are conceptualized as a
fractional s–t cut, with its capacity determined by the sum of the product of
edge capacities and their corresponding $\delta_{ij}$ values, that is,
$\sum_{(i,j)\in E}c_{ij}\delta_{ij}$. According to the LP-Duality Theorem,
this capacity equates to the maximum flow value.

Given an optimal dual solution $(\delta,\pi)$, the LP-duality theorem
stipulates that the game’s total value corresponds to the objective value of
this solution, expressed as:

$\text{worth}(E)=\sum_{(i,j)\in E}c_{ij}\cdot\delta_{ij}.$

Define the profit of edge $(i,j)$ to be

$p(i,j):=c_{ij}\cdot\delta_{ij}.$

[Vaz23] showed that for any max-flow game, the dual partially characterizes
its core and core imputations corresponding to optimal dual solutions allocate
all the profits to essential players only. [FZCD02] showed that in general,
checking whether an imputation is in the core is NP-hard. Therefore our focus
is finding a fair core imputation among the imputations that are obtained from
optimal solutions of the dual LP 2.4. This class of core imputations are
defined as dual-consistent core imputations.

######  Definition 2.5.

A max flow core imputation $p$ is dual-consistent if there exists an optimal
solution $(\delta,\pi)$ for the dual LP 2.4, where profit of each edge $(i,j)$
can be written as $p(i,j)=c_{ij}\cdot\delta_{ij}.$

Not all core imputations are dual-consistent. Next, we will provide an example
of a core imputation that does not correspond to any optimal solution of dual
LP 2.4.

######  Example 2.6.

Suppose $G=(V,E)$ is the following directed graph with four nodes $s$, $a$,
$b$, and $t$. The arrows between the nodes represent directed edges, and the
numbers above the edges represent the capacity associated with each edge. The
value of maximum flow from $s$ to $t$ is 10, which can be distributed evenly
among the four edges. The resulting imputation is a core imputation. Suppose
this imputation corresponds to an optimal solution of the dual LP 2.4
$(\delta,\pi)$. Given that the profit of each edge is $2.5$ units, where
$p(i,j)=c_{ij}\cdot\delta_{ij}$, distance labels of all the edges are uniquely
determined as $\delta_{sb}=1/2$, $\delta_{bt}=1/4$, $\delta_{sa}=1/2$, and
$\delta_{ab}=1/2$, . Observe that for any optimal solution of the dual LP 2.4,
$\pi_{s}=1$, $\pi_{t}=0$, and all constraints of the form
$\delta_{ij}-\pi_{i}+\pi_{j}\geq 0$ are tight. Therefore constraints
corresponding to the edges $\\{sb\\}$ and $\\{bt\\}$ imply that
$\delta_{sb}=1-\pi_{b}$, and $\delta_{bt}=\pi_{b}$. Given the distance labels
$\delta_{sb}=1/2$ and $\delta_{bt}=1/4$, no value of $\pi_{b}$ satisfies both
constraints of edges $\\{sb\\}$ and $\\{bt\\}$. Hence, no optimal solution of
the dual LP 2.4 can characterize the core imputation in which all edges
receive $2.5$ units of profit.

sabt55510 Figure 1: Example 2.6

######  Definition 2.7.

For each dual-consistent core imputation of the max flow game $G=(V,E)$,
$c:E\to\mathbb{R}+$, sort the allocations made to edges in increasing order.
Given two sorted lists L1 and L2, L1 is considered lexicographically larger
than L2 if, at the first position where they diverge, the element in L1
exceeds that in L2; this discrepancy could involve the profits of distinct
players. An imputation resulting in the lexicographically greatest sequence is
termed a leximin dual-consistent core imputation.

######  Definition 2.8.

For each dual-consistent core imputation of the max flow game $G=(V,E)$,
$c:E\to\mathbb{R}+$, sort the allocations made to edges in decreasing order.
Consider two sorted lists, L1 and L2. L1 is deemed lexicographically smaller
than L2 if, at the initial point of divergence between the two lists, the
entry in L1 is less than that in L2. An imputation that produces the
lexicographically smallest list is designated as a leximax dual-consistent
core imputation.

In [PQ80], authors gave a characterization of all minimum cuts, separating a
source from a sink in a graph. They also give a procedure to enumerate all
integral minimum cuts in the graph. Given this procedure, a natural approach
for finding a leximin dual-consistent core imputation is to find the linear
combination of integral min-cuts that results in a leximin fractional min-cut.
However since the number of integral min-cuts in a graph can be exponential,
this procedure must take exponential time in total, in the worst case.
Nevertheless, Picard-Queyranne graph is the main backbone of our algorithm
that finds the leximin dual-consistent core imputation in polynomial time.
Therefore, we will precisely describe the procedure for finding the Picard-
Queyranne graph, in short $G_{PQ}$, of a max flow game.

######  Definition 2.9.

Given a graph $G=(V,E)$, and a flow $f$, the residual graph $G_{R}$ is defined
as follows: For each edge $(i,j)$ in the original graph $G$ with capacity
$c(i,j)$ and flow $f(i,j)$, we introduce a forward edge in $G_{R}$ with a
residual capacity $c_{R}(i,j)=c(i,j)-f(i,j)$ and a backward edge with a
residual capacity $c_{R}(j,i)=f(i,j)$. Finally we remove all forward and
backward edges with zero residual capacity.

######  Definition 2.10.

Strongly connected components (SCCs) of a directed graph are maximal subgraphs
where there exists a directed path between all pairs of vertices.

Graphs are decomposed into SCCs using algorithms like Tarjan’s or Kosaraju’s,
which systematically explore edges to identify cycles and thereby delineate
components.

Algorithm 1

1:Input: $G=(V,E)$, $s\in V,t\in V$, $c:E\to\mathbb{R}+$.

2:Find max-flow $f$.

3:$G_{R}\leftarrow$ residual graph of $G=(V,E)$ given flow $f$

4:$V_{PQ}\leftarrow SCC(G_{R})$

5:$E_{PQ}\leftarrow$ Connections between SCCs

6:Construct graph $G_{PQ}=(V_{PQ},E_{PQ})$

7:Output: $G_{PQ}$.

Algorithm Description: The algorithm takes as input a max flow instance
$G=(V,E)$, with two distinguished vertices, a source $s$ and a sink $t$, and
non-negative capacities, $c:E\to\mathbb{R}+$. Then it finds a maximum flow
$f$, and a residual graph $G_{R}$ according to $f$. Then it condenses each SCC
of the graph $G_{R}$ into a single vertex to form a set $V_{PQ}$ of
representative vertices. Finally, it constructs a new graph
$G_{PQ}=(V_{PQ},E_{PQ})$ with vertices $V_{PQ}$ and directed edges $E_{PQ}$,
where each edge in $E_{PQ}$ represents a connection between SCCs in the
original graph, maintaining the original edge direction and capacity in the
residual graph $G_{R}$.

Let $S:V\rightarrow V_{PQ}$ be the function that takes a vertex in $G$ and
returns a vertex corresponding to its SCC in $G_{PQ}$. Let
$T:V_{PQ}\rightarrow 2^{V}$ be the function that takes a vertex in $G_{PQ}$
and returns the set vertices of $G$, in the SCC it represents. Let’s call
$S(s)$ and $S(t)$ the PQ-source and PQ-sink respectively. Also, note that
edges of PQ structure are directed the other way compared to the original
graph.

$E_{PQ}$ constitutes only a subset of edges in the residual graph $G_{R}$, and
since there is no $s-t$ path in $G_{R}$, no $s-t$ path exists in $G_{PQ}$
either. Each vertex in $V_{PQ}$ represents a set of vertices in $G$, and due
to the flow conservation principle upheld at every vertex (excluding $s$ and
$t$) in $G$, this property is similarly maintained for any vertex in
$V_{PQ}\setminus\\{S(s),S(t)\\}$.

By definition, any essential edge $(i,j)$ in graph $G$ is fully utilized in
every maximum flow. Therefore, in the residual graph $G_{R}$, only the
backward edge from $j$ to $i$ with capacity $c_{R}(j,i)=c_{ij}$ remains, as
the forward edge from $i$ to $j$ was removed. This results in vertex $i$ not
being reachable from $j$, ensuring that these vertices do not reside in the
same SCC. Thus, all essential edges of $G$ are preserved in $E_{PQ}$, albeit
with reversed direction and unchanged capacity. Conversely, both endpoints of
any non-essential edge $(i,j)$ are mutually reachable, implying they are
within the same SCC, leading to the exclusion of non-essential edges from
$E_{PQ}$. Hence, only the essential edges of the original graph are preserved
in $G_{PQ}$. Given that all minimum cuts of $G$ comprise subsets of essential
edges, and considering the preservation of these edges in $G_{PQ}$, there
exists a one-to-one correspondence between the minimum cuts in $G_{PQ}$ and
those in $G$. The preservation of only essential edges in $G_{PQ}$, coupled
with the invariant nature of corresponding edges in $G_{R}$ across all maximum
flows $f$, ensures the uniqueness of $G_{PQ}$ for any given $G$.

##  3 Results

First, we define the notion of “dual-consistent” potentials on vertices and
explain its relation to the core imputations given by the dual of the max-flow
game.

######  Definition 3.1.

A potential function $\bar{\pi}:V_{PQ}\rightarrow[0,1]$ on the vertices of the
Picard-Queyranne structure is said to be “dual-consistent” if

  1. 1.

Potential of the vertex corresponding to the source is 1, i.e.,
$\bar{\pi}(S(s))=1$

  2. 2.

Potential of the vertex corresponding to the sink is 0, i.e.,
$\bar{\pi}(S(t))=0$

  3. 3.

Potential on every (directed) edge is non-decreasing, i.e., $\forall(i,j)\in
E_{PQ},\bar{\pi}(i)\leq\bar{\pi}(j)$

######  Lemma 3.2.

Each dual-consistent potential $\bar{\pi}$ defines a unique fractional min-cut
of graph $G$.

###### Proof.

We will first construct a fractional cut $\mathcal{C}_{PQ}(\bar{\pi})$ of the
graph $G_{PQ}$ from $\bar{\pi}$. By taking the corresponding edges of $G$ with
equal weights, we get a fractional min-cut, $\mathcal{C}(\bar{\pi})$ of $G$.

List the vertices of $V_{PQ}$ in a non-increasing order of potentials,
starting with $S(s)$, ending with $S(t)$ and breaking ties arbitrarily. Let
this list be $L=\\{v_{1}=S(s),v_{2},v_{3},\ldots,v_{n}=S(t)\\}$, where
$n=|V_{PQ}|$. We will create a fractional cut that is a convex combination of
cuts, each of which breaks this list into two parts.

Define the first cut $\mathcal{S}_{1}$ to be the set of all edges directed
into the PQ-source, i.e.,

$\mathcal{S}_{1}=\\{e=(i,j)\in E_{PQ},s.t.j=v_{1}=S(s)\\}$

Note that this corresponds a min-cut of $G$. We will define new cuts
iteratively by “pulling vertices” across previous cuts. With each pull of a
vertex $v_{k}$, update $\mathcal{S}_{k-1}$ by removing all the edges going out
of $v_{k}$ and add all edges coming into $v_{k},k\in\\{2,3,\ldots,n-1\\}$,
i.e.,

$\mathcal{S}_{k}=\\{\mathcal{S}_{k-1}\setminus\\{e=(i,j)\in
E_{PQ},s.t.i=v_{k}\\}\\}\cup\\{e=(i,j)\in E_{PQ},s.t.j=v_{k}\\}$

Note that, for every vertex other than the source and the sink, the sum of
capacities of all incoming edges is equal to the sum of all outgoing edges.
This ensures that each $\mathcal{S}_{k}$ corresponds to a min-cut of $G$.
Define $\mathcal{C}_{PQ}(\bar{\pi})$ as a convex combination of the above cuts
as follows.

$\mathcal{C}_{PQ}(\bar{\pi})=(\bar{\pi}(v_{1})-\bar{\pi}(v_{2}))*(\S_{1})+(\bar{\pi}(v_{2})-\bar{\pi}(v_{3}))*(\S_{2})+\ldots+(\bar{\pi}(v_{k-1})-\bar{\pi}(v_{k}))*(\S_{k-1})$

The sum of all weights in $\mathcal{C}_{PQ}(\bar{\pi})$ add up to
$\bar{\pi}(v_{1})-\bar{\pi}(v_{k})=\bar{\pi}(S(s))-\bar{\pi}(S(t))=1$. So,
$\mathcal{C}_{PQ}$ is a fractional cut of the graph $G_{PQ}$ and by taking the
corresponding edges in $G$ with equal weights, we get a fractional min-cut,
$\mathcal{C}(\bar{\pi})$, of the graph $G$. And, while the list $L$ was
created by breaking ties arbitrarily, the cut $\mathcal{C}_{PQ}(\bar{\pi})$
itself has been created using successive differences of potentials, which
would become zero in case of ties. Hence, it is as if we are pulling all the
vertices with equal potentials together across the cuts. The uniqueness of the
cut follows. And so, every dual consistent potential defines a unique
fractional min-cut. ∎

######  Lemma 3.3.

A dual-consistent potential $\bar{\pi}$ defines a unique imputation of the
max-flow game in graph $G$.

###### Proof.

Define the profit of each edge $(i,j)\in E$ using the potentials of the
corresponding vertices in $G_{PQ}$ as $p_{ij}=c_{ij}*\delta_{ij}$ where
$\delta_{ij}=(\bar{\pi}(S(i))-\bar{\pi}(S(j)))$. The total profit distributed
by this imputation is just the value of the fractional min-cut
$\mathcal{C}(\bar{\pi})$, which in turn is the max-flow and the worth of graph
$G$. ∎

######  Lemma 3.4.

The imputation defined by a dual-consistent potential $\bar{\pi}$ is in the
core of the max-flow game of graph $G$.

###### Proof.

As above, define
$\delta_{ij}=(\bar{\pi}_{S(i)}-\bar{\pi}_{S(j)}),\forall(i,j)\in E$. Define
potentials on $\pi$ on vertices in $V$ as the potential assigned to
corresponding vertices in $V_{PQ}$, i.e., $\forall v\in
V,\pi_{v}=\bar{\pi}(S(v))$ It can be seen that $\delta$ together with $\pi$ is
a feasible solution to the dual LPLABEL:Eqn:LP_flow of the graph. It is also
an optimal solution as it distributes the worth of a fractional min-cut. The
lemma follows from Theorem LABEL:thm:dual_characterization, which states that
every dual-optimal imputation is in core. ∎

The above lemma is the reason why we call the potential function “dual-
consistent”. The potentials arising from this function are consistent with the
dual LP of the graph. This also changes the problem’s perspective in a key
way. Before, we were to compute an optimal assignment of profits to the edges
in $G$. Now, we can find the optimal potentials on vertices of $G_{PQ}$, and
construct profits of the edges as above.

###  3.1 Finding Leximin and Leximax dual-consistent core imputations in the
flow game

We provide an intuition of algorithm 2 which computes the leximin core
imputation. It first constructs the PQ-structure($G_{PQ}$) of a graph $G$ \-
this preserves only the essential edges of the graph which are the only edges
getting profits in dual-consistent core imputations. Then it recursively
assigns potentials to the vertices, in a greedy way, as follows. First, it
assigns potentials of 1 and 0 for the PQ-source($S(s)$) and PQ-sink($S(t)$)
respectively. Let’s call the vertices with assigned and unassigned potentials
”Fixed vertices” and ”Free vertices” and represent them as $F$ and $R$
respectively. Call a path from one fixed vertex to another fixed vertex that
traverses only through free vertices as ”Free paths”. Among all free paths,
the algorithm finds the one that can give highest leximin profits on this
path. That is, among all these paths, it tries to assign potentials in such a
way that each of the edges gets the same profit. Then it chooses the one with
the least profit. Note that, if this path wasn’t chosen, any other assignment
of potentials on this path would only give a lesser cost to some edge, meaning
the assignment is ”lexi-worse”. It recursively finds such paths until all the
vertices are given potentials and then computes the profits of edges.
Algorithm 3 works in the same way - it chooses the free path that maximizes
the average profits assigned. Algorithms 4 and 5 treat all edge capacities as
equal and so, just look at the length of the paths.

Algorithm 2 Leximin dual-consistent core imputation, for profits, in max-flow
game

1:Input: A max flow game on graph $G(V,E)$, with source $s$ and a sink $t$,
and non-negative capacities, $c:E\to\mathbb{N}_{+}$.

2:Compute the Picard-Queyranne structure, $G_{PQ}$, of the graph $G$

3:Assign potentials($\pi$) of 1 and 0 to the source and sink of $G_{PQ}$

4:while There is a free vertex do

5: Find a free path $P=\operatorname*{arg\,min}_{P=[a,\ldots,b]\in\text{Free
paths}}\frac{\pi_{b}-\pi_{a}}{\sum_{e\in P}\frac{1}{c_{e}}}$

6: Assign potentials($\pi$) on $P$ such that all edges get equal profits

7: Update free and fixed vertices

8:end while

9:For all edges $(i,j)\in E^{\prime}$, set
profit${}_{ij}=c_{ij}(\pi_{j}-\pi_{i})$

10:Output: The Leximin dual-consistent core imputation.

Algorithm 3 Leximax dual-consistent core imputation, for profits, in max-flow
game

1:Input: A max flow game on graph $G(V,E)$, with source $s$ and a sink $t$,
and non-negative capacities, $c:E\to\mathbb{N}_{+}$.

2:Compute the Picard-Queyranne structure, $G_{PQ}$, of the graph $G$

3:Assign potentials($\pi$) of 1 and 0 to the source and sink of $G_{PQ}$

4:while There is a free vertex do

5: Find a free path $P=\operatorname*{arg\,max}_{P=[a,\ldots,b]\in\text{Free
paths}}\frac{\pi_{b}-\pi_{a}}{\sum_{e\in P}\frac{1}{c_{e}}}$

6: Assign potentials($\pi$) on $P$ such that all edges get equal profits

7: Update free and fixed vertices

8:end while

9:For all edges $(i,j)\in E^{\prime}$, set
profit${}_{ij}=c_{ij}(\pi_{j}-\pi_{i})$

10:Output: The Leximax dual-consistent core imputation.

Algorithm 4 Leximin dual-consistent core imputation, for distance labels, in
max-flow game

1:Input: A max flow game on graph $G(V,E)$, with source $s$ and a sink $t$,
and non-negative capacities, $c:E\to\mathbb{N}_{+}$.

2:Compute the Picard-Queyranne structure, $G_{PQ}$, of the graph $G$

3:Assign potentials($\pi$) of 1 and 0 to the source and sink of $G_{PQ}$

4:while There is a free vertex do

5: Find a free path $P=\operatorname*{arg\,min}_{P=[a,\ldots,b]\in\text{Free
paths}}\frac{\pi_{b}-\pi_{a}}{\text{length of }P}$

6: Assign potentials($\pi$) on $P$ such that all edges get equal profits

7: Update free and fixed vertices

8:end while

9:For all edges $(i,j)\in E^{\prime}$, set
profit${}_{ij}=c_{ij}(\pi_{j}-\pi_{i})$

10:Output: The Leximin dual-consistent core imputation.

Algorithm 5 Leximax dual-consistent core imputation, for distance labels, in
max-flow game

1:Input: A max flow game on graph $G(V,E)$, with source $s$ and a sink $t$,
and non-negative capacities, $c:E\to\mathbb{N}_{+}$.

2:Compute the Picard-Queyranne structure, $G_{PQ}$, of the graph $G$

3:Assign potentials($\pi$) of 1 and 0 to the source and sink of $G_{PQ}$

4:while There is a free vertex do

5: Find a free path $P=\operatorname*{arg\,max}_{P=[a,\ldots,b]\in\text{Free
paths}}\frac{\pi_{b}-\pi_{a}}{{\text{length of }P}}$

6: Assign potentials($\pi$) on $P$ such that all edges get equal profits

7: Update free and fixed vertices

8:end while

9:For all edges $(i,j)\in E^{\prime}$, set
profit${}_{ij}=c_{ij}(\pi_{j}-\pi_{i})$

10:Output: The Leximax dual-consistent core imputation.

######  Theorem 3.5.

For a max flow game on a graph $G$, algorithms 2 and 3 compute the leximin and
leximax imputations over profits among all dual-consistent core imputations
and algorithms 4 and 5 compute the leximin and leximax imputations over
distance labels among all dual-consistent core imputations in polynomial time.

###### Proof.

We only argue about the correctness and efficiency of algorithm 2. The
workings of algorithms 3, 4 and 5 are similar.

In algorithm 2, finding the free path with least
$\frac{\pi_{b}-\pi_{a}}{\sum_{e\in P}\frac{1}{c_{e}}}$ is the same as finding
the free path with highest $\frac{\sum_{e\in
P}\frac{1}{c_{e}}}{\pi_{b}-\pi_{a}}$. This can be done in polynomial time by
considering a new graph with inverted edge lengths, finding the longest path,
$P_{i,j}$ with length $l_{i,j}$, between every pair $(i,j)$ of fixed vertices
in the new graph, and choosing the one with highest
$\frac{l_{i,j}}{\pi_{j}-\pi_{i}}$. Since the longest path in a directed
acyclic graph can be computed efficiently, the algorithm can be executed in
polynomial time.

Verifying that the assigned potentials are dual-consistent is trivial - a
violating edge $e=(i,j)$ with $\pi_{i}-\pi_{j}<0$ would imply a better free
path when $i$ was being assigned its potential. To show that the final
imputation is leximin, consider the profit of edges in the order we choose the
paths. Every time we choose a path and assign potentials, we assign the
minimum average profits possible on this path to all the edges. If one of
these edges gets a higher profit, some other edge on the path should get a
lower profit implying the allocation is lexicographically worse. And so, the
optimal allocation should assign the same profits to these edges and hence,
the same potentials on the vertices. The proof that the resulting imputation
is leximin among dual-consistent core imputations follows by induction. ∎

## References

  * [FZCD02] Qizhi Fang, Shanfeng Zhu, Maocheng Cai, and Xiaotie Deng.  On computational complexity of membership test in flow games and linear production games.  International Journal of Game Theory, 31:39–45, 2002.
  * [KZ82] Ehud Kalai and Eitan Zemel.  Totally balanced games and games of flow.  Mathematics of Operations Research, 7(3):476–478, 1982.
  * [PQ80] Jean-Claude Picard and Maurice Queyranne.  On the structure of all minimum cuts in a network and applications, pages 8–16.  Springer Berlin Heidelberg, Berlin, Heidelberg, 1980.
  * [Vaz23] Vijay V. Vazirani.  LP-Duality theory and the cores of games.  arXiv preprint arXiv: 2302.07627, 2023.
  * [Vaz24] Vijay V Vazirani.  The assignment game: New mechanisms for equitable core imputations.  arXiv preprint arXiv:2402.11437, 2024.