Correspondência "justa" do peso máximo

Estou interessado em uma variante da correspondência máxima de peso em um gráfico, que chamo de "Máxima correspondência justa".

Assume-se que o gráfico está cheio (ou seja, $E=V\times V$ ), tem ainda o número de vértices, e que o peso é dada por uma função de lucro . Dado um correspondente , denotado por o lucro da aresta é correspondido. $p:{V\choose 2}\to \mathbb N$ $M$ $M(v)$ $v$

Um correspondente é um iff correspondente justo, para quaisquer dois vértices : $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)$

Ou seja, se para qualquer vértice , a correspondência com um vértice der lucro maior do que com o vértice , uma correspondência justa deve ser suficiente . $w\in V$ $w$ $v$ $u$ $M(v)\geq M(u)$

Podemos encontrar uma combinação justa de peso máximo de forma eficiente?

Um caso interessante é quando o gráfico é bipartido e a justiça se aplica apenas a um lado, ou seja, assume que , e recebemos uma função de lucro . $G=(L\cup R,L\times R)$ $p:L\times R\to \mathbb N$

Uma correspondência bipartida justa é uma correspondência em modo que, para quaisquer dois vértices : $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)$

Quão rápido podemos encontrar uma correspondência bipartida justa e com peso máximo?

A motivação para esse problema vem do caso especial bipartido. Suponha que você tenha trabalhadores e tarefas, e o trabalhador possa produzir lucrar com o trabalho . O problema aqui é projetar um razoável (em certo sentido, os trabalhadores não se sentirão "enganados"), enquanto maximiza o total de recompensas (existe uma troca aqui entre o poder do mecanismo de atribuição e o benefício social). $n$ $m$ $i$ $p_{i,j}$ $j$

Se definirmos o bem-estar social (ou o lucro da fábrica) da atribuição de trabalhadores a empregos como a soma dos lucros.

Observando diferentes cenários para o poder do responsável pela tarefa, obtemos os seguintes resultados:

Se for permitido atribuir qualquer trabalhador a qualquer trabalho, podemos otimizar a fábrica com eficiência (basta encontrar uma correspondência de peso máximo).
Se todo trabalhador escolher uma tarefa sozinho, assumindo que seu trabalho será selecionado (apenas um único trabalho pode ser selecionado para cada trabalho), caso ele seja o trabalhador mais qualificado que escolheu a tarefa, os trabalhadores convergirão para o '' ganancioso '' 'equilíbrio. O motivo é que o trabalhador que poderia ganhar mais ( ) escolherá o trabalho mais lucrativo e assim por diante. Pela taxa de aproximação do algoritmo ganancioso de correspondência, isso deve fornecer uma aproximação 2 do bem-estar social máximo possível. $i=\mbox{argmax}_i \max_j p_{i,j}$

Estou procurando por algo intermediário. Vamos supor que poderíamos designar trabalhadores para empregos, mas temos que prometer que nenhum trabalhador "menos qualificado" ganha mais do que eles.

Como podemos encontrar uma ponderação máxima promissora "justiça" promissora para os funcionários de forma eficiente?

ds.algorithms graph-algorithms np-hardness matching bipartite-graphs RB
fonte

Tangencialmente, para o segundo caso (bipartido), parece fácil construir exemplos em que toda correspondência "justa" dá lucro ao primeiro trabalhador 1 e o restante zero, mesmo que existam correspondências "injustas" que dão lucro ao primeiro trabalhador e todos os outros lucram . Da mesma forma, exemplos em que a correspondência justa de peso máximo dá lucro a cada trabalhador , embora existam correspondências injustas que dão a cada trabalhador lucro em .

1 - 2 ϵ

$1−2\epsilon$

1 - ϵ

$1−\epsilon$

2 / n

$2/n$

{1 - ϵ, 1 - 2 ϵ}

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

Neal Young

@NealYoung - estou correto ao assumir que esses cenários não podem existir se os lucros forem distintos?

Parece uma questão padrão na teoria dos jogos, em que a incapacidade de distinguir entre alternativas reduz significativamente o bem-estar social.

Opa, retiro meu comentário - não tenho certeza se esses exemplos são realizáveis, afinal!

Neal Young

Eu acredito que "correspondência bipartida justa e com peso máximo", como você definiu, é difícil para NP. Ainda mais, é difícil determinar a existência de uma correspondência bipartida justa.

Antes de fazer um esboço de prova, para intuição, considere a pequena instância a seguir. Tome onde , . Tome tal que para e , enquanto para e . Em seguida, e são equivalentes, no sentido de que para todos , portanto, qualquer correspondência feira deve dar e o mesmo lucro. Portanto, as únicas correspondências justas correspondem $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$ e para e , ou eles correspondem e para e . Usando esse tipo de gadget, podemos forçar a coordenação das arestas na correspondência. Essa é a base da redução. $b$ $c$ $d$ $a$ $b$ $e$ $f$

Aqui está uma tentativa de prova. Está um pouco envolvido. Provavelmente existem alguns erros, mas espero que quaisquer erros possam ser corrigidos.

Lema 1. Dados e conforme descrito no problema, determinar se contém uma correspondência justa é NP -Difícil. $G'=(L, R, E'=L\times R)$ $p:E'\rightarrow\mathbb{R}_+$ $G'$

