Minimum cost subset selection with two competing agents
Abstract: We address an optimization problem in which two agents, each with a set of weighted items, compete in order to minimize the total weight of their solution sets. The latter are built according to a sequential game consisting in a fixed number of rounds. In every round each agent submits one item that may be included in its solution set. We study two natural rules to decide which item between the two will be included and, for both rules, we deal with the problem from different perspectives. From a centralized point of view, we investigate (i) the structure and the number of efficient (i.e. Pareto optimal) solutions, (ii) the complexity of finding such solutions, (iii) the best-worst ratio, i.e. the ratio between the efficient solution with largest and smallest total weight, and (iv) existence of Nash equilibria. Moreover, we address the problem from a strategic point of view, that is finding the best moves for one agent against the opponent, in two distinct scenarios. We consider preventive or minimax strategies, optimizing the objective of the agent in the worst case, and best-response strategies, where the items submitted by the opponent are known in advance in each round.
Keywords: Multi-agent optimization, Combinatorial game theory, Pareto optimality, Computational complexity, Minimax strategies, Online algorithms.
Category 1: Combinatorial Optimization
Category 2: Other Topics (Game Theory )
Citation: Technical Report RT-DIA-179-2010, Dipartimento di Informatica e Automazione, Universit\`a Roma Tre.
Entry Submitted: 11/11/2010
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|