# Heron triangles and the hunt for unicorns

Andrew N.W. Hone111School of Mathematics, Statistics & Actuarial Science,
University of Kent, Canterbury CT2 7FS, UK.
E-mail<EMAIL_ADDRESS>
###### Abstract

A Heron triangle is one that has all integer side lengths and integer area,
which takes its name from Heron of Alexandria’s area formula. From a more
relaxed point of view, if rescaling is allowed, then one can define a Heron
triangle to be one whose side lengths and area are all rational numbers. A
perfect triangle is a Heron triangle with all three medians being rational.
According to a longstanding conjecture, no such triangle exists, so perfect
triangles are as rare as unicorns.

However, if perfect is the enemy of good, then perhaps it is best to insist on
only two of the medians being rational. Buchholz and Rathbun found an infinite
family of Heron triangles with two rational medians, which they were able to
associate with the set of rational points on an elliptic curve
$E({\mathbb{Q}})$. Here we describe a recently discovered explicit formula for
the sides, area and medians of these (almost perfect) triangles, expressed in
terms of a pair of integer sequences: these are Somos sequences, which first
became popular thanks to David Gale’s column in Mathematical Intelligencer.

Acknowledgments: This research was supported by Fellowship EP/M004333/1 from
the Engineering & Physical Sciences Research Council, UK, with EP/V520718/1
UKRI COVID-19 Grant Extension Allocation, and grant IEC\R3\193024 from the
Royal Society.

##  1 Pythagorean triples

One of the oldest problems in the theory of Diophantine equations is to find
right-angled triangles with integer side lengths, or equivalently triples of
positive integers $(a,b,c)$ such that

$a^{2}+b^{2}=c^{2},$ (1.1)

which are called Pythagorean triples. Examples were known to the Babylonians
in around 1800 B.C. Taking positive integers $m>n$ and $\uptau$, all such
triples can be determined from the formula

$a=\uptau\,(m^{2}-n^{2}),\qquad b=2\uptau\,mn,\qquad c=\uptau\,(m^{2}+n^{2}),$
(1.2)

which was presented by Euclid, but without the arbitrary scale factor
$\uptau$. A primitive Pythagorean triple is one for which $\gcd(a,b,c)=1$, and
(up to switching $a$ and $b$) all primitive triples are obtained from (1.2) by
taking $\uptau=1$, and $m,n$ coprime with at least one of them being even.

The formula (1.2) can be derived directly by starting from simple congruences
mod 2 and mod 4, but another way to obtain it is to consider rational points
on an algebraic curve, namely the unit circle

$x^{2}+y^{2}=1,\qquad\mathrm{where}\qquad x=\frac{a}{c},\quad y=\frac{b}{c}.$

For any rational point $(x,y)\in{\mathbb{Q}}^{2}$ on this circle, distinct
from the point $(-1,0)$, we form the chord joining them, given by the line
$y=t(x+1)$ with slope $t$. Hence we find the rational parametrization of the
circle,

$x=\frac{1-t^{2}}{1+t^{2}},\qquad y=\frac{2t}{1+t^{2}},$ (1.3)

related to the usual trigonometric parametrization $x=\cos\theta$,
$y=\sin\theta$ by the “t-substitution” of integral calculus, that is
$t=\tan\tfrac{\theta}{2}$, and formula (1.2) follows from taking rational
$t=\tfrac{n}{m}$ with $0<t<1$.

##  2 Heron triangles and unicorns

For a triangle with sides $(a,b,c)$ and semiperimeter $s$, the area formula

$\Delta=\sqrt{s(s-a)(s-b)(s-c)},\qquad s=\frac{a+b+c}{2}$ (2.1)

is attributed to Heron of Alexandria. If the side lengths are integers and the
area $\Delta$ is also an integer, then this is called a Heron triangle.
Allowing the freedom to rescale all the sides by the same factor, it is
convenient to define a triangle to be Heron whenever the side lengths and the
area are all rational numbers.

Trivially, any right-angled triangle given by a Pythagorean triple is Heron.
More generally, dropping a perpendicular from any vertex of a Heron triangle
splits it into a pair of right-angled triangles with the same height, either
joined back-to-back, or overlapping one another, and it is not hard to see
that both triangles must have rational sides, so that (up to rescaling) the
Heron triangle is built from a pair of Pythagorean triples. This construction
can be used to derive a parametric formula for Heron triangles, that is

$a=\frac{p^{2}+r^{2}}{p},\qquad b=\frac{q^{2}+r^{2}}{q},\qquad
c=\frac{(p+q)\,|r^{2}-pq|}{pq},\qquad\mathrm{with}\quad\Delta=rc,$ (2.2)

for arbitrary positive rational numbers $p,q,r$ such that $r^{2}\neq pq$,
which was known to Brahmagupta in the 7th century A.D. [3].

To see a particular example, taking $p=3,q=4,r=6$ in (2.2) leads to the Heron
triangle with $a=15$, $b=13$, $c=14$ and area $\Delta=84$, which can be built
out of the $(5,12,13)$ and $(9,12,15)$ Pythagorean triples, by placing these
two right-angled triangles back-to-back along the height $2r=12$, as in Fig.1.
(This choice of parameters is not unique: for instance, ordering the sides
differently as $(a,b,c)=(15,14,13)$ instead of $(15,13,14)$, the same Heron
triangle can be obtained from $p=\tfrac{147}{13}$, $q=\tfrac{126}{13}$,
$r=\tfrac{84}{13}$.) A systematic method for enumerating Heron triangles with
integer sides was given by Schubert [11]. In Schubert’s scheme, $(15,13,14)$
is the first example of a Heron triangle with integer sides which is not
right-angled or isosceles. However, if we combine the same two Pythagorean
triples by overlapping the triangles (rather than back-to-back as in the
figure), then we get the $(15,13,4)$ Heron triangle with a smaller area
$\Delta=24$, which nevertheless appears further down in Schubert’s list.

Figure 1: The (15,13,14) Heron triangle from the two Pythagorean triples
(9,12,15) & (5,12,13).

The unicorns in our story are perfect triangles: triangles which have all
integer sides, all integer medians, and integer area. Does a perfect triangle
exist, or equivalently, is there a Heron triangle with three rational medians?
It is believed that there is no such thing, but despite incorrect “proofs” in
the literature, the problem remains open [7]. The rest of our discussion is
devoted to seeing how close we can get to perfection.

Henceforth the medians bisecting sides $a,b,c$ are denoted $k,\ell,m$,
respectively, which leads to the relations

$k^{2}=\frac{1}{4}(2b^{2}+2c^{2}-a^{2}),\quad\ell^{2}=\frac{1}{4}(2c^{2}+2a^{2}-b^{2}),\quad
m^{2}=\frac{1}{4}(2a^{2}+2b^{2}-c^{2}).$ (2.3)

We label the angles adjacent to the median $k$ as in Fig.2, and our first step
towards the elusive perfect triangle will be to consider the requirement that
just this median should be rational.

##  3 Heron triangles with one rational median

From a construction of parallelograms with rational sides, area and diagonals,
Schubert was led to the case of Heron triangles with one median being
rational, and went on to present an argument that such triangles could not
have a second rational median, which a fortiori would rule out the existence
of perfect triangles. However, as pointed out by Dickson [3], this argument
contained an oversight. This flaw notwithstanding, an identity of Schubert for
Heron triangles with one rational median is crucial for what follows.

If we write ${\bf b},{\bf c},{\bf k}$ for the vectors corresponding to the
lengths $b,c,k$, respectively, directed outwards from the top vertex in Fig.2,
and ${\bf a}={\bf b}-{\bf c}=2({\bf k}-{\bf c})=2({\bf b}-{\bf k})$, then the
dot product $({\bf b}-{\bf c})\cdot{\bf k}={\bf a}\cdot{\bf k}$ gives
$bk\cos{\alpha}-ck\cos{\beta}=ak\cos{\gamma}$, while the area of the triangle
is $\Delta=|{\bf b}\times{\bf k}|=|{\bf c}\times{\bf k}|=\tfrac{1}{2}|{\bf
a}\times{\bf k}|$, which gives
$\Delta=bk\sin{\alpha}=ck\sin{\beta}=\frac{1}{2}ak\sin{\gamma}$; so combining
these relations produces the identity

$2\cot{\gamma}=\cot{\alpha}-\cot{\beta}.$ (3.1)

Given three angles ${\alpha},{\beta},{\gamma}$ in the interval $(0,\pi)$,
subject to ${\alpha}+{\beta}<\pi$, it is convenient to take

$M=\mathrm{cot}\tfrac{{\alpha}}{2},\qquad
P=\mathrm{cot}\tfrac{{\beta}}{2},\qquad X=\mathrm{cot}\tfrac{{\gamma}}{2},$
(3.2)

as parameters, and then by standard trigonometric identities (equivalent to
the “t-substitution” in (1.3) above) the identity (3.1) becomes a rational
relation between these three quantities, namely

$M-\frac{1}{M}=P-\frac{1}{P}+2\left(X-\frac{1}{X}\right).$ (3.3)

This gives the equation of a surface in three-dimensional space with
coordinates $(M,P,X)$, which can be rewritten as the vanishing of a
polynomial: $2MP(X^{2}-1)+MX(P^{2}-1)-PX(M^{2}-1)=0;$ we refer to it as the
Schubert surface.

From the half-angle identity
$\mathrm{cot}\tfrac{{\alpha}}{2}=\sin{\alpha}/(1-\cos{\alpha})$ we have
$M=\Delta/(bk-{\bf b}\cdot{\bf k})$. Using the analogous expressions for $P$
and $X$, together with dot product relations, we can express these Schubert
parameters in terms of the area, side lengths and the median by the formulae

$M=\frac{4\Delta}{4bk+a^{2}-3b^{2}-c^{2}},\quad
P=\frac{4\Delta}{4ck+a^{2}-b^{2}-3c^{2}},\quad
X=\frac{4\Delta}{2ak-b^{2}+c^{2}}.$ (3.4)

The ratios of the side lengths are given in terms of the Schubert parameters
by

$\frac{a}{c}=\frac{2(X+X^{-1})}{P+P^{-1}},\qquad\frac{b}{c}=\frac{M+M^{-1}}{P+P^{-1}}.$
(3.5)

$b$$c$$k$${\beta}$${\alpha}$$a$${\gamma}$ Figure 2: Triangle with one labelled
median

