*******************************************************

PROCEEDINGS OF KOSEN WORKSHOP MTE2006

– MATHEMATICS, TECHNOLOGY AND EDUCATION –

IBARAKI NATIONAL COLLEGE OF TECHNOLOGY HITACHNAKA, IBARAKI, JAPAN DECEMBER 5-7, 2006

GOLDEN RATIO APPEARS IN DISCRETE-TIME DYNAMIC OPTIMIZATION PROCESSES

AKIFUMI KIRA Kyushu University, Fukuoka 812-8581, Japan

                        E-mail: ec207004@s.kyushu-u.ac.jp

MASAMI YASUDA Chiba University, Chiba 263-8522, Japan

                       E-mail: yasuda@math.s.chiba-u.ac.jp

SEIICHI IWAMOTO Kyushu University, Fukuoka 812-8581, Japan

                        E-mail: iwamoto@en.kyushu-u.ac.jp

Abstract.Since antiquity, the Golden Ratio (ϕ) has been keeping to show up in many aspects of geometry, architecture, music, art and even philosophy, and it appears also in newer domains. Here a few source of information about this will be listed as follows: A gambling in the coin tossing gives a amount of bet and observes a martingale property when it is adapted a probability of win called as the Golden probability(2-ϕ). We will also show a typical Discrete-time Dynamic Optimization Processes for Allocation problem, Linear-Quadratic control problem and Multi-variate stopping problem, of which the ratio has an interest rule.

1. Introductholds from (2.5). Soion. The Golden Ratio (ϕ = 1.61803 ⋯) has been a profound influence since ancient times such as the Parthenon at Athens. The beauty appears even in the ingredient of nature creatures. The most influential mathematics textbook by Euclid of Alexandria defines the proportion. These information presents a broad sampling of ϕ−related topics in an engaging and easy-to-understand format.

The Fibonacci sequence (1, 1, 2, 3, 5, 8, 13, ⋯) is closely related to the Golden Ratio, which is a limiting ratio of its two adjacent numbers. It is also known that the diagonal summation produces the Fibonacci sequence in the Pascal’s triangle. These repeated procedure or iteration have something in common.

2000 Mathematics Subject Classification: Primary 90C39; Secondary 11A99.

Key words and phrases: Golden Ratio appears to discret time optimization problem. The paper is in preliminary form and the final version of it will be published elsewhere.

The principle of Dynamic Programming is said to ‘divide and conquer.’ In fact, if it is not possible to work out directly, divide up a problem into smaller ones. The basic idea is aiming to provide the original problem an effective family of sub-problems. The Bellman’s curse of dimensionality conquers the computational explosion with the problem dimension through the use of parametric representations. The more it’s in a complex, the more it is divided. When a problem is in a multi-stage decision form, we should consider the problem repeatedly. If this reduction procedure gives a self-similar one, the methodology turns out to be effective. The Golden Ratio is created repeatedly by its own in a quite same form. A recurrence relation is ubiquitous. Let us say that a beautiful continued fraction represents the Golden number. It is interesting that this quite introductory problem of Dynamic programming produces the basic mathematical aspects.

In this way the Golden ratio is no isolated phenomenon, but, in many cases, the first and indeed, a simple example in the context of a sequence of generalizations of a common idea. Therefore the Golden ratio has a pedagogical significance as well.

A theme of this note is presented originally at the conference MTE2006 Dec. 2006 and also Research Meeting RIMS at Feb. 2007 as ”Golden ratio in optimal value function” by Seiichi Iwamoto and Masami Yasuda. Then adding the next section, this note is prepared.

2. Gambling holds from (2.5). So A coin tossing is the game of win or loss in the typical gambling for the probability theory. The gambling theory has been developed in the related various fields. Martingale is referred to as a popular class of betting strategies in 18th century France. The simplest of these strategies was designed for a game in which the gambler wins his stake if a coin comes up heads and loses it if the coin comes up tails. The strategy had the gambler double his bet after every loss, so that the first win would recover all previous losses. plus yield a profit equal to the original stake. Since as a gambler’s wealth and available time jointly approach infinity. his probability of eventual flipping heads approaches 1. Thus the martingale betting strategy was seen as a sure thing by those who practiced it. Of course in reality the exponential growth of the bets would eventually bankrupt those foolish enough to use the martingale for a long time. The concept of martingale in probability theory was introduced by Paul Pierre Levy(1986-1971), and much of the original development of the theory was done by Joseph Leo Doob(1910-2004). Part of the motivation for that work was to show the impossibility of successful betting strategies.

