Kinh tế học thuật toán: khi đầu vào của thuật toán biết tính toán
Thuật toán cho một thế giới ai cũng vì mình: cân bằng Nash, đấu giá khai thật, ghép cặp ổn định, giá của sự ích kỷ — và nên bắt đầu học từ đâu.
Ban biên tập OpenER
Cập nhật 18/11/2026 · 20 phút đọc · CC BY 4.0
Mỗi mùa tuyển sinh, hàng trăm nghìn thí sinh cùng băn khoăn: xếp ngành mơ ước lên nguyện vọng 1, hay xếp một ngành "chắc đỗ" lên trước cho an toàn? Mỗi lần ai đó gõ "điện thoại cũ" vào Google, một phiên đấu giá giữa các nhà quảng cáo diễn ra và kết thúc trước khi trang kết quả kịp hiện. Còn ứng dụng chỉ đường chỉ cho mỗi người con đường nhanh nhất cho riêng người đó — vậy mà giờ tan tầm, cả thành phố vẫn kẹt.
Ba chuyện có chung một điểm: đầu vào của thuật toán đến từ con người, và ai cũng muốn điều tốt nhất cho mình. Thuật toán sắp xếp không phải lo các con số nói dối; nhưng thí sinh có thể khai nguyện vọng khác ý thật, nhà quảng cáo có thể trả giá thấp hơn giá trị thật. Kinh tế học thuật toán (algorithmic economics), còn gọi là lý thuyết trò chơi thuật toán (algorithmic game theory), là môn học về cách thiết kế thuật toán cho một thế giới như vậy — nơi luật chơi phải khiến nói thật trở thành nước đi khôn nhất.
Trước khi có thiết kế luật chơi
Từ xưa, con người chia những thứ khan hiếm theo vài cách quen thuộc: ai đến trước được trước, ai quen biết được ưu tiên, hoặc mặc cả từng người. Luật hở chỗ nào, người ta lách vào chỗ đó. Ai từng sống qua thời bao cấp đều nhớ cảnh xếp hàng mua gạo, mua dầu bằng tem phiếu, và chuyện đặt một viên gạch thay người để giữ chỗ. Luật "đến trước được trước" chẳng nói gì về viên gạch.
Biến câu hỏi "người ta sẽ lách luật thế nào" thành toán học là việc của thế kỷ XX:
- Lý thuyết trò chơi (game theory). Năm 1928, John von Neumann chứng minh định lý minimax cho trò chơi hai người đối đầu, được bên này thì mất bên kia — họ hàng của minimax mà bài Nhập môn trí tuệ nhân tạo dùng để chơi cờ ca-rô. Năm 1944, ông cùng nhà kinh tế Oskar Morgenstern viết Theory of Games and Economic Behavior, mở ra ngành toán về những quyết định phụ thuộc lẫn nhau.
- Cân bằng Nash. Năm 1950, nghiên cứu sinh John Nash ở Princeton chứng minh trò chơi nào có hữu hạn người chơi và lựa chọn cũng có ít nhất một trạng thái mà không ai muốn đổi một mình (nếu cho phép chọn ngẫu nhiên). Ông nhận Nobel kinh tế năm 1994.
- Thiết kế cơ chế (mechanism design). Năm 1961, William Vickrey chỉ ra một kiểu đấu giá mà người mua có lợi nhất khi khai đúng giá trị thật. Leonid Hurwicz, Eric Maskin và Roger Myerson dựng thành lý thuyết: thay vì đoán người ta chơi ra sao, hãy thiết kế luật chơi để kết quả tốt. Vickrey nhận Nobel năm 1996, ba người kia năm 2007.
- Ghép cặp ổn định. Năm 1962, David Gale và Lloyd Shapley công bố bài báo "College Admissions and the Stability of Marriage" (tuyển sinh đại học và sự ổn định của hôn nhân). Hơn hai mươi năm sau, Alvin Roth phát hiện chương trình ghép bác sĩ nội trú với bệnh viện ở Mỹ, chạy từ năm 1952, dùng một thuật toán về cơ bản giống hệt. Roth và Shapley nhận Nobel năm 2012.
- Nhà kinh tế làm kỹ sư. Năm 1994, Ủy ban Truyền thông Liên bang Mỹ (FCC) bắt đầu bán giấy phép sóng di động bằng kiểu đấu giá nhiều vòng mà Paul Milgrom và Robert Wilson góp phần thiết kế. Hai ông nhận Nobel năm 2020.
- Khoa học máy tính bước vào — quanh năm 2000. Năm 1999, Noam Nisan và Amir Ronen đặt ra cụm từ "thiết kế cơ chế thuật toán (algorithmic mechanism design)"; Elias Koutsoupias và Christos Papadimitriou đo xem sự ích kỷ làm hệ thống tệ đi bao nhiêu. Năm 2002, Google chuyển sang bán quảng cáo tìm kiếm theo lượt bấm, xếp chỗ bằng đấu giá. Năm 2012, bốn người trên cùng Tim Roughgarden và Éva Tardos nhận giải Gödel, giải lớn của khoa học máy tính lý thuyết.
Đặt cạnh nhau:
Luật không tính tới người chơi | Luật thiết kế cho người chơi tự lợi | |
|---|---|---|
Chia thứ khan hiếm | Ai đến trước, ai nhanh tay, ai quen biết | Đấu giá, ghép cặp, bốc thăm — có tính chất chứng minh được |
Khi có người nói dối | Người thật thà chịu thiệt | Nói thật là chiến lược tốt nhất |
Dự đoán hệ thống | Chờ xem chuyện gì xảy ra | Tính cân bằng, đo nó kém tốt nhất bao nhiêu |
Cách chia "ai nhanh tay được trước" vẫn còn nguyên ở một chỗ quen thuộc: bán vé concert. Mỗi lần một ca sĩ nổi tiếng mở bán vé ở Hà Nội hay TP.HCM, trang bán vé thường nghẽn ngay phút đầu, rồi vé hiện ra trên các hội nhóm với giá gấp mấy lần. Vé không tới tay người mê ca sĩ nhất, mà tới người mạng nhanh, có phần mềm tự bấm, hoặc mua để bán lại. Bốc thăm, vé ghi tên, đấu giá — mỗi cách được cái này, mất cái kia; chọn cách nào là câu hỏi của môn này.
Môn này trả lời câu hỏi gì
Môn thuật toán cổ điển hỏi: cho đầu vào, tính đầu ra cho nhanh và đúng. Môn này thêm một giả định khó chịu: đầu vào do những người tự lợi khai ra, và họ khai thế nào lại phụ thuộc vào thuật toán. Từ đó có ba câu hỏi:
- Dự đoán: khi ai cũng chơi vì mình, hệ thống dừng ở đâu? Tính ra trạng thái đó có nhanh không?
- Đo lường: trạng thái đó kém phương án của một người điều phối biết hết bao nhiêu?
- Thiết kế: luật chơi nào khiến mỗi người tự nguyện khai thật, mà kết quả vẫn tốt và máy vẫn tính kịp?
Vì sao người học khoa học máy tính cần môn này? Vì sàn thương mại điện tử, ứng dụng gọi xe, chợ quảng cáo, hệ thống tuyển sinh đều là những cái chợ do code điều hành, và người dùng sẽ học cách lách bất cứ luật nào bạn viết. Đoán trước được họ lách thế nào là một kỹ năng thiết kế, như đoán trước được thuật toán chạy mất bao lâu.
Năm ý tưởng cốt lõi
1. Cân bằng Nash: không ai muốn đổi một mình
Hai xe bán nước dừa trên bãi biển Mỹ Khê. Khách nằm rải đều dọc bãi, ai khát thì ra xe gần mình nhất. Mỗi chủ xe muốn đứng chỗ đông khách nhất. Họ sẽ đứng ở đâu?
Một trò chơi (game) gồm người chơi, lựa chọn của mỗi người, và cái lợi mỗi người nhận được — phụ thuộc vào lựa chọn của tất cả. Phản ứng tốt nhất (best response) là lựa chọn có lợi nhất cho mình khi đã biết người kia chọn gì. Thử cho hai chủ xe lần lượt dời sang chỗ tốt nhất:
CHO = range(11) # bãi biển chia 11 chỗ, mỗi chỗ một nhóm khách
def khach(a, b):
"""Số nhóm khách của xe đứng ở a, khi xe kia đứng ở b: khách ra xe gần mình nhất."""
tong = 0
for k in CHO:
if abs(k - a) < abs(k - b):
tong += 1
elif abs(k - a) == abs(k - b):
tong += 0.5 # cách đều hai xe thì chia đôi
return tong
def phan_ung(b):
"""Phản ứng tốt nhất: chỗ đứng đông khách nhất cho mình khi đối thủ đứng ở b."""
return max(CHO, key=lambda a: khach(a, b))
a, b = 0, 10 # sáng ra, hai xe đứng ở hai đầu bãi
while True:
a_moi = phan_ung(b)
b_moi = phan_ung(a_moi)
print(a_moi, b_moi)
if (a_moi, b_moi) == (a, b):
break # không ai muốn dời chỗ nữa
a, b = a_moi, b_moi
def di_bo(a, b): # tổng quãng đường khách phải đi bộ
return sum(min(abs(k - a), abs(k - b)) for k in CHO)
print("cân bằng:", di_bo(a, b), "| ít nhất có thể:", min(di_bo(x, y) for x in CHO for y in CHO))9 8
7 6
5 5
5 5
cân bằng: 30 | ít nhất có thể: 15Đứng ở hai đầu bãi thì xe nào cũng muốn nhích vào trong giành khách; cứ thế hai xe nhảy cóc qua nhau tới khi cùng đứng giữa bãi, mỗi xe một nửa số khách. Tại đó không ai muốn dời đi một mình: nhích sang bên nào cũng mất khách. Đó là cân bằng Nash (Nash equilibrium); thử hết 121 cặp chỗ đứng thì đây là cân bằng duy nhất. Chuyện đối thủ dồn về "chính giữa" được Harold Hotelling nêu năm 1929, và hay được dùng để giải thích vì sao hai cửa hàng cùng loại thường mở sát nhau.
Dòng cuối mới là bài học: ở cân bằng, khách đi bộ tổng cộng 30 bước; nếu hai xe đứng ở khoảng một phần tư và ba phần tư bãi, chỉ 15. Cân bằng là nơi hệ thống dừng lại, không phải nơi tốt nhất — ý thứ tư sẽ đo khoảng cách đó.
Còn một câu hỏi rất "máy tính": cân bằng luôn tồn tại, nhưng tìm nó có dễ không? Năm 2006, Constantinos Daskalakis, Paul Goldberg và Christos Papadimitriou, rồi Xi Chen và Xiaotie Deng, chứng minh rằng tìm cân bằng Nash của trò chơi tổng quát — kể cả chỉ hai người — là bài toán PPAD-đầy đủ (PPAD-complete), nhiều khả năng không có thuật toán nhanh. Máy tính còn không tìm nổi, thì khó tin một thị trường sẽ luôn tự tìm ra.
2. Đấu giá: khiến nói thật là có lợi nhất
Bạn muốn mua một món đồ đáng 100 triệu đồng với bạn, trong một phiên đấu giá kín (sealed-bid auction): mỗi người bỏ một phong bì, giá cao nhất thắng. Nếu người thắng trả đúng giá mình bỏ — đấu giá giá thứ nhất (first-price auction) — thì bỏ 100 triệu có thắng cũng chẳng lời đồng nào; phải bỏ thấp hơn, nhưng thấp bao nhiêu thì tùy việc đoán người khác. Vickrey sửa đúng một chỗ: người thắng chỉ trả giá cao thứ hai — đấu giá giá thứ hai (second-price auction). Thử với 100.000 phiên, mỗi phiên ba đối thủ bỏ giá ngẫu nhiên:
import random
def loi(gia_tri, bo_gia, doi_thu, kieu):
"""Mình được lợi bao nhiêu (triệu đồng): thắng thì giá trị trừ số tiền phải trả, thua thì 0."""
cao_nhat_khac = max(doi_thu)
if bo_gia <= cao_nhat_khac:
return 0 # thua (hòa cũng tính là thua cho gọn)
tra = cao_nhat_khac if kieu == "giá thứ hai" else bo_gia
return gia_tri - tra
random.seed(2026)
phien = [[random.randint(0, 150) for _ in range(3)] for _ in range(100_000)] # 3 đối thủ mỗi phiên
gia_tri = 100 # món hàng đáng 100 triệu với mình
for kieu in ("giá thứ hai", "giá thứ nhất"):
for bo_gia in (60, 80, 100, 120):
tb = sum(loi(gia_tri, bo_gia, d, kieu) for d in phien) / len(phien)
print(f"{kieu}, bỏ {bo_gia}: lợi trung bình {tb:.2f}")
# Không cần trung bình: thử MỌI giá cao nhất của đối thủ và MỌI mức bỏ giá
hon = [(c, b) for c in range(151) for b in range(201)
if loi(gia_tri, b, [c], "giá thứ hai") > loi(gia_tri, gia_tri, [c], "giá thứ hai")]
print("Có trường hợp nào khai khác lại lợi hơn khai thật?", hon)giá thứ hai, bỏ 60: lợi trung bình 3.43
giá thứ hai, bỏ 80: lợi trung bình 5.98
giá thứ hai, bỏ 100: lợi trung bình 7.38
giá thứ hai, bỏ 120: lợi trung bình 5.25
giá thứ nhất, bỏ 60: lợi trung bình 2.47
giá thứ nhất, bỏ 80: lợi trung bình 2.97
giá thứ nhất, bỏ 100: lợi trung bình 0.00
giá thứ nhất, bỏ 120: lợi trung bình -10.03
Có trường hợp nào khai khác lại lợi hơn khai thật? []Với đấu giá giá thứ hai, bỏ đúng 100 cho lợi trung bình cao nhất. Dòng cuối còn mạnh hơn: thử mọi trường hợp, không lần nào khai khác lại lợi hơn khai thật. Lý do: giá bạn bỏ chỉ quyết định thắng hay thua, không quyết định trả bao nhiêu. Bỏ thấp hơn giá trị thì có lúc vuột món hàng mua được có lời; bỏ cao hơn thì có lúc thắng mà trả quá giá trị. Khai thật là chiến lược trội (dominant strategy) — tốt nhất bất kể người khác làm gì. Cơ chế như vậy gọi là trung thực (truthful). Ở đấu giá giá thứ nhất thì khác: bỏ 80 đang lợi hơn bỏ 60, nhưng con số tốt nhất đổi ngay khi đối thủ đổi.
Trên eBay, bạn nhập mức giá tối đa và hệ thống tự trả giá thay bạn, mỗi lần chỉ nhỉnh hơn người cao thứ hai một bước — gần như đấu giá giá thứ hai. Đấu giá trả giá lên, như đấu giá biển số ô tô trực tuyến ở Việt Nam từ năm 2023, về lý thuyết cũng vậy: người thắng chỉ trả quanh mức mà đối thủ trụ lâu nhất bỏ cuộc. Tổng quát hóa cho nhiều món hàng là cơ chế VCG (Vickrey–Clarke–Groves): mỗi người thắng trả đúng phần thiệt mình gây ra cho những người còn lại — nhưng khi người mua muốn trọn gói nhiều món, riêng việc tìm cách chia tốt nhất đã là bài toán NP-khó, và thiết kế cơ chế thành bài toán thuật toán thật sự. Quảng cáo tìm kiếm thì dùng một biến thể gọn hơn, đấu giá giá thứ hai tổng quát (generalized second-price — GSP): chạy nhanh, dễ hiểu, nhưng không hoàn toàn trung thực.
3. Ghép cặp ổn định: xét tuyển mà không ai muốn "bỏ trốn"
Có những cái chợ không dùng tiền, như chợ giữa thí sinh và trường. Một cách ghép là ổn định (stable) nếu không có cặp bất ổn (blocking pair) — một thí sinh thích một trường hơn chỗ mình được xếp, trong khi trường đó còn chỗ hoặc muốn nhận thí sinh ấy hơn một người đang nhận. Có cặp như thế, sớm muộn họ sẽ bỏ kết quả chung để tự đến với nhau.
Thuật toán của Gale và Shapley, gọi là chấp nhận hoãn lại (deferred acceptance): mỗi thí sinh nộp vào nguyện vọng cao nhất chưa nộp; mỗi trường tạm giữ những người điểm cao nhất trong chỉ tiêu và trả lại số còn lại; ai bị trả thì nộp tiếp nguyện vọng sau. Không trường nào nhận chính thức cho tới lúc cuối — chữ "hoãn lại" là vì thế. Thử với năm thí sinh và ba trường, mỗi trường xét theo tổ hợp môn của mình:
from itertools import permutations
nguyen_vong = { # mỗi thí sinh xếp trường từ thích nhất tới kém nhất
"An": ["Kỹ thuật", "Kinh tế", "Ngoại ngữ"],
"Bình": ["Kỹ thuật", "Ngoại ngữ", "Kinh tế"],
"Chi": ["Ngoại ngữ", "Kỹ thuật", "Kinh tế"],
"Dũng": ["Kỹ thuật", "Kinh tế", "Ngoại ngữ"],
"Hà": ["Ngoại ngữ", "Kinh tế", "Kỹ thuật"],
}
diem = { # mỗi trường xét theo tổ hợp môn của mình
"Kỹ thuật": {"An": 26, "Bình": 25, "Chi": 28, "Dũng": 27, "Hà": 21}, # Toán, Lý, Hóa
"Kinh tế": {"An": 25, "Bình": 26, "Chi": 24, "Dũng": 27, "Hà": 23}, # Toán, Lý, Anh
"Ngoại ngữ": {"An": 22, "Bình": 27, "Chi": 24, "Dũng": 21, "Hà": 26}, # Toán, Văn, Anh
}
chi_tieu = {"Kỹ thuật": 2, "Kinh tế": 2, "Ngoại ngữ": 1}
def xet_tuyen(nguyen_vong, ke=False):
da_nop = {ts: 0 for ts in nguyen_vong} # mỗi thí sinh đã nộp tới nguyện vọng thứ mấy
giu = {tr: [] for tr in chi_tieu} # thí sinh mỗi trường đang tạm giữ
cho = list(nguyen_vong) # thí sinh chưa có chỗ
while cho:
ts = cho.pop(0)
if da_nop[ts] == len(nguyen_vong[ts]):
continue # hết nguyện vọng: trượt
tr = nguyen_vong[ts][da_nop[ts]]
da_nop[ts] += 1
giu[tr].append(ts)
giu[tr].sort(key=lambda x: -diem[tr][x])
if len(giu[tr]) > chi_tieu[tr]:
bi_tra = giu[tr].pop() # quá chỉ tiêu: trả lại người điểm thấp nhất
cho.append(bi_tra)
if ke and bi_tra != ts:
print(f" {tr} trả {bi_tra} về để giữ {ts}")
return {ts: tr for tr, ds in giu.items() for ts in ds}
ket_qua = xet_tuyen(nguyen_vong, ke=True)
print(ket_qua)
# Cặp bất ổn: thí sinh thích trường kia hơn, và trường kia cũng muốn nhận thí sinh đó
bat_on = []
for ts, ds in nguyen_vong.items():
for tr in ds[:ds.index(ket_qua[ts])]:
da_nhan = [x for x, t in ket_qua.items() if t == tr]
if len(da_nhan) < chi_tieu[tr] or any(diem[tr][ts] > diem[tr][x] for x in da_nhan):
bat_on.append((ts, tr))
print("Cặp bất ổn:", bat_on)
# Có ai được lợi khi xếp nguyện vọng khác sở thích thật không?
for ts, that in nguyen_vong.items():
for khai in permutations(that):
kq = xet_tuyen({**nguyen_vong, ts: list(khai)})
if ts in kq and that.index(kq[ts]) < that.index(ket_qua[ts]):
print(ts, "được lợi khi khai", khai)
print("Đã thử mọi cách xếp nguyện vọng khác của từng thí sinh.") Kỹ thuật trả Bình về để giữ Dũng
Ngoại ngữ trả Chi về để giữ Hà
Ngoại ngữ trả Hà về để giữ Bình
Kỹ thuật trả An về để giữ Chi
{'Chi': 'Kỹ thuật', 'Dũng': 'Kỹ thuật', 'An': 'Kinh tế', 'Hà': 'Kinh tế', 'Bình': 'Ngoại ngữ'}
Cặp bất ổn: []
Đã thử mọi cách xếp nguyện vọng khác của từng thí sinh.Bình bị Dũng đẩy khỏi Kỹ thuật, sang Ngoại ngữ thì đẩy Hà ra; Chi bị Ngoại ngữ trả về, sang Kỹ thuật thì đẩy An ra… Cuối cùng không còn cặp bất ổn nào — Gale và Shapley chứng minh thuật toán luôn dừng với một kết quả ổn định. Đoạn code cuối kiểm một tính chất được chứng minh đầu thập niên 1980: với bên nộp đơn, xếp nguyện vọng đúng sở thích thật luôn là tốt nhất — đảo thứ tự kiểu nào, không ai được lợi hơn.
Nhìn theo kiểu quen thuộc: điểm của người cuối cùng mỗi trường giữ là điểm chuẩn — Kỹ thuật 27, Kinh tế 23, Ngoại ngữ 27 — và mỗi bạn đỗ đúng nguyện vọng cao nhất mà mình đủ điểm chuẩn. Xét tuyển đại học ở Việt Nam chạy theo cùng tinh thần: thí sinh xếp nguyện vọng theo thứ tự ưu tiên; mỗi ngành xét thí sinh theo điểm, không phân biệt họ đặt nó ở nguyện vọng thứ mấy; rồi hệ thống chung của Bộ Giáo dục và Đào tạo lọc ảo nhiều lần để mỗi người chỉ đỗ một nguyện vọng cao nhất. Lọc ảo nhằm chặn đúng chuyện "xếp gạch giữ chỗ" — viên gạch thời bao cấp trở lại, lần này trong một bài toán máy tính. Và lời khuyên mỗi mùa tuyển sinh, "cứ xếp ngành mình thích nhất lên đầu", trong mô hình này là một định lý.
4. Giá của sự ích kỷ: thêm đường mà lại thêm kẹt
Mỗi sáng có 4.000 xe máy đi từ khu đô thị A ở rìa một thành phố tưởng tượng vào trung tâm B, theo một trong hai tuyến: phố nhỏ A→X rồi vành đai X→B, hoặc vành đai A→Y rồi phố nhỏ Y→B. Vành đai rộng nhưng xa, lúc nào cũng mất 45 phút. Phố nhỏ gần nhưng hẹp: có n xe đi thì mất n/100 phút. Rồi thành phố xây một cây cầu ngắn nối X với Y, đi qua gần như không mất thời gian.
XE = 4000
def thoi_gian(a, b, c):
"""Số phút của mỗi tuyến khi a xe đi A-X-B, b xe đi A-Y-B, c xe đi A-X-Y-B (qua cầu mới)."""
hem_X = (a + c) / 100 # phố nhỏ A→X: càng đông càng chậm
hem_Y = (b + c) / 100 # phố nhỏ Y→B
return hem_X + 45, 45 + hem_Y, hem_X + 0 + hem_Y # vành đai: luôn 45 phút; cầu: 0 phút
print("Chưa có cầu:", thoi_gian(2000, 2000, 0)[:2])
# Có cầu. Từng người đổi sang tuyến nhanh hơn cho riêng mình, tới khi không ai muốn đổi nữa
xe = [2000, 2000, 0]
con_doi = True
while con_doi:
con_doi = False
for tu in range(3):
for sang in range(3):
if tu != sang and xe[tu] > 0:
thu = xe.copy()
thu[tu] -= 1
thu[sang] += 1
if thoi_gian(*thu)[sang] < thoi_gian(*xe)[tu]:
xe, con_doi = thu, True
print("Có cầu, ai cũng tự chọn:", xe, thoi_gian(*xe))
def trung_binh(a, b, c):
t = thoi_gian(a, b, c)
return (a * t[0] + b * t[1] + c * t[2]) / XE
tot = min(((a, b, XE - a - b) for a in range(0, XE + 1, 50) for b in range(0, XE + 1 - a, 50)),
key=lambda p: trung_binh(*p))
print("Có cầu, có người điều phối:", tot, trung_binh(*tot))Chưa có cầu: (65.0, 65.0)
Có cầu, ai cũng tự chọn: [0, 0, 4000] (85.0, 85.0, 80.0)
Có cầu, có người điều phối: (1750, 1750, 500) 64.6875Chưa có cầu, xe chia đôi, ai cũng mất 65 phút. Có cầu, đường "phố nhỏ – cầu – phố nhỏ" lúc đầu nhanh hơn hẳn, nên từng người chuyển sang, tới khi cả 4.000 xe dồn vào hai phố nhỏ và mỗi người mất 80 phút. Không ai muốn quay về tuyến cũ, vì giờ tuyến cũ mất 85 phút. Thêm một con đường, ai cũng chậm thêm 15 phút. Đây là nghịch lý Braess (Braess's paradox), do nhà toán học Đức Dietrich Braess nêu năm 1968.
Cây cầu không vô dụng: một người điều phối biết hết, chỉ cho 500 xe qua cầu, sẽ kéo thời gian trung bình xuống khoảng 64,7 phút. Tỷ số giữa kết quả ở cân bằng và kết quả tốt nhất — ở đây 80 / 64,7 ≈ 1,24 — gọi là giá của sự ích kỷ (price of anarchy), tên do Papadimitriou đặt năm 2001. Roughgarden và Tardos chứng minh: trong mạng giao thông bất kỳ, nếu thời gian đi mỗi đoạn tăng tuyến tính theo số xe, cân bằng không bao giờ tệ hơn tối ưu quá 4/3.
Ứng dụng chỉ đường chỉ cho mỗi người tuyến nhanh nhất cho riêng người đó — định tuyến ích kỷ ở quy mô cả thành phố. Khi nào thế là đủ, khi nào cần một luật chung như thu phí giờ cao điểm?
5. Chia cho công bằng: anh cắt, em chọn
Không phải lúc nào cũng có tiền hay điểm số để xếp hạng. Hai anh em chia một chiếc bánh chưng, người thích nhiều đỗ, người thích nhiều thịt. Cách cổ xưa nhất: anh cắt, em chọn (cut and choose). Người cắt chia thành hai phần mà trong mắt mình ngang nhau, vì biết phần nào hơn sẽ bị lấy mất; người chọn lấy phần mình thích hơn. Không ai thèm phần của người kia — tính chất gọi là không ganh tị (envy-free) — mà chẳng ai cần biết người kia thích gì.
Với ba người trở lên thì khó hơn hẳn: tới năm 2016, Haris Aziz và Simon Mackenzie mới tìm ra quy trình chia không ganh tị cho số người bất kỳ mà số bước có giới hạn — một giới hạn lớn khủng khiếp. Ngoài đời, nó ở rất gần: ba bạn thuê chung căn hộ, một phòng có ban công, một phòng không cửa sổ — chia tiền thuê thế nào để không ai thấy thiệt? Trang web Spliddit (2014) của nhóm Ariel Procaccia trả lời đúng những câu như vậy bằng thuật toán, miễn phí.
Kinh tế học thuật toán nằm ở đâu trong chồng tầng
Trong chồng tầng của bài Từ electron đến ứng dụng, môn này nằm ở tầng trên cùng, chỗ phần mềm gặp con người — và coi con người là một phần của hệ thống, có mục tiêu riêng:
- Thiết kế và phân tích thuật toán cho ngôn ngữ đo độ khó: cân bằng nào tính nhanh được, cơ chế nào NP-khó.
- Tối ưu hóa: định lý minimax là họ hàng gần của đối ngẫu trong quy hoạch tuyến tính; "người điều phối biết hết" ở ý thứ tư là lời giải của một bài toán tối ưu.
- Mạng máy tính: kiểm soát tắc nghẽn của TCP chỉ chạy được khi mỗi máy tự kiềm chế, dù chẳng gì bắt nó phải thế — đúng kiểu tình huống môn này nghiên cứu.
- Hệ phân tán giả định một số máy có thể nói dối tùy ý; môn này giả định ai cũng có thể nói dối, nhưng chỉ khi có lợi. Blockchain kết hợp cả hai: trả công sao cho làm đúng luật có lợi hơn gian lận.
Đưa lên
Một luật chơi — đấu giá, ghép cặp, định giá — mà người dùng tự lợi vẫn có lợi nhất khi khai thật, kèm dự đoán hệ thống dừng ở đâu và kém tốt nhất bao nhiêu.
Giấu đi
Tính toán và chiến thuật của từng người. Khi khai thật là chiến lược trội, không ai còn phải đoán người khác.
Học trước và học sau
· 4 mônThiết kế và phân tích thuật toán
Design and Analysis of Algorithms
Độ phức tạp, NP-khó và nhất là thói quen chứng minh. Nên học trước.
Xác suất và thống kê
Probability and Statistics
Kỳ vọng và phân phối: giá của đối thủ không biết trước, chiến lược chọn ngẫu nhiên, doanh thu kỳ vọng. Nên học trước.
Tối ưu hóa
Optimization
Quy hoạch tuyến tính và đối ngẫu, xương sống của nhiều chứng minh ở đây — học trước hoặc song song.
Nhập môn trí tuệ nhân tạo
Introduction to Artificial Intelligence
Minimax, độ hữu ích kỳ vọng, tác tử hợp lý — cùng gốc, nhưng nhìn từ phía một tác tử.
Xem chủ đề trên OpenER: Introduction to Artificial Intelligence
Ứng dụng thật và nghề nghiệp
- Quảng cáo trực tuyến: mỗi lượt tìm kiếm có quảng cáo là một phiên đấu giá chớp nhoáng; quảng cáo là nguồn thu lớn nhất của Google và Meta.
- Thương mại điện tử, gọi xe: tăng giá giờ cao điểm để kéo thêm tài xế ra đường, chống đánh giá ảo; còn tìm tài xế gần nhất là chuyện của bài Tính toán di động và cảm biến.
- Ghép cặp không dùng tiền: chương trình ghép bác sĩ nội trú của Mỹ được Roth và Elliott Peranson thiết kế lại cuối thập niên 1990; New York (2003) và Boston (2005) xếp học sinh vào trường bằng chấp nhận hoãn lại; các chương trình trao đổi thận nối những cặp người hiến – người nhận không hợp nhau thành vòng hiến chéo.
- Đấu giá tài nguyên công: tháng 3/2024, Việt Nam lần đầu đấu giá băng tần cho mạng 5G, thu hơn 10.000 tỷ đồng. Phiên đấu giá năm 2016–2017 của Mỹ mua lại sóng truyền hình để bán cho nhà mạng; mỗi bước phải nhờ bộ giải SAT (Logic cho khoa học máy tính) kiểm xem các đài còn lại có xếp vừa ít kênh hơn mà không nhiễu nhau.
Nghề liên quan: kỹ sư, nhà khoa học dữ liệu ở các đội quảng cáo, định giá, chợ hai phía (marketplace); nhà kinh tế trong công ty công nghệ; người thiết kế đấu giá, tuyển sinh cho nhà nước.
Học xong làm được gì, bắt đầu từ đâu
Sau môn này bạn có thể:
- viết một tình huống nhiều người thành trò chơi, tìm cân bằng Nash, biết khi nào việc đó khó;
- chứng minh một cơ chế là trung thực, hoặc chỉ ra chỗ người chơi được lợi khi nói dối;
- cài đặt đấu giá Vickrey, cơ chế VCG, thuật toán Gale–Shapley, tính giá của sự ích kỷ — và hiểu vì sao chúng đúng;
- nhìn một tính năng — bảng xếp hạng, mã giảm giá, thưởng giới thiệu bạn bè — và đoán trước người dùng sẽ lách nó thế nào.
Nên biết trước: thiết kế và phân tích thuật toán, nhất là viết chứng minh; xác suất cơ bản. Không cần học kinh tế trước: khái niệm nào cần, môn học tự giới thiệu.
Bắt đầu trên OpenER: trang chủ đề Algorithmic Economics có các khóa học đã chọn lọc, và hướng dẫn học gợi ý thứ tự đi qua chúng. Khóa chính là Stanford CS364A Algorithmic Game Theory (mùa thu 2013) của Tim Roughgarden, mỗi buổi có video và ghi chú. Chưa quen cân bằng Nash thì xem trước Yale ECON 159 Game Theory của Ben Polak, dễ vào và giảng sinh động, hoặc khóa Game Theory trên Coursera có bài tập chấm tự động. Muốn đi sâu mặt toán và ứng dụng vào mạng, có MIT 6.254 Game Theory with Engineering Applications.
Lời khuyên cho môn này: mỗi định lý, tự dựng một ví dụ nhỏ. Phần lớn bài tập là chứng minh, và chứng minh chỉ vào đầu khi bạn đã tận mắt thấy nó đúng trên một trò chơi hai người, một phiên đấu giá ba người, một mạng bốn nút.
Tài liệu tham khảo
- Tim Roughgarden — Twenty Lectures on Algorithmic Game Theory, Cambridge University Press, 2016; ghi chú bài giảng CS364A (Stanford, 2013) đọc miễn phí trên trang của tác giả.
- Noam Nisan, Tim Roughgarden, Éva Tardos, Vijay V. Vazirani (chủ biên) — Algorithmic Game Theory, Cambridge University Press, 2007.
- David Easley, Jon Kleinberg — Networks, Crowds, and Markets, Cambridge University Press, 2010; bản nháp đọc miễn phí trên trang của Đại học Cornell.
- Yale ECON 159 Game Theory (Ben Polak) — Open Yale Courses.
- MIT 6.254 Game Theory with Engineering Applications — MIT OpenCourseWare.
- David Gale, Lloyd S. Shapley — "College Admissions and the Stability of Marriage", The American Mathematical Monthly, 1962.
- Viện Hàn lâm Khoa học Hoàng gia Thụy Điển — tài liệu khoa học kèm giải Nobel kinh tế 2012 (ghép cặp ổn định) và 2020 (đấu giá), trên nobelprize.org.