Odporne na manipulację mechanizmy lokalizacyjne na grafach z cyklem

Model

Problem lokalizacyjny

Środowisko:

• graf ,
• zbiór agentów ,
• stan świata , czyli preferencje agentów z na punktach grafu zadane przez ich idealne lokalizacje.

Problem lokalizacyjny (cd.)

Agenci: Preferują punkty grafu , które są blisko ich idealnych lokalizacji.

Planista: Chce wybrać punkt grafu , który jest „dobry” dla wszystkich agentów — ma mały koszt społeczny.

Kosztem społecznym powiązanym z dowolnym punktem grafu nazwiemy sumę jego odległości od idealnych lokalizacji agentów:

Projektowanie mechanizmów

Pytanie: co jeśli preferencje agentów są ich prywatnymi informacjami i przekazują je oni planiście przez zgłoszenia?

Rozwiązanie: planista musi przeprowadzić wybory, aby uzyskać informacje od agentów o ich preferencjach.

Przebieg wyborów

Czynności:

1. Planista deklaruje zasadę rozstrzygania wyborów poprzez ustalenie mechanizmu (funkcji mapującej krotki zgłoszeń na wyniki).
2. Agenci zgłaszają planiście komunikaty o swoich preferencjach.
3. Do krotki wszystkich zgłoszeń agentów aplikowany jest mechanizm .

Problem z cyklem

Niech graf będzie cyklem o obwodzie i równo rozłożonych wierzchołkach.

Doprecyzowanie problemu: graf to .

Problem: istnieje stan świata, w którym pewnemu agentowi opłaca się skłamać.

Odporność na manipulacje (SP)

Definicja: nikomu nie opłaca się kłamać, tzn. zachodzi:

gdzie:

1. preferencje agentów,
2. agent,
3. alternatywne zgłoszenie agenta .

Dyktator

Mechanizmem dyktatorskim ze względu na agenta : nazwiemy funkcję zdefiniowaną jako:

Znany fakt: mechanizm dyktatorski jest SP, ale dla wielu stanów świata działa nieoptymalnie (czasem lepiej się nie da).

Randomizacja

Mechanizm zwraca rozkład prawdopodobieństwa na zbiorze punktów grafu.

Na koniec wyborów losowany jest jeden z punktów zgodnie z rozkładem prawdopodobieństwa zwróconym przez mechanizm.

Użyteczność agentów i koszt społeczny rozszerzamy dla rozkładów prawdopodobieństwa, przez zastosowanie wartości oczekiwanej.

RD (losowy dyktator)

Mechanizm RD:

• losuje z równym prawdopodobieństwem jednego z agentów ,
• zwraca zgłoszenie agenta (czyli działa według ).

Znany fakt: mechanizm RD jest SP, bo jest zmieszaniem mechanizmów dyktatorskich.

Współczynnik aproksymacji

Definicja: dla stanu świata i mechanizmu współczynnik aproksymacji definiujemy jako:

Dla zbioru stanów świata definicję rozszerzamy przez maksimum:

Intuicja: mierzy jakość działania mechanizmu w porównaniu do optymalnego rozwiązania (w najgorszej sytuacji).

Jak dobrze działają mechanizmy SP?

Ograniczenie dolne: istnieją instancje problemu lokalizacyjnego, dla których optymalny mechanizm SP ma współczynnik aproksymacji nie mniejszy niż .

Ograniczenie górne:

• mechanizm dyktatorski ma współczynnik aproksymacji równy ,
• mechanizm RD ma współczynnik aproksymacji równy i w ogólności jest to najlepiej działający znany mechanizm SP.

Mechanizm PCD

Mechanizm PCD

Dodatkowe informacje:

• zaproponowany przez Reshefa Meira w 2019 roku,
• jego współczynnik aproksymacji osiąga wartości dowolnie bliskie ,
• jest odporny na manipulacje.

Wyniki z pracy magisterskiej

Szacowanie ze względu na liczbę agentów

Twierdzenie: Współczynnik aproksymacji mechanizmu PCD jest ograniczony od góry przez:

Wniosek: Poprawa znanego ograniczenia górnego na współczynnik aproksymacji optymalnego mechanizmu SP na dla dowolnego i .

Szacowanie ze względu na minimalną odległość między różnymi zgłoszeniami

Niech oznacza najmniejszą odległość między różnymi zgłoszeniami agentów.

Twierdzenie: Współczynnik aproksymacji mechanizmu PCD jest ograniczony od góry przez:

Wniosek: Ustanowienie ograniczenia oddzielonego od przy ustalonej liczbie wierzchołków grafu .

Mechanizmy SP o mniejszym współczynniku aproksymacji

Mechanizm RD+PCD

Definicja: z prawdopodobieństwem działa według jednego z mechanizmów: RD, PCD.
Motywacja: Współczynnik aproksymacji mechanizmu RD+PCD jest równy:

Wynik eksperymentów: współczynnik aproksymacji RD+PCD jest ograniczony przez .

Mechanizm R3PCD

Definicja: losuje ze zwracaniem -elementowy ciąg zgłoszeń agentów, a następnie aplikuje do niego mechanizm PCD.
Wynik eksperymentów: współczynnik aproksymacji R3PCD jest ograniczony przez .

Eksperymenty

Metodyka:

• numeryczne policzenie konkretnych wartości współczynnika aproksymacji różnych mechanizmów dla zbiorów stanów świata (dla różnych ),
• obserwacja podzbiorów stanów świata, dla których mechanizmy działają źle, i wykonanie dla nich dalszych eksperymentów.

Dziękuję za uwagę