The following gambling with a toin tossing is considered. Assume that there are no ties and the result of any game is determined randomly. Let p be the probability of winning and q = 1 − p losing. If y is the amount of the commencing bet and let x^{n−1} be the finite number of bets you can afford in the n-th play of time. Then y − x^{n−1} is the amount when one losses, however, one can get x-time more if one wins in the betting, x^{n} when one wins. That is, at n-th time play(n = 1, 2, ⋯)

(2.1)  \begin{aligned}y + x^{n} & : p \\ y − x^{n−1} & : q = 1 − p \end{aligned}

When you counitue to lose all your bets, the amount of money you lose is 1 + x + x^{2} + ⋯ + x^{n−1}. Let W_{n} denote the amount of money in total until n-th time play. So the dynamics of the amount is expressed as follows:

(2.2)  W_{n+1} = W_{n} + A_{n+1}, n = 0, 1, …

where the gain of n-th time is A_{n}:

(2.3)  A_{n} = x^{n}ϵ_{n}−x^{n−1}(1 − ϵ_{n})

and

(2.4)  ϵ_{n} = \{ \begin{matrix}+1 & with probability p, \\ 0 & with probability q = 1 − p. \end{matrix}

Alternatively, if we change the gain to B_{n} from A_{n}:

(2.5)  B_{n} = (x^{n−1} + x^{n−2})ϵ_{n}−x^{n−1}(1 − ϵ_{n})

Because, if the gambler fails to win at (n − 1) and wants to continue the next play n, the regret is the loss x^{n−2} at (n − 1). And x^{n−1} is a bet for the next play n. To recover the loss, one can get not x-time but x^{n−2} more if one wins in the betting. And then

(2.6)  V_{n+1} = V_{n} + B_{n+1}, n = 0, 1, …

provided that V_{0} = 0.

Definition 2.1. ( [9, 12] ) A process (X_{n}, B_{n}) is called a martingale if (i) it is adapted, that is, for each n, X_{n} is B_{n})-measurable, (ii) E(|X_{n}|) < ∞ , ∀n, and (iii) E(|X_{n+1} | B_{n}) = X_{n}, a.s. (n ≥ 1).

Let B_{n} = σ(e_{k}; k ≤ n) denote the information (natural filtration), then we have the following theorem.

Theorem 2.1. In order to ensure each process a martingale, the relation between the probability and the reward is given as

(i) (W_{n}, B_{n}; n ≥ 1) constitutes a martingale if and only if p = 1/(1 + x), x > 0, (ii) (V_{n}, B_{n}; n ≥ 1) constitutes a martingale if and only if p = 1/(2 + 1/x), x > 0. Proof. The adaptation is clear and it holds that E|ϵ_{n}| < ∞ for each n. The condition makes zero-mean random variables, and so the sum is a martingale.

Definition 2.2. ( [9, 12] ) The class (X_{n}, n ≥ 1) of random variables is said to satisfy the uniform integrability condition if given ϵ > 0, there exists K > 0 such that E(|X_{n}|; |X_{n}| > K) < ϵ, ∀n.

Theorem 2.2. The boundedness of each process is given as follows:

(i) (W_{n}, B_{n}; n ≥ 1) satisfies the uniform integrability condition if x^{2} − x − 1 = 0. Thus the Golden ratio x = ϕ appears. (ii) (V_{n}, B_{n}; n ≥ 1) satisfies the uniform integrability condition if x^{2} − x − 1 = 0. Thus the Golden ratio x = ϕ appears.

Proof. (i) From (2.4), it holds that

P (ϵ_{1} = ϵ_{2} = ⋯ = ϵ_{n−1} = 0, ϵ_{n} = 1)

