Orientador: Paulo de Barros Correia / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecânica / Made available in DSpace on 2018-08-27T01:59:39Z (GMT). No. of bitstreams: 1 Silva_ElisaBastos_D.pdf: 2776184 bytes, checksum: 20b2252b72c7204d062893f8dcb3d304 (MD5) Previous issue date: 2015 / Resumo: Leilões de novos empreendimentos de energia envolvem o compromisso de construí-los e o direito de explorá-los por meio de contratos de outorga. O leiloeiro, cujo objetivo é minimizar o pagamento pela energia contratada, buscando a redução de seu preço para os consumidores finais, fornece o direito de outorga da usina para o vencedor. O licitante é um investidor, e.g., uma empresa de geração que procura maximizar seu benefício com a venda de energia proveniente do empreendimento. Quando a natureza desses empreendimentos é complementar, torna-se possível proporcionar maiores benefícios aos licitantes, e maior eficiência ao leilão, caso sejam negociados em conjunto. Atualmente, o projeto de leilão instituído é composto por uma abordagem híbrida, sequencial e simultânea, que não permite a extração das sinergias entre empreendimentos. Esta tese examina duas metodologias híbridas de leilões reversos, considerando-se o ponto de vista do leiloeiro. O primeiro modelo, centralizado, é composto por duas fases: uma simultânea de lance aberto e outra combinatória de lance fechado. A fase simultânea incentiva a revelação do preço da energia, enquanto a fase combinatória oferece oportunidade aos licitantes de submeterem ofertas mais agressivas através de pacotes de empreendimentos complementares. O modelo centralizado é formulado como um problema de otimização inteiro e combinatório. A função-objetivo consiste em minimizar o pagamento, isso é, energia multiplicada pelo preço (lance) para todas as usinas. A estratégia de solução identifica os vencedores, resolvendo um problema de set-packing restrito. A segunda metodologia utiliza uma abordagem, também, em duas fases. A primeira é um projeto simultâneo de lance aberto, e a segunda fase um projeto combinatório descentralizado. Nesse modelo, a dificuldade do problema aumenta progressivamente à medida que os pacotes são ofertados. A dificuldade da alocação é distribuída entre os licitantes e, por isso, o leiloeiro não necessita resolver um problema de otimização. As metodologias propostas são aplicadas aos leilões de energia nova para o setor elétrico brasileiro. Os resultados mostram que a utilização de ambas as metodologias resolvem o problema de alocação com um tempo computacional aceitável / Abstract: Auctions for new power plants involve a commitment of constructing and the right of exploring them through power sales contracts. The auctioneer -- whose objective is to minimize the payment for the contracted energy, seeking to reduce prices for consumers -- provides the power plant's right for the winner. The bidder is an investor, for example, a generation company, which aims to maximize benefits of energy sales. When the power plant's nature is complementary, it is possible to provide more benefits to bidders and greater efficiency to the auction if these plants were traded together. Currently, the instituted auction design consists of a hybrid approach -- sequential and simultaneous -- which does not allow the extraction of synergies among plants. This thesis examines two hybrid methods of reverse auctions from the auctioneer's view point. The first model, centralized, consists of two phases: a simultaneous open bid and a combinatorial sealed bid. The simultaneous phase encourages the energy prices revelation. The combinatorial phase allows aggressive bidders to acquire bundles of complementary plants. The centralized model is formulated as an integer and combinatorial optimization problem. The objective function consists of minimizing the payment, that is, energy multiplied by the price (bid) for all plants. The solution strategy identifies the winners solving a restricted set-packing problem. The second method also uses a two phase approach. The first phase is a simultaneous open bid design and the second phase is a decentralized combinatorial design. In this model, the problem difficulty increases gradually. The allocation difficulty is distributed among the bidders; therefore, the auctioneer does not need to solve an optimization problem. The proposed methodologies are applied to new energy auctions on Brazilian electrical energy sector. The results show the use of both methods solving the problem of allocation with an acceptable computational time / Doutorado / Planejamento de Sistemas Energeticos / Doutora em Planejamento de Sistemas Energéticos

This dissertation is a collection of articles on the design of procurement auctions. Chapter 1 provides a primer to the subsequent three essays. Rather than addressing all the issues involved, it illustrates some basic concepts about auctions, both institutionally and theoretically. It also highlights some problems that arise when auction theory is applied to procurement auctions. / Ph. D.

