Financial markets use auctions to provide accurate liquidity snapshots for traded instruments. Combination orders, such as time spreads require the atomic trading of more than one security contract. In order to auction such complex order types, a new design, which considers all contingent instruments simultaneously, is required. This work develops an optimization model and a software implementation of the dualsided multi-unit combinatorial auction problem. The optimization objective is finding an equilibrium price vector and a winner selection such that the auction turnover is maximized. The auction requirements are modeled as a discrete optimization problem, suitable for standard integer programming solvers. The model’s correctness and tractability are tested using synthetically generated orders as well as real market data. Test results with both synthetic and authentic orders produced equilibrium prices within 3% of the expected instrument valuations, using closing prices as a benchmark, indicating high accuracy of the solutions. The use of combinatorial auctions exposes greater liquidity and overall turnover, both valuable to exchanges that receive large numbers of combination orders.

The public procurement draws a lot of attention in terms of treatment with public resources. Unfortunately this attention has mostly negative character. The aim of this Diploma Thesis is to bring an untraditional overview on the processing of public procurement and introduce one of the modern ways of using auction mechanisms. Combinatorial auctions can, as it already happened in other areas, open new possibilities for contracting authorities and bidders who participate in procurement conducted in accordance with Czech legislation. Also this Diploma Thesis can be the inspiration for thought if the current rules for public procurement are in accordance with the best interests of contracting authorities and bidders. In order to present the application of combinatorial auctions on public procurement the mathematical model based on partially real data was compiled in software Lingo. The results of such model were used as the source for the effectiveness analysis of discussed topic.

A seleção de fornecedores de transporte é um desafio cada vez maior. O crescimento da rede de clientes a ser coberta demanda uma alocação eficiente em termos de custo não suprida por mecanismos tradicionais de negociação. Neste âmbito, o leilão combinatório torna-se uma alternativa de negociação ao permitir capturar sinergias entre os trajetos que devem ser atendidos. Em conseqüência disso, diminui-se o custo de transporte do fornecedor que se reflete nos menores preços de suas propostas e finalmente no custo total de compra do serviço. Por outro lado, esta decisão envolve fatores além do custo total; a mensuração destes torna-se importante para identificar fornecedores que melhor se ajustam aos requerimentos do comprador. No entanto, é fundamental escolher um método adequado para sua avaliação porque este influência a decisão final. Este problema de compra de serviços de transporte é conhecido na literatura como Winner Determination Problem (WDP) que, devido a sua complexidade, possui uma resolução limitada. Após revisão teórica, foi observado que os estudos relacionados à área de transporte focalizavam o desenvolvimento de modelos matemáticos que fossem representativos da realidade. Alguns destes modelos abordam a utilização de múltiplos critérios atribuindo um coeficiente que pondera cada critério. Evidenciou-se a necessidade do desenvolvimento de um algoritmo alternativo que além de facilitar sinergias entre trajetos, fosse abrangente o suficiente para tratar múltiplos critérios em instâncias compatíveis com problemas reais. Logo, com o intuito de contribuir com a literatura foi adaptado um algoritmo matemático otimizante ao problema de compras de fornecedores de transporte com base no algoritmo de Sandholm (2002). Este algoritmo aplica leilão combinatório de compras, apoiando-se na teoria da análise de decisão para mensurar critérios relevantes do comprador. Inicialmente, o algoritmo minimiza o custo total do comprador designando combinações de trajetos e fornecedores; depois é modificado para o tratamento multi-critério. Os resultados obtidos foram comparados com o software comercial CPLEX. / Selecting suppliers is a crescent challenge for the enterprises. The extent of the client web that needs to be served demands efficient allocations, in terms of cost, that are not addressed by traditional mechanisms. In this scenario, another mechanism came to be: the combinatorial auction. In this one, suppliers can express their synergies on routes they wish to supply. This leads to lowering their transportation costs, which is reflected in lower bidding prices as well as in the total cost of service. On the other hand, the selection of a supplier involves other criteria besides cost. The definition of these is essential to define which supplier fits the needs of the buyer. That is why it is of most importance to choose the right method to evaluate these needs, as it defines the final choice. This problem is known as Winner Determination Problem (WDP) and due to its complexity, possesses a feeble solution. After compiling what has been done about the subject, it was noticed that in the field of transport, studies are focused on mathematical models that represent reality. Some models address criteria assigning coefficients to the objective function by weighting on it. Clearly, there was a need for alternative algorithms that would, besides promoting synergies on routes, also treat multi-criteria problems close to reality. Therefore, searching for a valid contribution in the field, an adaption of an optimizing algorithm based on Sandholm (2002)s was made. The algorithm applies combinatorial auction, supported by decision analysis for measuring relevant buyers criteria. First, the main algorithms objective is to minimize buyers costs by combining routes and suppliers; then, a modified approach considers multi criteria. Results were then compared to the commercial software CPLEX.

