아이고리즘

(유한한 크기의) 집합 $V$를 생각하자. 이때 $V$의 각 원소에 $+1$ 혹은 $-1$을 지정하는 임의의 함수 $\chi:V\to \{\pm 1\}$를 생각해 보자. 달리 얘기하면, 각 원소를 파란색 혹은 빨간색으로 칠하는(coloring) 방법을 생각해 보자는 것이다. 이러한 coloring 함수 $\chi$가 주어졌을 때, 우리는 $V$의 임의의 부분집합 $S$에 대해 함수 $d(S)$를 다음과 같이 정의할 것이다.$$d(S):=\left| \sum_{v \in S}\chi(v) \right|.$$우리는 $d(S)$를 $\chi$에 대한 $S$의 discrepancy라 부를 것이다. (맥락에 따라 다루고 있는 함수 $\chi$가 명확하면 "$\chi$에 대한" 이란 말을 생략하도록 하겠다.) 이제..

Discrepancy Theory 2025. 8. 19. 03:45

Introduction 필자가 게임을 하나 제안하겠다. 상품이 하나씩 들어있는 박스가 여러 개 있다. 당신은 박스들을 하나씩 개봉하고 개봉한 박스들 중에서 하나를 골라 그 안에 있는 상품을 가져갈 수 있다. 당신은 물론 가장 좋은 상품을 고르고 싶을 것이다. 어떻게 하면 가장 좋은 상품을 고를 수 있을까? 매우 간단하다! 모든 박스를 열어보고 그 중에서 가장 좋은 것을 고르면 되니까. 하지만 이 문제에 제약 조건이 붙어 있다. 각 박스마다 개봉 비용이 있어서 열 때마다 필자에게 개봉 비용을 내야 한다. 따라서 모든 박스를 다 열어보는 것은 좋지 않은 전략일 수 있다. 그러면 다음 전략을 생각해볼 수 있다. 박스가 가지고 있는 상품의 값어치와 박스의 개봉 비용의 차이가 가장 큰 박스를 열고 그 안의 상품을..

Game Theory, Mechanism Design 2022. 11. 8. 16:49

이 글에선 Fundamental Theorem of Markov Chains의 증명을 마루리 하고자 한다. 지난글: https://cultivated-algorist.tistory.com/entry/Fundamental-Theorem-of-Markov-Chains-1 이전 글에서 Finite Markov chain은 항상 stationary distribution이 존재함을 보였다. 과연 stationary distribution은 unique할까? 그리고 임의의 시작 분포에서 시작하더라도 stationary distribution으로 수렴할까? 이 두 질문에 답하기 위해 두가지 개념을 생각하고자 한다. Irreducibility Markov chain을 directed graph라고 생각하자. 이때 그..

Stochastic Process 2022. 8. 4. 14:48

시작하기 앞서 Markov chain을 처음 들어보는 사람들을 위해 이를 간단하게 설명하고자 한다. Markov chain은 시간이 흐르면서 변화가 어떻게 이루어지는 지에 대한 확률 과정인 stochastic process의 특수한 경우이다. 이때 Markov chain에서의 시간의 변화는 이산적이다. 예를 들어 동전을 계속 던지는 게임을 한다고 생각하자. 동전을 한 번 던지는 것을 한 라운드로 생각한다면, 여기서의 시간의 변화는 라운드의 변화로 생각할 수 있다. 즉 $t$ 시점에서 $t+1$ 시점으로 가는 것을 $t$ 라운드에서 $t+1$ 라운드로 가는 것으로 생각할 수 있다는 것이다. 여기서 "변화"라는 것은 Markov chain의 용어로 설명하자면 "어떤 상태(state)에서 어떤 상태로 이동"하..

Stochastic Process 2022. 8. 2. 18:06

이전 글에서 Bilateral Trade 문제가 뭔지, Myerson-Satterthwaite Theorem이 뭔지 설명했다. 여기서는 이 정리를 증명하고자 한다. 기본적인 설정과 notation은 이전 글을 참고하시기 바란다. https://cultivated-algorist.tistory.com/entry/Bilateral-Trade-and-Myerson-Satterthwaite-Theorem-1 Bilateral Trade and Myerson-Satterthwaite Theorem (1) 이 글에서 보이고자 하는 정리가 무엇인지 말하기 전에 문제를 하나 정의하고자 한다. Bilateral Trade 사람1(판매자, seller)와 사람2(구매자, buyer)가 있다. 현재 상황은 사람1이 사람2에..

Game Theory, Mechanism Design 2022. 7. 28. 20:34

이 글에서 보이고자 하는 정리가 무엇인지 말하기 전에 문제를 하나 정의하고자 한다. Bilateral Trade 사람1(판매자, seller)와 사람2(구매자, buyer)가 있다. 현재 상황은 사람1이 사람2에게 물건을 파는 상황이다. 사람1은 속으로 '이 물건의 가치가 얼마나 되지?'라고 생각한다. 그리고 잠시 후에 $v_1$의 값이 머릿속에서 떠올랐다. 사람2도 마찬가지로 $v_2$의 값이 머릿속에 떠올랐다. (물건이 입력으로 주어졌을 때 머리가 값을 출력했다고 보면 좋을 것 같다.) (아직까지는 누가 얼마를 내고 얼마를 받고는 생각하지 말고 일단은) 어찌어찌 물건이 사람1에서 사람2에게 전달되었다고 생각하자. 이것을 사회의 관점에서 보았을 때, 물건이 그것의 가치를 $v_1$으로 생각하는 사람에서..

Game Theory, Mechanism Design 2022. 7. 28. 14:37

이전 글에서 Kőnig's Theorem, 쾨니그 정리를 증명했다. 핵심 아이디어만 말하자면 bipartite graph에서 모든 maximum matching에 등장하는 vertex가 하나 이상 존재함이었다. https://cultivated-algorist.tistory.com/entry/Kőnigs-theorem-쾨니그의-정리-증명 Kőnig's theorem (쾨니그의 정리) 증명 Kőnig's theorem. $G$가 bipartite라면 $G$의 maximum matching과 minimum node cover는 크기가 같다. 많은 증명들이 있지만 그 중에서 개인적으로 좋아하면서 (추측건데) 많이 보지 못했을 증명을 소개하고자 한.. cultivated-algorist.tistory.com 해..

Graph/Matching 2022. 7. 6. 12:54

Single-Parameter Environment Auction(경매)의 한 형태를 살펴보도록 하자. $n$명의 bidder(응찰자)들이 있고 각 bidder $i$는 경매에서 다룰 물건에 대해 각자가 생각하는 true valuation $v_i$가 있다. 이 $v_i$는 $i$만 알고있는 "private"한 정보이다. 즉, 이 값은 $i$가 아닌 다른 bidder나 auctioneer(경매인)에게는 공개되지 않는다. 경매가 시작되면 각 bidder는 물건에 대해 $b_i$만큼을 bidding한다. 경매인은 모든 bidder들로부터 bidding 금액을 받고 그 정보로 (1) 누구에게 물건을 줄지와 (2) 그 물건에 대해 받은 bidder가 지불해야할 가격을 정한다. (1) Allocation (1)번..

Game Theory, Mechanism Design 2022. 3. 29. 18:23