Local Bounds for Incentive Compatible Selection Mechanisms in Forests

We studied the incentive-compatible selection mechanisms for directed forests. A directed forest is an acyclic directed graph with maximum out-degree equal to 1. A selection mechanism gives a probability distribution on each vertex in the forest. A selection mechanism is incentive-compatible (IC), if the probability assigned to a vertex does not change when it changes which it points to (or add, delete the edge).An IC mechanism is fair if the probability of a vertex is always larger then the one with less vertices with access to itself, and the probability of a vertex is always equal to the one with the same number of vertices with access to itself. An IC mechanism is exact if the sum of the probability of each vertex is always 1.The quality of a selection mechanism is the worst-case ratio between the expected number with access to each vertex and the maximum number with access to a vertex. The upper bound is decided by a special case and the lower bound is decided by a mechanism. In this paper, we focus on the local case for this question, i.e. n = 2, 3.We prove that for n = 2, the tight bound of quality for IC, fair and exact mechanisms are all 0.8. For n = 3, IC mechanisms achieve a bound of quality [7/9, 0.8]. However, fair mechanisms achieve a bound of quality [0.6, 0.8] and exact mechanisms achieve a tight bound 7/9.