Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Linguistics and Philosophy, 1982. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND HUMANITIES / Vita. / Bibliography: leaves 443-488. / by Lauri Henrik Carlson. / Ph.D.

The performance of many protocols and applications of Vehicular Ad hoc Networks (VANETs), depends on vehicles obtaining enough fresh information on the status of their neighbouring vehicles. This should be fulfilled by exchanging Basic Safety Messages (BSMs) also called beacons using a shared channel. In dense vehicular conditions, many of the beacons are lost due to channel congestion. Therefore, in such conditions, it is necessary to control channel load at a level that maximizes BSM dissemination. To address the problem, in this thesis algorithms for adaptation of beaconing to control channel load are proposed. First, a position-based routing protocol for VANETs is proposed and the requirement of adaptive beaconing to increase the performance of the protocol is indicated. The routing protocol is traffic-aware and suitable for city environments and obtains real-time traffic information in a completely ad hoc manner without any central or dedicated control, such as traffic sensors, roadside units, or information obtained from outside the network. The protocol uses an ant-based algorithm to find a route that has optimum network connectivity. Using information included in small control packets called ants, vehicles calculate a weight for every street segment that is proportional to the network connectivity of that segment. Ant packets are launched by vehicles in junction areas. To find the optimal route between a source and destination, a source vehicle determines the path on a street map with the minimum total weight for the complete route. The correct functionality of the protocol design has been verified and its performance has been evaluated in a simulation environment. Moreover, the performance of the protocol in different vehicular densities has been studied and indicated that in dense vehicular conditions the performance of the protocol degrades due to channel load created by uncontrolled periodic beaconing. Then, the problem of beaconing congestion control has been formulated as non-cooperative games, and algorithms for finding the equilibrium point of the games have been presented. Vehicles as players of the games adjust their beacon rate or power or both, based on the proposed algorithms so that channel load is controlled at a desired level. The algorithms are overhead free and fairness in rate or power or both rate and power allocation are achieved without exchanging excess information in beacons. Every vehicle just needs local information on channel load while good fairness is achieved globally. In addition, the protocols have per-vehicle parameters, which makes them capable of meeting application requirements. Every vehicle can control its share of bandwidth individually based on its dynamics or requirements, while the whole usage of the bandwidth is controlled at an acceptable level. The algorithms are stable, computationally inexpensive and converge in a short time, which makes them suitable for the dynamic environment of VANETs. The correct functionality of the algorithms has been validated in several high density scenarios using simulations.

Network reciprocity describes the emergence of cooperative behaviour where interactions are constrained by incomplete network connectivity. It has been widely studied as an enabling mechanism for the emergence of cooperation and may be of particular interest in explaining cooperative behaviours amongst unrelated individuals or in organisms of lower cognitive abilities. Research in this area has been galvanised by the finding that heterogeneous topology promotes cooperation. Consequently there has been a strong focus on scale-free networks; however, such networks typically presuppose formative mechanisms based on preferential attachment, a process which has no general explanation. This assumption may give rise to models of cooperation that implicitly encode capabilities only generally found in more complex forms of life, thus constraining their relevance with regards to the real world. By considering the connectivity of populations to be dynamic, rather than fixed, cooperation can exist at lower levels of heterogeneity. This thesis demonstrates that a model of network fluctuation, based on random rather than preferential growth, supports cooperative behaviour in simulated social networks of only moderate heterogeneity, thus overcoming difficulties associated with explanations based on scale-free networks. In addition to illustrating the emergence and persistence of cooperation in existing networks, we also demonstrate how cooperation may evolve in networks during their growth. In particular our model supports the emergence of cooperation in populations where it is originally absent. The combined impact of our findings increases the generality of reciprocity as an explanation for cooperation in networks.

