Conocimiento común (lógica)

Declaración de que los jugadores saben y también saben que otros jugadores saben (ad infinitum)

El conocimiento común es un tipo especial de conocimiento para un grupo de agentes . Hay 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 . ^[1] Se puede denotar como . ${\displaystyle C_{G}p}$

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. ^[2] Robert Aumann (1976) le dio por primera vez una formulación matemática en un marco teórico de conjuntos . Los científicos informáticos desarrollaron un interés en 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. ^[1] Existen numerosos acertijos basados ​​en el concepto que han sido investigados exhaustivamente por matemáticos como John Conway . ^[3]

El filósofo Stephen Schiffer , en su libro Significado de 1972 , desarrolló de forma independiente una noción que llamó " conocimiento mutuo " ( ) que funciona de manera bastante similar al "conocimiento común" de Lewis y Friedel de 1969. ^[4] Si un anuncio confiable se hace en público , entonces se vuelve de conocimiento público; Sin embargo, si se transmite a cada agente en privado, se convierte en conocimiento mutuo pero no en conocimiento común. Incluso si el hecho de que "todos los agentes del grupo conocen p " ( ) se transmite a cada agente en privado, todavía no es de conocimiento común: . Pero, si algún agente anuncia públicamente su conocimiento de p , entonces se vuelve de conocimiento común que conoce p (a saber ). Si cada agente anuncia públicamente su conocimiento de p , p se convierte en conocimiento común . ${\displaystyle E_{G}p}$ ${\displaystyle E_{G}p}$ ${\displaystyle E_{G}E_{G}p\not \Rightarrow C_{G}p}$ ${\displaystyle a}$ ${\displaystyle C_{G}K_{a}p}$ ${\displaystyle C_{G}E_{G}p\Rightarrow C_{G}p}$

Ejemplo

Rompecabezas

La idea de conocimiento común a menudo se introduce mediante alguna variante de acertijos de inducción (por ejemplo, el acertijo de niños fangosos ): ^[2]

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 sabe su propio color de ojos. Por regla general, si una persona en la isla alguna vez descubre que tiene ojos azules, debe abandonar la isla al amanecer; Quien no hace tal descubrimiento siempre duerme hasta después del amanecer. En la isla, cada persona conoce el color de ojos de los demás, no hay superficies reflectantes y no hay comunicación sobre el color de ojos.

En algún momento, un forastero llega a la isla, reúne a toda la gente de la isla y hace el siguiente anuncio público : "Al menos uno de ustedes tiene los ojos azules". Además, todos saben que el forastero es veraz, y todos saben que todos lo saben, y así sucesivamente: es de conocimiento común que es veraz, y por lo tanto se vuelve de conocimiento común que hay al menos un isleño que tiene azul. ojos ( ). El problema: encontrar el resultado final, asumiendo que todas las personas en la isla son completamente lógicas (el conocimiento de cada participante obedece a los esquemas de axiomas de la lógica epistémica ) y que esto también es conocimiento común. ${\displaystyle C_{G}[\exists x\!\in \!G(Bl_{x})]}$

Solución

La respuesta es que, al késimo amanecer después del anuncio, todos los 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 ella tiene ojos azules (al ver solo ojos verdes en los demás) y se marchará al primer amanecer. Si k  = 2, nadie se irá al amanecer, y la inacción (y la implícita falta de conocimiento de cada agente) es observada por todos, lo que luego también se convierte en conocimiento común ( ). Las dos personas de ojos azules, al ver solo a una persona de ojos azules, y que nadie se fue en el primer amanecer (y por lo tanto que k  > 1; y también que la otra persona de ojos azules no piensa que todos excepto ellos no están de ojos azules , por lo que otra persona de ojos azules ), partirá en el segundo amanecer. Inductivamente, se puede razonar que nadie se irá en los primeros k  − 1 amaneceres si y sólo si hay al menos k personas de ojos azules. Aquellos con ojos azules, al ver k  − 1 personas de ojos azules entre las demás y saber que debe haber al menos k , razonarán que deben tener ojos azules y se marcharán. ${\displaystyle C_{G}[\forall x\!\in \!G(\neg K_{x}Bl_{x})]}$ ${\displaystyle \neg K_{a}[\forall x\!\in \!(G-a)(\neg Bl_{x})]}$ ${\displaystyle \exists x\!\in \!(G-a)(Bl_{x})}$

Para k  > 1, el forastero sólo les dice 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 conocimiento común , sino de conocimiento mutuo .

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. ${\displaystyle E_{G}[\exists x\!\in \!G(Bl_{x})]}$

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 extraño hace su declaración. ${\displaystyle E_{G}E_{G}[\exists x\!\in \!G(Bl_{x})]=E_{G}^{2}[\exists x\!\in \!G(Bl_{x})]}$

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 enésima persona tiene ojos azules, pero nadie lo sabe que hay una " k th" 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 hace la diferencia. Cuando el anuncio público del forastero (un hecho ya conocido por todos, a menos que k=1, entonces la persona con ojos azules no lo sabría hasta el anuncio) se vuelve de conocimiento público, las personas de ojos azules en esta isla eventualmente deducen su estatus y se van. . ${\displaystyle E_{G}^{k-1}[\exists x\!\in \!G(Bl_{x})]}$

