Problema de secretária - Secretary problem

Gráficos de probabilidades de obter o melhor candidato (círculos vermelhos) a partir de n aplicações e k / n (cruzes azuis), onde k é o tamanho da amostra

O problema da secretária demonstra um cenário envolvendo a teoria de parada ideal que é extensivamente estudada nos campos de probabilidade aplicada , estatística e teoria da decisão . É também conhecido como o problema do casamento , o problema do dote do sultão, o problema do pretendente exigente , o jogo do googol e o problema da melhor escolha .

A forma básica do problema é a seguinte: imagine um administrador que deseja contratar a melhor secretária dentre as candidatas classificáveis ​​para uma posição. Os candidatos são entrevistados um a um em ordem aleatória. A decisão sobre cada candidato em particular deve ser tomada imediatamente após a entrevista. Uma vez rejeitado, um candidato não pode ser retirado. Durante a entrevista, o administrador obtém informações suficientes para classificar o candidato entre todos os candidatos entrevistados até o momento, mas não tem conhecimento da qualidade de candidatos ainda não vistos. A questão é sobre a estratégia ótima ( regra de parada ) para maximizar a probabilidade de selecionar o melhor candidato. Se a decisão pode ser adiada para o final, isso pode ser resolvido pelo algoritmo de seleção máxima simples de rastrear o máximo em execução (e quem o atingiu) e selecionar o máximo geral no final. A dificuldade é que a decisão deve ser tomada imediatamente. ${\ displaystyle n}$

A prova mais curta e rigorosa conhecida até agora é fornecida pelo algoritmo de probabilidades . Isso implica que a probabilidade ótima de vitória é sempre pelo menos (onde e é a base do logaritmo natural ), e que o último se mantém mesmo em uma generalidade muito maior. A regra de parada ideal prescreve sempre rejeitar os primeiros candidatos entrevistados e, em seguida, parar no primeiro candidato que é melhor do que todos os entrevistados até agora (ou continuar até o último candidato se isso nunca ocorrer). Às vezes, essa estratégia é chamada de regra de parada, porque a probabilidade de parar no melhor candidato com esta estratégia já é para valores moderados de . Uma razão pela qual o problema da secretária tem recebido tanta atenção é que a política ótima para o problema (a regra de parada) é simples e seleciona o melhor candidato em cerca de 37% das vezes, independentemente de haver 100 ou 100 milhões de candidatos. ${\ displaystyle 1 / e}$${\ displaystyle \ sim n / e}$${\ displaystyle 1 / e}$${\ displaystyle 1 / e}$${\ displaystyle n}$

Formulação

Embora haja muitas variações, o problema básico pode ser expresso da seguinte forma:

• Só há uma posição a ser preenchida.
• Existem n candidatos para a posição e o valor de n é conhecido.
• Os candidatos, se vistos em conjunto, podem ser classificados do melhor ao pior de forma inequívoca.
• Os candidatos são entrevistados sequencialmente em ordem aleatória, com cada ordem sendo igualmente provável.
• Imediatamente após a entrevista, o candidato entrevistado é aceito ou rejeitado e a decisão é irrevogável.
• A decisão de aceitar ou rejeitar um candidato pode ser baseada apenas nas classificações relativas dos candidatos entrevistados até o momento.
• O objetivo da solução geral é ter a maior probabilidade de selecionar o melhor candidato de todo o grupo. Isso é o mesmo que maximizar o retorno esperado, com o retorno definido como um para o melhor candidato e zero caso contrário.

Um candidato é definido como um candidato que, ao ser entrevistado, é melhor do que todos os candidatos entrevistados anteriormente. Pular é usado para significar "rejeitar imediatamente após a entrevista". Como o objetivo do problema é selecionar o melhor candidato, apenas os candidatos serão considerados para aceitação. O "candidato" neste contexto corresponde ao conceito de registro em permutação.

Derivando a política ideal

A política ideal para o problema é uma regra de parada . Debaixo disto, o entrevistador rejeita o primeiro r  - 1 recorrentes (deixar requerente M ser o melhor candidato entre estes r  - 1 requerentes), e, em seguida, selecciona o primeiro requerente subsequente que é melhor do que a requerente M . Pode-se mostrar que a estratégia ótima está nesta classe de estratégias. (Observe que nunca devemos escolher um candidato que não seja o melhor que vimos até agora, uma vez que ele não pode ser o melhor candidato geral.) Para um corte arbitrário r , a probabilidade de que o melhor candidato seja selecionado é

