Bạn sẽ học được gì
- Mô hình hóa một tình huống nhiều tác nhân bằng trò chơi dạng chuẩn tắc và tìm cân bằng Nash
- Thiết kế cơ chế (mechanism design) khiến người chơi tự nguyện khai báo đúng thông tin riêng (truthful)
- Cài đặt và phân tích đấu giá Vickrey và cơ chế VCG cho bài toán phân bổ nhiều mặt hàng
- Đánh giá 'giá của sự ích kỷ' (Price of Anarchy) trong một hệ thống phi tập trung như định tuyến mạng
- Áp dụng thuật toán ghép cặp ổn định (stable matching) cho bài toán phân bổ hai phía
Nên học trước
Giới thiệu
Kinh tế học thuật toán nằm ở giao điểm của thiết kế thuật toán và lý thuyết trò chơi: thay vì giả định dữ liệu đầu vào cho sẵn, ta giả định đầu vào đến từ những tác nhân tự lợi, có thể nói dối nếu có lợi. Câu hỏi trung tâm: làm sao thiết kế luật chơi (cơ chế) để hành vi ích kỷ của từng cá nhân vẫn dẫn tới kết quả tốt cho cả hệ thống?
Hai vai trò của "thuật toán" trong kinh tế học
- Phân tích: một hệ thống phi tập trung có sẵn (định tuyến Internet, đấu giá quảng cáo) vận hành ra sao khi mọi người chơi vì lợi ích riêng? Price of Anarchy đo khoảng cách giữa kết quả ích kỷ và kết quả tối ưu tập trung.
- Thiết kế: ngược lại, ta thiết kế luật chơi — cơ chế đấu giá, thuật toán ghép cặp — để đạt mục tiêu mong muốn, thường là khiến nói thật trở thành chiến lược tốt nhất.
Đấu giá Vickrey: viên gạch nền tảng
Trong đấu giá giá thứ hai (Vickrey), người thắng trả giá cao thứ nhì, không phải giá mình khai — điều này khiến khai đúng bằng định giá thật là chiến lược tối ưu, bất kể người khác làm gì. Hiểu rõ vì sao cơ chế này truthful là chìa khóa để hiểu VCG, dạng tổng quát cho nhiều mặt hàng.
Đọc chứng minh nhiều hơn là code
Phần lớn bài tập ở đây là chứng minh (cân bằng tồn tại, cơ chế truthful, chặn Price of Anarchy) hơn là lập trình. Nên luyện đọc và tự vẽ lại các ví dụ phản chứng nhỏ (2 người chơi, 2 chiến lược) trước khi tổng quát hóa lên trường hợp nhiều người chơi.
Giáo trình & sách tham khảo
Xem tất cả trong tab SáchGiáo trình chính
Lecture Notes on Algorithmic Game Theory (CS364A, Stanford)
Tim Roughgarden
Vì sao chọn: 20 bài giảng đầy đủ, miễn phí, do chính Tim Roughgarden — một trong bốn chủ biên của Algorithmic Game Theory — công khai trên trang cá nhân. Chọn làm sách chính vì bám sát cả hai trục nội dung của lộ trình này (thiết kế cơ chế và Price of Anarchy) theo trình tự sư phạm rõ ràng, dễ tự học hơn một cuốn sách tham khảo tổng hợp.
Nên đọc: Bài 1–10 (Mechanism Design, Đấu giá, VCG) và Bài 11–20 (Price of Anarchy, Các khái niệm cân bằng)
Algorithmic Game Theory
Noam Nisan, Tim Roughgarden và 2 tác giả khác · 2007
Sách tham khảo nền tảng và toàn diện nhất của lĩnh vực, tập hợp bởi hơn 40 nhà nghiên cứu hàng đầu. Dùng để tra cứu sâu hơn hoặc đọc thêm góc nhìn khác cho từng chủ đề; bản tiếng Anh, không có bản đọc miễn phí hợp pháp.
Nên đọc: Các chương về Thiết kế cơ chế (Mechanism Design) và Đấu giá; các chương về Price of Anarchy trong định tuyến ích kỷ
Các bước học
Đăng nhập để đánh dấu các bước đã hoàn thành.
Bước 1: Trò chơi, chiến lược và cân bằng Nash
khoảng 6 giờHọc cách mô tả một trò chơi bằng người chơi, chiến lược và hàm lợi ích; tìm cân bằng Nash cho các trò chơi 2 người nhỏ. Tự lập bảng lợi ích và tìm mọi cân bằng Nash (thuần và hỗn hợp) cho trò chơi 'Chicken' hoặc 'Battle of the Sexes'.
- Đọc: Bài 1: Introduction and Examples — Lecture Notes on Algorithmic Game Theory (CS364A, Stanford)
Bước 2: Thiết kế cơ chế và đấu giá Vickrey
khoảng 7 giờHọc khái niệm truthful, đấu giá giá thứ hai (Vickrey) và Bổ đề Myerson mô tả cơ chế đơn-tham số tối ưu. Chứng minh bằng tay rằng khai đúng giá trị thật là chiến lược trội trong đấu giá Vickrey một mặt hàng.
- Đọc: Bài 2–3: Mechanism Design Basics, Myerson's Lemma — Lecture Notes on Algorithmic Game Theory (CS364A, Stanford)
- Đọc: Chương giới thiệu về Thiết kế cơ chế (Mechanism Design) và mô hình đấu giá — Algorithmic Game Theory
Bước 3: Cơ chế VCG cho phân bổ nhiều mặt hàng
khoảng 7 giờHọc cơ chế VCG tổng quát, cách tính khoản thanh toán dựa trên 'ngoại tác biên' và ứng dụng vào đấu giá phổ tần. Cài đặt cơ chế VCG cho bài toán phân bổ 3 mặt hàng cho 3 người mua với định giá cho trước, kiểm tra tính truthful bằng cách thử khai gian.
- Đọc: Bài 4, 7: Algorithmic Mechanism Design, VCG Mechanism — Lecture Notes on Algorithmic Game Theory (CS364A, Stanford)
Bước 4: Price of Anarchy trong định tuyến ích kỷ
khoảng 7 giờHọc mô hình định tuyến ích kỷ (selfish routing), nghịch lý Braess và cách chặn Price of Anarchy bằng lập luận smoothness. Dựng một ví dụ mạng nhỏ (3-4 cạnh) minh họa nghịch lý Braess và tính Price of Anarchy bằng tay.
- Đọc: Bài 11–12: Selfish Routing and the POA, Network Over-Provisioning — Lecture Notes on Algorithmic Game Theory (CS364A, Stanford)
- Đọc: Chương về Price of Anarchy và định tuyến ích kỷ (Selfish Routing) — Algorithmic Game Theory
Bước 5: Ghép cặp ổn định và các khái niệm cân bằng khác
khoảng 6 giờHọc thuật toán Gale-Shapley cho ghép cặp ổn định và mối liên hệ với trao đổi thận (kidney exchange). Cài đặt thuật toán Gale-Shapley cho bài toán ghép 5 sinh viên với 5 chỗ thực tập theo danh sách ưu tiên hai phía.
- Đọc: Bài 10: Kidney Exchange, Stable Matching — Lecture Notes on Algorithmic Game Theory (CS364A, Stanford)
Khái niệm chính
- Trò chơi dạng chuẩn tắc & Cân bằng Nash
- Mô tả trò chơi bằng tập người chơi, chiến lược và hàm lợi ích; cân bằng Nash là trạng thái không ai muốn đổi chiến lược một mình.
- Cơ chế truthful (Incentive-compatible)
- Cơ chế mà khai báo đúng sở thích hoặc định giá thật luôn là chiến lược tốt nhất cho mỗi người chơi, bất kể người khác làm gì.
- Đấu giá Vickrey (Second-price auction)
- Người trả giá cao nhất thắng nhưng chỉ trả giá cao thứ nhì; cơ chế đơn giản nhất chứng minh được là truthful.
- Cơ chế VCG (Vickrey-Clarke-Groves)
- Tổng quát hóa đấu giá Vickrey cho bài toán phân bổ nhiều mặt hàng/nhiều người, vẫn giữ tính truthful bằng cách tính khoản 'ngoại tác' mỗi người gây ra cho người khác.
- Giá của sự ích kỷ (Price of Anarchy)
- Tỉ số giữa chất lượng nghiệm tệ nhất tại cân bằng (mọi người chơi ích kỷ) và chất lượng nghiệm tối ưu nếu có một người điều phối trung tâm.
- Ghép cặp ổn định (Stable matching)
- Cách ghép cặp hai nhóm (như sinh viên–trường học) sao cho không tồn tại cặp nào cùng muốn bỏ ghép cặp hiện tại để đến với nhau; thuật toán Gale-Shapley luôn tìm được một ghép cặp ổn định.
Học xong để làm gì
- Đấu giá quảng cáo trực tuyến (Google Ads, Facebook Ads): cơ chế đấu giá gần với Vickrey cho mỗi lượt hiển thị quảng cáo
- Sàn thương mại điện tử và ứng dụng gọi xe: định giá động (dynamic pricing), ghép cung-cầu theo thời gian thực
- Xét tuyển đại học, phân bổ ký túc xá, ghép bác sĩ nội trú với bệnh viện bằng thuật toán ghép cặp ổn định
- Định tuyến mạng và giao thông: phân tích Price of Anarchy khi mỗi gói tin hoặc xe chọn đường đi ích kỷ
- Đấu giá phổ tần số của chính phủ cho các nhà mạng viễn thông — ứng dụng quy mô hàng tỷ đô la của cơ chế VCG
Câu hỏi thường gặp
Cần học kinh tế học trước không?
Không cần; môn học tự giới thiệu các khái niệm kinh tế cần thiết (lợi ích, cân bằng) từ góc nhìn thuật toán. Nền tảng quan trọng hơn là tư duy chứng minh của môn thiết kế thuật toán.
Lý thuyết trò chơi cổ điển khác gì kinh tế học thuật toán?
Lý thuyết trò chơi cổ điển hỏi 'cân bằng là gì'; kinh tế học thuật toán còn hỏi 'tính cân bằng đó nhanh cỡ nào' và 'thiết kế luật chơi ra sao để đạt mục tiêu' — luôn có góc nhìn độ phức tạp tính toán.
Tại sao đấu giá giá thứ hai lại tốt hơn đấu giá giá thứ nhất?
Ở đấu giá giá thứ nhất, người chơi phải đoán ý người khác để chọn giá khai thấp hơn giá trị thật; ở đấu giá giá thứ hai, khai đúng giá trị thật luôn là lựa chọn an toàn nhất — đơn giản hơn để phân tích và công bằng hơn để cài đặt.
Học xong áp dụng vào đâu?
Thiết kế hệ thống đấu giá quảng cáo, định giá động cho nền tảng chia sẻ, hoặc các hệ thống ghép cặp như tuyển sinh, phân bổ tài nguyên trong đám mây.
