DIMACS TR: 2009-07
On effectivity functions of game forms
Authors: Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Kazuhisa Makino
ABSTRACT
To each game form g an effectivity function (EFF) Eg can be naturally assigned. An EFF E will be called formal (respectively, formal-minor) if E = Eg (respectively, E<=Eg) for a game form g.
(i) An EFF is formal if and only if is superadditive and monotone.
(ii) An EFF is formal-minor if and only if it is weakly superadditive.
Theorem (ii) looks more sophisticated, yet, it is simpler and instrumental in the proof of (i). 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. (Peleg's proof works also in case of an infnite set of outcomes.) Both constructions are elegant, yet, the set of strategies Xi of each player i in I in g might be doubly exponential in size of the input EFF E. In this paper, we suggest a third construction such that jXij is only linear in the size of E.
One can verify in polynomial time whether an EFF is formal (or superadditive); in contrast, verification of whether an EFF is formal-minor (or weakly superadditive) is a CoNP-complete decision problem.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2009/2009-07.pdf
DIMACS Home Page