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

Question

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.

Answer 1

There are two standard kinds of approaches to this sort of problem.

1. Check out segment trees and interval trees, and see if either of them are useful here (e.g., by augmenting the data structure).

2. Explore a sweep line algorithm. In this sort of algorithm, we envision $p$ increasing from 0 upward as time progresses, and at each point in time, we keep track of the set of all intervals that contain $p$. Thus, when $p$ hits the left endpoint of an interval, we add it to the set; when it reaches the right endpoint, we remove it from the set. You can store the set as a balanced binary tree data structure, and then make it persistent using standard path copying techniques. Now that you have this persistent data structure that captures all points in time, often you can find a way to solve your problem fairly rapidly. Crucially, the tree will be of size $O(n \lg n)$ and depth $O(\lg n)$, so accesses are fast.

I haven't explored either of those approaches in the context of your particular problem, but these are two general techniques that are often useful for problems of this sort.

Answer 2

Okay, so this is how far I got. Adding each agent is $\mathcal O(n)$, for a total of $\mathcal O(n^2)$, but spread out (the application I had in mind would involve agents coming one at a time).

If you have no agents, start with an empty linked list. If you have $n$ agents, you will already have a solution of $p_{old}$ for $n-1$ agents, as well as an old linked list, as well as our new agent, agent $i$.

The linked list has elements of the form $(\Delta P_j,m_j,M_j)$, where $\Delta P_j = P - F(M_j)$, a.k.a., how much more money is needed if $p=M_j$. It is sorted by $M_j$, smallest first.

So we traverse our linked list, starting with $(\Delta P_j,m_j,M_j)$. If $M_i \ge M_j$, decrease $\Delta P_j$ accordingly. If $\Delta P_j = 0$, $p=M_j$, then the rest of the linked list is discarded (including agent $j$'s node), and we end. If $\Delta P_j \gt 0$, continue traversing. If $M_i < M_j$, keep a reference to $j$'s node. Now traverse the rest of the list to determine $\Delta P_i$. If $\Delta P_i = 0$, then $p=M_i$, and throw out all nodes after and including agent $j$. If $\Delta P_i \gt 0$, then before $j$ insert a node $(\Delta P_i,m_i,M_i)$, and $p=p_{old}$.