# Metric dimension in a prime ideal sum graph
of a commutative ring ††thanks: Key Words: Metric dimension, Resolving set,
Prime ideal sum graph, Commutative ring.
2010 Mathematics Subject Classification: 13A15; 13B99; 05C99; 05C25.

M. Adlifarda, Sh. Niknejadb, R. Nikandishc
bDepartment of Mathematics, Roudbar Branch, Islamic Azad University,
Roudbar, Iran
bDepartment of Mathematics, Gachsaran Branch, Islamic Azad University,
Gachsaran, Iran
cDepartment of Mathematics, Jundi-Shapur University of Technology,
P.O. BOX 64615-334, Dezful, Iran
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
Corresponding author

###### Abstract

The prime ideal sum graph of a commutative unital ring $R$, denoted by
$PIS(R)$, is an undirect and simple graph whose vertices are non-trivial
ideals of $R$ and there exists and edge between to distinct vertices if and
only if their sum is a prime ideal of $R$. In this paper, the metric dimension
of $PIS(R)$ is discussed and some formulae for this parameter in $PIS(R)$ are
given.

##  1 Introduction

Finding metric dimension in a graph is an example of NP-hard identification
problem in discrete structures which has many applications not only in robotic
but also in chemistry, image processing, combinatorial optimization and so on.
The study of this notion was initiated by Slater [16] in 1975 and Harary [16]
in 1976 , independently and several graph theorists computed this concept in
some classes of graphs, see for instance [2, 7, 8]. Both of wide range of
applications and complexity of computations have caused considerable attention
in characterizing this invariant for graphs associated with algebraic
structures, some examples in this direction may be found in [3, 4, 5, 9, 10,
11, 12, 13, 15]. This paper is in this theme and aims to investigate the
metric dimension in prime ideal sum graphs of commutative rings.

Throughout this paper, all rings are assumed to be commutative with identity.
The sets of all ideals, maximal ideals and jacobson radical of $R$ are denoted
by $A(R)$, $\mathrm{Max}(R)$ and $J(R)$, respectively. For a subset $T$ of a
ring $R$ we let $T^{*}=T\setminus\\{0\\}$. Moreover, by $A(T)$, we mean the
set of ideals of $R$ which are contained in $T$. The ring $R$ is called
reduced if $0$ is the only nilpotent element of $R$. Some more definitions
about commutative rings can be find in [1].

We use the standard terminology of graphs following [17]. Throughout this
work, all graphs $G=(V,E)$ are simple and connected. As usual, the symbol
$\mathrm{diam}(G)$ represents the diameter of $G$. The distance between two
distinct vertices $x$ and $y$ is denoted by $d(x,y)$. Also, a complete graph
of order $n$ is denoted by $K_{n}$. For a vertex $x$ in $V(G)$, open
neighborhood of $x$ is denoted $N(x)$. Let $G=(V,E)$ be a connected graph,
$S=\\{v_{1},v_{2},\dots,v_{k}\\}$ be an ordered subset of $V$ and $v\in
V(G)\setminus S$. The vector $D(v|S)=(d(v,v_{1}),d(v,v_{2}),\dots,d(v,v_{k}))$
is called the representation of $v$ with respect to $S$. A set $S\subseteq V$
is called a resolving set for $G$ if distinct vertices of $G$ have different
representations with respect to $S$. A resolving set of minimum cardinality is
called the metric basis for $G$ and the cardinality of metric basis is called
the metric dimension of $G$. The metric dimension of $G$ is denoted by
$dim_{M}(G)$.

Let $R$ be a commutative ring with identity. The prime ideal sum graph of $R$,
denoted by $PIS(R)$, is a graph whose vertices are nonzero proper ideals of
$R$ and two distinct vertices $I$ and $J$ are adjacent if and only if $I+J$ is
a prime ideal of $R$. This graph was first introduced and studied in [14] and
many interesting results were explored by the authors. For instance, they
investigated connectedness, diameter, girth, clique number and domination
number of $PIS(R)$. In this paper, we study the metric dimension of $PIS(R)$
and provide some metric dimension formulas for $PIS(R)$.

##  2  Metric dimension of a prime ideal sum graph of a reduced ring

In this section, the exact value of metric dimension in a prime ideal sum
graph associated with a reduced ring $R$ in terms of the number of maximal
ideals of $R$ is given. First, we need to state the following result.

Suppose that $R$ is a ring. By [14, Theorem 2.6], $PIS(R)$ is disconnected if
and only if $R$ is a direct product of two fields. Thus we exclude such
situation from the paper.

###### Lemma 2.1

If $R$ is a ring, then the following statements are equivalent.

$(1)$ $dim_{M}(PIS(R))$ is finite.

$(2)$ $R$ has only finitely many ideals.

###### Proof.

$(1)\Rightarrow(2)$ Assume that $dim_{M}(PIS(R))$ is finite and
$W=\\{I_{1},I_{2},\dots,I_{n}\\}$ is a metric basis in $PIS(R)$, for some non-
negative integer $n$. Let $I\in V(PIS(R))\setminus W$. Then the number of all
possible ways for $D(I|W)$ equals $(4+1)^{n}$, as $diam(PIS(R))\leq 4$ (see
[14, Theorem 2.6]). Thus $|V(PIS(R))|\leq 5^{n}+n$ and hence $R$ has finitely
many ideals.

$(2)\Rightarrow(1)$ is clear.  $\Box$

In order to compute $dim_{M}(PIS(R))$, it is enough to consider Artinian rings
$R$ (Indeed, rings with finitely many ideals), by Lemma 2.1. Moreover, every
reduced ring with finitely many ideals is a direct product of finitely many
fields, by [1, Theorem 8.7]. Using these facts, we prove the main result of
this section.

###### Theorem 2.1

Suppose that $R$ is a reduced ring and $dim_{M}(PIS(R))$ is finite. Then the
following statements hold:

$(1)$ If $|\mathrm{Max}(R)|=3$, then $dim_{M}(PIS(R))=2$.

$(2)$ If $|\mathrm{Max}(R)|=n\geq 4$, then $dim_{M}(PIS(R))=n$.

###### Proof.

$(1)$ If $n=3$, then $R\cong F_{1}\times F_{2}\times F_{3}$, where $F_{i}$ is
a field for every $1\leq i\leq 3$. Let $W=\\{(0)\times F_{2}\times
F_{3},F_{1}\times(0)\times F_{3}\\}$. Then by Figure 1,

$D({(0)\times F_{2}\times(0)}|W)=(1,2)$,

$D({F_{1}\times(0)\times(0)}|W)=(2,1)$,

$D({(0)\times(0)\times F_{3}}|W)=(1,1)$,

$D({F_{1}\times F_{2}\times(0)}|W)=(2,2)$.

Thus, $D(I|W)\neq D(J|W)$, for every $I,J\in V(PIS(R))\setminus W$. Therefore,
$dim_{M}(PIS(R))=2$.

$(0)\times F_{2}\times F_{3}$$(0)\times
F_{2}\times(0)$$F_{1}\times(0)\times(0)$$(0)\times(0)\times F_{3}$$F_{1}\times
F_{2}\times(0)$$F_{1}\times(0)\times F_{3}$ Figure 1: ${PIS}(F_{1}\times
F_{2}\times F_{3})$

$(2)$ Assume that $n\geq 4$. It follows from Lemma 2.1 that $R\cong
F_{1}\times\cdots\times F_{n}$, where $F_{i}$ is a field for every $1\leq
i\leq n$. We show that $dim_{M}(PIS(R))=n$. Indeed, we have the following
claims:

Claim 1. $dim_{M}(PIS(R))\geq n$.

By Lemma 2.1, we may suppose that $dim_{M}(PIS(R))=k$, where $k$ is a positive
integer. Since $R$ is a principal ideal ring, by [14, Theorem 2.6],
$diam(PIS(R))\in\\{1,2\\}$ and so there are $2^{k}$ possible ways for
$D(I|W)$, if $I\in V(PIS(R))\setminus W$. This implies that $|V(PIS(R))|-k\leq
2^{k}$. It is clear that $|V(PIS(R))|=2^{n}-2$ and thus $2^{n}-2-k\leq 2^{k}$.
Hence $2^{n}\leq 2^{k}+2+k$. Now, $n\geq 4$ implies that $k\geq n$. Therefore,
$dim_{M}(PIS(R))\geq n$.

Claim 2. $dim_{M}(PIS(R))\leq n$.

For every $1\leq i\leq n$, let $\mathfrak{m}_{i}=(I_{1},I_{2},\dots,I_{n})\in
A(R)^{*}$ such that $I_{i}=0$ and $I_{j}=F_{j}$, for every $1\leq j\leq n$
with $i\neq j$. Put
$W=\\{\mathfrak{m}_{1},\mathfrak{m}_{2},\dots,\mathfrak{m}_{n}\\}$ (Obviously,
$W=\mathrm{Max}(R)$). We prove that $W$ is a resolving set for $PIS(R)$. Let
$I,J\in V(PIS(R))\setminus W$ and $I\neq J$. We have to show that $D(I|W)\neq
D(J|W)$. Let $I=(I_{1},I_{2},\dots,I_{n})$ and $J=(J_{1},J_{2},\dots,J_{n})$.
Since $I\neq J$, there exists $1\leq i\leq n$ such that either $I_{i}=0$ and
$J_{i}=F_{i}$ or $I_{i}=F_{i}$ and $J_{i}=0$. Without loss of generality,
assume that $I_{1}=0$ and $J_{1}=F_{1}$. It is not hard to check that
$d(I,\mathfrak{m}_{1})=1$ and $d(J,\mathfrak{m}_{1})=2$. This clearly shows
that $D(I|W)\neq D(J|W)$, as desired.

Now, Claims 1, 2 show that $dim_{M}(PIS(R))=n$, if $n\geq 4$.  $\Box$

##  3  Metric dimension of a prime ideal sum graph of a non-reduced ring

In this section, $dim_{M}(PIS(R))$ is investigated, in case $R$ is non-
reduced.

We begin with the following lemma which provides an upper bound for
$dim_{M}(PIS(R))$, when $R$ is a direct product of finitely many rings with
one non-trivial ideal.

###### Lemma 3.1

Suppose that $R\cong R_{1}\times\cdots\times R_{n}$ and every $R_{i}$ is a
ring with a unique non-trivial ideal $\mathfrak{m}_{i}$, for $1\leq i\leq n$.
Then $dim_{M}(PIS(R))\leq 2n$.

###### Proof.

Suppose that

$A=\\{(0,R_{2},\dots,R_{n}),(R_{1},0,R_{3},\dots,R_{n}),\dots,(R_{1},\dots,R_{n-1},0)\\}$,

$B=\\{(\mathfrak{m}_{1},R_{2},\dots,R_{n}),(R_{1},\mathfrak{m}_{2},R_{3},\dots,R_{n}),\dots,(R_{1},\dots,R_{n-1},\mathfrak{m}_{n})\\}$
(in fact $B={\rm Max}(R)$) and

$W=A\cup B$.

