On effectivity functions of game forms

• 成果类型: Article
• 署名作者: Boros, Endre; Elbassioni, Khaled; Gurvich, Vladimir; Makino, Kazuhisa
• 署名单位: Max Planck Society; Rutgers University System; Rutgers University New Brunswick; University of Tokyo
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2009.09.002
• 发表日期: 2010
• 页码: 512-531
• 关键词: Game form; tight; Totally tight; Effectivity function; monotone; Superadditive; Weakly superadditive; Dual-minor; Self-dual

摘要

To each game form an effectivity function (EFF) E-g is assigned. An EFF E is called formal (formal-minor) if E = E-g (respectively, E <= E-g) for a game form g. (i) An EFF is formal iff it is superadditive and monotone. (ii) An EFF is formal-minor iff it is weakly superadditive. Theorem (ii) looks more sophisticated, yet, it is simpler than Theorem (i) and instrumental in its proof. In addition, (it) has important applications in social choice, game, and even graph theories. Constructive proofs of (i) were given by Moulin, in 1983, and by Peleg, in 1998. Both Constructions are elegant, yet, sets of strategies X-i of players i is an element of 1 might he doubly exponential in size of the input EFF E. In this paper, we suggest another construction such that vertical bar X-i vertical bar is only linear in the size of E. Also, we extend Theorems (i), (ii) to tight and totally tight game forms. (C) 2009 Elsevier Inc. All rights reserved.