= P (W_{n+1} = −1 − x − x^{2} − ⋯ − x^{n−1} + x^{n+1})
= P (W_{n+1} = \frac{(x^{2} − x − 1)x^{n} + 1}{x − 1}) = pq^{n}

Substituting x = ϕ implies that sup_{n} P (|W_{n}| > a) → 0 as a ↑ ∞. Hence the condition is satisfied.

(ii) Similarly

P (ϵ_{1} = ϵ_{2} = ⋯ = ϵ_{n−1} = 0, ϵ_{n} = 1)
= P (V_{n+1} = −1 − x − x^{2} − ⋯ − x^{n−1} + x^{n−1} + x^{n})
= P (V_{n+1} = \frac{(x^{2} − x − 1)x^{n−1} + 1}{x − 1}) = pq^{n}

holds from (2.5). So (V_{n}, B_{n}; n ≥ 1) satisfies the uniform integrability condition if x^{2} − x − 1 = 0.

Corollary 2.1. Let x = ϕ. That is, by letting an amount x of bet equal the Golden ratio ϕ, two problems (2.2) and (2.6) are equal: A_{n} = B_{n} and V_{n} = W_{n} for all n. And then, both processes (W_{n}, A_{n}; n ≥ 1) and (V_{n}, B_{n}; n ≥ 1) constitute a martingale if and only if p = 2 − ϕ which is the Golden probability. Proof. It suffices to note that the Golden ratio ϕ satisfies ϕ^{n+2} = ϕ^{n+1} + ϕ^{n}, 1/(1 + ϕ) = 2 − ϕ and 1/ϕ = ϕ − 1.

3. Discrete-time Dynamic Optimization In the following sections, we treat typical dynamic programming problems; Allocation problem and Linear-Quadratic Control problem. However problems are in a simple fashion, it figures out the essence of Dynamic Programming.

Let us consider a typical type of criterion in a deterministic optimization. We minimize the next quadratic criteria :

(3.1)  I(x) = ∑_{n=0}^{∞} [x_{n}^{2} + (x_{n} − x_{n+1})^{2}] ,

and

(3.2)  J(x) = ∑_{n=0}^{∞} [(x_{n} − x_{n+1})^{2} + x_{n+1}^{2}] .

Let R^{∞} be the set of all sequences of real values :

R^{∞} = {x = (x_{0}, x_{1}, …, x_{n}, …) | x_{n} ∈ R^{1} n = 0, 1, … }.

First we take the quadratic criterion (3.1).

Now we consider a mathematical programming problem for any given initial value c :

\underline{MP_{1}(c) :} minimize I(x) subject to (i) x ∈ R^{∞}, (ii) x_{0} = c.

Let us evaluate a few special trajectories :

Example 1. First all but on and after nothing y = {c, 0, 0, …, 0, …} yields I(y) = 2c^{2}.

Example 2. Always all constant z = {c, c, …, c, …} yields I(z) = ∞.

Example 3. A proportional (geometrical) w = {c, ρc, …, ρ^{n}c, …} yields

(3.3)  \begin{matrix}I(w) = & \{c^{2} + (1 − ρ)^{2}c^{2}\} (1 + ρ^{2} + ⋯ + ρ^{2n} + ⋯) \\ = & \frac{1 + (1 − ρ)^{2}}{1 − ρ^{2}} c^{2}  (0 < ρ < 1). \end{matrix}

Since min_{0≤ρ<1} \frac{1 + (1 − ρ)^{2}}{1 − ρ^{2}} is attained at ρ̂ = 2 − ϕ, we have the minimum value

\frac{1 + \{1 − (2 − ϕ)\}^{2}}{1 − (2 − ϕ)^{2}} = ϕ.

Example 4. The propotional û = {c, (2 − ϕ)c, …, (2 − ϕ)^{n}c, …}, with ratio (2 − ϕ), yields

(3.4)  I(û) = ϕc^{2}.

Thus û = (û_{n}) gives a Golden optimal trajectory, because û_{n+1} is always a Golden section point of interval [0, û_{n}].

Next let us now consider a control process with an additive transition T (x, u) = x+u.

