Cải thiện đảm bảo gần đúng EFX theo các giả định dựa trên thứ tự
Improved EFX Approximation Guarantees under Ordinal-based Assumptions.
Các tác giả nghiên cứu sự phân bổ hợp lý các mục không thể phân chia cho một tập hợp các tác nhân và nằm trong phạm vi thiết lập các đảm bảo gần đúng được cải thiện. Đến nay mọi người đều biết các khái niệm giải pháp cổ điển trong sự phân chia công bằng, chẳng hạn như cơ chế không ghen tị và sự cân xứng, không tồn tại khi có những mục không thể phân chia. Thật không may, thiếu sự tồn tại vẫn chưa được giải quyết ngay cả đối với một số trường hợp thoải mái không ghen tị, và đáng chú ý nhất là khái niệm về EFX, đã thu hút được sự chú ý đáng kể trong các tài liệu liên quan. Chính điều này đã thúc đẩy việc tìm kiếm các thuật toán gần đúng, dẫn đến sự đảm bảo gần đúng (ϕ − 1) được biết đến nhiều nhất hiện nay bởi [3], trong đó ϕ bằng tỷ lệ vàng. Cho đến nay, rất khó để đạt được bất kỳ tiến bộ nào ngoài yếu tố này. Đóng góp chính: các tác giả đạt được những kết quả gần đúng tốt hơn, đối với một số trường hợp đặc biệt nhất định, trong đó các tác nhân đồng ý về nhận thức của họ về một số mục theo giá trị. Cụ thể, trước tiên các tác giả cung cấp một thuật toán với giá trị gần đúng 2/3, khi các tác nhân đồng ý về n mục hàng đầu (nhưng không nhất thiết phải dựa trên thứ hạng chính xác của chúng), với n là số lượng tác nhân. Để làm như vậy, các tác giả cũng đề xuất một khung tổng quát có thể mang lại lợi ích độc lập cho việc đạt được những đảm bảo tiếp theo. Thứ hai, các tác giả thiết lập sự tồn tại của phân bổ EFX chính xác trong một kịch bản khác, trong đó các tác nhân xem các mục được chia thành các tầng với giá trị của chúng, và họ đồng ý về mục nào thuộc về mỗi tầng. Nhìn chung, các tác giả cung cấp bằng chứng cho thấy vẫn có thể thực hiện được các đảm bảo được cải thiện bằng cách khai thác thông tin thứ tự của việc định giá.
Đọc thêm các bài viết liên quan tại thẻ Tags bên dưới