Página 1 dos resultados de 6695 itens digitais encontrados em 0.031 segundos

Handling Interdependent Values in an Auction Mechanism for Bandwidth Allocation in Tactical Data Networks

Klein, Mark; Moreno, Gabriel A.; Parkes, David C.; Plakosh, Daniel; Seuken, Sven; Wallnau, Kurt C.
Fonte: Association for Computing Machinery Publicador: Association for Computing Machinery
Tipo: Monograph or Book
EN_US
Relevância na Pesquisa
55.83%
We consider a tactical data network with limited bandwidth, in which each agent is tracking objects and may have value for receiving data from other agents. The agents are self-interested and would prefer to receive data than share data. Each agent has private information about the quality of its data and can misreport this quality and degrade or otherwise decline to share its data. The problem is one of interdependent value mechanism design because the value to one agent for the broadcast of data on an object depends on the quality of the data, which is privately known to the sender. A recent two-stage mechanism due to Mezzetti (2004) can be modified to our setting. Our mechanism achieves efficient bandwidth allocation and provides incentive compatibility by conditioning payments on the realized value for data shared between agents.; Engineering and Applied Sciences

Computational-Mechanism Design: A Call to Arms

Dash, Rajdeep K.; Jennings, Nicholas R.; Parkes, David C.
Fonte: Institute of Electrical and Electronics Engineers Computer Society Publicador: Institute of Electrical and Electronics Engineers Computer Society
Tipo: Artigo de Revista Científica
EN_US
Relevância na Pesquisa
65.98%
Game theory has developed several powerful tools for analyzing decision making in systems composed of multiple autonomous actors. Given this fact, AI practitioners would like to exploit these tools when building software systems containing multiple agents. However, to do this, the tools must be tailored to computational settings. To this end, the authors provide an overview of computational-mechanism design, which deals with the application of economic principles in computer systems design. Moreover, because many complex systems are inherently distributed, they also present initial results from the relatively new field of distributed-computational-mechanism design and outline the key challenges involved in making the ideas practicable.; Engineering and Applied Sciences

Online Mechanism Design for Electric Vehicle Charging

Gerding, Enrico H.; Robu, Valentin; Stein, Sebastian; Parkes, David C.; Rogers, Alex; Jennings, Nicholas R.
Fonte: International Foundation for Autonomous Agents and Multiagent Systems Publicador: International Foundation for Autonomous Agents and Multiagent Systems
Tipo: Monograph or Book
EN_US
Relevância na Pesquisa
65.9%
Plug-in hybrid electric vehicles are expected to place a considerable strain on local electricity distribution networks, requiring charging to be coordinated in order to accommodate capacity constraints. We design a novel online auction protocol for this problem, wherein vehicle owners use agents to bid for power and also state time windows in which a vehicle is available for charging. This is a multi-dimensional mechanism design domain, with owners having non-increasing marginal valuations for each subsequent unit of electricity. In our design, we couple a greedy allocation algorithm with the occasional "burning" of allocated power, leaving it unallocated, in order to adjust an allocation and achieve monotonicity and thus truthfulness. We consider two variations: burning at each time step or on-departure. Both mechanisms are evaluated in depth, using data from a real-world trial of electric vehicles in the UK to simulate system dynamics and valuations. The mechanisms provide higher allocative efficiency than a fixed price system, are almost competitive with a standard scheduling heuristic which assumes non-strategic agents, and can sustain a substantially larger number of vehicles at the same per-owner fuel cost saving than a simple random scheme.; Engineering and Applied Sciences

Computationally feasible automated mechanism design: general approach and case studies

Guo, M.; Conitzer, V.
Fonte: AAAI; California; USA Publicador: AAAI; California; USA
Tipo: Conference paper
Publicado em //2010 EN
Relevância na Pesquisa
45.98%
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 paper, we describe 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, and analyze whether and to what extent the resulting mechanism is suboptimal outside the subfamily. We demonstrate the usefulness of our approach with two case studies.; Mingyu Guo and Vincent Conitzer

