Độ phức tạp của một phiên đấu giá VCG là bao nhiêu? (các bạn có thể google xem VCG là gì, cơ bản nó là cách các page trên fb trả tiền để quảng cáo)
A: Eric Mayefsky,Tiến sĩ kinh tế và hành vi thương mại, Đại học Stanford (2011)
http://qr.ae/TUIuMb
Tôi nghĩ rằng câu trả lời phụ thuộc vào việc phiên đấu giá VCG mà bạn hỏi có liên quan đến trường hợp đặc biệt trong cơ chế chung của VCG, cái mà mỗi nhà quảng cáo chỉ có thể nhận được 1 sản phẩm và những giá trị liên quan của sản phẩm được cố định cho tất cả những người tham gia (đây là trường hợp phổ biến nhất của đấu giá quảng cáo), hoặc là bạn đang đề cập đến tất cả các vấn đề phát sinh mà cơ chế VCG có thể kiểm soát (bạn có thể chọn bất kì vấn đề có thể phát sinh nào trong số chúng), hoặc là thứ gì đó riêng biệt nằm giữa, ví dụ như việc phân bổ hàng hóa chẳng hạn, nhà thầu có thể muốn nhiều thứ và ra giá cho tất cả các sản phẩm (kiểu như bạn có 2 thứ thì là giá trị, nhưng có 1 thì vô dụng), đây là định nghĩa của một phiên đấu giá VCG, theo Wikipedia.[1]
Nhìn chung, việc VCG hoạt động phụ thuộc vào các bản báo cáo từ nhà thầu / đại lý về số lợi nhuận đầu ra có thể đạt được:
1. Dựa vào thông tin mà các đại lý cung cấp, bạn tìm ra được kết quả tối ưu ( tức là kết quả tối đa hóa tổng tất cả các tiện ích được báo cáo của kết quả đó).
2. Với mỗi đại lý, tính toán ảnh hưởng ngoại lai của họ lên những đại lý khác, tức là, tính toán sự chênh lệch giữa giá trị mà những đại lý khác nhận được ở kết quả thực và kết quả mà thuật toán đã chọn nếu đại lý không thỏa mãn yêu cầu của câu hỏi, và tính phí đại lý đó.
Cho nên, bằng trực giác, nếu có n đại lý, bạn phải tìm ra sự phân bổ tối ưu n+1 lần (1 cho sự phân bổ tối ưu trong thực tế, và 1 phân bổ phản tác dụng cho mỗi đại lý trong bước 2) và tính toán giá trị cho n đại lý trong những trường hợp đó (những trường hợp trong bước 2). Đôi khi thứ này có thể trở nên khá đắt đỏ (NP-hard[2]), và khi cân nhắc các lựa chọn thay thế cho VCG, những thứ mà bạn đang thực sự nhắc đến là loại ước chừng nào bạn sẵn sàng cho phép để xác định kết quả chính xác, trái ngược với sự thanh toán và các tính năng ưu đãi của lý thuyết khoa học máy tính VCG.
Tuy nhiên, trong đấu giá VCG được sử dụng bối cảnh để quảng cáo, (như đã được trình bày trong [3], nó phù hợp với cách một số công ty nổi tiếng đã thực hiện trong những năm qua theo các thông tin mà họ đã công bố, tuy nhiên tôi đương nhiên sẽ không trực tiếp bình luận về hành vi hoạt động hiện tại của bất kỳ công ty hay bất kỳ quyền sở hữu nào khác) thường thì những nhà thầu chỉ đấu giá cho những vị trí hàng đầu và tốt nhất, hoặc thông qua các phương tiện hiển thị trực tiếp, hoặc thông qua việc thể hiện giá thầu cho một cú nhấp chuột hoặc một cuộc chuyển đổi, sau đó hệ thống chuyển đổi thành giá thầu hiển thị ( bằng cách dự đoán tỉ lệ click chuột hoặc tỉ lệ chuyển đổi) để có được tất cả các nhà quảng cáo trên cùng một nền tảng.
Sau đó – đây là phần quan trọng cho câu hỏi này – hệ thống đưa ra các giả định về những thứ có khả năng suy giảm trong vị trí đầu tiền, và thường đưa ra các giả định tương tự cho các nhà thầu. (Ví dụ: trong 1 tình huống nhất định, vị trí thứ 2 có giá trị bằng 75% vị trí thứ 1, dựa trên dữ liệu bạn có về hoạt động của người dùng mà bạn muốn trong các vị trí khác nhau, và vị trí thứ ba đáng giá 75% vị trí thứ 2, cứ thế)
Vì bạn đã giả định các giá trị liên quan của những ví trí này là giống nhau đối với tất cả các nhà thầu, cách phân bổ tốt nhất là cung cấp cho người thầu nhiều nhất vị trí đầu tiền, người tiếp theo vị trí số 2 và cứ thế đến khi bạn hết vị trí (slot)
Việc tính toán bên ngoài cũng là một công thức đơn giản-nó chỉ là một mức trung bình đơn giản của các nhà thầu trả giá thấp, cứ thế nâng lên và người trả giá cao nhất sẽ không giành được vị trí nào hết. Vì vậy, dựa theo góc độ phức tạp của lý thuyết độ phức tạp tính toán, bạn chỉ tìm và đặt hàng với m+1 trong số n giá thầu, trong đó m là số lượng vị trí và n là số lượng nhà thầu, sau đó đưa chúng vào một công thức đại số vừa đơn giản vừa chính xác ý hệt như nhau cho mỗi phiên đấu giá, hoặc ít nhất là cho một dòng quảng cáo trên trang. Tôi không phải chuyên gia về lý thuyết độ phức tạp tính toán nhưng có vẻ [4] bạn có thể nhận được giá thầu m+1 trong mức độ o(n) và sắp xếp chúng trong mức độ o(m logm), và trong thực tế bạn sẽ mong đợi số nhà thầu nhiều hơn số lượng vị trí vì vậy nó trông giống o(n) hơn. Lưu ý rằng về cơ bản, không có thứ gì đặc biệt với VCG-phần khó khăn mà bạn muốn làm với mọi phiên đấu giá, là tìm những người sẽ đặt giá thầu nhiều nhất và sắp xếp chúng.
Đương nhiên, đây chỉ là táo và cam (ý nói khác nhau nên khó so sánh trong thực tế), bởi vì bạn đang so sánh rất chung chung nên ta không thể ước lượng vào một tường hợp cụ thể với những giả định cho sẵn. Theo quan điểm của tôi, thật nực cười khi nói rằng việc đấu giá quảng cáo không như lý thuyết của VCG bởi vì bạn đang đưa ra những giả định về sở thích của nhà quảng cáo, nhưng nó lại là thứ duy nhất có ý nghĩa trong thực tế.
[1]https://en.wikipedia.org/…/Vickrey%E2%80%93Clarke%E2%80%93G…
[2]https://vi.wikipedia.org/wiki/NP-kh%C3%B3
[3]http://www.benedelman.org/publications/gsp-060801.pdf
[4]https://en.wikipedia.org/wiki/Selection_algorithm