Part I focuses on studying the extent of cooperation in networked entities, within the context of the Prisoner's Dilemma (PD) and the Snowdrift Game (SG). The iterated prisoner's dilemma (IPD) is studied in the full payoff space spanned by two parameters beta and gamma. A theoretical study on two-strategy IPD is presented. We then numerically study the IPD in the full payoff space, with four different initial configurations. It is found that including the Tit-for-tat-like (ETFT) and Always-defecting-like (EAllD) strategies as initial strategies can maximize the dominating area of generous strategies in the payoff space at equilibrium. The roles played by ETFT and EAllD are further studied on the diagonal and anti-diagonal lines of the payoff space. / Part II focuses mainly on studying the optical properties of grating within the Rigorous Coupled-Wave Analysis (RCWA) method. The surface plasmon (SP) dispersion relation in a system consisting of a thin metallic film sandwiched between a linear dielectric and nonlinear dielectric of arbitrary non- linearity is derived, based on a generalized "first integral" approach. The SP dispersion relation in a system consisting of a thin metallic film sandwiched in a symmetric nonlinear dielectric environment is then derived. The changes in SP dispersion relations on film thicknesses are discussed for both cases. / The optical properties of two samples of one-dimensional metallic reflection gratings are studied. The numerical results of the zeroth order reflectance are in good agreement with experimental data. The Wood's anomaly occurs when a particular diffraction order emerges or disappears, thus inducing a change in the efficiency of other diffraction orders. This phenomenon is studied by calculating and measuring the efficiencies of all allowed diffraction orders. Numerical results of the near field patterns show a coupling between the waveguide and SP modes. We also study the controllable enhanced trans- mission in a semiconductor grating. The dielectric constant of a semiconductor becomes a tensor in the presence of a static magnetic field parallel to the slit. Numerical results based on RCWA reveal that the zeroth order transmission peaks at normal incidence can be shifted to longer wavelengths and the peak values of transmission can largely be enhanced when a moderate magnetic field is applied. A single-mode theory incorporating anisotropy is developed. The analytic results are in quantitative agreement with RCWA, indicating that the tunability in the transmission stems from the waveguide mode. / The Snowdrift Game is regarded as an important alternative to PD in studying the emergence of cooperation in competing populations. The phase transitions in spatial snowdrift games are introduced. By studying the relative alignments of the payoffs of C and D nodes, the phase transitions are analytically explained. As an extension to the standard two-person SG, an N-person Snowdrift Game (NPSG) is proposed to include generic multi-person interactions. NPSG in a well-mixed population is studied analytically by using the replicator dynamics. A simulation algorithm is developed. We also study NPSG on lattices and find a suppressed cooperation frequency, when compared with the well-mixed case. For NPSG played on 1D chain, the problem can be solved analytically. We further extend our work to study co-evolving dynamics. We propose and study a model in which the connections are driven to evolve by the dynamics of SG. Compared with played on static network, the cooperation frequency is promoted. A semi-analytic theory is proposed, with the results qualitatively agree with simulation results. / The thesis consists of two independent parts. Part I focuses on evolutionary games in networked entities and Part II focuses on calculations on optical properties of metallic gratings. / Yin, Haiping = 競爭群體中合作的產生及具規則結構之金屬薄膜的光學性質 / 尹海平. / Adviser: Hui Pak Ming. / Source: Dissertation Abstracts International, Volume: 72-04, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (leaves 185-200). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. Ann Arbor, MI : ProQuest Information and Learning Company, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese. / Yin, Haiping = Jing zheng qun ti zhong he zuo de chan sheng ji ju gui ze jie gou zhi jin shu bo mo de guang xue xing zhi / Yin Haiping.

It is well established that one of the key contributing factors to the growth of countries’ economies is the existence of appropriate economic and social infrastructures. The setup of these infrastructures and their operation or delivery of public services associated with them have proved to be a costly and often unaffordable business for most governments. Therefore, private sector participation in the delivery of public services has been opted for by governments under Public-Private Partnerships (PPPs). Additional reasons for the public sector to choose a PPP framework to deliver public services include the public sector representatives’ lack of sufficient technical knowledge and specifications required by most projects; the required amount of investment to implement such projects is too high to be affordable by the public sector alone; the increasing difficulties of predicting and controlling the uncertainties that typically govern the phases of such projects including the level of actual demand for the related services by the time the project is operational; the level of bureaucracy in the public sector and its implications on the time frame of decision-making processes; the relatively low efficiency in project execution by the public sector; and most importantly the fact that, in practice, these difficulties are often better managed by the private sector who seem to possess both the financial and the executive capabilities to undertake such projects Currently, there is a gap in the game theory literature on modelling PPP related decisions and issues. This thesis contributes to reducing such gap by proposing three novel and practice-oriented game theoretical models along with algorithms for solving them, namely an ordinal game for the shortlisting of potential private sector partners; two non-cooperative dynamic games for negotiation with shortlisted private sector partners and selection of private sector partner to award the PPP contract to; and a non-cooperative dynamic game for financial renegotiation post-PPP contract award. In sum, each novel game addresses an important problem faced by the private sector during the typical stages of the life cycle of PPPs, namely private sector partner selection at the tendering stage; negotiation between the public sector and shortlisted bidders to select the candidate to whom to award a PPP contract to at the post-tendering stage; and financial re-negotiation between the public sector and the selected private sector partner at the post-contract award stage.

