Ingeniero Civil Matemático / El objetivo principal de esta memoria es estudiar generalizaciones del problema de emparejamientos en línea. En un artículo seminal Karp, Vazirani y Vazirani estudiaron el siguiente problema de optimización: Dado un grafo bipartito G=(L,R,E) del que el lado L es conocido y el lado R llega en línea, se busca maximizar el tamaño de un emparejamiento, bajo la condición de que solo se puede emparejar un vértice en el momento en el que llega. Karp, Vazirani y Vazirani encuentran un algoritmo que es una (1-1/e)-aproximación para el problema. En esta memoria se generaliza el problema al caso en el que un lado no está fijo, o sea que vértices de ambos lados pueden llegar en línea. Se estudian tres modelos: el modelo adversarial, el modelo de orden aleatorio y el modelo fuera de línea. Para el modelo adversarial se definen algoritmos locales y se demuestra que ninguno de ellos puede ser mejor que una 1/2-aproximación. Para el modelo de orden aleatorio se encuentra un algoritmo cuya competividad está en el intervalo [0.696, 0.727]. Finalmente, para el modelo fuera de línea se encuentra un algoritmo óptimo cuya competividad es desconocida, pero se demuestra que está en el intervalo [0.526, 0.591].

Ingeniero Civil Industrial / Este trabajo de título tiene como objetivo fundamental analizar el aporte que se pueda generar a una metodología al introducir un análisis con medidas de centralidad de Teoría de Grafos, para la detección de Objetos Claves dentro de un sitio web. Para lograr esto existen una serie de objetivos específicos que permitirán concluir finalmente con respecto a la hipótesis de investigación planteada, destacando que se pretende incorporar herramientas que hasta ahora no se habían utilizado para este campo. Este trabajo es parte del procedimiento para optar al título de Ingeniero Civil Industrial, siendo parte de un proyecto FONDEF llamado Plataforma informática basada en web-intelligence y herramientas de análisis de exploración visual para la mejora de la estructura y contenido de sitios web (AKORI: Advanced Kernel for Ocular Research and Web Intelligence). AKORI es un proyecto co-creado entre el departamento de Ingeniería Industrial y la Facultad de Medicina de la Universidad de Chile. La justificación de este trabajo está relacionado con el crecimiento que ha sucedido en la web durante los últimos años. Este aumento exponencial de la cantidad de usuarios y páginas de Internet, ha llevado a que muchas empresas que basan su modelo de negocios en sus sitios web, tengan interés por destacar en la nube y tener los sitios optimizados para sus respectivos usuarios, produciendo una nueva rama de investigación sociológica, para ello se han desarrollado diversas metodologías que apuntan a mejorar el contenido y la estructura de los sitios web. Metodologías que tienen por lo general altos grados de subjetividad, siendo poco eficientes para definir exactamente las zonas u objetos que llaman más la atención para los distintos usuarios. La hipótesis de investigación propuesta plantea que es posible mejorar la metodología creada por Juan D. Velásquez al evaluar con medidas de centralidad de teoría de grafos, outputs obtenidos por experimentos ya realizados a 23 sujetos que navegaron libremente en la página web del MBA del departamento de Ingeniería Industrial, experimento que utilizó herramientas de eye-tracking, dilatación pupilar y EEG. Al mejorar la detección de Website Keyobjects aumentando la eficiencia de la metodología con el modelo propuesto, se estaría creando un pilar fundamental para el proyecto AKORI. Los WKO clasificados con esta metodología se compararon con otros trabajos previos y fueron evaluados finalmente por el webmaster determinando así la eficiencia de este nuevo trabajo y estableciendo las futuras líneas de acción a seguir. Si bien se demostró la hipótesis de investigación planteada, se cree que se podría desarrollar un mejor trabajo mejorando ciertas propuestas que se declaran en la parte final de este informe.