It is proved that $W$ is a resolving set in $PIS(R)$. Let
$I=(I_{1},\dots,I_{n}),J=(J_{1},\dots,J_{n})\in A(R_{i})^{*}\setminus W$. It
is enough to show that $D(I|W)\neq D(J|W)$.

We have to consider the following cases:

Case 1. $I\subseteq J(R)$. If $J\subseteq J(R)$, too, then with no loss of
generality, one may assume that $I_{1}=0$ and $J_{1}=\mathfrak{m}_{1}$, as
$I\neq J$. We have
$D(I|W)=(2,\underbrace{-,\cdots,-}_{n-1},\underbrace{1,\cdots,1}_{n})$ and
$D(J|W)=(1,\underbrace{-,\cdots,-}_{n-1},\underbrace{1,\cdots,1}_{n})$.
Therefore, $D(I|W)\neq D(J|W)$. If $J\nsubseteq J(R)$, then with no loss of
generality, one may assume that $J_{n}=R_{n}$. Thus
$D(I|W)=(\underbrace{-,\cdots,-}_{n},\underbrace{1,\cdots,1}_{n})$ and
$D(J|W)=(\underbrace{-,\cdots,-}_{n-1},2,\underbrace{-,\cdots,-}_{n-1},2)$.
Therefore, $D(I|W)\neq D(J|W)$.

Case 2. $I\nsubseteq J(R)$ and $J\nsubseteq J(R)$. In this case, $I_{i}=R_{i}$
and $J_{j}=R_{j}$, for some $1\leq i,j\leq n$. If for every $1\leq i\leq n$,
$I_{i}=R_{i}$ if and only if $J_{i}=R_{i}$, then since $I\neq J$, for some
$1\leq i\leq n$, $\\{I_{i},J_{i}\\}\subseteq\\{0,\mathfrak{m}_{i}\\}$. Without
lost of generality, we may assume that $I_{1}=0$ and $J_{1}=\mathfrak{m}_{1}$.
Now, we have
$D(I|W)=(2,\underbrace{-,\cdots,-}_{n-1},\underbrace{x_{1},\cdots,x_{n}}_{n})\neq(1,\underbrace{-,\cdots,-}_{n-1},\underbrace{x_{1},\cdots,x_{n}}_{n})=D(J|W)$
such that $x_{i}\in\\{1,2\\}$ and there exists $1\leq i\leq n$ such that
$x_{i}=2$.

If $I_{i}=R_{i}$ and $J_{i}\neq R_{i}$, for some $1\leq i\leq n$, then
$\\{J_{i}\\}\subseteq\\{0,\mathfrak{m}_{i}\\}$. Without lost of generality,
assume that $I_{1}=R_{1}$ and $J_{1}=0$ or $J_{1}=\mathfrak{m}_{1}$. Thus
$D(I|W)=(2,\underbrace{-,\cdots,-}_{n-1},2,\underbrace{x_{2},\cdots,x_{n}}_{n-1})$,
but
$D(J|W)=(2,\underbrace{-,\cdots,-}_{n-1},1,\underbrace{x_{2},\cdots,x_{n-1}}_{n-1})$,
if $J_{1}=0$ and
$D(J|W)=(1,\underbrace{-,\cdots,-}_{n-1},1,\underbrace{x_{2},\cdots,x_{n-1}}_{n-1})$,
if $J_{1}=\mathfrak{m}_{1}$. The above arguments show that $D(I|W)\neq
D(J|W)$. Finally, we note that the situation $I\nsubseteq J(R)$ and
$J\subseteq J(R)$ is similar to $J\nsubseteq J(R)$ and $I\subseteq J(R)$ in
Case 1. Therefore, $W$ is a resolving set for $PIS(R)$. This implies that
$dim_{M}(PIS(R))\leq|W|=2n$.  $\Box$

The following example shows that the upper bound $2n$ in Lemma 3.1 is sharp.

###### Example 3.1

