Aprendizagem por reforço multiagente (do inglês, MARL) é uma tarefa desafiadora em que agentes buscam, concorrentemente, uma política capaz de maximizar sua utilidade. Aprender neste tipo de cenário é difícil porque os agentes devem se adaptar uns aos outros, tornando o objetivo um alvo em movimento. Consequentemente, não existem garantias de convergência para problemas de MARL em geral. Esta tese explora um problema em particular, denominado escolha de rotas (onde motoristas egoístas deve escolher rotas que minimizem seus custos de viagem), em busca de garantias de convergência. Em particular, esta tese busca garantir a convergência de algoritmos de MARL para o equilíbrio dos usuários (onde nenhum motorista consegue melhorar seu desempenho mudando de rota) e para o ótimo do sistema (onde o tempo médio de viagem é mínimo). O principal objetivo desta tese é mostrar que, no contexto de escolha de rotas, é possível garantir a convergência de algoritmos de MARL sob certas condições. Primeiramente, introduzimos uma algoritmo de aprendizagem por reforço baseado em minimização de arrependimento, o qual provamos ser capaz de convergir para o equilíbrio dos usuários Nosso algoritmo estima o arrependimento associado com as ações dos agentes e usa tal informação como sinal de reforço dos agentes. Além do mais, estabelecemos um limite superior no arrependimento dos agentes. Em seguida, estendemos o referido algoritmo para lidar com informações não-locais, fornecidas por um serviço de navegação. Ao usar tais informações, os agentes são capazes de estimar melhor o arrependimento de suas ações, o que melhora seu desempenho. Finalmente, de modo a mitigar os efeitos do egoísmo dos agentes, propomos ainda um método genérico de pedágios baseados em custos marginais, onde os agentes são cobrados proporcionalmente ao custo imposto por eles aos demais. Neste sentido, apresentamos ainda um algoritmo de aprendizagem por reforço baseado em pedágios que, provamos, converge para o ótimo do sistema e é mais justo que outros existentes na literatura. / Multiagent reinforcement learning (MARL) is a challenging task, where self-interested agents concurrently learn a policy that maximise their utilities. Learning here is difficult because agents must adapt to each other, which makes their objective a moving target. As a side effect, no convergence guarantees exist for the general MARL setting. This thesis exploits a particular MARL problem, namely route choice (where selfish drivers aim at choosing routes that minimise their travel costs), to deliver convergence guarantees. We are particularly interested in guaranteeing convergence to two fundamental solution concepts: the user equilibrium (UE, when no agent benefits from unilaterally changing its route) and the system optimum (SO, when average travel time is minimum). The main goal of this thesis is to show that, in the context of route choice, MARL can be guaranteed to converge to the UE as well as to the SO upon certain conditions. Firstly, we introduce a regret-minimising Q-learning algorithm, which we prove that converges to the UE. Our algorithm works by estimating the regret associated with agents’ actions and using such information as reinforcement signal for updating the corresponding Q-values. We also establish a bound on the agents’ regret. We then extend this algorithm to deal with non-local information provided by a navigation service. Using such information, agents can improve their regrets estimates, thus performing empirically better. Finally, in order to mitigate the effects of selfishness, we also present a generalised marginal-cost tolling scheme in which drivers are charged proportional to the cost imposed on others. We then devise a toll-based Q-learning algorithm, which we prove that converges to the SO and that is fairer than existing tolling schemes.

No description available.

