0937e642_Game_Theory_Discussion_Group__Title_and_abstract
[Date/Time] October 12, 2004 6:00 -- 7:30 PM [Location] Wean 4623 [Speaker] Vincent Conitzer [Title and abstract] 
Optimization in Multi-Issue Negotiation Settings with Externalities In recent years, certain formalizations of combinatorial negotiation settings, most notably combinatorial auctions, have been intensively studied in our community. A pervasive assumption has been that of no externalities: the agents deciding on a variable (such as whether a trade takes place between them) are the only ones affected by how this variable is set. This does not capture significant aspects of many important negotiation settings, leading to a loss in welfare. For instance, when an agent is deciding whether to build a public good such as a bridge, many other agents may be affected by this decision as they could use the bridge. As another example, a company setting its pollution level may affect the health and safety of many. To date, there has been no widely studied formalization of combinatorial negotiation settings with externalities. In this paper, we introduce such a formalization. We show that in a number of key special cases, it is NP-complete to find a feasible nontrivial solution (and therefore the maximum social welfare is completely inapproximable). However, for one important special case, we give an algorithm which converges to the solution with the maximal concession by each agent (in linear time for piecewise constant functions). Maximizing social welfare, however, remains NP-complete even in this setting. We also briefly mention a special case which can be solved (in polynomial time) by linear programming.
Game Theory Discussion Group
Title and abstract