Dopasowanie masy „sprawiedliwe”

Interesuje mnie wariant maksymalnego dopasowania wagi na wykresie, który nazywam „maksymalnym uczciwym dopasowaniem”.

Załóżmy, że wykres jest pełny (tj $E=V\times V$ ) Ma liczbę nawet wierzchołków, a masa jest podawana przez funkcję zysk . Biorąc pod uwagę pasujące , oznacz przez zysk krawędzi jest dopasowany. $p:{V\choose 2}\to \mathbb N$ $M$ $M(v)$ $v$

Pasujące jest sprawiedliwym pasującym iff, dla dowolnych dwóch wierzchołków : $M$ $u,v\in V$

(\forall w \in V : p ({w, v}) \geq p ({w, u})) \to M (v) \geq M (u)

$(\forall w\in V:\ \ p(\{w,v\})\geq p(\{w,u\}))\to M(v)\geq M(u)$

Oznacza to, że jeśli dla dowolnego wierzchołka , dopasowanie do wierzchołka daje większy zysk niż dopasowanie go do wierzchołka , wystarczające dopasowanie musi wystarczyć . $w\in V$ $w$ $v$ $u$ $M(v)\geq M(u)$

Czy możemy znaleźć skuteczne dopasowanie do maksymalnej wagi w sposób efektywny?

Ciekawym przypadkiem jest to, że wykres jest dwustronny, a uczciwość dotyczy tylko jednej strony, to znaczy, że , a otrzymujemy funkcję zysku . $G=(L\cup R,L\times R)$ $p:L\times R\to \mathbb N$

Fair dwustronny Dopasowanie to dopasowanie w , że dla dowolnych dwóch wierzchołków : $G$ $u,v\in L$

(\forall w \in R : p ({v, w}) \geq p ({u, w})) \to M (v) \geq M (u)

$(\forall w\in R:\ \ p(\{v,w\})\geq p(\{u,w\}))\to M(v)\geq M(u)$

Jak szybko możemy znaleźć maksymalne obciążenie dla uczciwego dwustronnego dopasowania?

Motywacja tego problemu wynika z dwustronnego specjalnego przypadku. Załóżmy, że masz pracowników i zadań, a pracownik może wygenerować zysku z pracy . Problem polega na zaprojektowaniu rozsądnego (w pewnym sensie pracownicy nie będą czuć się „oszukani”), przy jednoczesnym maksymalizowaniu całkowitych wypłat (istnieje tutaj kompromis między siłą mechanizmu przypisania a świadczeniem społecznym). $n$ $m$ $i$ $p_{i,j}$ $j$

Jeśli zdefiniujemy zasiłek socjalny (lub zysk fabryczny) przypisania pracowników do miejsc pracy jako sumę zysków.

Patrząc na różne scenariusze dotyczące siły osoby zlecającej zadanie, otrzymujemy następujące wyniki:

Jeśli wolno nam przypisać dowolnego pracownika do dowolnego zadania, możemy skutecznie zoptymalizować fabrykę (wystarczy znaleźć dopasowanie o maksymalnej masie).
Jeśli każdy pracownik sam wybierze zadanie, zakładając, że jego praca zostanie wybrana (dla każdej pracy można wybrać tylko jedną pracę), jeśli będzie on najlepiej wykwalifikowanym pracownikiem, który wybrał to zadanie, robotnicy staną się „chciwi” ' równowaga. Powodem jest to, że pracownik, który mógłby najwięcej zarobić ( ) wybierze najbardziej dochodową pracę i tak dalej. Przy współczynniku aproksymacji chciwego algorytmu dopasowywania powinno to dać przybliżone 2 maksymalne możliwe zabezpieczenie społeczne. $i=\mbox{argmax}_i \max_j p_{i,j}$

Szukam czegoś pośredniego. Załóżmy, że możemy przypisać pracowników do pracy, ale musimy obiecać im, że żaden „mniej wykwalifikowany” pracownik nie zarabia więcej niż oni.

Jak skutecznie znaleźć maksymalne dopasowanie wagi obiecujące „uczciwość” do pracowników?

ds.algorithms graph-algorithms np-hardness matching bipartite-graphs RB
źródło

