game-theory

You are currently browsing articles tagged game-theory.

Trong bài viết này chúng ta sẽ tìm hiểu trò chơi bắt trộm. Trò chơi phát biểu như sau:

Cops and Robbers game: Cho một đồ thị đơn, vô hướng $G(V,E)$ và hai người chơi $\mathcal{C}$ và $\mathcal{R}$ trong đó $\mathcal{C}$ kiểm soát một tập $c$ cảnh sát (cops) và $\mathcal{R}$ kiểm soát đúng một tên trộm (robber). Cảnh sát và trộm luôn đứng trên đỉnh của $G$. Trong mỗi nước đi, trộm và cảnh sát có thể chọn đứng yên tại chỗ hoặc di chuyển từ đỉnh hiện tại tới một đỉnh kề với đỉnh đó. Tuy nhiên, $\mathrm{C}$ có thể đồng thời di chuyển tất cả $c$ cảnh sát. Trộm luôn được quyền đi trước trong mỗi nước đi.

Trộm được gọi là bị bắt nếu tồn tại một cảnh sát cùng nằm trên một đỉnh với trộm. Một chiến lược được gọi là một winning strategy cho $\mathcal{C}$ ($\mathcal{R}$) nếu theo chiến lược đó, $\mathcal{C}$ luôn bắt được trộm, bất kể $\mathcal{R}$ ($\mathcal{C}$) đi như thế nào. Câu hỏi đặt ra là cần ít nhất bao nhiêu cảnh sát để tồn tại một winning strategy cho $\mathcal{C}$?

 
Giả sử trò chơi trên là trò chơi complete information, i.e, tất cả các người chơi đều biết vị trí của người chơi khác trong đồ thị.
tree-clique-cycle
Figure 1: Trò chơi bắt trộm trên (a) cây, (b) đồ thị đầy đủ $K_6$ và (c) chu trình. Trong đồ thị chu trình (c), một cảnh sát không thể bắt được trộm.

Để hiểu hơn về bài toán này ta xét một vài đồ thị đặc biệt. Nếu $G(V,E)$ là một cây (tree) (Figure 1(a)), hoặc một đồ thị đầy đủ (complete graph) (Figure 1(b)) thì dễ thấy chỉ cần 1 cảnh sát là có thể bắt được trộm rồi. Nếu $G(V,E)$ là một chu trình thì ta cần đúng 2 cảnh sát (Figure 1(c)).

Tuy nhiên, một tính chất thú vị là nếu $G(V,E)$ là một đồ thị phẳng (planar graph) thì chỉ cần đúng 3 cảnh sát là ta có thể bắt được trộm.

Theorem 1: Nếu $G(V,E)$ là một đồ thị phẳng và $\mathcal{C}$ có 3 cảnh sát thì $\mathcal{C}$ luôn có một winning strategy.

 

Để bạn đọc hình dung được cái hay của định lý này, xét đồ thị trong Figure 2. Hình vẽ minh họa một đồ thị phẳng kiểu grid kích thước $12\times 13$ (12 hàng 13 cột). Theorem 1 cho ta biết chỉ cần 3 cảnh sát là có thể bắt được tên trộm. Tổng quát hơn, mọi grid kích thước $p \times q$, với $p,q$ lớn tùy ý, cũng chỉ cần 3 cảnh sát là đủ. Thực tế, chứng minh dưới đây sẽ chỉ ra, với mọi grid kích thước $p \times q$ thì chỉ cần 2 cảnh sát cũng đủ bắt được trộm.

grid-12-13
Figure 2: Một grid kích thước 12 hàng 13 cột. 3 cảnh sát luôn có thể bắt được trộm trong grid này. Thực tế chỉ cần 2 cảnh sát là có thể bắt được trộm.

Bắt bóng của trộm

Ý tưởng duy nhất mà cũng là quan trọng nhất trong chứng minh Theorem 1 đó là chỉ cần đúng một cảnh sát là người chơi $\mathcal{C}$ có thể kiểm soát được một đường đi ngắn nhất bất kì trong đồ thị bằng cách đuổi theo cái bóng (shadow) của tên trộm.

Lemma 1: Gọi $P$ là đường đi ngắn nhất giữa hai đỉnh riêng biệt bất kì $u,v$ trong đồ thị. Giả sử sử $\mathcal{C}$ đặt một cảnh sát $s$ trên $P$. Tồn tại một chiến lược di duyển $s$, sau hữu hạn bước, sao cho nếu tên trộm đi vào đỉnh bất kì của $P$ thì nó bị bắt ngay lập tức.

 

