import ecyglpki
import collections
pspace = ('W', 'D', 'L')
"""The set of possible football match outcomes (Win, Draw, or Lose)"""
Gamble = collections.namedtuple('Gamble', pspace)
"""Gamble on the outcome of a football match
With each possible match outcome, the gamble assigns a payoff (a |Real|);
it corresponds to winnings if it is positive, to losses if it is negative.
"""
[docs]def lp_setup(lp, accdss):
"""Set up the basic linear feasibility problem defining the gambling pool
A number of players will form a gambling pool:
* Each player states which gambles he finds *acceptable*, i.e., which
have an expected payoff that is nonnegative
* If there is a bet between the players, a gamble is assigned to each
of them; from the player's perspective, the assigned gamble should
be acceptable, meaning that is a positive linear combination of the
gambles that that player has stated to be acceptable
* The stake is assumed to be one, i.e., the assigned gamble's lowest
payoff is -1.
* There is a bet between the players if the gambles assigned to the
players sum up to one for each possible match outcome and the
assigned gambles do not all have identically zero payoff
* An important quantity for each player is the ‘lower prevision’ of the
gamble assigned to him: the greatest lower bound on the player's
expected payoff for the assigned gamble that can be deduced from the
player's stated acceptable gambles
* The objective is to maximize the sum of the lower previsions,
possibly under additional constraints
:param lp: the problem object to set up
:type lp: `ecyglpki.Problem`
:param accdss: the gambles accepted by the players
:type accdss: `dict` of `str` (player id) to `list` of `Gamble`
:returns: the set up problem object
:rtype: `ecyglpki.Problem`
"""
for player, accds in accdss.items(): # per-player setup
for outcome in pspace:
player_outcome = player + outcome
# constraints to ensure the assigned gamble is acceptable,
# i.e., nonnegative for each outcome
lp.add_named_rows(player_outcome)
lp.set_row_bnds(player_outcome, None, 0)
# variables for the gamble to be assigned
lp.add_named_cols(player_outcome)
lp.set_col_bnds(player_outcome, -1, None) # stake of 1
lp.set_mat_col(player_outcome, {player_outcome: -1})
# variables for the assigned gambles' lower previsions
player_lpr = player + 'lpr'
lp.add_named_cols(player_lpr)
lp.set_col_bnds(player_lpr, 0, None) # ensure nonnegative lprs
lp.set_mat_col(player_lpr, {player + outcome: 1 for outcome in pspace})
lp.set_obj_coef(player_lpr, 1) # objective is the sum of lprs
# variables for the accepted gambles' coefficients that define the
# assigned gamble as a positive linear combination of acceptable
# gambles
for accd in accds:
j = lp.add_cols(1)
lp.set_col_bnds(j, 0, None) # ensure nonnegative coeffs
lp.set_mat_col(j, {player + outcome: getattr(accd, outcome)
for outcome in pspace})
# remove names from database that are not needed anymore
for outcome in pspace:
lp.set_row_name(player + outcome, '')
# global setup: constraints that ensure the assigned gambles sum up to zero
for outcome in pspace:
lp.add_named_rows(outcome)
lp.set_row_bnds(outcome, 0, 0)
lp.set_mat_row(outcome, {player + outcome: 1
for player in accdss.keys()})
return lp
[docs]def lp_assign(accdss):
"""Assign gambles to all players that maximize the sum of lower previsions
:param accdss: the gambles accepted by the players
:type accdss: `dict` of `str` (player id) to `list` of `Gamble`
:returns: the gamble assigned to the players
and the corresponding lower prevision value
:rtype: `dict` of `str` (player id) to
{`'gamble'`: `Gamble`, `'lpr'`: `float`}
>>> Agambles = [Gamble(.5, .25, -1), Gamble(1, -1, -1)]
>>> Bgambles = [Gamble(-1, -1, 2), Gamble(1, .5, -.25)]
>>> Cgambles = [Gamble(-1, 0, -1)]
>>> accdss = {'Alice': Agambles, 'Bob': Bgambles, 'Cthulhu': Cgambles}
>>> solution = lp_assign(accdss)
>>> assert solution == (
... {'Alice': {'gamble': Gamble(W=2.0, D=-1.0, L=-1.0), 'lpr': 0.5},
... 'Bob': {'gamble': Gamble(W=-1.0, D=-1.0, L=2.0), 'lpr': 0.0},
... 'Cthulhu': {'gamble': Gamble(W=-1.0, D=2.0, L=-1.0), 'lpr': 2.0}}
... )
"""
lp = ecyglpki.Problem() # construct the linear program
lp_setup(lp, accdss)
# solve the linear program
lp.set_obj_dir('maximize')
smcp = ecyglpki.SimplexControls() # (default) simplex control parameters
smcp.presolve = True
status = lp.simplex(smcp) # solve using control parameters given
if status != 'optimal':
raise RuntimeError('Error while solving...: ' + status)
smcp.presolve = False
status = lp.exact(smcp) # now solve exactly using control parameters given
if status != 'optimal':
raise RuntimeError('Error while solving...: ' + status)
return {player: {
'gamble': Gamble(*(lp.get_col_prim(player + outcome)
for outcome in pspace)),
'lpr': lp.get_col_prim(player + 'lpr')
} for player in accdss.keys()}
[docs]def milp_assign(accdss):
"""Assign gambles to some players that maximize the sum of lower previsions
As compared to `lp_assign`, we now try to make the bet fair in the sense
that for each player the lower prevision for the assigned gamble is equal
to the other player's lower prevision, or the gamble assigned to the player
is zero for all outcomes.
:param accdss: the gambles accepted by the players
:type accdss: `dict` of `str` (player id) to `list` of `Gamble`
:returns: the gamble assigned to the players
and the corresponding lower prevision value
:rtype: `dict` of `str` (player id) to
{`'gamble'`: `Gamble`, `'lpr'`: `float`}
>>> Agambles = [Gamble(.5, .25, -1), Gamble(1, -1, -1)]
>>> Bgambles = [Gamble(-1, -1, 2), Gamble(1, .5, -.25)]
>>> Cgambles = [Gamble(-1, 0, -1)]
>>> accdss = {'Alice': Agambles, 'Bob': Bgambles, 'Cthulhu': Cgambles}
>>> solution = milp_assign(accdss)
>>> for player, data in solution.items(): # round floats for doctest
... solution[player]['lpr'] = round(data['lpr'], 2)
... solution[player]['gamble'] = Gamble(round(data['gamble'].W, 2),
... round(data['gamble'].D, 2),
... round(data['gamble'].L, 2))
>>> assert solution == (
... {'Alice': {'gamble': Gamble(W=1.4, D=0.0, L=-1.0), 'lpr': 0.4},
... 'Bob': {'gamble': Gamble(W=-0.4, D=-0.4, L=2.0), 'lpr': 0.4},
... 'Cthulhu': {'gamble': Gamble(W=-1.0, D=0.4, L=-1.0), 'lpr': 0.4}}
... )
"""
milp = ecyglpki.Problem() # construct the linear program
lp_setup(milp, accdss)
maxval = len(accdss) - 1 # the largest possible payoff in the pool:
# stake (==1) times number of other players
# the unique lower prevision for included players
milp.add_named_cols('lpr')
milp.set_col_bnds('lpr', 0, None)
for player in accdss.keys():
player_b = player + 'b'
# the binary variable to select whether a player is included or not
milp.add_named_cols(player_b)
milp.set_col_kind(player_b, 'binary')
# add constraints to ensure that a player's lpr
# is either equal to the global one or zero
i = milp.add_rows(3)
# player_lpr <= lpr
milp.set_row_bnds(i, None, 0)
milp.set_mat_row(i, {player + 'lpr': 1, 'lpr': -1})
# player_lpr <= maxval * player_b
milp.set_row_bnds(i+1, None, 0)
milp.set_mat_row(i+1, {player + 'lpr': 1, player_b: -maxval})
# lpr - player_lpr <= maxval * (1 - player_b)
milp.set_row_bnds(i+2, None, maxval)
milp.set_mat_row(i+2, {'lpr': 1, player + 'lpr': -1, player_b: maxval})
# -1 * player_b <= player_outcome <= maxval * player_b
for outcome in pspace:
i = milp.add_rows(2)
milp.set_row_bnds(i, None, 0)
milp.set_mat_row(i, {player + outcome: 1, player_b: -maxval})
milp.set_row_bnds(i+1, 0, None)
milp.set_mat_row(i+1, {player + outcome: 1, player_b: 1})
# solve the mixed integer linear program
milp.set_obj_dir('maximize')
iocp = ecyglpki.IntOptControls() # (default) int. opt. control parameters
iocp.presolve = True
status = milp.intopt(iocp)
if status != 'optimal':
raise RuntimeError('Error while solving...: ' + status)
# fix the binary variables to their computed value and find exact solution
for player in accdss.keys():
player_b = player + 'b'
player_b_val = milp.mip_col_val(player_b)
milp.set_col_bnds(player_b, player_b_val, player_b_val)
smcp = ecyglpki.SimplexControls() # (default) simplex control parameters
smcp.presolve = True
status = milp.simplex(smcp) # solve
if status != 'optimal':
raise RuntimeError('Error while solving...: ' + status)
smcp.presolve = False
status = milp.exact(smcp) # now solve exactly
if status != 'optimal':
raise RuntimeError('Error while solving...: ' + status)
return {player: {
'gamble': Gamble(*(milp.get_col_prim(player + outcome)
for outcome in pspace)),
'lpr': milp.get_col_prim(player + 'lpr')
} for player in accdss.keys()}