Quantum entanglement is known to provide a strong advantage in many two-party distributed tasks. We investigate the question of how much entanglement is needed to reach optimal performance. For the first time we show that there exists a purely classical scenario for which no finite amount of entanglement suffices. To this end we introduce a simple two-party nonlocal game H, inspired by Lucien Hardy’s paradox. In our game each player has only two possible questions and can provide bit strings of any finite length as answer. We exhibit a sequence of strategies which use entangled states in increasing dimension d and succeed with probability 1 – O(d–c) for some c ≥ 0:13. On the other hand, we show that any strategy using an entangled state of local dimension d has success probability at most 1 – Ω(d–2). In addition, we show that any strategy restricted to producing answers in a set of cardinality at most d has success probability at most 1 –Ω (d–2). Finally, we generalize our construction to derive similar results starting from any game G with two questions per player and finite answers sets in which quantum strategies have an advantage.