Trong Lemma 1, ta nói cảnh $s$ kiểm soát đường đi ngắn nhất $P$. Trước khi đi vào chứng minh Lemma 1, ta xét ý nghĩa của nó. Gọi $H_{p,q}$ là một grid kích thước $p\times q$. Ta sử dụng Lemma 1 để chứng minh chỉ cần 2 cảnh sát $\{s_1,s_2\}$ là có thể bắt được một tên trộm trong $H_{p,q}$ (xem Figure 3). Do bất kì cột nào của grid cũng là đường đi ngắn nhất giữa hai đầu mút của cột đó, ta lần lượt cho $s_1$ kiểm soát cột $C_1$ (sau hữu hạn bước). Khi $s_1$ đã kiểm soát được $C_1$, ta cho $s_2$ kiểm soát $C_2$. Sau khi $s_2$ đã kiểm soát được $C_2$, ta cho $s_1$ kiểm soát $C_3$, blah blah. Cứ như vậy cho đến khi tên trộm bị dồn vào cột cuối cùng và lúc này ta dễ dàng bắt được nó. Chú ý, theo Lemma 1, nếu một cảnh sát đã kiểm soát được một cột thì tên trộm không thể bước vào cột đó vì nếu không nó sẽ bị bắt ngay lập tức.

two-cops-on-grid
Figure 3: Đường màu đỏ là đường đi đã bị kiểm soát và đường màu xanh là đường mà một cảnh sát đang trong quá trình kiểm soát. (a) Ta cho $s_1$ kiểm soát cột $C_1$ và $s_2$ kiểm soát $C_2$. (b) Sau khi $s_2$ đã kiểm soát được $C_2$, $s_1$ không còn cần kiểm soát $C_1$ nữa và ta cho nó kiểm soát $C_3$. (c) $s_1$ đang kiểm soát $C_3$. Cứ lặp lại quá trình này thì cuối cùng tên trộm cũng bị bắt.

Chứng minh Lemma 1: Gọi $z$ là vị trí hiện tại của tên trộm và $s$ là cảnh sát mà ta muốn nó kiểm soát $P$. Kí hiệu $d_G(x,y)$ là khoảng cách ngắn nhất giữa hai đỉnh riêng biệt $x,y$ của đồ thị. Ta định nghĩa cái bóng (shadow) của tên trộm là đỉnh $w$ trên đường đi $P$ sao cho:

$d_G(u,w) = \min(d_G(u,z), d_G(u,v)) \qquad (1)$

shadow
Figure 4: (a) Cái bóng của trộm $w$ trên đường đi ngắn nhất $P$. (b) Cảnh sát sẽ kiểm soát $P$ bằng cách đi theo "cái bóng" của trộm trên $P$.

Xem ví dụ cái bóng của trộm trong Figure 4(a). Chú ý, do $P$ là đường đi ngắn nhất nên $d_G(u,v)$ chính là độ dài của $P$. Khi trộm thay đổi vị trí thì cái bóng cũng thay đổi theo. Tuy nhiên, do $u\not= v$, sau hữu hạn bước, $s$ sẽ bắt được cái bóng của tên trộm, i.e, $s$ sẽ đứng ở vị trí $w$. Do mỗi nước đi, tên trộm chỉ được phép đi sang đỉnh kề với vị trí nó đang đứng, cái bóng cũng chỉ thay đổi sang trái hoặc sang phải 1 bước. Do đó, $s$ luôn bắt được "cái bóng" sau mỗi nước đi.

Tại sao ta lại quan tâm đến cái bóng? Đó là do nếu $s$ đứng trên vị trí của cái bóng $w$ thì:

$d_G(z,x) \geq d_P(s, x) \quad \forall x \in P \qquad (2)$

Xem minh họa trong Figure 4(b). Ý nghĩa của (2) là nếu tên trộm đi vào $P$ thì sẽ tồn tại $x$ sao cho $d_G(z,x) = 0$. Từ $(2)$ ta suy ra $d_P(s,x) = 0$. Hay nói cách khác, $s$ cũng đứng tại đỉnh $x$, i.e, tên trộm ngay lập tức sẽ bị bắt.

