Problema en la comisión de la UE

Question

Considere el siguiente problema.

Una colección de $n$ países $C_1, \dots, C_n$ sentarse en una comisión de la UE. Cada país $C_i$ es asignado a un voto peso $c_i$. Una resolución pasa si cuenta con el apoyo de una parte del panel de al menos $A$, teniendo en cuenta las ponderaciones de los votos. Cada país $C_i$ tiene una probabilidad $p_i$ de la votación de la resolución, y cada país actúa de forma independiente de los demás.

El problema es asignar las ponderaciones de los votos con el fin de maximizar la probabilidad de que cualquier resolución que va a pasar. Estoy interesado en responder a la pregunta asintóticamente bajo algo como los siguientes supuestos.

1. El número de países, $n$ es muy grande. (Tal vez el de la UE de $n = 28$ ya no tan lejos de esto!)

2. La proporción de los votos que ningún país está acotada arriba por $M/n$, para algunos fijos número razonable $M$.

3. $p_i > A$ todos los $i$.

4. Las probabilidades de $p_i$ se apartó de $1$.

Tal vez algunas de estas condiciones pueden ser relajado, o tal vez los supuestos adicionales son necesarios, pero estos son los que parecen ser necesarias para mis argumentos a continuación.

He tratado de responder a la pregunta en forma aproximada y no rigurosa de la siguiente manera.

Deje $X_i$ ser la variable aleatoria igual a $1$ país $C_i$ de los votos para la resolución, y $0$ lo contrario. Ahora vamos a $V = \sum c_i X_i$. Por un adecuadamente versión general del teorema del límite central (la Baya-Esseen la desigualdad?), $V$ sigue aproximadamente una distribución normal con media de $\sum c_i p_i$ y la varianza $\sum c_i^2 p_i(1-p_i)$. La probabilidad de que nos gustaría a maximizar es $$P\left( V \geq A\sum c_i \right).$$

Si dejamos $F(z)$ ser la función de distribución acumulativa de la distribución normal estándar, esta probabilidad puede ser aproximada por $F(z)$ donde $$z = \frac{\sum c_i(p_i - A)}{\left[\sum c_i^2 p_i (1-p_i) \right]^{1/2}}. $$

Teniendo en cuenta el gradiente de la función de $z = z(c_1,\dots,c_n)$ muestra que $z$ es máxima cuando los pesos $c_i$ son proporcionales a los números $$\gamma_i = \frac{p_i - A}{p_i(1-p_i)}.$$

Yo a la conclusión de que es plausible que los pesos $c_i = \gamma_i$ son cerca de ser óptima.

Mis preguntas, en orden descendente de importancia, son:

1. Tiene algo importante ha escrito acerca de este problema, o un equivalente?

2. Es mi "teorema", ¿correcto?

3. ¿Qué sería de una rigurosa formulación de la "teorema"?

EDIT: he simulado el problema de $A = 0.5$ con 1867 países con un 50.17% de probabilidad de votar a favor y 637 países con una probabilidad de 50.5%. Me dio peso $1$ a cada uno del primer grupo de países y peso $c$ a la segunda. En el siguiente gráfico, el eje horizontal es de $c$, y el eje vertical para la probabilidad de aprobar la resolución. La curva azul representa la probabilidad teórica tendríamos si la aproximación normal funcionó a la perfección, y el rojo de la curva experimental, basado en datos de 5 millones de repeticiones del experimento. El máximo de la gráfica roja no está demasiado lejos de la conjetura valor óptimo de $\gamma = 2.94$.

EDIT: En respuesta a un comentario, aquí están algunos detalles adicionales sobre la maximización de $z$ por encima. Por homogeneidad, no hace ninguna diferencia si estamos o no de limitar las $c_i$'s tener suma $1$. Pero si lo hacemos, entonces una compacidad argumento muestra que el $z$ debe alcanzar un máximo en algún punto.

Ahora regrese a sin restricciones de la $c_i$'s. $\partial z/\partial c_i$ tiene el mismo signo que $$\frac{\sum c_j^2 p_j (1 - p_j)}{\sum c_j (p_j - A)} \gamma_i - c_i.$$ Esto demuestra que cuando el máximo se produce, todos los $c_i$'s debe ser proporcional a $\gamma_i$.

Answer 1

Este es un problema interesante! En su teorema: no entiendo por qué a maximizar $z$, que es sólo una densidad (hasta ese punto todo parece bien). Desea maximizar $P(V\ge A)$. Usted asume suficiente para muchos países en que esto puede ser aproximada por una distribución normal, invocando alguna versión de la CLT. Por lo tanto, $$P(V\ge A)\approx \int^\infty_A \phi\left(\frac{x-\sum c_ip_i}{\sqrt{\sum c_i^2 p_i(1-p_i})}\right) dx=1-\Phi\left(\frac{A-\sum c_ip_i}{\sqrt{\sum c_i^2 p_i(1-p_i)}}\right).$$ Cómo maximizar esta? No estoy del todo seguro. Recuerdo que la distribución normal es registro-cóncavo, y el CDF de registro-cóncavo funciones de log-cóncava. Así que si $log(\Phi(x))$ es cóncava, a continuación, $-log(\Phi(x))$ es convexa. Pero eso no nos ayuda aquí..

Un par de sugerencias más:

• En la hipótesis 2): ¿por Qué usted necesita $M$ si se define pesos $c_i$ ya?

