Recent zbMATH articles in MSC 91B32 https://zbmath.org/atom/cc/91B32 2022-09-13T20:28:31.338867Z Werkzeug The power of one secret agent https://zbmath.org/1491.91043 2022-09-13T20:28:31.338867Z "Tamir, Tami" https://zbmath.org/authors/?q=ai:tamir.tami Summary: I am a job. In job-scheduling applications, my friends and I are assigned to machines that can process us. In the last decade, thanks to our strong employee committee, and the rise of algorithmic game theory, we are getting more and more freedom regarding our assignment. Each of us acts to minimize his own cost, rather than to optimize a global objective. My goal is different. I am a secret agent operated by the system. I do my best to lead my fellow jobs to an outcome with a high social cost. My naive friends keep doing the best they can, each of them performs his best-response move whenever he gets the opportunity to do so. Luckily, I am a charismatic guy. I can determine the order according to which the naive jobs perform their best-response moves. In this paper, I analyze my power, formalized as the price of a traitor (PoT), in cost-sharing scheduling games -- in which we need to cover the cost of the machines that process us. Starting from an initial Nash equilibrium (NE) profile, I join the instance and hurt its stability. A sequence of best-response moves is performed until I vanish, leaving the naive jobs in a new NE. For an initial NE assignment, $$S_0$$, the PoT measures the ratio between the social cost of a worst NE I can lead the jobs to, starting from $$S_0$$, and the social cost of $$S_0$$. The PoT of a game is the maximal such ratio among all game instances and initial NE assignments. My analysis distinguishes between instances with unit- and arbitrary-cost machines, and instances with unit- and arbitrary-length jobs. I give exact bounds on the PoT for each setting, in general and in symmetric games. While it turns out that in most settings my power is really impressive, my task is computationally hard (and also hard to approximate). For the entire collection see [Zbl 1390.68022]. A muffin-theorem generator https://zbmath.org/1491.91082 2022-09-13T20:28:31.338867Z "Cui, Guangqi" https://zbmath.org/authors/?q=ai:cui.guangqi "Dickerson, John" https://zbmath.org/authors/?q=ai:dickerson.john-r|dickerson.john-p "Durvasula, Naveen" https://zbmath.org/authors/?q=ai:durvasula.naveen "Gasarch, William" https://zbmath.org/authors/?q=ai:gasarch.william-i "Metz, Erik" https://zbmath.org/authors/?q=ai:metz.erik "Prinz, Jacob" https://zbmath.org/authors/?q=ai:prinz.jacob "Raman, Naveen" https://zbmath.org/authors/?q=ai:raman.naveen "Smolyak, Daniel" https://zbmath.org/authors/?q=ai:smolyak.daniel "Yoo, Sung Hyun" https://zbmath.org/authors/?q=ai:yoo.sung-hyun Summary: Consider the following FUN problem. Given $$m,s$$ you want to divide $$m$$ muffins among $$s$$ students so that everyone gets $$\frac{m}{s}$$ muffins; however, you want to maximize the minimum piece so that nobody gets crumbs. Let $$f(m,s)$$ be the size of the smallest piece in an optimal procedure. We study the case where $$\lceil\frac{2m}{s}\rceil=3$$ because (1) many of our hardest open problems were of this form until we found this method, (2) we have used the technique to generate muffin-theorems, and (3) we conjecture this can be used to solve the general case. We give (1) an algorithm to find an upper bound for $$f(m,s)$$ when $$\lceil\frac{2m}{s}\rceil=3$$ (and some ways to speed up that algorithm if certain conjectures are true), (2) an algorithm that uses the information from (1) to try to find a lower bound on $$f(m,s)$$ (a procedure) which matches the upper bound, (3) an algorithm that uses the information from (1) to generate muffin-theorems, and (4) an algorithm that we think works well in practice to find $$f(m,s)$$ for any $$m,s$$. For the entire collection see [Zbl 1390.68022]. Optimal energy consuming planning for a home-based microgrid with mobility constraint of electric vehicles and tractors https://zbmath.org/1491.91083 2022-09-13T20:28:31.338867Z "Inuzuka, Shota" https://zbmath.org/authors/?q=ai:inuzuka.shota "Shen, Tielong" https://zbmath.org/authors/?q=ai:shen.tielong (no abstract) Support optimal scheduling with weighted random forest for operation resources https://zbmath.org/1491.91084 2022-09-13T20:28:31.338867Z "Li, Li" https://zbmath.org/authors/?q=ai:li.li.8|li.li.13|li.li|li.li.17|li.li.15|li.li.11|li.li.18|li.li.14|li.li.2|li.li.5|li.li-erran|li.li.4|li.li.1|li.li.12|li.li.9|li.li.16|li.li.7 "Yu, Qingyun" https://zbmath.org/authors/?q=ai:yu.qingyun "Shi, Haoyi" https://zbmath.org/authors/?q=ai:shi.haoyi "Liu, Yuguang" https://zbmath.org/authors/?q=ai:liu.yuguang (no abstract) Utility design for distributed resource allocation. II: Applications to submodular, covering, and supermodular problems https://zbmath.org/1491.91085 2022-09-13T20:28:31.338867Z "Paccagnan, Dario" https://zbmath.org/authors/?q=ai:paccagnan.dario "Marden, Jason R." https://zbmath.org/authors/?q=ai:marden.jason-r Editorial remark: No review copy delivered. For Part I, see [the authors and \textit{R. Chandan}, ibid 65, No. 11, 4616--4631 (2020; Zbl 07320040)].