Abstract
This paper proposes a model for incomplete games where the knowledge of the players is represented by a Dempster-Shafer belief function. Beyond an extension of the classical definitions, it shows such a game can be transformed into an equivalent hypergraphical complete game (without uncertainty), thus generalizing Howson and Rosenthal’s theorem to the framework of belief functions and to any number of players. The complexity of this transformation is finally studied and shown to be polynomial in the degree of k-additivity of the mass function.
Pierre Pomeret-Coquot and Helene Fargier have benefited from the AI Interdisciplinary Institute ANITI. ANITI is funded by the French “Investing for the Future – PIA3” program under the Grant agreement n\(^\circ \)ANR-19-PI3A-0004.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Named after Selten, who proposed a similar definition for Bayesian games [16].
- 2.
We could use the notation \(\rho \) for both, but the pure strategy profiles of the credal game are vectors of functions \(\rho _i: \varTheta _i \mapsto A_i\) while the pure strategy profiles of \(\tilde{G}\) are vectors in \(\prod _{i\in N, \theta _i \in \varTheta _i} A_i\). So, we keep the two notations \(\tilde{\rho }\) and \(\rho \).
- 3.
The proofs are omitted for the sake of brevity and can be found at [11].
- 4.
Notice that in the latter approach, the belief function is understood as the lower bound of an imprecise probability – under this interpretation, the conditioning at work must rather be Fagin-Halpern’s [10].
References
Augustin, T., Schollmeyer, G.: Comment: on focusing, soft and strong revision of choquet capacities and their role in statistics. Stat. Sci. 36(2), 205–209 (2021)
Campos, L.M.D., Huete, J.F., Moral, S.: Probability intervals: a tool for uncertain reasoning. Int. J. Uncertain. Fuzziness Knowl. Based Syst. 2(2), 167–196 (1994)
Chapman, A., Farinelli, A., de Cote, E.M., Rogers, A., Jennings, N.: A distributed algorithm for optimising over pure strategy nash equilibria. In: Proceedings AAAI (2010)
Choquet, G.: Theory of capacities. Ann. de l’institut Four. 5, 131–295 (1954)
Dempster, A.P.: Upper and lower probabilities induced by a multivalued mapping. Ann. Math. Stat. 38, 325–339 (1967)
Denoeux, T., Shenoy, P.P.: An interval-valued utility theory for decision making with dempster-shafer belief functions. Int. J. Approx. Reason. 124, 194–216 (2020)
Dubois, D., Denoeux, T.: Conditioning in dempster-shafer theory: prediction vs. revision. In: Proceedings BELIEF, vol. 164, pp. 385–392. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29461-7_45
Eichberger, J., Kelsey, D.: Non-Additive Beliefs and Game Theory. Tilburg University, Center for Economic Research, Technical report (1994)
Ellsberg, D.: Risk, ambiguity, and the savage axioms. Q. J. Econ. 75, 643–669 (1961)
Fagin, R., Halpern, J.Y.: A new approach to updating beliefs. In: Proceedings UAI, pp. 347–374 (1990)
Fargier, H., Martin-Dorel, E., Pomeret-Coquot, P.: Games of Incomplete Information: a Framework Based on Belief Functions – version with proofs. https://www.irit.fr/~Erik.Martin-Dorel/ecrits/2021_credal-games_ecsqaru_extended.pdf or in HAL
Ghirardato, P., Le Breton, M.: Choquet rationality. J. Econ. Theory 90(2), 277–285 (2000)
Gilboa, I.: Expected utility with purely subjective non-additive probabilities. J. Math. Econ. 16(1), 65–88 (1987)
Gilboa, I., Schmeidler, D.: Maxmin expected utility with non-unique prior. J. Math. Econ. 18(2), 141–153 (1989)
Grabisch, M.: Upper approximation of non-additive measures by k-additive measures-the case of belief functions. In: ISIPTA, pp. 158–164 (1999)
Harsanyi, J.C.: Games with incomplete information played by “bayesian’’ players, I-III part I. The basic model. Manag. Sci. 14(3), 159–182 (1967)
Howson, J.T., Jr., Rosenthal, R.W.: Bayesian equilibria of finite two-person games with incomplete information. Manag. Sci. 21(3), 313–315 (1974)
Jaffray, J.Y.: Linear utility theory for belief functions. Oper. Res. Lett. 8(2), 107–112 (1989)
Miranda, P., Grabisch, M., Gil, P.: Dominance of capacities by \(k\)-additive belief functions. Eur. J. Oper. Res. 175(2), 912–930 (2006)
Montes, I., Miranda, E., Destercke, S.: Unifying neighbourhood and distortion models: Part II - new models and synthesis. Int. J. Gen. Syst. 49(6), 636–674 (2020)
Morgenstern, O., Von Neumann, J.: Theory of Games and Economic Behavior. Princeton University Press (1953)
Mukerji, S.: Understanding the nonadditive probability decision model. Econ. Theory 9(1), 23–46 (1997)
Mukerji, S., Shin, H.S.: Equilibrium departures from common knowledge in games with non-additive expected utility. Adv. Theor. Econ. 2(1), 1011 (2002)
Myerson, R.B.: Game Theory. Harvard University Press, Cambridge (2013)
Nash, J.: Non-cooperative games. Ann. Math., 286–295 (1951)
Papadimitriou, C.H., Roughgarden, T.: Computing correlated equilibria in multi-player games. J. ACM 55(3), 1–29 (2008)
Quiggin, J.: A Theory of Anticipated Utility. J. Econ. Behav. Organ. 3(4), 323–343 (1982)
Savage, L.J.: The Foundations of Statistics. Wiley, Hoboken (1954)
Schmeidler, D.: Integral representation without additivity. Proc. Am. Math. Soc. 97(2), 255–261 (1986)
Shafer, G.: A Mathematical Theory of Evidence. Princeton University Press, Princeton (1976)
Smets, P., Kennes, R.: The transferable belief model. Artif. Intell. 66(2), 191–234 (1994)
Wahbi, M., Brown, K.N.: A distributed asynchronous solver for nash equilibria in hypergraphical games. Front. Artif. Intell. Appl. 285, 1291–1299 (2016)
Yanovskaya, E.: Equilibrium points in polymatrix games. Lithuanian Math. J. 8, 381–384 (1968)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Fargier, H., Martin-Dorel, É., Pomeret-Coquot, P. (2021). Games of Incomplete Information: A Framework Based on Belief Functions. In: Vejnarová, J., Wilson, N. (eds) Symbolic and Quantitative Approaches to Reasoning with Uncertainty. ECSQARU 2021. Lecture Notes in Computer Science(), vol 12897. Springer, Cham. https://doi.org/10.1007/978-3-030-86772-0_24
Download citation
DOI: https://doi.org/10.1007/978-3-030-86772-0_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-86771-3
Online ISBN: 978-3-030-86772-0
eBook Packages: Computer ScienceComputer Science (R0)