Study with me =)

• 만약 어떤 player도 strictly dominant strategy(SDS)가 없다면 어떻게 해야 하는가?
  • Nash Equilibrium
    • P1이 S전략을 가지고 있고 P2가 T전략을 가지고 있다.
    • S가 T의 best response이며 T가 S의 best response라면 이는 Nash Equilibrium이다.
  • 만약 서로의 전략이 best response라면 다른 전략으로 이탈할 가능성이 없으므로 평형 상태라고 할 수 있다.
• 반면, 서로의 best response가 아닌 전략은 왜 평형 상태가 아닌가?
  • 상대가 다른 전략을 쓸 여지가 남아 있기 때문이다.
  • 결론적으로 Nash Equilibrium은 믿음의 평형이라 할 수 있다.

여섯번째 게임: 세 클라이언트 게임

• 두 회사 모두 SDS가 없다.
• 회사1의 best response는 A전략이다.
• 회사2의 best response는 A전략이다. 
• 따라서 (A,A)는 Nash 평형이다.

일곱번째 게임: 코디네이션 게임

• 두개의 Nash 평형이 생긴다. 
  • (파워포인트, 파워포인트)
  • (키노트, 키노트)
• 이때는 Focal point를 고려해야 한다.
• 몇몇 게임에서는 player가 하나의 Nash 평형 선택지를 고르도록 하는 자연스러운 요인이 있다.
• Nash를 확인하기 위해서 서로의 선택이 best인지 확인하는 것이 중요하다.

여덟번째 게임: stag hunt 버전의 발표냐 시험이냐

• SDS는 없고 Nash가 두개이다.
• 만약 당신이 더 높은 보상을 줄 수 있는 평형 전략을 선택할 것이라면 (발표,발표), 상대가 시험공부하기로 선택했을 수 있다는 리스크를 안고 가야한다.

아홉번째 게임: Hawk-Dove 게임

• 이 경우는 SDS가 없고 Nash가 있지만 같은 전략이 아닌 경우이다.
• (D,H)와 (H,D)가 Nash 평형 전략이고 이런 경우를 Chicken game이라 한다.
• 한쪽이 이득을 얻게 된다.
• 만약 Nash Equilibrium이 없다면 Mixed Stage를 사용해야 한다.
• 전략을 선택할 가능성을 정한다.
• players가 랜덤하게 행동할 수 있다면 Nash Equilibria는 항상 존재한다.

열번째 게임: 단순한 공격-방어 게임

• 이렇게 참가자들의 offset을 다 더하면 0이 되는 게임을 zero-sum game이라 한다.
• 어떤 경우에도, 각 플레이어는 자신의 동전을 뒤집고 싶어 할 것이므로 Nash 평형은 있을 수 없다.
• 왜냐하면 Nash는 상대의 전략을 알고 있어도 자신의 전략을 바꿀 여지가 없는 경우를 뜻하기 때문이다.
• 따라서 이 게임에서는 player가 서로의 전략을 예측하기 어렵도록 만들어야 한다. 이때 Mixed Strategies가 사용된다.
• H나 G를 전략으로 선택하는 것이 아닌, H를 선택할 확률과 G를 선택할 확률을 고른다.
• 이제 더이상 전략은 두개가 아니라, 0과 1사이 수의 집합이 된다.
• 즉, option을 mixing한 것과 같은 효과가 있다.
• Nash는 모든 게임에 최소한 하나의 mixed-strategy equilibrium이 있다는 것을 증명했다.
• 또한 한 게임에 pure strategy와 mixed가 둘 다 있을 수 있다.

• player2가 S전략을 행할 확률 q에 대한 player1의 payoff 계산
• player1이 S전략을 행할 확률 p에 대한 player2의 payoff 계산