${\ displaystyle {\ begin {alinhados} P (r) & = \ sum _ {i = 1} ^ {n} P \ left ({\ text {candidate}} i {\ text {is selected}} \ cap { \ text {requerente}} i {\ text {é o melhor}} \ direita) \\ & = \ sum _ {i = 1} ^ {n} P \ esquerda ({\ texto {requerente}} i {\ texto {é selecionado}} | {\ text {candidate}} i {\ text {is the best}} \ right) \ cdot P \ left ({\ text {candidate}} i {\ text {is the best}} \ direita) \\ & = \ left [\ sum _ {i = 1} ^ {r-1} 0+ \ sum _ {i = r} ^ {n} P \ left (\ left. {\ begin {array} {l} {\ text {o melhor do primeiro}} i-1 {\ text {candidatos}} \\ {\ text {está no primeiro}} r-1 {\ text {candidatos}} \ end {array }} \ right | {\ text {candidate}} i {\ text {é o melhor}} \ right) \ right] \ cdot {\ frac {1} {n}} \\ & = \ left [\ sum _ {i = r} ^ {n} {\ frac {r-1} {i-1}} \ direita] \ cdot {\ frac {1} {n}} \\ & = {\ frac {r-1} {n}} \ sum _ {i = r} ^ {n} {\ frac {1} {i-1}}. \ end {alinhado}}}$

A soma não é definida para r = 1, mas, neste caso, a única política viável é selecionar o primeiro candidato e, portanto, P (1) = 1 / n . Essa soma é obtida observando-se que, se o candidato i for o melhor candidato, ele será selecionado se, e somente se, o melhor candidato entre os primeiros i  - 1 candidatos estiver entre os primeiros r  - 1 candidatos rejeitados. Deixando n tender ao infinito, escrevendo como o limite de (r-1) / n , usando t para (i-1) / n e dt para 1 / n , a soma pode ser aproximada pela integral ${\ displaystyle x}$

${\ displaystyle P (x) = x \ int _ {x} ^ {1} {\ frac {1} {t}} \, dt = -x \ ln (x) \ ;.}$

Tomando a derivada de P ( x ) em relação a , definindo-a como 0 e resolvendo para x , descobrimos que o x ótimo é igual a 1 / e . Assim, o corte ótimo tende a n / e conforme n aumenta, e o melhor candidato é selecionado com probabilidade 1 / e . ${\ displaystyle x}$

Para pequenos valores de n , o r ótimo também pode ser obtido por métodos de programação dinâmica padrão . Os limites ótimos r e a probabilidade de selecionar a melhor alternativa P para vários valores de n são mostrados na tabela a seguir.

${\ displaystyle n}$	1	2	3	4	5	6	7	8	9
${\ displaystyle r}$	1	1	2	2	3	3	3	4	4
${\ displaystyle P}$	1,000	0,500	0,500	0,458	0,433	0,428	0,414	0,410	0,406

A probabilidade de selecionar o melhor candidato no problema clássico da secretária converge para . ${\ displaystyle 1 / e \ aproximadamente 0,368}$

Solução alternativa

Este problema e várias modificações podem ser resolvidos (incluindo a prova de otimalidade) de forma direta pelo algoritmo de odds , que também possui outras aplicações. As modificações para o problema da secretária que podem ser resolvidos por este algoritmo incluem disponibilidades aleatórias de candidatos, hipóteses mais gerais para candidatos de interesse do tomador de decisão, entrevistas em grupo para candidatos, bem como certos modelos para um número aleatório de candidatos.

Limitações

A solução do problema da secretária só tem sentido se for justificada a suposição de que os candidatos não têm conhecimento da estratégia de decisão empregada, porque os primeiros candidatos não têm nenhuma chance e podem não aparecer de outra forma.

Uma desvantagem importante para as aplicações da solução do problema clássico da secretária é que o número de candidatos deve ser conhecido com antecedência, o que raramente é o caso. Uma forma de contornar esse problema é supor que o número de candidatos seja uma variável aleatória com uma distribuição conhecida de (Presman e Sonin, 1972). Para este modelo, a solução ótima é em geral muito mais difícil. Além disso, a probabilidade de sucesso ideal agora não é mais em torno de 1 / e, mas normalmente mais baixa. Isso pode ser entendido no contexto de haver um "preço" a pagar por não se saber o número de candidatos. Porém, neste modelo o preço é alto. Dependendo da escolha da distribuição de , a probabilidade ótima de vitória pode se aproximar de zero. A busca por maneiras de lidar com esse novo problema levou a um novo modelo que gerou a chamada 1 / e-law da melhor escolha. ${\ displaystyle n}$${\ displaystyle N}$${\ displaystyle P (N = k) _ {k = 1,2, \ cdots}}$${\ displaystyle N}$

