Phân bổ một phần trong thiết kế cơ chế khả thi về ngân sách: Kết nối nhiều cấp độ dịch vụ và các tác nhân có thể chia nhỏ
Partial Allocations in Budget-Feasible Mechanism Design: Bridging Multiple Levels of Service and Divisible Agents.
Mua sắm khả thi về ngân sách đã là một mô hình chính trong thiết kế cơ chế kể từ khi được Singer giới thiệu [25]. Một người đấu giá (người mua) có ràng buộc ngân sách chặt chẽ muốn mua hàng hóa hoặc dịch vụ từ một nhóm các tác nhân chiến lược (người bán). Trong nhiều trường hợp, việc cho phép người đấu giá chỉ mua một phần những gì một tác nhân cung cấp là hợp lý, ví dụ, một tác nhân có thể có nhiều bản sao của một mặt hàng để bán, họ có thể cung cấp nhiều cấp độ dịch vụ hoặc họ có thể sẵn sàng thực hiện một nhiệm vụ trong bất kỳ phần nào của khoảng thời gian cụ thể. Tuy nhiên, trọng tâm của các tài liệu liên quan là các thiết lập mà các dịch vụ của từng tác nhân được mua đầy đủ hoặc không được mua gì cả. Một lý do cho điều này là trong các thiết lập có phân bổ một phần như đã đề cập, có những kết quả không gần đúng mạnh (xem, ví dụ, Chan và Chen [9], Anari và cộng sự [4]). Với giả định nhẹ nhàng là có khả năng chi trả hoàn toàn cho từng tác nhân, các tác giả có thể tránh được những kết quả như vậy. Các tác giả thiết kế một cơ chế gần đúng (2 + ), xác định, trung thực, khả thi về ngân sách, thời gian đa thức, cho bối cảnh mà mỗi tác nhân cung cấp nhiều cấp độ dịch vụ và người đấu giá có một hàm định giá là lõm tách biệt, tức là, nó là tổng của các hàm lõm. Sau đó, các tác giả sử dụng kết quả này để thiết kế một cơ chế xác định, trung thực và khả thi về ngân sách cho thiết lập mà bất kỳ phần nào của dịch vụ cũng có thể được mua lại. Tỷ lệ gần đúng của cơ chế thứ hai này phụ thuộc vào mức độ “tốt” của các hàm lõm tạo nên hàm định giá của người đấu giá; nó là O(1) đối với các hàm định giá là tổng của các hàm chính quy O(1) (ví dụ: các hàm như log(1 + x)). Đối với trường hợp đặc biệt của hàm định giá tuyến tính, các tác giả cải thiện tỷ lệ gần đúng tốt nhất đã biết cho vấn đề này từ (3 + )/2 (theo Klumper và Schäfer [18]) thành 2. Điều này thiết lập sự tách biệt giữa thiết lập này và phần tương ứng không thể chia nhỏ của nó.