
희대의 역작이 다시 또 경매에 올라왔습니다. 이번에도 여러 입찰자들이 작품을 쟁취하기 위하여 구름같이 모여들었군요. 열 길 물 속은 알아도 한 길 사람 속은 모른다고, 입찰자들은 약았습니다. 각자 본인이 생각하는 가치가 있지만, 본인의 이득을 위해서라면 거짓말도 서슴지 않을 속내입니다. 지난 시간에는 이런 상황 속에서 가치를 가장 높게 쳐주는 입찰자에게 작품을 판매하는 경매 방식인 비크리 경매(Vickrey auction)를 공부하였습니다.
비크리 경매 (Vickrey Auction)
희대의 역작이 경매로 올라왔고, 여러 입찰자들이 이 작품을 구매하기 위해 모여들었습니다. 작가는 자신의 가치를 실제로 가장 높게 쳐주는 사람에게 자신의 작품을 넘기기를 바라고 있습니다
gazelle-and-cs.tistory.com
이번 포스트에서는 목표를 다르게 잡아 보고자 합니다. 그동안 경매사는 가장 높게 가치를 매겨주는 입찰자에게 물건을 넘겨 주었습니다. 그러다 보니 슬슬 본인의 통장 잔고가 비어가는 것을 느꼈습니다. 더 이상의 자선 사업은 그만해야겠다고 마음을 먹은 경매사는 이제부터 자신의 수익을 극대화하는 방향으로 경매를 진행하기로 결정했습니다. 과연 어떻게 하면 경매사의 목표를 달성할 수 있을까요?
들어가며
본문에 바로 들어가기 전에 초기 정보가 전혀 없는 일반적인 상황을 먼저 생각해 봅시다. 가치를 가장 높게 쳐주는 입찰자에게 작품을 판매하는 비크리 경매는 경매사가 입찰자에 대한 초기 정보가 전혀 없어도 잘 동작했습니다. 그렇다면 경매사의 수익을 최대로 만들고자 하는 현재 목표에서는 초기 정보가 없어도 괜찮을까요?
안타깝지만 그렇지 않습니다. 예를 들어 보죠. 경매에 참가한 입찰자가 한 명이라고 생각해 봅시다. 만약 비크리 경매에서와 같이 가치를 가장 높게 쳐주는 입찰자에게 작품을 판매하는 것이 목표라면, 어떤 방식으로던 입찰자에게 작품을 넘기기만 하면 모든 상황이 종료됩니다. 따라서 공짜로 작품을 넘기는 것도 최대의 가치를 이룩하는 방법이 되죠. 하지만 이는 경매사의 입장에서는 최악의 수입니다.
그렇다면 경매사가 취할 수 있는 최적의 수는 무엇일까요? 바로 입찰자가 생각하는 가치만큼의 가격에 작품을 판매하는 것이죠. 문제는 여기서 발생합니다. 입찰자가 생각하는 가치가 무엇인지 알 방도가 없기 때문입니다. 따라서 이번에는 이렇게 과도하게 제한적인 상황을 좀 풀어 주고자 합니다. 바로 입찰자가 생각하는 가치가 이미 모두에게 알려진 어떤 확률 분포를 따른다는 것이죠. 이 상황에서 우리의 목표는 경매사의 기대 수익을 최대화하는 것이 되겠습니다.
이번에는 경매에 두 명의 입찰자가 들어왔다고 합시다. 두 입찰자는 각각 독립적으로
과연 더 잘할 수 있을까요? 이번에는 같은 입찰자들에 대해 다음과 같은 경매를 진행해 보겠습니다. 똑같이 비크리 경매를 수행한 후 승자가 지불해야 하는 금액이
과연 더 잘할 수 있을까요? 이 질문의 답은 본문의 말미에 남겨 두었습니다.
문제 정의
이번 절에서는 문제를 엄밀히 정의해 보겠습니다. 하나의 물건이 경매에 올라왔으며, 총
경매는 각 입찰자들에게서 자신이 생각하는 물건의 가치를 경매사가 수집하는 것으로 시작합니다. 입찰자는 필요에 따라서는 자신이 생각하는 가치를 속여서 제출할 수도 있습니다. 경매사는 수집한 정보를 토대로 최대 한 명의 낙찰자에게 물건을 제공하며, 각 입찰자들에게서 돈을 요구합니다. 이때, 경매사는 필요하다면 아무에게도 물건을 넘기지 않을 수 있으며, 물건을 받지 못한 입찰자에게서도 돈을 요구할 수 있습니다. 경매사의 수익은 입찰자들에게서 거둔 돈의 총액입니다. 우리의 목표는 입찰자들의 확률 분포에 대한 경매사의 기대 수익을 최대화하는 것입니다. 단, 이 경매에서도 마찬가지로 입찰자들에게는 거짓을 고할 유인이 없어야 합니다.
표현 편의를 위한 기호
표현의 편의를 위해 모든 입찰가를 다음과 같이 벡터로 쓸 수 있습니다.
경매의 조건
각 입찰자
입찰자
또한 우리는 경매에서 입찰자들이 거짓을 고하지 않기를 원합니다. 그러기 위해서는 입찰자가 실제로는
앞에서 살펴 본 내용들을 토대로 우리는 경매사의 기대 수익을 최대화하는 문제를 다음과 같은 최적화 문제(optimization problem)로 표현할 수 있습니다.
단순한 동치 문제
위 최적화 문제를 바로 푸는 것은 대단히 어려워 보입니다. 따라서 이를 보다 간단히 만들 수 없는지를 먼저 생각해 보겠습니다. 이를 위해서 먼저
이 정의를 활용하면 위 문제를 조금 더 단순하게 만들 수 있습니다. 마지막 유인 부합성 제약 조건의 우변을 살펴 보겠습니다. 우리는 다음의 등식을 얻을 수 있습니다.
따라서 P1을 다음과 같이 변환해 보겠습니다.
아쉽지만 이렇게 얻은 P2도 여전히 복잡합니다.
이제 다음의 최적화 문제를 생각해 봅시다.
할당 조건은 그대로 남아 있지만, 개별적 합리성과 유인 부합성은 보다 단순하게 바뀌었습니다. 크게 두 부분이 눈에 띕니다.
- 세 번째 제약 조건의 직관적인 의미는 입찰자
가 더 큰 값을 제출할 수록 얻을 확률이 높아지기만 한다는 것입니다. - 마지막 제약 조건은 등식입니다. 즉, 이는
를 와 로 특정 지을 수 있다는 의미죠.
이 문제를 정의한 이유는 놀랍게도 P2, 나아가 P1과 동치(equivalent)이기 때문입니다.
정리 1. 동치인 두 문제
P2와 P3는 동치이다. 다시 말해, 위 문제에서의 가능한(feasible) 해는 아래 문제에서도 가능하며, 아래 문제에서 가능한 해는 위 문제에서도 가능하다.
[증명] 먼저 P2의 가능한 해가 P3의 가능한 해임을 보이겠습니다. 일단 P3의 첫 번째, 두 번째, 네 번째 조건은 쉽게 증명이 가능합니다. 이제 입찰자
이제 P3의 가능한 해가 P2의 가능한 해가 됨을 보이겠습니다. P2의 첫 번째, 두 번째 조건은 쉽게 증명이 됩니다. 세 번째 조건 또한 어렵지 않습니다.
기대 수익
이전 절에서 우리는 복잡한 최적화 문제를 훨씬 단순하고 직관적인 형태로 바꾸는 것에 성공하였습니다. 이번 절에서는 이 형태를 토대로 경매사의 기대 수익을 다시 써 보도록 하겠습니다. 경매사의 기대 수익은
여기서 뒤의 항을 좀더 바꾸어 보도록 하겠습니다. P3의 마지막 조건에 의해 우리는
위에서 구한 것을 토대로 다시 식 1을 다시 적으면 우리는 경매사의 기대 수익이
정리 2. 수익 동치 정리
같은 환경의 서로 다른 두 경매 방식을 생각하자. 만약, 동일한 입찰가
적절한 지불 방식
지금까지의 내용을 정리해 봅시다. 우리는 다음의 최적화 문제를 얻은 상태입니다.
그런데 수익 동치 정리에서도 알 수 있듯이, 기대 수익은 각 입찰자의 지불 금액에 크게 관련이 없습니다. 오히려 모든 입찰자
먼저
마지막 제약 조건을 살펴 봅시다. 앞에서
식 2와 3을 모두 만족시키는 방법은 각 입찰자
앞의 논의를 통해 우리는 다음의 결과를 얻을 수 있습니다.
정리 3. 최적 경매의 형태
P5의 최적해를
레귤러 분포 (Regular Distribution)
P5와 식 4를 통해 우리는 최적 경매를 하나 찾을 수 있게 되었습니다. 하지만 P5는 딱 보기에 풀기 쉬워 보이지 않습니다. 하지만 특정한 조건이 있다면 우리는 이 문제를 훨씬 간단히 해결할 수 있습니다. 모든 입찰자
균등 분포(uniform distribution), 정규 분포, 지수 분포(exponential distribution) 등 많은 분포들이 레귤러 분포에 속한다고 합니다. 물론 모든 분포가 레귤러 성질을 만족하는 것은 아닙니다. 실례로 다음의 확률 밀도 함수를 갖는 분포는 레귤러하지 않습니다.
이제 다음과 같은 경매 방식을 생각해 봅시다. 아래에서는 할당 방법만 소개합니다. 지불 금액은 아래에서 식 4를 통해 얻을 예정입니다.
방법 1. 레귤러 분포 최적 경매
입력: 독립된 레귤러 분포
출력: 낙찰자 선정 방법
- 모든 입찰자
로부터 를 받는다. - 모든 입찰자들의
를 계산한다. 일반성을 잃지 않고 가장 큰 의 입찰자를 1이라고 하자. 일 때만 입찰자 1에게 물건을 준다 (즉, ). 그렇지 않으면 아무에게도 넘기지 않는다.
이렇게 할당하는 방법이 P5의 최적해임을 보이겠습니다. 먼저 제약 조건을 살펴 보죠. 위 방법을 보면
마지막 제약 조건을 따져 봅시다. 어떤 입찰자
이 방법이 최적해라는 것은 그리 어렵지 않습니다.
이렇게 위에서 얻은 할당 방법이 최적의 방법임을 알았습니다. 그럼 각 입찰자로부터 돈은 얼마큼 받으면 될까요? 식 4를 다시 가지고 오겠습니다.
먼저 입찰자
이제 입찰자
동일한 분포를 갖는 경우
마지막으로 모든 입찰자가 동일한 레귤러 분포를 갖는 경우를 고려해 보겠습니다. 그러면
서론에서 두 입찰자가 독립적으로 각각
마치며
이것으로 최적 경매에 대한 설명을 마칩니다. 경매 및 메커니즘 설계는 경제·경영학을 필두로 한 사회과학 분야에서 시작했지만 현재는 컴퓨터과학 분야에서도 활발히 연구가 되는 주제입니다. 요즘 이와 관련하여 학교에서 세미나를 진행하고 있습니다. 관심 있으신 분들은 아래 링크로 방문하시기 바랍니다.
Yonsei CS Theory Student Group
YONSEI CS THEORY STUDENT GROUP Welcome to Yonsei CS theory student group's webpage! We aim at exploring various aspects of theoretical computer science while providing a social community for graduate (or undergraduate) students who are working on (or inter
yonsei-cs-theory-students.github.io
이번에 어쩌다 보니 예정에 없던 최적 경매를 주제로 발표를 하게 되었습니다. 예전부터 언젠간 블로그에 적어야 겠다고 생각하기도 했고, 발표 준비를 마치고 나니 이대로는 약간 아쉬운 마음이 들기도 해서 블로그에도 포스팅을 합니다. 물론 토요일은 휘리릭 사라졌지만, 괜찮습니다. 내일은 일요일이거든요.
본문의 최적 경매는 크게 몇 가지 정도 발전시킬 방향이 있습니다.
- 본문에서의 경매는 모든 입찰자가 자신의 가치를 적어 경매사에게 제출하고, 경매사는 바로 낙찰자를 결정하는 방식으로만 진행된다고 가정하였습니다. 세상에는 다양한 종류의 경매 방식이 있습니다. 과연 그러한 경우를 포함해서도 본문의 방식이 최선일까요?
- 본문에서는 경매로 나온 물건이 하나뿐이라는 가정을 합니다. 혹시 여러 개의 물건이 나오고, 입찰자들 또한 여러 개의 물건을 원하는 상황에는 어떻게 될까요?
- 본문에서는 입찰자들의 효용이
와 같이 선형적(linear)입니다. 비선형 효용의 경우에는 어떻게 될까요? - 본문에서는 입찰자들의 확률 분포가 레귤러하다는 가정을 했을 때에만 간단한 경매 방법을 제시합니다. 혹시 레귤러하지 않은 분포에 대해서도 쉬운 경매 방법을 제시할 수 있을까요?
이제부터는 위 질문에 대한 답을 공부해 보고자 합니다. 이 중 몇 개는 이미 알고 있고, 또 몇 개는 학교에서 진행하는 학생 세미나에서 다룰 것 같습니다. 위 내용들에 대해서 잘 공부한 다음, 블로그에 정리해 보도록 하겠습니다.
읽어 주셔서 고맙습니다. :)
참고 문헌
[1] Roger B. Myerson. "Optimal auction design." Mathematics of operations research 6, no. 1 (1981): 58-73.
[2] Jason D. Hartline. "Mechanism design and approximation." (2013) Link: https://jasonhartline.com/MDnA/
'알고리즘 & 게임 이론 > Mechanism design' 카테고리의 다른 글
비크리-클라크-그로브스 메커니즘 (Vickrey-Clarke-Groves Mechanism) (0) | 2022.01.22 |
---|---|
애로우의 불가능성 정리 (Arrow's Impossibility Theorem) (2) | 2022.01.13 |
비크리 경매 (Vickrey Auction) (6) | 2021.12.04 |