The first essay studies the Marginal Cost of Funds in the existence of tax evasion. We develop a general equilibrium model of tax evasion, including the expected utility of taxpayers and three different revenue-raising government policies. In this rich model environment, we analytically derive the marginal cost of funds (MCF) for the alternative policy instruments. We consider two main fiscal reforms: the revision in the nonlinear tax scheme and the changes in enforcement mechanism (the audit and penalty rates). First, we derive the MCF for the tax reform and find its key determinants. The derived MCF is greater than the previous ones since it includes a "risk-bearing cost" as well as tax distortion. The reform in enforcement mechanism generates MCFs in different forms. Two more MCFs with respect to audit and penalty rates are presented. Finally, we compare these three different MCFs in numerical example and provide some policy implications. The second essay explores optimal tax structure in the presence of status effect. When the consumption of certain goods affects one's social status, this externality creates two opposite effects in a society. Seeking higher status through “positional goods" gives individuals much incentive to supply labor but still allocates income for less “nonpositional goods" as well. In this case, differential taxes on positional goods work as corrective instruments to internalize the social cost stemming from status seeking. Furthermore, the differential taxes generate revenue that can be used to alleviate preexisting income tax distortion. Thus, the differential taxes on positional goods could give so called “double dividend." I develop a game-theoretic model in which each individual with a different labor productivity unknown to the others engages in a status-seeking game, and the government has a revenue requirement. Then I show that, under a condition in which utility is separable between positional goods and leisure, a revenue-neutral shift in the tax mix away from nonlinear income taxes towards positional-good taxes enhances welfare. Hence, the differential taxes on positional goods are necessary together with the nonlinear income taxes for an optimal tax structure. The third essay explores the impact of increasing capital mobility on regional growth and environment. I develop an endogenous growth model in which each local government competes against the others, to induce imperfectly mobile stock of capital into its region. Then I show that an increase in capital mobility generates “tax importing" due to which each locality experiences a higher growth rate and more degraded environment. That is, the increasing mobility dampens the capital tax and transfers the burden of pollution abatement to the locality. This finding supports the hypothesis of “race to the bottom" in environmental standards. Identifying a reduction in overall welfare of residents, I consider two alternative federal interventions in the model: uniform environmental standard and requirement of lump sum transfer or tax. Both of these federal instruments enhance the residents' welfare. / text

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-04-20T19:23:49Z No. of bitstreams: 1 rafaeldeoliveiragomes.pdf: 1378975 bytes, checksum: acfbbb683eac1c9cda51ec90f2c5c8a6 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-04-24T16:51:01Z (GMT) No. of bitstreams: 1 rafaeldeoliveiragomes.pdf: 1378975 bytes, checksum: acfbbb683eac1c9cda51ec90f2c5c8a6 (MD5) / Made available in DSpace on 2017-04-24T16:51:01Z (GMT). No. of bitstreams: 1 rafaeldeoliveiragomes.pdf: 1378975 bytes, checksum: acfbbb683eac1c9cda51ec90f2c5c8a6 (MD5) Previous issue date: 2012-08-02 / O Plano Decenal de Expansão de Energia (EPE, 2010) apresenta a expansão da oferta (ainda não contratada) 100% atrelada à geração de energia baseada em fontes renováveis: hidrelétricas, eólicas e termelétricas com queima de biomassa. O incentivo a uma maior participação de fontes renováveis na matriz energética é uma atitude louvável do governo brasileiro que, de alguma forma, tenta minimizar a expansão contratada nos leilões de energia nova até o ano de 2008, fortemente baseada em termelétricas a óleo combustível. A maioria das hidrelétricas viáveis para o período está localizada na Região Amazônica e devido a restrições socioambientais não há previsão de implantação de usinas com reservatórios de regularização das vazões afluentes. A maior participação de hidrelétricas de grande porte sem reservatórios implica em consequências diversas para a operação do Sistema Interligado Nacional (SIN), tais como: menor manobra para controle de cheias; maior exigência dos reservatórios; e maior despacho termelétrico para atender às exigências sazonais da carga. Além disso, impactos comerciais podem ser vislumbrados, como maior volatilidade do Preço de Liquidação de Diferenças, aumento dos riscos hidrológicos de usinas participantes do MRE e maior despacho de usinas termelétricas por ordem de mérito econômico. O presente trabalho analisa problemas como a diminuição da capacidade de regularização plurianual dos reservatórios e a necessidade do aumento da participação térmica a fim de conservar a segurança energética do SIN. Utiliza o modelo NEWAVE para examinar diversos cenários de vazões afluentes, baseadas em séries hidrológicas históricas e sintéticas, analisando panoramas futuros e desdobramentos do mercado de energia. Ademais, realiza estudos quanto à opção da expansão da oferta de energia por grandes hidrelétricas a fio d’água em detrimento de usinas com reservatórios de regularização, para isso realiza simulações modificando as características físicas da UHE Jirau de forma a comparar os resultados entre as alternativas. / The Ten-year Plan for Expansion of Energy (EPE, 2010) presents the expansion of offer (not auctioned) 100% tied to power generation based on renewable sources: hydro, wind and thermal power plants with biomass burning. Encouraging greater participation in renewable energy sources is a commendable attitude of the Brazilian government that somehow tries to minimize the expansion contracted in the auctions of new energy by the year 2008, based heavily on fuel oil fired plants. Most hydroelectric ventures considered viable for the period is located in the Amazon region and due to social and environmental restrictions there is no provision for deployment of power plants with reservoirs of regularization of inflows. The high participation of large hydroelectric without reservoirs implies in several consequences for the operation of the National Interconnected System (SIN), such as reduced availability of maneuvers for flood control; a higher demand of the existing reservoirs; and order more frequently thermoelectric power plants to achieve the seasonal demands of the load. Moreover, trade impacts can be envisioned, such as increased volatility of the Settlement Price Differences, increased risks of hydrological plants participating in the MRE and higher order of power plants in order of economic merit. This paper analyzes problems such as decreased ability to multi-annual adjustment of the reservoirs and the need for increased participation in order to conserve thermal energy security of the SIN. Uses NEWAVE model to examine different scenarios of inflows based on historical hydrological series and synthetic overviews analyzing future market developments and energy. Moreover, studies carried out on the option of expanding the supply of energy by large dams to trickle over plants with reservoirs of regularization, for it carries out simulations by modifying the physical characteristics of UHE Jirau in order to compare the results among the alternatives.

