This thesis makes a number of contributions to the theory of approximation algorithm design for multi-agent systems. In particular, we focus on two research directions. The first direction is to generalize the classical framework of combinatorial optimization to the submodular setting, where we assume that each agent has a submodular cost function. We show hardness results from both the information-theoretic and computational aspects for several fundamental optimization problems in the submodular setting, and provide matching approximation algorithms for most of them. The second direction is to introduce game-theoretic issues to approximation algorithm design. Towards this direction, we study the application of approximation algorithms in the theory of truthful mechanism design. We study both the standard objectives of revenue and social welfare, by designing efficient algorithms that satisfy the requirement of truthfulness and guarantee approximate optimality.

This dissertation uses theoretical and empirical tools to answer applied questions of design with an emphasis on issues relating to safety and crime. The first essay incorporates safety in implementation theory and studies when and how safe mechanisms can be designed to obtain socially desirable outcomes. I provide general conditions under which a social choice rule can be implemented using safe mechanisms. The second essay is an empirical study of how criminals respond to changing profitability of crime, a question that informs the policy debate on the most effective crime fighting methods. I find that the price elasticity of theft is about 1 in the short term and increases to about 1.2 over a seven-month horizon, suggesting that policies that directly affect crime profitability, such as policies that shut down black markets or those that reduce demand for illegal goods, can be relatively effective. The third essay shows that any standard implementation problem can be formulated as a question about the existence of a graph that solves a graph coloring problem, establishing a connection between implementation theory and graph theory. More generally, an implementation problem can be viewed as a constraint satisfaction problem, and I propose an algorithm to design simple mechanisms to solve arbitrary implementation problems. / text

Unit-demand auctions have been well studied with applications in several areas. In this dissertation, we discuss new variants of the unit-demand auction that are motivated by practical applications. We design mechanisms for these variants that have strong properties related to truthfulness, efficiency, scalability, and privacy. The main contributions of this dissertation can be divided into two parts. In the first part, we introduce a new variant of the classic sealed-bid unit-demand auction in which each item is associated with a put option; the put option of an item gives the seller the right to sell the item at a specified strike price to a specified bidder, regardless of market conditions. We motivate our unit-demand auction setting by discussing applications to the reassignment of leases, and to the design of multi-round auctions. For the classic sealed-bid unit-demand framework, the VCG mechanism provides a truthful auction with strong associated guarantees, including efficiency and envy-freedom. For an item in our auction, the strike price of the associated put imposes a lower bound on the auction price. Due to these lower bound constraints on auction prices, we find that the VCG mechanism is not suitable for our setting. Instead, our work draws on two fundamental techniques, one from the realm of mechanism design for numerical preferences -- the dynamic unit-demand approximate auction of Demange, Gale, and Sotomayor -- and one from the realm of mechanism design for ordinal preferences -- the Top Trading Cycles algorithm -- to obtain a natural auction that satisfies the lower bound constraints on auction prices. While we cannot, in general, achieve either efficiency or envy-freedom in our setting, our auction achieves suitably relaxed versions of these properties. For example, this auction is envy-free for all bidders who do not acquire an item via the exercise of a put. We provide a polynomial time implementation of this auction. By breaking ties in an appropriate manner, we are able to prove that this auction is truthful. In the second part, we specify rules for a dynamic unit-demand auction that supports arbitrary bid revision. In each round, the dynamic auction takes a tentative allocation and pricing as part of the input, and allows each bidder -- including a tentatively allocated bidder -- to submit an arbitrary unit-demand bid. Each round of our dynamic auction is implemented via a single application of the sealed-bid unit-demand auction proposed in the first part. We show that our dynamic auction satisfies strong properties related to truthfulness and efficiency. Using a certain privacy preservation property of each round of the auction, we show that the overall dynamic auction is highly resistant to shilling. We present a fast algorithm for implementing the proposed auction. Using this algorithm, the amortized cost of processing each bidding operation is upper bounded by the complexity of solving a single-source shortest paths problem on a graph with nonnegative edge weights and a node for each item in the auction. We also propose a dynamic price adjustment scheme that discourages sniping by providing bidders with incentives to bid early in the auction. / text

