Helly metric

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

Consider a game $\Gamma=\left\langle\mathfrak{X},\mathfrak{Y},H\right\rangle$, between player I and II. Here, $\mathfrak{X}$ and $\mathfrak{Y}$ are the sets of pure strategies for players I and II respectively; and $H=H(\cdot,\cdot)$ is the payoff function.

(in other words, if player I plays $x\in\mathfrak{X}$ and player II plays $y\in\mathfrak{Y}$, then player I pays H(x,y) to player II).

The Helly metric ρ(x₁,x₂) is defined as

$\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.

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 stragegies. Two strategies are distant if their payoffs are different. Note that ρ(x₁,x₂) = 0 does not imply x₁ = x₂ but it does imply that the consequences of x₁ and x₂ are identical; and indeed this induces an equivalence relation.

If one stipulates that ρ(x₁,x₂) = 0 implies x₁ = x₂ then the topology so induced is called the natural topology.

The metric on the space of player II's strategies is analogous:

$\rho(y_1,y_2)=\sup_{x\in\mathfrak{X}}\left| H(x,y_1)-H(x,y_2)\right|.$

Note that Γ thus defines two Helly metrics: one for each player.

Conditional compactness

Notation (definition of an $\epsilon$-net). A set $X_\epsilon$ is an $\epsilon$-net in the space X with metric ρ if for any $x\in X$ there exists $x_\epsilon\in X_\epsilon$ with $\rho(x,x_\epsilon)<\epsilon$.

A metric space P is conditionally compact if for any ε > 0 there exists a finite $\epsilon$-net in P.

A game that is conditionally compact in the Helly metric has an $\epsilon$-optimal strategy for any ε > 0.

Other results

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).

This game theory article is a stub. You can help Wikipedia by expanding it.v · Categories: Game theory Economics and finance stubs Wikimedia Foundation. 2010. Игры ⚽ Нужно решить контрольную? Robert Halliday La France (airship) Look at other dictionaries: Metric space — In mathematics, a metric space is a set where a notion of distance (called a metric) between elements of the set is defined. The metric space which most closely corresponds to our intuitive understanding of space is the 3 dimensional Euclidean… …   Wikipedia Helly family — In combinatorics, a Helly family of order k is a family of sets such that any minimal subfamily with an empty intersection has k or fewer sets in it. In other words, any subfamily such that every (k+1) fold intersection is non empty has non empty …   Wikipedia Eduard Helly — (1884, Vienna – 1943, Chicago) was a mathematician and the eponym of Helly s theorem, Helly families, Helly s selection theorem, Helly metric, and the Helly Bray theorem.External links* …   Wikipedia Injective metric space — In metric geometry, an injective metric space, or equivalently a hyperconvex metric space, is a metric space with certain properties generalizing those of the real line and of L∞ distances in higher dimensional vector spaces. These properties can …   Wikipedia 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… …   Wikipedia Median graph — The median of three vertices in a median graph In mathematics, and more specifically graph theory, a median graph is an undirected graph in which any three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest… …   Wikipedia List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… …   Wikipedia Arzelà–Ascoli theorem — In mathematics, the Arzelà–Ascoli theorem of functional analysis gives necessary and sufficient conditions to decide whether every subsequence of a given sequence of real valued continuous functions defined on a closed and bounded interval has a… …   Wikipedia Grafo mediano — El mediano de tres vértices en un grafo mediano. En matemática, y más específicamente en la teoría de grafos, un grafo mediano es un grafo no dirigido en que cualesquiera tres vértices a, b, y c tienen un único mediano. Un mediano es un vértice… …   Wikipedia Español Counterexamples in Topology —   Author(s) Lynn Arthur Steen J. Ar …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”