Lời mở đầu

Lý do gì mà blockchain và tiền ảo bitcoin có thể tồn tại và trụ vững tới giờ. Blockchain và lý thuyết trò chơi có liên quan gì với nhau. Mời các bạn cùng mình tìm hiểu về blockchain và cái mà nó sử dụng: lý thuyết trò chơi nhé.

Mục lục

  • Lý thuyết trò chơi là gì
  • Thành phần
  • Phân loại
  • Ví dụ: song đề tù nhân
  • Ma trận thưởng phạt

Lý thuyết trò chơi là gì?

Đầu tiên là nói về trò chơi, có luật và những người tham gia. Khi tham gia một trò chơi, thì mục tiêu của người chơi, tất nhiên là giành chiến thắng, tính toán đưa ra chiến thuật hợp lý, hiệu quả sao cho kết quả có lợi nhất cho mình. Từ đó trong toán học ứng dụng, đã khái quát thành khái niệm về lý thuyết trò chơi:

alt

Lý thuyết trò chơi là ngành nghiên cứu các tình huống chiến thuật trong đó các đối thủ lựa chọn các hành động khác nhau để cố gắng làm tối đa kết quả nhận được.

Thành phần
Một mô hình trò chơi gồm ít nhất 3 thành phần:

  • Players: người đưa ra các quyết định
  • Strategies:  Các quyết định mà họ muốn thực hiện
  • Payoff: kết quả của các chiến lược

Phân loại
Trong lý thuyết trò chơi, có 2 loại trò chơi:

  • Trò chơi có tổng bằng 0 (Zero sum game): là loại trò chơi mà người chơi này nhận phần thưởng từ sự mất mát của người chơi khác.
  • Trò chơi có tổng không bằng 0 (Non zero sum game): là loại trò chơi mà người chơi này nhận phần thưởng không đến từ sự mất mát của người chơi khác.

