Juego con pesos

En teoría de juegos, más específicamente en teoría de juegos cooperativos, un juego con pesos o juego de mayoría ponderada (más comúnmente conocido en inglés como weighted game) es un tipo de juego simple en que los votos de algunos jugadores pueden valer más que los de otros. El valor de cada uno de dichos votos queda asumido por distintos pesos específicos.

Formalmente, un juego simple (N,W) es un juego con pesos si existe una cuota (número real positivo) q y una función peso w: N → $\scriptstyle \mathbb{R}$ tal que cada coalición S es ganadora cuando la suma de los pesos de sus miembros es mayor o igual que q.^[1]

Una tupla [q, w₁, ..., w_n], a veces abreviada simplemente [q, w] es una realización del juego.

En teoría de grafos, un juego con pesos puede representarse mediante un threshold graph.

Historia

De estos juegos se habla por primera vez en el libro Theory of Games and Economic Behavior, escrito por el matemático John von Neumann y el economista Oskar Morgenstern en 1944.^[2] Más tarde, son retomados por el matemático John R. Isbell en 1956.^[3]

En el contexto del estudio de transformaciones de transacciones (trade transforms), se conocen bajo el nombre de trade robust games,^[1] y en la lógica umbral, son equivalentes a las funciones umbrales, un subconjunto estricto de las funciones booleanas 2-monótonas.^[4]

Complejidad computacional

Del punto de vista de la complejidad computacional, como son equivalentes a las funciones umbrales, se sabe que son computables en tiempo polinomial. De hecho corresponden a una subclase (estricta^[4] ) de las funciones booleanas 2-monótonas, las cuales también se pueden computar eficientemente.^[5]

Referencias

1. ↑ ^{a b} Taylor, A.D.; Zwicker, W.S. (1999) (en inglés). Simple Games: Desirability Relations, Trading, and Pseudoweightings. W.S. Zwicker. Princeton University Press, NJ. http://press.princeton.edu/titles/6766.html. Consultado el 23 de noviembre de 2010. 
2. ↑ von Neumann, J.; Morgenstern, O. (1944) (en inglés). Theory of Games and Economic Behavior. Princeton University Press, NJ. http://ia600301.us.archive.org/29/items/theoryofgamesand030098mbp/theoryofgamesand030098mbp.pdf. 
3. ↑ Isbell, J.R. (1956) (en inglés). A class of majority games. 7. Ouart J. Math. Oxford Scr..  pp. 183-187. http://qjmath.oxfordjournals.org/content/7/1/183.extract. 
4. ↑ ^{a b} S. Muroga (1971), Threshold Logic and Its Applications, Wiley .
5. ↑ Kazuhisa Makino (2002), A linear time algorithm for recognizing regular Boolean functions, 43, Journal of Algorithms: Academic Press, pp. 155–176 .