Monotoniczność (projekt mechanizmu)

W projektowaniu mechanizmów monotoniczność jest właściwością funkcji wyboru społecznego . Jest to warunek konieczny, aby móc realizować funkcję z wykorzystaniem odpornego na strategię . Jego słowny opis to:

Jeśli zmiana typu jednego agenta (przy zachowaniu typów innych agentów niezmienionych) zmienia wynik w ramach funkcji wyboru społecznego, to wynikająca z tego różnica w użyteczności nowych i pierwotnych wyników ocenianych przy nowym typie tego agenta musi być co najmniej taka sama jak ta różnica w użyteczności ocenianej przy pierwotnym typie tego agenta.

Innymi słowy:

Jeśli wybór społeczny zmienia się, gdy pojedynczy gracz zmienia swoją wycenę, musi to być spowodowane tym, że gracz zwiększył swoją wartość nowego wyboru w stosunku do swojej wartości starego wyboru.

Notacja

Istnieje zestaw $.$ wyników

Istnieją $,$ którzy mają różne wyceny dla każdego wyniku. Wycena agenta jest reprezentowana jako funkcja: ${\ displaystyle i}$

$${\ Displaystyle v_ {i}: X \ longrightarrow R_ {+}}$$

który wyraża wartość, jaką przypisuje każdej alternatywie.

Wektor wszystkich funkcji wartości jest oznaczony przez ${\ displaystyle v}$ .

Dla każdego agenta ${$ wszystkich funkcji wartości innych agentów jest oznaczony przez $\ displaystyle v_ {-i}}$ . Więc ${\ Displaystyle v \ równoważnik (v_ {i}, v_ {-i})}$ .

Funkcja wyboru społecznego to funkcja, która jako dane wejściowe przyjmuje $displaystyle$ wartości i zwraca wynik $x \ in X}$ . Jest to oznaczone jako ${\ Displaystyle {\ tekst {Wynik}} (v)}$ lub ${\ Displaystyle {\ tekst {Wynik}} (v_ {i}, v_ { -i})}$ .

W mechanizmach bez pieniędzy

Funkcja wyboru społecznego spełnia właściwość silnej monotoniczności (SMON), jeśli dla każdego agenta $ja$ każdego ${ -i}}$ , jeśli:

$${\ Displaystyle x = {\ tekst {Wynik}} (v_ {i}, v_ {-i})}$$

$${\ Displaystyle x '= {\ tekst {Wynik}} (v'_ {i}, v_ {-i})}$$

Następnie:

