SIER Working Paper Series

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. Then, we introduce a procedure which enables us to calculate the maximum sequentially for each agent. By applying the 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.

Keywords: Minimum cost spanning tree problems, demand operators, irreducible matrix, Dutta-Kar rule, Prim algorithm

JEL classification: C71