Redes elétricas desempenham um papel fundamental no que tange à distribuição de energia elétrica. Entretanto, as redes elétricas convencionais são muito antigas, apresentando uma série de deficiências e inseguranças. Neste cenário surgem as redes elétricas inteligentes, mais conhecidas como smart grids. Smart grids são uma evolução para as redes elétricas tradicionais, apresentando como grande diferencial a presença intensiva de tecnologia de ponta para monitorar cada elemento que a compõe. Uma das principais características de smart grids é seu fluxo bidirecional de energia e informação, que permite a qualquer elemento tanto consumir quanto fornecer energia para a rede, seja um aerogerador ou mesmo uma residência. Tal característica vai de encontro à necessidade de se distribuir a produção energética, tornando-a mais robusta e tolerante a falhas. Uma tecnologia que surgiu em meio ao desenvolvimento de smart grids denomina-se Veículo-Para-Rede (V2G, do inglês Vehicle-To-Grid). Através de sessões V2G, veículos elétricos (EVs, em inglês electric vehicles) podem vender a energia de suas baterias para a rede, obtendo lucro com este procedimento. Existem duas vantagens nesta tecnologia. Por um lado, proprietários de EVs podem obter lucro com a venda de energia, reduzindo os custos de se manter seu veículo. Por outro lado, a rede como um todo se beneficia, pois as baterias podem ser utilizadas para aumentar a estabilidade da rede. Entretanto, para que estas vantagens sejam expressivas, é necessário utilizar-se de mecanismos para aumentar a eficiência do processo V2G, uma vez que baterias são muito caras. Uma alternativa que tem sido muito explorada é a formação de coalizões entre os EVs. A proposta deste trabalho é utilizar informações sobre o domínio de smart grids de modo a impor restrições no processo de formação de coalizões de EVs, visando à redução do espaço de busca de estruturas de coalizão. Especificamente, estabelece-se a distância máxima que pode haver entre dois EVs de uma mesma coalizão, através da qual é possível identificar e podar porções inválidas do espaço de busca. Para tanto, é proposto o algoritmo CPCSG, capaz de identificar restrições entre os EVs e de podar o espaço de busca. A abordagem proposta pode ser utilizada em conjunto com algoritmos de geração de estruturas de coalizão para torná-los mais rápidos e eficientes. Com base em experimentos, percebe-se que a abordagem proposta proporciona um ganho notável de desempenho e uma redução expressiva no uso de memória em relação a outros algoritmos para geração de estruturas de coalizão. Em geral, quanto mais restritiva a rede e quanto maior o número de agentes, maior será o percentual do espaço de busca passível de ser podado. Resultados mostram, ainda, que quando comparada com outros algoritmos de geração de estruturas de coalizão, a técnica proposta chega a superar o tempo dos demais em diversas ordens de magnitude. / Electric grids play a key role in the energy distribution process. However, conventional grids are very old, which causes the onset of weaknesses and uncertainties. In such a scenario the smart grid concept arises. Smart grids are an evolution to the ageing electric grids, whose major breakthrough is the intensive use of technology to monitor every element that comprises it. One of the main features of smart grids is its bi-directional flow of electricity and information, which allows any element to consume and even supply energy to the grid, regardless of being a wind turbine or even a residence. Such a characteristic meets the need to make the energy production more distributed, making it more robust and fault tolerant. Amidst the development of smart grids emerged the concept of Vehicle-To-Grid (V2G). Through V2G sessions, electric vehicles (EVs) can sell the surplus energy of their batteries to the grid, making a profit. Two advantages arise from this technology. First, EVs’ owners can make a profit from the sale of energy, reducing their vehicles’ maintenance cost. Second, the network as a whole is benefited as batteries could be used to increase the network stability. However, in order to benefit from such advantages, it is necessary the use mechanisms to increase the efficiency of the V2G process, since batteries are very expensive. One way that has been explored is the coalition formation among EVs. The proposal of this work is to use smart grids’ domain information to impose constraints on the coalition formation process in order to reduce the coalition structures’ search space. Specifically, we define a maximum distance that can exist between two EVs of a given coalition, through which it is possible to identify and prune invalid portions of the search space. To this end, we propose the CPCSG algorithm, which has the capability of identifying constraints among EVs and pruning the search space. The proposed approach can be used together with coalition structure generation algorithms to make them faster and more efficient. Based on experiments, it can be seen that our approach provides a noticeable performance gain and a significant memory usage reduction compared to other coalition structure generation algorithms. In general, the more restrictive the grid and the greater the number of agents, the greater the percentage of the search space that can be pruned. Results also show that when compared with other coalition structure generation algorithms, the proposed technique is able to overcome the other in time by several orders of magnitude.

