Wyniki wyszukiwania - BazTech

1

Secretary problem and two almost the same consecutive applicants

Rukavicka Josef

Mathematica Applicanda

|

2022

|

Vol. 50, no. 2

165--181

EN

The classical secretary problem involves sequentially interviewing a pool of n applicants with the aim of hiring exactly the best one in the pool; nothing less is good enough. The decision maker’s strategy should maximize the probability of appropriate selection. The various modification of the aim under the probability maximization criterion does not contain the issue of selecting the pairs of secretaries of very close absolute ranks. This paper is devoted to such a concern, with is formulated in a rigorous way. The effectiveness of the threshold rules is analyzed. It is shown that the probability of success in this class of strategies is asymptotically bounded by 0.5.

PL

Klasyczny problem sekretarki to sekwencyjny problem decyzyjny, w którym celem jest wybór najlepszej kandydatki w postępowaniu rekrutacyjnym, gdy w chwili decyzji statystyk ma niepełne dane o rzeczywistej wartości akceptowanej kandydatki. Wybór kończy się niepowodzeniem, gdy wyselekcjonowana kandydatka nie jest najlepszą wśród wszystkich n, które zgłosiły się na konkurs lub żadna nie zostanie wybrana. Rekruter posługuje się strategią maksymalizującą szanse powodzenia. Zadanie rozpatrzone w tej pracy jest modyfikacją, w której celem rekrutera jest wybór dwóch bliskich co do globalnej rangi kandydatów zatrzymując się na kandydacie, którego poprzednik jest potencjalnie bliski w przyjętym sensie. Autor wyznacza strategię, która maksymalizuje prawdopodobieństwo sukcesu w tym zadaniu. Pokazano, że asymptotyczne prawdopodobieństwo sukcesu w tej klasie strategii może osiągnąć 0.5.

2

The postdoc variant of the secretary problem

Vanderbei Robert J.

Mathematica Applicanda

|

2021

|

Vol. 49, no. 1

3--13

EN

The classical secretary problem involves sequentially interviewing a pool of n applicants with the aim of hiring exactly the best one in the pool-nothing less is good enough. The optimal decision strategy is easy to describe and the probability of success is 1/e. In this paper, we consider a minor variant of this classical problem. We wish to pick not the best, but the second best (the best is going to Harvard). In this case, an explicit solution can be given both for the optimal strategy and the associated optimal success probability. The probability of success is k*0 (n - k*0) / (n (n - 1)) where k*0 = [n/2]. Clearly, as n goes to infinity, the probability of success tends to 1/4. Apparently, it is easier to pick the best than the second best.

PL

