The protocol is defined here, but I'll give a summary here.
Okay, so a number of agents want a certain public good to be constructed (a public good is something like a book, a program, or a statue, something that can optionally benefit everyone once constructed.) It costs $P$ to construct this good. The agents each give an interval that they are willing to pay. Agent $i$'s interval is $[m_i,M_i]$. (In the case of a rational agent, $m_i=0$, but if the agent is somewhat altruistic, $m_i>0$. It has been proven that $M_i$ will always be how much value a rational agent $i$ expects to extract from the public good.)
Now, in this protocol, each person pays the same price $p$, or $m_i$, whichever is greater, or pays nothing at all if $p > M_i$. (Those who pay get access to the good, those who don't are excluded from the good.) What I am trying to do is find the minimum $p$, such that the total amount paid (let's call it $F(p)$) is equal to or greater than $P$, efficiently.
If all $m_i$ are $0$ and there are $n$ agents, I can do it $\mathcal O(n \log n)$. I first sort the agents by $M_i$. Then starting with the agent with least $M_i$, I figure out how much funds will be available with $p=M_i$. If $F(M_i) \gt P$, than $M_i$ is the minimum $p$. Otherwise, we go to the next agent, and so on. $F(M_i)$ can be calculated in $\mathcal O (n)$, by multiplying $M_i$ by how many agents come after (or are) agent $i$ (for each agent $j$ that comes after $i$, $M_j \ge M_i$. Since $p=M_i$, not $p>M_j$, and agent $j$ pays $p=M_i$.) (Note, I've left out the analysis for when $p$ is between the $M_i$'s; it doesn't change the it too much.)
My question is, how does one solve this problem efficiently in general, when the $m_i$ may not be $0$?
Note: Sorry if I didn't phrase this clearly. Feel free to ask for clarification in the comments.