×

Hard and soft preparation sets in Boolean games. (English) Zbl 1422.91157

Summary: A fundamental problem in game theory is the possibility of reaching equilibrium outcomes with undesirable properties, e.g., inefficiency. The economics literature abounds with models that attempt to modify games in order to avoid such undesirable properties, for example through the use of subsidies and taxation, or by allowing players to undergo a bargaining phase before their decision. In this paper, we consider the effect of such transformations in Boolean games with costs, where players control propositional variables that they can set to true or false, and are primarily motivated to seek the satisfaction of some goal formula, while secondarily motivated to minimise the costs of their actions. We adopt (pure) preparation sets (prep sets) as our basic solution concept. A preparation set is a set of outcomes that contains for every player at least one best response to every outcome in the set. Prep sets are well-suited to the analysis of Boolean games, because we can naturally represent prep sets as propositional formulas, which in turn allows us to refer to prep formulas. The preference structure of Boolean games with costs makes it possible to distinguish between hard and soft prep sets. The hard prep sets of a game are sets of valuations that would be prep sets in that game no matter what the cost function of the game was. The properties defined by hard prep sets typically relate to goal-seeking behaviour, and as such these properties cannot be eliminated from games by, for example, taxation or subsidies. In contrast, soft prep sets can be eliminated by an appropriate system of incentives. Besides considering what can happen in a game by unrestricted manipulation of players’ cost function, we also investigate several mechanisms that allow groups of players to form coalitions and eliminate undesirable outcomes from the game, even when taxes or subsidies are not a possibility.

MSC:

91A44 Games involving topology, set theory, or logic
91A10 Noncooperative games
91A12 Cooperative games

References:

[1] Aumann, R. J., Game theory, in J. Eatwell, M. Milgate, and P. Newman (eds.), The New Palgrave: A Dictionary of Economics, vol. 2, MacMillan, London, 1987, pp. 460-482
[2] Basu K., Weibull J.: Strategy subsets closed under rational behavior. Economic Letters 36, 141-146 (1991) · Zbl 0741.90097 · doi:10.1016/0165-1765(91)90179-O
[3] Bernheim B.D.: Rationalizable strategic behavior. Econometrica 52(4), 1007-1028 (1984) · Zbl 0552.90098 · doi:10.2307/1911196
[4] Bonzon, E., M.-C. Lagasquie, J. Lang, and B. Zanuttini, Boolean games revisited, in Proceedings of the Seventeenth European Conference on Artificial Intelligence (ECAI-2006), Riva del Garda, Italy, 2006, pp. 265-269 · Zbl 1262.68168
[5] Bonzon E., Lagasquie-Schiex M.-C., Lang J.: Dependencies between players in Boolean games. International Journal of Approximate Reasoning 50, 899-914 (2009) · Zbl 1186.91018 · doi:10.1016/j.ijar.2009.02.008
[6] Bonzon E., Lagasquie-Schiex M.-C., Lang J., Zanuttini B.: Compact preference representation and Boolean games. Autonomous Agents and Multi-Agent Systems 18(1), 1-35 (2009) · doi:10.1007/s10458-008-9040-2
[7] Coase R. H.: The nature of the firm. Economica 4(16), 386-405 (1937) · doi:10.1111/j.1468-0335.1937.tb00002.x
[8] Coase R.H.: The problem of social cost. Journal of Law and Economics 3, 1-44 (1960) · doi:10.1086/466560
[9] Dufwenberg M., Norde H., Reijnierse H., Tijs S.: The consistency principle for set-valued solutions and a new direction for normative game theory. Mathematical Methods of Operations Research 54(1), 119-131 (2001) · Zbl 1035.91003 · doi:10.1007/s001860100154
[10] Dunne, P. E., S. Kraus, W. van der Hoek, and M. Wooldridge, Cooperative Boolean games, in Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2008), Estoril, Portugal, 2008, pp. 1015-1022 · Zbl 0741.90097
[11] Harrenstein, P., P. Turrini, and M. Wooldridge, Hard and soft equilibria in Boolean games, in A. Lomuscio, P. Scerri, A. Bazzan, and M. Huhns (eds.), Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2014), Paris, France, 2014, pp. 845-852 · Zbl 1422.91157
[12] Harrenstein, P., W. van der Hoek, J.-J.Ch. Meyer, and C. Witteveen, Boolean games, in J. van Benthem (ed.), Proceeding of the Eighth Conference on Theoretical Aspects of Rationality and Knowledge (TARK VIII), Siena, Italy, 2001, pp. 287-298
[13] Jackson M.O., Wilkie S.: Endogenous games and mechanisms: Side payments among players. Review of Economic Studies 72(2), 543-566 (2005) · Zbl 1121.91013 · doi:10.1111/j.1467-937X.2005.00342.x
[14] Levit, V., T. Grinshpoun, and A. Meisels, Boolean games for charging electric vehicles, in Proceedings of 2013 IEEE/WIC/ACM International Conferences on Web Intelligence (WI) and Intelligent Agent Technology (IAT), 2013 · Zbl 1121.91013
[15] Levit, V., T. Grinshpoun, A. Meisels, and A. Bazzan, Taxation search in Boolean games, in Proceedings of 12th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-2013), St Paul, MN, 2013 · Zbl 1427.91012
[16] Maskin E.S.: The invisible hand and externalities. American Economic Review 84(2), 333-337 (1994)
[17] Meade J.: External economies and diseconomies in a competitive situation. Economic Journal 62(245), 54-67 (1952) · doi:10.2307/2227173
[18] Norde H., Potters J., Reijnierse H., Vermeulen D.: Equilibrium selection and consistency. Games and Economic Behavior 12(2), 219-225 (1996) · Zbl 0848.90132 · doi:10.1006/game.1996.0014
[19] Osborne M. J., Rubinstein A.: A Course in Game Theory. The MIT Press, Cambridge, MA (1994) · Zbl 1194.91003
[20] Pearce D.G.: Rationalizable strategic behavior and the problem of perfection. Econometrica 52(4), 1029-1050 (1984) · Zbl 0552.90097 · doi:10.2307/1911197
[21] Sauro L., Villata S.: Dependency in cooperative Boolean games. Journal of Logic and Computation 23(2), 425-444 (2013) · Zbl 1262.68168 · doi:10.1093/logcom/exr030
[22] Turrini, P., Endogenous Boolean games, in Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI-13), Beijing, China, 2013, pp. 390-396 · Zbl 1270.68340
[23] Varian H.: Microeconomic Analysis, 3rd ed., W. W. Norton, New York (1992)
[24] Voorneveld M.: Preparation. Games and Economic Behaviour 48, 403-414 (2004) · Zbl 1085.91006 · doi:10.1016/j.geb.2003.09.006
[25] Wooldridge M., Endriss U., Kraus S., Lang J.: Incentive engineering for Boolean games. Artificial Intelligence 195, 418-439 (2013) · Zbl 1270.68340 · doi:10.1016/j.artint.2012.11.003
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.