1 / e-law da melhor escolha

A essência do modelo é baseada na ideia de que a vida é sequencial e que os problemas do mundo real se colocam em tempo real. Além disso, é mais fácil estimar os tempos em que eventos específicos (chegadas de candidatos) devem ocorrer com mais frequência (se ocorrerem) do que estimar a distribuição do número de eventos específicos que ocorrerão. Essa ideia levou à seguinte abordagem, a chamada abordagem unificada (1984):

O modelo é definido da seguinte forma: Um candidato deve ser selecionado em algum intervalo de tempo de um número desconhecido de candidatos classificáveis. O objetivo é maximizar a probabilidade de selecionar apenas os melhores sob a hipótese de que todas as ordens de chegada de diferentes classificações são igualmente prováveis. Suponhamos que todos os requerentes têm a mesma, mas independentes uns dos outros, a densidade chegada tempo em e deixe denotam a função de distribuição do tempo de chegada correspondente, que é ${\ displaystyle [0, T]}$${\ displaystyle N}$${\ displaystyle f}$${\ displaystyle [0, T]}$${\ displaystyle F}$

${\ displaystyle F (t) = \ int _ {0} ^ {t} f (s) ds}$, .${\ displaystyle \, 0 \ leq t \ leq T}$

Seja tal que Considere a estratégia de esperar e observar todos os candidatos até o momento e então selecionar, se possível, o primeiro candidato após o tempo que é melhor do que todos os anteriores. Então, essa estratégia, chamada 1 / e-estratégia , tem as seguintes propriedades: ${\ displaystyle \ tau}$${\ displaystyle F (\ tau) = 1 / e.}$${\ displaystyle \ tau}$${\ displaystyle \ tau}$

A estratégia 1 / e

(i) rende para todas as probabilidades de sucesso de pelo menos 1 / e,${\ displaystyle N}$

(ii) é a estratégia única que garante este limite de probabilidade de sucesso inferior 1 / e, e o limite é ótimo,

(iii) seleciona, se houver pelo menos um candidato, nenhum com probabilidade exatamente 1 / e.

O 1 / e-law, provado em 1984 por F. Thomas Bruss , foi uma surpresa. O motivo era que um valor de cerca de 1 / e havia sido considerado antes como estando fora de alcance em um modelo para desconhecido , enquanto esse valor 1 / e agora era alcançado como um limite inferior para a probabilidade de sucesso, e isso em um modelo com indiscutivelmente hipóteses muito mais fracas (ver, por exemplo, Matemática. Revisões 85: m). ${\ displaystyle N}$

O 1 / e-law às vezes é confundido com a solução para o problema clássico da secretária descrito acima por causa do papel semelhante do número 1 / e. No entanto, no 1 / e-law, essa função é mais geral. O resultado também é mais forte, uma vez que vale para um número desconhecido de candidatos e porque o modelo baseado em uma distribuição de tempo de chegada F é mais tratável para aplicações.

O jogo do googol

De acordo com Ferguson ( 1989 ), o problema da secretária apareceu pela primeira vez na mídia impressa quando foi apresentado por Martin Gardner em sua coluna de Jogos Matemáticos de fevereiro de 1960 na Scientific American . Aqui está como Gardner 1966 formulou: "Peça a alguém para pegar quantas tiras de papel quiser e em cada tira escreva um número positivo diferente. Os números podem variar de pequenas frações de 1 a um número do tamanho de um googol ( 1 seguido de cem zeros) ou ainda maior. Essas tiras são viradas para baixo e embaralhadas sobre a mesa. Um de cada vez, você vira as tiras para cima. O objetivo é parar de girar quando chegar ao número que você acha que é o maior da série. Você não pode voltar e pegar um papel que já foi virado. Se você virar todos os tacos, então é claro que você deve pegar o último que foi virado. " erro harvnb: sem alvo: CITEREFGardner1966 ( ajuda )

No artigo "Quem resolveu o problema do secretário?" Ferguson ( 1989 ) apontou que o problema da secretária permaneceu sem solução, como foi afirmado por M. Gardner, ou seja, um jogo de soma zero para duas pessoas com dois jogadores antagônicos. Neste jogo, Alice, a jogadora bem informada, escreve números secretamente distintos nos cartões. Bob, o jogador que pára, observa os valores reais e pode parar de virar as cartas quando quiser, ganhando se a última carta virada tiver o número máximo geral. A diferença com o problema básico da secretária é que Bob observa os valores reais escritos nos cartões, que ele pode usar em seus procedimentos de decisão. Os números nos cartões são análogos às qualidades numéricas dos candidatos em algumas versões do problema da secretária. A distribuição de probabilidade conjunta dos números está sob o controle de Alice. ${\ displaystyle n}$