The formulae (3.4) show that each Heron triangle with a rational median $k$
produces a rational point on the Schubert surface (3.3), with positive
coordinates $(M,P,X)\in{\mathbb{Q}}^{3}$. How about the converse: does every
rational point on this surface correspond to a Heron triangle with (at least)
one rational median? In fact, using certain discrete symmetries of the surface
(sending $(M,P,X)\to(M^{-1},P^{-1},X^{-1})$, or replacing one of the Schubert
parameters by minus its reciprocal), we can start with any triple of non-zero
values $(M,P,X)\in{\mathbb{Q}}^{3}$ satisfying (3.3), and turn it into a valid
positive triple. Then the side lengths $(a,b,c)$ are determined by $(M,P,X)$
using the rational expressions (3.5), up to an arbitrary choice of scale;
after fixing the scale, any two of the equations (3.4) allow the rational
numbers $k$ and $\Delta$ to be recovered.

##  4 Triangles with two rational medians

In striving to get closer to perfection, another possible direction for our
first step is to drop the initial requirement that the area $\Delta$ should be
rational, and just consider triangles with rational sides $(a,b,c)$ and two
rational medians $k,\ell$. In his PhD thesis, Buchholz obtained a rational
parametrization of all such triangles, given by the formulae

$\begin{array}[]{rcl}a&=&\uptau\,(-2\theta^{2}\phi-\theta\phi^{2}+2\theta\phi-\phi^{2}+\theta+1),\\\
b&=&\uptau\,(\theta^{2}\phi+2\theta\phi^{2}-\theta^{2}+2\theta\phi-\phi+1),\\\
c&=&\uptau\,(\theta^{2}\phi-\theta\phi^{2}+\theta^{2}+2\theta\phi+\phi^{2}+\theta-\phi),\end{array}$
(4.1)

where $\theta,\phi$ are rational numbers subject to constraints ensuring
positivity of the side lengths, namely

$0<\theta<1,\qquad 0<\phi<1,\qquad\phi+2\theta>1,$ (4.2)

and the positive parameter $\uptau\in{\mathbb{Q}}$ allows for the arbitrary
choice of scale. Conversely, the parameters $(\theta,\phi)\in{\mathbb{Q}}^{2}$
can be written as rational functions of the side lengths and two medians,
given by

$\theta=\frac{c-a\pm 2\ell}{2s},\qquad\phi=\frac{b-c\pm 2k}{2s},$ (4.3)

where $s=\frac{1}{2}(a+b+c)$ is the semiperimeter, as before.

Note that in (4.3) there are two independent choices of $\pm$ signs, and hence
four different pairs $(\theta,\phi)$ associated with the same rational
triangle with two rational medians.

##  5 Intermezzo: Somos-5 sequences

Before we continue on our quest for the perfect triangle, we must recall some
beautiful observations made by Michael Somos [12]. The saga of Somos sequences
attracted widespread attention due to Mathematical Intelligencer articles by
David Gale [6], and provided inspiration for the study of the Laurent
phenomenon and its development in Fomin and Zelevinksy’s theory of cluster
algebras [4, 5], which has been one of the hottest topics in algebra for
almost 25 years.

A recurrence relation of Somos type is a homogeneous quadratic recurrence
relation of a particular form. Here we focus on the example of Somos-5, which
is the recurrence relation of order 5 given by

$S_{n+5}S_{n}=S_{n+4}S_{n+1}+S_{n+3}S_{n+2}$ (5.1)

Somos noticed that if all five initial values are 1, then the resulting
sequence222 See http://oeis.org/A006721. begins with

$1,1,1,1,1,2,3,5,11,37,83,274,1217,6161,22833,165713,\ldots,$ (5.2)

and consists entirely of integers. This seems very surprising, because at each
iteration of (5.1) one must divide the right-hand side by $S_{n}$ to obtain
the new term $S_{n+5}$. The Laurent property provides one explanation for the
integrality of the sequence (5.2): if the initial values $S_{j}$, $1\leq j\leq
5$ for the recurrence are considered as variables, then each iterate turns out
to be a polynomial in these quantities and their reciprocals with integer
coefficients: $S_{n}={\mathcal{P}}_{n}(S_{1}^{\pm 1},S_{2}^{\pm 1},S_{3}^{\pm
1},S_{4}^{\pm 1},S_{5}^{\pm 1})$ (that is, a Laurent polynomial). Upon
substituting $S_{1}=S_{2}=S_{3}=S_{4}=S_{5}=1$ into each polynomial
${\mathcal{P}}_{n}$, the integer sequence (5.2) results.

Figure 3: Some orbits of the map (5.4) in the positive quadrant.

Another completely different way to understand Somos-5 sequences relies on a
connection with integrable maps, which are discrete analogues of exactly
solvable systems in Hamiltonian mechanics. To see this connection, note that
the recurrence (5.1) has three independent scaling symmetries: rescaling
even/odd index terms separately, so $S_{2j}\to A_{+}\,S_{2j}$, $S_{2j+1}\to
A_{-}\,S_{2j+1}$, and rescaling $S_{n}\to B^{n}\,S_{n}$ for any $n$, where
$A_{+},A_{-},B$ are arbitrary non-zero constants. Moreover, we can form a
sequence of ratios that is left invariant by these scaling symmetries, and
find that it satisfies a recurrence of second order:

$u_{n}=\frac{S_{n-2}S_{n+1}}{S_{n-1}S_{n}}\implies
u_{n+1}u_{n-1}=1+\frac{1}{u_{n}}.$ (5.3)

By considering $(U,V)=(u_{n},u_{n+1})$ as a point in the plane, each shift
$n\to n+1$ of the discrete “time” in (5.3) is equivalent to an iteration of a
birational transformation (a rational map with a rational inverse):

$\varphi:\qquad\left(\begin{array}[]{c}U\\\
V\end{array}\right)\mapsto\left(\begin{array}[]{c}V\\\
U^{-1}(1+V^{-1})\end{array}\right).$ (5.4)

The transformation (5.4) is an example of a Quispel-Roberts-Thompson (QRT)
map: such maps have arisen in various physical contexts, including statistical
mechanics, nonlinear waves (solitons) and quantum field theory [10]. In a
suitable regime, the iterates of the map appear like a stroboscopic view of a
mechanical system with one degree of freedom. More precisely, the
transformation $\varphi$ is area-preserving (symplectic): it preserves the
logarithmic area element $(UV)^{-1}\,\mathrm{d}U\,\mathrm{d}V$ in the plane;
and it obeys conservation of energy, where “energy” in this case is the
rational function

$\tilde{J}=U+V+\frac{1}{U}+\frac{1}{V}+\frac{1}{UV}.$ (5.5)

The level sets of this function are plane curves $\tilde{J}=\,$constant, and
each orbit of $\varphi$ lies on a fixed level set. The behaviour is especially
regular in the positive quadrant $U>0$, $V>0$, where each orbit densely fills
a compact oval (see Fig.3, where 300 points are plotted on each orbit).

We shall see that in relation to Heron triangles with two rational medians,
two different integer sequences appear, namely the pair of Somos-5 sequences
given by

$(S_{n}):\quad 1,1,1,2,3,5,11,37,83,274,\ldots,\qquad(T_{n}):\quad
0,1,-1,1,1,-7,8,-1,-57,391,\ldots,$ (5.6)

where the terms above are listed starting from the index $n=0$. The first one,
$(S_{n})$, is just the original Somos-5 sequence (5.2), but indexed
differently: it corresponds to the orbit of the map $\varphi$ through the
point $(1,1)$, while the second sequence, $(T_{n})$, corresponds to the orbit
through the point $(-1,7)$. It is easily verified that both of these orbits
lie on the same level curve $\tilde{J}=5$ of the function (5.5),

$U^{2}V+UV^{2}+U+V-5UV+1=0,$ (5.7)

a plane cubic curve (total degree 3) which is also biquadratic (quadratic in
both $U$ and $V$). The first orbit corresponds to the oval shown in red in
Fig.3, whereas the second orbit lies outside the positive quadrant, moving
around the three unbounded components of this curve, which can be seen in
Fig.4.

Figure 4: The curve (5.7) in the $(U,V)$-plane.

##  6 Heron triangles with two rational medians

Buchholz found the first example of a Heron triangle with two rational
medians: the $(73,51,26)$ triangle with area $420$ and $k=\frac{35}{2}$,
$\ell=\frac{97}{2}$, which had been overlooked by Schubert in his work on
parallelograms. After joining forces, Buchholz and Rathbun conducted a
systematic search for such triangles, using the following algorithm based on
(4.1): fix the scale $\uptau=1$, enumerate pairs of rational numbers
$(\theta,\phi)$, and for each pair use Heron’s formula (2.1) to check whether
the area $\Delta$ is rational [1]. The first few triangles obtained from this
search are shown in Table 1, where each triangle is represented by positive
integers $(a,b,c)$ with $\gcd(a,b,c)=1$: their initial investigations
suggested that there should be an infinite family of such triangles (rows
labelled with a positive integer $n$), together with an unknown number of
sporadic triangles that do not fit into this family (rows labelled with
asterisks).

Table 1: The smallest Heron triangles with two rational medians. $n$ | $a$ | $b$ | $c$ | $k$ | $\ell$ | $\Delta$
---|---|---|---|---|---|---
1 | 73 | 51 | 26 | ${35}/{2}$ | ${97}/{2}$ | 420
2 | 626 | 875 | 291 | 572 | ${433}/{2}$ | 55440
* | 1241 | 4368 | 3673 | ${7975}/{2}$ | 1657 | 2042040
** | 14384 | 14791 | 11257 | 11001 | 21177/2 | 75698280
3 | 28779 | 13816 | 15155 | 3589/2 | 21937 | 23931600
4 | 1823675 | 185629 | 1930456 | 2048523/2 | 3751059/2 | 142334216640
*** | 2288232 | 1976471 | 2025361 | 1641725 | 3843143/2 | 1877686881840
**** | 22816608 | 20565641 | 19227017 | 16314487 | 36845705/2 | 185643608470320
5 | 2442655864 | 2396426547 | 46263061 | 1175099279 | 2488886435/2 | 2137147184560080

Heron triangles with two rational medians are associated with two different
triples of Schubert parameters $(M_{a},P_{a},X_{a})$, $(M_{b},P_{b},X_{b})$,
each corresponding to a particular set of angles ${\alpha},{\beta},{\gamma}$
adjacent to one of the medians $k$, $\ell$, respectively. These triples
provide two different rational points on the Schubert surface (3.3), coupled
by two constraints coming from the ratios of side lengths, as in (3.5).
Remarkably, by considering the patterns of prime factors appearing in these
rational numbers, Buchholz and Rathbun found conjectural formulae for a subset
of these parameter triples in terms of the two Somos sequences (5.6), such as