The electricity market is facing major changes in the coming years, with major production facilities that must be replaced and climate targets that are required to be met. The approach to the targets in the electricity market has been to invest in renewable energy, mostly in the form of wind power. However, it is an intermittent production type where production depends on weather conditions and planning cannot be predetermined. As a result, the price of electricity has varied a lot in recent years and has also become very low, which causes profitability challenges for the electricity producers. One consequence is the closure of four nuclear reactors due to lack of profitability. This creates a more uncertain environment for the Swedish industry, which is dependent on both low electricity prices and reliable power supply. A way to counter this has been the “Energy Agreement”, that partly aims to promote the use of nuclear power for their total technical service life. The electrical system will change until 2030 in many ways, but how this will go is difficult to predict. By creating three different scenarios that reflect likely future changes, it has been possible to draw conclusions about what is necessary to change for the electricity system to be robust and competitive in the future. These scenarios consider wind power, active nuclear reactors, export opportunities and future electricity prices. These three scenarios have included identification of the most important parameters that need to be changed or considered by 2030. These parameters have been divided into price issues, delivery security and taxes with subsequent proposals. The most important items under these are to maintain the marginal cost based pricing model, create incentives for flexibility of electricity users and for manufacturers to provide the power grid with inertia. These require special focus to create a robust and flexible system, but remaining points are required as well to handle these issues. These points resulted in a framework that should form the basis for decision making. The framework should also be used in its entirety to analyze situations that may arise during the transition from today's market to the future's renewable electricity system. / Elmarknaden står inför stora förändringar de kommande åren, med stora produktionsanläggningar som måste ersättas och klimatmål som förväntas uppfyllas. Tillvägagångssättet har på den svenska elektricitetsmarknaden varit att satsa på förnybar energi, mestadels i form av vindkraft. Det är dock ett intermittent produktionsslag där produktionen är väderberoende och inte går att planera. Elpriset har till följd av detta varierat mycket under de senaste åren och blivit väldigt lågt, något som orsakar lönsamhetsproblem för producenterna. Ett resultat av detta är stängningen av fyra kärnreaktorer till följd av bristande lönsamhet, vilket skapar en oroligare situation för den svenska industrin som är beroende av både låga elpris och en tillförlitlig eltillförsel. Ett sätt att möta konflikten mellan producenternas olönsamhet och industrins krav är Energiöverenskommelsen, som delvis syftar till att göra kärnkraften med konkurrenskraftig. Elsystemet kommer att förändras till 2030 på många vis, men hur detta kommer gå till är svårt att förutsäga. Genom att skapa tre olika scenarion som speglar troliga framtida förändringar, har det gått att dra slutsatser om vad som är nödvändigt att förändra för att elsystemet ska vara robust och konkurrenskraftigt även i framtiden. Dessa scenarion tar hänsyn till vindkraftsutbyggnad, aktiva kärnreaktorer, exportmöjligheter och framtida elpris. Dessa tre scenarion har inburit identifiering av de viktigaste parametrar som måste förändras eller tas i beaktande till 2030. Dessa har delats upp i prisfrågor, leveranssäkerhet samt skatter med efterföljande förslag. De viktigaste punkterna under dessa är att behålla marginalprissättningen, skapa incitament för flexibilitet hos elanvändare och för producenter att tillhandahålla svängmassa. Dessa kräver särskilt fokus för att skapa ett robust och flexibelt system, men resterande punkter behövs för att hantera dessa frågor. Dessa punkter resulterade i ett ramverk som bör ligga till grund för beslutsprocesser. Ramverket bör också användas i sin helhet för att analysera situationer som kan uppstå under omställningen från dagens marknad till framtidens förnybara elsystem.