Bob deseja adivinhar o número máximo com a maior probabilidade possível, enquanto o objetivo de Alice é manter essa probabilidade o mais baixo possível. Não é ideal para Alice amostrar os números independentemente de alguma distribuição fixa, e ela pode jogar melhor escolhendo números aleatórios de alguma forma dependente. Pois Alice não tem estratégia minimax , o que está intimamente relacionado a um paradoxo de T. Cover . Mas para o jogo há uma solução: Alice pode escolher números aleatórios (que são variáveis ​​aleatórias dependentes) de tal forma que Bob não pode jogar melhor do que usar a estratégia de parada clássica baseada nas classificações relativas ( Gnedin 1994 ). ${\ displaystyle n = 2}$${\ displaystyle n> 2}$

Desempenho heurístico

O restante do artigo trata novamente do problema da secretária para um número conhecido de candidatos.

Probabilidades de sucesso esperadas para três heurísticas.

Stein, Seale & Rapoport 2003 derivaram as probabilidades de sucesso esperadas para várias heurísticas psicologicamente plausíveis que podem ser empregadas no problema da secretária. As heurísticas que examinaram foram:

• A regra de corte (CR): Não aceite qualquer um dos primeiros y candidatos; depois disso, selecione o primeiro candidato encontrado (ou seja, um candidato com classificação relativa 1). Esta regra tem como caso especial a política ótima para o problema clássico da secretária para o qual y  =  r .
• Regra de contagem de candidatos (CCR): Selecione o y- ésimo candidato encontrado. Observe que esta regra não necessariamente ignora nenhum candidato; considera apenas quantos candidatos foram observados, não o quão profundo o tomador de decisão está na sequência de candidatos.
• Regra de não candidatos sucessivos (SNCR): Selecione o primeiro candidato encontrado após observar y não candidatos (ou seja, candidatos com classificação relativa> 1).

Cada heurística possui um único parâmetro y . A figura (mostrada à direita) exibe as probabilidades de sucesso esperadas para cada heurística como uma função de y para problemas com n  = 80.

Variante cardinal de recompensa

Encontrar o melhor candidato pode parecer um objetivo bastante estrito. Pode-se imaginar que o entrevistador prefira contratar um candidato de maior valor do que um de menor valor, e não se preocupe apenas em obter o melhor. Ou seja, o entrevistador obterá algum valor da seleção de um candidato que não é necessariamente o melhor, e o valor derivado aumenta com o valor daquele selecionado.

Para modelar este problema, suponha que os requerentes tenham valores "verdadeiros" que são variáveis ​​aleatórias X extraídas iid de uma distribuição uniforme em [ 0,1 ]. Semelhante ao problema clássico descrito acima, o entrevistador apenas observa se cada candidato é o melhor até o momento (um candidato), deve aceitar ou rejeitar cada um na hora, e deve aceitar o último caso seja alcançado. (Para ser claro, o entrevistador não descobre a posição relativa real de cada candidato. Ele / ela descobre apenas se o candidato tem posição relativa 1.) No entanto, nesta versão a recompensa é dada pelo valor real do candidato selecionado. Por exemplo, se ele / ela seleciona um candidato cujo valor verdadeiro é 0,8, então ele / ela ganhará 0,8. O objetivo do entrevistador é maximizar o valor esperado do candidato selecionado. ${\ displaystyle n}$

Uma vez que os valores do requerente são obtidos a partir de uma distribuição uniforme em [0, 1], o valor esperado do t- ésimo requerente dado que é dado por ${\ displaystyle x_ {t} = \ max \ left \ {x_ {1}, x_ {2}, \ ldots, x_ {t} \ right \}}$

${\ displaystyle E_ {t} = E \ left (X_ {t} | I_ {t} = 1 \ right) = {\ frac {t} {t + 1}}.}$

Como no problema clássico, a política ótima é dada por um limite, que para esse problema denotaremos por , no qual o entrevistador deve começar a aceitar candidatos. Bearden 2006 mostrou que c é ou . (Na verdade, o que estiver mais próximo de .) Isso decorre do fato de que, dado um problema com os candidatos, o retorno esperado para algum limite arbitrário é ${\ displaystyle c}$${\ displaystyle \ lfloor {\ sqrt {n}} \ rfloor}$${\ displaystyle \ lceil {\ sqrt {n}} \ rceil}$${\ displaystyle {\ sqrt {n}}}$${\ displaystyle n}$${\ displaystyle 1 \ leq c \ leq n}$

