Speaker(s)
Youngsub Chun (Seoul National University)
Date
2013-01-14
Location
Amsterdam

We investigate the implications of two demand operators, the weak demand operator and the strong demand operator, introduced by Granot and Huberman (1984) for minimum cost spanning tree problems (mcstp’s). The demand operator is intended to measure the maximum amount that each agent can ask to her followers in compensation for making a link to her. However, the original definition of the weak demand operator does not capture this idea and we propose its modification. Moreover, we introduce a procedure with the tie-breaking rule so that the maximum can sequentially be calculated for each agent. By applying this modified weak demand operator to the irreducible mcstp’s, the Dutta-Kar allocation is obtained from any component-wise efficient initial allocation. For the strong demand operator, the Dutta-Kar allocation can be obtained if the procedure is initiated from any allocation in the irreducible core.