This thesis includes three self-contained projects: In the first project Bidding strategies and their impact on the auctioneer's revenue in combinatorial auctions, focusing on combinatorial auctions, we propose a simple and efficient model for evaluating the value of any bundle given limited information, design bidding strategies that efficiently select desirable bundles, and evaluate the performance of different bundling strategies under various market settings. In the second project Retailer shelf-space management with promotion effects, promotional investment effects are integrated with retail store assortment decisions and shelf space allocation. An optimization model for the category shelf-space allocation incorporating promotion effects is presented. Based on the proposed model, a category shelf space allocation framework with trade allowances is presented where a multi-player Retailer Stackelberg game is introduced to model the interactions between retailer and manufacturers. In the third project Supply-chain oriented robust parameter design, we introduce the game theoretical method, commonly used in supply-chain analysis to solve potential conflicts between manufacturers at various stages. These manufacturing chain partners collaboratively decide parameter design settings of the controllable factors to make the product less sensitive to process variations.

How should we divide a good or set of goods among a set of agents? There are various constraints that we can consider. We consider two particular constraints. The first is fairness - how can we find fair allocations? The second is truthfulness - what if we do not know agents valuations for the goods being allocated? What if these valuations need to be elicited, and agents will misreport their valuations if it is beneficial? Can we design procedures that elicit agents' true valuations while preserving the quality of the allocation? We consider truthful and fair resource allocation procedures through a computational lens. We first study fair division of a heterogeneous, divisible good, colloquially known as the cake cutting problem. We depart from the existing literature and assume that agents have restricted valuations that can be succinctly communicated. We consider the problems of welfare-maximization, expressiveness, and truthfulness in cake cutting under this model. In the second part of this dissertation we consider truthfulness in settings where payments can be used to incentivize agents to truthfully reveal their private information. A mechanism asks agents to report their private preference information and computes an allocation and payments based on these reports. The mechanism design problem is to find incentive compatible mechanisms which incentivize agents to truthfully reveal their private information and simultaneously compute allocations with desirable properties. The traditional approach to mechanism design specifies mechanisms by hand and proves that certain desirable properties are satisfied. This limits the design space to mechanisms that can be written down and analyzed. We take a computational approach, giving computational procedures that produce mechanisms with desirable properties. Our first contribution designs a procedure that modifies heuristic branch and bound search and makes it usable as the allocation algorithm in an incentive compatible mechanism. Our second contribution draws a novel connection between incentive compatible mechanisms and machine learning. We use this connection to learn payment rules to pair with provided allocation rules. Our payment rules are not exactly incentive compatibility, but they minimize a measure of how much agents can gain by misreporting. / Engineering and Applied Sciences

Charles University in Prague Faculty of Social Sciences Institute of Economic Studies MASTER THESIS An Experimental Test of Design Alternatives for Spectrum Auctions with Communication Channels Author: Bc. Jindřich Matoušek Supervisor: PhDr. Lubomír Cingl Academic Year: 2013/2014 Abstract The multi-unit auction mechanisms are one of the most important instruments used for the allocation of spectrum licenses, airport time slots, delivery routes, networking or furniture allocation. This thesis experimentally examines the attributes of complex multi-unit auction mechanisms (Simultaneous Multi-Round Auction and its combinatorial extension Simultaneous Multi-Round Package Bidding) in the presence of an opportunity to collude among the bidding participants due to a provision of a simple communication channel - a chat window. The results suggest that in our parameter setting, the combinatorial bidding format does not bring higher efficiency. Interestingly, allowing for communication increases efficiency in both examined auction formats. Bidders are able to split the auctioned goods in a collusive agreement, which results in a better allocation compared to the auction formats without the communication channel. Combinatorial bidding on packages probably makes the decision-making problem of bidders hard to process...

The interaction of theoretical computer science with game theory and economics has resulted in the emergence of two very interesting research directions. First, it has provided a new model for algorithm design, which is to optimize in the presence of strategic behavior. Second, it has prompted us to consider the computational aspects of various solution concepts from game theory, economics and auction design which have traditionally been considered mainly in a non-constructive manner. In this thesis we present progress along both these directions. We first consider optimization problems that arise in the design of combinatorial auctions. We provide an online algorithm in the important case of budget-bounded utilities. This model is motivated by the recent development of the business of online auctions of search engine advertisements. Our algorithm achieves a factor of $1-1/e$, via a new linear programming based technique to determine optimal tradeoffs between bids and budgets. We also provide lower bounds in terms of hardness of approximation in more general submodular settings, via a PCP-based reduction. Second, we consider truth-revelation in auctions, and provide an equivalence theorem between two notions of strategy-proofness in randomized auctions of digital goods. Last, we consider the problem of computing an approximate Nash equilibrium in multi-player general-sum games, for which we provide the first subexponential time algorithm.

By the emergence of electronic commerce and low transaction costs on the Internet, an interest in the design of new auction mechanisms has been arisen. Recently many researchers in computer science, economics, business, and game theory have presented many valuable studies on the subject of online auctions, and auctions theory. When faced from a computational perspective, combinatorial auctions are perhaps the most challenging ones. Combinatorial auctions, that is, auctions where bidders can bid on combinations of items, tend to lead to more efficient allocations than traditional auction mechanisms in multi-item multi-unit situations where the agents&rsquo / valuations of the items are not additive. However, determining the winners to maximize the revenue is NP-complete. In this study, we first analyze the existing approaches for combinatorial auction problem. Based on this analysis, we then choose three different approaches, which are search approach, descending simultaneous auctions approach, and IP (Integer Programming) formulation approach to build our models. The performances of the models are compared using computer simulations, where we model bandwidth allocation system. Finally a combinatorial auction tool is built which can be used for online auctions and e-procurement systems.

The focus of this thesis is resource management in large-scale systems. Our primary concerns are energy management and practical principles for self-organization and self-management. The main contributions of our work are: 1. Models. We proposed several models for different aspects of resource management, e.g., energy-aware load balancing and application scaling for the cloud ecosystem, hierarchical architecture model for self-organizing and self-manageable systems and a new cloud delivery model based on auction-driven self-organization approach. 2. Algorithms. We also proposed several different algorithms for the models described above. Algorithms such as coalition formation, combinatorial auctions and clustering algorithm for scale-free organizations of scale-free networks. 3. Evaluation. Eventually we conducted different evaluations for the proposed models and algorithms in order to verify them. All the simulations reported in this thesis had been carried out on different instances and services of Amazon Web Services (AWS). All of these modules will be discussed in detail in the following chapters respectively.