Ingeniero Civil Matemático / La computación distribuida, rama de las ciencias de la computación, se focaliza en estu- diar sistemas distribuidos, tales como internet, redes sociales o protocolos de mensajería. La información se encuentra distribuida entre las distintas entidades que conforman el sistema y el objetivo último es resolver algún problema global. Para ello las distintas entidades se comunican mediante los canales de la red hasta que encuentran la solución. Esta memoria comienza estudiando el problema de la degenerancia de un grafo en los modelos de computación distribuida UCAST y BCAST, donde la degenerancia de un grafo G se define como el máximo grado mínimo de un subgrafo F de G. Los modelos distribuidos UCAST y BCAST corresponden a redes completas de n individuos, los cuales se comunican de manera síncrona por los canales de la red en rondas. En el primer caso, cada individuo por ronda puede enviar diferentes mensajes por cada uno de sus canales. En el segundo caso, cada individuo por ronda envía a través de sus canales el mismo mensaje. En general, se suele decir que BCAST es una restricción de UCAST. Primero, se construye un protocolo aleatorio en el modelo UCAST que calcula una (1 + ε)- aproximación de la degenerancia en O(log n) rondas con mensajes de largo O(log n). En el modelo BCAST se demuestra que el problema de calcular la degenerancia es difícil en 1 ronda. Más específicamente, se demuestra que todo protocolo aleatorio de 1 ronda que calcule exactamente la degenerancia debe enviar un mensaje de largo Ω(n). En el mismo modelo, se construye un protocolo aleatorio de 2 rondas con mensajes de largo O(log 2 n) que calcula una (1 + ε)-aproximación de la degenerancia para grafos α-densos. Finalmente, se construye un protocolo determinista que calcula una (2 + ε)-aproximación de la degenerancia en O(log n) rondas con mensajes de largo O(log n). Como segunda parte de este trabajo, y motivado por el protocolo en BCAST que calcula una (2 + ε)-aproximación de la degenerancia, se estudia la siguiente dinámica sobre grafos: Durante cada iteración, eliminar todos los vértices que tengan grado a lo más el grado prome- dio del grafo +1. Se conjetura que para todo grafo G de n vértices la dinámica toma O(log n) iteraciones en vaciar el grafo. Se aborda el problema estudiando clases de grafos tales como: bosques, grafos planares, grafos con degenerancia acotada y grafos unión disjunta de cliques. Finalmente, se estudian diversos problemas en el modelo BCAST. Se comienza estudiando el problema de calcular el conjunto independiente maximal con un vértice fijo. Se prueba que el problema es difícil en 1 ronda y luego se contruye un protocolo que en O(log n) rondas, usando mensaje de largo O(log n), calcula el conjunto independiente. Se estudia también el problema de calcular el número cromático de un grafo. Se prueba que el problema resulta difícil en 1 ronda. Concluyendo el capítulo, se estudian los problemas de encontrar conjuntos dominantes de tamaño k y conjuntos -dominantes de tamaño k, en ambos casos se demuestra que los problemas son difíciles en 1 ronda. / Este trabajo ha sido parcialmente financiado por Proyecto Fondecyt 1130061

El presente trabajo aborda la actividad registral del Estado y su vinculación con el sistema penal. Para ello, la investigación se centra en la distinción de tres sistemas que, considerados en conjunto, conforman el sistema de antecedentes penales en Chile. El primero de ellos lo constituye el sistema registral, el cual anota en el prontuario respectivo todas las sentencias condenatorias definitivas y ejecutoriadas sobre toda clase de delitos que recaigan sobre un individuo determinado. A su vez, estas anotaciones contenidas en el Registro General de Condenas, pueden ser modificadas por una serie de normas que contemplan distintas hipótesis para que los usuarios tengan la opción de eliminar u omitir los antecedentes penales a través de los mecanismos establecidos por la normativa vigente en Chile, y que conforman el sistema de eliminación y omisión. Finalmente, la tercera fase corresponde al sistema de distribución, compuesto por las vías de comunicación establecidas por ley para quienes quieran acceder a la información contenida en el Registro General de Condenas. Sin embargo, la eficacia y necesidad de este sistema de antecedentes penales es cuestionada cuando, con ocasión del registro y distribución de antecedentes, el titular de dicha información es objeto de actos discriminatorios a nivel laboral, social y económico como resultado del uso que ciertos individuos de la sociedad hacen de los antecedentes penales. Así, los antecedentes penales se convierten en un currículum vitae negativo en quienes, incluso una vez cumplida sus condenas penales, buscan reintegrarse a la sociedad. Desde un punto de vista teórico, se analiza la relación que existe entre la pena como la potestad del Estado de irrogar un mal ante el quebrantamiento culpable de una norma penal, y los antecedentes penales como la extensión injustificada de esa irrogación de un mal a etapas posteriores a la ejecución de la pena

