# Computation of a new error bound for tensor complementarity problem with P
tensor

R. Deba,1, A. Duttaa,2, A. K. Dasb,3
_a Jadavpur University, Kolkata , 700 032, India._
_b Indian Statistical Institute, 203 B. T. Road, Kolkata, 700 108, India._
_1 Email<EMAIL_ADDRESS>
_2 Email<EMAIL_ADDRESS>
_3 Email<EMAIL_ADDRESS>

###### Abstract

We propose a new error bound for the solution of tensor complementarity
problem TCP$(q,\mathcal{A})$ given that $\mathcal{A}$ is a $P$-tensor and $q$
is a real vector. We show that the proposed error bound is sharper than the
earlier version of error bound available in the literature. We establish
absolute and relative error bound for TCP$(q,\mathcal{A})$ where $\mathcal{A}$
is an even order positive diagonal tensor.

Keywords: Tensor complementarity problem, $P$-tensor, global error bound,
positively homogeneous operator.

AMS subject classifications: 90C33, 15A69, 65K10.

11footnotetext: Corresponding author

##  Introduction

In this article a new error bound sharper than the earlier version is
introduced for the tensor complementarity problem with $P$-tensor. During last
several years, the tensor complementarity problem attains much attraction and
has been studied extensively with respect to theory, to solution methods and
applications. In recent years, various tensors with special structures have
been studied. For details, see [41] and [44]. The tensor complementarity
problem was studied initially by Song and Qi [42]. The tensor complementarity
problem is a subclass of the non-linear complementarity problems where the
function involved in the non-linear complementarity problem is a special
polynomial defined by a tensor in the tensor complementarity problem. The
polynomial functions used in tensor complementarity problems have some special
structures.
For a given mapping $F:\mathbb{R}^{n}\mapsto\mathbb{R}^{n}$ the
complementarity problem is to find a vector $x\in\mathbb{R}^{n}$ such that

$x\geq 0,\leavevmode\nobreak\ \leavevmode\nobreak\ F(x)\geq
0,\leavevmode\nobreak\ \leavevmode\nobreak\ \mbox{and}\leavevmode\nobreak\
x^{T}F(x)=0.$ (1.1)

If $F$ is nonlinear mapping, then the problem (1.1) is called a nonlinear
complementarity problem [13], and if $F$ is linear function, then the problem
(1.1) reduces to a linear complementarity problem [4]. The linear
complementarity problem may be defined as follows:
Given a matrix $M\in\mathbb{R}^{n\times n}$ and a vector $q\in\mathbb{R}^{n}$,
the linear complementarity problem [4], denoted by $LCP(q,M)$, is to find a
pair of vectors $w,z\in\mathbb{R}^{n}$ such that

$z\geq 0,\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
w=Mz+q\geq 0,\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
z^{T}w=0.$ (1.2)

The algorithm based on principal pivot transforms namely Lemke’s algorithm,
Criss-cross algorithm which are used to find the solutions of linear
complementarity problem are studied extensively considering several matrix
classes.

It is important that large number of formulations not only enrich the linear
complementarity problem but also generate different matrix classes along with
their computational methods. For details see [9], [32], [11] [12], [36], [20],
[30], [35], [17], [21], [37], [7], [8]. For details of game theory see [27],
[33], [39], [29], [28], [6], [34] and for details of QMOP see [26]. Even
matrix classes arise during the study of Lemke’s algorithm as well as
principal pivot transform. For details see [25], [24] [31], [5], [38], [17],
[18], [21], [19]. Now we consider the case of $F(x)=\mathcal{A}x^{m-1}+q$ with
$\mathcal{A}\in T_{m,n}$ and $q\in\mathbb{R}^{n}$ then the problem (1.1)
becomes

$x\geq 0,\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\mathcal{A}x^{m-1}+q\geq 0,\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \mbox{and}\leavevmode\nobreak\ \leavevmode\nobreak\
x^{T}(\mathcal{A}x^{m-1}+q)=0$ (1.3)

which is called a tensor complementarity problem, denoted by the
TCP$(q,\mathcal{A})$. Denote $\omega=\mathcal{A}x^{m-1}+q$, then the tensor
complementarity problem is to find $x$ such that

$x\geq 0,\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\omega=\mathcal{A}x^{m-1}+q\geq 0,\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \mbox{and}\leavevmode\nobreak\ \leavevmode\nobreak\
x^{T}\omega=0.$ (1.4)

Motivated by the discussion on positive definiteness of multivariate
homogeneous polynomial forms [2], [15], [22], Qi [40] introduced the concept
of symmetric positive definite (positive semi-definite) tensors. Song and Qi
[44] studied $P(P_{0})$-tensors and $B(B_{0})$-tensors. The equivalence
between (strictly) semi-positive tensors and (strictly) copositive tensors in
symmetric case were shown by Song and Qi [45]. The existence and uniqueness of
solution of TCP$(q,\mathcal{A})$ with some special tensors were discussed by
Che, Qi, Wei [3]. The boundedness of the solution set of the
TCP$(q,\mathcal{A})$ was studied by Song and Yu [46]. The sparse solutions to
TCP$(q,\mathcal{A})$ with a $Z$-tensor and its method to calculate were
obtained by Luo, Qi and Xiu [23]. The equivalent conditions of solution to
TCP$(q,\mathcal{A})$ were shown by Gowda, Luo, Qi and Xiu [14] for a
$Z$-tensor $\mathcal{A}$. The global uniqueness of solution of
TCP$(q,\mathcal{A})$ was considered by Bai, Huang and Wang [1] for a strong
$P$-tensor $\mathcal{A}$. The properties of TCP$(q,\mathcal{A})$ was studied
by Ding, Luo and Qi [10] for a new class of $P$-tensor. The properties of the
several classes of $Q$-tensors were presented by Suo and Wang [16]. In this
article we introduce column adequate tensor in the context of tensor
complementarity problem and study different properties of this tensor.
The paper is organised as follows. Section 2 contains some basic notations and
results. In Section 3, We propose a new error bound for the solution of tensor
complementarity problem TCP$(q,\mathcal{A})$ given that $\mathcal{A}$ is a
$P$-tensor and $q$ is a real vector. We show that the proposed error bound is
sharper than the earlier version of error bound available in the literature.
We establish absolute and relative error bound for TCP$(q,\mathcal{A})$ where
$\mathcal{A}$ is an even order positive diagonal tensor. The results are
illustrated with the help of a numerical example.

##  Preliminaries

We begin by introducing some basic notations used in this paper. We consider
tensor, matrices and vectors with real entries. Let $m$th order $n$
dimensional real tensor $\mathcal{A}=(a_{i_{1}i_{2}...i_{m}})$ be a
multidimensional array of entries $a_{i_{1}i_{2}...i_{m}}\in\mathbb{R}$ where
$i_{j}\in[n]$ with $j\in[m]$. $T_{m,n}$ denotes the set of real tensors of
order $m$ and dimension $n.$ For any positive integer $n,$ $[n]$ denotes set
of $\\{1,2,...,n\\}$. All vectors are column vectors. Let $\mathbb{R}^{n}$
denote the $n$-dimensional Euclidean space and
$\mathbb{R}^{n}_{+}:=\\{x\in\mathbb{R}^{n}:x\geq 0\\}$. For any
$x\in\mathbb{R}^{n}$, let $x^{[m]}\in\mathbb{R}^{n}$ with its $i$th component
being $x^{m}_{i}$ for all $i\in[n]$.
$||x||_{\infty}=\max\\{|x_{i}|:i\in[n]\\}$ and
$||x||_{2}=\left(\sum_{i=1}^{n}|x_{i}|^{2}\right)^{\frac{1}{2}}.$ Then for a
continuous, positively homogeneous operator
$T:\mathbb{R}^{n}\mapsto\mathbb{R}^{n}$ it is obvious that
$||T||_{\infty}=\max_{||x||_{\infty}=1}||T(x)||_{\infty}$ is an operator norm
of $T$ and $||T(x)||_{\infty}\leq||T||_{\infty}||x||_{\infty}$ for any
$x\in\mathbb{R}^{n}.$ For $\mathcal{A}\in T_{m,n}$ and
$x\in\mathbb{R},\;\mathcal{A}x^{m-1}\in\mathbb{R}^{n}$ is a vector defined by

$(\mathcal{A}x^{m-1})_{i}=\sum_{i_{2},i_{3},...i_{m}=1}^{n}a_{ii_{2}i_{3}...i_{m}}x_{i_{2}}x_{i_{3}}\cdot\cdot\cdot
x_{i_{m}},\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\mbox{for all}\leavevmode\nobreak\ i\in[n]$

and $\mathcal{A}x^{m}\in\mathbb{R}$ is a scalar defined by

$\mathcal{A}x^{m}=\sum_{i_{1},i_{2},i_{3},...i_{m}=1}^{n}a_{i_{1}i_{2}i_{3}...i_{m}}x_{i_{1}}x_{i_{2}}\cdot\cdot\cdot
x_{i_{m}}.$

For any $\mathcal{A}\in T_{m,n},$

$||\mathcal{A}||_{\infty}=\max_{i\in[n]}\sum_{i_{2},...,i_{m}=1}^{n}|a_{ii_{2},...,i_{m}}|.$

Song et al. [44] defined two operators. Let $\mathcal{A}\in T_{m,n}.$ For
$x\in\mathbb{R}^{n},$ the operator
$T_{\mathcal{A}}:\mathbb{R}^{n}\mapsto\mathbb{R}^{n}$ is defined by

$T_{\mathcal{A}}x=\left\\{\begin{array}[]{rr}||x||_{2}^{2-m}\mathcal{A}x^{m-1},&x\neq
0,\\\ 0,&x=0.\end{array}\;\right.$ (2.1)

When $m$ is even, for $x\in\mathbb{R}^{n}$ another operator
$F_{\mathcal{A}}:\mathbb{R}^{n}\mapsto\mathbb{R}^{n}$ is defined by

$F_{\mathcal{A}}x=(\mathcal{A}x^{m-1})^{[\frac{1}{m-1}]}.$ (2.2)

Song et al. [44] introduced two important quantities

$\alpha(T_{\mathcal{A}})=\min_{||x||_{\infty}=1}\max_{i\in[n]}x_{i}(T_{\mathcal{A}}x)_{i}$
(2.3)

for any positive integer $m$ and

$\alpha(F_{\mathcal{A}})=\min_{||x||_{\infty}=1}\max_{i\in[n]}x_{i}(F_{\mathcal{A}}x)_{i}$
(2.4)

when $m$ is even. Since $P$-tensors are all even order, then
$\alpha(T_{\mathcal{A}})$ and $\alpha(F_{\mathcal{A}})$ are both well defined
for any $P$-tensor. The following result is necessary and sufficient
conditions for a P-tensor in terms of $\alpha(T_{\mathcal{A}})$ and
$\alpha(F_{\mathcal{A}}).$

######  lemma 2.1:

[44] Let $\mathcal{A}\in T_{m,n}.$ Then
(a) $\mathcal{A}$ is a $P$-tensor if and only if $\alpha(T_{\mathcal{A}})>0,$
(b) When $m$ is even $\mathcal{A}$ is a $P$-tensor if and only if
$\alpha(F_{\mathcal{A}})>0.$

Since every strong $P$-tensor is a $P$-tensor, the following corollary is
obvious.

######  corollary 2.1:

[47] Let $\mathcal{A}\in T_{m,n}.$ Then
(a) $\alpha(T_{\mathcal{A}})>0$ if $\mathcal{A}$ is a strong $P$-tensor,
(b) $\alpha(F_{\mathcal{A}})>0$ if $\mathcal{A}$ is a strong $P$-tensor.

######  Definition 2.1.

Let $e:\mathbb{R}^{n}\mapsto\mathbb{R}^{n}_{+}$ be a function. Assume that
TCP$(q,\mathcal{A})$ has a nonempty solution set.

(a) We say that $e(x)$ is a residual function of TCP$(q,\mathcal{A})$, if
$e(x)\geq 0$, and $e(x)=0$ if and only if $x$ solves TCP$(q,\mathcal{A})$.

(b) We say that a residual function $e(x)$ is a lower global error bound for
TCP$(q,\mathcal{A})$, if $\exists$ some constants $c_{1}>0$ such that for each
$x\in\mathbb{R}^{n}$ and any solution $\bar{x},$ $c_{1}e(x)\leq||x-\bar{x}||.$

(c) We say that a residual $e(x)$ is an upper global error bound for the
TCP$(q,\mathcal{A})$ if there exists some constant $c_{2}>0$ such that for
each $x\in\mathbb{R}^{n}$ and any solution $\bar{x},$ $||x-\bar{x}||\leq
c_{2}e(x),$

######  definition 2.1:

[46] Given $\mathcal{A}=(a_{i_{1}i_{2}...i_{m}})\in T_{m,n}$ and
$q\in\mathbb{R}^{n}$, a vector $x$ is said to be (strictly) feasible, if
$x(>)\geq 0$ and $\mathcal{A}x^{m-1}+q(>)\geq 0$.

TCP$(q,\mathcal{A})$, defined by equation (1.3) is said to be (strictly)
feasible if a (strictly) feasible vector exists.

TCP$(q,\mathcal{A})$ is said to be solvable if there is a feasible vector $x$
satisfying $x^{T}(\mathcal{A}x^{m-1}+q)=0$ and $x$ is the solution.

######  definition 2.2:

[44] A tensor $\mathcal{A}=(a_{i_{1}i_{2}...i_{m}})\in T_{m,n}$ is said to be
a $P$-tensor, if for each $x\in\mathbb{R}^{n}\backslash\\{0\\}$, there exists
an index $i\in[n]$ such that $x_{i}\neq 0$ and
$x_{i}(\mathcal{A}x^{m-1})_{i}>0$.

######  definition 2.3:

[1] A tensor $\mathcal{A}\in T_{m,n}$ is said to be strong $P$-tensor if for
any two different $x=(x_{i})$ and $y=(y_{i})$ in $\mathbb{R}^{n}$,
$\max_{i\in[n]}(x_{i}-y_{i})(\mathcal{A}x^{m-1}-\mathcal{A}y^{m-1})_{i}>0$.

######  theorem 2.1:

[1] For any $q\in\mathbb{R}^{n}$ and a $P$-tensor $\mathcal{A}\in T_{m,n}$,
the solution set of TCP$(q,\mathcal{A})$ is nonempty and compact.

######  theorem 2.2:

[1] Let $\mathcal{A}\in T_{m,n}$ be a strong $P$-tensor. Then the
TCP$(q,\mathcal{A})$ has the property of global uniqueness and solvability
property.

######  theorem 2.3:

[43] Let $\mathcal{A}\in T_{m,n}\;(m\geq 0)$ be a $P$-tensor, and let $x$ be a
solution of TCP$(q,\mathcal{A}).$ If $m$ be even, then

$\frac{||(-q)_{+}||_{\infty}^{\frac{1}{m-1}}}{||F_{\mathcal{A}}||_{\infty}}\leq||x||_{\infty}\leq\frac{||(-q)_{+}||_{\infty}^{\frac{1}{m-1}}}{\alpha(F_{\mathcal{A}})}.$
(2.5)

######  theorem 2.4:

[47] Given $q\in\mathbb{R}^{n},\;\mathcal{A}\in T_{m,n}$ with $\mathcal{A}$
being a $P$-tensor and $\alpha(F_{\mathcal{A}})$ is defined by (2.4). For any
$u\in\mathbb{R}^{n},$ let $x$ be a solution of TCP$(q,\mathcal{A}).$ Suppose
the residue function $\tilde{v}$ is defined as
$\tilde{v}=\min\\{u,[(\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]}+(\mathcal{A}z^{m-1}+q)^{[\frac{1}{m-1}]}]\\}.$
Then for any $u\in\mathbb{R}^{n},$

