Selling oranges when people queue up in a line We have $a$ oranges to give to $b$ people. Each person has a value $f(n)$ for receiving $n$ oranges, where $f$ is a nondecreasing, nonnegative function that is the same for everyone. Let $X$ be the maximum total value possible (summing up everybody's value).
Suppose that we set a price $p$ for each orange, and people queue up in a line. If there are $k$ oranges left, the next person will choose the number $l\in[0,k]$ that maximizes the profit $f(l)-p\cdot l$. Let $Y$ be the total value obtained this way (if there are ties, break them in a way that $Y$ is as low as possible.)
It is obvious that $Y\le X$. Is there a positive constant $r$ such that for any $a,b,f$, we can find $p$ so that $Y\ge rX$?
 A: Yes, we can choose $p$ such that at least $Y\geq \tfrac 14 X.$
It might help to visualize the concave envelope $\hat f$ of $f.$  This is a real-valued function defined on the range of reals $0\leq x\leq a.$ It agrees with $f$ at the extreme points - the points $(n,f(n))$ such that whenever $n=\theta n_1+(1-\theta) n_2$ with $0<\theta<1$ and $n_1<n<n_2,$ we have $f(n)>\theta f(n_1)+(1-\theta)f(n_2).$ And between these points it is a straight line. In other words, it is the top edge of the convex hull of the points $(n,f(n)).$
By convex duality, the extreme points are precisely what a suitable choice of $p$ can force the first person to buy. On the other hand, $X/b$ lies beneath $\hat f(a/b),$ because $(a/b,X/b)$ is a convex combination of the points $(n,f(n)).$ There are three cases:


*

*If $(a/b,\hat f(a/b))$ is itself an extreme point then $X/b=\hat f(a/b)$ and a choice of $p$ can force everyone to buy $a/b$ oranges, giving $X=Y.$ Otherwise, $\hat f$ has a line segment going through the point $(a/b,\hat f(a/b)).$

*If the slope of $\hat f$ at $a/b$ is at most $X/2a,$ then the leftmost (smallest $n$) point $(n,f(n))$ of the line segment going through $(a/b,\hat f(a/b))$ satisfies $f(n)\geq X/2b.$ A choice of $p$ can force everyone to buy $n$ oranges, giving $Y\geq \tfrac 12 X.$

*If the slope of $\hat f$ at $a/b$ is at least $X/2a$ then the rightmost point $(n,f(n))$ of the line segment going through $(a/b,\hat f(a/b))$ satisfies $f(n)\geq nX/2a.$ A choice of $p$ can force the first $\lfloor a/n\rfloor$ people to buy $n$ oranges, giving $Y\geq \tfrac 1 2 X \frac{\lfloor a/n\rfloor}{a/n}\geq \tfrac 1 4 X.$
