#16332: Game Theory: Build capacity to calculate Shapley value of cooperative
games.
-------------------------------------+-------------------------------------
Reporter: vinceknight | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.3
Component: PLEASE CHANGE | Resolution:
Keywords: Game Theory, | Merged in:
Cooperative Games | Reviewers:
Authors: | Work issues:
Report Upstream: N/A | Commit:
Branch: | f9bd4362c6228e6aefb31ceac9bd5660a02a588f
u/jcampbell/game_theory__build_capacity_to_calculate_shapley_value_of_cooperative_games_|
Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by vinceknight):
Replying to [comment:13 kcrisman]:
> > I'll try to look at this later today for some initial comments.
> Okay, here are my initial thoughts. They're not in priority order, just
the order I thought about them in.
Thanks a lot for getting back so quick: this is all super helpful.
> * First, there are lots of little formatting things in docstrings. I
won't bother about them now, might even just try to comment on github
eventually. But they are there. Please study other modules' docstrings
carefully - especially with regard to length of lines and where to put
double colons and blank lines.
Will do. We were keen to get this up here fast so as to see where we were
with bigger potential problems (that you've picked up below). Is that
generally an ok practice or is it felt to be bad etiquette to push to trac
things that could be better?
> * I really dislike the necessity of using tuples and dictionaries to
initialize the games. I understand why! But for instance, it requires
the **very** annoying `('A',)` syntax for tuples with one element. You
should at least allow any iterable as a key - but unfortunately the keys
need to be [http://stackoverflow.com/questions/4418741/im-able-to-use-a
-mutable-object-as-a-dictionary-key-in-python-is-this-not-disa hashable].
So as a corollary, dictionaries are not awesome for the games.
>
> Of course, then the question is "okay, mister smarty-pants, do you
have a better idea?" And the truth is I don't, yet. This implementation
is more flexible than
[https://github.com/drvinceknight/Gamepy/blob/master/Shappy/Shap.py
Shap.py], it's true. As a starting point, it might be useful to
demonstrate using a short program to ''generate'' the dictionaries needed
from an input of, say, five players and some rule on payoffs.
I had thought about this for a while and agree that `(A,)` isn't the best.
Just on this minor point, we thought about having a clean up in the init
method that would handle `A`, `(A,)` as well as `(A)` but require `(A,B)`
for two tuples etc... Is this a done thing?
Ultimately, re dictionaries as you say: I don't see a better way of doing
it. We need to map all the coalitions to values... Would be great if we
could think of a nicer way of doing this...
> * Might as well allow easy implementation of a subclass of Simple
Games. (In this case, one could imagine an initializer that uses either
a list of winning coalitions, or this initialization.)
> * Banzhaf, other values?
> * What if one assumed the game to ''be'' additive? Maybe then it could
be inputted in a more straightforward way?
I'm not entirely sure I follow... This sounds very particular and
restrictive... I agree that dictionaries are a pain but they do fit the
defining of a characteristic game... Not throwing the idea out: just
writing down my initial thoughts...
> * There should be mathematical descriptions of each concept in its
documentation. For instance, the Bessel function documentation is
practically an intro to Bessel functions.
We wondered about this. We will include it!
> * Should Shapley be ''the'' payoff vector? Indeed, isn't the point
that there could be many possible payoff vectors? (The core, etc.)
That's why we added the ability to check certain properties
(suparrditivity, nullplayer) for ANY vector so that any vector could be
set as an attribute and in effect compared to the Shapley value. Should
this be made more explicit? Perhaps setting the Shapley_value to be the
payoff_vector by default when running the shapley method isn't the way to
go...
> * Should one use Python permutations or Sage ones?
I have no idea... Is there a best practice with this sort of thing?
> * `get_predecessors` seems pointless as a separate function.
> * You could use list comprehensions some places (e.g.
`marginal_contributions`).
> * That same function is really, really hard to figure out. There is no
context whatsoever. I finally figured out what you meant, but it's pretty
hermetic. That said, I'm not sure how to put that information about the
permutations in without a very long thing. Maybe a better solution would
be to put marginal contributions of a player specific to a coalition.
That way you both avoid dealing with permutations, which isn't very
natural here (as opposed to coalitions, which is fundamental) as well as
make the user ask for what they want instead of providing them an
information dump, which could be very bad with more than three players :)
I agree that this can be tidied. It will be.
> * Oh, I see, you use it in the Shapley value. I probably should have
guessed... but in that case, again, I would make that a 'hidden'
(underscored) function. You can still provide the marginal contributions
per coalition, of course! But I think the thing for all of them should
not show up upon tab-completion because you really only use it for the
Shapley value.
Didn't realise that this could be done! Will do :) (Still think it can be
tidied)
> Finally, I want to affirm that this looks fun and useful so far! It's
just hard work thinking of what it should look like, because you want to
think about design and not just efficiency for your own research purposes.
I had some classes of voting stuff that looked similar - but they are in
no shape to be submitted to Sage, they just do what I want them to. This
is a little more ambitious, so we need more input. Do you know some
cooperative game theory types who might be able to take a look at the
organization of this? That would be really helpful; unfortunately, the
people I know in simple games probably wouldn't have the time to look at
in-progress stuff, though I think they would be very supportive of having
it in Sage.
I'm afraid that I don't actually. Cooperative game theory is a small part
of a course I teach and not actually within my research fields (ticket
16333 is the big cookie!). My initial idea was that this was actually
simple enough (calculation of shapley value) to be a nice first step so
that we could figure out how to get the docs right etc... (which we will
:)). What is the general procedure for finding reviewers? I'm guessing the
main reason this sort of stuff isn't in Sage yet is probably because there
aren't that many game theorists using Sage (which lends itself to a
Chicken and Egg situation I imagine).
I will see if I can email a few people who might be able to take a look
(not people that I know) but I expect they won't be too familiar with
Sage... We could give them a demo I suppose and see what they thought...
The big issue re 'how we want it to look' is dictionaries as inputs. I
don't see a way around that... (But hope someone else will...). I'll be
thinking...
Thanks again for your comments/guidance/tips/time: it's super helpful.
--
Ticket URL: <http://trac.sagemath.org/ticket/16332#comment:14>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
