[공지사항]을 빙자한 안부와 근황 
Show more

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

Este artículo introduce y estudia el dominio débil de cruzamiento simple en árboles, una generalización del dominio de cruzamiento simple bien 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 solo se pueden acceder secuencialmente y la estructura subyacente del árbol de cruzamiento simple no se conoce de antemano. También demostramos un límite inferior consistente en 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 Ω(m²log n) en el número de consultas que un algoritmo debe realizar para recopilar un perfil de cruzamiento simple cuando se permiten consultas aleatorias. Esto resuelve el problema abierto 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 al aspecto computacional de la teoría de la elección social al presentar un algoritmo eficiente de reconocimiento y recopilación de información para dominios débiles de cruzamiento simple en árboles. Aborda una cuestión pendiente de investigaciones previas al demostrar la optimalidad del algoritmo de recopilación de información de perfiles de cruzamiento simple cuando se permiten consultas aleatorias.
Limitations: El rendimiento del algoritmo puede variar según el tamaño relativo del número de votantes y el número de candidatos. En particular, el análisis del rendimiento se centra en el caso en que el número de votantes es mucho mayor que el de candidatos, por lo que la eficiencia del algoritmo podría ser menor en otras situaciones. Además, se necesita más investigación empírica sobre la eficacia de la prueba débil de dominio único cruzado en problemas de elección social del mundo real.
👍