CS Paper Radar

From Outranking Flow Scores to Linear Programs: Group Decision Making in PROMETHEE II

Alexandre Flachs, Yves De Smet

cs.AI ·submitted 2026-10-25 18:12 UTC · v1
published

Abstract

We study inverse and consensus analysis for PROMETHEE II ranking problems when the performance table is fixed. Existing approaches in PROMETHEE-based sensitivity and consensus analysis usually focus on deviations of criteria weights while treating preference functions as fixed. Nevertheless both sets of parameters jointly determine the outranking flow scores. We introduce a linear reparametrization of the PROMETHEE II net flow scores based on weighted preference increments over the observed differences of performances. This representation yields a linear expression of the net flows and clarifies how weights and preference functions interact. Building on this result, we derive linear optimization models for three settings: minimizing weight deviations while allowing preference functions to vary; minimizing deviations over the full set of preference parameters; and multiple decision-maker consensus analysis (with objectives based either on total deviation or on the maximal individual deviation to promote fairness). An illustrative example shows that allowing preference functions to vary can dramatically change the inverse-analysis conclusions obtained from weight-only models, and that the proposed group formulations distinguish efficient consensuses from fairer ones.

Comment
15 pages; 1 figure; to be published in Algorithmic Decision Theory, 9th International Conference, ADT 2026, Lecture Notes in Computer Science

Closest papers

Nearest neighbours by meaning across the whole index.

Matchings under One-Sided Preferences with Soft Quotas

cs.DS ·2026-11-03 ·Santhini K A, Raghu Raman Ravi, Meghana Nasre
top venue similarity 0.61
Abstract

Assigning applicants to posts in the presence of applicant preferences and quotas associated with posts is extensively investigated. For a post, a lower quota guarantees, and an upper quota limits the number of applicants assigned to it. Typically, quotas are assumed to be fixed, which need not be the case in practice. We address this by introducing a soft quota setting, in which every post is associated with two values - lower target and upper target - which together denote a range for the intended number of applicants in any assignment. Unlike the fixed quota setting, we allow the number of applicants assigned to a post to fall outside the range. This leads to assignments with deviation. Here, we study the problem of computing an assignment that has two orthogonal optimization objectives - minimizing the deviation (maximum or total) with respect to soft quotas and ensuring optimality with respect to preferences of applicants (rank-maximality or fairness). The order in which these objectives are considered, the different possibilities to optimize deviation combined with the well-studied notions of optimality with respect to preferences open up a range of optimization problems of practical importance. We present efficient algorithms based on flow networks to solve these optimization problems. We also consider a generalization of the soft quota setting, where every deviation is associated with a cost. We show extensions of our algorithms for solving the problems in this setting.

0.65

Weight Certificates for Convex Multi-Objective MPC: Geometric Characterization, $\ell^1$ Construction, and $\ell^2$ Foreclosure

eess.SY math.OCmath.AG ·2026-08-12 ·Hadi Hajieghrary, Benedikt Walter, Chaitanya Shinde, Miguel Hurtadoand Jerry Lopez
similarity 0.58
Abstract

Automated-driving rulebooks rank rule violations lexicographically, and model predictive control enforces that ranking either exactly, through $L{+}1$ sequential programs per tick, or approximately, through a weighted sum tuned by the separation heuristic $w_1\gg w_2\gg\cdots\gg w_L$. We show the heuristic answers the wrong question. For a convex priority-ordered program, a weighted sum reproduces the lexicographic optimum precisely when its weight, augmented by a unit performance coefficient, supports the upper image of the achievement map at the lexicographic point; the admissible weights form the unit-performance slice of an outward normal cone. Under hinge penalties this slice is a polyhedron obtained by projecting a scaled-KKT system, and a linear program returns an interior weight with a certified margin; under squared-hinge penalties no finite weight is exact whenever the limiting multiplier is nonzero, with violation along the local minimizer branch decaying as $O(1/w)$. Calibrated on held-out logs, the resulting weights have near-equal tier components in nine of eleven calibration-eligible scenario classes and roughly double legal-tier event precision against a matched heuristic weight in closed-loop nuPlan experiments on a 25-rule rulebook. The certificate is, however, pointwise: no single weight is valid across the sampled ticks of an episode, the median lifetime is one sampling interval (zero subsequent ticks at the native rate), and persistence tracks active-set stability. These findings motivate monitored weighted solves with selective cascade fallback, although the compliance-pattern monitor detects only a subset of measured lapses.