$(1)$ Let $n=2$ in Lemma 3.1 and
$W=\\{(R_{1},0),(0,R_{2}),(R_{1},\mathfrak{m}_{2})\\}$. Then
$D({(\mathfrak{m}_{1},R_{2})}|W)=(2,1,2)$,
$D({(0,\mathfrak{m}_{2})}|W)=(1,2,1)$, $D({(\mathfrak{m}_{1},0)}|W)=(2,1,1)$,
$D({(\mathfrak{m}_{1},\mathfrak{m}_{2})}|W)=(1,1,1)$ and hence $W$ is a
resolving set for $PIS(R)$. This means that $dim_{M}(PIS(R)\leq 3$. On the
other hand, since $diam(PIS(R))=2$ and $|V(PIS(R))|=7$, we conclude that
$dim_{M}(PIS(R)\geq 3$. So $dim_{M}(PIS(R))=3$.

$(2)$ Let $n=3$ in Lemma 3.1. By Lemma 3.1, $dim_{M}(PIS(R))\leq 6$. But we
show that $dim_{M}(PIS(R))=5$. Since $|V(PIS(R)))|=25$ and $diam(PIS(R))=2$,
we deduce that $dim_{M}(PIS(R))\geq 5$. To complete the proof, let

$W=\\{(0,R_{2},R_{3}),(R_{1},0,R_{3}),(R_{1},R_{2},0),(R_{1},\mathfrak{m}_{2},\mathfrak{m}_{3}),(\mathfrak{m}_{1},\mathfrak{m}_{2},R_{3})\\}$.

Then we have

$D({(\mathfrak{m}_{1},\mathfrak{m}_{2},\mathfrak{m}_{3})}|W)=(1,1,1,2,2)$,

$D({(\mathfrak{m}_{1},\mathfrak{m}_{2},0)}|W)=(1,1,2,2,2)$,

$D({(\mathfrak{m}_{1},0,\mathfrak{m}_{3})}|W)=(1,2,1,2,2)$,

$D({(0,\mathfrak{m}_{2},\mathfrak{m}_{3})}|W)=(2,1,1,2,2)$,

$D({(\mathfrak{m}_{1},0,0)}|W)=(1,2,2,2,2)$,

$D({(0,\mathfrak{m}_{2},0)}|W)=(2,1,2,2,2)$,

$D({(0,0,\mathfrak{m}_{3})}|W)=(2,2,1,2,2)$,

$D({(R_{1},0,0)}|W)=(2,2,2,2,1)$,

$D({(0,R_{2},0)}|W)=(2,2,2,1,1)$,

$D({(0,0,R_{3})}|W)=(2,2,2,1,2)$,

$D({(\mathfrak{m}_{1},R_{2},R_{3})}|W)=(1,2,2,2,1)$,

$D({(R_{1},\mathfrak{m}_{2},R_{3})}|W)=(2,1,2,1,1)$,

$D({(R_{1},R_{2},\mathfrak{m}_{3})}|W)=(2,2,1,1,2)$,

$D({(\mathfrak{m}_{1},R_{2},\mathfrak{m}_{3})}|W)=(1,2,1,1,1)$,

$D({(R_{1},\mathfrak{m}_{2},0)}|W)=(2,1,2,2,1)$,

$D({(R_{1},0,\mathfrak{m}_{3})}|W)=(2,2,1,2,1)$,

$D({(\mathfrak{m}_{1},R_{2},0)}|W)=(1,2,2,1,1)$,

$D({(0,R_{2},\mathfrak{m}_{3})}|W)=(2,2,1,1,1)$,

$D({(0,\mathfrak{m}_{2},R_{3})}|W)=(2,1,2,1,2)$,

$D({(\mathfrak{m}_{1},0,R_{3})}|W)=(1,2,2,1,2).$

It is not hard to see that $D(I|W)\neq D(J|W)$, for all $I,J\in
A(R)^{*}\setminus W$. Thus $W$ is a resolving set in $PIS(R)$ and so
$dim_{M}(PIS(R))=5$.

Lemma 3.1 enables us to give the exact value of $dim_{M}(PIS(R))$, when $R$ is
a direct product of finitely many rings with exactly one non-trivial ideal.

###### Theorem 3.1

Suppose that $R\cong R_{1}\times\cdots\times R_{n}$ and every $R_{i}$ is a
ring with a unique non-trivial ideal $\mathfrak{m}_{i}$, for $1\leq i\leq n$.
Then the following statements hold:

$(1)$ If $n=1$, then $dim_{M}(PIS(R))=0$.

$(2)$ If $n=2$ or $n=3$, then $dim_{M}(PIS(R))=2n-1$.

$(3)$ If $n\geq 4$, then $dim_{M}(PIS(R))=2n$.

###### Proof.

$(1)$ If $n=1$, then the result is obvious.

$(2)$ If $n=2$ or $n=3$, then the result follows from Example 3.1.

$(3)$ Let $n\geq 4$,

$A=\\{(0,R_{2},\dots,R_{n}),(R_{1},0,R_{3},\dots,R_{n}),\dots,(R_{1},\dots,R_{n-1},0)\\}$,

$B=\\{(\mathfrak{m}_{1},R_{2},\dots,R_{n}),(R_{1},\mathfrak{m}_{2},R_{3},\dots,R_{n}),\dots,(R_{1},\dots,R_{n-1},\mathfrak{m}_{n})\\}$
and

$C=A(R_{i})^{*}\setminus A\cup B$.

We claim that $A\cup B\subseteq W$, where $W$ is a resolving set for $PIS(R)$.
First, we show that $A\subseteq W$ (Indeed, we are going to prove that all
ideals contained in $J(R)\setminus W$ are resolved only by (some) vertices
contained in $A$). Let $|A(J(R))\cap W|=t$ and $I\in A(J(R))\cap W$. Since
$|A(J(R))|=2^{n}-1$ and $d(I,K)=1$ for every $K\in B$ and $d(I,K)=2$ for every
$K\in C$ with $I\neq K$, we must have $2^{n}-1-t\leq 2^{|S|}$, where
$S\subseteq A$ is a resolving set for $A(J(R)\setminus W)$. If $S\neq A$, then
since $|S|\leq n-1$, we infer that $2^{n}-1-t\leq 2^{n-1}$, a contradiction
(as $n\geq 4$). Hence $A\subseteq W$. Next, we show that $B\subseteq W$. Let
$T=\\{(I_{1},\dots,I_{n})\,\,|\,\,I_{i}\in\\{0,R_{i}\\}\\}$. Since $d(I,J)=2$,
for every $I\in T$ and $J\in A$, we must add some elements of $A(R)\setminus
A$ to $W$ for resolving elements in $T\setminus W$. Since $|T|=2^{n}-2$, we
must add at last $n$ elements of $A(R)\setminus A$ to $W$(In fact we must add
at last $t$ elements till $|T\setminus A|\leq 2^{t}$). This proves the claim
and so $dim_{M}(PIS(R))=|W|\geq 2n$ . Now, the result follows from Lemma 3.1.
$\Box$

The following remark has a key role in proof of Theorem 3.2.

###### Remark 3.1

For a connected graph $G$, if $V_{1},V_{2},\dots,V_{k}$ is a partition of
$V(G)$ such that for every $1\leq i\leq k$, $x,y\in V_{i}$ implies that
$N(x)=N(y)$. Then $dim_{M}(G)\geq|V(G)|-k$.

###### Theorem 3.2

Suppose that $R\cong R_{1}\times\cdots\times R_{n}$, where
$(R_{i},\mathfrak{m}_{i})$ is an Artinian local principal ideal ring and
$|A(R_{i})^{*}|\geq 2$, for every $1\leq i\leq n$. Then the following
statements hold:

$(1)$ If either $n\neq 1$ or $n=1$ and $|A(R_{i})^{*}|\geq 3$, then
$dim_{M}(PIS(R))=|A(R)^{*}|-3^{n}+1$.

$(2)$ If $n=1$ and $|A(R_{i})^{*}|=2$, then $dim_{M}(PIS(R))=1$.

###### Proof.

Suppose that $I=(I_{1},\dots,I_{n})$ and $J=(J_{1},\dots,J_{n})$ are vertices
of $PIS(R)$. Define the relation $\thicksim$ on $V(PIS(R))$ as follows:
$X\thicksim Y$, whenever for every $1\leq i\leq n$, the following conditions
hold.

$(1)$“$I_{i}=\mathfrak{m}_{i}$ if and only if $J_{i}=\mathfrak{m}_{i}$”.

$(2)$“$I_{i}\subseteq\mathfrak{m}_{i}$ with $I_{i}\neq\mathfrak{m}_{i}$ if and
only if $J_{i}\subseteq\mathfrak{m}_{i}$ with $J_{i}\neq\mathfrak{m}_{i}$.

$(3)$“$I_{i}=R_{i}$ if and only if $J_{i}=R_{i}$”.

Clearly, $\thicksim$ is an equivalence relation on $V(PIS(R))$. The
equivalence class of $I$ is denoted by $[I]$. Suppose that $X$ and $Y$ are two
elements of the equivalence class of $I$. By definition of the relation
$\thicksim$ and adjacency condition for $X$ and $Y$, one can check that
$N(X)=N(Y)$. Now, Remark 3.1 and the fact that “the number of equivalence
classes is $3^{n}-1$” imply that
$dim_{M}(PIS(R))\geq|A(R)^{*}|-(3^{n}-1)=|A(R)^{*}|-3^{n}+1$.

To complete the proof, it is shown that
$dim_{M}(PIS(R))\leq|A(R)^{*}|-3^{n}+1$. Let $(K_{1},\dots,K_{n})\in
V(PIS(R))$ be a fixed vertex such that for every $1\leq i\leq n$, $0\neq
K_{i}\subset\mathfrak{m}_{i}$ and

$A=\\{(I_{1},\dots,I_{n})\in
V(PIS(R))|\,\,I_{i}\in\\{0,R_{i},\mathfrak{m}_{i}\\}\,\,\mathrm{for\,\,every}\,\,1\leq
i\leq n\\}\cup\\{(K_{1},\dots,K_{n})\\}.$

We claim that $W=A(R)^{*}\setminus A$ is a resolving set for $PIS(R)$. Let
$I,J\in A$ and $I\neq J$. It is enough to show that $D(I|W)\neq D(J|W)$.
Consider the following sets:

$V_{1}=\\{(I_{1},\dots,I_{n})\in
V(PIS(R))|\,\,I_{i}\in\\{0,R_{i}\\}\,\,\mathrm{for\,\,every}\,\,1\leq i\leq
n\\}$,

$V_{2}=\\{(I_{1},\dots,I_{n})\in
V(PIS(R))|\,\,I_{i}\in\\{0,\mathfrak{m}_{i}\\}\,\,\mathrm{for\,\,every}\,\,1\leq
i\leq n\\}$,

$V_{3}=A\setminus\\{V_{1}\cup V_{2}\\}$,

$T_{1}=\\{(K_{1},R_{2}\dots,R_{n}),(R_{1},K_{2},R_{2}\dots,R_{n}),\dots,(R_{1},\dots,R_{n-1},K_{n})\\}$,

$T_{2}=\\{(I_{1},\dots,I_{n})\in
V(PIS(R))|\,\,I_{i}=K_{i},I_{j}=\mathfrak{m}_{j}\,\mathrm{with\,\,i\neq
j}\,\mathrm{and\,\,for\,\,every}\,k\in\\{1,\dots,n\\}\setminus\\{i,j\\},I_{k}=R_{k}\\}$
and

$T_{3}=W\setminus\\{T_{1}\cup T_{2}\\}$.

Arrange the elements of $W$ as follows:

$W=\\{\underbrace{w_{1},\dots,w_{|T_{1}|}}_{\in
T_{1}},\underbrace{w_{|T_{1}|+1},\dots,w_{|T_{1}|+|T_{2}|}}_{\in
T_{2}},\underbrace{w_{|T_{1}|+|T_{2}|+1},\dots,w_{|W|}}_{\in T_{3}}\\}.$

If $I\in V_{1}$, then

$D(I|W)=(\underbrace{2,\dots,2}_{|T_{1}|},\underbrace{y_{1},\dots,y_{|T_{2}|}}_{|T_{2}|},\underbrace{z_{1},\dots,z_{|T_{3}|}}_{|T_{3}|}),$

such that $y_{i}\in\\{1,2\\}$ and $y_{i}\neq y_{j}$, for some $1\leq
i,j\leq|T_{2}|$ with $i\neq j$.

If $I\in V_{2}$, then

$D(I|W)=(\underbrace{x_{1},\dots,x_{|T_{1}|}}_{|T_{1}|},\underbrace{2,\dots,2}_{|T_{2}|},\underbrace{z_{1},\dots,z_{|T_{3}|}}_{|T_{3}|}),$

such that $x_{i}\in\\{1,2\\}$ and $x_{i}\neq x_{j}$, for some $1\leq
i,j\leq|T_{1}|$ with $i\neq j$.

Finally, if $I\in V_{3}$, then

$D(I|W)=(\underbrace{x_{1},\dots,x_{|T_{1}|}}_{|T_{1}|},\underbrace{y_{1},\dots,y_{|T_{2}|}}_{|T_{2}|},\underbrace{z_{1},\dots,z_{|T_{3}|}}_{|T_{3}|}),$

such that $x_{i}=y_{j}=1$, where $1\leq i\leq|T_{1}|$ and $1\leq
j\leq|T_{2}|$.

The above vectors shows that $D(I|W)\neq D(J|W)$, if $I\in V_{i}$ and $J\in
V_{j}$, for every $1\leq i,j\leq 3$ with $i\neq j$. Next, we show that
$D(I|W)\neq D(J|W)$, if $I,J\in V_{i}$, for every $1\leq i\leq 3$. The
following cases should be considered:

Case 1. $I,J\in V_{1}$. Since $I\neq J$, with no loss of generality, one may
assume that $I_{i}=0$ and $J_{i}=R_{i}$, for some $1\leq i\leq n$. Moreover,
$J_{i}=R_{i}$ implies that the zero element must appear among components of
$J$. Let $J_{k}=0$ ($J_{k}$ is the $k$-th component of $J$), for some $k\neq
i$. Consider $y=(y_{1},\dots,y_{n})\in T_{2}$ such that $y_{i}=K_{i}$ and
$y_{k}=\mathfrak{m}_{k}$. Moreover, the other components of $y$ are $R_{j}$’s,
$j\neq i,k$. Now, $d(I,y)=2$ and $d(J,y)=1$ and so $D(I|W)\neq D(J|W)$.

Case 2. $I,J\in V_{2}$. Since $I\neq J$, without lost of generality, we may
assume that $I_{i}=0$ and $J_{i}=\mathfrak{m}_{i}$, for some $1\leq i\leq n$.
Consider $x=(x_{1},\dots,x_{n})\in T_{1}$ such that $x_{i}=K_{i}$. Moreover,
the other components of $x$ are $R_{j}$’s, $j\neq i$. Since $d(I,x)=2\neq
1=d(J,x)$, $D(I|W)\neq D(J|W)$.

Case 3. $I,J\in V_{3}$. The following subcases may occur:

Subcase 1. $I_{i}=\mathfrak{m}_{i}$ and $J_{i}=0$, for some $1\leq i\leq n$.
Since $I_{i}=\mathfrak{m}_{i}$, for some $1\leq j\leq n$ with $i\neq j$,
$I_{j}=R_{j}$. Let $y=(y_{1},\dots,y_{n})\in T_{3}$ such that $y_{i}=K_{i}$
and $y_{j}=K_{j}$. Moreover, the other components of $y$ are $R_{k}$’s, $k\neq
i,j$. Now, $d(I,y)=1$ and $d(J,y)=2$ and so $D(I|W)\neq D(J|W)$.

Subcase 2. $I_{i}=\mathfrak{m}_{i}$ and $J_{i}=R_{i}$, for some $1\leq i\leq
n$. Since $J_{i}=R_{i}$, for some $1\leq j\leq n$ with $i\neq j$,
$J_{j}=\mathfrak{m}_{j}$. If $I_{j}=\mathfrak{m}_{j}$, then let
$y=(y_{1},\dots,y_{n})\in T_{2}$ such that $y_{i}=K_{i}$ and
$y_{j}=\mathfrak{m}_{j}$. Moreover, the other components of $y$ are $R_{k}$’s,
$k\neq i,j$. Now, $d(I,y)=2$ and $d(J,y)=1$ and so $D(I|W)\neq D(J|W)$. If
$I_{j}=R_{j}$, then let $y=(y_{1},\dots,y_{n})\in T_{1}$ such that
$y_{j}=K_{j}$ and the other components of $y$ are $R_{i}$’s, $i\neq j$. Now,
$d(I,y)=2$ and $d(J,y)=1$ and so $D(I|W)\neq D(J|W)$.

Subcase 3. $I_{i}=\mathfrak{m}_{i}$ if and only if $J_{i}=\mathfrak{m}_{i}$,
for every $1\leq i\leq n$. Thus there exists $1\leq j\leq n$ such that
$I_{j}=R_{j}$ and $J_{j}=0$. We note that there exists $k\neq i,j$ $J$ such
that $J_{k}=R_{k}$ with. Let $y=(y_{1},\dots,y_{n})\in T_{3}$ such that
$y_{i}=K_{i}$, $y_{j}=0$ and the other components of $y$ are equal $R_{k}$’s,
$k\neq i,j$. Now, $d(I,y)=1$ and $d(J,y)=2$ and so $D(I|W)\neq D(J|W)$.
$\Box$

The following corollary is an immediate consequence of Theorem 3.2.

###### Corollary 3.1

Suppose that $R\cong R_{1}\times\cdots\times R_{n}$, where $R_{i}$ is an
Artinian local ring such that for every $1\leq i\leq n$, $|A(R_{i})^{*}|=2$.
Then $dim_{M}(PIS(R))=4^{n}-3^{n}-1$.

###### Corollary 3.2

Let $R\cong S_{1}\times S_{2}\times S_{3}$, $n,m,k$ are non-negative integer
with $n,m,k\not\in\\{1,2,3\\}$, $S_{1}\cong R_{1}\times\cdots\times R_{n}$,
$S_{2}\cong R^{\prime}_{1}\times\cdots\times R^{\prime}_{m}$ and $S_{3}\cong
F_{1}\times\cdots\times F_{k}$, where $(R_{i},\mathfrak{m}_{i})$ is an
Artinian local principal ideal ring such that for every $1\leq i\leq n$,
$|A(R_{i})^{*}|\geq 2$, $(R^{\prime}_{i},\mathfrak{m}^{\prime}_{i})$ is an
Artinian local ring such that $|A(R^{\prime}_{i})^{*}|=1$, for every $1\leq
i\leq m$ and $F_{i}$ is a field, for every $1\leq i\leq k$. Then
$dim_{M}(PIS(R))=|A(R)^{*}|-3^{n+m}2^{k}+2m+k+2$.

###### Proof.

Assume that

$A=\\{(I_{1},\dots,I_{n+m+k})\in
V(PIS(R))\,\,|\,\,I_{i}\in\\{0,R_{i},\mathfrak{m}_{i},R^{\prime}_{j},\mathfrak{m}^{\prime}_{j},F_{t}\\}\,\,\mathrm{for\,\,every}\,\,1\leq
i\leq n,\,\,n+1\leq j\leq n+m,\,\,n+m+1\leq t\leq n+m+k\\}$,

$B=\\{(R_{1},\dots,R_{n},0,R^{\prime}_{2},\dots,R^{\prime}_{m},F_{1},\dots,F_{k}),(R_{1},\dots,R_{n},R^{\prime}_{1},0,R^{\prime}_{3},\dots,R^{\prime}_{m},F_{1},\dots,F_{k}),$
$\dots,(R_{1},\dots,R_{n},R^{\prime}_{1},R^{\prime}_{2},\dots,R^{\prime}_{m-1},0,F_{1},\dots,F_{k})\\}$,

$C=\\{(R_{1},\dots,R_{n},\mathfrak{m}^{\prime}_{1},R^{\prime}_{2},\dots,R^{\prime}_{m},F_{1},\dots,F_{k}),(R_{1},\dots,R_{n},R^{\prime}_{1},\mathfrak{m}^{\prime}_{2},R^{\prime}_{3},\dots,R^{\prime}_{m},F_{1},\dots,F_{k}),$

$\dots,(R_{1},\dots,R_{n},R^{\prime}_{1},R^{\prime}_{2},\dots,R^{\prime}_{m-1},\mathfrak{m}^{\prime}_{m},F_{1},\dots,F_{k})\\}$,

$V_{1}=A(R)^{*}\setminus A$,

$V_{2}=B\cup C$ and

$V_{3}=\\{(R_{1},\dots,R_{n},R^{\prime}_{1},\dots,R^{\prime}_{m},0,F_{2},\dots,F_{k}),(R_{1},\dots,R_{n},R^{\prime}_{1},\dots,R^{\prime}_{m},F_{1},0,F_{2},\dots,F_{k}),$

$\dots,(R_{1},\dots,R_{n},R^{\prime}_{1},\dots,R^{\prime}_{m},F_{1},\dots,F_{k-1},0)\\}.$

Arrange the elements of $W$ as follows:

$W=\\{\underbrace{w_{1},\dots,w_{|V_{1}|}}_{\in
V_{1}},\underbrace{w_{|V_{1}|+1},\dots,w_{|V_{1}|+|V_{2}|}}_{\in
V_{2}},\underbrace{w_{|V_{1}|+|V_{2}|+1},\dots,w_{|V_{1}|+|V_{2}|+|V_{3}|}}_{\in
V_{3}}\\}.$

By similar proofs of Theorems 3.1, 3.2 and 2.1, $W$ is a metric basis for
$PIS(R)$ and so
$dim_{M}(PIS(R))=|W|=|V_{1}|+|V_{2}|+|V_{3}|=|A(R)^{*}|-3^{n+m}2^{k}+2m+k+2$.
$\Box$

We close this paper with the following example which shows that the condition
$n,m,k\not\in\\{1,2,3\\}$ is required in Corollary 3.2.

###### Example 3.2

$(1)$ Let $R=\mathbb{Z}_{4}\times\mathbb{Z}_{2}$. By the following figure, we
have $dim_{M}(PIS(R))=2$. But $n=0$ and $m=k=1$ do not satisfy in Corollary
3.2.
$(0)\times\mathbb{Z}_{2}$$<2>\times\mathbb{Z}_{2}$$<2>\times(0)$$\mathbb{Z}_{4}\times(0)$$PIS(\mathbb{Z}_{4}\times\mathbb{Z}_{2})$

$(2)$ Let $R=\mathbb{Z}_{4}\times\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ and
$W=\\{(0,\mathbb{Z}_{2},\mathbb{Z}_{2}),(\mathbb{Z}_{4},0,\mathbb{Z}_{2}),(\mathbb{Z}_{4},\mathbb{Z}_{2},0)\\}$.
Then

$D({(\mathfrak{m}_{1},\mathbb{Z}_{2},\mathbb{Z}_{2})}|W)=(1,2,2)$,

$D({(\mathfrak{m}_{1},0,\mathbb{Z}_{2})}|W)=(1,1,2)$,

$D({(\mathfrak{m}_{1},\mathbb{Z}_{2},0)}|W)=(1,2,1)$,

$D({(\mathfrak{m}_{1},0,0)}|W)=(1,1,1)$,

$D({(0,0,\mathbb{Z}_{2})}|W)=(2,1,2)$,

$D({(0,\mathbb{Z}_{2},0)}|W)=(2,2,1)$,

$D({(\mathbb{Z}_{4},0,0)}|W)=(2,1,1).$

Then $dim_{M}(PIS(R))=3$. But $n=0$, $m=1$ and $k=2$ do not satisfy in
Corollary 3.2.

## References

  * [1] M. F. Atiyah, I.G. Macdonald, Introduction to Commutative Algebra, Addison-Wesley Publishing Company (1969).
  * [2] G. Chartrand, L. Eroh, M. A. Johnson, O. R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000) 99-113.
  * [3] D. Dol${\rm\check{z}}$an, The metric dimension of the total graph of a finite commutative ring, Canad. Math. Bull. 59 (2016) 748-759.
  * [4] D. Dol${\rm\check{z}}$an, The metric dimension of the annihilating-ideal graph of a finite commutative ring, Bull. Aust. Math. Soc. 103 (2021) 362–368.
  * [5] Sh. Ebrahimi, R. Nikandish, A. Tehranian, H. Rasouli, Metric dimension of complement of annihilator graphs associated with commutative rings, Appl. Algebra Eng. Commun. Comput. (2021) https://doi.org/10.1007/s00200-021-00533-4.
  * [6] F. Harary, R. A. Melter, On the metric domension of a graph, Ara Combin. 2 (1976) 191–195.
  * [7] Z. Jiang, N. Polyanskii, On the metric dimension of Cartesian powers of a graph, J. Comb. theory Ser. A. 165 (2019) 1–14.
  * [8] S. Khuller, B Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (3) (1996) 217–229.
  * [9] X. Ma, L. Li, On the metric dimension of the reduced power graph of a finite group, Taiwanese J. Math. 26(1) (2022) 1–15.
  * [10] R. Nikandish, M. J. Nikmehr, M. Bakhtyiari, Metric and strong metric dimensions in cozero-divisor graphs of commutative rings, Mediterr. J. Math. 18, 112 (2021).https://doi.org/10.1007/s00009-021-01772-y.
  * [11] S. Pirzada, M. Aijaz, S. P. Redmond, Upper dimension and bases of zero-divisor graphs of commutative rings, AKCE International Journal of Graphs and Combinatorics, (2020) 168–173.
  * [12] S. Pirzada, M. Imran Bhat, Computing metric dimension of compressed zero divisor graphs associated of rings, Acta Univ. Sap. Mathematica, 10, 2 (2018) 298–318.
  * [13] S. Pirzada, R. Raja , On the metric domension of a zero-divisor graph, Comm. Algebra, 45:4 (2017): 1399–1408.
  * [14] M. Saha, A. Das, E. Yetkin Celikel, C. Abdio${\rm\breve{g}}$lu, Prime ideal sum graph of a commutative rings, J. Algebra Appl. (2023) 2350121 (14 pages) DOI: 10.1142/S0219498823501219.
  * [15] R. Shahriyari, R. Nikandish, A. Tehranian, and H. Rasouli, Computing the strong metric dimension for co-maximal ideal graphs of commutative rings, J. Algebra Appl. (2024) 2450048 (13 pages) DOI: 10.1142/S0219498824500488.
  * [16] P. J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549–559.
  * [17] D. B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, Upper Saddle River (2001).


