Thiết kế thị trường (Market design) và lý thuyết trò chơi (Game theory)

Ở trường Tohoku, ngành học của tôi là vật lý. Tuy nhiên, tôi cũng đang học một chương trình sau đại học khác song song đó là “Chương trình lãnh đạo sau đại học”. Có thể hiểu đây là một dạng lớp chọn giống như mô hình trường chuyên lớp chọn ở cấp phổ thông của chúng ta. Vào được lớp này phải cạnh tranh với các sinh viên sau đại học chính quy, những người đã đỗ vào trường Tohoku bao gồm cả quốc tế và Nhật bản. Hiện nay sau 3 năm bắt đầu, chương trình gồm có 3 sinh viên Tàu, 1 Hàn, 1 Bangladesh, 1 Thái, 1 Inđô, 1 Afghanistan, 1 Việt nam là tôi, và hàng chục sinh viên Nhật khác. Nói chung đây thực sự là chương trình tốt, cụ thể là sinh viên được tiếp cận các COE của Sony, Fujitsu, … hoặc các GS được giải Nobel, các nhà lãnh đạo hiện nay của nhật, và được học các môn kinh tế, các lớp về hùng biện. Về quan điểm cá nhân thì chương trình cũng có mặt trái của nó, nó giống một cái bánh vẽ hoành tráng. Vì đa số lớp học đều là kiểu cưỡi ngựa xem hoa. Hoặc là đào tạo một nhà lãnh đạo, đôi khi cái gì cũng phải biết một tí.

Trong chương trình học này, chúng tôi có tham gia một lớp học về thiết kế thị trường. Mặc dù được giảng bằng tiếng Nhật, nhưng tài liệu và slide bằng tiếng Anh, tôi thực sự bị kích thích vì nó liên quan đến lý thuyết trò chơi. Mà tôi là một fan của bộ phim “A Beautiful Mind” nói về cuộc đời nhà toán học Nash, cha đẻ của lý thuyết trò chơi. Ông được trao giải Nobel kinh tế năm 1994 và giải Abel năm 2015. Một tin rất buồn là ông và vợ mình qua đời trong một tai nạn xe hơi năm ngoái. Họ có một tình yêu đẹp và chúa đã đưa họ lên thiên đường cùng nhau, tạm biệt ông và người phụ nữ của ông. Tôi cũng chỉ mới đọc qua về lĩnh vực này, nên bài blog này chắc không thể nói về kinh tế chuyên sâu và nhiều thuật ngữ trong tiếng Việt có thể không chuẩn như các bạn chuyên ngành kinh tế, tôi chỉ muốn nói về điều mình hứng thú trong lý thuyết thị trường đó là lý thuyết phù hợp (matching theory). Tại sao phù hợp thị trường (matching markets) là quan trọng trong xã hội hiện nay. Tôi sẽ lấy một ví dụ cụ thể như sau:

Một bệnh nhân cần thay thận, nhưng không may người thân trong gia đình không ai có thận phù hợp để thay. Như chúng ta đều biết buôn bán nội tạng là bất hợp pháp. Vậy làm thế nào vấn đề này có thể được giải quyết. Nó có thể giải quyết nếu một cặp bệnh nhân-nhà tài trợ là phù hợp với một cặp bệnh nhân-nhà tài trợ khác. Vấn đề là làm sao các cặp này có thể ghép nối với nhau. Hoặc một ví dụ khác là thị trường việc làm đang cần 3000 công nhân, vậy làm sao để 3000 công nhân được nhận vào một cách hợp lý nhất mà không xung đột. Hoặc nếu ai từng mua hàng qua mạng đều biết hình thức đấu giá, cách kinh doanh doanh này thực chất là một sản phẩm của thiết kế thị trường. Vì trong tất cả các ví dụ trên một yếu tố quan trọng nhất đó là tính ổn định. Không ai muốn công nhân được tuyển vào lại không hài lòng với công việc, không ai muốn cấy ghép thận xong lại bị kiện cáo, hoặc mua hàng qua đấu giá nhưng lại không hài lòng về giá cả. Có thể hiểu nôm na là thiết kế thị trường là thiết kế một bộ quy tắc hay luật chơi để có thể đạt được sự phù hợp giữa hai nhóm cá nhân được gán ghép lẫn nhau. Tính ổn định của sự phù hợp này có thể dễ dàng đạt được thông qua thuật toán “Gale-Shapley algorithm” hay còn biết tới như “bài toán hôn nhân ổn định (The Stable Marriage Problem – SMP)” của Alvin Roth và Lloyd Shapley. Hai nhà toán học kinh tế Alvin Roth và Lloyd Shapley cũng đồng thời là chủ nhân của giải Nobel kinh tế năm 2012 cho những đóng góp của họ trong lĩnh vực thiết kế thị trường.

