Questions tagged [mechanism-design]

Mechanism design is a field in economics and game theory that takes an engineering approach to designing economic mechanisms or incentives, toward desired objectives, in strategic settings, where players act rationally.

Filter by
Sorted by
Tagged with
14
votes
2answers
3k views

Available code for computing solutions to matching algorithms?

The question of designing matching procedure (between high-schools and students, med intern and hospitals, kidney donors and receivers,...) has been widely studied by economists and vastly contributed ...
13
votes
3answers
25k views

What is the definition of "First Best", "Second Best", etc. in contract theory?

What is the definition of "First Best", "Second Best", etc. in contract theory? Especially, what is the difference between "First Best" in contract theory and "ex-post efficient" in mechanism design?
13
votes
2answers
1k views

What is the difference between contract theory and mechanism design?

Can someone explain the difference between contract theory and mechanism design?
11
votes
1answer
296 views

How does Google price the items on Google Play?

I am a fledgling computer science researcher working in intersection of economics and computation. Please excuse me if this question seems out of place to the administrator. I am currently studying ...
7
votes
2answers
1k views

What is virtual valuation?

I’m reading through a textbook in auction design when it describes a term, virtual valuation $$\phi_i(v_i) = v_i - \frac{1 - F(v_i)}{f(v_i)}$$ where $f$ is the pdf of a bidders valuation and $F$ is ...
7
votes
2answers
2k views

Code finding all stable matchings in one-to-one problem

Do you know of any publicly available code in python or R (or any other free high level language) that returns all the stable matchings for any one-to-one matching problem? Note: This is related but ...
6
votes
2answers
78 views

Auction theory reference request

I am interested in finding the literature or at least some references (books, journal papers etc.) for the following problem: Suppose there is an auction with one seller and one buyer. The seller ...
6
votes
1answer
295 views

What types of 'market mechanisms' are said to exist besides auctions?

The book Understanding Auctions states: The term auction covers a wide range of market mechanisms that are used to exchange products and services by determining who receives an item and how much is ...
6
votes
1answer
71 views

Any study on performance gap between optimal mechanism and linear mechanism?

In mechanism design, the optimal mechanism is usually not linear in the agent's type. However, linear mechanisms are easy for implementation. Are there any studies on the performance comparison ...
5
votes
4answers
304 views

Multi-item Auctions in Mechanism Design

I'm new to auction theory and only started reading it a few days ago. My question is this: Is it possible to design efficient auctions of multiple non-identical items? By efficient I mean maximize the ...
5
votes
1answer
83 views

Screening theory: Bundling problem

Consider an example of a risk-neutral seller that has two distinct indivisible goods for sale. The seller wants to maximize the expected revenue. The buyer's utility is $$I_av_a+I_bv_b-t,$$ where $I_a,...
5
votes
2answers
231 views

Are direct mechanisms always truthful?

I am very new to mechanism design so I am a bit lost among the concepts, even the most basic ones. One thing that is not clear to me is the concept of direct mechanism and its relationship with the ...
5
votes
2answers
158 views

Bayesian Mechanism vs Prior-free Mechanism

I have a double auction mechanism in which the valuations of the agents for the items are drawn from a known random distribution. To be precise, the valuations are the probability of each agent ...
5
votes
1answer
130 views

Incentive compatibility

I have a set of objects $A=\{a_1,a_2,a_3,\cdots,a_m\}$ and one player, who proposes a vector of valuations $t=(t_1~t_2~t_3~\cdots~t_m)$ for the $m$ objects. $T$ is the set of all such valuation types. ...
5
votes
2answers
72 views

Approximately Optimal Mechanism Design vs. Revelation Principle

The abstract of the article "Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations" (Dobzinski, Vondrak, 2016) states A long-standing open question in algorithmic ...
5
votes
1answer
375 views

Checking incentive compatibility of a mechanism

I was thrilled at seeing an interesting bidding system in an academic institutions. This bidding is for registration of courses. Each student is allocated some points based on her grade point(GPA). So,...
4
votes
1answer
94 views

Payoff from an option contract

In period 1 the consumer of type $\theta$ selects an option contract consisting of an up-front fee, $B>0$, and exercise price, $\bar{R}$. The consumer pays $B$ at the end of the first period. In ...
4
votes
1answer
478 views