En particular:

1. ${\displaystyle E_{G}^{i}[|G(Bl_{x})|>=j]}$es libre (es decir, conocido antes de la declaración del extraño) si . ${\displaystyle i+j<=k}$
2. ${\displaystyle E_{G}^{i}[|G(Bl_{x})|>=j]}$, con un día que pasa donde nadie se va, implica el día siguiente . ${\displaystyle E_{G}^{i-1}[|G(Bl_{x})|>=j+1]}$
3. ${\displaystyle E_{G}^{i}[|G(Bl_{x})|>=j]}$for se alcanza así si se alcanza . ${\displaystyle j>=k}$ ${\displaystyle i+j>k}$
4. El forastero da por . ${\displaystyle E_{G}^{i}[|G(Bl_{x})|>=j]}$ ${\displaystyle i=\infty ,j=1}$

Formalización

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

Al conocimiento común se le puede dar 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 Ki (con i = 1,...,  n ) con el significado pretendido de que "el agente _i sabe ". Así, K _i ${\displaystyle \varphi }$ (donde es una fórmula del cálculo lógico) se lee "el agente i sabe ". Podemos definir un operador E _G con el significado deseado de "todos en el grupo G lo saben" definiéndolo con el axioma ${\displaystyle \varphi }$ ${\displaystyle \varphi }$

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

Al abreviar la expresión con y definir , el conocimiento común podría definirse 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 finitos , mientras que el axioma anterior define el conocimiento común como una conjunción infinita de fórmulas y, por lo tanto, no es una fórmula bien formada del lenguaje. Para superar esta dificultad, se puede dar una definición fija de conocimiento común. Intuitivamente, se piensa que el conocimiento común es el punto fijo de la "ecuación" . Aquí está el Aleph-nada . De esta manera, es posible encontrar una fórmula que implique de la cual, en el límite, podamos inferir el conocimiento común de . ${\displaystyle C_{G}\varphi =[\varphi \wedge E_{G}(C_{G}\varphi )]=E_{G}^{\aleph _{0}}\varphi }$ ${\displaystyle \aleph _{0}}$ ${\displaystyle \psi }$ ${\displaystyle E_{G}(\varphi \wedge C_{G}\varphi )}$ ${\displaystyle \varphi }$

De esta definición se desprende que si es de conocimiento común, entonces también lo es de conocimiento común ( ). ${\displaystyle E_{G}\varphi }$ ${\displaystyle \varphi }$ ${\displaystyle C_{G}E_{G}\varphi \Rightarrow C_{G}\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 un conjunto de estados (o mundos posibles) S , n relaciones de accesibilidad , definidos en , que representan intuitivamente qué estados el agente i considera posibles a partir de cualquier estado dado, y una función de valoración que asigna un valor de verdad , en cada estado, a cada proposición primitiva del lenguaje. La semántica de Kripke para el operador de conocimiento viene dada estipulando que es verdadero en el estado s sif es verdadero en todos los estados t tales que . La semántica del operador de conocimiento común, entonces, viene dada tomando, para cada grupo de agentes G , la clausura reflexiva (axioma modal T ) y transitiva (axioma modal 4 ) de , para todos los agentes i en G , llamar a tal relación , y estipulando que es cierto en el estado s sif es cierto 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)\in R_{i}}$ ${\displaystyle R_{i}}$ ${\displaystyle R_{G}}$ ${\displaystyle C_{G}\varphi }$ ${\displaystyle \varphi }$ ${\displaystyle (s,t)\in R_{G}}$

Teórica de conjuntos (caracterización semántica)

De manera alternativa (aunque equivalente), el conocimiento común puede formalizarse utilizando la teoría de conjuntos (este fue el camino seguido por el premio Nobel Robert Aumann en su artículo fundamental de 1976). Comenzando con un conjunto de estados S . Un evento E puede entonces definirse como un subconjunto del conjunto de estados S. Para cada agente _i , defina una partición en S , Pi . Esta partición representa el estado de conocimiento de un agente en un estado. Intuitivamente, si dos estados s ₁ y s ₂ son elementos de la misma parte de partición de un agente, significa que s ₁ y s ₂ son indistinguibles para ese agente. En general, en el estado s , el agente i sabe que uno de los estados en P _i ( s ) se obtiene, pero no cuál. (Aquí P _i ( s ) denota el elemento único de Pi que contiene s . _Este modelo excluye los casos en los que los agentes saben cosas que no son ciertas.)

Una función de conocimiento K ahora se puede definir de la siguiente manera:

${\displaystyle K_{i}(e)=\{s\in S\mid P_{i}(s)\subset e\}}$

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