Bài toán hôn nhân ổn định – SMP

Giả sử có n đàn ông và n phụ nữ, những người đang muốn kết hôn. Làm thế nào để ghép đôi những cặp trên để họ có một hôn nhân hạnh phúc?

David Gale and Lloyd Shapley đã giải quyết vấn đề này vào năm 1962 với một công bố có tiêu đề là “College Admissions and The Stable Marriage Problem” [1].

Có rất nhiều các để ghép đôi một cuộc hôn nhân, ví dụ bằng cách yêu cầu mỗi người đàn ông về những điều kiện ưu tiên hàng đầu của họ về những người phụ nữ mà họ muốn kết hôn. Nhưng điều gì sẽ xảy ra nếu có nhiều hơn một người đàn ông cùng chọn một người phụ nữ, hoặc ngược lại người phụ nữ không hài lòng với người đàn ông đã chọn mình.

Vấn đề ở đây có thể là một số kết hợp (matchings) không ổn định. Gale và Shapley định nghĩa một sự “phù hợp không ổn định” là một tình huống mà hai người sẽ xuất hiện cùng nhau trong một tình huống hiện tại của họ. Nó không ổn định vì đơn giản là các đối tác phù hợp lẫn nhau vì có thể họ không chọn được ai khác thực sự phù hợp. Giống kiểu người tôi thích lấy chồng rồi lên tôi mới lấy anh. Vì vậy một sự kết hợp là hợp lý khi nó phải được ổn định. Gale và Shapley đã nghĩ ra một thuật toán mà có thể đảm đảo một sự phù hợp ổn định mà nó là tối ưu cho một bên.

Thuật toán Gale-Shapley

Vẻ đẹp của thuật toán này không phải quá khó hiểu. Dưới đây là thuật toán mà trong đó người đàn ông sẽ đề nghị.

  1. Mỗi người đàn ông sẽ đề xuất lựa chọn đầu tiên của mình.
  2. Nếu người phụ nữ nào nhận được nhiều đề xuất nhất, cô ta sẽ được chọn người đàn ông mà cô ưu thích nhất và loại bỏ những người còn lại.
  3. Những người đàn ông bị từ chối sau đó sẽ đề xuất lựa chọn thứ hai của họ.
  4. Lặp lại bước này, nếu người phụ nữ nào còn lại nhận được nhiều đề xuất nhất, cô ta sẽ là người tiếp theo được chọn người đàn ông mà cô ta thích nhất.
  5. Lặp lại bước 3, những người đàn ông bị từ chối sẽ tiếp tục đề xuất lựa chọn tiếp theo của họ.
  6. Những người phụ nữ tiếp tục chọn người yêu thích của họ, và người đàn ông bị từ chối lại tiếp tục đề xuất lựa chọn của họ cho đến khi các cặp được ghép đôi 1-1.
  7. Kết thúc, đây là một trận đấu ổn định và là tối ưu cho những người đàn ông.

Tôi chú ý với các bạn rằng đây chỉ là trận đấu mà sự phù hợp là được tối ưu cho người đàn ông. Đương nhiên một quá trình tương tự có thể được tối ưu cho người phụ nữ nếu họ là người đề xuất lựa chọn. Tuy nhiên, hai quá trình tối ưu cho đàn ông và tối ưu cho phụ nữ có thể có kết quả không giống nhau. Điều này dễ hiểu bởi đôi khi người phụ nữ lại thích người đàn ông, người mà đã không đề xuất họ. Tuy nhiên trong trường hợp người đàn ông đề xuất thì họ chỉ được phép chọn người đàn ông đã đề xuất mình. Nói chung trong cả hai trường hợp trên sự phù hợp là ổn định. Tuy nhiên sự tối ưu chỉ dành cho bên đề xuất lựa chọn của mình trước.

Ngày nay thuật toán này được áp dụng khắp mọi nơi, từ các tuyển sinh trong trường học, tuyển nhân viên trong các công ty, cung cấp nội tạng trong bệnh viện, chiến lược trong kinh doanh của các công ty nhỏ để không bị các công ty lớn nuốt chửng, đặc biệt là cơ chế hoạt động của các phiên đấu giá trên Amazon hoặc Yahoo. Nếu các bạn muốn tìm hiểu thêm có thể xem video sau:

[1] http://www.econ.ucsb.edu/~tedb/Courses/Ec100C/galeshapley.pdf

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s