TY - JOUR
T1 - On effectivity functions of game forms
AU - Boros, Endre
AU - Elbassioni, Khaled
AU - Gurvich, Vladimir
AU - Makino, Kazuhisa
N1 - Funding Information:
✩ This research was partially supported by DIMACS, Center for Discrete Mathematics and Theoretical Computer Science; the third author gratefully acknowledges the partial support of the Aarhus University Research Foundation and Center for Algorithmic Game Theory and also Equipe Combinatoire & Optimization, Université Pierre et Marie Curie, Paris 6. * Corresponding author. E-mail addresses: [email protected] (E. Boros), [email protected] (K. Elbassioni), [email protected] (V. Gurvich), [email protected] (K. Makino).
PY - 2010/3
Y1 - 2010/3
N2 - To each game form g an effectivity function (EFF) Eg is assigned. An EFF E is called formal (formal-minor) if E = Eg (respectively, E ≤ Eg) 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, (ii) 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 Xi of players i ∈ I might be doubly exponential in size of the input EFF E. In this paper, we suggest another construction such that | Xi | is only linear in the size of E. Also, we extend Theorems (i), (ii) to tight and totally tight game forms.
AB - To each game form g an effectivity function (EFF) Eg is assigned. An EFF E is called formal (formal-minor) if E = Eg (respectively, E ≤ Eg) 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, (ii) 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 Xi of players i ∈ I might be doubly exponential in size of the input EFF E. In this paper, we suggest another construction such that | Xi | is only linear in the size of E. Also, we extend Theorems (i), (ii) to tight and totally tight game forms.
KW - Dual-minor
KW - Effectivity function
KW - Game form
KW - Monotone
KW - Self-dual
KW - Superadditive
KW - Tight
KW - Totally tight
KW - Weakly superadditive
UR - http://www.scopus.com/inward/record.url?scp=75349108113&partnerID=8YFLogxK
U2 - 10.1016/j.geb.2009.09.002
DO - 10.1016/j.geb.2009.09.002
M3 - Article
AN - SCOPUS:75349108113
SN - 0899-8256
VL - 68
SP - 512
EP - 531
JO - Games and Economic Behavior
JF - Games and Economic Behavior
IS - 2
ER -