In
game theory, the Helly metric is used to assess the distance between two
strategies
Strategy (from Greek στρατηγία ''stratēgia'', "art of troop leader; office of general, command, generalship") is a general plan to achieve one or more long-term or overall goals under conditions of uncertainty. In the sense of the " ar ...
. It is named for
Eduard Helly
Eduard Helly (June 1, 1884 in Vienna – 28 November 1943 in Chicago) was a mathematician after whom Helly's theorem, Helly families, Helly's selection theorem, Helly metric, and the Helly–Bray theorem were named.
Life
Helly earned his doct ...
.
Consider a game
, between player I and II. Here,
and
are the sets of
pure strategies for players I and II respectively; and
is the payoff function.
(in other words, if player I plays
and player II plays
, then player I pays
to player II).
The Helly metric
is defined as
:
The metric so defined is symmetric, reflexive, and satisfies the
triangle inequality
In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side.
This statement permits the inclusion of degenerate triangles, but ...
.
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
does not imply
but it does imply that the ''consequences'' of
and
are identical; and indeed this induces an
equivalence relation.
If one stipulates that
implies
then the topology so induced is called the
natural topology
In any domain of mathematics, a space has a natural topology if there is a topology on the space which is "best adapted" to its study within the domain in question. In many cases this imprecise definition means little more than the assertion that ...
.
The metric on the space of player II's strategies is analogous:
:
Note that
thus defines ''two'' Helly metrics: one for each player's strategy space.
Conditional compactness
Recall the definition of
-net: A set
is an
-net in the space
with metric
if for any
there exists
with
.
A metric space
is
conditionally compact (or precompact), if for any
there exists a ''finite''
-net in
. Any game that is conditionally compact in the Helly metric has an
-optimal strategy for any
. Moreover, if the space of strategies for one player is conditionally compact, then the space of strategies for the other player is conditionally compact (in their Helly metric).
References
N. N. Vorob'ev 1977. ''Game theory lectures for economists and systems scientists''. Springer-Verlag (translated by S. Kotz).
Game theory
{{gametheory-stub