Mecanismo sin arrepentimiento

En el diseño de mecanismos , un mecanismo de revelación de la verdad sin remordimientos ( RFTT , o mecanismo sin remordimientos para abreviar) es un mecanismo en el que cada jugador que revela su verdadera información privada no siente remordimiento después de ver el resultado del mecanismo. Un mecanismo sin remordimientos incentiva a los agentes que quieren evitar el remordimiento a informar sus preferencias de manera veraz.

La ausencia de arrepentimiento es una relajación de la veracidad : todo mecanismo veraz está libre de arrepentimiento, pero hay mecanismos libres de arrepentimiento que no son veraces. En consecuencia, los mecanismos libres de arrepentimiento existen incluso en situaciones en las que los resultados de imposibilidad fuertes impiden la existencia de mecanismos veraces.

Definición formal

Hay un conjunto finito X de resultados potenciales . Hay un conjunto N de agentes. Cada agente i tiene una preferencia P _i sobre X.

Un mecanismo o regla es una función f que toma como entrada las preferencias de los agentes P1,... , Pn, y devuelve como salida un resultado de X.

Las preferencias de los agentes son su información privada; por lo tanto, cada agente puede informar su verdadera preferencia o informar alguna preferencia falsa.

Se supone que, una vez que un agente observa el resultado del mecanismo, siente arrepentimiento si su informe es una estrategia dominada "en retrospectiva". Es decir: dadas todas las posibles preferencias de otros agentes, que sean compatibles con el resultado observado, existe un informe alternativo que le hubiera proporcionado el mismo resultado o uno mejor.

Un mecanismo de decir la verdad sin arrepentimiento ^[1] es un mecanismo en el que un agente que informa sus preferencias veraces nunca siente arrepentimiento.

En coincidencia

Fernández ^[2] estudia RFTT en emparejamiento bilateral. Muestra que:

• En un mercado de emparejamiento uno a uno, el algoritmo Gale-Shapley (GS) es RFTT para ambas partes, independientemente de cuál de las partes esté proponiendo. Además, GS es el único mecanismo RFTT dentro de la clase de mecanismos de emparejamiento estables en cuanto a cuantiles. Fuera de esa clase, hay otros mecanismos RFTT, pero no son naturales. En particular, el mecanismo de Boston y los ciclos de negociación más altos no son RFTT. Además, en un mercado GS, decir la verdad es el único informe que garantiza que no habrá arrepentimiento.
  • Por ejemplo, supongamos que hay dos mujeres: Alice y Batya, y dos hombres: Chen y Dan. Las preferencias de las mujeres son Alice: Dan>Chen, Batya:Chen>Dan. Las preferencias de los hombres son Dan:Batya>Ninguno>Alice, Chen:Alice>Batya. Supongamos que los hombres se proponen matrimonio. Entonces, con informes veraces, la coincidencia es Dan-Batya, Chen-Alice. Si Alice trunca sus preferencias e informa solo Dan, entonces la coincidencia es Batya-Chen, y Alice permanece desempleada. En este caso, Alice lamenta no haber sido honesta, ya que ser honesta garantizaría que esté empleada.
• En un mercado de emparejamiento de muchos a uno (como el emparejamiento entre hospitales y médicos), el GS que propone el médico es RFTT para ambas partes, pero el GS que propone el hospital no es RFTT. Esto respalda la decisión de NRMP de cambiar del GS que propone el hospital al GS que propone el médico.

Chen y Moller ^[3] estudian los mecanismos de elección de escuela . Se centran en la regla de aceptación diferida ajustada por eficiencia (EADA o EDA). ^[4] Se sabe que la EDA no es a prueba de estrategias para los estudiantes; Chen y Moller muestran que la EDA es RFTT. También muestran que ninguna regla de emparejamiento eficiente que domine débilmente en el sentido de Pareto una regla de emparejamiento estable es RFTT.

En la votación

Arribillaga, Bonifacio y Fernández ^[1] estudian las reglas de votación de RFTT . Demuestran que:

• Cuando una regla de votación depende únicamente de la alternativa superior de cada agente (por ejemplo, votación por pluralidad ), la RFTT es equivalente a la a prueba de estrategias . Esto significa que, para 3 o más resultados, los únicos mecanismos de RFTT son dictaduras (según el teorema de imposibilidad de Gibbard-Satterthwaite ); y para 2 resultados, un mecanismo es RFTT si y solo si es una regla de mayoría extendida .
  • Por ejemplo, para ver que la votación por mayoría simple no es una estrategia de elección para tres resultados, supongamos que la clasificación de preferencias de un agente es z>y>x. Si ve que se elige x, entonces, en retrospectiva, votar por y es una estrategia dominante: nunca puede hacer daño (ya que x ya es el peor resultado) y puede ayudar (si y y x estuvieran empatados).
