Helly metric

In game theory, the Helly metric is used to assess the distance between two strategies. It is named for Eduard Helly.

Definition

Consider a game

Γ

=

⟨

X

,

Y

,

H

⟩

{\displaystyle \Gamma =\left\langle {\mathfrak {X}},{\mathfrak {Y}},H\right\rangle }

, between player I and II. Here,

X

{\displaystyle {\mathfrak {X}}}

and

Y

{\displaystyle {\mathfrak {Y}}}

are the sets of pure strategies for players I and II respectively. The payoff function is denoted by

H

=

H

(

⋅

,

⋅

)

{\displaystyle H=H(\cdot ,\cdot )}

. In other words, if player I plays

x

∈

X

{\displaystyle x\in {\mathfrak {X}}}

and player II plays

y

∈

Y

{\displaystyle y\in {\mathfrak {Y}}}

, then player I pays

H

(

x

,

y

)

{\displaystyle H(x,y)}

to player II.

The Helly metric

ρ

(

x

1

,

x

2

)

{\displaystyle \rho (x_{1},x_{2})}

is defined as

ρ

(

x

1

,

x

2

)

=

sup

y

∈

Y

|

H

(

x

1

,

y

)

−

H

(

x

2

,

y

)

|

.

{\displaystyle \rho (x_{1},x_{2})=\sup _{y\in {\mathfrak {Y}}}\left|H(x_{1},y)-H(x_{2},y)\right|.}

The metric so defined is symmetric, reflexive, and satisfies the triangle inequality.

Properties

The Helly metric measures distances between strategies, not in terms of the differences between the strategies themselves, but in terms of the consequences of the strategies. Two strategies are distant if their payoffs are different. Note that

ρ

(

x

1

,

x

2

)

=

0

{\displaystyle \rho (x_{1},x_{2})=0}

does not imply

x

1

=

x

2

{\displaystyle x_{1}=x_{2}}

but it does imply that the consequences of

x

1

{\displaystyle x_{1}}

and

x

2

{\displaystyle x_{2}}

are identical; and indeed this induces an equivalence relation.

If one stipulates that

ρ

(

x

1

,

x

2

)

=

0

{\displaystyle \rho (x_{1},x_{2})=0}

implies

x

1

=

x

2

{\displaystyle x_{1}=x_{2}}

, then the topology so induced is called the natural topology.