0.04

Adaptive Doubly Robust Off-Policy Evaluation for Ranking Policies under Diverse User Behavior

cs.LG cs.IR ·2026-08-30 ·Kosuke Iguchi, Ren Kishimoto
published similarity 0.57
Abstract · 14 pages, 4 figures, 7 tables. Accepted at CONSEQUENCES 2026 and selected for oral presentation

Off-policy evaluation (OPE) of ranking policies is challenging be- cause selecting and ordering multiple items from a candidate set makes the number of possible rankings grow combinatorially with the number of candidates and the ranking length. Consequently, Inverse Propensity Scoring (IPS), whose importance weight is the full-ranking probability ratio under the evaluation and logging policies, can have excessive variance. Independent IPS (IIPS) and Reward Interaction IPS (RIPS) reduce variance by imposing fixed assumptions on how users browse rankings, but may introduce bias when those assumptions mismatch actual behavior. Adaptive Inverse Propensity Scoring (AIPS) addresses this trade-off by adap- tively marginalizing importance weights over the actions that affect each position-wise reward. It attains minimum variance within a class of unbiased IPS-based estimators when the true user be- havior model is observed. However, its estimation accuracy may still degrade for longer rankings, and AIPS does not use a reward model for residual correction. We propose Adaptive Doubly Robust (ADR), which combines adaptive importance weighting with re- ward regression through a control-variate correction. We establish its unbiasedness when the true user behavior model is observed and characterize a sufficient condition under which it reduces vari- ance relative to AIPS. Across synthetic experiments with 10,000 simulations per condition, ADR improves mean squared error over AIPS and conventional ranking OPE estimators across a range of logged-data sizes and ranking lengths.

0.46

Proximal Preference Optimization: A Unified Framework for Stable and Reward-Free Alignment

cs.LG cs.AI ·2026-11-07 ·Qisai Liu, Zhanhong Jiang, Zahid Hasan, Soumik Sarkar
theorycode/data similarity 0.57
Abstract · 10 pages, 4 figures, IEEE BigData 2026

We introduce a proximal preference optimization framework that unifies the implicit reward formulation of Direct Preference Optimization (DPO) with the trust-region stability of Proximal Policy Optimization (PPO). Our framework yields two complementary algorithms. P$^2$O (Proximal Preference Optimization) introduces a clipped importance ratio directly into the DPO preference margin, producing a reward-model-free algorithm that supports safe dataset reuse, bounded policy divergence, and monotonic preference improvement guarantees. PKTO (Proximal Kahneman-Tversky Optimization) extends P$^2$O by replacing the DPO margin with KTO's prospect-theoretic utility margins, adding a self-regulating adaptive baseline that tightens the effective trust region as the policy drifts, and an asymmetric weighting that handles imbalanced or asymmetric preference datasets. We provide a unified theoretical analysis, including Kullback Leibler (KL) trust-region bounds, a policy-improvement lower bound, and convergence guarantees under multi-epoch proximal updates. Empirically, P$^2$O and PKTO match or exceed DPO and KTO in alignment quality while maintaining better stability under repeated dataset reuse across multiple LLMs on three preference benchmarks. The code base is available here.

0.33

A Framework for Designing Reward Functions: From Objectives to Features to Human-Aligned Reward Functions

cs.LG ·2026-08-12 ·Di Yang Shi, W. Bradley Knox
published similarity 0.56
Abstract · Presented at RLC "Finding the Frame" and "AutoRL" workshops

We present a formal process to enable non-experts to instantiate and iterate on human-aligned reward functions, i.e. reward functions that adhere to a given preference ordering over trajectories. Given a task described in natural language, our process produces a linear reward function in three steps: distill the task's objectives into a set of fundamental objectives and derive measurable outcome variables that capture those fundamental objectives, select a causally representative subset of outcome variables as the reward terms, and fit weights to those reward terms via preference elicitation. Our contributions describe the first step and formalize the latter two steps. The first is a guided workflow for deriving outcome variables. The second is a reduction of reward term selection to minimum-cost partial cover on a causal DAG, solved in polynomial time via max-flow. The third is a geometric framing of weight fitting as a convex feasibility problem iteratively narrowed by preference queries, solved by existing separation oracle methods. To the best of our knowledge, this is the first reward-design method that maintains a deterministically conflict-free feasible weight region, narrowed to a desired tolerance via a separation oracle with O(n log κ) preference queries.