Fair division is the problem of dividing one or several goods among a set of agents in a way that satisfies a suitable fairness criterion. Traditionally studied in economics, philosophy, and political science, fair division has drawn a lot of attention from the multiagent systems community, since this field is strongly concerned about how a surplus (or a cost) should be divided among a group of agents. Arguably, the Shapley value is the single most important contribution to the problem of fair division. It assigns to each agent a share of the resource equal to the expected marginal contribution of that agent. Thus, it is implicitly assumed that individual marginal contributions can be objectively computed. In this thesis, we propose a game-theoretic model for sharing a joint reward when the quality of individual contributions is subjective. In detail, we consider scenarios where a group has been formed and has accomplished a task for which it is granted a reward, which must be shared among the group members. After observing the contribution of the peers in accomplishing the task, each agent is asked to provide evaluations for the others. Mainly to facilitate the sharing process, agents can also be requested to provide predictions about how their peers are evaluated. These subjective opinions are elicited and aggregated by a central, trusted entity, called the mechanism, which is also responsible for sharing the reward based exclusively on the received opinions. Besides the formal game-theoretic model for sharing rewards based on subjective opinions, we propose three different mechanisms in this thesis. Our first mechanism, the peer-evaluation mechanism, divides the reward proportionally to the evaluations received by the agents. We show that this mechanism is fair, budget-balanced, individually rational, and strategy-proof, but that it can be collusion-prone. Our second mechanism, the peer-prediction mechanism, shares the reward by considering two aspects: the evaluations received by the agents and their truth-telling scores. To compute these scores, this mechanism uses a strictly proper scoring rule. Under the assumption that agents are Bayesian decision-makers, we show that this mechanism is weakly budget-balanced, individually rational, and incentive-compatible. Further, we present approaches that guarantee the mechanism to be collusion-resistant and fair. Our last mechanism, the BTS mechanism, is the only one to elicit both evaluations and predictions from the agents. It considers the evaluations received by the agents and their truth-telling scores when sharing the reward. For computing the scores, it uses the Bayesian truth serum method, a powerful scoring method based on the surprisingly common criterion. Under the assumptions that agents are Bayesian decision-makers, and that the population of agents is sufficiently large so that a single evaluation cannot significantly affect the empirical distribution of evaluations, we show that this mechanism is incentive-compatible, budget-balanced, individually rational, and fair.

This thesis studies issues in auctions and contests. The seller of an object and the organizer of a contest have many instruments to improve the revenue of the auction or the efficiency of the contest. The three essays in this dissertation shed light on these issues. Chapter 2 investigates how a refund policy affects a buyer's strategic behavior by characterizing the equilibria of a second-price auction with a linear refund policy. I find that a generous refund policy induces buyers to bid aggressively. I also examine the optimal mechanism design problem when buyers only have private initial estimates of their valuations and may privately learn of shocks that affect their valuations later. When all buyers are \emph{ex-ante} symmetric, this optimal selling mechanism can be implemented by a first-price or second-price auction with a refund policy. Chapter 3 investigates how information revelation rules affect the existence and the efficiency of equilibria in two-round elimination contests. I establish that there exists no symmetric separating equilibrium under the full revelation rule and find that the non-existence result is very robust. I then characterize a partially efficient separating equilibrium under the partial revelation rule when players' valuations are uniformly distributed. I finally investigate the no revelation rule and find that it is both most efficient and optimal in maximizing the total efforts from the contestants. Within my framework, more information revelation leads to less efficient outcomes. Chapter 4 analyzes the signaling effect of bidding in a two-round elimination contest. Before the final round, bids in the preliminary round are revealed and act as signals of the contestants' private valuations. Compared to the benchmark model, in which private valuations are revealed automatically before the final round and thus no signaling of bids takes place, I find that strong contestants bluff and weak contestants sandbag. In a separating equilibrium, bids in the preliminary round fully reveal the contestants' private valuations. However, this signaling effect makes the equilibrium bidding strategy in the preliminary round steeper for high valuations and flatter for low valuations compared to the benchmark model. / Thesis (Ph.D, Economics) -- Queen's University, 2010-04-20 21:34:12.295

No description available.

