In this dissertation auction formats are developed and discussed that focus on three specific economic environments. Regarding the impossibility results from mechanism design, the main task for the implementation of auction designs is to balance allocative efficiency and incentive compatibility – the main characteristics a mechanism should provide. Therefore, the dissertation investigates the limits of conceivable relaxations of allocative efficiency and incentive compatibility for complex settings such as double auctions, interdependent-valuation environments and electricity market designs. The overall aim is to carefully weigh up the advantages and disadvantages for either relaxing allocative efficiency or respectively incentive compatibility.:Preface … 7 1. Introduction … 8 1.1. Applications of auction design … 8 1.2. Optimal use of information in allocation processes … 12 1.3. Modeling non-cooperative situations … 14 1.4. Motivation for the dissertation … 16 2. An Incentive Compatible Double Auction for Multi-Unit Markets with Heterogeneous Goods … 21 2.1. Introduction into double auctions … 21 2.2. Setting of a multi-unit market with heterogeneous goods … 25 2.3. Concept of the Incentive Compatible Double Auction (ICDA) … 29 2.4. Definition of the allocation rule … 31 2.5. Creation of the price vector and the trading bundles … 37 2.6. Characteristics of the Incentive Compatible Double Auction (ICDA) … 40 2.7. Discussion of the properties of the Incentive Compatible Double Auction (ICDA) … 43 3. An Alternating-Price Auction for Interdependent-Valuation Environments … 46 3.1. Introduction into ex-post efficient auction design … 46 3.2. Setting of an interdependent-valuation environment … 50 3.3. Concept of the Alternating-Price Auction (APA) … 54 3.4. Characteristics of the Alternating-Price Auction (APA) 62 3.5. Discussion of the properties of the Alternating-Price Auction (APA) … 64 4. Facilitating Short-Term and Long-Term Efficiency with an Integrated Electricity Market Design … 66 4.1. Introduction into electricity market designs … 66 4.2. Setting of an electricity market … 72 4.3. Concept of the Integrated Electricity Market Design (IEMD) … 78 4.4. Characteristics of the Integrated Electricity Market Design (IEMD) … 88 4.5. Discussion of the properties of the Integrated Electricity Market Design (IEMD) … 91 5. Conclusion ... 94 Reference List … 96

Game balance has been a challenge for game developers since the time games have become more complex. There have been a handful of proposals for game balancing processes outside the manual labor-intensive play testing methods, which most game developers often are forced to use simply due to the lack of better methods. Simple solutions, like restrictive game play, are limited because of their inability to provide insight on interdependencies among the mechanisms in the game. Complex techniques framed around the potential of AI algorithms are limited by computational budgets or cognition inability to assess human actions. In order to find a middle ground we investigate Game Theory and Mechanism Design concepts. Both have proven to be effective tools to analyse strategic situations among interacting participants, or in this case `players'. We test the feasibility of using these techniques in an Real Time Strategy (RTS) game domain to understand game balance. MicroRTS, a small and simple execution of an RTS game is employed as our model. The results provide promising insight on the effectiveness of the method in detecting imbalances and further inspection to find the cause. An additional benefit out of this technique, besides detecting for game imbalances, the approach can be leveraged to create imbalances. This is useful when the designer or player desires to do so.

Inspired by the digital revolution to the financial industry, the discussion around central bank digital currency also attract attention from academics and central banks. The People’s Bank of China (PBOC) is also researching on China’s CBDC: digital currency electronic payment (DCEP) and announced that DCEP would be issued as soon as possible.  However, the PBOC does not systematically disclose the information of DCEP. The characteristics and mechanism design are still obscured and need to be explored deeply. This thesis analysed the classification and mechanism design choices of DCEP from the perspective of two different demands: general demand and central bank demand. Based on pragmatism philosophy, we use a mixed-methods approach that is a combination of qualitative and quantitative research. Through the interview and surveys, we identified the demands from the PBOC and the general public in China and the characteristics of DCEP from official claims. Then generate the design choices via the money flower and the pyramid of CBDC models and compare the result with the demand. The analysis shows that the DCEP belongs to type B general-purpose CB digital tokens, and it would adopt a complex multi-layer hybrid architecture design, with the support from both DLT and conventional way. In conclusion, the current mechanism design choices can meet the demands from each side to a certain extent and reached a delicate balance under the trade-off between privacy and security issues. This thesis provides an insightful view on the classification and design choices of DCEP, fulfils the lack of systematic research relating to the demand and design choices of DCEP, and reveals the public’s insufficient knowledge in DCEP.

付記する学位プログラム名: デザイン学大学院連携プログラム / 京都大学 / 0048 / 新制・課程博士 / 博士(工学) / 甲第21759号 / 工博第4576号 / 新制||工||1713(附属図書館) / 京都大学大学院工学研究科機械理工学専攻 / (主査)教授 松野 文俊, 教授 椹木 哲夫, 教授 小森 雅晴 / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DFAM

No description available.

In order to implement privacy preservation for individuals, systems need to utilize privacy mechanisms that privatize sensitive data by randomization. The goal of privacy mechanism design is to find optimal tradeoffs between maximizing the utility of the privatized data while providing a strict sense of privacy defined by a chosen privacy measure. In this thesis, we explore this tradeoff for the pointwise maximal leakage measure. Pointwise maximal leakage (PML) was recently proposed as an operationally meaningful privacy measure that quantifies the guessing advantage of an adversary that is interested in a random function of the private data. Opposite to many other information-theoretic measures, PML considers the privacy loss for every outcome of the privatized view separately, thereby enabling more flexible privacy guarantees that move away from averaging over all outcomes. We start by using PML to analyze the prior distribution-dependent behavior of the established randomized response mechanism designed for local differential privacy. Then, we formulate a general optimization problem for the privacy-utility tradeoff with PML as a privacy measure and utility functions based on sub-linear functions. Using methods from convex optimization, we analyze the valid region of mechanisms satisfying a PML privacy guarantee and show that the optimization can be solved by a linear program. We arrive at extremal formulations that yield closed-form solutions for some important special cases: Binary mechanism, general high-privacy regions, i.e., regions in which the required level of privacy is high, and low-privacy mechanisms for equal priors. We further present an approximate solution for general priors in this setting. Finally, we analyze the loss of optimality of this construction for different prior distributions. / För att kunna implementera integritetsskydd för individer, så behöver system utnyttja integritetsmekanismer som privatiserar känslig data genom randomisering. Målet vid design av integritetsmekanismer är att hitta den optimala balansen mellan att användbarheten av privatiserad data maximeras, samtidigt som det tillhandahålls integritet i strikt mening. Detta definierat av något valt typ av integritetsmått. I den här avhandlingen, så undersöks detta utbyte specifikt med “pointwise maximal leakage”-måttet. Pointwise maximal leakage (PML) har nyligen föreslagits som ett operativt meningsfullt integritetsmått som kvantifierar en gissande motparts informationstillgång om denna är intresserad av en slumpmässig funktion av den privata datan. Till skillnad mot många andra informations-teoretiska mått, så tar PML i åtanke integritetsinskränkningen separat för varje utfall av den privata slumpmässiga variabeln. Därmed möjliggörs mer flexibla försäkringar av integriteten, som strävar bort från genomsnittet av alla utfall. Först, används PML för att analysera det ursprungsberoende beteendet av den etablerade “randomized response”-mekanismen designad för local differential privacy. Därefter formuleras ett generellt optimeringsproblem för integritets-användbarhets-kompromissen med PML som ett integritetsmått och användbarhetsfunktioner baserade på sublinjära funktioner. Genom att utnyttja metoder från konvex optimering, analyseras den giltiga regionen av mekanismer som tillfredsställer en PML-integritetsgaranti och det visas att optimeringen kan lösas av ett linjärt program. Det leder till extremala formuleringar som ger slutna lösningar för några viktiga specialfall: Binär mekanism, allmänna högintegritets-regioner (d.v.s. regioner där kravet på nivån av integritet är hög) och lågintegritets-mekanismer för ekvivalenta ursprungliga distributioner. Vidare presenteras en approximativ lösning för allmänna ursprungliga distributioner i denna miljö. Slutligen, analyseras förlusten av optimalitet hos denna konstruktion för olika ursprungliga distributioner.

<p dir="ltr">Distributed cryptographic protocols typically assume a bounded number of malicious parties (who behave arbitrarily) in the system---and in turn, a lower bound on the number of <i>honest</i> parties (who follow and only follow a protocol faithfully/honestly without performing unspecified computations)---for their respective security guarantees to hold. However, when deploying these protocols in practice, the nature of computing parties does not necessarily align nicely with the protocols' assumptions. Specifically, there may be only a few honest/compliant parties, or none exists. Instead, non-malicious parties may be <i>semi-honest</i> (who follow the protocol specifications but are curious to learn as much information as possible from semi-honest parties' transcripts) or <i>rational</i> (who take actions that maximize their utilities instead of actions benefiting the protocol the most, e.g., performing extra computations or not following protocols). In such cases, the security guarantees of such protocols may deviate greatly in real life from what is theoretically promised, leaving a huge gap between theory and practice. </p><p dir="ltr">In this thesis, I bridge such a gap by enhancing the fault tolerance of various distributed cryptographic primitives by <i>relaxing the assumption on the existence of honest parties</i>.</p><p dir="ltr">First, in the context of <b>secure multi-party computations</b>, without honest parties, my goal is to induce honest (i.e., not compromising correctness) and non-curious (i.e., not harming privacy) behaviors from rational participants via game theoretic and cryptographic techniques. In particular, I first demonstrate how to ensure protocol correctness and deter collusion among parties to recover secrets---which also breaks privacy---in multiserver private information retrieval with a singleton access structure. Then for primitives with more general (non-singleton) access structures, I introduce a distinct treatment through the lens of verifiable secret sharing. The two solutions are designed with a public bulletin board, commitment schemes, digital signature schemes, zkSNARKs (zero-knowledge succinct non-interactive arguments of knowledge), and distinct incentive structures tailored for varying access structures underlying the schemes.</p><p dir="ltr">Second, in <b>permissionless blockchain systems</b>, for protocols without privacy guarantees like computation outsourcing and consensus, my goal is to incentivize rational parties to behave correctly. This means to act according to the protocol specifications or as implied by the security requirements of the primitive, e.g., fairly distribute rewards to participants based on contributions in proof-of-work (PoW) blockchains. Specifically, I present a defense against an undercutting attack in PoW blockchains from a game theory perspective and propose a decentralized computation outsourcing protocol built on permissionless blockchain systems based on multi-unit auctions.</p>

Deploying robots in real-world environments involves immense engineering complexity, potentially surpassing the resources required for autonomous vehicles due to the increased dimensionality and task variety. To maximize the chances of successful real-world deployment, finding a simple solution that minimizes engineering complexity at every level, from hardware to algorithm to operations, is crucial. In this dissertation, we consider a vision-based manipulation system that can be deployed in-the-wild when trained to imitate sufficient quantity and diversity of human demonstration data on the desired task. At deployment time, the robot is driven by a single diffusion-based visuomotor policy, with raw RGB images as input and robot end-effector pose as output. Compared to existing policy representations, Diffusion Policy handles multimodal action distributions gracefully, being scalable to high-dimensional action spaces and exhibiting impressive training stability. These properties allow a single software system to be used for multiple tasks, with data collected by multiple demonstrators, deployed to multiple robot embodiments, and without significant hyper-parameter tuning. We developed a Universal Manipulation Interface (UMI), a portable, low-cost, and information-rich data collection system to enable direct manipulation skill learning from in-the-wild human demonstrations. UMI provides an intuitive interface for non-expert users by using hand-held grippers with mounted GoPro cameras. Compared to existing robotic data collection systems, UMI enables robotic data collection without needing a robot, drastically reducing the engineering and operational complexity. Trained with UMI data, the resulting diffusion policies can be deployed across multiple robot platforms in unseen environments for novel objects and to complete dynamic, bimanual, precise, and long-horizon tasks. The Diffusion Policy and UMI combination provides a simple full-stack solution to many manipulation problems. The turn-around time of building a single-task manipulation system (such as object tossing and cloth folding) can be reduced from a few months to a few days.

Diese Dissertation besteht aus drei unabhängigen Kapiteln auf dem Gebiet der Mechanismus-Design-Theorie, mit einem besonderen Schwerpunkt auf ausschließbaren öffentlichen Gütern und dynamischem Mechanismus-Design. Die ersten beiden Kapitel befassen sich mit optimalen Preismechanismen für den Verkauf von ausschließbaren öffentlichen Gütern. Das erste Kapitel untersucht diese Thematik in einer sequenziellen Screening-Umgebung, während das zweite Kapitel den Einfluss von Netzwerk-Externalitäten auf optimale Preisfindungsstrategien für diese Güter analysiert. Das letzte Kapite untersucht die Auswirkungen von "Big Data" im dynamischen Mechanismusdesign und konzentriert sich dabei auf eine Ein-Käufer-Ein-Verkäufer Situation. Dieses Kapitel vergleicht die Auszahlungen der beteiligten Agenten in diesem Kontext und liefert Einblicke durch theoretische Analysen und die Nutzung von Simulationen. / This dissertation comprises three independent yet interconnected chapters in the field of mechanism design, with a specific focus on excludable public goods and dynamic mechanism design. The first two chapters study optimal pricing mechanisms for selling excludable public goods. Chapter 1 explores this issue in a sequential screening environment. Chapter 2 examines the impact of network effects on optimal pricing strategies for these goods. Chapter 3 studies the impact of "big data" in dynamic mechanism design, focusing on a one-buyer-one-seller setting. This chapter compares the payoffs of involved agents in this context, providing insights through theoretical analysis and the use of simulations.

Diese Arbeit enthält drei unabhängige Kapitel, jedes davon im Bereich der Dynamischen Vertragstheorie. Kapitel I zeigt, dass deterministische dynamische Prinzipal-Agenten-Verträge immer mindestens so ertragreich sind wie stochastische, falls die sogenannte Methode erster Ordnung des dynamischen Mechanismus-Designs erfüllt ist. Meine Ergebnisse legen dar, dass die in der Literatur übliche Einschränkung auf deterministische Verträge zulässig ist, so lange die Methode erster Ordnung gültig ist. Kapitel II basiert auf einer gemeinsamen Arbeit mit Ilia Krasikov und Rohit Lamba. Ein Großanbieter (Prinzipal) handelt mit einer kleinen Firma (Agent) einen wiederkehrenden Geschäftsvertrag aus, wobei sich der Agent als ungeduldiger erweist. Der optimale Vertrag wird durch zwei Schlüsseleigenschaften beschrieben: Neustart und Abbruch, die vielerlei Eigenschaften der angebotenen Verträge darlegen. Kapitel III basiert schließlich auf einer gemeinsamen Arbeit mit Rohit Lamba. Darin besitzt der Agent dynamische private Information, die einem Markovprozess folgt. Ein monopolistischer Prinzipal verkauft dem Agenten ein nicht-dauerhaftes Gut und er verpflichtet sich in jeder Periode an den ursprünglich ausgehandelten Vertrag. Die entstehenden Informationskosten verhindern erst-beste Verträge bei auftretender Persistenz im Typ des Agenten. Diese Arbeit stellt einen Weg bereit, wie man den optimalen deterministischen Vertrag in dynamischen Prinzipal-Agenten-Modellen erhält. Der gewöhnliche Weg mit lediglich lokal nach unten bindenden Anreizverträglichkeitsbedingungen misslingt bei hoher Persistenz der Typrealisierungen und bei stark differenzierender Diskontierung. Zudem zeigt die Arbeit wann mit Gewissheit stochastische Verträge ausgeschlossen werden können. / This dissertation consists of three independent chapters, each in the field of dynamic contracting. Chapter I shows that deterministic dynamic contracts between a principal and an agent are always at least as profitable to the principal as stochastic ones, if the so-called first-order approach in dynamic mechanism design is satisfied. My results demonstrate that the usual restriction in the literature to deterministic contracts is admissible, as long as the first-order approach is valid. Chapter II is based on joint work with Ilia Krasikov and Rohit Lamba. We consider a large supplier (principal) who contracts with a small firm (agent) to repeatedly provide working capital in return for payments. The agent is less patient than the principal. The optimal contract is characterized by two key properties: restart and shutdown, which capture various aspects of contracts offered in the marketplace. Finally, Chapter III is based on joint work with Rohit Lamba. We consider the problem of optimal contracting where the agent has dynamic private information, which follows a Markov process. In each period, a monopolistic principal sells a nondurable good to the agent and she commits to the contract she made in the initial period. The emerging information costs prevent first-best contracts whenever there is persistency in the agent’s type. This thesis provides a strategy on how to obtain the optimal deterministic contract in dynamic principal-agent models with Markovian type realizations. We see that the usual approach with only local downward binding incentive compatibility constraints does not work for highly persistent type realizations and for large differences in discounting. Furthermore, I show in which situations we with certainty can exclude stochastic contracts.