From 1cb6e4b28e77b8c1a87e54bbd7097d7f8af0e371 Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Sun, 22 Sep 2013 07:54:48 +0200 Subject: stratis edits --- .gitignore | 0 abstract.tex | 0 ack.tex | 0 appendix.tex | 0 approximation.tex | 0 conclusion.tex | 0 counterexample.tex | 0 definitions.tex | 0 ec/ec.pdf | Bin ec/rebuttal.txt | 0 ec/reviews.txt | 0 general.tex | 0 intro.tex | 0 main.tex | 0 myerson.tex | 0 notes.bib | 0 paper.tex | 0 papers/05budgeted.pdf | Bin papers/READMEbetterca.pdf | 0 papers/READMEexpectation.pdf | Bin papers/READMErandomca.pdf | 0 papers/READapproximationTechniques.pdf | Bin papers/READcomptruthful.pdf | 0 papers/READproxy.pdf | 0 papers/READsubmod-comm.pdf | 0 papers/Rubens-Active-Learning-RecSysHB2010.pdf | Bin .../budget_feasible_mechanisms/BudgetFeasibleMechanisms.pdf | Bin .../HowToWinFriendsAndInfluencePeople.pdf | Bin papers/budget_feasible_mechanisms/SODA11_054_chenn.pdf | Bin papers/experimental_design/chaloner.pdf | Bin papers/experimental_design/chaloner2.pdf | Bin papers/experimental_design/degroot1.pdf | Bin papers/experimental_design/ginebra.pdf | Bin papers/experimental_design/kiefer.pdf | Bin papers/experimental_design/lindley.pdf | Bin papers/experimental_design/max-ent00.pdf | Bin papers/influentialobservations79.pdf | Bin papers/krause05note.pdf | Bin papers/lse.pdf | Bin papers/matrixinverse.pdf | Bin papers/maxdet_rev.pdf | Bin papers/optimal.pdf | Bin papers/recommendation.pdf | Bin papers/settles.activelearning.pdf | Bin papers/shapley.pdf | Bin papers/shermanmorrison.pdf | Bin papers/strategyproof.ps | 0 papers/submod-knapsack-constraint.pdf | Bin papers/submodular_survey.pdf | Bin papers/subsetselection08.pdf | Bin papers/subsetselection11.pdf | Bin plot.py | 0 problem.tex | 0 proof_of_lower_bound1.tex | 0 related.tex | 0 slides/1.pdf | Bin slides/11949848541326072700padlock_aj_ashton_01.svg | 0 slides/1197103065746278958mcol_money_bag.svg | 0 slides/2.pdf | Bin slides/3.pdf | Bin slides/4.pdf | Bin slides/5.pdf | Bin slides/6.pdf | Bin slides/7.pdf | Bin slides/8.pdf | Bin slides/Amazon-logo.jpg | Bin slides/BudgetFeasibleExperimentalDesign.tex | 0 slides/BudgetFeasibleExperimentalDesignGoogle.tex | 0 slides/Google-logo1.jpg | Bin slides/Netflix_Logo.jpg | Bin slides/Padlock.svg | 0 slides/beamerbfootertechnicolor.png | Bin slides/beamerblogotechnicolor.png | Bin slides/beamercolorthemetechnicolor.sty | 0 slides/beamerfontthemetechnicolor.sty | 0 slides/beamerfootertechnicolor.png | Bin slides/beamerinnerthemetechnicolor.sty | 0 slides/beamerlogotechnicolor.png | Bin slides/beamerouterthemetechnicolor.sty | 0 slides/beamersampletechnicolor1.jpg | Bin slides/beamersampletechnicolor10.jpg | Bin slides/beamersampletechnicolor11.jpg | Bin slides/beamersampletechnicolor12.jpg | Bin slides/beamersampletechnicolor13.jpg | Bin slides/beamersampletechnicolor14.jpg | Bin slides/beamersampletechnicolor15.jpg | Bin slides/beamersampletechnicolor16.jpg | Bin slides/beamersampletechnicolor17.jpg | Bin slides/beamersampletechnicolor2.jpg | Bin slides/beamersampletechnicolor3.jpg | Bin slides/beamersampletechnicolor4.jpg | Bin slides/beamersampletechnicolor5.jpg | Bin slides/beamersampletechnicolor6.jpg | Bin slides/beamersampletechnicolor7.jpg | Bin slides/beamersampletechnicolor8.jpg | Bin slides/beamersampletechnicolor9.jpg | Bin slides/beamerthemetechnicolor.sty | 0 slides/db.svg | 0 slides/diagram.svg | 0 slides/facebook_logo.jpg | Bin slides/file.svg | 0 slides/lock.svg | 0 slides/money_bag.svg | 0 slides/scientist.svg | 0 slides/slides.tex | 0 slides/sp3.svg | 0 slides/st1.eps | 0 slides/st1.pdf | Bin slides/st1.png | Bin slides/st1.svg | 0 slides/st10.pdf | Bin slides/st10.svg | 0 slides/st10a.pdf | Bin slides/st10a.svg | 0 slides/st10b.pdf | Bin slides/st10b.svg | 0 slides/st10c.pdf | Bin slides/st10c.svg | 0 slides/st10d.pdf | Bin slides/st10d.svg | 0 slides/st10e.pdf | Bin slides/st10e.svg | 0 slides/st10f.pdf | Bin slides/st10f.svg | 0 slides/st11a.pdf | Bin slides/st11a.svg | 0 slides/st11b.pdf | Bin slides/st11b.svg | 0 slides/st11c.pdf | Bin slides/st11c.svg | 0 slides/st11d.pdf | Bin slides/st11d.svg | 0 slides/st1a.pdf | Bin slides/st1a.svg | 0 slides/st1b.pdf | Bin slides/st1b.svg | 0 slides/st1c.pdf | Bin slides/st1c.svg | 0 slides/st1d.pdf | Bin slides/st1d.svg | 0 slides/st1dd.pdf | Bin slides/st1dd.svg | 0 slides/st1e.pdf | Bin slides/st1e.svg | 0 slides/st1f.pdf | Bin slides/st1f.svg | 0 slides/st1g.pdf | Bin slides/st1g.svg | 0 slides/st1h.pdf | Bin slides/st1h.svg | 0 slides/st2.pdf | Bin slides/st2.svg | 0 slides/st25.pdf | Bin slides/st25.svg | 0 slides/st26.pdf | Bin slides/st26.svg | 0 slides/st2a.svg | 0 slides/st3.pdf | Bin slides/st3.svg | 0 slides/st31a.pdf | Bin slides/st31a.svg | 0 slides/st31b.pdf | Bin slides/st31b.svg | 0 slides/st31c.pdf | Bin slides/st31c.svg | 0 slides/st31d.pdf | Bin slides/st31d.svg | 0 slides/st31dd.pdf | Bin slides/st31dd.svg | 0 slides/st31e.pdf | Bin slides/st31e.svg | 0 slides/st31f.pdf | Bin slides/st31f.svg | 0 slides/st31g.pdf | Bin slides/st31g.svg | 0 slides/st4.pdf | Bin slides/st4.svg | 0 slides/st5.pdf | Bin slides/st5.svg | 0 slides/st6.pdf | Bin slides/st6.svg | 0 slides/st6a.pdf | Bin slides/st6a.svg | 0 slides/st6b.pdf | Bin slides/st6b.svg | 0 slides/st6c.pdf | Bin slides/st6c.svg | 0 slides/st6d.pdf | Bin slides/st6d.svg | 0 slides/st6e.pdf | Bin slides/st6e.svg | 0 slides/st6f.pdf | Bin slides/st6f.svg | 0 slides/st7.pdf | Bin slides/st7.svg | 0 slides/st8.pdf | Bin slides/st8.svg | 0 slides/st9.pdf | Bin slides/st9.svg | 0 slides/stg-1.pdf | Bin slides/stg-1.svg | 0 slides/stg-2.pdf | Bin slides/stg-2.svg | 0 slides/stg-3.pdf | Bin slides/stg-3.svg | 0 slides/stg-4.pdf | Bin slides/stg-4.svg | 0 slides/stg-5.pdf | Bin slides/stg-5.svg | 0 slides/stg-6.pdf | Bin slides/stg-6.svg | 0 slides/stg-7.pdf | Bin slides/stg-7.svg | 0 slides/stg-8.pdf | Bin slides/stg-8.svg | 0 slides/stg-9.pdf | 0 slides/stg31dd.svg | 0 slides/stgall.svg | 0 slides/user.svg | 0 stoc/reviews.txt | 0 stoc/stoc.pdf | Bin todo.txt | 0 222 files changed, 0 insertions(+), 0 deletions(-) mode change 100644 => 100755 .gitignore mode change 100644 => 100755 abstract.tex mode change 100644 => 100755 ack.tex mode change 100644 => 100755 appendix.tex mode change 100644 => 100755 approximation.tex mode change 100644 => 100755 conclusion.tex mode change 100644 => 100755 counterexample.tex mode change 100644 => 100755 definitions.tex mode change 100644 => 100755 ec/ec.pdf mode change 100644 => 100755 ec/rebuttal.txt mode change 100644 => 100755 ec/reviews.txt mode change 100644 => 100755 general.tex mode change 100644 => 100755 intro.tex mode change 100644 => 100755 main.tex mode change 100644 => 100755 myerson.tex mode change 100644 => 100755 notes.bib mode change 100644 => 100755 paper.tex mode change 100644 => 100755 papers/05budgeted.pdf mode change 100644 => 100755 papers/READMEbetterca.pdf mode change 100644 => 100755 papers/READMEexpectation.pdf mode change 100644 => 100755 papers/READMErandomca.pdf mode change 100644 => 100755 papers/READapproximationTechniques.pdf mode change 100644 => 100755 papers/READcomptruthful.pdf mode change 100644 => 100755 papers/READproxy.pdf mode change 100644 => 100755 papers/READsubmod-comm.pdf mode change 100644 => 100755 papers/Rubens-Active-Learning-RecSysHB2010.pdf mode change 100644 => 100755 papers/budget_feasible_mechanisms/BudgetFeasibleMechanisms.pdf mode change 100644 => 100755 papers/budget_feasible_mechanisms/HowToWinFriendsAndInfluencePeople.pdf mode change 100644 => 100755 papers/budget_feasible_mechanisms/SODA11_054_chenn.pdf mode change 100644 => 100755 papers/experimental_design/chaloner.pdf mode change 100644 => 100755 papers/experimental_design/chaloner2.pdf mode change 100644 => 100755 papers/experimental_design/degroot1.pdf mode change 100644 => 100755 papers/experimental_design/ginebra.pdf mode change 100644 => 100755 papers/experimental_design/kiefer.pdf mode change 100644 => 100755 papers/experimental_design/lindley.pdf mode change 100644 => 100755 papers/experimental_design/max-ent00.pdf mode change 100644 => 100755 papers/influentialobservations79.pdf mode change 100644 => 100755 papers/krause05note.pdf mode change 100644 => 100755 papers/lse.pdf mode change 100644 => 100755 papers/matrixinverse.pdf mode change 100644 => 100755 papers/maxdet_rev.pdf mode change 100644 => 100755 papers/optimal.pdf mode change 100644 => 100755 papers/recommendation.pdf mode change 100644 => 100755 papers/settles.activelearning.pdf mode change 100644 => 100755 papers/shapley.pdf mode change 100644 => 100755 papers/shermanmorrison.pdf mode change 100644 => 100755 papers/strategyproof.ps mode change 100644 => 100755 papers/submod-knapsack-constraint.pdf mode change 100644 => 100755 papers/submodular_survey.pdf mode change 100644 => 100755 papers/subsetselection08.pdf mode change 100644 => 100755 papers/subsetselection11.pdf mode change 100644 => 100755 plot.py mode change 100644 => 100755 problem.tex mode change 100644 => 100755 proof_of_lower_bound1.tex mode change 100644 => 100755 related.tex mode change 100644 => 100755 slides/1.pdf mode change 100644 => 100755 slides/11949848541326072700padlock_aj_ashton_01.svg mode change 100644 => 100755 slides/1197103065746278958mcol_money_bag.svg mode change 100644 => 100755 slides/2.pdf mode change 100644 => 100755 slides/3.pdf mode change 100644 => 100755 slides/4.pdf mode change 100644 => 100755 slides/5.pdf mode change 100644 => 100755 slides/6.pdf mode change 100644 => 100755 slides/7.pdf mode change 100644 => 100755 slides/8.pdf mode change 100644 => 100755 slides/Amazon-logo.jpg mode change 100644 => 100755 slides/BudgetFeasibleExperimentalDesign.tex mode change 100644 => 100755 slides/BudgetFeasibleExperimentalDesignGoogle.tex mode change 100644 => 100755 slides/Google-logo1.jpg mode change 100644 => 100755 slides/Netflix_Logo.jpg mode change 100644 => 100755 slides/Padlock.svg mode change 100644 => 100755 slides/beamerbfootertechnicolor.png mode change 100644 => 100755 slides/beamerblogotechnicolor.png mode change 100644 => 100755 slides/beamercolorthemetechnicolor.sty mode change 100644 => 100755 slides/beamerfontthemetechnicolor.sty mode change 100644 => 100755 slides/beamerfootertechnicolor.png mode change 100644 => 100755 slides/beamerinnerthemetechnicolor.sty mode change 100644 => 100755 slides/beamerlogotechnicolor.png mode change 100644 => 100755 slides/beamerouterthemetechnicolor.sty mode change 100644 => 100755 slides/beamersampletechnicolor1.jpg mode change 100644 => 100755 slides/beamersampletechnicolor10.jpg mode change 100644 => 100755 slides/beamersampletechnicolor11.jpg mode change 100644 => 100755 slides/beamersampletechnicolor12.jpg mode change 100644 => 100755 slides/beamersampletechnicolor13.jpg mode change 100644 => 100755 slides/beamersampletechnicolor14.jpg mode change 100644 => 100755 slides/beamersampletechnicolor15.jpg mode change 100644 => 100755 slides/beamersampletechnicolor16.jpg mode change 100644 => 100755 slides/beamersampletechnicolor17.jpg mode change 100644 => 100755 slides/beamersampletechnicolor2.jpg mode change 100644 => 100755 slides/beamersampletechnicolor3.jpg mode change 100644 => 100755 slides/beamersampletechnicolor4.jpg mode change 100644 => 100755 slides/beamersampletechnicolor5.jpg mode change 100644 => 100755 slides/beamersampletechnicolor6.jpg mode change 100644 => 100755 slides/beamersampletechnicolor7.jpg mode change 100644 => 100755 slides/beamersampletechnicolor8.jpg mode change 100644 => 100755 slides/beamersampletechnicolor9.jpg mode change 100644 => 100755 slides/beamerthemetechnicolor.sty mode change 100644 => 100755 slides/db.svg mode change 100644 => 100755 slides/diagram.svg mode change 100644 => 100755 slides/facebook_logo.jpg mode change 100644 => 100755 slides/file.svg mode change 100644 => 100755 slides/lock.svg mode change 100644 => 100755 slides/money_bag.svg mode change 100644 => 100755 slides/scientist.svg mode change 100644 => 100755 slides/slides.tex mode change 100644 => 100755 slides/sp3.svg mode change 100644 => 100755 slides/st1.eps mode change 100644 => 100755 slides/st1.pdf mode change 100644 => 100755 slides/st1.png mode change 100644 => 100755 slides/st1.svg mode change 100644 => 100755 slides/st10.pdf mode change 100644 => 100755 slides/st10.svg mode change 100644 => 100755 slides/st10a.pdf mode change 100644 => 100755 slides/st10a.svg mode change 100644 => 100755 slides/st10b.pdf mode change 100644 => 100755 slides/st10b.svg mode change 100644 => 100755 slides/st10c.pdf mode change 100644 => 100755 slides/st10c.svg mode change 100644 => 100755 slides/st10d.pdf mode change 100644 => 100755 slides/st10d.svg mode change 100644 => 100755 slides/st10e.pdf mode change 100644 => 100755 slides/st10e.svg mode change 100644 => 100755 slides/st10f.pdf mode change 100644 => 100755 slides/st10f.svg mode change 100644 => 100755 slides/st11a.pdf mode change 100644 => 100755 slides/st11a.svg mode change 100644 => 100755 slides/st11b.pdf mode change 100644 => 100755 slides/st11b.svg mode change 100644 => 100755 slides/st11c.pdf mode change 100644 => 100755 slides/st11c.svg mode change 100644 => 100755 slides/st11d.pdf mode change 100644 => 100755 slides/st11d.svg mode change 100644 => 100755 slides/st1a.pdf mode change 100644 => 100755 slides/st1a.svg mode change 100644 => 100755 slides/st1b.pdf mode change 100644 => 100755 slides/st1b.svg mode change 100644 => 100755 slides/st1c.pdf mode change 100644 => 100755 slides/st1c.svg mode change 100644 => 100755 slides/st1d.pdf mode change 100644 => 100755 slides/st1d.svg mode change 100644 => 100755 slides/st1dd.pdf mode change 100644 => 100755 slides/st1dd.svg mode change 100644 => 100755 slides/st1e.pdf mode change 100644 => 100755 slides/st1e.svg mode change 100644 => 100755 slides/st1f.pdf mode change 100644 => 100755 slides/st1f.svg mode change 100644 => 100755 slides/st1g.pdf mode change 100644 => 100755 slides/st1g.svg mode change 100644 => 100755 slides/st1h.pdf mode change 100644 => 100755 slides/st1h.svg mode change 100644 => 100755 slides/st2.pdf mode change 100644 => 100755 slides/st2.svg mode change 100644 => 100755 slides/st25.pdf mode change 100644 => 100755 slides/st25.svg mode change 100644 => 100755 slides/st26.pdf mode change 100644 => 100755 slides/st26.svg mode change 100644 => 100755 slides/st2a.svg mode change 100644 => 100755 slides/st3.pdf mode change 100644 => 100755 slides/st3.svg mode change 100644 => 100755 slides/st31a.pdf mode change 100644 => 100755 slides/st31a.svg mode change 100644 => 100755 slides/st31b.pdf mode change 100644 => 100755 slides/st31b.svg mode change 100644 => 100755 slides/st31c.pdf mode change 100644 => 100755 slides/st31c.svg mode change 100644 => 100755 slides/st31d.pdf mode change 100644 => 100755 slides/st31d.svg mode change 100644 => 100755 slides/st31dd.pdf mode change 100644 => 100755 slides/st31dd.svg mode change 100644 => 100755 slides/st31e.pdf mode change 100644 => 100755 slides/st31e.svg mode change 100644 => 100755 slides/st31f.pdf mode change 100644 => 100755 slides/st31f.svg mode change 100644 => 100755 slides/st31g.pdf mode change 100644 => 100755 slides/st31g.svg mode change 100644 => 100755 slides/st4.pdf mode change 100644 => 100755 slides/st4.svg mode change 100644 => 100755 slides/st5.pdf mode change 100644 => 100755 slides/st5.svg mode change 100644 => 100755 slides/st6.pdf mode change 100644 => 100755 slides/st6.svg mode change 100644 => 100755 slides/st6a.pdf mode change 100644 => 100755 slides/st6a.svg mode change 100644 => 100755 slides/st6b.pdf mode change 100644 => 100755 slides/st6b.svg mode change 100644 => 100755 slides/st6c.pdf mode change 100644 => 100755 slides/st6c.svg mode change 100644 => 100755 slides/st6d.pdf mode change 100644 => 100755 slides/st6d.svg mode change 100644 => 100755 slides/st6e.pdf mode change 100644 => 100755 slides/st6e.svg mode change 100644 => 100755 slides/st6f.pdf mode change 100644 => 100755 slides/st6f.svg mode change 100644 => 100755 slides/st7.pdf mode change 100644 => 100755 slides/st7.svg mode change 100644 => 100755 slides/st8.pdf mode change 100644 => 100755 slides/st8.svg mode change 100644 => 100755 slides/st9.pdf mode change 100644 => 100755 slides/st9.svg mode change 100644 => 100755 slides/stg-1.pdf mode change 100644 => 100755 slides/stg-1.svg mode change 100644 => 100755 slides/stg-2.pdf mode change 100644 => 100755 slides/stg-2.svg mode change 100644 => 100755 slides/stg-3.pdf mode change 100644 => 100755 slides/stg-3.svg mode change 100644 => 100755 slides/stg-4.pdf mode change 100644 => 100755 slides/stg-4.svg mode change 100644 => 100755 slides/stg-5.pdf mode change 100644 => 100755 slides/stg-5.svg mode change 100644 => 100755 slides/stg-6.pdf mode change 100644 => 100755 slides/stg-6.svg mode change 100644 => 100755 slides/stg-7.pdf mode change 100644 => 100755 slides/stg-7.svg mode change 100644 => 100755 slides/stg-8.pdf mode change 100644 => 100755 slides/stg-8.svg mode change 100644 => 100755 slides/stg-9.pdf mode change 100644 => 100755 slides/stg31dd.svg mode change 100644 => 100755 slides/stgall.svg mode change 100644 => 100755 slides/user.svg mode change 100644 => 100755 stoc/reviews.txt mode change 100644 => 100755 stoc/stoc.pdf mode change 100644 => 100755 todo.txt diff --git a/.gitignore b/.gitignore old mode 100644 new mode 100755 diff --git a/abstract.tex b/abstract.tex old mode 100644 new mode 100755 diff --git a/ack.tex b/ack.tex old mode 100644 new mode 100755 diff --git a/appendix.tex b/appendix.tex old mode 100644 new mode 100755 diff --git a/approximation.tex b/approximation.tex old mode 100644 new mode 100755 diff --git a/conclusion.tex b/conclusion.tex old mode 100644 new mode 100755 diff --git a/counterexample.tex b/counterexample.tex old mode 100644 new mode 100755 diff --git a/definitions.tex b/definitions.tex old mode 100644 new mode 100755 diff --git a/ec/ec.pdf b/ec/ec.pdf old mode 100644 new mode 100755 diff --git a/ec/rebuttal.txt b/ec/rebuttal.txt old mode 100644 new mode 100755 diff --git a/ec/reviews.txt b/ec/reviews.txt old mode 100644 new mode 100755 diff --git a/general.tex b/general.tex old mode 100644 new mode 100755 diff --git a/intro.tex b/intro.tex old mode 100644 new mode 100755 diff --git a/main.tex b/main.tex old mode 100644 new mode 100755 diff --git a/myerson.tex b/myerson.tex old mode 100644 new mode 100755 diff --git a/notes.bib b/notes.bib old mode 100644 new mode 100755 diff --git a/paper.tex b/paper.tex old mode 100644 new mode 100755 diff --git a/papers/05budgeted.pdf b/papers/05budgeted.pdf old mode 100644 new mode 100755 diff --git a/papers/READMEbetterca.pdf b/papers/READMEbetterca.pdf old mode 100644 new mode 100755 diff --git a/papers/READMEexpectation.pdf b/papers/READMEexpectation.pdf old mode 100644 new mode 100755 diff --git a/papers/READMErandomca.pdf b/papers/READMErandomca.pdf old mode 100644 new mode 100755 diff --git a/papers/READapproximationTechniques.pdf b/papers/READapproximationTechniques.pdf old mode 100644 new mode 100755 diff --git a/papers/READcomptruthful.pdf b/papers/READcomptruthful.pdf old mode 100644 new mode 100755 diff --git a/papers/READproxy.pdf b/papers/READproxy.pdf old mode 100644 new mode 100755 diff --git a/papers/READsubmod-comm.pdf b/papers/READsubmod-comm.pdf old mode 100644 new mode 100755 diff --git a/papers/Rubens-Active-Learning-RecSysHB2010.pdf b/papers/Rubens-Active-Learning-RecSysHB2010.pdf old mode 100644 new mode 100755 diff --git a/papers/budget_feasible_mechanisms/BudgetFeasibleMechanisms.pdf b/papers/budget_feasible_mechanisms/BudgetFeasibleMechanisms.pdf old mode 100644 new mode 100755 diff --git a/papers/budget_feasible_mechanisms/HowToWinFriendsAndInfluencePeople.pdf b/papers/budget_feasible_mechanisms/HowToWinFriendsAndInfluencePeople.pdf old mode 100644 new mode 100755 diff --git a/papers/budget_feasible_mechanisms/SODA11_054_chenn.pdf b/papers/budget_feasible_mechanisms/SODA11_054_chenn.pdf old mode 100644 new mode 100755 diff --git a/papers/experimental_design/chaloner.pdf b/papers/experimental_design/chaloner.pdf old mode 100644 new mode 100755 diff --git a/papers/experimental_design/chaloner2.pdf b/papers/experimental_design/chaloner2.pdf old mode 100644 new mode 100755 diff --git a/papers/experimental_design/degroot1.pdf b/papers/experimental_design/degroot1.pdf old mode 100644 new mode 100755 diff --git a/papers/experimental_design/ginebra.pdf b/papers/experimental_design/ginebra.pdf old mode 100644 new mode 100755 diff --git a/papers/experimental_design/kiefer.pdf b/papers/experimental_design/kiefer.pdf old mode 100644 new mode 100755 diff --git a/papers/experimental_design/lindley.pdf b/papers/experimental_design/lindley.pdf old mode 100644 new mode 100755 diff --git a/papers/experimental_design/max-ent00.pdf b/papers/experimental_design/max-ent00.pdf old mode 100644 new mode 100755 diff --git a/papers/influentialobservations79.pdf b/papers/influentialobservations79.pdf old mode 100644 new mode 100755 diff --git a/papers/krause05note.pdf b/papers/krause05note.pdf old mode 100644 new mode 100755 diff --git a/papers/lse.pdf b/papers/lse.pdf old mode 100644 new mode 100755 diff --git a/papers/matrixinverse.pdf b/papers/matrixinverse.pdf old mode 100644 new mode 100755 diff --git a/papers/maxdet_rev.pdf b/papers/maxdet_rev.pdf old mode 100644 new mode 100755 diff --git a/papers/optimal.pdf b/papers/optimal.pdf old mode 100644 new mode 100755 diff --git a/papers/recommendation.pdf b/papers/recommendation.pdf old mode 100644 new mode 100755 diff --git a/papers/settles.activelearning.pdf b/papers/settles.activelearning.pdf old mode 100644 new mode 100755 diff --git a/papers/shapley.pdf b/papers/shapley.pdf old mode 100644 new mode 100755 diff --git a/papers/shermanmorrison.pdf b/papers/shermanmorrison.pdf old mode 100644 new mode 100755 diff --git a/papers/strategyproof.ps b/papers/strategyproof.ps old mode 100644 new mode 100755 diff --git a/papers/submod-knapsack-constraint.pdf b/papers/submod-knapsack-constraint.pdf old mode 100644 new mode 100755 diff --git a/papers/submodular_survey.pdf b/papers/submodular_survey.pdf old mode 100644 new mode 100755 diff --git a/papers/subsetselection08.pdf b/papers/subsetselection08.pdf old mode 100644 new mode 100755 diff --git a/papers/subsetselection11.pdf b/papers/subsetselection11.pdf old mode 100644 new mode 100755 diff --git a/plot.py b/plot.py old mode 100644 new mode 100755 diff --git a/problem.tex b/problem.tex old mode 100644 new mode 100755 diff --git a/proof_of_lower_bound1.tex b/proof_of_lower_bound1.tex old mode 100644 new mode 100755 diff --git a/related.tex b/related.tex old mode 100644 new mode 100755 diff --git a/slides/1.pdf b/slides/1.pdf old mode 100644 new mode 100755 diff --git a/slides/11949848541326072700padlock_aj_ashton_01.svg b/slides/11949848541326072700padlock_aj_ashton_01.svg old mode 100644 new mode 100755 diff --git a/slides/1197103065746278958mcol_money_bag.svg b/slides/1197103065746278958mcol_money_bag.svg old mode 100644 new mode 100755 diff --git a/slides/2.pdf b/slides/2.pdf old mode 100644 new mode 100755 diff --git a/slides/3.pdf b/slides/3.pdf old mode 100644 new mode 100755 diff --git a/slides/4.pdf b/slides/4.pdf old mode 100644 new mode 100755 diff --git a/slides/5.pdf b/slides/5.pdf old mode 100644 new mode 100755 diff --git a/slides/6.pdf b/slides/6.pdf old mode 100644 new mode 100755 diff --git a/slides/7.pdf b/slides/7.pdf old mode 100644 new mode 100755 diff --git a/slides/8.pdf b/slides/8.pdf old mode 100644 new mode 100755 diff --git a/slides/Amazon-logo.jpg b/slides/Amazon-logo.jpg old mode 100644 new mode 100755 diff --git a/slides/BudgetFeasibleExperimentalDesign.tex b/slides/BudgetFeasibleExperimentalDesign.tex old mode 100644 new mode 100755 diff --git a/slides/BudgetFeasibleExperimentalDesignGoogle.tex b/slides/BudgetFeasibleExperimentalDesignGoogle.tex old mode 100644 new mode 100755 diff --git a/slides/Google-logo1.jpg b/slides/Google-logo1.jpg old mode 100644 new mode 100755 diff --git a/slides/Netflix_Logo.jpg b/slides/Netflix_Logo.jpg old mode 100644 new mode 100755 diff --git a/slides/Padlock.svg b/slides/Padlock.svg old mode 100644 new mode 100755 diff --git a/slides/beamerbfootertechnicolor.png b/slides/beamerbfootertechnicolor.png old mode 100644 new mode 100755 diff --git a/slides/beamerblogotechnicolor.png b/slides/beamerblogotechnicolor.png old mode 100644 new mode 100755 diff --git a/slides/beamercolorthemetechnicolor.sty b/slides/beamercolorthemetechnicolor.sty old mode 100644 new mode 100755 diff --git a/slides/beamerfontthemetechnicolor.sty b/slides/beamerfontthemetechnicolor.sty old mode 100644 new mode 100755 diff --git a/slides/beamerfootertechnicolor.png b/slides/beamerfootertechnicolor.png old mode 100644 new mode 100755 diff --git a/slides/beamerinnerthemetechnicolor.sty b/slides/beamerinnerthemetechnicolor.sty old mode 100644 new mode 100755 diff --git a/slides/beamerlogotechnicolor.png b/slides/beamerlogotechnicolor.png old mode 100644 new mode 100755 diff --git a/slides/beamerouterthemetechnicolor.sty b/slides/beamerouterthemetechnicolor.sty old mode 100644 new mode 100755 diff --git a/slides/beamersampletechnicolor1.jpg b/slides/beamersampletechnicolor1.jpg old mode 100644 new mode 100755 diff --git a/slides/beamersampletechnicolor10.jpg b/slides/beamersampletechnicolor10.jpg old mode 100644 new mode 100755 diff --git a/slides/beamersampletechnicolor11.jpg b/slides/beamersampletechnicolor11.jpg old mode 100644 new mode 100755 diff --git a/slides/beamersampletechnicolor12.jpg b/slides/beamersampletechnicolor12.jpg old mode 100644 new mode 100755 diff --git a/slides/beamersampletechnicolor13.jpg b/slides/beamersampletechnicolor13.jpg old mode 100644 new mode 100755 diff --git a/slides/beamersampletechnicolor14.jpg b/slides/beamersampletechnicolor14.jpg old mode 100644 new mode 100755 diff --git a/slides/beamersampletechnicolor15.jpg b/slides/beamersampletechnicolor15.jpg old mode 100644 new mode 100755 diff --git a/slides/beamersampletechnicolor16.jpg b/slides/beamersampletechnicolor16.jpg old mode 100644 new mode 100755 diff --git a/slides/beamersampletechnicolor17.jpg b/slides/beamersampletechnicolor17.jpg old mode 100644 new mode 100755 diff --git a/slides/beamersampletechnicolor2.jpg b/slides/beamersampletechnicolor2.jpg old mode 100644 new mode 100755 diff --git a/slides/beamersampletechnicolor3.jpg b/slides/beamersampletechnicolor3.jpg old mode 100644 new mode 100755 diff --git a/slides/beamersampletechnicolor4.jpg b/slides/beamersampletechnicolor4.jpg old mode 100644 new mode 100755 diff --git a/slides/beamersampletechnicolor5.jpg b/slides/beamersampletechnicolor5.jpg old mode 100644 new mode 100755 diff --git a/slides/beamersampletechnicolor6.jpg b/slides/beamersampletechnicolor6.jpg old mode 100644 new mode 100755 diff --git a/slides/beamersampletechnicolor7.jpg b/slides/beamersampletechnicolor7.jpg old mode 100644 new mode 100755 diff --git a/slides/beamersampletechnicolor8.jpg b/slides/beamersampletechnicolor8.jpg old mode 100644 new mode 100755 diff --git a/slides/beamersampletechnicolor9.jpg b/slides/beamersampletechnicolor9.jpg old mode 100644 new mode 100755 diff --git a/slides/beamerthemetechnicolor.sty b/slides/beamerthemetechnicolor.sty old mode 100644 new mode 100755 diff --git a/slides/db.svg b/slides/db.svg old mode 100644 new mode 100755 diff --git a/slides/diagram.svg b/slides/diagram.svg old mode 100644 new mode 100755 diff --git a/slides/facebook_logo.jpg b/slides/facebook_logo.jpg old mode 100644 new mode 100755 diff --git a/slides/file.svg b/slides/file.svg old mode 100644 new mode 100755 diff --git a/slides/lock.svg b/slides/lock.svg old mode 100644 new mode 100755 diff --git a/slides/money_bag.svg b/slides/money_bag.svg old mode 100644 new mode 100755 diff --git a/slides/scientist.svg b/slides/scientist.svg old mode 100644 new mode 100755 diff --git a/slides/slides.tex b/slides/slides.tex old mode 100644 new mode 100755 diff --git a/slides/sp3.svg b/slides/sp3.svg old mode 100644 new mode 100755 diff --git a/slides/st1.eps b/slides/st1.eps old mode 100644 new mode 100755 diff --git a/slides/st1.pdf b/slides/st1.pdf old mode 100644 new mode 100755 diff --git a/slides/st1.png b/slides/st1.png old mode 100644 new mode 100755 diff --git a/slides/st1.svg b/slides/st1.svg old mode 100644 new mode 100755 diff --git a/slides/st10.pdf b/slides/st10.pdf old mode 100644 new mode 100755 diff --git a/slides/st10.svg b/slides/st10.svg old mode 100644 new mode 100755 diff --git a/slides/st10a.pdf b/slides/st10a.pdf old mode 100644 new mode 100755 diff --git a/slides/st10a.svg b/slides/st10a.svg old mode 100644 new mode 100755 diff --git a/slides/st10b.pdf b/slides/st10b.pdf old mode 100644 new mode 100755 diff --git a/slides/st10b.svg b/slides/st10b.svg old mode 100644 new mode 100755 diff --git a/slides/st10c.pdf b/slides/st10c.pdf old mode 100644 new mode 100755 diff --git a/slides/st10c.svg b/slides/st10c.svg old mode 100644 new mode 100755 diff --git a/slides/st10d.pdf b/slides/st10d.pdf old mode 100644 new mode 100755 diff --git a/slides/st10d.svg b/slides/st10d.svg old mode 100644 new mode 100755 diff --git a/slides/st10e.pdf b/slides/st10e.pdf old mode 100644 new mode 100755 diff --git a/slides/st10e.svg b/slides/st10e.svg old mode 100644 new mode 100755 diff --git a/slides/st10f.pdf b/slides/st10f.pdf old mode 100644 new mode 100755 diff --git a/slides/st10f.svg b/slides/st10f.svg old mode 100644 new mode 100755 diff --git a/slides/st11a.pdf b/slides/st11a.pdf old mode 100644 new mode 100755 diff --git a/slides/st11a.svg b/slides/st11a.svg old mode 100644 new mode 100755 diff --git a/slides/st11b.pdf b/slides/st11b.pdf old mode 100644 new mode 100755 diff --git a/slides/st11b.svg b/slides/st11b.svg old mode 100644 new mode 100755 diff --git a/slides/st11c.pdf b/slides/st11c.pdf old mode 100644 new mode 100755 diff --git a/slides/st11c.svg b/slides/st11c.svg old mode 100644 new mode 100755 diff --git a/slides/st11d.pdf b/slides/st11d.pdf old mode 100644 new mode 100755 diff --git a/slides/st11d.svg b/slides/st11d.svg old mode 100644 new mode 100755 diff --git a/slides/st1a.pdf b/slides/st1a.pdf old mode 100644 new mode 100755 diff --git a/slides/st1a.svg b/slides/st1a.svg old mode 100644 new mode 100755 diff --git a/slides/st1b.pdf b/slides/st1b.pdf old mode 100644 new mode 100755 diff --git a/slides/st1b.svg b/slides/st1b.svg old mode 100644 new mode 100755 diff --git a/slides/st1c.pdf b/slides/st1c.pdf old mode 100644 new mode 100755 diff --git a/slides/st1c.svg b/slides/st1c.svg old mode 100644 new mode 100755 diff --git a/slides/st1d.pdf b/slides/st1d.pdf old mode 100644 new mode 100755 diff --git a/slides/st1d.svg b/slides/st1d.svg old mode 100644 new mode 100755 diff --git a/slides/st1dd.pdf b/slides/st1dd.pdf old mode 100644 new mode 100755 diff --git a/slides/st1dd.svg b/slides/st1dd.svg old mode 100644 new mode 100755 diff --git a/slides/st1e.pdf b/slides/st1e.pdf old mode 100644 new mode 100755 diff --git a/slides/st1e.svg b/slides/st1e.svg old mode 100644 new mode 100755 diff --git a/slides/st1f.pdf b/slides/st1f.pdf old mode 100644 new mode 100755 diff --git a/slides/st1f.svg b/slides/st1f.svg old mode 100644 new mode 100755 diff --git a/slides/st1g.pdf b/slides/st1g.pdf old mode 100644 new mode 100755 diff --git a/slides/st1g.svg b/slides/st1g.svg old mode 100644 new mode 100755 diff --git a/slides/st1h.pdf b/slides/st1h.pdf old mode 100644 new mode 100755 diff --git a/slides/st1h.svg b/slides/st1h.svg old mode 100644 new mode 100755 diff --git a/slides/st2.pdf b/slides/st2.pdf old mode 100644 new mode 100755 diff --git a/slides/st2.svg b/slides/st2.svg old mode 100644 new mode 100755 diff --git a/slides/st25.pdf b/slides/st25.pdf old mode 100644 new mode 100755 diff --git a/slides/st25.svg b/slides/st25.svg old mode 100644 new mode 100755 diff --git a/slides/st26.pdf b/slides/st26.pdf old mode 100644 new mode 100755 diff --git a/slides/st26.svg b/slides/st26.svg old mode 100644 new mode 100755 diff --git a/slides/st2a.svg b/slides/st2a.svg old mode 100644 new mode 100755 diff --git a/slides/st3.pdf b/slides/st3.pdf old mode 100644 new mode 100755 diff --git a/slides/st3.svg b/slides/st3.svg old mode 100644 new mode 100755 diff --git a/slides/st31a.pdf b/slides/st31a.pdf old mode 100644 new mode 100755 diff --git a/slides/st31a.svg b/slides/st31a.svg old mode 100644 new mode 100755 diff --git a/slides/st31b.pdf b/slides/st31b.pdf old mode 100644 new mode 100755 diff --git a/slides/st31b.svg b/slides/st31b.svg old mode 100644 new mode 100755 diff --git a/slides/st31c.pdf b/slides/st31c.pdf old mode 100644 new mode 100755 diff --git a/slides/st31c.svg b/slides/st31c.svg old mode 100644 new mode 100755 diff --git a/slides/st31d.pdf b/slides/st31d.pdf old mode 100644 new mode 100755 diff --git a/slides/st31d.svg b/slides/st31d.svg old mode 100644 new mode 100755 diff --git a/slides/st31dd.pdf b/slides/st31dd.pdf old mode 100644 new mode 100755 diff --git a/slides/st31dd.svg b/slides/st31dd.svg old mode 100644 new mode 100755 diff --git a/slides/st31e.pdf b/slides/st31e.pdf old mode 100644 new mode 100755 diff --git a/slides/st31e.svg b/slides/st31e.svg old mode 100644 new mode 100755 diff --git a/slides/st31f.pdf b/slides/st31f.pdf old mode 100644 new mode 100755 diff --git a/slides/st31f.svg b/slides/st31f.svg old mode 100644 new mode 100755 diff --git a/slides/st31g.pdf b/slides/st31g.pdf old mode 100644 new mode 100755 diff --git a/slides/st31g.svg b/slides/st31g.svg old mode 100644 new mode 100755 diff --git a/slides/st4.pdf b/slides/st4.pdf old mode 100644 new mode 100755 diff --git a/slides/st4.svg b/slides/st4.svg old mode 100644 new mode 100755 diff --git a/slides/st5.pdf b/slides/st5.pdf old mode 100644 new mode 100755 diff --git a/slides/st5.svg b/slides/st5.svg old mode 100644 new mode 100755 diff --git a/slides/st6.pdf b/slides/st6.pdf old mode 100644 new mode 100755 diff --git a/slides/st6.svg b/slides/st6.svg old mode 100644 new mode 100755 diff --git a/slides/st6a.pdf b/slides/st6a.pdf old mode 100644 new mode 100755 diff --git a/slides/st6a.svg b/slides/st6a.svg old mode 100644 new mode 100755 diff --git a/slides/st6b.pdf b/slides/st6b.pdf old mode 100644 new mode 100755 diff --git a/slides/st6b.svg b/slides/st6b.svg old mode 100644 new mode 100755 diff --git a/slides/st6c.pdf b/slides/st6c.pdf old mode 100644 new mode 100755 diff --git a/slides/st6c.svg b/slides/st6c.svg old mode 100644 new mode 100755 diff --git a/slides/st6d.pdf b/slides/st6d.pdf old mode 100644 new mode 100755 diff --git a/slides/st6d.svg b/slides/st6d.svg old mode 100644 new mode 100755 diff --git a/slides/st6e.pdf b/slides/st6e.pdf old mode 100644 new mode 100755 diff --git a/slides/st6e.svg b/slides/st6e.svg old mode 100644 new mode 100755 diff --git a/slides/st6f.pdf b/slides/st6f.pdf old mode 100644 new mode 100755 diff --git a/slides/st6f.svg b/slides/st6f.svg old mode 100644 new mode 100755 diff --git a/slides/st7.pdf b/slides/st7.pdf old mode 100644 new mode 100755 diff --git a/slides/st7.svg b/slides/st7.svg old mode 100644 new mode 100755 diff --git a/slides/st8.pdf b/slides/st8.pdf old mode 100644 new mode 100755 diff --git a/slides/st8.svg b/slides/st8.svg old mode 100644 new mode 100755 diff --git a/slides/st9.pdf b/slides/st9.pdf old mode 100644 new mode 100755 diff --git a/slides/st9.svg b/slides/st9.svg old mode 100644 new mode 100755 diff --git a/slides/stg-1.pdf b/slides/stg-1.pdf old mode 100644 new mode 100755 diff --git a/slides/stg-1.svg b/slides/stg-1.svg old mode 100644 new mode 100755 diff --git a/slides/stg-2.pdf b/slides/stg-2.pdf old mode 100644 new mode 100755 diff --git a/slides/stg-2.svg b/slides/stg-2.svg old mode 100644 new mode 100755 diff --git a/slides/stg-3.pdf b/slides/stg-3.pdf old mode 100644 new mode 100755 diff --git a/slides/stg-3.svg b/slides/stg-3.svg old mode 100644 new mode 100755 diff --git a/slides/stg-4.pdf b/slides/stg-4.pdf old mode 100644 new mode 100755 diff --git a/slides/stg-4.svg b/slides/stg-4.svg old mode 100644 new mode 100755 diff --git a/slides/stg-5.pdf b/slides/stg-5.pdf old mode 100644 new mode 100755 diff --git a/slides/stg-5.svg b/slides/stg-5.svg old mode 100644 new mode 100755 diff --git a/slides/stg-6.pdf b/slides/stg-6.pdf old mode 100644 new mode 100755 diff --git a/slides/stg-6.svg b/slides/stg-6.svg old mode 100644 new mode 100755 diff --git a/slides/stg-7.pdf b/slides/stg-7.pdf old mode 100644 new mode 100755 diff --git a/slides/stg-7.svg b/slides/stg-7.svg old mode 100644 new mode 100755 diff --git a/slides/stg-8.pdf b/slides/stg-8.pdf old mode 100644 new mode 100755 diff --git a/slides/stg-8.svg b/slides/stg-8.svg old mode 100644 new mode 100755 diff --git a/slides/stg-9.pdf b/slides/stg-9.pdf old mode 100644 new mode 100755 diff --git a/slides/stg31dd.svg b/slides/stg31dd.svg old mode 100644 new mode 100755 diff --git a/slides/stgall.svg b/slides/stgall.svg old mode 100644 new mode 100755 diff --git a/slides/user.svg b/slides/user.svg old mode 100644 new mode 100755 diff --git a/stoc/reviews.txt b/stoc/reviews.txt old mode 100644 new mode 100755 diff --git a/stoc/stoc.pdf b/stoc/stoc.pdf old mode 100644 new mode 100755 diff --git a/todo.txt b/todo.txt old mode 100644 new mode 100755 -- cgit v1.2.3-70-g09d2 From 656e4a1283a4e926d8b5d84eb8b702e4c7a48656 Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Sun, 22 Sep 2013 22:23:35 +0200 Subject: stintrorelated --- intro.tex | 6 +++--- related.tex | 14 ++++++-------- 2 files changed, 9 insertions(+), 11 deletions(-) diff --git a/intro.tex b/intro.tex index 166f07e..da38f8f 100755 --- a/intro.tex +++ b/intro.tex @@ -23,15 +23,15 @@ However, we are not aware of a principled study of this setting from a strategic % When subjects are strategic, they may have an incentive to misreport their cost, leading to the need for a sophisticated choice of experiments and payments. Arguably, user incentiviation is of particular pertinence due to the extent of statistical analysis over user data on the Internet. %, which has led to the rise of several different research efforts in studying data markets \cite{...}. -Our contributions are as follows. \emph{(1)} We initiate the study of experimental design in the presence of a budget and strategic subjects. +Our contributions are as follows. \emph{First}, we initiate the study of experimental design in the presence of a budget and strategic subjects. %formulate the problem of experimental design subject to a given budget, in the presence of strategic agents who may lie about their costs. %In particular, we focus on linear regression. This is naturally viewed as a budget feasible mechanism design problem, in which the objective function %is sophisticated and %is related to the covariance of the $x_i$'s. In particular, we formulate the {\em Experimental Design Problem} (\SEDP) as follows: the experimenter \E\ wishes to find a set $S$ of subjects to maximize -\begin{align}V(S) = \log\det\Big(I_d+\sum_{i\in S}x_i\T{x_i}\Big) \label{obj}\end{align} +\begin{align}V(S) = \log\det\Big(I_d+\textstyle\sum_{i\in S}x_i\T{x_i}\Big) \label{obj}\end{align} subject to a budget constraint $\sum_{i\in S}c_i\leq B$, where $B$ is \E's budget. When subjects are strategic, the above problem can be naturally approached as a \emph{budget feasible mechanism design} problem, as introduced by \citeN{singer-mechanisms}. %, and other {\em strategic constraints} we don't list here. -The objective function, which is the key, is formally obtained by optimizing the information gain in $\beta$ when the latter is learned through ridge regression, and is related to the so-called $D$-optimality criterion~\cite{pukelsheim2006optimal,atkinson2007optimum}. \emph{(2)} We present a polynomial time mechanism scheme for \SEDP{} that is approximately truthful and yields a constant factor ($\approx 12.98$) approximation to the optimal value of \eqref{obj}. %In particular, for any small $\delta>0$ and $\varepsilon>0$, we can construct a $(12.98\,,\varepsilon)$-approximate mechanism that is $\delta$-truthful and runs in polynomial time in both $n$ and $\log\log\frac{B}{\epsilon\delta}$. +The objective function, which is the key, is formally obtained by optimizing the information gain in $\beta$ when the latter is learned through ridge regression, and is related to the so-called $D$-optimality criterion~\cite{pukelsheim2006optimal,atkinson2007optimum}. \emph{Second}, we present a polynomial time mechanism scheme for \SEDP{} that is approximately truthful and yields a constant factor ($\approx 12.98$) approximation to the optimal value of \eqref{obj}. %In particular, for any small $\delta>0$ and $\varepsilon>0$, we can construct a $(12.98\,,\varepsilon)$-approximate mechanism that is $\delta$-truthful and runs in polynomial time in both $n$ and $\log\log\frac{B}{\epsilon\delta}$. In contrast to this, we show that no truthful, budget-feasible mechanisms are possible for \SEDP{} within a factor 2 approximation. We note that the objective \eqref{obj} is submodular. Using this fact, applying previous results on budget feasible mechanism design under general submodular objectives~\cite{singer-mechanisms,chen} would yield either a deterministic, truthful, constant-approximation mechanism that requires exponential time, or a non-determi\-nis\-tic, (universally) truthful, poly-time mechanism that yields a constant approximation ratio only \emph{in expectation} (\emph{i.e.}, its approximation guarantee for a given instance may in fact be unbounded). diff --git a/related.tex b/related.tex index c3d4ed6..f61db30 100755 --- a/related.tex +++ b/related.tex @@ -3,9 +3,9 @@ \junk{\subsection{Experimental Design} The classic experimental design problem, which we also briefly review in Section~\ref{sec:edprelim}, deals with which $k$ experiments to conduct among a set of $n$ possible experiments. It is a well studied problem both in the non-Bayesian \cite{pukelsheim2006optimal,atkinson2007optimum,boyd2004convex} and Bayesian setting \cite{chaloner1995bayesian}. Beyond $D$-optimality, several other objectives are encountered in the literature \cite{pukelsheim2006optimal}; many involve some function of the covariance matrix of the estimate of $\beta$, such as $E$-optimality (maximizing the smallest eigenvalue of the covariance of $\beta$) or $T$-optimality (maximizing the trace). Our focus on $D$-optimality is motivated by both its tractability as well as its relationship to the information gain. %are encountered in the literature, though they do not relate to entropy as $D$-optimality. We leave the task of approaching the maximization of such objectives from a strategic point of view as an open problem. } -\noindent\emph{Budget Feasible Mechanisms for General Submodular Functions} +\noindent\emph{Budget Feasible Mechanisms for General Submodular Functions.} Budget feasible mechanism design was originally proposed by \citeN{singer-mechanisms}. Singer considers the problem of maximizing an arbitrary submodular function subject to a budget constraint in the \emph{value query} model, \emph{i.e.} assuming an oracle providing the value of the submodular objective on any given set. - Singer shows that there exists a randomized, 112-approximation mechanism for submodular maximization that is \emph{universally truthful} (\emph{i.e.}, it is a randomized mechanism sampled from a distribution over truthful mechanisms). \citeN{chen} improve this result by providing a 7.91-approximate mechanism, and show a corresponding lower bound of $2$ among universally truthful randomized mechanisms for submodular maximization. + Singer shows that there exists a randomized, 112-approximation mechanism for submodular maximization that is \emph{universally truthful} (\emph{i.e.}, it is a randomized mechanism sampled from a distribution over truthful mechanisms). \citeN{chen} improve this result to a 7.91-approximate mechanism, and show a corresponding lower bound of $2$ among universally truthful randomized mechanisms for submodular maximization. The above approximation guarantees hold for the expected value of the randomized mechanism: for a given @@ -16,7 +16,7 @@ However, assuming access to an oracle providing the optimum in the full-information setup, Chen \emph{et al.},~propose a truthful, $8.34$-approximate mechanism; in cases for which the full information problem is NP-hard, as the one we consider here, this mechanism is not poly-time, unless P=NP. Chen \emph{et al.}~also prove a $1+\sqrt{2}$ lower bound for truthful deterministic mechanisms, improving upon an earlier bound of 2 by \citeN{singer-mechanisms}. -\noindent\emph{Budget Feasible Mechanism Design on Specific Problems} +\noindent\emph{Budget Feasible Mechanism Design on Specific Problems.} Improved bounds, as well as deterministic polynomial mechanisms, are known for specific submodular objectives. For symmetric submodular functions, a truthful mechanism with approximation ratio 2 is known, and this ratio is tight \cite{singer-mechanisms}. Singer also provides a 7.32-approximate truthful mechanism for the budget feasible version of \textsc{Matching}, and a corresponding lower bound of 2 \cite{singer-mechanisms}. Improving an earlier result by Singer, \citeN{chen} give a truthful, $2+\sqrt{2}$-approximate mechanism for \textsc{Knapsack}, and a lower bound of $1+\sqrt{2}$. Finally, a truthful, 31-approximate mechanism is also known for the budgeted version of \textsc{Coverage} \cite{singer-influence}. The deterministic mechanisms for \textsc{Knapsack} \cite{chen} and @@ -33,14 +33,14 @@ establish that it can be incorporated in the framework of %Our results therefore add \SEDP{} to the set of problems for which a deterministic, polynomial time, constant approximation mechanism is known. -\noindent\emph{Beyond Submodular Objectives} +\noindent\emph{Beyond Submodular Objectives.} Beyond submodular objectives, it is known that no truthful mechanism with approximation ratio smaller than $n^{1/2-\epsilon}$ exists for maximizing fractionally subadditive functions (a class that includes submodular functions) assuming access to a value query oracle~\cite{singer-mechanisms}. Assuming access to a stronger oracle (the \emph{demand} oracle), there exists a truthful, $O(\log^3 n)$-approximate mechanism \cite{dobz2011-mechanisms} as well as a universally truthful, $O(\frac{\log n}{\log \log n})$-appro\-xi\-mate mechanism for subadditive maximization \cite{bei2012budget}. Moreover, in a Bayesian setup, assuming a prior distribution among the agent's costs, there exists a truthful mechanism with a 768/512-approximation ratio \cite{bei2012budget}. %(in terms of expectations) Posted price, rather than direct revelation mechanisms, are also studied in \cite{singerposted}. -\noindent\emph{Monotone Approximations in Combinatorial Auctions} +\noindent\emph{Monotone Approximations in Combinatorial Auctions.} Relaxations of combinatorial problems are prevalent in \emph{combinatorial auctions}, % \cite{archer-approximate,lavi-truthful,dughmi-truthful,briest-approximation}, in which an auctioneer aims at maximizing a set function which is the sum of utilities of strategic bidders (\emph{i.e.}, the social welfare). As noted by \citeN{archer-approximate}, @@ -51,7 +51,6 @@ which is \emph{truthful-in-expectation}. %and in high probability. \citeN{lavi-truthful} construct randomized truthful-in-expectation mechanisms for several combinatorial auctions, improving the approximation ratio in \cite{archer-approximate}, by treating the fractional solution of an LP as a probability distribution from which they sample integral solutions. - Beyond LP relaxations, \citeN{dughmi2011convex} propose truthful-in-expectation mechanisms for combinatorial auctions in which @@ -59,10 +58,9 @@ the bidders' utilities are matroid rank sum functions (applied earlier to the \t on solving a convex optimization problem which can only be solved approximately. As in \cite{lavi-truthful}, they also treat the fractional solution as a distribution over which they sample integral solutions. The authors ensure that a solver is applied to a ``well-conditioned'' problem, which resembles the technical challenge we face in Section~\ref{sec:monotonicity}. However, we seek a deterministic mechanism and $\delta$-truthfulness, not truthfulness-in-expectation. In addition, our objective is not a matroid rank sum function. As such, both the methodology for dealing with problems that are not ``well-conditioned'' as well as the approximation guarantees of the convex relaxation in \cite{dughmi2011convex} do not readily extend to \EDP. - \citeN{briest-approximation} construct monotone FPTAS for problems that can be approximated through rounding techniques, which in turn can be used to construct truthful, deterministic, constant-approximation mechanisms for corresponding combinatorial auctions. \EDP{} is not readily approximable through such rounding techniques; as such, we rely on a relaxation to approximate it. -\noindent\emph{$\delta$-Truthfulness and Differential Privacy} +\noindent\emph{$\delta$-Truthfulness and Differential Privacy.} The notion of $\delta$-truthfulness has attracted considerable attention recently in the context of differential privacy (see, \emph{e.g.}, the survey by \citeN{pai2013privacy}). \citeN{mcsherrytalwar} were the first to observe that any $\epsilon$-differentially private mechanism must also be $\delta$-truthful in expectation, for $\delta=2\epsilon$. This property was used to construct $\delta$-truthful (in expectation) mechanisms for a digital goods auction~\cite{mcsherrytalwar} and for $\alpha$-approximate equilibrium selection \cite{kearns2012}. \citeN{approximatemechanismdesign} propose a framework for converting a differentially private mechanism to a truthful-in-expectation mechanism by randomly selecting between a differentially private mechanism with good approximation guarantees, and a truthful mechanism. They apply their framework to the \textsc{FacilityLocation} problem. We depart from the above works in seeking a deterministic mechanism for \EDP, and using a stronger notion of $\delta$-truthfulness. -- cgit v1.2.3-70-g09d2 From fc56a8f69d6eaeaecacdd4fdfa40df7e3d16599d Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Sun, 22 Sep 2013 22:41:24 +0200 Subject: space saving --- approximation.tex | 4 ++-- problem.tex | 22 +++++++++++----------- 2 files changed, 13 insertions(+), 13 deletions(-) diff --git a/approximation.tex b/approximation.tex index cc278e1..1b94615 100755 --- a/approximation.tex +++ b/approximation.tex @@ -47,7 +47,7 @@ expectation of $V$ under the distribution $P_\mathcal{N}^\lambda$: F(\lambda) \defeq \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\big[V(S)\big] % = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) V(S) -= \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\left[ \log\det\left( I_d + \sum_{i\in S} x_i\T{x_i}\right) \right],\quad \lambda\in[0,1]^n. += \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\big[ \log\det\big( I_d + \textstyle\sum_{i\in S} x_i\T{x_i}\big) \big],\quad \lambda\in[0,1]^n. \end{equation} Function $F$ is an extension of $V$ to the domain $[0,1]^n$, as it equals $V$ on integer inputs: $F(\id_S) = V(S)$ for all $S\subseteq\mathcal{N}$, where $\id_S$ denotes the indicator vector of $S$. %\citeN{pipage} have shown how to use this extension to obtain approximation guarantees for an interesting class of optimization problems through the \emph{pipage rounding} framework, which has been successfully applied in \citeN{chen, singer-influence}. @@ -56,7 +56,7 @@ multi-linear extension \eqref{eq:multi-linear} cannot be optimized in polynomial time for the value function $V$ we study here, given by \eqref{modified}. Hence, we introduce an extension $L:[0,1]^n\to\reals$ s.t.~ \begin{equation}\label{eq:our-relaxation} L(\lambda) \defeq -\log\det\left(I_d + \sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\right), +\log\det\big(I_d + \textstyle\sum_{i\in\mathcal{N}} \lambda_i x_i\T{x_i}\big), %= \log\det\left(\mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\bigg[I_d + \sum_{i\in S} x_i\T{x_i} \bigg]\right), \quad \lambda\in[0,1]^n. \end{equation} diff --git a/problem.tex b/problem.tex index 798e69a..0e9c75f 100755 --- a/problem.tex +++ b/problem.tex @@ -35,8 +35,8 @@ maximum a posteriori estimation leads to the following maximization \cite{hastie}: \begin{align} \begin{split} - \hat{\beta} = \argmax_{\beta\in\reals^d} \prob(\beta\mid y_S) - &=\argmin_{\beta\in\reals^d} \big(\sum_{i\in S} (y_i - \T{\beta}x_i)^2 + \hat{\beta} = \textstyle\argmax_{\beta\in\reals^d} \prob(\beta\mid y_S) + &=\textstyle\argmin_{\beta\in\reals^d} \big(\textstyle\sum_{i\in S} (y_i - \T{\beta}x_i)^2 + \T{\beta}R\beta\big)\\ & = (R+\T{X_S}X_S)^{-1}X_S^Ty_S \label{ridge} \end{split} @@ -64,7 +64,7 @@ Under the linear model, and the Gaussian prior, the information gain takes the f \begin{align} I(\beta;y_S)&= \frac{1}{2}\log\det(R+ \T{X_S}X_S) - \frac{1}{2}\log\det R\label{dcrit} %\\ \end{align} -Maximizing $I(\beta;y_S)$ is therefore equivalent to maximizing $\log\det(R+ \T{X_S}X_S)$, which is known in the experimental design literature as the Bayes +Maximizing $I(\beta;y_S)$ is therefore equivalent to maximizing $\log\det(R+ \T{X_S}X_S)$, which is known in literature as the Bayes $D$-optimality criterion \cite{pukelsheim2006optimal,atkinson2007optimum,chaloner1995bayesian}. @@ -104,18 +104,18 @@ The cost $c_i$ can capture, \emph{e.g.}, the amount the subject $i$ deems suffic \medskip\\\hspace*{\stretch{1}}\textsc{ExperimentalDesignProblem} (\EDP)\hspace*{\stretch{1}} \begin{subequations} \begin{align} -\text{Maximize}\quad V(S) &= \log\det(I_d+\T{X_S}X_S) \label{modified} \\ -\text{subject to}\quad \sum_{i\in S} c_i&\leq B\label{lincon} +\text{Maximize}\quad &V(S) = \log\det(I_d+\T{X_S}X_S) \label{modified} \\ +\text{subject to}\quad &\textstyle\sum_{i\in S} c_i\leq B\label{lincon} \end{align}\label{edp} \end{subequations} \emph{W.l.o.g.}, we assume that $c_i\in [0,B]$ for all $i\in \mathcal{N}$, as no $i$ with $c_i>B$ can be in an $S$ satisfying \eqref{lincon}. Denote by \begin{equation}\label{eq:non-strategic} - OPT = \max_{S\subseteq\mathcal{N}} \Big\{V(S) \;\Big| \; - \sum_{i\in S}c_i\leq B\Big\} + OPT = \textstyle\max_{S\subseteq\mathcal{N}} \big\{V(S) \;\Big| \; + \textstyle \sum_{i\in S}c_i\leq B\big\} \end{equation} the optimal value achievable in the full-information case. \EDP{}, as defined above, is NP-hard; to see this, note that \textsc{Knapsack} -reduces to EDP with dimension $d=1$ by mapping the weight of each item, say, +reduces to EDP with $d=1$ by mapping the weight of each item, say, $w_i$, to an experiment with $x_i^2=w_i$.% Moreover, \eqref{modified} is submodular, monotone and satisfies $V(\emptyset) = 0$. The value function \eqref{modified} has the following properties, which are proved in Appendix~\ref{app:properties}. First, it is non-negative, \emph{i.e.}, $V(S)\geq 0$ @@ -149,13 +149,13 @@ yields an approximation ratio of $\frac{5 e }{e-1}~$\cite{singer-mechanisms}; t \subsection{Budget-Feasible Experimental Design: Strategic Case} -We study the following \emph{strategic} setting, in which the costs $c_i$ are {\em not} common knowledge and their reporting can be manipulated by the experiment subjects. The latter are strategic and wish to maximize their utility, which is the difference of the payment they receive and their true cost. We note that, though subjects may misreport $c_i$, they cannot lie about $x_i$ (\emph{i.e.}, all public features are verifiable prior to the experiment) nor $y_i$ (\emph{i.e.}, the subject cannot falsify her measurement). -In this setting, experimental design reduces to a \emph{budget feasible reverse auction}, as introduced by \citeN{singer-mechanisms}; we review the formal definition in Appendix~\ref{app:budgetfeasible}. In short, given a budget $B$ and a value function $V:2^{\mathcal{N}}\to\reals_+$, a \emph{reverse auction mechanism} $\mathcal{M} = (S,p)$ comprises (a) an \emph{allocation function} $S:\reals_+^n \to 2^\mathcal{N}$, determining the set +We study the following \emph{strategic} setting, in which the costs $c_i$ are {\em not} common knowledge and their reporting can be manipulated by the experiment subjects. The latter are strategic and wish to maximize their utility, which is the difference of the payment they receive and their true cost. Note that, though subjects may misreport $c_i$, they cannot lie about $x_i$ (\emph{i.e.}, all public features are verifiable prior to the experiment) nor $y_i$ (\emph{i.e.}, the subject cannot falsify her measurement). +Experimental design thus reduces to a \emph{budget feasible reverse auction}, as introduced by \citeN{singer-mechanisms}; we review the formal definition in Appendix~\ref{app:budgetfeasible}. In short, given a budget $B$ and a value function $V:2^{\mathcal{N}}\to\reals_+$, a \emph{reverse auction mechanism} $\mathcal{M} = (S,p)$ comprises (a) an \emph{allocation function} $S:\reals_+^n \to 2^\mathcal{N}$, determining the set of experiments to be purchased, and (b) a \emph{payment function} $p:\reals_+^n\to \reals_+^n$, determining the payments $[p_i(c)]_{i\in \mathcal{N}}$ received by experiment subjects. We seek mechanisms that are \emph{normalized} (unallocated experiments receive zero payments), \emph{individually rational} (payments for allocated experiments exceed costs), have \emph{no positive transfers} (payments are non-negative), and are \emph{budget feasible} (the sum of payments does not exceed the budget $B$). -We relax the notion of truthfulness to \emph{$\delta$-truthfulness}, requiring that reporting one's true cost is an \emph{almost-dominant} strategy: no subject increases their utility by reporting a cost that differs more than $\delta>0$ from their true cost. Under this definition, a mechanism is truthful if $\delta=0$. +We relax the notion of truthfulness to \emph{$\delta$-truthfulness}, requiring that reporting one's true cost is an \emph{almost-dominant} strategy: no subject increases their utility by reporting a cost that differs more than $\delta>0$ (\emph{e.g.}, a tenth of a cent) from their true cost. Under this definition, a mechanism is truthful if $\delta=0$. In addition, we would like the allocation $S(c)$ to be of maximal value; however, $\delta$-truthfulness, as well as the hardness of \EDP{}, preclude achieving this goal. Hence, we seek mechanisms with that are \emph{$(\alpha,\beta)$-approximate}, \emph{i.e.}, there exist $\alpha\geq 1$ and $\beta>0$ s.t.~$OPT \leq \alpha V(S(c))+\beta$, and are \emph{computationally efficient}, in that $S$ and $p$ can be computed in polynomial time. We note that the constant approximation algorithm \eqref{eq:max-algorithm} breaks -- cgit v1.2.3-70-g09d2