weighted-fair-allocation 1.0.0

A realization of the weighted fair allocation problem, with implementations of common allocation algorithms. Created for experimentation purposes.

Weighted Fair Allocation

An implementation of the weighted setting for the fair allocation problem (see weighted fair allocation problem), with implementations of common allocation algorithms. Created as experimental tooling for research purposes.

Installation

Using a python>=3.11 environment, the package can be installed using pip install weighted-fair-allocation

Basic usage

Creation of a problem instance:

import weighted_fair_allocation.model as wfa

# Specify the set of items
a = wfa.Item('a')
b = wfa.Item('b')
c = wfa.Item('c')
items = set([a, b, c])

# Create valuations for 2 agents
valuation_1 = wfa.AdditiveValuation()
valuation_1.provide_valuations({a:1, b:2, c:3})

valuation_2 = wfa.AdditiveValuation()
valuation_2.provide_valuations({a:3, b:2, c:1})

# Create the set of agents
agent_i = wfa.Agent(
    1,              # Id 
    4,              # Weight
    valuation_1,    # Used valuation
    "i"             # Label
)
agent_j = wfa.Agent(2, 1, valuation_2, "j")
agents = set([agent_i, agent_j])

# Create the problem instance
instance = wfa.Instance(agents, items)

# Print a table view of the instance
print(instance.draw_str())
#   | w |   | a | b | c |                                                    
#   | - | - | - | - | - |
#   | 4 | i | 1 | 2 | 3 |
#   | 1 | j | 3 | 2 | 1 |

Now using this problem instance we can manually create an allocation:

# Create an allocation
allocation = wfa.Allocation().from_instance(instance)

# Assign the items to an agent
allocation.assign(a, agent_i)
allocation.assign(b, agent_i)
allocation.assign(c, agent_j)

print(allocation)
# {j: {c}, i: {a, b}}

Or use one of the common algorithms to calculate an allocation:

Weighted adjusted winner procedure

Only defined for instances with 2 agents, results in WEF1 + PO [Chakraborty et al. 2019] (+ acyclic) allocations.

from weighted_fair_allocation.algorithms.weighted_adjusted_winner import WeightedAdjustedWinner

# Create an instance of the algorithm and run it
alloc = WeightedAdjustedWinner(instance).run()
print(alloc)
# {j: {a}, i: {b, c}}

Picking sequences

Manually specify a picking sequence:

from weighted_fair_allocation.algorithms.picking_sequences import PickingSequence

# Create an picking sequence instance
alg = PickingSequence(instance)

# Specify a sequence over the agents of length (len(items))
sequence = [agent_i, agent_j, agent_i]

# Run the picking sequence using the specified sequence
alloc = alg.run(sequence)
print(alloc)
# {i: {b, c}, j: {a}}

Or use one of the divisor methods, all of which result in WWEF1 allocations (additionally Adams is WEF1 and Jefferson is WPROP1)[Chakraborty et al. 2021].

alloc = alg.adams()
alloc = alg.jefferson()
alloc = alg.webster()
alloc = alg.hill()
alloc = alg.dean()

Or generate the picking sequences which are guaranteed to result in allocations with a fairness guarantee:

• WEF1 [Chakraborty et al. 2021]
• WWEF1 [Chakraborty et al. 2021]
• WEF $(x, 1-x)$ (or parameterized WEF) [Chakraborty et al. 2021]
• best-of-both worlds (bobw) fairness [Aziz et al. 2023]

sequences = alg.get_valid_sequences_WEF1()
sequences = alg.get_valid_sequences_WWEF1()
sequences = alg.get_valid_sequences_param_WEF()
sequences = alg.get_valid_sequences_bobw()

Max Nash welfare

EF1 + PO allocations [Caragiannis et al. 2019]

from weighted_fair_allocation.algorithms.nash_welfare import MaxNashWelfare

alloc = MaxNashWelfare(instance).run()
print(alloc)
# {j: {a, b}, i: {c}}

Max weighted Nash welfare

WWEF1 + PO allocations [Chakraborty et al. 2019]

from weighted_fair_allocation.algorithms.nash_welfare import MaxNashWelfare

alloc = MaxNashWelfare(instance).run(weighted=True)
print(alloc)
# {j: {a}, i: {b, c}}