×

zbMATH — the first resource for mathematics

Approximate implementation in Markovian environments. (English) Zbl 1330.91102
Summary: This paper considers dynamic implementation problems in environments with changing private information (according to Markov processes). A social choice function is approximately implementable if it is correctly implemented an arbitrary large number of times with arbitrary high probability in all (communication) equilibria. We show that if a social choice function is strictly efficient in the set of social choice functions that satisfy an undetectability condition, then it is approximately implementable.

MSC:
91B26 Auctions, bargaining, bidding and selling, and other market models
91B14 Social choice
60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
91A25 Dynamic games
91A20 Multistage and repeated games
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abreu, Dilip; Sen, Arunava, Virtual implementation in Nash equilibrium, Econometrica, 59, 997-1021, (1991) · Zbl 0732.90007
[2] Cesa-Bianchi, Nicolò; Lugosi, Gábor, Prediction, learning, and games, (2006), Cambridge University Press · Zbl 1114.91001
[3] Escobar, Pablo; Toikka, Juuso, Efficiency in games with Markovian private information, Econometrica, 81, 1887-1934, (2013) · Zbl 1291.91025
[4] Fink, Arlington M., Equilibrium in a stochastic n-person game, J. Sci. Hiroshima Univ., 28, 89-93, (1964) · Zbl 0126.36506
[5] Forges, F., An approach to communication equilibria, Econometrica, 54, 1375-1385, (2006) · Zbl 0605.90146
[6] Frankel, Alex, 2011. Discounted quotas. Mimeo, Standford GSB.
[7] Fudenberg, Drew; Levine, David K.; Maskin, Eric, The folk theorem with imperfect public information, Econometrica, 62, 997-1039, (1994) · Zbl 0819.90137
[8] Glynn, Peter; Ormoneit, Dirk, Hoeffding’s inequality for uniformly ergodic Markov chains, Stat. Probab. Lett., 56, 143-146, (2002) · Zbl 0999.60019
[9] Jackson, Matthew O.; Sonnenschein, Hugo F., Overcoming incentive constraints by linking decisions, Econometrica, 75, 241-258, (2007) · Zbl 1201.91036
[10] Lee, Jihong, Sabourian, Hamid, 2008. Efficient repeated implementation II: incomplete information. Unpublished. · Zbl 1241.91046
[11] Lee, Jihong; Sabourian, Hamid, Efficient repeated implementation, Econometrica, 79, 1967-1994, (2011) · Zbl 1241.91046
[12] Lee, Jihong, Sabourian, Hamid, 2013. Repeated implementation with incomplete information. Mimeo, Cambridge University. · Zbl 1330.91072
[13] Lehrer, Ehud, Lower equilibrium payoffs in two-player repeated games with non-observable actions, Int. J. Game Theory, 18, 57-89, (1989) · Zbl 0675.90109
[14] Mailath, George J.; Matthews, Steven A.; Sekiguchi, Tadashi, Private strategies in finitely repeated games with imperfect public monitoring, Contrib. Theor. Econ., 2, 1, (2002), Article 2
[15] Matsushima, Hitoshi, New approach to the implementation problem, J. Econ. Theory, 45, 128-144, (1988) · Zbl 0642.90011
[16] Matsushima, Hitoshi; Miyazakim, Koichi; Yagi, Nobuyuki, Role of linking mechanisms in multitask agency with hidden information, J. Econ. Theory, 145, 2241-2259, (2010) · Zbl 1203.91070
[17] Mertens, Jean-Francois; Parthasarathy, T., Non zero sum stochastic games, (Raghavan, T. E.S.; etal., Stochastic Games and Related Topics, (1991), Kluwer Academic Publishers), 145-148 · Zbl 0753.90087
[18] Mezzetti, Claudio, Renou, Ludovic, 2014. Repeated Nash implementation. Mimeo.
[19] Myerson, R. B., Multistage games with communication, Econometrica, 54, 323-358, (2006) · Zbl 0599.90134
[20] Radner, Roy, Monitoring cooperative agreements in a repeated principal-agent relationship, Econometrica, 49, 1127-1148, (1981) · Zbl 0463.90100
[21] Radner, Roy, Repeated principal-agent games with discounting, Econometrica, 53, 1173-1198, (1985) · Zbl 0574.90100
[22] Rahman, David, 2011. Detecting profitable deviations. Mimeo, University of Minnesota.
[23] Renault, Jérôme; Solan, Eilon; Vieille, Nicolas, Dynamic sender-receiver games, J. Econ. Theory, 148, 502-534, (2013) · Zbl 1275.91026
[24] Sason, Igal, On refined versions of the azuma-Hoeffding inequality with applications in information theory, (February 2012)
[25] Townsend, Robert M., Optimal multiperiod contracts and the gain from enduring relationships under private information, J. Polit. Econ., 90, 1166-1186, (1982)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.