2025-07-09 | | Total: 6
Scoring rules elicit probabilistic predictions from a strategic agent by scoring the prediction against a ground truth state. A scoring rule is proper if, from the agent's perspective, reporting the true belief maximizes the expected score. With the development of language models, Wu and Hartline (2024) proposes a reduction from textual information elicitation to the numerical (i.e. probabilistic) information elicitation problem, which achieves provable properness for textual elicitation. However, not all proper scoring rules are well aligned with human preference over text. Our paper designs the Aligned Scoring rule (ASR) for text by optimizing and minimizing the mean squared error between a proper scoring rule and a reference score (e.g. human score). Our experiments show that our ASR outperforms previous methods in aligning with human preference while maintaining properness.
We study k-price auctions in a complete information environment and characterize all pure-strategy Nash equilibrium outcomes. In a setting with n agents having ordered valuations, we show that any agent, except those with the lowest k−2 valuations, can win in equilibrium. As a consequence, worst-case welfare increases monotonically as we go from k=2 (second-price auction) to k=n (lowest-price auction), with the first-price auction achieving the highest worst-case welfare.
This paper explores a novel extension of dynamic matching theory by analyzing a three-way matching problem involving agents from three distinct populations, each with two possible types. Unlike traditional static or two-way dynamic models, our setting captures more complex team-formation environments where one agent from each of the three populations must be matched to form a valid team. We consider two preference structures: assortative or homophilic, where agents prefer to be matched with others of the same type, and dis-assortative or heterophilic, where diversity within the team is valued. Agents arrive sequentially and face a trade-off between matching immediately or waiting for a higher quality match in the future albeit with a waiting cost. We construct and analyze the corresponding transition probability matrices for each preference regime and demonstrate the existence and uniqueness of stationary distributions. Our results show that stable and efficient outcomes can arise in dynamic, multi-agent matching environments, offering a deeper understanding of how complex matching processes evolve over time and how they can be effectively managed.
Assortment optimization is a critical tool for online retailers aiming to maximize revenue. However, optimizing purely for revenue can lead to imbalanced sales across products, potentially causing supplier disengagement and reduced product diversity. To address these fairness concerns, we introduce a market share balancing constraint that limits the disparity in expected sales between any two offered products to a factor of a given parameter α. We study both static and dynamic assortment optimization under the multinomial logit (MNL) model with this fairness constraint. In the static setting, the seller selects a distribution over assortments that satisfies the market share balancing constraint while maximizing expected revenue. We show that this problem can be solved in polynomial time, and we characterize the structure of the optimal solution: a product is included if and only if its revenue and preference weight exceed certain thresholds. We further extend our analysis to settings with additional feasibility constraints on the assortment and demonstrate that, given a β-approximation oracle for the constrained problem, we can construct a β-approximation algorithm under the fairness constraint. In the dynamic setting, each product has a finite initial inventory, and the seller implements a dynamic policy to maximize total expected revenue while respecting both inventory limits and the market share balancing constraint in expectation. We design a policy that is asymptotically optimal, with its approximation ratio converging to one as inventories grow large.
Minimal balanced collections are a generalization of partitions of a finite set of n elements and have important applications in cooperative game theory and discrete mathematics. However, their number is not known beyond n = 4. In this paper we investigate the problem of generating minimal balanced collections and implement the Peleg algorithm, permitting to generate all minimal balanced collections till n = 7. Secondly, we provide practical algorithms to check many properties of coalitions and games, based on minimal balanced collections, in a way which is faster than linear programming-based methods. In particular, we construct an algorithm to check if the core of a cooperative game is a stable set in the sense of von Neumann and Morgenstern. The algorithm implements a theorem according to which the core is a stable set if and only if a certain nested balancedness condition is valid. The second level of this condition requires generalizing the notion of balanced collection to balanced sets.
The design of energy markets is a subject of ongoing debate, particularly concerning the choice between the widely adopted Pay-as-Clear (PC) pricing mechanism and the alternative Pay-as-Bid (PB). These mechanisms determine how energy producers are compensated: under PC, all selected producers are paid the market-clearing price (i.e., the highest accepted bid), while under PB, each selected producer is paid their own submitted bid. The overarching objective is to meet the total demand for energy at minimal cost in the presence of strategic behavior. We present two key theoretical results. First, no mechanism can uniformly dominate PC or PB. This means that for any mechanism M, there exists a market configuration and a mixed-strategy Nash equilibrium of PC (respectively for PB) that yields strictly lower total energy costs than under M. Second, in terms of worst-case equilibrium outcomes, PB consistently outperforms PC: across all market instances, the highest possible equilibrium price under PB is strictly lower than that under PC. This suggests a structural robustness of PB to strategic manipulation. These theoretical insights are further supported by extensive simulations based on no-regret learning dynamics, which consistently yield lower average market prices in several energy market settings.