• 게임에는 player, strategies, payoff 세 가지 요소가 있다.
• 상대의 선택을 SEPARATELY하게 분석해야 한다.
• 게임이론에서 중요한 것이 두가지 있다.
  • Best Response
    • S가 P1의 전략, T가 P2의 전략이라 할 때 전체 전략은 (S, T)라 한다.
    • P1(S, T)는 P1의 offset이다.
    • P2(S, T)는 P2의 offset이다.
    • P1(S, T) ≥ P1(S’, T)인 경우 S는 best response이다.
    • P1(S, T) > P1(S’, T)인 경우 S는 strict best response이다.
  • Dominant Strategy
    • P2의 모든 전략에 대해 best response인 P1의 전략은 dominant strategy이다.
    • P2의 모든 전략에 대해 strictly best response인 P1의 전략은 strictly dominant strategy이다.
    • player는 상대의 전략에 대해 여러 개의 dominant strategy를 가질 수 있다.

첫 번째 게임: 시험이냐 발표냐

• 만약 상대가 발표를 준비한다면, 당신은 발표를 준비할 때 90점, 시험을 준비할 때 92점을 받으므로 시험을 준비해야 한다.
• 만약 상대가 시험을 준비한다면, 당신은 발표를 준비할 때 86점, 시험을 준비할 때 88점을 받으므로 시험을 준비해야 한다.
• --> 상대가 뭘 하든 당신은 시험을 준비해야 한다. 이때 상대의 선택에 따라 당신의 더 나은 선택이 바뀌지 않으므로 이를 Strictly dominant strategy라 한다.
• --> 예상 평균은 88이다. 당신도 당신의 상대도 시험을 준비하는 것이 이득이기 때문이다.
• --> 이처럼 더 나은 상생에 대한 협의 없이 각자의 이득을 극대화하기 위한 것을 Rational Play라 한다.

두 번째 게임: 죄수의 딜레마

• 만약 죄수 2가 자백하지 않는다면, 죄수 1은 자백해야 할 것이다.
• 만약 죄수2가 자백한다면, 죄수 1은 자백해야 할 것이다.
• --> 죄수2가 뭘 하든 죄수 1은 자백해야 할 것이고 이는 strictly dominant strategy이다.

세 번째 게임: 약물을 할 것인가?

• 만약 선수 2가 약물을 하지 않는다면, 선수 1은 약물을 해야 할 것이다.
• 만약 선수2가 약물을 한다면, 선수 1은 약물을 해야 할 것이다.
• --> 선수2가 뭘 하든 선수 1은 약물을 해야 하므로 이는 strictly dominant strategy이다.
• --> 서로 우위를 점하기 위해 계속해서 위험한 선택을 하는 것을 Arms races라 한다.

네 번째 게임: 쉬운 시험일 때, 시험이냐 발표냐

• 만약 상대가 발표를 한다면, 당신은 발표를 해야 한다.
• 만약 상대가 시험을 준비한다면, 당신은 발표를 해야 한다.
• --> 상대가 뭘 하든 당신은 발표를 준비해야 하므로 이는 strictly dominant strategy이다.

다섯 번째 게임: 마케팅 전략 게임

• 만약 회사2가 낮은 가격을 책정한다면, 회사 1은 낮은 가격을 책정할 것이다.
• 만약 회사2가 높은 가격을 책정한다면, 회사 1은 낮은 가격을 책정할 것이다.
• --> 회사1의 strictly dominant strategy는 낮은 가격이다.
• 만약 회사1이 낮은 가격을 책정한다면, 회사 2는 높은 가격을 책정할 것이다.
• 만약 회사1이 높은 가격을 책정한다면, 회사 2는 낮은 가격을 책정할 것이다.
• --> 회사2는 dominant strategy가 없다.
• 하지만 다행히 회사 2는 높은 가격을 책정해야 하는 것을 안다.
• 아래 두가지 가정이 있기 때문이다.
  • 회사 2는 회사 1이 이득을 최대화하고 싶어 하는 것을 안다.
  • 회사 2는 회사 1이 자신의 이득을 알고 있음을 안다.

