I am trying to understand this paper.

The one thing that I cannot wrap my head around is the payment policy for the Generalized Information Diffusion Mechanism. It is explained on page 72 with examples on page 73.

I understand it as follows:

So for any node $i \in N$, the payment is: $\mathcal{SW}_{-D_{i}} - (\mathcal{SW}_{-C_{i}^{\mathcal{K}}}-v_{i}^{'})$

$D_{i}$ is the union of $i$ and its critical children,

$\mathcal{SW}_{-D_{i}}$ sums over all nodes except the nodes in $D_{i}$.

$\pi_{j}(\theta^{'})$ is 1 if $j$ receives an item, else 0.

Thus, $\mathcal{SW}_{-D_{i}}$ is the sum of the bids of the nodes that receive an item and are not $i$ and not a critical child of $i$.

So for node D (figure 5) I get: $\mathcal{SW}_{-D_{D}} = 19 + 17 + 20 = 56$

$C_{i}^{\mathcal{K}}$ is the set of the top $\mathcal{K}$ ranked critical children of $i$ according to their bid. When the set is smaller that 5, we just take all critical children.

For node D: $\mathcal{SW}_{-C_{i}^{\mathcal{K}}} = 19 + 17 + 20 + 14 = 70$ (all nodes that receive an item that are not D's critical children).

Finally, $v_{i}^{'}$ is just node $i$'s reported valuation (bid).

For node D: $v_{D}^{'} = 14$.

Thus when I calculate D's payment: $\mathcal{SW}_{-D_{D}} - (\mathcal{SW}_{-C_{D}^{\mathcal{K}}} - v_{D}^{'}) = 56 - (70 - 14) = 0$.

Of course this is wrong because it always comes out as 0 and in reality D has to pay 10.

Has anyone read this paper already and can help me?


the calculation of $\mathcal{SW}_{-D_i}$ and $\mathcal{SW}_{-C_i^\mathcal{K}}$ is incorrect. There are still $\mathcal{K}$ items to be allocated in both allocations, so for node $D$, the first is 20+19+17+11+10 and the second is 20+19+17+14+11. So D's payment is 10.

p.s. there is a typo in one of the constraints for the two allocations, which is updated in the paper.


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.