This thesis looks at three aspects related to the design of E-commerce systems, online auctions and distributed grid computing systems. We show how formal verification techniques from computer science can be applied to ensure correctness of system design and implementation at the code level. Through e-ticket sales example, we demonstrate that model checking can locate subtle but critical flaws that traditional control and auditing methods (e.g., penetration testing, analytical procedure) most likely miss. Auditors should understand formal verification methods, enforce engineering to use them to create designs with less of a chance of failure, and even practice formal verification themselves in order to offer credible control and assistance for critical e-systems. Next, we study why many online auctions offer fixed buy prices to understand why sellers and auctioneers voluntarily limit the surplus they can get from an auction. We show when either the seller of the dibbers are risk-averse, a properly chosen fixed permanent buy-price can increase the social surplus and does not decrease the expected utility of the sellers and bidders, and we characterize the unique equilibrium strategies of uniformly risk-averse buyers in a buy-price auction. In the final chapter we look at the design of a distributed grid-computing system. We show how code-instrumentation can be used to generate a witness of program execution, and show how this witness can be used to audit the work of self-interested grid agents. Using a trusted intermediary between grid providers and customers, the audit allows payment to be contingent on the successful audit results, and it creates a verified reputation history of grid providers. We show that enabling the free trade of reputations provides economic incentives to agents to perform the computations assigned, and it induces increasing effort levels as the agents' reputation increases. We show that in such a reputation market only high-type agents would have incentive to purchase a high reputation, and only low-type agents would use low reputations, thus a market works as a natural signaling mechanism about the agents' type. / text

Pesquisas recentes mostram que abordagens baseadas em sistemas multiagentes (SMA) e mecanismos de mercado como leilões são eficazes para encontrar soluções factíveis para problemas de planejamento em cadeias de suprimento. Esta dissertação aborda a utilização do paradigma de SMA baseado em Leilões Combinatoriais e o uso de estratégias de participação em leilões na resolução do problema de transporte de derivados de petróleo em uma rede multimodal da PETROBRAS – Petróleo Brasileiro S/A, denominado Problema de Transporte de Derivados de Petróleo Simplificado (PTDPS), que se caracteriza como um problema de planejamento em cadeias de suprimento. Em leilões combinatoriais, a determinação do vencedor é um problema NP-Completo sem algoritmos de aproximação, cujo custo computacional aumenta com o número de ofertas recebidas pelo leiloeiro. Este trabalho tem por objetivo aumentar o escopo de aplicação de leilões combinatoriais em problemas de planejamento pelo uso de uma estratégia heurística de participação em leilões, além de servir como uma ferramenta de apoio à tomada de decisão por especialistas da indústria petrolífera. Os resultados obtidos a partir da aplicação do SMA desenvolvido em uma série de cenários para a estratégia proposta (avaliação da necessidade global) e outras de referência (geral - todos os leilões possíveis - e gulosa – somente um leilão) foram comparados entre si e demonstram que a utilização da estratégia proposta reduz o tempo de processamento em relação à estratégia geral e sem perda da qualidade da solução em comparação com as estratégias geral e gulosa. Outras contribuições deste trabalho são um SMA para realizar o planejamento do transporte de derivados de petróleo tendo como modelo de negociação o mecanismo de leilões combinatoriais e a proposição de um modelo descentralizado onde diversos leilões combinatoriais podem ser executados simultaneamente. / Recent researches have shown that approaches based on multi-agent systems (MAS) and market mechanisms like auctions are efficient on the resolution of planning problems in supply chains. This work uses the combinatorial auction-based MAS paradigm and participation strategies in auctions for solving the problem of transporting oil derivatives of PETROBRAS - Petroleo Brasileiro S/A, called Simplified Problem of Transporting Oil Derivatives (SPTOD), which is characterized as a planning problem in supply chains. In combinatorial auctions, the winner determination is a NP-Complete problem without approximation algorithms, whose computational cost increases with the number of bids received by the auctioneer. In this context, this work aims at enlarging the scope of application of combinatorial-auction mechanisms in planning problems by using a heuristic strategy for participation in auctions, besides serving as a support tool for decision-making process by specialists of industrial oil. The results were drawn from several scenarios where the MAS was used with the proposed strategy (global evaluation of needs) and with other strategies for comparison (general – all possible auctions – and greedy – only one auction). The results show that the use of the proposed strategy reduces the processing time when compared to the general strategy and that the quality of the solution is preserved in comparison with the general and greedy strategies. Other contributions of this work are the development of a MAS to realize the planning of transporting oil derivatives between producing and consuming basis having as negotiation model the combinatorial auction-based mechanism and a proposition of a decentralized model where several combinatorial auctions can be run simultaneously.

