Strong Demand Operator and the Dutta-Kar Rule for Minimum Cost Spanning Tree Problems

Abstract

We study the strong demand operator introduced by Granot and Huberman (1984) for minimum cost spanning tree problems. First, we review the strong demand operator. Next, we study the irreducible minimum cost spanning tree games and the irreducible core. Finally,we define a procedure with tie-breaking rule which generates an allocation from given initial allocation. In our procedure, a cost matrix is changed to its irreducible matrix before the operator is applied. We show that the Dutta-Kar allocation is obtained by applying the strong demand operator from any allocation in irreducible core.