$\frac{1}{1+||\mathcal{A}||^{\frac{1}{m-1}}}_{\infty}||\tilde{v}||_{\infty}\leq||u-x||_{\infty}\leq\frac{1+||\mathcal{A}||^{\frac{1}{m-1}}_{\infty}}{\alpha(F_{\mathcal{A}})}||\tilde{v}||_{\infty}$
(2.6)

##  Main results

We begin with a theorem which provides a solution bound for
TCP$(q,\mathcal{A})$ involving $P$-tensor.

######  theorem 3.1:

Let $\mathcal{A}\in T_{m,n}$ be a $P$-tensor where $m$ is even and $x$ be a
solution of TCP$(q,\mathcal{A}).$ Then

$\frac{||(-q)_{+}||_{\infty}^{\frac{1}{m-1}}}{||\mathcal{A}||_{\infty}^{\frac{1}{m-1}}}\leq||x||_{\infty}\leq\frac{||(-q)_{+}||_{\infty}^{\frac{1}{m-1}}}{\alpha(F_{\mathcal{A}})}.$
(3.1)

###### Proof.

Note that from Theorem 2.3 we obtain the right hand inequality. We prove the
left hand inequality. Since $x$ is a solution of TCP$(q,\mathcal{A})$ we have
$\mathcal{A}x^{m-1}+q\geq 0.$ Which implies

$\mathcal{A}x^{m-1}\geq-q.$ (3.2)

The following inequation is proved by Zheng et al [47] in Theorem 3.2. However
for the sake of completeness we give the details. We have

$\displaystyle||\mathcal{A}x||_{\infty}^{\frac{1}{m-1}}$
$\displaystyle=\left(\max_{i\in[n]}\left\\{|(\mathcal{A}x^{m-1})_{i}|\right\\}\right)^{\frac{1}{m-1}}$
$\displaystyle=\left(\max_{i\in[n]}\left\\{|\sum_{i_{2},...,i_{m}=1}^{n}a_{ii_{2}...i_{m}}x_{i_{1}}x_{i_{2}}...x_{i_{m}}|\right\\}\right)^{\frac{1}{m-1}}$
$\displaystyle\leq\left(\max_{i\in[n]}\left\\{\sum_{i_{2},...,i_{m}=1}^{n}|a_{ii_{2}...i_{m}}|\right\\}||x||_{\infty}^{m-1}\right)^{\frac{1}{m-1}}$
$\displaystyle=\left(||\mathcal{A}||_{\infty}||x||_{\infty}^{m-1}\right)^{\frac{1}{m-1}}$
$\displaystyle=||\mathcal{A}||_{\infty}^{\frac{1}{m-1}}||x||_{\infty}.$

Thus

$||\mathcal{A}x||_{\infty}^{\frac{1}{m-1}}\leq||\mathcal{A}||_{\infty}^{\frac{1}{m-1}}||x||_{\infty}.$
(3.3)

Therefore,

$||\mathcal{A}||_{\infty}^{\frac{1}{m-1}}||x||_{\infty}\geq||\mathcal{A}x||_{\infty}^{\frac{1}{m-1}}\geq||(\mathcal{A}x)_{+}||_{\infty}^{\frac{1}{m-1}}\geq||(-q)_{+}||_{\infty}^{\frac{1}{m-1}}\mbox{
using Equation \ref{for bound of solution}}.$

Hence the left hand inequality. ∎

Here we investigate the global error bound for the TCP$(q,\mathcal{A}).$

######  theorem 3.2:

Let $\mathcal{A}\in T_{m,n}$ be a $P$-tensor, $z\in\mathbb{R}^{n}$ be a
solution of TCP$(q,\mathcal{A})$ and $u$ be an arbitrary vector in
$\mathbb{R}^{n}$. Then

$\frac{||v||_{\infty}(1+||\mathcal{A}||_{\infty}^{\frac{1}{m-1}})-\sqrt{D}}{2\alpha(F_{\mathcal{A}})}\leq||z-u||_{\infty}\leq\frac{||v||_{\infty}(1+||\mathcal{A}||_{\infty}^{\frac{1}{m-1}})+\sqrt{D}}{2\alpha(F_{\mathcal{A}})},\;\forall\;u\in\mathbb{R}^{n},$
(3.4)

where

$v=u-\max\\{0,u-[(\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]}+(\mathcal{A}z^{m-1}+q)^{[\frac{1}{m-1}]}]\\},$

and

$D=||v||_{\infty}^{2}(1+||\mathcal{A}||_{\infty}^{\frac{1}{m-1}})^{2}-4\alpha(F_{\mathcal{A}})v_{t}^{2}\geq
0,$

the quantity $\alpha(F_{\mathcal{A}})$ is defined by (2.4) and $t$ satisfies
$v_{t}\neq 0,$

$\max_{i\in[n]}\\{(u-z)_{i}(\mathcal{A}(u-z)^{m-1})_{i}\\}=(u-z)_{t}(\mathcal{A}(u-z)^{m-1})_{t}.$

###### Proof.

Consider the TCP$(q,\mathcal{A})$, which is to find $z\in\mathbb{R}^{n}$ such
that,

$z\geq 0,\;\;\mathcal{A}z^{m-1}+q\geq 0,\;\;z^{T}(\mathcal{A}z^{m-1}+q)=0.$
(3.5)

Let the solution set of TCP$(q,\mathcal{A})$ be denoted by
$SOL(\mathcal{A},q)=\\{z\in\mathbb{R}^{n}:\;z\geq 0,\;\mathcal{A}z^{m-1}+q\geq
0,\;z^{T}(\mathcal{A}z^{m-1}+q)=0\\}$. Let $z\in SOL(\mathcal{A},q).$ Then for
$w=(\mathcal{A}z^{m-1}+q)^{[\frac{1}{m-1}]}\geq 0,$ we have

$z\geq 0,\;\;\;\;w\geq 0,\;\;\;\;z^{T}w=0.$ (3.6)

Let
$v=u-\max\\{0,u-[(\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]}+(\mathcal{A}z^{m-1}+q)^{[\frac{1}{m-1}]}]\\}.$
Now we consider the vector $y=u-v$ and
$x=(\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]}+(\mathcal{A}z^{m-1}+q)^{[\frac{1}{m-1}]}-v$.
Then

$y=u-v=\max\\{0,u-[(\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]}+(\mathcal{A}z^{m-1}+q)^{[\frac{1}{m-1}]}]\\}\geq
0.$

Again,

$\displaystyle x$
$\displaystyle=(\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]}+(\mathcal{A}z^{m-1}+q)^{[\frac{1}{m-1}]})-v$
$\displaystyle=(\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]}+(\mathcal{A}z^{m-1}+q)^{[\frac{1}{m-1}]}-u$
$\displaystyle\quad\quad+\max\\{0,u-[(\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]}+(\mathcal{A}z^{m-1}+q)^{[\frac{1}{m-1}]}]\\}$
$\displaystyle=\max\\{0,[(\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]}+(\mathcal{A}z^{m-1}+q)^{[\frac{1}{m-1}]}]-u\\}\geq
0.$

Also by the construction of the vectors $y$ and $x$ we have
$y_{i}x_{i}=0,\;\forall\;i\in[n.]$ Thus the vectors $y$ and $x$ satisfy the
following inequalities and complementarity condition.

$y\geq 0,\;\;\;\;x\geq 0,\;\;\;\;y^{T}x=0.$ (3.7)

Then for $i\in[n],$

$(y-z)_{i}(x-w)_{i}=y_{i}x_{i}-z_{i}x_{i}-y_{i}w_{i}+z_{i}w_{i}=-z_{i}x_{i}-y_{i}w_{i}\leq
0.$ (3.8)

Again

$\displaystyle(y-z)_{i}(x-w)_{i}$
$\displaystyle=(u-v-z)_{i}((\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]}-v)_{i}$
$\displaystyle=(u-z)_{i}((\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]})_{i}-v_{i}((\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]})_{i}$
$\displaystyle-(u-z)_{i}v_{i}+v^{2}_{i}$ $\displaystyle\leq 0\;\;\mbox{ by
(\ref{error bound proof 1}).}$

Hence for each $i$ we obtain

$(u-z)_{i}((\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]})_{i}\leq
v_{i}((\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]})_{i}+(u-z)_{i}v_{i}-v^{2}_{i}.$
(3.9)

As $\mathcal{A}$ is a $P$-tensor,
$\max_{i\in[n]}\\{x_{i}(\mathcal{A}x^{m-1})_{i}\\}>0,\;\forall\;x\;\in\mathbb{R}^{n}\backslash\\{0\\}$.
Let $t$ be the particular index for which

$\max_{i\in[n]}\\{(u-z)_{i}((\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]})_{i}\\}=(u-z)_{t}((\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]})_{t}\geq
0.$ (3.10)

Now using from (3.3) we have

$||\mathcal{A}(u-z)^{m-1}||_{\infty}^{\frac{1}{m-1}}\leq||\mathcal{A}||_{\infty}^{\frac{1}{m-1}}||u-z||_{\infty}.$
(3.11)

Again from Equation 14 of [47] we have,

$\alpha(F_{\mathcal{A}})||z-u||_{\infty}^{2}\leq\max_{i\in[n]}\\{(u-z)_{i}(\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]}_{i}\\}.$
(3.12)

Then from (3.9) (3.10), (3.11) and (3.12) we obtain,

$\displaystyle\alpha(F_{\mathcal{A}})||z-u||_{\infty}^{2}$
$\displaystyle\leq\max_{i\in[n]}\\{(u-z)_{i}(\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]}_{i}\\}$
$\displaystyle\leq(u-z)_{t}v_{t}+v_{t}((\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]})_{t}-v^{2}_{t}$
$\displaystyle\leq||u-z||_{\infty}||v||_{\infty}+||\mathcal{A}(u-z)^{m-1}||_{\infty}^{\frac{1}{m-1}}||v||_{\infty}-v_{t}^{2}$
$\displaystyle\leq||v||_{\infty}||u-z||_{\infty}+||\mathcal{A}||_{\infty}^{\frac{1}{m-1}}||u-z||_{\infty}||v||_{\infty}-v_{t}^{2}$
$\displaystyle=(1+||\mathcal{A}||_{\infty}^{\frac{1}{m-1}})||v||_{\infty}||u-z||_{\infty}-v_{t}^{2}.$

Therefore,

$\alpha(F_{\mathcal{A}})||z-u||_{\infty}^{2}\leq(1+||\mathcal{A}||_{\infty}^{\frac{1}{m-1}})||v||_{\infty}||u-z||_{\infty}-v_{t}^{2}$
(3.13)

