2023/09/26 by Ivan Geffner, Joseph Y. Halpern, Geffner, Ivan +1 · 2 citations
Decision Sciences · Economics, Econometrics and Finance · #91A27 (Secondary) #91A28 (Primary) 91A18 #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2309.14618
openalex publication_date 2023/09/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider k-resilient sequential equilibria, strategy profiles where no player in a coalition of at most k players believes that it can increase its utility by deviating, regardless of its local state. We prove that all k-resilient sequential equilibria that can be implemented with a trusted mediator can also be implemented without the mediator in a synchronous system of n players if n >3k. In asynchronous systems, where there is no global notion of time and messages may take arbitrarily long to get to their recipient, we prove that a k-resilient sequential equilibrium with a mediator can be implemented without the mediator if n > 4k. These results match the lower bounds given by Abraham, Dolev, and Halpern (2008) and Geffner and Halpern (2023) for implementing a Nash equilibrium without a mediator (which are easily seen to apply to implementing a sequential equilibrium) and improve the results of Gerardi, who showed that, in the case that k=1, a sequential equilibrium can be implemented in synchronous systems if n ≥ 5.