$M_{a}=-\frac{S_{n+1}S_{n+2}^{2}T_{n}}{S_{n}T_{n+1}T_{n+2}^{2}},\qquad
M_{b}=\frac{S_{n+1}S_{n+4}T_{n+1}T_{n+4}}{S_{n+2}S_{n+3}T_{n+2}T_{n+3}},$
(6.1)

and analogous expressions for the other elements of each triple. When, for
successive integers $n=1,2,3,\ldots$, they plotted the corresponding pairs
$(\theta,\phi)$ found from (4.3) with a fixed choice of $\pm$ signs, they
found them to lie on one of five algebraic curves ${\cal C}_{j}$, $1\leq j\leq
5$, isomorphic to one another and repeating in a pattern with period 7, the
simplest-looking curve being the biquadratic cubic

${\cal
C}_{4}:\qquad\theta^{2}\phi-\theta\phi^{2}+\theta\phi+2\theta-2\phi-1=0.$
(6.2)

It was pointed out by Elkies that the sequences (5.6) can be written using
theta functions associated with the elliptic curve given by the equation

$E({\mathbb{Q}}):\qquad y^{2}+xy=x^{3}+x^{2}-2x,$ (6.3)

which has infinitely many rational points,333See
https://www.lmfdb.org/EllipticCurve/Q/102a1/. and is isomorphic (birationally
equivalent) to ${\cal C}_{4}$. Indirectly, this led to a proof that every
rational point $(\theta,\phi)$ on the genus one curve ${\cal C}_{4}$ given by
(6.2), subject to the constraints (4.2), corresponds to a Heron triangle with
two rational medians [2].

Table 2: Prime factors of the semiperimeter, reduced side lengths and area in
the infinite family.

$n$ | $s$ | $s-a$ | $s-b$ | $s-c$ | $\Delta$
---|---|---|---|---|---
1 | $3\cdot 5^{2}$ | 2 | $2^{3}\cdot 3$ | $7^{2}$ | $2^{2}\cdot 3\cdot 5\cdot 7$
2 | $5\cdot 11^{2}$ | $3\cdot 7$ | $2\cdot 3^{3}\cdot 5$ | $2^{7}\cdot 7$ | $2^{4}\cdot 3^{2}\cdot 5\cdot 7\cdot 11$
3 | $11\cdot 37^{2}$ | $2^{3}\cdot 5\cdot 7^{3}$ | $3\cdot 5^{3}\cdot 7\cdot 11$ | $2^{5}\cdot 3$ | $2^{4}\cdot 3\cdot 5^{2}\cdot 7^{2}\cdot 11\cdot 37$
4 | $7\cdot 37\cdot 83^{2}$ | $2^{9}\cdot 7\cdot 11$ | $2^{3}\cdot 5\cdot 11^{3}\cdot 37$ | $3^{4}\cdot 5\cdot 19^{2}$ | $2^{6}\cdot 3^{2}\cdot 5\cdot 7\cdot 11^{2}\cdot 19\cdot 37\cdot 83$
5 | $2^{5}\cdot 7^{2}\cdot 83\cdot 137^{2}$ | $2^{3}\cdot 3\cdot 19\cdot 37$ | $11\cdot 37^{3}\cdot 83$ | $3\cdot 5^{2}\cdot 11\cdot 17^{2}\cdot 19\cdot 23^{2}$ | $2^{4}\cdot 3\cdot 5\cdot 7\cdot 11\cdot 17\cdot 19\cdot 23\cdot 37^{2}\cdot 83\cdot 137$

However, until very recently, (6.1) and the explicit expressions for the other
Schubert parameters remained conjectural. The key to progress in [8] was to
observe the elegant factorization pattern in the quantities appearing under
the square root in Heron’s formula, namely the semiperimeter $s$ and the
reduced side lengths $s-a$, $s-b$, $s-c$ (see Table 2). It turns out that (up
to an overall sign) each of these four quantities is given by a specific
product of terms from the two Somos-5 sequences, leading to the following
result.

######  Theorem 6.1.

For each integer $n\geq 1$, the terms in the pair of Somos-5 sequences
$(S_{n})$ and $(T_{n})$ in (5.6) provide a Heron triangle with two rational
medians, having integer side lengths given by

$\begin{array}[]{rcl}a&=&|S_{n+1}S_{n+2}^{3}S_{n+3}T_{n+2}+S_{n}^{2}S_{n+1}T_{n+3}T_{n+4}^{2}|,\\\
b&=&|S_{n}^{2}S_{n+1}T_{n+3}T_{n+4}^{2}-T_{n+1}T_{n+2}^{3}T_{n+3}S_{n+2}|,\\\
c&=&|T_{n+1}T_{n+2}^{3}T_{n+3}S_{n+2}-S_{n+1}S_{n+2}^{3}S_{n+3}T_{n+2}|,\end{array}$

with $\gcd(a,b,c)=1$, rational median lengths

$\begin{array}[]{rcl}k&=&{\scriptstyle\frac{1}{2}}|S_{n+4}T_{n+4}(T_{n}T_{n+1}^{2}T_{n+2}-S_{n}S_{n+1}^{2}S_{n+2})|,\\\
\ell&=&{\scriptstyle\frac{1}{2}}|S_{n}T_{n}(T_{n+2}T_{n+3}^{2}T_{n+4}-S_{n+2}S_{n+3}^{2}S_{n+4})|,\end{array}$

and integer area

$\Delta=|S_{n}S_{n+1}S_{n+2}^{2}S_{n+3}S_{n+4}T_{n}T_{n+1}T_{n+2}^{2}T_{n+3}T_{n+4}|.$

Table 3: Prime factors of the semiperimeter, reduced side lengths and area in
the sporadic cases.

$n$ | $s$ | $s-a$ | $s-b$ | $s-c$ | $\Delta$
---|---|---|---|---|---
* | $3\cdot 7\cdot 13\cdot 17$ | $2^{3}\cdot 5^{2}\cdot 17$ | $3\cdot 7\cdot 13$ | $2^{3}\cdot 11^{2}$ | $2^{3}\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17$
* | $2^{3}\cdot 7\cdot 19^{2}$ | $2^{3}\cdot 3^{6}$ | $5^{2}\cdot 7\cdot 31$ | $17^{2}\cdot 31$ | $2^{3}\cdot 3^{3}\cdot 5\cdot 7\cdot 17\cdot 19\cdot 31$
** | $2^{3}\cdot 3^{2}\cdot 11^{2}\cdot 19^{2}$ | $2^{5}\cdot 3^{2}\cdot 5^{2}\cdot 7\cdot 17$ | $23^{2}\cdot 47^{2}$ | $7\cdot 17\cdot 97^{2}$ | $2^{4}\cdot 3^{2}\cdot 5\cdot 7\cdot 11\cdot 17\cdot 19\cdot 23\cdot 47\cdot 97$
*** | $17\cdot 23^{2}\cdot 59^{2}$ | $5^{2}\cdot 7^{2}\cdot 13^{2}\cdot 41$ | $2^{4}\cdot 3\cdot 11^{2}\cdot 43^{2}$ | $2^{4}\cdot 3\cdot 17\cdot 19^{2}\cdot 41$ | $2^{4}\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23\cdot 41\cdot 43\cdot 59$

The curve (5.7) is birationally equivalent to the curve ${\cal C}_{4}$ in
(6.2), hence also to the curve (6.3). Its set of rational points is the union
of two orbits of the map (5.4): the orbit associated with the sequence
$(S_{n})$, lying on the oval in the positive quadrant in Fig.4; and the orbit
associated with $(T_{n})$, which jumps around the other three quadrants in a
pattern that repeats with period 7. Thus these two Somos-5 sequences
completely encode the structure of this infinite family of Heron triangles
with two rational medians. It is natural to wonder if any of the triangles in
this family can have a third rational median $m$, but it has been proven that
this is not the case [9].

Still, this leaves some big challenges to the reader: so far only four
sporadic triangles have been found, which do not belong to the infinite
family! The prime factorization of each semiperimeter and the reduced lengths
in Table 3 give tantalizing hints of further structure. Can you extend the
search to find more sporadic examples, and fit them into one or more new
infinite families, encoded by Somos (or other) sequences? Or can you show that
these four are the only sporadic triangles, thereby proving that unicorns do
not exist?

## References

  * [1] R.H. Buchholz and R.L. Rathbun, An infinite set of Heron triangles with two rational medians, Amer. Math. Monthly 104 (1997) 107–115.
  * [2] R.H. Buchholz and R.L. Rathbun, Heron triangles and elliptic curves, Bull. Austral. Math. Soc. 58 (1998) 411–421.
  * [3] L.E. Dickson, History of the Theory of Numbers, Vol. II: Diophantine Analysis, Carnegie Institution, Washington, 1920.
  * [4] S. Fomin and A. Zelevinsky, The Laurent Phenomenon, Adv. Appl. Math. 28 (2002) 119–144.
  * [5] A.P. Fordy and R.J. Marsh, Cluster mutation-periodic quivers and associated Laurent sequences, J. Algebraic Combin. 34 (2011) 19–66.
  * [6] D. Gale, The strange and surprising saga of the Somos sequences, Mathematical Intelligencer 13 (1) (1991) 40–42; Somos sequence update, Mathematical Intelligencer 13 (4) (1991) 49–50; reprinted in Tracking the Automatic Ant, Springer, 1998.
  * [7] R.K. Guy, Unsolved Problems in Number Theory, Springer-Verlag, New York, 1981.
  * [8] A.N.W. Hone, Heron triangles with two rational medians and Somos-5 sequences. European Journal of Mathematics 8 (2022) 1424–1486.
  * [9] S. Ismail and Z. Eshkuvatov, Perfect Triangles: Rational Points on the Curve $C_{4}$ (The Unsolved Case), J. Phys. Conf. Ser. 1489 (2020) 012003.
  * [10] G.R.W. Quispel, J.A.G. Roberts and C.J. Thompson, Integrable mappings and soliton equations, Phys. Lett. A 126 (1988) 419–421.
  * [11] H. Schubert, Die Ganzzahligkeit in der algebraischen Geometrie, Spamersche Buchdruckerei, Leipzig, 1905.
  * [12] M. Somos, Problem 1470, Crux Mathematicorum 15 (1989) 208.


# Cost Sharing under Private Costs and Connection Control on Directed Acyclic
Graphs

Tianyi Zhang, Dengji Zhao, Junyu Zhang, and Sizhe Gu  ShanghaiTech
UniversityShanghaiChina zhangty, zhaodj, zhangjy22022,
<EMAIL_ADDRESS>
###### Abstract.