${\ displaystyle V_ {n} (c) = \ sum _ {t = c} ^ {n-1} \ left [\ prod _ {s = c} ^ {t-1} \ left ({\ frac {s -1} {s}} \ right) \ right] \ left ({\ frac {1} {t + 1}} \ right) + \ left [\ prod _ {s = c} ^ {n-1} \ esquerda ({\ frac {s-1} {s}} \ direita) \ direita] {\ frac {1} {2}} = {\ frac {2cn- {c} ^ {2} + cn} {2cn} }.}$

Diferenciando em relação a c , obtém-se ${\ displaystyle V_ {n} (c)}$

${\ displaystyle {\ frac {\ partial V} {\ partial c}} = {\ frac {- {c} ^ {\, 2} + n} {2 {c} ^ {\, 2} n}}. }$

Aprendizagem no paradigma da busca sequencial de informação parcial. Os números exibem os valores esperados dos candidatos com base em sua classificação relativa (de um total de candidatos vistos até agora) em vários pontos da pesquisa. As expectativas são calculadas com base no caso em que seus valores são uniformemente distribuídos entre 0 e 1. As informações de classificação relativa permitem que o entrevistador avalie os candidatos com mais precisão à medida que eles acumulam mais pontos de dados para compará-los.

Visto que para todos os valores permitidos de , descobrimos que é maximizado em . Uma vez que V é convexo em , o limite de valor inteiro ideal deve ser ou . Assim, para a maioria dos valores, o entrevistador começará a aceitar candidatos mais cedo na versão de recompensa cardinal do que na versão clássica, onde o objetivo é selecionar o melhor candidato individual. Observe que este não é um resultado assintótico: vale para todos . No entanto, esta não é a política ideal para maximizar o valor esperado de uma distribuição conhecida. No caso de uma distribuição conhecida, o jogo ideal pode ser calculado por meio da programação dinâmica. ${\ displaystyle \ partial ^ {\, 2} V / \ partial c ^ {\, 2} <0}$${\ displaystyle c}$${\ displaystyle V}$${\ displaystyle c = {\ sqrt {n}}}$${\ displaystyle c}$${\ displaystyle \ lfloor {\ sqrt {n}} \ rfloor}$${\ displaystyle \ lceil {\ sqrt {n}} \ rceil}$${\ displaystyle n}$${\ displaystyle n}$

Uma forma mais geral desse problema introduzida por Palley e Kremer (2014) assume que, conforme cada novo candidato chega, o entrevistador observa sua classificação em relação a todos os candidatos que foram observados anteriormente. Esse modelo é consistente com a noção de um entrevistador aprendendo à medida que continua o processo de pesquisa, acumulando um conjunto de pontos de dados anteriores que pode usar para avaliar novos candidatos à medida que chegam. Um benefício desse modelo de informação parcial é que as decisões e resultados alcançados com base nas informações de classificação relativa podem ser comparados diretamente com as decisões e resultados ideais correspondentes se o entrevistador tivesse recebido informações completas sobre o valor de cada candidato. Esse problema de informação completa, em que os candidatos são sorteados independentemente de uma distribuição conhecida e o entrevistador busca maximizar o valor esperado do candidato selecionado, foi originalmente resolvido por Moser (1956), Sakaguchi (1961) e Karlin (1962).

Outras modificações

Existem várias variantes do problema da secretária que também apresentam soluções simples e elegantes.

Uma variante substitui o desejo de escolher o melhor pelo desejo de escolher o segundo melhor. Robert J. Vanderbei chama isso de problema do "pós-doutorado", argumentando que o "melhor" irá para Harvard. Para este problema, a probabilidade de sucesso para um número par de candidatos é exata . Essa probabilidade tende a 1/4 enquanto n tende ao infinito, ilustrando o fato de que é mais fácil escolher o melhor do que o segundo melhor. ${\ displaystyle {\ frac {0,25n ^ {2}} {n (n-1)}}}$

Para uma segunda variante, o número de seleções é especificado como maior que um. Em outras palavras, o entrevistador não está contratando apenas uma secretária, mas, digamos, admitindo uma classe de alunos de um pool de candidatos. Partindo do pressuposto de que o sucesso é alcançado se e somente se todos os candidatos selecionados forem superiores a todos os candidatos não selecionados, é novamente um problema que pode ser resolvido. Foi mostrado em Vanderbei 1980 que quando n é par e o desejo é selecionar exatamente metade dos candidatos, a estratégia ótima produz uma probabilidade de sucesso de . ${\ displaystyle {\ frac {1} {n / 2 + 1}}}$

