Hispanopedia Wiki
Articulo de referencia

Método de partes iguales

El método de reparto equitativo ( MES ) [ 1 ] es un algoritmo de presupuesto participativo diseñado específicamente para garantizar una representación justificada ampliada (una ...

Hispanopedia WikiContenido en espanolLectura gratuita

El método de reparto equitativo ( MES ) [ 1 ] es un algoritmo de presupuesto participativo diseñado específicamente para garantizar una representación justificada ampliada (una forma de representación proporcional ). Fue desarrollado originalmente para elecciones de comités (bajo el nombre de Regla X ). [ 2 ] Posteriormente se adaptó al presupuesto participativo (PB) [ 3 ] [ 4 ] y a decisiones públicas simultáneas. [ 5 ] [ 6 ] Puede utilizarse con cualquier formato de votación disponible, incluyendo votaciones de aprobación , votaciones por orden de preferencia o votaciones cardinales . El MES se ha utilizado para el presupuesto participativo en varias ciudades europeas. [ 7 ]

MES puede describirse como un miembro de una clase de métodos de votación llamados reglas de aprobación ampliadas introducidas a principios de 2019 por Aziz y Lee para preferencias ordinales (que incluyen boletas de aprobación). [ 8 ]

Motivación

La mayoría de las ciudades que implementan presupuestos participativos utilizan el algoritmo de la mochila , a pesar de ser un método desproporcionado. Por ejemplo, si el 51 % de la población apoya 10 proyectos rojos y el 49 % apoya 10 proyectos azules, y solo hay fondos para 10 proyectos, el presupuesto de la mochila elegirá los 10 proyectos rojos apoyados por el 51 %, y el 49 % restante quedará sin financiación. [ 9 ]

En cambio, MES garantiza la representación proporcional . Específicamente, satisface una variante extendida del axioma de representación justificada , adaptada al presupuesto participativo. [ 3 ] Esto significa que un grupo del X por ciento de la población tendrá el X por ciento del presupuesto destinado a proyectos apoyados por el grupo (suponiendo que todos los miembros del grupo hayan votado igual o al menos de forma similar). En particular, en el ejemplo anterior, MES seleccionaría al menos 5 proyectos azules y al menos 4 rojos (el décimo proyecto podría ser rojo o azul, dependiendo del método de finalización utilizado).

En el contexto de las elecciones de comités, existen otras reglas con garantías de representación justificada similares, como el voto de aprobación proporcional . Sin embargo, MES se ejecuta en tiempo polinomial y, por lo tanto, puede aplicarse fácilmente incluso a elecciones realistas con un gran número de votantes.

Procedimiento

MES tiene varias variantes, todas las cuales tienen la siguiente estructura para el presupuesto participativo:

1. Inicialización: El conjunto de "ganadores" (candidatos elegidos) se inicializa como un conjunto vacío. A cada votante i se le asignan b i unidades de dinero virtual; por lo general, b i es igual al presupuesto total disponible dividido por n (el número de votantes).

2. Bucle principal: Cada ronda consta de dos pasos:

  • (a) Uno de los candidatos restantes es elegido y añadido al conjunto de ganadores.
  • (b) El candidato elegido es financiado por sus partidarios; es decir, cada votante que lo apoya "paga" una cierta cantidad de su dinero virtual, de manera que la suma de todos los pagos sea igual al costo del candidato.

A medida que el dinero virtual total disminuye en cada ronda, finalmente ya no se pueden financiar más proyectos; en ese momento, el ciclo principal termina.

3. Finalización: Si el presupuesto disponible no se ha agotado (es decir, algunos votantes aún tienen dinero virtual, pero no es suficiente para financiar a ningún candidato restante), entonces se puede utilizar algún método de finalización para agregar algunos candidatos, hasta que no se puedan agregar más candidatos sujetos a las restricciones presupuestarias.

Para las elecciones de comités se utiliza la misma estructura, salvo que se supone que el "coste" de cada candidato es 1, y el "presupuesto" total disponible es el tamaño deseado del comité (generalmente denotado por k ). Así, cada votante recibe inicialmente k / n unidades de dinero virtual.

Las variantes de MES difieren en la forma en que eligen a un candidato en cada ronda y en cómo distribuyen su coste entre los agentes.

Bucle principal: papeletas de aprobación y utilidades binarias

Si los votantes emiten su voto mediante papeletas de aprobación , entonces MES pretende distribuir el coste del proyecto elegido p de la forma más equitativa posible entre sus partidarios. En concreto:

  • Si algunos s votantes aprueban p , y cada uno de ellos tiene al menos coste( p )/ s de dinero virtual, entonces cada uno de ellos paga exactamente coste( p )/ s.
  • De lo contrario, los simpatizantes con poco dinero restante pagan todo lo que les queda, y el costo restante se divide equitativamente entre los simpatizantes restantes. Esto significa que cada uno de los simpatizantes restantes paga más que costo( p )/ s.

Formalmente, paraρ≥0{\displaystyle \rho \geq 0}, decimos que el proyectopag{\displaystyle p}esρ{\displaystyle \rho }-asequible si

∑i∈norte,i aprueba pagmin(bi,ρ)=doost(pag).{\displaystyle {\begin{aligned}\sum _{i\in N,i{\text{ aprueba }}p}\min \left(b_{i},\rho \right)=\mathrm {costo} (p){\text{.}}\end{aligned}}}

Aquí, cada seguidor i con muy poco dinero virtual paga b i , mientras que todos los demás seguidores paganρ{\displaystyle \rho }Aquí tienes algunos ejemplos.

  • Un proyecto con un coste de 100 recibe el apoyo de 4 votantes, quienes aportan 25, 50, 75 y 100 monedas virtuales respectivamente. Dado que 100/4=25 y todos los partidarios tienen al menos 25 monedas virtuales, todos ellos pagarán 25; por lo tanto, el proyecto es asequible con un coste de 25. Los agentes se quedarán con 0, 25, 50 y 75 monedas virtuales respectivamente.
  • Un proyecto con un costo de 105 recibe el apoyo de los mismos 4 votantes, con 0, 25, 50 y 75 de dinero virtual. El primero no puede contribuir en absoluto. El segundo no puede contribuir con 100/3, por lo que aporta los 25 restantes. El costo restante es de 80. Este se puede dividir equitativamente entre el tercer y cuarto partidario, cada uno de los cuales pagaría 40. Por lo tanto, el proyecto es 40-asequible . Los agentes se quedarán con 0, 0, 10 y 35 de dinero virtual respectivamente.

En cada ronda, el proyecto elegido es un proyecto que esρ{\displaystyle \rho }-asequible para los más pequeñosρ{\displaystyle \rho }Es decir, elegimos un proyecto que minimiza la cantidad máxima que puede pagar un solo donante.

Ejemplo 1

En el siguiente ejemplo, hay 9 proyectos, cada uno con un costo de $200. Hay 100 votantes con papeletas de aprobación. El presupuesto total es de $1000, lo que permite seleccionar cinco proyectos de los nueve disponibles. Consulte el diagrama animado a continuación, que ilustra el funcionamiento de la regla.

El presupuesto se divide primero a partes iguales entre los votantes; así, cada votante recibe 10 dólares. ProyectoD{\displaystyle \mathrm {D} }recibió la mayor cantidad de votos y es seleccionado en la primera ronda. Si dividimos el costo deD{\displaystyle \mathrm {D} }por igual entre los votantes que apoyabanD{\displaystyle \mathrm {D} }cada uno de ellos pagaría$200/66≈$3.03{\displaystyle \$200/66\approx \$3.03}Por el contrario, si seleccionáramosmi{\displaystyle \mathrm {E} }, entonces el costo por votante sería$200/46≈$4.34{\displaystyle \$200/46\approx \$4.34}El método selecciona primero el proyecto que minimiza el precio por votante.

Tenga en cuenta que en el último paso, el proyectoH{\displaystyle \mathrm {H} }fue seleccionado a pesar de que había proyectos que contaban con el apoyo de más votantes, dicenmi{\displaystyle \mathrm {E} }Esto se debe a que el dinero que los partidarios demi{\displaystyle \mathrm {E} }tenía derecho a controlar se utilizó anteriormente para justificar la selección deD{\displaystyle \mathrm {D} },A{\displaystyle \mathrm {A} }, ydo{\displaystyle \mathrm {C} }Por otro lado, los votantes que votaron porH{\displaystyle \mathrm {H} }forman el 20 por ciento de la población y, por lo tanto, tendrán derecho a decidir sobre el 20 por ciento del presupuesto. Esos votantes apoyaron soloH{\displaystyle \mathrm {H} }Y por eso se seleccionó este proyecto.

Para un ejemplo más detallado que incluye votaciones cardinales , consulte el Ejemplo 2 .

Bucle principal: papeletas cardinales

Si los votantes votan mediante papeletas cardinales , entonces MES tiene como objetivo distribuir el costo de un proyecto elegido p proporcionalmente a las utilidades que los votantes obtienen del proyecto. Formalmente, tenemos un conjunto de proyectosPAG={pag1,pag2,…,pagmetro}{\displaystyle P=\{p_{1},p_{2},\ldots ,p_{m}\}}y un conjunto de votantesnorte={1,2,…,norte}{\displaystyle N=\{1,2,\ldots ,n\}}Para cada proyectopag∈PAG{\displaystyle p\in P}dejardoost(pag){\displaystyle \mathrm {costo} (p)}denotemos su costo y dejemosb{\displaystyle b}denota el tamaño del presupuesto municipal disponible.

Por cada votantei∈norte{\displaystyle i\in N}y cada proyectopag∈PAG{\displaystyle p\in P}dejartúi(pag){\displaystyle u_{i}(p)}denotan eli{\displaystyle i}El voto cardinal del cardenal enpag{\displaystyle p}, ese es el número que cuantifica el nivel de apreciación del votantei{\displaystyle i}hacia el proyectopag{\displaystyle p}. Para cualquierρ≥0{\displaystyle \rho \geq 0}, decimos que el proyectopag{\displaystyle p}esρ{\displaystyle \rho }-asequible si

∑i∈nortemin(bi,ρ⋅túi(pag))=doost(pag).{\displaystyle {\begin{aligned}\sum _{i\in N}\min \left(b_{i},\rho \cdot u_{i}(p)\right)=\mathrm {cost} (p){\text{.}}\end{aligned}}}

Intuitivamente, si un proyecto p es ρ{\displaystyle \rho }-asequible, entonces su costo puede distribuirse entre los votantes de manera que cada votante pague el precio por utilidad de como máximoρ{\displaystyle \rho }(los votantes con suficiente dinero pagaránρ⋅túi(pag){\displaystyle \rho \cdot u_{i}(p)}y los demás votantes pagarán el resto de su dinero b i ).

Si hay al menos uno aún no seleccionadoρ{\displaystyle \rho }-proyecto asequible, MES selecciona el proyecto p que esρ{\displaystyle \rho }-asequible para el valor más bajo deρ{\displaystyle \rho }(el proyecto que minimiza el precio por servicio que los votantes deben pagar).

Ejemplo 2

El siguiente diagrama ilustra el comportamiento de MES con votaciones cardinales.

Bucle principal: votaciones de aprobación (de nuevo)

La descripción anterior de MES con votaciones de aprobación puede verse como un caso especial de MES con votaciones cardinales donde los agentes tienen utilidades binarias , túi(pag)=1{\displaystyle u_{i}(p)=1}si el proyectopag{\displaystyle p}es aprobado por los votantesi{\displaystyle i}, ytúi(pag)=0{\displaystyle u_{i}(p)=0}de lo contrario. Esto supone que la utilidad de un votante es igual al número de proyectos seleccionados aprobados. Esta definición suele dar como resultado la selección de más proyectos, pero menos costosos, ya que un proyecto con un costo menor generalmente seráρ{\displaystyle \rho }-asequible para un valor menor deρ{\displaystyle \rho }.

Alternativamente, se pueden asumir utilidades de costo ,túi(pag)=doost(pag){\displaystyle u_{i}(p)=\mathrm {cost} (p)}si el proyectopag{\displaystyle p}es aprobado por los votantesi{\displaystyle i}ytúi(pag)=0{\displaystyle u_{i}(p)=0}De lo contrario, esto supone que la utilidad de un votante equivale al monto total de dinero gastado en los proyectos que apoya. Esta suposición se usa comúnmente en otros métodos de conteo de votos de aprobación para presupuestos participativos, por ejemplo, en el algoritmo de la mochila , y generalmente resulta en la selección de menos proyectos, pero más costosos.

Bucle principal: votaciones ordenadas

Supongamos que los votantes votan clasificando los proyectos del más al menos preferido. Suponiendo preferencias lexicográficas , se puede utilizar la convención de quetúi(pag){\displaystyle u_{i}(p)}depende de la posición del proyectopag{\displaystyle p}en el votantei{\displaystyle i}clasificación, y esotúi(pag)/túi(pag′)→∞{\displaystyle u_{i}(p)/u_{i}(p')\to \infty }, cuando seai{\displaystyle i}rangospag{\displaystyle p}como más preferido quepag′{\displaystyle p'}En este caso, MES se define de la siguiente manera.

Por cada votantei∈norte{\displaystyle i\in N}dejar≻i{\displaystyle \succ _{i}}denota la clasificación del votantei{\displaystyle i}sobre los proyectos. Por ejemplo,Y≻iincógnita≻iZ{\displaystyle Y\succ _{i}X\succ _{i}Z}significa queY{\displaystyle Y}es el proyecto preferido desde la perspectiva del votantei{\displaystyle i},incógnita{\displaystyle X}es el segundo proyecto preferido por los votantes yZ{\displaystyle Z}es el proyecto menos preferido. En este ejemplo decimos que el proyectoY{\displaystyle Y}está clasificado en la primera posición y escribepagosi(Y)=1{\displaystyle \mathrm {pos} _{i}(Y)=1}, proyectoincógnita{\displaystyle X}está clasificado en la segunda posición (pagosi(incógnita)=2{\displaystyle \mathrm {pos} _{i}(X)=2}), yZ{\displaystyle Z}en la tercera posición (pagosi(Z)=3{\displaystyle \mathrm {pos} _{i}(Z)=3}).

Para cada proyecto aún no seleccionadopag∈PAG{\displaystyle p\in P}decimos quepag{\displaystyle p}esδ{\displaystyle \delta }-asequible si el presupuesto restante de los votantes que se clasificanpag{\displaystyle p}en posiciónδ{\displaystyle \delta }o mejor es mayor o igual quedoost(pag){\displaystyle \mathrm {cost} (p)}:

∑i∈norte:pagosi(pag)≤δbi≥doost(pag).{\displaystyle {\begin{aligned}\sum _{i\in N\colon \mathrm {pos} _{i}(p)\leq \delta }b_{i}\geq \mathrm {cost} (p){\text{.}}\end{aligned}}}

Si existen proyectos asequibles, la regla selecciona el proyecto que aún no ha sido elegido.pag{\displaystyle p}eso esδ{\displaystyle \delta }-asequible para el valor más bajo deδ{\displaystyle \delta }Los presupuestos de los votantes se actualizan en consecuencia. Primero, el costo se distribuye equitativamente entre los votantes que se clasificanpag{\displaystyle p}en la primera posición. Si los presupuestos de estos votantes son insuficientes para cubrir el costo del proyecto, la parte restante del costo se distribuye equitativamente entre los votantes que se clasificanpag{\displaystyle p}en la segunda posición, etc. Formalmente comenzamos conδ:=1{\displaystyle \delta :=1} ydoost:=doost(pag){\displaystyle \mathrm {cost} :=\mathrm {cost} (p)} , y continuar en el bucle:

  1. Si∑i∈norte:pagosi(pag)=δbi≥doost{\displaystyle \textstyle \sum _{i\in N\colon \mathrm {pos} _{i}(p)=\delta }b_{i}\geq \mathrm {cost} }entonces encontramosρ{\displaystyle \rho }de tal manera que∑i∈norte:pagosi(pag)=δmin(ρ,bi)=doost{\displaystyle \textstyle \sum _{i\in N\colon \mathrm {pos} _{i}(p)=\delta }\min(\rho ,b_{i})=\mathrm {cost} }y por cada votantei∈norte{\displaystyle i\in N}conpagosi(pag)=δ{\displaystyle \mathrm {pos} _{i}(p)=\delta }nosotros establecimosbi:=máximo(0,bi−ρ){\displaystyle b_{i}:=\max(0,b_{i}-\rho )}.
  2. De lo contrario, actualizamos el costo:doost:=doost−∑i∈norte:pagosi(pag)=δbi{\displaystyle \mathrm {cost} :=\mathrm {costo} -\textstyle \sum _{i\in N\colon \mathrm {pos} _{i}(p)=\delta }b_{i}} . Cobramos a los votantes: por cada votantei∈norte{\displaystyle i\in N}conpagosi(pag)=δ{\displaystyle \mathrm {pos} _{i}(p)=\delta }nosotros establecimosbi:=0{\displaystyle b_{i}:=0}y pasar a la siguiente posiciónδ:=δ+1{\displaystyle \delta :=\delta +1} .

Métodos de finalización

El método de reparto equitativo puede generar un conjunto de proyectos que no agote todo el presupuesto. Existen diversas maneras de utilizar el presupuesto no gastado:

  1. El método utilitario: los proyectospag{\displaystyle p}se seleccionan en el orden de∑i∈nortetúi(pag)doost(pag){\displaystyle {\frac {\sum _{i\in N}u_{i}(p)}{\mathrm {cost} (p)}}}hasta que no se pueda seleccionar ningún otro proyecto dentro del límite presupuestario.
  2. Ajuste del presupuesto inicial: el presupuesto inicial se puede ajustar al valor más alto posible, lo que hace que el método seleccione proyectos cuyo coste total no supere el presupuesto sin ajustar.

Comparación con otros métodos de votación

En el contexto de las elecciones de comités , el método se compara a menudo con la votación de aprobación proporcional (PAV), ya que ambos métodos son proporcionales (satisfacen el axioma de representación justificada extendida (EJR)). [ 10 ] [ 2 ] La diferencia entre los dos métodos se puede describir de la siguiente manera.

  1. El método de reparto equitativo (MES) se puede calcular en tiempo polinomial, mientras que el algoritmo PAV es NP-difícil de calcular. La variante secuencial de PAV se puede calcular en tiempo polinomial, pero no satisface la condición de representación justificada.
  2. PAV es óptimo de Pareto , pero MES no lo es.
  3. MES es valorable . Esto significa que [ 2 ] es posible asignar un presupuesto fijo a cada votante y dividir el presupuesto de cada votante entre los candidatos que aprueba, de manera que cada candidato electo sea "comprado" por los candidatos que lo aprueban, y ningún candidato no electo pueda ser comprado con el dinero restante de los votantes que lo aprueban. MES puede considerarse una implementación del equilibrio de Lindahl en el modelo discreto, con el supuesto de que los clientes que comparten un artículo deben pagar el mismo precio por el artículo. [ 11 ]
  4. MES se extiende a los presupuestos participativos y a las votaciones cardinales, mientras que PAV no satisface la representación justificada extendida cuando se aplica ni a los presupuestos participativos ni a las votaciones cardinales. [ 3 ]

MES es similar a la regla secuencial de Phragmen . La diferencia radica en que en MES los votantes reciben sus presupuestos por adelantado, mientras que en la regla secuencial de Phragmen los votantes ganan dinero de forma continua a lo largo del tiempo. [ 12 ] [ 13 ] Los métodos se comparan de la siguiente manera:

  1. Ambos métodos son computables en tiempo polinomial, ambos son costosos, [ 2 ] y ambos pueden fallar en la optimalidad de Pareto. [ 1 ]
  2. MES satisface EJR, mientras que la regla secuencial de Phragmen satisface la representación justificada proporcional, una variante más débil de la propiedad. [ 3 ] [ 12 ]
  3. La regla secuencial de Phragmen satisface la monotonicidad del comité, mientras que MES no cumple con esta propiedad. [ 1 ] : Apéndice A
  4. MES se extiende al presupuesto participativo con votaciones cardinales, lo cual no ocurre con la regla secuencial de Phragmen. [ 3 ]

MES con ajuste del presupuesto inicial, PAV y las reglas de votación de Phragmen pueden considerarse extensiones del método D'Hondt al contexto en el que los votantes pueden votar por candidatos individuales en lugar de por partidos políticos. [ 14 ] [ 2 ] MES se extiende además al presupuesto participativo. [ 3 ]

Implementación

A continuación se muestra una implementación en Python del método que se aplica al presupuesto participativo. Para el modelo de elecciones de comités, las reglas se implementan como parte del paquete de Python abcvoting .

importar matemáticasdef method_of_equal_shares ( N , C , cost , u , b ): """Método de partes iguales Argumentos:  N: una lista de votantes.  C: una lista de proyectos (candidatos).  costo: un diccionario que asigna a cada proyecto su costo.  b: el presupuesto total disponible.  u: un diccionario; u[c][i] es el valor que el votante i asigna al candidato c.  Una entrada vacía significa que el valor correspondiente u[c][i] es igual a 0.  """ W = set () total_utility = { c : sum ( u [ c ] . values ​​()) for c in C } supporters = { c : set ([ i for i in N if u [ c ][ i ] > 0 ]) for c in C } budget = { i : b / len ( N ) for i in N } while True : next_candidate = None lowest_rho = float ( "inf" ) for c in C . difference ( W ): if _leq ( cost [ c ], sum ([ budget [ i ] for i in supporters [ c ]])): supporters_sorted = sorted ( supporters [ c ], key = lambda i : budget [ i ] / u [ c ][ i ]) price = cost [ c ] util = total_utility [ c ] for i in supporters_sorted : if _leq ( precio * u [ c ][ i ], presupuesto [ i ] *util ): break precio -= presupuesto [ i ] util -= u [ c ] [ i ] rho = precio / util \ si no math.isclose ( util , 0 ) y no math.isclose ( precio , 0 ) \ si no presupuesto [ partidarios_ordenados [ -1 ] ] / u [ c ] [ partidarios_ordenados [ -1 ] ] si rho < rho_más_bajo : siguiente_candidato = c rho_más_bajo = rho si siguiente_candidato es None : break W.add ( siguiente_candidato ) para i en N : presupuesto [ i ] - = min ( presupuesto [ i ], rho_más_bajo * u [ siguiente_candidato ][ i ] ) return _complete_utilitarian ( N , C , coste , u , b , W ) # una de las posibles completacionesdef _complete_utilitarian ( N , C , coste , u , b , W ) : util = { c : suma ([ u [ c ] [ i ] para i en N ]) para c en C } committee_cost = suma ([ coste [ c ] para c en W ]) while True : next_candidate = None highest_util = float ( "-inf" ) para c en C.difference ( W ) : if _leq ( committee_cost + coste [ c ], b ): if util [ c ] / coste [ c ] > highest_util : next_candidate = c highest_util = util [ c ] / coste [ c ] if next_candidate is None : break W.add ( next_candidate ) committee_cost + = coste [ next_candidate ] return Wdef _leq ( a , b ): return a < b or math . isclose ( a , b )

Apoyo empírico

Fairstein, Benade y Gal comparan MES con métodos de agregación voraz. [ 15 ] Encuentran que la agregación voraz produce resultados altamente sensibles al formato de entrada utilizado y a la fracción de la población que participa. En contraste, MES produce resultados que no son sensibles al tipo de formato de votación utilizado. Esto significa que MES puede usarse con boletas de aprobación, boletas ordinales o boletas cardinales sin mucha diferencia en el resultado. Estos resultados son estables incluso cuando solo entre el 25 y el 50 por ciento de la población participa en la elección.

Fairstein, Meir, Vilenchik y Gal estudian variantes de MES tanto en conjuntos de datos reales como sintéticos. [ 16 ] Encuentran que estas variantes funcionan muy bien en la práctica, tanto con respecto al bienestar social como con respecto a la representación justificada .

Aplicaciones en la vida real

En 2023, MES se estaba utilizando en un programa de presupuestos participativos en la ciudad polaca de Wieliczka . [ 17 ] El programa, conocido como Millón Verde ( Zielony Milion ), tenía como objetivo distribuir 1 millón de zlotys a proyectos ecológicos propuestos por los residentes de la ciudad.

MES también se utilizó en un programa de presupuestos participativos en las ciudades suizas de Aarau en 2023 ( Stadtidee ) [ 18 ] y Winterthur , así como en la ciudad holandesa de Assen . [ 7 ]

Problemas

Papasotiropoulos, Pishbin, Skibski, Skowron y Was presentan varios problemas con MES y con el requisito EJR en general. [ 19 ]

Paradoja de Helenka

La paradoja se descubrió por primera vez en las elecciones de presupuesto participativo celebradas en 2020 en Helenka , Polonia. Se presentaron dos proyectos con costos de $310,000 y $6,000 respectivamente. Participaron 414 votantes, de los cuales 403 aprobaron únicamente el proyecto de $310,000 y los 11 restantes aprobaron solo el de $6,000. El presupuesto total fue de $310,000. El Ministerio de Educación y Ciencia (MES) financió el proyecto de $6,000 y no le quedó presupuesto para financiar el de $310,000, a pesar de que este último satisfaría a muchos más votantes. Además, solo se utilizó una pequeña fracción del presupuesto. De hecho, esta es la única asignación de EJR, por lo que los mismos dos problemas afectarían a cualquier otra regla que garantice EJR.

Servicios públicos de cola

Este problema afecta únicamente a los sistemas de votación electrónica (MES) con utilidades cardinales. Supongamos que hay dos proyectos con el mismo coste 1. Hay 100 votantes. 99 votantes valoran el proyecto x en 100 y el proyecto y en 2; 1 votante valora el proyecto x en 1 y el proyecto y en 2. El presupuesto es 1. En este caso, el MES optaría por financiar el proyecto y, ya que es 0,005-asequible: todos los votantes pagarían 0,005 $ por unidad de utilidad. Por el contrario, el proyecto x solo es 0,01-financiable, ya que el único votante pagaría 0,01 $ por unidad de utilidad. Aunque los 99 votantes pagarían solo 0,0001 $ por unidad de utilidad, el único votante que pagaría 0,01 $ hace que el MES prefiera el proyecto y. En efecto, el MES es igualitario, puesto que maximiza la utilidad mínima de un agente (minimizando el pago máximo de un agente).

Variantes fraccionarias de MES

Algunas variantes recientes de los MES pueden financiar no solo proyectos completos, sino también fracciones de proyectos.

Participaciones fraccionarias iguales

Papasotiropoulos, Pishbin, Skibski, Skowron y Was describen una variante que denominan FrES ( participaciones fraccionarias iguales ). [ 19 ] : Apéndice A La idea es que, en lugar de financiar un proyecto completo, es posible financiar una fracción f <1 de un proyecto, por una fracción f de su costo y por una fracción f de su utilidad. Formalmente, para cualquierρ≥0{\displaystyle \rho \geq 0}y f en (0,1], decimos que el proyectopag{\displaystyle p}es(F,ρ){\displaystyle (f,\rho )}-asequible si

∑i∈nortemin(bi,ρ⋅F⋅túi(pag))=F⋅doost(pag).{\displaystyle {\begin{aligned}\sum _{i\in N}\min \left(b_{i},\rho \cdot f\cdot u_{i}(p)\right)=f\cdot \mathrm {cost} (p){\text{.}}\end{aligned}}}

En cada ronda, FrES selecciona un proyecto p que es(F,ρ){\displaystyle (f,\rho )}-asequible para el valor más bajo deρ{\displaystyle \rho }. Luego financia la mayor fracción posible f de p .

Nótese que, cuando f es suficientemente pequeño, el mínimo en la expresión anterior siempre seráρ⋅F⋅túi(pag){\displaystyle \rho \cdot f\cdot u_{i}(p)}. Por eso,ρ{\displaystyle \rho }siempre será igual acosto(pag)/∑i∈norte,bi>0túi(pag){\displaystyle {\textrm {cost}}(p)/\sum _{i\in N,b_{i}>0}u_{i}(p)}y f siempre será el mínimo entre la fracción aún no financiada de p ymini∈norte,bi>0bi/(ρ⋅túi(pag)){\displaystyle \min _{i\in N,b_{i}>0}b_{i}/(\rho \cdot u_{i}(p))}.

Demuestran que FrES satisface una variante fraccionaria de EJR, que denominan EJR fraccionaria , definida de la siguiente manera. [ 19 ] : Teorema 1 Para cada grupo de proyectos T , función f de los proyectos a [0,1] y función g de los proyectos a [0,], un grupo S de votantes se denomina ( T , f , g )-cohesivo si:

  1. ∑pag∈TF(pag)⋅doost(pag)≤B⋅(|S|/norte){\displaystyle \sum _{p\in T}f(p)\cdot cost(p)\leq B\cdot (|S|/n)}, y
  2. túi(pag)⋅F(pag)≥gramo(pag){\displaystyle u_{i}(p)\cdot f(p)\geq g(p)}para todo p en T e i en S .

El EJR fraccional significa que en cada grupo de votantes cohesionado ( T , f , g ), hay al menos un votante para quien ∑pag∈Ttúi(pag)⋅Wpag≥∑pag∈Tgramo(pag){\displaystyle \sum _{p\in T}u_{i}(p)\cdot W_{p}\geq \sum _{p\in T}g(p)}.

MES generalizado

Lu, Peters, Aziz, Bei y Suksompong presentan una variante de MES que puede manejar tanto proyectos indivisibles (como el MES original) como proyectos heterogéneos divisibles ("pasteles"), como en el reparto de pasteles . [ 20 ] Lo llaman MES generalizado . Funciona de la siguiente manera.

  • Cada porción restante del pastel se divide en intervalos, de manera que cada votante aprueba o desaprueba un intervalo completo. Cada intervalo se considera un único candidato divisible.
  • Se considera un candidato divisible p =[x 0 ,x 1 ].(incógnita,ρ){\displaystyle (x,\rho )}-asequible si
    ∑i∈norte,i aprueba pagmin(bi,ρ⋅(incógnita−incógnita0))=incógnita−incógnita0.{\displaystyle {\begin{aligned}\sum _{i\in N,i{\text{ approves }}p}\min \left(b_{i},\rho \cdot (x-x_{0})\right)=x-x_{0}{\text{.}}\end{aligned}}}
    Esto equivale a la definición utilizada en FrES, donde tanto el coste como la utilidad de cada intervalo para sus aprobadores son iguales a su duración.
  • Se considera un candidato indivisible p.ρ{\displaystyle \rho }-asequible si
    ∑i∈norte,i aprueba pagmin(bi,ρ)=1.{\displaystyle {\begin{aligned}\sum _{i\in N,i{\text{ approves }}p}\min \left(b_{i},\rho \right)=1{\text{.}}\end{aligned}}}
    Esto es equivalente a la definición utilizada en el MES estándar, donde tanto el costo como la utilidad de cada candidato indivisible para sus aprobadores son 1.

En cada ronda, se selecciona un candidato divisible o uno indivisible, dependiendo de cuál sea.ρ{\displaystyle \rho }-asequible con el tamaño más pequeñoρ{\displaystyle \rho }En el primer caso, el candidato elegido es p =[x 0 ,x] para el mayor valor posible de x para el cual aún es(incógnita,ρ){\displaystyle (x,\rho )}-asequible.

El MES generalizado con solo proyectos divisibles es equivalente al FrES con votaciones de aprobación y utilidades de costo. [ 19 ]

Demuestran que el MES generalizado satisface EJR-1 pero no EJR-M. Sin embargo, para instancias de solo divisible ( reparto de pastel ) satisface cake-EJR (EJR para grupos L-cohesivos con L posiblemente no entero; es equivalente a EJR fraccional con votaciones de aprobación y utilidades de costo). Además, el MES generalizado tiene un grado de proporcionalidad de ~ L /2. [ 20 ]

Otras variantes

Bienes sustitutivos

Fairstein, Meir y Gal extienden MES a un entorno en el que algunos proyectos pueden ser bienes sustitutos . [ 21 ]

Partes exactamente iguales

Kraiczy, Robinson y Elkind presentan una variante de MES que denominan participaciones iguales exactas ( EES ). [ 22 ] En EES, todos los partidarios de un proyecto pagan exactamente la misma cantidad por unidad de utilidad, o cero. En otras palabras, los partidarios que no tienen suficiente dinero para contribuir por igual no pagan todo el dinero restante; no pagan nada. Formalmente, decimos que el proyectopag{\displaystyle p}esρ{\displaystyle \rho }-asequible si existe un subconjunto V de votantes que aprueban p , de tal manera que para todo i en V ,ρ⋅túi(pag)≤bi{\displaystyle \rho \cdot u_{i}(p)\leq b_{i}}y

∑i∈Vρ⋅túi(pag)=doost(pag).{\displaystyle {\begin{aligned}\sum _{i\in V}\rho \cdot u_{i}(p)=\mathrm {cost} (p){\text{.}}\end{aligned}}}

En el caso especial de utilidades uniformestúi(pag)=tú(pag){\displaystyle u_{i}(p)=u(p)}para todo i , estas condiciones son equivalentes aρ=costo⁡(pag)|V|tú(pag){\displaystyle \rho ={\frac {\operatorname {cost} (p)}{|V|u(p)}}}yρtú(pag)≤bi{\displaystyle \rho u(p)\leq b_{i}}, eso es,costo⁡(pag)|V|≤bi{\displaystyle {\frac {\operatorname {cost} (p)}{|V|}}\leq b_{i}}.

La principal ventaja de EES sobre MES es que, debido a su simplicidad, el método de finalización para aumentar el presupuesto inicial se puede implementar en tiempo polinomial. [ 22 ] Por lo tanto, es posible utilizar este método de manera eficiente para obtener una alta utilización del presupuesto.

  • Repartos Iguales : un sitio web que explica y analiza el método de repartos iguales en varios idiomas.

Referencias

  1. 1 2 3 Lackner, Martin; Skowron, Piotr (2023). Votación multiganador con preferencias de aprobación . SpringerBriefs in Intelligent Systems. arXiv : 2007.01795 . doi : 10.1007/978-3-031-09016-5 . ISBN 978-3-031-09015-8. S2CID 244921148 . 
  2. 1 2 3 4 5 Peters, Dominik; Skowron, Piotr (2020). «Proporcionalidad y los límites del bienestarismo». Actas de la 21.ª Conferencia ACM sobre Economía y Computación . EC'20. págs. 793–794 . arXiv : 1911.11747 . doi : 10.1145/3391403.3399465 . ISBN  9781450379755. S2CID 208291203 . 
  3. 1 2 3 4 5 6 Peters, Dominik; Pierczyński, Grzegorz; Skowron, Piotr (2021). "Presupuesto participativo proporcional con utilidades aditivas" . Actas de la Conferencia de 2021 sobre Sistemas de Procesamiento de Información Neuronal . NeurIPS'21. arXiv : 2008.13276 .
  4. ↑ Rey, Simon; Maly, Jan (2023-03-08). "La perspectiva de la elección social (computacional) sobre el presupuesto participativo indivisible". arXiv : 2303.00621 [ cs.GT ].
  5. ↑ Freeman, Rupert; Kahng, Anson; Pennock, David (2020). «Proporcionalidad en elecciones basadas en aprobación con un número variable de ganadores» . Actas de la Vigésimo Novena Conferencia Internacional Conjunta sobre Inteligencia Artificial . IJCAI'20. Vol. 1. págs. 132–138 . doi : 10.24963/ijcai.2020/19 . ISBN   978-0-9992411-6-5. S2CID 211052991 . 
  6. ↑ Conitzer, Vincent; Freeman, Rupert; Shah, Nisarg (2017). «Toma de decisiones públicas justas». Actas de la Conferencia ACM de Economía y Computación de 2017. EC'17. págs. 629–646 . arXiv : 1611.04034 . doi : 10.1145/3033274.3085125 . ISBN  9781450345279. S2CID 30188911 . 
  7. 1 2 "EqualShares.Net" .
  8. ↑ Aziz, Haris; Lee, Barton E. (2019). "Presupuesto participativo proporcionalmente representativo con preferencias ordinales". arXiv : 1911.00864 [ cs.GT ].
  9. ↑ Fluschnik, Till; Skowron, Piotr; Triphaus, Mervin; Wilker, Kai (17 de julio de 2019). "Fair Knapsack" . Actas de la Conferencia AAAI sobre Inteligencia Artificial . 33 : 1941–1948 . doi : 10.1609/aaai.v33i01.33011941 . ISSN 2374-3468 . 
  10. ↑ Aziz, Haris; Brill, Markus; Conitzer, Vincent; Elkind, Edith; Freeman, Rupert; Walsh, Toby (2017). "Representación justificada en la votación de comités basada en la aprobación" . Social Choice and Welfare . 48 (2): 461– 485. arXiv : 1407.8269 . doi : 10.1007/s00355-016-1019-3 . S2CID 8564247 . 
  11. ↑ Peters, Dominik; Pierczynski, Grzegorz; Shah, Nisarg; Skowron, Piotr (2021). "Explicaciones basadas en el mercado de las decisiones colectivas" . Actas de la Conferencia AAAI sobre Inteligencia Artificial . AAAI'21. 35 (6): 5656– 5663. doi : 10.1609/aaai.v35i6.16710 . S2CID 222132258 . 
  12. 1 2 Janson, Svante (2018-10-12). "Métodos de elección de Phragmen y Thiele". arXiv : 1611.08826 [ math.HO ].
  13. ↑ Brill, Markus; Freeman, Rupert; Janson, Svante; Lackner, Martin (10 de febrero de 2017). "Métodos de votación de Phragmén y representación justificada" . Actas de la Conferencia AAAI sobre Inteligencia Artificial . 31 (1). arXiv : 2102.12305 . doi : 10.1609/aaai.v31i1.10598 . ISSN 2374-3468 . S2CID 2290202 .  
  14. ↑ Brill, Markus; Laslier, Jean-François; Skowron, Piotr (2018). "Reglas de aprobación de múltiples ganadores como métodos de reparto". Journal of Theoretical Politics . 30 (3): 358– 382. arXiv : 1611.08691 . doi : 10.1177/0951629818775518 . S2CID 10535322 . 
  15. ↑ Fairstein, Roy; Benadè, Gerdus; Gal, Kobi (2023). "Diseño de presupuestos participativos para el mundo real". arXiv : 2302.13316 [ cs.GT ].
  16. ↑ Fairstein, Roy; Meir, Reshef; Vilenchik, Dan; Gal, Kobi (2022). "Bienestar vs. Representación en el Presupuesto Participativo". arXiv : 2201.07546 [ cs.GT ].
  17. ↑ «Zielony Milion - proyecto rusza nowatorski BO w Wieliczce [ WIDEO ] » . Głos24 (en polaco). 2023-03-09 . Consultado el 11 de marzo de 2023 .
  18. ↑ Ciudad de Aarau. "Fase de absorción - Stadtidee Aarau" . stadtidee.aarau.ch . Consultado el 11 de marzo de 2023 .
  19. 1 2 3 4 Papasotiropoulos, Georgios; Pishbin, Seyedeh Zeinab; Skibski, Oskar; Skowron, Piotr; Wąs, Tomasz (2025-07-02). "Método de participaciones iguales con sobregasto limitado" . Actas de la 26.ª Conferencia ACM sobre Economía y Computación . EC '25. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 841–868 . doi : 10.1145/3736252.3742637 . ISBN  979-8-4007-1943-1.
  20. 1 2 Lu, Xinhang; Peters, Jannik; Aziz, Haris; Bei, Xiaohui; Suksompong, Warut (2023-06-26). "Votación basada en aprobación con bienes mixtos" . Actas de la Conferencia AAAI sobre Inteligencia Artificial . 37 (5): 5781– 5788. arXiv : 2211.12647 . doi : 10.1609/aaai.v37i5.25717 . ISSN 2374-3468 . 
  21. ↑ Fairstein, Roy; Meir, Reshef; Gal, Kobi (2021). "Presupuesto participativo proporcional con proyectos sustitutos". arXiv : 2106.05360 [ cs.GT ].
  22. 1 2 Kraiczy, Sonja; Robinson, Isaac; Elkind, Edith (2025-02-17), Streamlining Equal Shares , arXiv : 2502.11797
Obtenido de " https://en.wikipedia.org/w/index.php?title=Method_of_equal_shares&oldid=1363327789 "