from (3.13) we observe that if $v_{t}=0$ then $u=z$, which means $u$ is the
true solution. Thus if $v_{t}\neq 0$, then from (3.13) we obtain,

$\alpha(F_{\mathcal{A}})||z-u||_{\infty}^{2}-(1+||\mathcal{A}||_{\infty}^{\frac{1}{m-1}})||v||_{\infty}||u-z||_{\infty}+v_{t}^{2}\leq
0.$ (3.14)

Solving the above inequality we obtain the desired relation. ∎

Here we propose a relative error bound for the approximate solution for
TCP$(q,\mathcal{A})$ provided that the involved tensor $\mathcal{A}$ is a
$P$-tensor.

######  theorem 3.3:

Let $\mathcal{A}\in T_{m,n}$ be a $P$-tensor and $0\neq z\in\mathbb{R}^{n}$ be
a solution of TCP$(q,\mathcal{A})$ and $u$ be an arbitrary vector in
$\mathbb{R}^{n}$. If $(-q)_{+}\neq 0,$ we have

$\frac{||v||_{\infty}(1+||\mathcal{A}||_{\infty}^{\frac{1}{m-1}})-\sqrt{D}}{2||(-q)_{+}||_{\infty}^{\frac{1}{m-1}}}\leq\frac{||z-u||_{\infty}}{||z||_{\infty}}\leq\frac{||\mathcal{A}||_{\infty}^{\frac{1}{m-1}}[||v||_{\infty}(1+||\mathcal{A}||_{\infty}^{\frac{1}{m-1}})+\sqrt{D}]}{2\alpha(F_{\mathcal{A}})||(-q)_{+}||_{\infty}^{\frac{1}{m-1}}}$
(3.15)

where
$v=u-\max\\{0,u-[(\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]}+(\mathcal{A}z^{m-1}+q)^{[\frac{1}{m-1}]}]\\}$,

$D=||v||_{\infty}^{2}(1+||\mathcal{A}||_{\infty}^{\frac{1}{m-1}})^{2}-4\alpha(F_{\mathcal{A}})v_{t}^{2}\geq
0$ and $t$ satisfies $v_{t}\neq 0,$

$(u-z)_{t}(\mathcal{A}(u-z)^{m-1})_{t}=\max_{i\in[n]}\\{(u-z)_{i}(\mathcal{A}(u-z)^{m-1})_{i}\\}.$

###### Proof.

From Theorem 3.1 we have inequation (3.1). Since $(-q)_{+}\neq 0,$ and $z\neq
0$ the inequation (3.1) gives

$\frac{||\mathcal{A}||_{\infty}^{\frac{1}{m-1}}}{||(-q)_{+}||_{\infty}^{\frac{1}{m-1}}}\leq\frac{1}{||z||_{\infty}}\leq\frac{\alpha(F_{\mathcal{A}})}{||(-q)_{+}||_{\infty}^{\frac{1}{m-1}}}.$
(3.16)

From Theorem 3.2 we have inequation 3.4. Now combining inequations (3.4) and
(3.16) we obtain the desired result. ∎

Here we consider a positive diagonal tensor of even order which is eventually
a $P$-tensor, and find a property of the quantity $\alpha(F_{\mathcal{A}}).$

######  lemma 3.1:

Let $\mathcal{A}\in T_{m,n}$ be a positive diagonal tensor, where $m$ is even.
Then $\alpha(F_{\mathcal{A}})=\min_{i\in[n]}\\{(a_{ii\cdots
i})^{\frac{1}{m-1}}\\}$. Where $a_{ii\dots i}$ denote the main diagonal
elements of $\mathcal{A}$, for $i=1,2,...,n$.

###### Proof.

Let $x\in\mathbb{R}^{n}$ be an arbitrary vector satisfied with
$||x||_{\infty}=1.$ Then we have

$\displaystyle\max_{i\in[n]}\\{x_{i}(F_{\mathcal{A}(x)})_{i}\\}$
$\displaystyle=\max_{i\in[n]}\\{x_{i}(\mathcal{A}x^{m-1})^{[\frac{1}{m-1}]}_{i}\\}$
$\displaystyle=\max_{||x||_{\infty}=1}\\{x_{i}(a_{ii\dots
i}x_{i}^{m-1})^{\frac{1}{m-1}},\;i=1,2,\dots n\\}$
$\displaystyle=\max_{||x||_{\infty}=1}\\{(a_{ii\cdots
i})^{\frac{1}{m-1}}x_{i}^{2},\;i=1,2,\dots n\\}$
$\displaystyle\geq\min_{i\in[n]}\\{(a_{ii\cdots i})^{\frac{1}{m-1}}\\}\;>0.$

Thus

$\alpha(F_{\mathcal{A}})=\min_{||x||_{\infty}=1}\max_{i\in[n]}\\{x_{i}(F_{\mathcal{A}}(x))_{i}\\}\geq\min_{i\in[n]}\\{(a_{ii\cdots
i})^{\frac{1}{m-1}}\\}.$ (3.17)

On the other hand by Theorem 4.2 of [43] we have

$\alpha(F_{\mathcal{A}})\leq\min_{i\in[n]}\\{(a_{ii\cdots
i})^{\frac{1}{m-1}}\\}.$ (3.18)

Thus from (3.17) and (3.18) we have,

$\alpha(F_{\mathcal{A}})=\min_{i\in[n]}\\{(a_{ii\cdots
i})^{\frac{1}{m-1}}\\}.$ (3.19)

∎

Here we present solution bound, absolute and relative error bound of the
solution of TCP$(q,\mathcal{A}),$ where $\mathcal{A}$ is an even order
positive diagonal tensor.

######  theorem 3.4:

Let $\mathcal{A}\in T_{m,n}$ be a positive diagonal tensor and $m$ be even.
Let $z\in\mathbb{R}^{n}$ be a solution of the TCP$(q,\mathcal{A})$ and $u$ be
an arbitrary vector in $\mathbb{R}^{n}$. Then,

$\displaystyle\frac{||v_{1}||_{\infty}(1+(\max_{i\in[n]}\\{a_{ii\cdots
i}\\})^{\frac{1}{m-1}})-\sqrt{D_{1}}}{2\min_{i\in[n]}\\{(a_{ii\cdots
i})^{\frac{1}{m-1}}\\}}$ $\displaystyle\leq||z-u||_{\infty}$
$\displaystyle\leq\frac{||v_{1}||_{\infty}(1+(\max_{i\in[n]}\\{a_{ii\cdots
i}\\})^{\frac{1}{m-1}})+\sqrt{D_{1}}}{2\min_{i\in[n]}\\{(a_{ii\cdots
i})^{\frac{1}{m-1}}\\}}$

and

$\frac{||(-q)_{+}||_{\infty}^{\frac{1}{m-1}}}{(\max_{i\in[n]}\\{a_{ii\cdots
i}\\})^{\frac{1}{m-1}}}\leq||z||_{\infty}\leq\frac{||(-q)_{+}||_{\infty}^{\frac{1}{m-1}}}{\min_{i\in[n]}\\{(a_{ii\cdots
i})^{\frac{1}{m-1}}\\}},$

