European tenure games

We study a variant of the tenure game introduced by Spencer (Theoret. Comput. Sci. 131 (1994) 415). In this version, faculty is not fired, but downgraded to the lowest rung instead. For the upper bound we give a potential function argument showing that the value v_d of the game starting with d faculty on the first rung satisfies v_d ≤ ⌊log ₂d+log₂log₂d+1.98⌋. We prove a nearly matching lower bound of ⌊log₂d+log₂log ₂d⌋ using a strategy that can be interpreted as an antirandomization of Spencer's original game. For d tending to infinity, these bounds improve to ⌊log₂d+log₂log ₂d+1+o(1)⌋ ≤ v_d ≤ ⌊log ₂d+log₂log₂d+1.73+o(1)⌋. In particular, the set of all dN such that the value of the game is precisely ⌊log ₂d+log₂log₂d+1⌋ has lower density greater than 1/5.