This thesis concerns the interdisciplinary field of combinatorial auctions, combining the fields of computer science, optimization and economics. A combinatorial auction is an auction where many items are sold simultaneously and where bidders may submit indivisible combinatorial bids on groups of items. It is commonly believed that good solutions to the allocation problem can be achieved by allowing combinatorial bidding. Determining who wins in a combinatorial auction is fundamentally different from a traditional single-item auction because we are faced with a hard and potentially intractable optimization problem. Also, unless we are limited to truthful mechanisms, game theoretic analysis of the strategic behavior of bidders is still an open problem. We have chosen primarily to study the first-price combinatorial auction, a natural auction widely used in practice. Theoretical analysis of this type of auction is difficult and little has been done previously. In this thesis we investigate and discuss three fundamental questions with significant practical implications for combinatorial auctions. First, because the number of possible bids grows exponentially with the number of items, limitations on the number of bids are typically required. This gives rise to a problem since bidders are unlikely to choose the "correct" bids that make up the globally optimal solution. We provide evidence that an expressive and compact bidding language can be more important than finding the optimal solution. Second, given a first-price (sealed-bid) combinatorial auction, the question of equilibrium bidding strategies remains an open problem. We propose a heuristic for finding such strategies and also present feasible strategies. And finally, is a first-price combinatorial auction worth pursuing compared to the simpler simultaneous (single-item) auction? We prove, through a model capturing many fundamental properties of multiple items scenarios with synergies, that the first-price combinatorial auction produces higher revenue than simultaneous single-item auctions. We provide bounds on revenue, given a significantly more general model, in contrast to previous work.

A seleção de fornecedores de transporte é um desafio cada vez maior. O crescimento da rede de clientes a ser coberta demanda uma alocação eficiente em termos de custo não suprida por mecanismos tradicionais de negociação. Neste âmbito, o leilão combinatório torna-se uma alternativa de negociação ao permitir capturar sinergias entre os trajetos que devem ser atendidos. Em conseqüência disso, diminui-se o custo de transporte do fornecedor que se reflete nos menores preços de suas propostas e finalmente no custo total de compra do serviço. Por outro lado, esta decisão envolve fatores além do custo total; a mensuração destes torna-se importante para identificar fornecedores que melhor se ajustam aos requerimentos do comprador. No entanto, é fundamental escolher um método adequado para sua avaliação porque este influência a decisão final. Este problema de compra de serviços de transporte é conhecido na literatura como Winner Determination Problem (WDP) que, devido a sua complexidade, possui uma resolução limitada. Após revisão teórica, foi observado que os estudos relacionados à área de transporte focalizavam o desenvolvimento de modelos matemáticos que fossem representativos da realidade. Alguns destes modelos abordam a utilização de múltiplos critérios atribuindo um coeficiente que pondera cada critério. Evidenciou-se a necessidade do desenvolvimento de um algoritmo alternativo que além de facilitar sinergias entre trajetos, fosse abrangente o suficiente para tratar múltiplos critérios em instâncias compatíveis com problemas reais. Logo, com o intuito de contribuir com a literatura foi adaptado um algoritmo matemático otimizante ao problema de compras de fornecedores de transporte com base no algoritmo de Sandholm (2002). Este algoritmo aplica leilão combinatório de compras, apoiando-se na teoria da análise de decisão para mensurar critérios relevantes do comprador. Inicialmente, o algoritmo minimiza o custo total do comprador designando combinações de trajetos e fornecedores; depois é modificado para o tratamento multi-critério. Os resultados obtidos foram comparados com o software comercial CPLEX. / Selecting suppliers is a crescent challenge for the enterprises. The extent of the client web that needs to be served demands efficient allocations, in terms of cost, that are not addressed by traditional mechanisms. In this scenario, another mechanism came to be: the combinatorial auction. In this one, suppliers can express their synergies on routes they wish to supply. This leads to lowering their transportation costs, which is reflected in lower bidding prices as well as in the total cost of service. On the other hand, the selection of a supplier involves other criteria besides cost. The definition of these is essential to define which supplier fits the needs of the buyer. That is why it is of most importance to choose the right method to evaluate these needs, as it defines the final choice. This problem is known as Winner Determination Problem (WDP) and due to its complexity, possesses a feeble solution. After compiling what has been done about the subject, it was noticed that in the field of transport, studies are focused on mathematical models that represent reality. Some models address criteria assigning coefficients to the objective function by weighting on it. Clearly, there was a need for alternative algorithms that would, besides promoting synergies on routes, also treat multi-criteria problems close to reality. Therefore, searching for a valid contribution in the field, an adaption of an optimizing algorithm based on Sandholm (2002)s was made. The algorithm applies combinatorial auction, supported by decision analysis for measuring relevant buyers criteria. First, the main algorithms objective is to minimize buyers costs by combining routes and suppliers; then, a modified approach considers multi criteria. Results were then compared to the commercial software CPLEX.

