Motivation. In Game Theory we attempt to formalize our intuitive notion of fairness into rigorous mathematical statements, in order to be able to prove if our allocations are fair or not. There are many different was of doing this, and we will define a few:

  1. Scale Invariance (You can’t compare utilities)
  2. Envy-Free
  3. Pareto Efficiency (see linked definition.)
  4. Proportionality In these definitions, we assume there are divisible items, and agents. We also assume that the Utility Function of the agents are
  • Continuous
  • Strictly increasing across a single item, for all items
  • Concave (diminishing returns) In other words, the agents have Rational Taste.

def. Scale Invariace. An Allocation is fair if it only depends on the ordinal preferences of the agents, not their cardinal value. i.e., if we scale any agent’s utility by , the allocation would not change.

def. Envy-Free (EF). An allocation is envy free if they like their allocation rather than anybody else’s; .

def. Proportionality (Prop). Allocation of of each item to each agent shouldn’t be a better solution than the current allocation for every agent. i.e.

Other Fairness Criteria

  • When EF cannot be achieved we may attempt approximate-envy freeness EF1
  • Maximin Share is another benchmark based on Rawlsian maximin principle.
  • In Ordinal Allocation methods, in a probabilistic allocation setting, we may need to use baysian versions of the above criteria.
  • In Stable Matching Problems, stability is another fairness criteria.

Directory of Allocation Methods

Cardinal Utility Functions

Ordinal Utility Functions

  • Probabilistic Allocation
    • Random Dictatorship – DSIC
    • Proportional Eating – BEF, BPO
  • Stable Allocation (Kideney)
    • Top Trading Cycles (TTC) – DSIC, Stable
  • Stable Matching (Marriage)
    • Gale-Shapley—Proposer-optimal
  • Online
    • Deterministic Ski Rental even in best
    • Randomized Ski Rental
    • Deterministic Whole
    • Fractional Greedy ( in example bad case)
    • Fractional Water-filling ( in example bad case)