A Lower Bound On The Cost Recovery Of The Steiner Tree Game With Cross - Monotonic Cost Shares

In this article it is proven that no cross-monotonic cost-sharing method can guarantee a recovery of more than 12 of the cost of the computed tree in the Steiner Tree game. Hence the algorithms described by Jain and Vazirani [3] (Steiner Tree game) and by K¨onemann et al. [2] (Steiner Forest game) are the best possible. This is accomplished by modifying an instance used in the paper by Immorlica et al. [1] for the Facility Location game, and bounding the expected value of the sum of the cost shares.