#16331: Game Theory: Build capacity to solve matching games in to Sage.
-------------------------------------+-------------------------------------
Reporter: vinceknight | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: game theory | Resolution:
Keywords: Game Theory, | Merged in:
Matching Games, | Reviewers:
Authors: | Work issues:
Report Upstream: N/A | Commit:
Branch: | 0c19d87876a451c349448da3b27101f04162c985
u/vinceknight/game_theory__build_capacity_to_solve_matching_games_in_to_sage_|
Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by vinceknight):
Replying to [comment:45 kcrisman]:
> Comments I could reconstruct:
> * Should it be a game of 2n players or size n? Is there a standard
terminology?
> * Since the matching $M$ is bijective and the algorithm is not
symmetric, should the solution really have each match twice?
> {{{
> sage: m.solve()
> {'A': ['J'],
> 'C': ['K'],
> 'B': ['M'],
> 'D': ['L'],
> 'K': ['C'],
> 'J': ['A'],
> 'M': ['B'],
> 'L': ['D']}
> }}}
> maybe instead
> {{{
> sage: m.solve()
> {'A': ['J'],
> 'C': ['K'],
> 'B': ['M'],
> 'D': ['L'],
> }}}
> and then it will be easy to tell if it's inverted...
I have made this change but this has been done in conjunction with other
changes: in particular `_sol_dict_` is now an attribute that includes the
same dictionary as before (so that it can be used for the bi-partite graph
method for example) but `solve` only returns the required output (as you
suggest).
> * `_repr_` really shouldn't have it possible to have something other
than $2n$. I'm not asking to check the `_is_complete` at that point, but
at least they should be same number can be checked.
> * `latex` - I'm not sure this is standard notation. `4=\{(1, 0)\}`
equals sign?
These both have been fixed.
> * in `game_to_dict` I just don't know whether one should have
"undicted" the game in the first place. It seems like a lot of trouble to
redictify the game. Maybe the data should be stored differently in any
event. Constructing a whole `_Player` for each player seems like a lot of
overhead. They have no external existence.
The only reason to `undict` the game is because the players are not passed
to the instance so no dictionary with player instances as keys was
constructed until the `game_to_dict` method was called. This has now been
changed: upon initialisation the input dictionaries are used to create new
dictionaries with player instances as keys.
The reason for keeping the player instance is that it allows for an easier
and more readable coding of the algorithm itself (so I'm quite keen to
keep it).
> * Is it possible for someone to access all the partners and pref and
such in such a way as to mess with `_is_solved`? It just seems odd that
those things might be directly accessible.
I actually think this is worth keeping as it could be possible that
someone would want to access and change partners (I can't think of why but
I can imagine that it would be a shame to take that possibility away).
> * I think another word than 'complete' is needed in checking
completeness, because if `{3: (0, 2, 1)` was changed to `{3: (0, 2)` it
would still raise the error but seem "complete" in some sense...
I'm not sure I actually understand this one. `{3:(0,2)` would not be
complete as `2` is not a valid player? Maybe I'm missing something. Very
happy to change vocabulary.
> * What if the automatically added suitor name is already in use? (Say,
we already have names `3, 'Fred'` and now want to automatically add a
third one.) I don't know the right answer here.
I have added an error for this.
> * Any rationale for the autoprefs?
Not really... Do you think they should be something else?
> * I wonder if `sol_dict` should be an attribute and not a method.
Especially since you're not really supposed to access it publicly.
Completely agree: done, see earlier comment re `solve`.
> * And of course, if you REALLY want to use the `_Player` class, needs
doctests :)
I think this has been done. Note that I need to import the `_Player` class
in the tests themselves: I hope that's ok.
Thanks again for being so thorough: very much appreciated.
--
Ticket URL: <http://trac.sagemath.org/ticket/16331#comment:49>
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.