Essays in Mechanism Design

You, Jung Sook
Fonte: Universidade Rice Publicador: Universidade Rice
Tipo: Thesis; Text Formato: 149 p.; application/pdf
ENG
Relevância na Pesquisa
65.98%
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...

A software process engineering approach to improving software team productivity using socioeconomic mechanism design

Yilmaz, Murat; O'Connor, Rory V.
Fonte: Association for Computing Machinery Publicador: Association for Computing Machinery
Tipo: Article; all_ul_research; ul_published_reviewed; none
ENG
Relevância na Pesquisa
65.89%
peer-reviewed; Software development is a knowledge and human intensive activity. At the social level, the interactions of these participants and their ability to cooperate are important for improving the produc- tivity of teams and organizations. It is therefore not surprising to discover that recent contributions in software development have repeatedly asserted the critical role of people in software develop- ment e orts. However, existing approaches to software development fail to fully exploit the importance of social and intellectual capital that has been highlighted in the elds of economics and sociology. We propose that leveraging the existing approaches from economics and sociology and applying to software development can assist software organizations in maximizing their return on investment. For example, by applying one such approach, mechanism design, we can improve and model the organization's total productivity based on social aspects a ecting productivity (i.e. social productivity). This paper will discuss the vision and progress for applying the concept of mechanism design for optimizing software development teams.

Mechanism design with multidimensional, continuous types and interdependent valuations

Miller, Nolan; Pratt, John W; Zeckhauser, Richard J.; Johnson, Scott
Fonte: Academic Press Publicador: Academic Press
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
65.83%
We consider the mechanism design problem when agents' types are multidimensional and continuous, and their valuations are interdependent. If there are at least three agents whose types satisfy a weak correlation condition, then for any decision rule and a

New directions in mechanism design

Meng, Jiangtao
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 21/12/2005
Relevância na Pesquisa
46.03%
Mechanism design uses the tools of economics and game theory to design rules of interaction for economic transactions that will,in principle, yield some de- sired outcome. In the last few years this field has received much interest of researchers in computer science, especially with the Internet developing as a platform for communications and connections among enormous numbers of computers and humans. Arguably the most positive result in mechanism de- sign is truthful and there are only one general truthful mechanisms so far : the generalized Vickrey-Clarke-Groves (VCG) mechanism. But VCG mecha- nism has one shortage: The implementation of truthfulness is on the cost of decreasing the revenue of the mechanism. (e.g., Ning Chen and Hong Zhu. [1999]). We introduce three new characters of mechanism:partly truthful, criti- cal, consistent, and introduce a new mechanism: X mechanism that satisfy the above three characters. Like VCG mechanism, X mechanism also generalizes from Vickery Auction and is consistent with Vickery auction in many ways, but the extended methods used in X mechanism is different from that in VCG mechanism . This paper will demonstrate that X mechanism better than VCG mechanism in optimizing utility of mechanism, which is the original intention of mechanism design. So partly truthful...

Complexity of Mechanism Design

Conitzer, Vincent; Sandholm, Tuomas
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 07/08/2014
Relevância na Pesquisa
45.95%
The aggregation of conflicting preferences is a central problem in multiagent systems. The key difficulty is that the agents may report their preferences insincerely. Mechanism design is the art of designing the rules of the game so that the agents are motivated to report their preferences truthfully and a (socially) desirable outcome is chosen. We propose an approach where a mechanism is automatically created for the preference aggregation setting at hand. This has several advantages, but the downside is that the mechanism design optimization problem needs to be solved anew each time. Focusing on settings where side payments are not possible, we show that the mechanism design problem is NP-complete for deterministic mechanisms. This holds both for dominant-strategy implementation and for Bayes-Nash implementation. We then show that if we allow randomized mechanisms, the mechanism design problem becomes tractable. In other words, the coordinator can tackle the computational complexity introduced by its uncertainty about the agents preferences BY making the agents face additional uncertainty.This comes at no loss, AND IN SOME cases at a gain, IN the(social) objective.; Comment: Appears in Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence (UAI2002)

