Resumo Técnico: Suborno de Deslocamento em Redes Sociais

Definição do Problema

Este artigo introduz e analisa o Suborno de Deslocamento em Redes Sociais (Shift Bribery over Social Network), uma variante do clássico problema de Suborno de Deslocamento na escolha social computacional. No modelo clássico, um subornador busca promover um candidato preferido $c$ pagando eleitores para deslocar $c$ para uma posição superior em seus rankings de preferência. O custo é proporcional à distância do deslocamento. No entanto, o modelo clássico assume que os eleitores agem de forma independente.

O modelo proposto incorpora a influência social. Os eleitores são modelados como nós em um grafo direcionado e ponderado $G=(V, A, w)$, onde os arcos representam laços sociais e os pesos representam a força da influência. Quando um eleitor é subornado para deslocar sua preferência, esse deslocamento se propaga para seus vizinhos. Especificamente, se um eleitor $j$ desloca seu candidato preferido por $s_j$ posições, e existe um arco $(j, i)$ com peso $w(j, i)$, o eleitor $i$ recebe uma influência adicional de $s_j \cdot w(j, i)$. O deslocamento efetivo total para o eleitor $i$ é a soma de seu deslocamento direto e da influência recebida de todos os seus vizinhos. O objetivo é determinar se existe um vetor de deslocamento dentro de um orçamento $b$ tal que o candidato preferido $c$ se torne um vencedor após os efeitos do suborno direto e da influência propagada pela rede.

Metodologia

Os autores empregam uma combinação de teoria da complexidade clássica e análise de complexidade parametrizada para mapear o panorama computacional do problema.

1. Provas de Dureza: O artigo estabelece resultados de NP-completude e W[2]-dureza por meio de reduções de tempo polinomial a partir de problemas conhecidos e difíceis, especificamente Conjunto Dominante (Dominating Set) e Cobertura de Conjuntos (Set Cover). Essas reduções constroem instâncias de eleições específicas (frequentemente com dois candidatos e funções de custo de identidade) onde resolver o problema do suborno é equivalente a encontrar um conjunto dominante ou cobertura de conjuntos.
2. Design Algorítmico: Para classes de grafos e parametrizações específicas, os autores projetam algoritmos eficientes:
   • Programação Dinâmica (DP): Utilizada para grafos de caminho, grafos de clusters e grafos com largura de árvore (treewidth) limitada. Os estados da DP rastreiam o conjunto de vértices subornados e influenciados dentro das bolsas da decomposição em árvore.
   • Estratégias Gananciosas e de Busca: Aplicadas a grafos completos sob regras de maioria e pluralidade, aproveitando a monotonicidade das regras de votação para realizar buscas binárias ou cálculos de mediana.
   • Redução a Variantes do Conjunto Dominante: O problema é mapeado para o problema do $(k, t)$-Conjunto Dominante para estabelecer resultados de FPT (Fixed-Parameter Tractability).

Principais Contribuições e Resultados

1. Panorama de Complexidade para Grafos Gerais

O artigo demonstra que o Suborno de Deslocamento em Redes Sociais é significativamente mais difícil do que o Suborno de Deslocamento clássico devido à propagação de influência.

• NP-Completude: O problema é NP-completo mesmo para dois candidatos com funções de custo de identidade em grafos não direcionados gerais, grafos bipartidos e grafos acíclicos direcionados (DAGs). Isso contrasta com o Suborno de Deslocamento clássico, que é polinomial para as regras de maioria e pluralidade.
• W[2]-Dureza: O problema é W[2]-duro quando parametrizado pelo:
  • Orçamento ($b$).
  • Grau máximo do grafo.
  • Número de candidatos ($m$).
  • Número de eleitores subornados.
    Esses resultados de dureza mantêm-se mesmo para grafos conexos com dois candidatos, custos unitários e pesos de aresta uniformes.

2. Algoritmos de Tempo Polinomial para Classes Especiais de Grafos

Apesar da dureza geral, o problema torna-se tratável para topologias de rede específicas:

• Grafos Completos: Existem algoritmos de tempo polinomial tanto para as regras de maioria quanto de pluralidade com funções de custo lineares e pesos de aresta uniformes. A solução envolve encontrar a mediana do vetor de posição ou usar busca binária sobre possíveis valores de deslocamento.
• Torneios Transitivos: Um algoritmo de tempo linear ($O(n)$) é fornecido para o caso de dois candidatos com custos uniformes e pesos de aresta unitários.
• Grafos de Cluster: Um algoritmo de tempo pseudo-polinomial ($O(r \cdot b)$, onde $r$ é o número de cliques) é projetado usando programação dinâmica, tratando o problema como uma variação do problema da mochila sobre cliques.
• Grafos de Caminho: Um algoritmo de programação dinâmica que roda em $O(n^2 \cdot b)$ é apresentado para grafos de caminho com funções de custo lineares e a regra de maioria.

3. FPT (Fixed-Parameter Tractability)

Os autores identificam parâmetros sob os quais o problema é eficientemente solúvel:

• Largura de Árvore (Treewidth): O problema é FPT quando parametrizado pela largura de árvore do grafo (para dois candidatos, custos lineares e pesos uniformes). O algoritmo utiliza uma decomposição em árvore "legal" (nice tree decomposition) com um estado de DP que rastreia os conjuntos subornados e influenciados em cada bolsa.
• Número de Deleção de Vértice de Cluster: O problema é pseudo-FPT quando parametrizado pelo número de deleção de vértice de cluster (o número de vértices a serem removidos para tornar o grafo um grafo de cluster).
• Apoio Adicional Necessário: O problema é FPT quando parametrizado pelo número de apoiadores adicionais necessários para atingir a maioria ($\lceil (n+1)/2 \rceil - \ell$), via uma redução ao problema do $(k, t)$-Conjunto Dominante.

Significância e Alegações

O artigo afirma iniciar uma exploração sistemática do suborno no contexto de redes sociais, preenchendo a lacuna entre modelos clássicos de manipulação eleitoral e maximização de influência em redes.

• Contribuição Teórica: O trabalho fornece um detalhado panorama de complexidade, identificando os limites precisos entre instâncias tratáveis e intratáveis baseados na topologia do grafo (ex: completo vs. cluster vs. geral) e parâmetros (ex: orçamento, largura de árvore).
• Relevância Prática: Os autores argumentam que o modelo oferece uma abstração mais realista de campanhas e persuasão, onde influenciar alguns indivíduos bem conectados pode ter efeitos em cascata. Os resultados de dureza destacam a dificuldade inerente de controlar resultados em ambientes em rede, enquanto os algoritmos FPT oferecem soluções potenciais para redes com propriedades estruturais específicas (ex: baixa largura de árvore ou estruturas de comunidade).
• Direções Futuras: O artigo sugere modestamente que trabalhos futuros poderiam focar no design de algoritmos de aproximação de tempo polinomial ou esquemas de aproximação de parâmetro fixo, particularmente para regras de votação mais ricas como Borda e Copeland, onde as barreiras estruturais atuais permanecem.

Em resumo, o artigo estabelece que, embora a influência social amplifique o poder do suborno, ela também introduz uma complexidade computacional significativa, tornando o problema intratável em configurações gerais, mas solúvel para redes específicas e estruturalmente restritas.