Thiết kế lịch thi đấu giải Tennis
Ngô Quang Hưng | 28 tháng 01, 2007 | 
Bản để in
Với dạng cây nhị phân như hiện nay, có khả năng đấu thủ mạnh thứ hai trong giải (do bị đấu thủ mạnh nhất loại từ trước) không được huy chương bạc. Nếu ai đó (như Andy Rodick) mà xui xẻo nằm ở nửa nhánh cây chung với Federer thì coi như là … hẻo.
Lewis Carroll (tác giả Alice in Wonderland) còn là một nhà toán học có cỡ. Ông đã nêu vấn đề bất công này từ hồi 1883 trong tạp chí St. James’s Gazette. Chương 5 quyển 3 của bộ sách của Knuth ghi lại khá chi tiết các phát triển sau đó của câu hỏi này.
1 Nếu bạn phải thiết kế một lịch thi đấu tennis để xác định đấu thủ mạnh nhất và đấu thủ mạnh nhì, bạn cần tối thiểu bao nhiêu trận đấu, cho biết tổng số đấu thủ ban đầu là n?
2 Nếu ta muốn biết cả đấu thủ mạnh thứ 3 (huy chương đồng), thì cần tổng cộng bao nhiêu trận đấu, lịch thi đấu thế nào?
(Dĩ nhiên, câu hỏi tổng quát nhất là xác định m đấu thủ mạnh nhất, và đã có vài câu trả lời gần tối ưu cho câu hỏi này, nhưng chưa phải là tối ưu.)
1. Phuong phap toi uu co bound la n + log(n)
2. Bound la n + log(n) + log(log(n)) + …
As long as m << n, I’m not interested in verifying if it’s the least upper bound.
Chào dongta, ý tưởng của bạn là chính xác.
Cái bound tối ưu cho câu 1 là
. (See Knuth’s book for a pretty fascinating history of this question, along with many other results.)
Em co bai toan hinh nhu lien quan den thiet ke lich thi dau nay, rat mong anh Hung va moi nguoi chi bao:
Co k >=2 players va n>>> items. Mo^~i item nay co nha~n 0/1 (negative/positive) unknown. Moi player phai xep cac items theo 1 trat tu nhat dinh, trat tu nay la co^’ ddi.nh. Oracle biet label cua tat ca items nhung chi co the cung cap label cho 1 so luong nhat dinh items (due to the non-zero labeling cost). Performance cua moi player la 1 ham phu thuoc vao vi tri cua cac positive items trong top m items cua cai ordered permutation gom n items do.
Can tim ra the potentially best player. Hoac dua ra trat tu cac players (ties accepted).
Co the thoa man yeu cau tren ma khong can biet label cua bat ki item nao ko? Neu ko, co the tim duoc so items toi thieu va toi da de thoa man yeu cau duoc khong (lower bound and upper bound of sample complexity)? (theo k, n, m, delta de phan biet 2 players, sai so^’ epsilon)
1 ung dung cua bai toan nay: cho.n 1 or sap xep cac search engines by their effectiveness retrieval performance (player
Chào tvhvt, tôi chưa hiểu bài toán lắm. Có mấy thắc mắc như sau:
1. Như vậy mỗi player là một algorithm có quyền hỏi oracle một hằng số các câu hỏi? Dựa vào đó mỗi player xếp trật tự các items?
2. Sau đó ta phải quyết định xem player nào chơi tốt hơn? Ta làm điều này bằng cách tạo nhiều bộ items khác nhau, sau đó nhìn vào outputs rồi quyết định theo một xác suất nào đó?
3. Câu hỏi trên thì lại là thiết kế một player nhất định? Nếu không biết label của items nào thì chỉ có thể chọn ngẫu nhiên (cộng với giúp đỡ của Oracle) rồi dùng Chernoff bound. Câu này có lẽ là hay nhất.
Không hiểu tôi có hiểu đúng bài toán của bạn không?
Chào anh Hưng,
1. Mỗi player đúng là 1 algorithm (1 search engine) nhưng không có quyền hỏi oracle. Chỉ duy nhất 1 referee có quyền hỏi oracle thôi ạ.
2. Đúng là phải quyết định xem player nào chơi tốt hơn nhưng với càng ít số items mà referee hỏi oracle càng tốt ạ.
Hàm đánh giá chất lượng 1 player trên 1 item set (1 query) khi biết nhãn của các items là 1 hàm phụ thuộc vào vị trí của các positive items mà 1 player sắp xếp. Nghĩa là đây là weighted mean của xác suất 1 item có nhãn non-negative. Với các items mà referee không biết nhãn thì hoặc là cho là các negative items, hoặc nhận 1 giá trị trung gian (P(item = positive)=0.5).
3. Hàm đánh giá chất lượng 1 player là weighted mean phụ thuộc các non-negative items nên chỉ chọn ngẫu nhiên thì hình như chưa ổn ạ. Ít nhất là dùng các kiểu metasearch, voting để hi vọng đẩy được các positive items lên phía trước rồi lần lượt hỏi theo thứ tự này thì cũng không tệ đâu ạ.
Nếu chỉ có 2 players thôi, vì mục đích là tìm được the best player chứ không phải là tìm consistent estimate của cái weighted mean/player, có phải đây là small deviation thay vì large deviation không ạ?
Chào tvhvt, tôi vẫn chưa hiểu câu hỏi.
Player 1 returns ordering A, player 2 returns ordering B; làm thế nào để referee quyết định xem player nào tốt hơn? TVHVT có thể cho biết một ví dụ cụ thể của cái hàm đánh giá chất lượng được không?
Giả sử A = abc; B = xyz (trong đó a,b,c,x,y,z là 0 hoặc 1). Theo như mô tả thì hàm đánh giá là
a prob[a=1] + b prob[b=1] + c prob[c=1] cho ordering A?
Tôi có hiểu đúng không?