Mechanism Design without Money via Stable Matching

Chen, Ning; Gravin, Nick; Lu, Pinyan
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 14/04/2011
Relevância na Pesquisa
45.98%
Mechanism design without money has a rich history in social choice literature. Due to the strong impossibility theorem by Gibbard and Satterthwaite, exploring domains in which there exist dominant strategy mechanisms is one of the central questions in the field. We propose a general framework, called the generalized packing problem (\gpp), to study the mechanism design questions without payment. The \gpp\ possesses a rich structure and comprises a number of well-studied models as special cases, including, e.g., matroid, matching, knapsack, independent set, and the generalized assignment problem. We adopt the agenda of approximate mechanism design where the objective is to design a truthful (or strategyproof) mechanism without money that can be implemented in polynomial time and yields a good approximation to the socially optimal solution. We study several special cases of \gpp, and give constant approximation mechanisms for matroid, matching, knapsack, and the generalized assignment problem. Our result for generalized assignment problem solves an open problem proposed in \cite{DG10}. Our main technical contribution is in exploitation of the approaches from stable matching, which is a fundamental solution concept in the context of matching marketplaces...

Mechanism Design for Crowdsourcing: An Optimal 1-1/e Competitive Budget-Feasible Mechanism for Large Markets

Anari, Nima; Goel, Gagan; Nikzad, Afshin
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
45.96%
In this paper we consider a mechanism design problem in the context of large-scale crowdsourcing markets such as Amazon's Mechanical Turk, ClickWorker, CrowdFlower. In these markets, there is a requester who wants to hire workers to accomplish some tasks. Each worker is assumed to give some utility to the requester. Moreover each worker has a minimum cost that he wants to get paid for getting hired. This minimum cost is assumed to be private information of the workers. The question then is - if the requester has a limited budget, how to design a direct revelation mechanism that picks the right set of workers to hire in order to maximize the requester's utility. We note that although the previous work has studied this problem, a crucial difference in which we deviate from earlier work is the notion of large-scale markets that we introduce in our model. Without the large market assumption, it is known that no mechanism can achieve an approximation factor better than 0.414 and 0.5 for deterministic and randomized mechanisms respectively (while the best known deterministic and randomized mechanisms achieve an approximation ratio of 0.292 and 0.33 respectively). In this paper, we design a budget-feasible mechanism for large markets that achieves an approximation factor of 1-1/e (i.e. almost 0.63). Our mechanism can be seen as a generalization of an alternate way to look at the proportional share mechanism which is used in all the previous works so far on this problem. Interestingly...

Complexity of Mechanism Design

Conitzer, Vincent; Sandholm, Tuomas
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 28/05/2002
Relevância na Pesquisa
45.95%
The aggregation of conflicting preferences is a central problem in multiagent systems. The key difficulty is that the agents may report their preferences insincerely. Mechanism design is the art of designing the rules of the game so that the agents are motivated to report their preferences truthfully and a (socially) desirable outcome is chosen. We propose an approach where a mechanism is automatically created for the preference aggregation setting at hand. This has several advantages, but the downside is that the mechanism design optimization problem needs to be solved anew each time. Focusing on settings where side payments are not possible, we show that the mechanism design problem is NP-complete for deterministic mechanisms. This holds both for dominant-strategy implementation and for Bayes-Nash implementation. We then show that if we allow randomized mechanisms, the mechanism design problem becomes tractable. In other words, the coordinator can tackle the computational complexity introduced by its uncertainty about the agents' preferences by making the agents face additional uncertainty. This comes at no loss, and in some cases at a gain, in the (social) objective.

Higher-Order Approximate Relational Refinement Types for Mechanism Design and Differential Privacy