Algorithmic mechanism design deals with efficiently-computable algorithmic constructions in the presence of strategic players who hold the inputs to the problem and may misreport their input if doing so benefits them. Algorithmic mechanism design finds applications in a variety of internet settings such as resource allocation, facility location and e-commerce, such as sponsored search auctions. There is an extensive amount of work in algorithmic mechanism design on packing problems such as single-item auctions, multi-unit auctions and combinatorial auctions. But, surprisingly, covering problems, also called procurement auctions, have almost been completely unexplored, especially in the multidimensional setting. In this thesis, we systematically investigate multidimensional covering mechanism- design problems, wherein there are m items that need to be covered and n players who provide covering objects, with each player i having a private cost for the covering objects he provides. A feasible solution to the covering problem is a collection of covering objects (obtained from the various players) that together cover all items. Two widely considered objectives in mechanism design are: (i) cost-minimization (CM) which aims to minimize the total cost incurred by the players and the mechanism designer; and (ii) payment minimization (PayM), which aims to minimize the payment to players. Covering mechanism design problems turn out to behave quite differently from packing mechanism design problems. In particular, various techniques utilized successfully for packing problems do not perform well for covering mechanism design problems, and this necessitates new approaches and solution concepts. In this thesis we devise various techniques for handling covering mechanism design problems, which yield a variety of results for both the CM and PayM objectives. In our investigation of the CM objective, we focus on two representative covering problems: uncapacitated facility location (UFL) and vertex cover. For multi-dimensional UFL, we give a black-box method to transform any Lagrangian-multiplier-preserving ??-approximation algorithm for UFL into a truthful-in-expectation, ??-approximation mechanism. This yields the first result for multi-dimensional UFL, namely a truthful-in-expectation 2-approximation mechanism. For multi-dimensional VCP (Multi-VCP), we develop a decomposition method that reduces the mechanism-design problem into the simpler task of constructing threshold mechanisms, which are a restricted class of truthful mechanisms, for simpler (in terms of graph structure or problem dimension) instances of Multi-VCP. By suitably designing the decomposition and the threshold mechanisms it uses as building blocks, we obtain truthful mechanisms with approximation ratios (n is the number of nodes): (1) O(r2 log n) for r-dimensional VCP; and (2) O(r log n) for r-dimensional VCP on any proper minor-closed family of graphs (which improves to O(log n) if no two neighbors of a node belong to the same player). These are the first truthful mechanisms for Multi-VCP with non-trivial approximation guarantees. For the PayM objective, we work in the oft-used Bayesian setting, where players??? types are drawn from an underlying distribution and may be correlated, and the goal is to minimize the expected total payment made by the mechanism. We consider the problem of designing incentive compatible, ex-post individually rational (IR) mechanisms for covering problems in the above model. The standard notion of incentive compatibility (IC) in such settings is Bayesian incentive compatibility (BIC), but this notion is over-reliant on having precise knowledge of the underlying distribution, which makes it a rather non- robust notion. We formulate a notion of IC that we call robust Bayesian IC (robust BIC) that is substantially more robust than BIC, and develop black-box reductions from robust BIC-mechanism design to algorithm design. This black-box reduction applies to single- dimensional settings even when we only have an LP-relative approximation algorithm for the algorithmic problem. We obtain near-optimal mechanisms for various covering settings including single- and multi-item procurement auctions, various single-dimensional covering problems, and multidimensional facility location problems. Finally, we study the notion of frugality, which considers the PayM objective but in a worst-case setting, where one does not have prior information about the players??? types. We show that some of our mechanisms developed for the CM objective are also good with respect to certain oft-used frugality benchmarks proposed in the literature. We also introduce an alternate benchmark for frugality, which more directly reflects the goal that the mechanism???s payment be close to the best possible payment, and obtain some preliminary results with respect to this benchmark.

