= 27d567bc2d48d9f40e9ccc20ea370b15)
In addition to red and yellow
I believe "red and blue" is meant.
In response to
Strategyproof Mechanisms: Impossibilities
Thanks. Fixed.
In response to
Strategyproof Mechanisms: Impossibilities
My cursory understanding is that none of these proofs apply to rating systems, only ranking systems, correct?
Arrow's theorem doesn't apply to rating systems like approval or range voting. However, Gibbard-Satterthwaite still holds. It holds more intensely if anything since agents have more ways to lie. Now you have to worry about someone saying their favorite is ten times better than their second favorite rather than just three times better in addition to lying about the order.
Strategyproof Mechanisms: Impossibilities
In which the limits of dominant-strategy implementation are explored. The Gibbard-Satterthwaite dictatorship theorem for unrestricted preference domains is stated, showing no universal strategyproof mechanisms exist, along with a proof for a special case.
Due to the Revelation Principle, most design questions can be answered by studying incentive compatible mechanisms, as discussed in the last post. Incentive compatibility comes in many different flavors corresponding to different solution concepts—dominant-strategy IC and Bayes-Nash IC being the two most common. In this post, I’ll delve into what’s possible under dominant strategy incentive compatibility.
Recall that a strategy is dominant if playing it always leads to (weakly) higher payoffs for an agent than other strategy would, no matter what strategies other agents play. A social choice function is dominant-strategy incentive compatible if honest revelation is a dominant strategy in the direct mechanism for that SCF1. The appeal of implementation in dominant strategies is that an agent doesn't need to think about what other agents will do. Even in the worst case, a dominant-strategy IC social choice function leaves an agent better off for being honest. Since the need for strategic thinking is eliminated, dominant-strategy IC is also referred to as strategyproofness.
Gibbard-Satterthwaite: universal strategyproof mechanisms are out of reach
Arrow’s theorem is well-known for showing dictatorships are the only aggregators of ordinal rankings that satisfy a set of particular criteria. The result is commonly interpreted as saying there is no perfect voting system for more than two candidates. However, since Arrow deals with social welfare functions which take a profile of preferences as input and outputs a full preference ranking, it really says something about aggregating a set of preferences into a single group preference. Most of the time though, a full ranking of candidates will be superfluous—all we really need to know is who wins the election. Although Arrow doesn’t give social welfare functions much room to maneuver, maybe there are still some nice social choice functions out there.
Alas, it’s not to be. Alan Gibbard and Mark Satterthwaite have shown that, in general, the only strategyproof choice from three or more alternatives that is even slightly responsive to preferences is a dictatorship by one agent.
The maximum amount of deliberate practice you can get in a day tops out at 3-4 hours, according to K. Anders Ericsson.
Do you have a link?
See pg. 391-392 of The Role of Deliberate Practice in the Acquisition of Expert Performance, the paper that kicked off the field. A better summary is that 2-4 hours is the maximum sustainable amount of deliberate practice in a day.
In response to
[Sequence announcement] Introduction to Mechanism Design
It'd be nice if you could go over why you think you'd be a good candidate to cover the subject.
I'm a PhD student working in this field and have TA'd multiple years for a graduate course covering this material.
In response to
Incentive compatibility and the Revelation Principle
I believe you have a typo in this section with the subscripts:
If the sum of the two reports θJack + θJill is at least $300, the room will be painted. Jack’s payment will be pJack = 300 − θJill if the room is painted and zero otherwise. Similarly, Jill’s payment will be pJill = 300 − θJill when the room is painted and zero otherwise.
If Jill reports between $150 and $180, the room is painted and Jack gets a payoff of 120 − (300 − θJill) = θJill − 180 < 0, less than his payoff from honesty where the room isn’t painted.
When the room is painted, Jack and Jill have a $300 bill, but the mechanism only collects 300 − θJack + 300 − θJill < 300.
If pJack = 300 − θJill and pJill = 300 - θJill, then the mechanism should be collecting 600 - 2*θJill?
So it turns out that the reason none of the solutions I tried in the last article worked is because it's impossible for solutions to exist that satisfy the implicit restrictions I was putting on solutions. That's interesting. It's too bad that the second-best solution is so relatively crappy. Realistically, it doesn't seem to be any better than just negotiating with someone in the more traditional manner, and accepting that you may not end up revealing your true preferences.
Typo fixed now. Jill's payment should be p_Jill = 300 - p_Jack.
The second-best direct mechanisms do bite the bullet and assume agents would optimally manipulate themselves if the mechanism didn't do it for them. The "bid and split excess" mechanism I mention at the very end could be better if people are occasionally honest.
I'm now curious what's possible if agents have some known probability of ignoring incentives and being unconditionally helpful. It'd be fairly easy to calculate the potential welfare gain by adding a flag to the agent's type saying whether they are helpful or strategic and yet again applying the revelation principle. The trickier part would be finding an useful indirect mechanism to match that, since it'd be painfully obvious that you'd get a smaller payoff for saying you're helpful under the direct mechanism.
In response to
Incentive compatibility and the Revelation Principle
Still not quite grokking the Revelation Principle, although that's probably a function of inexperience with these kinds of problems. Is the idea that if I can assume or establish the sufficient properties of the players' utility functions then I can assume they announce their types to me, the mechanism designer, and proceed with design on that basis?
I added some explanation right after the diagram to clarify. The idea is that if I can design a game where players have dominant strategies, then I can also design a game where they have a dominant strategy to honestly reveal their types to me and proceed on that basis.
Incentive compatibility and the Revelation Principle
In which the Revelation Principle is introduced, showing all mechanisms can be reduced to incentive compatible mechanisms. With this insight, a solution (of sorts) is given to the public good problem in the last post. Limitations of the Revelation Principle are also discussed.
The formalism I introduced last time will now start paying off. We were left with the question of how to check whether a mechanism exists that satisfies some particular goal, naively requiring us to search over all possible procedures. Luckily though, the space of all possible mechanisms can be reduced to something manageable.
Observe the following: suppose through divine intervention we were granted a mechanism (M, g) that implements a social choice function f. In other words, the outcome when agents of types θ1, …, θn interact with the mechanism is exactly the outcome prescribed by the function f for those types. Since a person’s type encodes all relevant variation in their characteristics, preferences, or beliefs, we’d know what that person wants to do if we knew their type. In particular, when agent i is type θi, we expect her choice of message to be mi(θi). Once all the messages are sent, the function g translates the agents’ choices into an outcome so that g(m1(θ1), …, mn(θn)) = f(θ1, …, θn).
But wait! Since we expect a type θi agent to send message mi(θi), why don’t we just package that inside the mechanism? Each agent will tell us their type and the mechanism designer will play in proxy for the agent according to the original mechanism. We’ll call this the direct mechanism for f since all we need to know is that agents tell us their types and then are assigned outcome f(θ), no matter what we’ve blackboxed in the middle.
Oh, and now that I'm going over it more carefully, another nitpick: You don't seem to actually define the notation Π_i before using it in the definition of a social choice function, and it isn't clear (to me) from context what it's supposed to mean.
That's an indexed Cartesian product, analogous to sigma notation for indexed summation, so is the set of all vectors of agent types.
= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
= f037147d6e6c911a85753b9abdedda8d){kind=logo}
I'm going to nitpick here -- it's possible to write down forms of Arrow's theorem where you do get a single output. Of course, in that case, unlike in the usual formulation, you have to make assumptions about what happens when candidates drop out -- considering what you have as a voting system that yields results for an election among any subset of the candidates, rather than just that particular set of candidates. So it's a less convenient formulation for proving things. Formulated this way, though, the IIA condition actually becomes the thing it's usually paraphrased as -- "If someone other than the winner drops out, the winner stays the same."
Edit: Spelling
Since Arrow and GS are equivalent, it's not surprising to see intermediate versions. Thanks for pointing that one out. I still stand by the statement for the common formulation of the theorem. We're hitting the fuzzy lines between what counts as an alternate formulation of the same theorem, a corollary, or a distinct theorem.