Orientações EF1 e EFX

Estudamos o problema de encontrar alocações justas -- EF1 e EFX -- de bens indivisíveis com orientações. Em uma orientação, cada agente recebe itens de seu próprio conjunto pré-determinado. Para EF1, mostramos que as orientações EF1 sempre existem quando os agentes têm avaliações monótonas, por meio de um algoritmo de tempo pseudopolinomial. Este resultado surpreendentemente positivo é a principal contribuição do nosso artigo. Complementamos este resultado com um conjunto abrangente de cenários onde nosso algoritmo, ou uma leve modificação dele, encontra uma orientação EF1 em tempo polinomial. Para EFX, focamos nas instâncias de gráfico recentemente propostas, onde cada agente corresponde a um vértice em um gráfico e seu conjunto de itens permitidos consiste nas arestas incidentes ao seu vértice. Foi mostrado que encontrar uma orientação EFX é NP-completo em geral. Provamos que continua intratável mesmo quando o gráfico tem uma cobertura de vértice de tamanho 8, ou quando temos um multigráfo com apenas 10 vértices. Essencialmente, igualamos esses fortes resultados negativos com um algoritmo tratável de parâmetro fixo que é virtualmente o melhor que alguém poderia esperar.