In this thesis, we attack a challenging problem in the field of character animation: synthesizing interactions among multiple virtual characters in real-time. Although there are heavy demands in the gaming and animation industries, no systemic solution has been proposed due to the difficulties to model the complex behaviors of the characters. We represent the continuous interactions among characters as a discrete Markov Decision Process, and design a general objective function to evaluate the immediate rewards of launching an action. By applying game theory such as tree expansion and min-max search, the optimal actions that benefit the character the most in the future are selected. The simulated characters can interact competitively while achieving the requests from animators cooperatively. Since the interactions between two characters depend on a lot of criteria, it is difficult to exhaustively precompute the optimal actions for all variations of these criteria. We design an off-policy approach that samples and precomputes only meaningful interactions. With the precomputed policy, the optimal movements under different situations can be evaluated in real-time. To simulate the interactions for a large number of characters with minimal computational overhead, we propose a method to precompute short durations of interactions between two characters as connectable patches. The patches are concatenated spatially to generate interactions with multiple characters, and temporally to generate longer interactions. Based on the optional instructions given by the animators, our system automatically applies concatenations to create a huge scene of interacting crowd. We demonstrate our system by creating scenes with high quality interactions. On one hand, our algorithm can automatically generate artistic scenes of interactions such as the fighting scenes in movies that involve hundreds of characters. On the other hand, it can create controllable, intelligent characters that interact with the opponents for real-time applications such as 3D computer games.

Liu, Weiyang. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (p. 111-113). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Introduction and Literature Review --- p.1 / Chapter 1.1 --- Introduction --- p.1 / Chapter 1.1.1 --- Background and Motivating examples --- p.2 / Chapter 1.1.2 --- Basic Concepts --- p.4 / Chapter 1.1.3 --- Outline of the thesis --- p.6 / Chapter 1.2 --- Literature Review --- p.8 / Chapter 2 --- Multi-period Cooperative Re-investment Games: The Basic Model --- p.11 / Chapter 2.1 --- Basic settings and assumptions --- p.11 / Chapter 2.2 --- The problem --- p.13 / Chapter 3 --- Three sub-models and the allocation rule of Sub-Model III --- p.17 / Chapter 3.1 --- Three possible sub-models of the basic model --- p.17 / Chapter 3.1.1 --- Sub-model I --- p.17 / Chapter 3.1.2 --- Sub-model II --- p.18 / Chapter 3.1.3 --- Sub-model III --- p.19 / Chapter 3.2 --- The allocation rule of Sub-model III --- p.19 / Chapter 4 --- A two period example of the revised basic model --- p.25 / Chapter 4.1 --- The two period example with two projects --- p.25 / Chapter 4.2 --- The algorithm for the dual problem --- p.29 / Chapter 5 --- Extensions of the Basic Model --- p.35 / Chapter 5.1 --- The model with stochastic budgets --- p.36 / Chapter 5.2 --- The core of the model with stochastic budgets --- p.39 / Chapter 5.3 --- An example: the two-period case of models with stochastic bud- gets and an algorithm for the dual problem --- p.46 / Chapter 5.4 --- An interesting marginal effect --- p.52 / Chapter 5.5 --- "A Model with stochastic project prices, stochastic returns and stochastic budgets" --- p.54 / Chapter 6 --- Multi-period Re-investment Model with risks --- p.58 / Chapter 6.1 --- The Model with l1 risk measure --- p.58 / Chapter 6.2 --- The Model with risk measure --- p.66 / Chapter 7 --- Numerical Tests --- p.70 / Chapter 7.1 --- The affects from uncertainty changes --- p.71 / Chapter 7.2 --- The affects from budget changes --- p.71 / Chapter 7.3 --- The affects from the budget changes of only one group --- p.71 / Chapter 8 --- Conclusive Remarks --- p.77 / Chapter A --- Original Data and Analysis for Section 7.1 (Partial) --- p.79 / Chapter B --- Data Analysis for Section 7.2 (Partial) --- p.95 / Chapter C --- Data Analysis for Section 7.3 (Partial) --- p.98