Để chứng minh (2), ta xét hai trường hợp:

  • TH1: $x$ nằm giữa $u$ và $s$. Theo bất đẳng thức tam giác, ta có:

    $\begin{array} {l} d_G(z,x) &\geq d_G(u,z) - d_G(u,x) \\ & = d_P(x,s) - d_G(u,x)\\ &= d_P(x,s) - d_P(u,x) \\ &= d_P(x,s)\end{array}$

  • TH2: $x$ nằm giữa $v$ và $s$. Theo bất đẳng thức tam giác, ta có:

    $\begin{array} {l} d_G(z,x) &\geq d_G(u,x) - d_G(u,z) \\ & = d_P(u,x) - d_P(u,s) \\ &= d_P(x,s)\end{array}$


Chiến lược bắt trộm

Ta sẽ sử dụng Lemma 1 để tìm ra chiến lược bắt trộm bằng 3 cảnh sát $\{s_1,s_2,s_3\}$. Đầu tiên mình sẽ trình bày ý tưởng, và sau đó đi vào chứng minh hình thức hơn.

Ý tưởng: Ý tưởng của chiến lược bắt trộm khá đơn giản. Ta sẽ định nghĩa vùng an toàn của trộm là một đồ thị con $H$ của $G$, sao cho nếu trộm đi ra ngoài vùng an toàn đó thì lập tức nó bị bắt. Ban đầu $H$ là một thành phần liên thông của $G$ chứa tên trộm nếu ta xóa các đỉnh bị chiếm bởi cảnh sát ra khỏi đồ thị. Ta sẽ tìm chiến lược để thu hẹp dần vùng an toàn sau một số hữu hạn vòng chơi, đến cuối cùng, $H = \emptyset$. Lúc đó tên trộm sẽ bị bắt.

Ta sẽ cho $s_1$ kiểm soát một đường đi ngắn nhất $P_1$ từ $u$ tới $v$, $u\not= v$, bất kì. Sau đó tìm một đường đi ngắn nhất khác $P_2$ từ $u$ tới $v$ sao cho $P_1$ và $P_2$ không có đỉnh chung, ngoại trừ các đầu mút. $P_2$ có thể tìm được bằng cách xóa tất cả các đỉnh khác $u,v$ nằm trên $P_1$ khỏi đồ thị và áp dụng thuật toán tìm đường đi ngắn nhất. $P_1\cup P_2$ tạo thành một chu trình phân chia mặt phẳng thành hai phần, phần bên trong và bên ngoài. Ta sẽ cho $s_2$ kiểm soát $P_2$.

proof-ideas
Figure 5: Vùng tô màu xanh là vùng an toàn của kẻ trộm.

Không mất tính tổng quát, giả sử tên trộm nằm bên ngoài chu trình $P_1\cup P_2$ (Xem Figure 5(a)). Hay nói cách khác, vùng an toàn $H$ của tên trộm lúc này là phần đồ thị con bên ngoài chu trình $P_1\cup P_2$. Ta sẽ tìm một đường đi thứ 3, $P_3$ cũng từ $u$ tới $v$ nằm bên ngoài chu trình $P_1\cup P_2$, có độ dài ngắn nhất, sao cho $P_3$ không có đỉnh chung với $P_1,P_2$, ngoại trừ hai đầu mút. $P_3$ có thể tìm được xóa tất các đỉnh, ngoại trừ $u,v$, của $P_1,P_2$ và các đỉnh nằm trong đường chu trình $P_1\cup P_2$ ra khỏi đồ thị, và sau đó áp dụng thuật toán tìm đường đi ngắn nhất. Ta sẽ cho $s_3$ kiểm soát $P_3$.

Lúc này, tên trộm sẽ chỉ có thể nằm ở 1 trong 2 vùng của mặt phẳng có biên là $P_1\cup P_3$ và $P_2\cup P_3$. Nếu tên trộm nằm trong $P_2\cup P_3$, thì ta có thể bỏ đi $P_1$ và giải phóng cảnh sát $s_1$ cho vòng tiếp theo (Figure 5(b)). Nếu tên trộm nằm ngoài $P_1\cup P_3$, thì ta có thể bỏ đi $P_2$ và giải phóng cảnh sát $s_2$ (Figure 5(c)). Trong cả hai trường hợp, vùng an toàn của kẻ trộm bị thu hẹp. Lặp lại quá trình đó cho đến khi vùng an toàn $H = \emptyset$ và ta sẽ bắt được trộm.

Chứng minh hình thức: Chuyển ý tưởng trên thành một chứng minh hình thức cũng khá dài dòng. Lí do là không phải lúc nào cũng tồn tại các đường đi $P_2,P_3$. Trong trình bày ở trên thì ta luôn giả sử $P_2,P_3$ tồn tại. Ta sẽ chứng minh rằng nếu không tồn tại $P_2,P_3$ thì đồ thị sẽ có những cấu trúc khác đặc biệt hơn mà ta có thể sử dụng.