We study two classes of problems within Algorithmic Economics: revenue guarantees of simple mechanisms, and social welfare guarantees of auctions. We develop new structural and algorithmic tools for addressing these problems, and obtain the following results: In the 𝑘-unit model, four canonical mechanisms can be classified as: (i) the discriminating group, including Myerson Auction and Sequential Posted-Pricing, and (ii) the anonymous group, including Anonymous Reserve and Anonymous Pricing. We prove that any two mechanisms from the same group have an asymptotically tight revenue gap of 1 + θ(1 /√𝑘), while any two mechanisms from the different groups have an asymptotically tight revenue gap of θ(log 𝑘). In the single-item model, we prove a nearly-tight sample complexity of Anonymous Reserve for every value distribution family investigated in the literature: [0, 1]-bounded, [1, 𝐻]-bounded, regular, and monotone hazard rate (MHR). Remarkably, the setting-specific sample complexity poly(𝜖⁻¹) depends on the precision 𝜖 ∈ (0, 1), but not on the number of bidders 𝑛 ≥ 1. Further, in the two bounded-support settings, our algorithm allows correlated value distributions. These are in sharp contrast to the previous (nearly-tight) sample complexity results on Myerson Auction. In the single-item model, we prove that the tight Price of Anarchy/Stability for First Price Auctions are both PoA = PoS = 1 - 1/𝜖² ≈ 0.8647.

CAPES / O segmento downstream da cadeia de suprimentos da indústria brasileira de petróleo é composta por bases de produção (e.g. refinarias), armazenamento (e.g. terminais) e consumo (e.g. mercados consumidores) e modais de transportes (e.g. oleodutos, navios, caminhões e trens). O planejamento da transferência de derivados de petróleo nesta rede multimodal é um problema complexo e atualmente é realizado para um horizonte de três meses com base na experiência de profissionais e sem auxílio de um sistema computacional de apoio à decisão. Basicamente, o problema pode ser visto como uma negociação para alocação de recursos disponíveis (tais como derivados de petróleo, tanques e modais de transporte) pelas diferentes bases envolvidas que necessitam enviar ou receber derivados de petróleo. Na literatura, alguns problemas semelhantes, porém mais voltados para o planejamento de redes formadas por um único tipo de modal de transporte, têm sido tratados por diferentes abordagens, com predominância da programação matemática. Estes trabalhos ilustram a difícil tarefa de modelar grandes problemas por meio desta abordagem. Geralmente, tais trabalhos consideram apenas um curto horizonte de planejamento ou apenas uma parte do problema original, tal como uma parte da rede petrolífera brasileira, gerando limitações importantes para os modelos desenvolvidos. Devido às características do problema em estudo, o qual envolve toda a rede de transporte e apresenta perfil de negociação entre as diferentes entidades envolvidas, surge o interesse da utilização do paradigma de sistemas multiagente. O paradigma de agentes tem sido aplicado a problemas de diferentes contextos, particularmente em problemas de gerenciamento de cadeias de suprimentos devido à sua correspondência natural com a realidade e, em geral, em problemas que envolvem a competição por recursos por meio de mecanismos de negociação com base em leilões. Este trabalho apresenta um novo protocolo de negociação baseado em leilões e aplicação deste protocolo em forma de um modelo multiagente na resolução do problema de planejamento em questão. Os agentes que formam a solução representam principalmente os locais de produção, armazenamento, consumo e os modais de transporte na rede petrolífera brasileira. O objetivo destes agentes é manter um nível de estoque diário factível de cada produto em cada local por meio de transferências de produtos pela rede petrolífera brasileira com preferível redução do custo de transporte. Por fim, este trabalho apresenta a satisfação destes objetivos por meio de experimentos em cenários fictícios e reais da rede brasileira de petróleo. / The Brazilian oil supply chain is composed by oil refineries, consumer markets, terminals for intermediary storage and several transportation modals, such as pipelines, ships, trucks and trains. The transportation planning of oil products in this multimodal network is a complex problem that is currently performed manually based on expertise, for a period of three months, due to the lack of a software system to cover the problem complexity. Such problem involves the negotiation of available resources such as oil products, tanks and transportation modals between different sources and consumption points. Similar problems, but more directed to the planning of single modes of transportation, have been treated by different approaches, mainly mathematical programming. Such works illustrate the difficult task of modeling large problems with this mechanism. Generally, they consider a short horizon planning or only part of the original problem, such as a part of the network, rendering important limitations to the models developed. Due to the characteristics of the problem in study where the full network needs to be considered and there exists negotiation amongst the different entities involved, the usage of multi-agent models seems to be worth to explore. Such models have been applied in different contexts such as to supply chain problems due its natural correspondence with the reality. Furthermore, in problems involving competition for resources, multi-agents negotiation mechanisms based on auctions are commonly applied. Thus, this thesis presents one auction-based solution formed by the cooperation among agents for them to achieve their goals. The agents involved in the auctions represent mainly the production, storage and consumption locations. Their goal is to maintain a daily suitable inventory level for each product by means of transportation through the multimodal network at a low transport cost. Finally, this paper presents the satisfaction of these objectives through experiments on real and fictional scenarios of Brazilian oil network.