Outra variante é selecionar as melhores secretárias de um pool de , novamente em um algoritmo on-line. Isso leva a uma estratégia relacionada à clássica e limite de corte para a qual o problema clássico é um caso especial Ghirdar 2009 . ${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle {\ frac {0,25n ^ {2}} {n (n-1)}}}$erro harvnb: sem alvo: CITEREFGhirdar2009 ( ajuda )

Problema de múltipla escolha

Um jogador pode escolher, e ele vence se alguma escolha for a melhor. Gilbert & Mosteller 1966 mostraram que uma estratégia ótima é dada por uma estratégia de limite (estratégia de corte). Uma estratégia ótima pertence à classe de estratégias definidas por um conjunto de números limites , onde . A primeira escolha deve ser usada nos primeiros candidatos começando com o candidato e, uma vez que a primeira escolha seja usada, a segunda escolha será usada no primeiro candidato começando com o candidato, e assim por diante. ${\ displaystyle r}$${\ displaystyle (a_ {1}, a_ {2}, ..., a_ {r})}$${\ displaystyle a_ {1} <a_ {2} <\ cdots <a_ {r}}$${\ displaystyle a_ {1}}$${\ displaystyle a_ {2}}$

Gilbert e Mosteller mostraram isso . Para outros casos , consulte Matsui & Ano 2016 (por exemplo ). ${\ displaystyle \ left ({\ frac {a_ {1}} {n}}, {\ frac {a_ {2}} {n}}, {\ frac {a_ {3}} {n}}, {\ frac {a_ {4}} {n}} \ right) \ rightarrow \ left (e ^ {- 1}, e ^ {- {\ frac {3} {2}}}, e ^ {- {\ frac { 47} {24}}}, e ^ {- {\ frac {2761} {1152}}} \ right) (n \ rightarrow \ infty)}$${\ displaystyle r = 5,6, ..., 10}$${\ displaystyle {\ frac {a_ {5}} {n}} \ rightarrow e ^ {- {\ frac {4162637} {1474560}}}}$

Quando , a probabilidade de vitória converge para ( Gilbert & Mosteller 1966 ). Matsui & Ano 2016 mostraram que, para qualquer número inteiro positivo , a probabilidade de vitória (do problema do secretário de escolha) converge para onde . Assim, a probabilidade de vitória converge para e quando, respectivamente. ${\ displaystyle r = 2}$${\ displaystyle e ^ {- 1} + e ^ {- {\ frac {3} {2}}} (n \ rightarrow \ infty)}$${\ displaystyle r}$${\ displaystyle r}$${\ displaystyle p_ {1} + p_ {2} + \ cdots + p_ {r}}$${\ displaystyle p_ {i} = \ lim _ {n \ rightarrow \ infty} {\ frac {a_ {i}} {n}}}$${\ displaystyle e ^ {- 1} + e ^ {- {\ frac {3} {2}}} + e ^ {- {\ frac {47} {24}}}}$${\ displaystyle e ^ {- 1} + e ^ {- {\ frac {3} {2}}} + e ^ {- {\ frac {47} {24}}} + e ^ {- {\ frac { 2761} {1152}}}}$${\ displaystyle r = 3,4}$

Estudos experimentais

Psicólogos experimentais e economistas estudaram o comportamento de decisão de pessoas reais em situações problemáticas de secretárias. Em grande parte, este trabalho mostrou que as pessoas tendem a parar de pesquisar cedo demais. Isso pode ser explicado, pelo menos em parte, pelo custo da avaliação dos candidatos. Em configurações do mundo real, isso pode sugerir que as pessoas não pesquisam o suficiente sempre que se deparam com problemas em que as alternativas de decisão são encontradas sequencialmente. Por exemplo, ao tentar decidir em qual posto de gasolina ao longo de uma rodovia parar para abastecer, as pessoas podem não pesquisar o suficiente antes de parar. Se isso fosse verdade, eles tenderiam a pagar mais pela gasolina do que se tivessem procurado por mais tempo. O mesmo pode acontecer quando as pessoas pesquisam online por passagens aéreas. A pesquisa experimental sobre problemas como o problema da secretária é às vezes chamada de pesquisa operacional comportamental .

Correlatos neurais

Embora haja um corpo substancial de pesquisas neurocientíficas sobre integração de informações, ou a representação de crenças, em tarefas de tomada de decisão perceptual usando animais e seres humanos, sabe-se relativamente pouco sobre como se chega à decisão de parar de coletar informações.