Stycznie dla drugiego (dwustronnego) przypadku wydaje się łatwe do skonstruowania przykłady, w których każde „sprawiedliwe” dopasowanie daje pierwszemu pracownikowi zysk 1, a pozostałe zero, mimo że istnieją „niesprawiedliwe” dopasowania dające pierwszemu pracownikowi i wszyscy inni zyskują . Podobnie przykłady, w których uczciwe dopasowanie maksymalnej wagi daje każdemu pracownikowi zysk , mimo że istnieją niesprawiedliwe dopasowania dające zysk każdemu pracownikowi w .

1 - 2 ϵ

$1−2\epsilon$

1 - ϵ

$1−\epsilon$

2 / n

$2/n$

{1 - ϵ, 1 - 2 ϵ}

$\{1-\epsilon,1-2\epsilon\}$

Neal Young,

@NealYoung - czy słusznie zakładam, że te scenariusze nie mogą istnieć, jeśli zyski są różne?

Wydaje się, że jest to standardowy problem w teorii gier, w którym niemożność rozróżnienia alternatyw znacznie obniża poziom opieki społecznej.

Ups, cofam mój komentarz - nie jestem pewien, czy te przykłady są w końcu możliwe do zrealizowania!

Neal Young,

Uważam, że „maksymalne obciążenie uczciwe dwustronne dopasowanie”, jak już zdefiniowałeś, jest NP-trudne. Co więcej, ustalenie istnienia rzetelnego dwustronnego dopasowania jest trudne dla NP.

Przed podaniem szkicu próbnego, dla intuicji, rozważ następującą małą instancję. Weźmy gdzie , . Weź tak, że dla i , podczas gdy dla i . Następnie i są ekwiwalentne w takim sensie, że dla wszystkich , tak pasującego uzasadniona musi dać i taki sam wynik. Dlatego jedyne uczciwe dopasowania pasują do siebie $G'=(L, R, E'=L\times R)$ $L=\{a,b\}$ $R=\{c,d,e,f\}$ $p$ $p(u,w) = 0$ $u\in L$ $w\in\{c,d\}$ $p(u,w) = 1$ $u\in L$ $w\in\{e,f\}$ $a$ $b$ $p(a, w) = p(b, w)$ $w\in R$ $a$ $b$ $a$ i z i , albo dopasować i do i . Za pomocą tego rodzaju gadżetu możemy wymusić koordynację krawędzi w dopasowaniu. To jest podstawa redukcji. $b$ $c$ $d$ $a$ $b$ $e$ $f$

Oto próba dowodu. To jest trochę zaangażowane. Prawdopodobnie są jakieś błędy, ale mam nadzieję, że wszelkie błędy można naprawić.

Lemat 1. Biorąc pod uwagę i zgodnie z opisem problemu, ustalenie, czy zawiera prawidłowe dopasowanie, to NP -ciężko. $G'=(L, R, E'=L\times R)$ $p:E'\rightarrow\mathbb{R}_+$ $G'$