• En su formulación, podría limitar los pesos de a $\sum_i c_i=1$, entonces la condición es $V\ge A$, se ve más bonito, pero no es necesario.

• En asunción 3): estoy de acuerdo en que no hará que el problema no tiene sentido, pero parece innecesario - no cambia el problema de maximización. Sólo implica que, dicen, incluso a igualdad de voto de la distribución del peso que daría lugar a más pases que los fracasos de las resoluciones. Pero el problema de la $p_i<A$ para algunos (o incluso todos) los países que todavía sería interesante. Dada la aproximación normal, todavía hay una probabilidad positiva de que se aprobara la resolución, siempre que $p_i>0$ todos los $i$, pero sería más difícil. De esta forma se podría modelo "más difícil resultions".

• En la hipótesis 1) y 3): si $n\to\infty$, luego de la asunción 3 garantiza que la solución pasa, como el tiempo que han positivos peso $c_i$ en todos los países. Porque la espera voteshare está por encima de $A$, y asintóticamente a la espera voto compartir da cuenta de que con probabilidad 1 (algunas fuertes ley de los grandes números). Interesante: si algunos países tienen $p_i>A$ (positiva de masa, para ser exactos) y algunos $p_i<A$, $n\to\infty$ puede garantizar la aprobación de la resolución por dar positivo pesos para todos los con $p_i>A$ y ninguno a los otros.

• Dado el punto anterior, parece peligroso para hablar de "asymptotics" - usted sólo quiere finitely pero muchos países, de modo que usted puede aproximar con una distribución normal, pero en realidad no quieres a$n\to\infty$, ya que el problema entonces es trivial dado hipótesis 3). Tal vez esto es lo que el autor del comentario anterior quería decir.

• ¿Dónde puede encontrar algo similar? Creo que su mejor opción podría ser la de finanzas de la literatura, donde calcular la probabilidad de que su cartera de inversión de retorno está por encima de un cierto umbral $A$. Hay algunos activos que tienen una estructura similar a estos votos (por ejemplo, bonos): el activo paga un dividendo positivo o el emisor va a la quiebra y el retorno es cero, al igual que su variable aleatoria $X_i$. Mismo para una cartera de préstamos.

• Sus comentarios acerca de "llegar a una decisión correcta", me recordó que el jurado de Condorcet teoremas. El entorno es un caso especial de la suya, donde cada miembro tiene el mismo voto de peso y el umbral de la mayoría es $A=1/2$
• También me recordó el Feddersen Pesendorfer juego teórico de análisis de la unanimidad reglas de votación. Ninguno de los dos están directamente relacionados con su problema. De nuevo, las finanzas parece ser su mejor apuesta.

Answer 2

http://en.m.wikipedia.org/wiki/Roy's_safety-first_criterion

(Relacionados con los problemas de financiación).

tratando de elegir una cartera que maximiza la probabilidad de satisfacer un umbral es probablemente cerca del problema que estamos mencionando aquí.

En cuanto a la UE, su objetivo cuando el sistema no estaba demasiado lejos de lo que usted está describiendo. La idea era también para evitar la formación de coaliciones contra Francia y Alemania (si los 2 están de acuerdo en algo, es muy difícil de bloquear, y a la inversa, es muy difícil aprobar una ley sin ellos acordar).

Answer 3

Perdóname si esta solución puede parecer demasiado "simplista", tal vez no he entendido algo en tu pregunta original, pero lo que deduje es que usted tiene que establecer los distintos votos de los países de una manera que maximice la probabilidad de que una resolución por la que pasa. Curiosamente para todos los supuestos que se mencionan, 3 de ellos no importa en que mi solución y sólo número 2 tenía un significado.

Me hizo agregar un adicional de asunción, aunque. Todos los países son "ordenados" por la disminución de la probabilidad de aprobar la resolución, lo que significa:

$$ p_n \le p_{n-1} \le ... \le p_2 \le p_1$$

No debería afectar a la generalidad demasiado, ya que la probabilidad es de datos (por lo que yo entiendo).

Vamos a w el peso relativo de votos:

$$ w_i = {c_i \over \sum c_i}$$

De ello se sigue que:

$$ \sum w_i = 1 $$

También digamos que m es el límite de la proporción de votos:

$$ m = {M \over n} $$

Considere la posibilidad de que m es menor que 1, así que podemos escribir lo siguiente:

$$ {1 \over m} = k + \eta$$

Donde k es un entero y eta es un número real mayor o igual que 0 pero menor que 1.

Esto es útil para contar cómo muchos países puede tener asignado un peso de m, y, de hecho vamos a asignar a m a exactamente K de los países con la más alta probabilidad. (la primera K)

$$ w_1 = ... = w_k = m $$

País K + 1 tendrá los "restos" (tenga en cuenta que si eta es cero, este país se pone a cero votos):

$$ w_{k+1} = 1 - m \cdot k $$

Todos los demás se ponen a cero votos:

$$ w_{k+2} = ... = w_n = 0 $$

Tenga en cuenta que estos valores son en pesos, en pesos reales de los votos que simplemente tienen que multiplicar todos los pesos por la misma constante arbitraria.

De nuevo, ya que esto parece ser demasiado "simplista", es muy probable que me he perdido algo en tu pregunta original o no se entienden completamente. Si ese es el caso, por favor, dime y yo te borra de esta respuesta.