We consider a cost sharing problem on a weighted directed acyclic graph (DAG)
with a source node to which all the other nodes want to connect. The cost
(weight) of each edge is private information reported by multiple contractors,
and among them, only one contractor is selected as the builder. All the nodes
except for the source need to share the total cost of the used edges. However,
they may block others’ connections to the source by strategically cutting
their outgoing edges to reduce their cost share, which may increase the total
cost of connectivity. To minimize the total cost of connectivity, we design a
cost sharing mechanism to incentivize each node to offer all its outgoing
edges and each contractor to report all the edges’ weights truthfully, and
show the properties of the proposed mechanism. In addition, our mechanism
outperforms the two benchmark mechanisms.

Cost sharing, Mechanism design, Directed acyclic graphs, Truthfulness

††copyright: none

##  1\. Introduction

In the classic cost sharing problem, there is a group of agents at different
locations and a source (Bergantiños and Gómez-Rúa, 2010; Gómez-Rúa and Vidal-
Puga, 2011; Trudeau and Vidal-Puga, 2017). All the agents want to connect with
the source via the connections between the locations. Each connection has a
public cost. The goal is to share the total cost of connectivity among all the
agents (Claus and Kleitman, 1973; Granot and Huberman, 1981; Lorenzo and
Lorenzo-Freire, 2009). This problem exists in many real-world applications
such as electricity networks and communication networks, and many solutions
have been proposed to satisfy different properties (Bergantiños and Vidal-
Puga, 2007a; Hougaard et al., 2010; Trudeau, 2012; Freeman et al., 2016).

In many practical scenarios, the connections are directed rather than
undirected (Feigenbaum et al., 2001; PENNA and VENTRE, 2004). Meanwhile, there
exist two natural strategic behaviors. First, to connect to the source, an
agent may need to go through some intermediate agents. These agents will
strategically block the connection if their cost share is reduced by doing so,
which will potentially increase the total cost of connectivity. Second,
building the connections between agents needs cost. Assume that multiple
contractors compete to build the connections, and among them, only one
contractor is selected as the builder. The costs are private information of
contractors and need to be reported by them. However, they may misreport the
costs for their interests.

As an example, consider a water supply network. The source supplies water to
villages at different positions possibly through other villages. The
transmission of water from the source to a village or from one village to
another needs a cost. Each cost is reported by multiple contractors. All the
villages need to share the total cost of transmissions. To reduce the cost
share, a village may block the transmissions from itself to other villages,
which will potentially increase the total cost of transmissions. In addition,
a contractor may misreport transmission costs to increase its utility.

As another example, consider a multicast transmission network where the source
is the owner of some data and each agent is a receiver of the data. The source
transmits the data to the receivers. When a receiver receives the data, it
duplicates and transmits the data to its adjacent receivers. Each cost of
transmission is reported by multiple contractors and all the receivers need to
share the total cost of the transmissions. However, a receiver may
strategically block the transmissions of the data to reduce its cost share.
Additionally, a contractor may misreport transmission costs to increase its
utility.

On general networks, to minimize the total cost of connectivity, we design a
cost sharing mechanism that can prevent the above two strategic behaviors. One
challenge is how to deal with the conflict between the effort of mechanism
designer to use all the connections to minimize the total cost and the
motivation of agents to block the connections to reduce their cost share. This
conflict is essentially the one between the system’s optimality and the
individuals’ self-interests. Another challenge comes from the interaction
between the behaviors of agents and contractors. Specifically, the decisions
of agents to block connections affect the structure of the network, which
further affect the reports of contractors. Conversely, the reports of
contractors affect the decisions of agents to block connections.

To meet these challenges, we use a method inspired by the second price auction
(Vickrey, 1961; Groves, 1973) to select a contractor. Then according to the
report of the selected contractor, we compute each agent’s cost share based on
its shortest path from the source to it.

_Our contribution:_ We first model a typical scenario in real applications
involving both agents and contractors that have strategic behaviors
respectively. We then show that the cost sharing benchmark mechanisms based on
the well-known Shapley value (Shapley, 1953) and Bird rule (Bird, 1976) cannot
satisfy truthfulness (i.e. each agent is incentivized to offer all its
connections and each contractor is incentivized to truthfully report the costs
of connections). Next, we design a novel truthful cost sharing mechanism.
Finally, we show that the proposed mechanism also satisfies other desirable
properties studied in the literature (Gómez-Rúa and Vidal-Puga, 2017; Norde,
2019; Todo and Yokoo, 2020), i.e. budget balance, positiveness, individual
rationality, ranking and symmetry.

##  2\. Related Work

There exists a rich literature on the cost sharing problem and they all
modeled the problem as an undirected graph. We survey them from the following
perspectives.

Some studies treated the problem from the perspective of non-cooperative game.
Bergantiños and Lorenzo (Bergantiños and Lorenzo, 2004) studied the Nash
equilibrium of the problem. Tijs and Driessen (Tijs and Driessen, 1986)
proposed the cost gap allocation (CGA) method based on marginal contributions
of agents, but it only applies to complete graphs. Bird (Bird, 1976), Dutta
and Kar (Dutta and Kar, 2004), Norde et al. (Norde et al., 2004), Tijs et al.
(Tijs et al., 2006) and Hougaard et al. (Hougaard et al., 2010) provided cost
sharing methods based on the minimum spanning tree (MST) (Prim, 1957) of a
graph. Recently, Zhang et al. (Zhang et al., 2023) considered a cost sharing
mechanism design problem similar to ours. However, they assumed that the
connection costs are public information. In contrast, we consider a more
realistic scenario where the costs of connections are private information and
need to be reported by multiple contractors. Therefore, our definition of
truthfulness differs from theirs and their solutions cannot solve our problem.

Other studies treated the problem from the perspective of cooperative game.
They are all based on the Shapley value and differ in the definition of the
value of each coalition. Kar (Kar, 2002) proposed the Kar solution and defined
the value of a coalition as the minimal cost of connecting all agents of
coalition to the source without going through the agents outside of coalition.
Bergantiños and Vidal-Puga (Bergantiños and Vidal-Puga, 2007a) proposed the
folk solution. They first computed the irreducible cost matrix, and then based
on it, they defined the value of a coalition in the same way as the Kar
solution. However, the folk solution throws away much information of the
original graph. To look for a way to obtain a solution without throwing away
as much information as the folk solution, Trudeau (Trudeau, 2012) proposed the
cycle-complete solution. They made a less extreme transformation of the cost
matrix. Bergantiños and Vidal-Puga (Bergantiños and Vidal-Puga, 2007b)
proposed the optimistic game-based solution, where the value of a coalition is
defined as the minimal cost of connecting all agents of coalition to the
source given that agents outside of coalition are already connected to the
source.

The work mentioned above did not consider the situation in which agents
strategically block their connections to reduce their cost share and
contractors misreport the costs of connections to increase their utilities.
Hence, these solutions are insufficient for solving our problem.

##  3\. The Model

We formulate the cost sharing scenario discussed in Section 1 using a set of
weighted Directed Acyclic Graphs (DAGs) denoted as
$\\{G_{k}|G_{k}=(V\cup\\{s\\},E,W_{k})\\}$, where $s$ is the source to which
all the other nodes want to connect, $V$ is the set of connected nodes
representing agents and $k\in N=\\{1,\cdots,n\\}$ is a contractor. The
directed edge $(i,j)\in E$ represents the connection from $i$ to $j$ and $i$
is called $j$’s parent. The weight $c_{(i,j)}^{k}\in W_{k}$ represents the
cost of the edge $(i,j)\in E$ incurred by a contractor $k\in N$. A node $i\in
V$ connects to the source if there exists a directed path from the source to
$i$. The total cost of the connectivity has to be shared among all connected
nodes except for $s$.

Given a set of weighted DAGs, the questions here are how to select a
contractor to be the winner, how to determine the payment of the winner of
contractors and how to allocate this payment among the nodes. Two strategic
behaviors considered are that each node except for the source blocks
connections by cutting its outgoing edges and that each contractor misreports
the weight of each edge. A directed edge $(i,j)$ cannot be used for
connectivity if $i$ cuts it. Our goal is to design a cost sharing mechanism to
incentivize contractors to truthfully report all the weights, and to
incentivize nodes to offer all their outgoing edges so that we can use all the
edges to minimize the total cost of the connectivity.

The set of $i$’s outgoing edges is called $i$’s _t_ ype, denoted by $r_{i}$
$(i\in V\cup\\{s\\})$. The vector of all weights of the contractor $k\in N$ is
called $k$’s _t_ ype, denoted by $c_{k}=(c_{(i,j)}^{k})_{(i,j)\in E}$. The
vector of all nodes’ types and all contractors’ types is called type profile,
denoted by $\theta=(r_{1},\cdots,r_{|V|+1},c_{1},\cdots,c_{n})$. The set of
all type profiles is called type profile space, denoted by $\Theta$.

We design a cost sharing mechanism that asks each node and each contractor to
report their types. Let $r_{i}^{\prime}\subseteq r_{i}$ be the _r_ eport of
the node $i$ and $c_{k}^{\prime}\in\mathbb{R}^{|\bigcup_{i}r_{i}^{\prime}|}$
be the _r_ eport of the contractor $k$, and let
$\theta^{\prime}=(r_{1}^{\prime},\cdots,r_{|V|+1}^{\prime},c_{1}^{\prime},\cdots,c_{n}^{\prime})$
be the report profile of all nodes and contractors. Finally, given $k\in N$,
the DAG induced by $c_{k}^{\prime}$ and by
$(r_{1}^{\prime},\cdots,r_{|V|+1}^{\prime})$ is denoted by
$G_{k}^{\prime}=(V\cup\\{s\\},E^{\prime},W_{k}^{\prime})$, where
$E^{\prime}=\bigcup_{i}r_{i}^{\prime}\subseteq E$ and $W_{k}^{\prime}$ is the
set of reported weights of contractor $k$.

###### Definition 3.1.

A cost sharing mechanism consists of a contractor selection policy
$h:\Theta\rightarrow N$, a payment policy of contractors
$p:\Theta\rightarrow\mathbb{R}^{n}$, an edge selection policy
$f:\Theta\rightarrow 2^{E}$ and a cost sharing policy
$x:\Theta\rightarrow\mathbb{R}^{|V|}$. Given a report profile
$\theta^{\prime}\in\Theta$, $h(\theta^{\prime})\in N$ selects a contractor to
be the winner, $p(\theta^{\prime})=(p_{i}(\theta^{\prime}))_{i\in N}$ where
$p_{i}(\theta^{\prime})\leq 0$ means that the mechanism pays
$|p_{i}(\theta^{\prime})|$ to the contractor $i$ ($|p_{i}(\theta^{\prime})|=0$
if $i\neq h(\theta^{\prime})$), $f(\theta^{\prime})\subseteq E$ is the set of
the edges connecting the nodes in $V$, and
$x(\theta^{\prime})=(x_{i}(\theta^{\prime}))_{i\in V}$ determines the cost
share $x_{i}(\theta^{\prime})$ of each $i$.