where
$v_{1}=u-\max\\{0,u-[(\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]}+(\mathcal{A}z^{m-1}+q)^{[\frac{1}{m-1}]}]\\}$,
$D_{1}=||v_{1}||_{\infty}^{2}(1+(\max_{i\in[n]}\\{a_{ii\cdots
i}\\})^{\frac{1}{m-1}})^{2}-4(\min_{i\in[n]}\\{(a_{ii\cdots
i})^{\frac{1}{m-1}})v_{t}^{2}\geq 0$ and $t$ satisfies
$\max_{i\in[n]}\\{(u-z)_{i}(\mathcal{A}(u-z)^{m-1})_{i}\\}=(u-z)_{t}(\mathcal{A}(u-z)^{m-1})_{t}\geq
0$ and $v_{t}\neq 0$.

###### Proof.

$\mathcal{A}$ is positive diagonal tensor of even order then $a_{ii\cdots
i}>0,\forall i\in[n]$ and all other entries of $\mathcal{A}$ are zeros. Then
$\mathcal{A}$ is a $P$-tensor and
$||\mathcal{A}||_{\infty}=\max_{i\in[n]}\\{a_{ii\cdots i}\\}$ also from Lemma
3.1, $\alpha(F_{\mathcal{A}})=\min_{i\in[n]}\\{(a_{ii\cdots
i})^{\frac{1}{m-1}}\\}.$ In Theorem 3.1, putting the values of
$\alpha(F_{\mathcal{A}})$ and $||\mathcal{A}||_{\infty}$ in (3.1) we obtain

$\frac{||(-q)_{+}||_{\infty}^{\frac{1}{m-1}}}{(\max_{i\in[n]}\\{a_{ii\cdots
i}\\})^{\frac{1}{m-1}}}\leq||z||_{\infty}\leq\frac{||(-q)_{+}||_{\infty}^{\frac{1}{m-1}}}{\min_{i\in[n]}\\{(a_{ii\cdots
i})^{\frac{1}{m-1}}\\}}.$ (3.20)

In Theorem 3.2, putting the values of $\alpha(F_{\mathcal{A}})$ and
$||\mathcal{A}||_{\infty}$ in (3.4) we obtain

$\displaystyle\frac{||v_{1}||_{\infty}(1+(\max_{i\in[n]}\\{a_{ii\cdots
i}\\})^{\frac{1}{m-1}})-\sqrt{D_{1}}}{2\min_{i\in[n]}\\{(a_{ii\cdots
i})^{\frac{1}{m-1}}\\}}$ $\displaystyle\leq||z-u||_{\infty}$ (3.21)
$\displaystyle\leq\frac{||v_{1}||_{\infty}(1+(\max_{i\in[n]}\\{a_{ii\cdots
i}\\})^{\frac{1}{m-1}})+\sqrt{D_{1}}}{2\min_{i\in[n]}\\{(a_{ii\cdots
i})^{\frac{1}{m-1}}\\}},$ (3.22)

where
$v_{1}=u-\max\\{0,u-[(\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]}+(\mathcal{A}z^{m-1}+q)^{[\frac{1}{m-1}]}]\\}$,
$D_{1}=||v_{1}||_{\infty}^{2}(1+(\max_{i\in[n]}\\{a_{ii\cdots
i}\\})^{\frac{1}{m-1}})^{2}-4(\min_{i\in[n]}\\{(a_{ii\cdots
i})^{\frac{1}{m-1}})v_{t}^{2}\geq 0$ and $t$ satisfies
$\max_{i\in[n]}\\{(u-z)_{i}(\mathcal{A}(u-z)^{m-1})_{i}\\}=(u-z)_{t}(\mathcal{A}(u-z)^{m-1})_{t}\geq
0$ and $v_{t}\neq 0$. ∎

######  theorem 3.5:

Let $\mathcal{A}\in T_{m,n}$ be a positive diagonal tensor of even order,
$0\neq z\in\mathbb{R}^{n}$ be a solution of TCP$(q,\mathcal{A})$ and $u$ be an
arbitrary vector in $\mathbb{R}^{n}$. If $(-q)_{+}\neq 0$ then

$\displaystyle\frac{||v_{1}||_{\infty}(1+(\max_{i\in[n]}\\{a_{ii\cdots
i}\\})^{\frac{1}{m-1}})-\sqrt{D_{1}}}{2||(-q)_{+}||_{\infty}^{\frac{1}{m-1}}}$
$\displaystyle\leq\frac{||z-u||_{\infty}}{||z||_{\infty}}$
$\displaystyle\leq\frac{(\max_{i\in[n]}\\{a_{ii\cdots
i}\\})^{\frac{1}{m-1}}(||v_{1}||_{\infty}(1+(\max_{i\in[n]}\\{a_{ii\cdots
i}\\})^{\frac{1}{m-1}})+\sqrt{D_{1}})}{2\min_{i\in[n]}\\{(a_{ii\cdots
i})^{\frac{1}{m-1}}\\}||(-q)_{+}||_{\infty}^{\frac{1}{m-1}}}$

where
$v_{1}=u-\max\\{0,u-[(\mathcal{A}(u-z)^{m-1})^{[\frac{1}{m-1}]}+(\mathcal{A}z^{m-1}+q)^{[\frac{1}{m-1}]}]\\}$,
$D_{1}=||v_{1}||_{\infty}^{2}(1+(\max_{i\in[n]}\\{a_{ii\cdots
i}\\})^{\frac{1}{m-1}})^{2}-4(\min_{i\in[n]}\\{(a_{ii\cdots
i})^{\frac{1}{m-1}})v_{t}^{2}\geq 0$ and $t$ satisfies
$\max_{i\in[n]}\\{(u-z)_{i}(\mathcal{A}(u-z)^{m-1})_{i}\\}=(u-z)_{t}(\mathcal{A}(u-z)^{m-1})_{t}\geq
0$ and $v_{t}\neq 0$.

###### Proof.

Let $\mathcal{A}\in T_{m,n}$ be a positive diagonal tensor and
$z\in\mathbb{R}^{n}$ be a solution of TCP$(q,\mathcal{A})$ and let $u$ be an
arbitrary vector in $\mathbb{R}^{n}.$ Then by Theorem 3.4, the inequations
(3.20) and (3.21) hold. Since $(-q)_{+}\neq 0$ and $z\neq 0$ from (3.20) we
have

$\frac{(\max_{i\in[n]}\\{a_{ii\cdots
i}\\})^{\frac{1}{m-1}}}{||(-q)_{+}||_{\infty}^{\frac{1}{m-1}}}\leq\frac{1}{||z||_{\infty}}\leq\frac{\min_{i\in[n]}\\{(a_{ii\cdots
i})^{\frac{1}{m-1}}\\}}{||(-q)_{+}||_{\infty}^{\frac{1}{m-1}}}.$ (3.23)

Now combining inequations (3.21) and (3.23) we obtain

$\displaystyle\frac{||v_{1}||_{\infty}(1+(\max_{i\in[n]}\\{a_{ii\cdots
i}\\})^{\frac{1}{m-1}})-\sqrt{D_{1}}}{2||(-q)_{+}||_{\infty}^{\frac{1}{m-1}}}$
(3.24) $\displaystyle\leq\frac{||z-u||_{\infty}}{||z||_{\infty}}$ (3.25)
$\displaystyle\leq\frac{(\max_{i\in[n]}\\{a_{ii\cdots
i}\\})^{\frac{1}{m-1}}(||v_{1}||_{\infty}(1+(\max_{i\in[n]}\\{a_{ii\cdots
i}\\})^{\frac{1}{m-1}})+\sqrt{D_{1}})}{2\min_{i\in[n]}\\{(a_{ii\cdots
i})^{\frac{1}{m-1}}\\}||(-q)_{+}||_{\infty}^{\frac{1}{m-1}}}.$ (3.26)

∎

Here we give an numerical example to illustrate the result.

####  Numerical Example

Consider the tensor $\mathcal{A}\in T_{4,2}$ such that
$a_{1111}=1,\;a_{2222}=8.$ For $z=\left(\begin{array}[]{c}z_{1}\\\
z_{2}\end{array}\right)\in\mathbb{R}^{2},$
$\mathcal{A}z^{2}=\left(\begin{array}[]{c}z_{1}^{3}\\\
8z_{2}^{3}\end{array}\right).$ Then $\mathcal{A}$ is a $P$-tensor. Let
$q=\left(\begin{array}[]{c}1\\\ -1\end{array}\right).$ Then the
TCP$(q,\mathcal{A})$ is to find $z\in\mathbb{R}^{2}$ such that

$z\geq 0,\;\;\mathcal{A}z^{3}+q\geq 0,\;\;z^{T}(\mathcal{A}z^{3}+q)=0.$ (3.27)

Solving (3.27) we have $z=\left(\begin{array}[]{c}0\\\ .5\end{array}\right).$
Then $\mathcal{A}z^{3}=\left(\begin{array}[]{c}0\\\ 1\end{array}\right),$
$\mathcal{A}z^{3}+q=\left(\begin{array}[]{c}1\\\ 0\end{array}\right)$ and
$(\mathcal{A}z^{3}+q)^{\frac{1}{3}}=\left(\begin{array}[]{c}1\\\
0\end{array}\right).$ Now $||\mathcal{A}||_{\infty}=\max\\{1,8\\}=8$,
therefore $||\mathcal{A}||_{\infty}^{\frac{1}{3}}=2.$ Consider
$u\in\mathbb{R}^{n}$ such that $u=\left(\begin{array}[]{c}0.5\\\
0.4\end{array}\right).$ Then $u-z=\left(\begin{array}[]{c}0.5\\\
0.4\end{array}\right),$ $\mathcal{A}(u-z)^{3}=\left(\begin{array}[]{c}0.125\\\
0.008\end{array}\right)$ and
$(\mathcal{A}(u-z)^{3})^{\frac{1}{3}}=\left(\begin{array}[]{c}0.5\\\
0.8\end{array}\right).$ Then
$v=u-\max\\{0,(\mathcal{A}(u-z)^{3})^{[\frac{1}{3}]}+(\mathcal{A}z^{3}+q)^{[\frac{1}{3}]}-u\\}=$
$\left(\begin{array}[]{c}0.5\\\ 0.4\end{array}\right)$ and
$||v||_{\infty}=\max\\{0.5,0.4\\}=0.5.$ Now

$\max_{i\in[2]}\\{(u-z)_{i}(\mathcal{A}(u-z)^{3})_{i}\\}=\\{0.625,\;0.0008\\}=0.625,$
(3.28)

and the maximum occurs at $i=1$. Therefore $t=1$ and $v_{t}=v_{1}=0.5\;(\neq
0).$ Also

$F_{\mathcal{A}}(z)=(\mathcal{A}z)^{\frac{1}{3}}=\left(\begin{array}[]{c}z_{1}\\\
2z_{2}\end{array}\right).$

Therefore $\alpha(F_{\mathcal{A}})=\min\\{1,2\\}=1.$ Now

$\displaystyle D$ $\displaystyle=(0.5)^{2}\cdot(1+2)^{2}-4\cdot 1\cdot(0.5)$
$\displaystyle=0.25>0.$

Then upper bound of the error is
$UB_{AKD}=\frac{0.5\cdot(1+2)+\sqrt{0.25}}{2\cdot 1}=1$ and the lower bound is
$LB_{AKD}=\frac{0.5\cdot(1+2)-\sqrt{0.25}}{2\cdot 1}=0.5.$ But according to
Theorem 2.4 proposed by Zheng et al. in [47] the upper bound is
$UB=\frac{(1+2)\cdot 2}{0.5}=1.5$ and the lower bound is
$LB=\frac{1}{1+2}\cdot(0.5)=0.1667.$ Thus we see that $UB_{AKD}<UB$ and
$LB<LB_{AKD}.$ Hence our error bound is improved.

Obviously when $D\mapsto 0$ the error bounds get better. Now we show that the
error bound in Theorem 3.2 is better than that of in Theorem 2.4.

Here we are showing that our proposed error bound is sharper that the error
bound proposed by Zheng et al. [47].

###  Comparison of upper bounds:

The upper bound of error from inequation (2.6) is
$UB=||\tilde{v}||_{\infty}\cdot\frac{1+||\mathcal{A}||_{\infty}^{\frac{1}{m-1}}}{\alpha(F_{\mathcal{A}})}$
and the upper bound of error from inequation (3.4) is
$UB_{AKD}=\frac{||v||_{\infty}(1+||\mathcal{A}||_{\infty}^{\frac{1}{m-1}})+\sqrt{D}}{2\alpha(F_{\mathcal{A}})}.$
Now we have
$D=||v||_{\infty}^{2}(1+||\mathcal{A}||_{\infty}^{[\frac{1}{m-1}]})^{2}-4\alpha(F_{\mathcal{A}})v_{t}^{2}\geq
0$ i.e.,
$4\alpha(F_{\mathcal{A}})v_{t}^{2}=||v||_{\infty}^{2}(1+||\mathcal{A}||_{\infty}^{[\frac{1}{m-1}]})^{2}-D\geq
0,$ since $\alpha(F_{\mathcal{A}})\geq 0.$ Therefore

$(1+||\mathcal{A}||_{\infty}^{[\frac{1}{m-1}]})\geq\sqrt{\frac{D}{||v||_{\infty}^{2}}}.$
(3.29)

Note that by construction we have $||v||\leq||\tilde{v}||.$ By taking the
ratio of the upper bounds we obtain,

$\displaystyle\frac{UB_{AKD}}{UB}=\frac{\frac{||v||_{\infty}(1+||\mathcal{A}||_{\infty}^{\frac{1}{m-1}})+\sqrt{D}}{2\alpha(F_{\mathcal{A}})}}{||\tilde{v}||_{\infty}\cdot\frac{1+||\mathcal{A}||_{\infty}^{\frac{1}{m-1}}}{\alpha(F_{\mathcal{A}})}}\leq$
$\displaystyle\frac{(1+||\mathcal{A}||_{\infty}^{\frac{1}{m-1}})+\sqrt{\frac{D}{||v||_{\infty}^{2}}}}{2(1+||\mathcal{A}||_{\infty}^{\frac{1}{m-1}})}$
$\displaystyle\leq$
$\displaystyle\frac{(1+||\mathcal{A}||_{\infty}^{\frac{1}{m-1}})+(1+||\mathcal{A}||_{\infty}^{\frac{1}{m-1}})}{2(1+||\mathcal{A}||_{\infty}^{\frac{1}{m-1}})}=1\mbox{
by (\ref{equation for alg exp})}.$

##  Conclusion

In this article we introduce an error bound for the solution of tensor
complementarity problem TCP$(q,\mathcal{A})$ given that $\mathcal{A}$ is a
$P$-tensor and $q$ is a real vector. We establish a relative error bound for
TCP with $P$-tensor. We find the value of $\alpha(F_{\mathcal{A}})$ for even
order positive diagonal tensor. We establish absolute and relative error bound
for TCP$(q,\mathcal{A})$ where $\mathcal{A}$ is an even order positive
diagonal tensor. We prove that our proposed upper bound is sharper than the
earlier upper bound of absolute error available in the literature. One
numerical example is illustrated to support our result.

##  Acknowledgment

The author R. Deb is thankful to the Council of Scientific $\&$ Industrial
Research (CSIR), India, Junior Research Fellowship scheme for financial
support. The author A. Dutta is thankful to the Department of Science and
technology, Govt. of India, INSPIRE Fellowship Scheme for financial support.

## References

  * [1] Xue-Li Bai, Zheng-Hai Huang, and Yong Wang.  Global uniqueness and solvability for tensor complementarity problems.  Journal of Optimization Theory and Applications, 170(1):72–84, 2016\.
  * [2] N Bose and A Modarressi.  General procedure for multivariable polynomial positivity test with control applications.  IEEE Transactions on Automatic Control, 21(5):696–701, 1976.
  * [3] Maolin Che, Liqun Qi, and Yimin Wei.  Positive-definite tensors to nonlinear complementarity problems.  Journal of Optimization Theory and Applications, 168(2):475–487, 2016.
  * [4] RW Cottle, JS Pang, and RE Stone.  The linear complementarity problem.  SIAM, 2009.
  * [5] AK Das.  Properties of some matrix classes based on principal pivot transform.  Annals of Operations Research, 243(1):375–382, 2016.
  * [6] AK Das, R Jana, and Deepmala.  On generalized positive subdefinite matrices and interior point algorithm.  In International Conference on Frontiers in Optimization: Theory and Applications, pages 3–16. Springer, 2016.
  * [7] AK Das, R Jana, and Deepmala.  Finiteness of criss-cross method in complementarity problem.  In International Conference on Mathematics and Computing, pages 170–180. Springer, 2017.
  * [8] AK Das, R Jana, and Deepmala.  Invex programming problems with equality and inequality constraints.  Transactions of A. Razmadze Mathematical Institute, 172(3):361–371, 2018.
  * [9] AK Das, R Jana, and Deepmala.  Some aspects on solving transportation problem.  Yugoslav Journal of Operations Research, 30(1):45–57, 2019.
  * [10] Weiyang Ding, Ziyan Luo, and Liqun Qi.  P-tensors, p0-tensors, and their applications.  Linear Algebra and its Applications, 555:336–354, 2018.
  * [11] A Dutta and AK Das.  On some properties of $k$-type block matrices in the context of complementarity problem.  arXiv preprint arXiv:2109.09549, 2021.
  * [12] A Dutta, R Jana, and AK Das.  On column competent matrices and linear complementarity problem.  In Proceedings of the Seventh International Conference on Mathematics and Computing, pages 615–625. Springer Singapore, 2022.
  * [13] Francisco Facchinei and Jong-Shi Pang.  Finite-dimensional variational inequalities and complementarity problems.  Springer Science & Business Media, 2007.
  * [14] M Seetharama Gowda, Ziyan Luo, Liqun Qi, and Naihua Xiu.  Z-tensors and complementarity problems.  arXiv preprint arXiv:1510.07933, 2015.
  * [15] Mohammed A Hasan and Ali A Hasan.  A procedure for the positive definiteness of forms of even order.  IEEE Transactions on Automatic Control, 41(4):615–617, 1996.
  * [16] Zheng-Hai Huang, Yun-Yang Suo, and Jie Wang.  On ${Q}$-tensors.  arXiv preprint arXiv:1509.03088, 2015.
  * [17] R Jana, AK Das, and A Dutta.  On hidden ${Z}$-matrix and interior point algorithm.  Opsearch, 56(4):1108–1116, 2019.
  * [18] R Jana, AK Das, and VN Mishra.  Iterative descent method for generalized leontief model.  Proceedings of the National Academy of Sciences, India Section A: Physical Sciences, 91(2):237–244, 2021.
  * [19] R Jana, AK Das, and S Sinha.  On processability of Lemke’s algorithm.  Applications & Applied Mathematics, 13(2), 2018.
  * [20] R Jana, AK Das, and S Sinha.  On semimonotone star matrices and linear complementarity problem.  arXiv preprint arXiv:1808.00281, 2018.
  * [21] R Jana, A Dutta, and AK Das.  More on hidden ${Z}$-matrices and linear complementarity problem.  Linear and Multilinear Algebra, 69(6):1151–1160, 2021.
  * [22] E Jury and M Mansour.  Positivity and nonnegativity conditions of a quartic equation and related problems.  IEEE Transactions on Automatic Control, 26(2):444–451, 1981.
  * [23] Ziyan Luo, Liqun Qi, and Naihua Xiu.  The sparsest solutions to ${Z}$-tensor complementarity problems.  Optimization letters, 11(3):471–482, 2017.
  * [24] SR Mohan, SK Neogy, and AK Das.  More on positive subdefinite matrices and the linear complementarity problem.  Linear Algebra and its Applications, 338(1-3):275–285, 2001.
  * [25] SR Mohan, SK Neogy, and AK Das.  On the classes of fully copositive and fully semimonotone matrices.  Linear Algebra and its Applications, 323(1-3):87–97, 2001.
  * [26] SR Mohan, SK Neogy, and AK Das.  A note on linear complementarity problems and multiple objective programming.  Mathematical programming, 100(2):339–344, 2004.
  * [27] P Mondal, S Sinha, SK Neogy, and AK Das.  On discounted ARAT semi-markov games and its complementarity formulations.  International Journal of Game Theory, 45(3):567–583, 2016.
  * [28] SK Neogy, RB Bapat, and AK Das.  Optimization models with economic and game theoretic applications.  Annals of Operations Research, 243(1):1–3, 2016.
  * [29] SK Neogy and AK Das.  Linear complementarity and two classes of structured stochastic games.  Operations Research with Economic and Industrial Applications: Emerging Trends, eds: SR Mohan and SK Neogy, Anamaya Publishers, New Delhi, India, pages 156–180, 2005.
  * [30] SK Neogy and AK Das.  On almost type classes of matrices with ${Q}$-property.  Linear and Multilinear Algebra, 53(4):243–257, 2005.
  * [31] SK Neogy and AK Das.  Principal pivot transforms of some classes of matrices.  Linear algebra and its applications, 400:243–252, 2005.
  * [32] SK Neogy and AK Das.  Some properties of generalized positive subdefinite matrices.  SIAM journal on matrix analysis and applications, 27(4):988–995, 2006.
  * [33] SK Neogy and AK Das.  Mathematical programming and game theory for decision making, volume 1.  World Scientific, 2008.
  * [34] SK Neogy and AK Das.  Generalized monotone maps and complementarity problems.  In Topics in Nonconvex Optimization, pages 27–46. Springer, 2011\.
  * [35] SK Neogy and AK Das.  On singular ${N_{0}}$-matrices and the class ${Q}$.  Linear algebra and its applications, 434(3):813–819, 2011.
  * [36] SK Neogy and AK Das.  On weak generalized positive subdefinite matrices and the linear complementarity problem.  Linear and Multilinear Algebra, 61(7):945–953, 2013.
  * [37] SK Neogy, AK Das, and RB Bapat.  Modeling, computation and optimization, volume 6.  World Scientific, 2009.
  * [38] SK Neogy, AK Das, and A Gupta.  Generalized principal pivot transforms, complementarity theory and their applications in stochastic games.  Optimization Letters, 6(2):339–356, 2012.
  * [39] SK Neogy, AK Das, S Sinha, and A Gupta.  On a mixture class of stochastic game with ordered field property.  In Mathematical programming and game theory for decision making, pages 451–477. World Scientific, 2008.
  * [40] Liqun Qi.  Eigenvalues of a real supersymmetric tensor.  Journal of Symbolic Computation, 40(6):1302–1324, 2005.
  * [41] Liqun Qi and Ziyan Luo.  Tensor analysis: spectral theory and special tensors.  SIAM, 2017.
  * [42] Yisheng Song and Liqun Qi.  Properties of tensor complementarity problem and some classes of structured tensors.  arXiv preprint arXiv:1412.0113, 2014.
  * [43] Yisheng Song and Liqun Qi.  Error bound of p-tensor nonlinear complementarity problem.  arXiv preprint arXiv:1508.02005, 2015.
  * [44] Yisheng Song and Liqun Qi.  Properties of some classes of structured tensors.  Journal of Optimization Theory and Applications, 165(3):854–873, 2015.
  * [45] Yisheng Song and Liqun Qi.  Tensor complementarity problem and semi-positive tensors.  Journal of Optimization Theory and Applications, 169(3):1069–1078, 2016.
  * [46] Yisheng Song and Gaohang Yu.  Properties of solution set of tensor complementarity problem.  Journal of Optimization Theory and Applications, 170(1):85–96, 2016\.
  * [47] Mengmeng Zheng, Ying Zhang, and Zheng-Hai Huang.  Global error bounds for the tensor complementarity problem with a p-tensor.  Journal of Industrial & Management Optimization, 15(2):933, 2019\.


#  An Informed Model of Personal Information Release in Social Networking
Sites

Anna Squicciarini  College of Information Science and Technology
Penn State University
University Park, PA 16802
E-mail<EMAIL_ADDRESS>Christopher Griffin  Applied Research Laboratory
Penn State University
University Park, PA 16802
E-mail<EMAIL_ADDRESS>
###### Abstract

The emergence of online social networks and the growing popularity of digital
communication has resulted in an increasingly amount of information about
individuals available on the Internet. Social network users are given the
freedom to create complex digital identities, and enrich them with truthful or
even fake personal information. However, this freedom has led to serious
security and privacy incidents, due to the role users’ identities play in
establishing social and privacy settings.

In this paper, we take a step toward a better understanding of online
information exposure. Based on the detailed analysis of a sample of real-world
data, we develop a deception model for online users. The model uses a game
theoretic approach to characterizing a user’s willingness to release, withhold
or lie about information depending on the behavior of individuals within the
user’s circle of friends. In the model, we take into account both the
heterogeneous nature of users and their different attitudes, as well as the
different types of information they may expose online.

##  I Introduction

Online social networks (OSNs) such as Facebook, Myspace, and Google+ allow
individuals to present themselves and establish or maintain connections with
others. Users articulate their social networks by creating and managing
content, social connections, and a possibly large amount of personal
information. A typical OSN in fact allows users to create connections to
friends , thereby sharing with them a wide variety of personal information.
These connections are often based on the alleged identities and properties of
the individuals populating the OSN. Users of social media sites can, however,
generate accounts containing unverified information. On the one hand, this
allows the users to avoid identification and surveillance or observation of
any kind. On the other one, the ability to generate unverified accounts on
most of these sites, renders social relationships potentially weak, if based
on fake identities. Further, unverified accounts may and are often used by
malicious users to carry out disruptive activities hidden behind fake
identities [10]. To date, while some work has studied the incentives behind
information disclosures in OSNs [9, 26, 18], little is known about identities
misrepresentations.

In this paper, we speculate that information revelation in OSN is a complex
process where multiple contrasting influences are in play: not only privacy
attitudes, but also social pressure and personal attitudes are at stake.
Focusing on three types of users’ behavior related to information revelation:
truthful information sharing, information withholding and deception, we study
the effect of misrepresentation in these environments by means of a game
theoretical model.

To ground our model, we conducted an extensive empirical study, collecting
data about users’ common behavior and their attitude toward personal
information disclosure. The study involved almost 300 subjects, all active
social network users.

Our study reveals important insights on users’ attitudes and practices. In
particular, our results show that users’ decisions to lie or withhold
information are not strongly influenced by privacy concerns. Rather, results
show strong correlations between peer-pressure and attitudes toward lying.
Users who feel peer-pressured are less likely to withhold their information,
especially their whereabouts. The quest for gaining or maintaining popularity
also seems to play an important role, in particular with respect to the amount
of information users choose to reveal. Also, we identified that users’
identity information is managed differently depending upon the perceived
sensitivity of the information. For example, for basic demographic
information, users tend not to lie in the main social network account, as this
is typically revealed in the course of social interactions and may be easy to
verify by social network peers. On the other hand, information that is closer
to the users’ personal sphere, for example, social relationships, whereabouts,
etc. is revealed mostly by users who are in search or popularity and/or are
searching for self-affirmation in the network. In addition, we find that
misrepresentation interacts with measures of morality, suggesting that users
do not associate lies in social networks with unethical behavior, and that,
where lying is considered unethical, they are more likely to withhold
information, as a form of boundary control. Finally, we found that users’
behavior is mostly influenced by inner circles of close online friends,
regardless of the actual number of social connections users have.

The analysis of the responses is used as input to inform our qualitative model
of user information sharing, withholding and deception. In particular,
building on the finding that users treat information differently, the model
presupposes that individuals release, withhold or lie about certain classes of
information differently, and that each user behaves according to an individual
payoff function. The payoff function is constructed to take into account the
identified influential decision factors: morality, peer pressure, privacy and
popularity. The output of the function is also affected by the behavior of a
circle of close friends - as we found strong evidence of self-validation and
peer influence in our study. We provide an example model using evolutionary
dynamics, which we posit influences a users’ behavior as he interacts with his
OSN overtime and more accurately understands the true nature of his (personal)
objective function.

The paper is organized as follows. Next section reviews relevant literature.
Section III discusses our empirical study. Section IV presents our model. We
illustrate the various types of users and information in our examples in
Section V. We conclude the paper in Section VI with pointers to future
research directions.

##  II Literature review

Digital identity constitutes one of the building blocks of Web 2.0
technologies, ranging from social networking to e-commerce. Problems related
to digital identity management and protection have been tackled by both the
computer science community and by information scientists. From the
computational standpoint, a variety of digital identity and trust management
mechanisms have been developed to allow users to create and maintain complex
digital personas [3, 9] although there has been little work on the topic of
digital identity validation and trust in the context of social computing.

From a social science perspective, various studies have explored identity
sharing behavior in social network sites and the risk of over exposure
(notable examples are [9, 26, 2, 18]). Research studies have shown that users
in online environments rely on a variety of cues to make determinations about
one another; however, all these cues are not deemed equally credible. For
instance, Goffman [12] notes that identity cues can be intentionally given or
unintentionally revealed, and that humans are more likely to place greater
weight on those cues that are perceived to be unintentional as opposed to
strategically constructed. This ability to engage in deceptive self-
presentation online is compounded when users do not share a social network and
therefore have less access to information triangles such as mutual friends who
might confirm or deny information. Donath [10] argues that a shared social
network can provide explicit or implicit verification of identity claims.
Therefore, as highlighted in [18], a highly connected network such as Facebook
should encourage more truthful profiles, or misrepresentations that are
playful or ironic as opposed to being intentionally deceitful.

Burke et al. [7] studied user motivations for contributing in social
networking sites, based on server log data from Facebook. They found that
newcomers who see their friends contributing go on to share more content
themselves. Furthermore, those who were initially inclined to contribute,
receiving feedback and having a wide audience, were also predictors of
increased sharing.

Complementary to the body of work on identification and information
revelation, is the work on anonymity in social network sites [27, 5, 19]. The
emphasis in these works is however on algorithmic approaches for non-
disclosure and anonymity preservation, rather than on actual revelation.
Finally, parallel to this body of work is the work on reputation [29, 14].
Reputation of digital identities and trust in online environments have been
investigated by multiple research communities ranging from computer science
[22] to economics [6, 24].

With respect to our methodology, our work employs analytical models.
Analytical models for various security topics based on game, information and
decision theories are rapidly growing in interest [15]. In particular, game
theoretic approaches to reputation and trust first emerged in the economics
literature (a typical example is [11]) and were then applied to online
settings [1, 17, 21]. However, to the best of our knowledge, the only work
analyzing social identities using analytical tools is from Alpcan and
colleagues [4]. Alpcan’s work focuses on reputation and trust, where
strategies are defined in terms of opinion, quantified through a simple cost
function. As we discuss in the next sections, our focus is on validation and
individual attitudes toward deception, rather than lies. Additionally, an
interesting economically inspired work dealing with users’ privacy is
discussed by Papadimitrous and colleagues [17], who propose a precise estimate
of the value of the private information disclosed by a set of individuals, and
a compensation for such information release that may induce users to release
richer information. Yet, the model applies to a different set of applications,
such as online surveys and e-commerce applications.

This work is part of our research effort on deception and information
revelation in social networking sites. In [25] we studied the interaction of
users and servers at the time of user registration, and used a game
theoretical framework to describe a simple two-player general sum game
describing the behavior of a server system (like Facebook) that provides
utility to user. We showed that in the presence of a binding agreement to
cooperate, most players will agree to share information. In [13], we
investigated a simpler game model in which rewards for releasing information
and costs for withholding information and lying were represented by
arbitrarily chosen concave and convex functions. We showed for a specific
instance of a payoff function that a symmetric Nash equilibria existed and was
related to the automorphism class of the graph describing the interaction
graph of the social network. This work substantially extends our previous work
by more accurately modeling the qualitative nature of the user’s objective
function through the incorporation of information in our survey. Our previous
work was purely theoretical, and used a overly simplified the notion of
identity. Identity was mainly considered as an atomic value, and therefore was
focused on different aspects of information sharing in social networking sites
(for example the registration of new users). We also incorporate a model of
evolutionary dynamics to explain a user’s choices as he interacts with his
social network and is exposed to his friend’s choices.

##  III Informing the model through an exploratory study

In order to understand typical social network users’ attitudes and actions
with respect to information disclosure, we conducted an exploratory study
using real-world data. The specific aim of our study was to gain a deeper
understanding of users identity-revealing actions, the peculiar features of
average users, and the perceived understanding of identity on social sites.

###  III-A Methods

We conducted a web-based survey, collecting a total of 296 responses.
Respondents were recruited from two different undergraduate courses in the
college of Information Science and Technology at the Pennsylvania State
University. One extra credit point for the course was awarded for their
participation in the study. The survey was constructed to study three specific
aspects of users’ behavior: (1) privacy awareness, (2) attitude toward
information withholding and practices (3) attitude toward lies and
misrepresentation.

The respondents were aged between 20 and 35 ($\mu$=23, sd=2.34). The
respondents were 65% male and 35% female. 99.3% of them declared to have at
least one account on social sites, and 12% declared to have more than one
account on the same OSN. Participants were asked to indicate the social
network they most often accessed: 95.3% most often accessed Facebook, while
the remaining participants were distributed among Google+, Linkedin (6%) and
Twitter. In terms of network usage frequency, 94% of the respondents accessed
social network sites at least once a week, and 83.6% of those were daily
users.

Considering that Facebook is one of the social networks that most heavily
promotes personal information disclosure, our sample was deemed appropriate
for this study. While the overall sample reflects a specific subset of the
population, we notice that most of the active users in Facebook, according to
recent statistics, are below 26 years old (and specifically in the 21-24 age
range) 111http://www.socialbakers.com/facebook-statistics.

The instrument also included five broad types of measures of perceived
privacy, social pressure, and popularity (or social capital), which serve as
dependent variables.

###  III-B Measures

  * •

Deception was our independent measure, and was measured by two sets of 4 items
each. The first set focused on deceptive activities, and was measured on a a
frequency rating scale (1=all of the time to 5=never). The second set of items
related to the perception about deception (lies and withholding information on
social networking sites). An example item is “Lying in social network is
unethical”. These items were also rate using a Likert scale (5-point rating
scale, where 1= strongly agree and 5=strongly disagree).

  * •

Usage was measured using 6 different items. Three of the items where focused
on frequency of usage and number of connections. The remaining items where
added to ascertain the extent to which the participant engages in certain
types of social interactions, e.g., posting images, giving feedback to other’s
posts or images, sharing a url, tagging a video or an image. For these items,
we used a frequency rating scale (1=never to 5=once or a few times a day)

  * •

Privacy Concerns. Individual differences in privacy perceptions can be
significant [30, 32]. Thus, we need to establish a baseline understanding
about the awareness of and attitudes toward privacy protection by
participants. In our survey, we included five questions to ask participants
about their information disclosure behaviors and privacy concerns in Social
Networking sites (Cronbach $\alpha=.71)$, rated on a Likert scale (5-point
rating scale, where 1= strongly agree and 5=strongly disagree). An example
item is ”I have had concerns about the privacy of my data on Social Networks”.

  * •

Pressure was measured using 5 items (Cronbach $\alpha=.823$), focusing on
pressure of updating information (e.g. “I feel peer pressured to constantly
update my Social Network profile”) and uploading content. The items measured
perceived pressure from the social networking and from peers (e.g. “I need to
update my profile often to be popular among my friends”).

  * •

Perceived Popularity was measured by 6 items (Cronbach $\alpha=.732$),
focusing on the impact on one’s popularity (or social capital) upon passively
being involved in the social interactions listed in the usage measures.

ID |  Question | Average | Standard Dev.
---|---|---|---
Q1 |  I have put false information in my main social network account (1=strongly agree, 5=strongly disagree) | 1.87 | 0.4
Q2 |  I have withheld information from my main social network account (1=strongly agree, 5=strongly disagree) | 1.91 | 0.732
Q3 |  Putting false information about myself and my whereabouts on my profile can help me be more popular | 2.45 | 0.453
TABLE I: Descriptive Variables concerning Deceptive activities

###  III-C Findings

The main purpose of this study was to examine users attitudes towards
deception in social networking sites.

Leveraging results from previous research studies [10, 18], we hypothesized
that (h1) users in fact deceive in social networking sites, but mostly choose
to portray truthful portions of their basic identity, which could be validated
offline (e.g. the name or gender), and deceive or withhold information which
may be deemed too personal or inappropriate for disclosure to the social
network audience. We also hypothesized that participants decision to withhold
information or lie would be influenced by (h2) their privacy inclination, (h3)
their perceived pressure to be active on the social network site and (h4)
their wish to be popular among peers. Finally, we were interested in learning
whether users’ decision to withhold or lie would be connected with ethical
choices. Here, we did not have an initial hypothesis, but were interested in
exploring the correlations between morality and deception. We discuss our
results in a detailed manner in the following.

####  III-C1 h1: Frequency of Deception

We began with identifying whether deception is in fact significant. Table I
presents the descriptive statistics of some of the study’s variables related
to deception. As reported, a vast majority of the participants admit to having
lied at least once, and also chose to withhold information (94% of respondents
either agree or strongly agreed to have lied -the exact statistics are
reported in the table). Figure 1 highlights the specific types of attributes
users most often lie about. We further determined that users who are more
likely to be involved in discussions and are therefore active in the social
networking site report a lower frequency of lying (Pearson r=0.277, p=0.033),
therefore reinforcing the well-known signaling theory identified by Donath
[10]. The relationship with the “withholding question” shows a similar trend,
but it is not statistically significant, therefore a conclusive statement on
this relationship is not possible. Users also report it is easy to detect lies
of their close social connections with whom they often interact with
($\mu=2.61$, sd. 0.912), again confirming that self-validation is effective in
social networking sites.

Figure 1: Data Items most frequently misrepresented

####  III-C2 h1: Types of Information Revealed

To further explore which pieces of information users are likely to withhold or
lie about, we asked users to indicate their preferred action for six different
personal pieces of information: location, gender, GPA, relationship status,
telephone number, current occupation. We select properties that would be
considered important and potentially sensitive for our participants, who were
mostly students. Users were given the option to indicate for each attribute
one of three choices: tell the truth, provide false information, do not put
anything.

Figure 2: Responses breakdown by attribute

The responses, organized by attribute, are reported in Figure 2. In our
survey, most of the participants claimed to misrepresent only specific pieces
of information. In particular, our analysis confirms that highly
interconnected users are likely to reveal basic identity properties, such as
gender, age, etc. truthfully (Pearson .436, r=0.012). Information commonly
deemed as private, such as telephone number and GPA, is instead mostly
withheld, or misrepresented. Finally, there is some interesting variability
with respect to location, current occupation and relationship status, where
there is not a predominant choice. These results confirm our hypothesis (h1).

####  III-C3 Influential factors of information sharing

The analysis of the factors influencing information sharing activities
resulted in the following findings.

  * •

h2: Privacy We first analyzed the responses related to privacy awareness, to
get a sense of the respondents attitude toward information revelation and
leakage in social networking sites. An initial notable result is that, despite
the fact that most respondents maintained a detailed profile on their favorite
social network site, many of them also demonstrated relatively high levels of
privacy concern. The responses to the statement “I maintain a detailed profile
on my main social network account” confirm that they maintain rich profiles
($\mu$=1.97, std=0.96), and that they reveal their main identity for the most
part ($\mu$=2.01, std=0.45). Nevertheless, their responses to the statement
“There is a high potential for loss involved in sharing personal information
on Social Networks like Facebook” indicate their awareness of potential
information leakage ($\mu=1.80$, std=0.81). We then tested our first
hypothesis, i.e. whether lying or withholding information was related at all
to the respondents level of privacy awareness. We conducted an exploratory
least-squares multiple regression analysis, regressing their responses to
question Q1, with their responses related to privacy concerns as predictors.
None of these appeared to be strongly related.

The results lead to interesting findings. First, in general participants are
concerned with their privacy on social networking sites and are aware of the
potential loss of privacy; second, the results confirm the existence of
phenomenon known as the privacy paradox [31], in which individuals state that
they have privacy concerns, but behave in ways that seemingly contradict these
statements by providing detailed information about themselves. Finally, our
results show that privacy is not indicative of their choice to deceive, or
withhold information.

  * •

h3: Pressure Next, we investigated whether participants feeling peer pressured
are more likely to deceive or withhold information. We first tested whether
feeling peer pressured would be correlated with the amount of personal
information displayed on the social network site. We conducted a simple
regression analysis, using the answer to the question “I feel peer pressured
to constantly update my profile” as an independent variable, and their self-
declared level of detailed social network profile as a dependent variable. The
test shows that the more users agree to feeling pressured to update their
profile, the more they claim to display a detailed profile (Pearson r=0.433,
p=.034). We then studied whether the information being revealed upon being
pressured is truthful or not. We correlated Q1 and Q2 with our items related
to popularity. Our results show that there is not a significant correlation
between users’ perceived peer-pressure and their choice to deceive. However,
there is a clear correlation between their choice to withhold information and
their feeling of being peer pressured (Pearson r=0.163, p=0.03). That is to
say, the more users feel peer pressured, the less likely they are to withhold
information.

  * •

h4: Popularity When correlated with measures relative to popularity, we
obtained the following results. First, we correlated participants’ frequency
of sharing content (e.g., images) in the social networking site with their
perceived popularity gain by doing so. We obtained a significant correlation
(Pearsons r=0.272, p=.032). In line with previous studies in this space [18],
this finding shows that the more users perceive certain social interactions to
benefit their social capital, the more likely they are to pursue them. With
respect to deception, the majority of participants disagreed to have lied to
gain popularity or portray a different “self” (only 25% of respondents either
agreed or strongly agreed to the question ”I have put false information to
appear different from my original self”). However, we discovered a significant
correlation between their quest for popularity and their deceptive activities
(Pearson r=-0.2449, r=0.015), therefore confirming our hypothesis.

ID |  Question | Avg | St. Dev.
---|---|---|---
Q4 |  I consider lying in social network sites unethical | 3.30 | 0.943
Q5 |  I consider withholding information in social network sites unethical | 4.10 | 0.842
TABLE II: Morality and Deception (Likert Scale: 1=strongly agree, 5=strongly
disagree)

In summary, this study confirms that a social network user’s tendency to
deceive for certain data types is highly correlated with his or her desire to
portray a successful social image, and not statistically related to privacy
concerns. In other terms, the perceived usefulness of the social network
service increases online users willingness to disclose their personal
information.

Figure 3: Linear regression for questions correlating Q1 and Q4 (z(x)) and Q1
and Q5 (y(x))

####  III-C4 Morality in Social Networking Sites

Our results show non-obvious relation between lying or withholding information
on a social networking site and morality.

The results of correlating social network lying (corresponding to Q1) with Q4
and Q5 are interesting, as they show opposite effects of thinking that lying
on a social network is unethical and withholding information on a social
network is unethical. A higher value for Q4 (meaning an individual disagrees
that lying is unethical) predicts a higher frequency of putting up false
information on a social networking site (Q1). However, a higher value for the
withholding information questions (Q5) predicts a lower frequency of putting
up false information. The linear equations obtained through regression
analysis are reported in Figure 3. This result seems to reinforce the notion
that lying on a social networking website and withholding information function
as two completely different actions and that a user will choose one or the
other based on an internal utility function.

ID |  Question |  Scale | Avg | St. Dev.
---|---|---|---|---
Q7 |  How many friends do you think typically check your profile |  1=“$>$150”, 2=[100,150], 3=[50,100], 4=$<$50 | 3.63 | 0.658
Q8 |  How many friends do you check typically |  1=“$>$150”, 2=[100,150], 3=[50,100], 4=$<$50 | 3.53 | 0.760
Q9 |  How many social connections do you have? |  1=“$>$150”, 2=[100,150], 3=[50,100], 4=“$<$50” | 1.48 | .901
Q10 |  How often do you visit your favorite social network site? |  1=Once or a few times a day 2=Once or a few times a week 3= Once or a few times a month 4= Never | 1.21 | .464
TABLE III: Social network usage

####  III-C5 Inner Circles

Some other interesting findings were related to the existence and importance
users give to inner circles within their social network. Despite the complex
social connections tying users together, users are most strongly influenced by
a small set of connections with whom they interact regularly and whose opinion
counts to them. By correlating Q7 and Q8 (Table III), we discovered that
regardless of the number of social connections users have, most users check
and believe their profile is checked by a parallel number of users (Pearson r=
.521, p$<$0.001). Most of the actions (e.g., comments and feedback) users
perform involve inner-circle users, who are the ones influencing users
decisions about lying and not lying.

##  IV Game Theoretic Model of User Behavior

We build on the game theoretic approach to modeling users’ actions in a social
network begun in [25, 13] to qualitatively explain the behavior observed in
our experimental results.

We have identified that users treat types of information differently with
respect to whether they disclose, withhold or deceive. Furthermore, we know
that the behavior of users is highly dependent on the behavior of a small
group of their immediate network neighbors.

Let $G=(V,E)$ be a user graph for a social network and suppose we have several
classes of information $\mathcal{I}=\\{1,\dots,m\\}$. Let
$x^{(j)}_{i}\in[0,1]$ be the proportion of information type $i$ that Player
$j$ will release and let $y^{(j)}_{i}\in[0,1]$ be the proportion of
information type $i$ about which Player $j$ withholds. Then
$z^{(j)}_{i}\in[0,1]$ is the proportion of information type $i$ that Player
$j$ lies about. Then we have:

$x^{(j)}_{i}+y^{(j)}_{i}+z^{(j)}_{i}=1$ (1)

Let:

$\bar{x}^{(j)}_{i}=\frac{1}{|N(j)|}\sum_{k\in N(j)}x^{(k)}_{i}$ (2)

where $N(i)$ is the neighborhood of Player $j$ in $G$. We make similar
definitions for $\bar{y}^{(j)}_{i}$ and $\bar{z}^{(j)}_{i}$. These are the
average network level of releasing, withholding and lying about information
type $i$. In the presence of popularity measures (with respect to a given
user’s circle of friends) Equation 2 can be modified to be a popularity
weighted average with form:

$\hat{x}^{(j)}_{i}=\frac{1}{\sum_{k\in N(j)}p_{k}}\sum_{k\in
N(j)}p_{k}x^{(k)}_{i}$

Here $p_{k}$ is the popularity weight for player $k$.

In [13], we assumed the existence of functions returning the reward for
releasing information and costs for group deception and individual deception.
We assumed these functions were concave, convex and convex (respectively), but
provided no way to isolate their structure. We propose a richer model than the
one in [13], which incorporates our observations from the empirical
evaluation:

The more users interact with the network, the less likely they are to deceive
(see Sect. III-C1))

Users perceive interactions with their social network as a mechanism for
gaining popularity, a form of social capital (see Sect. III-C3). For the
remainder of this section, assume that we’ve fixed an information type (e.g.
location, interest, age etc). Again leveraging our analysis (Section III-C3),
we assume that five elements make up each user’s objective function:

Social capital gained from sharing information within the group,

Personal benefit gained from maintaining information privacy,

Personal cost from the discovery of deceptive information,

Moral cost from deceiving a group and

The cost associated with admitting information (in exchange for social
capital). The easiest way to understand the relationship of these elements is
as a token based model in which each action, causes a token (or fraction
thereof) to be deposited into a specific revenue or cost bucket. The proposed
model for this system is illustrated in the Petri net [8] shown in Figure 4.
Given space constraints, we cannot formally define Petri nets. In short, they
are graphical token models in which transitions move and spread within the
vertices of a graph structure. The interested reader should see Chapter 1 of
[8].

Figure 4: A Petri net model of the accumulation of various components of the
payoff associated to interacting in an online setting.

In general, we can think of the Truth, Withhold and Lie transitions as being
controlled by the user with all other transitions being uncontrolled or
controlled by nature. (Moody [20] discusses control in Petri nets.)
Alternatively, as shown in Figure 4, we can think of the user controlling the
fractional weights on the transitions leading to the Truth, Withhold and Lie
transitions. If the Petri net is continuous, then we can think of the
weightings leaving the controlled transitions as providing the benefit or cost
for each token (or fraction thereof). We let $X^{(j)}$, $Y^{(j)}$ and
$Z^{(j)}$ be correlated random variables whose dynamics are chosen by Player
$j$. In general, $X^{(j)}$ is $1$ only if Player $j$ releases a piece of
information, $Y^{(j)}$ is $1$ only if Player $j$ withholds information a piece
of information and $Z^{(j)}$ is $1$ only if Player $j$ deceives about a piece
of information. Naturally, only one of these elements can be $1$ at any given
time $t$ (thus we can think of these as being the outputs of a single discrete
distribution) chosen by the player. At time $t$, Player $j$’s stochastic
payoff function is:

$\Pi^{(j)}(t)=w_{1}\alpha(X^{(j)}(t),Z^{(j)}(t),\bar{x}^{(j)},\bar{z}^{(j)},t,\tau(t))+\\\
w_{2}\left(\beta(Y^{(j)},\bar{y}^{(j)},t)Y^{(j)}(t)+\eta(Z^{(j)}(t))\right)-\\\
w_{3}\gamma(Z^{(j)},\bar{z}^{(j)},t,\tau(t))-w_{4}\zeta(Z^{(j)}(t))-\\\
w_{5}\theta(X^{(i)}(t))$ (3)

In this expression:

$\alpha(X^{(j)},Z^{(j)},\bar{x}^{(j)},\bar{z}^{(j)},t)$ is a social capital
function that provides the reward obtained by releasing a piece of information
(true or false).

$\beta(Y^{(j)},\bar{y}^{(j)},t)$ is privacy capital function that provides the
reward obtained by keeping a piece of information private.

$\gamma(Z^{(j)},\bar{z}^{(j)},t)$ is a cost function that yields the social
price of lying about a piece of information.

$\theta$ is an admissions cost function for each piece of true information
revealed.

$\zeta$ is a moral cost function associated with each lie told.

$\eta$ is a privacy gain function associated to each lie (since a lie may
protect privacy irrespective of any other moral judgement.

Finally $\tau(t)$ is the probability that a lie will be discovered by the
social group.

Over a period of time, the complete stochastic payoff function for Player $j$
is:

$\Pi^{(j)}=\sum_{t=0}^{T}\rho^{t}\Pi^{(j)}(t)$ (4)

The variables $w_{i}$ ($i=1,\dots,5$) are the relative weights Player $j$
places on each component of his objective function. We can also think of
$\tau$ as being a function of the total quantity of information (true and
false) that has been released to the network:

$Q^{(j)}(s)=\sum_{t=0}^{s}X^{(j)}(t)+Z^{(j)}(t)$ (5)

This provides consistency with two observations reported in Section III-C:

Users who engage in their social network more frequently, tend to deceive less
and

The more information available about a user, the easier it is for him to be
trapped in a lie. The parameter $\rho$ in Equation 4 is a discount factor
chosen in the set $(0,1]$. It is worth noting that $\rho$ is only important if
we wish to consider the limiting dynamics as $T\rightarrow\infty$. When
$\rho<1$, the user recognizes that future rewards have less value than rewards
more immediately. To relate the parameters $x^{(j)}$, $y^{(j)}$ and $z^{(j)}$
to Equation 4, we need to compute the expected value
$\mathbb{E}\left(\Pi^{(j)}\right)$. In the form given, this may be complex,
since the functions defined in Equation 3 maybe non-linear, meaning we cannot
pass the expectation operator through the expression.

The solution to the game is then defined by the simultaneous optimization
problem:

$\forall j\left\\{\begin{aligned}
\max\;\;&\mathbb{E}\left(\Pi^{(j)}(\mathbf{x}(t),\mathbf{y}(t),\mathbf{z}(t))\right)\\\
s.t.\;\;&x^{(j)}(t)+y^{(j)}(t)+z^{(j)}(t)=1\quad\forall t\\\
&x^{(j)}(t),y^{(j)}(t),z^{(j)}(t)\geq 0\quad\forall t\end{aligned}\right.$ (6)

where $\mathbf{x}(t)$, $\mathbf{y}(t)$, $\mathbf{z}(t)$ are the vectors of
decision variables for the players. Let

$\Omega=\prod_{j,t}\left\\{(x^{(j)}(t),y^{(j)}(t),z^{(j)}(t))\in[0,1]^{3}:\right.\\\
x^{(j)}(t)+y^{(j)}(t)+z^{(j)}(t)=1,\\\
\left.x^{(j)}(t),y^{(j)}(t),z^{(j)}(t)\geq 0\right\\}$ (7)

This is the complete strategy space for all players over the course of time
$t\in[0,T]$. Any Nash equilibrium will be chosen from this strategy space.
Theorem 1 of [23] provides the following (uninteresting) result:

######  Proposition IV.1.

Suppose that
$\mathbb{E}\left(\Pi^{(j)}(\mathbf{x}(t),\mathbf{y}(t),\mathbf{z}(t))\right)$
is concave for all $j$ then there is a Nash equilibrium in $\Omega$ for this
game.

######  Remark IV.2.

The uniqueness of a Nash equilibrium in this case is completely a function of
the structure of specific objective functions.

We noted above that the structure of
$\mathbb{E}\left(\Pi^{(j)}(\mathbf{x}(t),\mathbf{y}(t),\mathbf{z}(t))\right)$
maybe complex. By way of simplification, we can write a specific form of
Equation 3, as:

$\Pi^{(j)}(t)=\\\
w_{1}\alpha(x^{(j)},z^{(j)},\bar{x}^{(j)},\bar{z}^{(j)},t)\left(X^{(j)}(t)+(1-\tau(t))Z^{(j)}(t)\right)\\\
+w_{2}\left(\beta(y^{(j)},\bar{y}^{(j)},t)Y^{(j)}(t)+\eta Z^{(j)}(t)\right)\\\
-w_{3}\gamma(z^{(j)},\bar{z}^{(j)},t)\tau(t)Z^{(j)}(t)-w_{4}\zeta
Z^{(j)}(t)\\\ -w_{5}\theta X^{(i)}(t)$ (8)

Here we replace the functions from Equation 3 with piecewise constant
multipliers. We can then relate Equation 4 to the parameters $x^{(j)}$,
$y^{(j)}$ and $z^{(j)}$, we note that:

$\mathbb{E}\left(\Pi^{(j)}\right)=\sum_{t=0}^{T}\rho^{t}\cdot\\\
\left[w_{1}\alpha(x^{(j)},z^{(j)},\bar{x}^{(j)},\bar{z}^{(j)},t)\left(x^{(j)}(t)+(1-\tau(t))z^{(j)}(t)\right)\right.\\\
+w_{2}\left(\beta(y^{(j)},\bar{y}^{(j)},t)y^{(j)}(t)+\eta
z^{(j)}(t)\right)-\\\
w_{3}\gamma(z^{(j)},\bar{z}^{(j)},t)\tau(t)z^{(j)}(t)-\\\ \left.w_{4}\zeta
z^{(j)}(t)-w_{5}\theta x^{(i)}(t)\right]$ (9)

That is, a user’s expected payoff after engaging in this game, is a function
of the proportion of time he releases information, withholds information and
lies about information. Moreover, because we assume the reward/cost
multipliers ($\alpha$, $\beta$ and $\gamma$) are dependent on the group
average rates of releasing, withholding and lying about information, the
payoff to Player $j$ is dependent on the choices of all other players in his
circle of friends. Thus, a game dynamic is established. We study this
simplified game form in the remainder of the paper.

##  V Evolutionary Dynamics and Example

A critical problem with the game defined in the previos section is that
individuals will never optimize their behavior according to it. An individual
can estimate many of the parameters in the model, but will never make
decisions based on the long run objective of maximizing his utility function.
It will simply be impossible for an individual to chose an optimizing strategy
ab initio, particularly without having a clear understanding of the strategies
of other players. This is especially true if (as is likely the case) multiple
Nash equilibria exist.

However, a user may engage in a more evolutionary model of decision making
[28]222Weibull’s book, [28] is an introduction to evolutionary game theory,
which inspires the approach described herein. We are not proposing a classical
evolutionary game. Instead, we are proposing an evolutionary mechanism applied
to a game theoretic context that describes user learning.:

At any time $t$, Player $j$ has a strategy
$(x^{(j)}(t),y^{(j)}(t),z^{(j)}(t))$ with an initial strategy
$(x^{(j)}(0),y^{(j)}(0),z^{(j)}(0))$

At each time $t$, Player $j$ will solve the one-stage game derived from
Equation 9 by finding a maximizing strategy
$\left(\hat{x}^{(j)},\hat{y}^{(j)},\hat{z}^{(j)}\right)$ with respect to the
current observed strategies of the other players and the current parameters in
the model.

Each player’s strategy is updated by the rule:

$\displaystyle
x^{(j)}(t+1)=x^{(j)}(t)+\epsilon^{(j)}\left(\hat{x}^{(j)}-x^{(j)}(t)\right)$
(10) $\displaystyle
y^{(j)}(t+1)=y^{(j)}(t)+\epsilon^{(j)}\left(\hat{y}^{(j)}-y^{(j)}(t)\right)$
(11) $\displaystyle
x^{(j)}(t+1)=z^{(j)}(t)+\epsilon^{(j)}\left(\hat{z}^{(j)}-z^{(j)}(t)\right)$
(12)

Here $\epsilon^{(j)}$ is a learning rate associated to the player, and is
assumed to be small – that is, $\epsilon^{(j)}\ll 1$. The dynamics given in
Equations 10 \- 12 are a discrete variation of the Jacobi iteration for
finding equilibria in games (see e.g., [16]). At its core, this is just a form
of gradient ascent.

Intuitively, each time a user makes a decision about a piece of information,
he considers his knowledge of the other players and computes an optimal move
for this time period. However, instead of changing his strategy completely, he
modifies his strategy (learns) by a small amount in the direction of
optimality. This is consistent with an individual who learns the average
behavior of the social network.

###  V-A Example

By way of example, assume we have a small clique of three friends on a social
network (this is the graph governing Equation 2). Consider the following
multiplier definitions for use in Equation 9. These functions are derived from
a qualitative analysis of the data collected in the experiment described in
the previous sections, and are intended to be simple token counting margin
functions.

$\alpha(x^{(j)},z^{(j)},\bar{x}^{(j)},\bar{z}^{(j)})=\begin{cases}1&x^{(j)}+z^{(j)}\leq\bar{x}^{(j)}+\bar{z}^{(j)}\\\
0&\text{otherwise}\end{cases}$ (13)

In this case, the social value of information is non-zero only if the
information provided is in some way lower than the mean information provided
by the group. That is to say, you can social capital only if you’re not
posting more information than the group average. However, if the group average
is high, you will accrue social capital the more you post.

$\beta(y^{(j)},\bar{y}^{(j)})=\begin{cases}1&y^{(j)}\geq\bar{y}^{(j)}\\\
0&\text{otherwise}\end{cases}$ (14)

Here, the privacy value is non-zero only if the amount of information that is
to be admitted is larger than average amount of information being admitted.
Similarly, we can define:

$\gamma(z^{(j)},\bar{z}^{(j)})=\begin{cases}1&z^{(j)}\geq\bar{z}^{(j)}\\\
0&\text{otherwise}\end{cases}$ (15)

In this case, the cost of a lie is only non-zero if the lie is in some sense
more egregious than the average level of dishonesty. Finally, we can set:
$\zeta=1$ and $\theta=1$.

Variations in the players behavior can then be created by modifying
$w_{1},\dots,w_{5}$ in Equation 9. Finally, we assume that $\tau$ increases
linearly in time from $0.1$ to $0.9$. Recall, $\tau$ is the probability that a
lie can be detected by the social network. Thus, as time proceeds, it becomes
more likely that a falsehood is detected because more information is available
about each player 333In a fully formalized model, we believe that $\tau$ will
be a function of $Q$ (defined in Equation 5), however for our simple studies,
this is sufficient.

We study three specific examples of the dynamics produced by this model to
illustrate that even these (simple) dynamics are capable of qualitatively
reproducing behavior observed in our study. In the first example, social
capital is deemed more important than privacy ($w_{1}=1$, $w_{2}=0.25$ and
$w_{5}=0.125$), but there is a stronger sense of morality ($w_{3}=0.5$,
$w_{4}=1$). We assume three identical players connected by a complete graph
with three vertices. Player evolution is illustrated in Figure 5

Figure 5: Evolutionary output of a game with three identical players in which
$w_{1}=1$, $w_{2}=0.25$, $w_{3}=0.5$, $w_{4}=1$ and $w_{5}=0.125$, suggesting
that social capital is much more important than the gain associated with
privacy.

When we start the game with three players, each playing the strategy
$x^{(j)}=0.7$, $y^{(j)}=0.2$ and $z^{(j)}=0.1$, we see deception is removed
from the system relatively quickly, while information hiding increases
(replacing deception in the system). Notice the system converges to a
stationary strategy near $x^{(j)}=2/3$, $y^{(j)}=1/3$ and $z^{(j)}=0$. In
simpler terms, these equilibrium points are consistent with our findings that
social capital is much more important than the gain associated with privacy,
because we see that there is a preference toward sharing information
truthfully. This was observed in Section III-C3. It is also worth noting, that
it can be shown numerically these are limiting Nash equilibria for this
example.

By way of comparison, we can construct a game with less morality and even more
importance associated to social capital (being obtained by any means
necessary) with $w_{1}=2$, $w_{2}=0.25$, $w_{3}=0.25$, $w_{4}=0.125$ and
$w_{5}=0.125$. Note, $w_{4}=0.125$ indicates a low moral penalty for lying.
The evolution of the players is illustrated in Figure 6.

Figure 6: Evolutionary output of a game with three identical players in which
$w_{1}=2$, $w_{2}=0.25$, $w_{3}=0.25$, $w_{4}=0.125$ and $w_{5}=0.125$,
suggesting that social capital is much more important than the gain associated
with privacy and morality is of little concern.

The dynamics in this game are different, than those of the first game. There
is an initial, substantial, increase in the level of deception (when it is
easy to lie) in order to obtain social capital. As it becomes more difficult
to lie, the players return to a more truthful scenario that is easier to
support. This example confirms the identified effects of the signaling theory
in our dataset: users are less likely to deceive when they are heavily
involved in social interactions (Section III-C1 and III-C2).

Figure 7: Evolutionary output of a game with three identical players in which
$w_{1}=0.5$, $w_{2}=5$, $w_{3}=2$, $w_{4}=100$ and $w_{5}=3$, suggesting that
morality and privacy are paramount to this user.

In our final example, we consider a highly moral player who puts less emphasis
on social capital and substantial emphasis on information privacy. In this
case, we have: $w_{1}=0.5$, $w_{2}=5$, $w_{3}=2$, $w_{4}=100$ and $w_{5}=3$.
The results are illustrated in Figure 7. This objective function models a user
who is highly moral deciding whether to release an information type that may
be sensitive, such as GPA or dating status and illustrates the ability of the
model to capture the various qualitative results observed in the survey. In
particular, this result is consistent with the finding reported in Section
III-C4: withholding is used as a form of control when deception is considered
unethical.

The proposed approach can also be used to study richer scenarios, including
those with players that begin with different strategies and games that are
played on distinct graph structures as was discussed in [13].

##  VI Future Directions

In this work, we have shown an informed model on deception and
misrepresentation in OSNs. The model is derived from a token counting approach
modeled in a stochastic, continuous Petri net. This net is then used to derive
an objective function for each player in which the payoff to a given player is
a function not only of his decisions but also the decisions of his circle of
friends. This leads to a game theoretic framework. We show that while this
game has at least one Nash equilibria, it is more interesting to consider an
evolutionary game dynamic in which players learn over time and converge to a
stationary strategy.

We are left with a number of unsolved questions, that we plan to explore in
the near future. First, we are interested in collecting more detailed data
from real-world users, to deepen our understanding of users’ interactions and
identity revelation processes. For example, in the current study we did not
focus on the users’ actions, that result in identity disclosure. What are the
typical passive social transactions (post an item on your page which may be
silently consumed by those who’ve been given access to it) or active
transactions (sharing, commenting on other’s content or status updates, give
feedback) that lead to information revelation and/or to deception? How do
different outcomes of such transactions affect social capital, and therefore
result in truthful and untruthful information sharing? How do secondary
(friend-of-friend, triad) relationships influence information sharing? Results
obtained from these studies will guide the next step of our research on the
model.

For example, using this information, we would like to determine the structural
characteristics of the benefit and cost functions in Equation 4. In addition
to this, it would be useful to identify whether the dynamics described force
the players to converge to an equilibria of some type. We expect that
convergence to an equilibrium point should occur, but it is not clear if this
is a global property of all well-behaved payoff functions. As noted in [13]
there can be an interaction between the properties of the graph on which the
game is played and the number and type of symmetric equilibria. We have not
explored this using the model presented in this paper, but we believe this is
a necessary step in understanding the behavior of user dynamics in information
expression in social networks.

## Ackowledgement

Portions of Dr. Griffin’s work were supported by the Army Research Office
under Grant W911NF-11-1-0487.

## References

  * [1] K. Aberer and Z. Despotovic.  On reputation in game theory application on online settings, 2004.
  * [2] S. Ahern, D. Eckles, N. S. Good, S. King, M. Naaman, and R. Nair.  Over-exposed?: privacy patterns and considerations in online and mobile photo sharing.  In CHI ’07: Proceedings of the SIGCHI conference on Human factors in computing systems, pages 357–366. ACM, 2007.
  * [3] G.-J. Ahn, M. Ko, and M. Shehab.  Privacy-enhanced user-centric identity management.  In IEEE International Conference on Communications, pages 1–5, 2009\.
  * [4] T. Alpcan, C. Örencik, A. Levi, and E. Savaş.  A game theoretic model for digital identity and trust in online communities.  In ASIACCS ’10: Proceedings of the 5th ACM Symposium on Information, Computer and Communications Security, pages 341–344. ACM, 2010\.
  * [5] S. Bhagat, G. Cormode, B. Krishnamurthy, and D. Srivastava.  Privacy in dynamic social networks.  In WWW ’10: Proceedings of the 19th international conference on World wide web, pages 1059–1060. ACM, 2010.
  * [6] G. Bolton, E. Katok, and A. Ockenfels.  How effective are online reputation mechanisms?  Papers on Strategic Interaction 2002-25, Max Planck Institute of Economics, Strategic Interaction Group, May 2002.
  * [7] M. Burke, C. Marlow, and T. Lento.  Feed me: motivating newcomer contribution in social network sites.  In Proceedings of the 27th international conference on Human factors in computing systems, CHI ’09, pages 945–954. ACM, 2009.
  * [8] R. David and H. Alla.  Discrete, Continuous, And Hybrid Petri Nets.  Springer, 2005.
  * [9] J. DiMicco and D. Millen.  Identity management: multiple presentations of self in facebook.  In GROUP ’07: Proceedings of the 2007 international ACM conference on Supporting group work, pages 383–386, New York, NY, USA, 2007\. ACM.
  * [10] J. Donath.  Signals, truth and design.  Forthcoming. (http://smg.media.mit.edu/people/judith/signalsTruthDesign.html), 2011.
  * [11] J. Ely, D. Fundenberg, and D. Levine.  When is reputation bad?  Games and Economic Behavior, pages 498–526, 2008.
  * [12] E. Goffman.  The Presentation of Self in Everyday Life.  1959\.
  * [13] C. Griffin and A. Squicciarini.  Toward a game theoretic model of information release in social media with experimental results.  In Proc. 2nd Workshop on Semantic Computing and Security, San Francisco, CA, USA, May 28 2012.
  * [14] T. Hogg and L. Adamic.  Enhancing reputation mechanisms via online social networks.  In EC ’04: Proceedings of the 5th ACM conference on Electronic commerce, pages 236–237, New York, NY, USA, 2004. ACM.
  * [15] IEEE.  Third IEEE Conference on Decision theory and Game for Security, 2012\.  www.gamesec-conf.org.
  * [16] Y. Jin and G. Kesidis.  Equilibria of a noncooperative game for heterogeneous users of an aloha network.  IEEE Comm. Lett.Communications Letters, 6(7):282–284, 2002.
  * [17] J. Kleinberg, C. H. Papadimitriou, and P. Raghavan.  On the value of private information.  In Proc. of the 8th conference on Theoretical aspects of rationality and knowledge, TARK ’01, pages 249–257, San Francisco, CA, USA, 2001\. Morgan Kaufmann Publishers Inc.
  * [18] C. A. Lampe, N. Ellison, and C. Steinfield.  A familiar face(book): profile elements as signals in an online social network.  In Proceedings of the SIGCHI conference on Human factors in computing systems, CHI ’07, pages 435–444. ACM, 2007.
  * [19] K. Liu and E. Terzi.  Towards identity anonymization on graphs.  In SIGMOD ’08: Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 93–106, New York, NY, USA, 2008. ACM.
  * [20] J. Moody.  Petri Net Supervisors for Discrete Event Systems.  PhD thesis, Dept. of Electrical Engineering, University of Notre Dame, Notre Dame, IN. USA, 1998.
  * [21] K. C. Nguyen, T. Alpcan, and T. Basar.  Stochastic games for security in networks with interdependent nodes.  CoRR, abs/1003.2440, 2010.
  * [22] P. Nurmi.  A bayesian framework for online reputation systems.  In Telecommunications, 2006. AICT-ICIW ’06. International Conference on Internet and Web Applications and Services/Advanced International Conference on, page 121, February 2006.
  * [23] J. B. Rosen.  Existence and uniqueness of equilibrium points for concave n-person games.  Econometrica, 33(3):520–534, 1963.
  * [24] C. Shapiro.  Consumer information, product quality, and seller reputation, 1982.
  * [25] A. C. Squicciarini, S. Sundareswaran, and C. Griffin.  A game theoretical perspective of users’ registration in online social platforms.  In Accepted to Third IEEE International Conference on Privacy, Security, Risk and Trust, October 9 - 11 2011.
  * [26] F. Stutzman.  An evaluation of identity-sharing behavior in social network communities.  iDMAa Journal, 3(1), 2006.
  * [27] B. Thompson and D. Yao.  The union-split algorithm and cluster-based anonymization of social networks.  In ASIACCS ’09: Proceedings of the 4th International Symposium on Information, Computer, and Communications Security, pages 218–227, New York, NY, USA, 2009. ACM.
  * [28] J. W. Weibull.  Evolutionary Game Theory.  MIT Press, 1997.
  * [29] P. J. Windley, D. Daley, B. Cutler, and K. Tew.  Using reputation to augment explicit authorization.  In DIM ’07: Proceedings of the 2007 ACM workshop on Digital identity management, pages 72–81, New York, NY, USA, 2007. ACM.
  * [30] H. Xu, T. Dinev, H. J. Smith, and P. J. Hart.  Examining the formation of individual’s privacy concerns: Toward an integrative view.  In ICIS, page 6, 2008.
  * [31] H. Xu, R. Parks, C. Chu, and X. Zhang.  Information disclosure and online social networks: From the case of facebook news feed controversy to a theoretical understanding.  Proc. of the 16th Americas Conference on Information Systems, AMCIS 2010, 2010.
  * [32] M. Z. Yao, R. E. Rice, and K. Wallis.  Predicting user concerns about online privacy.  Journal of the American Society for Information Science and Technology (JASIST), 58(5):710–722, 2007.