# A Recursive Maximization Problem

Let $A\ge B>0$ be real constants. I say that a function $f:[0,1]\rightarrow[0,1]$ satisfies the $(A,B)$-condition if for all $p\in [0,1]$, the expression $$q(A-Bp-Bf(q))$$ is maximized (not necessarily uniquely) at $q=f(p)$. More precisely, this means that for all $p,q$ we have $$f(p)(A-Bp-Bf(f(p)))\ge q(A-Bp-Bf(q))$$

(Of course, it's only the ratio $A/B$ that matters.)

I am interested in finding all functions from the unit interval to itself that satisfy the $(A,B)$-condition. I am particularly interested in the case $A=4,B=3$.

Some partial results (unless I've made mistakes, but I believe I've proved these):

Theorem. The only function satisfying the $(1,1)$-condition is $$f(p)=\cases{1&if p \neq 1\cr 0&if p=1}$$

Theorem. Suppose that $f$ satisfies the $(4,3)$-condition. Then:

1. If $x>y$ and $y$ is in the range of $f$, then $f(x)>f(y)$.

2. There exists a $p$ such that $f(p)\le 1/3$.

3. $f$ does not take the value $0$.

4. For all $p$, we have $p+f(f(p))\le 4/3$

5. The range of $f$ is infinite.

Question 1. Are there any functions satisfying the $(4,3)$ condition? If so, what are they?

Question 2. Same question with $(4,3)$ replaced by $(A,B)$.

(Note: This earlier question is vaguely related to the current one, but probably not really terribly relevant.)

-

## 1 Answer

Here is the sketch of how one can work this problem out: first, we can assume that $a=\frac{A}{B}>1,$ and the problem is equivalent to $$f(p)(a-p-f(f(p)))\ge q(a-p-f(q)).$$

Replacing $q\to f(q),$ we can rewrite the inequality as follows: $$(f(p)-f(q))(a-p)\ge f(p)f(f(p))-f(q)f(f(q)).$$ Switch $q$ and $p$ and add the results up to end up with $$(f(p)-f(q))(q-p)\ge 0.$$ The last inequality implies that $f$ is decreasing function. To simplify life, let me assume that $a> 2,$ but everything below can be adjusted to work for general case.

Since $a>2> p+f(f(p)),$ then for any $q\ge f(p)$ we must have $$a- p-f(f(p))> a-p-f(q)$$ or $f(q)\ge f(f(p))$ which is impossible since $f$ should decrease unless $f$ is constant on $[f(p),1].$ Now if $f(p)<f(q)$ for some $p\ne q$ we have $$(f(p)-f(q))(a-p)\ge f(p)f(f(p))-f(q)f(f(q))=f(f(p))(f(p)-f(q)),$$ we must have $a-p<f(f(p))$ which is impossible.

The general case could be handled in the same manner since you can always choose $p$ close to zero to satisfy $a>f(f(p))+p$ to obtain immediately that $f$ is $1$ near zero.

-
Safoura: This is great. I think the last part can be made even easier, since it's not hard to show that the restriction of $f$ to its own range is an increasing function. Together with your proof that it's decreasing, this makes $f\circ f$ a constant function, and one can go from there. –  Steven Landsburg Oct 25 '13 at 5:23
I'd like to cite your proof that $f$ is non-increasing in a note I'm writing. I'm not sure whether you'd rather stay anonymous or let me use your real name. I'll be glad if you can send me guidance (at the email address in my profile). –  Steven Landsburg Nov 4 '13 at 17:24