Ví dụ
Song đề tù nhân
Song đề tù nhân hay Thế tiến thoái lưỡng nan của người tù (Prisoner's Dilemma) là một trò chơi có tổng không bằng không (non-zero sum) trong lý thuyết trò chơi (game theory). Ví dụ đơn giản nhất của trò chơi là trường hợp có hai người chơi (gọi là tù nhân), mỗi người đều muốn giành thuận lợi cho mình, bất chấp tình trạng của người kia. Kết quả của trò chơi này không tối ưu. Nếu hai người đều hợp tác với nhau thì kết quả sẽ tốt nhất, nhưng mỗi người đều có động cơ để đào ngũ. Vì thế trò này mới được gọi là song đề.

Song đề tù nhân là một ví dụ thú vị để chúng ta bắt nhịp với vấn đề lý thuyết trò chơi. Một vấn đề khá lý thuyết. Để mấy thứ này đỡ khô khan hơn. Mời các bạn xem ví dụ bằng youtube về song đề tù nhân, đây là một clip rất thú vị và bí mật của nó được xuất hiện vào cuối clip:

Song đề tù nhân cổ điển được kể như sau:

Hai kẻ bị tình nghi là tội phạm bị cảnh sát bắt. Cảnh sát không có đủ chứng cớ để kết án họ, và đã cách ly họ. Cảnh sát gặp từng người một và làm cùng thoả thuận:

  • Nếu một người đổ tội mà người kia im lặng, người im lặng sẽ bị phạt 10 năm tù và người đổ tội sẽ được thả tự do.
  • Nếu cả hai đều im lặng, cảnh sát chỉ phạt được mỗi tù nhân 6 tháng tù vì một tội nhỏ khác.
  • Nếu cả hai đều phản bội, đổi tội cho đối phương, mỗi người sẽ bị phạt 2 năm.
    Trò chơi có thể được tóm tắt như sau:
Tù nhân A im lặng Tù nhân A đổ tội
Tù nhân B im lặng Cả hai bị 6 tháng tù B bị 10 năm tù; A được thả tự do
Tù nhân B đổ tội A bị 10 năm tù; B được thả tự do Cả hai bị 2 năm tù
Diễn giải tương tự bằng hình ảnh: ![alt](https://media1.britannica.com/eb-media/55/91955-004-AF92CB6A.jpg)

Ma trận thưởng phạt

  • Định nghĩa: ma trận thưởng phạt là ma trận thể hiện chiến thuật (các lựa chọn, hành vi) của người chơi và các kết quả mà họ sẽ nhận được tương ứng với các chiến thuật đó.

  • Ma trận thưởng phạt của song đề tù nhân có thể viết bằng nhiều cách, miễn là theo những nguyên lý sau đây:
    T > R > P > S
    Trong đó:

  • T là động cơ đào ngũ (temptation - khi đào ngũ và người kia hợp tác);

  • R là phần thưởng khi cả hai đều hợp tác (reward);

  • P là sự trừng phạt khi cả hai đều đào ngũ (punishment);

  • S là phần bị lãnh khi hợp tác và người kia đào ngũ (sucker's payoff).

Yêu cầu: các giá trị số phải được chọn để T + S < 2R để trò chơi được đáng kể(có ý nghĩa, nếu không sẽ quá dễ cho 2 người chơi).

Công thức trên bảo đảm rằng bất kỳ số nào được chọn, lựa chọn đào ngũ lúc nào cũng tốt hơn bất chấp lựa chọn của người kia (theo như lập luận ngay sau đây).
Bạn đào ngũ:

  • Người kia không đào ngũ -> bạn được tự do.
  • Người kia cũng đào ngũ -> bạn bị phạt 2 năm tù.
    Bạn không đào ngũ:
  • Người kia không đào ngũ -> bạn bị phạt 6 tháng tù.
  • Người kia đào ngũ -> bạn bị phạt 10 năm tù.

Theo nguyên lý này, chúng ta lấy được ma trận thưởng phạt chuẩn thường được nêu ra trong các bài viết về đề tài này. Trong cách trình bày này, số càng lớn thì kết quả càng tốt.

Ma trận thưởng theo thuật ngữ "thắng-thua"

Hợp tác Đào ngũ
Hợp tác Thắng-thắng Thua nhiều-thắng nhiều
Đào ngũ Thắng nhiều-thua nhiều Thua-thua

Như các bạn thấy, luật chơi đã được đưa ra như vậy, và mặc dù hợp tác là cách tốt nhất để win-win nhưng mọi người sẽ chọn đào ngũ.
Điều này giống như đi xe qua ngã tư đang tắc của Việt Nam.

Nhường đường, đúng làn Không nhường đường, không đúng làn
Nhường đường, đúng làn Đường được thông, mọi người được đi lại bình thường Người ở sau bị tắc-may mắn thì mình vọt lên trước (để lại mớ hỗn độn đằng sau)
Không nhường đường, không đúng làn Người ở sau bị tắc-may mắn thì mình vọt lên trước (để lại mớ hỗn độn đằng sau) Cả 2 bên đều chịu cảnh tắc đường
Nếu mình không nhanh mà vọt qua, có khả năng bị dính tắc đường -> vượt đèn đỏ, hoặc đèn chưa xanh đã đi -> tắc đường!!! Để tìm hiểu thêm về vấn đề điều tiết hành vi của người chơi. Chúng ta cùng tìm hiểu một chút về sự cân bằng Nash.

Sự cân bằng Nash

Trong luận án tiến sĩ của mình tại Princeton năm 1950, John Nash đã chứng minh rằng mọi trò chơi đều có ít nhất một điểm cân bằng.
Sự cân bằng Nash là một giải pháp chiến lược tối ưu nhất cho một trò chơi mà mỗi người chơi có được.

alt

Kết quả này đã cách mạng hóa lĩnh vực lý thuyết trò chơi và có ảnh hưởng rất lớn trong kinh tế học cũng như khoa học xã hội sau này. Vì vậy năm 1994, giải Nobel kinh tế được trao cho nhà toán học này để vinh danh những đóng góp của ông.
(mới nghe tưởng như đơn giản, mà được giải nobel chứng tỏ không hề đơn giản các bạn nhỉ. Thực tế ông này đầu óc ghê lắm, các bạn có thể xem bộ phim "A Beautiful Mind" để biết thêm về John F Nash)

Điều này có ý nghĩa to lớn trong một hệ thống máy tính phân tán như blockchain. Trên thực tế, blockchain là "không ăn gian" bởi vì toàn bộ giao thức nằm trong cân bằng Nash.

Vì vậy, quay trở lại bài toán song đề tù nhân. Cách giải quyết bài toán sao cho hợp lý nhất là gì? Đó chính là sự trừng phạt.
Sau khi tính toán thì rút ra kinh nghiệm thế này:
Chiến lược phạt thích hợp đó là:
"với mỗi -0.5 bị  lấy đi từ cộng đồng thì hình phạt sẽ là -7".

Trong trò chơi song đề tù nhân. Khi đưa ra hình phạt thích hợp về tội vu khống, thì 2 người chơi sẽ phải cân nhắc thêm về "sự trừng phạt", và cái giá cho sự nói dối có đáng để nói dối?
Tương tự như vậy, ở Việt Nam chúng ta hiện tại. Cái giá của sự vượt đèn đỏ, lấn làn so với cái giá phải trả cho mấy anh công an. Hiện tại là đáng hay không đáng? và nếu hình phạt nâng lên, thì lúc đó bạn sẽ thấy đáng hay không đáng?
Ví dụ tiếp theo là về vấn đề tham nhũng. nếu hình phạt được nâng lên, liệu tỉ lệ tham nhũng có giảm? Nếu luật được thực thi đúng cách. Tôi nghĩ là có! ;)

Ví dụ về áp dụng trong một xã hội? Công an được trả lương bởi thuế lấy từ người dân. Trong trường hợp này, chúng ta có một lực lượng đặc biệt để thực thi hình phạt và cách mà xã hội tham gia vào nó là trả các khoản thuế. Và nếu bạn không đóng thuế, thì bạn cũng phải chịu hình phạt.

Vậy cái gì khuyến khích cho xã hội cần sự trừng phạt? Tại sao họ sẽ muốn lãng phí các tiện ích (tiền, thời gian) của họ? Cách mà mọi người đã trả lời câu hỏi này đó là đưa ra hình phạt bắt buộc. Nói cách khác, nếu ai đó không tuân thủ luật đó của xã hội, thì chính họ sẽ trở thành tội phạm và phải chịu hình phạt. Không nộp thuế -> bị phạt tội trốn thuế!
-> Nhờ có sự trừng phạt thích đáng mà xã hội vận hành.

Kết luận về Nash

Khái niệm cân bằng Nash và trừng phạt có ý nghĩa quan trọng trong việc ngăn chặn và giữ chân các thợ mỏ trung thực. Chúng tôi sẽ khám phá điều đó trong một chút. Nhưng trước khi làm như vậy, chúng ta phải đi qua một số mô hình lý thuyết cơ bản hơn.

The Schelling (Focal) Point

"Điểm hội tụ" là điểm mà mọi người thường cùng cho ra cùng kết quả. vd: 1 lớp học được đặt câu hỏi sẽ hẹn nhau ở đâu khi gặp 1 người lạ vào ngày mai. Câu trả lời nhận được thường là: tại ga trung tâm thành phố.

Xem thử bài toán sau đây:
Có 4 số 7816239, 676716313, 100000000 và 871823719.
Số nào là số bạn nghĩ mọi người sẽ chọn?
Tôi nghĩ bạn sẽ chọn số 100000000. ^^

Grim Trigger

Cân bằng kích hoạt Grim
Chúng ta có một kịch bản. Chúng ta hãy tưởng tượng một tình huống xã hội nơi chế độ quân chủ vẫn còn tồn tại và người ta tin rằng vị vua được cai trị hơn những người khác vì một quyền thiêng liêng từ các vị thần. Tuy nhiên, trong một xã hội như thế này, nếu nhà vua bị giết sau đó thì sự thiêng liêng biến mất bởi vì mọi người sẽ hiểu rằng rằng nhà vua không phải là một đấng thiêng liêng. Điều này sẽ làm là nó sẽ mở ra cuộc chiến đẫm máu không hồi kết!

Cách duy nhất để ngăn chặn chu kỳ luẩn quẩn này là KHÔNG giết vua ở nơi đầu tiên và duy trì khái niệm "quyền thiêng liêng". Đây được gọi là Grim Trigger cân bằng. Hãy nghĩ về nó như là một trạng thái trong đó nếu bạn đi chệch thậm chí một chút bạn sẽ gây ra một chu kỳ vô tận của sự trừng phạt một cách đệ quy.

Bounded Rationality (biên hợp lý)
Theo nguyên lý trạng thái biên hợp lý (bounded rationality states) con người có xu hướng lúc nào cũng sử dụng giải pháp đơn giản nhất. Việc chuyển qua chain mới có vẻ là không cần thiết và phức tạp.
Hằng ngày Tuấn Anh đi mua bưởi ở cửa hàng nhà Lan Mai(tên nhân vật đã được thay đổi), lần nào Tuấn Anh cũng đều trả tiền đầy đủ, đến khi không có camera và không có chủ quán là Mai ở đó, Tuấn Anh vẫn không ăn trộm bưởi mà chờ đến khi chủ quán về -> con người có xu hướng đi theo lối mòn đơn giản.

Kết luận về phần tìm hiểu lý thuyết trò chơi

Ở trên chúng ta đã đi qua một lượt về các mô hình lý thuyết game. Trong giới hạn một bài viết thì trình bày thêm về sự liên quan tới block chain thì quá dài. Do đó mình xin trình bày tiếp ở bài viết tới. Chúng ta sẽ cùng xem block chain là gì cách chúng được áp dụng trong cryptocurrency (tiền kĩ thuật số)  và cách chúng giúp hệ thống chạy ổn định (keep the system floating) trước các loại hình tấn công ví dụ như double spending, để có thể được dùng như một đồng tiền đích thực.

Phần 2:
https://vietnamlab.vn/blog/2018/01/24/vi-sao-blockchain-duoc-tin-tuong-hay-ly-thuyet-tro-choi-va-blockchain-phan-2/

Link tham khảo

https://blockgeeks.com/guides/cryptocurrency-game-theory/
https://vi.wikipedia.org/wiki/Lý_thuyết_trò_chơi
https://vi.wikipedia.org/wiki/Song_đề_tù_nhân
https://vi.wikipedia.org/wiki/Cân_bằng_Nash