Search | arXiv e-print repository

<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8"/> <meta name="viewport" content="width=device-width, initial-scale=1"/>  <link rel="apple-touch-icon" sizes="180x180" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/apple-touch-icon.png"> <link rel="icon" type="image/png" sizes="32x32" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon-32x32.png"> <link rel="icon" type="image/png" sizes="16x16" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon-16x16.png"> <link rel="manifest" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/site.webmanifest"> <link rel="mask-icon" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/safari-pinned-tab.svg" color="#b31b1b"> <link rel="shortcut icon" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon.ico"> <meta name="msapplication-TileColor" content="#b31b1b"> <meta name="msapplication-config" content="images/icons/browserconfig.xml"> <meta name="theme-color" content="#b31b1b">  <title>Search | arXiv e-print repository</title> <script defer src="https://static.arxiv.org/static/base/1.0.0a5/fontawesome-free-5.11.2-web/js/all.js"></script> <link rel="stylesheet" href="https://static.arxiv.org/static/base/1.0.0a5/css/arxivstyle.css" /> <script type="text/x-mathjax-config"> MathJax.Hub.Config({ messageStyle: "none", extensions: ["tex2jax.js"], jax: ["input/TeX", "output/HTML-CSS"], tex2jax: { inlineMath: [ ['$','$'], ["\$","\$"] ], displayMath: [ ['$$','$$'], ["\\[","\\]"] ], processEscapes: true, ignoreClass: '.*', processClass: 'mathjax.*' }, TeX: { extensions: ["AMSmath.js", "AMSsymbols.js", "noErrors.js"], noErrors: { inlineDelimiters: ["$","$"], multiLine: false, style: { "font-size": "normal", "border": "" } } }, "HTML-CSS": { availableFonts: ["TeX"] } }); </script> <script src='//static.arxiv.org/MathJax-2.7.3/MathJax.js'></script> <script src="https://static.arxiv.org/static/base/1.0.0a5/js/notification.js"></script> <link rel="stylesheet" href="https://static.arxiv.org/static/search/0.5.6/css/bulma-tooltip.min.css" /> <link rel="stylesheet" href="https://static.arxiv.org/static/search/0.5.6/css/search.css" /> <script src="https://code.jquery.com/jquery-3.2.1.slim.min.js" integrity="sha256-k2WSCIexGzOj3Euiig+TlR8gA0EmPjuc79OEeY5L45g=" crossorigin="anonymous"></script> <script src="https://static.arxiv.org/static/search/0.5.6/js/fieldset.js"></script> <style> radio#cf-customfield_11400 { display: none; } </style> </head> <body> <header><a href="#main-container" class="is-sr-only">Skip to main content</a>  <div class="attribution level is-marginless" role="banner"> <div class="level-left"> <a class="level-item" href="https://cornell.edu/"><img src="https://static.arxiv.org/static/base/1.0.0a5/images/cornell-reduced-white-SMALL.svg" alt="Cornell University" width="200" aria-label="logo" /></a> </div> <div class="level-right is-marginless"><p class="sponsors level-item is-marginless"><span id="support-ack-url">We gratefully acknowledge support from<br /> the Simons Foundation, <a href="https://info.arxiv.org/about/ourmembers.html">member institutions</a>, and all contributors. <a href="https://info.arxiv.org/about/donate.html">Donate</a></span></p></div> </div>  <div class="identity level is-marginless"> <div class="level-left"> <div class="level-item"> <a class="arxiv" href="https://arxiv.org/" aria-label="arxiv-logo"> <img src="https://static.arxiv.org/static/base/1.0.0a5/images/arxiv-logo-one-color-white.svg" aria-label="logo" alt="arxiv logo" width="85" style="width:85px;"/> </a> </div> </div> <div class="search-block level-right"> <form class="level-item mini-search" method="GET" action="https://arxiv.org/search"> <div class="field has-addons"> <div class="control"> <input class="input is-small" type="text" name="query" placeholder="Search..." aria-label="Search term or terms" /> <p class="help"><a href="https://info.arxiv.org/help">Help</a> | <a href="https://arxiv.org/search/advanced">Advanced Search</a></p> </div> <div class="control"> <div class="select is-small"> <select name="searchtype" aria-label="Field to search"> <option value="all" selected="selected">All fields</option> <option value="title">Title</option> <option value="author">Author</option> <option value="abstract">Abstract</option> <option value="comments">Comments</option> <option value="journal_ref">Journal reference</option> <option value="acm_class">ACM classification</option> <option value="msc_class">MSC classification</option> <option value="report_num">Report number</option> <option value="paper_id">arXiv identifier</option> <option value="doi">DOI</option> <option value="orcid">ORCID</option> <option value="author_id">arXiv author ID</option> <option value="help">Help pages</option> <option value="full_text">Full text</option> </select> </div> </div> <input type="hidden" name="source" value="header"> <button class="button is-small is-cul-darker">Search</button> </div> </form> </div> </div>  <div class="container"> <div class="user-tools is-size-7 has-text-right has-text-weight-bold" role="navigation" aria-label="User menu"> <a href="https://arxiv.org/login">Login</a> </div> </div> </header> <main class="container" id="main-container"> <div class="level is-marginless"> <div class="level-left"> <h1 class="title is-clearfix"> Showing 1–27 of 27 results for author: <span class="mathjax">Fiat, A</span> </h1> </div> <div class="level-right is-hidden-mobile">  <span class="help" style="display: inline-block;"><a href="https://github.com/arXiv/arxiv-search/releases">Search v0.5.6 released 2020-02-24</a>  </span> </div> </div> <div class="content"> <form method="GET" action="/search/cs" aria-role="search"> Searching in archive <strong>cs</strong>. <a href="/search/?searchtype=author&query=Fiat%2C+A">Search in all archives.</a> <div class="field has-addons-tablet"> <div class="control is-expanded"> <label for="query" class="hidden-label">Search term or terms</label> <input class="input is-medium" id="query" name="query" placeholder="Search term..." type="text" value="Fiat, A"> </div> <div class="select control is-medium"> <label class="is-hidden" for="searchtype">Field</label> <select class="is-medium" id="searchtype" name="searchtype"><option value="all">All fields</option><option value="title">Title</option><option selected value="author">Author(s)</option><option value="abstract">Abstract</option><option value="comments">Comments</option><option value="journal_ref">Journal reference</option><option value="acm_class">ACM classification</option><option value="msc_class">MSC classification</option><option value="report_num">Report number</option><option value="paper_id">arXiv identifier</option><option value="doi">DOI</option><option value="orcid">ORCID</option><option value="license">License (URI)</option><option value="author_id">arXiv author ID</option><option value="help">Help pages</option><option value="full_text">Full text</option></select> </div> <div class="control"> <button class="button is-link is-medium">Search</button> </div> </div> <div class="field"> <div class="control is-size-7"> <label class="radio"> <input checked id="abstracts-0" name="abstracts" type="radio" value="show"> Show abstracts </label> <label class="radio"> <input id="abstracts-1" name="abstracts" type="radio" value="hide"> Hide abstracts </label> </div> </div> <div class="is-clearfix" style="height: 2.5em"> <div class="is-pulled-right"> <a href="/search/advanced?terms-0-term=Fiat%2C+A&terms-0-field=author&size=50&order=-announced_date_first">Advanced Search</a> </div> </div> <input type="hidden" name="order" value="-announced_date_first"> <input type="hidden" name="size" value="50"> </form> <div class="level breathe-horizontal"> <div class="level-left"> <form method="GET" action="/search/"> <div style="display: none;"> <select id="searchtype" name="searchtype"><option value="all">All fields</option><option value="title">Title</option><option selected value="author">Author(s)</option><option value="abstract">Abstract</option><option value="comments">Comments</option><option value="journal_ref">Journal reference</option><option value="acm_class">ACM classification</option><option value="msc_class">MSC classification</option><option value="report_num">Report number</option><option value="paper_id">arXiv identifier</option><option value="doi">DOI</option><option value="orcid">ORCID</option><option value="license">License (URI)</option><option value="author_id">arXiv author ID</option><option value="help">Help pages</option><option value="full_text">Full text</option></select> <input id="query" name="query" type="text" value="Fiat, A"> <ul id="abstracts"><li><input checked id="abstracts-0" name="abstracts" type="radio" value="show"> <label for="abstracts-0">Show abstracts</label></li><li><input id="abstracts-1" name="abstracts" type="radio" value="hide"> <label for="abstracts-1">Hide abstracts</label></li></ul> </div> <div class="box field is-grouped is-grouped-multiline level-item"> <div class="control"> <span class="select is-small"> <select id="size" name="size"><option value="25">25</option><option selected value="50">50</option><option value="100">100</option><option value="200">200</option></select> </span> <label for="size">results per page</label>. </div> <div class="control"> <label for="order">Sort results by</label> <span class="select is-small"> <select id="order" name="order"><option selected value="-announced_date_first">Announcement date (newest first)</option><option value="announced_date_first">Announcement date (oldest first)</option><option value="-submitted_date">Submission date (newest first)</option><option value="submitted_date">Submission date (oldest first)</option><option value="">Relevance</option></select> </span> </div> <div class="control"> <button class="button is-small is-link">Go</button> </div> </div> </form> </div> </div> <ol class="breathe-horizontal" start="1"> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2502.09377">arXiv:2502.09377</a> <span> [<a href="https://arxiv.org/pdf/2502.09377">pdf</a>, <a href="https://arxiv.org/ps/2502.09377">ps</a>, <a href="https://arxiv.org/format/2502.09377">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> </div> </div> <p class="title is-5 mathjax"> Fair Division via Resource Augmentation </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Akrami%2C+H">Hannaneh Akrami</a>, <a href="/search/cs?searchtype=author&query=Eden%2C+A">Alon Eden</a>, <a href="/search/cs?searchtype=author&query=Feldman%2C+M">Michal Feldman</a>, <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Gal-Tzur%2C+Y">Yoav Gal-Tzur</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2502.09377v1-abstract-short" style="display: inline;"> We introduce and formalize the notion of resource augmentation for maximin share allocations -- an idea that can be traced back to the seminal work of Budish [JPE 2011]. Specifically, given a fair division instance with $m$ goods and $n$ agents, we ask how many copies of the goods should be added in order to guarantee that each agent receives at least their original maximin share, or an approx… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2502.09377v1-abstract-full').style.display = 'inline'; document.getElementById('2502.09377v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2502.09377v1-abstract-full" style="display: none;"> We introduce and formalize the notion of resource augmentation for maximin share allocations -- an idea that can be traced back to the seminal work of Budish [JPE 2011]. Specifically, given a fair division instance with $m$ goods and $n$ agents, we ask how many copies of the goods should be added in order to guarantee that each agent receives at least their original maximin share, or an approximation thereof. We establish a tight bound of $m/e$ copies for arbitrary monotone valuations. For additive valuations, we show that at most $\min\{n-2,\lfloor \frac{m}{3}\rfloor (1+o(1))\}$ copies suffice. For approximate-MMS in ordered instances, we give a tradeoff between the number of copies needed and the approximation guarantee. In particular, we prove that $\lfloor n/2 \rfloor$ copies suffice to guarantee a $6/7$-approximation to the original MMS, and $\lfloor n/3 \rfloor$ copies suffice for a $4/5$-approximation. Both results improve upon the best known approximation guarantees for additive valuations in the absence of copies. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2502.09377v1-abstract-full').style.display = 'none'; document.getElementById('2502.09377v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 13 February, 2025; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2025. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2302.05590">arXiv:2302.05590</a> <span> [<a href="https://arxiv.org/pdf/2302.05590">pdf</a>, <a href="https://arxiv.org/format/2302.05590">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Theoretical Economics">econ.TH</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Cryptography and Security">cs.CR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> </div> </div> <p class="title is-5 mathjax"> Zero-Knowledge Mechanisms </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Canetti%2C+R">Ran Canetti</a>, <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Gonczarowski%2C+Y+A">Yannai A. Gonczarowski</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2302.05590v1-abstract-short" style="display: inline;"> A powerful feature in mechanism design is the ability to irrevocably commit to the rules of a mechanism. Commitment is achieved by public declaration, which enables players to verify incentive properties in advance and the outcome in retrospect. However, public declaration can reveal superfluous information that the mechanism designer might prefer not to disclose, such as her target function or pr… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.05590v1-abstract-full').style.display = 'inline'; document.getElementById('2302.05590v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2302.05590v1-abstract-full" style="display: none;"> A powerful feature in mechanism design is the ability to irrevocably commit to the rules of a mechanism. Commitment is achieved by public declaration, which enables players to verify incentive properties in advance and the outcome in retrospect. However, public declaration can reveal superfluous information that the mechanism designer might prefer not to disclose, such as her target function or private costs. Avoiding this may be possible via a trusted mediator; however, the availability of a trusted mediator, especially if mechanism secrecy must be maintained for years, might be unrealistic. We propose a new approach to commitment, and show how to commit to, and run, any given mechanism without disclosing it, while enabling the verification of incentive properties and the outcome -- all without the need for any mediators. Our framework is based on zero-knowledge proofs -- a cornerstone of modern cryptographic theory. Applications include non-mediated bargaining with hidden yet binding offers. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2302.05590v1-abstract-full').style.display = 'none'; document.getElementById('2302.05590v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 10 February, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2210.06846">arXiv:2210.06846</a> <span> [<a href="https://arxiv.org/pdf/2210.06846">pdf</a>, <a href="https://arxiv.org/format/2210.06846">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1016/j.artint.2024.104231">10.1016/j.artint.2024.104231 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> An $伪$-regret analysis of Adversarial Bilateral Trade </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Azar%2C+Y">Yossi Azar</a>, <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Fusco%2C+F">Federico Fusco</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2210.06846v2-abstract-short" style="display: inline;"> We study sequential bilateral trade where sellers and buyers valuations are completely arbitrary (i.e., determined by an adversary). Sellers and buyers are strategic agents with private valuations for the good and the goal is to design a mechanism that maximizes efficiency (or gain from trade) while being incentive compatible, individually rational and budget balanced. In this paper we consider ga… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2210.06846v2-abstract-full').style.display = 'inline'; document.getElementById('2210.06846v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2210.06846v2-abstract-full" style="display: none;"> We study sequential bilateral trade where sellers and buyers valuations are completely arbitrary (i.e., determined by an adversary). Sellers and buyers are strategic agents with private valuations for the good and the goal is to design a mechanism that maximizes efficiency (or gain from trade) while being incentive compatible, individually rational and budget balanced. In this paper we consider gain from trade which is harder to approximate than social welfare. We consider a variety of feedback scenarios and distinguish the cases where the mechanism posts one price and when it can post different prices for buyer and seller. We show several surprising results about the separation between the different scenarios. In particular we show that (a) it is impossible to achieve sublinear $伪$-regret for any $伪<2$, (b) but with full feedback sublinear $2$-regret is achievable (c) with a single price and partial feedback one cannot get sublinear $伪$ regret for any constant $伪$ (d) nevertheless, posting two prices even with one-bit feedback achieves sublinear $2$-regret, and (e) there is a provable separation in the $2$-regret bounds between full and partial feedback. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2210.06846v2-abstract-full').style.display = 'none'; document.getElementById('2210.06846v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 10 October, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 13 October, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2022. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">The conference version of this paper appeared in NeurIPS 22, while a journal version was published in the Artificial Intelligence Journal. With respect to the previous arXiv version, the current one contains a revised proof of Theorem 6</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Artificial Intelligence, Volume 337, December 2024, 104231 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2103.08634">arXiv:2103.08634</a> <span> [<a href="https://arxiv.org/pdf/2103.08634">pdf</a>, <a href="https://arxiv.org/ps/2103.08634">ps</a>, <a href="https://arxiv.org/format/2103.08634">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> </div> </div> <p class="title is-5 mathjax"> Competitive Equilibria with Unequal Budgets: Supporting Arbitrary Pareto Optimal Allocations </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Andelman%2C+N">Nir Andelman</a>, <a href="/search/cs?searchtype=author&query=Feldman%2C+M">Michal Feldman</a>, <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Mansour%2C+Y">Yishay Mansour</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2103.08634v1-abstract-short" style="display: inline;"> We consider a market setting of agents with additive valuations over heterogeneous divisible resources. Agents are assigned a budget of tokens (possibly unequal budgets) they can use to obtain resources; leftover tokens are worthless. We show how to support any Pareto efficient allocation in equilibrium, using anonymous resource prices and agent specific budgets. We also give computationally effic… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2103.08634v1-abstract-full').style.display = 'inline'; document.getElementById('2103.08634v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2103.08634v1-abstract-full" style="display: none;"> We consider a market setting of agents with additive valuations over heterogeneous divisible resources. Agents are assigned a budget of tokens (possibly unequal budgets) they can use to obtain resources; leftover tokens are worthless. We show how to support any Pareto efficient allocation in equilibrium, using anonymous resource prices and agent specific budgets. We also give computationally efficient algorithms for those tasks. In particular, this allows us to support the Rawlsian max-min allocation. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2103.08634v1-abstract-full').style.display = 'none'; document.getElementById('2103.08634v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 15 March, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 2021. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2102.10654">arXiv:2102.10654</a> <span> [<a href="https://arxiv.org/pdf/2102.10654">pdf</a>, <a href="https://arxiv.org/format/2102.10654">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> </div> </div> <p class="title is-5 mathjax"> (Almost Full) EFX Exists for Four Agents (and Beyond) </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Berger%2C+B">Ben Berger</a>, <a href="/search/cs?searchtype=author&query=Cohen%2C+A">Avi Cohen</a>, <a href="/search/cs?searchtype=author&query=Feldman%2C+M">Michal Feldman</a>, <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2102.10654v2-abstract-short" style="display: inline;"> The existence of EFX allocations is a major open problem in fair division, even for additive valuations. The current state of the art is that no setting where EFX allocations are impossible is known, and EFX is known to exist for ($i$) agents with identical valuations, ($ii$) 2 agents, ($iii$) 3 agents with additive valuations, ($iv$) agents with one of two additive valuations and ($v$) agents wit… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2102.10654v2-abstract-full').style.display = 'inline'; document.getElementById('2102.10654v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2102.10654v2-abstract-full" style="display: none;"> The existence of EFX allocations is a major open problem in fair division, even for additive valuations. The current state of the art is that no setting where EFX allocations are impossible is known, and EFX is known to exist for ($i$) agents with identical valuations, ($ii$) 2 agents, ($iii$) 3 agents with additive valuations, ($iv$) agents with one of two additive valuations and ($v$) agents with two-valued instances. It is also known that EFX exists if one can leave $n-1$ items unallocated, where $n$ is the number of agents. We develop new techniques that allow us to push the boundaries of the enigmatic EFX problem beyond these known results, and, arguably, to simplify proofs of earlier results. Our main results are ($i$) every setting with 4 additive agents admits an EFX allocation that leaves at most a single item unallocated, ($ii$) every setting with $n$ additive valuations has an EFX allocation with at most $n-2$ unallocated items. Moreover, all of our results extend beyond additive valuations to all nice cancelable valuations (a new class, including additive, unit-demand, budget-additive and multiplicative valuations, among others). Furthermore, using our new techniques, we show that previous results for additive valuations extend to nice cancelable valuations. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2102.10654v2-abstract-full').style.display = 'none'; document.getElementById('2102.10654v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 28 February, 2021; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 21 February, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2021. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1903.08384">arXiv:1903.08384</a> <span> [<a href="https://arxiv.org/pdf/1903.08384">pdf</a>, <a href="https://arxiv.org/format/1903.08384">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> </div> </div> <p class="title is-5 mathjax"> Combinatorial Auctions with Interdependent Valuations: SOS to the Rescue </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Eden%2C+A">Alon Eden</a>, <a href="/search/cs?searchtype=author&query=Feldman%2C+M">Michal Feldman</a>, <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Goldner%2C+K">Kira Goldner</a>, <a href="/search/cs?searchtype=author&query=Karlin%2C+A+R">Anna R. Karlin</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1903.08384v2-abstract-short" style="display: inline;"> We study combinatorial auctions with interdependent valuations. In such settings, each agent $i$ has a private signal $s_i$ that captures her private information, and the valuation function of every agent depends on the entire signal profile, ${\bf s}=(s_1,\ldots,s_n)$. The literature in economics shows that the interdependent model gives rise to strong impossibility results, and identifies assump… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1903.08384v2-abstract-full').style.display = 'inline'; document.getElementById('1903.08384v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1903.08384v2-abstract-full" style="display: none;"> We study combinatorial auctions with interdependent valuations. In such settings, each agent $i$ has a private signal $s_i$ that captures her private information, and the valuation function of every agent depends on the entire signal profile, ${\bf s}=(s_1,\ldots,s_n)$. The literature in economics shows that the interdependent model gives rise to strong impossibility results, and identifies assumptions under which optimal solutions can be attained. The computer science literature provides approximation results for simple single-parameter settings (mostly single item auctions, or matroid feasibility constraints). Both bodies of literature focus largely on valuations satisfying a technical condition termed {\em single crossing} (or variants thereof). We consider the class of {\em submodular over signals} (SOS) valuations (without imposing any single-crossing type assumption), and provide the first welfare approximation guarantees for multi-dimensional combinatorial auctions, achieved by universally ex-post IC-IR mechanisms. Our main results are: $(i)$ 4-approximation for any single-parameter downward-closed setting with single-dimensional signals and SOS valuations; $(ii)$ 4-approximation for any combinatorial auction with multi-dimensional signals and {\em separable}-SOS valuations; and $(iii)$ $(k+3)$- and $(2\log(k)+4)$-approximation for any combinatorial auction with single-dimensional signals, with $k$-sized signal space, for SOS and strong-SOS valuations, respectively. All of our results extend to a parameterized version of SOS, $d$-SOS, while losing a factor that depends on $d$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1903.08384v2-abstract-full').style.display = 'none'; document.getElementById('1903.08384v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 2 June, 2019; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 20 March, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 2019. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">To appear in the 20th ACM conference on Economics and Computation (ACM EC '19)</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1806.03865">arXiv:1806.03865</a> <span> [<a href="https://arxiv.org/pdf/1806.03865">pdf</a>, <a href="https://arxiv.org/format/1806.03865">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> </div> </div> <p class="title is-5 mathjax"> Interdependent Values without Single-Crossing </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Eden%2C+A">Alon Eden</a>, <a href="/search/cs?searchtype=author&query=Feldman%2C+M">Michal Feldman</a>, <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Goldner%2C+K">Kira Goldner</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1806.03865v1-abstract-short" style="display: inline;"> We consider a setting where an auctioneer sells a single item to $n$ potential agents with {\em interdependent values}. That is, each agent has her own private signal, and the valuation of each agent is a known function of all $n$ private signals. This captures settings such as valuations for artwork, oil drilling rights, broadcast rights, and many more. In the interdependent value setting, all… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1806.03865v1-abstract-full').style.display = 'inline'; document.getElementById('1806.03865v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1806.03865v1-abstract-full" style="display: none;"> We consider a setting where an auctioneer sells a single item to $n$ potential agents with {\em interdependent values}. That is, each agent has her own private signal, and the valuation of each agent is a known function of all $n$ private signals. This captures settings such as valuations for artwork, oil drilling rights, broadcast rights, and many more. In the interdependent value setting, all previous work has assumed a so-called {\sl single-crossing condition}. Single-crossing means that the impact of agent $i$'s private signal, $s_i$, on her own valuation is greater than the impact of $s_i$ on the valuation of any other agent. It is known that without the single-crossing condition an efficient outcome cannot be obtained. We study welfare maximization for interdependent valuations through the lens of approximation. We show that, in general, without the single-crossing condition, one cannot hope to approximate the optimal social welfare any better than the approximation given by assigning the item to a random bidder. Consequently, we introduce a relaxed version of single-crossing, {\sl $c$-single-crossing}, parameterized by $c\geq 1$, which means that the impact of $s_i$ on the valuation of agent $i$ is at least $1/c$ times the impact of $s_i$ on the valuation of any other agent ($c=1$ is single-crossing). Using this parameterized notion, we obtain a host of positive results. We propose a prior-free deterministic mechanism that gives an $(n-1)c$-approximation guarantee to welfare. We then show that a random version of the proposed mechanism gives a prior-free universally truthful $2c$-approximation to the optimal welfare for any concave $c$-single crossing setting (and a $2\sqrt{n}c^{3/2}$-approximation in the absence of concavity). We extend this mechanism to a universally truthful mechanism that gives $O(c^2)$-approximation to the optimal revenue. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1806.03865v1-abstract-full').style.display = 'none'; document.getElementById('1806.03865v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 11 June, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2018. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1804.09672">arXiv:1804.09672</a> <span> [<a href="https://arxiv.org/pdf/1804.09672">pdf</a>, <a href="https://arxiv.org/ps/1804.09672">ps</a>, <a href="https://arxiv.org/format/1804.09672">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> </div> </div> <p class="title is-5 mathjax"> Flow Equilibria via Online Surge Pricing </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Mansour%2C+Y">Yishay Mansour</a>, <a href="/search/cs?searchtype=author&query=Shultz%2C+L">Lior Shultz</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1804.09672v2-abstract-short" style="display: inline;"> We explore issues of dynamic supply and demand in ride sharing services such as Lyft and Uber, where demand fluctuates over time and geographic location. We seek to maximize social welfare which depends on taxicab and passenger locations, passenger valuations for service, and the distances between taxicabs and passengers. Our only means of control is to set surge prices, then taxicabs and passenge… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1804.09672v2-abstract-full').style.display = 'inline'; document.getElementById('1804.09672v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1804.09672v2-abstract-full" style="display: none;"> We explore issues of dynamic supply and demand in ride sharing services such as Lyft and Uber, where demand fluctuates over time and geographic location. We seek to maximize social welfare which depends on taxicab and passenger locations, passenger valuations for service, and the distances between taxicabs and passengers. Our only means of control is to set surge prices, then taxicabs and passengers maximize their utilities subject to these prices. We study two related models: a continuous passenger-taxicab setting, similar to the Wardrop model, and a discrete passenger-taxicab setting. In the continuous setting, every location is occupied by a set of infinitesimal strategic taxicabs and a set of infinitesimal non-strategic passengers. In the discrete setting every location is occupied by a set of strategic agents, taxicabs and passengers, passengers have differing values for service. We expand the continuous model to a time-dependent setting and study the corresponding online environment. Surge prices are in passenger-taxicab equilibrium if there exists a min cost flow that moves taxicabs about such that (a) every taxicab follows a best response, (b) all strategic passengers at $v$ with value above the surge price $r_v$ for $v$, are served and (c) no strategic passengers with value below $r_v$ are served (non-strategic infinitesimal passengers are always served). This paper computes surge prices such that resulting passenger-taxicab equilibrium maximizes social welfare, and the computation of such surge prices is in poly time. Moreover, it is a dominant strategy for passengers to reveal their true values. We seek to maximize social welfare in the online environment, and derive tight competitive ratio bounds to this end. Our online algorithms make use of the surge prices computed over time and geographic location, inducing successive passenger-taxicab equilibria. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1804.09672v2-abstract-full').style.display = 'none'; document.getElementById('1804.09672v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 12 July, 2018; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 25 April, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2018. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1804.06637">arXiv:1804.06637</a> <span> [<a href="https://arxiv.org/pdf/1804.06637">pdf</a>, <a href="https://arxiv.org/ps/1804.06637">ps</a>, <a href="https://arxiv.org/format/1804.06637">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> </div> </div> <p class="title is-5 mathjax"> An Economic-Based Analysis of RANKING for Online Bipartite Matching </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Eden%2C+A">Alon Eden</a>, <a href="/search/cs?searchtype=author&query=Feldman%2C+M">Michal Feldman</a>, <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Segal%2C+K">Kineret Segal</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1804.06637v2-abstract-short" style="display: inline;"> In their seminal paper, Karp, Vazirani and Vazirani (STOC'90) introduce the online bipartite matching problem, and the RANKING algorithm, which admits a tight $1-\frac{1}{e}$ competitive ratio. Since its publication, the problem has received considerable attention, including a sequence of simplified proofs. In this paper we present a new proof that gives an economic interpretation of the RANKING a… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1804.06637v2-abstract-full').style.display = 'inline'; document.getElementById('1804.06637v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1804.06637v2-abstract-full" style="display: none;"> In their seminal paper, Karp, Vazirani and Vazirani (STOC'90) introduce the online bipartite matching problem, and the RANKING algorithm, which admits a tight $1-\frac{1}{e}$ competitive ratio. Since its publication, the problem has received considerable attention, including a sequence of simplified proofs. In this paper we present a new proof that gives an economic interpretation of the RANKING algorithm -- further simplifying the proof and avoiding arguments such as duality. The new proof gives a new perspective on previous proofs. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1804.06637v2-abstract-full').style.display = 'none'; document.getElementById('1804.06637v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 10 October, 2020; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 18 April, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2018. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1804.03244">arXiv:1804.03244</a> <span> [<a href="https://arxiv.org/pdf/1804.03244">pdf</a>, <a href="https://arxiv.org/format/1804.03244">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> </div> </div> <p class="title is-5 mathjax"> Prompt Scheduling for Selfish Agents </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Eden%2C+A">Alon Eden</a>, <a href="/search/cs?searchtype=author&query=Feldman%2C+M">Michal Feldman</a>, <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Taub%2C+T">Tzahi Taub</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1804.03244v1-abstract-short" style="display: inline;"> We give a prompt online mechanism for minimizing the sum of [weighted] completion times. This is the first prompt online algorithm for the problem. When such jobs are strategic agents, delaying scheduling decisions makes little sense. Moreover, the mechanism has a particularly simple form of an anonymous menu of options. </span> <span class="abstract-full has-text-grey-dark mathjax" id="1804.03244v1-abstract-full" style="display: none;"> We give a prompt online mechanism for minimizing the sum of [weighted] completion times. This is the first prompt online algorithm for the problem. When such jobs are strategic agents, delaying scheduling decisions makes little sense. Moreover, the mechanism has a particularly simple form of an anonymous menu of options. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1804.03244v1-abstract-full').style.display = 'none'; document.getElementById('1804.03244v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 9 April, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2018. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1705.01965">arXiv:1705.01965</a> <span> [<a href="https://arxiv.org/pdf/1705.01965">pdf</a>, <a href="https://arxiv.org/format/1705.01965">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> </div> </div> <p class="title is-5 mathjax"> Makespan Minimization via Posted Prices </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Feldman%2C+M">Michal Feldman</a>, <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Roytman%2C+A">Alan Roytman</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1705.01965v1-abstract-short" style="display: inline;"> We consider job scheduling settings, with multiple machines, where jobs arrive online and choose a machine selfishly so as to minimize their cost. Our objective is the classic makespan minimization objective, which corresponds to the completion time of the last job to complete. The incentives of the selfish jobs may lead to poor performance. To reconcile the differing objectives, we introduce post… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1705.01965v1-abstract-full').style.display = 'inline'; document.getElementById('1705.01965v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1705.01965v1-abstract-full" style="display: none;"> We consider job scheduling settings, with multiple machines, where jobs arrive online and choose a machine selfishly so as to minimize their cost. Our objective is the classic makespan minimization objective, which corresponds to the completion time of the last job to complete. The incentives of the selfish jobs may lead to poor performance. To reconcile the differing objectives, we introduce posted machine prices. The selfish job seeks to minimize the sum of its completion time on the machine and the posted price for the machine. Prices may be static (i.e., set once and for all before any arrival) or dynamic (i.e., change over time), but they are determined only by the past, assuming nothing about upcoming events. Obviously, such schemes are inherently truthful. We consider the competitive ratio: the ratio between the makespan achievable by the pricing scheme and that of the optimal algorithm. We give tight bounds on the competitive ratio for both dynamic and static pricing schemes for identical, restricted, related, and unrelated machine settings. Our main result is a dynamic pricing scheme for related machines that gives a constant competitive ratio, essentially matching the competitive ratio of online algorithms for this setting. In contrast, dynamic pricing gives poor performance for unrelated machines. This lower bound also exhibits a gap between what can be achieved by pricing versus what can be achieved by online algorithms. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1705.01965v1-abstract-full').style.display = 'none'; document.getElementById('1705.01965v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 4 May, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2017. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1512.05868">arXiv:1512.05868</a> <span> [<a href="https://arxiv.org/pdf/1512.05868">pdf</a>, <a href="https://arxiv.org/format/1512.05868">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Artificial Intelligence">cs.AI</span> </div> </div> <p class="title is-5 mathjax"> On Voting and Facility Location </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Feldman%2C+M">Michal Feldman</a>, <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Golomb%2C+I">Iddan Golomb</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1512.05868v1-abstract-short" style="display: inline;"> We study mechanisms for candidate selection that seek to minimize the social cost, where voters and candidates are associated with points in some underlying metric space. The social cost of a candidate is the sum of its distances to each voter. Some of our work assumes that these points can be modeled on a real line, but other results of ours are more general. A question closely related to candi… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1512.05868v1-abstract-full').style.display = 'inline'; document.getElementById('1512.05868v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1512.05868v1-abstract-full" style="display: none;"> We study mechanisms for candidate selection that seek to minimize the social cost, where voters and candidates are associated with points in some underlying metric space. The social cost of a candidate is the sum of its distances to each voter. Some of our work assumes that these points can be modeled on a real line, but other results of ours are more general. A question closely related to candidate selection is that of minimizing the sum of distances for facility location. The difference is that in our setting there is a fixed set of candidates, whereas the large body of work on facility location seems to consider every point in the metric space to be a possible candidate. This gives rise to three types of mechanisms which differ in the granularity of their input space (voting, ranking and location mechanisms). We study the relationships between these three classes of mechanisms. While it may seem that Black's 1948 median algorithm is optimal for candidate selection on the line, this is not the case. We give matching upper and lower bounds for a variety of settings. In particular, when candidates and voters are on the line, our universally truthful spike mechanism gives a [tight] approximation of two. When assessing candidate selection mechanisms, we seek several desirable properties: (a) efficiency (minimizing the social cost) (b) truthfulness (dominant strategy incentive compatibility) and (c) simplicity (a smaller input space). We quantify the effect that truthfulness and simplicity impose on the efficiency. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1512.05868v1-abstract-full').style.display = 'none'; document.getElementById('1512.05868v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 18 December, 2015; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2015. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1511.05646">arXiv:1511.05646</a> <span> [<a href="https://arxiv.org/pdf/1511.05646">pdf</a>, <a href="https://arxiv.org/format/1511.05646">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> The Invisible Hand of Dynamic Market Pricing </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Cohen-Addad%2C+V">Vincent Cohen-Addad</a>, <a href="/search/cs?searchtype=author&query=Eden%2C+A">Alon Eden</a>, <a href="/search/cs?searchtype=author&query=Feldman%2C+M">Michal Feldman</a>, <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1511.05646v2-abstract-short" style="display: inline;"> Walrasian prices, if they exist, have the property that one can assign every buyer some bundle in her demand set, such that the resulting assignment will maximize social welfare. Unfortunately, this assumes carefully breaking ties amongst different bundles in the buyer demand set. Presumably, the shopkeeper cleverly convinces the buyer to break ties in a manner consistent with maximizing social we… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1511.05646v2-abstract-full').style.display = 'inline'; document.getElementById('1511.05646v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1511.05646v2-abstract-full" style="display: none;"> Walrasian prices, if they exist, have the property that one can assign every buyer some bundle in her demand set, such that the resulting assignment will maximize social welfare. Unfortunately, this assumes carefully breaking ties amongst different bundles in the buyer demand set. Presumably, the shopkeeper cleverly convinces the buyer to break ties in a manner consistent with maximizing social welfare. Lacking such a shopkeeper, if buyers arrive sequentially and simply choose some arbitrary bundle in their demand set, the social welfare may be arbitrarily bad. In the context of matching markets, we show how to compute dynamic prices, based upon the current inventory, that guarantee that social welfare is maximized. Such prices are set without knowing the identity of the next buyer to arrive. We also show that this is impossible in general (e.g., for coverage valuations), but consider other scenarios where this can be done. We further extend our results to Bayesian and bounded rationality models. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1511.05646v2-abstract-full').style.display = 'none'; document.getElementById('1511.05646v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 5 June, 2018; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 17 November, 2015; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2015. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1507.01732">arXiv:1507.01732</a> <span> [<a href="https://arxiv.org/pdf/1507.01732">pdf</a>, <a href="https://arxiv.org/ps/1507.01732">ps</a>, <a href="https://arxiv.org/format/1507.01732">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> The Temp Secretary Problem </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Gorelik%2C+I">Ilia Gorelik</a>, <a href="/search/cs?searchtype=author&query=Kaplan%2C+H">Haim Kaplan</a>, <a href="/search/cs?searchtype=author&query=Novgorodov%2C+S">Slava Novgorodov</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1507.01732v2-abstract-short" style="display: inline;"> We consider a generalization of the secretary problem where contracts are temporary, and for a fixed duration. This models online hiring of temporary employees, or online auctions for re-usable resources. The problem is related to the question of Finding a large independent set in a random unit interval graph. </span> <span class="abstract-full has-text-grey-dark mathjax" id="1507.01732v2-abstract-full" style="display: none;"> We consider a generalization of the secretary problem where contracts are temporary, and for a fixed duration. This models online hiring of temporary employees, or online auctions for re-usable resources. The problem is related to the question of Finding a large independent set in a random unit interval graph. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1507.01732v2-abstract-full').style.display = 'none'; document.getElementById('1507.01732v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 8 July, 2015; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 7 July, 2015; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2015. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">MSC Class:</span> 68Q25 <span class="has-text-black-bis has-text-weight-semibold">ACM Class:</span> F.2.2 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1504.01093">arXiv:1504.01093</a> <span> [<a href="https://arxiv.org/pdf/1504.01093">pdf</a>, <a href="https://arxiv.org/format/1504.01093">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Pricing Online Decisions: Beyond Auctions </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Cohen%2C+I+R">Ilan Reuven Cohen</a>, <a href="/search/cs?searchtype=author&query=Eden%2C+A">Alon Eden</a>, <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Je%C5%BC%2C+%C5%81">艁ukasz Je偶</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1504.01093v1-abstract-short" style="display: inline;"> We consider dynamic pricing schemes in online settings where selfish agents generate online events. Previous work on online mechanisms has dealt almost entirely with the goal of maximizing social welfare or revenue in an auction settings. This paper deals with quite general settings and minimizing social costs. We show that appropriately computed posted prices allow one to achieve essentially the… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1504.01093v1-abstract-full').style.display = 'inline'; document.getElementById('1504.01093v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1504.01093v1-abstract-full" style="display: none;"> We consider dynamic pricing schemes in online settings where selfish agents generate online events. Previous work on online mechanisms has dealt almost entirely with the goal of maximizing social welfare or revenue in an auction settings. This paper deals with quite general settings and minimizing social costs. We show that appropriately computed posted prices allow one to achieve essentially the same performance as the best online algorithm. This holds in a wide variety of settings. Unlike online algorithms that learn about the event, and then make enforceable decisions, prices are posted without knowing the future events or even the current event, and are thus inherently dominant strategy incentive compatible. In particular we show that one can give efficient posted price mechanisms for metrical task systems, some instances of the $k$-server problem, and metrical matching problems. We give both deterministic and randomized algorithms. Such posted price mechanisms decrease the social cost dramatically over selfish behavior where no decision incurs a charge. One alluring application of this is reducing the social cost of free parking exponentially. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1504.01093v1-abstract-full').style.display = 'none'; document.getElementById('1504.01093v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 5 April, 2015; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2015. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Appeared in the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1310.8381">arXiv:1310.8381</a> <span> [<a href="https://arxiv.org/pdf/1310.8381">pdf</a>, <a href="https://arxiv.org/format/1310.8381">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Distributed, Parallel, and Cluster Computing">cs.DC</span> </div> </div> <p class="title is-5 mathjax"> A Labeling Approach to Incremental Cycle Detection </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Cohen%2C+E">Edith Cohen</a>, <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Kaplan%2C+H">Haim Kaplan</a>, <a href="/search/cs?searchtype=author&query=Roditty%2C+L">Liam Roditty</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1310.8381v1-abstract-short" style="display: inline;"> In the \emph{incremental cycle detection} problem arcs are added to a directed acyclic graph and the algorithm has to report if the new arc closes a cycle. One seeks to minimize the total time to process the entire sequence of arc insertions, or until a cycle appears. In a recent breakthrough, Bender, Fineman, Gilbert and Tarjan \cite{BeFiGiTa11} presented two different algorithms, with time com… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1310.8381v1-abstract-full').style.display = 'inline'; document.getElementById('1310.8381v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1310.8381v1-abstract-full" style="display: none;"> In the \emph{incremental cycle detection} problem arcs are added to a directed acyclic graph and the algorithm has to report if the new arc closes a cycle. One seeks to minimize the total time to process the entire sequence of arc insertions, or until a cycle appears. In a recent breakthrough, Bender, Fineman, Gilbert and Tarjan \cite{BeFiGiTa11} presented two different algorithms, with time complexity $O(n^2 \log n)$ and $O(m \cdot \min \{m^{1/2}, n^{2/3} \})$, respectively. In this paper we introduce a new technique for incremental cycle detection that allows us to obtain both bounds (up to a logarithmic factor). Furthermore, our approach seems more amiable for distributed implementation. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1310.8381v1-abstract-full').style.display = 'none'; document.getElementById('1310.8381v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 31 October, 2013; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2013. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">15 pages, one figure</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1306.3772">arXiv:1306.3772</a> <span> [<a href="https://arxiv.org/pdf/1306.3772">pdf</a>, <a href="https://arxiv.org/format/1306.3772">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Minimal Indices for Successor Search </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Cohen%2C+S">Sarel Cohen</a>, <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Hershcovitch%2C+M">Moshik Hershcovitch</a>, <a href="/search/cs?searchtype=author&query=Kaplan%2C+H">Haim Kaplan</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1306.3772v1-abstract-short" style="display: inline;"> We give a new successor data structure which improves upon the index size of the P菐tra艧cu-Thorup data structures, reducing the index size from $O(n w^{4/5})$ bits to $O(n \log w)$ bits, with optimal probe complexity. Alternatively, our new data structure can be viewed as matching the space complexity of the (probe-suboptimal) $z$-fast trie of Belazzougui et al. Thus, we get the best of both approa… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1306.3772v1-abstract-full').style.display = 'inline'; document.getElementById('1306.3772v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1306.3772v1-abstract-full" style="display: none;"> We give a new successor data structure which improves upon the index size of the P菐tra艧cu-Thorup data structures, reducing the index size from $O(n w^{4/5})$ bits to $O(n \log w)$ bits, with optimal probe complexity. Alternatively, our new data structure can be viewed as matching the space complexity of the (probe-suboptimal) $z$-fast trie of Belazzougui et al. Thus, we get the best of both approaches with respect to both probe count and index size. The penalty we pay is an extra $O(\log w)$ inter-register operations. Our data structure can also be used to solve the weak prefix search problem, the index size of $O(n \log w)$ bits is known to be optimal for any such data structure. The technical contributions include highly efficient single word indices, with out-degree $w/\log w$ (compared to the $w^{1/5}$ out-degree of fusion tree based indices). To construct such high efficiency single word indices we device highly efficient bit selectors which, we believe, are of independent interest. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1306.3772v1-abstract-full').style.display = 'none'; document.getElementById('1306.3772v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 17 June, 2013; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2013. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">28 pages, full version, extended abstract submitted to MFCS 2013</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1208.3939">arXiv:1208.3939</a> <span> [<a href="https://arxiv.org/pdf/1208.3939">pdf</a>, <a href="https://arxiv.org/ps/1208.3939">ps</a>, <a href="https://arxiv.org/format/1208.3939">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> </div> </div> <p class="title is-5 mathjax"> Approaching Utopia: Strong Truthfulness and Externality-Resistant Mechanisms </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Karlin%2C+A+R">Anna R. Karlin</a>, <a href="/search/cs?searchtype=author&query=Koutsoupias%2C+E">Elias Koutsoupias</a>, <a href="/search/cs?searchtype=author&query=Vidali%2C+A">Angelina Vidali</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1208.3939v1-abstract-short" style="display: inline;"> We introduce and study strongly truthful mechanisms and their applications. We use strongly truthful mechanisms as a tool for implementation in undominated strategies for several problems,including the design of externality resistant auctions and a variant of multi-dimensional scheduling. </span> <span class="abstract-full has-text-grey-dark mathjax" id="1208.3939v1-abstract-full" style="display: none;"> We introduce and study strongly truthful mechanisms and their applications. We use strongly truthful mechanisms as a tool for implementation in undominated strategies for several problems,including the design of externality resistant auctions and a variant of multi-dimensional scheduling. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1208.3939v1-abstract-full').style.display = 'none'; document.getElementById('1208.3939v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 20 August, 2012; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 2012. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1205.1786">arXiv:1205.1786</a> <span> [<a href="https://arxiv.org/pdf/1205.1786">pdf</a>, <a href="https://arxiv.org/ps/1205.1786">ps</a>, <a href="https://arxiv.org/format/1205.1786">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Discrete Mathematics">cs.DM</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> </div> </div> <p class="title is-5 mathjax"> Tight Lower Bounds on Envy-Free Makespan Approximation </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Levavi%2C+A">Ariel Levavi</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1205.1786v1-abstract-short" style="display: inline;"> In this work we give a tight lower bound on makespan approximations for envy-free allocation mechanism dedicated to scheduling tasks on unrelated machines. Specifically, we show that no mechanism exists that can guarantee an envy-free allocation of jobs to $m$ machines with a makespan of less than a factor of $O(\log m)$ of the minimal makespan. Combined with previous results, this paper definitiv… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1205.1786v1-abstract-full').style.display = 'inline'; document.getElementById('1205.1786v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1205.1786v1-abstract-full" style="display: none;"> In this work we give a tight lower bound on makespan approximations for envy-free allocation mechanism dedicated to scheduling tasks on unrelated machines. Specifically, we show that no mechanism exists that can guarantee an envy-free allocation of jobs to $m$ machines with a makespan of less than a factor of $O(\log m)$ of the minimal makespan. Combined with previous results, this paper definitively proves that the optimal algorithm for obtaining a minimal makespan for any envy-free division can at best approximate the makespan to a factor of $O(\log m)$. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1205.1786v1-abstract-full').style.display = 'none'; document.getElementById('1205.1786v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 8 May, 2012; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2012. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1003.5328">arXiv:1003.5328</a> <span> [<a href="https://arxiv.org/pdf/1003.5328">pdf</a>, <a href="https://arxiv.org/ps/1003.5328">ps</a>, <a href="https://arxiv.org/format/1003.5328">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> </div> </div> <p class="title is-5 mathjax"> On the Interplay between Incentive Compatibility and Envy Freeness </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Cohen%2C+E">Edith Cohen</a>, <a href="/search/cs?searchtype=author&query=Feldman%2C+M">Michal Feldman</a>, <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Kaplan%2C+H">Haim Kaplan</a>, <a href="/search/cs?searchtype=author&query=Olonetsky%2C+S">Svetlana Olonetsky</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1003.5328v1-abstract-short" style="display: inline;"> We study mechanisms for an allocation of goods among agents, where agents have no incentive to lie about their true values (incentive compatible) and for which no agent will seek to exchange outcomes with another (envy-free). Mechanisms satisfying each requirement separately have been studied extensively, but there are few results on mechanisms achieving both. We are interested in those allocation… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1003.5328v1-abstract-full').style.display = 'inline'; document.getElementById('1003.5328v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1003.5328v1-abstract-full" style="display: none;"> We study mechanisms for an allocation of goods among agents, where agents have no incentive to lie about their true values (incentive compatible) and for which no agent will seek to exchange outcomes with another (envy-free). Mechanisms satisfying each requirement separately have been studied extensively, but there are few results on mechanisms achieving both. We are interested in those allocations for which there exist payments such that the resulting mechanism is simultaneously incentive compatible and envy-free. Cyclic monotonicity is a characterization of incentive compatible allocations, local efficiency is a characterization for envy-free allocations. We combine the above to give a characterization for allocations which are both incentive compatible and envy free. We show that even for allocations that allow payments leading to incentive compatible mechanisms, and other payments leading to envy free mechanisms, there may not exist any payments for which the mechanism is simultaneously incentive compatible and envy-free. The characterization that we give lets us compute the set of Pareto-optimal mechanisms that trade off envy freeness for incentive compatibility. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1003.5328v1-abstract-full').style.display = 'none'; document.getElementById('1003.5328v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 27 March, 2010; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 2010. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1003.5326">arXiv:1003.5326</a> <span> [<a href="https://arxiv.org/pdf/1003.5326">pdf</a>, <a href="https://arxiv.org/ps/1003.5326">ps</a>, <a href="https://arxiv.org/format/1003.5326">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> </div> </div> <p class="title is-5 mathjax"> Truth and Envy in Capacitated Allocation Games </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Cohen%2C+E">Edith Cohen</a>, <a href="/search/cs?searchtype=author&query=Feldman%2C+M">Michal Feldman</a>, <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Kaplan%2C+H">Haim Kaplan</a>, <a href="/search/cs?searchtype=author&query=Olonetsky%2C+S">Svetlana Olonetsky</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1003.5326v2-abstract-short" style="display: inline;"> We study auctions with additive valuations where agents have a limit on the number of goods they may receive. We refer to such valuations as {\em capacitated} and seek mechanisms that maximize social welfare and are simultaneously incentive compatible, envy-free, individually rational, and have no positive transfers. If capacities are infinite, then sequentially repeating the 2nd price Vickrey auc… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1003.5326v2-abstract-full').style.display = 'inline'; document.getElementById('1003.5326v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1003.5326v2-abstract-full" style="display: none;"> We study auctions with additive valuations where agents have a limit on the number of goods they may receive. We refer to such valuations as {\em capacitated} and seek mechanisms that maximize social welfare and are simultaneously incentive compatible, envy-free, individually rational, and have no positive transfers. If capacities are infinite, then sequentially repeating the 2nd price Vickrey auction meets these requirements. In 1983, Leonard showed that for unit capacities, VCG with Clarke Pivot payments is also envy free. For capacities that are all unit or all infinite, the mechanism produces a Walrasian pricing (subject to capacity constraints). Here, we consider general capacities. For homogeneous capacities (all capacities equal) we show that VCG with Clarke Pivot payments is envy free (VCG with Clarke Pivot payments is always incentive compatible, individually rational, and has no positive transfers). Contrariwise, there is no incentive compatible Walrasian pricing. For heterogeneous capacities, we show that there is no mechanism with all 4 properties, but at least in some cases, one can achieve both incentive compatibility and envy freeness. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1003.5326v2-abstract-full').style.display = 'none'; document.getElementById('1003.5326v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 28 February, 2011; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 27 March, 2010; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 2010. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1001.1686">arXiv:1001.1686</a> <span> [<a href="https://arxiv.org/pdf/1001.1686">pdf</a>, <a href="https://arxiv.org/ps/1001.1686">ps</a>, <a href="https://arxiv.org/format/1001.1686">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Combinatorial Auctions with Budgets </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Leonardi%2C+S">Stefano Leonardi</a>, <a href="/search/cs?searchtype=author&query=Saia%2C+J">Jared Saia</a>, <a href="/search/cs?searchtype=author&query=Sankowski%2C+P">Piotr Sankowski</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1001.1686v2-abstract-short" style="display: inline;"> We consider budget constrained combinatorial auctions where bidder $i$ has a private value $v_i$, a budget $b_i$, and is interested in all the items in $S_i$. The value to agent $i$ of a set of items $R$ is $|R \cap S_i| \cdot v_i$. Such auctions capture adword auctions, where advertisers offer a bid for ads in response to an advertiser-dependent set of adwords, and advertisers have budgets. It is… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1001.1686v2-abstract-full').style.display = 'inline'; document.getElementById('1001.1686v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1001.1686v2-abstract-full" style="display: none;"> We consider budget constrained combinatorial auctions where bidder $i$ has a private value $v_i$, a budget $b_i$, and is interested in all the items in $S_i$. The value to agent $i$ of a set of items $R$ is $|R \cap S_i| \cdot v_i$. Such auctions capture adword auctions, where advertisers offer a bid for ads in response to an advertiser-dependent set of adwords, and advertisers have budgets. It is known that even of all items are identical and all budgets are public it is not possible to be truthful and efficient. Our main result is a novel auction that runs in polynomial time, is incentive compatible, and ensures Pareto-optimality for such auctions when the valuations are private and the budgets are public knowledge. This extends the result of Dobzinski et al. (FOCS 2008) for auctions of multiple {\sl identical} items and public budgets to single-valued {\sl combinatorial} auctions with public budgets. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1001.1686v2-abstract-full').style.display = 'none'; document.getElementById('1001.1686v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 20 April, 2010; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 11 January, 2010; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2010. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">ACM Class:</span> F.2.2; G.2.2 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/0909.4569">arXiv:0909.4569</a> <span> [<a href="https://arxiv.org/pdf/0909.4569">pdf</a>, <a href="https://arxiv.org/ps/0909.4569">ps</a>, <a href="https://arxiv.org/format/0909.4569">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> </div> </div> <p class="title is-5 mathjax"> Envy, Multi Envy, and Revenue Maximization </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Wingarten%2C+A">Amiram Wingarten</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="0909.4569v1-abstract-short" style="display: inline;"> We study the envy free pricing problem faced by a seller who wishes to maximize revenue by setting prices for bundles of items. If there is an unlimited supply of items and agents are single minded then we show that finding the revenue maximizing envy free allocation/pricing can be solved in polynomial time by reducing it to an instance of weighted independent set on a perfect graph. We define… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('0909.4569v1-abstract-full').style.display = 'inline'; document.getElementById('0909.4569v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="0909.4569v1-abstract-full" style="display: none;"> We study the envy free pricing problem faced by a seller who wishes to maximize revenue by setting prices for bundles of items. If there is an unlimited supply of items and agents are single minded then we show that finding the revenue maximizing envy free allocation/pricing can be solved in polynomial time by reducing it to an instance of weighted independent set on a perfect graph. We define an allocation/pricing as \textit{multi envy free} if no agent wishes to replace her allocation with the union of the allocations of some set of other agents and her price with the sum of their prices. We show that it is \textit{coNP}-hard to decide if a given allocation/pricing is multi envy free. We also show that revenue maximization multi envy free allocation/pricing is \textit{APX} hard. Furthermore, we give efficient algorithms and hardness results for various variants of the highway problem. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('0909.4569v1-abstract-full').style.display = 'none'; document.getElementById('0909.4569v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 24 September, 2009; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2009. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/0909.1072">arXiv:0909.1072</a> <span> [<a href="https://arxiv.org/pdf/0909.1072">pdf</a>, <a href="https://arxiv.org/ps/0909.1072">ps</a>, <a href="https://arxiv.org/format/0909.1072">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Science and Game Theory">cs.GT</span> </div> </div> <p class="title is-5 mathjax"> Envy-Free Makespan Approximation </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Cohen%2C+E">Edith Cohen</a>, <a href="/search/cs?searchtype=author&query=Feldman%2C+M">Michal Feldman</a>, <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Kaplan%2C+H">Haim Kaplan</a>, <a href="/search/cs?searchtype=author&query=Olonetsky%2C+S">Svetlana Olonetsky</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="0909.1072v1-abstract-short" style="display: inline;"> We study envy-free mechanisms for scheduling tasks on unrelated machines (agents) that approximately minimize the makespan. For indivisible tasks, we put forward an envy-free poly-time mechanism that approximates the minimal makespan to within a factor of $O(\log m)$, where $m$ is the number of machines. We also show a lower bound of $惟(\log m / \log\log m)$. This improves the recent result of H… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('0909.1072v1-abstract-full').style.display = 'inline'; document.getElementById('0909.1072v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="0909.1072v1-abstract-full" style="display: none;"> We study envy-free mechanisms for scheduling tasks on unrelated machines (agents) that approximately minimize the makespan. For indivisible tasks, we put forward an envy-free poly-time mechanism that approximates the minimal makespan to within a factor of $O(\log m)$, where $m$ is the number of machines. We also show a lower bound of $惟(\log m / \log\log m)$. This improves the recent result of Hartline {\sl et al.} \cite{Ahuva:2008} who give an upper bound of $(m+1)/2$, and a lower bound of $2-1/m$. For divisible tasks, we show that there always exists an envy-free poly-time mechanism with optimal makespan. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('0909.1072v1-abstract-full').style.display = 'none'; document.getElementById('0909.1072v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 6 September, 2009; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2009. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/cs/0601127">arXiv:cs/0601127</a> <span> [<a href="https://arxiv.org/pdf/cs/0601127">pdf</a>, <a href="https://arxiv.org/ps/cs/0601127">ps</a>, <a href="https://arxiv.org/format/cs/0601127">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1109/SFCS.1997.646121">10.1109/SFCS.1997.646121 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Truly Online Paging with Locality of Reference </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Mendel%2C+M">Manor Mendel</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="cs/0601127v1-abstract-short" style="display: inline;"> The competitive analysis fails to model locality of reference in the online paging problem. To deal with it, Borodin et. al. introduced the access graph model, which attempts to capture the locality of reference. However, the access graph model has a number of troubling aspects. The access graph has to be known in advance to the paging algorithm and the memory required to represent the access gr… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('cs/0601127v1-abstract-full').style.display = 'inline'; document.getElementById('cs/0601127v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="cs/0601127v1-abstract-full" style="display: none;"> The competitive analysis fails to model locality of reference in the online paging problem. To deal with it, Borodin et. al. introduced the access graph model, which attempts to capture the locality of reference. However, the access graph model has a number of troubling aspects. The access graph has to be known in advance to the paging algorithm and the memory required to represent the access graph itself may be very large. In this paper we present truly online strongly competitive paging algorithms in the access graph model that do not have any prior information on the access sequence. We present both deterministic and randomized algorithms. The algorithms need only O(k log n) bits of memory, where k is the number of page slots available and n is the size of the virtual address space. I.e., asymptotically no more memory than needed to store the virtual address translation table. We also observe that our algorithms adapt themselves to temporal changes in the locality of reference. We model temporal changes in the locality of reference by extending the access graph model to the so called extended access graph model, in which many vertices of the graph can correspond to the same virtual page. We define a measure for the rate of change in the locality of reference in G denoted by Delta(G). We then show our algorithms remain strongly competitive as long as Delta(G) >= (1+ epsilon)k, and no truly online algorithm can be strongly competitive on a class of extended access graphs that includes all graphs G with Delta(G) >= k- o(k). <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('cs/0601127v1-abstract-full').style.display = 'none'; document.getElementById('cs/0601127v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 30 January, 2006; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2006. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">37 pages. Preliminary version appeared in FOCS '97</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> 38th Annual Symposium on Foundations of Computer Science (FOCS '97), 1997, pp. 326 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/cs/0406034">arXiv:cs/0406034</a> <span> [<a href="https://arxiv.org/pdf/cs/0406034">pdf</a>, <a href="https://arxiv.org/ps/cs/0406034">ps</a>, <a href="https://arxiv.org/format/cs/0406034">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1137/S0097539700376159">10.1137/S0097539700376159 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Better algorithms for unfair metrical task systems and applications </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Mendel%2C+M">Manor Mendel</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="cs/0406034v1-abstract-short" style="display: inline;"> Unfair metrical task systems are a generalization of online metrical task systems. In this paper we introduce new techniques to combine algorithms for unfair metrical task systems and apply these techniques to obtain improved randomized online algorithms for metrical task systems on arbitrary metric spaces. </span> <span class="abstract-full has-text-grey-dark mathjax" id="cs/0406034v1-abstract-full" style="display: none;"> Unfair metrical task systems are a generalization of online metrical task systems. In this paper we introduce new techniques to combine algorithms for unfair metrical task systems and apply these techniques to obtain improved randomized online algorithms for metrical task systems on arbitrary metric spaces. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('cs/0406034v1-abstract-full').style.display = 'none'; document.getElementById('cs/0406034v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 17 June, 2004; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2004. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">20 pages, 1 figure</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> SIAM Journal on Computing 32(6), pp. 1403-1422, 2003 </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/cs/0205038">arXiv:cs/0205038</a> <span> [<a href="https://arxiv.org/pdf/cs/0205038">pdf</a>, <a href="https://arxiv.org/ps/cs/0205038">ps</a>, <a href="https://arxiv.org/format/cs/0205038">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Networking and Internet Architecture">cs.NI</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1016/0196-6774(91)90041-V">10.1016/0196-6774(91)90041-V <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Competitive Paging Algorithms </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Fiat%2C+A">Amos Fiat</a>, <a href="/search/cs?searchtype=author&query=Karp%2C+R">Richard Karp</a>, <a href="/search/cs?searchtype=author&query=Luby%2C+M">Mike Luby</a>, <a href="/search/cs?searchtype=author&query=McGeoch%2C+L">Lyle McGeoch</a>, <a href="/search/cs?searchtype=author&query=Sleator%2C+D">Daniel Sleator</a>, <a href="/search/cs?searchtype=author&query=Young%2C+N+E">Neal E. Young</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="cs/0205038v1-abstract-short" style="display: inline;"> The paging problem is that of deciding which pages to keep in a memory of k pages in order to minimize the number of page faults. This paper introduces the marking algorithm, a simple randomized on-line algorithm for the paging problem, and gives a proof that its performance guarantee (competitive ratio) is O(log k). In contrast, no deterministic on-line algorithm can have a performance guarante… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('cs/0205038v1-abstract-full').style.display = 'inline'; document.getElementById('cs/0205038v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="cs/0205038v1-abstract-full" style="display: none;"> The paging problem is that of deciding which pages to keep in a memory of k pages in order to minimize the number of page faults. This paper introduces the marking algorithm, a simple randomized on-line algorithm for the paging problem, and gives a proof that its performance guarantee (competitive ratio) is O(log k). In contrast, no deterministic on-line algorithm can have a performance guarantee better than k. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('cs/0205038v1-abstract-full').style.display = 'none'; document.getElementById('cs/0205038v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 18 May, 2002; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2002. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">ACM Class:</span> F.2.0; F.1.2; C.0 </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Journal of Algorithms 12:685-699 (1991) </p> </li> </ol> <div class="is-hidden-tablet">  <span class="help" style="display: inline-block;"><a href="https://github.com/arXiv/arxiv-search/releases">Search v0.5.6 released 2020-02-24</a>  </span> </div> </div> </main> <footer> <div class="columns is-desktop" role="navigation" aria-label="Secondary">  <div class="column"> <div class="columns"> <div class="column"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/about">About</a></li> <li><a href="https://info.arxiv.org/help">Help</a></li> </ul> </div> <div class="column"> <ul class="nav-spaced"> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>contact arXiv</title><desc>Click here to contact arXiv</desc><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg> <a href="https://info.arxiv.org/help/contact.html"> Contact</a> </li> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>subscribe to arXiv mailings</title><desc>Click here to subscribe</desc><path d="M476 3.2L12.5 270.6c-18.1 10.4-15.8 35.6 2.2 43.2L121 358.4l287.3-253.2c5.5-4.9 13.3 2.6 8.6 8.3L176 407v80.5c0 23.6 28.5 32.9 42.5 15.8L282 426l124.6 52.2c14.2 6 30.4-2.9 33-18.2l72-432C515 7.8 493.3-6.8 476 3.2z"/></svg> <a href="https://info.arxiv.org/help/subscribe"> Subscribe</a> </li> </ul> </div> </div> </div>   <div class="column"> <div class="columns"> <div class="column"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/help/license/index.html">Copyright</a></li> <li><a href="https://info.arxiv.org/help/policies/privacy_policy.html">Privacy Policy</a></li> </ul> </div> <div class="column sorry-app-links"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/help/web_accessibility.html">Web Accessibility Assistance</a></li> <li> <p class="help"> <a class="a11y-main-link" href="https://status.arxiv.org" target="_blank">arXiv Operational Status <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 256 512" class="icon filter-dark_grey" role="presentation"><path d="M224.3 273l-136 136c-9.4 9.4-24.6 9.4-33.9 0l-22.6-22.6c-9.4-9.4-9.4-24.6 0-33.9l96.4-96.4-96.4-96.4c-9.4-9.4-9.4-24.6 0-33.9L54.3 103c9.4-9.4 24.6-9.4 33.9 0l136 136c9.5 9.4 9.5 24.6.1 34z"/></svg></a><br> Get status notifications via <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/email/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg>email</a> or <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/slack/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512" class="icon filter-black" role="presentation"><path d="M94.12 315.1c0 25.9-21.16 47.06-47.06 47.06S0 341 0 315.1c0-25.9 21.16-47.06 47.06-47.06h47.06v47.06zm23.72 0c0-25.9 21.16-47.06 47.06-47.06s47.06 21.16 47.06 47.06v117.84c0 25.9-21.16 47.06-47.06 47.06s-47.06-21.16-47.06-47.06V315.1zm47.06-188.98c-25.9 0-47.06-21.16-47.06-47.06S139 32 164.9 32s47.06 21.16 47.06 47.06v47.06H164.9zm0 23.72c25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06H47.06C21.16 243.96 0 222.8 0 196.9s21.16-47.06 47.06-47.06H164.9zm188.98 47.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06h-47.06V196.9zm-23.72 0c0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06V79.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06V196.9zM283.1 385.88c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06v-47.06h47.06zm0-23.72c-25.9 0-47.06-21.16-47.06-47.06 0-25.9 21.16-47.06 47.06-47.06h117.84c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06H283.1z"/></svg>slack</a> </p> </li> </ul> </div> </div> </div>  </div> </footer> <script src="https://static.arxiv.org/static/base/1.0.0a5/js/member_acknowledgement.js"></script> </body> </html>

CINXE.COM

Search | arXiv e-print repository