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×VE=V×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:(V2)→Np:(V2)→NMMM(v)M(v)vv
Um correspondente é um iff correspondente justo, para quaisquer dois vértices : MMu,v∈Vu,v∈V
(∀w∈V: p({w,v})≥p({w,u}))→M(v)≥M(u)(∀w∈V: p({w,v})≥p({w,u}))→M(v)≥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∈Vw∈VwwvvuuM(v)≥M(u)M(v)≥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∪R,L×R)G=(L∪R,L×R)p:L×R→Np:L×R→N
Uma correspondência bipartida justa é uma correspondência em modo que, para quaisquer dois vértices : u , v ∈ L ( ∀ w ∈ R : p ( { v , w } ) ≥ p ( { u , w } ) ) → M ( v ) ≥ M ( u )GGu,v∈Lu,v∈L
(∀w∈R: p({v,w})≥p({u,w}))→M(v)≥M(u)(∀w∈R: p({v,w})≥p({u,w}))→M(v)≥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).m i p i , j jnnmmiipi,jpi,jjj
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=argmaximaxjpi,ji=argmaximaxjpi,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?
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ϵ1−ϵ1−ϵ2/n2/n{1−ϵ,1−2ϵ}{1−ϵ,1−2ϵ}
@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!
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 correspondemG′=(L,R,E′=L×R)G′=(L,R,E′=L×R)L={a,b}L={a,b}R={c,d,e,f}R={c,d,e,f}ppp(u,w)=0p(u,w)=0u∈Lu∈Lw∈{c,d}w∈{c,d}p(u,w)=1p(u,w)=1u∈Lu∈Lw∈{e,f}w∈{e,f}aabbp(a,w)=p(b,w)p(a,w)=p(b,w)w∈Rw∈Raabbaa 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.bbccddaabbeeff
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×R)G′=(L,R,E′=L×R)p:E′→R+p:E′→R+
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=(V,E),k)G′G′G′G′vvℓ∈Lℓ∈Lℓ′∈Lℓ′∈Lℓℓℓ′ℓ′
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ℓℓLLr,r′r,r′
π(ℓ,r)≠π(ℓ,r′).π(ℓ,r)≠π(ℓ,r′).
rrr′r′ ℓℓℓ′ℓ′ (porque isso não atribuiria o mesmo lucro a e ).ℓℓℓ′ℓ′RR
Para endpoint , adicionar um par de parceiro vértices para . Set permitindo que e correspondam a e . iiℓ(i,j),ℓ′(i,j)ℓ(i,j),ℓ′(i,j)ℓ(i,j)ℓ(i,j)ℓ′(i,j)ℓ′(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 .jjℓ(j,i),ℓ′(j,i)ℓ(j,i),ℓ′(j,i)ℓ(j,i)ℓ(j,i)ℓ′(j,i)ℓ′(j,i)
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.ℓ∈Lℓ∈Lr∈Rr∈Rℓ,ℓ′ℓ,ℓ′π(ℓ,r)π(ℓ,r)π(ℓ,r′)π(ℓ,r′)LLR0R0R′0R0′L0L0L′0L0′r∈Rr∈Rπ(L0,r)π(L0,r)L0L0L′0L0′i∈Vi∈V, Para cada aresta incidente , conjunto e .{i,j}∈E{i,j}∈Eπ(ℓ(i,j),R0)=iπ(ℓ(i,j),R0)=iπ(ℓ(i,j),R′0)=|V|−i+1π(ℓ(i,j),R0′)=|V|−i+1i=i′i=i′L0L0L′0L0′i∈Vi∈V
N(i)={ℓ(i,j):{i,j}∈E}∪{ℓ′(i,j):{i,j}∈E}.N(i)={ℓ(i,j):{i,j}∈E}∪{ℓ′(i,j):{i,j}∈E}.
Combine e com e .L0L0L′0L0′
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∈Ii∈I{i,j1},{i,j2},{i,j3}{i,j1},{i,j2},{i,j3}{i,jh}{i,jh}ℓ(i,jh)ℓ(i,jh)ℓ′(i,jh)ℓ′(i,jh)N(i)N(i)ii
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|V|−ki∈V∖Ii∈V∖I{i,j}{i,j}iiℓ(i,j)ℓ(i,j)ℓ′(i,j)ℓ′(i,j)N(i)N(i)00
Portanto, essa correspondência é justa.
Em seguida, suponha que tem uma feira de correspondência .G′G′R0R0R′0R0′N(i)N(i)iiN(i)N(i)r({i,j})r({i,j})N(i)N(i)RRII 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}{i,j}r({i,j})r({i,j})II6(|V|−k)6(|V|−k)IIkk
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||R|>|L|LL|R|−|L||R|−|L|R0R0R′0R0′