Approximation of Walrasian equilibrium in single-minded auctions

Li Sha Huang; Minming Li; Bo Zhang

doi:10.1016/j.tcs.2005.03.008

Approximation of Walrasian equilibrium in single-minded auctions

Li Sha Huang^*
, Minming Li
, Bo Zhang

^*此作品的通讯作者

Tsinghua University

科研成果: 期刊稿件 › 文章 › 同行评审

4 引用（Scopus）

摘要

We consider a social optimization model of pricing scheme in single-minded auctions, in cases where Walrasian equilibrium does not exist. We are interested in the maximization of the ratio, R, of happy bidders over all agents, in a feasible allocation-pricing scheme. We show NP-hardness of the optimization problem, establish lower and upper bounds of R, as well as develop greedy algorithms to approximate the optimal value of R.

源语言	英语
页（从-至）	390-398
页数	9
期刊	Theoretical Computer Science
卷	337
期	1-3
DOI	https://doi.org/10.1016/j.tcs.2005.03.008
出版状态	已出版 - 9 6月 2005
已对外发布	是

访问文件

10.1016/j.tcs.2005.03.008

其它文件与链接

链接到 Scopus 的出版物

引用此

@article{8380fb6b97214c03b2a93fa6e2f7dcea,

title = "Approximation of Walrasian equilibrium in single-minded auctions",

abstract = "We consider a social optimization model of pricing scheme in single-minded auctions, in cases where Walrasian equilibrium does not exist. We are interested in the maximization of the ratio, R, of happy bidders over all agents, in a feasible allocation-pricing scheme. We show NP-hardness of the optimization problem, establish lower and upper bounds of R, as well as develop greedy algorithms to approximate the optimal value of R.",

keywords = "Combinatorial auction, Walrasian equilibrium",

author = "Huang, \{Li Sha\} and Minming Li and Bo Zhang",

year = "2005",

month = jun,

day = "9",

doi = "10.1016/j.tcs.2005.03.008",

language = "英语",

volume = "337",

pages = "390--398",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Approximation of Walrasian equilibrium in single-minded auctions

AU - Huang, Li Sha

AU - Li, Minming

AU - Zhang, Bo

PY - 2005/6/9

Y1 - 2005/6/9

N2 - We consider a social optimization model of pricing scheme in single-minded auctions, in cases where Walrasian equilibrium does not exist. We are interested in the maximization of the ratio, R, of happy bidders over all agents, in a feasible allocation-pricing scheme. We show NP-hardness of the optimization problem, establish lower and upper bounds of R, as well as develop greedy algorithms to approximate the optimal value of R.

AB - We consider a social optimization model of pricing scheme in single-minded auctions, in cases where Walrasian equilibrium does not exist. We are interested in the maximization of the ratio, R, of happy bidders over all agents, in a feasible allocation-pricing scheme. We show NP-hardness of the optimization problem, establish lower and upper bounds of R, as well as develop greedy algorithms to approximate the optimal value of R.

KW - Combinatorial auction

KW - Walrasian equilibrium

UR - https://www.scopus.com/pages/publications/18444412581

U2 - 10.1016/j.tcs.2005.03.008

DO - 10.1016/j.tcs.2005.03.008

M3 - 文章

AN - SCOPUS:18444412581

SN - 0304-3975

VL - 337

SP - 390

EP - 398

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-3

ER -

Approximation of Walrasian equilibrium in single-minded auctions

摘要

访问文件

其它文件与链接

指纹

引用此