minimize ∑_{n=0}^{∞} (x_{n}^{2} + u_{n}^{2})
subject to (i) x_{n+1} = x_{n} + u_{n}, n ≥ 0
(ii) −∞ < u_{n} < ∞
(iii) x_{0} = c.

Then the value function v satisfies Bellman equation :

(3.5)  v(x) = min_{−∞<u<∞} [x^{2} + u^{2} + v(x + u)] .

Eq. (3.5) has a quadratic form v(x) = ϕx^{2}.

Second we take the following quadratic criterion

J(x) = ∑_{n=0}^{∞} [(x_{n} − x_{n+1})^{2} + x_{n+1}^{2}] .

We consider a problem of form:

\underline{MP_{2}(c) :} minimize J(x) subject to (i) x ∈ R^{∞}, (ii) x_{0} = c.

Since J(x) = I(x) − c^{2}, the minimum value is J(û) = (ϕ − 1)c^{2} at the Golden trajectory

û = {c, μc, …, μ^{n}c, …}; μ = 2 − ϕ.

In fact, a proportional w = {c, ρc, …, ρ^{n}c, …} yields

\begin{aligned}J(w) & = \{ρ^{2}c^{2} + (1 − ρ)^{2}c^{2}\} (1 + ρ^{2} + ⋯ + ρ^{2n} + ⋯) \\ & = \frac{ρ^{2} + (1 − ρ)^{2}}{1 − ρ^{2}} c^{2} (0 < ρ < 1). \end{aligned}

Figure 1 in the Appendix shows that min_{0≤x<1} \frac{x^{2} + (1 − x)^{2}}{1 − x^{2}} is attained at x̂ = 2 − ϕ with the minimum value

\frac{(2 − ϕ)^{2} + \{1 − (2 − ϕ)\}^{2}}{1 − (2 − ϕ)^{2}} = ϕ − 1.

4. An Illustrative Graph. Let us now describe a graph which has dual Golden

extremum points in the previous section. The graph is x = f(u) = \frac{u^{2} + (1 − u)^{2}}{1 − u^{2}} . See Figure 1 in Appendix. For this function, it is seen that two equalities:

(4.1)  min_{0<u<1} f(u) = min_{0<u<1} \frac{u^{2} + (1 − u)^{2}}{1 − u^{2}} = −1 + ϕ

and max_{1<u<∞} f(u) = max_{1<u<∞} \frac{u^{2} + (1 − u)^{2}}{1 − u^{2}} = −ϕ hold. Equivalently, the latter equality is that

(4.2)  min_{1<u<∞}\{−f(u)\} = min_{1<u<∞} \frac{u^{2} + (1 − u)^{2}}{u^{2} − 1} = ϕ

The minimum in (4.1) attains iff û = 2−ϕ, and the minimum in (4.2) attains iff u^{∗} = 1+ϕ. Thus we have the inequality

f(u) ≥ −1 + ϕ on (−1, 1) and f(u) ≤ −ϕ on (−∞, −1) ∪ (1, ∞).

Refer to the shape for this graph in the Figure 1 of Appendix.

5. Dynamic Programming of the discrete-time system. The conceptual cluster of Dynamic Programming are investigated throughout the mathematics. Not only the analytical aspect of optimization method, but also the investigate problem with a repeated structure. To give a useful explanation and an interesting implication, we show some explicitly solvable problems.

First the general setting of Dynamic Programming problem are illustrated. It is composed as (S, A, r, T). Let S be a state space in the Euclidean space R and A = (A_{x}), A_{x} ⊂ R, x ∈ S means a feasible action space depending on a current state x ∈ S. The immediate reward is a function of r = r(x, a, t), x ∈ S, a ∈ A_{x}, t = 0, 1, 2, · · ·. And the terminal reward K = K(x), x ∈ S is given. The transition law from the current x to the new y = m(x, a, t) by the action or decision a ∈ A_{x} at a time t. If the transition law m(x, a, t) does not depend t, it is called a stationary m(x, a, t) and we treat it in this paper. Here we consider additive costs and the optimal value of a_{t} will be depend on the decision history. Assume its value at time t denoted by x_{t}, which enjoy the following properties:

