Abstract
We study in this paper single-peakedness on arbitrary graphs. Given a collection of preferences (rankings of alternatives), we aim at determining a connected graph G on which the preferences are single-peaked, in the sense that all the preferences are traversals of G. Note that a collection of preferences is always single-peaked on the complete graph. We propose an Integer Linear Programming formulation (ILP) of the problem of minimizing the number of edges in G or the maximum degree of a vertex in G. We prove that both problems are NP-hard in the general case. However, we show that if the optimal number of edges is \(m-1\) (where m is the number of candidates) then any optimal solution of the continuous relaxation of the ILP is integer and thus the integrality constraints can be relaxed. This provides an alternative proof of the polynomial time complexity of recognizing single-peaked preferences on a tree. We prove the same result for the case of a path (an axis), providing here also an alternative proof of polynomiality of the recognition problem. Furthermore, we provide a polynomial time procedure to recognize single-peaked preferences on a pseudotree (a connected graph that contains at most one cycle). We also give some experimental results, both on real and synthetic datasets.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
All tests were performed on a Intel Core i7-1065G7 CPU with 8 GB of RAM under the Windows OS. We used the IBM Cplex solver for the solution of ILPs.
- 2.
- 3.
Note that this problem differs from that studied by Sliwinski and Elkind [23], where voters’ preferences are independently sampled from rankings that are single-peaked on a given tree, and they manage to identify a maximum likelihood tree.
References
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network flows. Alfred P. Sloan School of Management, Massachusetts Institute of Technology (1988)
Andersen, R., et al.: Trust-based recommendation systems: an axiomatic approach. In: WWW 2008, pp. 199–208. ACM (2008)
Bartholdi III, J., Trick, M.A.: Stable matching with preferences derived from a psychological model. Oper. Res. Lett. 5(4), 165–169 (1986)
Betzler, N., Slinko, A., Uhlmann, J.: On the computation of fully proportional representation. J. Artif. Intell. Res. 47, 475–519 (2013)
Black, D.: On the rationale of group decision-making. J. Polit. Econ. 56(1), 23–34 (1948)
Brandt, F., Brill, M., Hemaspaandra, E., Hemaspaandra, L.A.: Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates. J. Artif. Intell. Res. 53, 439–496 (2015)
Bredereck, R., Chen, J., Woeginger, G.J.: Are there any nicely structured preference profiles nearby? Math. Soc. Sci. 79, 61–73 (2016)
Cheng, W., Hüllermeier, E.: A new instance-based label ranking approach using the Mallows model. In: Yu, W., He, H., Zhang, N. (eds.) ISNN 2009. LNCS, vol. 5551, pp. 707–716. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01507-6_80
Clémençon, S., Korba, A., Sibony, E.: Ranking median regression: learning to order through local consensus. In: ALT, pp. 212–245 (2018)
Cornaz, D., Galand, L., Spanjaard, O.: Bounded single-peaked width and proportional representation. In: ECAI, vol. 12, pp. 270–275 (2012)
Demange, G.: Single-peaked orders on a tree. Math. Soc. Sci. 3(4), 389–396 (1982)
Doignon, J., Falmagne, J.: A polynomial time algorithm for unidimensional unfolding representations. J. Algorithms 16(2), 218–233 (1994)
Elkind, E., Lackner, M., Peters, D.: Structured preferences. In: Trends in Computational Social Choice, Chapter 10, pp. 187–207. AI Access (2017)
Erdélyi, G., Lackner, M., Pfandler, A.: Computational aspects of nearly single-peaked electorates. J. Artif. Intell. Res. 58, 297–337 (2017)
Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.A.: The complexity of manipulative attacks in nearly single-peaked electorates. Artif. Intell. 207, 69–99 (2014)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)
Mattei, N., Walsh, T.: PrefLib: a library for preferences http://www.preflib.org. In: Perny, P., Pirlot, M., Tsoukiàs, A. (eds.) ADT 2013. LNCS (LNAI), vol. 8176, pp. 259–270. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-41575-3_20
Nehring, K., Puppe, C.: The structure of strategy-proof social choice-Part I: general characterization and possibility results on median spaces. J. Econ. Theory 135(1), 269–305 (2007)
Pennock, D.M., Horvitz, E., Giles, C.L.: Social choice theory and recommender systems: analysis of the axiomatic foundations of collaborative filtering. In: AAAI/IAAI, pp. 729–734 (2000)
Peters, D.: Single-peakedness and total unimodularity: new polynomial-time algorithms for multi-winner elections. In: AAAI, pp. 1169–1176 (2018)
Peters, D., Elkind, E.: Preferences single-peaked on nice trees. In: AAAI, pp. 594–600 (2016)
Peters, D., Lackner, M.: Preferences single-peaked on a circle. In: AAAI, pp. 649–655 (2017)
Sliwinski, J., Elkind, E.: Preferences single-peaked on a tree: sampling and tree recognition. In: IJCAI, August 2019
Trick, M.A.: Recognizing single-peaked preferences on a tree. Math. Soc. Sci. 17(3), 329–334 (1989)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Escoffier, B., Spanjaard, O., Tydrichová, M. (2020). Recognizing Single-Peaked Preferences on an Arbitrary Graph: Complexity and Algorithms. In: Harks, T., Klimm, M. (eds) Algorithmic Game Theory. SAGT 2020. Lecture Notes in Computer Science(), vol 12283. Springer, Cham. https://doi.org/10.1007/978-3-030-57980-7_19
Download citation
DOI: https://doi.org/10.1007/978-3-030-57980-7_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-57979-1
Online ISBN: 978-3-030-57980-7
eBook Packages: Computer ScienceComputer Science (R0)