TEORIA DA PARTILHA EQUILIBRADA Ana Isabel Cebola Inês Silva Liliana Nogueira Raquel Santos Teoria da partilha equilibrada Caso contínuo Caso discreto Caso misto Caso Contínuo: O objecto em causa pode ser dividido em partes, por exemplo, o tempo, a terra, o dinheiro, a areia, um bolo ou uma pizza. Método do Divisor Selector Método do Divisor Único Método do Selector Único Método do Último a Diminuir Método da Faca Deslizante Estes são métodos de partilha justa. No geral, um problema de divisão justa consiste em n indivíduos, chamados jogadores, a quem nós fazemos corresponder os números 1, 2, …, i, …, n-1, n. Eles devem dividir um conjunto S de ganhos (ou perdas) em n partes distintas S1, S2, …, Si, …, Sn-1, Sn. O objectivo é encontrar subconjuntos Si tais que cada pessoa i considere a sua parte recebida (Si) justa no seu sistema de valores pessoal. É meu! É meu! Hmm… Deve haver uma maneira melhor de dividir um bolo…? Método do Divisor-Selector A técnica para dividir um objecto S de uma maneira justa entre dois jogadores 1 e 2 é “um corta, o outro escolhe”: O jogador 1 divide o conjunto S em duas partes, S1 e S2; O jogador 2 escolhe uma das peças, S1 ou S2; O jogador 1 fica com a parte não escolhida pelo jogador 2. É comum lançar uma moeda ao ar no início para decidir qual dos jogadores será o cortador. Exemplo: A Rita e a Sofia querem dividir um bolo de chocolate e amêndoa. A Rita não tem qualquer preferência entre os sabores enquanto que a Sofia prefere a amêndoa ao chocolate. Rita Sofia Após o lançamento da moeda ao ar, coube à Rita o papel de cortador. A Sofia escolheu a parte que tinha mais amêndoa. Note que… Se fosse a Sofia a cortar, provavelmente, a divisão não seria a mesma. Pode funcionar para potências de base 2. Método do Divisor Único 1ª etapa – DIVISÃO: O divisor corta a pizza em três partes. A divisão é racional apenas se cada parte tiver igual valor para o divisor; 2ª etapa – DECLARAÇÕES: Cada selector declara quais as partes que considera aceitáveis; 3ª etapa – DISTRIBUIÇÃO: Depende da escolha feita na 2ª etapa Caso 1: O selector 1 declara mais do que uma parte aceitável. O selector 2 fica com a parte que escolheu, independentemente da escolha do selector 1. O selector 1 fica com uma das partes que escolheu. O divisor fica com a parte que sobrou. Caso 2: Ambos os selectores declaram uma só parte distinta. Cada selector fica com a parte que escolheu e o divisor fica com a restante. Caso 3: Ambos os selectores declaram a mesma parte. O divisor escolhe uma das partes que os selectores não escolheram. Para dividir, as duas partes que restam, pelos selectores utiliza-se o método do Divisor-Selector. Podemos facilmente estender este método a mais jogadores, se necessário. Método do Selector Único Passo 1: PRIMEIRA DIVISÃO – Os dois divisores cortam o bolo pelo Método do Divisor-Selector. Passo 2: SEGUNDA DIVISÃO – Cada divisor divide agora a sua parte em três porções que considera de igual valor. Passo 3: SELECÇÃO – O selector escolhe uma parte de cada um dos divisores, e cada divisor fica com o que restou da sua parte. Exemplo: O Afonso, a Lara e a Diana querem dividir um bolo de laranja e ananás que custou 27€. O Afonso não tem qualquer preferência de sabores. A Lara detesta ananás. A Diana prefere duas vezes mais ananás do que laranja. Por sorteio vai ser a Diana a selectora e o Afonso vai ser o primeiro a dividir por não ter preferências. A Lara, a outra divisora, escolhe dividir a parte do bolo com mais laranja. Afonso Lara Cada um dos divisores corta a sua parte em três porções que considere igualmente valiosas. A Diana escolhe, retirando uma parte a cada um dos outros dois. Afonso Lara Diana No final da divisão cada um deles obtém uma parte que equivale a pelo menos 1/3 do valor total do bolo. Conclusão: O que é importante é o valor e não o tamanho de cada parcela, para quem a recebe. Método do Último a Diminuir Todos os participantes são simultaneamente divisores e selectores; Estipula-se inicialmente a ordem dos cortadores; Vejamos como este método funciona para três amigos (o Luís, a Sara e a Vera) que querem dividir um bolo de ananás. Em que a ordem de corte é Luís – Sara – Vera. O Luís corta uma parte (sombreada) do bolo que ele considera ser 1/3. Será que a Sara pensa que a parte sombreada é mais do que 1/3? Não Sim A Sara corta a parte sombreada Será que a Vera pensa que a parte de modo a que a fatia sombreada é mais do que 1/3? quadriculada seja, do seu ponto de vista, 1/3. Não Sim O Luís tira a parte sombreada; a Sara corta outra fatia; a Vera A Vera tira a parte escolhe. sombreada; a Sara corta outra fatia; o Luís escolhe. Vera Será que a Vera pensa que a quadriculada é 1/3 ou mais? Luís Luís Sara Vera Sara Sim A Vera pega numa parte quadriculada; a Sara corta a outra em dois bocados; o Luís escolhe. Luís Sara Vera Sara Luís Não A Sara pega numa parte quadriculada; a Vera corta a outra em dois bocados; o Luís escolhe. Luís Vera Sara Vera Luís Método da Faca Deslizante A faca move-se contínua e lentamente sobre a porção do bolo; Qualquer uma das pessoas pode dizer “pára” a qualquer momento; A parte que é então cortada pertence à pessoa que disse “pára”; As outras pessoas repetem o processo com a restante porção de bolo. Caso Discreto: Os objectos não podem ser divididos em partes arbitrariamente pequenas de nenhuma maneira. Partilha justa: Exemplos: casas, carros, cd’s, chocolates,… Uma abordagem neste caso é tentar atribuir valores numéricos, quantias em euros, aos objectos e depois dividir o total em partes justas. A abordagem final pode pois ser alcançada atribuindo os valores numéricos ou os próprios objectos . Divisão proporcional: Exemplos: distribuição de lugares numa assembleia Distribuição de lugares em função do número de pessoas de cada estado. Método das licitações secretas Método dos marcadores Partilha justa Método de Hamilton Método de Jefferson Método de Adams Método de Webster-Willcox Método de Huntington-Hill Divisão proporcional SERÁ ESTA A MELHOR FORMA DE DIVIDIR BENS? Método das licitações secretas 1ª etapa: LICITAÇÃO – Cada herdeiro atribui um valor monetário a cada bem da herança, colocando o valor da sua licitação dentro de um envelope fechado. Ana Raquel Inês Liliana € 120 000 € 200 000 € 140 000 € 180 000 € 60 000 € 40 000 € 90 000 € 50 000 € 30 000 € 24 000 € 20 000 € 20 000 2ª etapa: DISTRIBUIÇÃO – Cada bem é entregue ao herdeiro que lhe atribuiu maior valor monetário. Se o valor atribuído a cada bem for superior/inferior à divisão justa, então o herdeiro terá de pagar/receber a diferença. Soma das ofertas Porção justa Ana Raquel Inês Liliana € 120 000 € 200 000 € 140 000 € 180 000 € 60 000 € 40 000 € 90 000 € 50 000 € 30 000 € 24 000 € 20 000 € 20 000 € 210 000 € 264 000 € 250 000 € 250 000 € 52 500 € 66 000 € 62 500 € 62 500 Objecto Soma / nº atribuído herdeiros Diferença Porção justa - oferta € 22 500 €(-) 134 000 € (-) 27 500 € 62 500 3ª etapa: EXCESSO – Existe quase sempre dinheiro em excesso, que deve ser dividido igualmente pelos herdeiros. Ana Raquel Inês Liliana € 120 000 € 200 000 € 140 000 € 180 000 € 60 000 € 40 000 € 90 000 € 50 000 € 30 000 € 24 000 € 20 000 € 20 000 Soma das ofertas € 210 000 € 264 000 € 250 000 € 250 000 Porção justa € 52 500 € 66 000 € 62 500 € 62 500 € 22 500 € (-) 134 000 € (-) 27 500 € 62 500 Objecto atribuído Diferença € 76 500 Excesso total Divisão do excesso € 19 125 € 19 125 € 19 125 + € 41 625 - € 114 875 - € 8 375 Distribuição final € 19 125 € 81 625 Circunstâncias necessárias Cada herdeiro deve ter dinheiro suficiente para as suas licitações. Cada herdeiro deve aceitar dinheiro como um substituto de qualquer bem. É obrigatório que cada herdeiro, antes de licitar, não tenha nenhuma informação útil sobre as licitações dos outros herdeiros. Método dos Marcadores Exemplo: Distribuição de 12 cd’s (numerados de 1 a 12) por três amigos (Francisco, Gonçalo e Pedro). 1ª etapa: Colocam-se os cd’s numerados, aleatoriamente, em linha; 1 2 F1 3 4 5 6 7 8 9 10 11 F2 2ª etapa: colocam-se os marcadores; 12 3ª etapa: Constrói-se uma tabela para colocar os segmentos efectuados por cada amigo; Seg 1 Seg 2 Seg 3 Francisco 1 2 -3 4 -12 Gonçalo 1-5 1-3 Pedro 1 2 F1 3 4 F2 5 6 - 10 4-9 6 7 11 - 12 10 - 12 8 9 10 11 12 4ª etapa: Observa-se a linha da esquerda para a direita até se encontrar o primeiro marcador. 1 2 F1 3 4 5 6 7 8 9 10 11 F2 Neste exemplo, é o marcador do Francisco. 5ª etapa: Este primeiro segmento é entregue ao Francisco e são retirados todos os seus marcadores; 12 6ª etapa: Procura-se agora o primeiro marcador do segundo segmento. 1 2 F1 3 4 5 6 7 8 9 10 11 12 F2 No nosso exemplo é o marcador do Pedro; 1 7ª etapa: Este segmento é entregue ao Pedro e retiram-se os seus marcadores. F 2 G 2-3 6-10 P 4-9 3 8ª etapa: Encontra-se ainda um marcador pertencente ao terceiro segmento. 1 2 3 4 5 6 7 8 9 10 11 12 F2 Este pertence ao Gonçalo pois é o único que resta. É-lhe entregue então o último segmento; 1 2 3 F 4-12 G 11-12 10-12 P Todos os amigos receberam cd’s. Contudo ainda sobram alguns. 2 3 10 Francisco Gonçalo Pedro Como distribui-los?... Estipula-se aleatoriamente uma ordem entre os amigos. Cada um vai escolhendo um cd até acabarem. Neste caso a ordem será Gonçalo – Francisco – Pedro Em Resumo: 1 2 3 4 5 6 7 8 9 10 11 12 Circunstâncias necessárias: Deve haver um número de cd’s superior ao número de amigos; Cada amigo deve poder dividir os cd’s em segmentos de valor igual. Definições necessárias: Quociente eleitoral = Quota = Pop. Total Nº lugares Pop. de cada estado Quociente eleitoral Quota mínima é a aproximação da quota por defeito. Quota máxima é a aproximação da quota por excesso. Regra da quota: cada estado deve receber a sua quota mínima ou a sua quota máxima na distribuição final. Método de Hamilton: 1º passo: Calcular a quota de cada círculo eleitoral; 2º passo: atribuir a cada círculo um número de lugares igual à parte inteira da quota (quota mínima); 3º passo: atribuir os lugares sobrantes, um a um, aos círculos com quota com maior parte decimal. Exemplo: Encontro de estudantes de Matemática Universidades Nº Estud. Lisboa 9230 Coimbra 8231 Beira Interior 139 Total 17600 Nº lugares 176 Q. eleitoral 100 Quota Quota mínima P.Decimal Lugar Nº Rep. 92,3 82,31 1,39 92 82 1 175 0,3 0,31 0,39 1º 92 82 2 176 Total Nº lugares O quociente eleitoral significa que uma universidade levará ao encontro um representante por cada 100 estudantes. Nº estudantes Quota= Quociente eleitoral A quota é o número exacto de representantes que cada faculdade deveria ter no encontro. Quociente eleitoral= Quota mínima é a aproximação da quota por defeito. Parte decimal = quota – quota mínima I ENCONTRO DE ESTUDANTES DE MATEMÁTICA De facto, para uma só aplicação, este método é provavelmente o mais simples de usar. A única confusão que pode ocorrer é quando existem duas partes decimais iguais porque dificulta a atribuição de lugares. Neste caso, vai ser a universidade com quota mínima mais elevada que irá receber o lugar extra. Pode surgir alguma controvérsia se este método for aplicado repetidamente durante um certo período de tempo. Falhas do Método de Hamilton Paradoxo da População Paradoxo dos Novos Estados Paradoxo de Alabama Paradoxo de Alabama: Aumento no tamanho do corpo legislativo Perda de um representante de um estado individual Suponhamos que há um aumento do número de lugares de representantes no encontro de 176 para 177. É necessário fazer uma nova distribuição dos lugares. Universidade Nº Estud. Lisboa 9230 Coimbra 8231 Beira Interior 139 Total 17600 Nº lugares 177 Q. eleitoral 99.44 Quota Quota mínima P.Decimal Lugar Nº Rep. 92.82 92 0.82 1º 93 83 82.77 82 0.77 2º 1.40 1 1 0.40 175 177 Tinha 2 rep. Paradoxo da População: Um estado X pode perder lugares para um estado Y mesmo que a população de X cresça muito mais do que a de Y Exemplo: Núcleo de estudantes de Matemática da Universidade de Évora Anos 1º 2º 3º 4º Total Nº lugares Q. eleitoral Nº Estud. 400 90 225 200 915 25 Quota Quota mínima P.Decimal Lugar Nº Rep. 10.929 2.459 6.148 5.464 10 2 6 5 0.929 0.459 0.148 0.464 1º 2º 23 11 2 6 6 25 36.6 Transferiram-se para esta universidade 20 alunos Anos 1º 2º 3º 4º Total Nº lugares Q. eleitoral Nº Estud. 400 99 225 211 935 25 37.4 Quota Quota mínima P.Decimal Lugar Nº Rep. 10.695 2.647 6.106 5.642 10 2 6 5 0.695 0.647 0.106 0.642 23 Ganhou mais estudantes, mas perdeu um rep. 1º 2º 11 3 6 5 25 Paradoxo dos novos estados O aparecimento de um novo estado e um aumento do número de lugares pode afectar a divisão de lugares dos outros estados. Contabilizando-se o ano de estágio… Tinha 2 rep. Anos 1º 2º 3º 4º 5º Total Nº lugares Q. eleitoral Nº Estud. 400 90 225 200 120 1035 28 36.964 Quota Quota mínima P.Decimal Lugar Nº Rep. 10.821 2.435 6.087 5.411 3.246 10 2 6 5 3 26 0.821 0.435 0.087 0.411 0.246 Tinha 6 rep. 1º 2º 11 3 6 5 3 28 A existência destes três paradoxos não significa que o método de Hamilton seja inválido ou incorrecto. Ao utilizar o método de Hamilton, cada estado recebe ou a sua quota mínima ou a sua quota máxima na distribuição final. Isto é, satisfaz a REGRA DA QUOTA . A maior fragilidade deste método surge no 3º passo. Seria bom eliminá-lo, modificando a quota, para que não haja lugares sobrantes. Assim, surge um novo método… Método de Jefferson 1º passo: encontrar um quociente eleitoral (modificado) de modo que as quotas modificadas arredondadas, às unidades, por defeito (quotas mínimas modificadas) somem o número exacto de lugares; 2º Passo: atribuir a cada círculo a sua quota mínima modificada. Q. mod= 1ª tentativa: Universidade Lisboa Coimbra Beira Interior Total Nº lugares Q. eleitoral Q. modificado Nº Estud. 9230 8231 139 17600 176 Nº estudantes Q. modificado Quota modificada Quota mín. mod. 91.84 81.90 1.38 173 100 100.5 Soma inferior TENTATIVA FALHADA!!! 91 81 1 2ª tentativa: Universidade Lisboa Coimbra Beira Interior Total Nº lugares Q. eleitoral Q. modificado Nº Estud. 9230 8231 139 17600 176 Quota modificada Quota mín. mod. 93.23 83.14 1.40 93 83 1 177 100 99 Soma superior OUTRA TENTATIVA FALHADA!!! 3ª tentativa: Universidade Lisboa Coimbra Beira Interior Total Nº lugares Q. eleitoral Q. modificado Nº Estud. 9230 8231 139 17600 176 Quota modificada Quota mín. mod. 93.04 82.97 1.40 93 82 1 176 100 99.2 Consegui!!! Será este quociente modificado único? Universidade Lisboa Coimbra Beira Interior Total Nº lugares Q. eleitoral Q. modificado Nº Estud. 9230 8231 139 17600 176 Quota modificada 93.06 82.99 1.40 Quota mín. mod. 93 82 1 176 100 99.18 NÃO!!! Outro modo de resolver sem ser por tentativas Este é o valor mais alto Universidade Lisboa Coimbra B. Interior Total Nº lugares Q. eleitoral Nº Est. Q Q mín. Q max. Q mín+2 Q. mod.1 Q. mod.2 Lugar Nº Rep. 9230 92.3 99.247 98.191 1º 93 93 94 92 8231 82.31 82 83 84 99.169 97.988 82 139 1.39 1 2 3 69.5 46.333 1 17600 176 175 176 100 Quota máxima = Quota mínima + 1 Nº Estudantes Quota modificada 1 = Quota mínima Nº Estudantes Quota modificada 2 = Quota máxima Encontramos a perfeição? Este método tem uma falha. Por vezes, viola a regra da quota. O problema está na análise simultânea das duas colunas das quotas modificadas. Exemplo: Simpósio de estudantes de Arquitectura da Universidade de Coimbra Anos 1º 2º 3º 4º 5º 6º Total Nº lugares Q. eleitoral 1º lugar 2º lugar Nº Est. Q Q mín. Q max. Q mín+2 Q. mod.1 Q. mod.2 Lugar Nº Rep. 328 39.36 39 40 8.200 8.000 39 41 1388 166.56 166 168 8.311 8.262 1º 2º 168 167 30 3.6 7.500 3 3 5 6.000 4 420 50.4 50 51 52 8.235 8.077 50 136 16.32 16 17 18 8.000 16 7.556 198 23.76 23 24 24 25 8.250 7.920 3º 2500 300 297 300 3º lugar 8.333 Falta distribuir 3 lugares Neste exemplo é violada a REGRA DA QUOTA Método de Adams 1º Passo: encontrar um quociente eleitoral (modificado) de modo que as quotas modificadas arredondadas, às unidades, por excesso (quotas máximas modificadas) somem o número exacto de lugares; 2ºPasso: atribuir a cada círculo a sua quota máxima modificada. 1ª tentativa: Universidade Lisboa Coimbra Beira Interior Total Nº lugares Q. eleitoral Q. modificado Nº Estud. 9230 8231 139 17600 176 Quota modificada Quota max. mod 88.75 79.14 1.34 171 100 104 Soma inferior TENTATIVA FALHADA!!! 89 80 2 2ª tentativa: Universidade Lisboa Coimbra Beira Interior Total Nº lugares Q. eleitoral Q. modificado Nº Estud. 9230 8231 139 17600 176 Quota modificada Quota max. mod 93.23 83.14 1.4 94 84 2 180 100 99 Soma superior OUTRA TENTATIVA FALHADA!!! 3ª tentativa: Universidade Lisboa Coimbra Beira Interior Total Nº lugares Q. eleitoral Q. modificado Nº Estud. 9230 8231 139 17600 176 Quota modificada Quota max. mod 91.84 81.9 1.38 92 82 2 176 100 100.5 Consegui!!! No nosso exemplo, a regra da quota não foi violada. No entanto, este método viola esta regra. O problema começa na escolha do quociente modificado. Contudo, os exemplos são escassos pois este método nunca foi utilizado na prática. Método de Webster-Willcox 1º Passo: encontrar um quociente eleitoral (modificado) de modo que as quotas modificadas arredondadas, às unidades, de modo convencional somem o número exacto de lugares; 2º Passo: atribuir a cada círculo a sua quota arredondada de modo convencional. 1ª tentativa: Universidade Lisboa Coimbra Beira Interior Total Nº lugares Q. eleitoral Q. modificado Nº Estud. 9230 8231 139 17600 176 Quota modificada 91.39 81.50 1.38 91 82 1 174 100 101 Soma inferior TENTATIVA FALHADA!!! Q. mod. arredondada 2ª tentativa: Universidade Lisboa Coimbra Beira Interior Total Nº lugares Q. eleitoral Q. modificado Nº Estud. 9230 8231 139 17600 176 Quota modificada Q. mod. arredondada 92.76 82.72 1.40 93 83 1 177 100 99.5 Soma superior OUTRA TENTATIVA FALHADA!!! 3ª tentativa: Universidade Lisboa Coimbra Beira Interior Total Nº lugares Q. eleitoral Q. modificado Nº Estud. 9230 8231 139 17600 176 Quota modificada 92.50 82.49 1.39 Q. mod. arredondada 93 82 1 176 100 99.78 Consegui!!! Será este o método ideal? O problema que surge neste método é mais teórico do que prático, já que as violações da regra da quota são consideradas raras. Do ponto de vista prático este é considerado por muitos especialistas o melhor de todos os métodos de partilha. Método de Huntington-Hill REGRA DE ARREDONDAMETO DE HUTINGTON-HILL Se a quota está entre L e L+1, o ponto de viragem é H = Lx(L+1) . Se a quota é inferior a H, arredonda-se por defeito, caso contrário, arredonda-se por excesso. 1º Passo: encontrar um quociente modificado tal que quando cada quota modificada é arredondada pela regra de Huntington-Hill, o total dos arredondamentos é exactamente o número de lugares a distribuir; 2º Passo: Atribuir a cada círculo a sua quota modificada arredondada pela regra de Huntington-Hill. 1ª tentativa: Universidade Lisboa Coimbra Beira Interior Total Nº lugares Q. eleitoral Q. modificado H = Lx(L+1) L = 88 Nº Estud. Q. modificada Ponto Viragem Q. mod. arredondada 9230 88.75 88.50 89 8231 79.50 79.14 79 139 1.41 1.34 1 17600 176 169 100 104 Soma inferior TENTATIVA FALHADA!!! 2ª tentativa: Universidade Lisboa Coimbra Beira Interior Total Nº lugares Q. eleitoral Q. modificado Nº Estud. Q. modificada Ponto Viragem Q. mod. arredondada 9230 92.76 92.50 93 8231 82.72 83 82.50 139 1 1.40 1.41 17600 176 177 100 99.5 Soma superior OUTRA TENTATIVA FALHADA!!! 3ª tentativa: Universidade Lisboa Coimbra Beira Interior Total Nº lugares Q. eleitoral Q. modificado Nº Estud. Q. modificada Ponto Viragem Q. mod. arredondada 9230 92.50 93 92.50 8231 82.50 82 82.49 1 139 1.39 1.41 17600 176 176 100 99.78 Consegui!!! Este exemplo não viola a regra da quota. Teorema da impossibilidade de Balinski e Young Qualquer método de partilha que não viole a regra da quota produz paradoxos e qualquer método de partilha que não produza paradoxos viola a regra da quota. Favorece universidades pequenas Viola a regra da quota Universidade Nº Estud. Lisboa 9230 Coimbra 8231 Beira Interior 139 Total 17600 Nº lugares 176 Q. eleitoral 100 Favorece universidades grandes Quota Hamilton Jefferson Adams Webster Huntington 92 93 92 93 92.30 93 82 82.31 82 82 82 82 1.39 2 1 2 1 1 176 176 176 176 Possui paradoxos 176 Caso Misto: É um combinação entre o caso contínuo e discreto, ou seja, existem objectos divisíveis e indivisíveis para distribuir. Como, por exemplo, no caso de uma herança em que haja para dividir uma casa, um piano e um terreno. Aplicação no secundário: No curso geral de Ciências Sociais e Humanas e no curso tecnológico de Ordenamento de Território, vai-se introduzir no próximo ano lectivo uma nova disciplina designada por Matemática Aplicada às Ciências Sociais (MACS). É no capítulo dos Métodos de Apoio à Decisão do 10º ano que se estuda a Teoria da Partilha Equilibrada. Ainda não existem manuais para esta nova disciplina. “Justiça” depende de quem a define…