This dissertation addresses five fundamental resource allocation problems on networks, all of which have applications to support Homeland Security or industry challenges. In the first application, we model and solve the strategic problem of minimizing the expected loss inflicted by a hostile terrorist organization. An appropriate allocation of certain capability-related, intent-related, vulnerability-related, and consequence-related resources is used to reduce the probabilities of success in the respective attack-related actions, and to ameliorate losses in case of a successful attack. Given the disparate nature of prioritizing capital and material investments by federal, state, local, and private agencies to combat terrorism, our model and accompanying solution procedure represent an innovative, comprehensive, and quantitative approach to coordinate resource allocations from various agencies across the breadth of domains that deal with preventing attacks and mitigating their consequences. Adopting a nested event tree optimization framework, we present a novel formulation for the problem as a specially structured nonconvex factorable program, and develop two branch-and-bound schemes based respectively on utilizing a convex nonlinear relaxation and a linear outer-approximation, both of which are proven to converge to a global optimal solution. We also investigate a fundamental special-case variant for each of these schemes, and design an alternative direct mixed-integer programming model representation for this scenario. Several range reduction, partitioning, and branching strategies are proposed, and extensive computational results are presented to study the efficacy of different compositions of these algorithmic ingredients, including comparisons with the commercial software BARON. The developed set of algorithmic implementation strategies and enhancements are shown to outperform BARON over a set of simulated test instances, where the best proposed methodology produces an average optimality gap of 0.35% (compared to 4.29% for BARON) and reduces the required computational effort by a factor of 33. A sensitivity analysis is also conducted to explore the effect of certain key model parameters, whereupon we demonstrate that the prescribed algorithm can attain significantly tighter optimality gaps with only a near-linear corresponding increase in computational effort. In addition to enabling effective comprehensive resource allocations, this research permits coordinating agencies to conduct quantitative what-if studies on the impact of alternative resourcing priorities. The second application is motivated by the author's experience with the U.S. Army during a tour in Iraq, during which combined operations involving U.S. Army, Iraqi Army, and Iraqi Police forces sought to interdict the transport of selected materials used for the manufacture of specialized types of Improvised Explosive Devices, as well as to interdict the distribution of assembled devices to operatives in the field. In this application, we model and solve the problem of minimizing the maximum flow through a network from a given source node to a terminus node, integrating different forms of superadditive synergy with respect to the effect of resources applied to the arcs in the network. Herein, the superadditive synergy reflects the additional effectiveness of forces conducting combined operations, vis-à-vis unilateral efforts. We examine linear, concave, and general nonconcave superadditive synergistic relationships between resources, and accordingly develop and test effective solution procedures for the underlying nonlinear programs. For the linear case, we formulate an alternative model representation via Fourier-Motzkin elimination that reduces average computational effort by over 40% on a set of randomly generated test instances. This test is followed by extensive analyses of instance parameters to determine their effect on the levels of synergy attained using different specified metrics. For the case of concave synergy relationships, which yields a convex program, we design an inner-linearization procedure that attains solutions on average within 3% of optimality with a reduction in computational effort by a factor of 18 in comparison with the commercial codes SBB and BARON for small- and medium-sized problems; and outperforms these softwares on large-sized problems, where both solvers failed to attain an optimal solution (and often failed to detect a feasible solution) within 1800 CPU seconds. Examining a general nonlinear synergy relationship, we develop solution methods based on outer-linearizations, inner-linearizations, and mixed-integer approximations, and compare these against the commercial software BARON. Considering increased granularities for the outer-linearization and mixed-integer approximations, as well as different implementation variants for both these approaches, we conduct extensive computational experiments to reveal that, whereas both these techniques perform comparably with respect to BARON on small-sized problems, they significantly improve upon the performance for medium- and large-sized problems. Our superlative procedure reduces the computational effort by a factor of 461 for the subset of test problems for which the commercial global optimization software BARON could identify a feasible solution, while also achieving solutions of objective value 0.20% better than BARON. The third application is likewise motivated by the author's military experience in Iraq, both from several instances involving coalition forces attempting to interdict the transport of a kidnapping victim by a sectarian militia as well as, from the opposite perspective, instances involving coalition forces transporting detainees between interment facilities. For this application, we examine the network interdiction problem of minimizing the maximum probability of evasion by an entity traversing a network from a given source to a designated terminus, while incorporating novel forms of superadditive synergy between resources applied to arcs in the network. Our formulations examine either linear or concave (nonlinear) synergy relationships. Conformant with military strategies that frequently involve a combination of overt and covert operations to achieve an operational objective, we also propose an alternative model for sequential overt and covert deployment of subsets of interdiction resources, and conduct theoretical as well as empirical comparative analyses between models for purely overt (with or without synergy) and composite overt-covert strategies to provide insights into absolute and relative threshold criteria for recommended resource utilization. In contrast to existing static models, in a fourth application, we present a novel dynamic network interdiction model that improves realism by accounting for interactions between an interdictor deploying resources on arcs in a digraph and an evader traversing the network from a designated source to a known terminus, wherein the agents may modify strategies in selected subsequent periods according to respective decision and implementation cycles. We further enhance the realism of our model by considering a multi-component objective function, wherein the interdictor seeks to minimize the maximum value of a regret function that consists of the evader's net flow from the source to the terminus; the interdictor's procurement, deployment, and redeployment costs; and penalties incurred by the evader for misperceptions as to the interdicted state of the network. For the resulting minimax model, we use duality to develop a reformulation that facilitates a direct solution procedure using the commercial software BARON, and examine certain related stability and convergence issues. We demonstrate cases for convergence to a stable equilibrium of strategies for problem structures having a unique solution to minimize the maximum evader flow, as well as convergence to a region of bounded oscillation for structures yielding alternative interdictor strategies that minimize the maximum evader flow. We also provide insights into the computational performance of BARON for these two problem structures, yielding useful guidelines for other research involving similar non-convex optimization problems. For the fifth application, we examine the problem of apportioning railcars to car manufacturers and railroads participating in a pooling agreement for shipping automobiles, given a dynamically determined total fleet size. This study is motivated by the existence of such a consortium of automobile manufacturers and railroads, for which the collaborative fleet sizing and efforts to equitably allocate railcars amongst the participants are currently orchestrated by the \textit{TTX Company} in Chicago, Illinois. In our study, we first demonstrate potential inequities in the industry standard resulting either from failing to address disconnected transportation network components separately, or from utilizing the current manufacturer allocation technique that is based on average nodal empty transit time estimates. We next propose and illustrate four alternative schemes to apportion railcars to manufacturers, respectively based on total transit time that accounts for queuing; two marginal cost-induced methods; and a Shapley value approach. We also provide a game-theoretic insight into the existing procedure for apportioning railcars to railroads, and develop an alternative railroad allocation scheme based on capital plus operating costs. Extensive computational results are presented for the ten combinations of current and proposed allocation techniques for automobile manufacturers and railroads, using realistic instances derived from representative data of the current business environment. We conclude with recommendations for adopting an appropriate apportionment methodology for implementation by the industry. / Ph. D.