Ta cần thêm một số khái niệm. Giả sử $x,y$ là hai đỉnh của đường đi $P$. Ta kí hiệu đường đi con của $P$ từ $x$ tới $y$ bởi $P[x,y]$. Nếu $P,Q$ là hai đường đi, trong đó điểm cuối của $P$ trùng với điểm đầu của $Q$, ta kí hiệu $P\circ Q$ là đường đi thu được bằng cách nối điểm cuối của $P$ và điểm đầu của $Q$.

Gọi $H$ là vùng an toàn của trộm, i.e, nếu trộm cố gắng đi ra khỏi $H$ thì nó bị bắt ngay lập tức. Ta sẽ luôn đảm bảo $H$ là một đồ thị liên thông. Ban đầu $H = G$. Ta định nghĩa hai cấu hình cho người chơi $\mathcal{C}$ như sau:

  • Cấu hình 1: Tất cả cảnh sát $s_1,s_2,s_3$ đều đứng trên cùng một đỉnh.
  • Cấu hình 2: Hai cảnh sát kiểm soát hai đường đi $P_1,P_2$ giữa hai đỉnh $u,v$.

Không mất tính tổng quát, ta giả sử ban đầu người chơi $\mathcal{C}$ ở cấu hình 1 vì ta có thể di chuyển tất cả các cảnh sát về cùng một đỉnh của đồ thị.

Ý tưởng là ta sẽ tìm cách di chuyển $\mathcal{C}$ từ cấu hình hiện tại, sau một hữu hạn bước, sang 1 trong 2 cấu hình ở trên, sao cho sau khi $C$ đạt sang cấu hình mới, vùng an toàn $H$ của tên trộm bị thu hẹp. Ta xét hai trường hợp:

TH1: $\mathcal{C}$ đang ở cấu hình 1. Gọi $u$ là đỉnh mà cả 3 cảnh sát đang đứng và $v$ là đỉnh kề với $u$ trong $H$. Có hai hai trường hợp con:

  1. Nếu xóa cạnh $uv$ ra khỏi $H$ ta thu được hai thành phần liên thông $H_1,H_2$ (xem Figure 6(a)). Không mất tính tổng quát, ta giả sử tên trộm nằm trong $H_2$. Nếu $u\in H_2$, ta chỉ việc xóa các đỉnh của $H_2$ ra khỏi $H$. Nếu $u \in H_1$ ($v \in H_2$), khi đó ta di chuyển cả 3 cảnh sát sang $v$ (Figure 6(b)), và xóa các đỉnh của $H_2$ và $v$ ra khỏi $H$. Như vậy, ta đã quay trở lại cấu hình 1 với $H$ nhỏ hơn.
  2. Ngược lại, tồn tại ít nhất một đường đi từ $u$ tới $v$ không chứa cạnh $uv$ (xem Figure 6(c)). Gọi $P_2$ là đường đi ngắn nhất trong số các đường đi như vậy. Gọi $P_1 = \{u,v\}$. Dễ thấy $P_1,P_2$ đều thỏa mãn điều kiện trong cấu hình 2. Ta cho $s_1$ kiểm soát $P_1$ và $s_2$ kiểm soát $P_2$. Do chu trình $P_1\cup P_2$ chia mặt phẳng ra làm hai phần, không giảm tính tổng quát, ta giả sử tên trộm nằm bên ngòai $P_1\cup P_2$. Lúc này ta có thể xóa phần bên trong của $P_1\cup P_2$ ra khỏi $H$ (Figure 6(d)). Như vậy, ta đã chuyển $\mathcal{C}$ sang cấu hình 2 với $H$ nhỏ hơn.

config-1
Figure 6: Vùng màu xanh là vùng an toàn của kẻ trộm.

TH2: $\mathcal{C}$ đang ở cấu hình 2. Không mất tính tổng quát, giả sử trộm đang ở ngoài chu trình $P_1\cup P_2$. Gọi $H_1 = H\setminus V(P_1\cup P_2)$ là thành phần liên thông chứa tên trộm sau khi xóa $P_1,P_2$ ra khỏi vùng an toàn hiện tại $H$. Trước hết ta xét trương hợp tồn tại duy nhất 1 đỉnh $x \in P_1\cup P_2$ có cạnh nối tới các đỉnh của $H_1$. Ta sẽ di chuyển $s_3$ về $u$ và sau đó di chuyển $s_1,s_2$ về $x$; ta quay trở lại cấu hình 1 với $H = H_1$. (Không nhất thiết vùng an toàn phải bị thu hẹp trong bước này vì ta đã quay lại cấu hình 1 và như ta đã chỉ ra ở trên, nếu cảnh ở cấu hình 1 thì sau đó người chơi $\mathcal{C}$ luôn thu hẹp được $H$.)
config-21
Figure 7: Vùng màu xanh là vùng an toàn của kẻ trộm.