(a) The value of x_{t} is observable at time t.

(b) The sequence {x_{t}} follows a recurrence in time:

(5.1)  x_{t+1} = m(x_{t}, a_{t}, t).

It is termed that the function y = m(x, π(x, t), t) means a move from the current x to the next y at t so the law of motion or the plant equation by adapting a policy a = π(x, t).

(c) The set of a_{t} may adopt depends on x_{t} and t.

(d) The cost function C_{π}(x, t) starting a state x at time-to-go T_{t} = T − t to optimize over all policies π has the additive form;

(5.2)  C_{π}(x_{0}, t_{0}) = ∑_{t=t_{0}}^{T −1} r(x_{t}, a_{t}, t) + K(x_{T})

with x_{0} = x_{t_{0}} and

x_{t+1} = m(x_{t}, π(x_{t}, t), t), a_{t} = π(x_{t}, t)

where T is a given finite planning horizon.

Let

F (x, t) = inf_{π} C_{π}(x, t).

It is well known that the sequence {F (·, t)} satisfies the optimality equation(DP equation):

(5.3)  F (x, t + 1) = inf_{a∈A_{x}}[r(x, a, t) + F (m(x, a, T_{t}), t)]

with the boundary F (x, T) = K(x) where T_{t} = T − t for x ∈ S, 0 ≤ t < T.

All of these are referred from text books by Bertsekas [1], Whittle [?], Sniedovich [?], etc.

The relation between The Golden ratio formula and Fibonacci sequence is known as [3] etc. To produce the Fibonacci sequence, it is a good example in a recursive programming [10]. Also the Fibonacci sequence are related with continued fraction. For the notation of continued fraction, we adopt ourself to the following notations:

b_{0} + \frac{c_{1}}{b_{1} + \frac{c_{2}}{b_{2} + \frac{c_{3}}{b_{3} + \frac{c_{4}}{b_{4} + ⋯}}}} = b_{0} + \frac{c_{1}}{b_{1}+} \frac{c_{2}}{b_{2}+} \frac{c_{3}}{b_{3}+} \frac{c_{4}}{b_{4}+} · · · .

Note that the Golden number satisfies ϕ^{2} = 1 + ϕ. By using this relation repeatedly,

ϕ = 1 + \frac{1}{ϕ} = 1 + \frac{1}{1 + \frac{1}{ϕ}} = 1 + \frac{1}{1+} \frac{1}{ϕ} = 1 + \frac{1}{1+} \frac{1}{1+} \frac{1}{ϕ} = 1 + \frac{1}{1+} \frac{1}{1+} \frac{1}{1+} · · ·. Similarly the

reciprocal (or sometimes called as a dual Golden number) is denoted ϕ^{−1} = 0.618 ⋯ =

ϕ − 1 = \frac{1}{ϕ} = \frac{1}{1+} \frac{1}{ϕ} = \frac{1}{1+} \frac{1}{1+} \frac{1}{ϕ} = \frac{1}{1+} \frac{1}{1+} \frac{1}{1+} · · ·.

This reproductive property suggests our fundamental claim for the following typical example of Dynamic Programming. Before we solve the problem, let us induce a sequence {ϕ_{n}} as

(5.4)  ϕ_{n+1} = 1 + \frac{1}{1 + 1/ϕ_{n}} = 1 + \frac{1}{1+} \frac{1}{ϕ_{n}} (n ≥ 1), ϕ_{1} = 1.

Also let {ϕ̂_{n}} as

(5.5)  \begin{matrix}ϕ̂_{n+1} = \frac{1}{1+} \frac{1}{1+}ϕ̂_{n} (n ≥ 1), ϕ̂_{1} = 1, \\ i.e. \\ ϕ̂_{n+1}^{−1} = \frac{1}{ϕ̂_{n+1}} = 1 + \frac{1}{1 + ϕ̂_{n}} = 1 + \frac{1}{1+}ϕ̂_{n} (n ≥ 1). \end{matrix}

The sequence {ϕ_{n}} of (5.4) satisfies