For simplicity, we use $(h,p,f,x)$ to denote a cost sharing mechanism. Given a
report profile $\theta^{\prime}\in\Theta$, the utility of a contractor $k\in
N$ under $(h,p,f,x)$ is defined as

$u_{k}(\theta^{\prime})=\begin{cases}|p_{k}(\theta^{\prime})|-\sum_{(i,j)\in
f(\theta^{\prime})}{c}_{(i,j)}^{k}&\text{$k=h(\theta^{\prime})$,}\\\
0&\text{$k\neq h(\theta^{\prime})$,}\end{cases}$

where ${c}_{(i,j)}^{k}$ is the weight of the edge $(i,j)$ incurred by $k$ and
$p_{k}(\theta^{\prime})$ is the payment of $k$ under $\theta^{\prime}$.

In the following, we introduce the desirable properties of a cost sharing
mechanism.

Truthfulness states that each node is incentivized to offer all its outgoing
edges and that each contractor is incentivized to truthfully report the
weights of all edges. Note that the source does not behave strategically in
this setting.

###### Definition 3.2.

A cost sharing mechanism $(h,p,f,x)$ satisfies truthfulness if

$x_{i}(r_{i},\theta_{-i}^{\prime})\leq
x_{i}(r_{i}^{\prime},\theta_{-i}^{\prime})$

and

$u_{j}(c_{j},\theta_{-j}^{\prime})\geq
u_{j}(c_{j}^{\prime},\theta_{-j}^{\prime}),$

for all $i\in V$ and for all $j\in N$, where

$\theta_{-i}^{\prime}=(r_{1}^{\prime},\cdots,r_{i-1}^{\prime},r_{i+1}^{\prime}.\cdots,r_{|V|+1}^{\prime},c_{1}^{\prime},\cdots,c_{n}^{\prime})$

and

$\theta_{-j}^{\prime}=(r_{1}^{\prime},\cdots,r_{|V|+1}^{\prime},c_{1}^{\prime},\cdots,c_{j-1}^{\prime},c_{j+1}^{\prime},\cdots,c_{n}^{\prime}).$

Another property is individual rationality, which means that the utility of
each contractor is always non-negative.

###### Definition 3.3.

A cost sharing mechanism $(h,p,f,x)$ satisfies individual rationality (IR) if
$u_{i}(\theta^{\prime})\geq 0$ for all $i\in N$ and for all
$\theta^{\prime}\in\Theta$.

We also require that the sum of all nodes’ cost share equals the total amount
paid to the contractors for all report profiles. That is, the mechanism has no
profit or loss.

###### Definition 3.4.

A cost sharing mechanism $(h,p,f,x)$ satisfies budget balance (BB) if
$\sum_{i\in V}x_{i}(\theta^{\prime})=\sum_{i\in N}|p_{i}(\theta^{\prime})|$
for all $\theta^{\prime}\in\Theta$.

The ranking property requires that for any nodes $i$ and $j$ that have the
same parents, if the cost of the edge $(k,i)$ is less expensive than the edge
$(k,j)$ for any parent $k$, then $i$ pays less than $j$.

###### Definition 3.5.

A cost sharing mechanism $(h,p,f,x)$ satisfies ranking if for all
$\theta^{\prime}\in\Theta$, for all $m\in N$, and for all $i,j\in V$ with
$a_{i}(\theta^{\prime})\backslash\\{j\\}=a_{j}(\theta^{\prime})\backslash\\{i\\}$
where $a_{i}(\theta^{\prime})$ and $a_{j}(\theta^{\prime})$ are respectively
the sets of parents of $i$ and $j$, it holds that
$c_{(k,i)}^{m}<c_{(k,j)}^{m}$ implies
$x_{i}(\theta^{\prime})<x_{j}(\theta^{\prime})$ for all $k\in
a_{i}(\theta^{\prime})\backslash\\{j\\}$.

Positiveness states that each node’s cost share should be non-negative.

###### Definition 3.6.

A cost sharing mechanism $(h,p,f,x)$ satisfies positiveness if
$x_{i}(\theta^{\prime})\geq 0$ for all $i\in V$ and for all
$\theta^{\prime}\in\Theta$.

Finally, we introduce the definition of symmetry which says nodes that play
the same role pay the same amount.

###### Definition 3.7.

A cost sharing mechanism $(h,p,f,x)$ satisfies symmetry if for all
$\theta^{\prime}\in\Theta$, for all $m\in N$, and for all $i,j\in V$ with
$a_{i}(\theta^{\prime})\backslash\\{j\\}=a_{j}(\theta^{\prime})\backslash\\{i\\}$
where $a_{i}(\theta^{\prime})$ and $a_{j}(\theta^{\prime})$ are respectively
the sets of parents of $i$ and $j$, it holds that
$c_{(k,i)}^{m}=c_{(k,j)}^{m}$ implies
$x_{i}(\theta^{\prime})=x_{j}(\theta^{\prime})$ for all $k\in
a_{i}(\theta^{\prime})\backslash\\{j\\}$.

In Section 5, we design a cost sharing mechanism to satisfy the above
properties.

##  4\. The Benchmark Mechanisms Based on Shapley Value and Bird Rule on DAGs

Our goal is to design a cost sharing mechanism to satisfy truthfulness, budget
balance and other properties. To guarantee that contractors truthfully report
their types, we select a contractor that corresponds to a minimum spanning
tree having the minimal cost, and pay it the second minimal cost.

If we allocate the payment using the DAG with the second minimum cost, nodes
have the opportunity to reduce their cost share by strategically cutting their
outgoing edges. Therefore, to guarantee that nodes truthfully report their
types, we must proportionally allocate the payment using another DAG. The
crucial challenge lies in determining the proportion of each node.

The Shapley value is a unique solution enabling the total cost to be shared
completely and enabling each node’s cost share to depend only on its marginal
contribution (Shapley, 1953). Since a node’s decision to cut its outgoing
edges affects its marginal contribution, we use Shapley value to compute each
node’s proportion and check whether the Shapley value based mechanism
satisfies truthfulness. Another widely used method to compute each node’s cost
share is the Bird rule, where each node’s cost share equals the cost of its
incident edge on the MST (Bird, 1976). Since a node’s decision to cut its
outgoing edges affects its cost share under the Bird rule, we also use the
Bird rule to compute each node’s proportion and check whether the Bird rule
based mechanism satisfies truthfulness.

###  4.1. The Shapley Value Based Mechanism

The key ideas of the mechanism are as follows. Given a report profile, when
the contractor is selected and its payment is determined, we use Shapley value
to compute each node’s proportion. Specifically, we first compute the minimum
cost of connecting any subset of nodes to the source. Then we get the marginal
cost of adding each node to a subset of other nodes. Furthermore, we get the
average marginal cost (Shapley value) of each node. Finally, each node’s
proportion equals the ratio of its Shapley value to the sum of all nodes’
Shapley values.

We introduce additional notations as follows. Let $j^{*}$ be the selected
contractor, and let $c^{mst}_{j^{*}}$ denote the cost of $j^{*}$’s MST, i.e.

$c^{mst}_{j^{*}}=min_{j\in N}c^{mst}_{j}.$

Let $k^{*}$ be the contractor the cost of whose MST is the second minimum, and
let the cost of its MST be denoted by

$c^{mst}_{k^{*}}=min_{j\neq j^{*},j\in N}c^{mst}_{j}.$

The mechanism is formally described in Algorithm 1. Line 1 to line 9 select
the winner of contractors and determine the payments of all the contractors.
Line 10 determines the set of selected edges. Line 11 to line 17 compute each
node’s proportion and its cost share.

Algorithm 1 The Shapley Value Based Mechanism

Input: A report profile $\theta^{\prime}\in\Theta$

Output: The winner $h(\theta^{\prime})$, the payments $p(\theta^{\prime})$,

the edges $f(\theta^{\prime})$, the cost shares $x(\theta^{\prime})$

1: for each contractor $j\in N$ do

2: Compute the MST of $G_{j}^{\prime}$ using Prim’s algorithm (Prim, 1957) and
compute its cost $c_{j}^{mst}$;

3: end for

4: Set $j^{*}=argmin_{j\in N}c_{j}^{mst}$;

5: Set $k^{*}=argmin_{j\neq j^{*},j\in N}c_{j}^{mst}$;

6: Set $h(\theta^{\prime})=j^{*}$ and
$p_{j^{*}}(\theta^{\prime})=-c_{k^{*}}^{mst}$;

7: for each contractor $j\in N\backslash\\{h(\theta^{\prime})\\}$ do

8: Set $p_{j}(\theta^{\prime})=0$;

9: end for

10: Set $f(\theta^{\prime})$ to be the set of all edges of the MST of
$G_{j^{*}}^{\prime}$;

11: for each subset $S\subseteq V$ do

12: Compute $v(S)$, which is the minimum cost to connect $S$ to $s$;

13: end for

14: for each $i\in V$ do

15: Compute the Shapley value of $i$, i.e.  (1) $\phi_{i}=\sum_{S\subseteq
V\backslash\\{i\\}}\frac{|S|!(|V|-|S|-1)!}{|V|!}\cdot(v(S\cup\\{i\\})-v(S));$

16: Set $x_{i}(\theta^{\prime})=\frac{\phi_{i}}{c_{j^{*}}^{mst}}\cdot
c_{k^{*}}^{mst}$;

17: end for

18: return $h(\theta^{\prime})$, $p(\theta^{\prime})$, $f(\theta^{\prime})$,
$x(\theta^{\prime})$

Next, we show the properties of Shapley value based mechanism.

###### Theorem 4.1.

The Shapley value based mechanism does not satisfy truthfulness.

Figure 1. The $s$ represents the source, $A,B,C$ represent the nodes, and the
numbers on the edges represent the costs of connections. Figure 2. The $s$
represents the source, $A,C$ represent the nodes, and the numbers on the edges
represent the costs of connections.

###### Proof.

