Economic Efficiency Requires Interaction

Shahar Dobzinski

​

Joint work with Noam Nisan and Sigal Oren

Markets

Auctions

Negotiations

Central planner

Is interaction needed in order to efficiently allocate resources?

which of these systems is likely to be more efficient depends ... on whether we are more likely to succeed in putting at the disposal of a single central authority all the knowledge which ... is initially dispersed among many different individuals, or in conveying to the individuals such additional knowledge as they need in order to enable them to fit their plans with those of others.

Hayek (1945) on centralized vs. decentralized systems:

Modeling (lack of) Interaction

Items

Players

eee

ddd

ccc

bbb

aaa

Simultaneous communication complexity:

• All players simultaneously send a message of length l.
• Based only on the messages, the “central planner” has to efficiently allocate resources to the players.

This talk: bipartite matching (unit demand).

• Each player i only knows the set S_i of goods he is connected to.
• Goal: find as big as possible matching.

Challenge: l is too�small to describe S_i.

​

In the paper: more technical results about combinatorial auctions.

Results (bipartite matching)

• Tight bounds for algorithms with message length l=n^ε.
• No simultaneous deterministic algorithm can obtain an approximation ratio of n^1-ε.
• No simultaneous randomized algorithm can obtain an approximation ratio of n^½-ε.
• Little interaction: an O(log n)/ε²-round algorithm with an approximation ratio of 1+ε.
• In each round each bidder sends O(log n) bits.
• Market convergence in sublinear time.

Hardness of Deterministic Simultaneous Bipartite Matching

Theorem: No deterministic algorithm can obtain an approximation ratio of n^1-ε with message length n^ε.

Items

Players

|Optimum| = 3

|Algorithm| = 3

hhh

ggg

fff

eee

ddd

ccc

bbb

aaa

Hardness of Deterministic Simultaneous Bipartite Matching (II)

Construct a fooling instance: change the valuations of players to ones that are mapped to the same simultaneous message. Intuition: |valuations| >> |messages|.

Items

Players

|Optimum| = 5

|Algorithm| = 3

hhh

ggg

fff

eee

ddd

ccc

bbb

aaa

Outline of the Proof of Hardness of Bipartite Matching

• Select x items at random and connect all players to them.
• The size of the optimal matching is x.
• Hard part: show that we can change the neighbor set of most players while ensuring that:
1. The messages (and hence the allocation) remain the same.
2. The size of the matching of the algorithm doesn’t increase.
3. Value of the new optimal matching is large.
• We have a new instance with optimal matching about n but the algorithm matches only x vertices.

​

​

Rounds: Little Interaction can Help

• Assume players have value 1 for vertices in their neighbor set. The “usual” ascending auction:
• Initialize the price p_j of every item j to 0, all players are unsatisfied.
• While there is some unsatisfied player i:
• Give i one of his most profitable items j. Increase p_j by ε.
• Player i is satisfied now. The previous player i’ that got j is unsatisfied if he demands some item at the current prices.
• Theorem [Demange et al’86]: (1+ε)-approximation is reached after n/ε rounds.

​

Our Algorithm

• Initialize the price p_j of every item j to 0, all players are unsatisfied.
• In every round, each unsatisfied player i reports simultaneously with the others a random most profitable item j:
• If item j was reported by at least one player, give j to an arbitrary player i that reported it. Increase p_j by ε.
• Player i is satisfied now. The previous player i’ that got j is unsatisfied if he demands some item at the current prices.
• Theorem: after O(log n)/ε² rounds we get a (1+ε) approximation.

​

Results (combinatorial auctions with subadditive bidders)

• A simultaneous algorithm with an approximation ratio of m^1/3 and polynomial message length.
• No simultaneous algorithm can obtain an approximation ratio of m^¼ with polynomial message length.
• In contrast, an interactive 2-approximation algorithm is known (Feige’06).
• The main technical construction of the paper.
• A k-round algorithm with an approximation ratio of O(k*m^1/(k+1)).
• In particular, a polylogarithmic approximation in �O(log m) rounds.

Summary

• Lack of interaction implies hardness of reaching an efficient allocation.
• Little interaction may help.
• Open questions:
• Gross substitutes valuations? Submodular?
• Lower bounds for rounds.
• Incentives?