Calculating the Shapley value in a weighted voting game.
$begingroup$
Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a player with a weight of $1$ as a function of $a$,$b$ and $q$.
I know how to calculate the Shapely value in general, but I would like to get a simple closed form for the result. I tried to think about what happens if there are only players with weights of $1$ (simple scenario $ a=2k-1,b=0,q=k $ I think you will agree that $ phi_{1}(v)=frac{1}{a}=frac{1}{2k-1} $. the simple calculation is $ binom{2k-2}{k-1}(k-1)!(k-1)!=frac{1}{2k-1}=frac{1}{a} $ which is $ frac{1}{2k-1} $. The calculation for a player of weight 1 (when there are 1s and 2s) would be a sum of choosing i players of weight 1 and $ frac{q-i}{2} $ players of weight 2. similar calculation for a player of weight 2.
I tagged binomial coefficients because I thought they could be useful for counting the occurrences.
Thanks in advance, Mati
also posted here: https://mathoverflow.net/questions/107507/calculating-the-shapely-value-in-a-weighted-voting-game
combinatorics binomial-coefficients game-theory combinatorial-game-theory
edited Apr 13 '17 at 12:58
Community♦
1
asked Sep 19 '12 at 11:39
Mati BotMati Bot
1463
$endgroup$
add a comment |
$begingroup$
Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a player with a weight of $1$ as a function of $a$,$b$ and $q$.
I know how to calculate the Shapely value in general, but I would like to get a simple closed form for the result. I tried to think about what happens if there are only players with weights of $1$ (simple scenario $ a=2k-1,b=0,q=k $ I think you will agree that $ phi_{1}(v)=frac{1}{a}=frac{1}{2k-1} $. the simple calculation is $ binom{2k-2}{k-1}(k-1)!(k-1)!=frac{1}{2k-1}=frac{1}{a} $ which is $ frac{1}{2k-1} $. The calculation for a player of weight 1 (when there are 1s and 2s) would be a sum of choosing i players of weight 1 and $ frac{q-i}{2} $ players of weight 2. similar calculation for a player of weight 2.
I tagged binomial coefficients because I thought they could be useful for counting the occurrences.
Thanks in advance, Mati
also posted here: https://mathoverflow.net/questions/107507/calculating-the-shapely-value-in-a-weighted-voting-game
combinatorics binomial-coefficients game-theory combinatorial-game-theory
edited Apr 13 '17 at 12:58
Community♦
1
asked Sep 19 '12 at 11:39
Mati BotMati Bot
1463
$endgroup$
$begingroup$
Joriki, please refer to the edit in my question. Thanks.
$endgroup$
– Mati Bot
Sep 19 '12 at 14:06
$begingroup$
Thanks for the quick response. I've removed my comments and downvote (and in fact upvoted). I doubt that there's a nice closed form, though. The result will depend on the quota if the quota is close to $0$ or $a+2b$, but for small $b$ there will be a plateau of intermediate quota where the result doesn't change with the quota.
$endgroup$
– joriki
Sep 19 '12 at 14:23
add a comment |
$begingroup$
Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a player with a weight of $1$ as a function of $a$,$b$ and $q$.
I know how to calculate the Shapely value in general, but I would like to get a simple closed form for the result. I tried to think about what happens if there are only players with weights of $1$ (simple scenario $ a=2k-1,b=0,q=k $ I think you will agree that $ phi_{1}(v)=frac{1}{a}=frac{1}{2k-1} $. the simple calculation is $ binom{2k-2}{k-1}(k-1)!(k-1)!=frac{1}{2k-1}=frac{1}{a} $ which is $ frac{1}{2k-1} $. The calculation for a player of weight 1 (when there are 1s and 2s) would be a sum of choosing i players of weight 1 and $ frac{q-i}{2} $ players of weight 2. similar calculation for a player of weight 2.
I tagged binomial coefficients because I thought they could be useful for counting the occurrences.
Thanks in advance, Mati
also posted here: https://mathoverflow.net/questions/107507/calculating-the-shapely-value-in-a-weighted-voting-game
combinatorics binomial-coefficients game-theory combinatorial-game-theory
edited Apr 13 '17 at 12:58
Community♦
1
asked Sep 19 '12 at 11:39
Mati BotMati Bot
1463
$endgroup$
Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a player with a weight of $1$ as a function of $a$,$b$ and $q$.
I know how to calculate the Shapely value in general, but I would like to get a simple closed form for the result. I tried to think about what happens if there are only players with weights of $1$ (simple scenario $ a=2k-1,b=0,q=k $ I think you will agree that $ phi_{1}(v)=frac{1}{a}=frac{1}{2k-1} $. the simple calculation is $ binom{2k-2}{k-1}(k-1)!(k-1)!=frac{1}{2k-1}=frac{1}{a} $ which is $ frac{1}{2k-1} $. The calculation for a player of weight 1 (when there are 1s and 2s) would be a sum of choosing i players of weight 1 and $ frac{q-i}{2} $ players of weight 2. similar calculation for a player of weight 2.
I tagged binomial coefficients because I thought they could be useful for counting the occurrences.
Thanks in advance, Mati
also posted here: https://mathoverflow.net/questions/107507/calculating-the-shapely-value-in-a-weighted-voting-game
combinatorics binomial-coefficients game-theory combinatorial-game-theory
combinatorics binomial-coefficients game-theory combinatorial-game-theory
edited Apr 13 '17 at 12:58
Community♦
1
asked Sep 19 '12 at 11:39
Mati BotMati Bot
1463
edited Apr 13 '17 at 12:58
Community♦
1
asked Sep 19 '12 at 11:39
Mati BotMati Bot
1463
edited Apr 13 '17 at 12:58
Community♦
1
edited Apr 13 '17 at 12:58
Community♦
1
edited Apr 13 '17 at 12:58
Community♦
1
1
asked Sep 19 '12 at 11:39
Mati BotMati Bot
1463
asked Sep 19 '12 at 11:39
Mati BotMati Bot
1463
asked Sep 19 '12 at 11:39
Mati BotMati Bot
1463
1463
$begingroup$
Joriki, please refer to the edit in my question. Thanks.
$endgroup$
– Mati Bot
Sep 19 '12 at 14:06
$begingroup$
Thanks for the quick response. I've removed my comments and downvote (and in fact upvoted). I doubt that there's a nice closed form, though. The result will depend on the quota if the quota is close to $0$ or $a+2b$, but for small $b$ there will be a plateau of intermediate quota where the result doesn't change with the quota.
$endgroup$
– joriki
Sep 19 '12 at 14:23
add a comment |
$begingroup$
Joriki, please refer to the edit in my question. Thanks.
$endgroup$
– Mati Bot
Sep 19 '12 at 14:06
$begingroup$
Thanks for the quick response. I've removed my comments and downvote (and in fact upvoted). I doubt that there's a nice closed form, though. The result will depend on the quota if the quota is close to $0$ or $a+2b$, but for small $b$ there will be a plateau of intermediate quota where the result doesn't change with the quota.
$endgroup$
– joriki
Sep 19 '12 at 14:23
$begingroup$
Joriki, please refer to the edit in my question. Thanks.
$endgroup$
– Mati Bot
Sep 19 '12 at 14:06
$begingroup$
Joriki, please refer to the edit in my question. Thanks.
$endgroup$
– Mati Bot
Sep 19 '12 at 14:06
$begingroup$
Thanks for the quick response. I've removed my comments and downvote (and in fact upvoted). I doubt that there's a nice closed form, though. The result will depend on the quota if the quota is close to $0$ or $a+2b$, but for small $b$ there will be a plateau of intermediate quota where the result doesn't change with the quota.
$endgroup$
– joriki
Sep 19 '12 at 14:23
$begingroup$
Thanks for the quick response. I've removed my comments and downvote (and in fact upvoted). I doubt that there's a nice closed form, though. The result will depend on the quota if the quota is close to $0$ or $a+2b$, but for small $b$ there will be a plateau of intermediate quota where the result doesn't change with the quota.
$endgroup$
– joriki
Sep 19 '12 at 14:23
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Note that the Shapley value for this game is the probability that a player is pivotal in a random ordering. Now the probability that a 1 player is pivotal is the probability that the sum is q-1 when she is reached. While for a 2 player it is the probability that it is q-1 or q-2. This should simplify the analysis, but I haven't worked out the details.
However a simple conclusion is that the Shapley value for 1 players is approximately 1/2 that for 2 players for reasonable size values and away from extremes, so the values are approximately 1/(a+2b) and 2/(a+2b) respectively. In particular this holds in the limit where a,b go to infinity and q=y(a+2b) for 05 and 2/a
answered Aug 27 '13 at 2:18
ericfericf
1563
$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%2f199080%2fcalculating-the-shapley-value-in-a-weighted-voting-game%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Note that the Shapley value for this game is the probability that a player is pivotal in a random ordering. Now the probability that a 1 player is pivotal is the probability that the sum is q-1 when she is reached. While for a 2 player it is the probability that it is q-1 or q-2. This should simplify the analysis, but I haven't worked out the details.
However a simple conclusion is that the Shapley value for 1 players is approximately 1/2 that for 2 players for reasonable size values and away from extremes, so the values are approximately 1/(a+2b) and 2/(a+2b) respectively. In particular this holds in the limit where a,b go to infinity and q=y(a+2b) for 05 and 2/a
answered Aug 27 '13 at 2:18
ericfericf
1563
$endgroup$
add a comment |
$begingroup$
Note that the Shapley value for this game is the probability that a player is pivotal in a random ordering. Now the probability that a 1 player is pivotal is the probability that the sum is q-1 when she is reached. While for a 2 player it is the probability that it is q-1 or q-2. This should simplify the analysis, but I haven't worked out the details.
However a simple conclusion is that the Shapley value for 1 players is approximately 1/2 that for 2 players for reasonable size values and away from extremes, so the values are approximately 1/(a+2b) and 2/(a+2b) respectively. In particular this holds in the limit where a,b go to infinity and q=y(a+2b) for 05 and 2/a
answered Aug 27 '13 at 2:18
ericfericf
1563
$endgroup$
add a comment |
$begingroup$
Note that the Shapley value for this game is the probability that a player is pivotal in a random ordering. Now the probability that a 1 player is pivotal is the probability that the sum is q-1 when she is reached. While for a 2 player it is the probability that it is q-1 or q-2. This should simplify the analysis, but I haven't worked out the details.
However a simple conclusion is that the Shapley value for 1 players is approximately 1/2 that for 2 players for reasonable size values and away from extremes, so the values are approximately 1/(a+2b) and 2/(a+2b) respectively. In particular this holds in the limit where a,b go to infinity and q=y(a+2b) for 05 and 2/a
answered Aug 27 '13 at 2:18
ericfericf
1563
$endgroup$
Note that the Shapley value for this game is the probability that a player is pivotal in a random ordering. Now the probability that a 1 player is pivotal is the probability that the sum is q-1 when she is reached. While for a 2 player it is the probability that it is q-1 or q-2. This should simplify the analysis, but I haven't worked out the details.
However a simple conclusion is that the Shapley value for 1 players is approximately 1/2 that for 2 players for reasonable size values and away from extremes, so the values are approximately 1/(a+2b) and 2/(a+2b) respectively. In particular this holds in the limit where a,b go to infinity and q=y(a+2b) for 05 and 2/a
answered Aug 27 '13 at 2:18
ericfericf
1563
answered Aug 27 '13 at 2:18
ericfericf
1563
answered Aug 27 '13 at 2:18
ericfericf
1563
answered Aug 27 '13 at 2:18
ericfericf
1563
1563
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%2f199080%2fcalculating-the-shapley-value-in-a-weighted-voting-game%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
$begingroup$
Joriki, please refer to the edit in my question. Thanks.
$endgroup$
– Mati Bot
Sep 19 '12 at 14:06
$begingroup$
Thanks for the quick response. I've removed my comments and downvote (and in fact upvoted). I doubt that there's a nice closed form, though. The result will depend on the quota if the quota is close to $0$ or $a+2b$, but for small $b$ there will be a plateau of intermediate quota where the result doesn't change with the quota.
$endgroup$
– joriki
Sep 19 '12 at 14:23