We have had an opportunity to review Professor Patrice Marcotte's 'A Note on Khilnani and Tse's USA Algorithm'. First we wish to thank Professor Marcotte for his remarks. Next we address the issues raised in the note.
In his note Professor Marcotte makes three points. First, he claims that the proof of convergence as given in our original paper, 'A Fixed Point Algorithm with Economic Applications ' (1985), is incorrect. He then .proposes a new algorithm together with its convergence proof. Finally Professor Marcotte shows some interesting properties that his algorithm satisfies. We address each point below.
In attempting to disprove the USA algorithm, Professor Marcotte develops a bound that the sequence of vectors ~r(k) must satisfy in relation to 7r(1) and ~r(0). He then implies that the bound is violated by USA and hence the algorithm will not converge. This logical argument is incorrect. The sufficiency bound developed is too loose. Violation of Professor Marcotte's sufficiency condition is insufficient to disprove the convergence of the USA algorithm.
The new algorithm presented by Professor Marcotte computes the relaxation parameter X via a new method. The new algorithm is consistent with our proof of convergence which indicated that any h < 2/(1 + p 2) would guarantee convergence. Other algorithms are also possible. Each algorithm may offer some distinct advantage over others.
In the USA algorithm the parameter h is based on the one-step minimization of error, which in turn is dependent on current error. Professor Marcotte's X's form a prespecified monotonic decreasing sequence. Heuristically we can argue that convergence of the USA algorithm should take fewer iterations than Marcotte's algorithm. In practice, performance comparison has to take both the number of iteration and time per iteration into consideration. In practice, performance is problem-dependent. We performed one simple test. We ran Professor Marcotte's algorithm on the problem presented in the USA paper. Five runs with arbitrarily chosen ~r(1)'s are performed. The results are indica-