n명의 후보자가 순서대로 면접을 보러 오는 상황에서, 각 면전에서는 각 후보자의 점수를 정확히 알 수 있고, 그 점수를 바탕으로 후보자의 합/불 여부를 면접하는 즉시 결정하여 최고의 점수를 가진 후보자를 뽑는 비서 문제에 대해서는 다들 여기저기 교양 서적에서 한번쯤 봤을거임.



이 문제에서 나오는 최적의 전략은 n명중 약 n/e을 먼저 확인해서 최고점을 측정한 후 나머지 사람중 그 점수를 넘는 사람을 고르는 거라고 대부분의 교양 서적이 얘기함.


이러는 경우 약 1/e의 확률로 최고점수의 사람을 고를 수 있다는 것은 잘 알려져 있고, 사실 이게 거의 최적이 맞기도 함.



사실 이 문제는 최근 많은 주목을 받고 있는, 데이터를 연속적으로 일부만 받는 온라인 알고리즘 혹은 스트리밍 알고리즘의 한 문제로 볼 수 있음.


그리고 이런 온라인 알고리즘에 대한 문제들은 데이터를 악의적으로 조작한 상황에 얼마나 우리가 잘 해낼 수 있는지를 많이들 궁금해 함ㅋ.


즉, 다음과 같은 상황을 해결할 수 있을지 궁금함.



경쟁사에서 첫 후보자로 (다른 모든 후보를 뛰어넘는) 엄청난 능력자를 보내는 경우, 이 전략은 100%로 실패하게 됨!!


혹은 몇몇 후보자들이 회사가 이 전략을 쓴다는 것을 아는 순간 그 후보자들은 후반 순서를 받기를 원할 것이고, 이 경우에도 뭔가 이상해 질 꺼임.


또, 만약 한 명이 아니라 여러명의 비서를 뽑고싶은 상황도 (문맥과는 다르지만) 생각해볼수 있고.



이러한 상황이 악의적 비서 문제, 혹은 음모적(Byzantine) 비서 문제라고 함. 과연 이런 악의적으로 정해진 상황에서 훌륭한 비서를 뽑을 수 있을까?


이 글은 이 문제에 대한 ITCS 2020에 발표된 논문의 결과를 소개하는 것이 목표임.


아쉽게도 알고리즘 자체는 디테일이 꽤나 복잡하고, 대략적인 아이디어만 소개할거임.


이게 최근 알고리즘/컴퓨터과학의 주제랑도 맞고, 다들 잘 아는 문제라서 재밌을듯 해서 소개해봄ㅋ





비잔틴 비서 문제는 좀 엄밀하게 다음과 같이 정의된다.



  • n명의 후보자는 각각의 음아닌 실수, 가치 x1,...,xn를 갖고, 우리는 K명의 비서를 뽑고자 한다. 즉, |S|=K인 집합 S에 대해 총 가치 V_S=∑_{s∈S} x_s를 최대화 하는 것이 목표. (K=1, xi들을 엄청나게 차이가 많이 나도록 잡는 경우 보통의 비서 문제가 됨.) 이제 N명의 후보자는 [0,1]의 시간대에서 적당히 면접을 보러 올꺼고, 우리는 각 면접에서 그 즉시 후보자를 탈락시킬지 합격시킬지 정해야 함.

  • 이제 악의적인 상대는 우리의 전략이 무엇인지 아는 상태에서 어떤 사람이 악의적인 순서로 오는지, 어떤 사람이 얼마나 유능한지를 전부 결정함. 즉, 다음 값들을 모두 정할 수 있음.

  1. n=R+G를 만족하는 R (=red), G (=green)를 고르고, R명에게 붉은색을, G명에게 초록색을 할당한다. 이제 R,G를 집합으로도 쓰자.

  2. x1,...,xn을 모두 정한다.

  3. R에 해당하는 후보자가 면접하는 시간을 [0,1]사이에서 원하는대로 고른다. 단, G에 해당하는 후보자가 면접하는 시간은 악의적인 상대가 알지 못하게, [0,1]에서 uniform random하게 정해진다.


여기서 면접을 진행하는 우리가 R,G 값은 모르고, n값은 안다고 가정하고,

각 후보자가 왔을 때 그 후보자가 붉은색이 할당되었는지 초록색이 할당되었는지조차 알 수 없다고 가정할거임.


이 세팅은 심지어 G의 값마저도 조정할 수 있다는 점에서 꽤나 일반적임.


과연 이런 상황에서 우리는 얼마나 퀄리티가 좋은 후보들을 뽑을 수 있을까? 다음이 논문에서 진행된 몇 가지 관찰.


  1. G의 원소의 가치를 모두 0으로 잡아보자. 이 경우 우리가 구할 총 가치는 악의적인 상대가 마음대로 정할 수 있는 R의 값과 순서에만 의존한다. 즉, 우리가 적절한 전략을 골라도 악의적인 상대는 그게 최대한 실패할 집합을 잘 고를 수 있으니, 최적의, 혹은 그에 가까운 집합을 일반적으로 찾는것도 굉장히 어려워보인다. 즉, 우리가 기대하는 총 가치는 R의 원소들의 (최대) 가치와는 관계짓기 어려울 것이다.
  2. 이번에는 모든 가치가 하나의 G의 원소에 집중된, G의 최고 가치 gmax가 다른 가치들에 비해 엄청나게 큰 경우를 생각해보자. 이 경우, 악의적인 상대가 g_나머지<<r_1<<r_2<<...<<r_R<<gmax가 되도록 다른 가치보다는 순서대로 엄청 커지지만, gmax보다는 한참 작은 R의 원소들을 커지는 순서대로 배치한 경우를 생각해보자. 이 경우, 우리는 gmax에 해당하는 후보자를 본 경우에 이게 gmax인지 R의 원소인지 구별할 방법이 없다. 즉, gmax를 높은 확률로 찾는 우리의 전략은 없어보인다. 실제로 그 확률이 1/(|R|+1)보다 크지 못하게 되도록 악의적인 상대가 값들을 잘 정할 수 있다.