In this thesis, we examine stochastic techniques for overcoming game theoretic and computational issues in the collective decision making process of self-interested individuals. In particular, we examine truthful, stochastic mechanisms, for settings with a strong budget balance constraint (i.e. there is no net flow of money into or away from the agents). Building on past results in AI and computational social choice, we characterise affine-maximising social choice functions that are implementable in truthful mechanisms for the setting of heterogeneous item allocation with unit demand agents. We further provide a characterisation of affine maximisers with the strong budget balance constraint. These mechanisms reveal impossibility results and poor worst-case performance that motivates us to examine stochastic solutions. To adequately compare stochastic mechanisms, we introduce and discuss measures that capture the behaviour of stochastic mechanisms, based on techniques used in stochastic algorithm design. When applied to deterministic mechanisms, these measures correspond directly to existing deterministic measures. While these approaches have more general applicability, in this work we assess mechanisms based on overall agent utility (efficiency and social surplus ratio) as well as fairness (envy and envy-freeness). We observe that mechanisms can (and typically must) achieve truthfulness and strong budget balance using one of two techniques: labelling a subset of agents as ``auctioneers'' who cannot affect the outcome, but collect any surplus; and partitioning agents into disjoint groups, such that each partition solves a subproblem of the overall decision making process. Worst-case analysis of random-auctioneer and random-partition stochastic mechanisms show large improvements over deterministic mechanisms for heterogeneous item allocation. In addition to this allocation problem, we apply our techniques to envy-freeness in the room assignment-rent division problem, for which no truthful deterministic mechanism is possible. We show how stochastic mechanisms give an improved probability of envy-freeness and low expected level of envy for a truthful mechanism. The random-auctioneer technique also improves the worst-case performance of the public good (or public project) problem. Communication and computational complexity are two other important concerns of computational social choice. Both the random-auctioneer and random-partition approaches offer a flexible trade-off between low complexity of the mechanism, and high overall outcome quality measured, for example, by total agent utility. They enable truthful and feasible solutions to be incrementally improved on as the mechanism receives more information and is allowed more processing time. The majority of our results are based on optimising worst-case performance, since this provides guarantees on how a mechanism will perform, regardless of the agents that use it. To complement these results, we perform empirical, average-case analyses on our mechanisms. Finally, while strong budget balance is a fixed constraint in our particular social choice problems, we show empirically that this can improve the overall utility of agents compared to a utility-maximising assignment that requires a budget imbalanced mechanism.

Der Vortrag zeigt die einzelnen notwendigen Schritte auf, die zur Lösung des Resonanzproblems an der Vorderradaufhängung eines E-Rollstuhls der Firma MEYRA-ORTOPEDIA notwendig waren. Alle Lösungsschritte wurden mit Creo Elements/Pro und seinen Modulen Mechanism Design Option (MDO) und Advanced Mechanica erarbeitet.

In this thesis, we examine stochastic techniques for overcoming game theoretic and computational issues in the collective decision making process of self-interested individuals. In particular, we examine truthful, stochastic mechanisms, for settings with a strong budget balance constraint (i.e. there is no net flow of money into or away from the agents). Building on past results in AI and computational social choice, we characterise affine-maximising social choice functions that are implementable in truthful mechanisms for the setting of heterogeneous item allocation with unit demand agents. We further provide a characterisation of affine maximisers with the strong budget balance constraint. These mechanisms reveal impossibility results and poor worst-case performance that motivates us to examine stochastic solutions. To adequately compare stochastic mechanisms, we introduce and discuss measures that capture the behaviour of stochastic mechanisms, based on techniques used in stochastic algorithm design. When applied to deterministic mechanisms, these measures correspond directly to existing deterministic measures. While these approaches have more general applicability, in this work we assess mechanisms based on overall agent utility (efficiency and social surplus ratio) as well as fairness (envy and envy-freeness). We observe that mechanisms can (and typically must) achieve truthfulness and strong budget balance using one of two techniques: labelling a subset of agents as ``auctioneers'' who cannot affect the outcome, but collect any surplus; and partitioning agents into disjoint groups, such that each partition solves a subproblem of the overall decision making process. Worst-case analysis of random-auctioneer and random-partition stochastic mechanisms show large improvements over deterministic mechanisms for heterogeneous item allocation. In addition to this allocation problem, we apply our techniques to envy-freeness in the room assignment-rent division problem, for which no truthful deterministic mechanism is possible. We show how stochastic mechanisms give an improved probability of envy-freeness and low expected level of envy for a truthful mechanism. The random-auctioneer technique also improves the worst-case performance of the public good (or public project) problem. Communication and computational complexity are two other important concerns of computational social choice. Both the random-auctioneer and random-partition approaches offer a flexible trade-off between low complexity of the mechanism, and high overall outcome quality measured, for example, by total agent utility. They enable truthful and feasible solutions to be incrementally improved on as the mechanism receives more information and is allowed more processing time. The majority of our results are based on optimising worst-case performance, since this provides guarantees on how a mechanism will perform, regardless of the agents that use it. To complement these results, we perform empirical, average-case analyses on our mechanisms. Finally, while strong budget balance is a fixed constraint in our particular social choice problems, we show empirically that this can improve the overall utility of agents compared to a utility-maximising assignment that requires a budget imbalanced mechanism.