웹 그래프를 다음 구조로 알아보자!

1) real system인 Web이 있다.

2) 우리는 이 Web을 directed graph로 나타낼 것이다.

3) Graph theory 중 Strongly Connected Components를 주로 볼 것이다.

4) SCC가 실제로 Web Graph를 잘 나타내는지 실험적으로 확인할 것이다.

5) Structure of Web이 Bowtie라는 것을 알 수 있다!

1. The Web as a Graph

• 정의
  • bridge edge: 없으면 그래프가 끊긴다.
  • local bridge: edge of span>2, bridge는 아니다.
  • edge of span:
• node는 웹사이트, edge는 하이퍼링크라고 이해하면 된다.
• 옛날의 web link는 navigational 한 특징이 있었지만, 요즘은 좋아요, 댓글 등 transactional 하다.
• 한 node에 대해 In(A)와 Out(A)를 정의할 수 있다.
• 모든 웹상의 directed graph는 아래 두 가지 종류 중 하나로 표현할 수 있다.
  • Stringly Connected: 모든 노드에서 모든 노드로 도달할 수 있다,  In(A) = Out(A) = {all}
  • Directed Acyclic Graph: 사이클이 존재하지 않는다, u는 v로 갈 수 있지만 반대는 그렇지 못하다.
• Connected Graph
  • Strongly connected
  • Directly acyclic

2. SCC: Strongly Connected Component

• 정의
  • 모든 노드 쌍은 서로에게 도달할 수 있다.
  • 위 성질을 가진 더 큰 set은 없다.
• Every direct graph is a DAG on its SCCs
  • SCCs partitions the nodes of G
    • 각 노드는 정확히 하나의 SCC에만 포함된다.
  • Every directed graph is a DAG on its SCCs
    • 모든 방향성 그래프는 비순환 그래프이다.

3. Structure of the Web

• Goal
  • Take a large snapshot of the Web and try to understand how its SCCs fit together as a DAG
• Computational issue
  
  • starting node가 무엇인지에 따라 SCC를 찾기 위해 굉장히 많은 node를 순회해야 할 수도 있다.
• Bowtie Structure of the Web
  • In: 100
  • Out: 100
  • SCC: 56
  • Bowtie: 44 - 56 - 44

4. Why is it that axquaitances are most helpful?

• friendship에 대한 두가지 관점
  
  • Structural: 친구 집합은 그래프의 다른 부분에 위치한다.
  • Interpersonal: 관계는 weak이거나 strong이다.
    • structurally embedded edges는 strong 하다.
    • long range edges는 weak 하다.
    • strong 한 관계의 information은 redundant 하다.
• Tradic Closure
  • A-B 친구이고 A-C 친구이면 B-C가 친구일 확률이 높다.
• 만약 strong tradic closure가 만족된다면 local bridges are weak tie
• Edge Overlap
  • 두 노드 이웃 교집합/두 노드 이웃 합집합
  • edge가 local bridge라면 Overlap=0
• Edge Overlap과 Strength의 관계
  • permutated data보다 strength가 클수록 overlap이 컸다.
  • 그래프로 보았을 때도 strength가 큰 edge가 모여있는 것을 볼 수 있다.
• Edge Removal by Strength
  • strength가 낮은 것부터 끊었더니 largest component가 와해되는 속도가 빨랐다.
• Edge Removal by Overlap
  • overlap이 낮은 것부터 끊었더니 largest component가 와해되는 속도가 빨랐다.

1. Structural hole

• Structural hole 
  • 정보격차를 가진 두 개인 사이의 연결
  • 예시)
    • few structural hole : 학과 내에서의 교류
    • many structural hole : 타과와 많이 교류
• Network Constraint
  • 두 노드의 관계가 얼마나 일치하는지에 대한 값
    • 1/(친구수)
    • 예시)
      • network constraint가 낮으면 겹치는 친구가 없다 --> 타과생
      • network constraint가 높으면 겹치는 친구가 많다 --> 우리 과 사
