Conocimiento común (lógica) - Common knowledge (logic)

El conocimiento común es un tipo de conocimiento especial para un grupo de agentes . Existe un conocimiento común de p en un grupo de agentes G cuando todos los agentes en G conocen p , todos saben que conocen p , todos saben que todos saben que conocen p , y así ad infinitum .

El concepto fue introducido por primera vez en la literatura filosófica por David Kellogg Lewis en su estudio Convención (1969). El sociólogo Morris Friedell definió el conocimiento común en un artículo de 1969. Robert Aumann (1976) le dio por primera vez una formulación matemática en un marco teórico de conjuntos . Los informáticos se interesaron por el tema de la lógica epistémica en general, y del conocimiento común en particular, a partir de la década de 1980. Existen numerosos acertijos basados ​​en el concepto que han sido ampliamente investigados por matemáticos como John Conway .

El filósofo Stephen Schiffer , en su libro Significado de 1972 , desarrolló independientemente una noción que llamó "conocimiento mutuo" que funciona de manera bastante similar al "conocimiento común" de Lewis y Friedel de 1969.

Ejemplo

Rompecabezas

La idea de conocimiento común a menudo se introduce mediante alguna variante de acertijos de inducción :

En una isla hay k personas que tienen ojos azules y el resto de personas tienen ojos verdes. Al comienzo del rompecabezas, nadie en la isla conoce su propio color de ojos. Por regla general, si una persona en la isla descubre que tiene los ojos azules, esa persona debe abandonar la isla al amanecer; cualquiera que no haga tal descubrimiento siempre duerme hasta después del amanecer. En la isla, cada persona conoce el color de ojos de las demás, no hay superficies reflectantes y no hay comunicación del color de ojos.

En algún momento, un forastero llega a la isla, convoca a todas las personas de la isla y hace el siguiente anuncio público: "Al menos uno de ustedes tiene los ojos azules". El forastero, además, es conocido por todos por ser veraz, y todos saben que todos saben esto, y así sucesivamente: es de conocimiento común que él es veraz, y por lo tanto se hace de conocimiento común que hay al menos un isleño que tiene azul ojos. El problema: asumiendo que todas las personas en la isla son completamente lógicas y que esto también es de conocimiento común, ¿cuál es el resultado final?

Solución

La respuesta es que, al amanecer del día k después del anuncio, todas las personas de ojos azules abandonarán la isla.

Prueba

La solución se puede ver con un argumento inductivo. Si k  = 1 (es decir, hay exactamente una persona de ojos azules), la persona reconocerá que solo él tiene ojos azules (al ver solo ojos verdes en los demás) y se irá al primer amanecer. Si k  = 2, nadie se irá al primer amanecer. Las dos personas de ojos azules, viendo sólo una persona con ojos azules, y que nadie se fue el primer amanecer (y por lo tanto k  > 1), se irán el segundo amanecer. Inductivamente, se puede razonar que nadie se irá a los primeros k  - 1 amanece si y solo si hay al menos k personas de ojos azules. Aquellos con ojos azules, viendo k  - 1 personas de ojos azules entre los demás y sabiendo que debe haber al menos k , razonarán que deben tener ojos azules y se irán.

Lo más interesante de este escenario es que, para k  > 1, el forastero solo les está diciendo a los ciudadanos de la isla lo que ya saben: que hay personas de ojos azules entre ellos. Sin embargo, antes de que se anuncie este hecho, el hecho no es de dominio público .

Para k  = 2, es simplemente conocimiento de "primer orden". Cada persona de ojos azules sabe que hay alguien con ojos azules, pero cada persona de ojos azules no sabe que la otra persona de ojos azules tiene este mismo conocimiento.

Para k  = 3, es conocimiento de "segundo orden". Cada persona de ojos azules sabe que una segunda persona de ojos azules sabe que una tercera persona tiene ojos azules, pero nadie sabe que hay una tercera persona de ojos azules con ese conocimiento, hasta que el forastero hace su declaración.