Magíster en Economía Aplicada / En un proceso de licitación existe un principal que está interesado en obtener un producto o servicio, para el cual existen múltiples oferentes que por supuesto poseen información privada respecto a sus capacidades. Con esto en mente, se dese diseñar de la mejor forma posible las reglas del juego, de manera tal de elegir a aquel agente más eficiente y asegurarse un precio que maximice sus utilidades. Cuando el producto está definido solo por el precio el mecanismo a implementar está bien definido, pero no sucede lo mismo cuando se desea modelar un producto compuesto de características más complejas. Asker & Cantillon desarrollan estudios en esta línea, analizando las características que debe poseer el mecanismo de licitación óptimo cuando el producto a licitar está definido por un precio y por una serie de dimensiones de calidad, que por supuesto hacen el problema más complejo y difícil de analizar. El objetivo del presente trabajo de tesis pretende seguir trabajando en dicha línea, con el fin de analizar las particularidades que posee el mecanismo implementado para un caso particular de mecanismo de licitación. Siguiendo el modelo y la teoría de resolución propuesta por Asker & Cantillon, se propone un tipo de mecanismo basado en una función lineal del tipo first score auction, que permite ordenar las diferentes ofertas que proveen los jugadores. Mediante implementación numérica en MatLab se realizan una serie de simulaciones, que buscan analizar las características del mecanismo óptimo a variaciones en las condiciones del proceso, identificando regularidades que den una pauta respecto a la forma genérica en que el mecanismo óptimo se construye. De la misma manera se busca dilucidar la robustez del mecanismo propuesto, a fin de verificar su validez frente a errores en la estimación de ciertos parámetros del modelo. Los resultados permiten relacionar de buena manera el peso dado a las dimensiones de calidad en la función de utilidad del principal, con aquellos dados en la función score del mecanismo propuesto. Se observa que en general la estrategia consiste en distorsionar hacia abajo la verdadera valoración que posee el principal en las calidades, entregándoles a los agentes una información distorsionada vía la función score que define al mecanismo. El efecto además disminuye al aumentar el número de jugadores, así como el peso relativo dado a las dimensiones respectivas. Por otro lado el mecanismo para funciones de distribuciones cargadas a los mejores y peores tipos se muestra bastante a insensible a cambio en las características de la distribución, lo que se traduce por cierto en una gran robustez del mecanismo estudiado. Si bien los errores numéricos son un factor a tener cuenta en la interpretación de los resultados, se piensa que las regularidades identificadas son representativas del problema, y permiten una comprensión e interpretación amplia de este y otros problemas relacionados. Sin embargo su aplicabilidad a casos concretos o extensión a otros problemas de mayor complejidad o dimensiones de calidad dependerán de las características de éstos. En base a ello se recomienda extender las pruebas a casos diferentes, modificando las funciones de distribución y primitivas del problema, y validando los resultados en una escala mas amplia.

Believing in the own capacity or self- effectiveness in certain situations could be considered as a vital concept within the academic field because it can better predict performance than otherwise personal skills and knowledge can do.This concept is inserted within Bandura’s Cognitive Social Theory, which considers the human being as a self-organized, self-reflexive and task-committed individual. A key point in this theory is that people have personal believes regarding their self- effectiveness that allow them to have a certain control on their feelings, actions and thoughts. This means that individuals’ behavior can be influenced by what they think, create and feel. Therefore, self- effectiveness becomes a good predictive of the human behavior. Self- effectiveness believes also have an influence in the way each person acts through cognitive, motivational, affective and selective processes. In the academic field specifically, self- effectiveness believes have an impact on student’s motivation, persistence and academic success. It is worth to mention, also, that teacher’s self- effectiveness believes about their work have an important influence in the student’s performance. Finally, we can say that between the self- effectiveness sources, we found: the successful use of experiences, the comparison with similar models, the social persuasion and the corporal states. / La autoeficacia o creencia en la propia capacidad en determinadas situaciones puede ser considerada un concepto vital en el ámbito educativo, puesto que es un elemento que predice de mejor manera el desempeño de la habilidad y del conocimiento personales. Este concepto se inserta dentro de la Teoría Social Cognitiva de Bandura, en la cual se considera al ser humano como un individuo autorganizado, autorreflexivo, autorregulado y comprometido con su desarrollo. Un punto clave en esta teoría es que las personas tienen creencias personales (creencias de autoeficacia), que les permiten ejercitar cierto control sobre sus sentimientos, acciones y pensamientos. Esto quiere decir que el comportamiento de los individuos se ve influido por lo que piensan, creen y sienten. Así, pues, la autoeficacia se convierte en un buen elemento de predicción del comportamiento humano. Las creencias de autoeficacia influyen en la conducta en general, mediante procesos cognitivos, motivacionales, afectivos y selectivos. Específicamente, en el ámbito académico, las creencias de autoeficacia actúan sobre la motivación, la persistencia y éxito académico. Cabe mencionar, también, que las creencias de autoeficacia que los profesores tienen acerca de su labor tienen una influencia importante en el desempeño de los alumnos. Finalmente, podemos mencionar que, entre las fuentes de autoeficacia, se encuentran el manejo exitoso de experiencias, la comparación con modelos similares, la persuasión social y los estados corporales.

