Buyer-Supplier Games

In a buyer-supplier game, a special type of assignment game, a distinguished player, called the buyer, wishes to purchase some combinatorial structure. A set of players, called suppliers, offer various components of the structure for sale. Any combinatorial minimization problem can be transformed into a buyer-supplier game. While most previous work has been concerned with characterizing the core of buyer-supplier games, in this work we focus on optimization over the set of core vectors.

We give a polynomial time algorithm for optimizing over the core of any buyer-supplier game for which the underlying minimization problem is solvable in polynomial time. In addition, we show a matching negative result that it is hard to determine whether a given vector belongs to the core if the base minimization problem is not solvable in polynomial time. Finally, we introduce and study the concept of focus point price, which answers the question: If we are constrained to play in equilibrium, how much can we lose by playing the wrong equilibrium?

You can also view a talk on buyer-supplier games.

Papers

Nedialko B. Dimitrov and C. Greg Plaxton. Buyer-Supplier Games: Optimization Over the Core. Theoretical Computer Science, in press, June 2009, doi:10.1016/j.tcs.2009.05.017

Nedialko B. Dimitrov and C. Greg Plaxton. Buyer-Supplier Games: Core Characterization and Computation. UT Austin, Technical Report T-06-19, April, 2006

Nedialko B. Dimitrov and C. Greg Plaxton. Buyer-Supplier Games: Optimization Over the Core. Proceedings of the 5th annual Workshop on Approximation and Online Algorithms (WAOA07), October, 2007

Comments and Questions


Warning: Creating default object from empty value in /home/nedd/neddimitrov.org/modules/CGExtensions/CGExtensions.module.php on line 630
Add a comment

Add A Comment

Visual Captcha
Code in the picture:
Your Name(*):
Comment(*):
 


© Copyright 2004-2017 - Ned Dimitrov