Lee, Kwan Ho = 探討網絡上的若干動態過程 / 李鈞浩. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2008. / Includes bibliographical references (leaves 114-118). / Abstracts in English and Chinese. / Lee, Kwan Ho = Tan tao wang luo shang de ruo gan dong tai guo cheng / Li Junhao. / Chapter 1 --- Overview --- p.1 / Chapter 2 --- Networks --- p.5 / Chapter 2.1 --- Describing Networks --- p.5 / Chapter 2.1.1 --- Adjacency Matrix --- p.6 / Chapter 2.1.2 --- "Degree, Degree Distribution and Mean Degree" --- p.6 / Chapter 2.1.3 --- Clustering Coefficient --- p.7 / Chapter 2.1.4 --- "Shortest Path, Shortest Distance and Diameter" --- p.7 / Chapter 2.1.5 --- Betweenness --- p.9 / Chapter 2.2 --- Barabasi-Albert (BA) Network --- p.10 / Chapter 2.2.1 --- Construction of BA Network --- p.10 / Chapter 2.2.2 --- Analytical Study of Degree Distribution --- p.11 / Chapter 2.2.3 --- Numerical Study of Degree Distribution --- p.12 / Chapter 2.2.4 --- Shortest Distance --- p.13 / Chapter 2.3 --- Summary --- p.14 / Chapter 3 --- Routing in Networks: A Review --- p.16 / Chapter 3.1 --- Introduction --- p.16 / Chapter 3.2 --- Dijkstra´ةs Algorithm --- p.17 / Chapter 3.2.1 --- Algorithm --- p.17 / Chapter 3.2.2 --- Running Time --- p.18 / Chapter 3.2.3 --- Routing Table Based on Shortest Path Algorithm --- p.19 / Chapter 3.3 --- Routing Model --- p.19 / Chapter 3.3.1 --- General Setup --- p.19 / Chapter 3.3.2 --- Phase Transition and Evaluation of Network Performance --- p.20 / Chapter 3.4 --- Using Shortest Path as Routing Algorithm on BA Networks --- p.21 / Chapter 3.5 --- Other Routing Algorithms --- p.22 / Chapter 3.5.1 --- Efficient Path --- p.23 / Chapter 3.5.2 --- Routing based on Local Structural Information --- p.24 / Chapter 3.5.3 --- Routing based on Dynamical Information --- p.25 / Chapter 3.6 --- Summary --- p.26 / Chapter 4 --- Optimization of Routing Efficiency through Redistributing Limited Resources --- p.28 / Chapter 4.1 --- A Reallocation Rule - Short to Long (S2L) --- p.29 / Chapter 4.2 --- Performance Enhancement After Applying S2L --- p.33 / Chapter 4.3 --- Optimized Capability Distribution in Detail --- p.36 / Chapter 4.4 --- Summary --- p.44 / Chapter 5 --- N-person Evolutionary Snowdrift Game: A Review --- p.47 / Chapter 5.1 --- Snowdrift Game (SG) and Evolutionary Snowdrift Game (ESG) --- p.47 / Chapter 5.2 --- N-person Evolutionary Snowdrift Game --- p.49 / Chapter 5.2.1 --- Payoffs of C-character and D-character Agents --- p.49 / Chapter 5.2.2 --- Replicator Dynamics --- p.50 / Chapter 5.2.3 --- Numerical Simulations --- p.52 / Chapter 5.3 --- Summary --- p.55 / Chapter 6 --- NESG on Complex Network --- p.56 / Chapter 6.1 --- Models --- p.57 / Chapter 6.2 --- Results of Model A (varying N) --- p.58 / Chapter 6.2.1 --- Correlation of Characters in Degree --- p.60 / Chapter 6.2.2 --- Correlation of Characters in Distance --- p.62 / Chapter 6.3 --- Results of Model B (Fixed-N) --- p.63 / Chapter 6.3.1 --- Correlation of Characters in Degree --- p.64 / Chapter 6.4 --- Summary --- p.69 / Chapter 7 --- Synchronization: A Review --- p.71 / Chapter 7.1 --- Kuramoto Model --- p.72 / Chapter 7.1.1 --- Analytical Method --- p.74 / Chapter 7.1.2 --- Numerical Method --- p.78 / Chapter 7.1.3 --- Summary of Kuramoto Model --- p.81 / Chapter 7.2 --- Integrate-and-Fire Model --- p.81 / Chapter 8 --- Kuramoto Model with Spatially Distributed Oscillators --- p.84 / Chapter 8.1 --- Model --- p.84 / Chapter 8.2 --- Numerical Results --- p.85 / Chapter 8.3 --- Analytic Results --- p.87 / Chapter 8.4 --- Summary --- p.90 / Chapter 9 --- Integrate-Fire-and-Run Model --- p.92 / Chapter 9.1 --- Model --- p.92 / Chapter 9.2 --- Two-Body System --- p.94 / Chapter 9.2.1 --- Case I: Oscillators A and B are in different sites --- p.94 / Chapter 9.2.2 --- Case II: Oscillators A and B are in the same site --- p.101 / Chapter 9.2.3 --- Comparison of Analytic Results and Numerical Simulations of Two-Body system --- p.103 / Chapter 9.3 --- N-Body System --- p.105 / Chapter 9.4 --- Summary --- p.111 / Chapter 10 --- Outlook --- p.112 / Bibliography --- p.114

