#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 kcrisman):
> Thanks a lot for getting back so quick: this is all super helpful.
Well, I'm pretty motivated because this is far more directly related to my
research than most things in Sage.
> > * 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?
To be honest, when we just had the patches system it wasn't such a big
deal - people could ignore the patches if they were "rough" because
someone else could always pick it up again later. I haven't gotten a good
sense with the branch system yet. That said, rough work is better than no
work; it was the GSOC context where I though maybe it would be worth doing
separately first, because there is a clear time frame and no worries about
abandoned code.
> > * 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.
> 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?
I don't see why not, but you would have to be careful, because the
dictionary requires hashable keys. So in that case
{{{
sage: {'A':1}
{'A': 1}
sage: a = 5
sage: {a:1}
{5: 1}
sage: {2:1}
{2: 1}
sage: {(1,2):1}
{(1, 2): 1}
sage: {[1,2]:1}
---------------------------------------------------------------------------
TypeError Traceback (most recent call
last)
<ipython-input-6-e1906c12ada7> in <module>()
----> 1 {[Integer(1),Integer(2)]:Integer(1)}
TypeError: unhashable type: 'list'
}}}
so I guess that you could accept a lot of different dictionaries. But
then one would want to check whether the singletons really were connected
to the larger tuples.
> > * 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...
It may not have been well thought-out by me, either; I meant if (say)
(A,B) gave 12 and A gave 7 then it could be computed that B gave 5, but
maybe that's not done often. Not necessary, anyway.
> > * 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?
No, that was clear.
> Perhaps setting the Shapley_value to be the payoff_vector by default
when running the shapley method isn't the way to go...
That's what I'm wondering.
> > * Should one use Python permutations or Sage ones?
> I have no idea... Is there a best practice with this sort of thing?
Speed is something that matters, so you might want to check that out. Now
that I see what it's for, having Sage inheritance etc. isn't as necessary
since you aren't using it for other things.
> 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 :)).
You're right, a toy(ish) implementation of this is a good thing to do as a
warm-up. But see [http://arxiv.org/list/cs.GT/recent Arxiv] for a
sampler of what people really do...
> 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).
Well, basically you just ask people. I can definitely help. But I would
like real experts to weigh in too. Now, it just so happens that there is
someone at [http://www.cs.ox.ac.uk/people/edith.elkind/ Oxford] who has
[http://www.amazon.com/Computational-Cooperative-Synthesis-Artificial-
Intelligence/dp/1608456528 written a book on the subject] and is
personally very well known to
[https://plus.google.com/+DimaPasechnik/posts a certain Sage developer].
I wonder if she might be willing to take a look.
By the way, you'll notice that [http://dl.acm.org/citation.cfm?id=1668360
LPs come up in this]. So having a robust version of this will be good.
> 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...
So what ''I'm'' thinking is that we find a way to make it clear this is a
"toy implementation" that would be general enough for someone actually in
the field to expand upon.
[http://webpages.math.luc.edu/~enb/ Here is] yet another implementation -
see the bottom, and then
[http://www.mathworks.com/matlabcentral/fileexchange/35933-mattugames this
link] which is - yes! - BSD licensed!!! I think it would definitely be
worth contacting these folks to see if we can use/adapt/at least use as
information for how to approach this cooperative material.
> Thanks again for your comments/guidance/tips/time: it's super helpful.
Thank YOU for actually getting people working on this!
----
Okay, but least I get too ambitious for coding I'm not doing, let me
reiterate that a basic implementation, with as much potential for further
development as possible, is what we want here. So for now, exposing as
little API as possible is good, so we wouldn't have to deprecate
functionality later on.
--
Ticket URL: <http://trac.sagemath.org/ticket/16332#comment:15>
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.