Empleado el enfoque de sistemas y realizando un trabajo multidisciplinario de investigación y desarrollo, se ha elaborado un modelo informático de un sistema empresarial de negocios, que permite a través de la simulación realizar los procesos de adquisiciones, producción, financiamiento y ventas dentro de un ambiente de competencia, como se realizaría en la gestión de una empresa de industrial. / -- Working with the system vision and making a multidisciplinary approach of and development , we have elaborated a computing model of a business management system that allows through the simulating practice.

Doctor en Ciencias de la Ingeniería, Mención Modelación Matemática / En esta tesis doctoral se abordan dos problemas relacionados con el comportamiento en tiempo largo de los procesos de Markov deterministas por pedazos (PDMP). En primer lugar se estudia el comportamiento asintótico de un PDMP general en relación con el comportamiento y propiedades de una cadena de Markov a tiempo discreto embuída. Este problema se desarrolla en el Capítulo 1. En segundo lugar, se considera un PDMP específico llamado Proceso del tamaño de ventana del TCP (sigla en inglés del protocolo de control de transmisión usado en internet). El objetivo en este caso es encontrar tasas de convergencia explícitas al equilibrio. Este problema se estudia en el Capítulo 2. Con respecto al primer problema, en el Cap´ıtulo 1 se relacionan las propiedades de recurrencia positiva y las medidas de probabilidad invariantes de un proceso PDMP general con las de una cadena espacio-tiempo discreta, formada por las posiciones post-salto del proceso y las longitudes de tiempo entre saltos. Esta cadena discreta se obtiene de manera simple a partir de las características locales que definen el proceso a tiempo continuo y contiene más información que la cadena discreta post-salto que ha sido habitualmente considerada. Utilizando esta cadena espacio-tiempo se puede definir un nuevo proceso a tiempo continuo asociado, formado por tres coordenadas: el proceso continuo propiamente dicho, la longitud de tiempo trancurrido desde el último tiempo de salto y la longitud de tiempo que falta para el siguiente tiempo de salto, en analogía con los procesos edad y vida residual de teoría de renovación. En este capítulo se describe completamente el equilibrio de este proceso asociado y se establece un resultado análogo de la waiting time paradox de teoría de renovación en el contexto de los PDMP. Para el segundo problema, en el Capítulo 2 se obtienen tasas de convergencia exponencial al equilibrio en distancia Wasserstein y en la norma en variación total. Estos resultados se basan en algunos argumentos de acoplamiento nuevos y dan una respuesta a una pregunta importante sobre el protocolo de transmisión de internet TCP, que es el entender cómo la congestión del tamaño de ventana del TCP alcanza equilibrio en tiempo largo.