Este trabalho tem por proposta analisar a credibilidade da política monetária brasileira. O período verificado pelo trabalho é a partir de outubro de 1997 a dezembro de 2007, marcado principalmente por políticas antiinflacionárias e por dificuldades externas. Particularmente, busca verificar se houve ou não credibilidade neste período. Para tanto, é utilizado instrumental econométrico, via modelo autorregressivo com variáveis dummies. São feitos também testes necessários à detecção de correlação serial. Considera-se que há credibilidade quando se têm resultados nos quais a variável desemprego gera impactos negativos sobre o diferencial de taxa de juros entre Brasil e EUA. Os resultados da regressão do modelo mostram uma medida válida para a questão da credibilidade da política monetária no caso brasileiro. / This research has for proposal to analyze the credibility of Brazilian monetary policy. The verified period is between October/1997 and December/2007, manly characterized by anti-inflationary policies and external difficulties. Specifically, this research proposes to verify if there was or not credibility on the period. For that, it is used an econometric instrumental, by an autoregressive model with dummie variables. The necessary tests for the detection of serial correlation were made. Credibility exists when the unemployment variable generates negative impacts on the interest rate differentials between Brazil and USA. The results of model’s regression show a valid measurement to Brazilian monetary policy credibility.

The goals of the master thesis are describing the strategic oligopoly environment of chosen industry of Czech telecommunications, together with introducing basic game theory principles with their possible real case application. It mentions historical shifts in Czech telecommunications sector which influence the actual industry conditions. The thesis briefly describes the individual players in the market and turns its attention towards the industry characterization through standard oligopoly models. Following, it introduces theoretical insight on possible market entry strategies into oligopoly industries. The application part focuses on game-theory in pricing strategies, market entry and entry deterring scenarios with examples. Final part summarizes the objectives in detail and provides final comments on the thesis.

Nesta dissertação é explorado o comportamento emergente de uma população heterogênea de jogadores negociando segundo o jogo do ultimato: dois jogadores recebem uma oferta; um deles (o proponente) propõe a sua divisão, enquanto o outro jogador (o aceitador) pode aceitar ou rejeitar a proposta. A rejeição é prejudicial a ambos jogadores, pois nenhum deles recebe sua parcela dos possíveis ganhos. Neste contexto, o ganho e seus momentos são calculados a partir de métodos analíticos simples e várias simulações computacionais corroboram os resultados obtidos. Também são analisadas as flutuações estatísticas da distribuição do ganho. Além disso, é apresentada uma abordagem simples evolucionária que considera mudanças em estratégias baseadas em ganhos anteriores. Para este caso, é demonstrado que o tempo médio de permanência (idade) de uma estratégia de uma população de "justos" convergepara um valor constante enquanto t se aproxima do ∞ e o cutoff médio decai segundouma lei de potência em tempos altos, após uma queda inicial. Também foram observadas transições entre comportamentos de alto e baixo ganho. Adicionalmente foi estudadauma versão espacial desse modelo. Para tanto são consideradosjogadores interagindo com seus primeiros vizinhos em reticulados 2D de acordo com duas dinâmicas estocáticas: (1) morte e nascimento com amostragem seletiva (MNAS), (2) Gibbs sampling sobre a vizinhança (GS). Estes resultados trazem importantes considerações sobre o projeto de simulaçõesno contexto da teoria dos jogos evolucionários, em particular na simulação dos aspectos relevantes quando modelando grandes populações. / Weexplore the emergent behavior of a heterogeneous population of players negotiating via an ultimatum game: two players are offered a gift; one of them (the proposer) suggestshow to divide the offer while the other player (the responder) can either agree or reject the deal. Rejection is detrimental to both players as it results in no eamings. In this context, the payoff and its moments are calculated from simple analytical methods and several computer simulations corroborate the obtained results. Wealso analyze statistical fluctuationson payoff distribution. In addition,we present a simple evolutionaryapproach that considers changes in strategies based on previous eamings. For this case, we show that average permanence time (age) in a strategy of a fair population converges to a constant value when t approaches ∞ and the cutoff average decays as a power law for large times after a initial deterministic slip. We have also observed transitions between highlow payoffbehaviors. Additionallywe studied a spatial version ofthis model. For this we consider players interacting with their nearest neighbors in 2D lattices according to two different stochastic dynamics: (1) Death and birth with selective sampling (MNAS), (2) Gibbs sampling on neighborhood (GS) Webelieve that these results can bring important considerationsto the design of simulations in the context ofthe evolutionary game theory, in particular in the simulation of relevant features when modeling large populations.

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.