published_or_final_version / Mechanical Engineering / Master / Master of Philosophy

No description available.

No description available.

No description available.

The field of algorithmic mechanism design is concerned with the design of computationally efficient algorithms for use when inputs are provided by rational agents, who may misreport their private values in order to strategically manipulate the algorithm for their own benefit. We revisit classic problems in this field by considering settings of incomplete information, where the players' private values are drawn from publicly-known distributions. Such Bayesian models of partial information are common in economics, but have been largely unexplored by the computer science community. In the first part of this thesis we show that, for a very broad class of single-parameter problems, any computationally efficient algorithm can be converted without loss into a mechanism that is truthful in the Bayesian sense of partial information. That is, we exhibit a transformation that generates mechanisms for which it is in each agent's best (expected) interest to refrain from strategic manipulation. The problem of constructing mechanisms for use by rational agents therefore reduces to the design of approximation algorithms without consideration of game-theoretic issues. We furthermore prove that no such general transformation is possible if we require mechanisms that are truthful in the stronger non-Bayesian sense of dominant strategies. In the second part of the thesis we study simple greedy methods for resolving complex auctions. We show that while such greedy algorithms are not truthful, they suffer very little loss in worst-case performance bounds when agents apply strategies at equilibrium, even in settings of partial information. Our analysis applies to various different equilibrium concepts, including Bayes-Nash equilibrium, regret-minimizing strategies, and asynchronous best-response dynamics. Thus, even though greedy auctions are not truthful, they may be appropriate for use as mechanisms under the goal of achieving high social efficiency at equilibrium. Moreover, we prove that no algorithm in a broad class of greedy-like methods can be used to create a deterministic truthful mechanism while retaining a non-trivial approximation to the optimal social welfare. Our overall conclusion is that while full-information models of agent rationality currently dominate the algorithmic mechanism design literature, a relaxation to settings of partial information is well-motivated and provides additional power in solving central problems in the field.

The field of algorithmic mechanism design is concerned with the design of computationally efficient algorithms for use when inputs are provided by rational agents, who may misreport their private values in order to strategically manipulate the algorithm for their own benefit. We revisit classic problems in this field by considering settings of incomplete information, where the players' private values are drawn from publicly-known distributions. Such Bayesian models of partial information are common in economics, but have been largely unexplored by the computer science community. In the first part of this thesis we show that, for a very broad class of single-parameter problems, any computationally efficient algorithm can be converted without loss into a mechanism that is truthful in the Bayesian sense of partial information. That is, we exhibit a transformation that generates mechanisms for which it is in each agent's best (expected) interest to refrain from strategic manipulation. The problem of constructing mechanisms for use by rational agents therefore reduces to the design of approximation algorithms without consideration of game-theoretic issues. We furthermore prove that no such general transformation is possible if we require mechanisms that are truthful in the stronger non-Bayesian sense of dominant strategies. In the second part of the thesis we study simple greedy methods for resolving complex auctions. We show that while such greedy algorithms are not truthful, they suffer very little loss in worst-case performance bounds when agents apply strategies at equilibrium, even in settings of partial information. Our analysis applies to various different equilibrium concepts, including Bayes-Nash equilibrium, regret-minimizing strategies, and asynchronous best-response dynamics. Thus, even though greedy auctions are not truthful, they may be appropriate for use as mechanisms under the goal of achieving high social efficiency at equilibrium. Moreover, we prove that no algorithm in a broad class of greedy-like methods can be used to create a deterministic truthful mechanism while retaining a non-trivial approximation to the optimal social welfare. Our overall conclusion is that while full-information models of agent rationality currently dominate the algorithmic mechanism design literature, a relaxation to settings of partial information is well-motivated and provides additional power in solving central problems in the field.

Efforts towards a low carbon economy are challenging the electricity industry. On the supply-side, centralised carbon-intensive power plants are set to gradually decrease their contribution to the generation mix, whilst distributed renewable generation is to successively increase its share. On the demand-side, electricity use is expected to increase in the future due to the electrification of heating and transport. Moreover, the demand-side is to become more active allowing end-users to invest in generation and storage technologies, such as solar photovoltaics (PV) and home batteries. As a result, some network reinforcements might be needed and instrumentation at the users’ end is to be required, such as controllers and home energy management systems (HEMS). The electricity grid must balance supply and demand at all times in order to maintain technical constraints of frequency, voltage, and current; and this will become more challenging as a result of this transition. Failure to meet these constraints compromises the service and could damage the power grid assets and end-users’ appliances. Balancing generation, although responsive, is carbon-intensive and associated with inefficient asset utilisation, as these generators are mostly used during peak hours and sit idle the rest of the time. Furthermore, energy storage is a potential solution to assist the balancing problem in the presence of non-dispatchable low-carbon generators; however, it is substantially expensive to store energy in large amounts. Therefore, demand response (DR) has been envisioned as a complementary solution to increase the system’s resilience to weather-dependent, stochastic, and intermittent generation along with variable and temperature-correlated electric load. In the domestic setting, operational flexibility of some appliances, such as heaters and electric cars, can be coordinated amongst several households so as to help balance supply and demand, and reduce the need of balancing generators. Against this background, the electricity supply system requires new organisational paradigms that integrate DR effectively. Although some dynamic pricing schemes have been proposed to guide DR, such as time of use (ToU) and real-time pricing (RTP), it is still unclear how to control oscillatory massive responses (e.g., large fleet of electric cars simultaneously responding to a favourable price). Hence, this thesis proposes an alternative approach in which households proactively submit DR offers that express their preferences to their respective retailer in exchange for a discount. This research develops a computational model of domestic electricity use, and simulates appliances with operational flexibility in order to evaluate the effects and benefits of DR for both retailers and households. It provides a representation for this flexibility so that it can be integrated into specific DR offers. Retailers and households are modelled as computational agents. Furthermore, two market-based mechanisms are proposed to determine the allocation of DR offers. More specifically, a one-sided Vickrey-Clarke-Groves (VCG)-based mechanism and penalty schemes were designed for electricity retailers to coordinate their customers’ DR efforts so as to ameliorate the imbalance of their trading schedules. Similarly, a two-sided McAfee-based mechanism was designed to integrate DR offers into a multi-retailer setting in order to reduce zonal imbalances. A suitable method was developed to construct DR block offers that could be traded amongst retailers. Both mechanisms are dominant-strategy incentive-compatible and trade off a small amount of economic efficiency in order to maintain individual rationality, truthful reporting, weak budget balance and tractable computation. Moreover, privacy preserving is achieved by including computational agents from the independent system operator (ISO) as intermediaries between each retailer and its domestic customers, and amongst retailers. The theoretical properties of these mechanisms were proved using worst-case analysis, and their economic effects were evaluated in simulations based on data from a survey of UK household electricity use. In addition, forecasting methods were assessed on the end-users’ side in order to make better DR offers and avoid penalties. The results show that, under reasonable assumptions, the proposed coordination mechanisms achieve significant savings for both end-users and retailers, as they reduce the required amount of expensive balancing generation.

O principal objetivo desta dissertação é obter um Teorema do Envelope que permita mecanismos não diferenciáveis, preferências arbitrárias e que possa ser aplicado em modelos com múltiplos agentes. Nós alcançamos isto ao expandir a análise de Milgrom e Segal (2002), generalizando seus resultados para espaços de tipos multidimensionais. Dessa forma, continuamos permitindo que a regra de escolha (mecanismo) seja descontínua. Para obter nosso resultado, é necessário o uso do Teorema do Máximo de Berge e, consequentemente, devemos impor compacidade no conjunto de escolha. Inicialmente esta hipótese pode parecer forte, porém argumentamos que em aplicações _e muito improvável termos um conjunto de escolha aberto ou, principalmente, não limitado. Nós também identificamos condições para que a função valor seja absolutamente contínua e mostramos que sua representação integral também é válida para espaços de tipos multidimensionais. Inicialmente propomos uma generalização direta do resultado de Milgrom e Segal (2002), utilizando a hipótese de continuidade absoluta da função de utilidade do agente. Entretanto, esta exigência não possui muito significado econômico e é considerada pouco elegante por parte da literatura. Neste sentido, incorporamos uma hipótese adicional de diferenciabilidade da utilidade em todo o domínio que gera a mesma representação integral e possui uma maior interpretação econômica. Nossos resultados são, em geral, aplicados a modelos com múltiplos agentes, em especial Economia do Setor Público (provisão de bens públicos e taxação ótima) e teoria dos leilões. / The main objective of this dissertation is to obtain an Envelope Theorem that allows non-di erentiable mechanisms, arbitrary preferences, and that can be applied to models with multiple agents. We achieve that by expanding the analysis of Milgrom and Segal (2002) and generalizing their results to multidimensional type spaces. Thus, we continue allowing that the choice rule (mechanism) is discontinuous. For our result, it is necessary to use the Berge's Maximum Theorem and therefore we must impose compactness in the choice set. Initially this assumption may seem strong, but we argue that in applications there is an open or unbounded choice set is very unlikely. We also identify conditions for the value function is absolutely continuous and show that its integral representation is also valid for multidimensional type spaces. Firstly we propose a direct generalization of the Milgrom and Segal (2002)'s result, using the assumption of absolute continuity of the agent's utility function. However, this requirement does not have much economic interpretation and it is considered not very elegant in the literature. In this sense, we incorporate an additional assumption of di erentiability of the utility in all range that generates the same integral representation and it possesses a greater economic interpretation. Our results are generally applied to models with multiple agents, in particular Public Economics (public goods supply and optimal taxation) and auction theory.

O principal objetivo desta dissertação é obter um Teorema do Envelope que permita mecanismos não diferenciáveis, preferências arbitrárias e que possa ser aplicado em modelos com múltiplos agentes. Nós alcançamos isto ao expandir a análise de Milgrom e Segal (2002), generalizando seus resultados para espaços de tipos multidimensionais. Dessa forma, continuamos permitindo que a regra de escolha (mecanismo) seja descontínua. Para obter nosso resultado, é necessário o uso do Teorema do Máximo de Berge e, consequentemente, devemos impor compacidade no conjunto de escolha. Inicialmente esta hipótese pode parecer forte, porém argumentamos que em aplicações _e muito improvável termos um conjunto de escolha aberto ou, principalmente, não limitado. Nós também identificamos condições para que a função valor seja absolutamente contínua e mostramos que sua representação integral também é válida para espaços de tipos multidimensionais. Inicialmente propomos uma generalização direta do resultado de Milgrom e Segal (2002), utilizando a hipótese de continuidade absoluta da função de utilidade do agente. Entretanto, esta exigência não possui muito significado econômico e é considerada pouco elegante por parte da literatura. Neste sentido, incorporamos uma hipótese adicional de diferenciabilidade da utilidade em todo o domínio que gera a mesma representação integral e possui uma maior interpretação econômica. Nossos resultados são, em geral, aplicados a modelos com múltiplos agentes, em especial Economia do Setor Público (provisão de bens públicos e taxação ótima) e teoria dos leilões. / The main objective of this dissertation is to obtain an Envelope Theorem that allows non-di erentiable mechanisms, arbitrary preferences, and that can be applied to models with multiple agents. We achieve that by expanding the analysis of Milgrom and Segal (2002) and generalizing their results to multidimensional type spaces. Thus, we continue allowing that the choice rule (mechanism) is discontinuous. For our result, it is necessary to use the Berge's Maximum Theorem and therefore we must impose compactness in the choice set. Initially this assumption may seem strong, but we argue that in applications there is an open or unbounded choice set is very unlikely. We also identify conditions for the value function is absolutely continuous and show that its integral representation is also valid for multidimensional type spaces. Firstly we propose a direct generalization of the Milgrom and Segal (2002)'s result, using the assumption of absolute continuity of the agent's utility function. However, this requirement does not have much economic interpretation and it is considered not very elegant in the literature. In this sense, we incorporate an additional assumption of di erentiability of the utility in all range that generates the same integral representation and it possesses a greater economic interpretation. Our results are generally applied to models with multiple agents, in particular Public Economics (public goods supply and optimal taxation) and auction theory.

abstract: Data privacy is emerging as one of the most serious concerns of big data analytics, particularly with the growing use of personal data and the ever-improving capability of data analysis. This dissertation first investigates the relation between different privacy notions, and then puts the main focus on developing economic foundations for a market model of trading private data. The first part characterizes differential privacy, identifiability and mutual-information privacy by their privacy--distortion functions, which is the optimal achievable privacy level as a function of the maximum allowable distortion. The results show that these notions are fundamentally related and exhibit certain consistency: (1) The gap between the privacy--distortion functions of identifiability and differential privacy is upper bounded by a constant determined by the prior. (2) Identifiability and mutual-information privacy share the same optimal mechanism. (3) The mutual-information optimal mechanism satisfies differential privacy with a level at most a constant away from the optimal level. The second part studies a market model of trading private data, where a data collector purchases private data from strategic data subjects (individuals) through an incentive mechanism. The value of epsilon units of privacy is measured by the minimum payment such that an individual's equilibrium strategy is to report data in an epsilon-differentially private manner. For the setting with binary private data that represents individuals' knowledge about a common underlying state, asymptotically tight lower and upper bounds on the value of privacy are established as the number of individuals becomes large, and the payment--accuracy tradeoff for learning the state is obtained. The lower bound assures the impossibility of using lower payment to buy epsilon units of privacy, and the upper bound is given by a designed reward mechanism. When the individuals' valuations of privacy are unknown to the data collector, mechanisms with possible negative payments (aiming to penalize individuals with "unacceptably" high privacy valuations) are designed to fulfill the accuracy goal and drive the total payment to zero. For the setting with binary private data following a general joint probability distribution with some symmetry, asymptotically optimal mechanisms are designed in the high data quality regime. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2016