CAPES / O segmento downstream da cadeia de suprimentos da indústria brasileira de petróleo é composta por bases de produção (e.g. refinarias), armazenamento (e.g. terminais) e consumo (e.g. mercados consumidores) e modais de transportes (e.g. oleodutos, navios, caminhões e trens). O planejamento da transferência de derivados de petróleo nesta rede multimodal é um problema complexo e atualmente é realizado para um horizonte de três meses com base na experiência de profissionais e sem auxílio de um sistema computacional de apoio à decisão. Basicamente, o problema pode ser visto como uma negociação para alocação de recursos disponíveis (tais como derivados de petróleo, tanques e modais de transporte) pelas diferentes bases envolvidas que necessitam enviar ou receber derivados de petróleo. Na literatura, alguns problemas semelhantes, porém mais voltados para o planejamento de redes formadas por um único tipo de modal de transporte, têm sido tratados por diferentes abordagens, com predominância da programação matemática. Estes trabalhos ilustram a difícil tarefa de modelar grandes problemas por meio desta abordagem. Geralmente, tais trabalhos consideram apenas um curto horizonte de planejamento ou apenas uma parte do problema original, tal como uma parte da rede petrolífera brasileira, gerando limitações importantes para os modelos desenvolvidos. Devido às características do problema em estudo, o qual envolve toda a rede de transporte e apresenta perfil de negociação entre as diferentes entidades envolvidas, surge o interesse da utilização do paradigma de sistemas multiagente. O paradigma de agentes tem sido aplicado a problemas de diferentes contextos, particularmente em problemas de gerenciamento de cadeias de suprimentos devido à sua correspondência natural com a realidade e, em geral, em problemas que envolvem a competição por recursos por meio de mecanismos de negociação com base em leilões. Este trabalho apresenta um novo protocolo de negociação baseado em leilões e aplicação deste protocolo em forma de um modelo multiagente na resolução do problema de planejamento em questão. Os agentes que formam a solução representam principalmente os locais de produção, armazenamento, consumo e os modais de transporte na rede petrolífera brasileira. O objetivo destes agentes é manter um nível de estoque diário factível de cada produto em cada local por meio de transferências de produtos pela rede petrolífera brasileira com preferível redução do custo de transporte. Por fim, este trabalho apresenta a satisfação destes objetivos por meio de experimentos em cenários fictícios e reais da rede brasileira de petróleo. / The Brazilian oil supply chain is composed by oil refineries, consumer markets, terminals for intermediary storage and several transportation modals, such as pipelines, ships, trucks and trains. The transportation planning of oil products in this multimodal network is a complex problem that is currently performed manually based on expertise, for a period of three months, due to the lack of a software system to cover the problem complexity. Such problem involves the negotiation of available resources such as oil products, tanks and transportation modals between different sources and consumption points. Similar problems, but more directed to the planning of single modes of transportation, have been treated by different approaches, mainly mathematical programming. Such works illustrate the difficult task of modeling large problems with this mechanism. Generally, they consider a short horizon planning or only part of the original problem, such as a part of the network, rendering important limitations to the models developed. Due to the characteristics of the problem in study where the full network needs to be considered and there exists negotiation amongst the different entities involved, the usage of multi-agent models seems to be worth to explore. Such models have been applied in different contexts such as to supply chain problems due its natural correspondence with the reality. Furthermore, in problems involving competition for resources, multi-agents negotiation mechanisms based on auctions are commonly applied. Thus, this thesis presents one auction-based solution formed by the cooperation among agents for them to achieve their goals. The agents involved in the auctions represent mainly the production, storage and consumption locations. Their goal is to maintain a daily suitable inventory level for each product by means of transportation through the multimodal network at a low transport cost. Finally, this paper presents the satisfaction of these objectives through experiments on real and fictional scenarios of Brazilian oil network.

Not available / text

Not available / text

Investigate the use of partial relations for multicriteria reverse auctions. At first, a theoretical framework is introduced. Then, an extension of traditional multicriteria tools is considered. This is referred to as the Butterfly model. Finally, the concept of Bidding Niches partitions is formalized and tested. / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished