Daily Arxiv

Esta página recopila y organiza artículos sobre inteligencia artificial publicados en todo el mundo.
La información aquí presentada se resume utilizando Google Gemini y el sitio se gestiona sin fines de lucro.
Los derechos de autor de los artículos pertenecen a sus autores y a las instituciones correspondientes; al compartir el contenido, basta con citar la fuente.

Reconocimiento y obtención de perfiles de cruces simples débiles en árboles

Created by
  • Haebom

Autor

Palash Dey

Describir

En este artículo, presentamos y estudiamos el dominio débil de cruce simple en árboles, una generalización del dominio de cruce simple, ampliamente estudiado en la teoría de la elección social. Diseñamos un algoritmo de tiempo polinomial para reconocer perfiles de preferencia pertenecientes a este dominio y desarrollamos un algoritmo eficiente de recopilación de información que funciona incluso cuando las preferencias se acceden solo secuencialmente y la estructura subyacente del árbol de cruce simple no se conoce de antemano. También demostramos un límite inferior consistente para la complejidad de consulta del algoritmo de recopilación de información cuando el número de votantes es mucho mayor que el número de candidatos. Demostramos un límite inferior de $\Omega(m^2\log n)$ para el número de consultas que un algoritmo debe realizar para recopilar un perfil de cruce simple cuando se permiten consultas aleatorias. Esto resuelve el problema pendiente del artículo anterior y demuestra la optimalidad del algoritmo de recopilación de información de preferencias cuando se permiten consultas aleatorias.

Takeaways, Limitations

Takeaways: Contribuye a la solución del problema de selección social mediante la presentación de un algoritmo eficiente de reconocimiento y recopilación de información para dominios débiles de cruzamiento simple en árboles. Demuestra la optimalidad de los algoritmos existentes cuando se permiten consultas aleatorias y resuelve problemas no resueltos en estudios previos.
Limitations: El rendimiento del algoritmo puede variar según la proporción entre el número de votantes y el número de candidatos. Está limitado a una prueba de límite inferior en ciertas condiciones (cuando el número de votantes es mucho mayor que el de candidatos), y la eficiencia del algoritmo puede ser diferente en otras condiciones.
👍