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

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

CC BY-SA 4.0
2019-03-07T09:53:16.840Z
2019-03-07T09:53:16.840Z
Dengji Zhao
<p>I am trying to understand <a href="http://dengji-zhao.net/publications/AAMAS/Zhao_AAMAS2018.pdf" rel="nofollow noreferrer">this</a> paper. </p>

<p>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. </p>

<p>I understand it as follows: </p>

<p>So for any node <span class="math-container">$i \in N$</span>, the payment is: <span class="math-container">$\mathcal{SW}_{-D_{i}} - (\mathcal{SW}_{-C_{i}^{\mathcal{K}}}-v_{i}^{'})$</span> </p>

<p><span class="math-container">$D_{i}$</span> is the union of <span class="math-container">$i$</span> and its critical children,</p>

<p><span class="math-container">$\mathcal{SW}_{-D_{i}}$</span> sums over all nodes except the nodes in <span class="math-container">$D_{i}$</span>. </p>

<p><span class="math-container">$\pi_{j}(\theta^{'})$</span> is 1 if <span class="math-container">$j$</span> receives an item, else 0. </p>

<p>Thus, <span class="math-container">$\mathcal{SW}_{-D_{i}}$</span> is the sum of the bids of the nodes that receive an item and are not <span class="math-container">$i$</span> and not a critical child of <span class="math-container">$i$</span>. </p>

<p>So for node D (figure 5) I get: <span class="math-container">$\mathcal{SW}_{-D_{D}} = 19 + 17 + 20 = 56$</span>  </p>

<p><span class="math-container">$C_{i}^{\mathcal{K}}$</span> is the set of the top <span class="math-container">$\mathcal{K}$</span> ranked critical children of <span class="math-container">$i$</span> according to their bid. When the set is smaller that 5, we just take all critical children. </p>

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

<p>Finally, <span class="math-container">$v_{i}^{'}$</span> is just node <span class="math-container">$i$</span>'s reported valuation (bid). </p>

<p>For node D:  <span class="math-container">$v_{D}^{'} = 14$</span>. </p>

<p>Thus when I calculate D's payment: 
<span class="math-container">$\mathcal{SW}_{-D_{D}} - (\mathcal{SW}_{-C_{D}^{\mathcal{K}}} - v_{D}^{'}) = 56 - (70 - 14) =  0$</span>.</p>

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

<p>Has anyone read this paper already and can help me?</p>

<combinatorial-game-theory><mechanism-design>
Auction theory - Selling Multiple Items via Social Networks
cmplx96
# Auction theory - Selling Multiple Items via Social Networks

(Asked by: username_0 on 2018-11-19)

I am trying to understand [this](http://dengji-zhao.net/publications/AAMAS/Zhao_AAMAS2018.pdf) 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?

**Tags:** combinatorial-game-theory, mechanism-design


---

## 1 answers

### Answer by username_1 on 2019-03-07. Score: 1 | Accepted answer

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.


---