# The Near Miss Effect
and the Framing of Lotteries††thanks: I am grateful to Rani Spiegler for his
valuable guidance and comments. I thank Yair Antler, Ayala Arad, Itzhak
Gilboa, Simon Litsyn, Zvika Neeman, Ariel Rubinstein, and Itzhak Tamo for
helpful discussions and comments.

Michael Crystal Tel Aviv University, E-mail<EMAIL_ADDRESS>
###### Abstract

We present a framework for analyzing the near miss effect in lotteries. A
decision maker (DM) facing a lottery, falsely interprets losing outcomes that
are close to winning ones, as a sign that success is within reach. As a result
of this false belief, the DM will prefer lotteries that induce a higher
frequency of near misses, even if the underlying probability of winning is
constant. We define a near miss index that measures the near miss effect
induced by a given lottery and analyze the optimal lottery design in terms of
near miss. This analysis leads us to establish a fruitful connection between
our near miss framework and the field of coding theory. Building on this
connection we compare different lottery frames and the near miss effect they
induce. Analyzing an interaction between a seller and a buyer of lotteries
allows us to gain further insight into the optimal framing of lotteries and
might offer a potential explanation as to why lotteries with a very small
probability of winning are commonplace and attractive.

Keywords: Near Miss, Framing, Coding theory, Covering codes.

##  1 Introduction

A miss is as good as a mile. This principle points to the fact that failing to
achieve a certain goal is considered a failure, regardless of how close one
came to success.

A rational DM should follow this principle in lotteries that are governed by
pure chance. That is because coming close to success does not provide any
useful information regarding the DM’s ability or any indication that success
is imminent. For example, consider a lottery in which $n$ independent and
identically distributed numbers are randomly drawn and participants receive a
prize only if they guessed all numbers correctly. In this lottery, one should
not hold different interpretations for guessing correctly $n-1$ numbers or
none of them.

Nevertheless, studies have shown that many individuals falsely interpret
events in which they come very close to the desired outcome, also known as
near miss events, as an indication of imminent success. Skinner (1953) was the
first to identify the near miss effect by claiming that in games of pure
chance near miss events reinforce continued play. Later studies strengthened
his claim by showing that individuals indeed react differently to different
kinds of misses (see Clark et al. (2009), Foxall and Sigurdsson (2012) and
Sundali et al. (2012) for such studies).

Reid (1986) showed that near misses in slot machine pay-lines resulted in
longer playing time. He argued that:

> Commercial gambling systems, particularly instant lotteries and slot
> machines, are contrived to ensure a higher frequency of near misses than
> would be expected by chance alone. (p. 32)