Since truthfulness is defined for any set of DAGs, it suffices to give a
specific set of DAGs where exists a node that is not willing to offer all its
outgoing edges. Consider the two DAGs shown in Figure 1, where the weights are
reported by the contractors $a$ and $b$. The costs of minimum spanning trees
of $a$ and $b$ are 7 and 700 respectively. So the winner is $a$ and the
mechanism pays $a$ 700\. Next, we compute the node $A$’s cost share using the
left DAG in Figure 1. First, the coalition values of all subsets of nodes are
as follows:

$\begin{split}v(\\{B\\})&=5,v(\\{A,B\\})=5,\\\
v(\\{A\\})&=3,v(\\{A,C\\})=7,v(\emptyset)=0,\\\
v(\\{C\\})&=7,v(\\{B,C\\})=7,v(\\{A,B,C\\})=7.\\\ \end{split}$

Second, according to Equation (1), the Shapley values of $A,B$ and $C$ are
$1,2$ and $4$ respectively. Finally, the cost share of $A$ is
$\frac{1}{7}\cdot 700=100$.

If the node $A$ cuts the edge $(A,B)$, then $B$ cannot join in the cost
sharing since there does not exist a directed path from the source to $B$. The
corresponding DAGs are illustrated in Figure 2. The costs of minimum spanning
trees of $a$ and $b$ are 103 and 800 respectively. Thus, the winner is still
$a$ and the mechanism pays $a$ 800\. Next, we compute the node $A$’s cost
share using the left DAG in Figure 2. The coalition values of all subsets of
nodes are as follows:

$\begin{split}v(\\{C\\})&=103,v(\emptyset)=0,\\\
v(\\{A\\})&=3,v(\\{A,C\\})=103.\\\ \end{split}$

By Equation (1), the Shapley values of $A$ and $C$ are $\frac{3}{2}$ and
$\frac{203}{2}$ respectively. Finally, the cost share of $A$ is

$\frac{1.5}{103}\cdot 800<100.$

So the node $A$ is not willing to offer all its outgoing edges, i.e. the
mechanism does not satisfy truthfulness. ∎

###### Theorem 4.2.

The Shapley value based mechanism satisfies budget balance.

###### Proof.

From Algorithm 1, the cost share of each node equals the product of its
proportion multiplied by the cost of the second minimum spanning tree where
the proportion is the ratio of its Shapley value to the sum of all nodes’
Shapley values. Therefore, the sum of all nodes’ cost share equals the cost of
the second minimum spanning tree. Since the mechanism pays the winner of
contractors the cost of the second minimum spanning tree, the mechanism has no
profit or loss. Hence, the mechanism satisfies budget balance. ∎

###### Theorem 4.3.

The Shapley value based mechanism satisfies positiveness.

###### Proof.

For each node $i\in V$, by Algorithm 1 and the definition of value function,
we get that $v(S\cup\\{i\\})-v(S)\geq 0$, $\forall S\subseteq V$. Therefore,
each node’s Shapley value is non-negative. Thus, the proportion of $i$ is non-
negative. Since the cost of second minimum spanning tree is positive, each
node’s cost share is non-negative. ∎

###### Theorem 4.4.

The Shapley value based mechanism satisfies individual rationality.

###### Proof.

From Algorithm 1, if a contractor is not the winner, then its utility is 0. If
a contractor is the winner, then the cost of its minimum spanning tree is
minimized. Since the mechanism pays the winner the cost of second minimum
spanning tree, its utility (the difference between the second minimum of costs
of MSTs and the minimum of costs of MSTs) is non-negative. Therefore, each
contractor’s utility is non-negative, i.e. the mechanism satisfies individual
rationality. ∎

###  4.2. The Bird Rule Based Mechanism

In Section 4.1, we show that the Shapley value based mechanism does not
satisfy truthfulness. In this subsection, we check whether the mechanism based
on the Bird rule (Bird, 1976) satisfies truthfulness.

The difference between the Bird rule based mechanism and Shapley value based
mechanism only lies in the method of computing the proportion of each node.
Under the Bird rule based mechanism, we first compute the MST of a DAG by
Prim’s algorithm. Second, we set the proportion of each node equal to the
ratio of the cost of its incident edge on the MST to the cost of the MST.

We restate the following notations. Let $j^{*}$ be the selected contractor,
and let $c^{mst}_{j^{*}}$ denote the cost of $j^{*}$’s MST, i.e.

$c^{mst}_{j^{*}}=min_{j\in N}c^{mst}_{j}.$

Let $k^{*}$ be the contractor the cost of whose MST is the second minimum, and
let the cost of its MST be denoted by

$c^{mst}_{k^{*}}=min_{j\neq j^{*},j\in N}c^{mst}_{j}.$

The mechanism is formally described in Algorithm 2. Line 1 to line 9 compute
the winner of contractors and all the contractors’ payments. Line 10
determines the set of selected edges. Line 11 to line 13 compute each node’s
cost share.

Algorithm 2 The Bird Rule Based Mechanism

Input: A report profile $\theta^{\prime}\in\Theta$

Output: The winner $h(\theta^{\prime})$, the payments $p(\theta^{\prime})$,

the edges $f(\theta^{\prime})$, the cost shares $x(\theta^{\prime})$

1: for each contractor $j\in N$ do

2: Compute the MST of $G_{j}^{\prime}$ using Prim’s algorithm and compute its
cost $c_{j}^{mst}$;

3: end for

4: Set $j^{*}=argmin_{j\in N}c_{j}^{mst}$;

5: Set $k^{*}=argmin_{j\neq j^{*},j\in N}c_{j}^{mst}$;

6: Set $h(\theta^{\prime})=j^{*}$ and
$p_{j^{*}}(\theta^{\prime})=-c_{k^{*}}^{mst}$;

7: for each contractor $j\in N\backslash\\{h(\theta^{\prime})\\}$ do

8: Set $p_{j}(\theta^{\prime})=0$;

9: end for

10: Set $f(\theta^{\prime})$ to be the set of all edges of the MST of
$G_{j^{*}}^{\prime}$;

11: for each $i\in V$ do

12: Set $x_{i}(\theta^{\prime})=\frac{k_{i}}{c_{j^{*}}^{mst}}\cdot
c_{k^{*}}^{mst}$, where $k_{i}$ is the cost of $i$’s incident edge on the MST
of $G_{j^{*}}^{\prime}$;

13: end for

14: return $h(\theta^{\prime})$, $p(\theta^{\prime})$, $f(\theta^{\prime})$,
$x(\theta^{\prime})$

Next, we show the properties of Bird rule based mechanism.

###### Theorem 4.5.

The Bird rule based mechanism does not satisfy truthfulness.

Figure 3. The $s$ represents the source, $A,B,C$ represent the nodes, and the
numbers on the edges represent the costs of connections. Figure 4. The $s$
represents the source, $A,B,C$ represent the nodes, and the numbers on the
edges represent the costs of connections.

###### Proof.

Since truthfulness is defined for any set of DAGs, it suffices to give a
specific set of DAGs where exists a node that is not willing to offer all its
outgoing edges. Consider the two DAGs shown in Figure 3, where the weights are
reported by the contractors $a$ and $b$. The costs of minimum spanning trees
of $a$ and $b$ are 7 and 35 respectively. So the winner is $a$ and the
mechanism pays $a$ 35\. Next, we compute the node $C$’s cost share on the left
DAG in Figure 3. The cost of its incident edge on the MST of the left DAG is
4. Thus the cost share of $C$ is $\frac{4}{7}\cdot 35$.

If the node $C$ cuts the edge $(C,B)$, the corresponding DAGs are illustrated
in Figure 4. The costs of minimum spanning trees of $a$ and $b$ are 14 and 35
respectively. So the winner is still $a$ and the mechanism pays $a$ 35\. Next,
we compute the node $C$’s cost share on the left DAG in Figure 4. The cost of
its incident edge on the MST of the left DAG is still 4. Thus the cost share
of $C$ is

$\frac{4}{14}\cdot 35<\frac{4}{7}\cdot 35.$

So the node $C$ is not willing to offer all its outgoing edges, i.e. the
mechanism does not satisfy truthfulness. ∎

###### Theorem 4.6.

The Bird rule based mechanism satisfies budget balance.

###### Proof.

From Algorithm 2, the cost share of each node equals the product of its
proportion multiplied by the cost of the second minimum spanning tree. The
proportion is the ratio of the cost of its incident edge on the MST to the
cost of MST. Therefore, the sum of all nodes’ cost share equals the cost of
the second minimum spanning tree. Since the mechanism pays the winner of
contractors the cost of the second minimum spanning tree, the mechanism has no
profit or loss. Hence, the mechanism satisfies budget balance. ∎

###### Theorem 4.7.

The Bird rule based mechanism satisfies positiveness.

###### Proof.

The cost of each node’s incident edge on the MST is non-negative. Then the
proportion of each node is non-negative. Since the cost of second minimum
spanning tree is positive, each node’s cost share is non-negative. That is,
the mechanism satisfies positiveness. ∎

###### Theorem 4.8.

The Bird rule based mechanism satisfies individual rationality.

###### Proof.

From Algorithm 2, if a contractor is not the winner, then its utility is 0. If
a contractor is the winner, then the cost of its minimum spanning tree is
minimized. Since the mechanism pays the winner the cost of second minimum
spanning tree, its utility (the difference between the second minimum of costs
of MSTs and the minimum of costs of MSTs) is non-negative. Therefore, each
contractor’s utility is non-negative, i.e. the mechanism satisfies individual
rationality. ∎

In summary, although both the Shapley value based mechanism and Bird rule
based mechanism satisfy budget balance, positiveness and individual
rationality, they do not satisfy truthfulness. Therefore, in the next section,
we propose a novel cost sharing mechanism that satisfies truthfulness and
other properties.

##  5\. The Shortest Path Based Mechanism

The reason why the mechanisms based on Shapley value and Bird rule do not
satisfy truthfulness is that nodes can cut their outgoing edges to reduce
their proportions and thus their cost share decreases. Therefore, to satisfy
truthfulness, we need to guarantee that cutting outgoing edges does not
decrease each node’s proportion.

In this section, we propose a novel cost sharing mechanism based on the
shortest path that satisfies truthfulness. In addition, we show that it also
satisfies budget balance, positiveness, individual rationality, ranking and
symmetry.

The key ideas of the proposed mechanism are as follows. To incentivize the
contractors to truthfully report their types, the mechanism selects a
contractor to be the winner whose minimum spanning tree has the minimum cost
among minimum spanning trees of all DAGs. The winner’s payment is defined as
the negative second minimum cost. To incentivize the nodes to truthfully
report their types, we first select the DAG with the minimum cost of minimum
spanning tree to compute each node’s proportion. Second, we use the Breadth-
First-Search (BFS) algorithm (Silvela and Portillo, 2001) to compute each
node’s depth and sort all nodes by their depths in descending order (with
random tie-breaking). Third, following the above order, we compute the
shortest path from the source to each node. Fourth, we update the costs on
this shortest path to zero. Fifth, we compute each node’s proportion, which is
defined as the ratio of the cost of its shortest path to the sum of costs of
all nodes’ shortest paths. Finally, we select the edges with zero cost.

