-
Introduction to Bilateral Trade
Bilateral Trade Bilateral Trade란 기본적으로 구매자 한 명과 판매자 한 명이 item을 거래하는 것입니다. 즉, 다음과 같은 구성 요소로 이루어진다고 볼 수 있습니다: 두 agent: 구매자와 판매자 구매자의 item에 대한 평가(valuation) $B \sim F_B$, 판매자의 평가 $S \sim F_S$ 여기에서 $F_B$와 $F_S$는 각각 $B$와 $S$가 선택되는 확률분포를 뜻합니다. Bilateral Trade Mechanism Bilateral Trade에서의 Mechanism이란 다음 두 가지 함수를 어떻게 설정하는지를 뜻합니다. 할당 함수(allocation function) $A:\mathbb{R} \times \mathbb{R} \rightarrow { 0, 1 }$. 두 reported valuation...
-
연산에 대한 O(n log n) / O(1) 구간 쿼리
프로그래밍을 하면서 많이 맞닥뜨리는 연산중 하나는 “구간 쿼리”입니다. 결합법칙을 만족하는 어떤 종류의 연산이든, $O(N \log N)$ 전처리로 쿼리당 $O(1)$ 시간에 구간에 대한 쿼리를 답할 수 있는 구조를 설명하려고 합니다. 구간 쿼리 구간 쿼리는 다음과 같은 문제입니다. (전처리) 배열 $A = (A_0, A_1, \cdots, A_{N-1})$과 연산 $\circ$가 주어집니다. (쿼리) $1 \le l \le r \le N$이 주어지면, $A_l \circ A_{l+1} \circ \cdots \circ A_r$을 계산해야합니다. 여기서, 우리가 주목해볼 연산의 성질은 다음과 같습니다. 결합법칙: 임의의 세 원소...
-
QGAN in Finance
Keywords: GAN, QGAN, copula, finance data 아이온큐 공식 블로그에 소개되어 있기도 하고, 2022년 11월에 실린 논문인데 아직 한국에 소개하는 글이 없어서 블로그 글로 작성한다. arxiv엔 2021년에 올라왔는데 왜이리 늦게 실렸는지 모르겠다. PRX저널에 실으려고 꽤 오래 존버했나..? 서론 이 논문은 특정한 결합확률 분포를 양자 생성기 (QGAN)으로 모델링하는것이 주제입니다. 꽤 흥미로운 접근법을 많이 보여주고 있어서 소개하고자 하였습니다. 이 논문에서 얻어갈만한 아이디어는 아래와 같습니다. 생성 문제를 probability integral transform을 통해 uniform distribution으로 바꾸고, 이걸 생성한 뒤 역변환 하는...
-
Introduction to Distributed Graph Algorithms
Introduction to Distributed Graph Algorithms 많은 일반적인 알고리즘은 하나의 프로세서에서 작동함을 가정하지만, 현실의 계산에서는 컴퓨팅 기계가 하나의 프로세서가 아닌 여러 프로세서를 사용할 수도 있다. Parallel Algorithm의 경우는 효율성을 위해서 여러 개의 프로세서를 두고 동시에 중앙적으로 컨트롤하지만, 가끔은 여러 프로세서를 두는 것이 단순 효율성 때문이 아니라 실제적인 시공간적 제약에 의해서일 수도 있다. 예를 들어, 세계 각지에서 정보를 모으는 컴퓨터가 있고, 이 정보들을 한데 모아서 특정한 계산을 하고 싶은데, 정보들이 하나로 모으기에는 너무 크거나, 아니면 장거리 네트워크를...
-
Dulmage-Mendelsohn Decomposition (Part 2)
개요 이전에 작성한 글에서는 Dulmage-Mendelsohn Decomposition(DM 분해)의 개념과 성질을 소개하고 이를 구하는 방법에 대해서 다루었습니다. 이 글에서는 Dulmage-Mendelsohn Decomposition의 코드와 PS에서의 활용에 대해 다룹니다. 코드 이전 글에서 언급한 구현 방법을 그대로 사용할 것입니다. BipartiteMatching은 이분 그래프를 받아서 최대 매칭을 구한 뒤에 각 정점이 어느 정점과 매칭되었는지를 반환하는 함수입니다. Kuhn’s Algorithm으로 $O(VE)$에 구현했지만, 더 빠른 시간복잡도를 원한다면 Hopcroft-Karp Algorithm 등의 다른 구현체로 대체해서 사용해도 됩니다. StronglyConnectedComponents는 방향 그래프를 받아서 SCC들의 번호를 위상정렬 순으로 매기고, SCC의 개수와...