Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

Comment author: Manfred 05 June 2014 11:00:43PM 1 point [-]

Poor Cato.

Cato swapping with Brutus produces the same absolute gains as Antonius swapping with Brutus - is there a strategyproof mechanism that goes that way instead?

How about "a soldier can signal that they don't have the job they want. Then, the people who want to change jobs are ordered into a random loop, and jobs are rotated one place."

Hm, but if Antonius doesn't want his job either, we could end up with a bad outcome. Is Cato really hosed?

Comment author: badger 11 June 2014 02:10:32PM 1 point [-]

It turns out the only Pareto efficient, individually rational (ie everyone never gets something worse than their initial job), and strategyproof mechanism is Top Trading Cycles. In order to make Cato better off, we'd have to violate one of those in some way.

Strategyproof Mechanisms: Possibilities

22 badger 02 June 2014 02:26AM

Despite dictatorships being the only strategyproof mechanisms in general, more interesting strategyproof mechanisms exist for specialized settings. I introduce single-peaked preferences and discrete exchange as two fruitful domains.

Strategyproofness is a very appealing property. When interacting with a strategyproof mechanism, a person is never worse off for being honest (at least in a causal decision-theoretic sense), so there is no need to make conjectures about the actions of others. However, the Gibbard-Satterthwaite theorem showed that dictatorships are the only universal strategyproof mechanisms for choosing from three or more outcomes. If we want to avoid dictatorships while keeping strategyproofness, we’ll have to narrow our attention to specific applications with more structure. In this post, I’ll introduce two restricted domains with more interesting strategyproof mechanisms.

continue reading »
Comment author: edanm 26 May 2014 02:23:09PM 13 points [-]

Reading "The Selfish Gene" teaches enough evolutionary biology to understand what the field is about, to understand the basics of the field, and to be able to converse on it intelligently.

What book can I read that will do the same for me in:

  • Medicine/biology/physiology (e.g. able to understand the very basic concepts of what a doctor does)

  • Law (e.g. able to understand the very basic concepts of working as a lawyer).

Bonus points - if the book on Law explains the practical difference between common-law and civil-law.


Comment author: badger 27 May 2014 09:43:10PM 9 points [-]

Metafilter has a classic thread on "What book is the best introduction to your field?". There are multiple recommendations there for both law and biology.

Comment author: Vaniver 17 May 2014 04:24:20PM 4 points [-]

Um, not quite:

In addition to red and red

Very Henry Ford-ish.

Comment author: badger 17 May 2014 04:36:25PM 0 points [-]


Comment author: Sniffnoy 16 May 2014 04:33:55AM *  2 points [-]

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.

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

Comment author: badger 16 May 2014 12:46:36PM 2 points [-]

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.

Comment author: Isaac_Davis 16 May 2014 11:39:44AM 1 point [-]

In addition to red and yellow

I believe "red and blue" is meant.

Comment author: badger 16 May 2014 12:15:01PM 0 points [-]

Thanks. Fixed.

Comment author: trist 16 May 2014 03:21:54AM 1 point [-]

My cursory understanding is that none of these proofs apply to rating systems, only ranking systems, correct?

Comment author: badger 16 May 2014 04:09:24AM 3 points [-]

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

14 badger 16 May 2014 12:52AM

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.

continue reading »
Comment author: Lumifer 06 May 2014 04:03:54PM 1 point [-]

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?

Comment author: badger 06 May 2014 04:46:37PM 2 points [-]

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.

Comment author: cursed 04 May 2014 05:33:17AM 1 point [-]

It'd be nice if you could go over why you think you'd be a good candidate to cover the subject.

Comment author: badger 05 May 2014 11:33:52PM 1 point [-]

I'm a PhD student working in this field and have TA'd multiple years for a graduate course covering this material.

View more: Next