5 papers
Maximin Shares with Lower Quotas
Hirota Kinoshita, Ayumi Igarashi
We study the fair division of indivisible items among agents with heterogeneous additive valuations, subject to lower and upper quotas on the number of items allocated to each…
A Relative-Budget Theory for Reinforcement Learning with Verifiable Rewards in Large Language Model Reasoning
Akifumi Wachi, Hirota Kinoshita, Shokichi Takakura +2
Reinforcement learning (RL) is a dominant paradigm for improving the reasoning abilities of large language models, yet its effectiveness varies across tasks and compute budgets. We…
Achieving PAC Guarantees in Mechanism Design through Multi-Armed Bandits
Takayuki Osogami, Hirota Kinoshita, Segev Wasserkrug
We analytically derive a class of optimal solutions to a linear program (LP) for automated mechanism design that satisfies efficiency, incentive compatibility, strong budget balanc…
A Faster Deterministic Algorithm for Mader's -Path Packing
Satoru Iwata, Hirota Kinoshita
Given an undirected graph with a set of terminals partitioned into a family of disjoint blocks, find the maximum number of vertex-disjoint…
Socially efficient mechanism on the minimum budget
Hirota Kinoshita, Takayuki Osogami, Kohei Miyaguchi
In social decision-making among strategic agents, a universal focus lies on the balance between social and individual interests. Socially efficient mechanisms are thus desirably de…