• Para reglas de votación igualitarias : todas las variantes neutrales (es decir, que resuelven los empates mediante un orden fijo de agentes) son RFTT. Las variantes anónimas (que resuelven los empates mediante un orden fijo de candidatos) son RFTT si hay al menos m -1 votantes, o si el número de votantes divide a m -1.
• En el caso de la regla de veto (una regla de puntuación en la que todos los candidatos reciben 1 punto, excepto el menos preferido, que recibe 0), los resultados son similares a las reglas igualitarias. De manera similar, la aprobación k es RFTT.
• Es posible que otras reglas de puntuación no sean RFTT. En particular, la votación Borda , la votación por pluralidad y la votación Dowdall , y todas las reglas anónimas eficientes, no son RFTT.
• Todas las reglas de votación consistentes con Condorcet que también satisfacen una condición de monotonía débil no son RFTT. Esta condición se cumple, en particular, para las reglas de Simpson, Copeland, Young, Dodgson, Fishburn y Black (tanto en versiones anónimas como neutrales). Las reglas de eliminación sucesiva tampoco son RFTT.

En división justa

Tamuz, Vardi y Ziani ^[5] estudian el arrepentimiento en el corte justo de la tarta . Estudian una variante repetida del juego de cortar y elegir . En el juego estándar de cortar y elegir, un cortador reacio al riesgo cortaría en dos trozos iguales a sus ojos. Pero en su entorno, hay un cortador diferente cada día, jugando a cortar y elegir con el mismo elector. Cada cortador conoce todas las elecciones pasadas del elector y puede potencialmente explotar esta información para hacer un corte que le garantice más de la mitad de la tarta. Su objetivo es diseñar protocolos no explotables : protocolos en los que el cortador nunca puede saber qué trozo va a elegir el elector y, por lo tanto, siempre corta la tarta en dos trozos iguales a sus ojos. La idea es restringir las posiciones en las que el cortador puede cortar; estos protocolos se denominan protocolos de corte forzado . Un protocolo simple de corte forzado no explotable es el siguiente: cada día, se toman todos los trozos generados el día anterior (por cortes forzados y no forzados) y se obliga al cortador a cortar cada uno de estos trozos en dos. Este protocolo utiliza 2 ⁿ cortes, donde n es el número de días. Hay protocolos que utilizan menos cortes, dependiendo del número de dimensiones del pastel:

• Si el pastel es un conjunto convexo de n dimensiones, entonces existe un protocolo de corte forzado sin envidia que utiliza n cortes (un corte por día). Cada día, el cortador se ve obligado a realizar un corte en una dimensión diferente, ortogonal a todos los cortes anteriores, por lo que la información de los días anteriores no es útil.
• Si el pastel es unidimensional, entonces:
  • Existe un protocolo de corte forzado adaptativo sin envidia que utiliza 3 cortes por día. Cada día, hay un corte forzado adaptativo y el cortador debe realizar dos cortes adicionales (uno en cada lado del corte forzado).
  • No existe ningún protocolo de corte forzado no adaptativo que utilice un número fijo de cortes por día;
  • Existe un protocolo de corte forzado no adaptativo que utiliza O( n ² ) cortes, donde n es el número de días. En cada día, hay n cortes forzados en 1/( n +1),..., n /( n +1); el cortador debe realizar n +1 cortes (uno en cada intervalo).
• Si el pastel es un conjunto bidimensional (por ejemplo, un cuadrado), entonces existe un protocolo de corte forzado no adaptativo que utiliza 3 cortes por día. En cada día t , hay un corte forzado vertical en t /( n +1). El cortador debe hacer un corte horizontal en cada lado del corte vertical.

Cresto y Tajer ^[6] también estudian el arrepentimiento en el reparto justo de la torta entre dos agentes, donde el arrepentimiento surge de un cambio en las preferencias: después de que un jugador ve la elección del otro jugador, sus preferencias pueden cambiar. Proponen una variante de cortar y elegir que evita este tipo de arrepentimiento.

Referencias

1. Pablo Arribillaga, R .; Bonifacio, Agustín G.; Marcelo Ariel Fernández (2022). "Reglas de votación para decir la verdad sin arrepentimientos". arXiv : 2208.13853 [econ.TH].
2. Fernandez, Marcelo Ariel (31 de julio de 2020). "Aceptación diferida y decir la verdad sin arrepentimiento". Archivo de Documentos de Trabajo de Economía .
3. Chen, Yiqiu; Möller, Markus (2021). "Decir la verdad sin arrepentimiento en la elección de escuela con consentimiento". Revista electrónica SSRN . doi :10.2139/ssrn.3896306. ISSN  1556-5068. S2CID  236911018.
4. academic.oup.com https://academic.oup.com/qje/article-abstract/125/3/1297/1903670 . Consultado el 15 de enero de 2024 . {{cite web}}: Falta o está vacío |title=( ayuda )
5. Tamuz, Omer; Vardi, Shai; Ziani, Juba (25 de abril de 2018). "Protocolos no explotables para el corte repetido de tartas". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 32 (1). doi : 10.1609/aaai.v32i1.11472 . ISSN  2374-3468.
6. Cresto, Eleonora; Tajer, Diego (1 de mayo de 2022). "Corte justo de la torta para agentes imitativos". Elección social y bienestar . 58 (4): 801–833. doi :10.1007/s00355-021-01375-2. ISSN  1432-217X. S2CID  244276548.