socialchoicekit.deterministic_allocation module

class socialchoicekit.deterministic_allocation.MaximumWeightMatching(zero_indexed: bool = False)

Bases: object

The maximum weight matching algorithm, which solves a special case of the minimum cost flow problem, finds an optimal matching between agents and items given the full cardinal utilities of the agents.

Uses the scipy implementation of LAPJVsp algorithm.

Parameters

zero_indexedbool

If True, the output of the social welfare function and social choice function will be zero-indexed. If False, the output will be one-indexed. One-indexed by default.

scf(valuation_profile: ValuationProfile) → ndarray

The social choice function, which takes in a valuation profile and returns an allocation.

Parameters

valuation_profile: ValuationProfile

This is the (complete) cardinal profile. A (N, N) array, where N is the number of agents and also the number of items. The element at (i, j) indicates the utility value (agent’s cardinal preference) for item j. If agent i finds item j unacceptable, the element would be np.nan

Returns

allocation: np.ndarray

This is the allocation. A (N,) array, where N is the number of items. Agent i is assigned to element i.

socialchoicekit.deterministic_allocation.root_n_serial_dictatorship(profile: Profile) → ndarray

Root n serial dictatorship is a subroutine used in the Match-TwoQueries routine [ABFV2022a] for elicitation allocation. This does not compute an approriate allocation. Instead, it generates a ‘sufficiently representative assignment’.

The algorithm assigns at most root n agents to each item based on a serial dictatorship algorithm. The algorithm is deterministic - hence, the order of the agents matters.

Note that the return values are 0-indexed.

Parameters

profile: Profile

A (N, M) array, where N is the number of agents and M is the number of items. The element at (i, j) indicates the agent’s preference for item j, where 1 is the most preferred item. If the agent finds an item unacceptable, the element would be np.nan.

Returns

np.ndarray

A numpy array containing the allocated item for each agent or np.nan if the agent is unallocated.