The Nevada Gaming Commission addressed this issue with a 1989 ruling that
banned the design and programming of higher frequencies of near misses than
chance alone.111Nevada Gaming Commission (1988, 1989). Nevada State Gaming
Control Board v. Universal Distributing of Nevada. Case-No. 88-4.

This paper proposes an approach to modeling the near miss effect induced by
different lottery frames and its influence on the subjective valuation of
lotteries. To model the near miss effect we need to describe the relevant
lottery framing and the metric used to measure the distance between any two
possible outcomes. Motivated by the framing of slot machines our lotteries
will consist of vectors of length $n$ in which each coordinate attains values
from an alphabet of symbols $Q$ of size $q$. This possible set of outcomes,
denoted by $Q^{n}$ along with a subset of winning outcomes $W\subseteq Q^{n}$
fully describes a lottery in our setting. Therefore, a lottery is depicted by
the triplet $\left(q,n,W\right)$. We assume that each possible outcome is
equally likely and thus the probability of winning is given by
$p=\frac{|W|}{q^{n}}$. We assume that there is no inner metric in our alphabet
of symbols and thus a natural measure for the distance between lottery
outcomes is the number of coordinates in which they differ.

We define a near miss index that captures the near miss effect induced by a
given lottery and obtains values between zero and one. This index allows us to
draw comparisons between different lotteries. Notably, we can form clear
distinctions between different lotteries that have the same objective
probability of winning, but entail a different framing that affect the near
miss index. A rational DM will be indifferent between lotteries with an
identical probability of winning and identical payoffs. However, a non-
rational DM, who is sensitive to near misses might prefer one lottery over
another, due to the former having a greater near miss effect.

Near misses might influence the DM’s belief formation in the following sense:
A rational DM taking part in a certain lottery will eventually form a correct
belief over the probability of winning because he views all losing outcomes
identically. However, for a non-rational DM, losing outcomes that are close to
winning ones might provide positive feedback that will lead to a distortion in
his probabilistic assessment and result in a higher perceived probability of
winning. Thus, we can interpret the near miss index as the DM’s perceived
probability of winning. Therefore, different lottery framing might have a
substantial impact on the subjective lottery valuation. This leads us to the
following question: Given an objective probability of winning $p$, what is the
lottery framing that maximizes the perceived probability of winning?

The search for an optimal lottery frame takes us down an unexpected path to
the field of information theory and connects our near miss index with coding
theory and the study of covering codes (see Cohen et al. (1997) for a
textbook).

We will show that designing an optimal lottery is an open problem that
generalizes the thoroughly studied covering code problem. Although the optimal
lottery frame remains out of reach, we are still able to rank general lottery
frames in terms of the near miss effect they generate. That is achieved by
modifying results from coding theory and adapting them to our near miss
analysis. We will show that by setting the lottery’s parameters accordingly we
obtain lottery frames that are preferable in terms of the near miss effect
they induce.

The paper proceeds as follows: Section 2 introduces the near miss framework,
describing the set of lotteries that will be analyzed and the near miss index
definition for these lotteries. Also, the connection between the near miss
index and the field of coding theory is established. Section 3 presents the
optimal lottery analysis and compares different lottery frames and the near
miss effect they induce. Furthermore, bounds on the near miss index are
derived. Section 4 describes an interaction between a seller who designs a
lottery and a buyer considering paying for it.

##  2 Near Miss Framework

Let $Q$ be a finite set of size $q\in\mathbb{N}$ that describes the alphabet
of symbols and let $n\in\mathbb{N}$ be the length of a possible lottery
outcome. Denote by $Q^{n}$ the set of all possible lottery outcomes. Thus,
each lottery outcome $x\in Q^{n}$ will be represented by an n-dimensional
vector in which each coordinate may obtain a finite set of values depicted by
the alphabet. We denote by $W\subseteq Q^{n}$ the subset of winning outcomes.

Therefore, a lottery is given by the triplet $\left(q,n,W\right)$. The framing
of the lottery is defined by its length, alphabet size and the winning set of
outcomes. Note that our lottery space consists of all possible lotteries that
have $q^{n}$ outcomes. We restrict attention to lotteries with identical
prizes and a uniform distribution over $Q^{n}$. Therefore, the probability of
winning, denoted by $p$, is given by $p=\frac{|W|}{q^{n}}$.

###  2.1 Near Miss index

The definition of a near miss index must incorporate a clear distinction
between different losing outcomes and their proximity to winning ones. For
this distinction we need to define a measure of distance between any two
possible outcomes in our lottery space. To address that, we will use the
Hamming distance, which was introduced by Hamming (1950).

######  Definition 1 (Hamming distance).

The Hamming distance between two equal-length vectors
$\mathrm{\bm{x}}=\left(x_{1},x_{2},\ldots,x_{n}\right)$,
$\mathrm{\bm{y}}=\left(y_{1},y_{2},\ldots,y_{n}\right)$ is the number of
coordinates in which they differ, i.e.,

$d\left(\mathrm{\bm{x}},\mathrm{\bm{y}}\right)=\hskip
2.84544pt\mid\left\\{i\colon x_{i}\neq y_{i}\right\\}\mid\\\ $ (1)

Note that by using the Hamming distance we assume that the distance between
any two lottery outcomes depends solely on the number of coordinates in which
they differ and not on the specific values these coordinates attain. This
assumption is plausible if the alphabet is comprised of unrelated symbols. For
example, in a slot machine, it is not clear whether the symbol 7 is closer to
a bar or a cherry. However, if the alphabet is comprised of numbers this
assumption seems less plausible because in that case, the alphabet has a clear
inner metric (e.g. guessing that 6 is one of the winning numbers in a lottery
ticket or guessing that 2 is, will likely be viewed differently by the DM if
the winning number turns out to be 7).

Using the Hamming distance we define the near miss index as follows.

######  Definition 2 (Near Miss Index).

The Near Miss Index for a lottery $\left(q,n,W\right)$ is given by:

$\mathcal{NM}\left(q,n,W\right)=\mathbb{E}_{x\in{Q^{n}}}\left(1-\frac{\min_{w\in{W}}d(x,w)}{n}\right)$
(2)

The near miss index is a weakly decreasing transformation of the expected
minimal Hamming distance to a winning outcome, where $\min_{w\in
W}d\left(x,w\right)$ is the minimal number of shifts needed to obtain a
winning outcome given a certain outcome $x\in Q^{n}$. Note that for any given
lottery the near miss index obtains values from zero to one, i.e.
$0\leq\mathcal{NM}\left(q,n,W\right)\leq 1$. The division by the lottery’s
length takes into account that being $k$ shifts away from a winning outcome is
intuitively closer to it as the lottery’s length increases.

As noted, a possible interpretation of the near miss index is the perceived
probability of winning. Following this interpretation, a DM facing a lottery
with a higher near miss index will form a belief that the underlying
probability of winning is higher than the actual objective one.

######  Example 1 (Slot Machine).

Consider a slot machine comprised of three reels and two equally likely
symbols - 7 or bar.

First, assume that there are two possible winning outcomes, either all three
reels show 7 or all three show bar. The set of outcomes of this lottery is
given by $\left\\{7,B\right\\}^{3}$. Each outcome is represented by a three
dimensional vector in which each coordinate is either 7 or bar, i.e. -
$x=\left(x_{1},x_{2},x_{3}\right)$ where $x_{i}\in\left\\{7,B\right\\}$. Thus,
this lottery can be represented by
$\left(q,n,W\right)=\left(2,3,\left\\{\left(7,7,7\right),\left(B,B,B\right)\right\\}\right)$
The near miss index for this lottery is given by:

$\begin{split}\mathcal{NM}\left(2,3,\left\\{\left(7,7,7\right),\left(B,B,B\right)\right\\}\right)&=\frac{1}{4}\cdot\left(1-\frac{0}{3}\right)+\frac{3}{4}\cdot\left(1-\frac{1}{3}\right)\\\\[10.0pt]
&=\frac{1}{4}+\frac{3}{4}\cdot\frac{2}{3}=\frac{3}{4}\\\\[10.0pt] \end{split}$

Alternatively, take the winning set of outcomes to be
$W^{{}^{\prime}}=\left\\{\left(7,7,7\right),\left(B,B,7\right)\right\\}$. This
lottery which is represented by
$\left(q,n,W\right)=\left(2,3,\left\\{\left(7,7,7\right),\left(B,B,7\right)\right\\}\right)$
obtains a near miss index of:

$\begin{split}\mathcal{NM}\left(2,3,\left\\{\left(7,7,7\right),\left(B,B,7\right)\right\\}\right)&=\frac{1}{4}\cdot\left(1-\frac{0}{3}\right)+\frac{2}{4}\cdot\left(1-\frac{1}{3}\right)+\frac{1}{4}\cdot\left(1-\frac{2}{3}\right)\\\\[10.0pt]
&=\frac{1}{4}+\frac{2}{4}\cdot\frac{2}{3}+\frac{1}{4}\cdot\frac{1}{3}=\frac{2}{3}\\\\[10.0pt]
\end{split}$

Note that both lotteries have the same objective probability of winning,
however, they differ in their near miss index and thus might induce different
perceived winning probability. We can see that even if we keep $q$, $n$ and
the size of $W$ fixed, changing the specific winning outcomes might result in
a different near miss index.

Moreover, we can see that when
$W=\left\\{\left(7,7,7\right),\left(B,B,B\right)\right\\}$, the Hamming
distance from any losing outcome to a winning one is at most one. Therefore,
if we set the objective probability of winning at $p=\frac{1}{4}$, this
specification of $W$ along with $q=2$ and $n=3$ maximizes the near miss index.
$\diamondsuit$

A natural question that arises is: Can we increase the perceived probability
of winning by changing the triplet $\left(q,n,W\right)$ while keeping the
objective probability of winning constant at some $p$.

###  2.2 Near Miss and Codes

Coding theory mainly focuses on the study of codes and their properties. It is
relevant to several scientific fields such as information theory and computer
science. We present a concise description of covering codes and the connection
to our near miss framework.

######  Definition 3 ($q$-ary codes).

Let $Q$ be a finite set with q elements. A nonempty subset $W$ of $Q^{n}$ is
called a $q$-ary code of length n.

For instance, in Example 1 the alphabet is given by $Q=\left\\{7,B\right\\}$,
which is the binary case. The set $Q^{n}$ is known in the literature as the
$n$-dimensional $q$-ary Hamming space. The vectors belonging to a code $W$ are
called code-words. Thus, the winning set of outcomes corresponds to a $q$-ary
code where each winning outcome corresponds to a code-word.

######  Definition 4 (Covering Radius).

The covering radius of a code $W\subseteq Q^{n}$ is the smallest integer $R$
such that every vector $x\in Q^{n}$ is $R$-covered by at least one code-word
of $W$, i.e.,

$\begin{split}R&=\max_{x\in Q^{n}}d\left(x,W\right)\\\\[5.0pt] &=\max_{x\in
Q^{n}}\min_{w\in W}d\left(x,w\right)\end{split}$