Real estate activity is notably influenced by local land use regulation. By acting as redtape costs or explicitly through compensatory payments, such rules typically increase construction costs by reducing supply and increasing demand in the housing market, which leads to higher prices. This is the first study to model the decision-making process of housing supply using a game theoretic approach. To shed light on the roleof regulation and competition in this industry, I employ a static-entry model that incorporates the demand, cost and strategic factors common to the activity. I built aunique data set forthe city of São Paulo, Brazil, with information on the universe ofnew residential buildings launched in the city, along with a history of all licenses requested by the developers tothe government for each project. My empirical results show that the regulation play akey role in developer activity. For the areas with the most intense activity of the city,the bureaucracy in the residential approval process cost annually R$ 47 millions (US$ 14millions) by entrant firm. / A atividade imobiliária é particularmente influenciada pela regulação do uso da terra. Ao agir como \"custos burocráticos\" ou explicitamente por meio de pagamentos compensatórios,essas regras normalmente aumentam os custos de construção ao reduzir a oferta e aumentara demanda de novas residências, o que leva a preços mais altos. Este é o primeiro estudo amodelar o processo de decisão de oferta de residências usando uma abordagem de teoria dos jogos. Para mostrar os efeitos da regulação e da competição nesse setor, eu emprego um modelo de entrada estático que incorpora os fatores de demanda, custo e estratégicos comuns a essa atividade. Eu construí uma base de dados única para a cidade de São Paulo, Brasil, com informações sobre o universo de novos empreendimentos residenciais na cidade, juntamente comum histórico de todas as licenças e alvarás requeridos pelas incorporadoras à Prefeitura para cada projeto. Meus resultados mostram que a regulação tem um papel chave na atividade imobiliária. Para as áreas com atividade mais intensa da cidade, a burocracia no processo de aprovação de novas residências tem um custo média anual de R$ 47 milhões por firma entrante no mercado.

In this paper I introduce some background for subtraction games and explore the Sprague-Grundy functions defined on them. I exhibit some subtraction games where the functions are guaranteed to be strictly periodic. I also exhibit a class of subtraction games which have bounded range, and show there are uncountably many of these.

No description available.

