9 papers
Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets
Taihei Oki, Shinsaku Sakaue
We study online inverse linear optimization, also known as contextual recommendation, where a learner sequentially infers an agent's hidden objective vector from observed optimal a…
Generalizing the Multiple Exchange Property for Matroid Bases
Taihei Oki, Tamás Schwarcz
The multiple exchange property for matroid bases states that for any bases and of a matroid and any subset , there exists a subset $Y\subseteq B\se…
Ascending Auctions for Combinatorial Markets with Frictions: A Unified Framework via Discrete Convex Analysis
Taihei Oki, Ryosuke Sato
We develop a unified ascending-auction framework for computing Walrasian equilibria in combinatorial markets with strong substitutes valuations and piecewise-linear payment functio…
No-Regret M-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Setting
Taihei Oki, Shinsaku Sakaue
M-concave functions, a.k.a. gross substitute valuation functions, play a fundamental role in many fields, including discrete mathematics and economics. In practice,…
Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound
Shinsaku Sakaue, Taira Tsuchiya, Han Bao +1
In online inverse linear optimization, a learner observes time-varying sets of feasible actions and an agent's optimal actions, selected by solving linear optimization over the fea…
Algorithmic aspects of semistability of quiver representations
Yuni Iwamasa, Taihei Oki, Tasuku Soma
We study the semistability of quiver representations from an algorithmic perspective. We present efficient algorithms for several fundamental computational problems on the semistab…