Klasyczny problem sekretarki to sekwencyjne analizowanie n zgłoszeń, wśród których nie ma dwóch identycznych, w celu wyboru najlepszego z kandydatów w chwili, gdy zgłosi się na konkurs- wybór kandydata o innego niż najlepszy nie jest satysfakcjonujący. Optymalna strategia w tym problemie jest łatwa do opisania, a prawdopodobieństwo sukcesu wynosi w przybliżeniu exp(-1). W tym artykule rozważamy wariant tego klasycznego problemu, w którym celem jest wybór dokładnie drugiego co do rangi wśród n kandydatów. Podobnie jak w życiu, na zatrudnienie najlepszego nas nie stać lub piszemy opinie zewnętrzne, i wybieramy dla wybranych najlepsze miejsce na studia doktoranckie. Chcemy wybrać nie najlepszych, ale drugich najlepszych (najlepszy jedzie na Harvard). Również w tym problemie można podać optymalne rozwiązanie: zarówno wskazać optymalną strategię, jak i wyliczyć związane z tą strategią prawdopodobieństwa sukcesu. Szansa na sukces w tym problemie wynosi k*0 (n - k*0) / (n (n - 1), gdzie k0 = [n/2]. Gdy n dąży do nieskończoności, to prawdopodobieństwo sukcesu wynosi ma granicę 1/4. Zatem najwyraźniej łatwiej jest wybrać najlepszego niż drugiego najlepszego.

3

Average number of candidates surveyed by the headhunter in the recruitment

Ernst Marlena, Szajowski Krzysztof J.

Mathematica Applicanda

|

2021

|

Vol. 49, no. 1

31--53

EN

The classical secretary problem involves sequentially interviewing a pool of N applicants with the aim of hiring exactly the best one in the pool-nothing less is good enough. The optimal decision strategy is easy to describe and the probability of success is known. In this paper, we analyze properties of the optimal Markov time related to the variants of the classical secretary problem. Modifications to the problem take into account the behavior that adopts a loss suffered by the recruiter in the absence of a final indication of the candidate or when the chosen candidate is not appropriate. There is no guarantee that the optimal strategy for these problems is unique. This ambiguity in the solution is particularly interesting when we analyze the time spent on recruitment.

PL

Klasyczny problem sekretarki polega na sekwencyjnej ocenie puli N kandydatów w celu wyłonienia najlepszego z nich - żadna o mniejszych kwalifikacjach nie jest wystarczająco dobra. Optymalna strategia w tym problemie jest łatwa do opisania i znane jest prawdopodobieństwo sukcesu (wartość problemu). W niniejszym artykule analizujemy właściwości optymalnej strategii związanej z wariantami klasycznego problemu sekretarki. Modyfikacje problemu uwzględniają naturalne konsekwencje tego, że strategia łowcy głów doprowadzi do wyłonienia niewłaściwego kandydata, lub przegląd kandydatów zakończy się tym, że takiego kandydata rekruter nie wskaże. Nie ma gwarancji, że optymalna strategia dla tych problemów jest jedyna. Ta niejednoznaczność rozwiązania jest szczególnie interesująca, gdy analizujemy czas poświęcony na rekrutację. Wiadomo, że w przeszłości badano modele w których był uwzględniany koszt każdego wywiadu lub wypłaty łowcy głów były dyskontowane, ale rozważane w tej pracy modele uwzględniają inne aspekty i nie są szczególnymi przypadkami wymienionych.

4

Odds-theorem and monotonicity

Bruss F. Thomas

Mathematica Applicanda

|

2019

|

Vol. 47, no. 1

25--43

EN

Given a finite sequence of events and a well-defined notion of events being interesting, the Odds-theorem (Bruss(2000)) gives an online strategy to stop on the last interesting event. This strategy is optimal for independent events, and it is obtained in a straightforward way by an algorithm which is optimal itself (odds-algorithm). Here we study questions in how far the optimal value mirrors monotonicity properties of the underlying sequence of probabilities of events. We make these questions precise, motivate them, and then give complete answers. The motivation is enhanced by certain problems where it seems desirable to apply the odds-algorithm but where a lack of information does not allow to do so without incorporating sequential estimation. In view of this goal, the notion of a plug-in odds-algorithm is introduced. Several applications are included.

PL

Rozważamy optymalne zatrzymanie na wyróżnionym zdarzeniu w sekwencyjnym eksperymencie ze skończoną liczbą opcji. Twierdzenie o ilorazie szansach (Bruss(2000)) wyznacza taką strategię, która maksymalizuje szansę na właściwy wybór. Strategia ta jest optymalna, gdy mamy sekwencję niezależnych eksperymentów, a jej wyznaczanie jest proste. Służy do tego wspomniany algorytm oparty o sumowanie ilorazu szans. W pracy analizowane są szczególne własności takich zadań. Badana jest monotoniczność wartości optymalnej w powiązaniu z monotonicznością podstawowej sekwencji prawdopodobieństw zdarzeń. Podana jest motywacja do takich badań, a następnie udzielono pełnych odpowiedzi. Motywację wzmacniają problemy, w których pożądane jest zastosowanie algorytmu szans, ale w których brak informacji nie pozwala na to bez zastosowania sekwencyjnej estymacji nieznanych parametrów. W związku z takimi zagadnieniami wprowadzono pojęcie adaptacyjnego algorytmu ilorazu szans. Rozważania są ilustrowane przykładami.

5

One step more in Robbins' problem: Explicit solution for the case n = 4

Dendievel R., Swan Y.

Mathematica Applicanda

|

2016

|

Vol. 44, No. 1

135--148

EN

Let X1, X2, …., Xn be independent random variables drawn from the uniform distribution on [0, 1]. A decision maker is shown the variables sequentially and, after each observation, must decide whether or not to keep the current one, with payoff being the overall rank of the selected observation. Decisions are final: no recall is allowed. The objective is to minimize the expected payoff. In this note we give the explicit solution to this problem, known as Robbins’ problem of optimal stopping, when n = 4.

PL

Niech X1, X2, …., Xn będzie ciągiem niezależnych zmiennych losowych o rozkładzie jednostajnym na [0, 1]. Statystyk obserwuje realizacje tych zmiennych sekwencyjnie i po każdej obserwacji decyduje o jej zatrzymaniu lub odrzuceniu. Zaakceptowanej obserwacji nie można w przyszłości zmieniać ani wracać do odrzuconych obserwacji. Celem jest minimalizacja oczekiwanej rangi zaakceptowanej obserwacji. Ten artykuł podaje rozwiązanie tego zadania dla n = 4. Problem w literaturze jest znany jako problem Robinsa.

6

Guess the Larger Number

Gnedin A.

Mathematica Applicanda

|

2016

|

Vol. 44, No. 1

183–-207

EN

We discuss variations of the zero-sum game where Bob selects two distinct numbers, and Alice learns one of them to make a guess which of the numbers is the larger.

PL

Przedmiotem rozważań są odmiany gry o sumie zerowej, gdy Bob wybiera dwa różne numery, a Alice dowiaduje się jedną z nich, by zgadnąć, która z liczb jest większa.

7

Duration problem: basic concept and some extensions

Porosiński Z., Skarupski M., Szajowski K.

Mathematica Applicanda

|

2016

|

Vol. 44, No. 1

87--112

EN

We consider a sequence of independent random variables with the known distribution observed sequentially. The observation n is assumed to be a value of one order statistics such as s : n-th, where 1 ≤ s ≤ n. It the instances following the nth observation it may remain of the s : m or it will be the value of the order statistics r : m (of m > n observations). Changing the rank of the observation, along with expanding a set of observations there is a random phenomenon that is difficult to predict. From practical reasons it is of great interest. Among others, we pose the question of the moment in which the observation appears and whose rank will not change significantly until the end of sampling of a certain size. We also attempt to answer which observation should be kept to have the “good quality observation” as long as possible. This last question was analysed by Ferguson, Hardwick and Tamaki (1991) in the abstract form which they called the problem of duration. This article gives a systematical presentation of the known duration models and a new modifications. We collect results from different papers on the duration of the extremal observation in the no-information (denoted as rank based) case and the full-information case. In the case of non-extremal observation duration models the most appealing are various settings related to the two extremal order statistics. In the no-information case it will be the maximizing duration of owning the relatively best or the second best object. The idea was formulated and the problem was solved by Szajowski and Tamaki (2006). The full-information duration problem with special requirement was presented by Kurushima and Ano (2010).

PL

Rozważmy ciąg niezależnych zmiennych losowych o znanym rozkładzie. N-ta obserwacja jest wartością pewnej statystyki pozycyjnej, powiedzmy s : n, gdzie 1 ≤ s ≤ n. W chwilach następujących po n-tej obserwacji może ona pozostać s : m lub zmieni swoją pozycję tak, iż stanie się statystyką pozycyjną r : m (gdzie m > n jest liczbą obserwacji). Zmiana rangi naszej obserwacji pośród wciąż powiększającego się zbioru wszystkich obserwacji jest zjawiskiem, które nie jest łatwo przewidzieć. Z pewnych względów jest to interesujący problem. Stawiamy zatem pytanie o moment pojawienia się obserwacji, której ranga się nie zmieni znacząco aż do czasu, gdy skończymy obserwować zjawisko. Można również postawić problem w następujący sposób: ”Który obserwowalny obiekt powinniśmy zatrzymać tak, aby posiadać obiekt dobrej jakości najdłużej jak to tylko możliwe?” Pytanie to było rozważane przez Fergusona, Hardwicka and Tamaki’ego (1991) w problemie, który został nazwany ‘problem of duration’, a który został tu nazwamy problemem okresu trwania. Niniejsza praca ma na celu uporządkowanie znanych do tej pory modeli problemu okresu trwania oraz prezentację kilku nowych rozszerzeń. Zebrane zostały wyniki z różnych prac na temat okresu trwania dla ekstremalnej obserwacji w przypadku bezinformacyjnym (nazywanym również modelem rangowym, no-information case) oraz w przypadku pełno-informacyjnym (full-information case). W przypadkach obserwacji nieekstremalnych najczęściej pojawiającym się modelem jest model dla pierwszej i/lub drugiej statystyki pozycyjnej. Model bez-informacyjny mówi o maksymalizacji okresu trwania dla pierwszego lub drugiego najlepszego obiektu. Idea ta została sformułowana przez Szajowskiego i Tamaki’ego (2006). Przypadek pełno-informacyjny z pewnymi ograniczeniami został zaprezentowany przez Kurushima i Ano(2010).

8

A secretary problem with missing observations

Ramsey D. M.

Mathematica Applicanda

|

2016

|

Vol. 44, No. 1

149--165

EN

Two versions of a best choice problem in which an employer views a sequence of N applicants are considered. The employer can hire at most one applicant. Each applicant is available for interview (and, equivalently, for employment) with some probability p. The available applicants are interviewed in the order that they are observed and the availability of the i-th applicant is ascertained before the employer can observe the (i + 1)-th applicant. The employer can rank an available applicant with respect to previously interviewed applicants. The employer has no information on the value of applicants who are unavailable for interview. Applicants appear in a random order. An employer can only offer a position to an applicant directly after the interview. If an available applicant is offered the position, then he will be hired. In the first version of the problem, the goal of the employer is to obtain the best of all the applicants. The form of the optimal strategy is derived. In the second version of the problem, the goal of the employer to obtain the best of the available applicants. It is proposed that the optimal strategy for this second version is of the same form as the form of the optimal strategy for the first version. Examples and the results of numerical calculations are given.

PL

Artykuł rozważa dwie wersje problemu wyboru najlepszego obiektu, w których pracodawca obserwuje sekwencyjnie N pracobiorców. Każdy pracobiorca jest wolny z prawdopodobieństwem p, a gdy nie jest wolny pracodawca nie może ani prowadzić rozmowy z nim, ani go zatrudnić. Rozmowa o pracy z i-tym pracobiorcą (o ile ma miejsce) jest przeprowadzana zanim pojawi się (i+1)-szy pracobiorca. Pracodawca może tylko porównać pracobiorców, czyli sporządzić ranking tych, z którymi już prowadził rozmowę. Nie posiada on żadnych informacji dotyczących wartości pracobiorców, którzy nie są wolni. Pracobiorcy pojawiają się w losowej kolejności. Pracodawca może zatrudnić tylko jednego pracobiorcę i to tylko zaraz po rozmowie z nim. Wolny pracobiorca zawsze przyjmuje ofertę pracy. Według pierwszego modelu, celem pracodawcy jest zatrudnienie najlepszego z wszystkich pracobiorców. Wyznaczono postać optymalnej strategii. Według drugiego modelu, celem pracodawcy jest zatrudnienie najlepszego z wolnych pracobiorców. Podane jest uzasadnienie, iż postać optymalnej strategii jest taka sama jak przy pierwszym modelu. Rozważono parę przykładów i podano wyniki obliczeń numerycznych.