Ingeniero Civil Industrial / Ingeniero Civil Mecánico / Muchas empresas poseen numerosos equipos mecánicos que son ocupados en sus procesos productivos, donde el mantenimiento de ellos es realizado por equipos de técnicos propios llevando también los costos y la derivación de las capacidades y habilidades. Otras firmas, consideran la estrategia de externalizar ciertos procesos, relacionados o no, con el negocio que está abocada la empresa, delegando a terceras entidades la realización de estas. La externalización es normada por medio de contratos que clarifican deberes y obligaciones de las partes. En Chile la externalización u outsourcing en mantenimiento de activos fijos es una de las actividades estratégicas más recurridas, además de ser una de las mejor evaluadas (Menéndez [11]). Las fallas de los equipos son hechos aleatorios por lo que no pueden ser previstos y que afectan la producción de la empresa. Estas son modeladas probabilísticamente en relación a la política de mantenimiento, aquí mantenimiento perfecto. El tiempo en que los equipos están no operativos siendo intervenidos también afectan la producción. Desde la perspectiva del proveedor del servicio juegan a favor la cantidad de intervenciones correctivas y preventivas que realice, marginalizando por cada una de ellas, juega en contra, por concepto de multa, el tiempo excesivo en que los equipos no son devueltos operativos al cliente. Estas constituyen los beneficios para el cliente y desutilidad para el proveedor. En esta memoria se determinarán los precios que caracterizan a los contratos, tanto de la intervención preventiva como de la correctiva. Esto se logrará mediante la teoría de juegos como un problema principal-agente, donde el principal es el cliente, con alto poder de negociación y el proveedor será el agente con escaso poder en relación a una estrategia, sea esta: mantenimiento correctivo, preventivo (intervención por edad y por bloque de tiempo).

The analysis of the computational aspects of strategic situations is a basic field in Computer Sciences. Two main topics related to strategic games have been developed. First, introduction and analysis of a class of games (so called angel/daemon games) designed to asses web applications, have been considered. Second, the problem of isomorphism between strategic games has been analysed. Both parts have been separately considered. Angel-Daemon Games A service is a computational method that is made available for general use through a wide area network. The performance of web-services may fluctuate; at times of stress the performance of some services may be degraded (in extreme cases, to the point of failure). In this thesis uncertainty profiles and Angel-Daemon games are used to analyse servicebased behaviours in situations where probabilistic reasoning may not be appropriate. In such a game, an angel player acts on a bounded number of ¿angelic¿ services in a beneficial way while a daemon player acts on a bounded number of ¿daemonic¿ services in a negative way. Examples are used to illustrate how game theory can be used to analyse service-based scenarios in a realistic way that lies between over-optimism and over-pessimism. The resilience of an orchestration to service failure has been analysed - here angels and daemons are used to model services which can fail when placed under stress. The Nash equilibria of a corresponding Angel-Daemon game may be used to assign a ¿robustness¿ value to an orchestration. Finally, the complexity of equilibria problems for Angel-Daemon games has been analysed. It turns out that Angel-Daemon games are, at the best of our knowledge, the first natural example of zero-sum succinct games. The fact that deciding the existence of a pure Nash equilibrium or a dominant strategy for a given player is Sp 2-complete has been proven. Furthermore, computing the value of an Angel-Daemon game is EXP-complete. Thus, matching the already known complexity results of the corresponding problems for the generic families of succinctly represented games with exponential number of actions. Game Isomorphism The question of whether two multi-player strategic games are equivalent and the computational complexity of deciding such a property has been addressed. Three notions of isomorphisms, strong, weak and local have been considered. Each one of these isomorphisms preserves a different structure of the game. Strong isomorphism is defined to preserve the utility functions and Nash equilibria. Weak isomorphism preserves only the player preference relations and thus pure Nash equilibria. Local isomorphism preserves preferences defined only on ¿close¿ neighbourhood of strategy profiles. The problem of the computational complexity of game isomorphism, which depends on the level of succinctness of the description of the input games but it is independent of the isomorphism to consider, has been shown. Utilities in games can be given succinctly by Turing machines, boolean circuits or boolean formulas, or explicitly by tables. Actions can be given also explicitly or succinctly. When the games are given in general form, an explicit description of actions and a succinct description of utilities have been assumed. It is has been established that the game isomorphism problem for general form games is equivalent to the circuit isomorphism when utilities are described by Turing Machines; and to the boolean formula isomorphism problem when utilities are described by formulas. When the game is given in explicit form, it is has been proven that the game isomorphism problem is equivalent to the graph isomorphism problem. Finally, an equivalence classes of small games and their graphical representation have been also examined.