\begin{aligned}ϕ_{n+1} & = 1 + \frac{1}{1+} \frac{1}{1+} \frac{1}{1+} \frac{1}{ϕ_{n−1}} \\ & = 1 + \frac{1}{1+} \frac{1}{1+} \frac{1}{1+} \frac{1}{1+} \frac{1}{1+} \frac{1}{ϕ_{n−2}} \end{aligned}

Similarly {ϕ̂_{n}} of (5.5) satisfies

\begin{aligned}\frac{1}{ϕ̂_{n+1}} & = 1 + \frac{1}{1+} \frac{1}{1+} \frac{1}{1+}ϕ̂_{n−1} \\ & = 1 + \frac{1}{1+} \frac{1}{1+} \frac{1}{1+} \frac{1}{1+}ϕ̂_{n−2} \end{aligned}

¿From this definition, it is seen easily that

(5.6)  lim_{n→∞} ϕ_{n} = ϕ = (\sqrt{5} + 1)/2
(5.7)  lim_{n→∞} ϕ̂_{n} = 1/ϕ = (\sqrt{5} − 1)/2

6. Linear-Quadratic Control problem. The Linear Quadratic (LQ) control problem is to minimize the quadratic cost function over the linear system. If the state of system {x_{t}} moves on

(6.1)  x_{t+1} = x_{t} + a_{t}, t = 0, 1, 2, ⋯

with x_{0} = 1 by an input control {a_{t}, −∞ < a_{t} < ∞} . The cost incured is

(6.2)  ∑_{t=0}^{T −1}(x_{t}^{2} + a_{t}^{2}) + x_{T}^{2} .

Then DP equation of LQ is

(6.3)  v_{t+1}(x) = min_{a∈A_{x}} {r(a, x) + v_{t}(a + x)}

where

\begin{matrix}r(a, x) = a^{2} + x^{2}, \\ a ∈ A_{x} = (−∞, ∞), x ∈ (−∞, ∞) \end{matrix}

Theorem 6.1. The solution of (6.3) is given by