0.19

Incentive Design for Multi-Agent Systems: A Bilevel Optimization Framework for Coordinating Independent Agents and Convergence Analysis

eess.SY ·2026-09-22 ·Xinyi Wei, Shuo Han, Jie Fu
similarity 0.56
Abstract

Incentive design aims to guide the performance of a system towards a human's intention or preference. We study this problem in a multi-agent system with one leader and multiple followers. Each follower independently solves a mdp to maximize its own expected total return with the same state space and action space. However, the leader's objective depends on the collective best-response policies of all followers. To influence these policies of followers, the leader provides side payments as incentives to individual followers at a cost, aiming to align the collective behaviors of followers with its own goal while minimizing this cost of incentive. Such a leader-followers interaction is formulated as a bilevel optimization problem: the lower level consists of followers individually optimizing their MDPs given the side payments, and the upper level involves the leader optimizing its objective function given the followers' best responses. The main challenge to solve the incentive design is that the leader's objective is generally non-concave and the lower level optimization problems can have multiple local optima. To this end, we employ a constrained optimization reformation of this bi-level optimization problem and develop an algorithm that provably converges to a stationary point of the original problem, by leveraging several smoothness properties of value functions in MDPs. We validate our algorithm in a stochastic gridworld by examining its convergence, verifying that the constraints are satisfied, and evaluating the improvement in the leader's performance.

0.17

Hidden Disparities in Ranking: Category-Aware Fairness via Distributional Stability

cs.LG stat.ML ·2026-10-29 ·Gayane Taturyan, Charlotte Laclau, Stephan Clémençon
similarity 0.56
Abstract

We study the problem of fair ranking in recommender systems. We provide a formal probabilistic framework in which ranking policies are distributions over permutations, and the utility of a user is the exposure given to the items they interact with, relative to that of an ideal ranking. We consider utility parity across user groups, as well as its category-aware refinement, conditional utility parity, which requires parity within each category of items. Following a recent view of fairness as distributional stability, we show that both criteria are equivalent to the stability of the utility under changes in the composition of user groups. Optimizing over mixtures of ranking policies leads to a second-order cone program, for which we provide generalization bounds. A numerical study validates our theoretical findings.

0.23

Multi-Expert Conformal Risk Control for Pairwise LLM Judging in Open-Ended Dialogue

cs.CL ·2026-08-27 ·Ming Cheng, Yusheng Dai, Qiuhong Ke, Zhaolin Chen, Lizhen Qu
top venuebenchmark similarity 0.56
Abstract · Accepted to EMNLP 2026 Main Conference

In this paper, we explore multi-expert Conformal Risk Control (CRC) algorithms for pairwise LLM-as-a-Judge evaluation in open-ended dialogue. Our core insight is that multi-expert aggregation offers a complementary remedy to CRC: whereas CRC controls risk at the decision threshold through abstention, aggregation sanitizes the scoring function at its source. Guided by this, we first design two multi-expert CRC methods: Score Averaging and Decision Voting, which aggregate at the score and decision levels, respectively. While both strategies outperform single-expert methods on homogeneous expert panels, on heterogeneous LLM judges they remain risk-valid but recover only limited coverage, because a uniform threshold cannot match the experts' distinct scoring scales. To resolve this issue, we further propose Marginal-Calibrated Conformal Consensus (MC3): it captures distinct per-expert scales via initial threshold ratios, while jointly tuning a unified decision function $C_t(x)$ applied identically in both calibration and test, thereby preserving exchangeability. To evaluate our framework, we construct Panel, a 1,800-pair human pairwise-preference benchmark for open-ended dialogue. It is built on responses generated by four open-weight LLMs over dialogue contexts from three domains (ESConv, MSC, DREAM), with full logit access. In experiments, we find that both Score Averaging and Decision Voting substantially improve accuracy and acceptance rate on homogeneous panels. Notably, MC3 extends these gains to heterogeneous panels by accommodating distinct per-expert scoring scales across all three datasets.

0.38