Thiết kế cơ chế

Thiết kế cơ chế, đôi khi được gọi là lý thuyết trò chơi nghịch đảo, là việc xây dựng các quy tắc tương tác sao cho các tác nhân vị kỷ, hành động một cách hợp lý, tạo ra kết quả mà người thiết kế mong muốn.

Definition

Thiết kế cơ chế là nghiên cứu về cách xác định các quy tắc của một tương tác đa tác nhân—ai có thể làm gì và cách xác định kết quả và khoản thanh toán—để hành vi cân bằng của các tác nhân hợp lý, vị kỷ đạt được một mục tiêu mong muốn như hiệu quả hoặc tính trung thực.

Scope

Chủ đề này bao gồm việc thiết kế các giao thức tương tác cho các tác nhân chiến lược: lựa chọn xã hội và tổng hợp các ưu tiên, các mục tiêu về hiệu quả và khả năng tương thích khuyến khích (tính trung thực), nguyên lý tiết lộ, đấu giá (bao gồm đấu giá giá thứ hai của Vickrey và cơ chế Vickrey-Clarke-Groves), và các khía cạnh thuật toán và tính toán của việc triển khai cơ chế. Nó đề cập đến cách điều chỉnh các khuyến khích cá nhân với các mục tiêu tập thể. Phân tích mô tả về cách các tác nhân hành xử trong các trò chơi cố định được xử lý trong lý thuyết trò chơi.

Core questions

• Làm thế nào để các quy tắc tương tác có thể được thiết kế sao cho các tác nhân có động cơ để báo cáo sở thích thực sự của họ?
• Nguyên lý tiết lộ nói gì về việc giới hạn sự chú ý vào các cơ chế trung thực?
• Các cuộc đấu giá phân bổ hàng hóa hiệu quả giữa các tác nhân có định giá riêng tư như thế nào?
• Chi phí tính toán để triển khai các cơ chế mong muốn là gì?

Key concepts

• lựa chọn xã hội và tổng hợp sở thích
• khả năng tương thích khuyến khích (tính trung thực)
• triển khai chiến lược ưu thế
• nguyên lý tiết lộ
• đấu giá
• đấu giá giá thứ hai của Vickrey
• cơ chế Vickrey-Clarke-Groves (VCG)
• hiệu quả và tính hợp lý cá nhân

Key theories

Khả năng tương thích khuyến khích và đấu giá giá thứ hai

Đấu giá giá thứ hai (đấu giá kín) của Vickrey, trong đó người thắng cuộc trả giá cao thứ hai, biến việc trả giá trung thực thành một chiến lược ưu thế, minh họa cách thiết kế quy tắc cẩn thận có thể khơi gợi hành vi trung thực từ các tác nhân vị kỷ.

Cơ chế Vickrey-Clarke-Groves

Họ VCG tổng quát hóa ý tưởng giá thứ hai cho các vấn đề phân bổ phức tạp, tính phí mỗi tác nhân theo ngoại tác của nó để báo cáo trung thực là một chiến lược ưu thế và kết quả hiệu quả được chọn.

Nguyên lý tiết lộ

Nguyên lý tiết lộ cho thấy rằng bất kỳ kết quả nào có thể đạt được bằng một cơ chế nào đó cũng có thể đạt được bằng một cơ chế trực tiếp trung thực, cho phép các nhà thiết kế tập trung vào các cơ chế tương thích khuyến khích mà không làm mất tính tổng quát.

Clinical relevance

Thiết kế cơ chế là nền tảng cho quảng cáo trực tuyến và đấu giá tìm kiếm được tài trợ, đấu giá phổ tần và tài nguyên, thị trường điện tử và hệ thống đối sánh, và phân bổ tài nguyên tính toán, bằng cách xây dựng các quy tắc mà theo đó các tác nhân chiến lược được dẫn đến các kết quả hiệu quả và trung thực.

History

Thiết kế cơ chế phát triển từ lý thuyết kinh tế, với phân tích đấu giá của Vickrey (1961) và các đóng góp sau này của Clarke và Groves hình thành nên họ VCG. Từ cuối những năm 1990, khoa học máy tính đã bổ sung nghiên cứu về tính khả thi tính toán và xấp xỉ, tạo ra thiết kế cơ chế thuật toán, được trình bày trong các văn bản như Lý thuyết trò chơi thuật toán (2007).

Key figures

• William Vickrey
• Edward H. Clarke
• Theodore Groves
• Noam Nisan
• Tim Roughgarden

Seminal works

• vickrey1961
• shoham2009
• nisan2007

Frequently asked questions

Tại sao thiết kế cơ chế được gọi là lý thuyết trò chơi nghịch đảo?

Lý thuyết trò chơi coi các quy tắc của một tương tác là đã cho và phân tích cách các tác nhân hợp lý sẽ hành xử. Thiết kế cơ chế hoạt động ngược lại: nó bắt đầu từ một kết quả mong muốn và thiết kế các quy tắc sao cho hành vi hợp lý của các tác nhân tạo ra kết quả đó, do đó có tên là lý thuyết trò chơi nghịch đảo.

Tại sao đấu giá giá thứ hai khuyến khích trả giá trung thực?

Trong đấu giá giá thứ hai của Vickrey, người thắng cuộc trả giá cao thứ hai chứ không phải giá của chính họ. Điều này loại bỏ mọi động cơ để che giấu giá thầu: trả giá trị thực của bạn chỉ có thể giúp bạn thắng khi đáng giá và không bao giờ khiến bạn trả quá nhiều, vì vậy việc trả giá trung thực trở thành một chiến lược ưu thế.