즉 우리가 기대하는 최대의 총 가치는 G에서 gmax를 제외한 나머지 가치들에 의존하게 될 것이다. 즉, x_t=gmax에 대해 다음 정도로 보임.

V*=max_{S⊂G-{t}, |S|=K} V_S



놀랍게도, 논문의 (일부) 결과는 다음과 같음.


  1. K=1일 때 예측 총 가치를 G의 두 번째 가치의 1/(log*n)2정도 이상이 되게 하는 알고리즘이 존재한다. 여기서 log*n은 굉장히 천천히 증가하는 iterative log.
  2. K가 적당히 크면 (정확히는 K >poly(log n/epsilon)정도이면) 비잔틴 비서 문제를 V*/(1+ε) 의 예측 총 가치를 갖도록 하는 알고리즘이 있다.


즉, 예상되는 최적값을 거의 얻을 수 있는 전략이 있다는 것! 과연 이게 어떻게 가능할까? 전체 알고리즘은 꽤나 복잡해서 다 살펴보긴 힘들고, 핵심 아이디어를 살펴보자.



우선, 다음과 같은, 우리가 아는 "쉬운 전략"들 (의 일반화)를 생각해 보자.


  1. 그냥 임의의 원소를 고르는 임의원소 전략을 생각해보자. 만약 이 전략을 상수확률로 고르면, 기대 총 가치가 V*보다 작아지기 위해서는 nV*의 상수배보다 큰 가치를 갖는 후보자가 없어야한다. 이 전략은 후보자들의 가치를 일정 범위 안으로 넣기 위해 쓰인다.
  2. 위 1/e 전략의 일반화로, 두-시간대 전략을 생각할 수 있다. 즉, [0,1]의 원소 T1<T2에 대해 [0,T1)의 원소는 무시하고, [T1,T2]의 원소중 최대 가치를 기록하고 (T2,1]에서 그 최댓값보다 큰 가치를 갖는 후보자를 고르는 전략을 생각할 수 있다. 이 전략은, [T1,T2]구간에 R의 원소가 없다면 G의 두 번째로 큰 원소가 [T1,T2]에 있으면서 (T2,1]에 G의 가장 큰 원소가 있을 때 항상 성공한다. 즉, 그 경우 (T2-T1)(1-T2)의 확률로 성공하고, 특히 T1,T2가 상수일 때 상수의 확률로 성공한다.


그럼 이제 비잔틴 비서 문제를 해결하는 논문의 핵심 아이디어는 다음과 같음.


  • 우선 K=1일 때, V*는 G의 두 번째로 큰 가치가 됨.
    1/2확률로 임의원소 전략을 이용해 모든 가치가 nV*정도 이하라고 가정하자.
    그리고 다시 나머지의 1/2확률로 T1=0, T2=1/2에 대해 두-시간대 전략을 쓴다.
    만약 이게 잘 된다면 문제가 없고, 그렇지 않다면 [0,1/2]에 R의 V*보다 가치가 큰 원소, 가치 M을 가지는 원소가 존재한다.
    그런데 앞의 가정에서 nV*>M이고, 이를 이용해서 V*의 범위를 n배 이내로 추측할 수 있다.
    이제 [M/n,M]을 [K,2K]형태의 log n개의 구간으로 나누고, 이를 임의로 선택해 V*가 그 구간에 속한다고 추측한다.
    그러면 그 추측이 맞을 확률은 1/log n이고, 1/2확률로 G의 가장 큰 원소가 [1/2,1]에 속해있으니 이 경우도 예상 총 가치는 V*/log n으로,
    총 예상 총 가치가 V*/log n의 상수배 이상임을 증명할 수 있다.
    이걸 iterative log로 바꾸려면 좀 노력이 필요하다.

  • 우선 K가 적당히 클 때, V*이 [1,n]에 속한다고 가정하자.
    아래 아이디어는 n이 poly(n)으로 바뀌어도 잘 되고, 이 조건을 없애려면 위 임의원소 전략의 변형을 이용해야한다.
    여튼 그렇다고 가정하고, 음아닌 정수 l에 대해 구간 Il=[n/(1+ε)l+1,n/(1+ε)l)을 생각하자. 또, 시간을 T개의 구간으로 나누자.
    그러면 우리는 각 시간의 구간에서 K/T개정도의 원소를 뽑아야한다. 이제 우리의 전략은
  1. 우선 첫 번째 시간의 구간에서는 l=0,1,...,K/T에 우리의 예산을 1씩 할당하고, 각 면접에서 후보자의 가치가 Il에 속하면서 해당 구간 의 예산이 남아 있는 경우에 합격시킨다. (합격시키는 경우 예산을 쓴다.)
  2. 그럼 두 번째 시간의 구간부터는 아마 남은 예산이 있을것이다. 이 첫 번째 과정의 결과를 이용해서 전체 사람들의 분포를 예측하여 다음 구간의 예산을 새로 할당한다.
  3. 이 과정을 끝까지 반복한다. (사실 좀 많이 복잡하다..)


굉장히 대충 설명해서 알아들을 방법이 있는지 잘 모르겠음ㅋ 여튼 비서문제를 컴퓨터과학에서는 이러한 관점으로 보고, 이런 문제들을 연구함.

재밌게 읽으면 좋겠는데 술한잔 빨구 써서 말이 되는가 멀겠네 ㅋ