$${\ Displaystyle x \ succeq _ {i} x'}$$

(według początkowych preferencji agent preferuje początkowy wynik).

$${\ Displaystyle x \ preceq _ {i'} x'}$$

(według ostatecznych preferencji agent preferuje ostateczny wynik). równoważnie:

$${\ Displaystyle v_ {i} (x) -v_ {i} (x ') \ geq 0}$$

$${\ Displaystyle v_ {i} '(x) -v_ {i}' (x') \ równoważnik 0}$$

Konieczność

Jeśli istnieje mechanizm odporny na strategię bez pieniędzy, z funkcją $funkcja$ musi

DOWÓD: Napraw jakiegoś agenta $v$ jakiś wektor wyceny $\ displaystyle v_ {-i}}$ . Odporność na strategię oznacza $,$ że ​​​​agent z realną wyceną $woli$$displaystyle v_ {i}}$ niż kłamać i deklarować ; stąd:

$${\ Displaystyle v_ {i} (x) \ geq v_ {i} (x ')}$$

Podobnie agent z realną wyceną $woli$ deklarować niż kłamać i deklarować $}$$v_$ ; stąd:

$${\ Displaystyle v_ {i} '(x') \ geq v_ {i}' (x)}$$

W mechanizmach z pieniędzmi

Kiedy mechanizmowi wolno używać pieniędzy, właściwość SMON nie jest już potrzebna do implementacji, ponieważ mechanizm może przełączyć się na alternatywę, która jest mniej preferowana dla agenta i zrekompensować agentowi pieniądze.

Funkcja wyboru społecznego spełnia właściwość słabej monotoniczności ( ${\ displaystyle v_ {i}, v_ {i} ', v_ { -i}}$ ), jeśli dla każdego agenta $ja$ każdego , jeśli:

$${\ Displaystyle x = {\ tekst {Wynik}} (v_ {i}, v_ {-i})}$$

$${\ Displaystyle x '= {\ tekst {Wynik}} (v'_ {i}, v_ {-i})}$$

Następnie:

$${\ Displaystyle v_ {i} (x) -v_ {i} (x ') \ geq v_ { i}'(x)-v_{i}'(x')}$$

Konieczność

$Jeśli$ istnieje mechanizm odporny na strategię z funkcją wyniku WMON

DOWÓD: Napraw jakiegoś agenta $v$ jakiś wektor wyceny $\ displaystyle v_ {-i}}$ . Mechanizm odporny na $która$ agent $}$ otrzymuje, gdy wynikiem mechanizmu jest ${\ displaystyle x}$ ; cena ta zależy od wyniku, ale nie może zależeć bezpośrednio od ${\ displaystyle v_ {i}}$ . Odporność na strategię oznacza $,$$displaystyle v_ {i}}'$ ​​​​gracz z wyceną $v ja$ deklarować deklarować ; stąd:

$${\ Displaystyle v_ {i} (x) + {\ tekst {cena} }_{i}(x,v_{-i})\geq v_{i}(x')+{\text{Cena}}_{i}(x',v_{-i})}$$

Podobnie, gracz z wyceną $niż$ woli deklarować deklarować $}}$$displaystyle$ v_ stąd:

$${\ Displaystyle v_ {i} '(x) + {\ tekst {Cena}}_{i}(x,v_{-i})\równoważnik v_{i}'(x')+{\text{Cena}}_{i}(x',v_{-i}) }$$

Odjęcie drugiej nierówności od pierwszej daje właściwość WMON.

Dostateczność

Monotoniczność nie zawsze jest wystarczającym warunkiem wykonalności, ale w kilku ważnych przypadkach jest wystarczająca (tj. każda funkcja wyboru społecznego WMON może zostać zaimplementowana):

• Gdy agenci mają jednoparametrowe funkcje użytkowe.
• W wielu domenach wypukłych, zwłaszcza gdy zakres każdej funkcji wartości wynosi ${\ displaystyle \ mathbb {R} ^ {+}}$ .
• Gdy zakres każdej funkcji wartości wynosi $.$ sześcian (Gui, Müller i Vohra (2004))
• W dowolnej domenie wypukłej (Saks i Yu (2005)).
• W dowolnej domenie z wypukłym zamknięciem.
• W dowolnej „domenie monotoniczności”.

Przykłady

1. Kiedy agenci mają preferencje o jednym piku , mediana funkcji wyboru społecznego (wybierająca medianę spośród wyników, które są najlepsze dla agentów) jest silnie monotoniczna . Rzeczywiście, mechanizm wybierania mediany głosów jest mechanizmem zgodnym z prawdą bez pieniędzy. Zobacz twierdzenie o medianie wyborcy .

2. Gdy agenci mają ogólne preferencje reprezentowane przez kardynalne funkcje użyteczności. utylitarna funkcja wyboru społecznego (wybór wyniku, który maksymalizuje sumę ocen agentów) nie jest silnie monotoniczna, ale jest słabo monotoniczna . Rzeczywiście, może to być zaimplementowane przez mechanizm VCG , który jest prawdziwym mechanizmem z pieniędzmi.

3. Własność słabej monotoniczności ma specjalną postać, gdy agenty mają jednoparametryczne funkcje użyteczności .

4. W planowaniu pracy funkcja wyboru społecznego z minimalizacją zakresu nie jest ani silnie monotoniczna, ani słabo monotoniczna. Rzeczywiście, nie można go wdrożyć za pomocą prawdziwego mechanizmu; zobacz rzetelne planowanie pracy .

Zobacz też

• Kryterium monotoniczności w systemach głosowania.
• Monotoniczność maski
• Inne znaczenia monotoniczności w różnych dziedzinach.