Doctor en Sistemas de Ingeniería / Medir la probabilidad de no pago de un gran número de solicitantes de crédito, el llamado riesgo de crédito a consumidores, es un problema clásico de la gestión financiera. Este problema requiere de una gran cantidad de herramientas estadísticas que lo hacen idóneo para su estudio por el área de Business Analytics. Su análisis se justifica en el fuerte impacto que los créditos a consumidores tienen en el mercado, pues por ejemplo en Chile más del 50% de los créditos se encuentran en carteras masivas, y en el resto del mundo se estima que superan a los créditos comerciales en más de un 50%. Esta tesis estudia este problema en base a la formalización de lo que se conoce sobre las determinantes del no pago (default) y la transformación de ese conocimiento en herramientas estadísticas para la medición del riesgo. Para lo anterior, durante el doctorado desarrollé una sucesión de publicaciones con el fin de unir el modelamiento económico con la práctica estadística predictiva, formalizando el conocido hecho que existen no pagadores por razones de falta de capacidad de pago, y por problemas en voluntad de pago. El trabajo comenzó generando un modelo económico que captura las utilidades de los solicitantes y la entidad prestamista, utilizando esta nueva definición de no pagadores, resultando en una serie de restricciones que definen un espacio de créditos factibles. Luego, los no pagadores son asignados a estas dos clases utilizando un nuevo método de clustering semi-supervisado que los agrupa tanto por sus características estadísticas como por su comportamiento económico, reflejado a través de las restricciones generadas previamente. El fin último de esta separación es mejorar la clasificación de los créditos y la comprensión del default, por lo que el siguiente paso correspondió al estudio de métodos de clasificación con múltiples clases. Para ello se exploró inicialmente la regresión logística multinomial, y luego se profundizó en el análisis de supervivencia, estudiando teóricamente los métodos de riesgos en competencia y los modelos mixtos, y desarrollando herramientas computacionales liberadas públicamente para apoyar futuras aplicaciones. Los métodos propuestos mejoran entre 1%-10% la discriminación por sobre los métodos clásicos en bases de datos reales, y enriquecen fuertemente la comprensión del default a través de las nuevas variables significativas y los patrones encontrados. Más aún, los modelos y herramientas desarrollados pueden ser perfectamente extrapolados a otras disciplinas, pues este trabajo ha mostrado cómo se puede enriquecer la clasificación donde típicamente se cuenta con dos clases, por la vía de añadir conocimiento adicional acerca de comportamientos económicos observados.

Magíster en Economía Aplicada / Ingeniero Civil Industrial / En este trabajo se define un concepto de equilibrio en juegos, bajo cierto tipo de racionalidad limitada (se hablará de k-racionalidad), definida por las creencias que los jugadores tienen respecto de la racionalidad de los demás. La evidencia experimental estudiada por los modelos de nivel k (Stahl & Wilson, 1994; Nagel, 1995) y de jerarquías cognitivas (Camerer, Ho, Chong, 2004) indica que, en general, los jugadores no asumen conocimiento común de la racionalidad, sino que eligen sus estrategias óptimas de acuerdo a la predicción que hacen del comportamiento de los demás. Este trabajo parte de estos supuestos, a través de un modelo de k-racionalidad que reemplaza el conocimiento común de la racionalidad por una regla de decisión que indica cómo eligen sus estrategias los jugadores a partir de las predicciones que hacen. Se propone un equilibrio k-autoconfirmante para juegos estáticos y dinámicos (tomando el concepto de Fudenberg & Levine (1993)) en este modelo, correspondiente a un perfil de estrategias y niveles de racionalidad tales, que una vez realizado el juego, los jugadores no pueden rechazar sus creencias dado que sus predicciones son correctas y que no hay incentivos a desviarse de este perfil. A lo largo de este trabajo se considerará que las creencias son un tipo que viene dado para los jugadores, sin capacidad de modificarlo; esto evita preocuparse por la formación de creencias y centra la discusión en las situaciones de equilibrio. Un primer resultado para juegos estáticos es que un perfil de estrategias en equilibrio k-autoconfirmante también corresponde a un equilibrio de Nash para el mismo juego sin considerar creencias, esto permitiría usar el modelo para seleccionar equilibrios. Además, se muestra que uno de los ejemplos paradigmáticos en la literatura experimental - el juego del Beauty Contest - no tiene equilibrio k-autoconfirmante, lo que podría explicar el sesgo por estudiar situaciones fuera de equilibrio. La verdadera riqueza del modelo, sin embargo, está en juegos dinámicos; al aplicar esta definición de equilibrio a juegos de negociación secuencial, el modelo entrega un contexto explicativo a situaciones en las que existe delay. Más importante, si la negociación secuencial es suficientemente larga, se prueba la existencia de múltiples equilibrios k-autoconfirmantes que tienen como resultado una negociación que se acaba en el primer período (es decir, sin delay) y que no corresponden al equilibrio perfecto en subjuegos. Esto entregaría nuevas perspectivas a la discusión respecto de la pertinencia de incorporar a la teoría supuestos traídos de la economía del comportamiento.