Do đó, ta có thể giả sử tồn tại ít nhất hai đỉnh trên $P_1\cup P_2$ có cạnh nối tới $H$. Như vậy, tồn tại ít nhất một đường đi từ $u$ tới $v$ chứa ít nhất 1 cạnh của $H$. Gọi $P_3$ là đường đi ngắn nhất trong số các đường đi đó. Gọi $x,y$ là đường đi con của $P_3$ sao cho $x, y \in P_1\cup P_2$ và không đỉnh nào khác của $P_3$ nằm trên $P_1\cup P_2$. Ta xét vài trường hợp:

  1. Hai đỉnh $x,y$ nằm trên $P_1$ (xem Figure 8(a)). Do $P_1[x,y]\cup P_3[x,y]$ là một chu trình, trộm chỉ có thể nằm bên trong hoặc bên ngoài chu trình này. Ta xét hai trường hợp: (i) Nếu trộm nằm bên trong chu trình $P_1[x,y]\cup P_3[x,y]$, ta cho $s_3$ kiểm soát $P_3[x,y]$ (đường màu đỏ trong FIgure 8(b)) và vẫn để $s_1$ kiểm soát $P_1[x,y]$ (đường màu xanh trong FIgure 8(b)). Do đó, ta có thể giải phóng $s_2$, và vùng an toàn của tên trộm thu hẹp lại (xem Figure 8(b)). (ii) Nếu trộm nằm bên ngoài chu trình $P_1[x,y]\cup P_3[x,y]$, ta cho $s_3$ kiểm soát $Q = P_1[u,x]\circ P_3[x,y]\circ P_1[y,v]$ (đường màu đỏ trong Figure 8(c)) và $s_2$ vẫn kiểm soát $P_2$ (đường màu xanh trong Figure 8(c)). Do đó, ta có thể giải phóng $s_1$, và vùng an toàn của trên trộm cũng bị thu hẹp lại.
    config-22
    Figure 8: Vùng màu xanh là vùng an toàn của kẻ trộm.
  2. Hai đỉnh $x,y \in P_2$, ta làm tương tự như (a).
  3. $x \in P_1, y \in P_2$ (xem Figure 9(a)). Gọi $C = P_3[x,y]\circ P_2[y,v]\circ P_1[v,x]$. Ta xét hai trường hợp: (i) Trộm nằm bên trong chu trình $C$. Gọi $Q = P_3[x,y]\circ P_2[y,v]$. Ta cho $s_3$ kiểm soát $Q$ (đường màu đỏ trong Figure 9(b)) và $s_1$ vẫn kiểm soát $P_1[y,v]$ (đường màu xanh trong Figure 9(b)). Do đó, ta có thể giải phóng $s_2$, và vùng an toàn của tên trộm thu hẹp lại. (ii) Trộm nằm ngoài chu trình $C$. Gọi $Q' = P_1[u,x]\circ P_3[x,y]$. Ta cho $s_3$ kiểm soát $Q'$ (đường màu đỏ trong Figure 9(c)) và $s_2$ vẫn kiểm soát $P_2[u,y]$ (đường màu xanh trong Figure 9(c)). Do đó, ta có thể giải phóng $s_1$, và vùng an toàn của tên trộm thu hẹp lại.

    config-23
    Figure 9: Vùng màu xanh là vùng an toàn của kẻ trộm.

Remark: Chò trơi bắt trộm được đề xuất trong bài báo của Aigner và Michael [1]. Trong bài báo đó, Aigner và Michael chứng minh rằng 3 canh sát có thể bắt được trộm trên mọi đồ thị phẳng. Chứng minh trình bày ở đây lấy ý tưởng từ đó. Adreaae [2] mở rộng kết quả của Aigner và Michale cho đồ thị minor-free.

Tham khảo

[1] M. Aigner and F. Michael. A Game of Cops and Robbers." Discrete Applied Mathematics 8.1 (1984): 1-12.
[2] T. Andreae. On a Pursuit Game Played on Graphs for which a Minor is Excluded. Journal of Combinatorial Theory, Series B 41.1 (1986): 37-47.

Tags: , , ,

« Older entries § Newer entries »