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 procedure 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.
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aggarwal, G., & Hartline, J. D. (2006). Knapsack auctions. In Proceedings of the 17th annual ACM-SIAM symposium on discrete algorithms (pp. 1083–1092).
Borodin, A., & El-Yaniv, R. (1998). Online computation and competitive analysis. Cambridge: Cambridge University Press.
Brotcorne, L., Hanafi, S., & Mansi, R. (2009). A dynamic programming algorithm for the bilevel knapsack problem. Operations Research Letters, 37, 215–218.
Cardinal, J., & Hoefer, M. (2010). Non-cooperative facility location and covering games. Theoretical Computer Science, 411, 1855–1876.
Demaine, E. D. (2001). In Lecture notes in computer science: Vol. 2136. Playing games with algorithms: algorithmic combinatorial game theory (pp. 18–33).
Felici, G., Mecoli, M., Mirchandani, P. B., & Pacifici, A. (2008). Equilibrium in a two-agent assignment problem. International Journal of Operational Research, 6, 4–26.
Fujimoto, M., & Yamada, T. (2006). An exact algorithm for the knapsack sharing problem with common items. European Journal of Operational Research, 171, 693–707.
Hifi, M., M’Hallab, H., & Sadfi, S. (2005). An exact algorithm for the knapsack sharing problem. Computers and Operations Research, 32, 1311–1324.
Kahn, J., Lagarias, J. C., & Witsenhausen, H. S. (1987). Single-suit two-person card play. International Journal of Game Theory, 16, 291–320.
Katoh, N., Koyanagi, J., Ohnishi, M., & Ibaraki, T. (1992). Optimal strategies for some team games. Discrete Applied Mathematics, 35, 275–291.
Leung, J. Y.-T., Pinedo, M., & Wan, G. (2010). Competitive two-agent scheduling and its applications. Operations Research, 58, 458–469.
Marini, C., Nicosia, G., Pacifici, A., & Pferschy, U. (2010). Minimum cost subset selection with two competing agents. Dipartimento di Informatica e Automazione, Università “Roma Tre”, Technical Report RT-DIA-179-2010.
Nicosia, G., Pacifici, A., & Pferschy, U. (2011). Competitive subset selection with two agents. Discrete Applied Mathematics, 159(16), 1865–1877.
Schlag, K. H., & Sela, A. (1998). You play (an action) only once. Economics Letters, 59, 299–303.
Wang, Z., Xing, W., & Fang, S.-C. (2010). Two-group knapsack game. Theoretical Computer Science, 411, 1094–1103.
Wästlund, J. (2005). A solution of two-person single-suit whist. The Electronic Journal of Combinatorics, 12, R43.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Marini, C., Nicosia, G., Pacifici, A. et al. Strategies in competing subset selection. Ann Oper Res 207, 181–200 (2013). https://doi.org/10.1007/s10479-011-1057-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-011-1057-2