Where $d\left(x,w\right)$ is the hamming distance.

In other words, the covering radius of a code $W$ is the distance between the
code and the farthest-off vectors (i.e. code-words) in the Hamming space. A
code $W$ with a covering radius $R$ is called a $q$-ary $R$-covering code.

Denote by $K_{q}\left(n,R\right)$ the minimal cardinality of a $q$-ary
$R$-covering code with length $n$. That is, $K_{q}\left(n,R\right)$ is the
minimal number of code-words needed to ensure that every code-word in
$n$-dimensional $q$-ary Hamming space is $R$-covered. The following table
presents some known values of $K_{q}\left(n,R\right)$ for the binary case and
$R\in\left\\{1,2\right\\}$.222See
http://old.sztaki.hu/~keri/codes/2_tables.pdf for known values of
$K_{2}\left(n,R\right)$.

$K_{2}(n,R)$ | $n=1$ | $n=2$ | $n=3$ | $n=4$ | $n=5$ | $n=6$ | $n=7$ | $n=8$ | $n=9$ | $n=10$
---|---|---|---|---|---|---|---|---|---|---
$R=1$ | 1 | 2 | 2 | 4 | 7 | 12 | 16 | 32 | 62 | 107-120
$R=2$ |  | 1 | 2 | 2 | 2 | 4 | 7 | 12 | 16 | 24-30
Table 1: $K_{2}\left(n,R\right)$ \- Size of minimal binary covering codes

We can see from Table 1 that even for the relatively simple case of $q=2$, if
we set $n=10$ the value of $K_{q}\left(n,R\right)$ is unknown. Finding
$K_{q}\left(n,R\right)$ for finite parameters $q,n$ and $R$ is called the
covering code problem. This problem is an open one and there is no known
algorithm or constructive solution for it. Note that an optimal construction
of minimal covering codes yields an optimal lottery frame for certain winning
probabilities. Thus, finding an optimal near miss index for any given
objective probability of winning $p$ generalizes the covering code problem.

Although such a construction remains unknown, adapting several results from
coding theory and modifying them to fit our near miss analysis will allow us
to compare general lottery frames.

##  3 Lottery Frames

In this section we will analyze different lottery frames, keeping the
objective probability of winning fixed. We will show that certain frames
induce a higher near miss effect.

We begin with presenting several qualitative results revolving around the
impact of $q$ and $n$ on the near miss effect. These preliminary results use
elementary arguments that do not rely on the coding theory analogy.

We start by examining the case where the number of possible lottery outcomes
is constant and allow for variation in $n$ and $q$. We show that the optimal
lottery frame will be achieved by increasing the length of the lottery while
reducing the alphabet size.

######  Proposition 1.

Fix an objective probability of winning $p$. For any $t\in\mathbb{N}$ and any
lottery $\left(q^{t},n,W\right)$ there exists a lottery
$\left(q,tn,W^{{}^{\prime}}\right)$ such that:

$\mathcal{NM}\left(q,tn,W^{{}^{\prime}}\right)\>\geq\>\mathcal{NM}\left(q^{t},n,W\right)$
(3)

Proof. Given a lottery $\left(q^{t},n,W\right)$ we will construct the lottery
$\left(q,tn,W^{{}^{\prime}}\right)$ such that $|W|=|W^{{}^{\prime}}|$ and (3)
holds.

Let $Q$ be the alphabet of size $q$ and define the set $Q\times\dots\times Q$
to be the alphabet of size $q^{t}$. Denote by $g:\left(Q^{t}\right)^{n}\to
Q^{tn}$ the bijective mapping that takes a vector of length $n$ over the
alphabet $Q\times\dots\times Q$ and maps it to a vector of length $tn$ over
the alphabet $Q$ by expanding each of the $n$ coordinates to a vector of
length $t$. For example, let $Q=\left\\{7,B\right\\}$, $t=2$, $n=2$, and
$x=\left(7B,77\right)\in\left(Q\times Q\right)^{2}$. Expanding each coordinate
of $x$ to a vector of length 2 we obtain $g(x)=\left(7,B,7,7\right)\in Q^{4}$.

Given a winning set of outcomes $W$ which is defined by vectors of length $n$
over the alphabet $Q\times\dots\times Q$ we will construct the winning set of
outcomes $W^{{}^{\prime}}$ by $g\left(W\right)$.

Note that $|W|=|W^{{}^{\prime}}|$ is immediate from construction. Moreover,
for each possible outcome $x\in\left(Q^{t}\right)^{n}$ the following holds:

$t\cdot\left(\min_{w\in W}d\left(x,w\right)\right)\geq\min_{g\left(w\right)\in
g\left(W\right)}d\left(g\left(x\right),g\left(w\right)\right)$

The above inequality holds due to the following: Assume that for a given
outcome $x\in\left(Q^{t}\right)^{n}$ the following $\min_{w\in
W}d\left(x,w\right)=k$ holds for some $k\in\mathbb{N}$. Take any coordinate in
which $x$ and $w$ differ. Expanding this coordinate in both $x$ and $w$ to
vectors of length $t$ will result in two vectors that differ by at most $t$
coordinates. Thus, the Hamming distance between $g(x)$ and $g(w)$ will be at
most $t\cdot k$.

Therefore,

$\begin{split}\mathcal{NM}\left(q,tn,W^{{}^{\prime}}\right)&=1-\frac{1}{tn}\mathbb{E}_{g\left(x\right)\in
g\left(\left(Q^{t}\right)^{n}\right)}\left[\min_{g\left(w\right)\in
g\left(W\right)}d\left(g\left(x\right),g\left(w\right)\right)\right]\\\\[10.0pt]
&\geq
1-\frac{1}{tn}\mathbb{E}_{x\in\left(Q^{t}\right)^{n}}\left[t\cdot\min_{w\in
W}d\left(x,w\right)\right]\\\\[10.0pt]
&=1-\frac{1}{n}\mathbb{E}_{x\in\left(Q^{t}\right)^{n}}\left[\min_{w\in
W}d\left(x,w\right)\right]\\\\[10.0pt]
&=\mathcal{NM}\left(q^{t},n,W\right)\end{split}$

∎

This result leverages the fact that the alphabet has no inner metric and
indicates that if our goal is to increase the near miss index and we were to
design a slot machine we would increase the number of reels and reduce the
number of symbols. However, there are feasibility constraints in designing a
slot machine with many reels, one of them is the physical space it requires.
Also, increasing the number of reels might complicate the DM’s inference as to
whether a given outcome is close or far from a winning one. This leads us to
our next result.

Assuming that the lottery’s length is set at some $n\in\mathbb{N}$, increasing
the alphabet size is weakly preferable in terms of near miss.

######  Proposition 2.

Fix an objective probability of winning $p$. For any $t\in\mathbb{N}$ and any
lottery $\left(q,n,W\right)$ there exists a lottery
$\left(tq,n,W^{{}^{\prime}}\right)$ such that:

$\mathcal{NM}\left(tq,n,W^{{}^{\prime}}\right)\>\geq\>\mathcal{NM}\left(q,n,W\right)$
(4)

Proof. Given a lottery $\left(q,n,W\right)$ we will construct the winning set
of outcomes $W^{{}^{\prime}}$ such that $|W^{{}^{\prime}}|=|W|\cdot t^{n}$ and
we will show that (4) holds.

Let $Q=\\{1,2,\dots,q\\}$ be the alphabet of size $q$. Denote by
$T=\\{1_{1},1_{2},\dots,1_{t},2_{1},2_{{}_{2}},\\\
\dots,2_{t},\dots,q_{1},\dots,q_{t}\\}$ the alphabet of size $tq$. We will
construct the winning set of outcomes $W^{{}^{\prime}}$ by associating with
each vector $w=(a,b,\dots,c,d)$ in $W$ the following $t^{n}$ vectors:

$(a_{i},b_{j},\dots,c_{k},d_{l}),\;1\leq i,j,\dots,k,l\leq t$

Note that $|W^{{}^{\prime}}|=|W|\cdot t^{n}$ is immediate from construction.
Let $u=(u_{1},\dots,u_{n})$ be a vector in $Q^{n}$ and assume that $w\in{W}$
is the closest winning outcome to $u$. Denote by $U$ the $t^{n}$ vectors
associated with $u$ and by $\bar{W}$ the $t^{n}$ vectors associated with $w$.
Note that by construction, for each vector in $U$ there exists a vector in
$\bar{W}$ located at a Hamming distance of $d(u,w)$. Therefore we have found a
specific construction in which equation (4) holds with equality. Moreover, by
setting $q=n=t=2$ and $p=\frac{1}{4}$ equation (4) holds with strict
inequality. That is because these parameters imply that $|W|=1$ and
$|W^{{}^{\prime}}|=4$. This along with the fact that $K_{4}\left(2,1\right)=4$
and $K_{2}\left(2,1\right)=2$ completes the proof. ∎

Some real-life evidence from the design of slot machines over the years might
suggest that these considerations were taken into account. From their
creation, at the end of the nineteenth century to this day, the most common
design is the three reel slot machine (i.e. the length of the lottery is
$n=3$). However, the number of symbols in most slot machines increased from
just five to around twenty (i.e. $q=20$). Moreover, some virtual slot machines
have as many as 256 symbols.

Moving forward, our next result shows that if we fix the lottery’s alphabet
size at some $q\in\mathbb{N}$, increasing the length will result in a higher
near miss index.

######  Proposition 3.

Fix an objective probability of winning $p$. For any lottery
$\left(q,n,W\right)$ there exists a lottery
$\left(q,n+1,W^{{}^{\prime}}\right)$ such that:

$\mathcal{NM}\left(q,n+1,W^{{}^{\prime}}\right)\>>\>\mathcal{NM}\left(q,n,W\right)\
$ (5)

Proof. Given a lottery $\left(q,n,W\right)$ we will construct the lottery
$\left(q,n+1,W^{{}^{\prime}}\right)$ such that $|W^{{}^{\prime}}|=|W|\cdot q$
and (5) holds.

Let $Q$ denote the alphabet of size $q$. Given a lottery $\left(q,n,W\right)$
we will use $W$ and $Q$ to construct the winning set of outcomes
$W^{{}^{\prime}}$ by the following:

$W^{{}^{\prime}}=W\oplus Q=\left\\{\left(w,w_{n+1}\right):w\in W,w_{n+1}\in
Q\right\\}$

In other words, $W^{{}^{\prime}}$ is the concatenation of all $n$-dimensional
code-words $w\in W$ with all $1$-dimensional code-words $w_{n+1}\in Q$.

$|W^{{}^{\prime}}|=|W|\cdot q$ is immediate from construction. Note that the
set of outcomes $Q^{n+1}$ can be written as $Q^{n}\oplus Q$. Thus, the minimal
distance between an outcome $x^{{}^{\prime}}=\left(x,x_{n+1}\right)\in
Q^{n+1}$ to a winning outcome is given by:

$\min_{w^{{}^{\prime}}\in
W^{{}^{\prime}}}d\left(x^{{}^{\prime}},w^{{}^{\prime}}\right)=\min_{w\in
W}d\left(x,w\right)+\min_{w_{n+1}\in Q}d\left(x_{n+1},w_{n+1}\right)$

Therefore $\min_{w_{n+1}\in Q}d\left(x_{n+1},w_{n+1}\right)=0$, which implies
that $\min_{w^{{}^{\prime}}\in
W^{{}^{\prime}}}d\left(x^{{}^{\prime}},w^{{}^{\prime}}\right)=\min_{w\in
W}d\left(x,w\right)$. Thus,
$\mathcal{NM}\left(q,n+1,W^{{}^{\prime}}\right)\>>\>\mathcal{NM}\left(q,n,W\right)$.
The strict inequality holds due to the division by the lottery’s length in the
near miss index. ∎

Therefore, keeping the number of symbols fixed we would benefit from
increasing the number of reels in a slot machine. This result indicates that
the physical constraint over the number of reels might be binding.

We have shown that if one parameter of the lottery’s frame is held fixed
increasing the other one is preferable in terms of near miss. Furthermore, if
we allow for variation in both parameters, reducing the alphabet size while
increasing the length will result in a preferable lottery frame.

###  3.1 Near Miss Bounds

In this subsection, we move from qualitative to quantitative results and
derive bounds on the ratio between the maximal near miss index and the
lottery’s objective probability of winning for a given lottery frame. This
ratio is of interest because it describes the degree to which the objective
probability of winning might be inflated. In what follows, we use the
connection between our near miss framework and coding theory.

######  Proposition 4.

Let $n$ and $q$ be the length and alphabet size of the lottery respectively.

  1. (i)

Assume that $p\leq\frac{q^{2}+1}{2q^{3}}$. Then there exists a set of outcomes
$W$ such that the following holds:

$\frac{2q^{3}(n-1)+(q^{2}+1)}{n(q^{2}+1)}\>\leq\>\frac{\mathcal{NM}\left(q,n,W\right)}{p}\>\leq\>q^{n-1}$
(6)

  2. (ii)

Assume that $p\geq\frac{q^{2}+1}{2q^{3}}$. Then there exists a set of outcomes
$W$ such that the following holds:

$1\>\leq\>\frac{\mathcal{NM}\left(q,n,W\right)}{p}\>\leq\>\frac{2q^{3}(n-1)+(q^{2}+1)}{n(q^{2}+1)}$
(7)

Proof. The proof proceeds by a series of steps.

Step 1: Concave near miss.
We begin by showing that the maximal near miss index as a function of the
objective probability of winning is concave. To show that we will prove an
equivalent claim, that the minimal sum of distances $\sum_{x\in
X_{q}^{n}}\min_{w\in W}d(x,w)$ is convex in $p$. Assume by contradiction that
this sum is not convex in $p$ and let $p_{m}=\frac{m}{q^{n}}$ be the smallest
probability which violates convexity (see Figure 1).

$p$$\sum_{x\in X_{q}^{n}}\min_{w\in
W}d(x,w)$$d_{1}^{*}$$d_{m}^{*}$$p_{1}$$p_{m}$ Figure 1: Minimal sum of
distances as a function of the objective probability of winning

Denote by $d_{1}^{*}$ and $d_{m}^{*}$ the minimal sum of distances for
$p_{1}=\frac{1}{q^{n}}$ and $p_{m}$ respectively and let $W_{m}$ be the set of
winning outcomes of size $m$ achieving $d_{m}^{*}$. We can order $W_{m}$ in a
greedy manner such that in each step the added winning outcome results in the
greatest reduction in the sum of distances. Therefore, the path of $W_{m}$
from $d_{1}^{*}$ to $d_{m}^{*}$ is convex and thus must pass below the path
illustrated in Figure 1, contradicting the minimality of distances sum. ∎

Step 2: M-Bound.
Denote by $\mathcal{NM}^{*}$ the maximal near miss index for a given objective
probability of winning $p^{*}$ and let $M=\frac{\mathcal{NM}^{*}}{p^{*}}$. By
the concavity of the maximal near miss index function it follows that for
every $p\leq p^{*}$ there exists a set of winning outcomes such that the
following holds:

$M\leq\frac{\mathcal{NM}\left(q,n,W\right)}{p}$

Furthermore, for every $p\geq p^{*}$ the following holds:

$\frac{\mathcal{NM}\left(q,n,W\right)}{p}\leq M$

∎

Step 3: Showing that
For $p=\frac{q^{2}+1}{2q^{3}}$, the $M$-bound is given by:

$M=\frac{2q^{3}(n-1)+q^{2}+1}{n(q^{2}+1)}$ (8)

We will integrate two known results from coding theory to show that (8) holds.

Theorem 1 (Kalbfleisch and Stanton (1969)).
$K_{q}(3,1)=\lfloor\frac{q^{2}+1}{2}\rfloor$.

Theorem 2 (Cohen et al. (1997)).333This Theorem is a well known folklore
result in coding theory. See Cohen et al. (1997) page 63. $K_{q}(n,R)\leq
qK_{q}(n-1,R)$.
Integrating these results we obtain:

$\begin{split}K_{q}(n,1)&\leq q^{n-3}K_{q}(3,1)\\\\[5.0pt]
&\leq\frac{q^{n-3}(q^{2}+1)}{2}\end{split}$

Therefore, if $|W|=\frac{q^{n-3}(q^{2}+1)}{2}$ we can construct a set of
winning outcomes such that each losing outcome is located within a Hamming
distance of one from a winning one. Thus, the $M$-bound is given by:

$\begin{split}M&=\frac{\mathcal{NM}\left(q,n,W\right)}{p}\\\\[5.0pt]
&=\frac{2q^{3}(n-1)+q^{2}+1}{n(q^{2}+1)}\end{split}$

∎

Step 4: The remaining bounds
We will complete the proof by showing that the upper bound in (6) and the
lower bound in (7) holds.

To prove that the upper bound in (6) holds we will look at $|W|=1$ which
implies $p=\frac{1}{q^{n}}$. Given only one winning outcome, the average
Hamming distance of the losing outcomes to the winning one is:

$\frac{\sum_{k=1}^{n}\binom{n}{k}k(q-1)^{k}}{q^{n}}=\frac{n(q-1)q^{n-1}}{q^{n}}=\frac{n(q-1)}{q}$

Therefore, the near miss index for $p=\frac{1}{q^{n}}$ is $\frac{1}{q}$ and
the $M$-bound is given by $M=q^{n-1}$.

Finally, by the definition of the near miss index
$p\leq\mathcal{NM}\left(q,n,W\right)$ holds for every $p$. Note that for $p=1$
this lower bound holds with equality. ∎

Note that the $M$-bound is increasing in both $q$ and $n$. Therefore, by
increasing these parameters we attain an increased magnitude of the near miss
effect relative to the objective probability of winning. To get a quantitative
sense of Proposition 4, consider the following table, which provides values of
the $M$-bound and the threshold objective probability of winning $p$ for
various specifications of $q$ and $n$:

$q$ | $n$ | $p(q)$ | $M$
---|---|---|---
2 | 2 | 0.3125 | 2.10
2 | 10 | 0.3125 | 2.98
5 | 2 | 0.1040 | 5.31
5 | 10 | 0.1040 | 8.75
8 | 2 | 0.0635 | 8.38
8 | 10 | 0.0635 | 14.28
11 | 2 | 0.0458 | 11.41
11 | 10 | 0.0458 | 19.74
14 | 2 | 0.0359 | 14.43
14 | 10 | 0.0359 | 25.17

This table illustrates how $q$ and $n$ affect the near miss index achieved.
For example, if we set $q=2$ and $n=2$, then for any objective probability of
winning $p\leq 0.3125$ we can obtain a near miss effect of $2.1p$ or more.
However, if we choose the objective probability of winning to be $p\geq
0.3125$ we can obtain a near miss effect of at most $2.1p$.

##  4 Selling a Framed Lottery

In this section, we present an interaction between a seller who designs a
lottery and a buyer (DM) who considers buying it.

The DM who faces the lottery has a misspecified belief that the probability of
winning is the lottery’s near miss index. Thus, assuming that the DM’s
willingness to pay is depicted by the near miss index and the seller’s cost is
given by the objective probability of winning, the seller wishes to design a
lottery that maximizes the difference between them. We will refer to this
difference as the seller’s value. Therefore, the seller maximizes the
following:

$\max_{\left(q,n,W\right)}\left[\mathbb{E}_{x\in{Q^{n}}}\left[1-\frac{\min_{w\in{W}}d(x,w)}{n}\right]-p\right]$
(9)

As we have seen, maximizing the near miss index is an open problem. However,
in this setting, we will show that if the seller chooses an objective
probability of winning from a certain range, the optimal lottery frame can be
fully characterized by parameters identical to those of a special family of
codes called Hamming codes. We start by stating the following upper bound on
the seller’s value.

######  Observation 1.

Fix the probability of winning at some $p^{*}$. Then for any given probability
of winning $p\geq p^{*}$ and any lottery frame $\left(q,n,W\right)$ the
following holds:

$\max_{\left(q,n,W\right)}\left[\mathbb{E}_{x\in{Q^{n}}}\left[1-\frac{\min_{w\in{W}}d(x,w)}{n}\right]-p\right]\>\leq\>\frac{n-1}{n}\cdot(1-p^{*})$
(10)

In other words, the seller’s value is bounded above by setting $p=p^{*}$ and
constructing a lottery in which every losing outcome is located within the
minimal Hamming distance possible of exactly one from a certain winning
outcome.

A code $W\subseteq Q^{n}$ with covering radius $1$ is called a Hamming code if
for every code-word $x\in Q^{n}\setminus W$ there is a unique code-word $w\in
W$ that is located within a Hamming distance of one from it. Hamming codes
were introduced by Hamming (1950) and a full characterization of their
parameters is known.444See Cohen et al. (1997) chapters 2 and 11 for a more
detailed description of Hamming codes that includes a general algorithm for
generating such codes. They are defined by the following parameters: $q$ is a
prime power, $n=\frac{q^{m}-1}{q-1}$ where $m\geq 1$ and $R=1$. For these
codes it is known that $K_{q}\left(n,1\right)=q^{n-m}$.

Hamming codes are used in the field of coding theory for data compression and
as error-correcting codes due to their efficiency.555Error correcting codes
are codes used to overcome possible errors in data transmission caused by an
unreliable or noisy communication channel. In our framework this efficiency
will be translated into maximizing the difference between the near miss index
and the objective probability of winning.

Our next result connects Hamming codes with the seller’s maximization problem,
showing that the optimal lottery frame has the same parameters.

######  Claim 1.

Assume that $p\geq\frac{1}{q^{m}}$ where $q$ is a prime power and $m\geq 1$.
Then the optimal lottery frame is defined by the following parameters: $q$,
$n=\frac{q^{m}-1}{q-1}$ and $|W|=q^{n-m}$.

