Strategy-proofness of social choice function in two dimensions
$begingroup$
Suppose the allocation space is the unit square $A=[0,1] times [0,1] in mathbb{R}^2$. The outcome is a single point $xin A$. Assume all agents have single-peaked preferences. That is, each agent $i$ has a preference ordering $succeq_i$ over the outcomes; there exists a point $p_i=(x_i, y_i) in A$ such that for all $xin A setminus {p_i}$ and all $lambda in [0,1)$, we have $(lambda x + (1 − lambda)p_i) succ_i x$.
The social choice $f$ takes in the agents' preferences $(succeq_1,dots,succeq_n)$, and output $xin A$.
Why is the function $f(succeq_1,dots,succeq_n)=(x_i,y_i)$ where $x_i$ and $y_i$ are the medians of the $x$ and $y$ coordinates, respectively, not strategy-proof?
What I think: In one dimension, we know that the median scheme is strategy-proof. I don't see how taking the median over each dimension is not?
game-theory algorithmic-game-theory social-choice-theory
asked Dec 4 '17 at 18:54
user3727610user3727610
18919
$endgroup$
add a comment |
$begingroup$
Suppose the allocation space is the unit square $A=[0,1] times [0,1] in mathbb{R}^2$. The outcome is a single point $xin A$. Assume all agents have single-peaked preferences. That is, each agent $i$ has a preference ordering $succeq_i$ over the outcomes; there exists a point $p_i=(x_i, y_i) in A$ such that for all $xin A setminus {p_i}$ and all $lambda in [0,1)$, we have $(lambda x + (1 − lambda)p_i) succ_i x$.
The social choice $f$ takes in the agents' preferences $(succeq_1,dots,succeq_n)$, and output $xin A$.
Why is the function $f(succeq_1,dots,succeq_n)=(x_i,y_i)$ where $x_i$ and $y_i$ are the medians of the $x$ and $y$ coordinates, respectively, not strategy-proof?
What I think: In one dimension, we know that the median scheme is strategy-proof. I don't see how taking the median over each dimension is not?
game-theory algorithmic-game-theory social-choice-theory
asked Dec 4 '17 at 18:54
user3727610user3727610
18919
$endgroup$
add a comment |
$begingroup$
Suppose the allocation space is the unit square $A=[0,1] times [0,1] in mathbb{R}^2$. The outcome is a single point $xin A$. Assume all agents have single-peaked preferences. That is, each agent $i$ has a preference ordering $succeq_i$ over the outcomes; there exists a point $p_i=(x_i, y_i) in A$ such that for all $xin A setminus {p_i}$ and all $lambda in [0,1)$, we have $(lambda x + (1 − lambda)p_i) succ_i x$.
The social choice $f$ takes in the agents' preferences $(succeq_1,dots,succeq_n)$, and output $xin A$.
Why is the function $f(succeq_1,dots,succeq_n)=(x_i,y_i)$ where $x_i$ and $y_i$ are the medians of the $x$ and $y$ coordinates, respectively, not strategy-proof?
What I think: In one dimension, we know that the median scheme is strategy-proof. I don't see how taking the median over each dimension is not?
game-theory algorithmic-game-theory social-choice-theory
asked Dec 4 '17 at 18:54
user3727610user3727610
18919
$endgroup$
Suppose the allocation space is the unit square $A=[0,1] times [0,1] in mathbb{R}^2$. The outcome is a single point $xin A$. Assume all agents have single-peaked preferences. That is, each agent $i$ has a preference ordering $succeq_i$ over the outcomes; there exists a point $p_i=(x_i, y_i) in A$ such that for all $xin A setminus {p_i}$ and all $lambda in [0,1)$, we have $(lambda x + (1 − lambda)p_i) succ_i x$.
The social choice $f$ takes in the agents' preferences $(succeq_1,dots,succeq_n)$, and output $xin A$.
Why is the function $f(succeq_1,dots,succeq_n)=(x_i,y_i)$ where $x_i$ and $y_i$ are the medians of the $x$ and $y$ coordinates, respectively, not strategy-proof?
What I think: In one dimension, we know that the median scheme is strategy-proof. I don't see how taking the median over each dimension is not?
game-theory algorithmic-game-theory social-choice-theory
game-theory algorithmic-game-theory social-choice-theory
asked Dec 4 '17 at 18:54
user3727610user3727610
18919
asked Dec 4 '17 at 18:54
user3727610user3727610
18919
asked Dec 4 '17 at 18:54
user3727610user3727610
18919
asked Dec 4 '17 at 18:54
user3727610user3727610
18919
asked Dec 4 '17 at 18:54
user3727610user3727610
18919
18919
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Your condition is not strong enough to enforce structure on the preferences that result. For example, with three options (say (0,0), (1,0), and (0,1)) a voter could have any linear preference over these options (even if his "peak" was fixed at say (1,1)). Thus, impossibility results such as Arrow’s Theorem and Gibbard–Satterthwaite will apply.
One variant you could try to fix this situation is define your peaks "coordinatewise", i.e. options are preferred less if both their coordinates are further from the "peak". However, you can check that this still allows all preferences on (0,0), (1,0), and (0,1), all with peak (0.5, 0.5).
In general, the test "are all preferences on three options possible" is probably a good litmus test for whether "good" voting schemes will exist (at least for the more basic definitions of "good").
answered Dec 13 '18 at 5:02
Clay ThomasClay Thomas
1406
$endgroup$
add a comment |
$begingroup$
In one dimension, under the median scheme, manipulating your preference peak doesn't get you anything: If you feign a peak on the side of the median where your peak actually lies, that doesn't change the median, and if you feign a peak on the other side, that only pulls the median even further away from your peak.
In more than one dimension, however, you might get a better result by shifting the result's $x$ coordinate further away from your peak's $x$ coordinate – while that causes the result to end up further away from your acutal peak, you're then on a different line $lambda x + (1 − lambda)p_i$, which might be more favourable to you, since nothing in the premise constrains the relative ordering of points along different lines through the peak, so a point on one line further from the peak might be preferable to a point on another line closer to the peak.
answered Jun 6 '18 at 1:37
jorikijoriki
171k10188348
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2550974%2fstrategy-proofness-of-social-choice-function-in-two-dimensions%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Your condition is not strong enough to enforce structure on the preferences that result. For example, with three options (say (0,0), (1,0), and (0,1)) a voter could have any linear preference over these options (even if his "peak" was fixed at say (1,1)). Thus, impossibility results such as Arrow’s Theorem and Gibbard–Satterthwaite will apply.
One variant you could try to fix this situation is define your peaks "coordinatewise", i.e. options are preferred less if both their coordinates are further from the "peak". However, you can check that this still allows all preferences on (0,0), (1,0), and (0,1), all with peak (0.5, 0.5).
In general, the test "are all preferences on three options possible" is probably a good litmus test for whether "good" voting schemes will exist (at least for the more basic definitions of "good").
answered Dec 13 '18 at 5:02
Clay ThomasClay Thomas
1406
$endgroup$
add a comment |
$begingroup$
Your condition is not strong enough to enforce structure on the preferences that result. For example, with three options (say (0,0), (1,0), and (0,1)) a voter could have any linear preference over these options (even if his "peak" was fixed at say (1,1)). Thus, impossibility results such as Arrow’s Theorem and Gibbard–Satterthwaite will apply.
One variant you could try to fix this situation is define your peaks "coordinatewise", i.e. options are preferred less if both their coordinates are further from the "peak". However, you can check that this still allows all preferences on (0,0), (1,0), and (0,1), all with peak (0.5, 0.5).
In general, the test "are all preferences on three options possible" is probably a good litmus test for whether "good" voting schemes will exist (at least for the more basic definitions of "good").
answered Dec 13 '18 at 5:02
Clay ThomasClay Thomas
1406
$endgroup$
add a comment |
$begingroup$
Your condition is not strong enough to enforce structure on the preferences that result. For example, with three options (say (0,0), (1,0), and (0,1)) a voter could have any linear preference over these options (even if his "peak" was fixed at say (1,1)). Thus, impossibility results such as Arrow’s Theorem and Gibbard–Satterthwaite will apply.
One variant you could try to fix this situation is define your peaks "coordinatewise", i.e. options are preferred less if both their coordinates are further from the "peak". However, you can check that this still allows all preferences on (0,0), (1,0), and (0,1), all with peak (0.5, 0.5).
In general, the test "are all preferences on three options possible" is probably a good litmus test for whether "good" voting schemes will exist (at least for the more basic definitions of "good").
answered Dec 13 '18 at 5:02
Clay ThomasClay Thomas
1406
$endgroup$
Your condition is not strong enough to enforce structure on the preferences that result. For example, with three options (say (0,0), (1,0), and (0,1)) a voter could have any linear preference over these options (even if his "peak" was fixed at say (1,1)). Thus, impossibility results such as Arrow’s Theorem and Gibbard–Satterthwaite will apply.
One variant you could try to fix this situation is define your peaks "coordinatewise", i.e. options are preferred less if both their coordinates are further from the "peak". However, you can check that this still allows all preferences on (0,0), (1,0), and (0,1), all with peak (0.5, 0.5).
In general, the test "are all preferences on three options possible" is probably a good litmus test for whether "good" voting schemes will exist (at least for the more basic definitions of "good").
answered Dec 13 '18 at 5:02
Clay ThomasClay Thomas
1406
answered Dec 13 '18 at 5:02
Clay ThomasClay Thomas
1406
answered Dec 13 '18 at 5:02
Clay ThomasClay Thomas
1406
answered Dec 13 '18 at 5:02
Clay ThomasClay Thomas
1406
1406
add a comment |
add a comment |
$begingroup$
In one dimension, under the median scheme, manipulating your preference peak doesn't get you anything: If you feign a peak on the side of the median where your peak actually lies, that doesn't change the median, and if you feign a peak on the other side, that only pulls the median even further away from your peak.
In more than one dimension, however, you might get a better result by shifting the result's $x$ coordinate further away from your peak's $x$ coordinate – while that causes the result to end up further away from your acutal peak, you're then on a different line $lambda x + (1 − lambda)p_i$, which might be more favourable to you, since nothing in the premise constrains the relative ordering of points along different lines through the peak, so a point on one line further from the peak might be preferable to a point on another line closer to the peak.
answered Jun 6 '18 at 1:37
jorikijoriki
171k10188348
$endgroup$
add a comment |
$begingroup$
In one dimension, under the median scheme, manipulating your preference peak doesn't get you anything: If you feign a peak on the side of the median where your peak actually lies, that doesn't change the median, and if you feign a peak on the other side, that only pulls the median even further away from your peak.
In more than one dimension, however, you might get a better result by shifting the result's $x$ coordinate further away from your peak's $x$ coordinate – while that causes the result to end up further away from your acutal peak, you're then on a different line $lambda x + (1 − lambda)p_i$, which might be more favourable to you, since nothing in the premise constrains the relative ordering of points along different lines through the peak, so a point on one line further from the peak might be preferable to a point on another line closer to the peak.
answered Jun 6 '18 at 1:37
jorikijoriki
171k10188348
$endgroup$
add a comment |
$begingroup$
In one dimension, under the median scheme, manipulating your preference peak doesn't get you anything: If you feign a peak on the side of the median where your peak actually lies, that doesn't change the median, and if you feign a peak on the other side, that only pulls the median even further away from your peak.
In more than one dimension, however, you might get a better result by shifting the result's $x$ coordinate further away from your peak's $x$ coordinate – while that causes the result to end up further away from your acutal peak, you're then on a different line $lambda x + (1 − lambda)p_i$, which might be more favourable to you, since nothing in the premise constrains the relative ordering of points along different lines through the peak, so a point on one line further from the peak might be preferable to a point on another line closer to the peak.
answered Jun 6 '18 at 1:37
jorikijoriki
171k10188348
$endgroup$
In one dimension, under the median scheme, manipulating your preference peak doesn't get you anything: If you feign a peak on the side of the median where your peak actually lies, that doesn't change the median, and if you feign a peak on the other side, that only pulls the median even further away from your peak.
In more than one dimension, however, you might get a better result by shifting the result's $x$ coordinate further away from your peak's $x$ coordinate – while that causes the result to end up further away from your acutal peak, you're then on a different line $lambda x + (1 − lambda)p_i$, which might be more favourable to you, since nothing in the premise constrains the relative ordering of points along different lines through the peak, so a point on one line further from the peak might be preferable to a point on another line closer to the peak.
answered Jun 6 '18 at 1:37
jorikijoriki
171k10188348
answered Jun 6 '18 at 1:37
jorikijoriki
171k10188348
answered Jun 6 '18 at 1:37
jorikijoriki
171k10188348
answered Jun 6 '18 at 1:37
jorikijoriki
171k10188348
171k10188348
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2550974%2fstrategy-proofness-of-social-choice-function-in-two-dimensions%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