Le cloud computing est l’accomplissement du rêve de nombreux informaticiens désireux de transformer et d’utiliser leurs logiciels comme de simples services, rendant ces derniers plus attractifs et séduisants pour les utilisateurs. Dans le cadre de cette thèse, les technologies du cloud computing sont présentées, ainsi que les principaux défis que ce dernier va rencontrer dans un futur proche, notamment pour la gestion et l’analyse des données. A partir de la théorie moderne d'ordonnancements des tâches, nous avons proposé une gestion hiérarchique d’ordonnancements des tâches qui satisfait aux différentes demandes des cloud services. D’un point de vue théorique, nous avons principalement répondu à trois questions cruciales de recherche. Premièrement, nous avons résolu le problème de l'allocation des ressources au niveau de l’utilisateur. Nous avons en particulier proposé des algorithmes basés sur la théorie des jeux. Avec une méthode Bayésienne d’apprentissage, l'allocation des ressources atteint l'équilibre de Nash parmi les utilisateurs en compétition malgré une connaissance insuffisante des comportements de ces derniers. Deuxièmement, nous avons abordé le problème d'ordonnancements des tâches au niveau du système. Nous avons trouvé un nouveau seuil pour l'utilisation d’ordonnancements des tâches en ligne, considérant le dispositif séquentiel de MapReduce. Ce seuil donne de meilleurs résultats que les méthodes existantes dans l’industrie. Troisièmement, nous avons défini un critère de comparaison pour les tests d’ordonnancements de tâches en ligne. Nous avons proposé un concept de fiabilité d'essai pour évaluer la probabilité qu'un ensemble de tâches aléatoires passe un essai donné. Plus la probabilité est grande, plus la fiabilité est élevée. Un test présentant une grande fiabilité garantit une bonne utilisation du système. D’un point de vue pratique, nous avons développé un simulateur basé sur le concept de MapReduce. Ce simulateur offre un environnement directement utilisable par les chercheurs familiers avec SimMapReduce, leur permettant de s’affranchir des aspects informatiques d’implémentations et leur permettant notamment de se concentrer sur les aspects algorithmiques d’un point de vue théorique. / Cloud computing, the long-held dream of computing as a utility, has the potential to transform a large part of the IT industry, making software even more attractive as a service and shaping the way in which hardware is designed and purchased. In this thesis, we reviewed the new cloud computing technologies, and indicated the main challenges for their development in future, among which resource management problem stands out and attracts our attention. Combining the current scheduling theories, we proposed cloud scheduling hierarchy to deal with different requirements of cloud services. From the theoretical aspects, we have accomplished three main research issues. Firstly, we solved the resource allocation problem in the user-level of cloud scheduling. We proposed game theoretical algorithms for user bidding and auctioneer pricing. With Bayesian learning prediction, resource allocation can reach Nash equilibrium among non-cooperative users even though common knowledge is insufficient. Secondly, we addressed the task scheduling problem in the system-level of cloud scheduling. We proved a new utilization bound for on-line schedulability test, considering the sequential feature of MapReduce. We deduced the relationship between cluster utilization bound and the ratio of Map to Reduce. This new schedulable bound with segmentation uplifts classic bound which is most used in industry. Thirdly, we settled the comparison problem among on-line schedulability tests in cloud computing. We proposed a concept of test reliability to evaluate the probability that a random task set could pass a given schedulability test. The larger the probability is, the more reliable the test is. From the aspect of system, a test with high reliability can guarantee high system utilization. From the practical aspects, we have developed a simulator to model MapReduce framework. This simulator offers a simulated environment directly used by MapReduce theoretical researchers. The users of SimMapReduce only concentrate on specific research issues without getting concerned about finer implementation details for diverse service models, so that they can accelerate study progress of new cloud technologies.

Heterogeneous Computing (HC) systems achieve high performance by networking together computing resources of diverse nature. The issues of task assignment and scheduling are critical in the design and performance of such systems. In this thesis, an auction based game theoretic framework is developed for dynamic task scheduling in HC systems. Based on the proposed game theoretic model, a new dynamic scheduling algorithm is developed that uses auction based strategies. The dynamic scheduling algorithm yields schedules with shorter completion times than static schedulers while incurring higher scheduling overhead. Thus, a second scheduling algorithm is proposed which uses an initial schedule generated with a learning automaton based algorithm, and then heuristics are used to identify windows of tasks within the application that can be rescheduled dynamically during run time.

The problem of resource allocation and management in the context of multiple crises occurring in an urban environment is challenging. In this thesis, the problem is formulated using game theory and a solution is developed based on the Nash equilibrium to optimize the allocation of resources to the different crisis events in a fair manner considering several constraints such as the availability of resources, the criticality of the events, the amount of resources requested etc. The proposed approach is targeted at managing small to medium level crisis events occurring simultaneously within a specific pre-defined perimeter with the resource allocation centers being located within the same fixed region. The objective is to maximize the utilization of the emergency response units while minimizing the response times. In the proposed model, players represent the crisis events and the strategies correspond to possible allocations. The choice of strategies by each player impacts the decisions of the other players. The Nash equilibrium condition will correspond to the set of strategies chosen by all the players such that the resource allocation optimal for a given player also corresponds to the optimal allocations of the other players. The implementation of the Nash equilibrium condition is based on the Hansen's combinatorial theorem based approximation algorithm. The proposed solution has been implemented using C++ and experimental results are presented for various test cases. Further, metrics are developed for establishing the quality and fairness of the obtained results.