snippetMinor
Average Cost Threshold Protocol with Minimum Thresholds: How to find the price?
Viewed 0 times
findprotocolthepricewithminimumaveragethresholdsthresholdhow
Problem
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.
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.
Solution
There are two standard kinds of approaches to this sort of problem.
-
Check out segment trees and interval trees, and see if either of them are useful here (e.g., by augmenting the data structure).
-
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.
-
Check out segment trees and interval trees, and see if either of them are useful here (e.g., by augmenting the data structure).
-
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.
Context
StackExchange Computer Science Q#51965, answer score: 2
Revisions (0)
No revisions yet.