Abstract

An important topic in algorithmic game theory is the study of the performance of systems operated by decentralized, self-interested agents, in comparison with systems under centralized control.  One such system modeling queueing systems was proposed by Gaitonde and Tardos (EC 20, 21), who studied the stability of the system when there is a centralized authority, when queues use no regret strategies, and when queues strategize ``patiently'', respectively.  Unlike games studied in the classical Price of Anarchy literature, in these queueing systems the strategy and outcome of one round impact the utility of future rounds.

In this talk, we generalize Gaitonde and Tardos's model from complete bipartite graphs to general bipartite graphs and DAGs.  In general bipartite graphs, we obtain performance analysis comparable to that by Gaitonde and Tardos, although ours reveals a connection to the dual constraints in the centralized stability conditions, and suggest that stability conditions in incomplete bipartite graphs are generally easier to satisfy.  For DAGs, we show that a straightforward generalization of the utility function considered by Gaitonde and Tardos may lead to infinite gaps between centralized and decentralized systems when the queues use no regret strategies.  We provide both a novel utility for queues and a service priority rule, which we show restore the stability conditions when queues use no regret strategies.  Lastly, for incomplete bipartite graphs, we obtain stability conditions when queues strategize patiently, giving a bound slightly worse than that of Gaitonde and Tarods [EC21] for complete bipartite graphs.

Time

2022-05-31  13:30 - 14:30   

Speaker

Qun Hu,  ITCS@SUFE

Room

Tencent meeting ID: 861-8393-9675; PW: 123456