Moshe Babaioff on Undominated Strategies

Theory Lunch, October 12, 2005

Minutes by Varsha Dani

Moshe Babaioff spoke about his work on mechanism design, which is the study of the working of markets in the presence of strategic agents, when both the mechanism and the agents have bounded computational resources.

Moshe started by describing the Edge Disjoint Path Problem (EDP):
There are n agents and a directed graph G whose edges are to be divided among them. (Each edge may be used only once.) Each agent, i, has source and target vertices s_i and t_i in G and wants a path in G that connects s_i to t_i; she values such a path at v_i. (The agent derives no value from a set of edges that does not connect s_i to t_i.)The goal of the mechanism is to assign the edges of G to the agents so as to maximize the sum of their values ("social welfare"). Two information models are considered, one in which the source and target of each agent are public knowledge and only the values are private, and another in which the source, target and value are all private information.

The EDP problem is a special case of a combinatorial auction. Here m goods are to be distributed among n agents. The agents have private monotone valuation functions that specify their desire for for each subset of goods. The mechanism elicits bids from the agents and allocates goods to them (in exchange for payments) to maximize social welfare. Although the agents can behave strategically, the goal of the mechanism is to to assign payments in such a way that each agent's best strategy is to truthfully declare their valuation. Note, however, that in general valuation functions are exponential even to merely express.

EDP is a special case in which the agents are "single-valued" i.e. they have the same value for all desired bundles.

Maximizing social welfare in combinatorial auctions is NP-hard. In fact even if each agent wants a single set (single-minded agent), it is hard to approximate better that m^{1/2 - \epsilon} unless ZPP = NP.

In the case of of single minded agents whose desired bundles are known, Moshe described a procedure to create a truthful mechanism from a c-approximation algorithm for the pure allocation problem.

The mechanism is an iterative process. On each round each agent bids a value for their desired bundle. Using the approximation algorithm, the mechanism comes up with a set of winners (who receive their desired bundles) and losers (who don't). On the next round winners may continue with the same bid, while losers have the choice to double their bid or retire from the game forever. Iterations continue until no loser wants to double their bid and continue. Moshe staeted the theorem that this mechanism is truthful and achieves an O(c log v_max) approximation in dominant strategies, and is moreover Pareto efficient.

Finally, returning to the unknown multiminded single valued case (e.g. the EDP problem) Moshe described a similar process to create a mechanism from a \sqrt{m} approximation algorithm. In this scenario dominant strategy equilibrium is not obtained. Instead the mechanism achieves an O(\sqrt{m} log^2 v_max) approximation in undominated strategies. However, Moshe pointed out that the startegy profile actually played is not an equilibrium in genearl. Thus this is an algorithmic implementation concept rather than an equilibrium concept.