Ex-post vs Ex-ante Budget Balance in Auctions

Have I understood this correctly? When I say my auction mechanism is ex-post budget balanced it means that in practice (I have done market simulations) and according to the results my mechanism is ...
4
votes
2answers
84 views

What does commitment in adverse selection mean?

In this slide deck, p15. it says "The revelation principle requires that the principal can fully commit to the terms of the contract. If this is not the case, an indirect mechanism, which allows for ...
4
votes
1answer
35 views

Incentive compatibilty conditions for multi-item auctions

In this paper by Myerson on optimal single item auctions, the incentive compatibility condition is shown to be equivalent to the following simpler conditions on the auction - (i) the allocation ...
4
votes
2answers
929 views

Computing Boston and TTC in Python

This is somewhat of a follow up question to Available code for computing solutions to matching algorithms?. In the above question, I got great answers, but all of them were for ...
4
votes
1answer
85 views

How to improve the underperforming construction productivity by correcting its market failures?

Globally, labor-productivity growth in construction has averaged only 1 percent a year over the past two decades, compared with growth of 2.8 percent for the total world economy and 3.6 percent in the ...
4
votes
0answers
39 views

VCG mechanism with a minimum payment threshold

Suppose that we want to find a socially-optimal allocation in the following setting: There are $n$ firms and $m$ workers. Each firm $i$ needs one worker and has value $v_i$ for having a worker (any ...
4
votes
0answers
50 views

Taking a mechanism as given, what goal functions can we implement?

Let $\theta_i$ be $i$'s private information about the state of the world, $\theta \in \Theta$, where $\theta = \times_i \theta_i$. Each agent reports $\hat{\theta_i}$ to a social planner, so that $\...
3
votes
2answers
124 views

What's the difference between Ex-post Incentive Compatibility and Dominant-Strategy Incentive Compatibility

According to the Wikipedia definition of Dominant-Strategy Incentive Compatibility (DSIC): DSIC means truth-telling is a weakly-dominant strategy, i.e. you fare best or at least not worse by being ...
3
votes
2answers
129 views

Mechanism Design: Proving that the expected utility is differentiable

Given a direct mechanism, we define a buyer's expected utility $u(\theta)$ conditional on her type being $\theta$ by $u(\theta)=\theta q(\theta)-t(\theta)$, where $q:[\underline{\theta},\bar{\theta}]\...
3
votes
3answers
132 views

Bidder Count Impact on Uniform Price Economics

Say we have an uniform price auction where 1 really rare stamp is for sale. Only 5 randomly selected stamp collectors are invited to bid and the stamp ends up selling for 1 million dollars. Now ...
3
votes
2answers
86 views

Derivation on p.99 of Salanie, The Economics of Taxation (2nd edition)

Starting on p. 98 of Salanie's "The Economic of Taxation" (2nd edition), it explains To probe it more rigorously, let us define the utility of taxpayer $w$ when he claims to have productivity $w'$: ...
3
votes
2answers
50 views

Mechanism design when the set of feasible decisions depends on types

Q : Can the tools of mechanism design be applied when the set of feasible decisions $D$ depends on the types $\theta$? For example, when $d \in D$ represents the total funding allocated toward some ...
3
votes
1answer
53 views

VCG mechanism and budget balance

I have a general question on how we state that in VCG (which doesn't balance the budget) we can't distribute the money as it will destroy incentives. I don't understand how for ex. this would affect ...
3
votes
1answer
103 views

Is VCG mechanism applicable in reverse auction? If so, how?

The VCG mechanism I've learnt is from Roughgarden's Twenty Lectures on Algorithmic Game Theory. Given an auction, we first identify the allocation that maximize the social welfare and then compute the ...
3
votes
1answer
93 views

Direct revelation mechanism's sets of strategies and types

Mas-Colell, Whinston and Green in Microeconomic Theory describe the direct revelation mechanism as it follows: The employed notation is the following: $θ_i$: Player i's type $Θ_i$: Set of types for ...
3
votes
1answer
81 views

Non-Bayesian Mechanism Design

Suppose we have a mechanism where a finite number of agents possess private information that is not drawn from a probability distribution. The agents' types are given and fixed but agents only know ...
3
votes
1answer
165 views

AGV mechanism and Individual rationality

I have the following question. I consider AGV mechanism which is as follows: $u_i(x,\theta_i) = v_i(k,\theta_i) + t_i $ is an utility function where $x = (k,t_1,...,t_n)$ vector of alternatives. There ...
3
votes
1answer
129 views

Help needed to understand proof in Myerson and Satterthwaite (1983)

The following image is an excerpt taken from Myerson and Satterthwaite's 1983 paper Efficient Mechanisms for Bilateral Trading: I know what the theorem is all about, all I need is some help with the ...
3
votes
1answer
283 views

Marginal Revenue Interpretation of Auctions

I'm reading Klemperer's survey on auction theory (pages 17-18) which discusses the relation between traditional microeconomic price theory and the revenue equivalence result. Firstly, I don't quite ...
3
votes
1answer
91 views

Decentralized Mechanism Design

From what I've read in mechanism design theory, it seems to me that the mechanism designer always plays an essential role in a mechanism. Information is sent to the designer who designs incentives ...
3
votes
1answer
95 views

Is Myerson's Lemma valid for piecewise linear allocation functions?

In Tim Roughgarden's fantastic course on Algorithmic Game Theory, he begins the course by introducing basic mechanism design, and Myerson's Lemma. He then proves that Myerson's Lemma is valid for ...
3
votes
1answer
135 views

Does the VCG algorithm work for any bundle valuation function?

Assume we have $n$ buyers of $|M|=m$ items in a combinatorial auction. So as we know, we can use the Vickrey-Clarke-Groves (VCG) algorithm to allocate bundles of items to buyers as best as possible. ...
3
votes
1answer
70 views

Is there an algorithm to find as many NE as possible in this generalized second price auction?

Suppose three advertisers, I, II, III are participating in an auction for three positions for online advertising, top, middle and bottom. Assume that click per second for a position is not affected ...
2
votes
1answer
48 views

Can you please help me find this topic in Mechanism design/Rational choice theory?

When I was in university, I remember studying some kind of topic in adv microeconomics where someone gives you three options, where one is obviously worse and is put there just to deceive you so that ...
2
votes
1answer
102 views

The influence of restricted type space on incentive compatible mechanism design?

When we are to design an IC mechanism for an auction, we usually assume that each agent $i$'s type $\theta_i$ is draw from its type space $\Theta_i$, which contains all the possible types of $i$. For ...
2
votes
1answer
52 views

Difference between social choice function and mechanism outcome function

Mas-Colell, Whinston and Green's Microeconomic Theory (3rd edition) defines the social choice function as the following: Later, the mechanism outcome function is also defined: The relationship ...
2
votes
1answer
99 views

Incentive compatibility: Weakly dominant strategy versus Nash equilibrium?

When it comes to proving that a mechanism e.g. auction is incentive compatible this is the approach I'm using: I break down all the cases that might happen if the agent reports an untruthful value to ...
2
votes
1answer
22 views

locating specific model from organizational economics

I am trying to find one specific model from organizational economics that I encountered in one of my past classes, but I cant remember the name of the model and google scholar search based on some of ...
2
votes
2answers
41 views

Multi-item multi-unit matching markets

This is a reference request. I'm interested in auction design problems of the following form: - Consider one seller and many buyers. - The seller seeks to sell multiple items where each item has ...
2
votes
1answer
320 views

Question on uncertainity

Please imagine that Nicole is uncertain of her future wealth. Her wealth in the bad state of the world is zero. Her wealth in the good state is $w>0$. Each state is initially equally likely. ...
2
votes
1answer
93 views

Allocating chores using auctions

I live in a student dorm with 16 people and we share a kitchen. Every week someone has to clean the kitchen. Right now we just take turns in a way determined by the numbers of our respective rooms. ...
2
votes
1answer
50 views

Bayesian incentive compatibility for a general distribution

Suppose there are $n$ bidders and a seller. Bidder $i$ observes a private signal $v_i$ from $[a,b]$. Let $\mathcal{X} = \times_{i=1}^n[a,b]$ Each bidder is represented by a random variable, that has a ...
2
votes
1answer
99 views

Monotonicity of second price auctions with bidder-specific reserve prices

I am having difficulty understanding the problem below: Given CDFs $F_1, ..., F_n$, prove that the allocation rule of a second-price auction with bidder-specific reserve prices is monotone. The item ...