En general: Para k  > 1, es  conocimiento de "( k - 1) orden". Cada persona de ojos azules sabe que una segunda persona de ojos azules sabe que una tercera persona de ojos azules sabe que ... (repita para un total de k  - 1 niveles) una k ésima persona tiene ojos azules, pero nadie lo sabe que hay una " k- ésima" persona de ojos azules con ese conocimiento, hasta que el forastero hace su declaración. Por tanto, la noción de conocimiento común tiene un efecto palpable. Saber que todo el mundo lo sabe marca la diferencia. Cuando el anuncio público del forastero (un hecho ya conocido por todos, a menos que k = 1, entonces la única persona con ojos azules no lo sabría hasta el anuncio) se vuelve de conocimiento común, las personas de ojos azules en esta isla eventualmente deducen su estado y se van. .

Formalización

Lógica modal (caracterización sintáctica)

El conocimiento común puede recibir una definición lógica en sistemas lógicos multimodales en los que los operadores modales se interpretan epistémicamente . En el nivel proposicional, tales sistemas son extensiones de la lógica proposicional . La extensión consiste en la introducción de un grupo G de agentes y de n operadores modales K _i (con i = 1, ...,  n ) con el significado pretendido de que "el agente i conoce". Por lo tanto K _i ${\ Displaystyle \ varphi}$ (donde es una fórmula del cálculo) se lee "agente i sabe ". Podemos definir un operador E _G con el significado pretendido de "todos en el grupo G saben" definiéndolo con el axioma ${\ Displaystyle \ varphi}$${\ Displaystyle \ varphi}$

${\ Displaystyle E_ {G} \ varphi \ Leftrightarrow \ bigwedge _ {i \ in G} K_ {i} \ varphi,}$

Abreviando la expresión con y definiendo , podríamos definir conocimiento común con el axioma ${\ Displaystyle E_ {G} E_ {G} ^ {n-1} \ varphi}$${\ Displaystyle E_ {G} ^ {n} \ varphi}$${\ Displaystyle E_ {G} ^ {0} \ varphi = \ varphi}$

${\ Displaystyle C \ varphi \ Leftrightarrow \ bigwedge _ {i = 0} ^ {\ infty} E ^ {i} \ varphi}$

Sin embargo, existe una complicación. Los lenguajes de la lógica epistémica suelen ser finitarios , mientras que el axioma anterior define el conocimiento común como una conjunción infinita de fórmulas, por lo que no es una fórmula bien formada del lenguaje. Para superar esta dificultad, se puede dar una definición de punto fijo de conocimiento común. Intuitivamente, el conocimiento común se considera el punto fijo de la "ecuación" . De esta manera, es posible encontrar una fórmula que implique a partir de la cual, en el límite, podamos inferir un conocimiento común . ${\ Displaystyle C_ {G} \ varphi = \ varphi \ wedge E_ {G} (C_ {G} \ varphi)}$${\ Displaystyle \ psi}$${\ Displaystyle E_ {G} (\ varphi \ wedge C_ {G} \ varphi)}$${\ Displaystyle \ varphi}$

A esta caracterización sintáctica se le da contenido semántico a través de las llamadas estructuras de Kripke . Una estructura de Kripke está dada por (i) un conjunto de estados (o mundos posibles) S , (ii) n relaciones de accesibilidad , definidas en , que representan intuitivamente los estados que el agente i considera posibles desde cualquier estado dado, y (iii) una función de valoración asignando un valor de verdad , en cada estado, a cada proposición primitiva en el lenguaje. La semántica para el operador de conocimiento se da estipulando que es verdadera en el estado s sif es verdadera en todos los estados t tales que . La semántica para el operador de conocimiento común, entonces, se da tomando, para cada grupo de agentes G , el cierre reflexivo y transitivo de , para todos los agentes i en G , llame a tal relación , y estipulando que es cierto en el estado s iff es verdadero en todos los estados t tales que . ${\ Displaystyle R_ {1}, \ dots, R_ {n}}$${\ Displaystyle S \ times S}$${\ Displaystyle \ pi}$${\ Displaystyle K_ {i} \ varphi}$${\ Displaystyle \ varphi}$${\ Displaystyle (s, t) \ en R_ {i}}$${\ Displaystyle R_ {i}}$${\ Displaystyle R_ {G}}$${\ Displaystyle C_ {G} \ varphi}$${\ Displaystyle \ varphi}$${\ Displaystyle (s, t) \ en R_ {G}}$