Barthe, Gilles; Gaboardi, Marco; Arias, Emilio Jesús Gallego; Hsu, Justin; Roth, Aaron; Strub, Pierre-Yves
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
45.95%
Mechanism design is the study of algorithm design in which the inputs to the algorithm are controlled by strategic agents, who must be incentivized to faithfully report them. Unlike typical programmatic properties, it is not sufficient for algorithms to merely satisfy the property---incentive properties are only useful if the strategic agents also believe this fact. Verification is an attractive way to convince agents that the incentive properties actually hold, but mechanism design poses several unique challenges: interesting properties can be sophisticated relational properties of probabilistic computations involving expected values, and mechanisms may rely on other probabilistic properties, like differential privacy, to achieve their goals. We introduce a relational refinement type system, called $\mathsf{HOARe}^2$, for verifying mechanism design and differential privacy. We show that $\mathsf{HOARe}^2$ is sound w.r.t. a denotational semantics, and correctly models $(\epsilon,\delta)$-differential privacy; moreover, we show that it subsumes DFuzz, an existing linear dependent type system for differential privacy. Finally, we develop an SMT-based implementation of $\mathsf{HOARe}^2$ and use it to verify challenging examples of mechanism design...

Mechanism Design and Risk Aversion

Bhalgat, Anand; Chakraborty, Tanmoy; Khanna, Sanjeev
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
45.95%
We develop efficient algorithms to construct utility maximizing mechanisms in the presence of risk averse players (buyers and sellers) in Bayesian settings. We model risk aversion by a concave utility function, and players play strategically to maximize their expected utility. Bayesian mechanism design has usually focused on maximizing expected revenue in a {\em risk neutral} environment, and no succinct characterization of expected utility maximizing mechanisms is known even for single-parameter multi-unit auctions. We first consider the problem of designing optimal DSIC mechanism for a risk averse seller in the case of multi-unit auctions, and we give a poly-time computable SPM that is $(1-1/e-\eps)$-approximation to the expected utility of the seller in an optimal DSIC mechanism. Our result is based on a novel application of a correlation gap bound, along with {\em splitting} and {\em merging} of random variables to redistribute probability mass across buyers. This allows us to reduce our problem to that of checking feasibility of a small number of distinct configurations, each of which corresponds to a covering LP. A feasible solution to the LP gives us the distribution on prices for each buyer to use in a randomized SPM. We next consider the setting when buyers as well as the seller are risk averse...

Computer-aided verification in mechanism design

Barthe, Gilles; Gaboardi, Marco; Arias, Emilio Jesús Gallego; Hsu, Justin; Roth, Aaron; Strub, Pierre-Yves
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
45.95%
In mechanism design, the gold standard solution concepts are dominant strategy incentive compatibility, and Bayesian incentive compatibility. These simple solution concepts relieve the (possibly unsophisticated) bidders from the need to engage in complicated strategizing. This is a clean story when the mechanism is "obviously" incentive compatible, as with a simple second price auction. However, when the proof of incentive compatibility is complex, unsophisticated agents may strategize in unpredictable ways if they are not convinced of the incentive properties. In practice, this concern may limit the mechanism designer to mechanisms where the incentive properties are obvious to all agents. To alleviate this problem, we propose to use techniques from computer-aided verification to construct formal proofs of incentive properties. Because formal proofs can be automatically checked, agents do not need to manually verify or even understand complicated paper proofs. To confirm the viability of this approach, we present the verification of one sophisticated mechanism: the generic reduction from Bayesian incentive compatible mechanism design to algorithm design given by Hartline, Kleinberg, and Malekian. This mechanism presents new challenges for formal verification...

Mechanism Design in the Case of Two Objects with the Possibility for Complementarities

Varma, Avtar
Fonte: Universidade Duke Publicador: Universidade Duke
Publicado em 18/04/2011 EN_US
Relevância na Pesquisa
55.8%
This research builds upon existing studies in that it investigates the possibility of expanding the mathematical and theoretical models of FPSB auctions, along with a slightly altered versions of this auction format, into a linear program in order to solve it with numerical techniques. The output generated from the linear optimization model suggests that the auction mechanisms being used today for the sale of multiple objects with complementarities may well be inefficient in maximizing seller’s revenue. The results further establish a basis for comparison of equilibrium surplus from the seller’s perspective in the case of an auction with two complementary objects. Moreover, the analytical and numerical results herein serve as a building block for future research examining different mechanism designs that will maximize seller revenue in a given auction.; Honors Thesis

