Anar al contingut

Joc de majoria ponderada

De L'Enciclopèdia, la wikipedia en valencià

En teoria de jocs, més específicament en teoria de jocs cooperatius, un joc en pesos o joc de majoria ponderada (més comunament conegut en anglés com weighted game) és un tipo de joc simple que els vots d'alguns jugadors poden valdre més que els de uns atres. El valor de cada u de dits vots queda assumit per distints pesos específics.

Formalment, un joc simple (N,W) és un joc en pesos si existix una quota (número real positiu) q i una funció pese w: N → ℝ tal que cada coalició S és guanyadora quan la suma dels pesos dels seus membres és major o igual que q.[1]

Una tupla [q, w1, ..., wn], a voltes abreviada simplement [q, w] és una realisació del joc.

En teoria de grafos, un joc en pesos pot representar-se per mig d'un threshold graph.

Història

D'estos jocs es parla per primera volta en el llibre Theory of Games and Economic Behavior, escrit pel matemàtic John von Neumann i l'economiste Oskar Morgenstern en 1944.[2] Més tart, són represos pel matemàtic John R. Isbell en 1956.[3]

En el context de l'estudi de transformacions de transaccions (trade transforms), es coneixen baix el nom de trade robust games,[1] i en la llògica llindar, són equivalents a les funciones llindars, un subconjunt estricte de les funcions booleanas 2-monòtones.[4]

Complexitat computacional

Del punt de vista de la complexitat computacional, com són equivalents a les funciones llindars, se sap que són computables en temps polinòmic. De fet corresponen a una subclasse (estricta[4]) de les funcions booleanas 2-monòtones, les quals també es poden computar eficientemente.[5]

Referències

  1. ↑ 1,0 1,1 Taylor, A.D.; Zwicker, W.S. (1999). Simple Games: Desirability Relations, Trading, and Pseudoweightings, W.S. Zwicker (en anglés), Princeton University Press, NJ. Consultat el 23 de novembre de 2010.
  2. ↑ von Neumann, J.; Morgenstern, O. (1944). Theory of Games and Economic Behavior (en anglés), Princeton University Press, NJ.
  3. ↑ Isbell, J.R.(1956).«A class of majority games».Ouart J. Math. Oxford Scr..7: 183-187.(en anglés)
  4. ↑ 4,0 4,1 Erro en la seqüencia d'órdens: no existix el mòdul «Citas»..
  5. ↑ Erro en la seqüencia d'órdens: no existix el mòdul «Citas»..


Referències