2012/08/03 by Diodato Ferraioli, Ferraioli, Diodato, Paolo Penna +1
Computer Science · Decision Sciences · Engineering · Mathematics · #Auction Theory and Applications #Best response #Business #Compatibility (geochemistry) #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #Computer science #Convergence (economics) #Distributed systems and fault tolerance #Economics #Engineering #FOS: Computer and information sciences #Game Theory and Applications #Imperfect #Incentive #Incentive compatibility #Mathematical economics #Mathematical optimization #Mathematics #Microeconomics #Nash equilibrium #Risk analysis (engineering) #cs.CC #cs.GT
paper · pdf · doi:10.48550/arxiv.1208.0699
In the conference version of this work, we claimed that in a modified version of PageRank games, there exists a subgame which is a potential game and thus our results can be used to obtain a good approximation of the logit dynamics for these games. Unfortunately, this claim was wrong and the logit dynamics for this subgame is in general not easy to analyze
openalex publication_date 2012/08/03 · arxiv created 2014/01/31 · arxiv updated 2014/02/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Best-response mechanisms (Nisan, Schapira, Valiant, Zohar, 2011) provide a unifying framework for studying various distributed protocols in which the participants are instructed to repeatedly best respond to each others' strategies. Two fundamental features of these mechanisms are convergence and incentive compatibility. This work investigates convergence and incentive compatibility conditions of such mechanisms when players are not guaranteed to always best respond but they rather play an imperfect best-response strategy. That is, at every time step every player deviates from the prescribed best-response strategy according to some probability parameter. The results explain to what extent convergence and incentive compatibility depend on the assumption that players never make mistakes, and how robust such protocols are to "noise" or "mistakes".