Extension of Excess Demand Ascending Auction to Multi-Demand Model by Discrete Convex Analysis Approach
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917450693476352 |
|---|---|
| author | Murota, Kazuo Shioura, Akiyoshi |
| author_facet | Murota, Kazuo Shioura, Akiyoshi |
| contents | We consider the problem of finding the (unique) minimal Walrasian equilibrium price in multi-item, multi-unit auction models: there are multiple indivisible items for sale, with several units of each item, and a bidder may be interested in buying more than one copy of each item. In its special case with unit-demand bidders, where each bidder demands at most one unit of any item, Andersson, Andersson, and Talman (2013) proposed a general framework of ascending auction algorithms based on the concept of excess-demand item set. This paper extends this approach to the multi-unit case by exploiting the discrete convexity of the Lyapunov function associated with the auction model. In particular, we make use of the facts that (i) the equilibrium price vectors are characterized as the minimizers of the Lyapunov function, (ii) the Lyapunov function is an instance of an L-natural-convex function, and (iii) a concept generalizing ``excess-demand item set'' can be defined in L-natural-convex function minimization in general. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_27765 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Extension of Excess Demand Ascending Auction to Multi-Demand Model by Discrete Convex Analysis Approach Murota, Kazuo Shioura, Akiyoshi Combinatorics 91B26, 52A41, 90C25 We consider the problem of finding the (unique) minimal Walrasian equilibrium price in multi-item, multi-unit auction models: there are multiple indivisible items for sale, with several units of each item, and a bidder may be interested in buying more than one copy of each item. In its special case with unit-demand bidders, where each bidder demands at most one unit of any item, Andersson, Andersson, and Talman (2013) proposed a general framework of ascending auction algorithms based on the concept of excess-demand item set. This paper extends this approach to the multi-unit case by exploiting the discrete convexity of the Lyapunov function associated with the auction model. In particular, we make use of the facts that (i) the equilibrium price vectors are characterized as the minimizers of the Lyapunov function, (ii) the Lyapunov function is an instance of an L-natural-convex function, and (iii) a concept generalizing ``excess-demand item set'' can be defined in L-natural-convex function minimization in general. |
| title | Extension of Excess Demand Ascending Auction to Multi-Demand Model by Discrete Convex Analysis Approach |
| topic | Combinatorics 91B26, 52A41, 90C25 |
| url | https://arxiv.org/abs/2604.27765 |