###### Definition 5.1.

The length of a directed path is the number of edges on it. For each node
$i\in V$, its depth is defined as the length of the shortest directed path
from the source to it.

Now we introduce additional notations. For each node $i$, let $S_{i}$ denote
the set consisting of the source $s$, the nodes with the depths larger than
$i$ and the nodes on their shortest paths. Let $d(i,S_{i})$ be the minimum of
costs from each node in $S_{i}$ to $i$, $E(i,S_{i})$ be the set of all edges
of the directed path corresponding to $d(i,S_{i})$, and $V(i,S_{i})$ be the
set of all nodes of the directed path corresponding to $d(i,S_{i})$. Let
$j^{*}$ be the selected contractor, $c^{mst}_{j^{*}}$ be the cost of $j^{*}$’s
MST, $k^{*}$ be the contractor the cost of whose MST is the second minimum,
and $c^{mst}_{k^{*}}$ be the cost of $k^{*}$’s MST.

The proposed mechanism is formally described in Algorithm 3. Line 1 to line 10
determine the winner of contractors and the payments of all contractors. Line
11 to line 21 compute each node’s proportion and its cost share. Line 22
defines the set of selected edges.

A running example is given in Example 5.2.

Algorithm 3 The Shortest Path Based Mechanism

Input: A report profile $\theta^{\prime}\in\Theta$

Output: The winner $h(\theta^{\prime})$, the payments $p(\theta^{\prime})$,

the edges $f(\theta^{\prime})$, the cost shares $x(\theta^{\prime})$

1: Initialize $A=\emptyset$ and $B=0$;

2: for each contractor $j\in N$ do

3: Compute the MST of $G_{j}^{\prime}$ using Prim’s algorithm and compute its
cost $c_{j}^{mst}$;

4: end for

5: Set $j^{*}=argmin_{j\in N}c_{j}^{mst}$;

6: Set $k^{*}=argmin_{j\neq j^{*},j\in N}c_{j}^{mst}$;

7: Set $h(\theta^{\prime})=j^{*}$ and
$p_{j^{*}}(\theta^{\prime})=-c_{k^{*}}^{mst}$;

8: for each contractor $j\in N\backslash\\{h(\theta^{\prime})\\}$ do

9: Set $p_{j}(\theta^{\prime})=0$;

10: end for

11: Sort nodes in descending order by their depths on $G_{j^{*}}^{\prime}$
(assuming the sequence is $1,\cdots,|V|$);

12: Set $S_{1}=\emptyset$;

13: for each node $i=1,\cdots,|V|$ do

14: Compute $d(i,S_{i})$, $E(i,S_{i})$ and $V(i,S_{i})$;

15: Set $S_{i+1}=S_{i}\cup V(i,S_{i})$;

16: Set $A=A\cup E(i,S_{i})$;

17: Set $B=B+d(i,S_{i})$;

18: end for

19: for each node $i=1,\cdots,|V|$ do

20: Set $x_{i}(\theta^{\prime})=\frac{d(i,S_{i})}{B}\cdot c_{k^{*}}^{mst}$;

21: end for

22: Set $f(\theta^{\prime})=A$;

23: return $h(\theta^{\prime})$, $p(\theta^{\prime})$, $f(\theta^{\prime})$,
$x(\theta^{\prime})$

Figure 5. The $s$ represents the source, the letters in circles represent the
nodes, and the numbers on the edges represent the costs of connections. Figure
6. The process of updating the costs of edges

###### Example 5.2.

The DAGs generated by a report profile $\theta^{\prime}\in\Theta$ are
illustrated in Figure 5, where $N=\\{a,b\\}$ and $V=\\{A,B,C,D,E,F,G\\}$.
According to each contractor’s report, we obtain that the costs of minimum
spanning trees of $a$ and $b$ are 40 and 44 respectively. Therefore, we have
$h(\theta^{\prime})=a$, $p_{a}(\theta^{\prime})=-44$ and
$p_{b}(\theta^{\prime})=0$. Next, we compute the cost shares of all nodes on
the left DAG in Figure 5. The nodes are ordered by their depths:
$G,D,F,E,C,B,A$. For node $G$, we get $S_{G}=\\{s\\}$. The shortest directed
path from the nodes in $S_{G}$ to $G$ is $s\rightarrow C\rightarrow G$. Thus
we have $d(G,S_{G})=2+12=14$. We set the costs of the edges $(s,C)$ and
$(C,G)$ to zero. For node $D$, we get $S_{D}=\\{s,C,G\\}$. The shortest
directed path from the nodes in $S_{D}$ to $D$ is $C\rightarrow D$. So we have
$d(D,S_{D})=10$. The cost of the edge $(C,D)$ is set to zero. Similarly, we
obtain

$\begin{split}d(F,S_{F})&=7,d(E,S_{E})=6,\\\
d(C,S_{C})&=0,d(B,S_{B})=3,d(A,S_{A})=1.\\\ \end{split}$

So, by the equation in Algorithm 3

$x_{i}(\theta^{\prime})=\frac{d(i,S_{i})}{B}\cdot c_{k^{*}}^{mst},$

we obtain that the cost shares of nodes $G,D,F,E,C,B,A$ are respectively

$\begin{split}x_{G}(\theta^{\prime})&=\frac{14}{41}\cdot
44,x_{D}(\theta^{\prime})=\frac{10}{41}\cdot
44,x_{F}(\theta^{\prime})=\frac{7}{41}\cdot 44,\\\
x_{E}(\theta^{\prime})&=\frac{6}{41}\cdot
44,x_{C}(\theta^{\prime})=0,x_{B}(\theta^{\prime})=\frac{3}{41}\cdot
44,x_{A}(\theta^{\prime})=\frac{1}{41}\cdot 44.\\\ \end{split}$

Finally, we get the set of selected edges

$f(\theta^{\prime})=\\{(s,C),(s,B),(s,A),(C,D),(C,G),(C,F),(F,E)\\}.$

The process of updating the costs of edges is illustrated in Figure 6
((1)-(6)).

###  5.1. Properties of the Shortest Path Based Mechanism

In the following, we show the nice properties of the proposed mechanism.

###### Theorem 5.3.

The shortest path based mechanism satisfies truthfulness.

###### Proof.

First, we prove that each contractor $i\in N$ will report all the weights
truthfully. To prove this, we only need to show that when $i$ truthfully
reports the weights, its utility is larger than or equal to the utility when
it misreports the weights.

When $i$ truthfully reports its weights, there are two cases.

  * •

$i=h(\theta^{\prime})$. According to our mechanism, $i$’s utility is the
difference between the second minimum of costs of MSTs and the minimum of
costs of MSTs, which is non-negative.

If $i$ reports larger weights, there are two possibilities.

    * –

$i\neq h(\theta^{\prime})$. Then $i$’s utility is 0.

    * –

$i=h(\theta^{\prime})$. Then the second minimum of costs of MSTs does not
change and so does $i$’s utility.

If $i$ reports lower weights, then it is still the winner and its utility does
not change.

  * •

$i\neq h(\theta^{\prime})$. Then its utility is 0.

If $i$ reports larger weights, then it is still not the winner and its utility
does not change.

If $i$ reports lower weights, there are two possibilities.

    * –

$i\neq h(\theta^{\prime})$. Then its utility is still 0.

    * –

$i=h(\theta^{\prime})$. Then its utility is negative.

So truthful report maximizes its utility.

Second, we prove that each node $i\in V$ will offer all its outgoing edges.

When $i$ offers all its outgoing edges, its cost share is

$\frac{d(i,S_{i})}{\sum_{i\in V}d(i,S_{i})}\cdot c_{k^{*}}^{mst}.$

If node $i$ does not offer all its outgoing edges, there are two
possibilities.

  * •

If there exists a node for which $i$ is on the directed path from the source
to that node, then the cost share of $i$ is 0. Thus, the cost share of $i$
will weakly increase.

  * •

Otherwise, we have that $d(j,S_{j})(j\neq i)$ remains unchanged. By the
definition of $d(i,S_{i})$, it also does not change. So $i$’s proportion

$\frac{d(i,S_{i})}{\sum_{i\in V}d(i,S_{i})}$

does not change. In addition, $c_{k^{*}}^{mst}$ will weakly increase. Hence,
the cost share of $i$ will weakly increase.

So truthful report minimizes its cost share.

Putting the above analysis together, the proposed mechanism satisfies
truthfulness. ∎

###### Theorem 5.4.

The shortest path based mechanism satisfies budget balance.

###### Proof.

We need to prove that given $\theta^{\prime}\in\Theta$, the sum of all nodes’
cost share equals the second minimum of costs of minimum spanning trees, i.e.

$\sum_{i\in V}x_{i}(\theta^{\prime})=c_{k^{*}}^{mst}.$

According to line 17 in Algorithm 3, we have

$\sum_{i\in V}d(i,S_{i})=B.$

According to line 20 in Algorithm 3, we get

$\sum_{i\in V}x_{i}(\theta^{\prime})=\frac{\sum_{i\in V}d(i,S_{i})}{B}\cdot
c_{k^{*}}^{mst}=c_{k^{*}}^{mst}.$

∎

###### Theorem 5.5.

The shortest path based mechanism satisfies individual rationality.

###### Proof.

According to the proposed mechanism, the utility of a contractor is zero if it
is not the winner. For the winner, since the mechanism pays it the second
minimum of costs of minimum spanning trees, its utility (the difference
between the second minimum of costs of MSTs and the minimum of costs of MSTs)
is non-negative. Therefore, the utility of each contractor is non-negative. ∎

###### Theorem 5.6.

The shortest path based mechanism satisfies positiveness.

###### Proof.

According to the proposed mechanism, given $\theta^{\prime}\in\Theta$, the
cost share of each $i\in V$ is computed as

$x_{i}(\theta^{\prime})=\frac{d(i,S_{i})}{\sum_{i\in V}d(i,S_{i})}\cdot
c_{k^{*}}^{mst}.$

Since both $d(i,S_{i})$ and $c_{k^{*}}^{mst}$ are non-negative, the cost share
of $i$ is also non-negative. ∎

###### Theorem 5.7.

The shortest path based mechanism satisfies ranking.

###### Proof.