De manera similar a la formulación de lógica modal anterior, un operador para la idea de que "todos saben" puede definirse como 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 puede verse fácilmente: consideremos una estructura de Aumann como la que acabamos de definir. Podemos definir una estructura de Kripke correspondiente tomando el mismo espacio S , relaciones de accesibilidad que definen las clases de equivalencia correspondientes a las particiones y una función de valoración tal que produzca 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 al 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 finita del conocimiento común también dada por Aumann en el artículo de 1976. ${\displaystyle R_{i}}$ ${\displaystyle P_{i}}$ ${\displaystyle s\in 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 explicación pionera 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 lewisiana y convencionalista del lenguaje.

Robert Aumann introdujo una formulación teórica establecida de conocimiento común (teóricamente equivalente a la dada anteriormente) y demostró el llamado teorema de acuerdo mediante el cual: si dos agentes tienen una probabilidad previa común sobre un determinado evento, y las probabilidades posteriores son de conocimiento común, entonces dichas probabilidades posteriores son iguales. Un resultado basado en el teorema del acuerdo y demostrado 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 . Desde hace varios años se pensaba que la asunción de un conocimiento común de la racionalidad por parte de los jugadores del juego era fundamental. Resulta (Aumann y Brandenburger 1995) que, en juegos de dos 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ógica epistémica (y conocimiento común) para razonar sobre sistemas distribuidos. Dichos sistemas pueden basarse en lógicas más complicadas que la simple lógica epistémica proposicional, ver Wooldridge Reasoning about Artificial Agents , 2000 (en el que utiliza 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 utiliza la noción de conocimiento común para analizar el tipo de discurso indirecto involucrado en las insinuaciones.

En la cultura popular

La película de comedia Hot Lead and Cold Foot tiene un ejemplo de una cadena de lógica que el conocimiento común colapsa. El Niño de Denver les dice a sus aliados que Rattlesnake está en la ciudad, pero que él [el Niño] tiene “la ventaja”: “Él está aquí y yo sé que está aquí, y él sabe que yo sé que está aquí, pero él no sabe que yo lo sé”. él sabe que yo sé que está aquí”. Entonces ambos protagonistas conocen el hecho principal (Rattlesnake está aquí), pero no es “conocimiento común”. Tenga en cuenta que esto es cierto incluso si Kid está equivocado: tal vez Rattlesnake sepa que Kid sabe que él sabe que sabe, la cadena aún se rompe porque Kid no lo sabe. Momentos después, Rattlesnake se enfrenta a Kid. Vemos a Kid darse cuenta de que su “ventaja” cuidadosamente construida se ha convertido en conocimiento común.

Ver también

• Portal de filosofía

• juego global
• Conocimiento mutuo (lógica)
• Ignorancia pluralista
• caza del ciervo
• Esteban Schiffer
• El problema de los dos generales por la imposibilidad de establecer conocimiento común a través de un canal poco confiable

Notas

1. ^ Véanse los libros de texto Razonamiento sobre el conocimiento de Fagin, Halpern, Moses y Vardi (1995) y Lógica epistémica para la informática de Meyer y van der Hoek (1995).
2. ^ Herbert Gintis (2000) proporciona un problema estructuralmente idénticoél lo llama "Las mujeres de Sevitan".

Referencias

1. Osborne, Martin J. y Ariel Rubinstein . Un curso de teoría de juegos . Cambridge, MA: MIT, 1994. Imprimir.
2. Morris Friedell, "Sobre la estructura de la conciencia compartida", Behavioral Science 14 (1969): 28–39.
3. Ian Stewart (2004). "Sé que tú sabes que...". Histeria matemática . OUP.
4. Stephen Schiffer, Significado , segunda edición, Oxford University Press, 1988. La primera edición fue publicada por OUP en 1972. Para una discusión de las nociones de Lewis y Schiffer, consulte Russell Dale, The Theory of Meaning (1996).

Otras lecturas

• Aumann, Robert (1976) "Aceptar estar 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, José; Moisés, Yoram; Vardi, Moshé (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 Cap. Meyer y W van der Hoek Lógica epistémica para la informática y la inteligencia artificial , volumen 41, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, 1995. ISBN 0-521-46014-X 
• Rescher, Nicolás (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.. Consulte el Capítulo 3.
• Shoham, Yoav; Leyton-Brown, Kevin (2009). Sistemas multiagente: fundamentos lógicos, algorítmicos y de teoría de juegos. Nueva York: Cambridge University Press . ISBN 978-0-521-89943-7.. Ver 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 saber 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 .
• Entrada del blog del profesor Terence Tao (febrero de 2008)
• Carr, Karem. "A la larga, todos estamos muertos", "A la larga, todos estamos muertos II" en The Twofold Gaze. Descripción detallada del problema de los isleños de ojos azules, con solución.
• física.harvard.edu "Problema de los dragones de ojos verdes" Archivado el 1 de diciembre de 2014 en Wayback Machine , "Solución de los dragones de ojos verdes" Archivado el 1 de diciembre de 2014 en Wayback Machine (septiembre de 2002)