# Average Cost Threshold Protocol with Minimum Thresholds: How to find the price?

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.

• Crowdfunding has reached CS/mathematics, it seems! Cool! FWIW, if the motivation is to solve the problem fast in practice, looking beyond $\Theta(n \log n)$ may not be worth the time. Improving the algorithm you have (constant factors, average case) may return more on your investment. – Raphael Jan 17 '16 at 16:22
• @Raphael mostly theoretical at this point. (That said, this protocol for funding is much more efficient than open source and closed source, in a certain technical yet broad sense. I'm surprised it hasn't arisen naturally.) – PyRulez Jan 18 '16 at 4:47
• @Raphael Also, has crowdfunding been more prevalent other places? – PyRulez Jan 18 '16 at 21:09
• @PyRulez I'm not sure I understand the example you gave with all $m_i = 0$. If all the $M_i$ are sufficiently large, then shouldn't the optimal $p = P/n$? I.e.: if 10 people are willing to pay between up to 100 for something where $P = 20$, then everyone should just pay 2, right? – mhum Jan 19 '16 at 3:22