Optimization Online


Competitive subset selection with two agents

Gaia Nicosia(nicosia***at***dia.uniroma3.it)
Andrea Pacifici(pacifici***at***disp.uniroma2.it)
Ulrich Pferschy(pferschy***at***uni-graz.at)

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.

Download: [PDF]

Entry Submitted: 11/02/2009
Entry Accepted: 12/01/2009
Entry Last Modified: 11/02/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society