Os pesquisadores estudaram as bases neurais para resolver o problema da secretária em voluntários saudáveis ​​usando ressonância magnética funcional . Um processo de decisão de Markov (MDP) foi usado para quantificar o valor de continuar a pesquisa em vez de se comprometer com a opção atual. As decisões de tomar ou recusar uma opção envolveram os córtices pré-frontais parietal e dorsolateral , bem como o estriado ventral , a ínsula anterior e o cingulado anterior . Portanto, as regiões do cérebro anteriormente implicadas na integração de evidências e na representação de recompensas codificam cruzamentos de limiares que acionam decisões para se comprometer com uma escolha.

História

O problema da secretária foi aparentemente apresentado em 1949 por Merrill M. Flood , que o chamou de problema da noiva em uma palestra que deu naquele ano. Ele se referiu a ele várias vezes durante os anos 1950, por exemplo, em uma palestra em uma conferência em Purdue em 9 de maio de 1958, e eventualmente se tornou amplamente conhecido no folclore, embora nada tenha sido publicado na época. Em 1958, ele enviou uma carta a Leonard Gillman , com cópias para uma dúzia de amigos, incluindo Samuel Karlin e J. Robbins, esboçando uma prova da estratégia ótima, com um apêndice de R. Palermo, que provou que todas as estratégias são dominadas por uma estratégia de a forma "rejeitar o primeiro p incondicionalmente, depois aceitar o próximo candidato que for melhor". (Veja Flood (1958).)

A primeira publicação foi aparentemente por Martin Gardner na Scientific American, fevereiro de 1960. Ele tinha ouvido falar sobre isso de John H. Fox Jr. e L. Gerald Marnie, que havia surgido independentemente com um problema equivalente em 1958; eles o chamaram de "jogo do googol". Fox e Marnie não conheciam a solução ideal; Gardner pediu conselho a Leo Moser , que (junto com JR Pounder) forneceu uma análise correta para publicação na revista. Logo depois, vários matemáticos escreveram a Gardner para contar-lhe sobre o problema equivalente que ouviram boatos, todos os quais provavelmente remontam ao trabalho original de Flood.

A 1 / e -law de melhor escolha deve-se a F. Thomas Bruss (1984).

Ferguson (1989) possui uma extensa bibliografia e aponta que um problema semelhante (mas diferente) foi considerado por Arthur Cayley em 1875 e mesmo por Johannes Kepler muito antes disso.

Generalização combinatória

O problema da secretária pode ser generalizado para o caso em que existem vários empregos diferentes. Novamente, há candidatos chegando em ordem aleatória. Quando chega um candidato, ela revela um conjunto de números não negativos. Cada valor especifica sua qualificação para um dos empregos. O administrador não deve apenas decidir se aceita ou não a candidata, mas, em caso afirmativo, também deve atribuí-la permanentemente a um dos empregos. O objetivo é encontrar um trabalho em que a soma das qualificações seja a maior possível. Esse problema é idêntico a encontrar uma correspondência de peso máximo em um grafo bipartido de aresta ponderada onde os nós de um lado chegam online em ordem aleatória. Portanto, é um caso especial do problema de correspondência bipartida online . ${\ displaystyle n}$${\ displaystyle n}$

Por uma generalização do algoritmo clássico para o problema da secretária, é possível obter uma atribuição em que a soma esperada de qualificações é apenas um fator menor do que uma atribuição ótima (offline). ${\ displaystyle e}$

Veja também

• Problema de atribuição
• Algoritmo de probabilidades
• Parada ideal
• Problema de Robbins
• Teoria da pesquisa
• Problema de casamento estável

Notas

Referências

• Bearden, JN (2006). "Um novo problema do secretário com a seleção baseada na classificação e recompensas cardeais". Journal of Mathematical Psychology . 50 : 58–9. doi : 10.1016 / j.jmp.2005.11.003 .
• Bearden, JN; Murphy, RO; Rapoport, A. (2005). “Uma extensão multi-atributo do problema da secretária: Teoria e experimentos”. Journal of Mathematical Psychology . 49 (5): 410–425. CiteSeerX  10.1.1.497.6468 . doi : 10.1016 / j.jmp.2005.08.002 .
• Bearden, J. Neil; Rapoport, Amnon; Murphy, Ryan O. (setembro de 2006). "Sequential Observation and Selection with Rank-Dependent Payoffs: An Experimental Study". Ciência da Administração . 52 (9): 1437–1449. doi : 10.1287 / mnsc.1060.0535 .
• Bruss, F. Thomas (junho de 2000). "Some as probabilidades para um e pare" . The Annals of Probability . 28 (3): 1384–1391. doi : 10.1214 / aop / 1019160340 .
• Bruss, F. Thomas (outubro de 2003). "Uma nota sobre limites para o teorema das probabilidades de parada ideal" . The Annals of Probability . 31 (4): 1859–1961. doi : 10.1214 / aop / 1068646368 .
• Bruss, F. Thomas (agosto de 1984). "Uma abordagem unificada para uma classe de problemas de melhor escolha com um número desconhecido de opções" . The Annals of Probability . 12 (3): 882–889. doi : 10.1214 / aop / 1176993237 .