Establecer teórico (caracterización semántica)

Alternativamente (aunque de manera equivalente) el conocimiento común se puede formalizar usando la teoría de conjuntos (este fue el camino tomado por el premio Nobel Robert Aumann en su artículo seminal de 1976). Vamos a empezar con un conjunto de estados S . Entonces podemos definir un evento E como un subconjunto del conjunto de estados S . Para cada agente i , defina una partición en S , P _i . Esta partición representa el estado de conocimiento de un agente en un estado. En el estado s , agente i sabe que uno de los estados en P _i ( s obtiene), pero no cuál. (Aquí P _i ( s ) denota el elemento único de P _i que contiene s . Nota que esto excluye modelo casos en que los agentes saben cosas que no son verdad.)

Ahora podemos definir una función de conocimiento K de la siguiente manera:

${\ Displaystyle K_ {i} (e) = \ {s \ in S \ mid P_ {i} (s) \ subconjunto e \}}$

Es decir, K _i ( e ) es el conjunto de estados en los que el agente sabrá que se produce el evento e . Es un subconjunto de e .

De manera similar a la formulación lógica modal anterior, podemos definir un operador para la idea de que "todos conocen e ".

${\ Displaystyle E (e) = \ bigcap _ {i} K_ {i} (e)}$

Al igual que con el operador modal, iteraremos la función E y . Usando esto, podemos definir una función de conocimiento común, ${\ Displaystyle E ^ {1} (e) = E (e)}$${\ Displaystyle E ^ {n + 1} (e) = E (E ^ {n} (e))}$

${\ Displaystyle C (e) = \ bigcap _ {n = 1} ^ {\ infty} E ^ {n} (e).}$

La equivalencia con el enfoque sintáctico esbozado anteriormente se puede ver fácilmente: considere una estructura de Aumann como la que se acaba de definir. Podemos definir una estructura de Kripke correspondiente tomando (i) el mismo espacio S , (ii) las relaciones de accesibilidad que definen las clases de equivalencia correspondientes a las particiones , y (iii) una función de valoración tal que dé un valor fiel a la proposición primitiva p en todos y sólo los estados s tales que , donde es el evento de la estructura de Aumann correspondiente a la proposición primitiva p . No es difícil ver que la función de accesibilidad del conocimiento común definida en la sección anterior corresponde al mejor engrosamiento común de las particiones para todos , que es la caracterización finitaria del conocimiento común también dada por Aumann en el artículo de 1976. ${\ Displaystyle R_ {i}}$${\ Displaystyle P_ {i}}$${\ Displaystyle s \ en E ^ {p}}$${\ Displaystyle E ^ {p}}$${\ Displaystyle R_ {G}}$${\ Displaystyle P_ {i}}$${\ Displaystyle i \ in G}$

Aplicaciones

David Lewis utilizó el conocimiento común en su relato pionero de la convención en la teoría de juegos. En este sentido, el conocimiento común es un concepto todavía central para los lingüistas y filósofos del lenguaje (ver Clark 1996) que mantienen una explicación del lenguaje lewisiana y convencionalista.

Robert Aumann introdujo una formulación teórica de conjunto de conocimiento común (teóricamente equivalente a la dada anteriormente) y demostró el llamado teorema del acuerdo mediante el cual: si dos agentes tienen una probabilidad previa común sobre un evento determinado, y las probabilidades posteriores son de conocimiento común, entonces esas probabilidades posteriores son iguales. Un resultado basado en el teorema del acuerdo y probado por Milgrom muestra que, dadas ciertas condiciones de eficiencia e información del mercado, el comercio especulativo es imposible.