\{ \begin{matrix}v_{0}(x) = ϕ_{T} x^{2} \\ v_{t}(x) = ϕ_{T −t}x^{2}, t = 1, 2, ⋯ \end{matrix}

using the Golden number related sequence {ϕ_{n}} by (5.4).

(Proof) The proof is immediately obtained by an elementary quadratic minimization and then the mathematical induction. □

7. Allocation problem. Allocation problem or sometime called as partition problem is of the form

(7.1)  v_{t+1}(x) = min_{a∈A_{x}} {r(a, x) + v_{t}(a)}

for t = 0, 1, 2, ⋯, T, where

\begin{matrix}r(a, x) = a^{2} + (x − a)^{2}, \\ a ∈ A_{x} = [0, x], x ∈ (−∞, ∞). \end{matrix}

Theorem 7.1. The solution of (7.1) is given by using the dual golden number as

\{ \begin{matrix}v_{0}(x) = ϕ̂_{T} x^{2} \\ v_{t}(x) = ϕ̂_{T −t}x^{2}, t = 1, 2, ⋯ \end{matrix}

(Proof) Using the Schwartz inequality, the following holds immediately: For given positive constants A and B with a fixed x,

min_{0≤a≤1}\{Aa^{2} + B(x − a)^{2}\} = \frac{x^{2}}{1/A + 1/B} .

So the proof could be done inductively. □

Remark 1 : We note here that the number ϕ^{−1} = 0.618 ⋯ of reciprocal of the Golden number is called sometimes Dual Golden number. The above two problems are closely related.

Remark 2 : It is seen that the same quadratic function of the form; v(x) = cx^{2} where c is a constant, becomes a solution if the DP equation is, for Allocation and LQ,

(7.2)  v_{t+1}(x) = min_{a∈A_{x}} {r(a, x) + 2 ∫_{0}^{a} v_{t}(y)/y dy}

(7.3)  v_{t+1}(x) = min_{a∈A_{x}} {r(a, x) + 2 ∫_{0}^{a+x} v_{t}(y)/y dy}

respectively. Refer to [6].

8. Monotone Stopping Game. A monotone rule is introduced to sum up individual declarirations in a multi-variate stopping problem [13]. The rule is defined by a monotone logical function and is equivalent to the winning class of Kadane [?]. There given p-dimensional random process {X_{n}; n = 1, 2, ⋯ } and a stopping rule π by which the group decision determined from the declararion of p players at each stage. The stopping rule is p-variate {0, 1}-valued monotone logical function. We consider two cases of rules with p = 3 as follows:

(8.1)  π(x_{1}, x_{2}, x_{3}) = x_{1} + x_{2}

and

(8.2)  π(x_{1}, x_{2}, x_{3}) = x_{1}x_{2} + x_{1}x_{3}.

That is, in case of the case (8.1), if either of player 1 and 2 declares stop, then the system stops neglecting of x_{3}. In case of (8.1), we have the system stops when either of player 1 and 2 declares stop accompanying with player 1. Without loss of generality, we can assume that each X_{n} takes the uniformly distribution on [0, 1]. Then equilibrium expected values for each player is given as

\begin{matrix}x_{1} & x_{2} & π(x_{1}, x_{2}, x_{3}) \\ 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{matrix}

Figure 1. π(x_{1}, x_{2}, x_{3}) = x_{1} + x_{2} for any x_{3}

\begin{matrix}x_{1} & x_{2} & x_{3} & π(x_{1}, x_{2}, x_{3}) \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \end{matrix} Figure 2. π(x_{1}, x_{2}, x_{3}) = x_{1}x_{2} + x_{1}x_{3}

Player 1 Player 2 Player 3

π(x_{1}, x_{2}, x_{3}) = x_{1} + x_{2}  \frac{\sqrt{5} − 1}{2} \frac{\sqrt{5} − 1}{2}  0.5

π(x_{1}, x_{2}, x_{3}) = x_{1}x_{2} + x_{1}x_{3}  1  \frac{\sqrt{5} − 1}{2} \frac{\sqrt{5} − 1}{2}

Table 1. The equilibrium expected value for each players.

In order to derive the value ϕ^{−1} = \frac{\sqrt{5} − 1}{2} , we consider an equilibrium stopping strategy of threshold type in the form {X_{n} > a} for some a. Bellman type equation for this game version will be given as [13]. That is, each player declares “stop” or “continue” if the observed value exceeds some a or not. The event of the occurence is denoted by D_{n}^{i} = {Player i declares stop}. Two trivial cases are the whole event Ω and the empty event ∅.

In generally a logical function is assumed “monotone” so its function can be written as

π(x^{1}, ⋯, x^{p}) = x^{i} · π(x^{1}, ⋯, 1^{i}, ⋯ x^{p}) + \overline{x^{i}} · π(x^{1}, ⋯, 0^{i}, ⋯ x^{p}) x^{i} ∈ \{0, 1\} ∀i

where \overline{x^{i}} = 1 − x^{i}. Corresponding to this expression,

Π(D^{1}, ⋯, D^{p}) = D^{i} · Π(D^{1}, ⋯, Ω^{i}, ⋯ D^{p}) + \overline{D^{i}} · Π(D^{1}, ⋯, ∅^{i}, ⋯ D^{p})

where \overline{D^{i}} is the complement of the event D^{i}. The general equation for the expected for player i equals

(8.3)  E [(X_{n}^{i} − v^{i})^{+}1_{Π(D_{n}^{1},··· ,Ω^{i},···D_{n}^{p})}] + E [(X_{n}^{i} − v^{i})^{−}1_{Π(D_{n}^{1},··· ,∅^{i},···D_{n}^{p})}]

where D_{n}^{i} = {X_{n}^{i} ≥ v^{i}} and (x)^{+} = max{x, 0}, (x)^{−} = min{x, 0}. If we assume an independence case between player’s random variable X_{n}^{i} for each i. The equation (8.3) becomes as

(8.4)  β_{n}^{Π(i)}E [(X_{n}^{i} − v^{i})^{+}] − α_{n}^{Π(i)}E [(X_{n}^{i} − v^{i})^{−}]

where rule(a)Our objection is to find an equilibrium strategy and values of playes for a given monotone rule as the rule (8.1) and (8.2). A sequence of expected value (a net gain) under the situation formulated in the section is obtained as

(8.5)  v_{n+1}^{i} = v_{n}^{i} + β_{n}^{Π(i)}E [(X_{n}^{i} − v_{n}^{i})^{+}] − α_{n}^{Π(i)}E [(X_{n}^{i} − v_{n}^{i})^{−}]

for player i = 1, ⋯, p and n denotes a time-to-go. The details refer to Theorem 2.1 in YKN [13]. Under these derivation, now we are able to calculate the optimal (equilibrium) value v^{i} = lim_{n} v_{n}^{i} for player i = 1, 2, 3 for the rule (8.1) and (8.2) in the table .

12  S. IWAMOTO AND M. YASUDA

................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................ 7. Apppendix. f(u) = \frac{u^{2} + (1 − u)^{2}}{1 − u^{2}} f′(u) = (−2)\frac{u^{2} − 3u + 1}{(u^{2} − 1)^{2}} f′′(u) = 2\frac{2u^{3} − 9u^{2} + 6u − 3}{(u^{2} − 1)^{3}}  The golden ratio \frac{1 + ϕ}{−(−ϕ)} = \frac{−1 + ϕ}{2 − ϕ} = \frac{ϕ}{1} \frac{−(−ϕ)}{1} = \frac{1}{−1 + ϕ} = \frac{ϕ}{1}  u x  → ↑ • O  ·· ·· ·  · ·  · • 2 − ϕ + −1  + 1  + 3/2 + 2  + 3 ⋆  • 1 + ϕ ⋆ • −1 + ϕ1 2 • • • +  • −2 −ϕ

Figure 1. The curve x = f(u) has dual golden extremum points with a marked ⋆.

References

[1] D. P. Bertsekas, Dynamic Programming and Stochastic Control, Academic Press, New York, 1976.

[2] A. Beutelspacher and B. Petri; Der Goldene Schnitt 2., überarbeitete und erweiterte Auflange, Elsevier GmbH, Spectrum Akademischer Verlag, Heidelberg, 1996.

[3] R. A. Dunlap; The Golden Ratio and Fibonacci Numbers, World Scientific Press, 1997.

[4] S. Iwamoto; Cross dual on the Golden optimum solutions, RIMS Kokyuroku, Kyoto Yniv. No.1443, pp.27-43, 2005.

[5] S. Iwamoto; “The Golden optimum solution in quadratic programming”, Ed. W. Takahashi and T. Tanaka, Proceedings of The Fourth International Conference on Nonlinear Analysis and Convex Analysis (NACA05), Okinawa, Japan, June-July, 2005, Yokohama Publishers, 173–180, 2007.

[6] S. Iwamoto; Controlled integral equations on nondeterminstic dynamic programming: Fredholm and Volterra types, Abstract of Math Soc Japan, Statistic Division, 51–52, March, 2003.

[7] S. Iwamoto and M. Yasuda; “Dynamic programming creates the Golden Ratio, too”, Proc. of the Sixth Intl Conference on Optimization: Techniques and Applications (ICOTA 2004), Ballarat, Australia, December 2004.

[8] S. Iwamoto and M. Yasuda; “Golden Optimal Path in Discrete-Time Dynamic Optimization Processes”, The 15-th International Conference on Difference Equations and Application (ICDEA 2006), Kyoto University, Kyoto, Japan, July, 2006.

[9] J. Neveu; Discrete-Parameter Martingales, North-Holand, Amsterdam, 1975.

[10] Ron  Knott;  “Fibonacci  Numbers  and  the  Golden  Section”  in

http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fib.html

[11] H. Walser; Der Goldene Schnitt, B.G.Teubner, Leibzig, 1996.

[12] D. Williams; Probability with martingales, Cambridge University Press, Cambridge, 1991.

[13] M. Yasuda, J. Nakagami, M. Kurano; “Multi-variate stopping problems with a monotone rule”, J. Oper. Res. Soc. Japan, vol. 25, No. 4, 334-349, (1982).