[HN Gopher] Gibbard's Theorem vs. Stable Matching
___________________________________________________________________
Gibbard's Theorem vs. Stable Matching
Author : gbrown_
Score : 57 points
Date : 2021-06-03 09:10 UTC (1 days ago)
(HTM) web link (cdsmithus.medium.com)
(TXT) w3m dump (cdsmithus.medium.com)
| dane-pgp wrote:
| > Gibbard's theorem assumes that each participant has a set of
| preferences about the _entire_ outcome of the process. In this
| case, the outcome of the process is the matching of _all_
| candidates to _all_ positions.
|
| Doesn't this mean it's actually not very applicable to voting
| systems?
|
| Voters generally only care whether their preferred candidate
| comes first, not about the relative ordering of the other
| candidates.
|
| I suppose a voter might care how close their preferred candidate
| came to winning (or their margin of victory), but that's still a
| slightly weaker requirement than having a total ordering of all
| candidates relative to each other.
| cdsmith wrote:
| Author here. No, it doesn't mean that. If the election is held
| to determine who wins, then the outcome is who wins, and
| everyone has opinions about that same outcome.
|
| Contrast this to the matching problem, where the outcome is
| where ALL the candidates are assigned. You're allowed to have
| an opinion about where _you_ are assigned. I 'm allowed to have
| an opinion about where _I_ am assigned. These opinions might
| conflict indirectly because of limited spots, but they don 't
| conflict directly. This is very different from the election
| case, where if you and I have different opinions about who we
| want to win, those opinions are always contradictory.
| dane-pgp wrote:
| What if an election is held to determine a set of two
| "finalists"? People might disagree about who the top two
| candidates are, but they might be satisfied as long as one of
| their top preferences makes it through to the second round.
|
| Obviously once there are two candidates remaining, Gibbard's
| Theorem doesn't apply, so I'm guessing that any procedure
| which reduces the set to two outcomes must itself be subject
| to strategy, but it would be interesting if allowing people
| to cast a separate vote in a run-off election was enough to
| make the first round no longer require strategy.
| bo1024 wrote:
| There are versions of Gibbard's theorem for outputting a single
| winner too. The famous one is Gibbard-Satterthwaite:
| https://en.wikipedia.org/wiki/Gibbard%E2%80%93Satterthwaite_...
| svcphr wrote:
| You can have weak inequalities in the preferences over
| alternatives -- e.g. you're indifferent between all rankings
| where your preferred candidate is number 1
| bo1024 wrote:
| The final note is important, otherwise the statement of Roth's
| result is misleading. The X-proposing version of deferred
| acceptance is strategyproof for X's, but not for the other side
| (the Y's). For example in the national residency matching
| program, it's (roughly) strategyproof for doctors but not for
| hospitals.
| bhl wrote:
| When I was taught stable matching, there was a homework problem
| on showing that the algorithm is "proposer-optimal" and
| "proposee-pessimal", meaning that a proposer always does the
| best they can do relative to other proposers' preferences while
| proposees do the worst.
|
| The crucial part here is how big is the gap between a
| proposee's worst and best match: if the gap is null for all
| proposees, there isn't any strategic incentive for one to lie
| about their preferences. However, that obviously is a very hard
| requirement.
___________________________________________________________________
(page generated 2021-06-04 23:02 UTC)