{"id":116233,"date":"2018-03-11T10:45:12","date_gmt":"2018-03-11T10:45:12","guid":{"rendered":"https:\/\/www.deberes.net\/tesis\/sin-categoria\/structural-and-computational-aspects-of-simple-and-influence-games\/"},"modified":"2018-03-11T10:45:12","modified_gmt":"2018-03-11T10:45:12","slug":"structural-and-computational-aspects-of-simple-and-influence-games","status":"publish","type":"post","link":"https:\/\/www.deberes.net\/tesis\/ciencia-de-los-ordenadores\/structural-and-computational-aspects-of-simple-and-influence-games\/","title":{"rendered":"Structural and computational aspects of simple and influence games"},"content":{"rendered":"<h2>Tesis doctoral de <strong> Fabi\u00e1n Rolando Riquelme Csori <\/strong><\/h2>\n<p>Los juegos simples son una clase fundamental de juegos cooperativos, que tiene una enorme relevancia en diversas \u00e1reas de ciencias de la computaci\u00f3n, ciencias sociales y matem\u00e1ticas discretas aplicadas. En los \u00faltimos a\u00f1os, los distintos aspectos algor\u00edtmicos y de complejidad computacional de los juegos simples ha ido ganando notoriedad.  en esta tesis revisamos los distintos problemas computacionales relacionados con propiedades, par\u00e1metros y conceptos de soluci\u00f3n de juegos simples.  primero consideramos distintas formas de representaci\u00f3n de juegos simples, juegos regulares y juegos de mayor\u00eda ponderada, y estudiamos la complejidad computacional requerida para transformar un juego desde una representaci\u00f3n a otra. Tambi\u00e9n analizamos la complejidad de varios problemas abiertos bajo diferentes formas de representaci\u00f3n. En este sentido, demostramos que el problema de decidir si un juego simple en forma ganadora minimal es decisivo (un problema asociado al problema de dualidad de hipergrafos y funciones booleanas mon\u00f3tonas) puede resolverse en tiempo cuasi-polinomial, y que este problema puede reducirse polinomialmente al mismo problema pero restringido a juegos regulares en forma ganadora shift-minimal. Tambi\u00e9n demostramos que el problema de decidir si un juego regular en forma ganadora shift-minimal es fuerte (strong) es conp-completo. Adicionalmente, para juegos simples en forma ganadora minimal demostramos que el par\u00e1metro de anchura (width) puede computarse en tiempo polinomial. Independientemente de la forma de representaci\u00f3n, tambi\u00e9n estudiamos problemas de enumeraci\u00f3n y conteo para varias subfamilias de juegos simples.  luego introducimos los juegos de influencia, un nuevo enfoque para estudiar juegos simples basado en un modelo de dispersi\u00f3n de influencia en redes sociales, donde la influencia se dispersa de acuerdo con el modelo de umbral lineal (linear threshold model). Demostramos que los juegos de influencia abarcan la totalidad de la clase de los juegos simples. Para estos juegos tambi\u00e9n estudiamos la complejidad de los problemas relacionados con par\u00e1metros, propiedades y conceptos de soluci\u00f3n considerados para los juegos simples. Adem\u00e1s consideramos casos extremos con respecto a la demanda de influencia, y probamos que para ciertas subfamilias, varios de estos problemas se vuelven polinomiales.  finalmente estudiamos algunas aplicaciones inspiradas en los juegos de influencia. El primer conjunto de estos resultados tiene que ver con la definici\u00f3n de modelos de decisi\u00f3n colectiva. Para sistemas de mediaci\u00f3n, varios de los problemas de propiedades mencionados anteriormente son polinomialmente resolubles. Para los sistemas de influencia, demostramos que computar la satisfacci\u00f3n (una medida equivalente al \u00edndice de rae y similar al valor de banzhaf) es dif\u00edcil a menos que consideremos algunas restricciones en el modelo. Para los sistemas olfm, una generalizaci\u00f3n de los sistemas olf (van den brink et al. 2011, 2012) proporcionamos una axiomatizaci\u00f3n para la medida de satisfacci\u00f3n. El segundo conjunto de resultados se refiere al an\u00e1lisis de redes sociales, y en particular con la definici\u00f3n de nuevas medidas de centralidad de redes sociales, que comparamos en redes reales con otras medidas de centralidad cl\u00e1sicas.<\/p>\n<p>&nbsp;<\/p>\n<h3>Datos acad\u00e9micos de la tesis doctoral \u00ab<strong>Structural and computational aspects of simple and influence games<\/strong>\u00ab<\/h3>\n<ul>\n<li><strong>T\u00edtulo de la tesis:<\/strong>\u00a0 Structural and computational aspects of simple and influence games <\/li>\n<li><strong>Autor:<\/strong>\u00a0 Fabi\u00e1n Rolando Riquelme Csori <\/li>\n<li><strong>Universidad:<\/strong>\u00a0 Polit\u00e9cnica de catalunya<\/li>\n<li><strong>Fecha de lectura de la tesis:<\/strong>\u00a0 29\/07\/2014<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3>Direcci\u00f3n y tribunal<\/h3>\n<ul>\n<li><strong>Director de la tesis<\/strong>\n<ul>\n<li>Mar\u00eda  Jose Serna Iglesias<\/li>\n<\/ul>\n<\/li>\n<li><strong>Tribunal<\/strong>\n<ul>\n<li>Presidente del tribunal: josep Freixas bosch <\/li>\n<li>vito Fragnelli (vocal)<\/li>\n<li>martin Olsen (vocal)<\/li>\n<li>Jos\u00e9 Mar\u00eda Alonso meijide (vocal)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tesis doctoral de Fabi\u00e1n Rolando Riquelme Csori Los juegos simples son una clase fundamental de juegos cooperativos, que tiene una [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"footnotes":""},"categories":[1890,13880,15596,13536,13728],"tags":[229559,52051,30360,105628,229560,218773],"class_list":["post-116233","post","type-post","status-publish","format-standard","hentry","category-ciencia-de-los-ordenadores","category-informatica","category-politecnica-de-catalunya","category-teoria-de-juegos","category-teoria-y-procesos-de-decision","tag-fabian-rolando-riquelme-csori","tag-jose-maria-alonso-meijide","tag-josep-freixas-bosch","tag-maria-jose-serna-iglesias","tag-martin-olsen","tag-vito-fragnelli"],"_links":{"self":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/116233","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/comments?post=116233"}],"version-history":[{"count":0,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/116233\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/media?parent=116233"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/categories?post=116233"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/tags?post=116233"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}