We need to show that, given $\theta^{\prime}\in\Theta$, the winner of
contractors $m\in N$, and $i,j\in V$ with
$a_{i}(\theta^{\prime})\backslash\\{j\\}=a_{j}(\theta^{\prime})\backslash\\{i\\}$,
it holds that $c_{(k,i)}^{m}<c_{(k,j)}^{m}$ ($\forall k\in
a_{i}(\theta^{\prime})\backslash\\{j\\}$) implies
$x_{i}(\theta^{\prime})<x_{j}(\theta^{\prime})$.

From Algorithm 3, we know

$x_{i}(\theta^{\prime})=\frac{d(i,S_{i})}{\sum_{l\in V}d(l,S_{l})}\cdot
c_{k^{*}}^{mst}$

and

$x_{j}(\theta^{\prime})=\frac{d(j,S_{j})}{\sum_{l\in V}d(l,S_{l})}\cdot
c_{k^{*}}^{mst}.$

We only need to compare $d(i,S_{i})$ with $d(j,S_{j})$. The $d(i,S_{i})$
represents the minimum of costs from each node in $S_{i}$ to $i$ and the
$d(j,S_{j})$ represents the minimum of costs from each node in $S_{j}$ to $j$.
Due to the definition of ranking, the depth of $i$ equals the depth of $j$.
Therefore, we have $S_{i}=S_{j}$. Since $c_{(k,i)}^{m}<c_{(k,j)}^{m}$
($\forall k\in a_{i}(\theta^{\prime})\backslash\\{j\\}$), we have
$d(i,S_{i})<d(j,S_{j})$. Therefore, it holds that
$x_{i}(\theta^{\prime})<x_{j}(\theta^{\prime})$. ∎

###### Theorem 5.8.

The shortest path based mechanism satisfies symmetry.

###### Proof.

We need to show that, given $\theta^{\prime}\in\Theta$, the winner of
contractors $m\in N$, and $i,j\in V$ with
$a_{i}(\theta^{\prime})\backslash\\{j\\}=a_{j}(\theta^{\prime})\backslash\\{i\\}$,
it holds that $c_{(k,i)}^{m}=c_{(k,j)}^{m}$ ($\forall k\in
a_{i}(\theta^{\prime})\backslash\\{j\\}$) implies
$x_{i}(\theta^{\prime})=x_{j}(\theta^{\prime})$.

From Algorithm 3, we know

$x_{i}(\theta^{\prime})=\frac{d(i,S_{i})}{\sum_{l\in V}d(l,S_{l})}\cdot
c_{k^{*}}^{mst}$

and

$x_{j}(\theta^{\prime})=\frac{d(j,S_{j})}{\sum_{l\in V}d(l,S_{l})}\cdot
c_{k^{*}}^{mst}.$

The $d(i,S_{i})$ represents the minimum of costs from each node in $S_{i}$ to
$i$ and the $d(j,S_{j})$ represents the minimum of costs from each node in
$S_{j}$ to $j$. Since the depth of $i$ equals the depth of $j$, it follows
that $S_{i}=S_{j}$. Since $c_{(k,i)}^{m}=c_{(k,j)}^{m}$ ($\forall k\in
a_{i}(\theta^{\prime})\backslash\\{j\\}$), we have $d(i,S_{i})=d(j,S_{j})$.
Further, we infer that $x_{i}(\theta^{\prime})=x_{j}(\theta^{\prime})$. ∎

##  6\. Conclusions

For the first time, we study how to design a cost sharing mechanism to prevent
the agents’ strategic behaviors, i.e. the contractors’ misreporting the
weights of edges and the nodes’ cutting their outgoing edges. We model the two
strategic behaviors and define key properties that cost sharing mechanisms
satisfy. Then we show that the cost sharing benchmark mechanisms based on
Shapley value and Bird rule cannot satisfy truthfulness. Finally, we propose a
novel cost sharing mechanism based on shortest path and show it satisfies
truthfulness and other properties.

In the future, we try to establish sufficient and necessary conditions for a
cost sharing mechanism to satisfy truthfulness.

###### Acknowledgements.

This work is supported by Science and Technology Commission of Shanghai
Municipality (No. 23010503000 and No. 22ZR1442200), and Shanghai Frontiers
Science Center of Human-centered Artificial Intelligence (ShangHAI).

## References

  * (1)
  * Bergantiños and Gómez-Rúa (2010) Gustavo Bergantiños and María Gómez-Rúa. 2010\.  Minimum cost spanning tree problems with groups.  _Economic Theory_ 43, 2 (2010), 227–262.
  * Bergantiños and Lorenzo (2004) Gustavo Bergantiños and Leticia Lorenzo. 2004.  A non-cooperative approach to the cost spanning tree problem.  _Mathematical Methods of Operations Research_ 59, 3 (2004), 393–403.
  * Bergantiños and Vidal-Puga (2007a) Gustavo Bergantiños and Juan J Vidal-Puga. 2007a.  A fair rule in minimum cost spanning tree problems.  _Journal of Economic Theory_ 137, 1 (2007), 326–352.
  * Bergantiños and Vidal-Puga (2007b) Gustavo Bergantiños and Juan J Vidal-Puga. 2007b.  The optimistic TU game in minimum cost spanning tree problems.  _International Journal of Game Theory_ 36, 2 (2007), 223–239.
  * Bird (1976) Charles G Bird. 1976\.  On cost allocation for a spanning tree: a game theoretic approach.  _Networks_ 6, 4 (1976), 335–350.
  * Claus and Kleitman (1973) Armin Claus and Daniel J Kleitman. 1973.  Cost allocation for a spanning tree.  _Networks_ 3, 4 (1973), 289–304.
  * Dutta and Kar (2004) Bhaskar Dutta and Anirban Kar. 2004.  Cost monotonicity, consistency and minimum cost spanning tree games.  _Games and Economic Behavior_ 48, 2 (2004), 223–248.
  * Feigenbaum et al. (2001) Joan Feigenbaum, Christos H Papadimitriou, and Scott Shenker. 2001.  Sharing the cost of multicast transmissions.  _J. Comput. System Sci._ 63 (2001), 21–41.
  * Freeman et al. (2016) Rupert Freeman, Samuel Haney, and Debmalya Panigrahi. 2016\.  On the price of stability of undirected multicast games. In _Proceedings of the 12th International Conference on Web and Internet Economics_. 354–368.
  * Gómez-Rúa and Vidal-Puga (2011) María Gómez-Rúa and Juan Vidal-Puga. 2011.  Merge-proofness in minimum cost spanning tree problems.  _International Journal of Game Theory_ 40, 2 (2011), 309–329.
  * Gómez-Rúa and Vidal-Puga (2017) María Gómez-Rúa and Juan Vidal-Puga. 2017.  A monotonic and merge-proof rule in minimum cost spanning tree situations.  _Economic Theory_ 63, 3 (2017), 813–826.
  * Granot and Huberman (1981) Daniel Granot and Gur Huberman. 1981.  Minimum cost spanning tree games.  _Mathematical Programming_ 21, 1 (1981), 1–18.
  * Groves (1973) Theodore Groves. 1973\.  Incentives in teams.  _Econometrica: Journal of the Econometric Society_ (1973), 617–631.
  * Hougaard et al. (2010) Jens Leth Hougaard, Hervé Moulin, and Lars Peter Østerdal. 2010.  Decentralized pricing in minimum cost spanning trees.  _Economic Theory_ 44, 2 (2010), 293–306.
  * Kar (2002) Anirban Kar. 2002\.  Axiomatization of the Shapley value on minimum cost spanning tree games.  _Games and Economic Behavior_ 38, 2 (2002), 265–277.
  * Lorenzo and Lorenzo-Freire (2009) Leticia Lorenzo and Silvia Lorenzo-Freire. 2009.  A characterization of Kruskal sharing rules for minimum cost spanning tree problems.  _International Journal of Game Theory_ 38, 1 (2009), 107–126.
  * Norde (2019) Henk Norde. 2019\.  The degree and cost adjusted folk solution for minimum cost spanning tree games.  _Games and Economic Behavior_ 113 (2019), 734–742.
  * Norde et al. (2004) Henk Norde, Stefano Moretti, and Stef Tijs. 2004\.  Minimum cost spanning tree games and population monotonic allocation schemes.  _European Journal of Operational Research_ 154, 1 (2004), 84–97.
  * PENNA and VENTRE (2004) Paolo PENNA and Carmine VENTRE. 2004.  Sharing the cost of multicast transmissions in wireless networks.  _Lecture Notes in Computer Science_ (2004), 255–266.
  * Prim (1957) Robert Clay Prim. 1957\.  Shortest connection networks and some generalizations.  _The Bell System Technical Journal_ 36, 6 (1957), 1389–1401.
  * Shapley (1953) Lloyd S Shapley. 1953\.  A value for n-person games.  _Contributions to the Theory of Games_ 2, 28 (1953), 307–317.
  * Silvela and Portillo (2001) Jaime Silvela and Javier Portillo. 2001.  Breadth-first search and its application to image processing problems.  _IEEE Transactions on Image Processing_ 10, 8 (2001), 1194–1199.
  * Tijs et al. (2006) Stef Tijs, Rodica Branzei, Stefano Moretti, and Henk Norde. 2006.  Obligation rules for minimum cost spanning tree situations and their monotonicity properties.  _European Journal of Operational Research_ 175, 1 (2006), 121–134.
  * Tijs and Driessen (1986) Stef H Tijs and Theo SH Driessen. 1986.  Game theory and cost allocation problems.  _Management Science_ 32, 8 (1986), 1015–1028.
  * Todo and Yokoo (2020) Taiki Todo and Makoto Yokoo. 2020.  Split manipulations in cost sharing of minimum cost spanning tree.  In _Proceedings of the 2020 European Conference on Artifical Intelligence_. 219–226.
  * Trudeau (2012) Christian Trudeau. 2012\.  A new stable and more responsive cost sharing solution for minimum cost spanning tree problems.  _Games and Economic Behavior_ 75, 1 (2012), 402–412.
  * Trudeau and Vidal-Puga (2017) Christian Trudeau and Juan Vidal-Puga. 2017.  On the set of extreme core allocations for minimal cost spanning tree problems.  _Journal of Economic Theory_ 169 (2017), 425–452.
  * Vickrey (1961) William Vickrey. 1961\.  Counterspeculation, auctions, and competitive sealed tenders.  _The Journal of Finance_ 16, 1 (1961), 8–37.
  * Zhang et al. (2023) Tianyi Zhang, Junyu Zhang, Sizhe Gu, and Dengji Zhao. 2023\.  Cost sharing under private valuation and connection control. In _Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems_. 2161–2169.