Welfare Maximization in Congestion Games

Liad Blumrosen and Shahar Dobzinski��The Hebrew University

Example: File Sharing Systems�(Positive Externalities)

Example: Scheduling�(Negative Externalities)

Related Work

• Both in game theory and computer science.

​

• Examples:
• Pure Nash: Rosenthal 73’, Monderer-Shapley 96’
• Price of Anarchy: Roughgarden & Tardos 02’,…
• …

The Model

• n players, m resources
• v_i(j,k) - the (non-negative) benefit for player i from using resource j with exactly k-1 other players

​

​

​

• An anonymous model �(player-specific games, Milchtaich 96)

​

Goal: welfare maximization (centralized point of view)�

Find an assignment (S₁,…,S_n) of players to resources to maximizes the welfare Σ_jΣ_i∈Sjv_i(j,|Sj|)

• Each player can be assigned to at most one resource.

​

Value

Congestion

Related Work (cont.)

• Closest in spirit: paper by�Chakrabarty, Mehta, Nagarajan and Vazirani 05’
• Cost minimization, negative externalities

Main Results

1. Relation to combinatorial auctions.�
2. Approximation algorithms:
• Main result: an O(1)-approximation
• Even with valuations unresetricted externalities.
• Constant approximation lower bounds

​

• Mechanism design:
• An O(m^½log n) truthful mechanism
• with monotone valuations

Congestion Games

Resource 1

Resource 2

Resource 3

Players

Congestion Games

Resource 1

Resource 2

Resource 3

Combinatorial Auctions

• m items for sale.
• n bidders, each bidder i has a value v_i(S) for every bundle of items S
• Goal: find a partition S₁,…,S_n of the items such that the total welfare Σv_i(S_i) is maximized.

Resource 1

Resource 2

Resource 3

Players

Combinatorial Auctions

Resource 1

Resource 2

Resource 3

Value: 2

Value: 4

Value: 6

Every congestion game has a corresponding

combinatorial auction with the same optimal welfare

Combinatorial Auctions & Congestion Games

• Similarities -- “Hierarchy” Results:
• Negative externalities 🡪 substitutabilities
• Specifically, a subclass of XOS
• Positive externalities 🡪 complementarities

​

• Differences:
• Incentives are treated differently�like a combinatorial auction with strategic items
• Different types of reasonable queries.

Main Algorithmic Result

An O(1)-approximation algorithm for congestion games with unrestricted externalities

The First Step – Solving the LP

• Solve the linear relaxation of the problem:

Maximize: Σ_j,Sx_j,Sv_i(j,|S|)

Subject to:

• For each player i: Σ_j,S|i∈Sx_i,S ≤ 1
• For each resource j: Σ_Sx_j,S ≤ 1
• For each j,S: x_j,S ≥ 0

​

• Solvable in polynomial time even though the number of variables is exponential.

The First Lottery

• Reminder: Given the fractional solution: �X_j,S = the fraction of the set of players S assigned to resource j
• Assign to each resource j:
• the players in S with probability x_j,S/10
• φ with probability 1-Σ_Sx_j,S/10
• The expected welfare is OPT/10, but the solution is not necessarily feasible.

Not feasible because players are assigned to more than one resource.

After the First Lottery

• Claim: with constant probability the solution produced by the first lottery has the following properties:
• The welfare is at least OPT/50
• The total number of assignments after the first lottery is at most n/2
• Each player is assigned to at most one resource in the LP, so the expected number of assignments is n/10.

Unassigned Players

Second Lottery

• Assign each player i to exactly one resource:
• Choose a resource uniformly at random from the set of resources i was assigned to.
• Use the unassigned players to keep the congestion on each resource the same.

Unassigned Players

The solution is now feasible!

Same number of users are using the resource before and after second lottery

We have enough unassigned players.

Analysis of the Approximation Ratio

• Lemma: The expected number of resources a player is assigned to after the first lottery is O(1).
• Corollary: We lose only a constant fraction of the welfare in the second lottery.

Value: 1

Value: 2

Value: 2

Value: 0

Value: 0

Value: 4

Value: 2

Value: 2

Value: 3

Value: 4

The Algorithm – The Big Picture

• Solve the linear relaxation.
• First Lottery: use randomized rounding and obtain an (unfeasible) assignment such that:
• The welfare is at least OPT/50
• The total number of assignments is at most n/2
• Second Lottery: select uniformly at random one assignment of each player, and arbitrarily replace the rest of the assignments of that player.
• We lose only a constant fraction of the welfare because the expected number of assignments per player is constant.

Summary and Open Questions

• We study congestion games from a centralized of view.
• With different types of externalities.

​

• Open Question: closing the gaps in the approximation ratios.

​

• Open Question: designing polynomial-time truthful mechanisms with better performance.
• More generally, design mechanisms for multi-parameter settings with externalities.