3
$\begingroup$

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$?

See http://blog.felixbreuer.net/2013/02/06/digital-goods.html

Note: Sorry if I didn't phrase this clearly. Feel free to ask for clarification in the comments.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Jan 17 '16 at 16:22
  • $\begingroup$ @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.) $\endgroup$ – PyRulez Jan 18 '16 at 4:47
  • $\begingroup$ @Raphael Also, has crowdfunding been more prevalent other places? $\endgroup$ – PyRulez Jan 18 '16 at 21:09
  • $\begingroup$ @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? $\endgroup$ – mhum Jan 19 '16 at 3:22
  • $\begingroup$ @mhum That would be correct. The intuition though is that the $M_i$ are all rather small compared to $P$. In the image, all the $M_i$ are below $\$100$, while $P=\$1.0$m ($\$1000000$). (Its not like everyone is willing to pay for the whole statue.) $\endgroup$ – PyRulez Jan 19 '16 at 3:24
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The problem is the number of possible prices could be on the order of $n$. $\endgroup$ – PyRulez Jan 19 '16 at 3:26
0
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.