BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Olivier Spanjaard

Olivier Spanjaard appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Artificial IntelligenceComputational ComplexityComputer Science and Game TheoryDiscrete MathematicsMachine Learningmath.OC

Catalog footprint

What is connected

6works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

6 published item(s)

preprint2022arXiv

Beyond Pairwise Comparisons in Social Choice: A Setwise Kemeny Aggregation Problem

In this paper, we advocate the use of setwise contests for aggregating a set of input rankings into an output ranking. We propose a generalization of the Kemeny rule where one minimizes the number of k-wise disagreements instead of pairwise disagreements (one counts 1 disagreement each time the top choice in a subset of alternatives of cardinality at most k differs between an input ranking and the output ranking). After an algorithmic study of this k-wise Kemeny aggregation problem, we introduce a k-wise counterpart of the majority graph. This graph reveals useful to divide the aggregation problem into several sub-problems, which enables to speed up the exact computation of a consensus ranking. By introducing a k-wise counterpart of the Spearman distance, we also provide a 2-approximation algorithm for the k-wise Kemeny aggregation problem. We conclude with numerical tests.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Cautious Learning of Multiattribute Preferences

This paper is dedicated to a cautious learning methodology for predicting preferences between alternatives characterized by binary attributes (formally, each alternative is seen as a subset of attributes). By "cautious", we mean that the model learned to represent the multi-attribute preferences is general enough to be compatible with any strict weak order on the alternatives, and that we allow ourselves not to predict some preferences if the data collected are not compatible with a reliable prediction. A predicted preference will be considered reliable if all the simplest models (following Occam's razor principle) explaining the training data agree on it. Predictions are based on an ordinal dominance relation between alternatives [Fishburn and LaValle, 1996]. The dominance relation relies on an uncertainty set encompassing the possible values of the parameters of the multi-attribute utility function. Numerical tests are provided to evaluate the richness and the reliability of the predictions made.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Weighted majority tournaments and Kemeny ranking with 2-dimensional Euclidean preferences

The assumption that voters' preferences share some common structure is a standard way to circumvent NP-hardness results in social choice problems. While the Kemeny ranking problem is NP-hard in the general case, it is known to become easy if the preferences are 1-dimensional Euclidean. In this note, we prove that the Kemeny ranking problem remains NP-hard for $k$-dimensional Euclidean preferences with $k\!\ge\!2$ under norms $\ell_1$, $\ell_2$ and $\ell_\infty$, by showing that any weighted tournament (resp. weighted bipartite tournament) with weights of same parity (resp. even weights) is inducible as the weighted majority tournament of a profile of 2-Euclidean preferences under norm $\ell_2$ (resp. $\ell_1,\ell_{\infty}$), computable in polynomial time. More generally, this result regarding weighted tournaments implies, essentially, that hardness results relying on the (weighted) majority tournament that hold in the general case (e.g., NP-hardness of Slater ranking) are still true for 2-dimensional Euclidean preferences.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Bayesian preference elicitation for multiobjective combinatorial optimization

We introduce a new incremental preference elicitation procedure able to deal with noisy responses of a Decision Maker (DM). The originality of the contribution is to propose a Bayesian approach for determining a preferred solution in a multiobjective decision problem involving a combinatorial set of alternatives. We assume that the preferences of the DM are represented by an aggregation function whose parameters are unknown and that the uncertainty about them is represented by a density function on the parameter space. Pairwise comparison queries are used to reduce this uncertainty (by Bayesian revision). The query selection strategy is based on the solution of a mixed integer linear program with a combinatorial set of variables and constraints, which requires to use columns and constraints generation methods. Numerical tests are provided to show the practicability of the approach.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Recognizing Single-Peaked Preferences on an Arbitrary Graph: Complexity and Algorithms

This paper is devoted to a study of single-peakedness on arbitrary graphs. Given a collection of preferences (rankings of a set 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 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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

An Axiomatic Approach to Robustness in Search Problems with Multiple Scenarios

This paper is devoted to the search of robust solutions in state space graphs when costs depend on scenarios. We first present axiomatic requirements for preference compatibility with the intuitive idea of robustness.This leads us to propose the Lorenz dominance rule as a basis for robustness analysis. Then, after presenting complexity results about the determination of robust solutions, we propose a new sophistication of A* specially designed to determine the set of robust paths in a state space graph. The behavior of the algorithm is illustrated on a small example. Finally, an axiomatic justification of the refinement of robustness by an OWA criterion is provided.

0 citations0 reviewsNo code linkedOpen access