27.10.2005

Ciągi dokładne, liczby Fibonacci'ego i równowagi w grach sąsiedztwa

Ciąg a-dokładny jest to skończony ciąg liczbowy (x(1),...,x(k)), taki, że wielkość x(i) + a*x(i-1) + a*x(i+1) jest stała ze względu na i (na brzegach uzupełnia się x(0)=x(k+1)=0). Przykładowo, ciągi (3,2,2,3) oraz (5,3,4,3,5) są 1/3-dokładne. Ciągi 1/3-dokładne konstruuje się przekształcając odpowiednio ciąg Fibonacci'ego (1,1,2,3,5,...). Dla innych a ciągi a-dokładne konstruuje się przekształcając odpowiednio inne nieskończone ciągi liczbowe zdefiniowane w sposób rekursywny, podobnie, jak ciąg Fibonacci'ego, ale trochę inaczej.
Alternatywną konstrukcję ciągów dokładnych dostaje się tworząc odpowiednie trójkąty liczbowe, kształtu takiego, jak trójkąt Pascala, ale tworzone według innych reguł. Ciągi dokładne służą do wyznaczania równowag w grach sąsiedztwa z nieskończoną populacją jednorodnych graczy. Przykład: wyobraźmy sobie nieskończoną populację, która może się osiedlić na wyspach 1, 2, 3 i 4. Każdy gracz podejmuje decyzję o wyborze wyspy niezależnie i w rezultacie powstaje rozkład p(1), p(2), p(3), p(4) (liczby nieujemne, sumujące się do jedynki). Osobniki są towarzyskie i ich wypłaty (po wyborze wyspy i) wynoszą p(i) + 1/3*p(i-1) + 1/3*p(i+1) (również tu przyjmujemy p(0)=p(5)=0, a więc wyspy 2 i 3 mają po dwie wyspy sąsiednie, a wyspy 1 i 4 - po jednej). Równowaga to taki rozkład, przy którym nikt nie może zwiększyć swojej wypłaty przez zmianę swojej decyzji. Z drugiego zdania nin. streszczenia wnioskujemy, że równowagą tej gry jest (3/10, 2/10, 2/10. 3/10). Oczywiście nie jest to jedyna równowaga, bo n.p. rozkłady (1, 0, 0, 0) oraz (0, 1/2, 1/2, 0) też są równowagami. Ogólnie grę sąiedztwa wyznacza dowolny graf niezorientowany (graf sąsiedztwa) oraz parametr a.
Wiedza o ciągach dokładnych pozwala wyznaczyć wszystkie równowagi w tych grach, w których graf sąsiedztwa jest łańcuchem lub cyklem, a parametr a należy do przedziału [0, 1/2]. Gry z bardziej ogólnymi grafami sąsiedztwa to już zupełnie inna sprawa.