Random Matching with Minimums

Resumo Técnico: Correspondência Aleatória com Mínimos

Enunciado do Problema
Este artigo aborda problemas de atribuição estocástica de objetos onde os objetos estão sujeitos tanto a restrições de capacidade máxima ($c_j$) quanto a restrições de requisito mínimo ($m_j$). Embora mecanismos padrão de atribuição aleatória (como a Ditadura Serial Aleatória ou o Mecanismo de Serial Probabilístico) lidem com restrições de capacidade, eles falham em garantir alocações implementáveis quando cotas mínimas estão presentes. O desafio central é construir um mecanismo de alocação aleatória que:

1. Produza uma alocação aleatória implementável (uma que possa ser decomposta em uma loteria sobre alocações determinísticas viáveis que satisfaçam todos os $m_j$ e $c_j$).
2. Alcance eficiência de Dominância Estocástica (DE) (eficiência de Pareto sob dominância estocástica de primeira ordem).
3. Mantenha propriedades de equidade (ausência de inveja e anonimato).
4. Preserve a incentivabilidade fraca no cenário de demanda unitária.

A literatura existente enfrenta um trade-off: mecanismos como o Serial Probabilístico Generalizado (SPG) de Budish et al. (2013) lidam com restrições bi-hierárquicas (apenas máximos), mas não conseguem representar mínimos. Por outro lado, o Serial Probabilístico Generalizado Constrained (SPGC) de Balbuzanov (2022) lida com restrições arbitrárias, mas requer a enumeração de todas as alocações determinísticas permitidas para caracterizar o poliedro viável. Essa enumeração é factorial em complexidade, tornando o SPGC computacionalmente intratável até mesmo para tamanhos de problema modestos.

Metodologia
Os autores propõem o mecanismo Serial Probabilístico de Mínimos (SPM). A metodologia procede em duas etapas principais:

1. Caracterização do Poliedro Viável:
   Em vez de enumerar o conjunto de alocações determinísticas $D$ (o que é computacionalmente proibitivo), os autores caracterizam diretamente o conjunto de alocações aleatórias implementáveis, denotado $\Delta_D$, usando um sistema de desigualdades lineares positivas.

   • Para o caso de demanda unitária ($d=1$), eles derivam um sistema específico de desigualdades (Proposição 3) que define o conjunto de contorno inferior $lcs(\Delta_D)$. Este sistema inclui:
     • Restrições de demanda unitária ($\sum_j \mu_{ij} \leq 1$).
     • Restrições de capacidade ($\mu_j \leq c_j$).
     • Um novo conjunto de restrições (Min-III) garantindo que, para qualquer subconjunto de objetos $S$ com mínimos, a probabilidade total atribuída a objetos fora de $S$ não exceda a capacidade dos agentes restantes de satisfazer os mínimos de $S$.
   • Esta caracterização é posteriormente simplificada em uma forma compacta (Proposição 4) envolvendo $\sum_j \max\{m_j, \mu_j\} \leq N$, o que facilita uma implementação algorítmica.
   • Para demanda geral ($d > 1$), eles fornecem um sistema mais complexo de desigualdades (Proposição 5) derivado usando o teorema de existência de Hoffman para circulações em redes.

2. Design do Mecanismo e Algoritmo:

   • Definição em Tempo Contínuo: O mecanismo SPM é definido como um processo de "consumo" em tempo contínuo (análogo ao Serial Probabilístico) onde os agentes consomem seu objeto disponível mais preferido a uma velocidade uniforme. Um objeto está "disponível" apenas se consumi-lo não violar as desigualdades lineares derivadas.
   • Algoritmo em Tempo Discreto: Aproveitando a estrutura específica das desigualdades de demanda unitária, os autores constroem o Algoritmo 1, um algoritmo discreto de tempo polinomial. O algoritmo procede em etapas onde os agentes consomem objetos até que uma restrição se torne vinculativa. Crucialmente, o algoritmo identifica um tempo crítico $\tau$ onde as restrições globais de mínimo tornam-se vinculativas. Em $\tau$, qualquer objeto que tenha atendido ao seu requisito mínimo é fechado para consumo adicional, garantindo que os agentes restantes sejam forçados a satisfazer os mínimos de outros objetos.

Resultados Principais
O artigo estabelece as seguintes propriedades teóricas para o mecanismo SPM:

• Eficiência DE: O mecanismo SPM produz alocações que são eficientes em Dominância Estocástica. Nenhuma outra alocação aleatória implementável é preferida por todos os agentes via dominância estocástica de primeira ordem.
• Equidade: O mecanismo é anônimo (invariante à reindexação dos agentes) e livre de inveja (nenhum agente prefere estritamente a loteria de outro agente).
• Incentivabilidade: No caso de demanda unitária, o SPM é fracamente incentivável. Os agentes não podem alcançar uma alocação estocasticamente dominante ao relatar incorretamente suas preferências. A prova baseia-se em mostrar que manipular preferências para alterar o tempo crítico $\tau$ ou os tempos de fechamento dos objetos nunca gera um benefício líquido para o agente que relata incorretamente.
  • Nota: Para demanda geral ($d > 1$), o mecanismo permanece eficiente em DE, anônimo e livre de inveja, mas a incentivabilidade fraca é perdida, consistente com as descobertas em Kojima (2009b).
• Implementação: A alocação aleatória resultante é garantida como implementável. Como as restrições são bi-hierárquicas (no sentido de Budish et al., 2013), o teorema de Birkhoff-von Neumann (ou sua generalização em BCKM13) garante que a alocação aleatória possa ser decomposta em uma loteria sobre alocações determinísticas viáveis.

Significado e Alegações
O artigo afirma preencher a lacuna entre mecanismos teóricos de atribuição aleatória e aplicações práticas envolvendo cotas mínimas (por exemplo, clubes escolares, equipes de projetos, seleção de júri).

• Viabilidade Computacional: A contribuição primária é fornecer o primeiro algoritmo viável para correspondência aleatória com mínimos. Ao evitar a complexidade factorial da enumeração de alocações determinísticas e a complexidade exponencial do problema de enumeração de facetas (FEP) exigido por Balbuzanov (2022), os autores fornecem um algoritmo de tempo polinomial para o caso de demanda unitária.
• Preservação de Incentivos: Ao contrário do mecanismo SPGC mais geral, que perde a incentivabilidade fraca, o mecanismo SPM preserva essa propriedade no cenário de demanda unitária.
• Extensão Teórica: O trabalho generaliza o mecanismo Serial Probabilístico para cenários com limites inferiores, demonstrando que eficiência e equidade podem ser mantidas mesmo quando a estrutura de restrições impede o uso de frameworks padrão bi-hierárquicos de apenas máximos.

Os autores afirmam explicitamente que, embora forneçam um algoritmo de tempo polinomial para demanda unitária, a descrição algorítmica para demanda geral ($d > 1$) permanece uma questão aberta para pesquisa futura devido ao aumento da complexidade do sistema de desigualdades.