School Choice: A Mechanism Design Approach

Abdulkadiroglu, Atila; Sonmez, Tayfun
Fonte: American Economic Association Publicador: American Economic Association
Tipo: Artigo de Revista Científica Formato: 1928086 bytes; application/pdf
Publicado em //2003 EN_US
Relevância na Pesquisa
55.89%
A central issue in school choice is the design of a student assignment mechanism. Education literature provides guidance for the design of such mechanisms but does not offer specific mechanisms. The flaws in the existing school choice plans result in appeals by unsatisfied parents. We formulate the school choice problem as a mechanism design problem and analyze some of the existing school choice plans including those in Boston, Columbus, Minneapolis, and Seattle. We show that these existing plans have serious shortcomings, and offer two alternative mechanisms each of which may provide a practical solution to some critical school choice issues.

Coordination Mechanism Design for Sustainable Global Supply Networks

Liu, Fang
Fonte: Universidade Duke Publicador: Universidade Duke
Tipo: Dissertação
Publicado em //2011
Relevância na Pesquisa
65.89%

This dissertation studies coordination mechanism design for sustainable supply networks in a globalized environment, with the goal of achieving long-term profitability, environmental friendliness and social responsibility. We examine three different types of supply networks in detail.

The first network consists of one supplier and multiple retailers. The main issue is how to efficiently share a scarce resource, such as capacities for green technology, among all members with private information under dynamically changing environment. We design a shared surplus supply agreement among the members which can lead to both efficient private investments and efficient capacity allocation under unpredictable and unverifiable market conditions.

The second network is a serial supply chain. The source node provides critical raw material (like coffee cherries) for the entire chain and is typically located in an underdeveloped economy, the end node is a retailer serving consumer at a developed economy (like Starbucks Co.). We construct a dynamic supply agreement that takes into account the changing market and production conditions to ensure fair compensations so that the partners have the right incentives to work together to develop sustainable quality supply.

The third network is a stylized global production network of a multinational company consisting of a home plant and a foreign branch. The branch serves the foreign market but receives a key component from the home plant. The distinctive feature is that both facilities belong to the same company...

Computationally Feasible Approaches to Automated Mechanism Design

Guo, Mingyu
Fonte: Universidade Duke Publicador: Universidade Duke
Tipo: Dissertação
Publicado em //2010
Relevância na Pesquisa
66.05%

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...

Network Extenality and Mechanism Design

Xu, Xiaoming
Fonte: Universidade Duke Publicador: Universidade Duke
Tipo: Dissertação
Publicado em //2015
Relevância na Pesquisa
65.96%

\abstract

{\em Mechanism design} studies optimization problems taking into accounts of the selfish agents. {\em Network externality} is the effect a consumer receives from other consumers of the same good. This effect can be negative or positive. We first consider several mechanism design problems under the network externality assumption. The externality model used in this dissertation is more general than the widely used cardinality based model. In particular the network we consider in this dissertation is a graph, which is not necessarily complete. Our goal is to design {\em truthful} mechanisms to maximize the seller's revenue. Our main results under the network externality utility model are several optimal or near optimal mechanisms for {\em digital goods auctions}. To do so we invent several novel approximation schemes as well as applying results from the {\em approximation algorithm} literature. In particular when the agents exhibit negative network externality, we first model the problem as a two staged {\em pricing game}. We then show that the pricing game is an exact {\em potential game} which always admits a pure {\em Nash Equilibrium}. We then study the {\em best} and {\em worst} Nash Equilibrium in this game in terms of the revenue. We show two positive results. For the best Nash Equilibrium we show a $2$-approximation to the maximum revenue on bipartite graphs. For the worst Nash Equilibrium we use the notion of a {\em $\delta$-relaxed} equilibrium. In the sense that the prices for the same type of agents are within $\delta$ factor of each other. We accompany our positive results with matching hardness results. On the other hand...