À cause des stratégies de production et de marketing de plus en plus ambitieuses tellesque le Juste-À-Temps et la production adaptée au client, les approches de collaboration logistique verticale qui sont courantes atteignent une limite d'efficacité notamment en transport. La collaboration logistique horizontale (CLH) et plus particulièrement la mutualisation, dont l'efficacité a été prouvée dans la littérature et dans les cas réels, a attiré l'attention des chercheurs ainsi que des praticiens. Cependatn, un des obstacles principaux à la mise en œuvre des CLHs est l'absence d'un mécanisme de collaboration raisonné, en particulier un mécanisme de partage des gains. Nous identifions deux formes d'organisation des CLHs : centralisée limité en pratique à de petites coalitions et décentralisée pouvant comprendre de nombreux participants. Pour des CLHs centralisées, nous proposons un modèle de collaboration qui est un processus de conduite qui intègre les outils d'aide à la décision. Nous développons également un mécanisme de partage par la théorie des jeux. Ce mécanisme est applicable aux différentes catégories des CLHs centralisées, qui peuvent être modélisées par des jeux coopératifs super-additif et non-super-additifs. Afin de proposer un plan de partage crédible aux collaborateurs, ce mécanisme de partage prend en compte la contribution de chacun des collaborateurs, la stabilité de la coalition et leur pouvoir de négociation. Ce cadre est illustré par des exemples numériques issus de cas logistiques. Pour la mise en œuvre des CLHs décentralisées, nous proposons un cadre de travail de logistique collaborative qui est ouvert aux participants potentiels, et avons conçu des protocoles fondés sur le mécanisme d'enchère combinatoire, qui spécifient l'allocation de demande de livraison et la détermination de paiement pour faciliter les collaborations. Cette dernière partie s'appuie sur la théorie dite de Mechanism design. / As the result of the more and more ambitious production and marketing strategies,such as Just-In-Time and increasing customization of products, the current vertical logistics collaboration approaches based on single supply chain seems insufficient to achieve further improvements in transportation efficiency. The horizontal logistics collaboration (HLC), which has been proved an effective approach to efficiency improvement, has attracted both academics and practitioners. One of the main barriers to the implementation of HLCs is the lack of feasible collaboration mechanism, in particular the gain sharing mechanism. We identify two organizational forms of HLCs: the centralized and decentralized ones. For centralized HLCs, we propose a collaboration model that is a collaboration conducting process integrating decision-aiding tools to guide the implementation of the collaboration. We also develop a generally applicable game-theoretic sharing mechanism for different categories of centralized HLCs modeled as super-additive and non-super-additive cooperative games. This sharing mechanism takes into account the collaborators' contribution, the coalition stability, and the bargaining power to propose a credible sharing scheme for collaborators. The approach is illustrated by numerical example taken from logistics cases. For the implementation of the decentralized HLCs, we propose an open collaborative logistics framework, and design the system protocols as the collaboration mechanism that specifies the combinatorial-auction-based request allocation and payment determination to foster the collaborations.