Thuật toán bỏ phiếu "làm cho mọi người hạnh phúc" là gì?

Question

Tôi đang tìm một thuật toán bỏ phiếu chọn người chiến thắng dựa trên sự kết hợp của đa số phiếu bầu và số phiếu bầu.

Bất dụ cuộc sống:

Công ty chúng tôi có một thanh ngũ cốc. Chúng tôi có chỗ cho 3 loại ngũ cốc khác nhau. Chúng tôi muốn cho phép nhân viên của chúng tôi bỏ phiếu cho loại ngũ cốc họ muốn.

Chúng tôi không muốn chọn đúng 3 người chiến thắng hàng đầu dựa trên sự nổi tiếng vì có thể có một số ít nhân viên chỉ có thể ăn 1 ngũ cốc đặc biệt (vì lý do gì) và chúng tôi muốn cung cấp cho họ trợ cấp đặc biệt nhất có thể.

Với kết quả bỏ phiếu sau đây, đây là kết quả chúng tôi muốn thuật toán cung cấp cho chúng tôi.

Tôi đang tìm một thuật toán thực hiện loại xếp hạng này. Nếu bạn ít nhất có thể cung cấp tên của những gì tôi đang tìm kiếm đó sẽ là một trợ giúp lớn như tôi có thể tìm kiếm nó tốt hơn. :)

Cảm ơn!

Answer 1

Bạn có thể muốn xem xét tổng quát của Hall's marriage theorem và/hoặc assignment problem.

Ý tưởng cho mô hình này là tạo ra một đồ thị hai phía nơi các nút là con người và các loại ngũ cốc, với một cạnh giữa người p và ngũ cốc c nếu p bình chọn cho c.Mục đích là để chọn 3 loại ngũ cốc như vậy mà đồ thị kết quả từ loại bỏ tất cả các loại ngũ cốc khác là

1. kết nối (tất cả mọi người sẽ ăn ít nhất một trong những loại ngũ cốc được chọn), và

2. tối đa hóa tối thiểu/trung bình mức độ của mỗi người (tối đa hóa niềm vui tối thiểu/trung bình)

Thay vào đó, bạn có thể nghĩ về điều này là Maximum Coverage Problem. Trong trường hợp này, bạn có bộ C1,C2,...,Cm trong đó Ci là tập hợp những người thích ngũ cốc i. Đối với bạn ví dụ, lấy ngũ cốc và các người theo thứ tự được liệt kê trong bảng, bạn có

C1 = {1,5} 
C2 = {2} 
C3 = {1,4,5} 
C4 = {3,5} 

Hãy n được số lượng người, do đó Ci là một tập hợp con của {1,2,...,n}. Mục đích là để tìm k bộ như vậy rằng cardinality của công đoàn là tối đa. Nếu tồn tại nhiều giải pháp, hãy chọn giải pháp tối thiểu hóa số lượng giao điểm (giảm thiểu số tiền mà một người chiếm ưu thế) hoặc tối đa số lần yếu tố ít được lặp lại nhiều nhất (tối đa hóa hạnh phúc của người ít hạnh phúc nhất).

Ví dụ này, có nhỏ nhất k mà tất cả các phần tử được bao phủ là k=3 và nó cung cấp giải pháp duy nhất C2,C3,C4.

Tuy nhiên bạn nhìn vào nó, bạn có vấn đề NP, nhưng có các thuật toán đã biết để giải quyết chúng (kiểm tra các bài viết wikipedia để tham khảo).

Answer 2

Không có hệ thống bỏ phiếu hoàn hảo nào - xem http://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem. Đã có nhiều nỗ lực để vượt qua điều này bằng cách uốn các quy tắc, bao gồm http://en.wikipedia.org/wiki/Range_voting.

Một ý tưởng gần với bỏ phiếu ở phạm vi là cho tất cả 12 phiếu bầu và cho phép họ phân phối chúng theo ý muốn. Nhìn vào ví dụ của bạn, nếu bạn giả định rằng những người có nhiều lựa chọn phân phối 12 phiếu bầu của họ như nhau - 12x1 hoặc 6x2 hoặc 4x3 hoặc 3x4 - thì tôi nghĩ rằng bạn có được kết quả mong muốn của mình, với Lucky Charms nhận tổng cộng 10 phiếu và mọi thứ khác nhận được nhiều hơn thế này.

Answer 3

Nếu số lượng ngũ cốc là nhỏ, bạn có thể xem vấn đề của bạn là một vấn đề tập hợp con-cover và brute force theo cách của bạn để tìm kiếm những gì cấu hình cung cấp cho các "happyness" nhất

var max_happyness = -INF 
for every subset {c1, c2, c3} of C: 
    max_hapyness = max(max_happyness, happyness(i1,i2,i3)) 

Bạn vẫn có vấn đề xác định hàm hạnh phúc phù hợp. Ví dụ, bạn có thể chọn một chức năng hạnh phúc là ưu tiên hàng đầu tính toán số người có thể ăn bất kỳ thực phẩm nào. Sau đó, ưu tiên thứ hai là số người thích hai loại ngũ cốc, sau đó là những người thích ba ngũ cốc và vân vân.

Ưu điểm: Nếu bạn có thể xác định chức năng hạnh phúc, điều này mang lại kết quả tốt nhất được đảm bảo.

Nhược điểm: Bạn phải có khả năng xác định chức năng hạnh phúc.