Esboço de prova. A prova é por redução do Conjunto Independente em gráficos cúbicos. Seja uma instância do Conjunto Independente, onde é um gráfico cúbico (todo vértice possui grau 3). Descrevemos como construir um gráfico e a função de lucro modo que tenha uma correspondência bipartida justa se e somente se tiver um conjunto independente de tamanho . $(G=(V,E),k)$ $G'$ $G'=(L, R, E'=L\times R)$ $p:E'\rightarrow\mathbb{R}_+$ $G'$ $G$ $k$

Os vértices em virão em pares, chamados parceiros . Da mesma forma para os vértices . Para cada vértice , vamos denotar o parceiro de . Cada vértice e seu parceiro serão equivalentes , o que significa que Consequentemente, qualquer correspondência justa deve atribuir o mesmo lucro a e . A seguir, usamos para denotar o valor de . $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)$

Além disso, para cada par em e cada par de parceiros em , criamos ou criamos No primeiro caso, dizemos que permitimos que e correspondam a e (porque isso atribuiria o mesmo lucro a e , conforme necessário). No último caso, dizemos que impedimos e de serem (ambos) correspondidos a e $\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'$ (porque isso não atribuiria o mesmo lucro a e ).

ℓ

$\ell$

ℓ^{'}

$\ell'$

Como o gráfico dado é cúbico, satisfaz, e qualquer conjunto independente do tamanho em ocorre exatamente em arestas. Suponha, com facilidade, que . $G=(V,E)$ $3|V|=2|E|$ $I$ $k$ $G$ $3k$ $V=\{1,2,\ldots,n\}$

Para cada aresta , faça o seguinte. $\{i, j\}\in E$

Adicionar um par de vértices parceiros para . $r(\{i,j\}), r'(\{i,j\})$ $R$
Para endpoint , adicionar um par de parceiro vértices para . Set permitindo que e correspondam a e . $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\})$
Simetricamente, para o outro ponto de extremidade : adicione outro par de vértices parceiros a e defina permitindo e para corresponder a e . $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\})$

Para cada e adicionados até agora, se o par não tiver permissão explícita (acima) de corresponder a , evite a correspondência atribuindo e possuem um número único. $\ell\in L$ $r\in R$ $\ell, \ell'$ $r, r'$ $\pi(\ell, r)$ $\pi(\ell, r')$

Em seguida, adicionar pares de enchimento vértices para . Para cada vértice de preenchimento e cada , defina . $3(|V|-k)$ $R$ $r$ $\ell(i,j)\in L$ $\pi(\ell(i,j), r) = 0$

Finalmente, adicione dois vértices e (parceiros) de , junto com dois vértices e (também parceiros) para . Defina , permitindo que e sejam correspondidos a e . Para todos os outros vértices , defina para um número único. (Portanto, qualquer correspondência justa deve corresponder a e a e .) Para cada $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$ , Para cada aresta incidente , conjunto e . $\{i,j\}\in E$ $\pi(\ell(i,j), R_0) = i$ $\pi(\ell(i,j), R'_0) = |V|-i+1$

Isso completa a redução. Para finalizar, provamos que está correto.

Primeiro considere para quais pares de vértices o último domina o anterior, ou seja, $\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).$

Considerando os lucros atribuídos às arestas incidentes em e , essa condição só pode ser atendida se e, inspecionando a definição de para as arestas restantes, a condição é suficiente. Portanto, uma correspondência é justa se, e somente se, atribuir e a e , e também, para cada , der o mesmo lucro a todos os vértices em $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\}.$

Primeiro, suponha que tenha um conjunto independente de tamanho . Obtenha uma correspondência justa para de seguinte maneira. $G$ $I$ $k$ $G'$ $I$

Combine e com e . $L_0$ $L'_0$ $R_0$ $R'_0$

Para cada vértice , sejam suas três arestas de incidência. Para cada aresta , combine o vértice e seu parceiro a e . Isso fornece todos os vértices em lucro . $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$

Para cada um dos vértices , para cada uma das três arestas incidente em , combine e seu parceiro a um par único de vértices de preenchimento e seu parceiro . Isso fornece todos os vértices em lucro . $|V|-k$ $i\in V\setminus I$ $\{i,j\}$ $i$ $\ell(i,j)$ $\ell'(i,j)$ $r$ $r'$ $N(i)$ $0$

Portanto, essa correspondência é justa.

Em seguida, suponha que tem uma feira de correspondência . $G'$ $M$

$M$ deve corresponder a e a e . Para cada , a correspondência deve dar a cada um dos vértices em o mesmo lucro. Para cada , seu parceiro também está em . Portanto, inspecionando a redução, o lucro de cada um desses vértices deve ser (nesse caso, todos os seis vértices em são correspondidos aos vértices e seus parceiros) ou zero (nesse caso, todos os seis vértices em são correspondidos aos vértices de preenchimento em ). Deixei $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$ o conjunto de vértices para os quais o primeiro caso é válido. Para cada aresta , o vértice e seu parceiro são correspondidos a um vértice. Daqui resulta que sou um conjunto independente. Como o número de vértices de preenchimento é , o tamanho de deve ser pelo menos . $\{i,j\}$ $r(\{i,j\})$ $I$ $6(|V|-k)$ $I$ $k$

QED (?)

Eu acho que é basicamente correto, se um pouco complicado. Deixe-me saber se você encontrar algum erro ou uma maneira de simplificar a prova.

A redução acima pressupõe que não há problema em aceitar. Se isso for indesejável, acho que podemos preencher comvértices de preenchimento, atribuindo lucro 0 a todas as suas arestas, exceto as arestas a e . Podemos atribuir lucros às últimas arestas para garantir que os vértices de preenchimento não sejam dominados por (nem dominem) qualquer outro vértice. $|R|>|L|$ $L$ $|R|-|L|$ $R_0$ $R'_0$

Neal Young
fonte

Correspondência "justa" do peso máximo

Respostas: