<p>In many multiagent settings, a decision must be made based on the preferences of multiple agents, and agents may lie about their preferences if this is to their benefit. In mechanism design, the goal is to design procedures (mechanisms) for making the decision that work in spite of such strategic behavior, usually by making untruthful behavior suboptimal. In automated mechanism design, the idea is to computationally search through the space of feasible mechanisms, rather than to design them analytically by hand. Unfortunately, the most straightforward approach to automated mechanism design does not scale to large instances, because it requires searching over a very large space of possible functions. In this thesis, we adopt an approach to automated mechanism design that is computationally feasible. Instead of optimizing over all feasible mechanisms, we carefully choose a parameterized subfamily of mechanisms. Then we optimize over mechanisms within this family. Finally, we analyze whether and to what extent the resulting mechanism is suboptimal outside the subfamily. We apply (computationally feasible) automated mechanism design to three resource allocation mechanism design problems: mechanisms that redistribute revenue, mechanisms that involve no payments at all, and mechanisms that guard against false-name manipulation.</p> / Dissertation

In this thesis, we address several generic problems concerned with procurement of tasks from a crowd that consists of strategic workers with uncertainty in their qualities. These problems assume importance as the quality of services in a service marketplace is known to degrade when there is (unchecked) information asymmetry pertaining to quality. Moreover, crowdsourcing is increasingly being used for a wide variety of tasks these days since it offers high levels of flexibility to workers as well as employers. We seek to address the issue of quality uncertainty in crowdsourcing through mechanism design and machine learning. As the interactions in web-based crowdsourcing platform are logged, the data captured could be used to learn unknown parameters such as qualities of individual crowd workers. Further, many of these platforms invite bids by crowd workers for available tasks but the strategic workers may not bid truthfully. This warrants the use of mechanism design to induce truthful bidding. There ensues a complex interplay between machine learning and mechanism design, leading to interesting technical challenges. We resolve some generic challenges in the context of the following problems. Design of a quality eliciting mechanism with interdependent values We consider an expert sourcing problem, where a planner seeks opinions from a pool of experts. Execution of the task at an assured quality level in a cost effective manner turns out to be a mechanism design problem when the individual qualities are private information of the experts. Also, the task execution problem involves interdependent values, where truthfulness and efficiency cannot be achieved in an unrestricted setting due to an impossibility result. We propose a novel mechanism that exploits the special structure of the problem and guarantees allocative efficiency, ex-post incentive compatibility and strict budget balance for the mechanism, and ex-post individual rationality for the experts. Design of an optimal dimensional crowdsourcing auction We study the problem faced by an auctioneer who gains stochastic rewards by procuring multiple units of a service from a pool of heterogeneous strategic workers. The reward obtained depends on the inherent quality of the worker; the worker’s quality is fixed but unknown. The costs and capacities are private information of the workers. The auctioneer is required to elicit costs and capacities (making the mechanism design dimensional) and further, has to learn the qualities of the workers as well, to enable utility maximization. To solve this problem, we design a dimensional multi-armed bandit auction that maximizes the expected utility of the auctioneer subject to incentive compatibility and individual rationality while simultaneously learning the unknown qualities of the agents. Design of a multi-parameter learning mechanism for crowdsourcing We investigate the problem of allocating divisible jobs, arriving online, to workers in a crowd-sourcing platform. Each job is split into a certain number of tasks that are then allocated to workers. These tasks have to meet several constraints that depend on the worker performance. The performance of each worker in turn is characterized by several intrinsic stochastic parameters. In particular, we study a problem where each arriving job has to be completed within a deadline and each task has to be completed, honouring a lower bound on quality. The job completion time and quality of each worker are stochastic with fixed but unknown means. We propose a learning mechanism to elicit the costs truthfully while simultaneously learning the stochastic parameters. Our proposed mechanism is dominant strategy incentive compatible and ex-post individually rational with asymptotically optimal regret performance.

This thesis looks into the economics of crowdsourcing using game theoretic modeling. The art of aggregating information and expertise from a diverse population has been in practice since a long time. The Internet and the revolution in communication and computational technologies have made this task easier and given birth to a new era of online resource aggregation, which is now popularly referred to as crowdsourcing. Two important features of this aggregation technique are: (a) crowdsourcing is always human driven, hence the participants are rational and intelligent, and they have a payoff function that they aim to maximize, and (b) the participants are connected over a social network which helps to reach out to a large set of individuals. To understand the behavior and the outcome of such a strategic crowd, we need to understand the economics of a crowdsourcing network. In this thesis, we have considered the following three major facets of the strategic crowdsourcing problem. (i) Elicitation of the true qualities of the crowd workers: As the crowd is often unstructured and unknown to the designer, it is important to ensure if the crowdsourced job is indeed performed at the highest quality, and this requires elicitation of the true qualities which are typically the participants' private information. (ii) Resource critical task execution ensuring the authenticity of both the information and the identity of the participants: Due to the diverse geographical, cultural, socio-economic reasons, crowdsourcing entails certain manipulations that are unusual in the classical theory. The design has to be robust enough to handle fake identities or incorrect information provided by the crowd while performing crowdsourcing contests. (iii) Improving the productive output of the crowdsourcing network: As the designer's goal is to maximize a certain measurable output of the crowdsourcing system, an interesting question is how one can design the incentive scheme and/or the network so that the system performs at an optimal level taking into account the strategic nature of the individuals. In the thesis, we design novel mechanisms to solve the problems above using game theoretic modeling. Our investigation helps in understanding certain limits of achievability, and provides design protocols in order to make crowdsourcing more reliable, effective, and productive.

<div>A central issue in systems engineering is to design systems where the stakeholders do not behave as expected by the systems designer. Usually, these stakeholders have different and often conflicting objectives. The stakeholders try to maximize their individual objective and the overall system do not function as expected by the systems designers.</div><div><br></div><div><div>We specifically study two such systems- a) cloud-based design and manufacturing system (CBDM) and b) Air Transportation System (ATS). In CBDM, two stakeholders</div><div>with conflicting objectives are designers trying to get their parts printed at the lowest possible price and manufacturers trying to sell their excess resource capacity at maximum prots. In ATS, on one hand, airlines make route selection decision with the goal of maximizing their market share and prots and on the other hand regulatory bodies such as Federal Aviation Administration tries to form policies that increase overall welfare of the people.</div></div><div><br></div><div><div>The objective in this dissertation is to establish a mechanism design based framework: a) for resource allocation in CBDM, and b) to guide the policymakers in channeling the evolution of network topology of ATS.</div></div><div><br></div><div><div>This is the rst attempt in literature to formulate the resource allocation in CBDM as a bipartite matching problem with designers and manufacturers forming two distinct set of agents. We recommend best mechanisms in different CBDM scenarios like totally decentralized scenario, organizational scenario etc. based on how well the properties of the mechanism meet the requirements of that scenario. In addition to analyzing existing mechanisms, CBDM offers challenges that are not addressed in the literature. One such challenge is how often should the matching mechanism be implemented when agents interact over a long period of time. We answer this question through theoretical propositions backed up by simulation studies. We conclude that a matching period equal to the ratio of the number of service providers to the arrival rate of designers is optimal when service rate is high and a matching period equal to</div><div>the ratio of mean printing time to mean service rate is optimal when service rate is low.</div></div><div><br></div><div><div>In ATS, we model the evolution of the network topology as the result of route selection decisions made by airlines under competition. Using data from historic decisions we use discrete games to model the preference parameters of airlines towards explanatory variables such as market demand and operating cost. Different from the existing literature, we use an airport presence based technique to estimate these parameters. This reduces the risk of over-tting and improves prediction accuracy. We conduct a forward simulation to study the effect of altering the explanatory variables on the Nash equilibrium strategies. Regulatory bodies could use these insights while forming policies.</div></div><div><br></div><div><div>The overall contribution in this research is a mechanism design framework to design complex engineered systems such as CBDM and ATS. Specically, in CBDM a matching mechanism based resource allocation framework is established and matching mechanisms are recommended for various CBDM scenarios. Through theoretical and</div><div>simulation studies we propose the frequency at which matching mechanisms should be implemented in CBDM. Though these results are established for CBDM, these</div><div>are general enough to be applied anywhere matching mechanisms are implemented multiple times. In ATS, we propose an airport presence based approach to estimate</div><div>the parameters that quantify the preference of airlines towards explanatory variables.</div></div>

在世界各地，自然或人為災難隨時可能發生。災難回應作為災難處理的重要環節顯得尤為重要，隨著科學技術的進步和提高，人們希望通過使用各種科學手段來提高災難的回應效率。機器人技術作為21世紀高科技結合的產物被廣泛應用於這一領域。一般情況下，設計者會採用功能集成的思想對機器人進行設計，他們的主要設計思想是根據自己對環境的理解和認知得到機器人的設計需求，然後針對設計需求，通過功能集成和疊加的方式來完成對機器人的設計，採用這種方式機器人一旦設計完畢，其功能也隨之確立並不可更改，這種設計思想是基於環境狀況的，即一旦災難現場的環境不符合預先的設定，機器人的執行能力將大幅下降，同時功能疊加的設計方式會產生功能與功能之間相互約束，影響其專業性。 / 本文介紹了一種基於分散式設計思想的全新設計理念，並且根據這一理念設計了一套基於任務需求的救援機器人系統。機器人系統不會根據設計者對災難現場的預先理解和認知而被一體化設計，相反根據"如何到達"和"如何操作"把機器人系統拆分成移動單元和操作單元兩個環節，針對每個環節分別設計了符合現場需求的通用移動模組和任務執行模組，救援人員可以根據災難現場的即時任務需求而迅速搭建出有針對性的機器人系統任務解決方案，和傳統的機器人系統相比，具適應性廣、靈活性高、針對性強等特點。 / 在本論文中，對三種通用的移動平臺和兩種通用的模組化關節以及一個快速連接器分別進行了結構設計、理論分析及樣機設計，並採用基本的通用模組，根據即時的任務需求構建出有針對性的多個機器人系統。實驗表明該機器人系統可以提供對災難環境有針對性的系統解決方案，具有一定容錯性、經濟性及災難環境的適應性。文章的創新點如下，首次針對于救援機器人提出分散式的設計思想，並以該思想為基礎設計了基於通用模組的救援機器人系統，針對不同任務對移動性能的不同要求設計了三種移動平臺，為滿足不同的救援操作要求設計了兩種模組化關節以及快速連接器。同時，文中為實際的地震救援任務提出了一套救援機器人系統解決方案。 / Natural and man-made disasters nowadays still present a large amount of risk. Disaster response is an important phase of disaster management, and the enhancement of its effectiveness and accountability has attracted an increasing amount of attention. Robots can help rescuers in doing this task because of its wide range of applications. In general, the rescue robot concept assumes one or more targeted tasks while design, and one or a set of robot(s) is/are designed by integrating different functions to accomplish those tasks. Once the design of a robot is finished, its function cannot be changed. However, this kind of design is environment-dependent, as once a disaster environment changes, the execution performance of the robot will reduce. Furthermore the function-integrated design concept may cause internal constraints between functions, and fail to provide a targeted solution for different disaster environments. / This dissertation introduces a novel design concept, based on which a requirement-oriented rescue robot system is developed. This design concept adopts a distributed strategy, according to which tasks are no longer seen as a whole but divided into two parts: traversability and operation. Several functional modules are designed to meet the different requirements of the two parts separately, and the entire robot system can be assembled using different functional modules according to the real-time requirements of the disaster environment. Compared with the traditional rescue robot system, this system can provide a more targeted solution for different disaster situations, and is more adaptable and flexible. / This dissertation details the basic functional modules, including three kinds of mobile bases for traversability and two sets of modular joints for operation, and analyzes a quick connector that makes the connection easier and more convenient. Several possible combinations of the rescue robot system are displayed to show how to construct a rescue robot system according to different requirements. This kind of rescue robot system can provide targeted solutions to different disaster tasks. Robustness is also enhanced, as the replacement of the functional modules is flexible and easy to overhaul. Furthermore, the functional modules can be decomposed and reused to make the robot system more economical. This dissertation makes several contributions. It presents a systematic solution for rescue robot, develops three mobile bases for high traversability and two kinds of modular joints and a quick connector for rescue operation. Furthermore, it also develops a rescue robot system for missions in earthquake. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Yang, Yong. / Thesis (Ph.D.) Chinese University of Hong Kong, 2014. / Includes bibliographical references (leaves 226-236). / Abstracts also in Chinese.

空間站探索是世界熱點研究問題，空間站巨大因此往往在外太空在軌建造和組裝，因此需要由宇航員和機器人開展大量的艙外工作（ Extra-Vehicular Activities，EVAs）。目前，宇航員的艙外工作存在以下三個方面的問題：（1）宇航員在移動攀爬和任務操作相互衝突的問題， 宇航員在艙外工作時不能一邊沿著扶手攀爬，一邊搬運載荷；（2）當前的空間機器人工作空間有限，在空間站表面有許多地方無法達到開展艙體檢查等在軌服務；（3）當前的空間機器人在狹窄空間裡操作效率不高，不能很好地避開障礙物和做精細化靈巧操作。 / 本論文針對以上問題提出了2 個機器人系統，四腿行走機器人（ Four-legged Robot Walker, FLRW ） 和圓弧軌道機器人（Circular Rail Robot System , CRRS）。四腿行走機器人擅長多退的扶手攀爬和操作，攀爬和操作可同時開展。四腿行走機器人還有一個可旋轉頭部（可旋轉的視覺系統）來增強攀爬過程中的視覺範圍。圓弧軌道機器人通過移動機器人在圓弧軌道的運動能完全覆蓋空間站的所有工作空間，該系統是在太空應用的第一個弧形軌道系統，同時也有最小的轉彎半徑。 / 本論文對提出的2 個機器人系統的移動性進行了深入的研究，四腿機器人側重在雙臂攀爬的策略、攀爬步態，並開展了全艙攀爬的在軌任務模擬驗證。圓弧軌道機器人開展了艙體軌道系統、多艙體軌道切換器、移動基座平臺、移動平臺驅動和轉彎半徑的深入設計與分析，並且完成了移動軌道平臺的原型樣機試製驗證。 / 本論文對提出的2 個機器人系統的操作臂開展了非球形腕部掛接、冗餘操作臂奇異點辨識研究，提出了一種雅克比初等變換（MJET）演算法進行操作臂奇異分析，該演算法可以將冗餘機械臂的6x7 奇異矩陣轉化到3x4 的子矩陣，大大提高了運算效率。論文還開展了在多移動物體環境下的避障研究，提出了一種即時的多移動物體障礙回避（MMOA）演算法，該演算法採用超曲面函數描述障礙物的包絡，採用偽距離即時計算與移動障礙物距離，取得了控制精度和即時性的平衡。 / 本論文對提出的2 個機器人系統的操作臂開展了動力學建模和在軌裝配研究，採用拉格朗日建模方法對操作臂建模，並與商務軟體ADAMS 對比驗證建模準確度。同時，並運用阻抗控制演算法針對ORU 的在軌抓取、安裝和轉移等在軌任務的實現驗證。 / 最後論文進行了總結和後續工作展望。 / Space station exploration is a global hot research topic. The space stations are usually large in scale so that they have to be fabricated and assembled in space, which involves a large number of Extra-Vehicular Activities (EVAs) by astronauts and robots. There are three main problems of EVA mission. (1) Astronauts experience a conflict between climbing and manipulation during EVA missions, as they cannot carry payloads while handrail climbing. (2) Current space robots have workspace limitations and cannot reach the whole exterior of a space station, making it challenging to carry out inspection and servicing. (3) It is also difficult for robots to avoid obstacles and perform fine manipulation tasks in a compact workspace. / Two robotics systems, the Four-Legged Robot Walker (FLRW) and the Circular-Rail Robot System (CRRS), are proposed to address the above problems. The FLRW is good at handrail climbing as it has multiple, identical legs. It also has a rotatable vision system to enhance its field of view during climbing. The CRRS provides full coverage of the space station workspace, as it is a mobile robot that drives on a circular rail system around the space station. This system is the first design of robotic system with circular-rail in space and also has the smallest turning radius. / The mobility of both robots is addressed. The FLRW analysis focuses on the climbing strategy and climbing gait analysis. The circular rail system, rail switch, mobile platform, driving force and turning radius of CRRS are carefully designed and analyzed. A prototype of the CRRS mobile platform is implemented for verification. / The proposed manipulator is designed with redundant joint and non-spherical-wrists. A Modified Jacobian Elementary Transformation (MJET) approach is proposed to determine all of the singularity conditions. This approach has a singularity isolation feature to reduce the computational workload. A Multiple Moving Obstacle Avoidance (MMOA) approach is proposed for manipulator path planning in a compact workspace. A super-quadric surface function is used to describe the shape of an obstacle, and the pseudo-distance from the manipulator to the obstacle is measured and controlled in real time. This approach achieves a good balance between computational complexity and accuracy. / The proposed manipulator is modeled using the Lagrangian dynamics formulation and the dynamics of the proposed manipulator is verified with the commercial software ADAMS (Automatic Dynamic Analysis of Mechanical Systems). The mathematics model has similar output in ADAMS under a constant torque input and a sine torque input. The Orbital Replacement Unit (ORU) assembly task is implemented using impedance control. Both simulation and hardware tests are completed for verification, and the experimental results show that the controller is good for on-orbit servicing tasks. / The contributions of the thesis are summarized and future work is proposed. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Chen, Yongquan. / Thesis (Ph.D.) Chinese University of Hong Kong, 2014. / Includes bibliographical references (leaves 131-148). / Abstracts also in Chinese.

This thesis addresses problems in the area of mechanism design. In many settings in winch collective decisions are made, individuals' actual preferences are not publicly observable. As a result, individuals should be relied on to reveal this information. We are interested in an important application of mechanism design, which is the construction of desirable procedures for deciding upon resource allocation or task assignment. We make two main contributions. First, we propose a new mechanism for allocating a divisible commodity between a number of buyers efficiently and fairly. Buyers are assumed to behave as price-anticipators rather than as price-takers. The proposed mechanism is as parsimonious as possible, in the sense that it requires participants to report a one-dimensional message (scalar strategy) instead of an entire utility function, as required by Vickrey-Clarke-Groves (VCG) mechanisms. We show that this mechanism yields efficient allocations in Nash equilibria and moreover, that these equilibria are envy-free. Additionally, we present distinct results that this mechanism is the only simple scalar strategy mechanism that both implements efficient Nash equilibria and satisfies the no envy axiom of fairness. The mechanism's Nash equilibria are proven to satisfy the fairness properties of both Ranking and Voluntary Participation. Our second contribution is to develop optimal VCG mechanisms in order to assign identical economic "bads" (for example, costly tasks) to agents. An optimal VCG mechanism minimizes the largest ratio of budget imbalance to efficient surplus over all cost profiles. The optimal non-deficit VCG mechanism achieves asymptotic budget balance, yet the non-deficit requirement is incompatible with reasonable welfare bounds. If we omit the non-deficit requirement, individual rationality greatly changes the behavior of surplus loss and deficit loss. Allowing a slight deficit, the optimal individually rational VCG mechanism becomes asymptotically budget balanced. Such a phenomenon cannot be found in the case of assigning economic "goods."

Main objective of this study is to design a compliant mechanism with high frequency and high mechanical amplification ratio to be used for amplifying the stroke of a piezostack actuator. In this thesis, first of all, related literature is investigated and then alternative conceptual designs are established utilizing the mechanisms found in literature survey. Once best conceptual design is selected, detailed design of this mechanism is done. For detailed design of the compliant mechanism, topology optimization method is used in this study. To design the mechanism, first a design domain is defined and then a finite element model of the design domain is prepared to be used in topology optimization runs. After running the topology optimization model by using TOSCA with ANSYS, results are imported to ANSYS, where final performance of the mechanism design is checked. After finalizing design of the mechanism, it is produced and its performance is tested through experiments.

Main objective of this study is to design a compliant mechanism with high frequency and high mechanical amplification ratio to be used for amplifying the stroke of a piezostack actuator. In this thesis, first of all, related literature is investigated and then alternative conceptual designs are established utilizing the mechanisms found in literature survey. Once best conceptual design is selected, detailed design of this mechanism is done. For detailed design of the compliant mechanism, topology optimization method is used in this study. To design the mechanism, first a design domain is defined and then a finite element model of the design domain is prepared to be used in topology optimization runs. After running the topology optimization model by using TOSCA with ANSYS, results are imported to ANSYS, where final performance of the mechanism design is checked. After finalizing design of the mechanism, it is produced and its performance is tested through experiments.

This thesis presents an in-depth investigation to determine the most suitable mobile base design for a powerful and dynamic robotic manipulator. It details the design process of such a mobile platform for use in an indoor human environment that is to carry a two-arm upper-body humanoid manipulator system. Through systematic dynamics analysis, it was determined that a variable footprint holonomic wheeled mobile platform is the design of choice for such an application. Determining functional requirements and evaluating design options is performed for the platform’s general configuration, geometry, locomotion system, suspension, and propulsion, with a particularly in-depth evaluation of the problem of overcoming small steps. Other aspects such as processing, sensing and the power system are dealt with sufficiently to ensure the feasibility of the overall proposed design. The control of the platform is limited to that necessary to determine the appropriate mechanical components. Simulations are performed to investigate design problems and verify performance. A basic CAD model of the system is included for better design visualization. The research carried out in this thesis was performed in cooperation with the German Aerospace Center (Deutsches Zentrum für Luft- und Raumfahrt)’s Robotics and Mechatronics Institute (DLR RM). The DLR RM is currently utilizing the findings of this research to finish the development of the platform with a target completion date of May 2008.