Szkic próbny. Dowodem jest redukcja z Independent Set w grafach sześciennych. Niech będzie danym wystąpieniem zbioru niezależnego, gdzie jest wykresem sześciennym (każdy wierzchołek ma stopień 3). Opisujemy, jak skonstruować wykres i funkcję zysku tak, że ma sprawiedliwe dopasowanie dwustronne, jeśli i tylko jeśli ma niezależny zestaw wielkości . $(G=(V,E),k)$ $G'$ $G'=(L, R, E'=L\times R)$ $p:E'\rightarrow\mathbb{R}_+$ $G'$ $G$ $k$

Wierzchołki w przyjdą parami, zwanymi partnerami . Podobnie do wierzchołków . Dla każdego wierzchołka , pozwalamy oznaczać partnera . Każdy wierzchołek i jego partner będą równoważne , co oznacza, że utworzymy W konsekwencji każde uczciwe dopasowanie musi przypisać ten sam zysk do i . W poniższym przykładzie używamy do oznaczenia wartości . $L$ $R$ $v\in L\cup R$ $v'$ $v$ $\ell\in L$ $\ell'\in L$

p (ℓ, r) = p (ℓ^{'}, r) for all r \in R .

$p(\ell, r) = p(\ell', r) \text{ for all } r\in R.$

ℓ

$\ell$

ℓ^{'}

$\ell'$

π (ℓ, r)

$\pi(\ell, r)$

p (ℓ, r) = p (ℓ^{'}, r)

$p(\ell,r) = p(\ell', r)$

Ponadto, dla każdej pary w i każdej pary partnerów w , albo robimy lub tworzymy W pierwszym przypadku mówimy, że zezwalamy na dopasowanie i do i (ponieważ w ten sposób przypisano by ten sam zysk do i , zgodnie z wymaganiami). W tym drugim przypadku mówimy, że zapobiegamy dopasowaniu i (oba) do i $\ell$ $L$ $r, r'$ $R$

π (ℓ, r) = π (ℓ, r^{'})

$\pi(\ell, r) = \pi(\ell, r')$

π (ℓ, r) \neq π (ℓ, r^{'}) .

$\pi(\ell, r) \ne \pi(\ell, r').$

ℓ

$\ell$

ℓ^{'}

$\ell'$

r

$r$

r^{'}

$r'$

ℓ

$\ell$

ℓ^{'}

$\ell'$

ℓ

$\ell$

ℓ^{'}

$\ell'$

r

$r$

r^{'}

$r'$ (ponieważ zrobienie tego nie przypisałoby tego samego zysku do i ).

ℓ

$\ell$

ℓ^{'}

$\ell'$

Ponieważ podany wykres jest sześcienny, spełnia on, a każdy niezależny zestaw o rozmiarze w ma dokładnie krawędzi. Załóżmy dla ułatwienia, że . $G=(V,E)$ $3|V|=2|E|$ $I$ $k$ $G$ $3k$ $V=\{1,2,\ldots,n\}$

Dla każdej krawędzi wykonaj następujące czynności. $\{i, j\}\in E$

Dodawanie pary wierzchołków partnerem do . $r(\{i,j\}), r'(\{i,j\})$ $R$
Dla punktów końcowych dodać parę partnera wierzchołki do . Ustaw umożliwiając dopasowanie i do i . $i$ $\ell(i,j), \ell'(i,j)$ $L$
$π (ℓ (i, j), r ({i, j})) = π (ℓ (i, j), r^{'} ({i, j})) = i,$ $\pi(\ell(i,j), r(\{i,j\})) = \pi(\ell(i,j), r'(\{i,j\}))= i,$ $\ell(i,j)$ $\ell'(i,j)$ $r(\{i,j\})$ $r'(\{i,j\})$
Symetrycznie dla drugiego punktu końcowego : dodaj kolejną parę partnerskich wierzchołków do i ustaw dopuszczając i do dopasowania do i . $j$ $\ell(j,i), \ell'(j,i)$ $L$
$π (ℓ (j, i), r ({i, j}) = π (ℓ (j, i), r^{'} ({i, j})) = j,$ $\pi(\ell(j,i), r(\{i,j\}) = \pi(\ell(j,i), r'(\{i,j\}))= j,$ $\ell(j,i)$ $\ell'(j,i)$ $r(\{i,j\})$ $r'(\{i,j\})$

Dla każdego dodanego do tej pory i , jeśli para nie jest wyraźnie dozwolone (powyżej), aby dopasować do , to należy zapobiec dopasowaniu, przypisując i każdy jakiś unikalny numer. $\ell\in L$ $r\in R$ $\ell, \ell'$ $r, r'$ $\pi(\ell, r)$ $\pi(\ell, r')$

Następnie dodawano pary wypełniacza wierzchołki . Dla każdego wierzchołka wypełniacza każdego ustaw wartość . $3(|V|-k)$ $R$ $r$ $\ell(i,j)\in L$ $\pi(\ell(i,j), r) = 0$

Na koniec, dodać dwa wierzchołki i (partnerzy) do , wraz z dwoma wierzchołkami i (również partnerzy) do . Ustaw , umożliwiając i do i . Dla każdego innego wierzchołka ustaw na jakąś unikalną liczbę. (W związku z tym każde uczciwe dopasowanie musi pasować i do i .) Dla każdego $L_0$ $L'_0$ $L$ $R_0$ $R'_0$ $R$ $\pi(L_0, R_0) = \pi(L_0, R'_0) = 1$ $L_0$ $L'_0$ $R_0$ $R'_0$ $r\in R$ $\pi(L_0, r)$ $L_0$ $L'_0$ $R_0$ $R'_0$ $i\in V$ , dla każdej krawędzi zdarzenia , ustaw i . $\{i,j\}\in E$ $\pi(\ell(i,j), R_0) = i$ $\pi(\ell(i,j), R'_0) = |V|-i+1$

To kończy redukcję. Na koniec potwierdzamy, że jest poprawny.

Najpierw zastanów się, jakie pary wierzchołków to drugie dominuje pierwsze, to znaczy $\ell(i,j),\ell(i',j')\in L$

(\forall r \in R) π (ℓ (i, j), r) \leq π (ℓ (i^{'}, j^{'}), r) .

$(\forall r\in R)~\pi(\ell(i,j),r) \le \pi(\ell(i',j'), r).$

Biorąc pod uwagę zyski przypisane do krawędzi na i , warunek ten można spełnić tylko wtedy, gdy , i sprawdzając definicję dla pozostałych krawędzi, warunek jest wystarczający. Dlatego dopasowanie jest uczciwe tylko wtedy, gdy przypisuje i do i , a także, dla każdego , daje taki sam zysk wszystkim wierzchołkom w $R_0$ $R'_0$ $i=i'$ $\pi$ $i=i'$ $L_0$ $L'_0$ $R_0$ $R'_0$ $i\in V$

N (i) = {ℓ (i, j) : {i, j} \in E} \cup {ℓ^{'} (i, j) : {i, j} \in E} .

$N(i) = \{\ell(i,j) : \{i,j\}\in E\} \cup \{\ell'(i,j) : \{i,j\}\in E\}.$

Najpierw załóżmy, że ma niezależny zestaw o rozmiarze . Uzyskaj sprawiedliwe dopasowanie dla od w następujący sposób. $G$ $I$ $k$ $G'$ $I$

Dopasuj i do i . $L_0$ $L'_0$ $R_0$ $R'_0$

Dla każdego wierzchołka niech będą trzema krawędziami zdarzenia. Dla każdej krawędzi dopasuj wierzchołek i jego partnera do i . Daje to wszystkie wierzchołki w zysku . $i\in I$ $\{i,j_1\}, \{i,j_2\}, \{i,j_3\}$ $\{i, j_h\}$ $\ell(i,j_h)$ $\ell'(i,j_h)$ $r(\{i,j_h\})$ $r'(\{i, j_h\})$ $N(i)$ $i$

Dla każdego z wierzchołków , dla każdej z trzech krawędzi incydentu z , match i jego partner do jakiejś unikalnej pary wierzchołków wypełniacza i jego partnera . Daje to wszystkim wierzchołkom zysku . $|V|-k$ $i\in V\setminus I$ $\{i,j\}$ $i$ $\ell(i,j)$ $\ell'(i,j)$ $r$ $r'$ $N(i)$ $0$

Dlatego dopasowanie jest uczciwe.

Następnie załóżmy, że ma sprawiedliwy pasujący . $G'$ $M$

$M$ musi pasować i do i . Dla każdego dopasowanie musi dać każdemu wierzchołkowi w taki sam zysk. Dla każdego jego partner również znajduje się w . Tak więc, przez inspekcję redukcji, zysk z każdego takiego wierzchołka musi być albo (w tym przypadku wszystkie sześć wierzchołków są dopasowane do wierzchołków i ich partnerzy) lub zero (w którym to przypadku wszystkie sześć wierzchołków w jest dopasowanych do wypełniających wierzchołków w ). Pozwolić $L_0$ $L'_0$ $R_0$ $R'_0$ $i\in V$ $N(i)$ $\ell(i,j)\in N(i)$ $\ell'(i,j)$ $N(i)$ $i$ $N(i)$ $r(\{i,j\})$ $N(i)$ $R$ $I$ zbiorem wierzchołków, dla których obowiązuje poprzednia sprawa. Dla każdej krawędzi każdy wierzchołek i jego partner są dopasowani do jednego wierzchołka. Wynika z tego że niezależnym zestawem. Ponieważ liczba wierzchołków wypełniających wynosi , rozmiar musi wynosić co najmniej . $\{i,j\}$ $r(\{i,j\})$ $I$ $6(|V|-k)$ $I$ $k$

QED (?)

Myślę, że jest to w zasadzie poprawne, choć trochę skomplikowane. Daj mi znać, jeśli zobaczysz jakieś błędy lub sposób na uproszczenie dowodu.

Powyższa redukcja zakłada, że przyjęcie jest w porządku . Jeśli to niepożądane, to przypuszczam, że możemy uzupełnić pomocąwypełniaj wierzchołki, przypisując zysk 0 do wszystkich ich krawędzi oprócz krawędzi do i . Możemy przypisać zyski do tych ostatnich krawędzi, aby upewnić się, że wierzchołki wypełniacza nie są zdominowane (ani zdominowane) przez żaden inny wierzchołek. $|R|>|L|$ $L$ $|R|-|L|$ $R_0$ $R'_0$

Neal Young
źródło

Dopasowanie masy „sprawiedliwe”

Odpowiedzi: