Competitive subset selection with two agents
Abstract: We address an optimization problem in which two agents, each with a set of weighted items, compete in order to maximize the total weight of their winning 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 for possible inclusion in its winning set. We study two natural rules to decide the winner of each round. 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. Finally, we address the problem from a single agent perspective. We consider preventive or maximin strategies, optimizing the objective of the agent in the worst case, and best response strategies, where the items submitted by the other agent are known in advance either in each round (on-line) or for the whole game (off-line).
Keywords: multi-agent optimization; combinatorial game theory; on-line strategies; computational complexity
Category 1: Other Topics (Game Theory )
Category 2: Combinatorial Optimization
Citation: A preliminiary, shortened version appeared as: Proceedings of the International Conference on Algorithmic Decision Theory (ADT 2009), Springer Lecture Notes in Computer Science 5783, 74-85, 2009.
Entry Submitted: 11/02/2009
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|