Qi Qi

Qi Qi

Auto-generated profile, based on publicly available information

Qi Qi

Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China

Research Focus & Metrics

Academic Career Length

21Years (2006-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 December 2012 in Operations Research
Verified
Journal Article
Closed access
XDXiaotie Deng
Xiaotie Deng
QQQi Qi
Qi Qi
ASAmin Saberi
Amin Saberi
We study the problem of finding an envy-free allocation of a cake to d + 1 players using d cuts. Two models are considered, namely, the oracle-function model and the polynomial-time function model. In the oracle-function model, we are interested in the number of times an algorithm has to query the players about their preferences to find an allocation with the envy less than ϵ. We derive a matching lower and upper bound of θ(1/ϵ)d − 1 for players with Lipschitz utilities and any d > 1. In the polynomial-time function model, where the utility functions are given explicitly by polynomial-time algorithms, we show that the envy-free cake-cutting problem has the same complexity as finding a Brouwer's fixed point, or, more formally, it is PPAD-complete. On the flip side, for monotone utility functions, we propose a fully polynomial-time algorithm (FPTAS) to find an approximate envy-free allocation of a cake among three people using two cuts.

24 April 2023 in Transportation Research Part B: Methodological
Verified
Journal Article
Closed access
XDXiaoshu Ding
Xiaoshu Ding
QQQi Qi
Qi Qi
SJSisi Jian
Sisi Jian
HYHai Yang
Hai Yang

16 January 2008 in Information Processing Letters
Verified
Journal Article
Closed access
TBTian-Ming Bu
Tian-Ming Bu
XDXiaotie Deng
Xiaotie Deng
QQQi Qi
Qi Qi

1 August 2023 in Mathematics of Operations Research
Verified
Journal Article
Closed access
YCYukun Cheng
Yukun Cheng
XDXiaotie Deng
Xiaotie Deng
QQQi Qi
Qi Qi
XYXiang Yan
Xiang Yan
We consider a sharing economy over a network in which each vertex agent allocates resources to its neighbors in response to their contributions. General equilibrium theory can be applied here to solve the problem of deciding how to fairly and efficiently allocate resources among agents as resource sharing over the network can be modeled as a pure exchange economy. It is known that proportional sharing dynamics converges to a market equilibrium solution. We are particularly interested in proportional sharing dynamics as a mechanism for network resource sharing. Our focus is on the key issue in internet market design: whether an agent may manipulate its report of its own private information to gain more resources under this mechanism. This work establishes the first mathematical proof that such a practical distributed network resource-sharing protocol is truthful against the manipulative strategies of feasible weight misreporting and edge deletion applied both individually and together. Funding: This work was supported by the National Nature Science Foundation of China [Grants 11871366, 62172012]; Beijing Outstanding Young Scientist Program [Grant BJJWZYJH012019100020098]; the Fundamental Research Funds for the Central Universities; the Research Funds of Renmin University of China [Grant 297522503709]; and the Intelligent Social Governance Platform, Major Innovation & Planning Interdisciplinary Platform for the “Double-First Class” Initiative, Renmin University of China.

3 December 2007
Verified
Book Chapter
Closed access
PDF file
LLLi Liang
Li Liang
QQQi Qi
Qi Qi

13 May 2024
Verified
Conference Paper
Open access
CXChen Xu
Chen Xu
JXJun Xu
Jun Xu
YDYiming Ding
Yiming Ding
XZXiao Zhang
Xiao Zhang
QQQi Qi
Qi Qi
In pursuit of fairness and balanced development, recommender systems (RS) often prioritize group fairness, ensuring that specific groups maintain a minimum level of exposure over a given period. For example, RS platforms aim to ensure adequate exposure for new providers or specific categories of items according to their needs. Modern industry RS usually adopts a two-stage pipeline: stage-1 (retrieval stage) retrieves hundreds of candidates from millions of items distributed across various servers, and stage-2 (ranking stage) focuses on presenting a small-size but accurate selection from items chosen in stage-1. Existing efforts for ensuring amortized group exposures focus on stage-2, however, stage-1 is also critical for the task. Without a high-quality set of candidates, the stage-2 ranker cannot ensure the required exposure of groups. Previous fairness-aware works designed for stage-2 typically require accessing and traversing all items. In stage-1, however, millions of items are distributively stored in servers, making it infeasible to traverse all of them. How to ensure group exposures in the distributed retrieval process is a challenging question. To address this issue, we introduce a model named FairSync, which transforms the problem into a constrained distributed optimization problem. Specifically, FairSync resolves the issue by moving it to the dual space, where a central node aggregates historical fairness data into a vector and distributes it to all servers. To trade off the efficiency and accuracy, the gradient descent technique is used to periodically update the parameter of the dual vector. The experiment results on two public recommender retrieval datasets showcased that FairSync outperformed all the baselines, achieving the desired minimum level of exposures while maintaining a high level of retrieval accuracy.