El concepto de conocimiento común es central en la teoría de juegos . Durante varios años se ha pensado que la asunción de un conocimiento común de la racionalidad para los jugadores en el juego era fundamental. Resulta (Aumann y Brandenburger 1995) que, en los juegos de 2 jugadores, el conocimiento común de la racionalidad no es necesario como condición epistémica para las estrategias de equilibrio de Nash .

Los informáticos utilizan lenguajes que incorporan lógicas epistémicas (y conocimiento común) para razonar sobre sistemas distribuidos. Tales sistemas pueden basarse en lógicas más complicadas que la lógica epistémica proposicional simple, ver Wooldridge Reasoning about Artificial Agents , 2000 (en el que usa una lógica de primer orden que incorpora operadores epistémicos y temporales) o van der Hoek et al. "Lógica epistémica del tiempo alterno".

En su libro de 2007, The Stuff of Thought: Language as a Window into Human Nature , Steven Pinker usa la noción de conocimiento común para analizar el tipo de discurso indirecto involucrado en insinuaciones.

Ver también

• Juego global
• Conocimiento mutuo (lógica)
• Stephen Schiffer
• El problema de dos generales por la imposibilidad de establecer un conocimiento común a través de un canal no confiable

Notas

1. ^ Véanse los libros de textoReasoning about knowledgede Fagin, Halpern, Moses y Vardi (1995) yEpistemic Logic for computer sciencede Meyer y van der Hoek (1995).
2. ↑ Herbert Gintis(2000) proporciona un problema estructuralmente idéntico; lo llama "Las mujeres de Sevitan".

Referencias

Otras lecturas

• Aumann, Robert (1976) "De acuerdo en desacuerdo" Annals of Statistics 4 (6): 1236-1239.
• Aumann Robert y Adam Brandenburger (1995) "Condiciones epistémicas para el equilibrio de Nash" Econometrica 63 (5): 1161-1180.
• Clark, Herbert (1996) Uso del lenguaje , Cambridge University Press ISBN  0-521-56745-9
• Fagin, Ronald; Halpern, Joseph; Moisés, Yoram; Vardi, Moshe (2003). Razonamiento sobre el conocimiento . Cambridge: MIT Press . ISBN 978-0-262-56200-3..
• Lewis, David (1969) Convención: Un estudio filosófico Oxford: Blackburn. ISBN  0-631-23257-5
• JJ Ch. Meyer y W van der Hoek Epistémica Logic for Computer Science and Artificial Intelligence , volumen 41, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, 1995. ISBN  0-521-46014-X
• Rescher, Nicolas (2005). Lógica epistémica: un estudio de la lógica del conocimiento . Prensa de la Universidad de Pittsburgh . ISBN 978-0-8229-4246-7.. Vea el Capítulo 3.
• Shoham, Yoav; Leyton-Brown, Kevin (2009). Sistemas multiagente: fundamentos algorítmicos, teóricos de juegos y lógicos . Nueva York: Cambridge University Press . ISBN 978-0-521-89943-7.. Consulte la Sección 13.4; descargable gratis en línea .
• Gintis, Herbert (2000) Teoría de juegos en evolución Princeton University Press. ISBN  0-691-14051-0
• Gintis, Herbert (2009) Los límites de la razón Princeton University Press. ISBN  0-691-14052-9
• Halpern, JY ; Moisés, Y. (1990). "Conocimiento y conocimiento común en un entorno distribuido". Revista de la ACM . 37 (3): 549–587. arXiv : cs / 0006009 . doi : 10.1145 / 79147.79161 . S2CID  52151232 .

enlaces externos

• Vanderschraaf, Peter; Sillari, Giacomo. "Conocimiento común" . En Zalta, Edward N. (ed.). Enciclopedia de Filosofía de Stanford .
• Publicación del blog del profesor Terence Tao (febrero de 2008)
• Carr, Kareem. "A largo plazo, todos estaremos muertos" , "A largo plazo, todos estaremos muertos II" ante la doble mirada. Descripción detallada del problema de los isleños de ojos azules, con solución.
• physics.harvard.edu "Problema de los dragones de ojos verdes" , "Solución de los dragones de ojos verdes" (septiembre de 2002)