• Redundant
  • 정보가 얼마나 중복되는가 (불필요한가)
  • 예시)
    • 자신의 친구들끼리 모여있다.
    • network constraint가 높다.
    • strongly tied
• 결론
  • 그래서 network constraint가 낮다는 것은 structural hole이 많다는 것을 뜻한다.
  • 그래서 정보일치성이 낮다는 것은 정보격차를 가진 개인 간의 연결이 있다는 것이다.
  • 그래서 낮은 network constraint는 실제로 좋은가?

2. How to detect dense community?

• Network community
  • 자기들끼리의 connection이 많고 바깥쪽으로는 적은 집합, 관계가 많이 겹치는 집합
  • 예시)
    • cluster
    • group
    • community
    • module
    • Micro-markets in sponsored search
    • Zachary's karate club network
• Definition of community
  • 우리는 clusterling을 위해 두가지 질문에 답해야 한다.
    • Q1. how to compute betweenness?
    • Q2. how to select the number of clusters?
  • A1. Girvan-Newman algorithm
    • division method for decomposing a network into hierarchical modules
    • 논리 
      • 그래프의 natural module을 찾기 위해 high betweenness를 가진 edge를 지운다.
      • 왜냐하면 high betweenness인 edge는 traffic of information의 bottleneck이기 때문이다.
      • 따라서 그래프를 파편화할 때 betweenness가 높은 edge를 끊는 것이 설득력 있다.
        • betweenness
          • 해당 edge를 통과해야만 하는 shortest path의 개수
            • 한 노드를 기준으로 잡고 BFS를 통해 그 노드로 가는 shortest path 개수 센다.
            • 수식
    • algorithm
      • 각 edge의 betweenness를 계산한다.
      • 가장 높은 betweenness를 가진 edge를 제거한다. --> 만약 같다면?
      • 남은 edge의 betweenness를 다시 계산한다.
      • 모든 edge가 사라질 때까지 반복한다.
      • 당연히 알고리즘이 진행될수록 module은 작아진다.
    • edge betweenness vs edge strength
      • betweenness는 그래프 구조만 사용한다.
      • strength는 weight를 사용한다.
    • 참고) www.youtube.com/watch?v=LtQoPEKKRYM
  • A2. Modularity Q
    • Girvan-Newman algorithm을 사용하며 언제 멈추어야 적절한 clusterling일지 알 수 있어야 한다.
    • '얼마나 잘 나뉘었는가'를 수치로 나타낸 것이 modularity Q이다. (-1~+1)
    • 기댓값이 0.3 ~ 0.7이면 partitioning이 잘 된 것이다. mod가 max일 때 가장 좋다.
    • Modularity Q
      • 네트워크가 얼마나 잘 partitioning 되었는가?
      • sum of {(# edges within group s) - (expexted # edges within group s})
    • 짚고 넘어간다: 왜 modularity를 decomposing의 기준으로 삼는가? (실제 edge 개수 - expected edge 개수)가 클수록 군집되어있기 때문에 community일 확률이 높다. 이것이 모든 community(라고 간주한 것)의 Q값 합을 구하는 이유
    • 왜 Q를 진작 optimize하지 않는가?
      • 모든 값을 계산해야 Q값이 나오기 때문이다.

3. Network with signed edge

• Signed edge
  • node가 positive인지 negative 관계인지 예측하는 것이 목적이다.
• Structural balance
  • balanced : (+,+,+) (+,-,-)
  • unbalanced : (+,+,-) (-,-,-)
  • 어떤 세 노드도 이 규칙에 위배되지 않는 그래프가 balanced graph
    • 모든 positive edge로 연결된 node는 한 set으로 취급 가능하다.
    • negative relationship은 이 set 간에만 이뤄진다.
  • 예시) international relationship