Proof. We start by setting the length of the lottery to be
$n=\frac{q^{m}-1}{q-1}$ and the size of $W$ to $q^{n-m}$. By doing that, we
obtain a lottery with an objective probability of winning
$p=\frac{|W|}{q^{n}}=\frac{1}{q^{m}}$ that has the same parameters as those of
a Hamming code. As noted, for these codes the following holds
$K_{q}\left(n,1\right)=q^{n-m}=|W|$. Thus, there exists a set of outcomes $W$
of size $q^{n-m}$ such that for any $x\in Q^{n}\setminus W$ the following
$\min_{w\in W}d\left(x,w\right)=1$ holds. Therefore, the seller’s value
obtained from this lottery is given by:

$\begin{split}\mathbb{E}_{x\in
Q^{n}}\left[1-\frac{\min_{w\in{W}}d(x,w)}{n}\right]-p&=1-\frac{0}{n}\cdot
p-\frac{1}{n}\cdot(1-p)-p\\\\[5.0pt] &=\frac{n-1}{n}\cdot(1-p)\\\\[5.0pt]
&=\frac{n-1}{n}\cdot\frac{q^{m}-1}{q^{m}}\end{split}$

Thus, we have attained the upper bound on the seller’s value for
$p\geq\frac{1}{q^{m}}$ which concludes the proof. ∎

Therefore, by restricting attention to winning probabilities depicted by
$p\geq\frac{1}{q^{m}}$ where $m\geq 1$ and selecting an alphabet size that is
a prime power, we can obtain a closed solution for the seller’s optimal
lottery frame.

The following result shows that given a probability of $p=\frac{1}{q^{m}}$,
the minimal length needed to obtain the seller’s maximal value is that of a
Hamming code.

######  Claim 2.

Assume that $p=\frac{1}{q^{m}}$ where $q$ is a prime power and $m\geq 1$. Then
the minimal length needed to obtain the seller’s maximal value is
$n=\frac{q^{m}-1}{q-1}$.

Proof. To prove this result we will use a lower bound of covering codes called
the sphere covering lower bound which is only attained by perfect
codes.666Hamming codes are a family of perfect codes.

The Sphere Covering Bound. For any $q$, $n$ and $R$ the following holds:

$K_{q}\left(n,R\right)\geq\frac{q^{n}}{\mathrm{\sum_{i=0}^{R}}{n\choose
i}\left(q-1\right)^{i}}$ (11)

As previously noted, by setting $n=\frac{q^{m}-1}{q-1}$ and $|W|=q^{n-m}$ we
can obtain a perfect Hamming code with a covering radius of one, for which the
sphere covering bound is attained with equality. For
$n-1=\frac{q^{m}-1}{q-1}-1$ the sphere covering bound holds with strict
inequality and thus,

$\begin{split}K_{q}\left(n-1,1\right)&>\frac{q^{n-1}}{1+(n-1)(q-1)}\\\\[5.0pt]
&=\frac{q^{n}}{q\left(1+(n-1)(q-1)\right)}\\\\[5.0pt]
&>\frac{q^{n}}{q\left(1+n\left(q-1\right)\right)}=\frac{1}{q}K_{q}\left(n,1\right)\end{split}$

Therefore, we obtain that $K_{q}\left(n,1\right)<qK_{q}\left(n-1,1\right)$ for
$n=\frac{q^{m}-1}{q-1}$. Thus, for any $1\leq k\leq n-1$ the following holds:

$K_{q}\left(n,1\right)\><\>q^{k}K_{q}\left(n-k,1\right)$

This implies that $n=\frac{q^{m}-1}{q-1}$ is the minimal length required to
obtain the seller’s maximal value. ∎

Thus, not only is the lottery frame defined by the parameters of Hamming codes
optimal, but it is also the minimal length required to maximize the seller’s
value.

Assuming that we have no restrictions on the alphabet size, the lottery’s
length and we allow the objective probability of winning to be arbitrarily
small, the following corollary is immediate from the previous results.

######  Corollary 1.

To maximize his value, the seller will choose $p=\frac{1}{q^{m}}$ where $q$ is
a prime power, $m\to\infty$, $n=\frac{q^{m}-1}{q-1}$ and $|W|=q^{n-m}$.

Therefore, if the seller is not restricted in any sense he will opt for
lotteries with a very small objective probability of winning that generate a
relatively high near miss effect and with it a high perceived probability of
winning.

As we have seen, a general construction of an optimal lottery frame that
maximizes the near miss index, and with it, the perceived probability of
winning is an open problem. Nonetheless, our analysis and results show that
clear comparisons between different lottery frames can be drawn, rendering
specific frames preferable over others in terms of near miss.

Moreover, the analysis of the seller’s optimal lottery design resulted in a
full characterization of the optimal lottery frame. We showed that the optimal
lottery parameters belong to a special class of codes known as Hamming codes.
The connection established in this paper between our near miss framework and
the field of coding theory might open up new avenues of future research.

An important observation is that choosing the lottery’s frame while taking
into consideration the near miss effect did not only influence the alphabet
size and the lottery’s length but also had implications for the objective
probability of winning. The results provided in this section, mainly Corollary
1, might provide us with additional intuition and a potential explanation as
to why some of the most common lottery designs are those with a very small
objective probability of winning.

## References

  * (1)
  * Ahn and Ergin (2010) Ahn, D. S. and H. Ergin, “Framing Contingencies,” Econometrica, 2010, 78, 655–695.
  * Amsel (1958) Amsel, A., “The role of frustrative nonreward in noncontinuous reward situations,” Psychological Bulletin, 1958, 55, 102–119.
  * Binmore and Hiller (2020) Binmore, K. and T. Hiller, “Why Are Near Misses Thrilling?,” mimeo, 2020.
  * Blokhuis and Lam (1984) Blokhuis, A. and C. W. H. Lam, “More coverings by rook domains,” Journal of Combinatorial Theory, 1984, 36, 240–244.
  * Carnielli (1985) Carnielli, W. A., “On covering and coloring problems for rook domains,” Discrete Math, 1985, 57, 9–16.
  * Chockler and Halpern (2004) Chockler, H. and J. Y. Halpern, “Responsibility and blame: A structural-model approach,” Journal of Articial Intelligence Research, 2004, 22, 93–115.
  * Clark et al. (2009) Clark, L., A. J. Lawrence, F. Astley-Jones, and N. Gray, “Gambling near-misses enhance motivation to gamble and recruit win-related brain circuitry,” Neuron, 2009, 61, 481–490.
  * Cohen et al. (1997) Cohen, G., I. Honkala, S. Litsyn, and A. Lobstein, Covering Codes, North-Holland, 1997.
  * Dillon et al. (2012) Dillon, R. L., C. H. Tinsley, and M. A. Cronin, “How near-miss events amplify or attenuate risky decision making,” Management Science, 2012, 68, 1596–1613.
  * Foxall and Sigurdsson (2012) Foxall, G. R. and V. Sigurdsson, “When loss rewards: the near-miss effect in slot machine gambling,” Analysis of Gambling Behaviour, 2012, 6.
  * Gerstenberg and Lagnado (2014) Gerstenberg, T. and D. A. Lagnado, “Attributing responsibility: Actual and counterfactual worlds. In J. Knobe, T. Lombrozo and S. Nichols (Eds.),” Oxford Studies of Experimental Philosophy, 2014.
  * Ginsberg and Smith (1987) Ginsberg, M. and D. E. Smith, “Reasoning About Action I: A Possible Worlds Approach,” Artificial Intelligence, 1987, 35, 165–195.
  * Golomb and Posner (1964) Golomb, S. and E. Posner, “Rook domains, Latin squares, affine planes, and error-distributing codes,” IEEE Transactions on Information Theory, 1964, 10, 196–208.
  * Halpern (2016) Halpern, J, Actual Causality, Cambridge, Massachusetts; London, England: The MIT Press, 2016.
  * Hamming (1950) Hamming, R. W., “Error detecting and error correcting codes,” IEEE Transactions on Information Theory, 1950, 29, 147–160.
  * Kahneman and Tversky (1982) Kahneman, D. and A. Tversky, The simulation heuristic In D. Kahneman, P. Slovic, and A. Tversky (Eds.), Judgment under Uncertainty: Heuristics and Biases (201-208), Cambridge University Press, 1982.
  * Kahneman and Varey (1990) and C. A. Varey, “Propensities and counterfactuals: The loser that almost won,” Journal of Personality and Social Psychology, 1990, 59, 1101–1110.
  * Kahneman and Miller (1986) and D. T. Miller, “Norm theory: Comparing reality to its alternatives,” Psychological Review, 1986, 93, 136–153.
  * Kalbfleisch and Stanton (1969) Kalbfleisch, J. G. and R. G. Stanton, “A Combinatorial Problem in Matching,” Journal of the London Mathematical Society, 1969, 1, 60–64.
  * Keri and Ostergard (2005) Keri, G. and P. R. J. Ostergard, “Bounds for Covering Codes over Large Alphabets,” Designs, Codes and Cryptography, 2005, 37, 45–60.
  * Lagnado et al. (2013) Lagnado, D. A., T. Gerstenberg, and R. Zultan, “Causal responsibility and counterfactuals,” Cognitive Science, 2013, 37, 1036–1073.
  * Lewis (1973) Lewis, D, Counterfactuals, Oxford: Blackwell Publishers, 1973.
  * Ostergard and Kaikkonen (1998) Ostergard, P. R. and M. K. Kaikkonen, “New upper bounds for binary covering codes,” Discrete Mathematics, 1998, 178, 165–179.
  * Pearl (2009) Pearl, J, Causality: Models, Reasoning and Inference, Cambridge University Press, Cambridge, 2009.
  * Pisklak et al. (2020) Pisklak, J. M., J. J. H. Yong, and M. L. Spetch, “The Near-Miss Effect in Slot Machines: A Review and Experimental Analysis Over Half a Century Later,” Journal of Gambling Studies, 2020, 36, 611–632.
  * Rabin and Schrag (1999) Rabin, M. and J. L. Schrag, “First Impressions Matter: A Model of Confirmatory Bias,” The Quarterly Journal of Economics, 1999, 114, 37–82.
  * Reid (1986) Reid, R. L., “The psychology of the near miss,” Journal of Gambling Behavior, 1986, 2, 32–39.
  * Rodemich (1970) Rodemich, E. R., “Coverings by Rook Domains,” Journal Of Combinatorial Theory, 1970, 9, 117–128.
  * Schonheim (1968) Schonheim, J., “On linear and nonlinear single error correcting q-ary perfect codes,” Information and Control, 1968, 12, 23–26.
  * Skinner (1953) Skinner, B.F, Science and Human Behavior, New York: Macmillan, 1953\.
  * Stange et al. (2017) Stange, M. G., S. Mikyla, C. Osazuwa, Graydon, and M. J. Dixon, “Reinforcing Small Wins and Frustrating Near-Misses: Further Investigation Into Scratch Card Gambling,” Journal of Gambling Studies, 2017, 33, 47–63.
  * Sundali et al. (2012) Sundali, J. A., A. H. Safford, and R. Croson, “The impact of near-miss events on betting behavior: An examination of casino rapid roulette play,” Judgment and Decision Making, 2012, 7, 768–778.