• Freeman, PR (1983). “O problema do secretário e suas extensões: uma revisão”. Revisão Estatística Internacional / Revue Internationale de Statistique . 51 (2): 189–206. doi : 10.2307 / 1402748 . JSTOR  1402748 .
• Girdhar, Yogesh; Dudek, Gregory (2009). "Amostragem otimizada de dados online ou como contratar as melhores secretárias". Conferência Canadense de 2009 sobre Visão Computacional e Robótica . pp. 292–298. CiteSeerX  10.1.1.161.41 . doi : 10.1109 / CRV.2009.30 . ISBN 978-1-4244-4211-9. S2CID  2742443 .
• Gilbert, J; Mosteller, F (1966). "Reconhecendo o máximo de uma sequência". Journal of the American Statistical Association . 61 (313): 35–73. doi : 10.2307 / 2283044 . JSTOR  2283044 .
• Gnedin, A. (1994). “Uma solução para o jogo do Googol” . Annals of Probability . 22 (3): 1588–1595. doi : 10.1214 / aop / 1176988613 .
• Hill, TP " Saber quando parar ". American Scientist , vol. 97, 126-133 (2009). (Para tradução francesa, veja a matéria de capa na edição de julho da Pour la Science (2009))
• Ketelaar, Timothy; Todd, Peter M. (2001). "Enquadrando Nossos Pensamentos: Racionalidade Ecológica como Resposta da Psicologia Evolucionária ao Problema de Enquadramento". Desafios conceituais em psicologia evolutiva . Estudos em Sistemas Cognitivos. 27 . pp. 179–211. doi : 10.1007 / 978-94-010-0618-7_7 . ISBN 978-94-010-3890-4.
• Martin Gardner , New Mathematical Diversions from Scientific American. Simon and Schuster, 1966, Capítulo 3, Problema 3 [reimprime sua coluna original publicada em fevereiro de 1960 com comentários adicionais].
• Matsui, T; Ano, K (2016). "Limites inferiores para o problema de probabilidades de Bruss com interrupções múltiplas". Matemática da Pesquisa Operacional . 41 (2): 700–714. arXiv : 1204,5537 . doi : 10.1287 / moor.2015.0748 . S2CID  31778896 .
• Merrill R. Flood, carta escrita em 1958, uma cópia da qual pode ser encontrada nos documentos de Martin Gardner nos Arquivos da Universidade de Stanford, série 1, caixa 5, pasta 19.
• Miller, Geoffrey F. (2001). A mente de acasalamento: como a escolha sexual moldou a evolução da natureza humana . Anchor Books. ISBN 978-0-385-49517-2.
• Sardelis, Dimitris A .; Valahas, Theodoros M. (março de 1999). "Tomada de decisão: uma regra de ouro". The American Mathematical Monthly . 106 (3): 215. doi : 10,2307 / 2589677 . JSTOR  2589677 .
• Seale, DA; Rapoport, A. (1997). "Tomada de decisão sequencial com classificações relativas: Uma investigação experimental do 'problema da secretária ' ". Comportamento Organizacional e Processos de Decisão Humana . 69 (3): 221–236. doi : 10.1006 / obhd.1997.2683 .
• Stein, WE; Seale, DA; Rapoport, A. (2003). “Análise de soluções heurísticas para o problema de melhor escolha”. European Journal of Operational Research . 151 : 140–152. doi : 10.1016 / S0377-2217 (02) 00601-X .
• Vanderbei, RJ (novembro de 1980). "A escolha ideal de um subconjunto de uma população". Matemática da Pesquisa Operacional . 5 (4): 481–486. doi : 10.1287 / moor.5.4.481 .
• Vanderbei, Robert J. (2012). "A variante do pós-doutorado do problema da secretária" (PDF) . CiteSeerX  10.1.1.366.1718 . Citar diário requer |journal=( ajuda )

links externos

• Sequência OEIS A054404 (Número de filhas a esperar antes de escolher o problema de dote do sultão com n filhas)
• Weisstein, Eric W. "Sultan's Dotery Problem" . MathWorld .
• Neil Bearden. "Busca ótima (problemas de secretário)" . Arquivado do original em 4 de janeiro de 2017.
• Livro Optimal Stopping and Applications de Thomas S. Ferguson